llvm/unittests/ADT/IntervalMapTest.cpp

   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