/ 
Tie-RangeHash-1.02
River stage one • 1 direct dependent • 1 total dependent
/ Tie::RangeHash

NAME

Tie::RangeHash - Allows hashes to associate values with a range of keys

REQUIREMENTS

Algorithm::SkipList is required. Otherwise it uses standard modules.

Installation

Installation is pretty standard:

perl Makefile.PL
make
make test
make install

Note that when you run the tests, you will see warnings. That is intentional.

SYNOPSIS

use Tie::RangeHash;

tie %hash, 'Tie::RangeHash';

$hash{'A,C'} = 1;
$hash{'D,F'} = 2;
$hash{'G,K'} = 3;

$hash{'E'};           # returns '2'
$hash{'BB'};          # returns '1'

$hash{'KL'};          # returns nothing ('undef')

There is also an object-oriented interface:

$hash = new Tie::RangeHash;

$hash->add('A,C', 1);
$hash->add('G,I', 2);

$hash->fetch('H');    # returns '2'

DESCRIPTION

This module allows hashes to associate a value with a range of keys rather than a single key.

For example, you could pass date ranges to the hash and then query it with a specific date, like so:

$cost{'1999-12-15,2000-01-14'} = 150;
$cost{'2000-01-15,2000-02-14'} = 103;
$cost{'2000-02-15,2000-03-14'} =  97;

and then query the cost on a specific date:

$this_cost = $cost{'2000-02-08'};

Numeric key ranges can also be used:

tie %hash, 'Tie::RangeHash', {
  Type => Tie::RangeHash::TYPE_NUMBER
};

$hash{'1.4,1.8'}      = 'Jim';
$hash{'1.0,1.399999'} = 'Ned';
$hash{'1.800001,2.0'} = 'Boo';

Custom comparison routines to support alternate datatypes can be implemented by specifying a new node type for Algorithm::SkipList.

Information to be added.

Object-Oriented Interface

Tie::RangeHash has an object-oriented interface as an alternative to using a tied hash.

new

Creates a new object.

$OBJ = Tie::RangeHash->new( %ATTR );

%ATTR is a hash containing the attributes described above. This is the same as the TIEHASH method used for tied hashes.

add

Adds a new key/value pair to the object.

$OBJ->add( $KEY, $VALUE );

$KEY may be a string value in the form of low,high or an array reference in the form of [ low, high ]. This is the same as the STORE method used for tied hashes.

fetch
$VALUE = $OBJ->fetch( $KEY );

Returns the value associated with $KEY. ($KEY may be in the form of low,high or a key between low and high.) This is the same as the FETCH method used for tied hashes.

fetch_key
$REAL_KEY = $OBJ->fetch( $KEY );

($REAL_KEY, $VALUE) = $OBJ->fetch( $KEY );

Like fetch, but it returns the key range that was matched rather than the value. If it is called in an array context, it will return the key and value.

key_exists
if ($OBJ->key_exists( $KEY )) { .. }

Returns true if $KEY has been defined (even if the value is undef). ($KEY is in the same form as is used by the fetch method.) This is the same as the EXISTS method used for tied hashes.

It is called key_exists so as not to be confused with the exists keyword in Perl.

clear
$OBJ->clear();

Deletes all keys and values defined in the object. This is the same as the CLEAR method used for tied hashes.

remove
$VALUE = $OBJ->remove( $KEY );

Deletes the $KEY from the object and returnes the associated value. ($KEY is in the same form as is used by the fetch method.) If $KEY is not the exact low,high range, a warning will be emitted. This is the same as the DELETE method used for tied hashes.

It is called remove so as not to be confused with the delete keyword in Perl.

first_key
$KEY = $OBJ->first_key();
next_key
$KEY = $OBJ->next_key($LAST_KEY);

Implementation Notes

Internally, the hash uses skip lists. Skip lists are an alternative to binary trees. For more information, see Algorithm::SkipList.

KNOWN ISSUES

The is a new version of the module and has behaves differently compared to older versions. This is due to using the Algorithm::SkipList module for maintaining the underlying data rather than re-implementing it. While this improves the maintainability with the code, it increases incompatability with previous versions.

Some of the changes include:

Overlapping keys cause fatal errors instead of warnings

Because the key comparison is now performed in the skip list node, there is no obvious way for it to give a warning and return a meaningful result. So instead the code dies. If you code relies on the possibility of using overlapping keys, then it may be more appropriate to have it test the code:

eval {
  $hash{'111,999'} = $value;
};

This error can also occur by merely testing a hash, so it is important to run some checks if you are testing hash ranges:

eval {
  if ($hash{'111,999'} == $value) { ... }
}
Keys can be redefined

Nodes can now be redefined. For example:

$hash{'1,3'} = $value;
...
$hash{'1,3'} = $new_value;
...
$hash{'2'}   = $new_value;

Note that a range is no longer required.

Non-range keys can be added.

When inserting a key, $hash{'x'} will be treated like $hash{'x,x'}.

Open-ended ranges are allowed.

Open ended ranges are now supported. So the following can be added:

$hash{',10'} = $upper_bound;
$hash{'11,'} = $lower_bound;
array references can no longer be keys.

The following is not supported anymore:

$hash{ \@array ) = $value;
warnings no longer registered.

Warning registration is no longer used. This may change in the future.

Custom separators and comparisons are not supported.

Only commas can be used as separators.

To customize separators and comparisons, you will have to specify a custom Algorithm::SkipList::Node method.

See the Changes file for a more complete list of incompatabilities.

If your code does not rely on these quirks, then you should be able to substitute with no problems.

SEE ALSO

A module with similar functionality for numerical values is Array::IntSpan.

Algorithm::SkipList for more information on skip lists.

AUTHOR

Robert Rothenberg <rrwo at cpan.org>

Acknowledgements

Charles Huff <charleshuff atdecisionresearch.com> for suggestions and bug reports.

Sam Tregar <sam at tregar.com> for optimization suggestions.

Various Perl Monks <http://www.perlmonks.org> for advice and code snippets.

Suggestions and Bug Reporting

Feedback is always welcome. Please use the CPAN Request Tracker at http://rt.cpan.org to submit bug reports.

LICENSE

Copyright (C) 2000-2004 Robert Rothenberg. All rights reserved. This program is free software; you can redistribute it and/or modify it under the same terms as Perl itself.