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(), 1); 104 CheckData(Point, Intervals[0], 10, 20, 10.20); 105 106 Point = 15; 107 Intervals = Tree.getContaining(Point); 108 ASSERT_EQ(Intervals.size(), 1); 109 CheckData(Point, Intervals[0], 10, 20, 10.20); 110 111 Point = 20; 112 Intervals = Tree.getContaining(Point); 113 ASSERT_EQ(Intervals.size(), 1); 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(), 1); 125 CheckData(Point, Intervals[0], 30, 40, 30.40); 126 127 Point = 35; 128 Intervals = Tree.getContaining(Point); 129 ASSERT_EQ(Intervals.size(), 1); 130 CheckData(Point, Intervals[0], 30, 40, 30.40); 131 132 Point = 40; 133 Intervals = Tree.getContaining(Point); 134 ASSERT_EQ(Intervals.size(), 1); 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(), 1); 204 checkData(Point, Intervals[0], 10, 20, 1020); 205 206 Point = 15; 207 Intervals = Tree.getContaining(Point); 208 ASSERT_EQ(Intervals.size(), 1); 209 checkData(Point, Intervals[0], 10, 20, 1020); 210 211 Point = 20; 212 Intervals = Tree.getContaining(Point); 213 ASSERT_EQ(Intervals.size(), 1); 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(), 1); 246 checkData(Point, Intervals[0], 10, 20, 1020); 247 248 Point = 15; 249 Intervals = Tree.getContaining(Point); 250 ASSERT_EQ(Intervals.size(), 1); 251 checkData(Point, Intervals[0], 10, 20, 1020); 252 253 Point = 20; 254 Intervals = Tree.getContaining(Point); 255 ASSERT_EQ(Intervals.size(), 1); 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(), 1); 267 checkData(Point, Intervals[0], 30, 40, 3040); 268 269 Point = 35; 270 Intervals = Tree.getContaining(Point); 271 ASSERT_EQ(Intervals.size(), 1); 272 checkData(Point, Intervals[0], 30, 40, 3040); 273 274 Point = 40; 275 Intervals = Tree.getContaining(Point); 276 ASSERT_EQ(Intervals.size(), 1); 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(), 1); 311 checkData(Point, Intervals[0], 10, 20, 1020); 312 313 Point = 15; 314 Intervals = Tree.getContaining(Point); 315 ASSERT_EQ(Intervals.size(), 1); 316 checkData(Point, Intervals[0], 10, 20, 1020); 317 318 Point = 20; 319 Intervals = Tree.getContaining(Point); 320 ASSERT_EQ(Intervals.size(), 1); 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(), 1); 332 checkData(Point, Intervals[0], 30, 40, 3040); 333 334 Point = 35; 335 Intervals = Tree.getContaining(Point); 336 ASSERT_EQ(Intervals.size(), 1); 337 checkData(Point, Intervals[0], 30, 40, 3040); 338 339 Point = 40; 340 Intervals = Tree.getContaining(Point); 341 ASSERT_EQ(Intervals.size(), 1); 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(), 1); 353 checkData(Point, Intervals[0], 50, 60, 5060); 354 355 Point = 55; 356 Intervals = Tree.getContaining(Point); 357 ASSERT_EQ(Intervals.size(), 1); 358 checkData(Point, Intervals[0], 50, 60, 5060); 359 360 Point = 60; 361 Intervals = Tree.getContaining(Point); 362 ASSERT_EQ(Intervals.size(), 1); 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(), 1); 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(), 1); 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(), 2); 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(), 1); 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(), 1); 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(), 1); 479 checkData(Point, Intervals[0], 10, 90, 1090); 480 481 Point = 15; 482 Intervals = Tree.getContaining(Point); 483 ASSERT_EQ(Intervals.size(), 1); 484 checkData(Point, Intervals[0], 10, 90, 1090); 485 486 Point = 20; 487 Intervals = Tree.getContaining(Point); 488 ASSERT_EQ(Intervals.size(), 2); 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(), 2); 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(), 2); 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(), 2); 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(), 2); 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(), 2); 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(), 3); 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(), 3); 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(), 3); 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(), 3); 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(), 3); 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(), 3); 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(), 4); 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(), 4); 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(), 4); 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(), 4); 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(), 4); 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(), 4); 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(), 4); 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(), 4); 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(), 4); 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(), 3); 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(), 3); 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(), 3); 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(), 3); 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(), 3); 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(), 3); 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(), 2); 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(), 2); 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(), 2); 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(), 2); 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(), 2); 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(), 2); 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(), 1); 695 checkData(Point, Intervals[0], 10, 90, 1090); 696 697 Point = 90; 698 Intervals = Tree.getContaining(Point); 699 ASSERT_EQ(Intervals.size(), 1); 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(), 5); 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(), 5); 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(), 5); 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(), 5); 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(), 5); 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(), 5); 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(), 6); 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(), 6); 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(), 6); 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(), 6); 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(), 6); 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(), 6); 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(), 5); 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(), 5); 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(), 5); 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(), 5); 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(), 5); 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(), 5); 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(), 5); 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(), 5); 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(), 5); 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(), 5); 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(), 5); 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(), 5); 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(), 3); 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(), 3); 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(), 3); 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(), 4); 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(), 4); 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(), 4); 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(), 4); 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(), 4); 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(), 4); 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(), 5); 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(), 5); 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(), 5); 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(), 5); 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(), 5); 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(), 5); 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(), 4); 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(), 4); 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(), 4); 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(), 3); 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(), 3); 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(), 3); 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(), 3); 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(), 3); 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(), 3); 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(), 2); 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(), 2); 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(), 2); 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(), 4); 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(), 4); 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(), 4); 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(), 4); 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(), 4); 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(), 4); 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(), 5); 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(), 5); 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(), 5); 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(), 5); 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(), 5); 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(), 5); 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(), 5); 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(), 5); 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(), 5); 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(), 5); 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(), 5); 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(), 5); 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(), 3); 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(), 3); 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(), 3); 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(), 4); 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(), 4); 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(), 4); 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(), 2); 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(), 2); 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(), 2); 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(), 4); 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(), 4); 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(), 4); 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(), 6); 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(), 6); 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(), 6); 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(), 5); 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(), 5); 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(), 5); 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(), 5); 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(), 5); 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(), 5); 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(), 6); 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(), 6); 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(), 6); 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(), 4); 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(), 4); 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(), 4); 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(), 1); 1509 checkData(Point, Intervals[0], 10, 85, 1085); 1510 1511 Point = 85; 1512 Intervals = Tree.getContaining(Point); 1513 ASSERT_EQ(Intervals.size(), 1); 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 1608