1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
|
package Set::IntervalTree;
# ABSTRACT: Perform range-based lookups on sets of ranges
use 5.006001;
use strict;
use warnings;
use Carp;
our $VERSION = '0.12'; # VERSION
require Exporter;
use AutoLoader;
our @ISA = qw(Exporter);
# Items to export into callers namespace by default. Note: do not export
# names by default without a very good reason. Use EXPORT_OK instead.
# Do not simply export all your public functions/methods/constants.
# This allows declaration use Set::IntervalTree ':all';
# If you do not need this, moving things directly into @EXPORT or @EXPORT_OK
# will save memory.
our %EXPORT_TAGS = ( 'all' => [ qw(
) ] );
our @EXPORT_OK = ( @{ $EXPORT_TAGS{'all'} } );
our @EXPORT = qw(
);
sub AUTOLOAD {
# This AUTOLOAD is used to 'autoload' constants from the constant()
# XS function.
my $constname;
our $AUTOLOAD;
($constname = $AUTOLOAD) =~ s/.*:://;
croak "&Set::IntervalTree::constant not defined!" if $constname eq 'constant';
my ($error, $val) = constant($constname);
if ($error) { croak $error; }
{
no strict 'refs';
# Fixed between 5.005_53 and 5.005_61
#XXX if ($] >= 5.00561) {
#XXX *$AUTOLOAD = sub () { $val };
#XXX }
#XXX else {
*$AUTOLOAD = sub { $val };
#XXX }
}
goto &$AUTOLOAD;
}
require XSLoader;
XSLoader::load('Set::IntervalTree', $VERSION);
# Preloaded methods go here.
# Autoload methods go after =cut, and are processed by the autosplit program.
1;
__END__
=pod
=encoding UTF-8
=head1 NAME
Set::IntervalTree - Perform range-based lookups on sets of ranges
=head1 VERSION
version 0.12
=head1 SYNOPSIS
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.\n";
# 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;
});
=head1 DESCRIPTION
Set::IntervalTree uses Interval Trees to store and efficiently
look up ranges using a range-based lookup.
All intervals are half-open, i.e. [1,3), [2,6), etc.
=head1 EXPORTS
Nothing.
=head1 METHODS
my $tree = Set::IntervalTree->new;
Creates a new interval tree object.
$tree->insert($object, $low, $high);
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.
my $results = $tree->fetch($low, $high)
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.
my $results = $tree->fetch_window($low, $high)
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.
my $nearest_up = $tree->fetch_nearest_up($query)
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
my $nearest_down = $tree->fetch_nearest_down($query)
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
my $removed = $tree->remove($low, $high [, optional \&coderef]);
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.
my $removed = $tree->remove_window($low, $high [, optional \&coderef]);
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.
=head1 LIMITATIONS
A $tree->print() serialization method might be useful for debugging.
=head1 SEE ALSO
The source code for this module contains a reusable template-based
C++ header for Interval trees that might be useful.
=head1 AUTHORS
=over 4
=item *
Benjamin Booth <benbooth@cpan.org>
=item *
Stephan Loyd <sloyd@cpan.org>
=back
=head1 COPYRIGHT AND LICENSE
This software is copyright (c) 2012 by Benjamin Booth.
This is free software; you can redistribute it and/or modify it under
the same terms as the Perl 5 programming language system itself.
=cut
|
