| //===-- IntervalTree.h ------------------------------------------*- C++ -*-===// |
| // |
| // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions. |
| // See https://llvm.org/LICENSE.txt for license information. |
| // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception |
| // |
| //===----------------------------------------------------------------------===// |
| // |
| // This file implements an interval tree. |
| // |
| // Further information: |
| // https://en.wikipedia.org/wiki/Interval_tree |
| // |
| //===----------------------------------------------------------------------===// |
| |
| #ifndef LLVM_ADT_INTERVALTREE_H |
| #define LLVM_ADT_INTERVALTREE_H |
| |
| #include "llvm/ADT/SmallSet.h" |
| #include "llvm/ADT/SmallVector.h" |
| #include "llvm/Support/Allocator.h" |
| #include "llvm/Support/Format.h" |
| #include "llvm/Support/raw_ostream.h" |
| #include <algorithm> |
| #include <cassert> |
| #include <iterator> |
| |
| // IntervalTree is a light tree data structure to hold intervals. It allows |
| // finding all intervals that overlap with any given point. At this time, |
| // it does not support any deletion or rebalancing operations. |
| // |
| // The IntervalTree is designed to be set up once, and then queried without |
| // any further additions. |
| // |
| // Synopsis: |
| // Closed intervals delimited by PointT objects are mapped to ValueT objects. |
| // |
| // Restrictions: |
| // PointT must be a fundamental type. |
| // ValueT must be a fundamental or pointer type. |
| // |
| // template <typename PointT, typename ValueT, typename DataT> |
| // class IntervalTree { |
| // public: |
| // |
| // IntervalTree(); |
| // ~IntervalTree(): |
| // |
| // using IntervalReferences = SmallVector<IntervalData *>; |
| // |
| // void create(); |
| // void insert(PointT Left, PointT Right, ValueT Value); |
| // |
| // IntervalReferences getContaining(PointT Point); |
| // static void sortIntervals(IntervalReferences &Intervals, Sorting Sort); |
| // |
| // find_iterator begin(PointType Point) const; |
| // find_iterator end() const; |
| // |
| // bool empty() const; |
| // void clear(); |
| // |
| // void print(raw_ostream &OS, bool HexFormat = true); |
| // }; |
| // |
| //===----------------------------------------------------------------------===// |
| // |
| // In the below given dataset |
| // |
| // [a, b] <- (x) |
| // |
| // 'a' and 'b' describe a range and 'x' the value for that interval. |
| // |
| // The following data are purely for illustrative purposes: |
| // |
| // [30, 35] <- (3035), [39, 50] <- (3950), [55, 61] <- (5561), |
| // [31, 56] <- (3156), [12, 21] <- (1221), [25, 41] <- (2541), |
| // [49, 65] <- (4965), [71, 79] <- (7179), [11, 16] <- (1116), |
| // [20, 30] <- (2030), [36, 54] <- (3654), [60, 70] <- (6070), |
| // [74, 80] <- (7480), [15, 40] <- (1540), [43, 43] <- (4343), |
| // [50, 75] <- (5075), [10, 85] <- (1085) |
| // |
| // The data represents a set of overlapping intervals: |
| // |
| // 30--35 39------------50 55----61 |
| // 31------------------------56 |
| // 12--------21 25------------41 49-------------65 71-----79 |
| // 11----16 20-----30 36----------------54 60------70 74---- 80 |
| // 15---------------------40 43--43 50--------------------75 |
| // 10----------------------------------------------------------------------85 |
| // |
| // The items are stored in a binary tree with each node storing: |
| // |
| // MP: A middle point. |
| // IL: All intervals whose left value are completely to the left of the middle |
| // point. They are sorted in ascending order by their beginning point. |
| // IR: All intervals whose right value are completely to the right of the |
| // middle point. They are sorted in descending order by their ending point. |
| // LS: Left subtree. |
| // RS: Right subtree. |
| // |
| // As IL and IR will contain the same intervals, in order to optimize space, |
| // instead of storing intervals on each node, we use two vectors that will |
| // contain the intervals described by IL and IR. Each node will contain an |
| // index into that vector (global bucket), to indicate the beginning of the |
| // intervals assigned to the node. |
| // |
| // The following is the output from print(): |
| // |
| // 0: MP:43 IR [10,85] [31,56] [36,54] [39,50] [43,43] |
| // 0: MP:43 IL [10,85] [31,56] [36,54] [39,50] [43,43] |
| // 1: MP:25 IR [25,41] [15,40] [20,30] |
| // 1: MP:25 IL [15,40] [20,30] [25,41] |
| // 2: MP:15 IR [12,21] [11,16] |
| // 2: MP:15 IL [11,16] [12,21] |
| // 2: MP:36 IR [] |
| // 2: MP:36 IL [] |
| // 3: MP:31 IR [30,35] |
| // 3: MP:31 IL [30,35] |
| // 1: MP:61 IR [50,75] [60,70] [49,65] [55,61] |
| // 1: MP:61 IL [49,65] [50,75] [55,61] [60,70] |
| // 2: MP:74 IR [74,80] [71,79] |
| // 2: MP:74 IL [71,79] [74,80] |
| // |
| // with: |
| // 0: Root Node. |
| // MP: Middle point. |
| // IL: Intervals to the left (in ascending order by beginning point). |
| // IR: Intervals to the right (in descending order by ending point). |
| // |
| // Root |
| // | |
| // V |
| // +------------MP:43------------+ |
| // | IL IR | |
| // | [10,85] [10,85] | |
| // LS | [31,56] [31,56] | RS |
| // | [36,54] [36,54] | |
| // | [39,50] [39,50] | |
| // | [43,43] [43,43] | |
| // V V |
| // +------------MP:25------------+ MP:61------------+ |
| // | IL IR | IL IR | |
| // | [15,40] [25,41] | [49,65] [50,75] | |
| // LS | [20,30] [15,40] | RS [50,75] [60,70] | RS |
| // | [25,41] [20,30] | [55,61] [49,65] | |
| // | | [60,70] [55,61] | |
| // V V V |
| // MP:15 +-------MP:36 MP:74 |
| // IL IR | IL IR IL IR |
| // [11,16] [12,21] LS | [] [] [71,79] [74,80] |
| // [12,21] [11,16] | [74,80] [71,79] |
| // V |
| // MP:31 |
| // IL IR |
| // [30,35] [30,35] |
| // |
| // The creation of an interval tree is done in 2 steps: |
| // 1) Insert the interval items by calling |
| // void insert(PointT Left, PointT Right, ValueT Value); |
| // Left, Right: the interval left and right limits. |
| // Value: the data associated with that specific interval. |
| // |
| // 2) Create the interval tree by calling |
| // void create(); |
| // |
| // Once the tree is created, it is switched to query mode. |
| // Query the tree by using iterators or container. |
| // |
| // a) Iterators over intervals overlapping the given point with very weak |
| // ordering guarantees. |
| // find_iterator begin(PointType Point) const; |
| // find_iterator end() const; |
| // Point: a target point to be tested for inclusion in any interval. |
| // |
| // b) Container: |
| // IntervalReferences getContaining(PointT Point); |
| // Point: a target point to be tested for inclusion in any interval. |
| // Returns vector with all the intervals containing the target point. |
| // |
| // The returned intervals are in their natural tree location. They can |
| // be sorted: |
| // |
| // static void sortIntervals(IntervalReferences &Intervals, Sorting Sort); |
| // |
| // Ability to print the constructed interval tree: |
| // void print(raw_ostream &OS, bool HexFormat = true); |
| // Display the associated data in hexadecimal format. |
| |
| namespace llvm { |
| |
| //===----------------------------------------------------------------------===// |
| //--- IntervalData ----// |
| //===----------------------------------------------------------------------===// |
| /// An interval data composed by a \a Left and \a Right points and an |
| /// associated \a Value. |
| /// \a PointT corresponds to the interval endpoints type. |
| /// \a ValueT corresponds to the interval value type. |
| template <typename PointT, typename ValueT> class IntervalData { |
| protected: |
| using PointType = PointT; |
| using ValueType = ValueT; |
| |
| private: |
| PointType Left; |
| PointType Right; |
| ValueType Value; |
| |
| public: |
| IntervalData() = delete; |
| IntervalData(PointType Left, PointType Right, ValueType Value) |
| : Left(Left), Right(Right), Value(Value) { |
| assert(Left <= Right && "'Left' must be less or equal to 'Right'"); |
| } |
| virtual ~IntervalData() = default; |
| PointType left() const { return Left; } |
| PointType right() const { return Right; } |
| ValueType value() const { return Value; } |
| |
| /// Return true if \a Point is inside the left bound of closed interval \a |
| /// [Left;Right]. This is Left <= Point for closed intervals. |
| bool left(const PointType &Point) const { return left() <= Point; } |
| |
| /// Return true if \a Point is inside the right bound of closed interval \a |
| /// [Left;Right]. This is Point <= Right for closed intervals. |
| bool right(const PointType &Point) const { return Point <= right(); } |
| |
| /// Return true when \a Point is contained in interval \a [Left;Right]. |
| /// This is Left <= Point <= Right for closed intervals. |
| bool contains(const PointType &Point) const { |
| return left(Point) && right(Point); |
| } |
| }; |
| |
| //===----------------------------------------------------------------------===// |
| //--- IntervalTree ----// |
| //===----------------------------------------------------------------------===// |
| // Helper class template that is used by the IntervalTree to ensure that one |
| // does instantiate using only fundamental and/or pointer types. |
| template <typename T> |
| using PointTypeIsValid = std::bool_constant<std::is_fundamental<T>::value>; |
| |
| template <typename T> |
| using ValueTypeIsValid = std::bool_constant<std::is_fundamental<T>::value || |
| std::is_pointer<T>::value>; |
| |
| template <typename PointT, typename ValueT, |
| typename DataT = IntervalData<PointT, ValueT>> |
| class IntervalTree { |
| static_assert(PointTypeIsValid<PointT>::value, |
| "PointT must be a fundamental type"); |
| static_assert(ValueTypeIsValid<ValueT>::value, |
| "ValueT must be a fundamental or pointer type"); |
| |
| public: |
| using PointType = PointT; |
| using ValueType = ValueT; |
| using DataType = DataT; |
| using Allocator = BumpPtrAllocator; |
| |
| enum class Sorting { Ascending, Descending }; |
| using IntervalReferences = SmallVector<const DataType *, 4>; |
| |
| private: |
| using IntervalVector = SmallVector<DataType, 4>; |
| using PointsVector = SmallVector<PointType, 4>; |
| |
| class IntervalNode { |
| PointType MiddlePoint; // MP - Middle point. |
| IntervalNode *Left = nullptr; // LS - Left subtree. |
| IntervalNode *Right = nullptr; // RS - Right subtree. |
| unsigned BucketIntervalsStart = 0; // Starting index in global bucket. |
| unsigned BucketIntervalsSize = 0; // Size of bucket. |
| |
| public: |
| PointType middle() const { return MiddlePoint; } |
| unsigned start() const { return BucketIntervalsStart; } |
| unsigned size() const { return BucketIntervalsSize; } |
| |
| IntervalNode(PointType Point, unsigned Start) |
| : MiddlePoint(Point), BucketIntervalsStart(Start) {} |
| |
| friend IntervalTree; |
| }; |
| |
| Allocator &NodeAllocator; // Allocator used for creating interval nodes. |
| IntervalNode *Root = nullptr; // Interval tree root. |
| IntervalVector Intervals; // Storage for each interval and all of the fields |
| // point back into it. |
| PointsVector EndPoints; // Sorted left and right points of all the intervals. |
| |
| // These vectors provide storage that nodes carve buckets of overlapping |
| // intervals out of. All intervals are recorded on each vector. |
| // The bucket with the intervals associated to a node, is determined by |
| // the fields 'BucketIntervalStart' and 'BucketIntervalSize' in the node. |
| // The buckets in the first vector are sorted in ascending order using |
| // the left value and the buckets in the second vector are sorted in |
| // descending order using the right value. Every interval in a bucket |
| // contains the middle point for the node. |
| IntervalReferences IntervalsLeft; // Intervals to the left of middle point. |
| IntervalReferences IntervalsRight; // Intervals to the right of middle point. |
| |
| // Working vector used during the tree creation to sort the intervals. It is |
| // cleared once the tree is created. |
| IntervalReferences References; |
| |
| /// Recursively delete the constructed tree. |
| void deleteTree(IntervalNode *Node) { |
| if (Node) { |
| deleteTree(Node->Left); |
| deleteTree(Node->Right); |
| Node->~IntervalNode(); |
| NodeAllocator.Deallocate(Node); |
| } |
| } |
| |
| /// Print the interval list (left and right) for a given \a Node. |
| static void printList(raw_ostream &OS, IntervalReferences &IntervalSet, |
| unsigned Start, unsigned Size, bool HexFormat = true) { |
| assert(Start + Size <= IntervalSet.size() && |
| "Start + Size must be in bounds of the IntervalSet"); |
| const char *Format = HexFormat ? "[0x%08x,0x%08x] " : "[%2d,%2d] "; |
| if (Size) { |
| for (unsigned Position = Start; Position < Start + Size; ++Position) |
| OS << format(Format, IntervalSet[Position]->left(), |
| IntervalSet[Position]->right()); |
| } else { |
| OS << "[]"; |
| } |
| OS << "\n"; |
| } |
| |
| /// Print an interval tree \a Node. |
| void printNode(raw_ostream &OS, unsigned Level, IntervalNode *Node, |
| bool HexFormat = true) { |
| const char *Format = HexFormat ? "MP:0x%08x " : "MP:%2d "; |
| auto PrintNodeData = [&](StringRef Text, IntervalReferences &IntervalSet) { |
| OS << format("%5d: ", Level); |
| OS.indent(Level * 2); |
| OS << format(Format, Node->middle()) << Text << " "; |
| printList(OS, IntervalSet, Node->start(), Node->size(), HexFormat); |
| }; |
| |
| PrintNodeData("IR", IntervalsRight); |
| PrintNodeData("IL", IntervalsLeft); |
| } |
| |
| /// Recursively print all the interval nodes. |
| void printTree(raw_ostream &OS, unsigned Level, IntervalNode *Node, |
| bool HexFormat = true) { |
| if (Node) { |
| printNode(OS, Level, Node, HexFormat); |
| ++Level; |
| printTree(OS, Level, Node->Left, HexFormat); |
| printTree(OS, Level, Node->Right, HexFormat); |
| } |
| } |
| |
| /// Recursively construct the interval tree. |
| /// IntervalsSize: Number of intervals that have been processed and it will |
| /// be used as the start for the intervals bucket for a node. |
| /// PointsBeginIndex, PointsEndIndex: Determine the range into the EndPoints |
| /// vector of end points to be processed. |
| /// ReferencesBeginIndex, ReferencesSize: Determine the range into the |
| /// intervals being processed. |
| IntervalNode *createTree(unsigned &IntervalsSize, int PointsBeginIndex, |
| int PointsEndIndex, int ReferencesBeginIndex, |
| int ReferencesSize) { |
| // We start by taking the entire range of all the intervals and dividing |
| // it in half at x_middle (in practice, x_middle should be picked to keep |
| // the tree relatively balanced). |
| // This gives three sets of intervals, those completely to the left of |
| // x_middle which we'll call S_left, those completely to the right of |
| // x_middle which we'll call S_right, and those overlapping x_middle |
| // which we'll call S_middle. |
| // The intervals in S_left and S_right are recursively divided in the |
| // same manner until there are no intervals remaining. |
| |
| if (PointsBeginIndex > PointsEndIndex || |
| ReferencesBeginIndex >= ReferencesSize) |
| return nullptr; |
| |
| int MiddleIndex = (PointsBeginIndex + PointsEndIndex) / 2; |
| PointType MiddlePoint = EndPoints[MiddleIndex]; |
| |
| unsigned NewBucketStart = IntervalsSize; |
| unsigned NewBucketSize = 0; |
| int ReferencesRightIndex = ReferencesSize; |
| |
| IntervalNode *Root = |
| new (NodeAllocator) IntervalNode(MiddlePoint, NewBucketStart); |
| |
| // A quicksort implementation where all the intervals that overlap |
| // with the pivot are put into the "bucket", and "References" is the |
| // partition space where we recursively sort the remaining intervals. |
| for (int Index = ReferencesBeginIndex; Index < ReferencesRightIndex;) { |
| |
| // Current interval contains the middle point. |
| if (References[Index]->contains(MiddlePoint)) { |
| IntervalsLeft[IntervalsSize] = References[Index]; |
| IntervalsRight[IntervalsSize] = References[Index]; |
| ++IntervalsSize; |
| Root->BucketIntervalsSize = ++NewBucketSize; |
| |
| if (Index < --ReferencesRightIndex) |
| std::swap(References[Index], References[ReferencesRightIndex]); |
| if (ReferencesRightIndex < --ReferencesSize) |
| std::swap(References[ReferencesRightIndex], |
| References[ReferencesSize]); |
| continue; |
| } |
| |
| if (References[Index]->left() > MiddlePoint) { |
| if (Index < --ReferencesRightIndex) |
| std::swap(References[Index], References[ReferencesRightIndex]); |
| continue; |
| } |
| ++Index; |
| } |
| |
| // Sort intervals on the left and right of the middle point. |
| if (NewBucketSize > 1) { |
| // Sort the intervals in ascending order by their beginning point. |
| std::stable_sort(IntervalsLeft.begin() + NewBucketStart, |
| IntervalsLeft.begin() + NewBucketStart + NewBucketSize, |
| [](const DataType *LHS, const DataType *RHS) { |
| return LHS->left() < RHS->left(); |
| }); |
| // Sort the intervals in descending order by their ending point. |
| std::stable_sort(IntervalsRight.begin() + NewBucketStart, |
| IntervalsRight.begin() + NewBucketStart + NewBucketSize, |
| [](const DataType *LHS, const DataType *RHS) { |
| return LHS->right() > RHS->right(); |
| }); |
| } |
| |
| if (PointsBeginIndex <= MiddleIndex - 1) { |
| Root->Left = createTree(IntervalsSize, PointsBeginIndex, MiddleIndex - 1, |
| ReferencesBeginIndex, ReferencesRightIndex); |
| } |
| |
| if (MiddleIndex + 1 <= PointsEndIndex) { |
| Root->Right = createTree(IntervalsSize, MiddleIndex + 1, PointsEndIndex, |
| ReferencesRightIndex, ReferencesSize); |
| } |
| |
| return Root; |
| } |
| |
| public: |
| class find_iterator { |
| public: |
| using iterator_category = std::forward_iterator_tag; |
| using value_type = DataType; |
| using difference_type = DataType; |
| using pointer = DataType *; |
| using reference = DataType &; |
| |
| private: |
| const IntervalReferences *AscendingBuckets = nullptr; |
| const IntervalReferences *DescendingBuckets = nullptr; |
| |
| // Current node and index while traversing the intervals that contain |
| // the reference point. |
| IntervalNode *Node = nullptr; |
| PointType Point; |
| unsigned Index = 0; |
| |
| // For the current node, check if we have intervals that contain the |
| // reference point. We return when the node does have intervals that |
| // contain such point. Otherwise we keep descending on that branch. |
| void initNode() { |
| Index = 0; |
| while (Node) { |
| // Return if the reference point is the same as the middle point or |
| // the current node doesn't have any intervals at all. |
| if (Point == Node->middle()) { |
| if (Node->size() == 0) { |
| // No intervals that contain the reference point. |
| Node = nullptr; |
| } |
| return; |
| } |
| |
| if (Point < Node->middle()) { |
| // The reference point can be at the left or right of the middle |
| // point. Return if the current node has intervals that contain the |
| // reference point; otherwise descend on the respective branch. |
| if (Node->size() && (*AscendingBuckets)[Node->start()]->left(Point)) { |
| return; |
| } |
| Node = Node->Left; |
| } else { |
| if (Node->size() && |
| (*DescendingBuckets)[Node->start()]->right(Point)) { |
| return; |
| } |
| Node = Node->Right; |
| } |
| } |
| } |
| |
| // Given the current node (which was initialized by initNode), move to |
| // the next interval in the list of intervals that contain the reference |
| // point. Otherwise move to the next node, as the intervals contained |
| // in that node, can contain the reference point. |
| void nextInterval() { |
| // If there are available intervals that contain the reference point, |
| // traverse them; otherwise move to the left or right node, depending |
| // on the middle point value. |
| if (++Index < Node->size()) { |
| if (Node->middle() == Point) |
| return; |
| if (Point < Node->middle()) { |
| // Reference point is on the left. |
| if (!(*AscendingBuckets)[Node->start() + Index]->left(Point)) { |
| // The intervals don't contain the reference point. Move to the |
| // next node, preserving the descending order. |
| Node = Node->Left; |
| initNode(); |
| } |
| } else { |
| // Reference point is on the right. |
| if (!(*DescendingBuckets)[Node->start() + Index]->right(Point)) { |
| // The intervals don't contain the reference point. Move to the |
| // next node, preserving the ascending order. |
| Node = Node->Right; |
| initNode(); |
| } |
| } |
| } else { |
| // We have traversed all the intervals in the current node. |
| if (Point == Node->middle()) { |
| Node = nullptr; |
| Index = 0; |
| return; |
| } |
| // Select a branch based on the middle point. |
| Node = Point < Node->middle() ? Node->Left : Node->Right; |
| initNode(); |
| } |
| } |
| |
| find_iterator() = default; |
| explicit find_iterator(const IntervalReferences *Left, |
| const IntervalReferences *Right, IntervalNode *Node, |
| PointType Point) |
| : AscendingBuckets(Left), DescendingBuckets(Right), Node(Node), |
| Point(Point), Index(0) { |
| initNode(); |
| } |
| |
| const DataType *current() const { |
| return (Point <= Node->middle()) |
| ? (*AscendingBuckets)[Node->start() + Index] |
| : (*DescendingBuckets)[Node->start() + Index]; |
| } |
| |
| public: |
| find_iterator &operator++() { |
| nextInterval(); |
| return *this; |
| } |
| |
| find_iterator operator++(int) { |
| find_iterator Iter(*this); |
| nextInterval(); |
| return Iter; |
| } |
| |
| /// Dereference operators. |
| const DataType *operator->() const { return current(); } |
| const DataType &operator*() const { return *(current()); } |
| |
| /// Comparison operators. |
| friend bool operator==(const find_iterator &LHS, const find_iterator &RHS) { |
| return (!LHS.Node && !RHS.Node && !LHS.Index && !RHS.Index) || |
| (LHS.Point == RHS.Point && LHS.Node == RHS.Node && |
| LHS.Index == RHS.Index); |
| } |
| friend bool operator!=(const find_iterator &LHS, const find_iterator &RHS) { |
| return !(LHS == RHS); |
| } |
| |
| friend IntervalTree; |
| }; |
| |
| private: |
| find_iterator End; |
| |
| public: |
| explicit IntervalTree(Allocator &NodeAllocator) |
| : NodeAllocator(NodeAllocator) {} |
| ~IntervalTree() { clear(); } |
| |
| /// Return true when no intervals are mapped. |
| bool empty() const { return Root == nullptr; } |
| |
| /// Remove all entries. |
| void clear() { |
| deleteTree(Root); |
| Root = nullptr; |
| Intervals.clear(); |
| IntervalsLeft.clear(); |
| IntervalsRight.clear(); |
| EndPoints.clear(); |
| } |
| |
| /// Add a mapping of [Left;Right] to \a Value. |
| void insert(PointType Left, PointType Right, ValueType Value) { |
| assert(empty() && "Invalid insertion. Interval tree already constructed."); |
| Intervals.emplace_back(Left, Right, Value); |
| } |
| |
| /// Return all the intervals in their natural tree location, that |
| /// contain the given point. |
| IntervalReferences getContaining(PointType Point) const { |
| assert(!empty() && "Interval tree it is not constructed."); |
| IntervalReferences IntervalSet; |
| for (find_iterator Iter = find(Point), E = find_end(); Iter != E; ++Iter) |
| IntervalSet.push_back(const_cast<DataType *>(&(*Iter))); |
| return IntervalSet; |
| } |
| |
| /// Sort the given intervals using the following sort options: |
| /// Ascending: return the intervals with the smallest at the front. |
| /// Descending: return the intervals with the biggest at the front. |
| static void sortIntervals(IntervalReferences &IntervalSet, Sorting Sort) { |
| std::stable_sort(IntervalSet.begin(), IntervalSet.end(), |
| [Sort](const DataType *RHS, const DataType *LHS) { |
| return Sort == Sorting::Ascending |
| ? (LHS->right() - LHS->left()) > |
| (RHS->right() - RHS->left()) |
| : (LHS->right() - LHS->left()) < |
| (RHS->right() - RHS->left()); |
| }); |
| } |
| |
| /// Print the interval tree. |
| /// When \a HexFormat is true, the interval tree interval ranges and |
| /// associated values are printed in hexadecimal format. |
| void print(raw_ostream &OS, bool HexFormat = true) { |
| printTree(OS, 0, Root, HexFormat); |
| } |
| |
| /// Create the interval tree. |
| void create() { |
| assert(empty() && "Interval tree already constructed."); |
| // Sorted vector of unique end points values of all the intervals. |
| // Records references to the collected intervals. |
| SmallVector<PointType, 4> Points; |
| for (const DataType &Data : Intervals) { |
| Points.push_back(Data.left()); |
| Points.push_back(Data.right()); |
| References.push_back(std::addressof(Data)); |
| } |
| std::stable_sort(Points.begin(), Points.end()); |
| auto Last = std::unique(Points.begin(), Points.end()); |
| Points.erase(Last, Points.end()); |
| |
| EndPoints.assign(Points.begin(), Points.end()); |
| |
| IntervalsLeft.resize(Intervals.size()); |
| IntervalsRight.resize(Intervals.size()); |
| |
| // Given a set of n intervals, construct a data structure so that |
| // we can efficiently retrieve all intervals overlapping another |
| // interval or point. |
| unsigned IntervalsSize = 0; |
| Root = |
| createTree(IntervalsSize, /*PointsBeginIndex=*/0, EndPoints.size() - 1, |
| /*ReferencesBeginIndex=*/0, References.size()); |
| |
| // Save to clear this storage, as it used only to sort the intervals. |
| References.clear(); |
| } |
| |
| /// Iterator to start a find operation; it returns find_end() if the |
| /// tree has not been built. |
| /// There is no support to iterate over all the elements of the tree. |
| find_iterator find(PointType Point) const { |
| return empty() |
| ? find_end() |
| : find_iterator(&IntervalsLeft, &IntervalsRight, Root, Point); |
| } |
| |
| /// Iterator to end find operation. |
| find_iterator find_end() const { return End; } |
| }; |
| |
| } // namespace llvm |
| |
| #endif // LLVM_ADT_INTERVALTREE_H |
