Velocity Reviews - Computer Hardware Reviews

Velocity Reviews > Newsgroups > Programming > Perl > Perl Misc > iterating over a hashref of hashrefs

Reply
Thread Tools

iterating over a hashref of hashrefs

 
 
Sam
Guest
Posts: n/a
 
      06-07-2005
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.


 
Reply With Quote
 
 
 
 
Mark Clements
Guest
Posts: n/a
 
      06-07-2005
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
 
Reply With Quote
 
 
 
 
xhoster@gmail.com
Guest
Posts: n/a
 
      06-07-2005
"Sam" <(E-Mail Removed)> 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
 
Reply With Quote
 
John Bokma
Guest
Posts: n/a
 
      06-07-2005
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

 
Reply With Quote
 
Brian McCauley
Guest
Posts: n/a
 
      06-08-2005


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.

 
Reply With Quote
 
Brian McCauley
Guest
Posts: n/a
 
      06-08-2005
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).

 
Reply With Quote
 
Anno Siegel
Guest
Posts: n/a
 
      06-15-2005
Sam <(E-Mail Removed)> wrote in comp.lang.perl.misc:
> 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
 
Reply With Quote
 
 
 
Reply

Thread Tools

Posting Rules
You may not post new threads
You may not post replies
You may not post attachments
You may not edit your posts

BB code is On
Smilies are On
[IMG] code is On
HTML code is Off
Trackbacks are On
Pingbacks are On
Refbacks are Off


Similar Threads
Thread Thread Starter Forum Replies Last Post
Iterating a std::vector vs iterating a std::map? carl C++ 5 11-25-2009 09:55 AM
VOIP over VPN over TCP over WAP over 3G Theo Markettos UK VOIP 2 02-14-2008 03:27 PM
sorting an array of hashrefs John W. Krahn Perl Misc 1 08-29-2006 08:29 PM
grouping hashrefs to trees Matija Papec Perl Misc 1 11-16-2003 04:38 PM
array of hashrefs (nested) monkeys paw Perl Misc 9 10-28-2003 01:55 AM



Advertisments