Beefy Boxes and Bandwidth Generously Provided by pair Networks
Perl: the Markov chain saw
 
PerlMonks  

Re: seeking in hash data structure

by graff (Chancellor)
on Oct 25, 2006 at 03:24 UTC ( #580477=note: print w/ replies, xml ) Need Help??


in reply to seeking in hash data structure

If your hash structure is always HoHoHo... -- i.e. no arrays, just hashes -- then the first trick you need to nail down is a way to distinguish between terminal nodes and non-terminal nodes in your tree.

Based on your examples, I'd guess that the easiest way to do this is by using your actual strings only as hash keys, never as values assigned to keys. The value of a hash element would always be a hash ref; non-terminal nodes would contain hash refs with one or more keys, whereas a terminal node would contain an empty hashref. The point here is that hash value is either a simple scalar or else it's a reference -- it can't be both.

Here's a way you could take hyphen-delimited strings to create an abitrarily deep / arbitrarily wide tree structure:

use strict; use warnings; use Data::Dumper; sub load_hash { my ( $href, $path ) = @_; my @path = split /-/, $path; my $key = shift @path; while ( @path and exists( $$href{$key} )) { $href = $$href{$key}; $key = shift @path; } if ( ! exists( $$href{$key} )) { # there's a new key in this path $$href{$key} = {}; # so create a new hashref for it load_hash( $$href{$key}, join( "-", @path )) if ( @path ); # recurse if this key/node is non-terminal } # otherwise, do nothing -- the path already exists in the structure } sub trace_paths # look for paths to a chosen node (hash key) { my ( $href, $aref, $node, $path ) = @_; $path ||= ''; my @keys = keys %$href; if ( grep /^$node$/, @keys ) { push @$aref, ( $path ) ? "$path-$node" : $node; } for my $key ( @keys ) { my $nxt_path = ( $path ) ? "$path-$key" : $key; trace_paths( $$href{$key}, $aref, $node, $nxt_path ) if ( scalar keys %{$$href{$key}} ); } } my @strings = qw/one-foo-bar-baz one-foo-zuz two-fump-zill two-fizz-foo/; my %hash; load_hash( \%hash, $_ ) for ( @strings ); print Dumper( \%hash ); my @found; trace_paths( \%hash, \@found, 'foo' ); print Dumper( \@found );
(updated to fix an annoying initial dash in @found values)

Now, if you really want the structure to hold scalar values as well as hash keys, you'll need to reserve one or more "special keys" that you can use for storing strings or numbers instead of lower-level hash refs. These special keys need to be strings that will never occur as data (nodes in the structure), and the load_hash and/or trace_paths subs would need an extra line or two of code to use them as needed.


Comment on Re: seeking in hash data structure
Download Code

Log In?
Username:
Password:

What's my password?
Create A New User
Node Status?
node history
Node Type: note [id://580477]
help
Chatterbox?
and the web crawler heard nothing...

How do I use this? | Other CB clients
Other Users?
Others studying the Monastery: (17)
As of 2014-07-28 19:49 GMT
Sections?
Information?
Find Nodes?
Leftovers?
    Voting Booth?

    My favorite superfluous repetitious redundant duplicative phrase is:









    Results (207 votes), past polls