Dirk80 has asked for the wisdom of the Perl Monks concerning the following question:

Hello,

I want to iterate over each node of a nested hash.

I learnt from you perlmonks how to iterate over all leaves of a nested hash with Data::Leaf::Walker.

I like this way a lot. So I ask you if there is a similar way to iterate over all nodes of a nested hash and not only over its leaves.

Here a code example:

use strict;
use warnings;

use Data::Leaf::Walker;

my %nested_hash = ( a => { aa => {aaa => 5,
                                  aab => 5,
                                  aac => 5},
                           ab => {aba => 5,
                                  abb => 5,
                                  abc => 5} },
                    b => { ba => {baa => 5,
                                  bab => 5,
                                  bac => 5},
                           bb => {bba => 5,
                                  bbb => 5,
                                  bbc => 5} } );

my $walker = Data::Leaf::Walker->new( \%nested_hash );

# only iterating over leaves
while ( my ( $k, $v ) = $walker->each )
{
    print "@{ $k } : $v\n";
}


# --> I want to iterate over all nodes.
# --> wanted solution for @{ $k }:
# ('a')
# ('a', 'aa')
# ('a', 'aa', 'aaa')
# ('a', 'aa', 'aab')
# ('a', 'aa', 'aac')
# ('a', 'ab')
# ('a', 'ab', 'aba')
# ('a', 'ab', 'abb')
# ('a', 'ab', 'abc')
# ('b')
# ('b', 'ba')
# ('b', 'ba', 'baa')
# ('b', 'ba', 'bab')
# ('b', 'ba', 'bac')
# ('b', 'bb')
# ('b', 'bb', 'bba')
# ('b', 'bb', 'bbb')
# ('b', 'bb', 'bbc')

[download]

Thank you very much.

Greetings,

Dirk

Replies are listed 'Best First'.
Re: Iterating over nested hash
by Perlbotics (Archbishop) on Dec 12, 2010 at 18:39 UTC

    Maybe something along the following lines? 

    use strict;
use warnings;

my %nested_hash = ( a => { aa => {aaa => 1,
                                  aab => 2,
                                  aac => 3},
                           ab => {aba => 4,
                                  abb => 5,
                                  abc => 6} },
                    b => { ba => {baa => 7,
                                  bab => 8,
                                  bac => 9},
                           bb => {bba => 10,
                                  bbb => 11,
                                  bbc => 12} } );


my @nodes;

sub walk {
  my $node = shift;

  foreach (sort keys %{ $node }) {
    push @nodes, $_;
    print join(", ", @nodes), "\n";
    walk( $node->{$_} ) if ref $node->{$_};
    pop @nodes;
  }
}

walk( \%nested_hash );

__END__
a
a, aa
a, aa, aaa
a, aa, aab
a, aa, aac
a, ab
a, ab, aba
a, ab, abb
a, ab, abc
b
b, ba
b, ba, baa
b, ba, bab
b, ba, bac
b, bb
b, bb, bba
b, bb, bbb
b, bb, bbc

    [download]

[reply]
[d/l]
      The above will work nicely so long as you are certain there are no circularities in your nested hash. If there are you will get an infinite loop. To fix this you'll need to do two things:
      • give each node in the hash a unique id
      • check the path you have traversed to reach the node for circularities

      A small addition to the above code will eliminate the problem of circularities

      
# %nested_hash revised to contain a circularity
my $hAA = {aaa => 1, aab => 2 };
$hAA->{aac} = $hAA;

my %nested_hash = ( a => { aa => $hAA,
                           ab => {aba => 4,
                                  abb => 5,
                                  abc => 6} },
                    b => { ba => {baa => 7,
                                  bab => 8,
                                  bac => 9},
                           bb => {bba => 10,
                                  bbb => 11,
                                  bbc => 12} } );


sub walk {
  my $node = shift;

 OUTER:
  foreach my $k (sort keys %{ $node }) {

    # replace these lines with the lines between ***
    # push @nodes, $k;
    # print join(", ", @nodes), "\n";
    # ***

    print join(", ", @nodes) . (scalar(@nodes)?', ':'');
    foreach my $kInPath (@nodes) {
      if ($k eq $kInPath) {
        print "$k ... (circularity)\n";
        next OUTER if ($k eq $kInPath);
      }
    }

    print "$k\n";
    push @nodes, $k;

    # ***

    walk( $node->{$k} ) if ref $node->{$k};
    pop @nodes;
  }
}

# outputs
a
a, aa
a, aa, aaa
a, aa, aab
a, aa, aac
a, aa, aac, aaa
a, aa, aac, aab
a, aa, aac, aac ... (circularity)
a, ab
a, ab, aba
a, ab, abb
a, ab, abc
b
b, ba
b, ba, baa
b, ba, bab
b, ba, bac
b, bb
b, bb, bba
b, bb, bbb
b, bb, bbc

      [download]

      Also, it is a good idea to use named variables in your for loop rather than $_, i.e. for my $k (@nodes) instead of for (@nodes). It makes things like nested for loops a bit easier to manage and protects you from some odd side effects that can result if subroutines called within a for loop don't properly localize $_.

      Update: Added code to show %nested_hash with circularity

      Update: Added sample output.

[reply]
[d/l]
[select]

Back to Seekers of Perl Wisdom