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");
}