The Perl Toolchain Summit needs more sponsors. If your company depends on Perl, please support this very important event.
 / 
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.