I knew tye's approach was based on a closure as an iterator. Allright, I understand that, so I'll take what I understand and try to build it up to what NestedLoops() does...
sub make_iter { my @values = @_; my $idx = -1; return sub { # check if we are out of values, # return a value or undef if we're out return (++$idx > $#values) ? undef : $values[$idx]; } } my $iter = make_iter(3,4,6,7); print while( $_ = $iter->() );
Maybe that's a trivial example, but I understand it.
The crux of NestedLoops is it takes this trivial example to an arbitrary depth. Maybe I can do that, if I accept an AoA for my @values to iterate over. Then, use an array (@idx) for my old $idx value. And since the iterator returns multiple values, I'll have to store them in an array (@return), too. Finally, I need an index ($i) into my arrays, so I know where I'm currently working.
Let's make it work for just the "simplest" case of one set of values again (i.e. $i is always 0), then generalize.
sub make_iter_deeper { my @AoA = @_; my @idx; my $i = 0; # keeping it simple $idx[0] = -1; # same as $idx = -1 above; my @return; return sub { # if the index of the array i'm working in is # past the end of elements if ( ++$idx[$i] > $#{@{$AoA[$i]}} ) { return; } # if not, put the next element in the return value else { $return[$i] = $AoA[$i][$idx[$i]] } return @return; } } my $iter = make_iter_deeper([3,4,6,7]); print join(',',@_) . "\n" while( @_ = $iter->() );
The next step is to handle any number of lists to "nestedly" iterate over.
sub make_iter_deeperer { my @AoA = @_; my @idx; my $i = -1; $idx[0] = -1; my @return; return sub { # depth first to produce "nested" result behavior # if we aren't at the end of AoA's elements, go to # the next, reseting the next elements' index if( $i < $#AoA ) { $idx[++$i]= -1; } LOOP: { if ( ++$idx[$i] > $#{@{$AoA[$i]}} ) { # if the index of the array i'm working in is # past the end of elements it means we need to # go up a level and clear the last return value pop @return; # we may have finished everything return if --$i < 0; # we may have finished more than one # so check again redo LOOP; } # if not, put the next element in the return value else { $return[$i] = $AoA[$i][$idx[$i]] } } return @return; } }
Whew! Okay, I'll admit that I didn't come up with that last one all by myself--in fact, it was born of my examinations of tye's A::L::NestedLoops source. The important bit of which, is the subroutine _NL_iter. Let's take a look.
sub _NL_Iter { my( $loops, $code, $when )= @_; my @list; my $i= -1; my @idx; my @vals= @$loops; return sub { return } if ! @vals; return sub { while( 1 ) { # Prepare to append one more value: if( $i < $#$loops ) { $idx[++$i]= -1; if( isa( $loops->[$i], 'CODE' ) ) { local( $_ )= $list[-1]; $vals[$i]= $loops->[$i]->(@list); } } ## return if $i < 0; # Increment furthest value, chopping if done there: while( @{$vals[$i]} <= ++$idx[$i] ) { pop @list; return if --$i < 0; } $list[$i]= $vals[$i][$idx[$i]]; my $act; $act= !ref($when) ? $when : do { local( $_ )= $list[-1]; $when->(@list); }; return @list if $act; } }; }
Now, tye's function is chock-full of handy features and error-checking. If you can mentally strip that away, you'll find the iterators are identical.
If it weren't late on Saturday morning, I might go more into the usage and the features supported. But, tye's already said he's adding more, so maybe I'll wait until the next version! ;-)
++tye! Fantastic module!
--
I think my eyes are getting better. Instead of a big dark blur, I see a big light blur.
In reply to A::L::NestedLoops walkthrough (was Re^3: Better algorithm than brute-force stack for combinatorial problems?)
by Solo
in thread Better algorithm than brute-force stack for combinatorial problems?
by Solo
For: | Use: | ||
& | & | ||
< | < | ||
> | > | ||
[ | [ | ||
] | ] |