The following module was proposed for inclusion in the Module List:
modid: Tree::Interval
DSLIP: bdpOp
description: Perl implementation of an interval tree
userid: GNB (Greg Banks)
chapterid: 6 (Data_Type_Utilities)
communities:
similar:
rationale:
This is a perl implementation of an interval tree for
non-overlapping intervals, based on Tree::RedBlack by Benjamin
Holzman <[email protected]>. 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.
There is an existing Set::IntervalTree, but it a) has additional
complexity to deal with the more complex case of overlapping
intervals, b) is an XS wrapper around a C++ class c) was severely
broken when I tried it. This module is pure Perl, simpler, and by
handling the simple case of non-overlapping intervals can be
implemented as an easy extension of a working RedBlack tree module.
enteredby: GNB (Greg Banks)
enteredon: Fri Dec 16 05:14:31 2011 GMT
The resulting entry would be:
Tree::
::Interval bdpOp Perl implementation of an interval tree GNB
Thanks for registering,
--
The PAUSE
PS: The following links are only valid for module list maintainers:
Registration form with editing capabilities:
https://pause.perl.org/pause/authenquery?ACTION=add_mod&USERID=82900000_4192fecec2af560e&SUBMIT_pause99_add_mod_preview=1
Immediate (one click) registration:
https://pause.perl.org/pause/authenquery?ACTION=add_mod&USERID=82900000_4192fecec2af560e&SUBMIT_pause99_add_mod_insertit=1
Peek at the current permissions:
https://pause.perl.org/pause/authenquery?pause99_peek_perms_by=me&pause99_peek_perms_query=Tree%3A%3AInterval
