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