Having just the message's parent ID is indeed enough to thread messages in this manner. I have implemented an algorithm to do this in Perl and Java using a stack to simulate recursion (for walking the tree).

The basic algorithm is as follows:

1. Seed the stack with all top level messages, i.e. those with parent ID equal to zero. Initialize the level of each of these messages as zero.
2. While the stack still has messages, perform the following steps
   1. Pop a message off the stack.
   2. Display the message at the appropriate level.
   3. Get all messages which are children of the current message and put them onto the stack with the level equal to one more than the current message's level.

That's it! The tree is constructed "on the fly" through the simulated recursion.

There are a few drawbacks to this algorithm:

• Sorting becomes fairly difficult. If you want to display the most recent message first, you actually have to sort the data in ascending order of date. This occurs because of the tail recursion used in the algorithm (I believe - please correct me if I am wrong).
• You have to be clever with how you display a message. You know the level, as determined by the algorithm, but indentation can sometimes be difficult.
• The algorithm is easy to use with SQL databases, but not as easy to use with other data sources.

It's also important to note that the way this algorithm seeds the stack is its only way to avoid getting thrown into an infinite loop. You could create two messages, each with the parent ID pointing to the other, but they will not be displayed because there is no way to reach them from the top-level (parent ID equal to zero) nodes. At least, I hope so - I haven't found a way to break it. (Please let me know if you see a fault in this.)

Jamie Zawinski's algorithm is much more robust in the places where this one is not. If you have the time, you should definitely implement that one. :-)

--PotPieMan

---

---

Posts are HTML formatted. Put <p> </p> tags around your paragraphs. Put <code> </code> tags around your code and data!

Titles consisting of a single word are discouraged, and in most cases are disallowed outright.

Read Where should I post X? if you're not absolutely sure you're posting in the right place.

Please read these before you post! —

• How do I compose an effective node title?
• How do I post a question effectively?
• Markup in the Monastery

Posts may use any of the Perl Monks Approved HTML tags:

a, abbr, b, big, blockquote, br, caption, center, col, colgroup, dd, del, details, div, dl, dt, em, font, h1, h2, h3, h4, h5, h6, hr, i, ins, li, ol, p, pre, readmore, small, span, spoiler, strike, strong, sub, summary, sup, table, tbody, td, tfoot, th, thead, tr, tt, u, ul, wbr

You may need to use entities for some characters, as follows. (Exception: Within code tags, you can put the characters literally.)

	For:		Use:
	&		&
	<		&lt;
	>		&gt;
	[		&#91;
	]		&#93;

Link using PerlMonks shortcuts! What shortcuts can I use for linking?

See Writeup Formatting Tips and other pages linked from there for more info.