in reply to retrieve next avaiable element in sorted hash

Nothing is jumping out at me from CPAN, except maybe Tie::RangeHash, which you might find a way to use with what you're doing. If not, here's a solution (not particularly efficient though):

sub get_fuzzy {
    my ($k, $h) = @_;
    return $h->{$k} if exists $h->{$k};

    for (sort keys %$h) {
        return $h->{$_} if $_ gt $k;  # if keys are numeric, change "g
+t" to ">"
    }

    return undef;    # if key is higher than the highest
}

my %hash = (a=>1, c=>3, e=>5, g=>7, i=>9);
print "|", join('|', map { get_fuzzy($_, \%h) } a..j), "|\n";

[download]

It's inefficient because it sorts all the hash keys each time there is a lookup and does a linear search through them. Also, I'm not sure what you want to do when looking up a value larger than the largest hash key. In this case, my code returns undef.

If you want efficiency, you may want to tie a class of your own that maintains the keys in sorted order, perhaps even indexed so you could do a binary search instead of a linear one.

-- Mike

--
XML::Simpler does not require XML::Parser or a SAX parser. It does require File::Slurp.
-- grantm, perldoc XML::Simpler

Replies are listed 'Best First'.
Re: Re: retrieve next avaiable element in sorted hash
by Limbic~Region (Chancellor) on Oct 06, 2003 at 23:47 UTC
    thelenm,
    I was thinking about adding a new method to Tie::Hash::Sorted after reading this thread as it already stores the hash keys in a sorted array. A person may want to indicate where in the sorted hash they wanted to start from on a case by case basis. After giving it some thought, it won't help here.

    The problem is that what is being asked for is not they next key, but the next key with a defined value. Even with the binary search, you still need to iterate after you find your target until you find a defined key value. My idea is a variation that should get the job done.

    Cheers - L~R

[reply]

      Even with the binary search, you still need to iterate after you find your target until you find a defined key.

      Not so. Its trivial to adjust binary search to handle "find the node immediately preceding/following my value or the value itself" searches. If you already know one endpoint linear search makes sense, as does using it as the left boundary and range searching the appropriate side.


      ---
      demerphq

        First they ignore you, then they laugh at you, then they fight you, then you win.
        -- Gandhi

[reply]
[d/l]
        demerphq,
        I stand by my claim. If the value before or after is undefined, then it is not desired. You need to keep moving forward until you find a key with a defined value.

        Cheers - L~R

        Update: After discussing this in the CB, I wanted to record why I interpreted next key with defined value versus just next key. It was based off of:

        without going through all the trouble of making a for loop to check each element after '2' until find one defined.

[reply]

In Section Seekers of Perl Wisdom