llvm/unittests/ADT/IntervalTreeTest.cpp

   1 //===---- ADT/IntervalTreeTest.cpp - IntervalTree unit tests --------------===//
   2 //
   3 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
   4 // See https://llvm.org/LICENSE.txt for license information.
   5 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
   6 //
   7 //===----------------------------------------------------------------------===//
   8
   9 #include "llvm/ADT/IntervalTree.h"
  10 #include "gtest/gtest.h"
  11
  12 // The test cases for the IntervalTree implementation, follow the below steps:
  13 // a) Insert a series of intervals with their associated mapped value.
  14 // b) Create the interval tree.
  15 // c) Query for specific interval point, covering points inside and outside
  16 //    of any given intervals.
  17 // d) Traversal for specific interval point, using the iterators.
  18 //
  19 // When querying for a set of intervals containing a given value, the query is
  20 // done three times, by calling:
  21 // 1) Intervals = getContaining(...).
  22 // 2) Intervals = getContaining(...).
  23 //    sortIntervals(Intervals, Sorting=Ascending).
  24 // 3) Intervals = getContaining(...).
  25 //    sortIntervals(Intervals, Sorting=Ascending).
  26 //
  27 // The returned intervals are:
  28 // 1) In their location order within the tree.
  29 // 2) Smaller intervals first.
  30 // 3) Bigger intervals first.
  31
  32 using namespace llvm;
  33
  34 namespace {
  35
  36 // Helper function to test a specific item or iterator.
  37 template <typename TPoint, typename TItem, typename TValue>
  38 void checkItem(TPoint Point, TItem Item, TPoint Left, TPoint Right,
  39                TValue Value) {
  40   EXPECT_TRUE(Item->contains(Point));
  41   EXPECT_EQ(Item->left(), Left);
  42   EXPECT_EQ(Item->right(), Right);
  43   EXPECT_EQ(Item->value(), Value);
  44 }
  45
  46 // User class tree tests.
  47 TEST(IntervalTreeTest, UserClass) {
  48   using UUPoint = unsigned;
  49   using UUValue = double;
  50   class MyData : public IntervalData<UUPoint, UUValue> {
  51     using UUData = IntervalData<UUPoint, UUValue>;
  52
  53   public:
  54     // Inherit Base's constructors.
  55     using UUData::UUData;
  56     PointType left() const { return UUData::left(); }
  57     PointType right() const { return UUData::right(); }
  58     ValueType value() const { return UUData::value(); }
  59
  60     bool left(const PointType &Point) const { return UUData::left(Point); }
  61     bool right(const PointType &Point) const { return UUData::right(Point); }
  62     bool contains(const PointType &Point) const {
  63       return UUData::contains(Point);
  64     }
  65   };
  66
  67   using UUTree = IntervalTree<UUPoint, UUValue, MyData>;
  68   using UUReferences = UUTree::IntervalReferences;
  69   using UUData = UUTree::DataType;
  70   using UUAlloc = UUTree::Allocator;
  71
  72   auto CheckData = [](UUPoint Point, const UUData *Data, UUPoint Left,
  73                       UUPoint Right, UUValue Value) {
  74     checkItem<UUPoint, const UUData *, UUValue>(Point, Data, Left, Right,
  75                                                 Value);
  76   };
  77
  78   UUAlloc Allocator;
  79   UUTree Tree(Allocator);
  80   UUReferences Intervals;
  81   UUPoint Point;
  82
  83   EXPECT_TRUE(Tree.empty());
  84   Tree.clear();
  85   EXPECT_TRUE(Tree.empty());
  86
  87   // [10, 20] <- (10.20)
  88   // [30, 40] <- (30.40)
  89   //
  90   //    [10...20]   [30...40]
  91   Tree.insert(10, 20, 10.20);
  92   Tree.insert(30, 40, 30.40);
  93   Tree.create();
  94
  95   // Invalid interval values: x < [10
  96   Point = 5;
  97   Intervals = Tree.getContaining(Point);
  98   EXPECT_TRUE(Intervals.empty());
  99
 100   // Valid interval values: [10...20]
 101   Point = 10;
 102   Intervals = Tree.getContaining(Point);
 103   ASSERT_EQ(Intervals.size(), 1u);
 104   CheckData(Point, Intervals[0], 10, 20, 10.20);
 105
 106   Point = 15;
 107   Intervals = Tree.getContaining(Point);
 108   ASSERT_EQ(Intervals.size(), 1u);
 109   CheckData(Point, Intervals[0], 10, 20, 10.20);
 110
 111   Point = 20;
 112   Intervals = Tree.getContaining(Point);
 113   ASSERT_EQ(Intervals.size(), 1u);
 114   CheckData(Point, Intervals[0], 10, 20, 10.20);
 115
 116   // Invalid interval values: 20] < x < [30
 117   Point = 25;
 118   Intervals = Tree.getContaining(Point);
 119   EXPECT_TRUE(Intervals.empty());
 120
 121   // Valid interval values: [30...40]
 122   Point = 30;
 123   Intervals = Tree.getContaining(Point);
 124   ASSERT_EQ(Intervals.size(), 1u);
 125   CheckData(Point, Intervals[0], 30, 40, 30.40);
 126
 127   Point = 35;
 128   Intervals = Tree.getContaining(Point);
 129   ASSERT_EQ(Intervals.size(), 1u);
 130   CheckData(Point, Intervals[0], 30, 40, 30.40);
 131
 132   Point = 40;
 133   Intervals = Tree.getContaining(Point);
 134   ASSERT_EQ(Intervals.size(), 1u);
 135   CheckData(Point, Intervals[0], 30, 40, 30.40);
 136
 137   // Invalid interval values: 40] < x
 138   Point = 45;
 139   Intervals = Tree.getContaining(Point);
 140   EXPECT_TRUE(Intervals.empty());
 141 }
 142
 143 using UUPoint = unsigned; // Interval endpoint type.
 144 using UUValue = unsigned; // Mapped value type.
 145
 146 using UUTree = IntervalTree<UUPoint, UUValue>;
 147 using UUReferences = UUTree::IntervalReferences;
 148 using UUData = UUTree::DataType;
 149 using UUSorting = UUTree::Sorting;
 150 using UUPoint = UUTree::PointType;
 151 using UUValue = UUTree::ValueType;
 152 using UUIter = UUTree::find_iterator;
 153 using UUAlloc = UUTree::Allocator;
 154
 155 void checkData(UUPoint Point, const UUData *Data, UUPoint Left, UUPoint Right,
 156                UUValue Value) {
 157   checkItem<UUPoint, const UUData *, UUValue>(Point, Data, Left, Right, Value);
 158 }
 159
 160 void checkData(UUPoint Point, UUIter Iter, UUPoint Left, UUPoint Right,
 161                UUValue Value) {
 162   checkItem<UUPoint, UUIter, UUValue>(Point, Iter, Left, Right, Value);
 163 }
 164
 165 // Empty tree tests.
 166 TEST(IntervalTreeTest, NoIntervals) {
 167   UUAlloc Allocator;
 168   UUTree Tree(Allocator);
 169   EXPECT_TRUE(Tree.empty());
 170   Tree.clear();
 171   EXPECT_TRUE(Tree.empty());
 172
 173   // Create the tree and switch to query mode.
 174   Tree.create();
 175   EXPECT_TRUE(Tree.empty());
 176   EXPECT_EQ(Tree.find(1), Tree.find_end());
 177 }
 178
 179 // One item tree tests.
 180 TEST(IntervalTreeTest, OneInterval) {
 181   UUAlloc Allocator;
 182   UUTree Tree(Allocator);
 183   UUReferences Intervals;
 184   UUPoint Point;
 185
 186   // [10, 20] <- (1020)
 187   //
 188   //    [10...20]
 189   Tree.insert(10, 20, 1020);
 190
 191   EXPECT_TRUE(Tree.empty());
 192   Tree.create();
 193   EXPECT_FALSE(Tree.empty());
 194
 195   // Invalid interval values: x < [10.
 196   Point = 5;
 197   Intervals = Tree.getContaining(Point);
 198   EXPECT_TRUE(Intervals.empty());
 199
 200   // Valid interval values: [10...20].
 201   Point = 10;
 202   Intervals = Tree.getContaining(Point);
 203   ASSERT_EQ(Intervals.size(), 1u);
 204   checkData(Point, Intervals[0], 10, 20, 1020);
 205
 206   Point = 15;
 207   Intervals = Tree.getContaining(Point);
 208   ASSERT_EQ(Intervals.size(), 1u);
 209   checkData(Point, Intervals[0], 10, 20, 1020);
 210
 211   Point = 20;
 212   Intervals = Tree.getContaining(Point);
 213   ASSERT_EQ(Intervals.size(), 1u);
 214   checkData(Point, Intervals[0], 10, 20, 1020);
 215
 216   // Invalid interval values: 20] < x
 217   Point = 25;
 218   Intervals = Tree.getContaining(Point);
 219   EXPECT_TRUE(Intervals.empty());
 220 }
 221
 222 // Two items tree tests. No overlapping.
 223 TEST(IntervalTreeTest, TwoIntervals) {
 224   UUAlloc Allocator;
 225   UUTree Tree(Allocator);
 226   UUReferences Intervals;
 227   UUPoint Point;
 228
 229   // [10, 20] <- (1020)
 230   // [30, 40] <- (3040)
 231   //
 232   //    [10...20]   [30...40]
 233   Tree.insert(10, 20, 1020);
 234   Tree.insert(30, 40, 3040);
 235   Tree.create();
 236
 237   // Invalid interval values: x < [10
 238   Point = 5;
 239   Intervals = Tree.getContaining(Point);
 240   EXPECT_TRUE(Intervals.empty());
 241
 242   // Valid interval values: [10...20]
 243   Point = 10;
 244   Intervals = Tree.getContaining(Point);
 245   ASSERT_EQ(Intervals.size(), 1u);
 246   checkData(Point, Intervals[0], 10, 20, 1020);
 247
 248   Point = 15;
 249   Intervals = Tree.getContaining(Point);
 250   ASSERT_EQ(Intervals.size(), 1u);
 251   checkData(Point, Intervals[0], 10, 20, 1020);
 252
 253   Point = 20;
 254   Intervals = Tree.getContaining(Point);
 255   ASSERT_EQ(Intervals.size(), 1u);
 256   checkData(Point, Intervals[0], 10, 20, 1020);
 257
 258   // Invalid interval values: 20] < x < [30
 259   Point = 25;
 260   Intervals = Tree.getContaining(Point);
 261   EXPECT_TRUE(Intervals.empty());
 262
 263   // Valid interval values: [30...40]
 264   Point = 30;
 265   Intervals = Tree.getContaining(Point);
 266   ASSERT_EQ(Intervals.size(), 1u);
 267   checkData(Point, Intervals[0], 30, 40, 3040);
 268
 269   Point = 35;
 270   Intervals = Tree.getContaining(Point);
 271   ASSERT_EQ(Intervals.size(), 1u);
 272   checkData(Point, Intervals[0], 30, 40, 3040);
 273
 274   Point = 40;
 275   Intervals = Tree.getContaining(Point);
 276   ASSERT_EQ(Intervals.size(), 1u);
 277   checkData(Point, Intervals[0], 30, 40, 3040);
 278
 279   // Invalid interval values: 40] < x
 280   Point = 45;
 281   Intervals = Tree.getContaining(Point);
 282   EXPECT_TRUE(Intervals.empty());
 283 }
 284
 285 // Three items tree tests. No overlapping.
 286 TEST(IntervalTreeTest, ThreeIntervals) {
 287   UUAlloc Allocator;
 288   UUTree Tree(Allocator);
 289   UUReferences Intervals;
 290   UUPoint Point;
 291
 292   // [10, 20] <- (1020)
 293   // [30, 40] <- (3040)
 294   // [50, 60] <- (5060)
 295   //
 296   //    [10...20]   [30...40]   [50...60]
 297   Tree.insert(10, 20, 1020);
 298   Tree.insert(30, 40, 3040);
 299   Tree.insert(50, 60, 5060);
 300   Tree.create();
 301
 302   // Invalid interval values: x < [10
 303   Point = 5;
 304   Intervals = Tree.getContaining(Point);
 305   EXPECT_TRUE(Intervals.empty());
 306
 307   // Valid interval values: [10...20]
 308   Point = 10;
 309   Intervals = Tree.getContaining(Point);
 310   ASSERT_EQ(Intervals.size(), 1u);
 311   checkData(Point, Intervals[0], 10, 20, 1020);
 312
 313   Point = 15;
 314   Intervals = Tree.getContaining(Point);
 315   ASSERT_EQ(Intervals.size(), 1u);
 316   checkData(Point, Intervals[0], 10, 20, 1020);
 317
 318   Point = 20;
 319   Intervals = Tree.getContaining(Point);
 320   ASSERT_EQ(Intervals.size(), 1u);
 321   checkData(Point, Intervals[0], 10, 20, 1020);
 322
 323   // Invalid interval values: 20] < x < [30
 324   Point = 25;
 325   Intervals = Tree.getContaining(Point);
 326   EXPECT_TRUE(Intervals.empty());
 327
 328   // Valid interval values: [30...40]
 329   Point = 30;
 330   Intervals = Tree.getContaining(Point);
 331   ASSERT_EQ(Intervals.size(), 1u);
 332   checkData(Point, Intervals[0], 30, 40, 3040);
 333
 334   Point = 35;
 335   Intervals = Tree.getContaining(Point);
 336   ASSERT_EQ(Intervals.size(), 1u);
 337   checkData(Point, Intervals[0], 30, 40, 3040);
 338
 339   Point = 40;
 340   Intervals = Tree.getContaining(Point);
 341   ASSERT_EQ(Intervals.size(), 1u);
 342   checkData(Point, Intervals[0], 30, 40, 3040);
 343
 344   // Invalid interval values: 40] < x < [50
 345   Point = 45;
 346   Intervals = Tree.getContaining(Point);
 347   EXPECT_TRUE(Intervals.empty());
 348
 349   // Valid interval values: [50...60]
 350   Point = 50;
 351   Intervals = Tree.getContaining(Point);
 352   ASSERT_EQ(Intervals.size(), 1u);
 353   checkData(Point, Intervals[0], 50, 60, 5060);
 354
 355   Point = 55;
 356   Intervals = Tree.getContaining(Point);
 357   ASSERT_EQ(Intervals.size(), 1u);
 358   checkData(Point, Intervals[0], 50, 60, 5060);
 359
 360   Point = 60;
 361   Intervals = Tree.getContaining(Point);
 362   ASSERT_EQ(Intervals.size(), 1u);
 363   checkData(Point, Intervals[0], 50, 60, 5060);
 364
 365   // Invalid interval values: 60] < x
 366   Point = 65;
 367   Intervals = Tree.getContaining(Point);
 368   EXPECT_TRUE(Intervals.empty());
 369 }
 370
 371 // One item tree tests.
 372 TEST(IntervalTreeTest, EmptyIntervals) {
 373   UUAlloc Allocator;
 374   UUTree Tree(Allocator);
 375   UUReferences Intervals;
 376   UUPoint Point;
 377
 378   // [40, 60] <- (4060)
 379   // [50, 50] <- (5050)
 380   // [10, 10] <- (1010)
 381   // [70, 70] <- (7070)
 382   //
 383   //                [40...............60]
 384   //                      [50...50]
 385   //    [10...10]
 386   //                                        [70...70]
 387   Tree.insert(40, 60, 4060);
 388   Tree.insert(50, 50, 5050);
 389   Tree.insert(10, 10, 1010);
 390   Tree.insert(70, 70, 7070);
 391
 392   EXPECT_TRUE(Tree.empty());
 393   Tree.create();
 394   EXPECT_FALSE(Tree.empty());
 395
 396   // Invalid interval values: x < [10.
 397   Point = 5;
 398   Intervals = Tree.getContaining(Point);
 399   EXPECT_TRUE(Intervals.empty());
 400
 401   // Valid interval values: [10...10].
 402   Point = 10;
 403   Intervals = Tree.getContaining(Point);
 404   ASSERT_EQ(Intervals.size(), 1u);
 405   checkData(Point, Intervals[0], 10, 10, 1010);
 406
 407   // Invalid interval values: 10] < x
 408   Point = 15;
 409   Intervals = Tree.getContaining(Point);
 410   EXPECT_TRUE(Intervals.empty());
 411
 412   // Invalid interval values: x < [50.
 413   Point = 45;
 414   Intervals = Tree.getContaining(Point);
 415   ASSERT_EQ(Intervals.size(), 1u);
 416   checkData(Point, Intervals[0], 40, 60, 4060);
 417
 418   // Valid interval values: [50...50].
 419   Point = 50;
 420   Intervals = Tree.getContaining(Point);
 421   ASSERT_EQ(Intervals.size(), 2u);
 422   checkData(Point, Intervals[0], 40, 60, 4060);
 423   checkData(Point, Intervals[1], 50, 50, 5050);
 424
 425   // Invalid interval values: 50] < x
 426   Point = 55;
 427   Intervals = Tree.getContaining(Point);
 428   ASSERT_EQ(Intervals.size(), 1u);
 429   checkData(Point, Intervals[0], 40, 60, 4060);
 430
 431   // Invalid interval values: x < [70.
 432   Point = 65;
 433   Intervals = Tree.getContaining(Point);
 434   EXPECT_TRUE(Intervals.empty());
 435
 436   // Valid interval values: [70...70].
 437   Point = 70;
 438   Intervals = Tree.getContaining(Point);
 439   ASSERT_EQ(Intervals.size(), 1u);
 440   checkData(Point, Intervals[0], 70, 70, 7070);
 441
 442   // Invalid interval values: 70] < x
 443   Point = 75;
 444   Intervals = Tree.getContaining(Point);
 445   EXPECT_TRUE(Intervals.empty());
 446 }
 447
 448 // Simple overlapping tests.
 449 TEST(IntervalTreeTest, SimpleIntervalsOverlapping) {
 450   UUAlloc Allocator;
 451   UUTree Tree(Allocator);
 452   UUReferences Intervals;
 453   UUPoint Point;
 454
 455   // [40, 60] <- (4060)
 456   // [30, 70] <- (3070)
 457   // [20, 80] <- (2080)
 458   // [10, 90] <- (1090)
 459   //
 460   //                      [40...60]
 461   //                [30...............70]
 462   //          [20...........................80]
 463   //    [10.......................................90]
 464   Tree.insert(40, 60, 4060);
 465   Tree.insert(30, 70, 3070);
 466   Tree.insert(20, 80, 2080);
 467   Tree.insert(10, 90, 1090);
 468   Tree.create();
 469
 470   // Invalid interval values: x < [10
 471   Point = 5;
 472   Intervals = Tree.getContaining(Point);
 473   EXPECT_TRUE(Intervals.empty());
 474
 475   // Valid interval values:
 476   Point = 10;
 477   Intervals = Tree.getContaining(Point);
 478   ASSERT_EQ(Intervals.size(), 1u);
 479   checkData(Point, Intervals[0], 10, 90, 1090);
 480
 481   Point = 15;
 482   Intervals = Tree.getContaining(Point);
 483   ASSERT_EQ(Intervals.size(), 1u);
 484   checkData(Point, Intervals[0], 10, 90, 1090);
 485
 486   Point = 20;
 487   Intervals = Tree.getContaining(Point);
 488   ASSERT_EQ(Intervals.size(), 2u);
 489   checkData(Point, Intervals[0], 10, 90, 1090);
 490   checkData(Point, Intervals[1], 20, 80, 2080);
 491   Intervals = Tree.getContaining(Point);
 492   Tree.sortIntervals(Intervals, UUSorting::Ascending);
 493   ASSERT_EQ(Intervals.size(), 2u);
 494   checkData(Point, Intervals[0], 20, 80, 2080);
 495   checkData(Point, Intervals[1], 10, 90, 1090);
 496   Intervals = Tree.getContaining(Point);
 497   Tree.sortIntervals(Intervals, UUSorting::Descending);
 498   ASSERT_EQ(Intervals.size(), 2u);
 499   checkData(Point, Intervals[0], 10, 90, 1090);
 500   checkData(Point, Intervals[1], 20, 80, 2080);
 501
 502   Point = 25;
 503   Intervals = Tree.getContaining(Point);
 504   ASSERT_EQ(Intervals.size(), 2u);
 505   checkData(Point, Intervals[0], 10, 90, 1090);
 506   checkData(Point, Intervals[1], 20, 80, 2080);
 507   Intervals = Tree.getContaining(Point);
 508   Tree.sortIntervals(Intervals, UUSorting::Ascending);
 509   ASSERT_EQ(Intervals.size(), 2u);
 510   checkData(Point, Intervals[0], 20, 80, 2080);
 511   checkData(Point, Intervals[1], 10, 90, 1090);
 512   Intervals = Tree.getContaining(Point);
 513   Tree.sortIntervals(Intervals, UUSorting::Descending);
 514   ASSERT_EQ(Intervals.size(), 2u);
 515   checkData(Point, Intervals[0], 10, 90, 1090);
 516   checkData(Point, Intervals[1], 20, 80, 2080);
 517
 518   Point = 30;
 519   Intervals = Tree.getContaining(Point);
 520   ASSERT_EQ(Intervals.size(), 3u);
 521   checkData(Point, Intervals[0], 10, 90, 1090);
 522   checkData(Point, Intervals[1], 20, 80, 2080);
 523   checkData(Point, Intervals[2], 30, 70, 3070);
 524   Intervals = Tree.getContaining(Point);
 525   Tree.sortIntervals(Intervals, UUSorting::Ascending);
 526   ASSERT_EQ(Intervals.size(), 3u);
 527   checkData(Point, Intervals[0], 30, 70, 3070);
 528   checkData(Point, Intervals[1], 20, 80, 2080);
 529   checkData(Point, Intervals[2], 10, 90, 1090);
 530   Intervals = Tree.getContaining(Point);
 531   Tree.sortIntervals(Intervals, UUSorting::Descending);
 532   ASSERT_EQ(Intervals.size(), 3u);
 533   checkData(Point, Intervals[0], 10, 90, 1090);
 534   checkData(Point, Intervals[1], 20, 80, 2080);
 535   checkData(Point, Intervals[2], 30, 70, 3070);
 536
 537   Point = 35;
 538   Intervals = Tree.getContaining(Point);
 539   ASSERT_EQ(Intervals.size(), 3u);
 540   checkData(Point, Intervals[0], 10, 90, 1090);
 541   checkData(Point, Intervals[1], 20, 80, 2080);
 542   checkData(Point, Intervals[2], 30, 70, 3070);
 543   Intervals = Tree.getContaining(Point);
 544   Tree.sortIntervals(Intervals, UUSorting::Ascending);
 545   ASSERT_EQ(Intervals.size(), 3u);
 546   checkData(Point, Intervals[0], 30, 70, 3070);
 547   checkData(Point, Intervals[1], 20, 80, 2080);
 548   checkData(Point, Intervals[2], 10, 90, 1090);
 549   Intervals = Tree.getContaining(Point);
 550   Tree.sortIntervals(Intervals, UUSorting::Descending);
 551   ASSERT_EQ(Intervals.size(), 3u);
 552   checkData(Point, Intervals[0], 10, 90, 1090);
 553   checkData(Point, Intervals[1], 20, 80, 2080);
 554   checkData(Point, Intervals[2], 30, 70, 3070);
 555
 556   Point = 40;
 557   Intervals = Tree.getContaining(Point);
 558   ASSERT_EQ(Intervals.size(), 4u);
 559   checkData(Point, Intervals[0], 10, 90, 1090);
 560   checkData(Point, Intervals[1], 20, 80, 2080);
 561   checkData(Point, Intervals[2], 30, 70, 3070);
 562   checkData(Point, Intervals[3], 40, 60, 4060);
 563   Intervals = Tree.getContaining(Point);
 564   Tree.sortIntervals(Intervals, UUSorting::Ascending);
 565   ASSERT_EQ(Intervals.size(), 4u);
 566   checkData(Point, Intervals[0], 40, 60, 4060);
 567   checkData(Point, Intervals[1], 30, 70, 3070);
 568   checkData(Point, Intervals[2], 20, 80, 2080);
 569   checkData(Point, Intervals[3], 10, 90, 1090);
 570   Intervals = Tree.getContaining(Point);
 571   Tree.sortIntervals(Intervals, UUSorting::Descending);
 572   ASSERT_EQ(Intervals.size(), 4u);
 573   checkData(Point, Intervals[0], 10, 90, 1090);
 574   checkData(Point, Intervals[1], 20, 80, 2080);
 575   checkData(Point, Intervals[2], 30, 70, 3070);
 576   checkData(Point, Intervals[3], 40, 60, 4060);
 577
 578   Point = 50;
 579   Intervals = Tree.getContaining(Point);
 580   ASSERT_EQ(Intervals.size(), 4u);
 581   checkData(Point, Intervals[0], 10, 90, 1090);
 582   checkData(Point, Intervals[1], 20, 80, 2080);
 583   checkData(Point, Intervals[2], 30, 70, 3070);
 584   checkData(Point, Intervals[3], 40, 60, 4060);
 585   Intervals = Tree.getContaining(Point);
 586   Tree.sortIntervals(Intervals, UUSorting::Ascending);
 587   ASSERT_EQ(Intervals.size(), 4u);
 588   checkData(Point, Intervals[0], 40, 60, 4060);
 589   checkData(Point, Intervals[1], 30, 70, 3070);
 590   checkData(Point, Intervals[2], 20, 80, 2080);
 591   checkData(Point, Intervals[3], 10, 90, 1090);
 592   Intervals = Tree.getContaining(Point);
 593   Tree.sortIntervals(Intervals, UUSorting::Descending);
 594   ASSERT_EQ(Intervals.size(), 4u);
 595   checkData(Point, Intervals[0], 10, 90, 1090);
 596   checkData(Point, Intervals[1], 20, 80, 2080);
 597   checkData(Point, Intervals[2], 30, 70, 3070);
 598   checkData(Point, Intervals[3], 40, 60, 4060);
 599
 600   Point = 60;
 601   Intervals = Tree.getContaining(Point);
 602   ASSERT_EQ(Intervals.size(), 4u);
 603   checkData(Point, Intervals[0], 10, 90, 1090);
 604   checkData(Point, Intervals[1], 20, 80, 2080);
 605   checkData(Point, Intervals[2], 30, 70, 3070);
 606   checkData(Point, Intervals[3], 40, 60, 4060);
 607   Intervals = Tree.getContaining(Point);
 608   Tree.sortIntervals(Intervals, UUSorting::Ascending);
 609   ASSERT_EQ(Intervals.size(), 4u);
 610   checkData(Point, Intervals[0], 40, 60, 4060);
 611   checkData(Point, Intervals[1], 30, 70, 3070);
 612   checkData(Point, Intervals[2], 20, 80, 2080);
 613   checkData(Point, Intervals[3], 10, 90, 1090);
 614   Intervals = Tree.getContaining(Point);
 615   Tree.sortIntervals(Intervals, UUSorting::Descending);
 616   ASSERT_EQ(Intervals.size(), 4u);
 617   checkData(Point, Intervals[0], 10, 90, 1090);
 618   checkData(Point, Intervals[1], 20, 80, 2080);
 619   checkData(Point, Intervals[2], 30, 70, 3070);
 620   checkData(Point, Intervals[3], 40, 60, 4060);
 621
 622   Point = 65;
 623   Intervals = Tree.getContaining(Point);
 624   ASSERT_EQ(Intervals.size(), 3u);
 625   checkData(Point, Intervals[0], 10, 90, 1090);
 626   checkData(Point, Intervals[1], 20, 80, 2080);
 627   checkData(Point, Intervals[2], 30, 70, 3070);
 628   Intervals = Tree.getContaining(Point);
 629   Tree.sortIntervals(Intervals, UUSorting::Ascending);
 630   ASSERT_EQ(Intervals.size(), 3u);
 631   checkData(Point, Intervals[0], 30, 70, 3070);
 632   checkData(Point, Intervals[1], 20, 80, 2080);
 633   checkData(Point, Intervals[2], 10, 90, 1090);
 634   Intervals = Tree.getContaining(Point);
 635   Tree.sortIntervals(Intervals, UUSorting::Descending);
 636   ASSERT_EQ(Intervals.size(), 3u);
 637   checkData(Point, Intervals[0], 10, 90, 1090);
 638   checkData(Point, Intervals[1], 20, 80, 2080);
 639   checkData(Point, Intervals[2], 30, 70, 3070);
 640
 641   Point = 70;
 642   Intervals = Tree.getContaining(Point);
 643   ASSERT_EQ(Intervals.size(), 3u);
 644   checkData(Point, Intervals[0], 10, 90, 1090);
 645   checkData(Point, Intervals[1], 20, 80, 2080);
 646   checkData(Point, Intervals[2], 30, 70, 3070);
 647   Intervals = Tree.getContaining(Point);
 648   Tree.sortIntervals(Intervals, UUSorting::Ascending);
 649   ASSERT_EQ(Intervals.size(), 3u);
 650   checkData(Point, Intervals[0], 30, 70, 3070);
 651   checkData(Point, Intervals[1], 20, 80, 2080);
 652   checkData(Point, Intervals[2], 10, 90, 1090);
 653   Intervals = Tree.getContaining(Point);
 654   Tree.sortIntervals(Intervals, UUSorting::Descending);
 655   ASSERT_EQ(Intervals.size(), 3u);
 656   checkData(Point, Intervals[0], 10, 90, 1090);
 657   checkData(Point, Intervals[1], 20, 80, 2080);
 658   checkData(Point, Intervals[2], 30, 70, 3070);
 659
 660   Point = 75;
 661   Intervals = Tree.getContaining(Point);
 662   ASSERT_EQ(Intervals.size(), 2u);
 663   checkData(Point, Intervals[0], 10, 90, 1090);
 664   checkData(Point, Intervals[1], 20, 80, 2080);
 665   Intervals = Tree.getContaining(Point);
 666   Tree.sortIntervals(Intervals, UUSorting::Ascending);
 667   ASSERT_EQ(Intervals.size(), 2u);
 668   checkData(Point, Intervals[0], 20, 80, 2080);
 669   checkData(Point, Intervals[1], 10, 90, 1090);
 670   Intervals = Tree.getContaining(Point);
 671   Tree.sortIntervals(Intervals, UUSorting::Descending);
 672   ASSERT_EQ(Intervals.size(), 2u);
 673   checkData(Point, Intervals[0], 10, 90, 1090);
 674   checkData(Point, Intervals[1], 20, 80, 2080);
 675
 676   Point = 80;
 677   Intervals = Tree.getContaining(Point);
 678   ASSERT_EQ(Intervals.size(), 2u);
 679   checkData(Point, Intervals[0], 10, 90, 1090);
 680   checkData(Point, Intervals[1], 20, 80, 2080);
 681   Intervals = Tree.getContaining(Point);
 682   Tree.sortIntervals(Intervals, UUSorting::Ascending);
 683   ASSERT_EQ(Intervals.size(), 2u);
 684   checkData(Point, Intervals[0], 20, 80, 2080);
 685   checkData(Point, Intervals[1], 10, 90, 1090);
 686   Intervals = Tree.getContaining(Point);
 687   Tree.sortIntervals(Intervals, UUSorting::Descending);
 688   ASSERT_EQ(Intervals.size(), 2u);
 689   checkData(Point, Intervals[0], 10, 90, 1090);
 690   checkData(Point, Intervals[1], 20, 80, 2080);
 691
 692   Point = 85;
 693   Intervals = Tree.getContaining(Point);
 694   ASSERT_EQ(Intervals.size(), 1u);
 695   checkData(Point, Intervals[0], 10, 90, 1090);
 696
 697   Point = 90;
 698   Intervals = Tree.getContaining(Point);
 699   ASSERT_EQ(Intervals.size(), 1u);
 700   checkData(Point, Intervals[0], 10, 90, 1090);
 701
 702   // Invalid interval values: 90] < x
 703   Point = 95;
 704   Intervals = Tree.getContaining(Point);
 705   EXPECT_TRUE(Intervals.empty());
 706 }
 707
 708 // Complex Overlapping.
 709 TEST(IntervalTreeTest, ComplexIntervalsOverlapping) {
 710   UUAlloc Allocator;
 711   UUTree Tree(Allocator);
 712   UUReferences Intervals;
 713   UUPoint Point;
 714
 715   // [30, 35] <- (3035)
 716   // [39, 50] <- (3950)
 717   // [55, 61] <- (5561)
 718   // [31, 56] <- (3156)
 719   // [12, 21] <- (1221)
 720   // [25, 41] <- (2541)
 721   // [49, 65] <- (4965)
 722   // [71, 79] <- (7179)
 723   // [11, 16] <- (1116)
 724   // [20, 30] <- (2030)
 725   // [36, 54] <- (3654)
 726   // [60, 70] <- (6070)
 727   // [74, 80] <- (7480)
 728   // [15, 40] <- (1540)
 729   // [43, 45] <- (4345)
 730   // [50, 75] <- (5075)
 731   // [10, 85] <- (1085)
 732
 733   //                    30--35  39------------50  55----61
 734   //                      31------------------------56
 735   //     12--------21 25------------41      49-------------65   71-----79
 736   //   11----16  20-----30    36----------------54    60------70  74---- 80
 737   //       15---------------------40  43--45  50--------------------75
 738   // 10----------------------------------------------------------------------85
 739
 740   Tree.insert(30, 35, 3035);
 741   Tree.insert(39, 50, 3950);
 742   Tree.insert(55, 61, 5561);
 743   Tree.insert(31, 56, 3156);
 744   Tree.insert(12, 21, 1221);
 745   Tree.insert(25, 41, 2541);
 746   Tree.insert(49, 65, 4965);
 747   Tree.insert(71, 79, 7179);
 748   Tree.insert(11, 16, 1116);
 749   Tree.insert(20, 30, 2030);
 750   Tree.insert(36, 54, 3654);
 751   Tree.insert(60, 70, 6070);
 752   Tree.insert(74, 80, 7480);
 753   Tree.insert(15, 40, 1540);
 754   Tree.insert(43, 45, 4345);
 755   Tree.insert(50, 75, 5075);
 756   Tree.insert(10, 85, 1085);
 757   Tree.create();
 758
 759   // Find valid interval values.
 760   Point = 30;
 761   Intervals = Tree.getContaining(Point);
 762   ASSERT_EQ(Intervals.size(), 5u);
 763   checkData(Point, Intervals[0], 10, 85, 1085);
 764   checkData(Point, Intervals[1], 25, 41, 2541);
 765   checkData(Point, Intervals[2], 15, 40, 1540);
 766   checkData(Point, Intervals[3], 20, 30, 2030);
 767   checkData(Point, Intervals[4], 30, 35, 3035);
 768   Intervals = Tree.getContaining(Point);
 769   Tree.sortIntervals(Intervals, UUSorting::Ascending);
 770   ASSERT_EQ(Intervals.size(), 5u);
 771   checkData(Point, Intervals[0], 30, 35, 3035);
 772   checkData(Point, Intervals[1], 20, 30, 2030);
 773   checkData(Point, Intervals[2], 25, 41, 2541);
 774   checkData(Point, Intervals[3], 15, 40, 1540);
 775   checkData(Point, Intervals[4], 10, 85, 1085);
 776   Intervals = Tree.getContaining(Point);
 777   Tree.sortIntervals(Intervals, UUSorting::Descending);
 778   ASSERT_EQ(Intervals.size(), 5u);
 779   checkData(Point, Intervals[0], 10, 85, 1085);
 780   checkData(Point, Intervals[1], 15, 40, 1540);
 781   checkData(Point, Intervals[2], 25, 41, 2541);
 782   checkData(Point, Intervals[3], 20, 30, 2030);
 783   checkData(Point, Intervals[4], 30, 35, 3035);
 784
 785   Point = 35;
 786   Intervals = Tree.getContaining(Point);
 787   ASSERT_EQ(Intervals.size(), 5u);
 788   checkData(Point, Intervals[0], 10, 85, 1085);
 789   checkData(Point, Intervals[1], 31, 56, 3156);
 790   checkData(Point, Intervals[2], 25, 41, 2541);
 791   checkData(Point, Intervals[3], 15, 40, 1540);
 792   checkData(Point, Intervals[4], 30, 35, 3035);
 793   Intervals = Tree.getContaining(Point);
 794   Tree.sortIntervals(Intervals, UUSorting::Ascending);
 795   ASSERT_EQ(Intervals.size(), 5u);
 796   checkData(Point, Intervals[0], 30, 35, 3035);
 797   checkData(Point, Intervals[1], 25, 41, 2541);
 798   checkData(Point, Intervals[2], 31, 56, 3156);
 799   checkData(Point, Intervals[3], 15, 40, 1540);
 800   checkData(Point, Intervals[4], 10, 85, 1085);
 801   Intervals = Tree.getContaining(Point);
 802   Tree.sortIntervals(Intervals, UUSorting::Descending);
 803   ASSERT_EQ(Intervals.size(), 5u);
 804   checkData(Point, Intervals[0], 10, 85, 1085);
 805   checkData(Point, Intervals[1], 31, 56, 3156);
 806   checkData(Point, Intervals[2], 15, 40, 1540);
 807   checkData(Point, Intervals[3], 25, 41, 2541);
 808   checkData(Point, Intervals[4], 30, 35, 3035);
 809
 810   Point = 39;
 811   Intervals = Tree.getContaining(Point);
 812   ASSERT_EQ(Intervals.size(), 6u);
 813   checkData(Point, Intervals[0], 10, 85, 1085);
 814   checkData(Point, Intervals[1], 31, 56, 3156);
 815   checkData(Point, Intervals[2], 36, 54, 3654);
 816   checkData(Point, Intervals[3], 39, 50, 3950);
 817   checkData(Point, Intervals[4], 25, 41, 2541);
 818   checkData(Point, Intervals[5], 15, 40, 1540);
 819   Intervals = Tree.getContaining(Point);
 820   Tree.sortIntervals(Intervals, UUSorting::Ascending);
 821   ASSERT_EQ(Intervals.size(), 6u);
 822   checkData(Point, Intervals[0], 39, 50, 3950);
 823   checkData(Point, Intervals[1], 25, 41, 2541);
 824   checkData(Point, Intervals[2], 36, 54, 3654);
 825   checkData(Point, Intervals[3], 31, 56, 3156);
 826   checkData(Point, Intervals[4], 15, 40, 1540);
 827   checkData(Point, Intervals[5], 10, 85, 1085);
 828   Intervals = Tree.getContaining(Point);
 829   Tree.sortIntervals(Intervals, UUSorting::Descending);
 830   ASSERT_EQ(Intervals.size(), 6u);
 831   checkData(Point, Intervals[0], 10, 85, 1085);
 832   checkData(Point, Intervals[1], 31, 56, 3156);
 833   checkData(Point, Intervals[2], 15, 40, 1540);
 834   checkData(Point, Intervals[3], 36, 54, 3654);
 835   checkData(Point, Intervals[4], 25, 41, 2541);
 836   checkData(Point, Intervals[5], 39, 50, 3950);
 837
 838   Point = 50;
 839   Intervals = Tree.getContaining(Point);
 840   ASSERT_EQ(Intervals.size(), 6u);
 841   checkData(Point, Intervals[0], 10, 85, 1085);
 842   checkData(Point, Intervals[1], 31, 56, 3156);
 843   checkData(Point, Intervals[2], 36, 54, 3654);
 844   checkData(Point, Intervals[3], 39, 50, 3950);
 845   checkData(Point, Intervals[4], 49, 65, 4965);
 846   checkData(Point, Intervals[5], 50, 75, 5075);
 847   Intervals = Tree.getContaining(Point);
 848   Tree.sortIntervals(Intervals, UUSorting::Ascending);
 849   ASSERT_EQ(Intervals.size(), 6u);
 850   checkData(Point, Intervals[0], 39, 50, 3950);
 851   checkData(Point, Intervals[1], 49, 65, 4965);
 852   checkData(Point, Intervals[2], 36, 54, 3654);
 853   checkData(Point, Intervals[3], 31, 56, 3156);
 854   checkData(Point, Intervals[4], 50, 75, 5075);
 855   checkData(Point, Intervals[5], 10, 85, 1085);
 856   Intervals = Tree.getContaining(Point);
 857   Tree.sortIntervals(Intervals, UUSorting::Descending);
 858   ASSERT_EQ(Intervals.size(), 6u);
 859   checkData(Point, Intervals[0], 10, 85, 1085);
 860   checkData(Point, Intervals[1], 31, 56, 3156);
 861   checkData(Point, Intervals[2], 50, 75, 5075);
 862   checkData(Point, Intervals[3], 36, 54, 3654);
 863   checkData(Point, Intervals[4], 49, 65, 4965);
 864   checkData(Point, Intervals[5], 39, 50, 3950);
 865
 866   Point = 55;
 867   Intervals = Tree.getContaining(Point);
 868   ASSERT_EQ(Intervals.size(), 5u);
 869   checkData(Point, Intervals[0], 10, 85, 1085);
 870   checkData(Point, Intervals[1], 31, 56, 3156);
 871   checkData(Point, Intervals[2], 49, 65, 4965);
 872   checkData(Point, Intervals[3], 50, 75, 5075);
 873   checkData(Point, Intervals[4], 55, 61, 5561);
 874   Intervals = Tree.getContaining(Point);
 875   Tree.sortIntervals(Intervals, UUSorting::Ascending);
 876   ASSERT_EQ(Intervals.size(), 5u);
 877   checkData(Point, Intervals[0], 55, 61, 5561);
 878   checkData(Point, Intervals[1], 49, 65, 4965);
 879   checkData(Point, Intervals[2], 31, 56, 3156);
 880   checkData(Point, Intervals[3], 50, 75, 5075);
 881   checkData(Point, Intervals[4], 10, 85, 1085);
 882   Intervals = Tree.getContaining(Point);
 883   Tree.sortIntervals(Intervals, UUSorting::Descending);
 884   ASSERT_EQ(Intervals.size(), 5u);
 885   checkData(Point, Intervals[0], 10, 85, 1085);
 886   checkData(Point, Intervals[1], 31, 56, 3156);
 887   checkData(Point, Intervals[2], 50, 75, 5075);
 888   checkData(Point, Intervals[3], 49, 65, 4965);
 889   checkData(Point, Intervals[4], 55, 61, 5561);
 890
 891   Point = 61;
 892   Intervals = Tree.getContaining(Point);
 893   ASSERT_EQ(Intervals.size(), 5u);
 894   checkData(Point, Intervals[0], 10, 85, 1085);
 895   checkData(Point, Intervals[1], 49, 65, 4965);
 896   checkData(Point, Intervals[2], 50, 75, 5075);
 897   checkData(Point, Intervals[3], 55, 61, 5561);
 898   checkData(Point, Intervals[4], 60, 70, 6070);
 899   Intervals = Tree.getContaining(Point);
 900   Tree.sortIntervals(Intervals, UUSorting::Ascending);
 901   ASSERT_EQ(Intervals.size(), 5u);
 902   checkData(Point, Intervals[0], 55, 61, 5561);
 903   checkData(Point, Intervals[1], 60, 70, 6070);
 904   checkData(Point, Intervals[2], 49, 65, 4965);
 905   checkData(Point, Intervals[3], 50, 75, 5075);
 906   checkData(Point, Intervals[4], 10, 85, 1085);
 907   Intervals = Tree.getContaining(Point);
 908   Tree.sortIntervals(Intervals, UUSorting::Descending);
 909   ASSERT_EQ(Intervals.size(), 5u);
 910   checkData(Point, Intervals[0], 10, 85, 1085);
 911   checkData(Point, Intervals[1], 50, 75, 5075);
 912   checkData(Point, Intervals[2], 49, 65, 4965);
 913   checkData(Point, Intervals[3], 60, 70, 6070);
 914   checkData(Point, Intervals[4], 55, 61, 5561);
 915
 916   Point = 31;
 917   Intervals = Tree.getContaining(Point);
 918   ASSERT_EQ(Intervals.size(), 5u);
 919   checkData(Point, Intervals[0], 10, 85, 1085);
 920   checkData(Point, Intervals[1], 31, 56, 3156);
 921   checkData(Point, Intervals[2], 25, 41, 2541);
 922   checkData(Point, Intervals[3], 15, 40, 1540);
 923   checkData(Point, Intervals[4], 30, 35, 3035);
 924   Intervals = Tree.getContaining(Point);
 925   Tree.sortIntervals(Intervals, UUSorting::Ascending);
 926   ASSERT_EQ(Intervals.size(), 5u);
 927   checkData(Point, Intervals[0], 30, 35, 3035);
 928   checkData(Point, Intervals[1], 25, 41, 2541);
 929   checkData(Point, Intervals[2], 31, 56, 3156);
 930   checkData(Point, Intervals[3], 15, 40, 1540);
 931   checkData(Point, Intervals[4], 10, 85, 1085);
 932   Intervals = Tree.getContaining(Point);
 933   Tree.sortIntervals(Intervals, UUSorting::Descending);
 934   ASSERT_EQ(Intervals.size(), 5u);
 935   checkData(Point, Intervals[0], 10, 85, 1085);
 936   checkData(Point, Intervals[1], 31, 56, 3156);
 937   checkData(Point, Intervals[2], 15, 40, 1540);
 938   checkData(Point, Intervals[3], 25, 41, 2541);
 939   checkData(Point, Intervals[4], 30, 35, 3035);
 940
 941   Point = 56;
 942   Intervals = Tree.getContaining(Point);
 943   ASSERT_EQ(Intervals.size(), 5u);
 944   checkData(Point, Intervals[0], 10, 85, 1085);
 945   checkData(Point, Intervals[1], 31, 56, 3156);
 946   checkData(Point, Intervals[2], 49, 65, 4965);
 947   checkData(Point, Intervals[3], 50, 75, 5075);
 948   checkData(Point, Intervals[4], 55, 61, 5561);
 949   Intervals = Tree.getContaining(Point);
 950   Tree.sortIntervals(Intervals, UUSorting::Ascending);
 951   ASSERT_EQ(Intervals.size(), 5u);
 952   checkData(Point, Intervals[0], 55, 61, 5561);
 953   checkData(Point, Intervals[1], 49, 65, 4965);
 954   checkData(Point, Intervals[2], 31, 56, 3156);
 955   checkData(Point, Intervals[3], 50, 75, 5075);
 956   checkData(Point, Intervals[4], 10, 85, 1085);
 957   Intervals = Tree.getContaining(Point);
 958   Tree.sortIntervals(Intervals, UUSorting::Descending);
 959   ASSERT_EQ(Intervals.size(), 5u);
 960   checkData(Point, Intervals[0], 10, 85, 1085);
 961   checkData(Point, Intervals[1], 31, 56, 3156);
 962   checkData(Point, Intervals[2], 50, 75, 5075);
 963   checkData(Point, Intervals[3], 49, 65, 4965);
 964   checkData(Point, Intervals[4], 55, 61, 5561);
 965
 966   Point = 12;
 967   Intervals = Tree.getContaining(Point);
 968   ASSERT_EQ(Intervals.size(), 3u);
 969   checkData(Point, Intervals[0], 10, 85, 1085);
 970   checkData(Point, Intervals[1], 11, 16, 1116);
 971   checkData(Point, Intervals[2], 12, 21, 1221);
 972   Intervals = Tree.getContaining(Point);
 973   Tree.sortIntervals(Intervals, UUSorting::Ascending);
 974   ASSERT_EQ(Intervals.size(), 3u);
 975   checkData(Point, Intervals[0], 11, 16, 1116);
 976   checkData(Point, Intervals[1], 12, 21, 1221);
 977   checkData(Point, Intervals[2], 10, 85, 1085);
 978   Intervals = Tree.getContaining(Point);
 979   Tree.sortIntervals(Intervals, UUSorting::Descending);
 980   ASSERT_EQ(Intervals.size(), 3u);
 981   checkData(Point, Intervals[0], 10, 85, 1085);
 982   checkData(Point, Intervals[1], 12, 21, 1221);
 983   checkData(Point, Intervals[2], 11, 16, 1116);
 984
 985   Point = 21;
 986   Intervals = Tree.getContaining(Point);
 987   ASSERT_EQ(Intervals.size(), 4u);
 988   checkData(Point, Intervals[0], 10, 85, 1085);
 989   checkData(Point, Intervals[1], 15, 40, 1540);
 990   checkData(Point, Intervals[2], 20, 30, 2030);
 991   checkData(Point, Intervals[3], 12, 21, 1221);
 992   Intervals = Tree.getContaining(Point);
 993   Tree.sortIntervals(Intervals, UUSorting::Ascending);
 994   ASSERT_EQ(Intervals.size(), 4u);
 995   checkData(Point, Intervals[0], 12, 21, 1221);
 996   checkData(Point, Intervals[1], 20, 30, 2030);
 997   checkData(Point, Intervals[2], 15, 40, 1540);
 998   checkData(Point, Intervals[3], 10, 85, 1085);
 999   Intervals = Tree.getContaining(Point);
1000   Tree.sortIntervals(Intervals, UUSorting::Descending);
1001   ASSERT_EQ(Intervals.size(), 4u);
1002   checkData(Point, Intervals[0], 10, 85, 1085);
1003   checkData(Point, Intervals[1], 15, 40, 1540);
1004   checkData(Point, Intervals[2], 20, 30, 2030);
1005   checkData(Point, Intervals[3], 12, 21, 1221);
1006
1007   Point = 25;
1008   Intervals = Tree.getContaining(Point);
1009   ASSERT_EQ(Intervals.size(), 4u);
1010   checkData(Point, Intervals[0], 10, 85, 1085);
1011   checkData(Point, Intervals[1], 15, 40, 1540);
1012   checkData(Point, Intervals[2], 20, 30, 2030);
1013   checkData(Point, Intervals[3], 25, 41, 2541);
1014   Intervals = Tree.getContaining(Point);
1015   Tree.sortIntervals(Intervals, UUSorting::Ascending);
1016   ASSERT_EQ(Intervals.size(), 4u);
1017   checkData(Point, Intervals[0], 20, 30, 2030);
1018   checkData(Point, Intervals[1], 25, 41, 2541);
1019   checkData(Point, Intervals[2], 15, 40, 1540);
1020   checkData(Point, Intervals[3], 10, 85, 1085);
1021   Intervals = Tree.getContaining(Point);
1022   Tree.sortIntervals(Intervals, UUSorting::Descending);
1023   ASSERT_EQ(Intervals.size(), 4u);
1024   checkData(Point, Intervals[0], 10, 85, 1085);
1025   checkData(Point, Intervals[1], 15, 40, 1540);
1026   checkData(Point, Intervals[2], 25, 41, 2541);
1027   checkData(Point, Intervals[3], 20, 30, 2030);
1028
1029   Point = 41;
1030   Intervals = Tree.getContaining(Point);
1031   ASSERT_EQ(Intervals.size(), 5u);
1032   checkData(Point, Intervals[0], 10, 85, 1085);
1033   checkData(Point, Intervals[1], 31, 56, 3156);
1034   checkData(Point, Intervals[2], 36, 54, 3654);
1035   checkData(Point, Intervals[3], 39, 50, 3950);
1036   checkData(Point, Intervals[4], 25, 41, 2541);
1037   Intervals = Tree.getContaining(Point);
1038   Tree.sortIntervals(Intervals, UUSorting::Ascending);
1039   ASSERT_EQ(Intervals.size(), 5u);
1040   checkData(Point, Intervals[0], 39, 50, 3950);
1041   checkData(Point, Intervals[1], 25, 41, 2541);
1042   checkData(Point, Intervals[2], 36, 54, 3654);
1043   checkData(Point, Intervals[3], 31, 56, 3156);
1044   checkData(Point, Intervals[4], 10, 85, 1085);
1045   Intervals = Tree.getContaining(Point);
1046   Tree.sortIntervals(Intervals, UUSorting::Descending);
1047   ASSERT_EQ(Intervals.size(), 5u);
1048   checkData(Point, Intervals[0], 10, 85, 1085);
1049   checkData(Point, Intervals[1], 31, 56, 3156);
1050   checkData(Point, Intervals[2], 36, 54, 3654);
1051   checkData(Point, Intervals[3], 25, 41, 2541);
1052   checkData(Point, Intervals[4], 39, 50, 3950);
1053
1054   Point = 49;
1055   Intervals = Tree.getContaining(Point);
1056   ASSERT_EQ(Intervals.size(), 5u);
1057   checkData(Point, Intervals[0], 10, 85, 1085);
1058   checkData(Point, Intervals[1], 31, 56, 3156);
1059   checkData(Point, Intervals[2], 36, 54, 3654);
1060   checkData(Point, Intervals[3], 39, 50, 3950);
1061   checkData(Point, Intervals[4], 49, 65, 4965);
1062   Intervals = Tree.getContaining(Point);
1063   Tree.sortIntervals(Intervals, UUSorting::Ascending);
1064   ASSERT_EQ(Intervals.size(), 5u);
1065   checkData(Point, Intervals[0], 39, 50, 3950);
1066   checkData(Point, Intervals[1], 49, 65, 4965);
1067   checkData(Point, Intervals[2], 36, 54, 3654);
1068   checkData(Point, Intervals[3], 31, 56, 3156);
1069   checkData(Point, Intervals[4], 10, 85, 1085);
1070   Intervals = Tree.getContaining(Point);
1071   Tree.sortIntervals(Intervals, UUSorting::Descending);
1072   ASSERT_EQ(Intervals.size(), 5u);
1073   checkData(Point, Intervals[0], 10, 85, 1085);
1074   checkData(Point, Intervals[1], 31, 56, 3156);
1075   checkData(Point, Intervals[2], 36, 54, 3654);
1076   checkData(Point, Intervals[3], 49, 65, 4965);
1077   checkData(Point, Intervals[4], 39, 50, 3950);
1078
1079   Point = 65;
1080   Intervals = Tree.getContaining(Point);
1081   ASSERT_EQ(Intervals.size(), 4u);
1082   checkData(Point, Intervals[0], 10, 85, 1085);
1083   checkData(Point, Intervals[1], 50, 75, 5075);
1084   checkData(Point, Intervals[2], 60, 70, 6070);
1085   checkData(Point, Intervals[3], 49, 65, 4965);
1086   Intervals = Tree.getContaining(Point);
1087   Tree.sortIntervals(Intervals, UUSorting::Ascending);
1088   ASSERT_EQ(Intervals.size(), 4u);
1089   checkData(Point, Intervals[0], 60, 70, 6070);
1090   checkData(Point, Intervals[1], 49, 65, 4965);
1091   checkData(Point, Intervals[2], 50, 75, 5075);
1092   checkData(Point, Intervals[3], 10, 85, 1085);
1093   Intervals = Tree.getContaining(Point);
1094   Tree.sortIntervals(Intervals, UUSorting::Descending);
1095   ASSERT_EQ(Intervals.size(), 4u);
1096   checkData(Point, Intervals[0], 10, 85, 1085);
1097   checkData(Point, Intervals[1], 50, 75, 5075);
1098   checkData(Point, Intervals[2], 49, 65, 4965);
1099   checkData(Point, Intervals[3], 60, 70, 6070);
1100
1101   Point = 71;
1102   Intervals = Tree.getContaining(Point);
1103   ASSERT_EQ(Intervals.size(), 3u);
1104   checkData(Point, Intervals[0], 10, 85, 1085);
1105   checkData(Point, Intervals[1], 50, 75, 5075);
1106   checkData(Point, Intervals[2], 71, 79, 7179);
1107   Intervals = Tree.getContaining(Point);
1108   Tree.sortIntervals(Intervals, UUSorting::Ascending);
1109   ASSERT_EQ(Intervals.size(), 3u);
1110   checkData(Point, Intervals[0], 71, 79, 7179);
1111   checkData(Point, Intervals[1], 50, 75, 5075);
1112   checkData(Point, Intervals[2], 10, 85, 1085);
1113   Intervals = Tree.getContaining(Point);
1114   Tree.sortIntervals(Intervals, UUSorting::Descending);
1115   ASSERT_EQ(Intervals.size(), 3u);
1116   checkData(Point, Intervals[0], 10, 85, 1085);
1117   checkData(Point, Intervals[1], 50, 75, 5075);
1118   checkData(Point, Intervals[2], 71, 79, 7179);
1119
1120   Point = 79;
1121   Intervals = Tree.getContaining(Point);
1122   ASSERT_EQ(Intervals.size(), 3u);
1123   checkData(Point, Intervals[0], 10, 85, 1085);
1124   checkData(Point, Intervals[1], 74, 80, 7480);
1125   checkData(Point, Intervals[2], 71, 79, 7179);
1126   Intervals = Tree.getContaining(Point);
1127   Tree.sortIntervals(Intervals, UUSorting::Ascending);
1128   ASSERT_EQ(Intervals.size(), 3u);
1129   checkData(Point, Intervals[0], 74, 80, 7480);
1130   checkData(Point, Intervals[1], 71, 79, 7179);
1131   checkData(Point, Intervals[2], 10, 85, 1085);
1132   Intervals = Tree.getContaining(Point);
1133   Tree.sortIntervals(Intervals, UUSorting::Descending);
1134   ASSERT_EQ(Intervals.size(), 3u);
1135   checkData(Point, Intervals[0], 10, 85, 1085);
1136   checkData(Point, Intervals[1], 71, 79, 7179);
1137   checkData(Point, Intervals[2], 74, 80, 7480);
1138
1139   Point = 11;
1140   Intervals = Tree.getContaining(Point);
1141   ASSERT_EQ(Intervals.size(), 2u);
1142   checkData(Point, Intervals[0], 10, 85, 1085);
1143   checkData(Point, Intervals[1], 11, 16, 1116);
1144   Intervals = Tree.getContaining(Point);
1145   Tree.sortIntervals(Intervals, UUSorting::Ascending);
1146   ASSERT_EQ(Intervals.size(), 2u);
1147   checkData(Point, Intervals[0], 11, 16, 1116);
1148   checkData(Point, Intervals[1], 10, 85, 1085);
1149   Intervals = Tree.getContaining(Point);
1150   Tree.sortIntervals(Intervals, UUSorting::Descending);
1151   ASSERT_EQ(Intervals.size(), 2u);
1152   checkData(Point, Intervals[0], 10, 85, 1085);
1153   checkData(Point, Intervals[1], 11, 16, 1116);
1154
1155   Point = 16;
1156   Intervals = Tree.getContaining(Point);
1157   ASSERT_EQ(Intervals.size(), 4u);
1158   checkData(Point, Intervals[0], 10, 85, 1085);
1159   checkData(Point, Intervals[1], 15, 40, 1540);
1160   checkData(Point, Intervals[2], 12, 21, 1221);
1161   checkData(Point, Intervals[3], 11, 16, 1116);
1162   Intervals = Tree.getContaining(Point);
1163   Tree.sortIntervals(Intervals, UUSorting::Ascending);
1164   ASSERT_EQ(Intervals.size(), 4u);
1165   checkData(Point, Intervals[0], 11, 16, 1116);
1166   checkData(Point, Intervals[1], 12, 21, 1221);
1167   checkData(Point, Intervals[2], 15, 40, 1540);
1168   checkData(Point, Intervals[3], 10, 85, 1085);
1169   Intervals = Tree.getContaining(Point);
1170   Tree.sortIntervals(Intervals, UUSorting::Descending);
1171   ASSERT_EQ(Intervals.size(), 4u);
1172   checkData(Point, Intervals[0], 10, 85, 1085);
1173   checkData(Point, Intervals[1], 15, 40, 1540);
1174   checkData(Point, Intervals[2], 12, 21, 1221);
1175   checkData(Point, Intervals[3], 11, 16, 1116);
1176
1177   Point = 20;
1178   Intervals = Tree.getContaining(Point);
1179   ASSERT_EQ(Intervals.size(), 4u);
1180   checkData(Point, Intervals[0], 10, 85, 1085);
1181   checkData(Point, Intervals[1], 15, 40, 1540);
1182   checkData(Point, Intervals[2], 20, 30, 2030);
1183   checkData(Point, Intervals[3], 12, 21, 1221);
1184   Intervals = Tree.getContaining(Point);
1185   Tree.sortIntervals(Intervals, UUSorting::Ascending);
1186   ASSERT_EQ(Intervals.size(), 4u);
1187   checkData(Point, Intervals[0], 12, 21, 1221);
1188   checkData(Point, Intervals[1], 20, 30, 2030);
1189   checkData(Point, Intervals[2], 15, 40, 1540);
1190   checkData(Point, Intervals[3], 10, 85, 1085);
1191   Intervals = Tree.getContaining(Point);
1192   Tree.sortIntervals(Intervals, UUSorting::Descending);
1193   ASSERT_EQ(Intervals.size(), 4u);
1194   checkData(Point, Intervals[0], 10, 85, 1085);
1195   checkData(Point, Intervals[1], 15, 40, 1540);
1196   checkData(Point, Intervals[2], 20, 30, 2030);
1197   checkData(Point, Intervals[3], 12, 21, 1221);
1198
1199   Point = 30;
1200   Intervals = Tree.getContaining(Point);
1201   ASSERT_EQ(Intervals.size(), 5u);
1202   checkData(Point, Intervals[0], 10, 85, 1085);
1203   checkData(Point, Intervals[1], 25, 41, 2541);
1204   checkData(Point, Intervals[2], 15, 40, 1540);
1205   checkData(Point, Intervals[3], 20, 30, 2030);
1206   checkData(Point, Intervals[4], 30, 35, 3035);
1207   Intervals = Tree.getContaining(Point);
1208   Tree.sortIntervals(Intervals, UUSorting::Ascending);
1209   ASSERT_EQ(Intervals.size(), 5u);
1210   checkData(Point, Intervals[0], 30, 35, 3035);
1211   checkData(Point, Intervals[1], 20, 30, 2030);
1212   checkData(Point, Intervals[2], 25, 41, 2541);
1213   checkData(Point, Intervals[3], 15, 40, 1540);
1214   checkData(Point, Intervals[4], 10, 85, 1085);
1215   Intervals = Tree.getContaining(Point);
1216   Tree.sortIntervals(Intervals, UUSorting::Descending);
1217   ASSERT_EQ(Intervals.size(), 5u);
1218   checkData(Point, Intervals[0], 10, 85, 1085);
1219   checkData(Point, Intervals[1], 15, 40, 1540);
1220   checkData(Point, Intervals[2], 25, 41, 2541);
1221   checkData(Point, Intervals[3], 20, 30, 2030);
1222   checkData(Point, Intervals[4], 30, 35, 3035);
1223
1224   Point = 36;
1225   Intervals = Tree.getContaining(Point);
1226   ASSERT_EQ(Intervals.size(), 5u);
1227   checkData(Point, Intervals[0], 10, 85, 1085);
1228   checkData(Point, Intervals[1], 31, 56, 3156);
1229   checkData(Point, Intervals[2], 36, 54, 3654);
1230   checkData(Point, Intervals[3], 25, 41, 2541);
1231   checkData(Point, Intervals[4], 15, 40, 1540);
1232   Intervals = Tree.getContaining(Point);
1233   Tree.sortIntervals(Intervals, UUSorting::Ascending);
1234   ASSERT_EQ(Intervals.size(), 5u);
1235   checkData(Point, Intervals[0], 25, 41, 2541);
1236   checkData(Point, Intervals[1], 36, 54, 3654);
1237   checkData(Point, Intervals[2], 31, 56, 3156);
1238   checkData(Point, Intervals[3], 15, 40, 1540);
1239   checkData(Point, Intervals[4], 10, 85, 1085);
1240   Intervals = Tree.getContaining(Point);
1241   Tree.sortIntervals(Intervals, UUSorting::Descending);
1242   ASSERT_EQ(Intervals.size(), 5u);
1243   checkData(Point, Intervals[0], 10, 85, 1085);
1244   checkData(Point, Intervals[1], 31, 56, 3156);
1245   checkData(Point, Intervals[2], 15, 40, 1540);
1246   checkData(Point, Intervals[3], 36, 54, 3654);
1247   checkData(Point, Intervals[4], 25, 41, 2541);
1248
1249   Point = 54;
1250   Intervals = Tree.getContaining(Point);
1251   ASSERT_EQ(Intervals.size(), 5u);
1252   checkData(Point, Intervals[0], 10, 85, 1085);
1253   checkData(Point, Intervals[1], 31, 56, 3156);
1254   checkData(Point, Intervals[2], 36, 54, 3654);
1255   checkData(Point, Intervals[3], 49, 65, 4965);
1256   checkData(Point, Intervals[4], 50, 75, 5075);
1257   Intervals = Tree.getContaining(Point);
1258   Tree.sortIntervals(Intervals, UUSorting::Ascending);
1259   ASSERT_EQ(Intervals.size(), 5u);
1260   checkData(Point, Intervals[0], 49, 65, 4965);
1261   checkData(Point, Intervals[1], 36, 54, 3654);
1262   checkData(Point, Intervals[2], 31, 56, 3156);
1263   checkData(Point, Intervals[3], 50, 75, 5075);
1264   checkData(Point, Intervals[4], 10, 85, 1085);
1265   Intervals = Tree.getContaining(Point);
1266   Tree.sortIntervals(Intervals, UUSorting::Descending);
1267   ASSERT_EQ(Intervals.size(), 5u);
1268   checkData(Point, Intervals[0], 10, 85, 1085);
1269   checkData(Point, Intervals[1], 31, 56, 3156);
1270   checkData(Point, Intervals[2], 50, 75, 5075);
1271   checkData(Point, Intervals[3], 36, 54, 3654);
1272   checkData(Point, Intervals[4], 49, 65, 4965);
1273
1274   Point = 60;
1275   Intervals = Tree.getContaining(Point);
1276   ASSERT_EQ(Intervals.size(), 5u);
1277   checkData(Point, Intervals[0], 10, 85, 1085);
1278   checkData(Point, Intervals[1], 49, 65, 4965);
1279   checkData(Point, Intervals[2], 50, 75, 5075);
1280   checkData(Point, Intervals[3], 55, 61, 5561);
1281   checkData(Point, Intervals[4], 60, 70, 6070);
1282   Intervals = Tree.getContaining(Point);
1283   Tree.sortIntervals(Intervals, UUSorting::Ascending);
1284   ASSERT_EQ(Intervals.size(), 5u);
1285   checkData(Point, Intervals[0], 55, 61, 5561);
1286   checkData(Point, Intervals[1], 60, 70, 6070);
1287   checkData(Point, Intervals[2], 49, 65, 4965);
1288   checkData(Point, Intervals[3], 50, 75, 5075);
1289   checkData(Point, Intervals[4], 10, 85, 1085);
1290   Intervals = Tree.getContaining(Point);
1291   Tree.sortIntervals(Intervals, UUSorting::Descending);
1292   ASSERT_EQ(Intervals.size(), 5u);
1293   checkData(Point, Intervals[0], 10, 85, 1085);
1294   checkData(Point, Intervals[1], 50, 75, 5075);
1295   checkData(Point, Intervals[2], 49, 65, 4965);
1296   checkData(Point, Intervals[3], 60, 70, 6070);
1297   checkData(Point, Intervals[4], 55, 61, 5561);
1298
1299   Point = 70;
1300   Intervals = Tree.getContaining(Point);
1301   ASSERT_EQ(Intervals.size(), 3u);
1302   checkData(Point, Intervals[0], 10, 85, 1085);
1303   checkData(Point, Intervals[1], 50, 75, 5075);
1304   checkData(Point, Intervals[2], 60, 70, 6070);
1305   Intervals = Tree.getContaining(Point);
1306   Tree.sortIntervals(Intervals, UUSorting::Ascending);
1307   ASSERT_EQ(Intervals.size(), 3u);
1308   checkData(Point, Intervals[0], 60, 70, 6070);
1309   checkData(Point, Intervals[1], 50, 75, 5075);
1310   checkData(Point, Intervals[2], 10, 85, 1085);
1311   Intervals = Tree.getContaining(Point);
1312   Tree.sortIntervals(Intervals, UUSorting::Descending);
1313   ASSERT_EQ(Intervals.size(), 3u);
1314   checkData(Point, Intervals[0], 10, 85, 1085);
1315   checkData(Point, Intervals[1], 50, 75, 5075);
1316   checkData(Point, Intervals[2], 60, 70, 6070);
1317
1318   Point = 74;
1319   Intervals = Tree.getContaining(Point);
1320   ASSERT_EQ(Intervals.size(), 4u);
1321   checkData(Point, Intervals[0], 10, 85, 1085);
1322   checkData(Point, Intervals[1], 50, 75, 5075);
1323   checkData(Point, Intervals[2], 71, 79, 7179);
1324   checkData(Point, Intervals[3], 74, 80, 7480);
1325   Intervals = Tree.getContaining(Point);
1326   Tree.sortIntervals(Intervals, UUSorting::Ascending);
1327   ASSERT_EQ(Intervals.size(), 4u);
1328   checkData(Point, Intervals[0], 74, 80, 7480);
1329   checkData(Point, Intervals[1], 71, 79, 7179);
1330   checkData(Point, Intervals[2], 50, 75, 5075);
1331   checkData(Point, Intervals[3], 10, 85, 1085);
1332   Intervals = Tree.getContaining(Point);
1333   Tree.sortIntervals(Intervals, UUSorting::Descending);
1334   ASSERT_EQ(Intervals.size(), 4u);
1335   checkData(Point, Intervals[0], 10, 85, 1085);
1336   checkData(Point, Intervals[1], 50, 75, 5075);
1337   checkData(Point, Intervals[2], 71, 79, 7179);
1338   checkData(Point, Intervals[3], 74, 80, 7480);
1339
1340   Point = 80;
1341   Intervals = Tree.getContaining(Point);
1342   ASSERT_EQ(Intervals.size(), 2u);
1343   checkData(Point, Intervals[0], 10, 85, 1085);
1344   checkData(Point, Intervals[1], 74, 80, 7480);
1345   Intervals = Tree.getContaining(Point);
1346   Tree.sortIntervals(Intervals, UUSorting::Ascending);
1347   ASSERT_EQ(Intervals.size(), 2u);
1348   checkData(Point, Intervals[0], 74, 80, 7480);
1349   checkData(Point, Intervals[1], 10, 85, 1085);
1350   Intervals = Tree.getContaining(Point);
1351   Tree.sortIntervals(Intervals, UUSorting::Descending);
1352   ASSERT_EQ(Intervals.size(), 2u);
1353   checkData(Point, Intervals[0], 10, 85, 1085);
1354   checkData(Point, Intervals[1], 74, 80, 7480);
1355
1356   Point = 15;
1357   Intervals = Tree.getContaining(Point);
1358   ASSERT_EQ(Intervals.size(), 4u);
1359   checkData(Point, Intervals[0], 10, 85, 1085);
1360   checkData(Point, Intervals[1], 15, 40, 1540);
1361   checkData(Point, Intervals[2], 11, 16, 1116);
1362   checkData(Point, Intervals[3], 12, 21, 1221);
1363   Intervals = Tree.getContaining(Point);
1364   Tree.sortIntervals(Intervals, UUSorting::Ascending);
1365   ASSERT_EQ(Intervals.size(), 4u);
1366   checkData(Point, Intervals[0], 11, 16, 1116);
1367   checkData(Point, Intervals[1], 12, 21, 1221);
1368   checkData(Point, Intervals[2], 15, 40, 1540);
1369   checkData(Point, Intervals[3], 10, 85, 1085);
1370   Intervals = Tree.getContaining(Point);
1371   Tree.sortIntervals(Intervals, UUSorting::Descending);
1372   ASSERT_EQ(Intervals.size(), 4u);
1373   checkData(Point, Intervals[0], 10, 85, 1085);
1374   checkData(Point, Intervals[1], 15, 40, 1540);
1375   checkData(Point, Intervals[2], 12, 21, 1221);
1376   checkData(Point, Intervals[3], 11, 16, 1116);
1377
1378   Point = 40;
1379   Intervals = Tree.getContaining(Point);
1380   ASSERT_EQ(Intervals.size(), 6u);
1381   checkData(Point, Intervals[0], 10, 85, 1085);
1382   checkData(Point, Intervals[1], 31, 56, 3156);
1383   checkData(Point, Intervals[2], 36, 54, 3654);
1384   checkData(Point, Intervals[3], 39, 50, 3950);
1385   checkData(Point, Intervals[4], 25, 41, 2541);
1386   checkData(Point, Intervals[5], 15, 40, 1540);
1387   Intervals = Tree.getContaining(Point);
1388   Tree.sortIntervals(Intervals, UUSorting::Ascending);
1389   ASSERT_EQ(Intervals.size(), 6u);
1390   checkData(Point, Intervals[0], 39, 50, 3950);
1391   checkData(Point, Intervals[1], 25, 41, 2541);
1392   checkData(Point, Intervals[2], 36, 54, 3654);
1393   checkData(Point, Intervals[3], 31, 56, 3156);
1394   checkData(Point, Intervals[4], 15, 40, 1540);
1395   checkData(Point, Intervals[5], 10, 85, 1085);
1396   Intervals = Tree.getContaining(Point);
1397   Tree.sortIntervals(Intervals, UUSorting::Descending);
1398   ASSERT_EQ(Intervals.size(), 6u);
1399   checkData(Point, Intervals[0], 10, 85, 1085);
1400   checkData(Point, Intervals[1], 31, 56, 3156);
1401   checkData(Point, Intervals[2], 15, 40, 1540);
1402   checkData(Point, Intervals[3], 36, 54, 3654);
1403   checkData(Point, Intervals[4], 25, 41, 2541);
1404   checkData(Point, Intervals[5], 39, 50, 3950);
1405
1406   Point = 43;
1407   Intervals = Tree.getContaining(Point);
1408   ASSERT_EQ(Intervals.size(), 5u);
1409   checkData(Point, Intervals[0], 10, 85, 1085);
1410   checkData(Point, Intervals[1], 31, 56, 3156);
1411   checkData(Point, Intervals[2], 36, 54, 3654);
1412   checkData(Point, Intervals[3], 39, 50, 3950);
1413   checkData(Point, Intervals[4], 43, 45, 4345);
1414   Intervals = Tree.getContaining(Point);
1415   Tree.sortIntervals(Intervals, UUSorting::Ascending);
1416   ASSERT_EQ(Intervals.size(), 5u);
1417   checkData(Point, Intervals[0], 43, 45, 4345);
1418   checkData(Point, Intervals[1], 39, 50, 3950);
1419   checkData(Point, Intervals[2], 36, 54, 3654);
1420   checkData(Point, Intervals[3], 31, 56, 3156);
1421   checkData(Point, Intervals[4], 10, 85, 1085);
1422   Intervals = Tree.getContaining(Point);
1423   Tree.sortIntervals(Intervals, UUSorting::Descending);
1424   ASSERT_EQ(Intervals.size(), 5u);
1425   checkData(Point, Intervals[0], 10, 85, 1085);
1426   checkData(Point, Intervals[1], 31, 56, 3156);
1427   checkData(Point, Intervals[2], 36, 54, 3654);
1428   checkData(Point, Intervals[3], 39, 50, 3950);
1429   checkData(Point, Intervals[4], 43, 45, 4345);
1430
1431   Point = 45;
1432   Intervals = Tree.getContaining(Point);
1433   ASSERT_EQ(Intervals.size(), 5u);
1434   checkData(Point, Intervals[0], 10, 85, 1085);
1435   checkData(Point, Intervals[1], 31, 56, 3156);
1436   checkData(Point, Intervals[2], 36, 54, 3654);
1437   checkData(Point, Intervals[3], 39, 50, 3950);
1438   checkData(Point, Intervals[4], 43, 45, 4345);
1439   Intervals = Tree.getContaining(Point);
1440   Tree.sortIntervals(Intervals, UUSorting::Ascending);
1441   ASSERT_EQ(Intervals.size(), 5u);
1442   checkData(Point, Intervals[0], 43, 45, 4345);
1443   checkData(Point, Intervals[1], 39, 50, 3950);
1444   checkData(Point, Intervals[2], 36, 54, 3654);
1445   checkData(Point, Intervals[3], 31, 56, 3156);
1446   checkData(Point, Intervals[4], 10, 85, 1085);
1447   Intervals = Tree.getContaining(Point);
1448   Tree.sortIntervals(Intervals, UUSorting::Descending);
1449   ASSERT_EQ(Intervals.size(), 5u);
1450   checkData(Point, Intervals[0], 10, 85, 1085);
1451   checkData(Point, Intervals[1], 31, 56, 3156);
1452   checkData(Point, Intervals[2], 36, 54, 3654);
1453   checkData(Point, Intervals[3], 39, 50, 3950);
1454   checkData(Point, Intervals[4], 43, 45, 4345);
1455
1456   Point = 50;
1457   Intervals = Tree.getContaining(Point);
1458   ASSERT_EQ(Intervals.size(), 6u);
1459   checkData(Point, Intervals[0], 10, 85, 1085);
1460   checkData(Point, Intervals[1], 31, 56, 3156);
1461   checkData(Point, Intervals[2], 36, 54, 3654);
1462   checkData(Point, Intervals[3], 39, 50, 3950);
1463   checkData(Point, Intervals[4], 49, 65, 4965);
1464   checkData(Point, Intervals[5], 50, 75, 5075);
1465   Intervals = Tree.getContaining(Point);
1466   Tree.sortIntervals(Intervals, UUSorting::Ascending);
1467   ASSERT_EQ(Intervals.size(), 6u);
1468   checkData(Point, Intervals[0], 39, 50, 3950);
1469   checkData(Point, Intervals[1], 49, 65, 4965);
1470   checkData(Point, Intervals[2], 36, 54, 3654);
1471   checkData(Point, Intervals[3], 31, 56, 3156);
1472   checkData(Point, Intervals[4], 50, 75, 5075);
1473   checkData(Point, Intervals[5], 10, 85, 1085);
1474   Intervals = Tree.getContaining(Point);
1475   Tree.sortIntervals(Intervals, UUSorting::Descending);
1476   ASSERT_EQ(Intervals.size(), 6u);
1477   checkData(Point, Intervals[0], 10, 85, 1085);
1478   checkData(Point, Intervals[1], 31, 56, 3156);
1479   checkData(Point, Intervals[2], 50, 75, 5075);
1480   checkData(Point, Intervals[3], 36, 54, 3654);
1481   checkData(Point, Intervals[4], 49, 65, 4965);
1482   checkData(Point, Intervals[5], 39, 50, 3950);
1483
1484   Point = 75;
1485   Intervals = Tree.getContaining(Point);
1486   ASSERT_EQ(Intervals.size(), 4u);
1487   checkData(Point, Intervals[0], 10, 85, 1085);
1488   checkData(Point, Intervals[1], 50, 75, 5075);
1489   checkData(Point, Intervals[2], 74, 80, 7480);
1490   checkData(Point, Intervals[3], 71, 79, 7179);
1491   Intervals = Tree.getContaining(Point);
1492   Tree.sortIntervals(Intervals, UUSorting::Ascending);
1493   ASSERT_EQ(Intervals.size(), 4u);
1494   checkData(Point, Intervals[0], 74, 80, 7480);
1495   checkData(Point, Intervals[1], 71, 79, 7179);
1496   checkData(Point, Intervals[2], 50, 75, 5075);
1497   checkData(Point, Intervals[3], 10, 85, 1085);
1498   Intervals = Tree.getContaining(Point);
1499   Tree.sortIntervals(Intervals, UUSorting::Descending);
1500   ASSERT_EQ(Intervals.size(), 4u);
1501   checkData(Point, Intervals[0], 10, 85, 1085);
1502   checkData(Point, Intervals[1], 50, 75, 5075);
1503   checkData(Point, Intervals[2], 71, 79, 7179);
1504   checkData(Point, Intervals[3], 74, 80, 7480);
1505
1506   Point = 10;
1507   Intervals = Tree.getContaining(Point);
1508   ASSERT_EQ(Intervals.size(), 1u);
1509   checkData(Point, Intervals[0], 10, 85, 1085);
1510
1511   Point = 85;
1512   Intervals = Tree.getContaining(Point);
1513   ASSERT_EQ(Intervals.size(), 1u);
1514   checkData(Point, Intervals[0], 10, 85, 1085);
1515
1516   // Invalid interval values.
1517   Point = 5;
1518   Intervals = Tree.getContaining(Point);
1519   EXPECT_TRUE(Intervals.empty());
1520   Point = 90;
1521   Intervals = Tree.getContaining(Point);
1522   EXPECT_TRUE(Intervals.empty());
1523 }
1524
1525 // Four items tree tests. Overlapping. Check mapped values and iterators.
1526 TEST(IntervalTreeTest, MappedValuesIteratorsTree) {
1527   UUAlloc Allocator;
1528   UUTree Tree(Allocator);
1529   UUPoint Point;
1530
1531   // [10, 20] <- (1020)
1532   // [15, 25] <- (1525)
1533   // [50, 60] <- (5060)
1534   // [55, 65] <- (5565)
1535   //
1536   //    [10.........20]
1537   //          [15.........25]
1538   //                            [50.........60]
1539   //                                  [55.........65]
1540   Tree.insert(10, 20, 1020);
1541   Tree.insert(15, 25, 1525);
1542   Tree.insert(50, 60, 5060);
1543   Tree.insert(55, 65, 5565);
1544   Tree.create();
1545
1546   // Iterators.
1547   {
1548     // Start searching for '10'.
1549     Point = 10;
1550     UUIter Iter = Tree.find(Point);
1551     EXPECT_NE(Iter, Tree.find_end());
1552     checkData(Point, Iter, 10, 20, 1020);
1553     ++Iter;
1554     EXPECT_EQ(Iter, Tree.find_end());
1555   }
1556   {
1557     // Start searching for '15'.
1558     Point = 15;
1559     UUIter Iter = Tree.find(Point);
1560     ASSERT_TRUE(Iter != Tree.find_end());
1561     checkData(Point, Iter, 15, 25, 1525);
1562     ++Iter;
1563     ASSERT_TRUE(Iter != Tree.find_end());
1564     checkData(Point, Iter, 10, 20, 1020);
1565     ++Iter;
1566     EXPECT_EQ(Iter, Tree.find_end());
1567   }
1568   {
1569     // Start searching for '20'.
1570     Point = 20;
1571     UUIter Iter = Tree.find(Point);
1572     ASSERT_TRUE(Iter != Tree.find_end());
1573     checkData(Point, Iter, 15, 25, 1525);
1574     ++Iter;
1575     ASSERT_TRUE(Iter != Tree.find_end());
1576     checkData(Point, Iter, 10, 20, 1020);
1577     ++Iter;
1578     EXPECT_EQ(Iter, Tree.find_end());
1579   }
1580   {
1581     // Start searching for '25'.
1582     Point = 25;
1583     UUIter Iter = Tree.find(Point);
1584     ASSERT_TRUE(Iter != Tree.find_end());
1585     checkData(Point, Iter, 15, 25, 1525);
1586     ++Iter;
1587     EXPECT_EQ(Iter, Tree.find_end());
1588   }
1589   // Invalid interval values.
1590   {
1591     Point = 5;
1592     UUIter Iter = Tree.find(Point);
1593     EXPECT_EQ(Iter, Tree.find_end());
1594   }
1595   {
1596     Point = 45;
1597     UUIter Iter = Tree.find(Point);
1598     EXPECT_EQ(Iter, Tree.find_end());
1599   }
1600   {
1601     Point = 70;
1602     UUIter Iter = Tree.find(Point);
1603     EXPECT_EQ(Iter, Tree.find_end());
1604   }
1605 }
1606
1607 } // namespace