Debian Codegraph @

src/libs/IntervalTree.h

raw
1 /*
2 *
3 * Copyright (c) 2011 Erik Garrison
4 *
5 * Permission is hereby granted, free of charge, to any person obtaining a copy of
6 * this software and associated documentation files (the "Software"), to deal in
7 * the Software without restriction, including without limitation the rights to
8 * use, copy, modify, merge, publish, distribute, sublicense, and/or sell copies
9 * of the Software, and to permit persons to whom the Software is furnished to do
10 * so, subject to the following conditions:
11
12 * The above copyright notice and this permission notice shall be included in all
13 * copies or substantial portions of the Software.
14
15 * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
16 * IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
17 * FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE
18 * AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
19 * LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM,
20 * OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE
21 * SOFTWARE.
22 */
23
24 // Pulled from https://github.com/ekg/intervaltree - thanks to Erik Garrison
25
26 #ifndef __INTERVAL_TREE_H
27 #define __INTERVAL_TREE_H
28
29 #include <vector>
30 #include <algorithm>
31 #include <iostream>
32
33 template <class T, typename K = std::size_t>
34 class Interval {
35 public:
36 K start;
37 K stop;
38 T value;
39 Interval(K s, K e, const T& v)
40 : start(s)
41 , stop(e)
42 , value(v)
43 { }
44 };
45
46 template <class T, typename K>
47 K intervalStart(const Interval<T,K>& i) {
48 return i.start;
49 }
50
51 template <class T, typename K>
52 K intervalStop(const Interval<T,K>& i) {
53 return i.stop;
54 }
55
56 template <class T, typename K>
57 std::ostream& operator<<(std::ostream& out, Interval<T,K>& i) {
58 out << "Interval(" << i.start << ", " << i.stop << "): " << i.value;
59 return out;
60 }
61
62 template <class T, typename K = std::size_t>
63 class IntervalStartSorter {
64 public:
65 bool operator() (const Interval<T,K>& a, const Interval<T,K>& b) {
66 return a.start < b.start;
67 }
68 };
69
70 template <class T, typename K = std::size_t>
71 class IntervalTree {
72
73 public:
74 typedef Interval<T,K> interval;
75 typedef std::vector<interval> intervalVector;
76 typedef IntervalTree<T,K> intervalTree;
77
78 intervalVector intervals;
79 intervalTree* left;
80 intervalTree* right;
81 K center;
82
83 IntervalTree<T,K>(void)
84 : left(NULL)
85 , right(NULL)
86 , center(0)
87 { }
88
89 IntervalTree<T,K>(const intervalTree& other)
90 : left(NULL)
91 , right(NULL)
92 {
93 center = other.center;
94 intervals = other.intervals;
95 if (other.left) {
96 left = new intervalTree(*other.left);
97 }
98 if (other.right) {
99 right = new intervalTree(*other.right);
100 }
101 }
102
103 IntervalTree<T,K>& operator=(const intervalTree& other) {
104 center = other.center;
105 intervals = other.intervals;
106 if (other.left) {
107 left = new intervalTree(*other.left);
108 } else {
109 if (left) delete left;
110 left = NULL;
111 }
112 if (other.right) {
113 right = new intervalTree(*other.right);
114 } else {
115 if (right) delete right;
116 right = NULL;
117 }
118 return *this;
119 }
120
121 IntervalTree<T,K>(
122 intervalVector& ivals,
123 std::size_t depth = 16,
124 std::size_t minbucket = 64,
125 K leftextent = 0,
126 K rightextent = 0,
127 std::size_t maxbucket = 512
128 )
129 : left(NULL)
130 , right(NULL)
131 {
132
133 --depth;
134 IntervalStartSorter<T,K> intervalStartSorter;
135 if (depth == 0 || (ivals.size() < minbucket && ivals.size() < maxbucket)) {
136 std::sort(ivals.begin(), ivals.end(), intervalStartSorter);
137 intervals = ivals;
138 } else {
139 if (leftextent == 0 && rightextent == 0) {
140 // sort intervals by start
141 std::sort(ivals.begin(), ivals.end(), intervalStartSorter);
142 }
143
144 K leftp = 0;
145 K rightp = 0;
146 K centerp = 0;
147
148 if (leftextent || rightextent) {
149 leftp = leftextent;
150 rightp = rightextent;
151 } else {
152 leftp = ivals.front().start;
153 std::vector<K> stops;
154 stops.resize(ivals.size());
155 transform(ivals.begin(), ivals.end(), stops.begin(), intervalStop<T,K>);
156 rightp = *max_element(stops.begin(), stops.end());
157 }
158
159 //centerp = ( leftp + rightp ) / 2;
160 centerp = ivals.at(ivals.size() / 2).start;
161 center = centerp;
162
163 intervalVector lefts;
164 intervalVector rights;
165
166 for (typename intervalVector::iterator i = ivals.begin(); i != ivals.end(); ++i) {
167 interval& interval = *i;
168 if (interval.stop < center) {
169 lefts.push_back(interval);
170 } else if (interval.start > center) {
171 rights.push_back(interval);
172 } else {
173 intervals.push_back(interval);
174 }
175 }
176
177 if (!lefts.empty()) {
178 left = new intervalTree(lefts, depth, minbucket, leftp, centerp);
179 }
180 if (!rights.empty()) {
181 right = new intervalTree(rights, depth, minbucket, centerp, rightp);
182 }
183 }
184 }
185
186 void findOverlapping(K start, K stop, intervalVector& overlapping) const {
187 if (!intervals.empty() && ! (stop < intervals.front().start)) {
188 for (typename intervalVector::const_iterator i = intervals.begin(); i != intervals.end(); ++i) {
189 const interval& interval = *i;
190 if (interval.stop >= start && interval.start <= stop) {
191 overlapping.push_back(interval);
192 }
193 }
194 }
195
196 if (left && start <= center) {
197 left->findOverlapping(start, stop, overlapping);
198 }
199
200 if (right && stop >= center) {
201 right->findOverlapping(start, stop, overlapping);
202 }
203
204 }
205
206 void findContained(K start, K stop, intervalVector& contained) const {
207 if (!intervals.empty() && ! (stop < intervals.front().start)) {
208 for (typename intervalVector::const_iterator i = intervals.begin(); i != intervals.end(); ++i) {
209 const interval& interval = *i;
210 if (interval.start >= start && interval.stop <= stop) {
211 contained.push_back(interval);
212 }
213 }
214 }
215
216 if (left && start <= center) {
217 left->findContained(start, stop, contained);
218 }
219
220 if (right && stop >= center) {
221 right->findContained(start, stop, contained);
222 }
223
224 }
225
226 ~IntervalTree(void) {
227 // traverse the left and right
228 // delete them all the way down
229 if (left) {
230 delete left;
231 }
232 if (right) {
233 delete right;
234 }
235 }
236
237 };
238
239 #endif