NAME

Tree::Range::RB – range tree implemented on top of Tree::RB

SYNOPSIS

require Tree::Range::RB;

sub ncmp { $_[0] <=> $_[1]; }
my $nrt
    = Tree::Range::RB->new ({ "cmp" => \&ncmp });
$nrt->range_set (100, 200, "foo");
$nrt->range_set (200, 300, "bar");
$nrt->range_set (150, 250, "baz");
$nrt->range_set (400, 500, "qux");
my $r100 = $nrt->get_range (100);
## now $r100 is  "foo"
my @r200 = $nrt->get_range (200);
## now @r200 is ("baz", 150, 250)
my @r300 = $nrt->get_range (300);
## now @r300 is (undef, 300, 400)
my $free_p = $nrt->range_free_p (200, 300);
## now $free_p is a false value
my ($ic)
    = $nrt->range_iter_closure (450);
my @ri1 = $ic->();
## now @ri1 is ("qux", 400, 500)
my @ri2 = $ic->();
## now @ri2 is (undef, 500, undef)
my @ri3 = $ic->();
## now @ri3 is ()

sub cmp { $_[0] cmp $_[1]; }
my $srt
    = Tree::Range::RB->new ({ "cmp" => \&cmp });
$srt->range_set (qw (apple  peach   1));
$srt->range_set (qw (banana cherry  2));
my @rmango = $srt->get_range ("mango");
## now @rmango is (1, "cherry", "peach")

DESCRIPTION

This class implements a range tree (as described in Tree::Range::base) on top of the Tree::RB red-black tree implementation. It inherits from Tree::Range::base.

INTERFACE

my $rat = Tree::Range::RB->new (\%options);

Create and return a new range tree object.

Available options are as follows.

cmp

Specifies the comparison function for the range tree. Possible values include sub { $_[0] cmp $_[1]; } and sub { $_[0] <=> $_[1]; }.

If not given, the cmp string comparison operator will be used.

equal-p

Specifies the optional value equality predicate.

See the range_set method description in Tree::Range::base for more information.

leftmost

Specifies the value the keys lower than the lowest bound are mapped to. If left unspecified, undef will be used.

The following methods are inherited from Tree::Range::base. See the Tree::Range::base documentation for more information.

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.

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 Tree::Range::RB::Conflict documentation.)

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

This method is defined in Tree::Range::base as an alias to range_set.

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.

The following methods are implemented in order to inherit from Tree::Range::base. See the Tree::Range::base documentation for more information.

my $cmp_fn = $rat->cmp_fn ();

my $equal_p_fn = $rat->value_equal_p_fn ();

my $leftmost = $rat->leftmost_value ();

Return the comparison function, the value equality predicate, or the value the keys lower than the lowest bound are mapped to, respectively.

These values are the same as specified at the object creation time, or the respective defaults.

$rat->put ($key, $value)

my $node = $rat->min_node ($key)

my $node = $rat->max_node ($key)

my $node = $rat->lookup_leq ($key)

my $node = $rat->lookup_geq ($key)

my $okay = $put->delete ($key)

Associate a (key, value) pair with the value of $key, return the node object having the minimum or the maximum key in the tree, perform a less-than-or-equal or greater-than-or-equal lookup (returning a node object), or remove any such association, respectively.

The delete method will return a true value upon successful completion.

These methods are mapped to the put, min, max, lookup and delete methods of the underlying Tree::RB object.

SEE ALSO

Tree::Interval, Tree::RB, Tree::Range::base Tree::Range::RB::Conflict

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.