1 // Copyright (c) 2017 Google Inc. 2 // 3 // Licensed under the Apache License, Version 2.0 (the "License"); 4 // you may not use this file except in compliance with the License. 5 // You may obtain a copy of the License at 6 // 7 // http://www.apache.org/licenses/LICENSE-2.0 8 // 9 // Unless required by applicable law or agreed to in writing, software 10 // distributed under the License is distributed on an "AS IS" BASIS, 11 // WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. 12 // See the License for the specific language governing permissions and 13 // limitations under the License. 14 15 #include <algorithm> 16 #include <iostream> 17 #include <set> 18 #include <string> 19 #include <vector> 20 21 #include "gmock/gmock.h" 22 #include "source/comp/move_to_front.h" 23 24 namespace spvtools { 25 namespace comp { 26 namespace { 27 28 // Class used to test the inner workings of MoveToFront. 29 class MoveToFrontTester : public MoveToFront { 30 public: 31 // Inserts the value in the internal tree data structure. For testing only. 32 void TestInsert(uint32_t val) { InsertNode(CreateNode(val, val)); } 33 34 // Removes the value from the internal tree data structure. For testing only. 35 void TestRemove(uint32_t val) { 36 const auto it = value_to_node_.find(val); 37 assert(it != value_to_node_.end()); 38 RemoveNode(it->second); 39 } 40 41 // Prints the internal tree data structure to |out|. For testing only. 42 void PrintTree(std::ostream& out, bool print_timestamp = false) const { 43 if (root_) PrintTreeInternal(out, root_, 1, print_timestamp); 44 } 45 46 // Returns node handle corresponding to the value. The value may not be in the 47 // tree. 48 uint32_t GetNodeHandle(uint32_t value) const { 49 const auto it = value_to_node_.find(value); 50 if (it == value_to_node_.end()) return 0; 51 52 return it->second; 53 } 54 55 // Returns total node count (both those in the tree and removed, 56 // but not the NIL singleton). 57 size_t GetTotalNodeCount() const { 58 assert(nodes_.size()); 59 return nodes_.size() - 1; 60 } 61 62 uint32_t GetLastAccessedValue() const { return last_accessed_value_; } 63 64 private: 65 // Prints the internal tree data structure for debug purposes in the following 66 // format: 67 // 10H3S4----5H1S1-----D2 68 // 15H2S2----12H1S1----D3 69 // Right links are horizontal, left links step down one line. 70 // 5H1S1 is read as value 5, height 1, size 1. Optionally node label can also 71 // contain timestamp (5H1S1T15). D3 stands for depth 3. 72 void PrintTreeInternal(std::ostream& out, uint32_t node, size_t depth, 73 bool print_timestamp) const; 74 }; 75 76 void MoveToFrontTester::PrintTreeInternal(std::ostream& out, uint32_t node, 77 size_t depth, 78 bool print_timestamp) const { 79 if (!node) { 80 out << "D" << depth - 1 << std::endl; 81 return; 82 } 83 84 const size_t kTextFieldWvaluethWithoutTimestamp = 10; 85 const size_t kTextFieldWvaluethWithTimestamp = 14; 86 const size_t text_field_wvalueth = print_timestamp 87 ? kTextFieldWvaluethWithTimestamp 88 : kTextFieldWvaluethWithoutTimestamp; 89 90 std::stringstream label; 91 label << ValueOf(node) << "H" << HeightOf(node) << "S" << SizeOf(node); 92 if (print_timestamp) label << "T" << TimestampOf(node); 93 const size_t label_length = label.str().length(); 94 if (label_length < text_field_wvalueth) 95 label << std::string(text_field_wvalueth - label_length, '-'); 96 97 out << label.str(); 98 99 PrintTreeInternal(out, RightOf(node), depth + 1, print_timestamp); 100 101 if (LeftOf(node)) { 102 out << std::string(depth * text_field_wvalueth, ' '); 103 PrintTreeInternal(out, LeftOf(node), depth + 1, print_timestamp); 104 } 105 } 106 107 void CheckTree(const MoveToFrontTester& mtf, const std::string& expected, 108 bool print_timestamp = false) { 109 std::stringstream ss; 110 mtf.PrintTree(ss, print_timestamp); 111 EXPECT_EQ(expected, ss.str()); 112 } 113 114 TEST(MoveToFront, EmptyTree) { 115 MoveToFrontTester mtf; 116 CheckTree(mtf, std::string()); 117 } 118 119 TEST(MoveToFront, InsertLeftRotation) { 120 MoveToFrontTester mtf; 121 122 mtf.TestInsert(30); 123 mtf.TestInsert(20); 124 125 CheckTree(mtf, std::string(R"( 126 30H2S2----20H1S1----D2 127 )") 128 .substr(1)); 129 130 mtf.TestInsert(10); 131 CheckTree(mtf, std::string(R"( 132 20H2S3----10H1S1----D2 133 30H1S1----D2 134 )") 135 .substr(1)); 136 } 137 138 TEST(MoveToFront, InsertRightRotation) { 139 MoveToFrontTester mtf; 140 141 mtf.TestInsert(10); 142 mtf.TestInsert(20); 143 144 CheckTree(mtf, std::string(R"( 145 10H2S2----D1 146 20H1S1----D2 147 )") 148 .substr(1)); 149 150 mtf.TestInsert(30); 151 CheckTree(mtf, std::string(R"( 152 20H2S3----10H1S1----D2 153 30H1S1----D2 154 )") 155 .substr(1)); 156 } 157 158 TEST(MoveToFront, InsertRightLeftRotation) { 159 MoveToFrontTester mtf; 160 161 mtf.TestInsert(30); 162 mtf.TestInsert(20); 163 164 CheckTree(mtf, std::string(R"( 165 30H2S2----20H1S1----D2 166 )") 167 .substr(1)); 168 169 mtf.TestInsert(25); 170 CheckTree(mtf, std::string(R"( 171 25H2S3----20H1S1----D2 172 30H1S1----D2 173 )") 174 .substr(1)); 175 } 176 177 TEST(MoveToFront, InsertLeftRightRotation) { 178 MoveToFrontTester mtf; 179 180 mtf.TestInsert(10); 181 mtf.TestInsert(20); 182 183 CheckTree(mtf, std::string(R"( 184 10H2S2----D1 185 20H1S1----D2 186 )") 187 .substr(1)); 188 189 mtf.TestInsert(15); 190 CheckTree(mtf, std::string(R"( 191 15H2S3----10H1S1----D2 192 20H1S1----D2 193 )") 194 .substr(1)); 195 } 196 197 TEST(MoveToFront, RemoveSingleton) { 198 MoveToFrontTester mtf; 199 200 mtf.TestInsert(10); 201 CheckTree(mtf, std::string(R"( 202 10H1S1----D1 203 )") 204 .substr(1)); 205 206 mtf.TestRemove(10); 207 CheckTree(mtf, ""); 208 } 209 210 TEST(MoveToFront, RemoveRootWithScapegoat) { 211 MoveToFrontTester mtf; 212 213 mtf.TestInsert(10); 214 mtf.TestInsert(5); 215 mtf.TestInsert(15); 216 CheckTree(mtf, std::string(R"( 217 10H2S3----5H1S1-----D2 218 15H1S1----D2 219 )") 220 .substr(1)); 221 222 mtf.TestRemove(10); 223 CheckTree(mtf, std::string(R"( 224 15H2S2----5H1S1-----D2 225 )") 226 .substr(1)); 227 } 228 229 TEST(MoveToFront, RemoveRightRotation) { 230 MoveToFrontTester mtf; 231 232 mtf.TestInsert(10); 233 mtf.TestInsert(5); 234 mtf.TestInsert(15); 235 mtf.TestInsert(20); 236 CheckTree(mtf, std::string(R"( 237 10H3S4----5H1S1-----D2 238 15H2S2----D2 239 20H1S1----D3 240 )") 241 .substr(1)); 242 243 mtf.TestRemove(5); 244 245 CheckTree(mtf, std::string(R"( 246 15H2S3----10H1S1----D2 247 20H1S1----D2 248 )") 249 .substr(1)); 250 } 251 252 TEST(MoveToFront, RemoveLeftRotation) { 253 MoveToFrontTester mtf; 254 255 mtf.TestInsert(10); 256 mtf.TestInsert(15); 257 mtf.TestInsert(5); 258 mtf.TestInsert(1); 259 CheckTree(mtf, std::string(R"( 260 10H3S4----5H2S2-----1H1S1-----D3 261 15H1S1----D2 262 )") 263 .substr(1)); 264 265 mtf.TestRemove(15); 266 267 CheckTree(mtf, std::string(R"( 268 5H2S3-----1H1S1-----D2 269 10H1S1----D2 270 )") 271 .substr(1)); 272 } 273 274 TEST(MoveToFront, RemoveLeftRightRotation) { 275 MoveToFrontTester mtf; 276 277 mtf.TestInsert(10); 278 mtf.TestInsert(15); 279 mtf.TestInsert(5); 280 mtf.TestInsert(12); 281 CheckTree(mtf, std::string(R"( 282 10H3S4----5H1S1-----D2 283 15H2S2----12H1S1----D3 284 )") 285 .substr(1)); 286 287 mtf.TestRemove(5); 288 289 CheckTree(mtf, std::string(R"( 290 12H2S3----10H1S1----D2 291 15H1S1----D2 292 )") 293 .substr(1)); 294 } 295 296 TEST(MoveToFront, RemoveRightLeftRotation) { 297 MoveToFrontTester mtf; 298 299 mtf.TestInsert(10); 300 mtf.TestInsert(15); 301 mtf.TestInsert(5); 302 mtf.TestInsert(8); 303 CheckTree(mtf, std::string(R"( 304 10H3S4----5H2S2-----D2 305 8H1S1-----D3 306 15H1S1----D2 307 )") 308 .substr(1)); 309 310 mtf.TestRemove(15); 311 312 CheckTree(mtf, std::string(R"( 313 8H2S3-----5H1S1-----D2 314 10H1S1----D2 315 )") 316 .substr(1)); 317 } 318 319 TEST(MoveToFront, MultipleOperations) { 320 MoveToFrontTester mtf; 321 std::vector<uint32_t> vals = {5, 11, 12, 16, 15, 6, 14, 2, 322 7, 10, 4, 8, 9, 3, 1, 13}; 323 324 for (uint32_t i : vals) { 325 mtf.TestInsert(i); 326 } 327 328 CheckTree(mtf, std::string(R"( 329 11H5S16---5H4S10----3H3S4-----2H2S2-----1H1S1-----D5 330 4H1S1-----D4 331 7H3S5-----6H1S1-----D4 332 9H2S3-----8H1S1-----D5 333 10H1S1----D5 334 15H3S5----13H2S3----12H1S1----D4 335 14H1S1----D4 336 16H1S1----D3 337 )") 338 .substr(1)); 339 340 mtf.TestRemove(11); 341 342 CheckTree(mtf, std::string(R"( 343 10H5S15---5H4S9-----3H3S4-----2H2S2-----1H1S1-----D5 344 4H1S1-----D4 345 7H3S4-----6H1S1-----D4 346 9H2S2-----8H1S1-----D5 347 15H3S5----13H2S3----12H1S1----D4 348 14H1S1----D4 349 16H1S1----D3 350 )") 351 .substr(1)); 352 353 mtf.TestInsert(11); 354 355 CheckTree(mtf, std::string(R"( 356 10H5S16---5H4S9-----3H3S4-----2H2S2-----1H1S1-----D5 357 4H1S1-----D4 358 7H3S4-----6H1S1-----D4 359 9H2S2-----8H1S1-----D5 360 13H3S6----12H2S2----11H1S1----D4 361 15H2S3----14H1S1----D4 362 16H1S1----D4 363 )") 364 .substr(1)); 365 366 mtf.TestRemove(5); 367 368 CheckTree(mtf, std::string(R"( 369 10H5S15---6H4S8-----3H3S4-----2H2S2-----1H1S1-----D5 370 4H1S1-----D4 371 8H2S3-----7H1S1-----D4 372 9H1S1-----D4 373 13H3S6----12H2S2----11H1S1----D4 374 15H2S3----14H1S1----D4 375 16H1S1----D4 376 )") 377 .substr(1)); 378 379 mtf.TestInsert(5); 380 381 CheckTree(mtf, std::string(R"( 382 10H5S16---6H4S9-----3H3S5-----2H2S2-----1H1S1-----D5 383 4H2S2-----D4 384 5H1S1-----D5 385 8H2S3-----7H1S1-----D4 386 9H1S1-----D4 387 13H3S6----12H2S2----11H1S1----D4 388 15H2S3----14H1S1----D4 389 16H1S1----D4 390 )") 391 .substr(1)); 392 393 mtf.TestRemove(2); 394 mtf.TestRemove(1); 395 mtf.TestRemove(4); 396 mtf.TestRemove(3); 397 mtf.TestRemove(6); 398 mtf.TestRemove(5); 399 mtf.TestRemove(7); 400 mtf.TestRemove(9); 401 402 CheckTree(mtf, std::string(R"( 403 13H4S8----10H3S4----8H1S1-----D3 404 12H2S2----11H1S1----D4 405 15H2S3----14H1S1----D3 406 16H1S1----D3 407 )") 408 .substr(1)); 409 } 410 411 TEST(MoveToFront, BiggerScaleTreeTest) { 412 MoveToFrontTester mtf; 413 std::set<uint32_t> all_vals; 414 415 const uint32_t kMagic1 = 2654435761; 416 const uint32_t kMagic2 = 10000; 417 418 for (uint32_t i = 1; i < 1000; ++i) { 419 const uint32_t val = (i * kMagic1) % kMagic2; 420 if (!all_vals.count(val)) { 421 mtf.TestInsert(val); 422 all_vals.insert(val); 423 } 424 } 425 426 for (uint32_t i = 1; i < 1000; ++i) { 427 const uint32_t val = (i * kMagic1) % kMagic2; 428 if (val % 2 == 0) { 429 mtf.TestRemove(val); 430 all_vals.erase(val); 431 } 432 } 433 434 for (uint32_t i = 1000; i < 2000; ++i) { 435 const uint32_t val = (i * kMagic1) % kMagic2; 436 if (!all_vals.count(val)) { 437 mtf.TestInsert(val); 438 all_vals.insert(val); 439 } 440 } 441 442 for (uint32_t i = 1; i < 2000; ++i) { 443 const uint32_t val = (i * kMagic1) % kMagic2; 444 if (val > 50) { 445 mtf.TestRemove(val); 446 all_vals.erase(val); 447 } 448 } 449 450 EXPECT_EQ(all_vals, std::set<uint32_t>({2, 4, 11, 13, 24, 33, 35, 37, 46})); 451 452 CheckTree(mtf, std::string(R"( 453 33H4S9----11H3S5----2H2S2-----D3 454 4H1S1-----D4 455 13H2S2----D3 456 24H1S1----D4 457 37H2S3----35H1S1----D3 458 46H1S1----D3 459 )") 460 .substr(1)); 461 } 462 463 TEST(MoveToFront, RankFromValue) { 464 MoveToFrontTester mtf; 465 466 uint32_t rank = 0; 467 EXPECT_FALSE(mtf.RankFromValue(1, &rank)); 468 469 EXPECT_TRUE(mtf.Insert(1)); 470 EXPECT_TRUE(mtf.Insert(2)); 471 EXPECT_TRUE(mtf.Insert(3)); 472 EXPECT_FALSE(mtf.Insert(2)); 473 CheckTree(mtf, 474 std::string(R"( 475 2H2S3T2-------1H1S1T1-------D2 476 3H1S1T3-------D2 477 )") 478 .substr(1), 479 /* print_timestamp = */ true); 480 481 EXPECT_FALSE(mtf.RankFromValue(4, &rank)); 482 483 EXPECT_TRUE(mtf.RankFromValue(1, &rank)); 484 EXPECT_EQ(3u, rank); 485 486 CheckTree(mtf, 487 std::string(R"( 488 3H2S3T3-------2H1S1T2-------D2 489 1H1S1T4-------D2 490 )") 491 .substr(1), 492 /* print_timestamp = */ true); 493 494 EXPECT_TRUE(mtf.RankFromValue(1, &rank)); 495 EXPECT_EQ(1u, rank); 496 497 EXPECT_TRUE(mtf.RankFromValue(3, &rank)); 498 EXPECT_EQ(2u, rank); 499 500 EXPECT_TRUE(mtf.RankFromValue(2, &rank)); 501 EXPECT_EQ(3u, rank); 502 503 EXPECT_TRUE(mtf.Insert(40)); 504 505 EXPECT_TRUE(mtf.RankFromValue(1, &rank)); 506 EXPECT_EQ(4u, rank); 507 508 EXPECT_TRUE(mtf.Insert(50)); 509 510 EXPECT_TRUE(mtf.RankFromValue(1, &rank)); 511 EXPECT_EQ(2u, rank); 512 513 CheckTree(mtf, 514 std::string(R"( 515 2H3S5T6-------3H1S1T5-------D2 516 50H2S3T9------40H1S1T7------D3 517 1H1S1T10------D3 518 )") 519 .substr(1), 520 /* print_timestamp = */ true); 521 522 EXPECT_TRUE(mtf.RankFromValue(50, &rank)); 523 EXPECT_EQ(2u, rank); 524 525 EXPECT_EQ(5u, mtf.GetSize()); 526 CheckTree(mtf, 527 std::string(R"( 528 2H3S5T6-------3H1S1T5-------D2 529 1H2S3T10------40H1S1T7------D3 530 50H1S1T11-----D3 531 )") 532 .substr(1), 533 /* print_timestamp = */ true); 534 535 EXPECT_FALSE(mtf.RankFromValue(0, &rank)); 536 EXPECT_FALSE(mtf.RankFromValue(20, &rank)); 537 } 538 539 TEST(MoveToFront, ValueFromRank) { 540 MoveToFrontTester mtf; 541 542 uint32_t value = 0; 543 EXPECT_FALSE(mtf.ValueFromRank(0, &value)); 544 EXPECT_FALSE(mtf.ValueFromRank(1, &value)); 545 546 EXPECT_TRUE(mtf.Insert(1)); 547 EXPECT_EQ(1u, mtf.GetLastAccessedValue()); 548 EXPECT_TRUE(mtf.Insert(2)); 549 EXPECT_EQ(2u, mtf.GetLastAccessedValue()); 550 EXPECT_TRUE(mtf.Insert(3)); 551 EXPECT_EQ(3u, mtf.GetLastAccessedValue()); 552 553 EXPECT_TRUE(mtf.ValueFromRank(3, &value)); 554 EXPECT_EQ(1u, value); 555 EXPECT_EQ(1u, mtf.GetLastAccessedValue()); 556 557 EXPECT_TRUE(mtf.ValueFromRank(1, &value)); 558 EXPECT_EQ(1u, value); 559 EXPECT_EQ(1u, mtf.GetLastAccessedValue()); 560 561 CheckTree(mtf, 562 std::string(R"( 563 3H2S3T3-------2H1S1T2-------D2 564 1H1S1T4-------D2 565 )") 566 .substr(1), 567 /* print_timestamp = */ true); 568 569 EXPECT_TRUE(mtf.ValueFromRank(2, &value)); 570 EXPECT_EQ(3u, value); 571 572 EXPECT_EQ(3u, mtf.GetSize()); 573 574 CheckTree(mtf, 575 std::string(R"( 576 1H2S3T4-------2H1S1T2-------D2 577 3H1S1T5-------D2 578 )") 579 .substr(1), 580 /* print_timestamp = */ true); 581 582 EXPECT_TRUE(mtf.ValueFromRank(3, &value)); 583 EXPECT_EQ(2u, value); 584 585 CheckTree(mtf, 586 std::string(R"( 587 3H2S3T5-------1H1S1T4-------D2 588 2H1S1T6-------D2 589 )") 590 .substr(1), 591 /* print_timestamp = */ true); 592 593 EXPECT_TRUE(mtf.Insert(10)); 594 CheckTree(mtf, 595 std::string(R"( 596 3H3S4T5-------1H1S1T4-------D2 597 2H2S2T6-------D2 598 10H1S1T7------D3 599 )") 600 .substr(1), 601 /* print_timestamp = */ true); 602 603 EXPECT_TRUE(mtf.ValueFromRank(1, &value)); 604 EXPECT_EQ(10u, value); 605 } 606 607 TEST(MoveToFront, Remove) { 608 MoveToFrontTester mtf; 609 610 EXPECT_FALSE(mtf.Remove(1)); 611 EXPECT_EQ(0u, mtf.GetTotalNodeCount()); 612 613 EXPECT_TRUE(mtf.Insert(1)); 614 EXPECT_TRUE(mtf.Insert(2)); 615 EXPECT_TRUE(mtf.Insert(3)); 616 617 CheckTree(mtf, 618 std::string(R"( 619 2H2S3T2-------1H1S1T1-------D2 620 3H1S1T3-------D2 621 )") 622 .substr(1), 623 /* print_timestamp = */ true); 624 625 EXPECT_EQ(1u, mtf.GetNodeHandle(1)); 626 EXPECT_EQ(3u, mtf.GetTotalNodeCount()); 627 EXPECT_TRUE(mtf.Remove(1)); 628 EXPECT_EQ(3u, mtf.GetTotalNodeCount()); 629 630 CheckTree(mtf, 631 std::string(R"( 632 2H2S2T2-------D1 633 3H1S1T3-------D2 634 )") 635 .substr(1), 636 /* print_timestamp = */ true); 637 638 uint32_t value = 0; 639 EXPECT_TRUE(mtf.ValueFromRank(2, &value)); 640 EXPECT_EQ(2u, value); 641 642 CheckTree(mtf, 643 std::string(R"( 644 3H2S2T3-------D1 645 2H1S1T4-------D2 646 )") 647 .substr(1), 648 /* print_timestamp = */ true); 649 650 EXPECT_TRUE(mtf.Insert(1)); 651 EXPECT_EQ(1u, mtf.GetNodeHandle(1)); 652 EXPECT_EQ(3u, mtf.GetTotalNodeCount()); 653 } 654 655 TEST(MoveToFront, LargerScale) { 656 MoveToFrontTester mtf; 657 uint32_t value = 0; 658 uint32_t rank = 0; 659 660 for (uint32_t i = 1; i < 1000; ++i) { 661 ASSERT_TRUE(mtf.Insert(i)); 662 ASSERT_EQ(i, mtf.GetSize()); 663 664 ASSERT_TRUE(mtf.RankFromValue(i, &rank)); 665 ASSERT_EQ(1u, rank); 666 667 ASSERT_TRUE(mtf.ValueFromRank(1, &value)); 668 ASSERT_EQ(i, value); 669 } 670 671 ASSERT_TRUE(mtf.ValueFromRank(999, &value)); 672 ASSERT_EQ(1u, value); 673 674 ASSERT_TRUE(mtf.ValueFromRank(999, &value)); 675 ASSERT_EQ(2u, value); 676 677 ASSERT_TRUE(mtf.ValueFromRank(999, &value)); 678 ASSERT_EQ(3u, value); 679 680 ASSERT_TRUE(mtf.ValueFromRank(999, &value)); 681 ASSERT_EQ(4u, value); 682 683 ASSERT_TRUE(mtf.ValueFromRank(999, &value)); 684 ASSERT_EQ(5u, value); 685 686 ASSERT_TRUE(mtf.ValueFromRank(999, &value)); 687 ASSERT_EQ(6u, value); 688 689 ASSERT_TRUE(mtf.ValueFromRank(101, &value)); 690 ASSERT_EQ(905u, value); 691 692 ASSERT_TRUE(mtf.ValueFromRank(101, &value)); 693 ASSERT_EQ(906u, value); 694 695 ASSERT_TRUE(mtf.ValueFromRank(101, &value)); 696 ASSERT_EQ(907u, value); 697 698 ASSERT_TRUE(mtf.ValueFromRank(201, &value)); 699 ASSERT_EQ(805u, value); 700 701 ASSERT_TRUE(mtf.ValueFromRank(201, &value)); 702 ASSERT_EQ(806u, value); 703 704 ASSERT_TRUE(mtf.ValueFromRank(201, &value)); 705 ASSERT_EQ(807u, value); 706 707 ASSERT_TRUE(mtf.ValueFromRank(301, &value)); 708 ASSERT_EQ(705u, value); 709 710 ASSERT_TRUE(mtf.ValueFromRank(301, &value)); 711 ASSERT_EQ(706u, value); 712 713 ASSERT_TRUE(mtf.ValueFromRank(301, &value)); 714 ASSERT_EQ(707u, value); 715 716 ASSERT_TRUE(mtf.RankFromValue(605, &rank)); 717 ASSERT_EQ(401u, rank); 718 719 ASSERT_TRUE(mtf.RankFromValue(606, &rank)); 720 ASSERT_EQ(401u, rank); 721 722 ASSERT_TRUE(mtf.RankFromValue(607, &rank)); 723 ASSERT_EQ(401u, rank); 724 725 ASSERT_TRUE(mtf.ValueFromRank(1, &value)); 726 ASSERT_EQ(607u, value); 727 728 ASSERT_TRUE(mtf.ValueFromRank(2, &value)); 729 ASSERT_EQ(606u, value); 730 731 ASSERT_TRUE(mtf.ValueFromRank(3, &value)); 732 ASSERT_EQ(605u, value); 733 734 ASSERT_TRUE(mtf.ValueFromRank(4, &value)); 735 ASSERT_EQ(707u, value); 736 737 ASSERT_TRUE(mtf.ValueFromRank(5, &value)); 738 ASSERT_EQ(706u, value); 739 740 ASSERT_TRUE(mtf.ValueFromRank(6, &value)); 741 ASSERT_EQ(705u, value); 742 743 ASSERT_TRUE(mtf.ValueFromRank(7, &value)); 744 ASSERT_EQ(807u, value); 745 746 ASSERT_TRUE(mtf.ValueFromRank(8, &value)); 747 ASSERT_EQ(806u, value); 748 749 ASSERT_TRUE(mtf.ValueFromRank(9, &value)); 750 ASSERT_EQ(805u, value); 751 752 ASSERT_TRUE(mtf.ValueFromRank(10, &value)); 753 ASSERT_EQ(907u, value); 754 755 ASSERT_TRUE(mtf.ValueFromRank(11, &value)); 756 ASSERT_EQ(906u, value); 757 758 ASSERT_TRUE(mtf.ValueFromRank(12, &value)); 759 ASSERT_EQ(905u, value); 760 761 ASSERT_TRUE(mtf.ValueFromRank(13, &value)); 762 ASSERT_EQ(6u, value); 763 764 ASSERT_TRUE(mtf.ValueFromRank(14, &value)); 765 ASSERT_EQ(5u, value); 766 767 ASSERT_TRUE(mtf.ValueFromRank(15, &value)); 768 ASSERT_EQ(4u, value); 769 770 ASSERT_TRUE(mtf.ValueFromRank(16, &value)); 771 ASSERT_EQ(3u, value); 772 773 ASSERT_TRUE(mtf.ValueFromRank(17, &value)); 774 ASSERT_EQ(2u, value); 775 776 ASSERT_TRUE(mtf.ValueFromRank(18, &value)); 777 ASSERT_EQ(1u, value); 778 779 ASSERT_TRUE(mtf.ValueFromRank(19, &value)); 780 ASSERT_EQ(999u, value); 781 782 ASSERT_TRUE(mtf.ValueFromRank(20, &value)); 783 ASSERT_EQ(998u, value); 784 785 ASSERT_TRUE(mtf.ValueFromRank(21, &value)); 786 ASSERT_EQ(997u, value); 787 788 ASSERT_TRUE(mtf.RankFromValue(997, &rank)); 789 ASSERT_EQ(1u, rank); 790 791 ASSERT_TRUE(mtf.RankFromValue(998, &rank)); 792 ASSERT_EQ(2u, rank); 793 794 ASSERT_TRUE(mtf.RankFromValue(996, &rank)); 795 ASSERT_EQ(22u, rank); 796 797 ASSERT_TRUE(mtf.Remove(995)); 798 799 ASSERT_TRUE(mtf.RankFromValue(994, &rank)); 800 ASSERT_EQ(23u, rank); 801 802 for (uint32_t i = 10; i < 1000; ++i) { 803 if (i != 995) { 804 ASSERT_TRUE(mtf.Remove(i)); 805 } else { 806 ASSERT_FALSE(mtf.Remove(i)); 807 } 808 } 809 810 CheckTree(mtf, 811 std::string(R"( 812 6H4S9T1029----8H2S3T8-------7H1S1T7-------D3 813 9H1S1T9-------D3 814 2H3S5T1033----4H2S3T1031----5H1S1T1030----D4 815 3H1S1T1032----D4 816 1H1S1T1034----D3 817 )") 818 .substr(1), 819 /* print_timestamp = */ true); 820 821 ASSERT_TRUE(mtf.Insert(1000)); 822 ASSERT_TRUE(mtf.ValueFromRank(1, &value)); 823 ASSERT_EQ(1000u, value); 824 } 825 826 } // namespace 827 } // namespace comp 828 } // namespace spvtools 829
