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
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
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
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.
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.
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.
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.
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.
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 
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 
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