1 | //===-- IntervalTree.h ------------------------------------------*- C++ -*-===// |
2 | // |
3 | // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions. |
4 | // See https://llvm.org/LICENSE.txt for license information. |
5 | // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception |
6 | // |
7 | //===----------------------------------------------------------------------===// |
8 | // |
9 | // This file implements an interval tree. |
10 | // |
11 | // Further information: |
12 | // https://en.wikipedia.org/wiki/Interval_tree |
13 | // |
14 | //===----------------------------------------------------------------------===// |
15 | |
16 | #ifndef LLVM_ADT_INTERVALTREE_H |
17 | #define LLVM_ADT_INTERVALTREE_H |
18 | |
19 | #include "llvm/ADT/SmallVector.h" |
20 | #include "llvm/Support/Allocator.h" |
21 | #include "llvm/Support/Format.h" |
22 | #include "llvm/Support/raw_ostream.h" |
23 | #include <algorithm> |
24 | #include <cassert> |
25 | #include <iterator> |
26 | |
27 | // IntervalTree is a light tree data structure to hold intervals. It allows |
28 | // finding all intervals that overlap with any given point. At this time, |
29 | // it does not support any deletion or rebalancing operations. |
30 | // |
31 | // The IntervalTree is designed to be set up once, and then queried without |
32 | // any further additions. |
33 | // |
34 | // Synopsis: |
35 | // Closed intervals delimited by PointT objects are mapped to ValueT objects. |
36 | // |
37 | // Restrictions: |
38 | // PointT must be a fundamental type. |
39 | // ValueT must be a fundamental or pointer type. |
40 | // |
41 | // template <typename PointT, typename ValueT, typename DataT> |
42 | // class IntervalTree { |
43 | // public: |
44 | // |
45 | // IntervalTree(); |
46 | // ~IntervalTree(): |
47 | // |
48 | // using IntervalReferences = SmallVector<IntervalData *>; |
49 | // |
50 | // void create(); |
51 | // void insert(PointT Left, PointT Right, ValueT Value); |
52 | // |
53 | // IntervalReferences getContaining(PointT Point); |
54 | // static void sortIntervals(IntervalReferences &Intervals, Sorting Sort); |
55 | // |
56 | // find_iterator begin(PointType Point) const; |
57 | // find_iterator end() const; |
58 | // |
59 | // bool empty() const; |
60 | // void clear(); |
61 | // |
62 | // void print(raw_ostream &OS, bool HexFormat = true); |
63 | // }; |
64 | // |
65 | //===----------------------------------------------------------------------===// |
66 | // |
67 | // In the below given dataset |
68 | // |
69 | // [a, b] <- (x) |
70 | // |
71 | // 'a' and 'b' describe a range and 'x' the value for that interval. |
72 | // |
73 | // The following data are purely for illustrative purposes: |
74 | // |
75 | // [30, 35] <- (3035), [39, 50] <- (3950), [55, 61] <- (5561), |
76 | // [31, 56] <- (3156), [12, 21] <- (1221), [25, 41] <- (2541), |
77 | // [49, 65] <- (4965), [71, 79] <- (7179), [11, 16] <- (1116), |
78 | // [20, 30] <- (2030), [36, 54] <- (3654), [60, 70] <- (6070), |
79 | // [74, 80] <- (7480), [15, 40] <- (1540), [43, 43] <- (4343), |
80 | // [50, 75] <- (5075), [10, 85] <- (1085) |
81 | // |
82 | // The data represents a set of overlapping intervals: |
83 | // |
84 | // 30--35 39------------50 55----61 |
85 | // 31------------------------56 |
86 | // 12--------21 25------------41 49-------------65 71-----79 |
87 | // 11----16 20-----30 36----------------54 60------70 74---- 80 |
88 | // 15---------------------40 43--43 50--------------------75 |
89 | // 10----------------------------------------------------------------------85 |
90 | // |
91 | // The items are stored in a binary tree with each node storing: |
92 | // |
93 | // MP: A middle point. |
94 | // IL: All intervals whose left value are completely to the left of the middle |
95 | // point. They are sorted in ascending order by their beginning point. |
96 | // IR: All intervals whose right value are completely to the right of the |
97 | // middle point. They are sorted in descending order by their ending point. |
98 | // LS: Left subtree. |
99 | // RS: Right subtree. |
100 | // |
101 | // As IL and IR will contain the same intervals, in order to optimize space, |
102 | // instead of storing intervals on each node, we use two vectors that will |
103 | // contain the intervals described by IL and IR. Each node will contain an |
104 | // index into that vector (global bucket), to indicate the beginning of the |
105 | // intervals assigned to the node. |
106 | // |
107 | // The following is the output from print(): |
108 | // |
109 | // 0: MP:43 IR [10,85] [31,56] [36,54] [39,50] [43,43] |
110 | // 0: MP:43 IL [10,85] [31,56] [36,54] [39,50] [43,43] |
111 | // 1: MP:25 IR [25,41] [15,40] [20,30] |
112 | // 1: MP:25 IL [15,40] [20,30] [25,41] |
113 | // 2: MP:15 IR [12,21] [11,16] |
114 | // 2: MP:15 IL [11,16] [12,21] |
115 | // 2: MP:36 IR [] |
116 | // 2: MP:36 IL [] |
117 | // 3: MP:31 IR [30,35] |
118 | // 3: MP:31 IL [30,35] |
119 | // 1: MP:61 IR [50,75] [60,70] [49,65] [55,61] |
120 | // 1: MP:61 IL [49,65] [50,75] [55,61] [60,70] |
121 | // 2: MP:74 IR [74,80] [71,79] |
122 | // 2: MP:74 IL [71,79] [74,80] |
123 | // |
124 | // with: |
125 | // 0: Root Node. |
126 | // MP: Middle point. |
127 | // IL: Intervals to the left (in ascending order by beginning point). |
128 | // IR: Intervals to the right (in descending order by ending point). |
129 | // |
130 | // Root |
131 | // | |
132 | // V |
133 | // +------------MP:43------------+ |
134 | // | IL IR | |
135 | // | [10,85] [10,85] | |
136 | // LS | [31,56] [31,56] | RS |
137 | // | [36,54] [36,54] | |
138 | // | [39,50] [39,50] | |
139 | // | [43,43] [43,43] | |
140 | // V V |
141 | // +------------MP:25------------+ MP:61------------+ |
142 | // | IL IR | IL IR | |
143 | // | [15,40] [25,41] | [49,65] [50,75] | |
144 | // LS | [20,30] [15,40] | RS [50,75] [60,70] | RS |
145 | // | [25,41] [20,30] | [55,61] [49,65] | |
146 | // | | [60,70] [55,61] | |
147 | // V V V |
148 | // MP:15 +-------MP:36 MP:74 |
149 | // IL IR | IL IR IL IR |
150 | // [11,16] [12,21] LS | [] [] [71,79] [74,80] |
151 | // [12,21] [11,16] | [74,80] [71,79] |
152 | // V |
153 | // MP:31 |
154 | // IL IR |
155 | // [30,35] [30,35] |
156 | // |
157 | // The creation of an interval tree is done in 2 steps: |
158 | // 1) Insert the interval items by calling |
159 | // void insert(PointT Left, PointT Right, ValueT Value); |
160 | // Left, Right: the interval left and right limits. |
161 | // Value: the data associated with that specific interval. |
162 | // |
163 | // 2) Create the interval tree by calling |
164 | // void create(); |
165 | // |
166 | // Once the tree is created, it is switched to query mode. |
167 | // Query the tree by using iterators or container. |
168 | // |
169 | // a) Iterators over intervals overlapping the given point with very weak |
170 | // ordering guarantees. |
171 | // find_iterator begin(PointType Point) const; |
172 | // find_iterator end() const; |
173 | // Point: a target point to be tested for inclusion in any interval. |
174 | // |
175 | // b) Container: |
176 | // IntervalReferences getContaining(PointT Point); |
177 | // Point: a target point to be tested for inclusion in any interval. |
178 | // Returns vector with all the intervals containing the target point. |
179 | // |
180 | // The returned intervals are in their natural tree location. They can |
181 | // be sorted: |
182 | // |
183 | // static void sortIntervals(IntervalReferences &Intervals, Sorting Sort); |
184 | // |
185 | // Ability to print the constructed interval tree: |
186 | // void print(raw_ostream &OS, bool HexFormat = true); |
187 | // Display the associated data in hexadecimal format. |
188 | |
189 | namespace llvm { |
190 | |
191 | //===----------------------------------------------------------------------===// |
192 | //--- IntervalData ----// |
193 | //===----------------------------------------------------------------------===// |
194 | /// An interval data composed by a \a Left and \a Right points and an |
195 | /// associated \a Value. |
196 | /// \a PointT corresponds to the interval endpoints type. |
197 | /// \a ValueT corresponds to the interval value type. |
198 | template <typename PointT, typename ValueT> class IntervalData { |
199 | protected: |
200 | using PointType = PointT; |
201 | using ValueType = ValueT; |
202 | |
203 | private: |
204 | PointType Left; |
205 | PointType Right; |
206 | ValueType Value; |
207 | |
208 | public: |
209 | IntervalData() = delete; |
210 | IntervalData(PointType Left, PointType Right, ValueType Value) |
211 | : Left(Left), Right(Right), Value(Value) { |
212 | assert(Left <= Right && "'Left' must be less or equal to 'Right'" ); |
213 | } |
214 | virtual ~IntervalData() = default; |
215 | PointType left() const { return Left; } |
216 | PointType right() const { return Right; } |
217 | ValueType value() const { return Value; } |
218 | |
219 | /// Return true if \a Point is inside the left bound of closed interval \a |
220 | /// [Left;Right]. This is Left <= Point for closed intervals. |
221 | bool left(const PointType &Point) const { return left() <= Point; } |
222 | |
223 | /// Return true if \a Point is inside the right bound of closed interval \a |
224 | /// [Left;Right]. This is Point <= Right for closed intervals. |
225 | bool right(const PointType &Point) const { return Point <= right(); } |
226 | |
227 | /// Return true when \a Point is contained in interval \a [Left;Right]. |
228 | /// This is Left <= Point <= Right for closed intervals. |
229 | bool contains(const PointType &Point) const { |
230 | return left(Point) && right(Point); |
231 | } |
232 | }; |
233 | |
234 | //===----------------------------------------------------------------------===// |
235 | //--- IntervalTree ----// |
236 | //===----------------------------------------------------------------------===// |
237 | // Helper class template that is used by the IntervalTree to ensure that one |
238 | // does instantiate using only fundamental and/or pointer types. |
239 | template <typename T> |
240 | using PointTypeIsValid = std::bool_constant<std::is_fundamental<T>::value>; |
241 | |
242 | template <typename T> |
243 | using ValueTypeIsValid = std::bool_constant<std::is_fundamental<T>::value || |
244 | std::is_pointer<T>::value>; |
245 | |
246 | template <typename PointT, typename ValueT, |
247 | typename DataT = IntervalData<PointT, ValueT>> |
248 | class IntervalTree { |
249 | static_assert(PointTypeIsValid<PointT>::value, |
250 | "PointT must be a fundamental type" ); |
251 | static_assert(ValueTypeIsValid<ValueT>::value, |
252 | "ValueT must be a fundamental or pointer type" ); |
253 | |
254 | public: |
255 | using PointType = PointT; |
256 | using ValueType = ValueT; |
257 | using DataType = DataT; |
258 | using Allocator = BumpPtrAllocator; |
259 | |
260 | enum class Sorting { Ascending, Descending }; |
261 | using IntervalReferences = SmallVector<const DataType *, 4>; |
262 | |
263 | private: |
264 | using IntervalVector = SmallVector<DataType, 4>; |
265 | using PointsVector = SmallVector<PointType, 4>; |
266 | |
267 | class IntervalNode { |
268 | PointType MiddlePoint; // MP - Middle point. |
269 | IntervalNode *Left = nullptr; // LS - Left subtree. |
270 | IntervalNode *Right = nullptr; // RS - Right subtree. |
271 | unsigned BucketIntervalsStart = 0; // Starting index in global bucket. |
272 | unsigned BucketIntervalsSize = 0; // Size of bucket. |
273 | |
274 | public: |
275 | PointType middle() const { return MiddlePoint; } |
276 | unsigned start() const { return BucketIntervalsStart; } |
277 | unsigned size() const { return BucketIntervalsSize; } |
278 | |
279 | IntervalNode(PointType Point, unsigned Start) |
280 | : MiddlePoint(Point), BucketIntervalsStart(Start) {} |
281 | |
282 | friend IntervalTree; |
283 | }; |
284 | |
285 | Allocator &NodeAllocator; // Allocator used for creating interval nodes. |
286 | IntervalNode *Root = nullptr; // Interval tree root. |
287 | IntervalVector Intervals; // Storage for each interval and all of the fields |
288 | // point back into it. |
289 | PointsVector EndPoints; // Sorted left and right points of all the intervals. |
290 | |
291 | // These vectors provide storage that nodes carve buckets of overlapping |
292 | // intervals out of. All intervals are recorded on each vector. |
293 | // The bucket with the intervals associated to a node, is determined by |
294 | // the fields 'BucketIntervalStart' and 'BucketIntervalSize' in the node. |
295 | // The buckets in the first vector are sorted in ascending order using |
296 | // the left value and the buckets in the second vector are sorted in |
297 | // descending order using the right value. Every interval in a bucket |
298 | // contains the middle point for the node. |
299 | IntervalReferences IntervalsLeft; // Intervals to the left of middle point. |
300 | IntervalReferences IntervalsRight; // Intervals to the right of middle point. |
301 | |
302 | // Working vector used during the tree creation to sort the intervals. It is |
303 | // cleared once the tree is created. |
304 | IntervalReferences References; |
305 | |
306 | /// Recursively delete the constructed tree. |
307 | void deleteTree(IntervalNode *Node) { |
308 | if (Node) { |
309 | deleteTree(Node: Node->Left); |
310 | deleteTree(Node: Node->Right); |
311 | Node->~IntervalNode(); |
312 | NodeAllocator.Deallocate(Node); |
313 | } |
314 | } |
315 | |
316 | /// Print the interval list (left and right) for a given \a Node. |
317 | static void printList(raw_ostream &OS, IntervalReferences &IntervalSet, |
318 | unsigned Start, unsigned Size, bool HexFormat = true) { |
319 | assert(Start + Size <= IntervalSet.size() && |
320 | "Start + Size must be in bounds of the IntervalSet" ); |
321 | const char *Format = HexFormat ? "[0x%08x,0x%08x] " : "[%2d,%2d] " ; |
322 | if (Size) { |
323 | for (unsigned Position = Start; Position < Start + Size; ++Position) |
324 | OS << format(Format, IntervalSet[Position]->left(), |
325 | IntervalSet[Position]->right()); |
326 | } else { |
327 | OS << "[]" ; |
328 | } |
329 | OS << "\n" ; |
330 | } |
331 | |
332 | /// Print an interval tree \a Node. |
333 | void printNode(raw_ostream &OS, unsigned Level, IntervalNode *Node, |
334 | bool HexFormat = true) { |
335 | const char *Format = HexFormat ? "MP:0x%08x " : "MP:%2d " ; |
336 | auto PrintNodeData = [&](StringRef Text, IntervalReferences &IntervalSet) { |
337 | OS << format(Fmt: "%5d: " , Vals: Level); |
338 | OS.indent(NumSpaces: Level * 2); |
339 | OS << format(Format, Node->middle()) << Text << " " ; |
340 | printList(OS, IntervalSet, Start: Node->start(), Size: Node->size(), HexFormat); |
341 | }; |
342 | |
343 | PrintNodeData("IR" , IntervalsRight); |
344 | PrintNodeData("IL" , IntervalsLeft); |
345 | } |
346 | |
347 | /// Recursively print all the interval nodes. |
348 | void printTree(raw_ostream &OS, unsigned Level, IntervalNode *Node, |
349 | bool HexFormat = true) { |
350 | if (Node) { |
351 | printNode(OS, Level, Node, HexFormat); |
352 | ++Level; |
353 | printTree(OS, Level, Node: Node->Left, HexFormat); |
354 | printTree(OS, Level, Node: Node->Right, HexFormat); |
355 | } |
356 | } |
357 | |
358 | /// Recursively construct the interval tree. |
359 | /// IntervalsSize: Number of intervals that have been processed and it will |
360 | /// be used as the start for the intervals bucket for a node. |
361 | /// PointsBeginIndex, PointsEndIndex: Determine the range into the EndPoints |
362 | /// vector of end points to be processed. |
363 | /// ReferencesBeginIndex, ReferencesSize: Determine the range into the |
364 | /// intervals being processed. |
365 | IntervalNode *createTree(unsigned &IntervalsSize, int PointsBeginIndex, |
366 | int PointsEndIndex, int ReferencesBeginIndex, |
367 | int ReferencesSize) { |
368 | // We start by taking the entire range of all the intervals and dividing |
369 | // it in half at x_middle (in practice, x_middle should be picked to keep |
370 | // the tree relatively balanced). |
371 | // This gives three sets of intervals, those completely to the left of |
372 | // x_middle which we'll call S_left, those completely to the right of |
373 | // x_middle which we'll call S_right, and those overlapping x_middle |
374 | // which we'll call S_middle. |
375 | // The intervals in S_left and S_right are recursively divided in the |
376 | // same manner until there are no intervals remaining. |
377 | |
378 | if (PointsBeginIndex > PointsEndIndex || |
379 | ReferencesBeginIndex >= ReferencesSize) |
380 | return nullptr; |
381 | |
382 | int MiddleIndex = (PointsBeginIndex + PointsEndIndex) / 2; |
383 | PointType MiddlePoint = EndPoints[MiddleIndex]; |
384 | |
385 | unsigned NewBucketStart = IntervalsSize; |
386 | unsigned NewBucketSize = 0; |
387 | int ReferencesRightIndex = ReferencesSize; |
388 | |
389 | IntervalNode *Root = |
390 | new (NodeAllocator) IntervalNode(MiddlePoint, NewBucketStart); |
391 | |
392 | // A quicksort implementation where all the intervals that overlap |
393 | // with the pivot are put into the "bucket", and "References" is the |
394 | // partition space where we recursively sort the remaining intervals. |
395 | for (int Index = ReferencesBeginIndex; Index < ReferencesRightIndex;) { |
396 | |
397 | // Current interval contains the middle point. |
398 | if (References[Index]->contains(MiddlePoint)) { |
399 | IntervalsLeft[IntervalsSize] = References[Index]; |
400 | IntervalsRight[IntervalsSize] = References[Index]; |
401 | ++IntervalsSize; |
402 | Root->BucketIntervalsSize = ++NewBucketSize; |
403 | |
404 | if (Index < --ReferencesRightIndex) |
405 | std::swap(References[Index], References[ReferencesRightIndex]); |
406 | if (ReferencesRightIndex < --ReferencesSize) |
407 | std::swap(References[ReferencesRightIndex], |
408 | References[ReferencesSize]); |
409 | continue; |
410 | } |
411 | |
412 | if (References[Index]->left() > MiddlePoint) { |
413 | if (Index < --ReferencesRightIndex) |
414 | std::swap(References[Index], References[ReferencesRightIndex]); |
415 | continue; |
416 | } |
417 | ++Index; |
418 | } |
419 | |
420 | // Sort intervals on the left and right of the middle point. |
421 | if (NewBucketSize > 1) { |
422 | // Sort the intervals in ascending order by their beginning point. |
423 | std::stable_sort(IntervalsLeft.begin() + NewBucketStart, |
424 | IntervalsLeft.begin() + NewBucketStart + NewBucketSize, |
425 | [](const DataType *LHS, const DataType *RHS) { |
426 | return LHS->left() < RHS->left(); |
427 | }); |
428 | // Sort the intervals in descending order by their ending point. |
429 | std::stable_sort(IntervalsRight.begin() + NewBucketStart, |
430 | IntervalsRight.begin() + NewBucketStart + NewBucketSize, |
431 | [](const DataType *LHS, const DataType *RHS) { |
432 | return LHS->right() > RHS->right(); |
433 | }); |
434 | } |
435 | |
436 | if (PointsBeginIndex <= MiddleIndex - 1) { |
437 | Root->Left = createTree(IntervalsSize, PointsBeginIndex, PointsEndIndex: MiddleIndex - 1, |
438 | ReferencesBeginIndex, ReferencesSize: ReferencesRightIndex); |
439 | } |
440 | |
441 | if (MiddleIndex + 1 <= PointsEndIndex) { |
442 | Root->Right = createTree(IntervalsSize, PointsBeginIndex: MiddleIndex + 1, PointsEndIndex, |
443 | ReferencesBeginIndex: ReferencesRightIndex, ReferencesSize); |
444 | } |
445 | |
446 | return Root; |
447 | } |
448 | |
449 | public: |
450 | class find_iterator { |
451 | public: |
452 | using iterator_category = std::forward_iterator_tag; |
453 | using value_type = DataType; |
454 | using difference_type = DataType; |
455 | using pointer = DataType *; |
456 | using reference = DataType &; |
457 | |
458 | private: |
459 | const IntervalReferences *AscendingBuckets = nullptr; |
460 | const IntervalReferences *DescendingBuckets = nullptr; |
461 | |
462 | // Current node and index while traversing the intervals that contain |
463 | // the reference point. |
464 | IntervalNode *Node = nullptr; |
465 | PointType Point = {}; |
466 | unsigned Index = 0; |
467 | |
468 | // For the current node, check if we have intervals that contain the |
469 | // reference point. We return when the node does have intervals that |
470 | // contain such point. Otherwise we keep descending on that branch. |
471 | void initNode() { |
472 | Index = 0; |
473 | while (Node) { |
474 | // Return if the reference point is the same as the middle point or |
475 | // the current node doesn't have any intervals at all. |
476 | if (Point == Node->middle()) { |
477 | if (Node->size() == 0) { |
478 | // No intervals that contain the reference point. |
479 | Node = nullptr; |
480 | } |
481 | return; |
482 | } |
483 | |
484 | if (Point < Node->middle()) { |
485 | // The reference point can be at the left or right of the middle |
486 | // point. Return if the current node has intervals that contain the |
487 | // reference point; otherwise descend on the respective branch. |
488 | if (Node->size() && (*AscendingBuckets)[Node->start()]->left(Point)) { |
489 | return; |
490 | } |
491 | Node = Node->Left; |
492 | } else { |
493 | if (Node->size() && |
494 | (*DescendingBuckets)[Node->start()]->right(Point)) { |
495 | return; |
496 | } |
497 | Node = Node->Right; |
498 | } |
499 | } |
500 | } |
501 | |
502 | // Given the current node (which was initialized by initNode), move to |
503 | // the next interval in the list of intervals that contain the reference |
504 | // point. Otherwise move to the next node, as the intervals contained |
505 | // in that node, can contain the reference point. |
506 | void nextInterval() { |
507 | // If there are available intervals that contain the reference point, |
508 | // traverse them; otherwise move to the left or right node, depending |
509 | // on the middle point value. |
510 | if (++Index < Node->size()) { |
511 | if (Node->middle() == Point) |
512 | return; |
513 | if (Point < Node->middle()) { |
514 | // Reference point is on the left. |
515 | if (!(*AscendingBuckets)[Node->start() + Index]->left(Point)) { |
516 | // The intervals don't contain the reference point. Move to the |
517 | // next node, preserving the descending order. |
518 | Node = Node->Left; |
519 | initNode(); |
520 | } |
521 | } else { |
522 | // Reference point is on the right. |
523 | if (!(*DescendingBuckets)[Node->start() + Index]->right(Point)) { |
524 | // The intervals don't contain the reference point. Move to the |
525 | // next node, preserving the ascending order. |
526 | Node = Node->Right; |
527 | initNode(); |
528 | } |
529 | } |
530 | } else { |
531 | // We have traversed all the intervals in the current node. |
532 | if (Point == Node->middle()) { |
533 | Node = nullptr; |
534 | Index = 0; |
535 | return; |
536 | } |
537 | // Select a branch based on the middle point. |
538 | Node = Point < Node->middle() ? Node->Left : Node->Right; |
539 | initNode(); |
540 | } |
541 | } |
542 | |
543 | find_iterator() = default; |
544 | explicit find_iterator(const IntervalReferences *Left, |
545 | const IntervalReferences *Right, IntervalNode *Node, |
546 | PointType Point) |
547 | : AscendingBuckets(Left), DescendingBuckets(Right), Node(Node), |
548 | Point(Point), Index(0) { |
549 | initNode(); |
550 | } |
551 | |
552 | const DataType *current() const { |
553 | return (Point <= Node->middle()) |
554 | ? (*AscendingBuckets)[Node->start() + Index] |
555 | : (*DescendingBuckets)[Node->start() + Index]; |
556 | } |
557 | |
558 | public: |
559 | find_iterator &operator++() { |
560 | nextInterval(); |
561 | return *this; |
562 | } |
563 | |
564 | find_iterator operator++(int) { |
565 | find_iterator Iter(*this); |
566 | nextInterval(); |
567 | return Iter; |
568 | } |
569 | |
570 | /// Dereference operators. |
571 | const DataType *operator->() const { return current(); } |
572 | const DataType &operator*() const { return *(current()); } |
573 | |
574 | /// Comparison operators. |
575 | friend bool operator==(const find_iterator &LHS, const find_iterator &RHS) { |
576 | return (!LHS.Node && !RHS.Node && !LHS.Index && !RHS.Index) || |
577 | (LHS.Point == RHS.Point && LHS.Node == RHS.Node && |
578 | LHS.Index == RHS.Index); |
579 | } |
580 | friend bool operator!=(const find_iterator &LHS, const find_iterator &RHS) { |
581 | return !(LHS == RHS); |
582 | } |
583 | |
584 | friend IntervalTree; |
585 | }; |
586 | |
587 | private: |
588 | find_iterator End; |
589 | |
590 | public: |
591 | explicit IntervalTree(Allocator &NodeAllocator) |
592 | : NodeAllocator(NodeAllocator) {} |
593 | ~IntervalTree() { clear(); } |
594 | |
595 | /// Return true when no intervals are mapped. |
596 | bool empty() const { return Root == nullptr; } |
597 | |
598 | /// Remove all entries. |
599 | void clear() { |
600 | deleteTree(Node: Root); |
601 | Root = nullptr; |
602 | Intervals.clear(); |
603 | IntervalsLeft.clear(); |
604 | IntervalsRight.clear(); |
605 | EndPoints.clear(); |
606 | } |
607 | |
608 | /// Add a mapping of [Left;Right] to \a Value. |
609 | void insert(PointType Left, PointType Right, ValueType Value) { |
610 | assert(empty() && "Invalid insertion. Interval tree already constructed." ); |
611 | Intervals.emplace_back(Left, Right, Value); |
612 | } |
613 | |
614 | /// Return all the intervals in their natural tree location, that |
615 | /// contain the given point. |
616 | IntervalReferences getContaining(PointType Point) const { |
617 | assert(!empty() && "Interval tree it is not constructed." ); |
618 | IntervalReferences IntervalSet; |
619 | for (find_iterator Iter = find(Point), E = find_end(); Iter != E; ++Iter) |
620 | IntervalSet.push_back(const_cast<DataType *>(&(*Iter))); |
621 | return IntervalSet; |
622 | } |
623 | |
624 | /// Sort the given intervals using the following sort options: |
625 | /// Ascending: return the intervals with the smallest at the front. |
626 | /// Descending: return the intervals with the biggest at the front. |
627 | static void sortIntervals(IntervalReferences &IntervalSet, Sorting Sort) { |
628 | std::stable_sort(IntervalSet.begin(), IntervalSet.end(), |
629 | [Sort](const DataType *RHS, const DataType *LHS) { |
630 | return Sort == Sorting::Ascending |
631 | ? (LHS->right() - LHS->left()) > |
632 | (RHS->right() - RHS->left()) |
633 | : (LHS->right() - LHS->left()) < |
634 | (RHS->right() - RHS->left()); |
635 | }); |
636 | } |
637 | |
638 | /// Print the interval tree. |
639 | /// When \a HexFormat is true, the interval tree interval ranges and |
640 | /// associated values are printed in hexadecimal format. |
641 | void print(raw_ostream &OS, bool HexFormat = true) { |
642 | printTree(OS, Level: 0, Node: Root, HexFormat); |
643 | } |
644 | |
645 | /// Create the interval tree. |
646 | void create() { |
647 | assert(empty() && "Interval tree already constructed." ); |
648 | // Sorted vector of unique end points values of all the intervals. |
649 | // Records references to the collected intervals. |
650 | SmallVector<PointType, 4> Points; |
651 | for (const DataType &Data : Intervals) { |
652 | Points.push_back(Data.left()); |
653 | Points.push_back(Data.right()); |
654 | References.push_back(std::addressof(Data)); |
655 | } |
656 | std::stable_sort(Points.begin(), Points.end()); |
657 | auto Last = std::unique(Points.begin(), Points.end()); |
658 | Points.erase(Last, Points.end()); |
659 | |
660 | EndPoints.assign(Points.begin(), Points.end()); |
661 | |
662 | IntervalsLeft.resize(Intervals.size()); |
663 | IntervalsRight.resize(Intervals.size()); |
664 | |
665 | // Given a set of n intervals, construct a data structure so that |
666 | // we can efficiently retrieve all intervals overlapping another |
667 | // interval or point. |
668 | unsigned IntervalsSize = 0; |
669 | Root = |
670 | createTree(IntervalsSize, /*PointsBeginIndex=*/PointsBeginIndex: 0, PointsEndIndex: EndPoints.size() - 1, |
671 | /*ReferencesBeginIndex=*/ReferencesBeginIndex: 0, ReferencesSize: References.size()); |
672 | |
673 | // Save to clear this storage, as it used only to sort the intervals. |
674 | References.clear(); |
675 | } |
676 | |
677 | /// Iterator to start a find operation; it returns find_end() if the |
678 | /// tree has not been built. |
679 | /// There is no support to iterate over all the elements of the tree. |
680 | find_iterator find(PointType Point) const { |
681 | return empty() |
682 | ? find_end() |
683 | : find_iterator(&IntervalsLeft, &IntervalsRight, Root, Point); |
684 | } |
685 | |
686 | /// Iterator to end find operation. |
687 | find_iterator find_end() const { return End; } |
688 | }; |
689 | |
690 | } // namespace llvm |
691 | |
692 | #endif // LLVM_ADT_INTERVALTREE_H |
693 | |