Beefy Boxes and Bandwidth Generously Provided by pair Networks
There's more than one way to do things
 
PerlMonks  

Re: An iterator for (not "iterating") a recursive data structure.

by LanX (Archbishop)
on Jul 13, 2019 at 18:49 UTC ( #11102797=note: print w/replies, xml ) Need Help??


in reply to An iterator for (not "iterating") a recursive data structure.

I found all solutions so far overly complicated, what am I missing?

please note that the maximal length of the queue is only the sum of children at the current descend path, not all tree elements. (e.g. a binary tree with 10 levels has 2**10 = 2014 nodes but the queue will never exceed 20 = 10*2 elements)

Changing from unshift to push will perform a breadth first search.

use strict; use warnings; use Data::Dump qw/pp dd/; print "\n---------- Input\n"; sub genNested { my $n = shift; map{ rand() < 0.5 ? [ int rand(20), genNested( $n-1 ) ] : int rand +( 20 ) } 1 ..$n; } my @nested = genNested( 3 ); print pp \@nested; print "\n\n---------- my solution\n"; sub genIterator { my $tree = shift; my @queue = @{$tree}; return sub { while ( my ($node) = splice @queue,0,1 ) { # shift is buggy if ( ref $node eq 'ARRAY' ) { unshift @queue, @{$node}; next; } else { return $node } } return; }; } my $iter = genIterator( \@nested ); while ( my ($next) = $iter->() ) { print "$next,\t"; } print "\n\n---------- BUKs goal\n"; sub cbIterator (&$) { my( $code, $tree ) = @_; for my $i ( 0 .. $#$tree ) { if( ref( $tree->[ $i ] ) eq 'ARRAY' ) { &cbIterator( $code, $tree->[ $i ] ); } else { local $_ = $tree->[ $i ]; $code->(); } } } cbIterator { print "$_,\t"; } \@nested;

---------- Input [ [934, [993, 105], [167, [213]]], [71, [120, [973]], 135], [404, [828, [571]], 945], ] ---------- my solution 934, 993, 105, 167, 213, 71, 120, 973, 135, + 404, 828, 571, 945, ---------- BUKs goal 934, 993, 105, 167, 213, 71, 120, 973, 135, + 404, 828, 571, 945,

Cheers Rolf
(addicted to the Perl Programming Language :)
Wikisyntax for the Monastery FootballPerl is like chess, only without the dice

update

fixed issue with strange shift behaviour.

update

changed from shift to splice to handle bug with false nodes

Log In?
Username:
Password:

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

How do I use this? | Other CB clients
Other Users?
Others exploiting the Monastery: (4)
As of 2020-05-31 17:04 GMT
Sections?
Information?
Find Nodes?
Leftovers?
    Voting Booth?
    If programming languages were movie genres, Perl would be:















    Results (175 votes). Check out past polls.

    Notices?