BMaximus has asked for the wisdom of the Perl Monks concerning the following question:

In a couple of threads there was a discussion on what was best to store messages in a database like MySQL. One of the threads said that the messages should be given a thread id and also have the parent child scheme implemented. The thread id is for fast retrieval and then the messages be sorted out by thread in the program so as not to put stress on the database. The other way is basically to recursively query the database for the children of a parent. Get the parent message and then query for its children and then query for their children ad infinitum and due to the recursion unraveling at the end the messages should be in the correct order.


I've tried to figure out how to sort out the messages without using a recursive way and by retrieveing the messages by thread id and then sorting them to get the correct order for the threads. However the answer eludes me. Is there a way to use sort to get the messages in the correct order for threading?
my $testarray = [ { messageId => 1, parent => 1 }, { messageId => 2, parent => 1 }, { messageId => 3, parent => 1 }, { messageId => 4, parent => 2 }, { messageId => 5, parent => 3 }, { messageId => 6, parent => 2 }, { messageId => 7, parent => 4 } ];
What I'm trying to get from
messageId parent
1          1
2          1
3          1
4          2
5          3
6          2
7          4

to
1          1
2          1
4          2
7          4
6          2
3          1
5          3

Can anyone offer a nudge in the right direction for this please?

My thanks for helping me keep my hair,

BMaximus

Replies are listed 'Best First'.
Re: Sorting an Array of Hashes (AoH) by its keys as a threaded message
by davorg (Chancellor) on Feb 19, 2002 at 11:17 UTC

    Sound like you want to sort by parent and then by message ID. Something like this will work:

    my @sorted = sort { $a->{parent} <=> $b->{parent} || $a->{messageId} <=> $b->{messageId} } @$testarray; foreach (@sorted) { print "$_->{messageId}\t$_->{parent}\n"; }
    --
    <http://www.dave.org.uk>

    "The first rule of Perl club is you do not talk about Perl club."
    -- Chip Salzenberg

(crazyinsomniac) Re: Sorting an Array of Hashes (AoH) by its keys as a threaded message
by crazyinsomniac (Prior) on Feb 19, 2002 at 12:42 UTC
    A nudge, a push, a kick, it's all good ;D
    #!/usr/bin/perl -wl use strict; ## consider this a better way to go ## let %NODE be the representation of a typical record ## and in this case, our initial thread (aka a "root" node) my %THREAD= ( node_id => 1, root_id => 0, # 0 is the node_id of 'FooStuff', a "sect +ion" parent_id => 0, # well the parent of a "root" node is a +section content => "how do I echo a value to the screen?", title => "How do I echo a value to the screen?", ,); ## at this point you've *selected* all nodes whose parent ## is %THREAD, ie, node_id => 1 ## see, no need for recursive calls to the database ## it might be worth having a 'section' attribute ## if you want to be able to search through threads based on section my @NODES = ( \%THREAD, # therad is #1 { node_id => 2, root_id => 1, parent_id => 1, content => "i dunno", title => "re: How do I echo a value to the screen?" }, { node_id => 3, root_id => 1, parent_id => 1, content => "well you use the function print", title => "re: How do I echo a value to the screen?" }, { node_id => 6, root_id => 1, parent_id => 2, content => "don't say that", title => "re: re: How do I echo a value to the screen?" }, { node_id => 9, root_id => 1, parent_id => 6, content => "you guys are dumb", title => "re: re: re: How do I echo a value to the screen?" }, ,); print_kids(\%THREAD, 1, @NODES); exit; # not the most efficient, but it will do # (you're welcome to make with the improvements as always) sub print_kids { my ($NODE, $t, @NODES) = @_; for my $ix(0..scalar @NODES) { next unless exists $NODES[$ix]->{parent_id}; # due to sideffect of splice if( $$NODE{node_id} == $NODES[$ix]->{parent_id} ) { print "$t) ", " " x (4 * $t ), "( $NODES[$ix]->{node_id} ) ", $NODES[$ix]->{title}, "\n>>>>>>>>", ">" x (4 * $t ), " $NODES[$ix]->{content}\n"; my $N = splice(@NODES,$ix,1); print_kids($N, $t+1, @NODES); } elsif( $$NODE{node_id} == $NODES[$ix]->{node_id} ) { print "0) ", "( $NODES[$ix]->{node_id} ) ", $NODES[$ix]->{title}, "\n>>>>>>>>", ">" x (4 * $t ), " $NODES[$ix]->{content}\n"; my $N = splice(@NODES,$ix,1); print_kids($N, 1, @NODES); } } return undef; } __END__ $>perl thread.txt.pl 0) ( 1 ) How do I echo a value to the screen? >>>>>>>>>>>> how do I echo a value to the screen? 1) ( 2 ) re: How do I echo a value to the screen? >>>>>>>>>>>> i dunno 2) ( 6 ) re: re: How do I echo a value to the screen? >>>>>>>>>>>>>>>> don't say that 3) ( 9 ) re: re: re: How do I echo a value to the screen? >>>>>>>>>>>>>>>>>>>> you guys are dumb 1) ( 3 ) re: How do I echo a value to the screen? >>>>>>>>>>>> well you use the function print

     
    ______crazyinsomniac_____________________________
    Of all the things I've lost, I miss my mind the most.
    perl -e "$q=$_;map({chr unpack qq;H*;,$_}split(q;;,q*H*));print;$q/$q;"

      But the request specifically stated 'non-recursive' meaning this solution is not what was required.

      rdfield

        No recursive calls to a database. This one clearly doesn't recursively call to a database.

        BMaximus
Re: Sorting an Array of Hashes (AoH) by its keys as a threaded message
by rdfield (Priest) on Feb 19, 2002 at 11:22 UTC
    This code does what you need, other than the fact that the children of a message aren't guaranteed to be in any particular order:
    my $testarray = [ { messageId => 1, parent => 1 }, { messageId => 2, parent => 1 }, { messageId => 3, parent => 1 }, { messageId => 4, parent => 2 }, { messageId => 5, parent => 3 }, { messageId => 6, parent => 2 }, { messageId => 7, parent => 4 } ]; #wander down array, setting "children" field foreach my $key (@$testarray) { next if ($key->{parent} eq $key->{messageId}); # skip root nodes push @{$$testarray[$key->{parent} - 1]->{children}}, $key->{message +Id}; # messageIds are 1-relative, arrays are 0-relative } # build up a sorted array of elements... my @newstack; # a. retrieve each element in turn foreach my $message (@$testarray) { # b. if parent = messageid, push onto new stack, and go back to the be +ginning if ($message->{parent} eq $message->{messageId}) { push @newstack,$message; next; } # c. insert it into the new stack, just after the parent for (my $loop = scalar(@newstack) - 1;$loop >= 0;$loop--) { #d. if the last element IS the parent, just push it and move on if ($newstack[$loop]->{messageId} eq $message->{parent}) { push @newstack,$message; $loop = -1; next; } #e. move the stack down a place $newstack[$loop + 1] = $newstack[$loop]; #f. insert new value, if appropriate and trip out of loop if ($newstack[$loop - 1]->{messageId} == $message->{parent}) { $newstack[$loop] = $message; $loop = -1; } } } #print the results print "Message\tParent\n"; print $_->{messageId} . "\t" . $_->{parent} . "\n" for @newstack;

    produces the results:

    Message Parent 1 1 3 1 5 3 2 1 6 2 4 2 7 4

    rdfield

    update of course you could always retrieve the messages from the database in the correct order in the first place:

    select messageId,parent from messages start with messageId = 1 connect by prior messageId = parent