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 Need Help??

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

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?