For my PerlMonks::NewestNodes
module, I used a technique very similar to the one described
by mikfire. All the nodes are stored in a hash indexed by
node ID, and each element is a hash reference containing the
different pieces of information about the node.
in reply to threaded display of replies
subroutine receives as argument a list of nodes to thread
(this allows adding new nodes to the existing structure without
rethreading everything). Then it goes through those nodes, and
for each one it visits its parent and inserts its ID into
the parent's "kids" element, which is an array ordered
chronologically. Nodes that do not have a parent_node element
are marked as "top nodes".
This is complicated a little bit by the fact that the
Newest Nodes XML Generator will give you a node, but
not its parent, when the parent is already marked as seen.
So the thread subroutine also checks to see which nodes
it doesn't have yet, and adds those to a list of "nodes to
get". The nodes without parents are added to a list of
"nodes to rethread". Nodes that are threaded correctly are
removed from the list. At the end, any necessary nodes are
grabbed (using the Node Query XML Generator, you pass it
an argument of the form "nodes=id1,id2,..."), added to the
list, and the loop repeats.
Once every node has its kids element properly populated, it's
just a matter of descending recursively from each "top node"
to generate its tree of replies.
Shameless plug: check out Shendal's Perl/Tk Newest Nodes Client,
which uses my module to show you a very nice threaded display
of the Newest Nodes.