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