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