|Pathologically Eclectic Rubbish Lister
Re: Message threadingby PotPieMan (Hermit)
|on Jun 21, 2003 at 20:55 UTC
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:
That's it! The tree is constructed "on the fly" through the simulated recursion.
There are a few drawbacks to this algorithm:
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. :-)