NAME

Tree::Interval - Perl implementation of an interval tree

SYNOPSIS

use Tree::Interval;

my $t = Tree::Interval->new();
$t->insert(3, 5, 'cat');
$t->insert(7, 15, 'dog');
my $v = $t->find(4);
my $min = $t->min();
my $max = $t->max();

DESCRIPTION

This is a perl implementation of an interval tree for non-overlapping intervals, based on Tree::RedBlack by Benjamin Holzman <bholzman@earthlink.net>. An interval tree is a binary tree which remains "balanced" i.e. the longest length from root to a node is at most one more than the shortest such length. It is fairly efficient; no operation takes more than O(log(N)) time.

A Tree::Interval object supports the following methods:

Tree::Interval->new()

Creates a new Interval tree object.

root()

Returns the root node of the tree. Note that this will either be undef if no nodes have been added to the tree, or a Tree::Interval::Node object.

cmp(coderef)

Use this method to set a comparator subroutine. The tree defaults to builtin Perl numerical comparisons. This subroutine should be just like a comparator subroutine to sort, except that it doesn't do the $a, $b trick; the two elements to compare will just be the first two items on the stack. For example,

sub example_comparator
{
   my ($ka, $kb) = @_;
   return $ka <=> $kb;
}

insert(low, high, value)

Adds a new node to the tree. The first two arguments are an interval which forms the key of the node, the third is its value and may not be undef. Overlapping or duplicate keys are an error. Errors are handled using die. Nothing is returned.

min()

Returns the node with the minimal key.

max()

Returns the node with the maximal key.

find(key)

Searches the tree to find the node whose interval contains the given key. Returns the value of that node, or undef if a node with that key isn't found.

values()

Returns a list of all the node values.

AUTHOR

Greg Banks <gnb@fastmail.fm>, heavily based on Tree::RedBlack by Benjamin Holzman <bholzman@earthlink.net>