The London Perl and Raku Workshop takes place on 26th Oct 2024. If your company depends on Perl, please consider sponsoring and/or attending.
 / 
Tree-Interval-Fast-0.0.1
River stage zero No dependents
/ Tree::Interval::Fast

NAME

Tree::Interval::Fast - Perl extension for efficient creation and manipulation of interval trees.

VERSION

Version 0.0.1

DESCRIPTION

This module provides a simple and fast implementation of interval trees. It uses the Perl XS extension mechanism by providing a tiny wrapper around an efficient C library which does the core of the work.

SEE ALSO

Tree::Interval::Fast::Interval - implements an interval stored in the tree

SYNOPSIS

You can create an interval tree, add intervals to it and ask for intervals overlapping with a certain range.

use Tree::Interval::Fast;
use Tree::Interval::Fast::Interval;

# create the tree
my $foo = Tree::Interval::Fast->new();

# add some intervals
$tree->insert(Tree::Interval::Fast::Interval->new(15, 20, 10));
$tree->insert(Tree::Interval::Fast::Interval->new(10, 30, 20));
$tree->insert(Tree::Interval::Fast::Interval->new(17, 19, 30));
...

# query the tree for an overlapping interval
my $result = $tree->find(6., 7.);
printf "(%.2f, %.2f)", $result->low, $result->high;
print Dumper $result->data; # overlapping interval might store data

# another (unsuccesful) query
$result = $tree->find(1, 4);
if(!$result) {
  print "No overlapping interval with the query.";
}

# query the tree for all overlapping intervals
my $results = $tree->findall(8, 11);
foreach my $item (@{$results}) {
  print "Query overlaps with (%.2f, %.2f)\n", $item->low, $item->high;
}

METHODS

new

Arg [...]   : None

Example     : my $tree = Tree::Interval::Fast->new();
              carp "Unable to instantiate tree" unless defined $tree;

Description : Creates a new empty interval tree object.

Returntype  : An instance of Tree::Interval::Fast or undef
Exceptions  : None
Caller      : General
Status      : Stable

find

Arg [1]     : Number; query interval left boundary
Arg [2]     : Number; query interval right boundary

Example     : $result = $tree->find(6, 7);
              if($result) {
                printf "Found an overlapping interval: (%.2f, %.2f)\n", $result->low, $result->high
              } else { print "No overlapping interval with (6, 7)\n"; }

Description : Query the tree for an overlapping interval with the specified range.

Returntype  : An instance of Tree::Interval::Fast::Interval, representing the overlapping
              interval, if found, as stored in the tree or undef.
Exceptions  : None
Caller      : General
Status      : Unstable

findall

Arg [1]     : Number; query interval left boundary
Arg [2]     : Number; query interval right boundary

Example     : $results = $tree->findall(6, 7);
              if(!$result) {
                print "No overlapping intervals with (6, 7)\n"; 
              } else {
                foreach my $item (@{$results}) {
                  print "Found (%.2f, %.2f)\n", $item->low, $item->high;
                }
              }

Description : Query the tree for all overlapping intervals with the specified range.

Returntype  : ArraryRef; the list of Tree::Interval::Fast::Interval instances, representing 
              each one an overlapping interval, or undef if no interval is found.
Exceptions  : None
Caller      : General
Status      : Stable

insert

Arg [1]     : Tree::Interval::Fast::Interval; the interval to insert in the tree

Example     : my $interval = Tree::Interval::Fast::Interval->new(100, 1000, [1, 2, 3]);
              my $ok = $tree->insert($interval);
              if($ok) {
                printf "Could insert (100, 1000)\n";
              } else { print "Something went wrong\n"; }

Description : Insert an interval in the tree.

Returntype  : True/False, depending on whether the insertion was successful or not
Exceptions  : None
Caller      : General
Status      : Unstable

remove

Arg [1]     : Tree::Interval::Fast::Interval; the interval to remove from the tree

Example     : my $interval = Tree::Interval::Fast::Interval->new(100, 1000, undef);
              my $ok = $tree->remove($interval);
              if($ok) {
                printf "Could remove (100, 1000)\n";
              } else { print "Something went wrong\n"; }

Description : Remove an interval in the tree.

Returntype  : True/False, depending on whether the operation was successful or not
Exceptions  : None
Caller      : General
Status      : Unstable

size

Arg [...]   : None

Example     : printf "Size of the tree: %d\n", $tree->size();

Description : Get the size (number of intervals) of the tree.

Returntype  : Int; the number of intervals currently stored in the tree.
Exceptions  : None
Caller      : General
Status      : Stable

EXPORT

None

AUTHOR

Alessandro Vullo, <avullo at cpan.org>

BUGS

Please report any bugs or feature requests to bug-tree-interval-fast at rt.cpan.org, or through the web interface at http://rt.cpan.org/NoAuth/ReportBug.html?Queue=Tree-Interval-Fast. I will be notified, and then you'll automatically be notified of progress on your bug as I make changes.

CONTRIBUTING

You can obtain the most recent development version of this module via the GitHub repository at https://github.com/avullo/AVLTree. Please feel free to submit bug reports, patches etc.

SUPPORT

You can find documentation for this module with the perldoc command.

perldoc Tree::Interval::Fast

You can also look for information at:

ACKNOWLEDGEMENTS

I am very grateful to Julienne Walker for generously providing the source code of his production quality C library for handling AVL balanced trees. The library has been adapted to implement interval trees.

Julienne's library can be found at:

http://www.eternallyconfuzzled.com/Libraries.aspx

LICENSE AND COPYRIGHT

Copyright 2018 Alessandro Vullo.

This program is free software; you can redistribute it and/or modify it under the terms of either: the GNU General Public License as published by the Free Software Foundation; or the Artistic License.

See http://dev.perl.org/licenses/ for more information.