Index: llvm/docs/ProgrammersManual.rst =================================================================== --- llvm/docs/ProgrammersManual.rst +++ llvm/docs/ProgrammersManual.rst @@ -2314,6 +2314,18 @@ The IntervalMap iterators are quite big, so they should not be passed around as STL iterators. The heavyweight iterators allow a smaller data structure. +.. _dss_intervaltree: + +llvm/ADT/IntervalTree.h +^^^^^^^^^^^^^^^^^^^^^^^ + +``llvm::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. + .. _dss_map: Index: llvm/include/llvm/ADT/IntervalTree.h =================================================================== --- /dev/null +++ llvm/include/llvm/ADT/IntervalTree.h @@ -0,0 +1,693 @@ +//===-- 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 +#include +#include + +// 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 +// class IntervalTree { +// public: +// +// IntervalTree(); +// ~IntervalTree(): +// +// using IntervalReferences = SmallVector; +// +// 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 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 +using PointTypeIsValid = std::bool_constant::value>; + +template +using ValueTypeIsValid = std::bool_constant::value || + std::is_pointer::value>; + +template > +class IntervalTree { + static_assert(PointTypeIsValid::value, + "PointT must be a fundamental type"); + static_assert(ValueTypeIsValid::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; + +private: + using IntervalVector = SmallVector; + using PointsVector = SmallVector; + + 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::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::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(&(*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::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 Points; + for (const DataType &Data : Intervals) { + Points.push_back(Data.left()); + Points.push_back(Data.right()); + References.push_back(std::addressof(Data)); + } + std::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 Index: llvm/unittests/ADT/CMakeLists.txt =================================================================== --- llvm/unittests/ADT/CMakeLists.txt +++ llvm/unittests/ADT/CMakeLists.txt @@ -43,6 +43,7 @@ ImmutableSetTest.cpp IntEqClassesTest.cpp IntervalMapTest.cpp + IntervalTreeTest.cpp IntrusiveRefCntPtrTest.cpp IteratorTest.cpp MappedIteratorTest.cpp Index: llvm/unittests/ADT/IntervalTreeTest.cpp =================================================================== --- /dev/null +++ llvm/unittests/ADT/IntervalTreeTest.cpp @@ -0,0 +1,1607 @@ +//===---- ADT/IntervalTreeTest.cpp - IntervalTree unit tests --------------===// +// +// 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 +// +//===----------------------------------------------------------------------===// + +#include "llvm/ADT/IntervalTree.h" +#include "gtest/gtest.h" + +// The test cases for the IntervalTree implementation, follow the below steps: +// a) Insert a series of intervals with their associated mapped value. +// b) Create the interval tree. +// c) Query for specific interval point, covering points inside and outside +// of any given intervals. +// d) Traversal for specific interval point, using the iterators. +// +// When querying for a set of intervals containing a given value, the query is +// done three times, by calling: +// 1) Intervals = getContaining(...). +// 2) Intervals = getContaining(...). +// sortIntervals(Intervals, Sorting=Ascending). +// 3) Intervals = getContaining(...). +// sortIntervals(Intervals, Sorting=Ascending). +// +// The returned intervals are: +// 1) In their location order within the tree. +// 2) Smaller intervals first. +// 3) Bigger intervals first. + +using namespace llvm; + +namespace { + +// Helper function to test a specific item or iterator. +template +void checkItem(TPoint Point, TItem Item, TPoint Left, TPoint Right, + TValue Value) { + EXPECT_TRUE(Item->contains(Point)); + EXPECT_EQ(Item->left(), Left); + EXPECT_EQ(Item->right(), Right); + EXPECT_EQ(Item->value(), Value); +} + +// User class tree tests. +TEST(IntervalTreeTest, UserClass) { + using UUPoint = unsigned; + using UUValue = double; + class MyData : public IntervalData { + using UUData = IntervalData; + + public: + // Inherit Base's constructors. + using UUData::UUData; + PointType left() const { return UUData::left(); } + PointType right() const { return UUData::right(); } + ValueType value() const { return UUData::value(); } + + bool left(const PointType &Point) const { return UUData::left(Point); } + bool right(const PointType &Point) const { return UUData::right(Point); } + bool contains(const PointType &Point) const { + return UUData::contains(Point); + } + }; + + using UUTree = IntervalTree; + using UUReferences = UUTree::IntervalReferences; + using UUData = UUTree::DataType; + using UUAlloc = UUTree::Allocator; + + auto CheckData = [](UUPoint Point, const UUData *Data, UUPoint Left, + UUPoint Right, UUValue Value) { + checkItem(Point, Data, Left, Right, + Value); + }; + + UUAlloc Allocator; + UUTree Tree(Allocator); + UUReferences Intervals; + UUPoint Point; + + EXPECT_TRUE(Tree.empty()); + Tree.clear(); + EXPECT_TRUE(Tree.empty()); + + // [10, 20] <- (10.20) + // [30, 40] <- (30.40) + // + // [10...20] [30...40] + Tree.insert(10, 20, 10.20); + Tree.insert(30, 40, 30.40); + Tree.create(); + + // Invalid interval values: x < [10 + Point = 5; + Intervals = Tree.getContaining(Point); + EXPECT_TRUE(Intervals.empty()); + + // Valid interval values: [10...20] + Point = 10; + Intervals = Tree.getContaining(Point); + ASSERT_EQ(Intervals.size(), 1); + CheckData(Point, Intervals[0], 10, 20, 10.20); + + Point = 15; + Intervals = Tree.getContaining(Point); + ASSERT_EQ(Intervals.size(), 1); + CheckData(Point, Intervals[0], 10, 20, 10.20); + + Point = 20; + Intervals = Tree.getContaining(Point); + ASSERT_EQ(Intervals.size(), 1); + CheckData(Point, Intervals[0], 10, 20, 10.20); + + // Invalid interval values: 20] < x < [30 + Point = 25; + Intervals = Tree.getContaining(Point); + EXPECT_TRUE(Intervals.empty()); + + // Valid interval values: [30...40] + Point = 30; + Intervals = Tree.getContaining(Point); + ASSERT_EQ(Intervals.size(), 1); + CheckData(Point, Intervals[0], 30, 40, 30.40); + + Point = 35; + Intervals = Tree.getContaining(Point); + ASSERT_EQ(Intervals.size(), 1); + CheckData(Point, Intervals[0], 30, 40, 30.40); + + Point = 40; + Intervals = Tree.getContaining(Point); + ASSERT_EQ(Intervals.size(), 1); + CheckData(Point, Intervals[0], 30, 40, 30.40); + + // Invalid interval values: 40] < x + Point = 45; + Intervals = Tree.getContaining(Point); + EXPECT_TRUE(Intervals.empty()); +} + +using UUPoint = unsigned; // Interval endpoint type. +using UUValue = unsigned; // Mapped value type. + +using UUTree = IntervalTree; +using UUReferences = UUTree::IntervalReferences; +using UUData = UUTree::DataType; +using UUSorting = UUTree::Sorting; +using UUPoint = UUTree::PointType; +using UUValue = UUTree::ValueType; +using UUIter = UUTree::find_iterator; +using UUAlloc = UUTree::Allocator; + +void checkData(UUPoint Point, const UUData *Data, UUPoint Left, UUPoint Right, + UUValue Value) { + checkItem(Point, Data, Left, Right, Value); +} + +void checkData(UUPoint Point, UUIter Iter, UUPoint Left, UUPoint Right, + UUValue Value) { + checkItem(Point, Iter, Left, Right, Value); +} + +// Empty tree tests. +TEST(IntervalTreeTest, NoIntervals) { + UUAlloc Allocator; + UUTree Tree(Allocator); + EXPECT_TRUE(Tree.empty()); + Tree.clear(); + EXPECT_TRUE(Tree.empty()); + + // Create the tree and switch to query mode. + Tree.create(); + EXPECT_TRUE(Tree.empty()); + EXPECT_EQ(Tree.find(1), Tree.find_end()); +} + +// One item tree tests. +TEST(IntervalTreeTest, OneInterval) { + UUAlloc Allocator; + UUTree Tree(Allocator); + UUReferences Intervals; + UUPoint Point; + + // [10, 20] <- (1020) + // + // [10...20] + Tree.insert(10, 20, 1020); + + EXPECT_TRUE(Tree.empty()); + Tree.create(); + EXPECT_FALSE(Tree.empty()); + + // Invalid interval values: x < [10. + Point = 5; + Intervals = Tree.getContaining(Point); + EXPECT_TRUE(Intervals.empty()); + + // Valid interval values: [10...20]. + Point = 10; + Intervals = Tree.getContaining(Point); + ASSERT_EQ(Intervals.size(), 1); + checkData(Point, Intervals[0], 10, 20, 1020); + + Point = 15; + Intervals = Tree.getContaining(Point); + ASSERT_EQ(Intervals.size(), 1); + checkData(Point, Intervals[0], 10, 20, 1020); + + Point = 20; + Intervals = Tree.getContaining(Point); + ASSERT_EQ(Intervals.size(), 1); + checkData(Point, Intervals[0], 10, 20, 1020); + + // Invalid interval values: 20] < x + Point = 25; + Intervals = Tree.getContaining(Point); + EXPECT_TRUE(Intervals.empty()); +} + +// Two items tree tests. No overlapping. +TEST(IntervalTreeTest, TwoIntervals) { + UUAlloc Allocator; + UUTree Tree(Allocator); + UUReferences Intervals; + UUPoint Point; + + // [10, 20] <- (1020) + // [30, 40] <- (3040) + // + // [10...20] [30...40] + Tree.insert(10, 20, 1020); + Tree.insert(30, 40, 3040); + Tree.create(); + + // Invalid interval values: x < [10 + Point = 5; + Intervals = Tree.getContaining(Point); + EXPECT_TRUE(Intervals.empty()); + + // Valid interval values: [10...20] + Point = 10; + Intervals = Tree.getContaining(Point); + ASSERT_EQ(Intervals.size(), 1); + checkData(Point, Intervals[0], 10, 20, 1020); + + Point = 15; + Intervals = Tree.getContaining(Point); + ASSERT_EQ(Intervals.size(), 1); + checkData(Point, Intervals[0], 10, 20, 1020); + + Point = 20; + Intervals = Tree.getContaining(Point); + ASSERT_EQ(Intervals.size(), 1); + checkData(Point, Intervals[0], 10, 20, 1020); + + // Invalid interval values: 20] < x < [30 + Point = 25; + Intervals = Tree.getContaining(Point); + EXPECT_TRUE(Intervals.empty()); + + // Valid interval values: [30...40] + Point = 30; + Intervals = Tree.getContaining(Point); + ASSERT_EQ(Intervals.size(), 1); + checkData(Point, Intervals[0], 30, 40, 3040); + + Point = 35; + Intervals = Tree.getContaining(Point); + ASSERT_EQ(Intervals.size(), 1); + checkData(Point, Intervals[0], 30, 40, 3040); + + Point = 40; + Intervals = Tree.getContaining(Point); + ASSERT_EQ(Intervals.size(), 1); + checkData(Point, Intervals[0], 30, 40, 3040); + + // Invalid interval values: 40] < x + Point = 45; + Intervals = Tree.getContaining(Point); + EXPECT_TRUE(Intervals.empty()); +} + +// Three items tree tests. No overlapping. +TEST(IntervalTreeTest, ThreeIntervals) { + UUAlloc Allocator; + UUTree Tree(Allocator); + UUReferences Intervals; + UUPoint Point; + + // [10, 20] <- (1020) + // [30, 40] <- (3040) + // [50, 60] <- (5060) + // + // [10...20] [30...40] [50...60] + Tree.insert(10, 20, 1020); + Tree.insert(30, 40, 3040); + Tree.insert(50, 60, 5060); + Tree.create(); + + // Invalid interval values: x < [10 + Point = 5; + Intervals = Tree.getContaining(Point); + EXPECT_TRUE(Intervals.empty()); + + // Valid interval values: [10...20] + Point = 10; + Intervals = Tree.getContaining(Point); + ASSERT_EQ(Intervals.size(), 1); + checkData(Point, Intervals[0], 10, 20, 1020); + + Point = 15; + Intervals = Tree.getContaining(Point); + ASSERT_EQ(Intervals.size(), 1); + checkData(Point, Intervals[0], 10, 20, 1020); + + Point = 20; + Intervals = Tree.getContaining(Point); + ASSERT_EQ(Intervals.size(), 1); + checkData(Point, Intervals[0], 10, 20, 1020); + + // Invalid interval values: 20] < x < [30 + Point = 25; + Intervals = Tree.getContaining(Point); + EXPECT_TRUE(Intervals.empty()); + + // Valid interval values: [30...40] + Point = 30; + Intervals = Tree.getContaining(Point); + ASSERT_EQ(Intervals.size(), 1); + checkData(Point, Intervals[0], 30, 40, 3040); + + Point = 35; + Intervals = Tree.getContaining(Point); + ASSERT_EQ(Intervals.size(), 1); + checkData(Point, Intervals[0], 30, 40, 3040); + + Point = 40; + Intervals = Tree.getContaining(Point); + ASSERT_EQ(Intervals.size(), 1); + checkData(Point, Intervals[0], 30, 40, 3040); + + // Invalid interval values: 40] < x < [50 + Point = 45; + Intervals = Tree.getContaining(Point); + EXPECT_TRUE(Intervals.empty()); + + // Valid interval values: [50...60] + Point = 50; + Intervals = Tree.getContaining(Point); + ASSERT_EQ(Intervals.size(), 1); + checkData(Point, Intervals[0], 50, 60, 5060); + + Point = 55; + Intervals = Tree.getContaining(Point); + ASSERT_EQ(Intervals.size(), 1); + checkData(Point, Intervals[0], 50, 60, 5060); + + Point = 60; + Intervals = Tree.getContaining(Point); + ASSERT_EQ(Intervals.size(), 1); + checkData(Point, Intervals[0], 50, 60, 5060); + + // Invalid interval values: 60] < x + Point = 65; + Intervals = Tree.getContaining(Point); + EXPECT_TRUE(Intervals.empty()); +} + +// One item tree tests. +TEST(IntervalTreeTest, EmptyIntervals) { + UUAlloc Allocator; + UUTree Tree(Allocator); + UUReferences Intervals; + UUPoint Point; + + // [40, 60] <- (4060) + // [50, 50] <- (5050) + // [10, 10] <- (1010) + // [70, 70] <- (7070) + // + // [40...............60] + // [50...50] + // [10...10] + // [70...70] + Tree.insert(40, 60, 4060); + Tree.insert(50, 50, 5050); + Tree.insert(10, 10, 1010); + Tree.insert(70, 70, 7070); + + EXPECT_TRUE(Tree.empty()); + Tree.create(); + EXPECT_FALSE(Tree.empty()); + + // Invalid interval values: x < [10. + Point = 5; + Intervals = Tree.getContaining(Point); + EXPECT_TRUE(Intervals.empty()); + + // Valid interval values: [10...10]. + Point = 10; + Intervals = Tree.getContaining(Point); + ASSERT_EQ(Intervals.size(), 1); + checkData(Point, Intervals[0], 10, 10, 1010); + + // Invalid interval values: 10] < x + Point = 15; + Intervals = Tree.getContaining(Point); + EXPECT_TRUE(Intervals.empty()); + + // Invalid interval values: x < [50. + Point = 45; + Intervals = Tree.getContaining(Point); + ASSERT_EQ(Intervals.size(), 1); + checkData(Point, Intervals[0], 40, 60, 4060); + + // Valid interval values: [50...50]. + Point = 50; + Intervals = Tree.getContaining(Point); + ASSERT_EQ(Intervals.size(), 2); + checkData(Point, Intervals[0], 40, 60, 4060); + checkData(Point, Intervals[1], 50, 50, 5050); + + // Invalid interval values: 50] < x + Point = 55; + Intervals = Tree.getContaining(Point); + ASSERT_EQ(Intervals.size(), 1); + checkData(Point, Intervals[0], 40, 60, 4060); + + // Invalid interval values: x < [70. + Point = 65; + Intervals = Tree.getContaining(Point); + EXPECT_TRUE(Intervals.empty()); + + // Valid interval values: [70...70]. + Point = 70; + Intervals = Tree.getContaining(Point); + ASSERT_EQ(Intervals.size(), 1); + checkData(Point, Intervals[0], 70, 70, 7070); + + // Invalid interval values: 70] < x + Point = 75; + Intervals = Tree.getContaining(Point); + EXPECT_TRUE(Intervals.empty()); +} + +// Simple overlapping tests. +TEST(IntervalTreeTest, SimpleIntervalsOverlapping) { + UUAlloc Allocator; + UUTree Tree(Allocator); + UUReferences Intervals; + UUPoint Point; + + // [40, 60] <- (4060) + // [30, 70] <- (3070) + // [20, 80] <- (2080) + // [10, 90] <- (1090) + // + // [40...60] + // [30...............70] + // [20...........................80] + // [10.......................................90] + Tree.insert(40, 60, 4060); + Tree.insert(30, 70, 3070); + Tree.insert(20, 80, 2080); + Tree.insert(10, 90, 1090); + Tree.create(); + + // Invalid interval values: x < [10 + Point = 5; + Intervals = Tree.getContaining(Point); + EXPECT_TRUE(Intervals.empty()); + + // Valid interval values: + Point = 10; + Intervals = Tree.getContaining(Point); + ASSERT_EQ(Intervals.size(), 1); + checkData(Point, Intervals[0], 10, 90, 1090); + + Point = 15; + Intervals = Tree.getContaining(Point); + ASSERT_EQ(Intervals.size(), 1); + checkData(Point, Intervals[0], 10, 90, 1090); + + Point = 20; + Intervals = Tree.getContaining(Point); + ASSERT_EQ(Intervals.size(), 2); + checkData(Point, Intervals[0], 10, 90, 1090); + checkData(Point, Intervals[1], 20, 80, 2080); + Intervals = Tree.getContaining(Point); + Tree.sortIntervals(Intervals, UUSorting::Ascending); + ASSERT_EQ(Intervals.size(), 2); + checkData(Point, Intervals[0], 20, 80, 2080); + checkData(Point, Intervals[1], 10, 90, 1090); + Intervals = Tree.getContaining(Point); + Tree.sortIntervals(Intervals, UUSorting::Descending); + ASSERT_EQ(Intervals.size(), 2); + checkData(Point, Intervals[0], 10, 90, 1090); + checkData(Point, Intervals[1], 20, 80, 2080); + + Point = 25; + Intervals = Tree.getContaining(Point); + ASSERT_EQ(Intervals.size(), 2); + checkData(Point, Intervals[0], 10, 90, 1090); + checkData(Point, Intervals[1], 20, 80, 2080); + Intervals = Tree.getContaining(Point); + Tree.sortIntervals(Intervals, UUSorting::Ascending); + ASSERT_EQ(Intervals.size(), 2); + checkData(Point, Intervals[0], 20, 80, 2080); + checkData(Point, Intervals[1], 10, 90, 1090); + Intervals = Tree.getContaining(Point); + Tree.sortIntervals(Intervals, UUSorting::Descending); + ASSERT_EQ(Intervals.size(), 2); + checkData(Point, Intervals[0], 10, 90, 1090); + checkData(Point, Intervals[1], 20, 80, 2080); + + Point = 30; + Intervals = Tree.getContaining(Point); + ASSERT_EQ(Intervals.size(), 3); + checkData(Point, Intervals[0], 10, 90, 1090); + checkData(Point, Intervals[1], 20, 80, 2080); + checkData(Point, Intervals[2], 30, 70, 3070); + Intervals = Tree.getContaining(Point); + Tree.sortIntervals(Intervals, UUSorting::Ascending); + ASSERT_EQ(Intervals.size(), 3); + checkData(Point, Intervals[0], 30, 70, 3070); + checkData(Point, Intervals[1], 20, 80, 2080); + checkData(Point, Intervals[2], 10, 90, 1090); + Intervals = Tree.getContaining(Point); + Tree.sortIntervals(Intervals, UUSorting::Descending); + ASSERT_EQ(Intervals.size(), 3); + checkData(Point, Intervals[0], 10, 90, 1090); + checkData(Point, Intervals[1], 20, 80, 2080); + checkData(Point, Intervals[2], 30, 70, 3070); + + Point = 35; + Intervals = Tree.getContaining(Point); + ASSERT_EQ(Intervals.size(), 3); + checkData(Point, Intervals[0], 10, 90, 1090); + checkData(Point, Intervals[1], 20, 80, 2080); + checkData(Point, Intervals[2], 30, 70, 3070); + Intervals = Tree.getContaining(Point); + Tree.sortIntervals(Intervals, UUSorting::Ascending); + ASSERT_EQ(Intervals.size(), 3); + checkData(Point, Intervals[0], 30, 70, 3070); + checkData(Point, Intervals[1], 20, 80, 2080); + checkData(Point, Intervals[2], 10, 90, 1090); + Intervals = Tree.getContaining(Point); + Tree.sortIntervals(Intervals, UUSorting::Descending); + ASSERT_EQ(Intervals.size(), 3); + checkData(Point, Intervals[0], 10, 90, 1090); + checkData(Point, Intervals[1], 20, 80, 2080); + checkData(Point, Intervals[2], 30, 70, 3070); + + Point = 40; + Intervals = Tree.getContaining(Point); + ASSERT_EQ(Intervals.size(), 4); + checkData(Point, Intervals[0], 10, 90, 1090); + checkData(Point, Intervals[1], 20, 80, 2080); + checkData(Point, Intervals[2], 30, 70, 3070); + checkData(Point, Intervals[3], 40, 60, 4060); + Intervals = Tree.getContaining(Point); + Tree.sortIntervals(Intervals, UUSorting::Ascending); + ASSERT_EQ(Intervals.size(), 4); + checkData(Point, Intervals[0], 40, 60, 4060); + checkData(Point, Intervals[1], 30, 70, 3070); + checkData(Point, Intervals[2], 20, 80, 2080); + checkData(Point, Intervals[3], 10, 90, 1090); + Intervals = Tree.getContaining(Point); + Tree.sortIntervals(Intervals, UUSorting::Descending); + ASSERT_EQ(Intervals.size(), 4); + checkData(Point, Intervals[0], 10, 90, 1090); + checkData(Point, Intervals[1], 20, 80, 2080); + checkData(Point, Intervals[2], 30, 70, 3070); + checkData(Point, Intervals[3], 40, 60, 4060); + + Point = 50; + Intervals = Tree.getContaining(Point); + ASSERT_EQ(Intervals.size(), 4); + checkData(Point, Intervals[0], 10, 90, 1090); + checkData(Point, Intervals[1], 20, 80, 2080); + checkData(Point, Intervals[2], 30, 70, 3070); + checkData(Point, Intervals[3], 40, 60, 4060); + Intervals = Tree.getContaining(Point); + Tree.sortIntervals(Intervals, UUSorting::Ascending); + ASSERT_EQ(Intervals.size(), 4); + checkData(Point, Intervals[0], 40, 60, 4060); + checkData(Point, Intervals[1], 30, 70, 3070); + checkData(Point, Intervals[2], 20, 80, 2080); + checkData(Point, Intervals[3], 10, 90, 1090); + Intervals = Tree.getContaining(Point); + Tree.sortIntervals(Intervals, UUSorting::Descending); + ASSERT_EQ(Intervals.size(), 4); + checkData(Point, Intervals[0], 10, 90, 1090); + checkData(Point, Intervals[1], 20, 80, 2080); + checkData(Point, Intervals[2], 30, 70, 3070); + checkData(Point, Intervals[3], 40, 60, 4060); + + Point = 60; + Intervals = Tree.getContaining(Point); + ASSERT_EQ(Intervals.size(), 4); + checkData(Point, Intervals[0], 10, 90, 1090); + checkData(Point, Intervals[1], 20, 80, 2080); + checkData(Point, Intervals[2], 30, 70, 3070); + checkData(Point, Intervals[3], 40, 60, 4060); + Intervals = Tree.getContaining(Point); + Tree.sortIntervals(Intervals, UUSorting::Ascending); + ASSERT_EQ(Intervals.size(), 4); + checkData(Point, Intervals[0], 40, 60, 4060); + checkData(Point, Intervals[1], 30, 70, 3070); + checkData(Point, Intervals[2], 20, 80, 2080); + checkData(Point, Intervals[3], 10, 90, 1090); + Intervals = Tree.getContaining(Point); + Tree.sortIntervals(Intervals, UUSorting::Descending); + ASSERT_EQ(Intervals.size(), 4); + checkData(Point, Intervals[0], 10, 90, 1090); + checkData(Point, Intervals[1], 20, 80, 2080); + checkData(Point, Intervals[2], 30, 70, 3070); + checkData(Point, Intervals[3], 40, 60, 4060); + + Point = 65; + Intervals = Tree.getContaining(Point); + ASSERT_EQ(Intervals.size(), 3); + checkData(Point, Intervals[0], 10, 90, 1090); + checkData(Point, Intervals[1], 20, 80, 2080); + checkData(Point, Intervals[2], 30, 70, 3070); + Intervals = Tree.getContaining(Point); + Tree.sortIntervals(Intervals, UUSorting::Ascending); + ASSERT_EQ(Intervals.size(), 3); + checkData(Point, Intervals[0], 30, 70, 3070); + checkData(Point, Intervals[1], 20, 80, 2080); + checkData(Point, Intervals[2], 10, 90, 1090); + Intervals = Tree.getContaining(Point); + Tree.sortIntervals(Intervals, UUSorting::Descending); + ASSERT_EQ(Intervals.size(), 3); + checkData(Point, Intervals[0], 10, 90, 1090); + checkData(Point, Intervals[1], 20, 80, 2080); + checkData(Point, Intervals[2], 30, 70, 3070); + + Point = 70; + Intervals = Tree.getContaining(Point); + ASSERT_EQ(Intervals.size(), 3); + checkData(Point, Intervals[0], 10, 90, 1090); + checkData(Point, Intervals[1], 20, 80, 2080); + checkData(Point, Intervals[2], 30, 70, 3070); + Intervals = Tree.getContaining(Point); + Tree.sortIntervals(Intervals, UUSorting::Ascending); + ASSERT_EQ(Intervals.size(), 3); + checkData(Point, Intervals[0], 30, 70, 3070); + checkData(Point, Intervals[1], 20, 80, 2080); + checkData(Point, Intervals[2], 10, 90, 1090); + Intervals = Tree.getContaining(Point); + Tree.sortIntervals(Intervals, UUSorting::Descending); + ASSERT_EQ(Intervals.size(), 3); + checkData(Point, Intervals[0], 10, 90, 1090); + checkData(Point, Intervals[1], 20, 80, 2080); + checkData(Point, Intervals[2], 30, 70, 3070); + + Point = 75; + Intervals = Tree.getContaining(Point); + ASSERT_EQ(Intervals.size(), 2); + checkData(Point, Intervals[0], 10, 90, 1090); + checkData(Point, Intervals[1], 20, 80, 2080); + Intervals = Tree.getContaining(Point); + Tree.sortIntervals(Intervals, UUSorting::Ascending); + ASSERT_EQ(Intervals.size(), 2); + checkData(Point, Intervals[0], 20, 80, 2080); + checkData(Point, Intervals[1], 10, 90, 1090); + Intervals = Tree.getContaining(Point); + Tree.sortIntervals(Intervals, UUSorting::Descending); + ASSERT_EQ(Intervals.size(), 2); + checkData(Point, Intervals[0], 10, 90, 1090); + checkData(Point, Intervals[1], 20, 80, 2080); + + Point = 80; + Intervals = Tree.getContaining(Point); + ASSERT_EQ(Intervals.size(), 2); + checkData(Point, Intervals[0], 10, 90, 1090); + checkData(Point, Intervals[1], 20, 80, 2080); + Intervals = Tree.getContaining(Point); + Tree.sortIntervals(Intervals, UUSorting::Ascending); + ASSERT_EQ(Intervals.size(), 2); + checkData(Point, Intervals[0], 20, 80, 2080); + checkData(Point, Intervals[1], 10, 90, 1090); + Intervals = Tree.getContaining(Point); + Tree.sortIntervals(Intervals, UUSorting::Descending); + ASSERT_EQ(Intervals.size(), 2); + checkData(Point, Intervals[0], 10, 90, 1090); + checkData(Point, Intervals[1], 20, 80, 2080); + + Point = 85; + Intervals = Tree.getContaining(Point); + ASSERT_EQ(Intervals.size(), 1); + checkData(Point, Intervals[0], 10, 90, 1090); + + Point = 90; + Intervals = Tree.getContaining(Point); + ASSERT_EQ(Intervals.size(), 1); + checkData(Point, Intervals[0], 10, 90, 1090); + + // Invalid interval values: 90] < x + Point = 95; + Intervals = Tree.getContaining(Point); + EXPECT_TRUE(Intervals.empty()); +} + +// Complex Overlapping. +TEST(IntervalTreeTest, ComplexIntervalsOverlapping) { + UUAlloc Allocator; + UUTree Tree(Allocator); + UUReferences Intervals; + UUPoint Point; + + // [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, 45] <- (4345) + // [50, 75] <- (5075) + // [10, 85] <- (1085) + + // 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--45 50--------------------75 + // 10----------------------------------------------------------------------85 + + Tree.insert(30, 35, 3035); + Tree.insert(39, 50, 3950); + Tree.insert(55, 61, 5561); + Tree.insert(31, 56, 3156); + Tree.insert(12, 21, 1221); + Tree.insert(25, 41, 2541); + Tree.insert(49, 65, 4965); + Tree.insert(71, 79, 7179); + Tree.insert(11, 16, 1116); + Tree.insert(20, 30, 2030); + Tree.insert(36, 54, 3654); + Tree.insert(60, 70, 6070); + Tree.insert(74, 80, 7480); + Tree.insert(15, 40, 1540); + Tree.insert(43, 45, 4345); + Tree.insert(50, 75, 5075); + Tree.insert(10, 85, 1085); + Tree.create(); + + // Find valid interval values. + Point = 30; + Intervals = Tree.getContaining(Point); + ASSERT_EQ(Intervals.size(), 5); + checkData(Point, Intervals[0], 10, 85, 1085); + checkData(Point, Intervals[1], 25, 41, 2541); + checkData(Point, Intervals[2], 15, 40, 1540); + checkData(Point, Intervals[3], 20, 30, 2030); + checkData(Point, Intervals[4], 30, 35, 3035); + Intervals = Tree.getContaining(Point); + Tree.sortIntervals(Intervals, UUSorting::Ascending); + ASSERT_EQ(Intervals.size(), 5); + checkData(Point, Intervals[0], 30, 35, 3035); + checkData(Point, Intervals[1], 20, 30, 2030); + checkData(Point, Intervals[2], 25, 41, 2541); + checkData(Point, Intervals[3], 15, 40, 1540); + checkData(Point, Intervals[4], 10, 85, 1085); + Intervals = Tree.getContaining(Point); + Tree.sortIntervals(Intervals, UUSorting::Descending); + ASSERT_EQ(Intervals.size(), 5); + checkData(Point, Intervals[0], 10, 85, 1085); + checkData(Point, Intervals[1], 15, 40, 1540); + checkData(Point, Intervals[2], 25, 41, 2541); + checkData(Point, Intervals[3], 20, 30, 2030); + checkData(Point, Intervals[4], 30, 35, 3035); + + Point = 35; + Intervals = Tree.getContaining(Point); + ASSERT_EQ(Intervals.size(), 5); + checkData(Point, Intervals[0], 10, 85, 1085); + checkData(Point, Intervals[1], 31, 56, 3156); + checkData(Point, Intervals[2], 25, 41, 2541); + checkData(Point, Intervals[3], 15, 40, 1540); + checkData(Point, Intervals[4], 30, 35, 3035); + Intervals = Tree.getContaining(Point); + Tree.sortIntervals(Intervals, UUSorting::Ascending); + ASSERT_EQ(Intervals.size(), 5); + checkData(Point, Intervals[0], 30, 35, 3035); + checkData(Point, Intervals[1], 25, 41, 2541); + checkData(Point, Intervals[2], 31, 56, 3156); + checkData(Point, Intervals[3], 15, 40, 1540); + checkData(Point, Intervals[4], 10, 85, 1085); + Intervals = Tree.getContaining(Point); + Tree.sortIntervals(Intervals, UUSorting::Descending); + ASSERT_EQ(Intervals.size(), 5); + checkData(Point, Intervals[0], 10, 85, 1085); + checkData(Point, Intervals[1], 31, 56, 3156); + checkData(Point, Intervals[2], 15, 40, 1540); + checkData(Point, Intervals[3], 25, 41, 2541); + checkData(Point, Intervals[4], 30, 35, 3035); + + Point = 39; + Intervals = Tree.getContaining(Point); + ASSERT_EQ(Intervals.size(), 6); + checkData(Point, Intervals[0], 10, 85, 1085); + checkData(Point, Intervals[1], 31, 56, 3156); + checkData(Point, Intervals[2], 36, 54, 3654); + checkData(Point, Intervals[3], 39, 50, 3950); + checkData(Point, Intervals[4], 25, 41, 2541); + checkData(Point, Intervals[5], 15, 40, 1540); + Intervals = Tree.getContaining(Point); + Tree.sortIntervals(Intervals, UUSorting::Ascending); + ASSERT_EQ(Intervals.size(), 6); + checkData(Point, Intervals[0], 39, 50, 3950); + checkData(Point, Intervals[1], 25, 41, 2541); + checkData(Point, Intervals[2], 36, 54, 3654); + checkData(Point, Intervals[3], 31, 56, 3156); + checkData(Point, Intervals[4], 15, 40, 1540); + checkData(Point, Intervals[5], 10, 85, 1085); + Intervals = Tree.getContaining(Point); + Tree.sortIntervals(Intervals, UUSorting::Descending); + ASSERT_EQ(Intervals.size(), 6); + checkData(Point, Intervals[0], 10, 85, 1085); + checkData(Point, Intervals[1], 31, 56, 3156); + checkData(Point, Intervals[2], 15, 40, 1540); + checkData(Point, Intervals[3], 36, 54, 3654); + checkData(Point, Intervals[4], 25, 41, 2541); + checkData(Point, Intervals[5], 39, 50, 3950); + + Point = 50; + Intervals = Tree.getContaining(Point); + ASSERT_EQ(Intervals.size(), 6); + checkData(Point, Intervals[0], 10, 85, 1085); + checkData(Point, Intervals[1], 31, 56, 3156); + checkData(Point, Intervals[2], 36, 54, 3654); + checkData(Point, Intervals[3], 39, 50, 3950); + checkData(Point, Intervals[4], 49, 65, 4965); + checkData(Point, Intervals[5], 50, 75, 5075); + Intervals = Tree.getContaining(Point); + Tree.sortIntervals(Intervals, UUSorting::Ascending); + ASSERT_EQ(Intervals.size(), 6); + checkData(Point, Intervals[0], 39, 50, 3950); + checkData(Point, Intervals[1], 49, 65, 4965); + checkData(Point, Intervals[2], 36, 54, 3654); + checkData(Point, Intervals[3], 31, 56, 3156); + checkData(Point, Intervals[4], 50, 75, 5075); + checkData(Point, Intervals[5], 10, 85, 1085); + Intervals = Tree.getContaining(Point); + Tree.sortIntervals(Intervals, UUSorting::Descending); + ASSERT_EQ(Intervals.size(), 6); + checkData(Point, Intervals[0], 10, 85, 1085); + checkData(Point, Intervals[1], 31, 56, 3156); + checkData(Point, Intervals[2], 50, 75, 5075); + checkData(Point, Intervals[3], 36, 54, 3654); + checkData(Point, Intervals[4], 49, 65, 4965); + checkData(Point, Intervals[5], 39, 50, 3950); + + Point = 55; + Intervals = Tree.getContaining(Point); + ASSERT_EQ(Intervals.size(), 5); + checkData(Point, Intervals[0], 10, 85, 1085); + checkData(Point, Intervals[1], 31, 56, 3156); + checkData(Point, Intervals[2], 49, 65, 4965); + checkData(Point, Intervals[3], 50, 75, 5075); + checkData(Point, Intervals[4], 55, 61, 5561); + Intervals = Tree.getContaining(Point); + Tree.sortIntervals(Intervals, UUSorting::Ascending); + ASSERT_EQ(Intervals.size(), 5); + checkData(Point, Intervals[0], 55, 61, 5561); + checkData(Point, Intervals[1], 49, 65, 4965); + checkData(Point, Intervals[2], 31, 56, 3156); + checkData(Point, Intervals[3], 50, 75, 5075); + checkData(Point, Intervals[4], 10, 85, 1085); + Intervals = Tree.getContaining(Point); + Tree.sortIntervals(Intervals, UUSorting::Descending); + ASSERT_EQ(Intervals.size(), 5); + checkData(Point, Intervals[0], 10, 85, 1085); + checkData(Point, Intervals[1], 31, 56, 3156); + checkData(Point, Intervals[2], 50, 75, 5075); + checkData(Point, Intervals[3], 49, 65, 4965); + checkData(Point, Intervals[4], 55, 61, 5561); + + Point = 61; + Intervals = Tree.getContaining(Point); + ASSERT_EQ(Intervals.size(), 5); + checkData(Point, Intervals[0], 10, 85, 1085); + checkData(Point, Intervals[1], 49, 65, 4965); + checkData(Point, Intervals[2], 50, 75, 5075); + checkData(Point, Intervals[3], 55, 61, 5561); + checkData(Point, Intervals[4], 60, 70, 6070); + Intervals = Tree.getContaining(Point); + Tree.sortIntervals(Intervals, UUSorting::Ascending); + ASSERT_EQ(Intervals.size(), 5); + checkData(Point, Intervals[0], 55, 61, 5561); + checkData(Point, Intervals[1], 60, 70, 6070); + checkData(Point, Intervals[2], 49, 65, 4965); + checkData(Point, Intervals[3], 50, 75, 5075); + checkData(Point, Intervals[4], 10, 85, 1085); + Intervals = Tree.getContaining(Point); + Tree.sortIntervals(Intervals, UUSorting::Descending); + ASSERT_EQ(Intervals.size(), 5); + checkData(Point, Intervals[0], 10, 85, 1085); + checkData(Point, Intervals[1], 50, 75, 5075); + checkData(Point, Intervals[2], 49, 65, 4965); + checkData(Point, Intervals[3], 60, 70, 6070); + checkData(Point, Intervals[4], 55, 61, 5561); + + Point = 31; + Intervals = Tree.getContaining(Point); + ASSERT_EQ(Intervals.size(), 5); + checkData(Point, Intervals[0], 10, 85, 1085); + checkData(Point, Intervals[1], 31, 56, 3156); + checkData(Point, Intervals[2], 25, 41, 2541); + checkData(Point, Intervals[3], 15, 40, 1540); + checkData(Point, Intervals[4], 30, 35, 3035); + Intervals = Tree.getContaining(Point); + Tree.sortIntervals(Intervals, UUSorting::Ascending); + ASSERT_EQ(Intervals.size(), 5); + checkData(Point, Intervals[0], 30, 35, 3035); + checkData(Point, Intervals[1], 25, 41, 2541); + checkData(Point, Intervals[2], 31, 56, 3156); + checkData(Point, Intervals[3], 15, 40, 1540); + checkData(Point, Intervals[4], 10, 85, 1085); + Intervals = Tree.getContaining(Point); + Tree.sortIntervals(Intervals, UUSorting::Descending); + ASSERT_EQ(Intervals.size(), 5); + checkData(Point, Intervals[0], 10, 85, 1085); + checkData(Point, Intervals[1], 31, 56, 3156); + checkData(Point, Intervals[2], 15, 40, 1540); + checkData(Point, Intervals[3], 25, 41, 2541); + checkData(Point, Intervals[4], 30, 35, 3035); + + Point = 56; + Intervals = Tree.getContaining(Point); + ASSERT_EQ(Intervals.size(), 5); + checkData(Point, Intervals[0], 10, 85, 1085); + checkData(Point, Intervals[1], 31, 56, 3156); + checkData(Point, Intervals[2], 49, 65, 4965); + checkData(Point, Intervals[3], 50, 75, 5075); + checkData(Point, Intervals[4], 55, 61, 5561); + Intervals = Tree.getContaining(Point); + Tree.sortIntervals(Intervals, UUSorting::Ascending); + ASSERT_EQ(Intervals.size(), 5); + checkData(Point, Intervals[0], 55, 61, 5561); + checkData(Point, Intervals[1], 49, 65, 4965); + checkData(Point, Intervals[2], 31, 56, 3156); + checkData(Point, Intervals[3], 50, 75, 5075); + checkData(Point, Intervals[4], 10, 85, 1085); + Intervals = Tree.getContaining(Point); + Tree.sortIntervals(Intervals, UUSorting::Descending); + ASSERT_EQ(Intervals.size(), 5); + checkData(Point, Intervals[0], 10, 85, 1085); + checkData(Point, Intervals[1], 31, 56, 3156); + checkData(Point, Intervals[2], 50, 75, 5075); + checkData(Point, Intervals[3], 49, 65, 4965); + checkData(Point, Intervals[4], 55, 61, 5561); + + Point = 12; + Intervals = Tree.getContaining(Point); + ASSERT_EQ(Intervals.size(), 3); + checkData(Point, Intervals[0], 10, 85, 1085); + checkData(Point, Intervals[1], 11, 16, 1116); + checkData(Point, Intervals[2], 12, 21, 1221); + Intervals = Tree.getContaining(Point); + Tree.sortIntervals(Intervals, UUSorting::Ascending); + ASSERT_EQ(Intervals.size(), 3); + checkData(Point, Intervals[0], 11, 16, 1116); + checkData(Point, Intervals[1], 12, 21, 1221); + checkData(Point, Intervals[2], 10, 85, 1085); + Intervals = Tree.getContaining(Point); + Tree.sortIntervals(Intervals, UUSorting::Descending); + ASSERT_EQ(Intervals.size(), 3); + checkData(Point, Intervals[0], 10, 85, 1085); + checkData(Point, Intervals[1], 12, 21, 1221); + checkData(Point, Intervals[2], 11, 16, 1116); + + Point = 21; + Intervals = Tree.getContaining(Point); + ASSERT_EQ(Intervals.size(), 4); + checkData(Point, Intervals[0], 10, 85, 1085); + checkData(Point, Intervals[1], 15, 40, 1540); + checkData(Point, Intervals[2], 20, 30, 2030); + checkData(Point, Intervals[3], 12, 21, 1221); + Intervals = Tree.getContaining(Point); + Tree.sortIntervals(Intervals, UUSorting::Ascending); + ASSERT_EQ(Intervals.size(), 4); + checkData(Point, Intervals[0], 12, 21, 1221); + checkData(Point, Intervals[1], 20, 30, 2030); + checkData(Point, Intervals[2], 15, 40, 1540); + checkData(Point, Intervals[3], 10, 85, 1085); + Intervals = Tree.getContaining(Point); + Tree.sortIntervals(Intervals, UUSorting::Descending); + ASSERT_EQ(Intervals.size(), 4); + checkData(Point, Intervals[0], 10, 85, 1085); + checkData(Point, Intervals[1], 15, 40, 1540); + checkData(Point, Intervals[2], 20, 30, 2030); + checkData(Point, Intervals[3], 12, 21, 1221); + + Point = 25; + Intervals = Tree.getContaining(Point); + ASSERT_EQ(Intervals.size(), 4); + checkData(Point, Intervals[0], 10, 85, 1085); + checkData(Point, Intervals[1], 15, 40, 1540); + checkData(Point, Intervals[2], 20, 30, 2030); + checkData(Point, Intervals[3], 25, 41, 2541); + Intervals = Tree.getContaining(Point); + Tree.sortIntervals(Intervals, UUSorting::Ascending); + ASSERT_EQ(Intervals.size(), 4); + checkData(Point, Intervals[0], 20, 30, 2030); + checkData(Point, Intervals[1], 25, 41, 2541); + checkData(Point, Intervals[2], 15, 40, 1540); + checkData(Point, Intervals[3], 10, 85, 1085); + Intervals = Tree.getContaining(Point); + Tree.sortIntervals(Intervals, UUSorting::Descending); + ASSERT_EQ(Intervals.size(), 4); + checkData(Point, Intervals[0], 10, 85, 1085); + checkData(Point, Intervals[1], 15, 40, 1540); + checkData(Point, Intervals[2], 25, 41, 2541); + checkData(Point, Intervals[3], 20, 30, 2030); + + Point = 41; + Intervals = Tree.getContaining(Point); + ASSERT_EQ(Intervals.size(), 5); + checkData(Point, Intervals[0], 10, 85, 1085); + checkData(Point, Intervals[1], 31, 56, 3156); + checkData(Point, Intervals[2], 36, 54, 3654); + checkData(Point, Intervals[3], 39, 50, 3950); + checkData(Point, Intervals[4], 25, 41, 2541); + Intervals = Tree.getContaining(Point); + Tree.sortIntervals(Intervals, UUSorting::Ascending); + ASSERT_EQ(Intervals.size(), 5); + checkData(Point, Intervals[0], 39, 50, 3950); + checkData(Point, Intervals[1], 25, 41, 2541); + checkData(Point, Intervals[2], 36, 54, 3654); + checkData(Point, Intervals[3], 31, 56, 3156); + checkData(Point, Intervals[4], 10, 85, 1085); + Intervals = Tree.getContaining(Point); + Tree.sortIntervals(Intervals, UUSorting::Descending); + ASSERT_EQ(Intervals.size(), 5); + checkData(Point, Intervals[0], 10, 85, 1085); + checkData(Point, Intervals[1], 31, 56, 3156); + checkData(Point, Intervals[2], 36, 54, 3654); + checkData(Point, Intervals[3], 25, 41, 2541); + checkData(Point, Intervals[4], 39, 50, 3950); + + Point = 49; + Intervals = Tree.getContaining(Point); + ASSERT_EQ(Intervals.size(), 5); + checkData(Point, Intervals[0], 10, 85, 1085); + checkData(Point, Intervals[1], 31, 56, 3156); + checkData(Point, Intervals[2], 36, 54, 3654); + checkData(Point, Intervals[3], 39, 50, 3950); + checkData(Point, Intervals[4], 49, 65, 4965); + Intervals = Tree.getContaining(Point); + Tree.sortIntervals(Intervals, UUSorting::Ascending); + ASSERT_EQ(Intervals.size(), 5); + checkData(Point, Intervals[0], 39, 50, 3950); + checkData(Point, Intervals[1], 49, 65, 4965); + checkData(Point, Intervals[2], 36, 54, 3654); + checkData(Point, Intervals[3], 31, 56, 3156); + checkData(Point, Intervals[4], 10, 85, 1085); + Intervals = Tree.getContaining(Point); + Tree.sortIntervals(Intervals, UUSorting::Descending); + ASSERT_EQ(Intervals.size(), 5); + checkData(Point, Intervals[0], 10, 85, 1085); + checkData(Point, Intervals[1], 31, 56, 3156); + checkData(Point, Intervals[2], 36, 54, 3654); + checkData(Point, Intervals[3], 49, 65, 4965); + checkData(Point, Intervals[4], 39, 50, 3950); + + Point = 65; + Intervals = Tree.getContaining(Point); + ASSERT_EQ(Intervals.size(), 4); + checkData(Point, Intervals[0], 10, 85, 1085); + checkData(Point, Intervals[1], 50, 75, 5075); + checkData(Point, Intervals[2], 60, 70, 6070); + checkData(Point, Intervals[3], 49, 65, 4965); + Intervals = Tree.getContaining(Point); + Tree.sortIntervals(Intervals, UUSorting::Ascending); + ASSERT_EQ(Intervals.size(), 4); + checkData(Point, Intervals[0], 60, 70, 6070); + checkData(Point, Intervals[1], 49, 65, 4965); + checkData(Point, Intervals[2], 50, 75, 5075); + checkData(Point, Intervals[3], 10, 85, 1085); + Intervals = Tree.getContaining(Point); + Tree.sortIntervals(Intervals, UUSorting::Descending); + ASSERT_EQ(Intervals.size(), 4); + checkData(Point, Intervals[0], 10, 85, 1085); + checkData(Point, Intervals[1], 50, 75, 5075); + checkData(Point, Intervals[2], 49, 65, 4965); + checkData(Point, Intervals[3], 60, 70, 6070); + + Point = 71; + Intervals = Tree.getContaining(Point); + ASSERT_EQ(Intervals.size(), 3); + checkData(Point, Intervals[0], 10, 85, 1085); + checkData(Point, Intervals[1], 50, 75, 5075); + checkData(Point, Intervals[2], 71, 79, 7179); + Intervals = Tree.getContaining(Point); + Tree.sortIntervals(Intervals, UUSorting::Ascending); + ASSERT_EQ(Intervals.size(), 3); + checkData(Point, Intervals[0], 71, 79, 7179); + checkData(Point, Intervals[1], 50, 75, 5075); + checkData(Point, Intervals[2], 10, 85, 1085); + Intervals = Tree.getContaining(Point); + Tree.sortIntervals(Intervals, UUSorting::Descending); + ASSERT_EQ(Intervals.size(), 3); + checkData(Point, Intervals[0], 10, 85, 1085); + checkData(Point, Intervals[1], 50, 75, 5075); + checkData(Point, Intervals[2], 71, 79, 7179); + + Point = 79; + Intervals = Tree.getContaining(Point); + ASSERT_EQ(Intervals.size(), 3); + checkData(Point, Intervals[0], 10, 85, 1085); + checkData(Point, Intervals[1], 74, 80, 7480); + checkData(Point, Intervals[2], 71, 79, 7179); + Intervals = Tree.getContaining(Point); + Tree.sortIntervals(Intervals, UUSorting::Ascending); + ASSERT_EQ(Intervals.size(), 3); + checkData(Point, Intervals[0], 74, 80, 7480); + checkData(Point, Intervals[1], 71, 79, 7179); + checkData(Point, Intervals[2], 10, 85, 1085); + Intervals = Tree.getContaining(Point); + Tree.sortIntervals(Intervals, UUSorting::Descending); + ASSERT_EQ(Intervals.size(), 3); + checkData(Point, Intervals[0], 10, 85, 1085); + checkData(Point, Intervals[1], 71, 79, 7179); + checkData(Point, Intervals[2], 74, 80, 7480); + + Point = 11; + Intervals = Tree.getContaining(Point); + ASSERT_EQ(Intervals.size(), 2); + checkData(Point, Intervals[0], 10, 85, 1085); + checkData(Point, Intervals[1], 11, 16, 1116); + Intervals = Tree.getContaining(Point); + Tree.sortIntervals(Intervals, UUSorting::Ascending); + ASSERT_EQ(Intervals.size(), 2); + checkData(Point, Intervals[0], 11, 16, 1116); + checkData(Point, Intervals[1], 10, 85, 1085); + Intervals = Tree.getContaining(Point); + Tree.sortIntervals(Intervals, UUSorting::Descending); + ASSERT_EQ(Intervals.size(), 2); + checkData(Point, Intervals[0], 10, 85, 1085); + checkData(Point, Intervals[1], 11, 16, 1116); + + Point = 16; + Intervals = Tree.getContaining(Point); + ASSERT_EQ(Intervals.size(), 4); + checkData(Point, Intervals[0], 10, 85, 1085); + checkData(Point, Intervals[1], 15, 40, 1540); + checkData(Point, Intervals[2], 12, 21, 1221); + checkData(Point, Intervals[3], 11, 16, 1116); + Intervals = Tree.getContaining(Point); + Tree.sortIntervals(Intervals, UUSorting::Ascending); + ASSERT_EQ(Intervals.size(), 4); + checkData(Point, Intervals[0], 11, 16, 1116); + checkData(Point, Intervals[1], 12, 21, 1221); + checkData(Point, Intervals[2], 15, 40, 1540); + checkData(Point, Intervals[3], 10, 85, 1085); + Intervals = Tree.getContaining(Point); + Tree.sortIntervals(Intervals, UUSorting::Descending); + ASSERT_EQ(Intervals.size(), 4); + checkData(Point, Intervals[0], 10, 85, 1085); + checkData(Point, Intervals[1], 15, 40, 1540); + checkData(Point, Intervals[2], 12, 21, 1221); + checkData(Point, Intervals[3], 11, 16, 1116); + + Point = 20; + Intervals = Tree.getContaining(Point); + ASSERT_EQ(Intervals.size(), 4); + checkData(Point, Intervals[0], 10, 85, 1085); + checkData(Point, Intervals[1], 15, 40, 1540); + checkData(Point, Intervals[2], 20, 30, 2030); + checkData(Point, Intervals[3], 12, 21, 1221); + Intervals = Tree.getContaining(Point); + Tree.sortIntervals(Intervals, UUSorting::Ascending); + ASSERT_EQ(Intervals.size(), 4); + checkData(Point, Intervals[0], 12, 21, 1221); + checkData(Point, Intervals[1], 20, 30, 2030); + checkData(Point, Intervals[2], 15, 40, 1540); + checkData(Point, Intervals[3], 10, 85, 1085); + Intervals = Tree.getContaining(Point); + Tree.sortIntervals(Intervals, UUSorting::Descending); + ASSERT_EQ(Intervals.size(), 4); + checkData(Point, Intervals[0], 10, 85, 1085); + checkData(Point, Intervals[1], 15, 40, 1540); + checkData(Point, Intervals[2], 20, 30, 2030); + checkData(Point, Intervals[3], 12, 21, 1221); + + Point = 30; + Intervals = Tree.getContaining(Point); + ASSERT_EQ(Intervals.size(), 5); + checkData(Point, Intervals[0], 10, 85, 1085); + checkData(Point, Intervals[1], 25, 41, 2541); + checkData(Point, Intervals[2], 15, 40, 1540); + checkData(Point, Intervals[3], 20, 30, 2030); + checkData(Point, Intervals[4], 30, 35, 3035); + Intervals = Tree.getContaining(Point); + Tree.sortIntervals(Intervals, UUSorting::Ascending); + ASSERT_EQ(Intervals.size(), 5); + checkData(Point, Intervals[0], 30, 35, 3035); + checkData(Point, Intervals[1], 20, 30, 2030); + checkData(Point, Intervals[2], 25, 41, 2541); + checkData(Point, Intervals[3], 15, 40, 1540); + checkData(Point, Intervals[4], 10, 85, 1085); + Intervals = Tree.getContaining(Point); + Tree.sortIntervals(Intervals, UUSorting::Descending); + ASSERT_EQ(Intervals.size(), 5); + checkData(Point, Intervals[0], 10, 85, 1085); + checkData(Point, Intervals[1], 15, 40, 1540); + checkData(Point, Intervals[2], 25, 41, 2541); + checkData(Point, Intervals[3], 20, 30, 2030); + checkData(Point, Intervals[4], 30, 35, 3035); + + Point = 36; + Intervals = Tree.getContaining(Point); + ASSERT_EQ(Intervals.size(), 5); + checkData(Point, Intervals[0], 10, 85, 1085); + checkData(Point, Intervals[1], 31, 56, 3156); + checkData(Point, Intervals[2], 36, 54, 3654); + checkData(Point, Intervals[3], 25, 41, 2541); + checkData(Point, Intervals[4], 15, 40, 1540); + Intervals = Tree.getContaining(Point); + Tree.sortIntervals(Intervals, UUSorting::Ascending); + ASSERT_EQ(Intervals.size(), 5); + checkData(Point, Intervals[0], 25, 41, 2541); + checkData(Point, Intervals[1], 36, 54, 3654); + checkData(Point, Intervals[2], 31, 56, 3156); + checkData(Point, Intervals[3], 15, 40, 1540); + checkData(Point, Intervals[4], 10, 85, 1085); + Intervals = Tree.getContaining(Point); + Tree.sortIntervals(Intervals, UUSorting::Descending); + ASSERT_EQ(Intervals.size(), 5); + checkData(Point, Intervals[0], 10, 85, 1085); + checkData(Point, Intervals[1], 31, 56, 3156); + checkData(Point, Intervals[2], 15, 40, 1540); + checkData(Point, Intervals[3], 36, 54, 3654); + checkData(Point, Intervals[4], 25, 41, 2541); + + Point = 54; + Intervals = Tree.getContaining(Point); + ASSERT_EQ(Intervals.size(), 5); + checkData(Point, Intervals[0], 10, 85, 1085); + checkData(Point, Intervals[1], 31, 56, 3156); + checkData(Point, Intervals[2], 36, 54, 3654); + checkData(Point, Intervals[3], 49, 65, 4965); + checkData(Point, Intervals[4], 50, 75, 5075); + Intervals = Tree.getContaining(Point); + Tree.sortIntervals(Intervals, UUSorting::Ascending); + ASSERT_EQ(Intervals.size(), 5); + checkData(Point, Intervals[0], 49, 65, 4965); + checkData(Point, Intervals[1], 36, 54, 3654); + checkData(Point, Intervals[2], 31, 56, 3156); + checkData(Point, Intervals[3], 50, 75, 5075); + checkData(Point, Intervals[4], 10, 85, 1085); + Intervals = Tree.getContaining(Point); + Tree.sortIntervals(Intervals, UUSorting::Descending); + ASSERT_EQ(Intervals.size(), 5); + checkData(Point, Intervals[0], 10, 85, 1085); + checkData(Point, Intervals[1], 31, 56, 3156); + checkData(Point, Intervals[2], 50, 75, 5075); + checkData(Point, Intervals[3], 36, 54, 3654); + checkData(Point, Intervals[4], 49, 65, 4965); + + Point = 60; + Intervals = Tree.getContaining(Point); + ASSERT_EQ(Intervals.size(), 5); + checkData(Point, Intervals[0], 10, 85, 1085); + checkData(Point, Intervals[1], 49, 65, 4965); + checkData(Point, Intervals[2], 50, 75, 5075); + checkData(Point, Intervals[3], 55, 61, 5561); + checkData(Point, Intervals[4], 60, 70, 6070); + Intervals = Tree.getContaining(Point); + Tree.sortIntervals(Intervals, UUSorting::Ascending); + ASSERT_EQ(Intervals.size(), 5); + checkData(Point, Intervals[0], 55, 61, 5561); + checkData(Point, Intervals[1], 60, 70, 6070); + checkData(Point, Intervals[2], 49, 65, 4965); + checkData(Point, Intervals[3], 50, 75, 5075); + checkData(Point, Intervals[4], 10, 85, 1085); + Intervals = Tree.getContaining(Point); + Tree.sortIntervals(Intervals, UUSorting::Descending); + ASSERT_EQ(Intervals.size(), 5); + checkData(Point, Intervals[0], 10, 85, 1085); + checkData(Point, Intervals[1], 50, 75, 5075); + checkData(Point, Intervals[2], 49, 65, 4965); + checkData(Point, Intervals[3], 60, 70, 6070); + checkData(Point, Intervals[4], 55, 61, 5561); + + Point = 70; + Intervals = Tree.getContaining(Point); + ASSERT_EQ(Intervals.size(), 3); + checkData(Point, Intervals[0], 10, 85, 1085); + checkData(Point, Intervals[1], 50, 75, 5075); + checkData(Point, Intervals[2], 60, 70, 6070); + Intervals = Tree.getContaining(Point); + Tree.sortIntervals(Intervals, UUSorting::Ascending); + ASSERT_EQ(Intervals.size(), 3); + checkData(Point, Intervals[0], 60, 70, 6070); + checkData(Point, Intervals[1], 50, 75, 5075); + checkData(Point, Intervals[2], 10, 85, 1085); + Intervals = Tree.getContaining(Point); + Tree.sortIntervals(Intervals, UUSorting::Descending); + ASSERT_EQ(Intervals.size(), 3); + checkData(Point, Intervals[0], 10, 85, 1085); + checkData(Point, Intervals[1], 50, 75, 5075); + checkData(Point, Intervals[2], 60, 70, 6070); + + Point = 74; + Intervals = Tree.getContaining(Point); + ASSERT_EQ(Intervals.size(), 4); + checkData(Point, Intervals[0], 10, 85, 1085); + checkData(Point, Intervals[1], 50, 75, 5075); + checkData(Point, Intervals[2], 71, 79, 7179); + checkData(Point, Intervals[3], 74, 80, 7480); + Intervals = Tree.getContaining(Point); + Tree.sortIntervals(Intervals, UUSorting::Ascending); + ASSERT_EQ(Intervals.size(), 4); + checkData(Point, Intervals[0], 74, 80, 7480); + checkData(Point, Intervals[1], 71, 79, 7179); + checkData(Point, Intervals[2], 50, 75, 5075); + checkData(Point, Intervals[3], 10, 85, 1085); + Intervals = Tree.getContaining(Point); + Tree.sortIntervals(Intervals, UUSorting::Descending); + ASSERT_EQ(Intervals.size(), 4); + checkData(Point, Intervals[0], 10, 85, 1085); + checkData(Point, Intervals[1], 50, 75, 5075); + checkData(Point, Intervals[2], 71, 79, 7179); + checkData(Point, Intervals[3], 74, 80, 7480); + + Point = 80; + Intervals = Tree.getContaining(Point); + ASSERT_EQ(Intervals.size(), 2); + checkData(Point, Intervals[0], 10, 85, 1085); + checkData(Point, Intervals[1], 74, 80, 7480); + Intervals = Tree.getContaining(Point); + Tree.sortIntervals(Intervals, UUSorting::Ascending); + ASSERT_EQ(Intervals.size(), 2); + checkData(Point, Intervals[0], 74, 80, 7480); + checkData(Point, Intervals[1], 10, 85, 1085); + Intervals = Tree.getContaining(Point); + Tree.sortIntervals(Intervals, UUSorting::Descending); + ASSERT_EQ(Intervals.size(), 2); + checkData(Point, Intervals[0], 10, 85, 1085); + checkData(Point, Intervals[1], 74, 80, 7480); + + Point = 15; + Intervals = Tree.getContaining(Point); + ASSERT_EQ(Intervals.size(), 4); + checkData(Point, Intervals[0], 10, 85, 1085); + checkData(Point, Intervals[1], 15, 40, 1540); + checkData(Point, Intervals[2], 11, 16, 1116); + checkData(Point, Intervals[3], 12, 21, 1221); + Intervals = Tree.getContaining(Point); + Tree.sortIntervals(Intervals, UUSorting::Ascending); + ASSERT_EQ(Intervals.size(), 4); + checkData(Point, Intervals[0], 11, 16, 1116); + checkData(Point, Intervals[1], 12, 21, 1221); + checkData(Point, Intervals[2], 15, 40, 1540); + checkData(Point, Intervals[3], 10, 85, 1085); + Intervals = Tree.getContaining(Point); + Tree.sortIntervals(Intervals, UUSorting::Descending); + ASSERT_EQ(Intervals.size(), 4); + checkData(Point, Intervals[0], 10, 85, 1085); + checkData(Point, Intervals[1], 15, 40, 1540); + checkData(Point, Intervals[2], 12, 21, 1221); + checkData(Point, Intervals[3], 11, 16, 1116); + + Point = 40; + Intervals = Tree.getContaining(Point); + ASSERT_EQ(Intervals.size(), 6); + checkData(Point, Intervals[0], 10, 85, 1085); + checkData(Point, Intervals[1], 31, 56, 3156); + checkData(Point, Intervals[2], 36, 54, 3654); + checkData(Point, Intervals[3], 39, 50, 3950); + checkData(Point, Intervals[4], 25, 41, 2541); + checkData(Point, Intervals[5], 15, 40, 1540); + Intervals = Tree.getContaining(Point); + Tree.sortIntervals(Intervals, UUSorting::Ascending); + ASSERT_EQ(Intervals.size(), 6); + checkData(Point, Intervals[0], 39, 50, 3950); + checkData(Point, Intervals[1], 25, 41, 2541); + checkData(Point, Intervals[2], 36, 54, 3654); + checkData(Point, Intervals[3], 31, 56, 3156); + checkData(Point, Intervals[4], 15, 40, 1540); + checkData(Point, Intervals[5], 10, 85, 1085); + Intervals = Tree.getContaining(Point); + Tree.sortIntervals(Intervals, UUSorting::Descending); + ASSERT_EQ(Intervals.size(), 6); + checkData(Point, Intervals[0], 10, 85, 1085); + checkData(Point, Intervals[1], 31, 56, 3156); + checkData(Point, Intervals[2], 15, 40, 1540); + checkData(Point, Intervals[3], 36, 54, 3654); + checkData(Point, Intervals[4], 25, 41, 2541); + checkData(Point, Intervals[5], 39, 50, 3950); + + Point = 43; + Intervals = Tree.getContaining(Point); + ASSERT_EQ(Intervals.size(), 5); + checkData(Point, Intervals[0], 10, 85, 1085); + checkData(Point, Intervals[1], 31, 56, 3156); + checkData(Point, Intervals[2], 36, 54, 3654); + checkData(Point, Intervals[3], 39, 50, 3950); + checkData(Point, Intervals[4], 43, 45, 4345); + Intervals = Tree.getContaining(Point); + Tree.sortIntervals(Intervals, UUSorting::Ascending); + ASSERT_EQ(Intervals.size(), 5); + checkData(Point, Intervals[0], 43, 45, 4345); + checkData(Point, Intervals[1], 39, 50, 3950); + checkData(Point, Intervals[2], 36, 54, 3654); + checkData(Point, Intervals[3], 31, 56, 3156); + checkData(Point, Intervals[4], 10, 85, 1085); + Intervals = Tree.getContaining(Point); + Tree.sortIntervals(Intervals, UUSorting::Descending); + ASSERT_EQ(Intervals.size(), 5); + checkData(Point, Intervals[0], 10, 85, 1085); + checkData(Point, Intervals[1], 31, 56, 3156); + checkData(Point, Intervals[2], 36, 54, 3654); + checkData(Point, Intervals[3], 39, 50, 3950); + checkData(Point, Intervals[4], 43, 45, 4345); + + Point = 45; + Intervals = Tree.getContaining(Point); + ASSERT_EQ(Intervals.size(), 5); + checkData(Point, Intervals[0], 10, 85, 1085); + checkData(Point, Intervals[1], 31, 56, 3156); + checkData(Point, Intervals[2], 36, 54, 3654); + checkData(Point, Intervals[3], 39, 50, 3950); + checkData(Point, Intervals[4], 43, 45, 4345); + Intervals = Tree.getContaining(Point); + Tree.sortIntervals(Intervals, UUSorting::Ascending); + ASSERT_EQ(Intervals.size(), 5); + checkData(Point, Intervals[0], 43, 45, 4345); + checkData(Point, Intervals[1], 39, 50, 3950); + checkData(Point, Intervals[2], 36, 54, 3654); + checkData(Point, Intervals[3], 31, 56, 3156); + checkData(Point, Intervals[4], 10, 85, 1085); + Intervals = Tree.getContaining(Point); + Tree.sortIntervals(Intervals, UUSorting::Descending); + ASSERT_EQ(Intervals.size(), 5); + checkData(Point, Intervals[0], 10, 85, 1085); + checkData(Point, Intervals[1], 31, 56, 3156); + checkData(Point, Intervals[2], 36, 54, 3654); + checkData(Point, Intervals[3], 39, 50, 3950); + checkData(Point, Intervals[4], 43, 45, 4345); + + Point = 50; + Intervals = Tree.getContaining(Point); + ASSERT_EQ(Intervals.size(), 6); + checkData(Point, Intervals[0], 10, 85, 1085); + checkData(Point, Intervals[1], 31, 56, 3156); + checkData(Point, Intervals[2], 36, 54, 3654); + checkData(Point, Intervals[3], 39, 50, 3950); + checkData(Point, Intervals[4], 49, 65, 4965); + checkData(Point, Intervals[5], 50, 75, 5075); + Intervals = Tree.getContaining(Point); + Tree.sortIntervals(Intervals, UUSorting::Ascending); + ASSERT_EQ(Intervals.size(), 6); + checkData(Point, Intervals[0], 39, 50, 3950); + checkData(Point, Intervals[1], 49, 65, 4965); + checkData(Point, Intervals[2], 36, 54, 3654); + checkData(Point, Intervals[3], 31, 56, 3156); + checkData(Point, Intervals[4], 50, 75, 5075); + checkData(Point, Intervals[5], 10, 85, 1085); + Intervals = Tree.getContaining(Point); + Tree.sortIntervals(Intervals, UUSorting::Descending); + ASSERT_EQ(Intervals.size(), 6); + checkData(Point, Intervals[0], 10, 85, 1085); + checkData(Point, Intervals[1], 31, 56, 3156); + checkData(Point, Intervals[2], 50, 75, 5075); + checkData(Point, Intervals[3], 36, 54, 3654); + checkData(Point, Intervals[4], 49, 65, 4965); + checkData(Point, Intervals[5], 39, 50, 3950); + + Point = 75; + Intervals = Tree.getContaining(Point); + ASSERT_EQ(Intervals.size(), 4); + checkData(Point, Intervals[0], 10, 85, 1085); + checkData(Point, Intervals[1], 50, 75, 5075); + checkData(Point, Intervals[2], 74, 80, 7480); + checkData(Point, Intervals[3], 71, 79, 7179); + Intervals = Tree.getContaining(Point); + Tree.sortIntervals(Intervals, UUSorting::Ascending); + ASSERT_EQ(Intervals.size(), 4); + checkData(Point, Intervals[0], 74, 80, 7480); + checkData(Point, Intervals[1], 71, 79, 7179); + checkData(Point, Intervals[2], 50, 75, 5075); + checkData(Point, Intervals[3], 10, 85, 1085); + Intervals = Tree.getContaining(Point); + Tree.sortIntervals(Intervals, UUSorting::Descending); + ASSERT_EQ(Intervals.size(), 4); + checkData(Point, Intervals[0], 10, 85, 1085); + checkData(Point, Intervals[1], 50, 75, 5075); + checkData(Point, Intervals[2], 71, 79, 7179); + checkData(Point, Intervals[3], 74, 80, 7480); + + Point = 10; + Intervals = Tree.getContaining(Point); + ASSERT_EQ(Intervals.size(), 1); + checkData(Point, Intervals[0], 10, 85, 1085); + + Point = 85; + Intervals = Tree.getContaining(Point); + ASSERT_EQ(Intervals.size(), 1); + checkData(Point, Intervals[0], 10, 85, 1085); + + // Invalid interval values. + Point = 5; + Intervals = Tree.getContaining(Point); + EXPECT_TRUE(Intervals.empty()); + Point = 90; + Intervals = Tree.getContaining(Point); + EXPECT_TRUE(Intervals.empty()); +} + +// Four items tree tests. Overlapping. Check mapped values and iterators. +TEST(IntervalTreeTest, MappedValuesIteratorsTree) { + UUAlloc Allocator; + UUTree Tree(Allocator); + UUPoint Point; + + // [10, 20] <- (1020) + // [15, 25] <- (1525) + // [50, 60] <- (5060) + // [55, 65] <- (5565) + // + // [10.........20] + // [15.........25] + // [50.........60] + // [55.........65] + Tree.insert(10, 20, 1020); + Tree.insert(15, 25, 1525); + Tree.insert(50, 60, 5060); + Tree.insert(55, 65, 5565); + Tree.create(); + + // Iterators. + { + // Start searching for '10'. + Point = 10; + UUIter Iter = Tree.find(Point); + EXPECT_NE(Iter, Tree.find_end()); + checkData(Point, Iter, 10, 20, 1020); + ++Iter; + EXPECT_EQ(Iter, Tree.find_end()); + } + { + // Start searching for '15'. + Point = 15; + UUIter Iter = Tree.find(Point); + ASSERT_TRUE(Iter != Tree.find_end()); + checkData(Point, Iter, 15, 25, 1525); + ++Iter; + ASSERT_TRUE(Iter != Tree.find_end()); + checkData(Point, Iter, 10, 20, 1020); + ++Iter; + EXPECT_EQ(Iter, Tree.find_end()); + } + { + // Start searching for '20'. + Point = 20; + UUIter Iter = Tree.find(Point); + ASSERT_TRUE(Iter != Tree.find_end()); + checkData(Point, Iter, 15, 25, 1525); + ++Iter; + ASSERT_TRUE(Iter != Tree.find_end()); + checkData(Point, Iter, 10, 20, 1020); + ++Iter; + EXPECT_EQ(Iter, Tree.find_end()); + } + { + // Start searching for '25'. + Point = 25; + UUIter Iter = Tree.find(Point); + ASSERT_TRUE(Iter != Tree.find_end()); + checkData(Point, Iter, 15, 25, 1525); + ++Iter; + EXPECT_EQ(Iter, Tree.find_end()); + } + // Invalid interval values. + { + Point = 5; + UUIter Iter = Tree.find(Point); + EXPECT_EQ(Iter, Tree.find_end()); + } + { + Point = 45; + UUIter Iter = Tree.find(Point); + EXPECT_EQ(Iter, Tree.find_end()); + } + { + Point = 70; + UUIter Iter = Tree.find(Point); + EXPECT_EQ(Iter, Tree.find_end()); + } +} + +} // namespace