iterating over a hashref of hashrefs

[Sam]

I have a data structure that looks like this:
$self->{'foo'}->{'bar'}->{'dog'} = "fred";
$self->{'foo'}->{'bar'}->{'blue'}->{'cat'} = "barney";


$self->{'foo'}->{'ban'}->{'dog'} = "wilma";
$self->{'foo'}->{'ban'}->{'cat'} = "betty";


$self->{'foo'}->{'bas'}->{'dog'}= "bambam";
$self->{'foo'}->{'bas'}->{'cat'} = "dino";

Where I want all entries which have a key = "cat". The trick is that the
depth of the hashref tree is not constant. (line2) otherwise I'd just use a
bunch of nested foreach statements.

 

[Mark Clements]

I have a data structure that looks like this:
$self->{'foo'}->{'bar'}->{'dog'} = "fred";
$self->{'foo'}->{'bar'}->{'blue'}->{'cat'} = "barney";


$self->{'foo'}->{'ban'}->{'dog'} = "wilma";
$self->{'foo'}->{'ban'}->{'cat'} = "betty";


$self->{'foo'}->{'bas'}->{'dog'}= "bambam";
$self->{'foo'}->{'bas'}->{'cat'} = "dino";

Where I want all entries which have a key = "cat". The trick is that the
depth of the hashref tree is not constant. (line2) otherwise I'd just use a
bunch of nested foreach statements.

You need to put your question in the body of the message, otherwise it isn't clear
exactly what you are asking. Read the posting guidelines.

Assuming that what you want is:

an algorithm to retrieve all items in the structure with a keyname of "cat"

then:

a) you can use a recursive algorithm to traverse your structure.
b) you can use an iterative algorithm to traverse your structure (may require more work)
c) you can maintain a secondary data structure indexing where "cat" entries are, making
it easier to pull them out again afterwards.

Mark

 

[xhoster]

I have a data structure that looks like this:
$self->{'foo'}->{'bar'}->{'dog'} = "fred";
$self->{'foo'}->{'bar'}->{'blue'}->{'cat'} = "barney";

$self->{'foo'}->{'ban'}->{'dog'} = "wilma";
$self->{'foo'}->{'ban'}->{'cat'} = "betty";

$self->{'foo'}->{'bas'}->{'dog'}= "bambam";
$self->{'foo'}->{'bas'}->{'cat'} = "dino";

Where I want all entries which have a key = "cat".

Which key? Will 'cat' only occur as a key in the lowest level of nesting?

sub foo {
return unless ref $_[0];
return map {$_ eq 'cat'? $_[0]{$_} : foo ($_[0]{$_})} keys %{$_[0]};
};


Xho

 

[John Bokma]

I have a data structure that looks like this:
$self->{'foo'}->{'bar'}->{'dog'} = "fred";
$self->{'foo'}->{'bar'}->{'blue'}->{'cat'} = "barney";


$self->{'foo'}->{'ban'}->{'dog'} = "wilma";
$self->{'foo'}->{'ban'}->{'cat'} = "betty";


$self->{'foo'}->{'bas'}->{'dog'}= "bambam";
$self->{'foo'}->{'bas'}->{'cat'} = "dino";

Where I want all entries which have a key = "cat". The trick is that
the depth of the hashref tree is not constant. (line2) otherwise I'd
just use a bunch of nested foreach statements.

find( 'cat', $self );

sub find {

my ( $query, $hash ) = @_;

for my $key ( keys %$hash ) {

my $item = $hash->{ $key };
if ( ref $item ) {

find( $query, $item );
next;
}

if ( $key eq $query ) {

print "Found $query: $item\n";
}
}
}

I have written it out a bit, since I don't know your exact requirements
(sort order, etc), but this is a way to do such a thing: recursive tree
traversal (in this case depth first). If you want to search first at the
same level before going to the next level, you can do something like:

if ( ref $item ) {

push @todo, $key;
next;
}

and add after the for:

find( $query, $hash->{ $_ } ) for @todo;

(untested, etc).

 

[Brian McCauley]

I have a data structure that looks like this:
$self->{'foo'}->{'bar'}->{'dog'} = "fred";
$self->{'foo'}->{'bar'}->{'blue'}->{'cat'} = "barney";


$self->{'foo'}->{'ban'}->{'dog'} = "wilma";
$self->{'foo'}->{'ban'}->{'cat'} = "betty";


$self->{'foo'}->{'bas'}->{'dog'}= "bambam";
$self->{'foo'}->{'bas'}->{'cat'} = "dino";

Where I want all entries which have a key = "cat". The trick is that the
depth of the hashref tree is not constant. (line2) otherwise I'd just use a
bunch of nested foreach statements.

I'd go for a queue and an iterative approach...

my @hashes = $self;
my @found;
while ( my $hash = shift @hashes ) {
# push @hashes => map { eval { \%$_ } } values %$hash;
push @hashes => grep { ref eq 'HASH' } values %$hash;
push @found => $hash->{cat} if exists $hash->{cat};
}

Note the commented-out eval{} based alternate line allows you to cope
with blessed hashes and object that emmulate hashes via overloading. If
you are only interested in plain hashes then stick with the uncommented
code.

Note if 'cat' appears as a non-terminal subscript in the tree then
@found will contain whole subtrees (i.e. it will contain hashrefs). I'm
assuming this is what you want.

 

[Brian McCauley]

while ( my $hash = shift @hashes ) {
push @hashes => grep { ref eq 'HASH' } values %$hash;
}

Actually it's probably more more memory efficient to make @hashes a
stack rather then a queue. Change shift to pop (or change push to unshift).

 

[Anno Siegel]

I have a data structure that looks like this:
$self->{'foo'}->{'bar'}->{'dog'} = "fred";
$self->{'foo'}->{'bar'}->{'blue'}->{'cat'} = "barney";


$self->{'foo'}->{'ban'}->{'dog'} = "wilma";
$self->{'foo'}->{'ban'}->{'cat'} = "betty";


$self->{'foo'}->{'bas'}->{'dog'}= "bambam";
$self->{'foo'}->{'bas'}->{'cat'} = "dino";

Where I want all entries which have a key = "cat". The trick is that the
depth of the hashref tree is not constant. (line2) otherwise I'd just use a
bunch of nested foreach statements.

You haven't said what else you want to do with the data, but for
the problem at hand what you want is not a hash of hashes but
multidimensional array emulation (see "$;" in perlvar).

my $self;
$self->{'foo', 'bar', 'dog'} = "fred";
$self->{'foo', 'bar', 'blue', 'cat'} = "barney";

$self->{'foo', 'ban', 'dog'} = "wilma";
$self->{'foo', 'ban', 'cat'} = "betty";

$self->{'foo', 'bas', 'dog'}= "bambam";
$self->{'foo', 'bas', 'cat'} = "dino";

$self->{'foo', 'cat', 'paw'} = "wilma";

/\bcat\b/ and print "$_ => $self->{ $_}\n" for keys %$self;

Anno