Finding Previous and Next in a HASH

skazat has asked for the wisdom of the Perl Monks concerning the following question:

Hello everyone,

I have a hash, that could look like this:

 

my %hash = (
1  => 'hello', 
2  => 'wizeguy', 
4  => 'zoom', 
5  => 'foo', 
24 => 'grr', 
);
[download]

I want to be working on the value of key number five, but I'll need the value of the previous and next keys (when sorted in numnerical order), in other words, if I'm working on $hash{2} I need the value of $hash{1} and $hash{4}

This seems really tricky to me, especially when the key values skip numbers and/or you're at the end of the sorted hash, like $hash{24} and $hash{1}.

It makes sense that I should first sort the keys in numeric order using an array to hold the keys but after that I'm stumped, all my loops aren't working,

Anyone want to help?

-justin simoni
!skazat!

Comment on Finding Previous and Next in a HASH Download Code

Replies are listed 'Best First'.
Re: Finding Previous and Next in a HASH by arturo (Vicar) on Dec 12, 2000 at 04:11 UTC
One way to the answer to your question is the `keys` function in conjunction with `sort` ... you can call `my @keys = sort keys %hash;` to get a sorted array of the keys of the hash; while you're poking through the hash, set an index variable and grab `$keys[$index-1]` and `$keys[$index+1]` to get the keys you want. (Of course, you should add in some checks to determine when you're at the beginning and at the end of the list of keys!). Philosophy can be made out of anything. Or less -- Jerry A. Fodor	[reply] [d/l] [select]
Optimized Previous and Next Accessors by tedv (Pilgrim) on Dec 12, 2000 at 08:26 UTC
You can get away with `$keys[$index-1]` and `$keys[($index+1) % @keys]` because the first array access, should it be negative, will access from the back of the array, and the last array access is guaranteed to be in range. So no extra checking is needed for boundaries. -Ted	[reply] [d/l] [select]
Re: Re: Finding Previous and Next in a HASH by myocom (Deacon) on Dec 12, 2000 at 04:59 UTC
This is very much like what I was trying to do earlier. And this is the solution I ended up using.	[reply]
Re: Finding Previous and Next in a HASH by runrig (Abbot) on Dec 12, 2000 at 04:24 UTC
`my %nxt; my %prev; my $prv; for (sort { $a <=> $b } keys %hash) { if (defined $prv) { $nxt{$prv} = $_; $prev{$_} = $prv; } $prv = $_; }` [download]	[reply] [d/l]
Re: Re: Finding Previous and Next in a HASH by turnstep (Parson) on Dec 12, 2000 at 07:31 UTC
This is a good answer, but it fails to point the first element "back" to the last, and the last "forward" to the first. Here's one way to do that: `my %nxt; my %prev; my $prv; my $first; for (sort { $a <=> $b } keys %hash) { $first \|\|= $_; if (defined $prv) { $nxt{$prv} = $_; $prev{$_} = $prv; } $prv = $_; } $nxt{$prv}=$first; $prev{$first}=$prv;`	[reply]
Re: Finding Previous and Next in a HASH by japhy (Canon) on Dec 12, 2000 at 04:47 UTC
Here's a simple non-OO doubly-linked list: `%hash = ( this => { PREV => undef, NEXT => 'that', VALUE => 10 }, that => { PREV => 'this', NEXT => 'those', VALUE => 5 }, those => { PREV => 'that', NEXT => undef, VALUE => 0 }, );` [download] You figure out how to use it (it's not that hard). `japhy` -- Perl and Regex Hacker	[reply] [d/l]
Re: Finding Previous and Next in a HASH by Hot Pastrami (Monk) on Dec 12, 2000 at 04:48 UTC
Well, here's my attempt, assuming that $current holds the value of the current key: `my ($previous,$next); my @keys = sort { $a <=> $b } keys %hash; for (my $i=0; $i < scalar @keys; $i+=1) { $previous = $keys[$i-1] unless $i == 0; $next = $keys[$i+1] unless $i == scalar @keys; last if $keys[$i] == $current; }` [download] Alan "Hot Pastrami" Bellows Update: Oh, this also assumes that the value of $current is known to be in %hash, if a value is in $current that is not in %hash it won't work too good.	[reply] [d/l]
Re: Finding Previous and Next in a HASH by FouRPlaY (Monk) on Dec 12, 2000 at 05:07 UTC
I forget where I read it - whether it was on this site or in a Perl book - but someone said/wrote that if you find yourself wishing arrays were associative or hashes were ordered, you're using the wrong tool. It seems to me that you sould start off with an array and not use a hash at all. FouRPlaY Learning Perl or Going To die() Trying	[reply]
Re: Re: Finding Previous and Next in a HASH by myocom (Deacon) on Dec 12, 2000 at 05:17 UTC
Sometimes you end up with conflicting wishes, though. For the problem I was having earlier, I had a case of requiring unique keys and also wanting to index into the hash (or rather, the keys of the hash). In my case, at least, the fact that hash keys are by definition unique outweighed my desire for ordered hashes. Otherwise, you're right, I would've used an array. :-)	[reply]
Re: Finding Previous and Next in a HASH by eg (Friar) on Dec 12, 2000 at 04:40 UTC
What arturo says is right, but I think the more fundemental problem is that you're using a less than perfect data structure given your problem. It would be much easier to just use a doubly linked list. There's probably something on CPAN.	[reply]
Re: Finding Previous and Next in a HASH by Fastolfe (Vicar) on Dec 12, 2000 at 12:22 UTC
If your range of keys is kept reasonably sane (e.g. not jumping from 1 to 100 to 10000), consider using an array instead of a hash. This doesn't solve the problem of finding the next or previous item in the list (a jump leaves that element in the array undefined), but it could be considerably more efficient, depending upon your application. An array, in practice, is equivalent to a numerically-addressed hash. So long as you're not doing too much jumping, you're not likely to be wasting a significant amount of space by ignoring the gaps.	[reply]


laziness, impatience, and hubris
	PerlMonks