Subversion Repositories QNX 8.QNX8 LLVM/Clang compiler suite

Rev

Blame | Last modification | View Log | Download | RSS feed

  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.