1608 lines · 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-exception6//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 outside16// 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 is20// 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 32using namespace llvm;33 34namespace {35 36// Helper function to test a specific item or iterator.37template <typename TPoint, typename TItem, typename TValue>38void 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.47TEST(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 < [1096 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 < [30117 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] < x138 Point = 45;139 Intervals = Tree.getContaining(Point);140 EXPECT_TRUE(Intervals.empty());141}142 143using UUPoint = unsigned; // Interval endpoint type.144using UUValue = unsigned; // Mapped value type.145 146using UUTree = IntervalTree<UUPoint, UUValue>;147using UUReferences = UUTree::IntervalReferences;148using UUData = UUTree::DataType;149using UUSorting = UUTree::Sorting;150using UUPoint = UUTree::PointType;151using UUValue = UUTree::ValueType;152using UUIter = UUTree::find_iterator;153using UUAlloc = UUTree::Allocator;154 155void 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 160void 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.166TEST(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.180TEST(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] < x217 Point = 25;218 Intervals = Tree.getContaining(Point);219 EXPECT_TRUE(Intervals.empty());220}221 222// Two items tree tests. No overlapping.223TEST(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 < [10238 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 < [30259 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] < x280 Point = 45;281 Intervals = Tree.getContaining(Point);282 EXPECT_TRUE(Intervals.empty());283}284 285// Three items tree tests. No overlapping.286TEST(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 < [10303 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 < [30324 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 < [50345 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] < x366 Point = 65;367 Intervals = Tree.getContaining(Point);368 EXPECT_TRUE(Intervals.empty());369}370 371// One item tree tests.372TEST(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] < x408 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] < x426 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] < x443 Point = 75;444 Intervals = Tree.getContaining(Point);445 EXPECT_TRUE(Intervals.empty());446}447 448// Simple overlapping tests.449TEST(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 < [10471 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] < x703 Point = 95;704 Intervals = Tree.getContaining(Point);705 EXPECT_TRUE(Intervals.empty());706}707 708// Complex Overlapping.709TEST(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----61734 // 31------------------------56735 // 12--------21 25------------41 49-------------65 71-----79736 // 11----16 20-----30 36----------------54 60------70 74---- 80737 // 15---------------------40 43--45 50--------------------75738 // 10----------------------------------------------------------------------85739 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.1526TEST(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} // namespace1608