[llvm-debuginfo-analyzer] 01 - Interval tree

[CarlosAlbertoEnciso]

Summary

LLVM debug information visual analyzer

For more information, see the RFC https://discourse.llvm.org/t/llvm-dev-rfc-llvm-dva-debug-information-visual-analyzer/62570

Patches:
01 - Interval Tree
02 - Driver and Documentation
03 - Logical Elements
04 - Locations and Ranges
05 - Select Elements
06 - Warning and Internal Options
07 - Compare Elements
08 - ELF Reader
09 - CodeView Reader
10 - Smart Pointers

This is a high level summary of the changes in this patch.

Interval tree
Implementation for an Interval Tree (light tree data structure to hold intervals).

[psamolysov]

I'm not familiar with the discussion of the class design. From the architecture point of view, the class can be divided into a builder that accumulates the intervals and build the tree and an immutable tree class that contains the query methods only. This design can be an overengineering but on the other hand the implemented algorithm (in the find_iterator for example) is not short and it deserves its own class.

llvm/include/llvm/ADT/IntervalTree.h

119

It is described as the intervals are stored above but I see in the example they are printed in the same order, for IR - in the descending order by ending point.

151

Just a nit. Personally I didn't manage to get how the intervals actually stored in the node until I had a look at the source code. Maybe the "that vector (global bucket)" should be introduced a little bit before?

175

208

224

Maybe to use contains (with S) as the method's name? For example, the standard library contains classes with methods with this name: https://en.cppreference.com/w/cpp/string/basic_string_view/contains

256–258

Should these three methods be marked as const?

261

We have no idea what the type will be used for the PointType, theoretically it can be heavy, so move could make sense.

298

This method looks as it could be static.

300

315

Just a nit. By the coding convention all names of the variables should start from a capital letter, I'm not sure whether lambdas are exception here?

355

The word left has different meaning in the comment: as opposite to the right and while there is at least one interval. English is not my native language, and the first time I read the phrase as "there are no intervals in the left side". Could you rewrite the comment a bit?

362

To not copy the PointType of unknown size?

430

std::iterator is deprecated in C++17, because the project will use C++17 soon it might make sense to not use a deprecated class for the new code.

521

539

There is a code duplication between operator-> and operator*. It may make sense to extract the body of the operator-> into a private method (current(), for example) that returns a pointer and dereference this method's return value in the operator*.

580

Maybe the References vector also should be cleared?

592

Should all the query methods contain an assert that the tree has been actually created?

601

This method is for sorting already returned interval set, so this is just a helper and it looks like the method can be a static member of the class.

[probinson]

llvm/include/llvm/ADT/IntervalTree.h

355

Maybe "no intervals remaining" would avoid the ambiguity.

[psamolysov]

llvm/include/llvm/ADT/IntervalTree.h

580

Sorry, I see the References vector are cleared at the end of the create() method.

601

Hm... maybe I get it wrong and because the IntervalSet contains only pointers inside the instance of the tree, the method should be a member of the class, not a static member.

625

628

To be consistent with 2 lines above.

657

llvm/unittests/ADT/IntervalTreeTest.cpp

82

84

97

I see you use ASSERT_TRUE with == and EXPECT_EQ(..., true) many times below. So, it means that this usage is expected.

[psamolysov]

llvm/include/llvm/ADT/IntervalTree.h

355

@probinson Sounds good

[probinson]

llvm/unittests/ADT/IntervalTreeTest.cpp

102

Better to use ASSERT_EQ(Intervals.size(), 1) here and below. Googletest will provide a better diagnostic on failure, this way.

[CarlosAlbertoEnciso]

llvm/include/llvm/ADT/IntervalTree.h

119

You are rigth. The comment should read in descending order by ending point.

151

May be before the line // The following is the output from print(): ?

175

Changed will to with.

224

Sounds good. Changing contain to contains.

315

The current discussion:
https://discourse.llvm.org/t/naming-lambdas-in-llvm-coding-standards/62689/6

It seems the consensus is to treat them as variables.

[CarlosAlbertoEnciso]

llvm/include/llvm/ADT/IntervalTree.h

256–258

Marked as const.

355

The comment will read as ... until there are no intervals remaining..

539

Good point. Refactored the common code into a private method current().

[CarlosAlbertoEnciso]

llvm/include/llvm/ADT/IntervalTree.h

362

I am not sure if I understand the issue. A typical case to create the IntervalTree would be:

using UUPoint = unsigned; // Interval range type.
using UUValue = unsigned; // Mapped value type.

using UUTree = IntervalTree<UUPoint, UUValue>;

with PointType being unsigned

[psamolysov]

llvm/include/llvm/ADT/IntervalTree.h

315

If we treat lambdas as variables, we should use leading upper case characters like for other variables. Would you like to rename all the lambdas?

362

@CarlosAlbertoEnciso Thank you for the response. I though because PointType is a template parameter (an alias for PointT actually) it may be any type. If you are sure the type will be unsigned in a typical case, there is no reason to use a const reference for unsigned.

[CarlosAlbertoEnciso]

llvm/include/llvm/ADT/IntervalTree.h

151

Moved comments before the // The following is the output from print():

300

I belive the assertion condition should be:
assert(Start + Size < IntervalSet.size() && "Start + Size must be in bounds of the IntervalSet");

315

Yes. I will rename all the lambdas across all patches.

362

I think we get confused.

• PointType is a template parameter; alias for PointT and can be any type.
• I used unsigned as an example to show how the IntervalTree can be used.

In your original comment, you wrote:
To not copy the PointType of unknown size?

I am not quite sure about your question.

[psamolysov]

llvm/include/llvm/ADT/IntervalTree.h

300

Sure, sorry for the typo in the suggestion.

362

I mean that one can create the following IntervalTree:

using UUPoint = std::array<unsigned, 128>; // Just an example, this maybe makes no sense but it is possible.
using UUValue = unsigned; // Mapped value type.

using UUTree = IntervalTree<UUPoint, UUValue>;

And in this tree your original line

PointType MiddlePoint = EndPoints[MiddleIndex];

means that the whole array of 128 unsigneds will be copied into MiddlePoint even though the value is already in the EndPoints and can be accessible by a const reference. On the other hand, if PointType is just an unsigned, the copy is better than the reference creation.

[CarlosAlbertoEnciso]

llvm/include/llvm/ADT/IntervalTree.h

300

Added your suggested assertion.

[CarlosAlbertoEnciso]

llvm/include/llvm/ADT/IntervalTree.h

362

Thanks for your example and explanation.

May be the main problem is that you can create a tree with types that make no sense, like your example. The IntervalTree is expecting fundamental types and pointers.
I will add the following for both PointT and ValueT:

static_assert(std::is_fundamental<PointT>::value ||
                  std::is_pointer<PointT>::value,
              "PointT must be an fundamental or pointer type");

This is added code:

...
template <typename T>
using TypeIsValid =
    std::integral_constant<bool, std::is_fundamental<T>::value ||
                                     std::is_pointer<T>::value>;

template <typename PointT, typename ValueT,
          typename DataT = IntervalData<PointT, ValueT>>
class IntervalTree {
  static_assert(TypeIsValid<PointT>::value,
                "PointT must be an fundamental or pointer type");
  static_assert(TypeIsValid<ValueT>::value,
                "ValueT must be an fundamental or pointer type");
...
};

With this code, all your comments about std::move(...) will be addressed.

430

Removing std::iterator and replacing it with:

...
  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 &;
...

592

I think it is a good idea. I will add some asserts.

625

Added the const.

[CarlosAlbertoEnciso]

llvm/include/llvm/ADT/IntervalTree.h

208

Addressed by enforcing the allowed types (fundamental/pointer) when creating the IntervalTree.

261

Addressed by enforcing the allowed types (fundamental/pointer) when creating the IntervalTree.

521

Addressed by enforcing the allowed types (fundamental/pointer) when creating the IntervalTree.

657

Addressed by enforcing the allowed types (fundamental/pointer) when creating the IntervalTree.

[psamolysov]

llvm/include/llvm/ADT/IntervalTree.h

362

Good idea! Thank you! Yes, having the constraint on both PointT and ValueT addresses all my comments about references and std::move.

[CarlosAlbertoEnciso]

llvm/include/llvm/ADT/IntervalTree.h

592

Added assertion:

IntervalReferences getContaining(PointType Point) const {
  assert(!empty() && "Interval tree it is not constructed.");
  ...
}

628

Changed.

[psamolysov]

llvm/include/llvm/ADT/IntervalTree.h

592

Looks good, thank you. Maybe the it word is unnecessary.

[CarlosAlbertoEnciso]

llvm/include/llvm/ADT/IntervalTree.h

592

Thanks. Fixed the typo.

[CarlosAlbertoEnciso]

llvm/include/llvm/ADT/IntervalTree.h

298

Added the static bit.

601

I am afraid I don't follow you. IntervalSet is just an alias for the SmallVector instance. Do you mean make it static as the printList method you mentioned in other comment?

[psamolysov]

llvm/include/llvm/ADT/IntervalTree.h

601

@CarlosAlbertoEnciso Yes, I mean the method sortIntervals should be static as well as the printList one. Technically this should work well. Actually, the sortIntevals method expects the IntervalReferences &IntervalSet parameter that actually contains the pointers to the IntervalData values (as you said, IntervalReferences is just an alias to SmallVector<IntervalData *>) stored in the tree the method is a member of, but nothing protect the user from calling the method with pointers to IntevalDatas from another tree and even from an actually dead tree, in other words - with dangling pointers. So, I think it is not a big deal whether the method is static or not but because it doesn't use any members of a concrete tree object, it could be better to make the method static as well as the printList one. Sorry for my previous comment where I said the method should be a non-static member of the class, currently I think it can be a static member but the last word is yours.

[CarlosAlbertoEnciso]

llvm/include/llvm/ADT/IntervalTree.h

601

@psamolysov Thanks very much for the great explanation.
Making both methods sortIntervals and printList statics.

[psamolysov]

Ongoing changes LGTM but I would like you to wait for another approve too. @CarlosAlbertoEnciso please upload the final revision.

[CarlosAlbertoEnciso]

• Addressed the reviewer’s feedback.
• Tool renamed as: llvm-debuginfo-analyzer.

[CarlosAlbertoEnciso]

Ping.

[CarlosAlbertoEnciso]

In D125776#3592136, @psamolysov wrote:

Ongoing changes LGTM but I would like you to wait for another approve too. @CarlosAlbertoEnciso please upload the final revision.

@psamolysov Thanks for your reviews. Currently waiting for another LGTM.

[probinson]

llvm/include/llvm/ADT/IntervalTree.h

37

I think this description sounds too much like what std::map does. Also I think it's worth mentioning that they are closed intervals.
Suggested synopsis: "Closed intervals delimited by PointT objects are mapped to ValueT objects. "

Also, should state the restriction enforced by IntervalData, i.e., that PointT and ValueT must be fundamental or pointer types. (A pointer type for PointT would be risky, as pointer comparison results are "unspecified" if the two pointers address different objects that are not in the same array. The only really safe pointer type for PointT would be void*. Maybe you want to disallow pointer types? Or only void* ?)

78

Are you allowed to have an interval like [12, 12]? I don't see any examples like that here.

194

Let's not use the word "ranges" to describe a type, as that means something else in C++. "interval endpoints type" maybe?
(In other commentary, "ranges" can be a reasonable word to use.)

209

assert(Left < Right) ? Or assert(Left <= Right) if [x, x] intervals are allowed.
Maybe you check this elsewhere and I didn't see it.

237

This could use std::bool_constant

llvm/unittests/ADT/IntervalTreeTest.cpp

82

+1

84

+1

144

Interval endpoint type.

[CarlosAlbertoEnciso]

llvm/include/llvm/ADT/IntervalTree.h

37

I think this description sounds too much like what std::map does. Also I think it's worth mentioning that they are closed intervals.
Suggested synopsis: "Closed intervals delimited by PointT objects are mapped to ValueT objects. "

Taking your suggested synopsis.

Also, should state the restriction enforced by IntervalData, i.e., that PointT and ValueT must be fundamental or pointer types. (A pointer type for PointT would be risky, as pointer comparison results are "unspecified" if the two pointers address different objects that are not in the same array. The only really safe pointer type for PointT would be void*. Maybe you want to disallow pointer types? Or only void* ?)

Added the following restrictions:
ValueT: fundamental or pointer types.
PointT: fundamental types.

78

It is allowed.
I have changed [43, 45] -> [43, 43].
Added test case.

194

Let's not use the word "ranges" to describe a type, as that means something else in C++. "interval endpoints type" maybe?

Changed ranges to interval endpoints.

209

Added
assert(Left <= Right && "'Left' must be less or equal that 'Right'");

237

Changed to use std::bool_constant.

llvm/unittests/ADT/IntervalTreeTest.cpp

82

Changed all ocurrences:
EXPECT_EQ(cond, true); --> EXPECT_TRUE(cond);

84

Changed all ocurrences:
EXPECT_EQ(cond, true); --> EXPECT_TRUE(cond);

144

Changed.

[CarlosAlbertoEnciso]

Address points raised by @probinson.

[probinson]

A couple of nits, LGTM.

llvm/include/llvm/ADT/IntervalTree.h

214

llvm/unittests/ADT/IntervalTreeTest.cpp

104

[CarlosAlbertoEnciso]

llvm/include/llvm/ADT/IntervalTree.h

214

Changed.

llvm/unittests/ADT/IntervalTreeTest.cpp

104

Replaced all occurrences of ASSERT_TRUE(cond1 == cond2) to ASSERT_EQ(cond1, cond2)

[CarlosAlbertoEnciso]

Updated patch

Thanks to @psamolysov and @psamolysov for your reviews.

[antondaubert]

The test seems to be failing, could you please take a look?

x86-64 Linux, and debug mode

Errors are like:

IntervalTreeTest.cpp:41
Expected equality of these values:
  Item->left()
    Which is: 15
  Left
    Which is: 31

(and many other similar failures)

[uabelho]

llvm/unittests/ADT/IntervalTreeTest.cpp

104

Hi,

Compiling with clang 8 I get the following warning here:

11:37:12 In file included from ../unittests/ADT/IntervalTreeTest.cpp:10:
11:37:12 ../utils/unittest/googletest/include/gtest/gtest.h:1526:11: error: comparison of integers of different signs: 'const unsigned long' and 'const int' [-Werror,-Wsign-compare]
11:37:12   if (lhs == rhs) {
11:37:12       ~~~ ^  ~~~
11:37:12 ../utils/unittest/googletest/include/gtest/gtest.h:1553:12: note: in instantiation of function template specialization 'testing::internal::CmpHelperEQ<unsigned long, int>' requested here
11:37:12     return CmpHelperEQ(lhs_expression, rhs_expression, lhs, rhs);
11:37:12            ^
11:37:12 ../unittests/ADT/IntervalTreeTest.cpp:103:3: note: in instantiation of function template specialization 'testing::internal::EqHelper::Compare<unsigned long, int, nullptr>' requested here
11:37:12   ASSERT_EQ(Intervals.size(), 1);
11:37:12   ^
11:37:12 ../utils/unittest/googletest/include/gtest/gtest.h:2056:32: note: expanded from macro 'ASSERT_EQ'
11:37:12 # define ASSERT_EQ(val1, val2) GTEST_ASSERT_EQ(val1, val2)
11:37:12                                ^
11:37:12 ../utils/unittest/googletest/include/gtest/gtest.h:2040:54: note: expanded from macro 'GTEST_ASSERT_EQ'
11:37:12   ASSERT_PRED_FORMAT2(::testing::internal::EqHelper::Compare, val1, val2)
11:37:12                                                      ^
11:37:12 1 error generated.

[CarlosAlbertoEnciso]

@uabelho: Sorry for the issues. The problem is with the ASSERT_EQ(Intervals.size(), 1); comparisons.
They should be ASSERT_EQ(Intervals.size(), 1u);.

I am working on a new patch.

[CarlosAlbertoEnciso]

In D125776#3817597, @antondaubert wrote:

The test seems to be failing, could you please take a look?

Errors are like:

IntervalTreeTest.cpp:41
Expected equality of these values:
  Item->left()
    Which is: 15
  Left
    Which is: 31

(and many other similar failures)

@antondaubert: From the buildbot: I can see only these type of errors:
https://lab.llvm.org/buildbot/#/builders/36/builds/25424

/home/buildbots/ppc64le-lld-multistage-test/ppc64le-lld-multistage-test/llvm-project/llvm/unittests/ADT/IntervalTreeTest.cpp:103:3: note: in instantiation of function template specialization 'testing::internal::EqHelper::Compare<unsigned long, int, nullptr>' requested here

ASSERT_EQ(Intervals.size(), 1);

[CarlosAlbertoEnciso]

Updated patch to correct build failures:

https://lab.llvm.org/buildbot/#/builders/36/builds/25424

error: comparison of integers of different signs: 'const unsigned long' and 'const int' [-Werror,-Wsign-compare]

[Orlando]

The most recent change LGTM. FYI it looks like your most recent diff only includes the fix and is missing the changes from the original patch.

[CarlosAlbertoEnciso]

In D125776#3817740, @Orlando wrote:

The most recent change LGTM. FYI it looks like your most recent diff only includes the fix and is missing the changes from the original patch.

The diff was created based on the commited change.

[Orlando]

The diff was created based on the commited change.

I think it's typical to open a new revision if you don't intend to revert the original. The other option is to revert the change, fold this fix into the original patch (in this revision) and re-commit.

[CarlosAlbertoEnciso]

In D125776#3817785, @Orlando wrote:

The diff was created based on the commited change.

I think it's typical to open a new revision if you don't intend to revert the original. The other option is to revert the change, fold this fix into the original patch (in this revision) and re-commit.

Thanks for pointing out the typical process for this situations.

[antondaubert]

In D125776#3817691, @CarlosAlbertoEnciso wrote:

In D125776#3817597, @antondaubert wrote:

The test seems to be failing, could you please take a look?

Errors are like:

IntervalTreeTest.cpp:41
Expected equality of these values:
  Item->left()
    Which is: 15
  Left
    Which is: 31

(and many other similar failures)

@antondaubert: From the buildbot: I can see only these type of errors:
https://lab.llvm.org/buildbot/#/builders/36/builds/25424

/home/buildbots/ppc64le-lld-multistage-test/ppc64le-lld-multistage-test/llvm-project/llvm/unittests/ADT/IntervalTreeTest.cpp:103:3: note: in instantiation of function template specialization 'testing::internal::EqHelper::Compare<unsigned long, int, nullptr>' requested here

ASSERT_EQ(Intervals.size(), 1);

It seems like the test is flaky in debug build, from 100 executions around 80 are failing. I wasn't able to reproduce the failure in release mode.

[CarlosAlbertoEnciso]

In D125776#3818010, @antondaubert wrote:

It seems like the test is flaky in debug build, from 100 executions around 80 are failing. I wasn't able to reproduce the failure in release mode.

The failure you get is from a particular buildbot? Or it is just a local debug build?
I will check a local debug build.

[antondaubert]

In D125776#3818041, @CarlosAlbertoEnciso wrote:

In D125776#3818010, @antondaubert wrote:

It seems like the test is flaky in debug build, from 100 executions around 80 are failing. I wasn't able to reproduce the failure in release mode.

The failure you get is from a particular buildbot? Or it is just a local debug build?
I will check a local debug build.

It is a local debug build.

[CarlosAlbertoEnciso]

In D125776#3818048, @antondaubert wrote:

In D125776#3818041, @CarlosAlbertoEnciso wrote:

In D125776#3818010, @antondaubert wrote:

It seems like the test is flaky in debug build, from 100 executions around 80 are failing. I wasn't able to reproduce the failure in release mode.

The failure you get is from a particular buildbot? Or it is just a local debug build?
I will check a local debug build.

It is a local debug build.

I will investigate it on a local debug build.
Can you provide me with more information on you local build environment:
CMake command line, platform, compiler, etc.

Thanks

[antondaubert]

In D125776#3818052, @CarlosAlbertoEnciso wrote:

I will investigate it on a local debug build.
Can you provide me with more information on you local build environment:
CMake command line, platform, compiler, etc.

Thanks

Our build setup is based on the internal version of bazel. As mentioned I was able to reproduce this failure in around 80% in debug build. Maybe it is related to the usage of std::sort. Consider looking into https://libcxx.llvm.org/DesignDocs/UnspecifiedBehaviorRandomization.html. We have _LIBCPP_DEBUG_RANDOMIZE_UNSPECIFIED_STABILITY enabled in our debug builds specifically to find this sort of a reliance on a specific ordering of partially ordered elements after std::sort.

[CarlosAlbertoEnciso]

@antondaubert: I tried a local debug build on both Windows/Linux and I was unable to reproduce any failure.

[antondaubert]

In D125776#3820456, @CarlosAlbertoEnciso wrote:

@antondaubert: I tried a local debug build on both Windows/Linux and I was unable to reproduce any failure.

Have you tried it using _LIBCPP_DEBUG_RANDOMIZE_UNSPECIFIED_STABILITY ?

[CarlosAlbertoEnciso]

In D125776#3820399, @antondaubert wrote:

In D125776#3818052, @CarlosAlbertoEnciso wrote:

I will investigate it on a local debug build.
Can you provide me with more information on you local build environment:
CMake command line, platform, compiler, etc.

Thanks

Our build setup is based on the internal version of bazel. As mentioned I was able to reproduce this failure in around 80% in debug build. Maybe it is related to the usage of std::sort. Consider looking into https://libcxx.llvm.org/DesignDocs/UnspecifiedBehaviorRandomization.html. We have _LIBCPP_DEBUG_RANDOMIZE_UNSPECIFIED_STABILITY enabled in our debug builds specifically to find this sort of a reliance on a specific ordering of partially ordered elements after std::sort.

Thanks for the notes about https://libcxx.llvm.org/DesignDocs/UnspecifiedBehaviorRandomization.html
Please, can I have more specific details on your build configuration options, so I can build with _LIBCPP_DEBUG_RANDOMIZE_UNSPECIFIED_STABILITY enabled.

In the meantime, I would suggest to replace std::sort with std::stable_sort in your llvm\include\llvm\ADT\IntervalTree.h version.

// 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();
            });
}

Thanks

[antondaubert]

@CarlosAlbertoEnciso using stable_sort within the method sortIntervals does the trick.

[CarlosAlbertoEnciso]

In D125776#3820563, @antondaubert wrote:

@CarlosAlbertoEnciso using stable_sort within the method sortIntervals does the trick.

Excellent. I will update a patch with that change. Thanks for your help.

[CarlosAlbertoEnciso]

In D125776#3820563, @antondaubert wrote:

@CarlosAlbertoEnciso using stable_sort within the method sortIntervals does the trick.

There are couple of more std::sort instances.

/// Create the interval tree.
void create() {
  ...
  std::sort(Points.begin(), Points.end());
  ...
}

static void sortIntervals(IntervalReferences &IntervalSet, Sorting Sort) {
  std::sort(IntervalSet.begin(), IntervalSet.end(),
  ...
}

Can you replace them as well. Thanks.

[antondaubert]

@CarlosAlbertoEnciso I replaced them as well. They did't had an effect. only the one within the method sortIntervals was relevant. So, if replacing all sort with stable_sort it was also not harmful.

[CarlosAlbertoEnciso]

In D125776#3820631, @antondaubert wrote:

@CarlosAlbertoEnciso I replaced them as well. They did't had an effect. only the one within the method sortIntervals was relevant. So, if replacing all sort with stable_sort it was also not harmful.

@antondaubert I have created a patch https://reviews.llvm.org/D134805

Once again, thanks very much for all your help.

llvm/docs/ProgrammersManual.rst

 IntervalMap is a compact map for small keys and values.  It maps key intervals
 instead of single keys, and it will automatically coalesce adjacent intervals.
 When the map only contains a few intervals, they are stored in the map object
 itself to avoid allocations.
 
 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:
 
 <map>
 ^^^^^
 
 std::map has similar characteristics to :ref:`std::set <dss_set>`: it uses a
 single allocation per pair inserted into the map, it offers log(n) lookup with
 an extremely large constant factor, imposes a space penalty of 3 pointers per

llvm/include/llvm/ADT/IntervalTree.h

+//===-- 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:
+//   PointT objects are mapped to ValueT objects.
+//
+// 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);
+//   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, 45] <- (4345),
+// [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--45  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.
+//
+// The following is the output from print():
+//
+// 0: MP:43 IR [10,85] [31,56] [36,54] [39,50] [43,45]
+// 0: MP:43 IL [10,85] [31,56] [36,54] [39,50] [43,45]
+// 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 ascending 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,45] [43,45]       |
+//                       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]
+//
+// 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 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 will all the intervals containing the target point.
+//
+// The returned intervals are in their natural tree location. They can
+// be sorted:
+//
+// 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 ranges 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) {}
+  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 contain(const PointType &Point) const {
+    return left(Point) && right(Point);
+  }
+};
+
+//===----------------------------------------------------------------------===//
+//---                          IntervalTree                               ----//
+//===----------------------------------------------------------------------===//
+template <typename PointT, typename ValueT,
+          typename DataT = IntervalData<PointT, ValueT>>
+class IntervalTree {
+public:
+  using PointType = PointT;
+  using ValueType = ValueT;
+  using DataType = DataT;
+  using Allocator = BumpPtrAllocator;
+
+  enum class Sorting { Ascending, Descending };
+  using IntervalReferences = SmallVector<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() { return MiddlePoint; }
+    unsigned start() { return BucketIntervalsStart; }
+    unsigned size() { 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.
+  void printList(raw_ostream &OS, IntervalReferences &IntervalSet,
+                 unsigned Start, unsigned Size, bool HexFormat = true) {
+    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 left.
+
+    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]->contain(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,
+                [](DataType *LHS, 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,
+                [](DataType *LHS, 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 std::iterator<std::forward_iterator_tag, DataType> {
+
+    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();
+    }
+
+  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 (Point <= Node->middle())
+                 ? (*AscendingBuckets)[Node->start() + Index]
+                 : (*DescendingBuckets)[Node->start() + Index];
+    }
+    const DataType &operator*() const {
+      return *(((Point <= Node->middle())
+                    ? ((*AscendingBuckets)[Node->start() + Index])
+                    : ((*DescendingBuckets)[Node->start() + Index])));
+    }
+
+    /// 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 {
+    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.
+  void sortIntervals(IntervalReferences &IntervalSet, Sorting Sort) const {
+    std::sort(IntervalSet.begin(), IntervalSet.end(),
+              [Sort](DataType *RHS, 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 (DataType &Data : Intervals) {
+      Points.push_back(Data.left());
+      Points.push_back(Data.right());
+      References.emplace_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

llvm/unittests/ADT/CMakeLists.txt

add_llvm_unittest(ADTTests
   IListNodeTest.cpp
   IListSentinelTest.cpp
   IListTest.cpp
   ImmutableListTest.cpp
   ImmutableMapTest.cpp
   ImmutableSetTest.cpp
   IntEqClassesTest.cpp
   IntervalMapTest.cpp
+  IntervalTreeTest.cpp
   IntrusiveRefCntPtrTest.cpp
   IteratorTest.cpp
   MappedIteratorTest.cpp
   MapVectorTest.cpp
   OptionalTest.cpp
   PackedVectorTest.cpp
   PointerEmbeddedIntTest.cpp
   PointerIntPairTest.cpp

llvm/unittests/ADT/IntervalTreeTest.cpp

+//===---- 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 <typename TPoint, typename TItem, typename TValue>
+void checkItem(TPoint Point, TItem Item, TPoint Left, TPoint Right,
+               TValue Value) {
+  EXPECT_TRUE(Item->contain(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<UUPoint, UUValue> {
+    using UUData = IntervalData<UUPoint, UUValue>;
+
+  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 contain(const PointType &Point) const {
+      return UUData::contain(Point);
+    }
+  };
+
+  using UUTree = IntervalTree<UUPoint, UUValue, MyData>;
+  using UUReferences = UUTree::IntervalReferences;
+  using UUData = UUTree::DataType;
+  using UUAlloc = UUTree::Allocator;
+
+  auto checkData = [](UUPoint Point, UUData *Data, UUPoint Left, UUPoint Right,
+                      UUValue Value) {
+    checkItem<UUPoint, UUData *, UUValue>(Point, Data, Left, Right, Value);
+  };
+
+  UUAlloc Allocator;
+  UUTree Tree(Allocator);
+  UUReferences Intervals;
+  UUPoint Point;
+
+  EXPECT_EQ(Tree.empty(), true);
+  Tree.clear();
+  EXPECT_EQ(Tree.empty(), true);
+
+  // [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_EQ(Intervals.empty(), true);
+
+  // Valid interval values: [10...20]
+  Point = 10;
+  Intervals = Tree.getContaining(Point);
+  ASSERT_TRUE(Intervals.size() == 1);
+  checkData(Point, Intervals[0], 10, 20, 10.20);
+
+  Point = 15;
+  Intervals = Tree.getContaining(Point);
+  ASSERT_TRUE(Intervals.size() == 1);
+  checkData(Point, Intervals[0], 10, 20, 10.20);
+
+  Point = 20;
+  Intervals = Tree.getContaining(Point);
+  ASSERT_TRUE(Intervals.size() == 1);
+  checkData(Point, Intervals[0], 10, 20, 10.20);
+
+  // Invalid interval values: 20] < x < [30
+  Point = 25;
+  Intervals = Tree.getContaining(Point);
+  EXPECT_EQ(Intervals.empty(), true);
+
+  // Valid interval values: [30...40]
+  Point = 30;
+  Intervals = Tree.getContaining(Point);
+  ASSERT_TRUE(Intervals.size() == 1);
+  checkData(Point, Intervals[0], 30, 40, 30.40);
+
+  Point = 35;
+  Intervals = Tree.getContaining(Point);
+  ASSERT_TRUE(Intervals.size() == 1);
+  checkData(Point, Intervals[0], 30, 40, 30.40);
+
+  Point = 40;
+  Intervals = Tree.getContaining(Point);
+  ASSERT_TRUE(Intervals.size() == 1);
+  checkData(Point, Intervals[0], 30, 40, 30.40);
+
+  // Invalid interval values: 40] < x
+  Point = 45;
+  Intervals = Tree.getContaining(Point);
+  EXPECT_EQ(Intervals.empty(), true);
+}
+
+using UUPoint = unsigned; // Interval range type.
+using UUValue = unsigned; // Mapped value type.
+
+using UUTree = IntervalTree<UUPoint, UUValue>;
+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, UUData *Data, UUPoint Left, UUPoint Right,
+               UUValue Value) {
+  checkItem<UUPoint, UUData *, UUValue>(Point, Data, Left, Right, Value);
+}
+
+void checkData(UUPoint Point, UUIter Iter, UUPoint Left, UUPoint Right,
+               UUValue Value) {
+  checkItem<UUPoint, UUIter, UUValue>(Point, Iter, Left, Right, Value);
+}
+
+// Empty tree tests.
+TEST(IntervalTreeTest, NoIntervals) {
+  UUAlloc Allocator;
+  UUTree Tree(Allocator);
+  EXPECT_EQ(Tree.empty(), true);
+  Tree.clear();
+  EXPECT_EQ(Tree.empty(), true);
+
+  // Create the tree and switch to query mode.
+  Tree.create();
+  EXPECT_EQ(Tree.empty(), true);
+  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_EQ(Tree.empty(), true);
+  Tree.create();
+  EXPECT_FALSE(Tree.empty());
+
+  // Invalid interval values: x < [10.
+  Point = 5;
+  Intervals = Tree.getContaining(Point);
+  EXPECT_EQ(Intervals.empty(), true);
+
+  // Valid interval values: [10...20].
+  Point = 10;
+  Intervals = Tree.getContaining(Point);
+  ASSERT_TRUE(Intervals.size() == 1);
+  checkData(Point, Intervals[0], 10, 20, 1020);
+
+  Point = 15;
+  Intervals = Tree.getContaining(Point);
+  ASSERT_TRUE(Intervals.size() == 1);
+  checkData(Point, Intervals[0], 10, 20, 1020);
+
+  Point = 20;
+  Intervals = Tree.getContaining(Point);
+  ASSERT_TRUE(Intervals.size() == 1);
+  checkData(Point, Intervals[0], 10, 20, 1020);
+
+  // Invalid interval values: 20] < x
+  Point = 25;
+  Intervals = Tree.getContaining(Point);
+  EXPECT_EQ(Intervals.empty(), true);
+}
+
+// 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_EQ(Intervals.empty(), true);
+
+  // Valid interval values: [10...20]
+  Point = 10;
+  Intervals = Tree.getContaining(Point);
+  ASSERT_TRUE(Intervals.size() == 1);
+  checkData(Point, Intervals[0], 10, 20, 1020);
+
+  Point = 15;
+  Intervals = Tree.getContaining(Point);
+  ASSERT_TRUE(Intervals.size() == 1);
+  checkData(Point, Intervals[0], 10, 20, 1020);
+
+  Point = 20;
+  Intervals = Tree.getContaining(Point);
+  ASSERT_TRUE(Intervals.size() == 1);
+  checkData(Point, Intervals[0], 10, 20, 1020);
+
+  // Invalid interval values: 20] < x < [30
+  Point = 25;
+  Intervals = Tree.getContaining(Point);
+  EXPECT_EQ(Intervals.empty(), true);
+
+  // Valid interval values: [30...40]
+  Point = 30;
+  Intervals = Tree.getContaining(Point);
+  ASSERT_TRUE(Intervals.size() == 1);
+  checkData(Point, Intervals[0], 30, 40, 3040);
+
+  Point = 35;
+  Intervals = Tree.getContaining(Point);
+  ASSERT_TRUE(Intervals.size() == 1);
+  checkData(Point, Intervals[0], 30, 40, 3040);
+
+  Point = 40;
+  Intervals = Tree.getContaining(Point);
+  ASSERT_TRUE(Intervals.size() == 1);
+  checkData(Point, Intervals[0], 30, 40, 3040);
+
+  // Invalid interval values: 40] < x
+  Point = 45;
+  Intervals = Tree.getContaining(Point);
+  EXPECT_EQ(Intervals.empty(), true);
+}
+
+// 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_EQ(Intervals.empty(), true);
+
+  // Valid interval values: [10...20]
+  Point = 10;
+  Intervals = Tree.getContaining(Point);
+  ASSERT_TRUE(Intervals.size() == 1);
+  checkData(Point, Intervals[0], 10, 20, 1020);
+
+  Point = 15;
+  Intervals = Tree.getContaining(Point);
+  ASSERT_TRUE(Intervals.size() == 1);
+  checkData(Point, Intervals[0], 10, 20, 1020);
+
+  Point = 20;
+  Intervals = Tree.getContaining(Point);
+  ASSERT_TRUE(Intervals.size() == 1);
+  checkData(Point, Intervals[0], 10, 20, 1020);
+
+  // Invalid interval values: 20] < x < [30
+  Point = 25;
+  Intervals = Tree.getContaining(Point);
+  EXPECT_EQ(Intervals.empty(), true);
+
+  // Valid interval values: [30...40]
+  Point = 30;
+  Intervals = Tree.getContaining(Point);
+  ASSERT_TRUE(Intervals.size() == 1);
+  checkData(Point, Intervals[0], 30, 40, 3040);
+
+  Point = 35;
+  Intervals = Tree.getContaining(Point);
+  ASSERT_TRUE(Intervals.size() == 1);
+  checkData(Point, Intervals[0], 30, 40, 3040);
+
+  Point = 40;
+  Intervals = Tree.getContaining(Point);
+  ASSERT_TRUE(Intervals.size() == 1);
+  checkData(Point, Intervals[0], 30, 40, 3040);
+
+  // Invalid interval values: 40] < x < [50
+  Point = 45;
+  Intervals = Tree.getContaining(Point);
+  EXPECT_EQ(Intervals.empty(), true);
+
+  // Valid interval values: [50...60]
+  Point = 50;
+  Intervals = Tree.getContaining(Point);
+  ASSERT_TRUE(Intervals.size() == 1);
+  checkData(Point, Intervals[0], 50, 60, 5060);
+
+  Point = 55;
+  Intervals = Tree.getContaining(Point);
+  ASSERT_TRUE(Intervals.size() == 1);
+  checkData(Point, Intervals[0], 50, 60, 5060);
+
+  Point = 60;
+  Intervals = Tree.getContaining(Point);
+  ASSERT_TRUE(Intervals.size() == 1);
+  checkData(Point, Intervals[0], 50, 60, 5060);
+
+  // Invalid interval values: 60] < x
+  Point = 65;
+  Intervals = Tree.getContaining(Point);
+  EXPECT_EQ(Intervals.empty(), true);
+}
+
+// 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_EQ(Intervals.empty(), true);
+
+  // Valid interval values:
+  Point = 10;
+  Intervals = Tree.getContaining(Point);
+  ASSERT_TRUE(Intervals.size() == 1);
+  checkData(Point, Intervals[0], 10, 90, 1090);
+
+  Point = 15;
+  Intervals = Tree.getContaining(Point);
+  ASSERT_TRUE(Intervals.size() == 1);
+  checkData(Point, Intervals[0], 10, 90, 1090);
+
+  Point = 20;
+  Intervals = Tree.getContaining(Point);
+  ASSERT_TRUE(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_TRUE(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_TRUE(Intervals.size() == 2);
+  checkData(Point, Intervals[0], 10, 90, 1090);
+  checkData(Point, Intervals[1], 20, 80, 2080);
+
+  Point = 25;
+  Intervals = Tree.getContaining(Point);
+  ASSERT_TRUE(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_TRUE(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_TRUE(Intervals.size() == 2);
+  checkData(Point, Intervals[0], 10, 90, 1090);
+  checkData(Point, Intervals[1], 20, 80, 2080);
+
+  Point = 30;
+  Intervals = Tree.getContaining(Point);
+  ASSERT_TRUE(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_TRUE(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_TRUE(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_TRUE(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_TRUE(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_TRUE(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_TRUE(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_TRUE(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_TRUE(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_TRUE(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_TRUE(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_TRUE(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_TRUE(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_TRUE(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_TRUE(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_TRUE(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_TRUE(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_TRUE(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_TRUE(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_TRUE(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_TRUE(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_TRUE(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_TRUE(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_TRUE(Intervals.size() == 2);
+  checkData(Point, Intervals[0], 10, 90, 1090);
+  checkData(Point, Intervals[1], 20, 80, 2080);
+
+  Point = 80;
+  Intervals = Tree.getContaining(Point);
+  ASSERT_TRUE(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_TRUE(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_TRUE(Intervals.size() == 2);
+  checkData(Point, Intervals[0], 10, 90, 1090);
+  checkData(Point, Intervals[1], 20, 80, 2080);
+
+  Point = 85;
+  Intervals = Tree.getContaining(Point);
+  ASSERT_TRUE(Intervals.size() == 1);
+  checkData(Point, Intervals[0], 10, 90, 1090);
+
+  Point = 90;
+  Intervals = Tree.getContaining(Point);
+  ASSERT_TRUE(Intervals.size() == 1);
+  checkData(Point, Intervals[0], 10, 90, 1090);
+
+  // Invalid interval values: 90] < x
+  Point = 95;
+  Intervals = Tree.getContaining(Point);
+  EXPECT_EQ(Intervals.empty(), true);
+}
+
+// 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_TRUE(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_TRUE(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_TRUE(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_TRUE(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_TRUE(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_TRUE(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_TRUE(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_TRUE(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_TRUE(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_TRUE(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_TRUE(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_TRUE(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_TRUE(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_TRUE(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_TRUE(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_TRUE(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_TRUE(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_TRUE(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_TRUE(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_TRUE(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_TRUE(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_TRUE(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_TRUE(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_TRUE(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_TRUE(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_TRUE(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_TRUE(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_TRUE(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_TRUE(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_TRUE(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_TRUE(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_TRUE(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_TRUE(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_TRUE(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_TRUE(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_TRUE(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_TRUE(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_TRUE(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_TRUE(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_TRUE(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_TRUE(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_TRUE(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_TRUE(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_TRUE(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_TRUE(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_TRUE(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_TRUE(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_TRUE(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_TRUE(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_TRUE(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_TRUE(Intervals.size() == 2);
+  checkData(Point, Intervals[0], 10, 85, 1085);
+  checkData(Point, Intervals[1], 11, 16, 1116);
+
+  Point = 16;
+  Intervals = Tree.getContaining(Point);
+  ASSERT_TRUE(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_TRUE(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_TRUE(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_TRUE(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_TRUE(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_TRUE(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_TRUE(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_TRUE(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_TRUE(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_TRUE(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_TRUE(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_TRUE(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_TRUE(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_TRUE(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_TRUE(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_TRUE(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_TRUE(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_TRUE(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_TRUE(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_TRUE(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_TRUE(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_TRUE(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_TRUE(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_TRUE(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_TRUE(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_TRUE(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_TRUE(Intervals.size() == 2);
+  checkData(Point, Intervals[0], 10, 85, 1085);
+  checkData(Point, Intervals[1], 74, 80, 7480);
+
+  Point = 15;
+  Intervals = Tree.getContaining(Point);
+  ASSERT_TRUE(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_TRUE(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_TRUE(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_TRUE(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_TRUE(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_TRUE(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_TRUE(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_TRUE(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_TRUE(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_TRUE(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_TRUE(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_TRUE(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_TRUE(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_TRUE(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_TRUE(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_TRUE(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_TRUE(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_TRUE(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_TRUE(Intervals.size() == 1);
+  checkData(Point, Intervals[0], 10, 85, 1085);
+
+  Point = 85;
+  Intervals = Tree.getContaining(Point);
+  ASSERT_TRUE(Intervals.size() == 1);
+  checkData(Point, Intervals[0], 10, 85, 1085);
+
+  // Invalid interval values.
+  Point = 5;
+  Intervals = Tree.getContaining(Point);
+  EXPECT_EQ(Intervals.empty(), true);
+  Point = 90;
+  Intervals = Tree.getContaining(Point);
+  EXPECT_EQ(Intervals.empty(), true);
+}
+
+// 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