.\" -*- mode: troff; coding: utf-8 -*-
.\" Automatically generated by Pod::Man 5.01 (Pod::Simple 3.43)
.\"
.\" Standard preamble:
.\" ========================================================================
.de Sp \" Vertical space (when we can't use .PP)
.if t .sp .5v
.if n .sp
..
.de Vb \" Begin verbatim text
.ft CW
.nf
.ne \\$1
..
.de Ve \" End verbatim text
.ft R
.fi
..
.\" \*(C` and \*(C' are quotes in nroff, nothing in troff, for use with C<>.
.ie n \{\
.    ds C` ""
.    ds C' ""
'br\}
.el\{\
.    ds C`
.    ds C'
'br\}
.\"
.\" Escape single quotes in literal strings from groff's Unicode transform.
.ie \n(.g .ds Aq \(aq
.el       .ds Aq '
.\"
.\" If the F register is >0, we'll generate index entries on stderr for
.\" titles (.TH), headers (.SH), subsections (.SS), items (.Ip), and index
.\" entries marked with X<> in POD.  Of course, you'll have to process the
.\" output yourself in some meaningful fashion.
.\"
.\" Avoid warning from groff about undefined register 'F'.
.de IX
..
.nr rF 0
.if \n(.g .if rF .nr rF 1
.if (\n(rF:(\n(.g==0)) \{\
.    if \nF \{\
.        de IX
.        tm Index:\\$1\t\\n%\t"\\$2"
..
.        if !\nF==2 \{\
.            nr % 0
.            nr F 2
.        \}
.    \}
.\}
.rr rF
.\" ========================================================================
.\"
.IX Title "Set::IntervalTree 3pm"
.TH Set::IntervalTree 3pm 2024-03-07 "perl v5.38.2" "User Contributed Perl Documentation"
.\" For nroff, turn off justification.  Always turn off hyphenation; it makes
.\" way too many mistakes in technical documents.
.if n .ad l
.nh
.SH NAME
Set::IntervalTree \- Perform range\-based lookups on sets of ranges
.SH VERSION
.IX Header "VERSION"
version 0.12
.SH SYNOPSIS
.IX Header "SYNOPSIS"
.Vb 6
\&  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);
\&  my $window = $tree\->fetch_window(100,200);
\&  print scalar(@$results)." intervals found.\en";
\&
\&  # remove only items overlapping location 100..200 with values 
\&  # less than 100;
\&  my $removed = $tree\->remove(100,200 sub {
\&    my ($item, $low, $high) = @_;
\&    return $item < 100;
\&  });
.Ve
.SH DESCRIPTION
.IX Header "DESCRIPTION"
Set::IntervalTree uses Interval Trees to store and efficiently 
look up ranges using a range-based lookup.
.PP
All intervals are half-open, i.e. [1,3), [2,6), etc.
.SH EXPORTS
.IX Header "EXPORTS"
Nothing.
.SH METHODS
.IX Header "METHODS"
my \f(CW$tree\fR = Set::IntervalTree\->new;
.PP
.Vb 1
\&  Creates a new interval tree object.
.Ve
.PP
\&\f(CW$tree\fR\->insert($object, \f(CW$low\fR, \f(CW$high\fR);
.PP
.Vb 2
\&  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 half\-closed integer intervals.
.Ve
.PP
my \f(CW$results\fR = \f(CW$tree\fR\->fetch($low, \f(CW$high\fR)
.PP
.Vb 2
\&  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.
.Ve
.PP
my \f(CW$results\fR = \f(CW$tree\fR\->fetch_window($low, \f(CW$high\fR)
.PP
.Vb 2
\&  Return an arrayref of perl objects whose ranges are completely contained
\&  witin the specified range.
\&
\&  $low is the lower bound of the region to query.
\&  $high is the upper bound of the region to query.
.Ve
.PP
my \f(CW$nearest_up\fR = \f(CW$tree\fR\->fetch_nearest_up($query)
.PP
.Vb 2
\&  Search for the closest interval in upstream that does not contain the query
\&  and returns the perl object associated with it.
\&
\&  $query is the position to use for the search
.Ve
.PP
my \f(CW$nearest_down\fR = \f(CW$tree\fR\->fetch_nearest_down($query)
.PP
.Vb 2
\&  Search for the closest interval in downstream that does not contain the query
\&  and returns the perl object associated with it.
\&
\&  $query is the position to use for the search
.Ve
.PP
my \f(CW$removed\fR = \f(CW$tree\fR\->remove($low, \f(CW$high\fR [, optional \e&coderef]);
.PP
.Vb 5
\&  Remove items in the tree that overlap the region from $low to $high. 
\&  A coderef can be passed in as an optional third argument for filtering
\&  what is removed. The coderef receives the stored item, the low point,
\&  and the high point as its arguments. If the result value of the coderef
\&  is true, the item is removed, otherwise the item remains in the tree.
\&
\&  Returns the list of removed items.
.Ve
.PP
my \f(CW$removed\fR = \f(CW$tree\fR\->remove_window($low, \f(CW$high\fR [, optional \e&coderef]);
.PP
.Vb 6
\&  Remove items in the tree that are contained within the region from $low
\&  to $high.  A coderef can be passed in as an optional third argument
\&  for filtering what is removed. The coderef receives the stored item,
\&  the low point, and the high point as its arguments. If the result
\&  value of the coderef is true, the item is removed, otherwise the item
\&  remains in the tree.
\&
\&  Returns the list of removed items.
.Ve
.SH LIMITATIONS
.IX Header "LIMITATIONS"
A \f(CW$tree\fR\->\fBprint()\fR serialization method might be useful for debugging.
.SH "SEE ALSO"
.IX Header "SEE ALSO"
The source code for this module contains a reusable template-based 
C++ header for Interval trees that might be useful.
.SH AUTHORS
.IX Header "AUTHORS"
.IP \(bu 4
Benjamin Booth <benbooth@cpan.org>
.IP \(bu 4
Stephan Loyd <sloyd@cpan.org>
.SH "COPYRIGHT AND LICENSE"
.IX Header "COPYRIGHT AND LICENSE"
This software is copyright (c) 2012 by Benjamin Booth.
.PP
This is free software; you can redistribute it and/or modify it under
the same terms as the Perl 5 programming language system itself.