unittests/tests/RangeMapTest.cpp

   1 #include <muleunit/test.h>
   2 #include <algorithm>
   3 #include "Types.h"
   4 #include "RangeMap.h"
   5
   6
   7 using namespace muleunit;
   8
   9 typedef CRangeMap<int> TestRangeMap;
  10
  11
  12 /**
  13  * Returns the contents of a TestRangeMap iterator as a string-presentation.
  14  */
  15 wxString StringFrom(const TestRangeMap::const_iterator& it)
  16 {
  17         return wxString::Format(wxT("(%") wxLongLongFmtSpec wxT("u, %")  wxLongLongFmtSpec wxT("u, %i)"), it.keyStart(), it.keyEnd(), *it);
  18 }
  19
  20 /**
  21  * Returns the contents of a TestRangeMap iterator as a string-presentation.
  22  */
  23 wxString StringFrom(TestRangeMap::iterator it)
  24 {
  25         return wxString::Format(wxT("(%") wxLongLongFmtSpec wxT("u, %")  wxLongLongFmtSpec wxT("u, %i)"), it.keyStart(), it.keyEnd(), *it);
  26 }
  27
  28
  29 /**
  30  * Returns the contents of a CRangeSet iterator as a string-presentation.
  31  */
  32 wxString StringFrom(const CRangeMap<void>::const_iterator& it)
  33 {
  34         return wxString::Format(wxT("(%") wxLongLongFmtSpec wxT("u, %")  wxLongLongFmtSpec wxT("u)"), it.keyStart(), it.keyEnd());
  35 }
  36
  37 /**
  38  * Returns the contents of a CRangeSet iterator as a string-presentation.
  39  */
  40 wxString StringFrom(CRangeMap<void>::iterator it)
  41 {
  42         return wxString::Format(wxT("(%") wxLongLongFmtSpec wxT("u, %")  wxLongLongFmtSpec wxT("u)"), it.keyStart(), it.keyEnd());
  43 }
  44
  45
  46
  47 /**
  48  * Returns the contents of a TestRangeMap as a string-representation.
  49  *
  50  * Using this function allows for easy comparison against the expected
  51  * result of a particular test.
  52  */
  53 template <typename VALUE>
  54 wxString StringFrom(const CRangeMap<VALUE>& map)
  55 {
  56         wxString stream;
  57
  58         typename CRangeMap<VALUE>::const_iterator it = map.begin();
  59         for (; it != map.end(); ++it) {
  60                 if (it != map.begin()) {
  61                         stream << wxT(", ");
  62                 }
  63
  64                 stream += StringFrom(it);
  65         }
  66
  67         return wxT("[") + stream + wxT("]");
  68 }
  69
  70
  71
  72 DECLARE(RangeMap);
  73         TestRangeMap m_map;
  74         TestRangeMap m_mmaps[3];
  75
  76         // Identifers for the multirange maps
  77         enum Maps {
  78                 CONT  = 0, // Continues ranges, IE no gap
  79                 SSAME = 1, // Seperated but equal
  80                 SDIFF = 2  // Seperated and not equal
  81         };
  82
  83         // Sets up a few maps with predefined ranges.
  84         void setUp() {
  85                 m_map.insert(100, 150, 0);
  86
  87                 m_mmaps[CONT].insert(100, 150, 0);
  88                 m_mmaps[CONT].insert(151, 200, 1);
  89
  90                 m_mmaps[SDIFF].insert(100, 150, 0);
  91                 m_mmaps[SDIFF].insert(160, 200, 1);
  92
  93                 m_mmaps[SSAME].insert(100, 150, 1);
  94                 m_mmaps[SSAME].insert(160, 200, 1);
  95
  96                 ASSERT_EQUALS(wxT("[(100, 150, 0)]"), StringFrom(m_map));
  97                 ASSERT_EQUALS(wxT("[(100, 150, 0), (151, 200, 1)]"), StringFrom(m_mmaps[CONT]));
  98                 ASSERT_EQUALS(wxT("[(100, 150, 0), (160, 200, 1)]"), StringFrom(m_mmaps[SDIFF]));
  99                 ASSERT_EQUALS(wxT("[(100, 150, 1), (160, 200, 1)]"), StringFrom(m_mmaps[SSAME]));
 100         }
 101
 102         void tearDown() {
 103                 m_map.clear();
 104                 m_mmaps[0].clear();
 105                 m_mmaps[1].clear();
 106                 m_mmaps[2].clear();
 107         }
 108
 109
 110         /**
 111          * Tests insertion into a map with a single range, checking against an
 112          * expected result.
 113          */
 114         void singleInsert(uint32 start, uint32 end, int value, const wxString& result)
 115         {
 116                 TestRangeMap::iterator it = m_map.insert(start, end, value);
 117
 118                 // Test that the correct iterator was returned
 119                 ASSERT_TRUE(it.keyStart() <= start);
 120                 ASSERT_TRUE(it.keyEnd() >= end);
 121                 ASSERT_EQUALS(*it, value);
 122
 123                 // Check the resulting map
 124                 ASSERT_EQUALS(result, StringFrom(m_map));
 125                 ASSERT_EQUALS((uint32)std::count(result.begin(), result.end(), '('), m_map.size());
 126
 127                 // Reset the rangemap
 128                 tearDown();
 129                 setUp();
 130         }
 131
 132         void doErase(uint32 start, uint32 end, const wxString& result)
 133         {
 134                 m_map.erase_range(start, end);
 135
 136                 // Check the resulting map
 137                 ASSERT_EQUALS(result, StringFrom(m_map));
 138                 ASSERT_EQUALS((uint32)std::count(result.begin(), result.end(), '('), m_map.size());
 139
 140                 // Reset the rangemap
 141                 tearDown();
 142                 setUp();
 143         }
 144
 145         /**
 146          * Tests insertion into a map with multiple ranges, checking against an
 147          * expected result.
 148          */
 149         void multiInsert(int type, uint32 start, uint32 end, int value, const wxString& result)
 150         {
 151                 TestRangeMap::iterator it = m_mmaps[type].insert(start, end, value);
 152
 153                 // Test that the correct iterator was returned
 154                 ASSERT_TRUE(it.keyStart() <= start);
 155                 ASSERT_TRUE(it.keyEnd() >= end);
 156                 ASSERT_EQUALS(*it, value);
 157
 158                 // Check the resulting map
 159                 ASSERT_EQUALS(result, StringFrom(m_mmaps[type]));
 160                 ASSERT_EQUALS((uint32)std::count(result.begin(), result.end(), '('), m_mmaps[type].size());
 161
 162                 tearDown();
 163                 setUp();
 164         }
 165 END_DECLARE;
 166
 167
 168
 169 TEST(RangeMap, DefaultConstructor)
 170 {
 171         TestRangeMap map;
 172
 173         ASSERT_EQUALS(0u, map.size());
 174         ASSERT_TRUE(map.empty());
 175 }
 176
 177
 178 TEST(RangeMap, CopyConstructor)
 179 {
 180         // Check basic copying
 181         TestRangeMap mapA(m_map);
 182         TestRangeMap mapB(m_mmaps[CONT]);
 183         TestRangeMap mapC(m_mmaps[SSAME]);
 184         TestRangeMap mapD(m_mmaps[SDIFF]);
 185
 186         ASSERT_EQUALS(m_map, mapA);
 187         ASSERT_EQUALS(m_mmaps[CONT], mapB);
 188         ASSERT_EQUALS(m_mmaps[SSAME], mapC);
 189         ASSERT_EQUALS(m_mmaps[SDIFF], mapD);
 190
 191
 192         // The copies must not affect the originals
 193         mapA.insert(125, 175, 2);
 194         mapB.insert(125, 175, 2);
 195         mapC.insert(125, 175, 2);
 196         mapD.insert(125, 175, 2);
 197
 198         ASSERT_FALSE(m_map == mapA);
 199         ASSERT_FALSE(m_mmaps[CONT] == mapB);
 200         ASSERT_FALSE(m_mmaps[SSAME] == mapC);
 201         ASSERT_FALSE(m_mmaps[SDIFF] == mapD);
 202 }
 203
 204
 205 TEST(RangeMap, AssignmentOperator)
 206 {
 207         // Check basic assignment
 208         TestRangeMap mapA, mapB;
 209         mapA = mapB = m_map;
 210
 211         ASSERT_EQUALS(m_map, mapA);
 212         ASSERT_EQUALS(m_map, mapB);
 213
 214
 215         // The copies must not affect the originals
 216         mapA.insert(125, 175, 2);
 217         mapB.insert(125, 175, 2);
 218
 219         ASSERT_TRUE(mapA == mapB);
 220         ASSERT_FALSE(m_map == mapA);
 221         ASSERT_FALSE(m_map == mapB);
 222 }
 223
 224
 225 TEST(RangeMap, Equality)
 226 {
 227         TestRangeMap mapA(m_mmaps[SSAME]), mapB(m_mmaps[SDIFF]);
 228
 229         ASSERT_FALSE(mapA == mapB);
 230
 231         mapA = mapB;
 232
 233         ASSERT_EQUALS(mapA, mapB);
 234
 235         mapA.insert(10, 20, 3);
 236
 237         ASSERT_FALSE(mapA == mapB);
 238 }
 239
 240
 241 TEST(RangeMap, Iterators)
 242 {
 243         // Adding a third range
 244         m_mmaps[CONT].insert(125, 175, 2);
 245         TestRangeMap map(m_mmaps[CONT]);
 246
 247         TestRangeMap::iterator it = map.begin();
 248         TestRangeMap::iterator it_orig = map.begin();
 249         TestRangeMap::iterator it_other = map.end();
 250
 251         ASSERT_EQUALS(wxT("(100, 124, 0)"), StringFrom(it));
 252
 253         it_other = ++it;
 254
 255         ASSERT_EQUALS(wxT("(125, 175, 2)"), StringFrom(it));
 256         ASSERT_EQUALS(it_other, it++);
 257         ASSERT_EQUALS(wxT("(176, 200, 1)"), StringFrom(it));
 258
 259         it_other = --it;
 260
 261         ASSERT_EQUALS(wxT("(125, 175, 2)"), StringFrom(it));
 262         ASSERT_EQUALS(it_other, it--);
 263         ASSERT_EQUALS(wxT("(100, 124, 0)"), StringFrom(it));
 264 }
 265
 266
 267 TEST(RangeMap, Erase)
 268 {
 269         // Adding a third range
 270         m_mmaps[CONT].insert(125, 175, 2);
 271
 272         // The expected results from forwards deletion
 273         TestRangeMap map(m_mmaps[CONT]);
 274         wxString expectedFW[4];
 275         expectedFW[0] = wxT("[(100, 124, 0), (125, 175, 2), (176, 200, 1)]");
 276         expectedFW[1] = wxT("[(125, 175, 2), (176, 200, 1)]");
 277         expectedFW[2] = wxT("[(176, 200, 1)]");
 278         expectedFW[3] = wxT("[]");
 279
 280         for (int i = 0; i < 4; ++i) {
 281                 ASSERT_EQUALS(expectedFW[i], StringFrom(map));
 282
 283                 if (map.begin() != map.end()) {
 284                         map.erase(map.begin());
 285                 }
 286         }
 287
 288         // Test the expected result from backwards deletion
 289         map = m_mmaps[CONT];
 290         wxString expectedBW[4];
 291         expectedBW[0] = wxT("[(100, 124, 0), (125, 175, 2), (176, 200, 1)]");
 292         expectedBW[1] = wxT("[(100, 124, 0), (125, 175, 2)]");
 293         expectedBW[2] = wxT("[(100, 124, 0)]");
 294         expectedBW[3] = wxT("[]");
 295
 296         for (int i = 0; i < 4; ++i) {
 297                 ASSERT_EQUALS(expectedBW[i], StringFrom(map));
 298
 299                 if (map.begin() != map.end()) {
 300                         map.erase(--map.end());
 301                 }
 302         }
 303 }
 304
 305
 306 TEST(RangeMap, Clear)
 307 {
 308         m_map.clear();
 309         ASSERT_TRUE(m_map.empty());
 310         ASSERT_EQUALS(0u, m_map.size());
 311         ASSERT_EQUALS(wxT("[]"), StringFrom(m_map));
 312
 313         for (int i = 0; i < 3; ++i) {
 314                 m_mmaps[i].clear();
 315                 ASSERT_TRUE(m_mmaps[i].empty());
 316                 ASSERT_EQUALS(0u, m_mmaps[i].size());
 317                 ASSERT_EQUALS(wxT("[]"), StringFrom(m_mmaps[i]));
 318         }
 319 }
 320
 321
 322 TEST(RangeMap, FindRange)
 323 {
 324         // Adding a third range
 325         m_mmaps[CONT].insert(125, 175, 2);
 326         TestRangeMap map(m_mmaps[CONT]);
 327
 328         ASSERT_EQUALS(map.end(), map.find_range(0));
 329         ASSERT_EQUALS(map.end(), map.find_range(98));
 330         ASSERT_EQUALS(map.end(), map.find_range(99));
 331
 332         ASSERT_EQUALS(wxT("(100, 124, 0)"), StringFrom(map.find_range(100)));
 333         ASSERT_EQUALS(wxT("(100, 124, 0)"), StringFrom(map.find_range(112)));
 334         ASSERT_EQUALS(wxT("(100, 124, 0)"), StringFrom(map.find_range(124)));
 335
 336         ASSERT_EQUALS(wxT("(125, 175, 2)"), StringFrom(map.find_range(125)));
 337         ASSERT_EQUALS(wxT("(125, 175, 2)"), StringFrom(map.find_range(150)));
 338         ASSERT_EQUALS(wxT("(125, 175, 2)"), StringFrom(map.find_range(175)));
 339
 340         ASSERT_EQUALS(wxT("(176, 200, 1)"), StringFrom(map.find_range(176)));
 341         ASSERT_EQUALS(wxT("(176, 200, 1)"), StringFrom(map.find_range(186)));
 342         ASSERT_EQUALS(wxT("(176, 200, 1)"), StringFrom(map.find_range(200)));
 343
 344         ASSERT_EQUALS(map.end(), map.find_range(201));
 345         ASSERT_EQUALS(map.end(), map.find_range(202));
 346         ASSERT_EQUALS(map.end(), map.find_range(250));
 347 }
 348
 349
 350 TEST(RangeMap, InvalidErase)
 351 {
 352         ASSERT_RAISES(CInvalidParamsEx, m_map.erase(m_map.end()));
 353 }
 354
 355
 356 TEST(RangeMap, InvalidInsert)
 357 {
 358         ASSERT_RAISES(CInvalidParamsEx, m_map.insert(10, 9, 8));
 359 }
 360
 361
 362 /////////////////////////////////////////////////
 363 // The following tests exercize the merging algorithm.
 364 // The comment before each comment descrices the RangeMaps used to test,
 365 // and which types of ranges are tested. For example, the description
 366 // "a / b <-> c / d" is to be read as:
 367 //   Insert range starting at a or b, ending at c or d.
 368
 369
 370 // Single insert before start <-> before start.
 371 TEST(RangeMap, SingleInsert_BeforeStart_BeforeStart)
 372 {
 373         // Test with same and different type
 374         singleInsert(0, 90, 0, wxT("[(0, 90, 0), (100, 150, 0)]"));
 375         singleInsert(0, 90, 1, wxT("[(0, 90, 1), (100, 150, 0)]"));
 376 }
 377
 378
 379 // Single insert before start <-> touching start.
 380 TEST(RangeMap, SingleInsert_BeforeStart_TouchingStart)
 381 {
 382         singleInsert(0, 99, 0, wxT("[(0, 150, 0)]")); // Same type
 383         singleInsert(0, 99, 1, wxT("[(0, 99, 1), (100, 150, 0)]")); // Different type
 384 }
 385
 386
 387 // Single insert before start <-> at start / inside.
 388 TEST(RangeMap, SingleInsert_BeforeStart_AtStart_InSide)
 389 {
 390         for (int offset = 0; offset < 3; ++offset) { // at start, inside, inside
 391                 singleInsert(0, 100 + offset, 0, wxT("[(0, 150, 0)]")); // Same type
 392
 393                 wxString expected = wxString::Format(wxT("[(0, %u, 1), (%u, 150, 0)]"), 100 + offset, 101 + offset);
 394                 singleInsert(0, 100 + offset, 1, expected); // Different type
 395         }
 396 }
 397
 398
 399 // Single insert before start / touching start <-> at end / touching end / after end.
 400 TEST(RangeMap, SingleInsert_BeforeStart_TouchingStart_AtEnd_TouchingEnd_AfterEnd)
 401 {
 402         // Test with same and different type
 403         for (int type = 0; type < 2; ++type) {
 404                 // (at end, touching end, after end)
 405                 for (int end_offset = 0; end_offset < 3; ++end_offset) {
 406                         // (before start, touching start)
 407                         for (int start_offset = 0; start_offset < 2; ++start_offset) {
 408                                 wxString expected = wxString::Format(wxT("[(%u, %u, %i)]"), 98 + start_offset, 150 + end_offset, type);
 409                                 singleInsert(98 + start_offset, 150 + end_offset, type, expected);
 410                         }
 411                 }
 412         }
 413 }
 414
 415
 416 // Single insert touching start <-> touching start.
 417 TEST(RangeMap, SingleInsert_TouchingStart_TouchingStart)
 418 {
 419         singleInsert(99, 99, 0, wxT("[(99, 150, 0)]")); // Same
 420         singleInsert(99, 99, 1, wxT("[(99, 99, 1), (100, 150, 0)]")); // Different
 421 }
 422
 423
 424 // Single insert touching start / at start <-> at start / inside.
 425 TEST(RangeMap, SingleInsert_TouchingStart_AtStart_AtStart_Inside)
 426 {
 427         for (int offset_a = 0; offset_a < 2; ++offset_a) { // (touching start, at start)
 428                 for (int offset_b = 0; offset_b < 2; ++offset_b) { // (at start, inside)
 429                         int start = 99 + offset_a;
 430                         int end   = 100 + offset_b;
 431
 432                         // Same
 433                         singleInsert(start, end, 0, wxString::Format(wxT("[(%u, 150, 0)]"), 99 + offset_a));
 434
 435                         // Different
 436                         wxString exp = wxString::Format(wxT("[(%u, %u, 1), (%u, 150, 0)]"), start, end, 101 + offset_b);
 437                         singleInsert(start, end, 1, exp);
 438                 }
 439         }
 440 }
 441
 442
 443 // Single insert at start <-> at end / touching end / after end.
 444 TEST(RangeMap, SingleInsert_AtStart_AtEnd_TouchingEnd_AfterEnd)
 445 {
 446         // (at end, touching end, after end)
 447         for (int offset = 0; offset < 3; ++offset) {
 448                 // Same
 449                 singleInsert(100, 150 + offset, 0, wxString::Format(wxT("[(100, %u, 0)]"), 150 + offset));
 450                 // Different
 451                 singleInsert(100, 150 + offset, 1, wxString::Format(wxT("[(100, %u, 1)]"), 150 + offset));
 452         }
 453 }
 454
 455
 456 // Single insert inside / at end <-> at end / touching end / after end.
 457 TEST(RangeMap, SingleInsert_Inside_AtEnd_AtEnd_TouchingEnd_AfterEnd)
 458 {
 459         // (inside, at end)
 460         for (int offset_a = 0; offset_a < 2; ++offset_a) {
 461                 // (at end, touching end, after end)
 462                 for (int offset_b = 0; offset_b < 3; ++offset_b) {
 463                         int start = 149 + offset_a;
 464                         int end   = 150 + offset_b;
 465
 466                         // Same
 467                         singleInsert(start, end, 0, wxString::Format(wxT("[(100, %u, 0)]"), end));
 468
 469                         // Different
 470                         singleInsert(start, end, 1, wxString::Format(wxT("[(100, %u, 0), (%u, %u, 1)]"), 148 + offset_a, start, end));
 471                 }
 472         }
 473 }
 474
 475
 476 // Single insert touching end <-> touching end / after end.
 477 TEST(RangeMap, SingleInsert_TouchingEnd_TouchingEnd_AfterEnd)
 478 {
 479         // (touching end, after end)
 480         for (int offset = 0; offset < 2; ++offset) {
 481                 int end = 151 + offset;
 482
 483                 // Same
 484                 singleInsert(151, end, 0, wxString::Format(wxT("[(100, %u, 0)]"), end));
 485
 486                 // Different
 487                 singleInsert(151, end, 1, wxString::Format(wxT("[(100, 150, 0), (151, %u, 1)]"), end));
 488         }
 489 }
 490
 491
 492 // Single insert after end <-> after end.
 493 TEST(RangeMap, SingleInsert_AfterEnd_AfterEnd)
 494 {
 495         singleInsert(152, 170, 0, wxT("[(100, 150, 0), (152, 170, 0)]")); // Same
 496         singleInsert(152, 170, 1, wxT("[(100, 150, 0), (152, 170, 1)]")); // Different
 497 }
 498
 499
 500 // Multi insert before start <-> before start.
 501 TEST(RangeMap, MultiInsert_BeforeStart_BeforeStart)
 502 {
 503         for (int type = 0; type < 2; ++type) { // Test with same and different type
 504                 multiInsert(CONT, 0, 90, type, wxString(wxT("[(0, 90, ")) << type << wxT("), (100, 150, 0), (151, 200, 1)]"));
 505                 multiInsert(SDIFF, 0, 90, type, wxString(wxT("[(0, 90, ")) << type << wxT("), (100, 150, 0), (160, 200, 1)]"));
 506                 multiInsert(SSAME, 0, 90, type, wxString(wxT("[(0, 90, ")) << type << wxT("), (100, 150, 1), (160, 200, 1)]"));
 507         }
 508 }
 509
 510
 511 // Multi insert before start <-> touching start.
 512 TEST(RangeMap, MultiInsert_BeforeStart_TouchingStart)
 513 {
 514         multiInsert(CONT, 0, 99, 0, wxT("[(0, 150, 0), (151, 200, 1)]"));
 515         multiInsert(SDIFF, 0, 99, 0, wxT("[(0, 150, 0), (160, 200, 1)]"));
 516         multiInsert(SSAME, 0, 99, 0, wxT("[(0, 99, 0), (100, 150, 1), (160, 200, 1)]"));
 517
 518         multiInsert(CONT, 0, 99, 1, wxT("[(0, 99, 1), (100, 150, 0), (151, 200, 1)]"));
 519         multiInsert(SDIFF, 0, 99, 1, wxT("[(0, 99, 1), (100, 150, 0), (160, 200, 1)]"));
 520         multiInsert(SSAME, 0, 99, 1, wxT("[(0, 150, 1), (160, 200, 1)]"));
 521 }
 522
 523
 524 // Multi insert before start <-> at start / inside.
 525 TEST(RangeMap, MultiInsert_BeforeStart_AtStart_InSide)
 526 {
 527         for (int offset = 0; offset < 3; ++offset) { // (at start, inside, inside)
 528                 int end = 100 + offset;
 529
 530                 multiInsert(CONT, 0, end, 0, wxT("[(0, 150, 0), (151, 200, 1)]"));
 531                 multiInsert(SDIFF, 0, end, 0, wxT("[(0, 150, 0), (160, 200, 1)]"));
 532                 multiInsert(SSAME, 0, end, 0, wxString::Format(wxT("[(0, %u, 0), (%u, 150, 1), (160, 200, 1)]"), end, 101 + offset));
 533
 534                 multiInsert(CONT, 0, end, 1, wxString::Format(wxT("[(0, %u, 1), (%u, 150, 0), (151, 200, 1)]"), end, 101 + offset));
 535                 multiInsert(SDIFF, 0, end, 1, wxString::Format(wxT("[(0, %u, 1), (%u, 150, 0), (160, 200, 1)]"), end, 101 + offset));
 536                 multiInsert(SSAME, 0, end, 1, wxT("[(0, 150, 1), (160, 200, 1)]"));
 537         }
 538 }
 539
 540
 541 // Multi insert before start / touching start <-> at end / touching end / after end.
 542 TEST(RangeMap, MultiInsert_BeforeStart_TouchingStart_AtEnd_TouchingEnd_AfterEnd)
 543 {
 544         for (int end_offset = 0; end_offset < 3; ++end_offset) { // (at end, touching end, after end)
 545                 for (int start_offset = 0; start_offset < 2; ++start_offset) { // (before start, touching start)
 546                         int start = 98 + start_offset;
 547                         int end   = 150 + end_offset;
 548
 549                         multiInsert(CONT, start, end, 0, wxString::Format(wxT("[(%u, %u, 0), (%u, 200, 1)]"), start, end, end + 1));
 550                         multiInsert(SDIFF, start, end, 0, wxString::Format(wxT("[(%u, %u, 0), (160, 200, 1)]"), start, end));
 551                         multiInsert(SSAME, start, end, 0, wxString::Format(wxT("[(%u, %u, 0), (160, 200, 1)]"), start, end));
 552
 553                         multiInsert(CONT, start, end, 1, wxString::Format(wxT("[(%u, 200, 1)]"), start));
 554                         multiInsert(SDIFF, start, end, 1, wxString::Format(wxT("[(%u, %u, 1), (160, 200, 1)]"), start, end));
 555                         multiInsert(SSAME, start, end, 1, wxString::Format(wxT("[(%u, %u, 1), (160, 200, 1)]"), start, end));
 556                 }
 557         }
 558 }
 559
 560
 561 // Multi insert touching start <-> touching start.
 562 TEST(RangeMap, MultiInsert_TouchingStart_TouchingStart)
 563 {
 564         multiInsert(CONT, 99, 99, 0, wxT("[(99, 150, 0), (151, 200, 1)]"));
 565         multiInsert(SDIFF, 99, 99, 0, wxT("[(99, 150, 0), (160, 200, 1)]"));
 566         multiInsert(SSAME, 99, 99, 0, wxT("[(99, 99, 0), (100, 150, 1), (160, 200, 1)]"));
 567
 568         multiInsert(CONT, 99, 99, 1, wxT("[(99, 99, 1), (100, 150, 0), (151, 200, 1)]"));
 569         multiInsert(SDIFF, 99, 99, 1, wxT("[(99, 99, 1), (100, 150, 0), (160, 200, 1)]"));
 570         multiInsert(SSAME, 99, 99, 1, wxT("[(99, 150, 1), (160, 200, 1)]"));
 571 }
 572
 573
 574 // Multi insert touching start / at start <-> at start / inside.
 575 TEST(RangeMap, MultiInsert_TouchingStart_AtStart_AtStart_Inside)
 576 {
 577         for (int offset_a = 0; offset_a < 2; ++offset_a) { // (touching start, at start)
 578                 for (int offset_b = 0; offset_b < 2; ++offset_b) { // (at start, inside)
 579                         int start = 99 + offset_a;
 580                         int end   = 100 + offset_b;
 581
 582                         multiInsert(CONT, start, end, 0, wxString::Format(wxT("[(%u, 150, 0), (151, 200, 1)]"), start));
 583                         multiInsert(SDIFF, start, end, 0, wxString::Format(wxT("[(%u, 150, 0), (160, 200, 1)]"), start));
 584                         multiInsert(SSAME, start, end, 0, wxString::Format(wxT("[(%u, %u, 0), (%u, 150, 1), (160, 200, 1)]"), start, end, end + 1));
 585
 586                         multiInsert(CONT, start, end, 1, wxString::Format(wxT("[(%u, %u, 1), (%u, 150, 0), (151, 200, 1)]"), start, end, end + 1));
 587                         multiInsert(SDIFF, start, end, 1, wxString::Format(wxT("[(%u, %u, 1), (%u, 150, 0), (160, 200, 1)]"), start, end, end + 1));
 588                         multiInsert(SSAME, start, end, 1, wxString::Format(wxT("[(%u, 150, 1), (160, 200, 1)]"), start));
 589                 }
 590         }
 591 }
 592
 593
 594 // rangeMap: Multi insert at start <-> at end / touching end / after end.
 595 TEST(RangeMap, MultiInsert_AtStart_AtEnd_TouchingEnd_AfterEnd)
 596 {
 597         for (int offset = 0; offset < 3; ++offset) { // (at end, touching end, after end)
 598                 int start = 100;
 599                 int end   = 150 + offset;
 600
 601                 multiInsert(CONT, start, end, 0, wxString::Format(wxT("[(%u, %u, 0), (%u, 200, 1)]"), start, end, end + 1));
 602                 multiInsert(SDIFF, start, end, 0, wxString::Format(wxT("[(%u, %u, 0), (160, 200, 1)]"), start, end));
 603                 multiInsert(SSAME, start, end, 0, wxString::Format(wxT("[(%u, %u, 0), (160, 200, 1)]"), start, end));
 604
 605                 multiInsert(CONT, start, end, 1, wxString::Format(wxT("[(%u, 200, 1)]"), start));
 606                 multiInsert(SDIFF, start, end, 1, wxString::Format(wxT("[(%u, %u, 1), (160, 200, 1)]"), start, end));
 607                 multiInsert(SSAME, start, end, 1, wxString::Format(wxT("[(%u, %u, 1), (160, 200, 1)]"), start, end));
 608         }
 609 }
 610
 611
 612 // Multi insert inside <-> inside.
 613 TEST(RangeMap, MultiInsert_Inside_Inside)
 614 {
 615         multiInsert(CONT, 110, 140, 0, wxT("[(100, 150, 0), (151, 200, 1)]"));
 616         multiInsert(SDIFF, 110, 140, 0, wxT("[(100, 150, 0), (160, 200, 1)]"));
 617         multiInsert(SSAME, 110, 140, 0, wxT("[(100, 109, 1), (110, 140, 0), (141, 150, 1), (160, 200, 1)]"));
 618
 619         multiInsert(CONT, 110, 140, 1, wxT("[(100, 109, 0), (110, 140, 1), (141, 150, 0), (151, 200, 1)]"));
 620         multiInsert(SDIFF, 110, 140, 1, wxT("[(100, 109, 0), (110, 140, 1), (141, 150, 0), (160, 200, 1)]"));
 621         multiInsert(SSAME, 110, 140, 1, wxT("[(100, 150, 1), (160, 200, 1)]"));
 622 }
 623
 624
 625 // Multi insert inside / at end <-> at end / touching end / after end.
 626 TEST(RangeMap, MultiInsert_Inside_AtEnd_AtEnd_TouchingEnd_AfterEnd)
 627 {
 628         for (int offset_a = 0; offset_a < 2; ++offset_a) { // (inside, at end)
 629                 for (int offset_b = 0; offset_b < 3; ++offset_b) { // (at end, touching end, after end)
 630                         int start = 149 + offset_a;
 631                         int end   = 150 + offset_b;
 632
 633                         multiInsert(CONT, start, end, 0, wxString::Format(wxT("[(100, %u, 0), (%u, 200, 1)]"), end, end + 1));
 634                         multiInsert(SDIFF, start, end, 0, wxString::Format(wxT("[(100, %u, 0), (160, 200, 1)]"), end));
 635                         multiInsert(SSAME, start, end, 0, wxString::Format(wxT("[(100, %u, 1), (%u, %u, 0), (160, 200, 1)]"), start - 1, start, end));
 636
 637                         multiInsert(CONT, start, end, 1, wxString::Format(wxT("[(100, %u, 0), (%u, 200, 1)]"), start - 1, start));
 638                         multiInsert(SDIFF, start, end, 1, wxString::Format(wxT("[(100, %u, 0), (%u, %u, 1), (160, 200, 1)]"), start - 1, start, end));
 639                         multiInsert(SSAME, start, end, 1, wxString::Format(wxT("[(100, %u, 1), (160, 200, 1)]"), end));
 640                 }
 641         }
 642 }
 643
 644
 645 // Multi insert touching end <-> touching end / after end.
 646 TEST(RangeMap, MultiInsert_TouchingEnd_TouchingEnd_AfterEnd)
 647 {
 648         for (int offset = 0; offset < 2; ++offset) { // (touching end, after end)
 649                 int start = 151;
 650                 int end   = 151 + offset;
 651
 652                 multiInsert(CONT, start, end, 0, wxString::Format(wxT("[(100, %u, 0), (%u, 200, 1)]"), end, end + 1));
 653                 multiInsert(SDIFF, start, end, 0, wxString::Format(wxT("[(100, %u, 0), (160, 200, 1)]"), end));
 654                 multiInsert(SSAME, start, end, 0, wxString::Format(wxT("[(100, 150, 1), (%u, %u, 0), (160, 200, 1)]"), start, end));
 655
 656                 multiInsert(CONT, start, end, 1, wxString::Format(wxT("[(100, 150, 0), (%u, 200, 1)]"), start));
 657                 multiInsert(SDIFF, start, end, 1, wxString::Format(wxT("[(100, 150, 0), (%u, %u, 1), (160, 200, 1)]"), start, end));
 658                 multiInsert(SSAME, start, end, 1, wxString::Format(wxT("[(100, %u, 1), (160, 200, 1)]"), end));
 659         }
 660 }
 661
 662
 663 // Multi insert after end <-> after end.
 664 TEST(RangeMap, MultiInsert_AfterEnd_AfterEnd)
 665 {
 666         multiInsert(CONT, 152, 170, 0, wxT("[(100, 150, 0), (151, 151, 1), (152, 170, 0), (171, 200, 1)]"));
 667         multiInsert(SDIFF, 152, 170, 0, wxT("[(100, 150, 0), (152, 170, 0), (171, 200, 1)]"));
 668         multiInsert(SSAME, 152, 170, 0, wxT("[(100, 150, 1), (152, 170, 0), (171, 200, 1)]"));
 669
 670         multiInsert(CONT, 152, 170, 1, wxT("[(100, 150, 0), (151, 200, 1)]"));
 671         multiInsert(SDIFF, 152, 170, 1, wxT("[(100, 150, 0), (152, 200, 1)]"));
 672         multiInsert(SSAME, 152, 170, 1, wxT("[(100, 150, 1), (152, 200, 1)]"));
 673 }
 674
 675
 676 /////////////////////////////////////////////////
 677 // The following tests exercize the erase function.
 678 // Since the erase function use the insert function, all
 679 // that is needed is to test that no merging is done.
 680
 681 // Single erase before start <-> before start.
 682 TEST(RangeMap, Erase_BeforeStart_BeforeStart)
 683 {
 684         // Test with same and different type
 685         doErase(0, 90, wxT("[(100, 150, 0)]"));
 686 }
 687
 688
 689 // Single erase before start <-> touching start.
 690 TEST(RangeMap, Erase_BeforeStart_TouchingStart)
 691 {
 692         doErase(0, 99, wxT("[(100, 150, 0)]"));
 693 }
 694
 695
 696 // Single erase before start <-> at start / inside.
 697 TEST(RangeMap, Erase_BeforeStart_AtStart_InSide)
 698 {
 699         for (int offset = 0; offset < 3; ++offset) { // at start, inside, inside
 700                 doErase(0, 100 + offset, wxString::Format(wxT("[(%u, 150, 0)]"), 100 + offset + 1));
 701         }
 702 }
 703
 704
 705 // Single erase before start / touching start <-> at end / touching end / after end.
 706 TEST(RangeMap, Erase_BeforeStart_TouchingStart_AtEnd_TouchingEnd_AfterEnd)
 707 {
 708         // (at end, touching end, after end)
 709         for (int end_offset = 0; end_offset < 3; ++end_offset) {
 710                 // (before start, touching start)
 711                 for (int start_offset = 0; start_offset < 2; ++start_offset) {
 712                         doErase(98 + start_offset, 150 + end_offset, wxT("[]"));
 713                 }
 714         }
 715 }
 716
 717
 718 // Single erase touching start <-> touching start.
 719 TEST(RangeMap, Erase_TouchingStart_TouchingStart)
 720 {
 721         doErase(99, 99, wxT("[(100, 150, 0)]"));
 722 }
 723
 724
 725 // Single erase touching start / at start <-> at start / inside.
 726 TEST(RangeMap, Erase_TouchingStart_AtStart_AtStart_Inside)
 727 {
 728         for (int offset_a = 0; offset_a < 2; ++offset_a) { // (touching start, at start)
 729                 for (int offset_b = 0; offset_b < 2; ++offset_b) { // (at start, inside)
 730                         int start = 99 + offset_a;
 731                         int end   = 100 + offset_b;
 732
 733                         doErase(start, end, wxString::Format(wxT("[(%u, 150, 0)]"), 100 + offset_b + 1));
 734                 }
 735         }
 736 }
 737
 738
 739 // Single erase at start <-> at end / touching end / after end.
 740 TEST(RangeMap, Erase_AtStart_AtEnd_TouchingEnd_AfterEnd)
 741 {
 742         // (at end, touching end, after end)
 743         for (int offset = 0; offset < 3; ++offset) {
 744                 doErase(100, 150 + offset, wxT("[]"));
 745         }
 746 }
 747
 748
 749 // Single erase inside / at end <-> at end / touching end / after end.
 750 TEST(RangeMap, Erase_Inside_AtEnd_AtEnd_TouchingEnd_AfterEnd)
 751 {
 752         // (inside, at end)
 753         for (int offset_a = 0; offset_a < 2; ++offset_a) {
 754                 // (at end, touching end, after end)
 755                 for (int offset_b = 0; offset_b < 3; ++offset_b) {
 756                         int start = 149 + offset_a;
 757                         int end   = 150 + offset_b;
 758
 759                         doErase(start, end, wxString::Format(wxT("[(100, %u, 0)]"), start - 1));
 760                 }
 761         }
 762 }
 763
 764
 765 // Single erase touching end <-> touching end / after end.
 766 TEST(RangeMap, Erase_TouchingEnd_TouchingEnd_AfterEnd)
 767 {
 768         // (touching end, after end)
 769         for (int offset = 0; offset < 2; ++offset) {
 770                 int end = 151 + offset;
 771
 772                 doErase(151, end, wxT("[(100, 150, 0)]"));
 773         }
 774 }
 775
 776
 777 // Single erase after end <-> after end.
 778 TEST(RangeMap, Erase_AfterEnd_AfterEnd)
 779 {
 780         doErase(152, 170, wxT("[(100, 150, 0)]"));
 781 }
 782
 783
 784 TEST(RangeMap, Swap)
 785 {
 786         {
 787                 TestRangeMap mapA = m_mmaps[CONT];
 788                 TestRangeMap mapB = m_mmaps[SSAME];
 789
 790                 ASSERT_EQUALS(mapA, m_mmaps[CONT]);
 791                 ASSERT_EQUALS(mapB, m_mmaps[SSAME]);
 792
 793                 std::swap(mapA, mapB);
 794
 795                 ASSERT_EQUALS(mapB, m_mmaps[CONT]);
 796                 ASSERT_EQUALS(mapA, m_mmaps[SSAME]);
 797         }
 798
 799         {
 800                 TestRangeMap mapA = m_mmaps[CONT];
 801                 TestRangeMap mapB = m_mmaps[SSAME];
 802
 803                 ASSERT_EQUALS(mapA, m_mmaps[CONT]);
 804                 ASSERT_EQUALS(mapB, m_mmaps[SSAME]);
 805
 806                 mapA.swap(mapB);
 807
 808                 ASSERT_EQUALS(mapB, m_mmaps[CONT]);
 809                 ASSERT_EQUALS(mapA, m_mmaps[SSAME]);
 810         }
 811 }
 812
 813
 814 /////////////////////////////////////////////////
 815 // The following test exercize the CRangeSet specialization.
 816 //
 817
 818 TEST(RangeMap, RangeSet)
 819 {
 820         CRangeSet set;
 821
 822         set.insert(0, 10);
 823         set.insert(20, 30);
 824         set.insert(40, 50);
 825
 826         ASSERT_EQUALS(wxT("[(0, 10), (20, 30), (40, 50)]"), StringFrom(set));
 827         ASSERT_EQUALS(3u, set.size());
 828
 829         {
 830                 CRangeSet::iterator it = set.begin();
 831                 unsigned value = 0;
 832                 for (; it != set.end(); ++it, value += 20) {
 833                         ASSERT_EQUALS(value, it.keyStart());
 834                         ASSERT_EQUALS(value + 10, it.keyEnd());
 835                 }
 836
 837                 ASSERT_EQUALS(60u, value);
 838         }
 839
 840         set.erase_range(5, 45);
 841
 842         ASSERT_EQUALS(wxT("[(0, 4), (46, 50)]"), StringFrom(set));
 843         ASSERT_EQUALS(2u, set.size());
 844 }
 845