NAME
Tree::Range::base – base class for range tree implementations
SYNOPSIS
package Tree::Range::Foo;
require Tree::Foo;
require Tree::Range::base;
push (our @ISA, qw (Tree::Range::base));
## Define cmp_fn, value_equal_p_fn, leftmost_value,
## lookup_leq, lookup_geq, min_node, max_node,
## put, and delete here
DESCRIPTION
This class is intended to allow for easy creation of range tree classes on top of arbitrary trees.
A range tree is defined here as an object, which maps values (keys) lying within a finite number of continuous, nonoverlapping subsets (ranges) of an ordered (as defined by the comparison function) set, to arbitrary values.
Specifically, this class provides implementations of the get_range
, range_free_p
, range_iter_closure
, and range_set
methods on top of the cmp_fn
, value_equal_p_fn
, leftmost_value
, lookup_leq
, lookup_geq
, min_node
, max_node
, put
, and delete
ones.
In the terms of the underlying tree object, the value is associated with the range extending from the lower (leftmost) inclusive bound, serving as the tree node’s own key, to the upper (rightmost) exclusive bound, which is the successor’s node key.
In particular, this means that the range tree maps the keys of the underlying tree to the same values as the underlying tree itself.
INTERFACE
Note that the methods below are used, and not implemented by this base class.
my $cmp_fn = $rat>cmp_fn ();

Return the comparison function for the range tree.
Possible values include
sub { $_[0] cmp $_[1]; }
andsub { $_[0] <=> $_[1]; }
. my $equal_p_fn = $rat>value_equal_p_fn ();

Return the value equality predicate.
A possible value is
sub { $_[0] eq $_[1]; }
, assuming that the values dealt with will all be either simple strings, references (including objects), orundef
.See the
range_set
method description for more information. my $leftmost = $rat>leftmost_value ();

Return the value the keys lower than the lowest bound are mapped to.
See the
range_set
method description for more information. my $node = $rat>lookup_leq ($key)
my $node = $rat>lookup_geq ($key)

Return the tree node object associated with the key specified.
If the tree has no such node, the one that would immediately preceed (
lookup_leq
) or succeed (lookup_geq
) it is returned instead. Should no such node be available, either, returnundef
.The node object is assumed to implement the following methods:
my $node = $rat>min_node ($key)
my $node = $rat>max_node ($key)

Return the tree node objects associated with the minimum and maximum keys currently in the tree.
This base class uses these methods solely in the
range_iter_closure
method’s implementation, when no explicit key to start iteration from is given. $rat>put ($key, $value)
my $okay = $put>delete ($key)

Associate a (key, value) pair with the value of
$key
, or remove such association, respectively.The
delete
method is assumed to return a true value upon successful completion.
The following methods are the only actually implemented by this base class.
my $v = $rat>get_range ($key)
my ($v, $lower, $upper) = $rat>get_range ($key)

Return the value associated with the range
$key
lies within.In the list context, return also the range’s lower and upper bounds.
The current implementation will omit the upper bound from the resulting list if such a range extends rightwards indefinitely. The lower bound will also be omitted if the key is less than any currently known lower bound. (In which case the leftmost value will be returned.)
The caller should accept the values to be either omitted or
undef
under the conditions stated above. my $free_p = $rat>range_free_p ($lower, $upper)

Return a true value if the range specified is either unassociated, or associated with the leftmost value (as determined by the value equality predicate.) Return a false value otherwise.
$rat>range_set ($lower, $upper, $value);

Associate the keys lying between
$lower
(inclusive) and$upper
(exclusive) with$value
.Raise an exception (i. e., die) unless the upper bound is greater than the lower one, as determined by the comparison function.
All the overlapping range associations, if any, are overwritten. (But see also the
range_set_over
method description below, and also the Tree::Range::conflict documentation.) Consider, e. g.:## assuming numeric (<=>) comparison function $rat>range_set (100, 200, "foo"); $rat>range_set (200, 300, "bar"); $rat>range_set (150, 250, "baz");
Assuming an initially empty range tree, this sequence will divide the 100–300 range into three subranges, namely: 100–150 (
foo
), 150–250 (bar
), 250–300 (baz
).Thus:
my @r = $rat>get_range (200); ## now @r is ("baz", 150, 250)
Associating the leftmost value with a range can be thought of as “deleting” such a range.
In addition to the ranges being automatically split as necessary, the adjacent ones will also be merged, should it be possible to prove that the overall key to value mapping (taking the value equality predicate used into account) is preserved by the change. Consider, e. g.:
## assuming numeric (<=>) comparison function my @a = ("foo"); $rat>range_set (100, 150, \@a); $rat>range_set (250, 300, \@a); $rat>range_set (125, 275, \@a); my @r = $rat>get_range (200); ## now @r is (\@a, 100, 300)
Such optimization is performed whenever the values of the adjacent ranges satisfy either of the following conditions:
$rat>range_set_over ($lower, $upper, $value);

This class defines the
range_set_over
method as an alias torange_set
. The latter, however, is overridden by the Tree::Range::conflict class, so that it fails instead of writing over the ranges associated with a value other than the leftmost one (as determined by therange_free_p
method), while this method remains unaltered and available.See Tree::Range::conflict for more information.
my $ic = $rat>range_iter_closure ();
my $ic = $rat>range_iter_closure ($key);
my $ic = $rat>range_iter_closure ($key, $descending_p);
while ((my ($v, $lower, $upper) = $ic>())) { … }
while ((my $v = $ic>())) { … }

Return a range iterator closure.
If
$descending_p
is given and true, the closure will return ranges so that the respective keys are in descending order (as defined by the comparison function.) The ascending order will be used otherwise.The first range returned by the closure will be the one containing the key specified, if any, or the first range of the tree for the order chosen.
Either way, the first range will be determined at the time of the first call to the iterator closure.
Note that the behavior of the closure is undefined if the tree is modified while the iteration is in progress. It is safe, however, to modify the tree before the closure is called for the first time.
Also to note is that the closure returns only the associated value in scalar context, thus matching the behavior of the
get_range
method.
SEE ALSO
Tree::Range::conflict, Tree::Range::RB
AUTHOR
Ivan Shmakov <oneingray@gmail.com>
This library is free software; you can redistribute it and/or modify it under the terms of the 3clause BSD license, as included within the code.