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