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