Debian Codegraph @

README

raw
1 NAME
2
3 Set::IntervalTree - Perform range-based lookups on sets of ranges
4
5 VERSION
6
7 version 0.12
8
9 SYNOPSIS
10
11 use Set::IntervalTree;
12 my $tree = Set::IntervalTree->new;
13 $tree->insert("ID1",100,200);
14 $tree->insert(2,50,100);
15 $tree->insert({id=>3},520,700);
16 $tree->insert($some_obj,1000,1100);
17
18 my $results = $tree->fetch(400,800);
19 my $window = $tree->fetch_window(100,200);
20 print scalar(@$results)." intervals found.\n";
21
22 # remove only items overlapping location 100..200 with values
23 # less than 100;
24 my $removed = $tree->remove(100,200 sub {
25 my ($item, $low, $high) = @_;
26 return $item < 100;
27 });
28
29 DESCRIPTION
30
31 Set::IntervalTree uses Interval Trees to store and efficiently look up
32 ranges using a range-based lookup.
33
34 All intervals are half-open, i.e. [1,3), [2,6), etc.
35
36 EXPORTS
37
38 Nothing.
39
40 METHODS
41
42 my $tree = Set::IntervalTree->new;
43
44 Creates a new interval tree object.
45
46 $tree->insert($object, $low, $high);
47
48 Insert a range into the interval tree and associate it with a
49 perl scalar.
50
51 $object can be any perl scalar. This is what will be returned by fetch().
52 $low is the lower bound of the range.
53 $high is the upper bound of the range.
54
55 Ranges are represented as half-closed integer intervals.
56
57 my $results = $tree->fetch($low, $high)
58
59 Return an arrayref of perl objects whose ranges overlap
60 the specified range.
61
62 $low is the lower bound of the region to query.
63 $high is the upper bound of the region to query.
64
65 my $results = $tree->fetch_window($low, $high)
66
67 Return an arrayref of perl objects whose ranges are completely contained
68 witin the specified range.
69
70 $low is the lower bound of the region to query.
71 $high is the upper bound of the region to query.
72
73 my $nearest_up = $tree->fetch_nearest_up($query)
74
75 Search for the closest interval in upstream that does not contain the query
76 and returns the perl object associated with it.
77
78 $query is the position to use for the search
79
80 my $nearest_down = $tree->fetch_nearest_down($query)
81
82 Search for the closest interval in downstream that does not contain the query
83 and returns the perl object associated with it.
84
85 $query is the position to use for the search
86
87 my $removed = $tree->remove($low, $high [, optional \&coderef]);
88
89 Remove items in the tree that overlap the region from $low to $high.
90 A coderef can be passed in as an optional third argument for filtering
91 what is removed. The coderef receives the stored item, the low point,
92 and the high point as its arguments. If the result value of the coderef
93 is true, the item is removed, otherwise the item remains in the tree.
94
95 Returns the list of removed items.
96
97 my $removed = $tree->remove_window($low, $high [, optional \&coderef]);
98
99 Remove items in the tree that are contained within the region from $low
100 to $high. A coderef can be passed in as an optional third argument
101 for filtering what is removed. The coderef receives the stored item,
102 the low point, and the high point as its arguments. If the result
103 value of the coderef is true, the item is removed, otherwise the item
104 remains in the tree.
105
106 Returns the list of removed items.
107
108 LIMITATIONS
109
110 A $tree->print() serialization method might be useful for debugging.
111
112 SEE ALSO
113
114 The source code for this module contains a reusable template-based C++
115 header for Interval trees that might be useful.
116
117 AUTHORS
118
119 * Benjamin Booth <[email protected]>
120
121 * Stephan Loyd <[email protected]>
122
123 COPYRIGHT AND LICENSE
124
125 This software is copyright (c) 2012 by Benjamin Booth.
126
127 This is free software; you can redistribute it and/or modify it under
128 the same terms as the Perl 5 programming language system itself.
129