| Author |
iterating over a hashref of hashrefs
|
|
|
| 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 2005-06-07, 8:57 pm |
| Sam wrote:
> 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@gmail.com 2005-06-07, 8:57 pm |
| "Sam" <perlquestions@mail.com> wrote:
> 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
--
-------------------- http://NewsReader.Com/ --------------------
Usenet Newsgroup Service $9.95/Month 30GB
| |
| John Bokma 2005-06-07, 8:57 pm |
| Sam wrote:
> 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).
--
John Small Perl scripts: http://johnbokma.com/perl/
Perl programmer available: http://castleamber.com/
Happy Customers: http://castleamber.com/testimonials.html
| |
| Brian McCauley 2005-06-08, 3:59 pm |
|
Sam wrote:
> 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 2005-06-08, 3:59 pm |
| Brian McCauley wrote:
> 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).
|
|
|
|