NAME

Tree::Range::base – base class for range tree implementations

SYNOPSIS

  package Tree::Range::Foo;
  use base 'Tree::Range::base';

  require Tree::Foo;

  ## Define cmp_fn, value_equal_p_fn, leftmost_value,
  ## lookup_leq, lookup_geq, put, 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 and range_set methods on top of the cmp_fn, value_equal_p_fn, leftmost_value, lookup_leq, lookup_geq, 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, 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.

$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 two methods are those which are 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.

$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. 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 though of as “deleting” such a range.

In addition to the ranges being automatically split as necessary, the adjacent ones could also be merged, so that:

    ## 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 any 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.

SEE ALSO

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.