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