iterating over a hashref of hashrefs

Discussion in 'Perl Misc' started by Sam, Jun 7, 2005.

  1. Sam

    Sam Guest

    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.
    Sam, Jun 7, 2005
    #1
    1. Advertising

  2. 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
    Mark Clements, Jun 7, 2005
    #2
    1. Advertising

  3. Sam

    Guest

    "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".


    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
    , Jun 7, 2005
    #3
  4. Sam

    John Bokma Guest

    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
    John Bokma, Jun 7, 2005
    #4
  5. 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, Jun 8, 2005
    #5
  6. 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).
    Brian McCauley, Jun 8, 2005
    #6
  7. Sam

    Anno Siegel Guest

    Sam <> 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
    Anno Siegel, Jun 15, 2005
    #7
    1. Advertising

Want to reply to this thread or ask your own question?

It takes just 2 minutes to sign up (and it's free!). Just click the sign up button to choose a username and then you can ask your own questions on the forum.
Similar Threads
  1. monkeys paw

    array of hashrefs (nested)

    monkeys paw, Oct 27, 2003, in forum: Perl Misc
    Replies:
    9
    Views:
    166
    Bob Walton
    Oct 28, 2003
  2. Matija Papec

    grouping hashrefs to trees

    Matija Papec, Nov 16, 2003, in forum: Perl Misc
    Replies:
    1
    Views:
    68
    Ben Morrow
    Nov 16, 2003
  3. penguinista

    hashref strange side effects

    penguinista, Dec 23, 2004, in forum: Perl Misc
    Replies:
    3
    Views:
    128
    penguinista
    Dec 24, 2004
  4. bill

    Equality of hashref objects

    bill, Feb 4, 2005, in forum: Perl Misc
    Replies:
    7
    Views:
    138
    Anno Siegel
    Feb 5, 2005
  5. John W. Krahn

    sorting an array of hashrefs

    John W. Krahn, Aug 29, 2006, in forum: Perl Misc
    Replies:
    1
    Views:
    86
    monkeys paw
    Aug 29, 2006
Loading...

Share This Page