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

I am printing a tree based on the contents of an array, where each element has id,name,parentID, and level, where level is the depth of the item in the tree. i.e.: 
foo
->bar
-->troz
->narf

[download]
where foo is level0, bar is level1 with parent foo, narf is level 1 with parent foo, and troz is level 2 with parent bar. The array is created by 
$item{id} = $id;
$item{name} = $name;
$item{level} = $level;
$item{parent} = $parent;
push @list, \%item;

[download]
how can I sort @list so that it will print out in the correct tree order? it can be arbitrary depth and the goal is to avoid recursion, both in creating the list and displaying the list. My attempts with an ST and various other closures have failed to create the correct ordering, so far the only successful algorithm involves creating the list via recursion, or building an HoH and recursing over it to build the display, but that doesn't scale very nicely.

Replies are listed 'Best First'.
Re: group based array sort
by Trimbach (Curate) on Feb 19, 2004 at 20:07 UTC
    Unless you're intent on reinventing the wheel, something like Sort::Tree looks like it does what you want.

    Gary Blackburn
    Trained Killer

[reply]
Re: group based array sort
by artist (Parson) on Feb 19, 2004 at 20:23 UTC
    Assuming you have data in given format. It would be easy to remember the parent. You don't need recursion in that case. You don't even need to mention the name of the parent. In the ouptut, you are given the order,level and parent information. Which you can format the way you like. 
    use strict;
use warnings;
my %Entry;
$Entry{-1} = '';
my @list;
my $id;
while(<DATA>){
  chomp;
  last if /OUTPUT/;
  my $entry = $1 if /\b(\w+)$/;
  my $level = () = $_ =~ m[\-]g;
  my $item;
  $Entry{$level} = $entry; #Remember the last entry
  $item->{id} = ++$id;
  $item->{name} = $entry;
  $item->{parent} = $Entry{$level-1};
  $item->{level} = $level;
  push @list,$item;
}
foreach my $item (@list){
  print join "|", map { $item->{$_} } qw(id level name parent);
  print "\n";

}

__DATA__
foo
->bar
-->troz
->narf
__OUTPUT__
1|0|foo|
2|1|bar|foo
3|2|troz|bar
4|1|narf|foo

    [download]
[reply]
[d/l]
      that's good and fine if the data came in the sorted tree order, which it doesn't in my situation. :-) think like pulling from a database, where the order is unknown and i'm not allowed to do ORDER BY in my sql.
[reply]
        bageler,
        While I really think using Sort::Tree is probably the best option, here is a purely iterative solution. It has the following requirements:
      • IDs will always be numerical
      • Root level nodes will always have a parent of 0
      • Probably a few others
        Read more... (2 kB)
        Cheers - L~R
[reply]
[d/l]
Re: group based array sort
by Limbic~Region (Chancellor) on Feb 19, 2004 at 19:55 UTC
    bageler,
    I am pretty sure this is easier than it sounds. You have an AoH and want to sort it based off one of the hash values. Try the following code and see if it does what you want: 
    @list = sort { $a->{level} <=> $b->{level} } @list;
# Print code goes here

    [download]
    Cheers - L~R

    Update: After re-reading your problem I realized the issue is not in the sorting but in the printing, which I conveniently left out. Since a great solution has already been provided below, I will only point to my iterative solution by using a stack.

[reply]
[d/l]
      bageler seems to be looking for something more complicated that that, I'm afraid - that would simply give 
      foo
->bar
->narf
-->trof
-->etc.

      [download]
      I don't know if this is possible without recursion...being lazy, I'd personally use a recursive "GetChildren($id)" routine which greps for the parent $id and pushes the returned list onto itself - terribly inefficient (as you'd be grepping the list for every element), but easier to code :)

      Cheers,
      Ben.
[reply]
[d/l]
Re: group based array sort
by ysth (Canon) on Feb 19, 2004 at 21:03 UTC
    I'm not sure why you say "that doesn't scale very nicely". Doing the moral equivalent of building the HoH is going to be necessary to do anything tree-like with that data structure.

    It's fairly trivial, anyway; but you've not said what the difference between id and name is...which is foo,bar,troz,narf in your example, and what is the other?

[reply]

Back to Seekers of Perl Wisdom