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