Aleph-w 3.0
A C++ Library for Data Structures and Algorithms
Loading...
Searching...
No Matches
interval_tree_test.cc
Go to the documentation of this file.
1/*
2 Aleph_w
3
4 Data structures & Algorithms
5 version 2.0.0b
6 https://github.com/lrleon/Aleph-w
7
8 This file is part of Aleph-w library
9
10 Copyright (c) 2002-2026 Leandro Rabindranath Leon
11
12 Permission is hereby granted, free of charge, to any person obtaining a copy
13 of this software and associated documentation files (the "Software"), to deal
14 in the Software without restriction, including without limitation the rights
15 to use, copy, modify, merge, publish, distribute, sublicense, and/or sell
16 copies of the Software, and to permit persons to whom the Software is
17 furnished to do so, subject to the following conditions:
18
19 The above copyright notice and this permission notice shall be included in all
20 copies or substantial portions of the Software.
21
22 THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
23 IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
24 FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE
25 AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
26 LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM,
27 OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE
28 SOFTWARE.
29*/
30
31
37# include <gtest/gtest.h>
38# include <tpl_interval_tree.H>
39# include <random>
40# include <algorithm>
41# include <string>
42# include <vector>
43# include <type_traits>
44
45using namespace Aleph;
46using namespace testing;
47
48static_assert(not std::is_copy_constructible_v<Interval_Tree<int>>);
49static_assert(not std::is_copy_assignable_v<Interval_Tree<int>>);
50static_assert(not std::is_move_constructible_v<Interval_Tree<int>>);
51static_assert(not std::is_move_assignable_v<Interval_Tree<int>>);
52
53struct CountingLess
54{
55 int *counter;
56
57 explicit CountingLess(int *c = nullptr) noexcept : counter(c) {}
58
59 bool operator ()(const int &a, const int &b) const noexcept
60 {
61 if (counter != nullptr)
62 ++*counter;
63 return a < b;
64 }
65};
66
67// ─────────────────────────────────────────────────────────────────
68// Interval<T> value type tests
69// ─────────────────────────────────────────────────────────────────
70
71class IntervalTypeTest : public Test {};
72
73TEST_F(IntervalTypeTest, Construction)
74{
75 Interval<int> a(1, 5);
76 EXPECT_EQ(a.low, 1);
77 EXPECT_EQ(a.high, 5);
78
79 auto pt = Interval<int>::point(3);
80 EXPECT_EQ(pt.low, 3);
81 EXPECT_EQ(pt.high, 3);
82}
83
84TEST_F(IntervalTypeTest, Validity)
85{
86 Interval<int> valid(1, 5);
87 EXPECT_TRUE(valid.is_valid());
88
89 Interval<int> point(3, 3);
90 EXPECT_TRUE(point.is_valid());
91
92 Interval<int> invalid(5, 1);
93 EXPECT_FALSE(invalid.is_valid());
94}
95
96TEST_F(IntervalTypeTest, OverlapDetection)
97{
98 Interval<int> a(1, 5);
99 Interval<int> b(3, 7);
100 Interval<int> c(6, 10);
101 Interval<int> d(1, 5);
102 Interval<int> e(10, 15);
103
104 EXPECT_TRUE(a.overlaps(b)); // partial overlap
105 EXPECT_FALSE(a.overlaps(c)); // a.high=5 < c.low=6
106 EXPECT_TRUE(a.overlaps(d)); // identical
107 EXPECT_FALSE(a.overlaps(e)); // disjoint
108
109 // touching endpoints count as overlap for closed intervals
110 Interval<int> f(5, 10);
111 EXPECT_TRUE(a.overlaps(f));
112}
113
123
124TEST_F(IntervalTypeTest, PointIntervals)
125{
126 auto pt = Interval<int>::point(5);
127 EXPECT_TRUE(pt.is_valid());
128 EXPECT_TRUE(pt.contains(5));
129 EXPECT_FALSE(pt.contains(4));
130 EXPECT_FALSE(pt.contains(6));
131
132 Interval<int> a(3, 7);
133 EXPECT_TRUE(pt.overlaps(a));
134
135 Interval<int> b(6, 10);
136 EXPECT_FALSE(pt.overlaps(b));
137}
138
139TEST_F(IntervalTypeTest, Ordering)
140{
141 Interval_Less<int> cmp;
142 Interval<int> a(1, 5);
143 Interval<int> b(2, 3);
144 Interval<int> c(1, 7);
145
146 EXPECT_TRUE(cmp(a, b)); // 1 < 2
147 EXPECT_FALSE(cmp(b, a));
148 EXPECT_TRUE(cmp(a, c)); // same low, 5 < 7
149 EXPECT_FALSE(cmp(c, a));
150 EXPECT_FALSE(cmp(a, a)); // irreflexive
151}
152
153// ─────────────────────────────────────────────────────────────────
154// Low-level Interval_Tree tests
155// ─────────────────────────────────────────────────────────────────
156
157class IntervalTreeRawTest : public Test
158{
159protected:
160 using IvTree = Interval_Tree<int>;
161 using Node = IvTree::Node;
162 using Key = Interval<int>;
163
164 IvTree tree;
165
166 void SetUp() override { tree.set_seed(42); }
167
168 void TearDown() override
169 {
170 destroyRec(tree.getRoot());
171 }
172
173 Node * make_node(int lo, int hi)
174 {
175 return new Node(Key(lo, hi));
176 }
177};
178
179TEST_F(IntervalTreeRawTest, EmptyTree)
180{
181 EXPECT_TRUE(tree.is_empty());
182 EXPECT_EQ(tree.size(), 0u);
183 EXPECT_TRUE(tree.verify());
184 EXPECT_EQ(tree.search(Key(0, 0)), nullptr);
185 EXPECT_EQ(tree.overlap_search(Key(0, 10)), nullptr);
186}
187
188TEST_F(IntervalTreeRawTest, SingleInsert)
189{
190 auto * p = make_node(1, 5);
191 EXPECT_NE(tree.insert(p), nullptr);
192 EXPECT_EQ(tree.size(), 1u);
193 EXPECT_TRUE(tree.verify());
194 EXPECT_NE(tree.search(Key(1, 5)), nullptr);
195}
196
197TEST_F(IntervalTreeRawTest, MultipleInserts)
198{
199 tree.insert(make_node(15, 20));
200 tree.insert(make_node(10, 30));
201 tree.insert(make_node(17, 19));
202 tree.insert(make_node(5, 20));
203 tree.insert(make_node(12, 15));
204 tree.insert(make_node(30, 40));
205
206 EXPECT_EQ(tree.size(), 6u);
207 EXPECT_TRUE(tree.verify());
208}
209
210TEST_F(IntervalTreeRawTest, DuplicateInsert)
211{
212 auto * p1 = make_node(1, 5);
213 auto * p2 = make_node(1, 5);
214 EXPECT_NE(tree.insert(p1), nullptr);
215 EXPECT_EQ(tree.insert(p2), nullptr);
216 EXPECT_EQ(tree.size(), 1u);
217 EXPECT_TRUE(tree.verify());
218 delete p2;
219}
220
221TEST_F(IntervalTreeRawTest, InsertDup)
222{
223 auto * p1 = make_node(1, 5);
224 auto * p2 = make_node(1, 5);
225 tree.insert_dup(p1);
226 tree.insert_dup(p2);
227 EXPECT_EQ(tree.size(), 2u);
228 EXPECT_TRUE(tree.verify());
229}
230
231TEST_F(IntervalTreeRawTest, Remove)
232{
233 tree.insert(make_node(1, 5));
234 tree.insert(make_node(10, 20));
235 tree.insert(make_node(3, 7));
236
237 EXPECT_EQ(tree.size(), 3u);
238 EXPECT_TRUE(tree.verify());
239
240 auto * removed = tree.remove(Key(10, 20));
241 EXPECT_NE(removed, nullptr);
242 EXPECT_EQ(tree.size(), 2u);
243 EXPECT_TRUE(tree.verify());
244 delete removed;
245}
246
247TEST_F(IntervalTreeRawTest, RemoveNonexistent)
248{
249 tree.insert(make_node(1, 5));
250 auto * removed = tree.remove(Key(99, 100));
251 EXPECT_EQ(removed, nullptr);
252 EXPECT_EQ(tree.size(), 1u);
253 EXPECT_TRUE(tree.verify());
254}
255
256TEST_F(IntervalTreeRawTest, OverlapSearchFound)
257{
258 tree.insert(make_node(15, 20));
259 tree.insert(make_node(10, 30));
260 tree.insert(make_node(17, 19));
261 tree.insert(make_node(5, 20));
262 tree.insert(make_node(12, 15));
263 tree.insert(make_node(30, 40));
264
265 auto * result = tree.overlap_search(Key(14, 16));
266 ASSERT_NE(result, nullptr);
267 EXPECT_TRUE(KEY(result).overlaps(Key(14, 16)));
268}
269
270TEST_F(IntervalTreeRawTest, OverlapSearchNotFound)
271{
272 tree.insert(make_node(1, 5));
273 tree.insert(make_node(10, 15));
274 tree.insert(make_node(20, 25));
275
276 auto * result = tree.overlap_search(Key(6, 9));
277 EXPECT_EQ(result, nullptr);
278}
279
280TEST_F(IntervalTreeRawTest, AllOverlaps)
281{
282 tree.insert(make_node(1, 5));
283 tree.insert(make_node(3, 8));
284 tree.insert(make_node(7, 10));
285 tree.insert(make_node(15, 20));
286
287 DynList<Key> results;
288 tree.all_overlaps(Key(4, 7), [&results](const Key & iv) {
289 results.append(iv);
290 });
291
292 // [1,5] overlaps [4,7]: yes (5>=4 and 1<=7)
293 // [3,8] overlaps [4,7]: yes
294 // [7,10] overlaps [4,7]: yes (7<=7)
295 // [15,20] overlaps [4,7]: no
296 EXPECT_EQ(results.size(), 3u);
297}
298
299TEST_F(IntervalTreeRawTest, StabQuery)
300{
301 tree.insert(make_node(1, 5));
302 tree.insert(make_node(3, 8));
303 tree.insert(make_node(7, 10));
304 tree.insert(make_node(15, 20));
305
306 auto results = tree.find_stab(4);
307 // [1,5] contains 4: yes
308 // [3,8] contains 4: yes
309 // [7,10] contains 4: no
310 // [15,20] contains 4: no
311 EXPECT_EQ(results.size(), 2u);
312}
313
314TEST_F(IntervalTreeRawTest, PointIntervalQueries)
315{
316 tree.insert(make_node(5, 5));
317 tree.insert(make_node(3, 7));
318
319 auto * result = tree.overlap_search(Key(5, 5));
320 ASSERT_NE(result, nullptr);
321 EXPECT_TRUE(KEY(result).overlaps(Key(5, 5)));
322}
323
324TEST_F(IntervalTreeRawTest, MaxEndpointInvariant)
325{
326 tree.insert(make_node(1, 10));
327 EXPECT_TRUE(tree.verify());
328
329 tree.insert(make_node(5, 20));
330 EXPECT_TRUE(tree.verify());
331
332 tree.insert(make_node(15, 25));
333 EXPECT_TRUE(tree.verify());
334
335 auto * r1 = tree.remove(Key(5, 20));
336 EXPECT_TRUE(tree.verify());
337 delete r1;
338
339 auto * r2 = tree.remove(Key(1, 10));
340 EXPECT_TRUE(tree.verify());
341 delete r2;
342}
343
344TEST_F(IntervalTreeRawTest, IteratorOrdering)
345{
346 tree.insert(make_node(10, 20));
347 tree.insert(make_node(5, 15));
348 tree.insert(make_node(1, 3));
349 tree.insert(make_node(20, 30));
350
351 Interval_Less<int> cmp;
352 Key prev_key;
353 bool first = true;
354 for (IvTree::Iterator it(tree); it.has_curr(); it.next())
355 {
356 Key k = KEY(it.get_curr());
357 if (not first)
358 EXPECT_TRUE(cmp(prev_key, k) or (not cmp(k, prev_key) and not cmp(prev_key, k)));
359 prev_key = k;
360 first = false;
361 }
362}
363
364TEST_F(IntervalTreeRawTest, CLRSTextbookExample)
365{
366 // CLRS 3rd ed, Figure 14.4 intervals
367 tree.insert(make_node(0, 3));
368 tree.insert(make_node(5, 8));
369 tree.insert(make_node(6, 10));
370 tree.insert(make_node(8, 9));
371 tree.insert(make_node(15, 23));
372 tree.insert(make_node(16, 21));
373 tree.insert(make_node(17, 19));
374 tree.insert(make_node(19, 20));
375 tree.insert(make_node(25, 30));
376 tree.insert(make_node(26, 26));
377
378 EXPECT_EQ(tree.size(), 10u);
379 EXPECT_TRUE(tree.verify());
380
381 // Query [22, 25]: should overlap [15,23] and [25,30]
382 auto overlaps = tree.find_all_overlaps(Key(22, 25));
383 EXPECT_GE(overlaps.size(), 2u);
384 overlaps.for_each([](const Key & iv) {
385 EXPECT_TRUE(iv.overlaps(Key(22, 25)));
386 });
387
388 // Query [11, 14]: should not overlap anything
389 auto * result = tree.overlap_search(Key(11, 14));
390 EXPECT_EQ(result, nullptr);
391}
392
393TEST_F(IntervalTreeRawTest, LargeRandomizedVerification)
394{
395 std::mt19937 gen(12345);
396 std::uniform_int_distribution<int> dist(0, 10000);
397
398 const size_t N = 5000;
399 std::vector<Key> intervals;
400 intervals.reserve(N);
401
402 for (size_t i = 0; i < N; ++i)
403 {
404 int a = dist(gen), b = dist(gen);
405 if (a > b) std::swap(a, b);
406 tree.insert_dup(make_node(a, b));
407 intervals.push_back(Key(a, b));
408 }
409
410 EXPECT_EQ(tree.size(), N);
411 EXPECT_TRUE(tree.verify());
412
413 // Verify overlap_search against brute force for a sample of queries
414 for (int q = 0; q < 100; ++q)
415 {
416 int a = dist(gen), b = dist(gen);
417 if (a > b) std::swap(a, b);
418 Key query(a, b);
419
420 auto * found = tree.overlap_search(query);
421 bool brute_force_found = false;
422 for (const auto & iv : intervals)
423 if (iv.overlaps(query))
424 {
425 brute_force_found = true;
426 break;
427 }
428
429 if (brute_force_found)
430 EXPECT_NE(found, nullptr) << "BF found overlap for ["
431 << a << "," << b << "] but tree didn't";
432 else
433 EXPECT_EQ(found, nullptr) << "BF found no overlap for ["
434 << a << "," << b << "] but tree did";
435 }
436}
437
438// ─────────────────────────────────────────────────────────────────
439// DynIntervalTree tests
440// ─────────────────────────────────────────────────────────────────
441
442class DynIntervalTreeTest : public Test
443{
444protected:
445 using Key = Interval<int>;
446 DynIntervalTree<int> tree;
447};
448
449TEST_F(DynIntervalTreeTest, Construction)
450{
451 EXPECT_TRUE(tree.is_empty());
452 EXPECT_EQ(tree.size(), 0u);
453 EXPECT_TRUE(tree.empty());
454 EXPECT_TRUE(tree.verify());
455}
456
457TEST_F(DynIntervalTreeTest, InsertAndSearch)
458{
459 tree.insert(Key(1, 5));
460 tree.insert(Key(10, 20));
461 EXPECT_EQ(tree.size(), 2u);
462 EXPECT_TRUE(tree.verify());
463
464 auto * found = tree.search(Key(1, 5));
465 ASSERT_NE(found, nullptr);
466 EXPECT_EQ(found->low, 1);
467 EXPECT_EQ(found->high, 5);
468
469 EXPECT_EQ(tree.search(Key(2, 3)), nullptr);
470}
471
472TEST_F(DynIntervalTreeTest, InsertByEndpoints)
473{
474 tree.insert(1, 5);
475 tree.insert(10, 20);
476 EXPECT_EQ(tree.size(), 2u);
477 EXPECT_TRUE(tree.verify());
478}
479
480TEST_F(DynIntervalTreeTest, Remove)
481{
482 tree.insert(Key(1, 5));
483 tree.insert(Key(10, 20));
484 tree.insert(Key(3, 7));
485
486 EXPECT_TRUE(tree.remove(Key(10, 20)));
487 EXPECT_EQ(tree.size(), 2u);
488 EXPECT_TRUE(tree.verify());
489 EXPECT_EQ(tree.search(Key(10, 20)), nullptr);
490}
491
492TEST_F(DynIntervalTreeTest, RemoveByEndpoints)
493{
494 tree.insert(1, 5);
495 EXPECT_TRUE(tree.remove(1, 5));
496 EXPECT_TRUE(tree.is_empty());
497}
498
499TEST_F(DynIntervalTreeTest, RemoveNonexistent)
500{
501 tree.insert(Key(1, 5));
502 EXPECT_FALSE(tree.remove(Key(99, 100)));
503 EXPECT_EQ(tree.size(), 1u);
504}
505
506TEST_F(DynIntervalTreeTest, InvalidIntervalThrows)
507{
508 EXPECT_THROW(tree.insert(Key(5, 1)), std::domain_error);
509 EXPECT_TRUE(tree.is_empty());
510}
511
512TEST_F(DynIntervalTreeTest, OverlapSearch)
513{
514 tree.insert(Key(1, 5));
515 tree.insert(Key(10, 15));
516 tree.insert(Key(20, 25));
517
518 auto * result = tree.overlap_search(Key(4, 11));
519 ASSERT_NE(result, nullptr);
520 EXPECT_TRUE(result->overlaps(Key(4, 11)));
521
522 EXPECT_EQ(tree.overlap_search(Key(6, 9)), nullptr);
523}
524
525TEST_F(DynIntervalTreeTest, OverlapSearchByEndpoints)
526{
527 tree.insert(Key(1, 5));
528 auto * result = tree.overlap_search(3, 4);
529 ASSERT_NE(result, nullptr);
530}
531
532TEST_F(DynIntervalTreeTest, AllOverlaps)
533{
534 tree.insert(Key(1, 5));
535 tree.insert(Key(3, 8));
536 tree.insert(Key(7, 10));
537 tree.insert(Key(15, 20));
538
539 auto results = tree.find_all_overlaps(Key(4, 7));
540 EXPECT_EQ(results.size(), 3u);
541
542 results.for_each([](const Key & iv) {
543 EXPECT_TRUE(iv.overlaps(Key(4, 7)));
544 });
545}
546
547TEST_F(DynIntervalTreeTest, FindAllOverlapsByEndpoints)
548{
549 tree.insert(Key(1, 5));
550 tree.insert(Key(3, 8));
551 auto results = tree.find_all_overlaps(2, 4);
552 EXPECT_EQ(results.size(), 2u);
553}
554
555TEST_F(DynIntervalTreeTest, Stab)
556{
557 tree.insert(Key(1, 5));
558 tree.insert(Key(3, 8));
559 tree.insert(Key(7, 10));
560
561 size_t count = 0;
562 tree.stab(4, [&count](const Key &) { ++count; });
563 EXPECT_EQ(count, 2u);
564}
565
566TEST_F(DynIntervalTreeTest, FindStab)
567{
568 tree.insert(Key(1, 10));
569 tree.insert(Key(5, 15));
570 tree.insert(Key(20, 25));
571
572 auto results = tree.find_stab(7);
573 EXPECT_EQ(results.size(), 2u);
574
575 results = tree.find_stab(20);
576 EXPECT_EQ(results.size(), 1u);
577
578 results = tree.find_stab(16);
579 EXPECT_EQ(results.size(), 0u);
580}
581
582TEST_F(DynIntervalTreeTest, CopyConstruction)
583{
584 tree.insert(Key(1, 5));
585 tree.insert(Key(10, 20));
586 tree.insert(Key(3, 7));
587
588 DynIntervalTree<int> copy(tree);
589 EXPECT_EQ(copy.size(), 3u);
590 EXPECT_TRUE(copy.verify());
591 EXPECT_NE(copy.search(Key(1, 5)), nullptr);
592 EXPECT_NE(copy.search(Key(10, 20)), nullptr);
593 EXPECT_NE(copy.search(Key(3, 7)), nullptr);
594}
595
596TEST_F(DynIntervalTreeTest, MoveConstruction)
597{
598 tree.insert(Key(1, 5));
599 tree.insert(Key(10, 20));
600
601 DynIntervalTree<int> moved(std::move(tree));
602 EXPECT_EQ(moved.size(), 2u);
603 EXPECT_TRUE(moved.verify());
604 EXPECT_TRUE(tree.is_empty());
605}
606
607TEST_F(DynIntervalTreeTest, CopyAssignment)
608{
609 tree.insert(Key(1, 5));
610 tree.insert(Key(10, 20));
611
612 DynIntervalTree<int> other;
613 other.insert(Key(100, 200));
614
615 other = tree;
616 EXPECT_EQ(other.size(), 2u);
617 EXPECT_TRUE(other.verify());
618}
619
620TEST_F(DynIntervalTreeTest, MoveAssignment)
621{
622 tree.insert(Key(1, 5));
623 tree.insert(Key(10, 20));
624
625 DynIntervalTree<int> other;
626 other = std::move(tree);
627 EXPECT_EQ(other.size(), 2u);
628 EXPECT_TRUE(other.verify());
629 EXPECT_TRUE(tree.is_empty());
630}
631
632TEST(IntervalTreeComparatorStateTest, CopyAssignmentPropagatesComparatorState)
633{
634 int left_counter = 0;
635 int right_counter = 0;
636
637 DynIntervalTree<int, CountingLess> left{CountingLess(&left_counter)};
638 DynIntervalTree<int, CountingLess> right{CountingLess(&right_counter)};
639
640 left.insert(Interval<int>(1, 3));
641 right.insert(Interval<int>(10, 20));
642
643 left = right;
644
645 left_counter = 0;
646 right_counter = 0;
647
648 const auto *found = left.search(Interval<int>(10, 20));
649 ASSERT_NE(found, nullptr);
650 EXPECT_EQ(left_counter, 0);
651 EXPECT_GT(right_counter, 0);
652}
653
654TEST_F(DynIntervalTreeTest, FunctionalForEach)
655{
656 tree.insert(Key(1, 5));
657 tree.insert(Key(10, 20));
658 tree.insert(Key(3, 7));
659
660 size_t count = 0;
661 tree.for_each([&count](const Key &) { ++count; });
662 EXPECT_EQ(count, 3u);
663}
664
665TEST_F(DynIntervalTreeTest, FunctionalExists)
666{
667 tree.insert(Key(1, 5));
668 tree.insert(Key(10, 20));
669
670 EXPECT_TRUE(tree.exists([](const Key & iv) { return iv.low == 10; }));
671 EXPECT_FALSE(tree.exists([](const Key & iv) { return iv.low == 99; }));
672}
673
674TEST_F(DynIntervalTreeTest, FunctionalFilter)
675{
676 tree.insert(Key(1, 5));
677 tree.insert(Key(10, 20));
678 tree.insert(Key(3, 7));
679
680 auto wide = tree.filter([](const Key & iv) {
681 return (iv.high - iv.low) >= 5;
682 });
683 EXPECT_EQ(wide.size(), 1u); // [1,5] has width 4, [10,20] has 10, [3,7] has 4
684}
685
686TEST_F(DynIntervalTreeTest, InitializerList)
687{
688 DynIntervalTree<int> t = {Key(1, 5), Key(10, 20), Key(3, 7)};
689 EXPECT_EQ(t.size(), 3u);
690 EXPECT_TRUE(t.verify());
691}
692
693TEST_F(DynIntervalTreeTest, Verify)
694{
695 tree.insert(Key(1, 5));
696 tree.insert(Key(10, 20));
697 tree.insert(Key(3, 7));
698 tree.insert(Key(25, 30));
699 tree.insert(Key(0, 2));
700
701 EXPECT_TRUE(tree.verify());
702}
703
704TEST_F(DynIntervalTreeTest, StlRangeFor)
705{
706 tree.insert(Key(1, 5));
707 tree.insert(Key(10, 20));
708 tree.insert(Key(3, 7));
709
710 size_t count = 0;
711 for (const auto & iv : tree)
712 {
713 EXPECT_TRUE(iv.is_valid());
714 ++count;
715 }
716 EXPECT_EQ(count, 3u);
717}
718
719// ─────────────────────────────────────────────────────────────────
720// Type tests
721// ─────────────────────────────────────────────────────────────────
722
723TEST(IntervalTreeTypeTest, IntIntervals)
724{
725 DynIntervalTree<int> tree;
726 tree.insert(Interval<int>(1, 5));
727 tree.insert(Interval<int>(3, 8));
728
729 auto * result = tree.overlap_search(Interval<int>(4, 6));
730 ASSERT_NE(result, nullptr);
731 EXPECT_TRUE(tree.verify());
732}
733
734TEST(IntervalTreeTypeTest, DoubleIntervals)
735{
736 DynIntervalTree<double> tree;
737 tree.insert(Interval<double>(1.0, 5.5));
738 tree.insert(Interval<double>(3.2, 8.1));
739 tree.insert(Interval<double>(10.0, 20.0));
740
741 EXPECT_EQ(tree.size(), 3u);
742 EXPECT_TRUE(tree.verify());
743
744 auto * result = tree.overlap_search(Interval<double>(4.0, 6.0));
745 ASSERT_NE(result, nullptr);
746 EXPECT_TRUE(result->overlaps(Interval<double>(4.0, 6.0)));
747
748 EXPECT_EQ(tree.overlap_search(Interval<double>(8.2, 9.9)), nullptr);
749}
750
751TEST(IntervalTreeTypeTest, StringIntervals)
752{
753 DynIntervalTree<std::string> tree;
754 tree.insert(Interval<std::string>("apple", "cherry"));
755 tree.insert(Interval<std::string>("banana", "grape"));
756 tree.insert(Interval<std::string>("mango", "peach"));
757
758 EXPECT_EQ(tree.size(), 3u);
759 EXPECT_TRUE(tree.verify());
760
761 auto * result = tree.overlap_search(
762 Interval<std::string>("blueberry", "cantaloupe"));
763 ASSERT_NE(result, nullptr);
764}
765
766// ─────────────────────────────────────────────────────────────────
767// Stress test: insertions + removals + queries stay consistent
768// ─────────────────────────────────────────────────────────────────
769
770TEST(IntervalTreeStressTest, InsertRemoveVerify)
771{
772 DynIntervalTree<int> tree;
773 std::mt19937 gen(54321);
774 std::uniform_int_distribution<int> dist(0, 1000);
775
776 DynList<Interval<int>> inserted;
777
778 // Insert 1000 intervals
779 for (int i = 0; i < 1000; ++i)
780 {
781 int a = dist(gen), b = dist(gen);
782 if (a > b) std::swap(a, b);
783 Interval<int> iv(a, b);
784 tree.insert_dup(iv);
785 inserted.append(iv);
786 }
787
788 EXPECT_EQ(tree.size(), 1000u);
789 EXPECT_TRUE(tree.verify());
790
791 // Remove half
792 size_t removed = 0;
793 DynList<Interval<int>> remaining;
794 inserted.for_each([&](const Interval<int> & iv) {
795 if (removed < 500)
796 {
797 tree.remove(iv);
798 ++removed;
799 }
800 else
801 remaining.append(iv);
802 });
803
804 EXPECT_TRUE(tree.verify());
805
806 // Verify remaining intervals are still findable
807 remaining.for_each([&](const Interval<int> & iv) {
808 auto * found = tree.search(iv);
809 EXPECT_NE(found, nullptr)
810 << "Lost interval [" << iv.low << "," << iv.high << "]";
811 });
812}
813
814TEST(IntervalTreeStressTest, AllOverlapsBruteForce)
815{
816 std::mt19937 gen(99999);
817 std::uniform_int_distribution<int> dist(0, 100);
818
819 DynIntervalTree<int> tree;
820 std::vector<Interval<int>> intervals;
821
822 for (int i = 0; i < 200; ++i)
823 {
824 int a = dist(gen), b = dist(gen);
825 if (a > b) std::swap(a, b);
826 Interval<int> iv(a, b);
827 tree.insert_dup(iv);
828 intervals.push_back(iv);
829 }
830
831 EXPECT_TRUE(tree.verify());
832
833 // Compare all_overlaps against brute force
834 for (int q = 0; q < 50; ++q)
835 {
836 int a = dist(gen), b = dist(gen);
837 if (a > b) std::swap(a, b);
838 Interval<int> query(a, b);
839
840 auto tree_results = tree.find_all_overlaps(query);
841
842 size_t bf_count = 0;
843 for (const auto & iv : intervals)
844 if (iv.overlaps(query))
845 ++bf_count;
846
847 EXPECT_EQ(tree_results.size(), bf_count)
848 << "Mismatch for query [" << a << "," << b << "]";
849 }
850}
KEY
@ KEY
Definition btreepic.C:169
Aleph::DynIntervalTree
High-level interval tree with automatic memory management.
Definition tpl_interval_tree.H:1035
Aleph::DynIntervalTree::find_all_overlaps
DynList< Key > find_all_overlaps(const Key &query) const
Find all overlapping intervals.
Definition tpl_interval_tree.H:1289
Aleph::DynIntervalTree::insert_dup
Key & insert_dup(const Key &iv)
Insert interval, allowing duplicates.
Definition tpl_interval_tree.H:1196
Aleph::DynIntervalTree::insert
Key & insert(const Key &iv)
Insert an interval (unique).
Definition tpl_interval_tree.H:1145
Aleph::DynIntervalTree::overlap_search
const Key * overlap_search(const Key &query) const
Find any interval overlapping query.
Definition tpl_interval_tree.H:1255
Aleph::DynIntervalTree::verify
bool verify() const
Verify all tree invariants (BST, Treap, MaxEndpoint).
Definition tpl_interval_tree.H:1347
Aleph::DynIntervalTree::size
size_t size() const noexcept
Return the number of intervals in the tree.
Definition tpl_interval_tree.H:1330
Aleph::DynIntervalTree::remove
bool remove(const Key &iv)
Remove an interval from the tree.
Definition tpl_interval_tree.H:1217
Aleph::DynIntervalTree::search
const Key * search(const Key &iv) const noexcept
Search for an exact interval.
Definition tpl_interval_tree.H:1243
Aleph::DynList
Dynamic singly linked list with functional programming support.
Definition htlist.H:1155
Aleph::DynList::append
T & append(const T &item)
Definition htlist.H:1271
Aleph::Gen_Interval_Tree::Node
NodeType< Key > Node
Definition tpl_interval_tree.H:518
Aleph::Gen_Interval_Tree::set_seed
void set_seed(const unsigned long seed) noexcept
Set the random number generator seed.
Definition tpl_interval_tree.H:732
Aleph::Gen_Interval_Tree::getRoot
Node *& getRoot() noexcept
Return the tree's root.
Definition tpl_interval_tree.H:798
DynIntervalTreeTest::tree
DynIntervalTree< int > tree
Definition interval_tree_test.cc:446
FunctionalMethods::for_each
void for_each(Operation &operation)
Traverse all the container and performs an operation on each element.
Definition ah-dry.H:779
IntervalTreeRawTest::make_node
Node * make_node(int lo, int hi)
Definition interval_tree_test.cc:173
TEST
#define TEST(name)
Definition disjoint_sparse_table_test.cc:95
N
#define N
Definition fib.C:294
cmp
int cmp(const __gmp_expr< T, U > &expr1, const __gmp_expr< V, W > &expr2)
Definition gmpfrxx.h:4118
Aleph::destroyRec
void destroyRec(Node *&root) noexcept
Free recursively all the memory occupied by the tree root
Definition tpl_binNodeUtils.H:524
TEST_F
TEST_F(IntervalTypeTest, Construction)
Definition interval_tree_test.cc:73
Aleph
Main namespace for Aleph-w library functions.
Definition ah-arena.H:89
Aleph::and
and
Check uniqueness with explicit hash + equality functors.
Definition ahFunctional.H:2594
Aleph::copy
Itor2 copy(Itor1 sourceBeg, const Itor1 &sourceEnd, Itor2 destBeg)
Copy elements from one range to another.
Definition ahAlgo.H:584
Aleph::divide_and_conquer_partition_dp
Divide_Conquer_DP_Result< Cost > divide_and_conquer_partition_dp(const size_t groups, const size_t n, Transition_Cost_Fn transition_cost, const Cost inf=dp_optimization_detail::default_inf< Cost >())
Optimize partition DP using divide-and-conquer optimization.
Definition DP_Optimizations.H:133
Aleph::count
Itor::difference_type count(const Itor &beg, const Itor &end, const T &value)
Count elements equal to a value.
Definition ahAlgo.H:127
Aleph::Interval_Less
BST comparator for intervals: order by (low, then high).
Definition tpl_interval_tree.H:206
Aleph::Interval_Tree< int >
Aleph::Interval
Closed interval [low, high].
Definition tpl_interval_tree.H:91
Aleph::Interval::point
static Interval point(const T &p) noexcept(std::is_nothrow_copy_constructible_v< T >)
Construct a point interval [p, p].
Definition tpl_interval_tree.H:125
Aleph::Interval::contains
bool contains(const T &p, const Compare &cmp=Compare()) const noexcept(std::is_nothrow_invocable_v< const Compare &, const T &, const T & >)
Return true if this interval contains the point p.
Definition tpl_interval_tree.H:155
Aleph::Interval::is_valid
bool is_valid(const Compare &cmp=Compare()) const noexcept(std::is_nothrow_invocable_v< const Compare &, const T &, const T & >)
Return true if low <= high.
Definition tpl_interval_tree.H:169
Aleph::Interval::overlaps
bool overlaps(const Interval &other, const Compare &cmp=Compare()) const noexcept(std::is_nothrow_invocable_v< const Compare &, const T &, const T & >)
Return true if this interval overlaps with other.
Definition tpl_interval_tree.H:139
Aleph::Interval::low
T low
Lower endpoint.
Definition tpl_interval_tree.H:92
Aleph::Interval::high
T high
Upper endpoint.
Definition tpl_interval_tree.H:93
CountingLess::CountingLess
CountingLess(int *c=nullptr) noexcept
Definition interval_tree_test.cc:57
CountingLess::operator()
bool operator()(const int &a, const int &b) const noexcept
Definition interval_tree_test.cc:59
Test
Dnode< int > Test
Definition testDnode.C:37
k
static int * k
Definition testOpBinTree.C:49
tpl_interval_tree.H
Interval tree: augmented BST for overlap/stabbing queries.