Data-IntervalTree-Shared

 view release on metacpan or  search on metacpan

MANIFEST  view on Meta::CPAN

intervaltree.h
Changes
eg/calendar.pl
eg/cross_process.pl
lib/Data/IntervalTree/Shared.pm
Makefile.PL
MANIFEST			This list of files
MANIFEST.SKIP
README
Shared.xs
t/01-basic.t
t/02-frozen.t
t/03-recover.t

README  view on Meta::CPAN

        # share the index across processes via a backing file
        my $shared = Data::IntervalTree::Shared->new("/tmp/bookings.it", 100_000);

DESCRIPTION
    An interval tree in shared memory: a set of integer intervals "[lo, hi]"
    that answers overlap and stabbing queries far faster than scanning every
    interval -- "which stored intervals contain point "p"?" and "which overlap
    the range "[lo, hi]"?". It complements Data::SegmentTree::Shared
    (range-aggregate over indexed positions) and Data::KDTree::Shared
    (multi-dimensional points): this one indexes a set of intervals for
    containment/overlap. Classic uses: scheduling and calendar conflict
    detection, IP-range to owner lookup, genomic feature overlap, and "what is
    active at time "t"".

    Endpoints are signed 64-bit integers (timestamps, IP addresses, genomic
    coordinates -- exact, with no floating-point edge cases). Each interval
    carries a user-supplied 64-bit id (defaulting to its insertion index),
    returned with every match. Internally it is an augmented balanced binary
    search tree keyed by the low endpoint, each node caching the maximum high
    endpoint of its subtree so a query prunes whole subtrees that end before
    it.

eg/calendar.pl  view on Meta::CPAN

use FindBin;
# Prefer a freshly built blib/ (picks up both lib and the compiled .so),
# fall back to lib/ or the installed module.
BEGIN {
    my $blib = "$FindBin::Bin/../blib";
    if (-d "$blib/arch") { require blib; blib->import($blib) }
    else { unshift @INC, "$FindBin::Bin/../lib" }
}
use Data::IntervalTree::Shared;

# A booking calendar: each reservation is a half-open time interval keyed by a
# booking id.  An interval tree answers "what's booked at time T?" (stab) and
# "does a proposed slot clash with anything?" (overlaps) in O(log n + matches),
# instead of scanning every booking.

my $cal = Data::IntervalTree::Shared->new(undef, 100_000);

# add some bookings: [start, end] in minutes-since-midnight, id = booking number
my @bookings = (
    [540,  600, 1],   #  9:00-10:00  room A
    [570,  630, 2],   #  9:30-10:30  room B (overlaps 1)

lib/Data/IntervalTree/Shared.pm  view on Meta::CPAN

    my $shared = Data::IntervalTree::Shared->new("/tmp/bookings.it", 100_000);

=head1 DESCRIPTION

An B<interval tree> in shared memory: a set of integer intervals C<[lo, hi]> that
answers B<overlap> and B<stabbing> queries far faster than scanning every
interval -- "which stored intervals contain point C<p>?" and "which overlap the
range C<[lo, hi]>?". It complements L<Data::SegmentTree::Shared> (range-aggregate
over indexed positions) and L<Data::KDTree::Shared> (multi-dimensional points):
this one indexes a B<set of intervals> for containment/overlap. Classic uses:
scheduling and calendar conflict detection, IP-range to owner lookup, genomic
feature overlap, and "what is active at time C<t>".

Endpoints are B<signed 64-bit integers> (timestamps, IP addresses, genomic
coordinates -- exact, with no floating-point edge cases). Each interval carries a
user-supplied 64-bit B<id> (defaulting to its insertion index), returned with
every match. Internally it is an B<augmented balanced binary search tree> keyed
by the low endpoint, each node caching the maximum high endpoint of its subtree
so a query prunes whole subtrees that end before it.

Intervals are B<appended in O(1)> and the balanced tree is B<bulk-built on the