Afternoon

I'm looking for something that works like a hash, but whose keys are ranges of integers. When I want a value from a hash, I give it a single integer, and it should return the value whose range key includes the given integer. Here's an implementation:

package RangedHash;

sub TIEHASH { bless({}, shift); }
# the key should be the start point of the range
sub STORE { $_[0]->{$_[1]} = $_[2]; }

sub FETCH {
    my ($self, $point) = @_;
    my $cursor = 0;
    foreach ( sort keys %$self ) {
        return $self->{$cursor} if ( $point >= $cursor && $point < $_ 
+);
        $cursor = $_;
    }
    return $self->{$cursor}
}

package main;

my %ranged_hash;
tie(%ranged_hash, "RangedHash");
$ranged_hash{0} = 'foo';
$ranged_hash{10} = 'bar';
$ranged_hash{20} = 'qux';
$range_hash{3}; # 'foo'
$range_hash{14}; # 'bar'
$range_hash{27}; # 'qux'
[download]

However, for high values, it has to look through every other key first, which rather defeats the point of hashes. In the real application, I'm working with these ranged hashes with hundreds or thousands of pairs. I'm wondering if there's a better algorithm, or prior art here? It doesn't necessarily have to work with tie, btw.

(If it's of interest, I'm working with long strings in a GUI that are composed of fragments of other strings. Some of the time, I need to be able to work out for a given point in the long composite string where the original fragment came from.)

Update: I should have stated that the ranges are:

• Contiguous: there's a value for every integer point in the range 0 .. n, where n is the upper bound of the highest range.
• Discrete: none of them overlap
• Entered sequentially from lowest to highest, and stable after created

TIA,
alex

---

---

Posts are HTML formatted. Put <p> </p> tags around your paragraphs. Put <code> </code> tags around your code and data!

Titles consisting of a single word are discouraged, and in most cases are disallowed outright.

Read Where should I post X? if you're not absolutely sure you're posting in the right place.

Please read these before you post! —

• How do I compose an effective node title?
• How do I post a question effectively?
• Markup in the Monastery

Posts may use any of the Perl Monks Approved HTML tags:

a, abbr, b, big, blockquote, br, caption, center, col, colgroup, dd, del, details, div, dl, dt, em, font, h1, h2, h3, h4, h5, h6, hr, i, ins, li, ol, p, pre, readmore, small, span, spoiler, strike, strong, sub, summary, sup, table, tbody, td, tfoot, th, thead, tr, tt, u, ul, wbr

You may need to use entities for some characters, as follows. (Exception: Within code tags, you can put the characters literally.)

	For:		Use:
	&		&
	<		&lt;
	>		&gt;
	[		&#91;
	]		&#93;

Link using PerlMonks shortcuts! What shortcuts can I use for linking?

See Writeup Formatting Tips and other pages linked from there for more info.