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