Beefy Boxes and Bandwidth Generously Provided by pair Networks
Welcome to the Monastery

Re: various hash construction/ printing questions..

by demerphq (Chancellor)
on Jun 13, 2009 at 16:42 UTC ( #771257=note: print w/replies, xml ) Need Help??

in reply to various hash construction/ printing questions..
in thread how to construct tree from parent pointer list

-- I'm not use to putting '$_' as a key for a hash. I am also not sure what '||=$_' means/does. Can you explain

My code uses a for modifier to alias $c and $p to $_ for the duration of the statement. This is done to eliminate duplicated code. The ||= $_ means "or-equal's $_". Its easiest to exlain by just defining ||= properly, which is that $x ||= $y; does exactly the same thing that $x = $x || $y; which in turn is effectively the same as $x=$y if not $x;

I'm also not sure why you are deleting children...

My algorithm is meant to be order insensitive. That is that you should build the same tree regardless of the order that each parent/child tuple is processed. It does this by putting each node in the root tree, and then basically merging the trees together. However every tree that is a child shouldnt be in the root hash at the end of processing. However we dont know if a node is a true root (the tuples may represent a forest of trees) until we have processed the full list.

-- I'd like to print out something like this

Basically you would write a recursive routine that recursively inorder traverse the tree. Such a routine would look something like the following:

sub print_inorder { my $node= shift; print $node->{name}, "\n"; print_inorder($_) for sort { $a->{name} cmp $b->{name} } values %{ $node->{kids} || {} }; }

And before you ask... %{ $node->{kids} || {} } is a "trick" to make the code relatively simple yet also able to deal with nodes that have no children (as it dereferences an empty hash if there are no kids defined).


Replies are listed 'Best First'.
Re^2: various hash construction/ printing questions..
by bryank (Acolyte) on Jun 13, 2009 at 22:50 UTC

    That was very informative. What if I have three points of data.. say, child, parent, node name (ie descriptor)? Something like:

    __DATA__ b:a:apples d:b:fuji apples <\c> <p> The structure would look something like: <p> <c> $VAR1 = { 'a' => { 'name' => 'fruit', 'child' => { 'b' => { 'name' => 'apples', 'child' => { 'd' => { 'name' +=> 'fuji apples' } } } } } };

    Can your current algorithm be modified to work with this?

      Of course it can. :-)

      If you play around with it I'm sure you'll figure it out. :-)


        Hee hee. I did figure it out. Thanks for teaching me to fish, as it were. :)
Re^2: various hash construction/ printing questions..
by bryank (Acolyte) on Jun 30, 2009 at 16:28 UTC
    Hi. I am having problems incorporating your output subroutine. Can you help?

    use Data::Dumper; use strict; use warnings; my %nodes; my @children; while (<>) { chomp; my ($c,$p)=split "\t"; push @children,$c unless $nodes{$c}; $nodes{$_}{name}||=$_ for $c,$p; $nodes{$p}{kids}{$c}=$nodes{$c}; } delete $nodes{$_} for @children; my @roots=keys %nodes; #print Dumper($nodes{$_}) for @roots; print_inorder(%nodes); sub print_inorder { my $node= shift; print $node->{name}, "\n"; print_inorder($_) for sort { $a->{name} cmp $b->{name} } values %{ $node->{kids} || {} }; }

Log In?

What's my password?
Create A New User
Node Status?
node history
Node Type: note [id://771257]
[marto]: Eily, there's actually a lot of good discussion on the topic in the HN link choroba posted
[marto]: sorry for the late response, busy busy :/
[Corion]: I think you need to load Readline in the debugger, but I don't know how
[Corion]: Yay, invitation for a team-building workshop, with a team of 100 people :-/
[Eily]: marto after an additional read I started to see the light actually. And choroba's link was helpful as well :)
[Corion]: I'll send my colleague who doesn't yet know the people there, and I'll do production duty instead.
[GotToBTru]: ugh. Thanks Corion

How do I use this? | Other CB clients
Other Users?
Others exploiting the Monastery: (14)
As of 2017-07-26 15:05 GMT
Find Nodes?
    Voting Booth?
    I came, I saw, I ...

    Results (396 votes). Check out past polls.