Greg Banks >
Tree-Interval >
Tree::Interval

Module Version: 0.3.2
Tree::Interval - Perl implementation of an interval tree

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();

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.

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

syntax highlighting: