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
13using namespace llvm;
14
15namespace {
16
17typedef IntervalMap<unsigned, unsigned, 4> UUMap;
18
19// Empty map tests
20TEST(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
54TEST(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.
141TEST(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.
211TEST(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.
325TEST(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.
468TEST(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.
544TEST(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
567TEST(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
611TEST(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