My idea would be to have the primary data structure look something like this and keyed by the node id.

my %created = ( AUTHOR => $author,
                TYPE   => $node_type,
                TIME   => $node_time,
                PARENT => $parent_id || '',
                KIDS   => [],
              );
[download]

for my $root ( sort { $a <=> $b } keys %created ) {
   my $parent = $created{$root}{PARENT};
   push @{$created{$parent}{KIDS}}, $root;
}
[download]

sub print_nodes {
   my @kids = @_;

   for my $id ( @nodes ) {
      print "Interesting data from node\n";
      if ( @{$created{$id}{KIDS} ) {
         print_nodes( @{$created{$id}{KIDS};
      }
      
   }
}

# Some work to make sure we start at the parents and move
# our way down correctly.  grep would work just as well.
my @topnodes = ();
for my $id ( keys %created ) {
   push @topnodes, $id unless ( defined( $created{$id}{PARENT} ) );
}

print_nodes( @topnodes );
[download]

However, and where it will get messy, is to take the child node, find it's parent (and all nodes in between), then increament on the node number starting with the ultimate parent node; if the parent of that node is one that is in the thread already, add it to the thread. This will get trees like:

P
+--1
   +--2
   +--3
      +--4
         +--5  <- the current node
+--6
   +--7
   +--8
[download]

The thread 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.

--ZZamboni

Cases like this aside, though, it'd be a welcome addition.

---
A fair fight is a sign of poor planning.

Sprad, if you look at the XML stream, the parent node id is included probably to avoid exactly this issue.

mikfire

well, each node should be represented by a node_id in a DB or whatever file U use and this should know (store) the id of its parent, so you can't mess up things. And btw, there is no need to let anode know if it has children or not. If there are children THEY WILL KNOW their parent. Keep it simple: stupid. :-)
btw BmeCat works this way and made it to a standard.

Have a nice day
All decision is left to your taste

so said little:

And btw, there is no need to let anode [sic] know if it has children or not. If there are children THEY WILL KNOW their parent.

Unless, of course, you want to find all the children of a particular node without doing an exhaustive search of the DB. While not strictly necessary, it can make life simpler in some cases. I think this application might qualify as one of those cases (see Masem's reply). :-)

bbfu
Seasons don't fear The Reaper.
Nor do the wind, the sun, and the rain.
We can be like they are.