Beefy Boxes and Bandwidth Generously Provided by pair Networks
Just another Perl shrine
 
PerlMonks  

Re: Eliminating Recursive Tree Walking by using MJD-style Infinite Streams?

by ikegami (Pope)
on Jun 16, 2008 at 23:51 UTC ( #692404=note: print w/replies, xml ) Need Help??


in reply to Eliminating Recursive Tree Walking by using MJD-style Infinite Streams?

I made the iterator version.

I changed the names of just about everything so I could keep things straight in my head. Feel free to change them back.

I changed the param order too. I tend to put the structure on which I am operating on the left, like $self is. It was also more convenient internally. Feel free to change that back too.

use strict; use warnings; sub build_and_pop { my ($stack) = @_; my $path = [ map $_->[0], @$stack ]; pop @$stack; return $path; } sub find_paths { my ($tree, $regs) = splice(@_, 0, 2); my @stack = ( [ [ @_ ], 0 ] ); return sub { for (;;) { return if !@stack; our ($node, $idx); local (*node, *idx) = map \$_, @{ $stack[-1] }; # $node can be a reference into $tree, # so don't modify @$node. my ($x_s, $y_s, $s_s) = @$node; my $children = $tree->[$x_s][$y_s][$s_s]; if (!$idx) { if (!defined $children) { # pad endpoint (base case)} $node = [ $x_s, $y_s, $s_s, 'pad' ]; return build_and_pop(\@stack); } if (exists $regs->{$x_s}{$y_s}{$s_s}) { # register endpoint (base case) $node = [ $x_s, $y_s, $s_s, 'reg' ]; return build_and_pop(\@stack); } } if ($idx > $#$children) { pop @stack; } else { my $child = $children->[$idx++]; push @stack, [ $child, 0 ]; } } }; }
my $regs; $regs->{1}{0}{0} = 1; my $tree; $tree->[0][0][0] = [ [ 3, 0, 0 ], ]; $tree->[0][1][0] = [ [ 0, 2, 0 ], ]; $tree->[1][0][0] = [ [ 0, 3, 0 ], ]; $tree->[3][0][0] = [ [ 0, 1, 0 ], [ 1, 0, 0 ], ];
my $iter = find_paths($tree, $regs, 3,0,0); while (my ($route) = $iter->()) { for my $node (@$route) { print(join(',', @$node), "\n"); } print("\n"); }

Log In?
Username:
Password:

What's my password?
Create A New User
Domain Nodelet?
Node Status?
node history
Node Type: note [id://692404]
help
Chatterbox?
and the web crawler heard nothing...

How do I use this? | Other CB clients
Other Users?
Others rifling through the Monastery: (3)
As of 2021-12-07 18:39 GMT
Sections?
Information?
Find Nodes?
Leftovers?
    Voting Booth?
    R or B?



    Results (34 votes). Check out past polls.

    Notices?