1 //===---- ADT/IntervalMapTest.cpp - IntervalMap unit tests ------*- C++ -*-===//
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/IntervalMap.h"
10 #include "gtest/gtest.h"
11 #include <type_traits>
12
13 using namespace llvm;
14
15 namespace {
16
17 typedef IntervalMap<unsigned, unsigned, 4> UUMap;
18 typedef IntervalMap<unsigned, unsigned, 4,
19 IntervalMapHalfOpenInfo<unsigned>> UUHalfOpenMap;
20
21 // Empty map tests
TEST(IntervalMapTest,EmptyMap)22 TEST(IntervalMapTest, EmptyMap) {
23 UUMap::Allocator allocator;
24 UUMap map(allocator);
25 EXPECT_TRUE(map.empty());
26
27 // Lookup on empty map.
28 EXPECT_EQ(0u, map.lookup(0));
29 EXPECT_EQ(7u, map.lookup(0, 7));
30 EXPECT_EQ(0u, map.lookup(~0u-1));
31 EXPECT_EQ(7u, map.lookup(~0u-1, 7));
32
33 // Iterators.
34 EXPECT_TRUE(map.begin() == map.begin());
35 EXPECT_TRUE(map.begin() == map.end());
36 EXPECT_TRUE(map.end() == map.end());
37 EXPECT_FALSE(map.begin() != map.begin());
38 EXPECT_FALSE(map.begin() != map.end());
39 EXPECT_FALSE(map.end() != map.end());
40 EXPECT_FALSE(map.begin().valid());
41 EXPECT_FALSE(map.end().valid());
42 UUMap::iterator I = map.begin();
43 EXPECT_FALSE(I.valid());
44 EXPECT_TRUE(I == map.end());
45
46 // Default constructor and cross-constness compares.
47 UUMap::const_iterator CI;
48 CI = map.begin();
49 EXPECT_TRUE(CI == I);
50 UUMap::iterator I2;
51 I2 = map.end();
52 EXPECT_TRUE(I2 == CI);
53 }
54
55 // Test one-element closed ranges.
TEST(IntervalMapTest,OneElementRanges)56 TEST(IntervalMapTest, OneElementRanges) {
57 UUMap::Allocator allocator;
58 UUMap map(allocator);
59 map.insert(1, 1, 1);
60 map.insert(2, 2, 2);
61 EXPECT_EQ(1u, map.lookup(1));
62 EXPECT_EQ(2u, map.lookup(2));
63 }
64
65 // Single entry map tests
TEST(IntervalMapTest,SingleEntryMap)66 TEST(IntervalMapTest, SingleEntryMap) {
67 UUMap::Allocator allocator;
68 UUMap map(allocator);
69 map.insert(100, 150, 1);
70 EXPECT_FALSE(map.empty());
71
72 // Lookup around interval.
73 EXPECT_EQ(0u, map.lookup(0));
74 EXPECT_EQ(0u, map.lookup(99));
75 EXPECT_EQ(1u, map.lookup(100));
76 EXPECT_EQ(1u, map.lookup(101));
77 EXPECT_EQ(1u, map.lookup(125));
78 EXPECT_EQ(1u, map.lookup(149));
79 EXPECT_EQ(1u, map.lookup(150));
80 EXPECT_EQ(0u, map.lookup(151));
81 EXPECT_EQ(0u, map.lookup(200));
82 EXPECT_EQ(0u, map.lookup(~0u-1));
83
84 // Iterators.
85 EXPECT_TRUE(map.begin() == map.begin());
86 EXPECT_FALSE(map.begin() == map.end());
87 EXPECT_TRUE(map.end() == map.end());
88 EXPECT_TRUE(map.begin().valid());
89 EXPECT_FALSE(map.end().valid());
90
91 // Iter deref.
92 UUMap::iterator I = map.begin();
93 ASSERT_TRUE(I.valid());
94 EXPECT_EQ(100u, I.start());
95 EXPECT_EQ(150u, I.stop());
96 EXPECT_EQ(1u, I.value());
97
98 // Preincrement.
99 ++I;
100 EXPECT_FALSE(I.valid());
101 EXPECT_FALSE(I == map.begin());
102 EXPECT_TRUE(I == map.end());
103
104 // PreDecrement.
105 --I;
106 ASSERT_TRUE(I.valid());
107 EXPECT_EQ(100u, I.start());
108 EXPECT_EQ(150u, I.stop());
109 EXPECT_EQ(1u, I.value());
110 EXPECT_TRUE(I == map.begin());
111 EXPECT_FALSE(I == map.end());
112
113 // Change the value.
114 I.setValue(2);
115 ASSERT_TRUE(I.valid());
116 EXPECT_EQ(100u, I.start());
117 EXPECT_EQ(150u, I.stop());
118 EXPECT_EQ(2u, I.value());
119
120 // Grow the bounds.
121 I.setStart(0);
122 ASSERT_TRUE(I.valid());
123 EXPECT_EQ(0u, I.start());
124 EXPECT_EQ(150u, I.stop());
125 EXPECT_EQ(2u, I.value());
126
127 I.setStop(200);
128 ASSERT_TRUE(I.valid());
129 EXPECT_EQ(0u, I.start());
130 EXPECT_EQ(200u, I.stop());
131 EXPECT_EQ(2u, I.value());
132
133 // Shrink the bounds.
134 I.setStart(150);
135 ASSERT_TRUE(I.valid());
136 EXPECT_EQ(150u, I.start());
137 EXPECT_EQ(200u, I.stop());
138 EXPECT_EQ(2u, I.value());
139
140 // Shrink the interval to have a length of 1
141 I.setStop(150);
142 ASSERT_TRUE(I.valid());
143 EXPECT_EQ(150u, I.start());
144 EXPECT_EQ(150u, I.stop());
145 EXPECT_EQ(2u, I.value());
146
147 I.setStop(160);
148 ASSERT_TRUE(I.valid());
149 EXPECT_EQ(150u, I.start());
150 EXPECT_EQ(160u, I.stop());
151 EXPECT_EQ(2u, I.value());
152
153 // Shrink the interval to have a length of 1
154 I.setStart(160);
155 ASSERT_TRUE(I.valid());
156 EXPECT_EQ(160u, I.start());
157 EXPECT_EQ(160u, I.stop());
158 EXPECT_EQ(2u, I.value());
159
160 // Erase last elem.
161 I.erase();
162 EXPECT_TRUE(map.empty());
163 EXPECT_EQ(0, std::distance(map.begin(), map.end()));
164 }
165
166 // Single entry half-open map tests
TEST(IntervalMapTest,SingleEntryHalfOpenMap)167 TEST(IntervalMapTest, SingleEntryHalfOpenMap) {
168 UUHalfOpenMap::Allocator allocator;
169 UUHalfOpenMap map(allocator);
170 map.insert(100, 150, 1);
171 EXPECT_FALSE(map.empty());
172
173 UUHalfOpenMap::iterator I = map.begin();
174 ASSERT_TRUE(I.valid());
175
176 // Shrink the interval to have a length of 1
177 I.setStart(149);
178 ASSERT_TRUE(I.valid());
179 EXPECT_EQ(149u, I.start());
180 EXPECT_EQ(150u, I.stop());
181 EXPECT_EQ(1u, I.value());
182
183 I.setStop(160);
184 ASSERT_TRUE(I.valid());
185 EXPECT_EQ(149u, I.start());
186 EXPECT_EQ(160u, I.stop());
187 EXPECT_EQ(1u, I.value());
188
189 // Shrink the interval to have a length of 1
190 I.setStop(150);
191 ASSERT_TRUE(I.valid());
192 EXPECT_EQ(149u, I.start());
193 EXPECT_EQ(150u, I.stop());
194 EXPECT_EQ(1u, I.value());
195 }
196
197 // Flat coalescing tests.
TEST(IntervalMapTest,RootCoalescing)198 TEST(IntervalMapTest, RootCoalescing) {
199 UUMap::Allocator allocator;
200 UUMap map(allocator);
201 map.insert(100, 150, 1);
202
203 // Coalesce from the left.
204 map.insert(90, 99, 1);
205 EXPECT_EQ(1, std::distance(map.begin(), map.end()));
206 EXPECT_EQ(90u, map.start());
207 EXPECT_EQ(150u, map.stop());
208
209 // Coalesce from the right.
210 map.insert(151, 200, 1);
211 EXPECT_EQ(1, std::distance(map.begin(), map.end()));
212 EXPECT_EQ(90u, map.start());
213 EXPECT_EQ(200u, map.stop());
214
215 // Non-coalesce from the left.
216 map.insert(60, 89, 2);
217 EXPECT_EQ(2, std::distance(map.begin(), map.end()));
218 EXPECT_EQ(60u, map.start());
219 EXPECT_EQ(200u, map.stop());
220 EXPECT_EQ(2u, map.lookup(89));
221 EXPECT_EQ(1u, map.lookup(90));
222
223 UUMap::iterator I = map.begin();
224 EXPECT_EQ(60u, I.start());
225 EXPECT_EQ(89u, I.stop());
226 EXPECT_EQ(2u, I.value());
227 ++I;
228 EXPECT_EQ(90u, I.start());
229 EXPECT_EQ(200u, I.stop());
230 EXPECT_EQ(1u, I.value());
231 ++I;
232 EXPECT_FALSE(I.valid());
233
234 // Non-coalesce from the right.
235 map.insert(201, 210, 2);
236 EXPECT_EQ(3, std::distance(map.begin(), map.end()));
237 EXPECT_EQ(60u, map.start());
238 EXPECT_EQ(210u, map.stop());
239 EXPECT_EQ(2u, map.lookup(201));
240 EXPECT_EQ(1u, map.lookup(200));
241
242 // Erase from the left.
243 map.begin().erase();
244 EXPECT_EQ(2, std::distance(map.begin(), map.end()));
245 EXPECT_EQ(90u, map.start());
246 EXPECT_EQ(210u, map.stop());
247
248 // Erase from the right.
249 (--map.end()).erase();
250 EXPECT_EQ(1, std::distance(map.begin(), map.end()));
251 EXPECT_EQ(90u, map.start());
252 EXPECT_EQ(200u, map.stop());
253
254 // Add non-coalescing, then trigger coalescing with setValue.
255 map.insert(80, 89, 2);
256 map.insert(201, 210, 2);
257 EXPECT_EQ(3, std::distance(map.begin(), map.end()));
258 (++map.begin()).setValue(2);
259 EXPECT_EQ(1, std::distance(map.begin(), map.end()));
260 I = map.begin();
261 ASSERT_TRUE(I.valid());
262 EXPECT_EQ(80u, I.start());
263 EXPECT_EQ(210u, I.stop());
264 EXPECT_EQ(2u, I.value());
265 }
266
267 // Flat multi-coalescing tests.
TEST(IntervalMapTest,RootMultiCoalescing)268 TEST(IntervalMapTest, RootMultiCoalescing) {
269 UUMap::Allocator allocator;
270 UUMap map(allocator);
271 map.insert(140, 150, 1);
272 map.insert(160, 170, 1);
273 map.insert(100, 110, 1);
274 map.insert(120, 130, 1);
275 EXPECT_EQ(4, std::distance(map.begin(), map.end()));
276 EXPECT_EQ(100u, map.start());
277 EXPECT_EQ(170u, map.stop());
278
279 // Verify inserts.
280 UUMap::iterator I = map.begin();
281 EXPECT_EQ(100u, I.start());
282 EXPECT_EQ(110u, I.stop());
283 ++I;
284 EXPECT_EQ(120u, I.start());
285 EXPECT_EQ(130u, I.stop());
286 ++I;
287 EXPECT_EQ(140u, I.start());
288 EXPECT_EQ(150u, I.stop());
289 ++I;
290 EXPECT_EQ(160u, I.start());
291 EXPECT_EQ(170u, I.stop());
292 ++I;
293 EXPECT_FALSE(I.valid());
294
295 // Test advanceTo on flat tree.
296 I = map.begin();
297 I.advanceTo(135);
298 ASSERT_TRUE(I.valid());
299 EXPECT_EQ(140u, I.start());
300 EXPECT_EQ(150u, I.stop());
301
302 I.advanceTo(145);
303 ASSERT_TRUE(I.valid());
304 EXPECT_EQ(140u, I.start());
305 EXPECT_EQ(150u, I.stop());
306
307 I.advanceTo(200);
308 EXPECT_FALSE(I.valid());
309
310 I.advanceTo(300);
311 EXPECT_FALSE(I.valid());
312
313 // Coalesce left with followers.
314 // [100;110] [120;130] [140;150] [160;170]
315 map.insert(111, 115, 1);
316 I = map.begin();
317 ASSERT_TRUE(I.valid());
318 EXPECT_EQ(100u, I.start());
319 EXPECT_EQ(115u, I.stop());
320 ++I;
321 ASSERT_TRUE(I.valid());
322 EXPECT_EQ(120u, I.start());
323 EXPECT_EQ(130u, I.stop());
324 ++I;
325 ASSERT_TRUE(I.valid());
326 EXPECT_EQ(140u, I.start());
327 EXPECT_EQ(150u, I.stop());
328 ++I;
329 ASSERT_TRUE(I.valid());
330 EXPECT_EQ(160u, I.start());
331 EXPECT_EQ(170u, I.stop());
332 ++I;
333 EXPECT_FALSE(I.valid());
334
335 // Coalesce right with followers.
336 // [100;115] [120;130] [140;150] [160;170]
337 map.insert(135, 139, 1);
338 I = map.begin();
339 ASSERT_TRUE(I.valid());
340 EXPECT_EQ(100u, I.start());
341 EXPECT_EQ(115u, I.stop());
342 ++I;
343 ASSERT_TRUE(I.valid());
344 EXPECT_EQ(120u, I.start());
345 EXPECT_EQ(130u, I.stop());
346 ++I;
347 ASSERT_TRUE(I.valid());
348 EXPECT_EQ(135u, I.start());
349 EXPECT_EQ(150u, I.stop());
350 ++I;
351 ASSERT_TRUE(I.valid());
352 EXPECT_EQ(160u, I.start());
353 EXPECT_EQ(170u, I.stop());
354 ++I;
355 EXPECT_FALSE(I.valid());
356
357 // Coalesce left and right with followers.
358 // [100;115] [120;130] [135;150] [160;170]
359 map.insert(131, 134, 1);
360 I = map.begin();
361 ASSERT_TRUE(I.valid());
362 EXPECT_EQ(100u, I.start());
363 EXPECT_EQ(115u, I.stop());
364 ++I;
365 ASSERT_TRUE(I.valid());
366 EXPECT_EQ(120u, I.start());
367 EXPECT_EQ(150u, I.stop());
368 ++I;
369 ASSERT_TRUE(I.valid());
370 EXPECT_EQ(160u, I.start());
371 EXPECT_EQ(170u, I.stop());
372 ++I;
373 EXPECT_FALSE(I.valid());
374
375 // Test clear() on non-branched map.
376 map.clear();
377 EXPECT_TRUE(map.empty());
378 EXPECT_TRUE(map.begin() == map.end());
379 }
380
381 // Branched, non-coalescing tests.
TEST(IntervalMapTest,Branched)382 TEST(IntervalMapTest, Branched) {
383 UUMap::Allocator allocator;
384 UUMap map(allocator);
385
386 // Insert enough intervals to force a branched tree.
387 // This creates 9 leaf nodes with 11 elements each, tree height = 1.
388 for (unsigned i = 1; i < 100; ++i) {
389 map.insert(10*i, 10*i+5, i);
390 EXPECT_EQ(10u, map.start());
391 EXPECT_EQ(10*i+5, map.stop());
392 }
393
394 // Tree limits.
395 EXPECT_FALSE(map.empty());
396 EXPECT_EQ(10u, map.start());
397 EXPECT_EQ(995u, map.stop());
398
399 // Tree lookup.
400 for (unsigned i = 1; i < 100; ++i) {
401 EXPECT_EQ(0u, map.lookup(10*i-1));
402 EXPECT_EQ(i, map.lookup(10*i));
403 EXPECT_EQ(i, map.lookup(10*i+5));
404 EXPECT_EQ(0u, map.lookup(10*i+6));
405 }
406
407 // Forward iteration.
408 UUMap::iterator I = map.begin();
409 for (unsigned i = 1; i < 100; ++i) {
410 ASSERT_TRUE(I.valid());
411 EXPECT_EQ(10*i, I.start());
412 EXPECT_EQ(10*i+5, I.stop());
413 EXPECT_EQ(i, *I);
414 ++I;
415 }
416 EXPECT_FALSE(I.valid());
417 EXPECT_TRUE(I == map.end());
418
419 // Backwards iteration.
420 for (unsigned i = 99; i; --i) {
421 --I;
422 ASSERT_TRUE(I.valid());
423 EXPECT_EQ(10*i, I.start());
424 EXPECT_EQ(10*i+5, I.stop());
425 EXPECT_EQ(i, *I);
426 }
427 EXPECT_TRUE(I == map.begin());
428
429 // Test advanceTo in same node.
430 I.advanceTo(20);
431 ASSERT_TRUE(I.valid());
432 EXPECT_EQ(20u, I.start());
433 EXPECT_EQ(25u, I.stop());
434
435 // Change value, no coalescing.
436 I.setValue(0);
437 ASSERT_TRUE(I.valid());
438 EXPECT_EQ(20u, I.start());
439 EXPECT_EQ(25u, I.stop());
440 EXPECT_EQ(0u, I.value());
441
442 // Close the gap right, no coalescing.
443 I.setStop(29);
444 ASSERT_TRUE(I.valid());
445 EXPECT_EQ(20u, I.start());
446 EXPECT_EQ(29u, I.stop());
447 EXPECT_EQ(0u, I.value());
448
449 // Change value, no coalescing.
450 I.setValue(2);
451 ASSERT_TRUE(I.valid());
452 EXPECT_EQ(20u, I.start());
453 EXPECT_EQ(29u, I.stop());
454 EXPECT_EQ(2u, I.value());
455
456 // Change value, now coalescing.
457 I.setValue(3);
458 ASSERT_TRUE(I.valid());
459 EXPECT_EQ(20u, I.start());
460 EXPECT_EQ(35u, I.stop());
461 EXPECT_EQ(3u, I.value());
462
463 // Close the gap, now coalescing.
464 I.setValue(4);
465 ASSERT_TRUE(I.valid());
466 I.setStop(39);
467 ASSERT_TRUE(I.valid());
468 EXPECT_EQ(20u, I.start());
469 EXPECT_EQ(45u, I.stop());
470 EXPECT_EQ(4u, I.value());
471
472 // advanceTo another node.
473 I.advanceTo(200);
474 ASSERT_TRUE(I.valid());
475 EXPECT_EQ(200u, I.start());
476 EXPECT_EQ(205u, I.stop());
477
478 // Close the gap left, no coalescing.
479 I.setStart(196);
480 ASSERT_TRUE(I.valid());
481 EXPECT_EQ(196u, I.start());
482 EXPECT_EQ(205u, I.stop());
483 EXPECT_EQ(20u, I.value());
484
485 // Change value, no coalescing.
486 I.setValue(0);
487 ASSERT_TRUE(I.valid());
488 EXPECT_EQ(196u, I.start());
489 EXPECT_EQ(205u, I.stop());
490 EXPECT_EQ(0u, I.value());
491
492 // Change value, now coalescing.
493 I.setValue(19);
494 ASSERT_TRUE(I.valid());
495 EXPECT_EQ(190u, I.start());
496 EXPECT_EQ(205u, I.stop());
497 EXPECT_EQ(19u, I.value());
498
499 // Close the gap, now coalescing.
500 I.setValue(18);
501 ASSERT_TRUE(I.valid());
502 I.setStart(186);
503 ASSERT_TRUE(I.valid());
504 EXPECT_EQ(180u, I.start());
505 EXPECT_EQ(205u, I.stop());
506 EXPECT_EQ(18u, I.value());
507
508 // Erase from the front.
509 I = map.begin();
510 for (unsigned i = 0; i != 20; ++i) {
511 I.erase();
512 EXPECT_TRUE(I == map.begin());
513 EXPECT_FALSE(map.empty());
514 EXPECT_EQ(I.start(), map.start());
515 EXPECT_EQ(995u, map.stop());
516 }
517
518 // Test clear() on branched map.
519 map.clear();
520 EXPECT_TRUE(map.empty());
521 EXPECT_TRUE(map.begin() == map.end());
522 }
523
524 // Branched, high, non-coalescing tests.
TEST(IntervalMapTest,Branched2)525 TEST(IntervalMapTest, Branched2) {
526 UUMap::Allocator allocator;
527 UUMap map(allocator);
528
529 // Insert enough intervals to force a height >= 2 tree.
530 for (unsigned i = 1; i < 1000; ++i)
531 map.insert(10*i, 10*i+5, i);
532
533 // Tree limits.
534 EXPECT_FALSE(map.empty());
535 EXPECT_EQ(10u, map.start());
536 EXPECT_EQ(9995u, map.stop());
537
538 // Tree lookup.
539 for (unsigned i = 1; i < 1000; ++i) {
540 EXPECT_EQ(0u, map.lookup(10*i-1));
541 EXPECT_EQ(i, map.lookup(10*i));
542 EXPECT_EQ(i, map.lookup(10*i+5));
543 EXPECT_EQ(0u, map.lookup(10*i+6));
544 }
545
546 // Forward iteration.
547 UUMap::iterator I = map.begin();
548 for (unsigned i = 1; i < 1000; ++i) {
549 ASSERT_TRUE(I.valid());
550 EXPECT_EQ(10*i, I.start());
551 EXPECT_EQ(10*i+5, I.stop());
552 EXPECT_EQ(i, *I);
553 ++I;
554 }
555 EXPECT_FALSE(I.valid());
556 EXPECT_TRUE(I == map.end());
557
558 // Backwards iteration.
559 for (unsigned i = 999; i; --i) {
560 --I;
561 ASSERT_TRUE(I.valid());
562 EXPECT_EQ(10*i, I.start());
563 EXPECT_EQ(10*i+5, I.stop());
564 EXPECT_EQ(i, *I);
565 }
566 EXPECT_TRUE(I == map.begin());
567
568 // Test advanceTo in same node.
569 I.advanceTo(20);
570 ASSERT_TRUE(I.valid());
571 EXPECT_EQ(20u, I.start());
572 EXPECT_EQ(25u, I.stop());
573
574 // advanceTo sibling leaf node.
575 I.advanceTo(200);
576 ASSERT_TRUE(I.valid());
577 EXPECT_EQ(200u, I.start());
578 EXPECT_EQ(205u, I.stop());
579
580 // advanceTo further.
581 I.advanceTo(2000);
582 ASSERT_TRUE(I.valid());
583 EXPECT_EQ(2000u, I.start());
584 EXPECT_EQ(2005u, I.stop());
585
586 // advanceTo beyond end()
587 I.advanceTo(20000);
588 EXPECT_FALSE(I.valid());
589
590 // end().advanceTo() is valid as long as x > map.stop()
591 I.advanceTo(30000);
592 EXPECT_FALSE(I.valid());
593
594 // Test clear() on branched map.
595 map.clear();
596 EXPECT_TRUE(map.empty());
597 EXPECT_TRUE(map.begin() == map.end());
598 }
599
600 // Random insertions, coalescing to a single interval.
TEST(IntervalMapTest,RandomCoalescing)601 TEST(IntervalMapTest, RandomCoalescing) {
602 UUMap::Allocator allocator;
603 UUMap map(allocator);
604
605 // This is a poor PRNG with maximal period:
606 // x_n = 5 x_{n-1} + 1 mod 2^N
607
608 unsigned x = 100;
609 for (unsigned i = 0; i != 4096; ++i) {
610 map.insert(10*x, 10*x+9, 1);
611 EXPECT_GE(10*x, map.start());
612 EXPECT_LE(10*x+9, map.stop());
613 x = (5*x+1)%4096;
614 }
615
616 // Map should be fully coalesced after that exercise.
617 EXPECT_FALSE(map.empty());
618 EXPECT_EQ(0u, map.start());
619 EXPECT_EQ(40959u, map.stop());
620 EXPECT_EQ(1, std::distance(map.begin(), map.end()));
621
622 }
623
setupOverlaps(UUMap & M)624 static void setupOverlaps(UUMap &M) {
625 M.insert(10, 20, 0);
626 M.insert(30, 40, 0);
627 M.insert(50, 60, 0);
628 // Add extra nodes to force allocations.
629 for (int i = 70; i < 100; i += 2)
630 M.insert(i, i + 1, i);
631 }
632
checkOverlaps(UUMap & M)633 static void checkOverlaps(UUMap &M) {
634 EXPECT_FALSE(M.overlaps(0, 9));
635 EXPECT_TRUE(M.overlaps(0, 10));
636 EXPECT_TRUE(M.overlaps(0, 15));
637 EXPECT_TRUE(M.overlaps(0, 25));
638 EXPECT_TRUE(M.overlaps(0, 45));
639 EXPECT_TRUE(M.overlaps(10, 45));
640 EXPECT_TRUE(M.overlaps(30, 45));
641 EXPECT_TRUE(M.overlaps(35, 36));
642 EXPECT_TRUE(M.overlaps(40, 45));
643 EXPECT_FALSE(M.overlaps(45, 45));
644 EXPECT_TRUE(M.overlaps(60, 60));
645 EXPECT_TRUE(M.overlaps(60, 66));
646 EXPECT_FALSE(M.overlaps(66, 66));
647 }
648
TEST(IntervalMapTest,Copy)649 TEST(IntervalMapTest, Copy) {
650 // Test that copy assignment and initialization works.
651 UUHalfOpenMap::Allocator Allocator;
652 UUMap Src(Allocator);
653 setupOverlaps(Src);
654
655 UUMap CopyAssignmentDst(Allocator);
656 CopyAssignmentDst = Src;
657
658 UUMap CopyInitDst(Src);
659
660 checkOverlaps(Src);
661 Src.clear();
662
663 checkOverlaps(CopyAssignmentDst);
664 checkOverlaps(CopyInitDst);
665 }
666
TEST(IntervalMapTest,Move)667 TEST(IntervalMapTest, Move) {
668 // Test that move assignment and initialization works.
669 UUHalfOpenMap::Allocator Allocator;
670 // Double check that MoveAssignmentDst owns all its data by moving from an
671 // object that is destroyed before we call checkOverlaps.
672 UUMap MoveAssignmentDst(Allocator);
673 {
674 UUMap Src(Allocator);
675 setupOverlaps(Src);
676 MoveAssignmentDst = std::move(Src);
677 }
678 checkOverlaps(MoveAssignmentDst);
679
680 UUMap MoveInitSrc(Allocator);
681 setupOverlaps(MoveInitSrc);
682 UUMap MoveInitDst(std::move(MoveInitSrc));
683 checkOverlaps(MoveInitDst);
684 }
685
TEST(IntervalMapTest,Overlaps)686 TEST(IntervalMapTest, Overlaps) {
687 UUMap::Allocator allocator;
688 UUMap map(allocator);
689 setupOverlaps(map);
690 checkOverlaps(map);
691 }
692
TEST(IntervalMapTest,OverlapsHalfOpen)693 TEST(IntervalMapTest, OverlapsHalfOpen) {
694 UUHalfOpenMap::Allocator allocator;
695 UUHalfOpenMap map(allocator);
696 map.insert(10, 20, 0);
697 map.insert(30, 40, 0);
698 map.insert(50, 60, 0);
699
700 EXPECT_FALSE(map.overlaps(0, 9));
701 EXPECT_FALSE(map.overlaps(0, 10));
702 EXPECT_TRUE(map.overlaps(0, 15));
703 EXPECT_TRUE(map.overlaps(0, 25));
704 EXPECT_TRUE(map.overlaps(0, 45));
705 EXPECT_TRUE(map.overlaps(10, 45));
706 EXPECT_TRUE(map.overlaps(30, 45));
707 EXPECT_TRUE(map.overlaps(35, 36));
708 EXPECT_FALSE(map.overlaps(40, 45));
709 EXPECT_FALSE(map.overlaps(45, 46));
710 EXPECT_FALSE(map.overlaps(60, 61));
711 EXPECT_FALSE(map.overlaps(60, 66));
712 EXPECT_FALSE(map.overlaps(66, 67));
713 }
714
TEST(IntervalMapOverlapsTest,SmallMaps)715 TEST(IntervalMapOverlapsTest, SmallMaps) {
716 typedef IntervalMapOverlaps<UUMap,UUMap> UUOverlaps;
717 UUMap::Allocator allocator;
718 UUMap mapA(allocator);
719 UUMap mapB(allocator);
720
721 // empty, empty.
722 EXPECT_FALSE(UUOverlaps(mapA, mapB).valid());
723
724 mapA.insert(1, 2, 3);
725
726 // full, empty
727 EXPECT_FALSE(UUOverlaps(mapA, mapB).valid());
728 // empty, full
729 EXPECT_FALSE(UUOverlaps(mapB, mapA).valid());
730
731 mapB.insert(3, 4, 5);
732
733 // full, full, non-overlapping
734 EXPECT_FALSE(UUOverlaps(mapA, mapB).valid());
735 EXPECT_FALSE(UUOverlaps(mapB, mapA).valid());
736
737 // Add an overlapping segment.
738 mapA.insert(4, 5, 6);
739
740 UUOverlaps AB(mapA, mapB);
741 ASSERT_TRUE(AB.valid());
742 EXPECT_EQ(4u, AB.a().start());
743 EXPECT_EQ(3u, AB.b().start());
744 ++AB;
745 EXPECT_FALSE(AB.valid());
746
747 UUOverlaps BA(mapB, mapA);
748 ASSERT_TRUE(BA.valid());
749 EXPECT_EQ(3u, BA.a().start());
750 EXPECT_EQ(4u, BA.b().start());
751 // advance past end.
752 BA.advanceTo(6);
753 EXPECT_FALSE(BA.valid());
754 // advance an invalid iterator.
755 BA.advanceTo(7);
756 EXPECT_FALSE(BA.valid());
757 }
758
TEST(IntervalMapOverlapsTest,BigMaps)759 TEST(IntervalMapOverlapsTest, BigMaps) {
760 typedef IntervalMapOverlaps<UUMap,UUMap> UUOverlaps;
761 UUMap::Allocator allocator;
762 UUMap mapA(allocator);
763 UUMap mapB(allocator);
764
765 // [0;4] [10;14] [20;24] ...
766 for (unsigned n = 0; n != 100; ++n)
767 mapA.insert(10*n, 10*n+4, n);
768
769 // [5;6] [15;16] [25;26] ...
770 for (unsigned n = 10; n != 20; ++n)
771 mapB.insert(10*n+5, 10*n+6, n);
772
773 // [208;209] [218;219] ...
774 for (unsigned n = 20; n != 30; ++n)
775 mapB.insert(10*n+8, 10*n+9, n);
776
777 // insert some overlapping segments.
778 mapB.insert(400, 400, 400);
779 mapB.insert(401, 401, 401);
780 mapB.insert(402, 500, 402);
781 mapB.insert(600, 601, 402);
782
783 UUOverlaps AB(mapA, mapB);
784 ASSERT_TRUE(AB.valid());
785 EXPECT_EQ(400u, AB.a().start());
786 EXPECT_EQ(400u, AB.b().start());
787 ++AB;
788 ASSERT_TRUE(AB.valid());
789 EXPECT_EQ(400u, AB.a().start());
790 EXPECT_EQ(401u, AB.b().start());
791 ++AB;
792 ASSERT_TRUE(AB.valid());
793 EXPECT_EQ(400u, AB.a().start());
794 EXPECT_EQ(402u, AB.b().start());
795 ++AB;
796 ASSERT_TRUE(AB.valid());
797 EXPECT_EQ(410u, AB.a().start());
798 EXPECT_EQ(402u, AB.b().start());
799 ++AB;
800 ASSERT_TRUE(AB.valid());
801 EXPECT_EQ(420u, AB.a().start());
802 EXPECT_EQ(402u, AB.b().start());
803 AB.skipB();
804 ASSERT_TRUE(AB.valid());
805 EXPECT_EQ(600u, AB.a().start());
806 EXPECT_EQ(600u, AB.b().start());
807 ++AB;
808 EXPECT_FALSE(AB.valid());
809
810 // Test advanceTo.
811 UUOverlaps AB2(mapA, mapB);
812 AB2.advanceTo(410);
813 ASSERT_TRUE(AB2.valid());
814 EXPECT_EQ(410u, AB2.a().start());
815 EXPECT_EQ(402u, AB2.b().start());
816
817 // It is valid to advanceTo with any monotonic sequence.
818 AB2.advanceTo(411);
819 ASSERT_TRUE(AB2.valid());
820 EXPECT_EQ(410u, AB2.a().start());
821 EXPECT_EQ(402u, AB2.b().start());
822
823 // Check reversed maps.
824 UUOverlaps BA(mapB, mapA);
825 ASSERT_TRUE(BA.valid());
826 EXPECT_EQ(400u, BA.b().start());
827 EXPECT_EQ(400u, BA.a().start());
828 ++BA;
829 ASSERT_TRUE(BA.valid());
830 EXPECT_EQ(400u, BA.b().start());
831 EXPECT_EQ(401u, BA.a().start());
832 ++BA;
833 ASSERT_TRUE(BA.valid());
834 EXPECT_EQ(400u, BA.b().start());
835 EXPECT_EQ(402u, BA.a().start());
836 ++BA;
837 ASSERT_TRUE(BA.valid());
838 EXPECT_EQ(410u, BA.b().start());
839 EXPECT_EQ(402u, BA.a().start());
840 ++BA;
841 ASSERT_TRUE(BA.valid());
842 EXPECT_EQ(420u, BA.b().start());
843 EXPECT_EQ(402u, BA.a().start());
844 BA.skipA();
845 ASSERT_TRUE(BA.valid());
846 EXPECT_EQ(600u, BA.b().start());
847 EXPECT_EQ(600u, BA.a().start());
848 ++BA;
849 EXPECT_FALSE(BA.valid());
850
851 // Test advanceTo.
852 UUOverlaps BA2(mapB, mapA);
853 BA2.advanceTo(410);
854 ASSERT_TRUE(BA2.valid());
855 EXPECT_EQ(410u, BA2.b().start());
856 EXPECT_EQ(402u, BA2.a().start());
857
858 BA2.advanceTo(411);
859 ASSERT_TRUE(BA2.valid());
860 EXPECT_EQ(410u, BA2.b().start());
861 EXPECT_EQ(402u, BA2.a().start());
862 }
863
864 } // namespace
865