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