Re: Message threading

[PotPieMan]

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