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