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

Note that you can drop the ", 0", the "ref" and both of the "next;"s.

Since you just need pairs, you can even drop the "["s and "]"s, reducing the code to:

sub genIterator {
    my( $root ) = @_;
    my @stack = ( $root, 0 );
    return sub {
        while( @stack ) {
            my $index = pop @stack;
            my $tree =  pop @stack;
            if( ref( $tree->[$index] ) ) {
                push( @stack, $tree, $index+1, $tree->[$index], 0 );
            } elsif( $index < @$tree ) {
                push( @stack, $tree, $index+1 );
                return $tree->[$index];
            }
         }
         return;     # empty stack
    }
}
[download]

(Not some fundamental change, just a minor reworking.)

- tye

Comment on Re^2: An iterator for (not "iterating") a recursive data structure. (terser) Download Code

Replies are listed 'Best First'.
Re^3: An iterator for (not "iterating") a recursive data structure. (Winner!) by BrowserUk (Patriarch) on Feb 12, 2015 at 15:01 UTC
We have a winner! Thanks to you and MidLifeXis. With the rise and rise of 'Social' network sites: 'Computers are making people easier to use everyday' Examine what is said, not who speaks -- Silence betokens consent -- Love the truth but pardon error. "Science is about questioning the status quo. Questioning authority". I'm with torvalds on this In the absence of evidence, opinion is indistinguishable from prejudice. Agile (and TDD) debunked	[reply]
Re^3: An iterator for (not "iterating") a recursive data structure. (terser) by ikegami (Patriarch) on Feb 13, 2015 at 15:30 UTC
It's identical to what you'd use for a breadth-first search (as an iterator or otherwise) except then you'd use a queue instead of a stack for a breadth-first search. In both cases, you need to save the search state in a local var rather than using recursion to save it on the system stack.	[reply]
Re^3: An iterator for (not "iterating") a recursive data structure. (index into keys?) by LanX (Saint) on Jun 18, 2020 at 20:48 UTC
I'm wondering if this could also be done with nested hashes. A stored array index has a natural successor, but a hash key hasn't.° Using `each` is accessing an internal iterator "cursor", but can't be used multiple times with the same hash. The only solution which comes to mind is to initially cache the `keys` into an array and to go by index. But this static copy defies the idea of a dynamic iterator. Any better idea? update Tie::Hash requires us to implement a `NEXTKEY this, lastkey` method. But there doesn't seem to be a way to access this API with a native hash. update Is `(keys %hash)[$idx++]` optimized to be performant, or will it create a long list of keys to be thrown away? Cheers Rolf _{(addicted to the Perl Programming Language :) Wikisyntax for the Monastery} °) well there is an internal order but this is a) kept secret and b) shuffled with every new run of perl	[reply] [d/l] [select]
Re^4: An iterator for (not "iterating") a recursive data structure. (updated x 2) by LanX (Saint) on Jun 19, 2020 at 00:32 UTC
UPDATE: Please don't trust the benchmark, turns out, that when operating on the same hash they are sabotaging each other* > Is `(keys %hash)[$idx++]` optimized to be performant, or will it create a long list of keys to be thrown away? ~~it's way faster than `each` !?!~~ UPDATE Sorry I misread the results, it's late. :) The approach with `(keys %hash)[$idx++]` is far slower. <Reveal this spoiler or all in this thread> Compilation started at Fri Jun 19 02:17:48 C:/Perl_524/bin\perl.exe d:/exp/hash_iter.pl * Testing gen_idx_keys ok 1 - 'gen_idx_keys' iterates over all entries ok 2 - 'gen_idx_keys' cycles and iterates again * Testing gen_copy_hash_and_each ok 3 - 'gen_copy_hash_and_each' iterates over all entries ok 4 - 'gen_copy_hash_and_each' cycles and iterates again * Testing gen_copy_keys ok 5 - 'gen_copy_keys' iterates over all entries ok 6 - 'gen_copy_keys' cycles and iterates again * Testing gen_each ok 7 - 'gen_each' iterates over all entries ok 8 - 'gen_each' cycles and iterates again 1..8 Rate idx_keys copy_keys each copy_has +h_and_each idx_keys 3.05/s -- -100% -100% + -100% copy_keys 2361328/s 77510489% -- -6% + -23% each 2522717/s 82808095% 7% -- + -17% copy_hash_and_each 3047966/s 100049391% 29% 21% + -- Compilation finished at Fri Jun 19 02:18:05 [download] Cheers Rolf _{(addicted to the Perl Programming Language :) Wikisyntax for the Monastery}	[reply] [d/l] [select]

update

update

UPDATE: Please don't trust the benchmark, turns out, that when operating on the same hash they are sabotaging each other*