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)

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.

$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.

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->lookup_leq ($key)

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

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

Associate a (key, value) pair with the value of $key, 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, lookup and delete methods of the underlying Tree::RB object.

SEE ALSO

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

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.