864 lines · 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-exception6//7//===----------------------------------------------------------------------===//8 9#include "llvm/ADT/IntervalMap.h"10#include "gtest/gtest.h"11 12using namespace llvm;13 14namespace {15 16using UUMap = IntervalMap<unsigned, unsigned, 4>;17using UUHalfOpenMap =18 IntervalMap<unsigned, unsigned, 4, IntervalMapHalfOpenInfo<unsigned>>;19 20// Empty map tests21TEST(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.55TEST(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 tests65TEST(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 1140 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 1153 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 tests166TEST(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 1176 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 1189 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.197TEST(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.267TEST(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.381TEST(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.524TEST(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.600TEST(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^N606 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 623static void setupOverlaps(UUMap &M) {624 M.insert(10, 20, 0);625 M.insert(30, 40, 0);626 M.insert(50, 60, 0);627 // Add extra nodes to force allocations.628 for (int i = 70; i < 100; i += 2)629 M.insert(i, i + 1, i);630}631 632static void checkOverlaps(UUMap &M) {633 EXPECT_FALSE(M.overlaps(0, 9));634 EXPECT_TRUE(M.overlaps(0, 10));635 EXPECT_TRUE(M.overlaps(0, 15));636 EXPECT_TRUE(M.overlaps(0, 25));637 EXPECT_TRUE(M.overlaps(0, 45));638 EXPECT_TRUE(M.overlaps(10, 45));639 EXPECT_TRUE(M.overlaps(30, 45));640 EXPECT_TRUE(M.overlaps(35, 36));641 EXPECT_TRUE(M.overlaps(40, 45));642 EXPECT_FALSE(M.overlaps(45, 45));643 EXPECT_TRUE(M.overlaps(60, 60));644 EXPECT_TRUE(M.overlaps(60, 66));645 EXPECT_FALSE(M.overlaps(66, 66));646}647 648TEST(IntervalMapTest, Copy) {649 // Test that copy assignment and initialization works.650 UUHalfOpenMap::Allocator Allocator;651 UUMap Src(Allocator);652 setupOverlaps(Src);653 654 UUMap CopyAssignmentDst(Allocator);655 CopyAssignmentDst = Src;656 657 UUMap CopyInitDst(Src);658 659 checkOverlaps(Src);660 Src.clear();661 662 checkOverlaps(CopyAssignmentDst);663 checkOverlaps(CopyInitDst);664}665 666TEST(IntervalMapTest, Move) {667 // Test that move assignment and initialization works.668 UUHalfOpenMap::Allocator Allocator;669 // Double check that MoveAssignmentDst owns all its data by moving from an670 // object that is destroyed before we call checkOverlaps.671 UUMap MoveAssignmentDst(Allocator);672 {673 UUMap Src(Allocator);674 setupOverlaps(Src);675 MoveAssignmentDst = std::move(Src);676 }677 checkOverlaps(MoveAssignmentDst);678 679 UUMap MoveInitSrc(Allocator);680 setupOverlaps(MoveInitSrc);681 UUMap MoveInitDst(std::move(MoveInitSrc));682 checkOverlaps(MoveInitDst);683}684 685TEST(IntervalMapTest, Overlaps) {686 UUMap::Allocator allocator;687 UUMap map(allocator);688 setupOverlaps(map);689 checkOverlaps(map);690}691 692TEST(IntervalMapTest, OverlapsHalfOpen) {693 UUHalfOpenMap::Allocator allocator;694 UUHalfOpenMap map(allocator);695 map.insert(10, 20, 0);696 map.insert(30, 40, 0);697 map.insert(50, 60, 0);698 699 EXPECT_FALSE(map.overlaps(0, 9));700 EXPECT_FALSE(map.overlaps(0, 10));701 EXPECT_TRUE(map.overlaps(0, 15));702 EXPECT_TRUE(map.overlaps(0, 25));703 EXPECT_TRUE(map.overlaps(0, 45));704 EXPECT_TRUE(map.overlaps(10, 45));705 EXPECT_TRUE(map.overlaps(30, 45));706 EXPECT_TRUE(map.overlaps(35, 36));707 EXPECT_FALSE(map.overlaps(40, 45));708 EXPECT_FALSE(map.overlaps(45, 46));709 EXPECT_FALSE(map.overlaps(60, 61));710 EXPECT_FALSE(map.overlaps(60, 66));711 EXPECT_FALSE(map.overlaps(66, 67));712}713 714TEST(IntervalMapOverlapsTest, SmallMaps) {715 using UUOverlaps = IntervalMapOverlaps<UUMap, UUMap>;716 UUMap::Allocator allocator;717 UUMap mapA(allocator);718 UUMap mapB(allocator);719 720 // empty, empty.721 EXPECT_FALSE(UUOverlaps(mapA, mapB).valid());722 723 mapA.insert(1, 2, 3);724 725 // full, empty726 EXPECT_FALSE(UUOverlaps(mapA, mapB).valid());727 // empty, full728 EXPECT_FALSE(UUOverlaps(mapB, mapA).valid());729 730 mapB.insert(3, 4, 5);731 732 // full, full, non-overlapping733 EXPECT_FALSE(UUOverlaps(mapA, mapB).valid());734 EXPECT_FALSE(UUOverlaps(mapB, mapA).valid());735 736 // Add an overlapping segment.737 mapA.insert(4, 5, 6);738 739 UUOverlaps AB(mapA, mapB);740 ASSERT_TRUE(AB.valid());741 EXPECT_EQ(4u, AB.a().start());742 EXPECT_EQ(3u, AB.b().start());743 ++AB;744 EXPECT_FALSE(AB.valid());745 746 UUOverlaps BA(mapB, mapA);747 ASSERT_TRUE(BA.valid());748 EXPECT_EQ(3u, BA.a().start());749 EXPECT_EQ(4u, BA.b().start());750 // advance past end.751 BA.advanceTo(6);752 EXPECT_FALSE(BA.valid());753 // advance an invalid iterator.754 BA.advanceTo(7);755 EXPECT_FALSE(BA.valid());756}757 758TEST(IntervalMapOverlapsTest, BigMaps) {759 using UUOverlaps = IntervalMapOverlaps<UUMap, UUMap>;760 UUMap::Allocator allocator;761 UUMap mapA(allocator);762 UUMap mapB(allocator);763 764 // [0;4] [10;14] [20;24] ...765 for (unsigned n = 0; n != 100; ++n)766 mapA.insert(10*n, 10*n+4, n);767 768 // [5;6] [15;16] [25;26] ...769 for (unsigned n = 10; n != 20; ++n)770 mapB.insert(10*n+5, 10*n+6, n);771 772 // [208;209] [218;219] ...773 for (unsigned n = 20; n != 30; ++n)774 mapB.insert(10*n+8, 10*n+9, n);775 776 // insert some overlapping segments.777 mapB.insert(400, 400, 400);778 mapB.insert(401, 401, 401);779 mapB.insert(402, 500, 402);780 mapB.insert(600, 601, 402);781 782 UUOverlaps AB(mapA, mapB);783 ASSERT_TRUE(AB.valid());784 EXPECT_EQ(400u, AB.a().start());785 EXPECT_EQ(400u, AB.b().start());786 ++AB;787 ASSERT_TRUE(AB.valid());788 EXPECT_EQ(400u, AB.a().start());789 EXPECT_EQ(401u, AB.b().start());790 ++AB;791 ASSERT_TRUE(AB.valid());792 EXPECT_EQ(400u, AB.a().start());793 EXPECT_EQ(402u, AB.b().start());794 ++AB;795 ASSERT_TRUE(AB.valid());796 EXPECT_EQ(410u, AB.a().start());797 EXPECT_EQ(402u, AB.b().start());798 ++AB;799 ASSERT_TRUE(AB.valid());800 EXPECT_EQ(420u, AB.a().start());801 EXPECT_EQ(402u, AB.b().start());802 AB.skipB();803 ASSERT_TRUE(AB.valid());804 EXPECT_EQ(600u, AB.a().start());805 EXPECT_EQ(600u, AB.b().start());806 ++AB;807 EXPECT_FALSE(AB.valid());808 809 // Test advanceTo.810 UUOverlaps AB2(mapA, mapB);811 AB2.advanceTo(410);812 ASSERT_TRUE(AB2.valid());813 EXPECT_EQ(410u, AB2.a().start());814 EXPECT_EQ(402u, AB2.b().start());815 816 // It is valid to advanceTo with any monotonic sequence.817 AB2.advanceTo(411);818 ASSERT_TRUE(AB2.valid());819 EXPECT_EQ(410u, AB2.a().start());820 EXPECT_EQ(402u, AB2.b().start());821 822 // Check reversed maps.823 UUOverlaps BA(mapB, mapA);824 ASSERT_TRUE(BA.valid());825 EXPECT_EQ(400u, BA.b().start());826 EXPECT_EQ(400u, BA.a().start());827 ++BA;828 ASSERT_TRUE(BA.valid());829 EXPECT_EQ(400u, BA.b().start());830 EXPECT_EQ(401u, BA.a().start());831 ++BA;832 ASSERT_TRUE(BA.valid());833 EXPECT_EQ(400u, BA.b().start());834 EXPECT_EQ(402u, BA.a().start());835 ++BA;836 ASSERT_TRUE(BA.valid());837 EXPECT_EQ(410u, BA.b().start());838 EXPECT_EQ(402u, BA.a().start());839 ++BA;840 ASSERT_TRUE(BA.valid());841 EXPECT_EQ(420u, BA.b().start());842 EXPECT_EQ(402u, BA.a().start());843 BA.skipA();844 ASSERT_TRUE(BA.valid());845 EXPECT_EQ(600u, BA.b().start());846 EXPECT_EQ(600u, BA.a().start());847 ++BA;848 EXPECT_FALSE(BA.valid());849 850 // Test advanceTo.851 UUOverlaps BA2(mapB, mapA);852 BA2.advanceTo(410);853 ASSERT_TRUE(BA2.valid());854 EXPECT_EQ(410u, BA2.b().start());855 EXPECT_EQ(402u, BA2.a().start());856 857 BA2.advanceTo(411);858 ASSERT_TRUE(BA2.valid());859 EXPECT_EQ(410u, BA2.b().start());860 EXPECT_EQ(402u, BA2.a().start());861}862 863} // namespace864