NAME

Set::IntervalTree - Perform range-based lookups on sets of ranges.

SYNOPSIS

use Set::IntervalTree;
my $tree = Set::IntervalTree->new;
$tree->insert("ID1",100,200);
$tree->insert(2,50,100);
$tree->insert({id=>3},520,700);
$tree->insert($some_obj,1000,1100);

my $results = $tree->fetch(400,800);
print scalar(@$results)." intervals found.\n";

DESCRIPTION

Set::IntervalTree uses Interval Trees to store and efficiently look up ranges using a range-based lookup.

EXPORTS

Nothing.

METHODS

my $tree = Set::IntervalTree->new;

Creates a new interval tree object.

$tree->insert($object, $low, $high);

Insert a range into the interval tree and associate it with a 
perl scalar.

$object can be any perl scalar. This is what will be returned by fetch().
$low is the lower bound of the range.
$high is the upper bound of the range.

Ranges are represented as both-ends closed intervals.

my $results = $tree->fetch($low, $high)

Return an arrayref of perl objects whose ranges overlap 
the specified range.

$low is the lower bound of the region to query.
$high is the upper bound of the region to query.

Limitations

I still haven't implemented a $tree->remove() method to remove ranges from a tree.

A $tree->print() serialization method might be useful for debugging.

SEE ALSO

The source code for this module contains a reusable template-based C++ header for Interval trees that might be useful.

AUTHOR

Ben Booth, <bbooth@>

COPYRIGHT AND LICENSE

Copyright (C) 2010 by Ben Booth

This library is free software; you can redistribute it and/or modify it under the same terms as Perl itself, either Perl version 5.10.1 or, at your option, any later version of Perl 5 you may have available.