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 ];
         }
      }
   };
}