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, non-overlapping 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]; } and sub { $_[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), or undef.

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, return undef.

The node object is assumed to implement the following methods:

my $key = $node->key ();

my $val = $node->val ();

Return the node’s key and value, respectively.

my $node = $node->predecessor ();

my $node = $node->successor ();

Return the immediately preceeding and succeeding nodes, respectively, or undef.

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:

•

both are undef;

•

both are references, sharing the same refaddr;

•

the user’s value equality predicate returns true for the pair.

$rat->range_set_over ($lower, $upper, $value);

This class defines the range_set_over method as an alias to range_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 the range_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

Scalar::Util

AUTHOR

Ivan Shmakov <oneingray@gmail.com>

This library is free software; you can redistribute it and/or modify it under the terms of the 3-clause BSD license, as included within the code.