-- Randal L. Schwartz, Perl hacker

I would suggest that you parse 'treepaths' into a true tree datastructure of some kind (either nested Objects, or a simple hash of hashes). Once you have that, rendering tree's in the way you describe becomes extremely trivial using a recursive method which takes a "node" and a "indenting" depth as input.

They already are in a HoH structure

$page->[$id]->{'parent'} = whatever..
[download]

The 'treepath' element is just there to make sorting them a lot easier.

Since it's 'trivial' to render, perhaps you could provide an example? That would really help! Oh, and although I didn't specifiy, the graphical representation is for a web page.

thanks

cLive ;-)

Okay, a couple of things...
1. I don't really understand your example of "$page->[$id]->{'parent'}". I don't see how that's a hash of hashes.

2. I underestimated the problem, because of the "|" issue. When I've seen this problem before, the only important issues were:
   1. Nest/tab the children properly
   2. Do something special for hte first/last child
   An example of "pipeless" output is in the method "render_node_nopipe" below

3. Even with the pipes, I still think it's cleaner to use a recursive method -- BUT, instead of passing an "indent" depth, you pass an acctuall padding string, that contains the pipes. The only real new complexity is that when dealing with each node, it's not enough to know if that node is the last of it's siblings, you also have to know if it's parent was the last of it's siblings (in order to build up the padding string properly).
   An example of the recursive solution is the method "render_node" below.

4. It should be clear how to make this generate the appropriate HTML (<img src..>) output by modifing the single letter vars.

#!/usr/local/bin/perl -w
use strict;

my $d = " #";
my $t = " +";
my $l = " \\";
my $p = " |";
my $s = "  ";

my $tree = {
    'one' => {
        'two' => {
            'five' => {
                'boo' => {
                    'baz' => { },
                },
            },
        },
        'three' => {
            'four' => { },
            'yak' => { },
            'six' => {
                'foo' => {
                    'yuk' => { },
                },
                'ggg' => { },
            },
        },
    },
};

print "with pipes...\n" . &render_node($tree->{'one'}, 'one');
print "no pipes...\n" . &render_node_tab($tree->{'one'}, 'one');

sub render_node {
    my ($tree, $node, $tok, $pad, $last) = @_;
    $tok  = $s unless defined $tok;
    $pad  = "" unless defined $pad;
    $last = 1  unless defined $last;
    
    my $out = $pad . $tok . $d . $node . "\n";

    my @kids = sort keys %{$tree};
    for (my $i = 0; $i < scalar @kids; $i++) {
        my $knode = $kids[$i];
        my $ktree = $tree->{$knode};
        my $klast = ($i+1 == scalar @kids);
        my $ktok  = ($klast ? $l : $t);
        my $kpad  = $pad . ($last ? $s : $p);
        
        $out .= &render_node($ktree, $knode, $ktok, $kpad, $klast);
    }
    return $out;
}

sub render_node_tab {
    my ($tree, $node, $tok, $indent) = @_;
    $tok    = $s unless defined $tok;
    $indent = 0  unless defined $indent;

    my $out = ($s x $indent) . $tok . $d . $node . "\n";

    my @kids = sort keys %{$tree};

    for (my $i = 0; $i < scalar @kids; $i++) {
        my $knode   = $kids[$i];
        my $ktree   = $tree->{$knode};
        my $ktok    = ($i+1 == scalar @kids) ? $l : $t;
        my $kindent = $indent+1;
        
        $out .= &render_node_tab($ktree, $knode, $ktok, $kindent);
    }
    
    return $out;
}
__END__
with pipes...
   #one
   + #three
   | + #four
   | + #six
   | | + #foo
   | | | \ #yuk
   | | \ #ggg
   | \ #yak
   \ #two
     \ #five
       \ #boo
         \ #baz
no pipes...
   #one
   + #three
     + #four
     + #six
       + #foo
         \ #yuk
       \ #ggg
     \ #yak
   \ #two
     \ #five
       \ #boo
         \ #baz
[download]

Well, it depends. :^)

If this is an HTML-related question, then I've always preferred to use a LoL along the following lines:

• my @submenu = ('div', 'img', 'alt');
• my @menu = (
  • ('div', 'img', 'alt', \@submenu)
• );

This does away with the sorting issue and gives you a fairly obvious way to change parameters in a menu so that if you need a special icon or want to manipulate the menu while writing an HTML file, you can.

Of course, this doesn't have any obvious mechanism for drawing your nodes correctly (this straight scenario works best for DHTML menus where elements aren't supposed to cause a reflow.

For displaying a tree more properly I've found JavaScript objects to be pretty handy (unless you want to write for NN3 or IE3 and early IE4) -- you create a Tree object and Node object and then assign your nodes to the tree in any order using some kind of simple path system. Each node 'knows' how deep it is in the tree (since it can query its parent node) and can draw itself appropriately (again, by querying its parents as necessary).

I don't know if this exactly answers your question since it's unclear (to me at least) what your output format is, and I do like some aspects of your system a lot (the matrix transformations seem quite quick and simple), while having doubts about others (the numbering scheme is unduly difficult for a human to read).

HTH

OK, after looking at your sample output I realize this is not what you need ... but anyway, for those that have a similar need (visualizing tree structures) let me point out GraphViz, the Perl interface to the GraphViz tool.

With GraphViz installed, making a little nice postscript (could be PNG, too, or whatever you can postscript convert too) image of your treepath input from above (assumed to be in file try.txt below) becomes as easy as this little shell script:

echo 'digraph G { concentrate = true; ' > try.dot
cat try.txt | perl -lane '$F[2] =~ s/:000//g; $F[2] =~ s/:/ -> /g; $F[
+2] .= ";"; print $F[2] if $F[2] =~ /->/' >> try.dot
echo '}' >> try.dot
dot -Tps -o try.ps try.dot
[download]

Where file try.txt is:

1 => 001:000:000
2 => 001:002:000
3 => 001:003:000
4 => 001:003:004
5 => 001:002:005
[download]

Christian Lemburg
Brainbench MVP for Perl
http://www.brainbench.com

cat try.txt | perl -lane '$F[2] =~ s/:000//g; $F[2] =~ s/:/ -> /g; $F[
+2] .= ";"; print $F[2] if $F[2] =~ /->/' >> try.dot
[download]

If that had been posted to comp.unix.questions, I'd have given it a Useless Use of Cat Award.

-- Randal L. Schwartz, Perl hacker

I stand corrected.

Christian Lemburg
Brainbench MVP for Perl
http://www.brainbench.com

For the curious:

Here's a capture of some sample output (with text added to each row) - each image is 16x16

In answer to another comment - yes, it's easy to work out the 'treepath' by parent lookup, but that doesn't tell you whether to use an 'L' or a '|-', or a '|' or a '|-' for parts of the tree, so I fail to see how you can 'trivially' build the graphic ;-)

cLive ;-)