.\" Automatically generated by Pod::Man 4.14 (Pod::Simple 3.40) .\" .\" 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 .. .\" Set up some character translations and predefined strings. \*(-- will .\" give an unbreakable dash, \*(PI will give pi, \*(L" will give a left .\" double quote, and \*(R" will give a right double quote. \*(C+ will .\" give a nicer C++. Capital omega is used to do unbreakable dashes and .\" therefore won't be available. \*(C` and \*(C' expand to `' in nroff, .\" nothing in troff, for use with C<>. .tr \(*W- .ds C+ C\v'-.1v'\h'-1p'\s-2+\h'-1p'+\s0\v'.1v'\h'-1p' .ie n \{\ . ds -- \(*W- . ds PI pi . if (\n(.H=4u)&(1m=24u) .ds -- \(*W\h'-12u'\(*W\h'-12u'-\" diablo 10 pitch . if (\n(.H=4u)&(1m=20u) .ds -- \(*W\h'-12u'\(*W\h'-8u'-\" diablo 12 pitch . ds L" "" . ds R" "" . ds C` "" . ds C' "" 'br\} .el\{\ . ds -- \|\(em\| . ds PI \(*p . ds L" `` . ds R" '' . 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 "2020-11-09" "perl v5.32.0" "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 .IP "\(bu" 4 Stephan Loyd .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.