| // Copyright (c) 2017 Google Inc. |
| // |
| // Licensed under the Apache License, Version 2.0 (the "License"); |
| // you may not use this file except in compliance with the License. |
| // You may obtain a copy of the License at |
| // |
| // http://www.apache.org/licenses/LICENSE-2.0 |
| // |
| // Unless required by applicable law or agreed to in writing, software |
| // distributed under the License is distributed on an "AS IS" BASIS, |
| // WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. |
| // See the License for the specific language governing permissions and |
| // limitations under the License. |
| |
| #include <algorithm> |
| #include <iostream> |
| #include <set> |
| #include <string> |
| #include <vector> |
| |
| #include "gmock/gmock.h" |
| #include "source/comp/move_to_front.h" |
| |
| namespace spvtools { |
| namespace comp { |
| namespace { |
| |
| // Class used to test the inner workings of MoveToFront. |
| class MoveToFrontTester : public MoveToFront { |
| public: |
| // Inserts the value in the internal tree data structure. For testing only. |
| void TestInsert(uint32_t val) { InsertNode(CreateNode(val, val)); } |
| |
| // Removes the value from the internal tree data structure. For testing only. |
| void TestRemove(uint32_t val) { |
| const auto it = value_to_node_.find(val); |
| assert(it != value_to_node_.end()); |
| RemoveNode(it->second); |
| } |
| |
| // Prints the internal tree data structure to |out|. For testing only. |
| void PrintTree(std::ostream& out, bool print_timestamp = false) const { |
| if (root_) PrintTreeInternal(out, root_, 1, print_timestamp); |
| } |
| |
| // Returns node handle corresponding to the value. The value may not be in the |
| // tree. |
| uint32_t GetNodeHandle(uint32_t value) const { |
| const auto it = value_to_node_.find(value); |
| if (it == value_to_node_.end()) return 0; |
| |
| return it->second; |
| } |
| |
| // Returns total node count (both those in the tree and removed, |
| // but not the NIL singleton). |
| size_t GetTotalNodeCount() const { |
| assert(nodes_.size()); |
| return nodes_.size() - 1; |
| } |
| |
| uint32_t GetLastAccessedValue() const { return last_accessed_value_; } |
| |
| private: |
| // Prints the internal tree data structure for debug purposes in the following |
| // format: |
| // 10H3S4----5H1S1-----D2 |
| // 15H2S2----12H1S1----D3 |
| // Right links are horizontal, left links step down one line. |
| // 5H1S1 is read as value 5, height 1, size 1. Optionally node label can also |
| // contain timestamp (5H1S1T15). D3 stands for depth 3. |
| void PrintTreeInternal(std::ostream& out, uint32_t node, size_t depth, |
| bool print_timestamp) const; |
| }; |
| |
| void MoveToFrontTester::PrintTreeInternal(std::ostream& out, uint32_t node, |
| size_t depth, |
| bool print_timestamp) const { |
| if (!node) { |
| out << "D" << depth - 1 << std::endl; |
| return; |
| } |
| |
| const size_t kTextFieldWvaluethWithoutTimestamp = 10; |
| const size_t kTextFieldWvaluethWithTimestamp = 14; |
| const size_t text_field_wvalueth = print_timestamp |
| ? kTextFieldWvaluethWithTimestamp |
| : kTextFieldWvaluethWithoutTimestamp; |
| |
| std::stringstream label; |
| label << ValueOf(node) << "H" << HeightOf(node) << "S" << SizeOf(node); |
| if (print_timestamp) label << "T" << TimestampOf(node); |
| const size_t label_length = label.str().length(); |
| if (label_length < text_field_wvalueth) |
| label << std::string(text_field_wvalueth - label_length, '-'); |
| |
| out << label.str(); |
| |
| PrintTreeInternal(out, RightOf(node), depth + 1, print_timestamp); |
| |
| if (LeftOf(node)) { |
| out << std::string(depth * text_field_wvalueth, ' '); |
| PrintTreeInternal(out, LeftOf(node), depth + 1, print_timestamp); |
| } |
| } |
| |
| void CheckTree(const MoveToFrontTester& mtf, const std::string& expected, |
| bool print_timestamp = false) { |
| std::stringstream ss; |
| mtf.PrintTree(ss, print_timestamp); |
| EXPECT_EQ(expected, ss.str()); |
| } |
| |
| TEST(MoveToFront, EmptyTree) { |
| MoveToFrontTester mtf; |
| CheckTree(mtf, std::string()); |
| } |
| |
| TEST(MoveToFront, InsertLeftRotation) { |
| MoveToFrontTester mtf; |
| |
| mtf.TestInsert(30); |
| mtf.TestInsert(20); |
| |
| CheckTree(mtf, std::string(R"( |
| 30H2S2----20H1S1----D2 |
| )") |
| .substr(1)); |
| |
| mtf.TestInsert(10); |
| CheckTree(mtf, std::string(R"( |
| 20H2S3----10H1S1----D2 |
| 30H1S1----D2 |
| )") |
| .substr(1)); |
| } |
| |
| TEST(MoveToFront, InsertRightRotation) { |
| MoveToFrontTester mtf; |
| |
| mtf.TestInsert(10); |
| mtf.TestInsert(20); |
| |
| CheckTree(mtf, std::string(R"( |
| 10H2S2----D1 |
| 20H1S1----D2 |
| )") |
| .substr(1)); |
| |
| mtf.TestInsert(30); |
| CheckTree(mtf, std::string(R"( |
| 20H2S3----10H1S1----D2 |
| 30H1S1----D2 |
| )") |
| .substr(1)); |
| } |
| |
| TEST(MoveToFront, InsertRightLeftRotation) { |
| MoveToFrontTester mtf; |
| |
| mtf.TestInsert(30); |
| mtf.TestInsert(20); |
| |
| CheckTree(mtf, std::string(R"( |
| 30H2S2----20H1S1----D2 |
| )") |
| .substr(1)); |
| |
| mtf.TestInsert(25); |
| CheckTree(mtf, std::string(R"( |
| 25H2S3----20H1S1----D2 |
| 30H1S1----D2 |
| )") |
| .substr(1)); |
| } |
| |
| TEST(MoveToFront, InsertLeftRightRotation) { |
| MoveToFrontTester mtf; |
| |
| mtf.TestInsert(10); |
| mtf.TestInsert(20); |
| |
| CheckTree(mtf, std::string(R"( |
| 10H2S2----D1 |
| 20H1S1----D2 |
| )") |
| .substr(1)); |
| |
| mtf.TestInsert(15); |
| CheckTree(mtf, std::string(R"( |
| 15H2S3----10H1S1----D2 |
| 20H1S1----D2 |
| )") |
| .substr(1)); |
| } |
| |
| TEST(MoveToFront, RemoveSingleton) { |
| MoveToFrontTester mtf; |
| |
| mtf.TestInsert(10); |
| CheckTree(mtf, std::string(R"( |
| 10H1S1----D1 |
| )") |
| .substr(1)); |
| |
| mtf.TestRemove(10); |
| CheckTree(mtf, ""); |
| } |
| |
| TEST(MoveToFront, RemoveRootWithScapegoat) { |
| MoveToFrontTester mtf; |
| |
| mtf.TestInsert(10); |
| mtf.TestInsert(5); |
| mtf.TestInsert(15); |
| CheckTree(mtf, std::string(R"( |
| 10H2S3----5H1S1-----D2 |
| 15H1S1----D2 |
| )") |
| .substr(1)); |
| |
| mtf.TestRemove(10); |
| CheckTree(mtf, std::string(R"( |
| 15H2S2----5H1S1-----D2 |
| )") |
| .substr(1)); |
| } |
| |
| TEST(MoveToFront, RemoveRightRotation) { |
| MoveToFrontTester mtf; |
| |
| mtf.TestInsert(10); |
| mtf.TestInsert(5); |
| mtf.TestInsert(15); |
| mtf.TestInsert(20); |
| CheckTree(mtf, std::string(R"( |
| 10H3S4----5H1S1-----D2 |
| 15H2S2----D2 |
| 20H1S1----D3 |
| )") |
| .substr(1)); |
| |
| mtf.TestRemove(5); |
| |
| CheckTree(mtf, std::string(R"( |
| 15H2S3----10H1S1----D2 |
| 20H1S1----D2 |
| )") |
| .substr(1)); |
| } |
| |
| TEST(MoveToFront, RemoveLeftRotation) { |
| MoveToFrontTester mtf; |
| |
| mtf.TestInsert(10); |
| mtf.TestInsert(15); |
| mtf.TestInsert(5); |
| mtf.TestInsert(1); |
| CheckTree(mtf, std::string(R"( |
| 10H3S4----5H2S2-----1H1S1-----D3 |
| 15H1S1----D2 |
| )") |
| .substr(1)); |
| |
| mtf.TestRemove(15); |
| |
| CheckTree(mtf, std::string(R"( |
| 5H2S3-----1H1S1-----D2 |
| 10H1S1----D2 |
| )") |
| .substr(1)); |
| } |
| |
| TEST(MoveToFront, RemoveLeftRightRotation) { |
| MoveToFrontTester mtf; |
| |
| mtf.TestInsert(10); |
| mtf.TestInsert(15); |
| mtf.TestInsert(5); |
| mtf.TestInsert(12); |
| CheckTree(mtf, std::string(R"( |
| 10H3S4----5H1S1-----D2 |
| 15H2S2----12H1S1----D3 |
| )") |
| .substr(1)); |
| |
| mtf.TestRemove(5); |
| |
| CheckTree(mtf, std::string(R"( |
| 12H2S3----10H1S1----D2 |
| 15H1S1----D2 |
| )") |
| .substr(1)); |
| } |
| |
| TEST(MoveToFront, RemoveRightLeftRotation) { |
| MoveToFrontTester mtf; |
| |
| mtf.TestInsert(10); |
| mtf.TestInsert(15); |
| mtf.TestInsert(5); |
| mtf.TestInsert(8); |
| CheckTree(mtf, std::string(R"( |
| 10H3S4----5H2S2-----D2 |
| 8H1S1-----D3 |
| 15H1S1----D2 |
| )") |
| .substr(1)); |
| |
| mtf.TestRemove(15); |
| |
| CheckTree(mtf, std::string(R"( |
| 8H2S3-----5H1S1-----D2 |
| 10H1S1----D2 |
| )") |
| .substr(1)); |
| } |
| |
| TEST(MoveToFront, MultipleOperations) { |
| MoveToFrontTester mtf; |
| std::vector<uint32_t> vals = {5, 11, 12, 16, 15, 6, 14, 2, |
| 7, 10, 4, 8, 9, 3, 1, 13}; |
| |
| for (uint32_t i : vals) { |
| mtf.TestInsert(i); |
| } |
| |
| CheckTree(mtf, std::string(R"( |
| 11H5S16---5H4S10----3H3S4-----2H2S2-----1H1S1-----D5 |
| 4H1S1-----D4 |
| 7H3S5-----6H1S1-----D4 |
| 9H2S3-----8H1S1-----D5 |
| 10H1S1----D5 |
| 15H3S5----13H2S3----12H1S1----D4 |
| 14H1S1----D4 |
| 16H1S1----D3 |
| )") |
| .substr(1)); |
| |
| mtf.TestRemove(11); |
| |
| CheckTree(mtf, std::string(R"( |
| 10H5S15---5H4S9-----3H3S4-----2H2S2-----1H1S1-----D5 |
| 4H1S1-----D4 |
| 7H3S4-----6H1S1-----D4 |
| 9H2S2-----8H1S1-----D5 |
| 15H3S5----13H2S3----12H1S1----D4 |
| 14H1S1----D4 |
| 16H1S1----D3 |
| )") |
| .substr(1)); |
| |
| mtf.TestInsert(11); |
| |
| CheckTree(mtf, std::string(R"( |
| 10H5S16---5H4S9-----3H3S4-----2H2S2-----1H1S1-----D5 |
| 4H1S1-----D4 |
| 7H3S4-----6H1S1-----D4 |
| 9H2S2-----8H1S1-----D5 |
| 13H3S6----12H2S2----11H1S1----D4 |
| 15H2S3----14H1S1----D4 |
| 16H1S1----D4 |
| )") |
| .substr(1)); |
| |
| mtf.TestRemove(5); |
| |
| CheckTree(mtf, std::string(R"( |
| 10H5S15---6H4S8-----3H3S4-----2H2S2-----1H1S1-----D5 |
| 4H1S1-----D4 |
| 8H2S3-----7H1S1-----D4 |
| 9H1S1-----D4 |
| 13H3S6----12H2S2----11H1S1----D4 |
| 15H2S3----14H1S1----D4 |
| 16H1S1----D4 |
| )") |
| .substr(1)); |
| |
| mtf.TestInsert(5); |
| |
| CheckTree(mtf, std::string(R"( |
| 10H5S16---6H4S9-----3H3S5-----2H2S2-----1H1S1-----D5 |
| 4H2S2-----D4 |
| 5H1S1-----D5 |
| 8H2S3-----7H1S1-----D4 |
| 9H1S1-----D4 |
| 13H3S6----12H2S2----11H1S1----D4 |
| 15H2S3----14H1S1----D4 |
| 16H1S1----D4 |
| )") |
| .substr(1)); |
| |
| mtf.TestRemove(2); |
| mtf.TestRemove(1); |
| mtf.TestRemove(4); |
| mtf.TestRemove(3); |
| mtf.TestRemove(6); |
| mtf.TestRemove(5); |
| mtf.TestRemove(7); |
| mtf.TestRemove(9); |
| |
| CheckTree(mtf, std::string(R"( |
| 13H4S8----10H3S4----8H1S1-----D3 |
| 12H2S2----11H1S1----D4 |
| 15H2S3----14H1S1----D3 |
| 16H1S1----D3 |
| )") |
| .substr(1)); |
| } |
| |
| TEST(MoveToFront, BiggerScaleTreeTest) { |
| MoveToFrontTester mtf; |
| std::set<uint32_t> all_vals; |
| |
| const uint32_t kMagic1 = 2654435761; |
| const uint32_t kMagic2 = 10000; |
| |
| for (uint32_t i = 1; i < 1000; ++i) { |
| const uint32_t val = (i * kMagic1) % kMagic2; |
| if (!all_vals.count(val)) { |
| mtf.TestInsert(val); |
| all_vals.insert(val); |
| } |
| } |
| |
| for (uint32_t i = 1; i < 1000; ++i) { |
| const uint32_t val = (i * kMagic1) % kMagic2; |
| if (val % 2 == 0) { |
| mtf.TestRemove(val); |
| all_vals.erase(val); |
| } |
| } |
| |
| for (uint32_t i = 1000; i < 2000; ++i) { |
| const uint32_t val = (i * kMagic1) % kMagic2; |
| if (!all_vals.count(val)) { |
| mtf.TestInsert(val); |
| all_vals.insert(val); |
| } |
| } |
| |
| for (uint32_t i = 1; i < 2000; ++i) { |
| const uint32_t val = (i * kMagic1) % kMagic2; |
| if (val > 50) { |
| mtf.TestRemove(val); |
| all_vals.erase(val); |
| } |
| } |
| |
| EXPECT_EQ(all_vals, std::set<uint32_t>({2, 4, 11, 13, 24, 33, 35, 37, 46})); |
| |
| CheckTree(mtf, std::string(R"( |
| 33H4S9----11H3S5----2H2S2-----D3 |
| 4H1S1-----D4 |
| 13H2S2----D3 |
| 24H1S1----D4 |
| 37H2S3----35H1S1----D3 |
| 46H1S1----D3 |
| )") |
| .substr(1)); |
| } |
| |
| TEST(MoveToFront, RankFromValue) { |
| MoveToFrontTester mtf; |
| |
| uint32_t rank = 0; |
| EXPECT_FALSE(mtf.RankFromValue(1, &rank)); |
| |
| EXPECT_TRUE(mtf.Insert(1)); |
| EXPECT_TRUE(mtf.Insert(2)); |
| EXPECT_TRUE(mtf.Insert(3)); |
| EXPECT_FALSE(mtf.Insert(2)); |
| CheckTree(mtf, |
| std::string(R"( |
| 2H2S3T2-------1H1S1T1-------D2 |
| 3H1S1T3-------D2 |
| )") |
| .substr(1), |
| /* print_timestamp = */ true); |
| |
| EXPECT_FALSE(mtf.RankFromValue(4, &rank)); |
| |
| EXPECT_TRUE(mtf.RankFromValue(1, &rank)); |
| EXPECT_EQ(3u, rank); |
| |
| CheckTree(mtf, |
| std::string(R"( |
| 3H2S3T3-------2H1S1T2-------D2 |
| 1H1S1T4-------D2 |
| )") |
| .substr(1), |
| /* print_timestamp = */ true); |
| |
| EXPECT_TRUE(mtf.RankFromValue(1, &rank)); |
| EXPECT_EQ(1u, rank); |
| |
| EXPECT_TRUE(mtf.RankFromValue(3, &rank)); |
| EXPECT_EQ(2u, rank); |
| |
| EXPECT_TRUE(mtf.RankFromValue(2, &rank)); |
| EXPECT_EQ(3u, rank); |
| |
| EXPECT_TRUE(mtf.Insert(40)); |
| |
| EXPECT_TRUE(mtf.RankFromValue(1, &rank)); |
| EXPECT_EQ(4u, rank); |
| |
| EXPECT_TRUE(mtf.Insert(50)); |
| |
| EXPECT_TRUE(mtf.RankFromValue(1, &rank)); |
| EXPECT_EQ(2u, rank); |
| |
| CheckTree(mtf, |
| std::string(R"( |
| 2H3S5T6-------3H1S1T5-------D2 |
| 50H2S3T9------40H1S1T7------D3 |
| 1H1S1T10------D3 |
| )") |
| .substr(1), |
| /* print_timestamp = */ true); |
| |
| EXPECT_TRUE(mtf.RankFromValue(50, &rank)); |
| EXPECT_EQ(2u, rank); |
| |
| EXPECT_EQ(5u, mtf.GetSize()); |
| CheckTree(mtf, |
| std::string(R"( |
| 2H3S5T6-------3H1S1T5-------D2 |
| 1H2S3T10------40H1S1T7------D3 |
| 50H1S1T11-----D3 |
| )") |
| .substr(1), |
| /* print_timestamp = */ true); |
| |
| EXPECT_FALSE(mtf.RankFromValue(0, &rank)); |
| EXPECT_FALSE(mtf.RankFromValue(20, &rank)); |
| } |
| |
| TEST(MoveToFront, ValueFromRank) { |
| MoveToFrontTester mtf; |
| |
| uint32_t value = 0; |
| EXPECT_FALSE(mtf.ValueFromRank(0, &value)); |
| EXPECT_FALSE(mtf.ValueFromRank(1, &value)); |
| |
| EXPECT_TRUE(mtf.Insert(1)); |
| EXPECT_EQ(1u, mtf.GetLastAccessedValue()); |
| EXPECT_TRUE(mtf.Insert(2)); |
| EXPECT_EQ(2u, mtf.GetLastAccessedValue()); |
| EXPECT_TRUE(mtf.Insert(3)); |
| EXPECT_EQ(3u, mtf.GetLastAccessedValue()); |
| |
| EXPECT_TRUE(mtf.ValueFromRank(3, &value)); |
| EXPECT_EQ(1u, value); |
| EXPECT_EQ(1u, mtf.GetLastAccessedValue()); |
| |
| EXPECT_TRUE(mtf.ValueFromRank(1, &value)); |
| EXPECT_EQ(1u, value); |
| EXPECT_EQ(1u, mtf.GetLastAccessedValue()); |
| |
| CheckTree(mtf, |
| std::string(R"( |
| 3H2S3T3-------2H1S1T2-------D2 |
| 1H1S1T4-------D2 |
| )") |
| .substr(1), |
| /* print_timestamp = */ true); |
| |
| EXPECT_TRUE(mtf.ValueFromRank(2, &value)); |
| EXPECT_EQ(3u, value); |
| |
| EXPECT_EQ(3u, mtf.GetSize()); |
| |
| CheckTree(mtf, |
| std::string(R"( |
| 1H2S3T4-------2H1S1T2-------D2 |
| 3H1S1T5-------D2 |
| )") |
| .substr(1), |
| /* print_timestamp = */ true); |
| |
| EXPECT_TRUE(mtf.ValueFromRank(3, &value)); |
| EXPECT_EQ(2u, value); |
| |
| CheckTree(mtf, |
| std::string(R"( |
| 3H2S3T5-------1H1S1T4-------D2 |
| 2H1S1T6-------D2 |
| )") |
| .substr(1), |
| /* print_timestamp = */ true); |
| |
| EXPECT_TRUE(mtf.Insert(10)); |
| CheckTree(mtf, |
| std::string(R"( |
| 3H3S4T5-------1H1S1T4-------D2 |
| 2H2S2T6-------D2 |
| 10H1S1T7------D3 |
| )") |
| .substr(1), |
| /* print_timestamp = */ true); |
| |
| EXPECT_TRUE(mtf.ValueFromRank(1, &value)); |
| EXPECT_EQ(10u, value); |
| } |
| |
| TEST(MoveToFront, Remove) { |
| MoveToFrontTester mtf; |
| |
| EXPECT_FALSE(mtf.Remove(1)); |
| EXPECT_EQ(0u, mtf.GetTotalNodeCount()); |
| |
| EXPECT_TRUE(mtf.Insert(1)); |
| EXPECT_TRUE(mtf.Insert(2)); |
| EXPECT_TRUE(mtf.Insert(3)); |
| |
| CheckTree(mtf, |
| std::string(R"( |
| 2H2S3T2-------1H1S1T1-------D2 |
| 3H1S1T3-------D2 |
| )") |
| .substr(1), |
| /* print_timestamp = */ true); |
| |
| EXPECT_EQ(1u, mtf.GetNodeHandle(1)); |
| EXPECT_EQ(3u, mtf.GetTotalNodeCount()); |
| EXPECT_TRUE(mtf.Remove(1)); |
| EXPECT_EQ(3u, mtf.GetTotalNodeCount()); |
| |
| CheckTree(mtf, |
| std::string(R"( |
| 2H2S2T2-------D1 |
| 3H1S1T3-------D2 |
| )") |
| .substr(1), |
| /* print_timestamp = */ true); |
| |
| uint32_t value = 0; |
| EXPECT_TRUE(mtf.ValueFromRank(2, &value)); |
| EXPECT_EQ(2u, value); |
| |
| CheckTree(mtf, |
| std::string(R"( |
| 3H2S2T3-------D1 |
| 2H1S1T4-------D2 |
| )") |
| .substr(1), |
| /* print_timestamp = */ true); |
| |
| EXPECT_TRUE(mtf.Insert(1)); |
| EXPECT_EQ(1u, mtf.GetNodeHandle(1)); |
| EXPECT_EQ(3u, mtf.GetTotalNodeCount()); |
| } |
| |
| TEST(MoveToFront, LargerScale) { |
| MoveToFrontTester mtf; |
| uint32_t value = 0; |
| uint32_t rank = 0; |
| |
| for (uint32_t i = 1; i < 1000; ++i) { |
| ASSERT_TRUE(mtf.Insert(i)); |
| ASSERT_EQ(i, mtf.GetSize()); |
| |
| ASSERT_TRUE(mtf.RankFromValue(i, &rank)); |
| ASSERT_EQ(1u, rank); |
| |
| ASSERT_TRUE(mtf.ValueFromRank(1, &value)); |
| ASSERT_EQ(i, value); |
| } |
| |
| ASSERT_TRUE(mtf.ValueFromRank(999, &value)); |
| ASSERT_EQ(1u, value); |
| |
| ASSERT_TRUE(mtf.ValueFromRank(999, &value)); |
| ASSERT_EQ(2u, value); |
| |
| ASSERT_TRUE(mtf.ValueFromRank(999, &value)); |
| ASSERT_EQ(3u, value); |
| |
| ASSERT_TRUE(mtf.ValueFromRank(999, &value)); |
| ASSERT_EQ(4u, value); |
| |
| ASSERT_TRUE(mtf.ValueFromRank(999, &value)); |
| ASSERT_EQ(5u, value); |
| |
| ASSERT_TRUE(mtf.ValueFromRank(999, &value)); |
| ASSERT_EQ(6u, value); |
| |
| ASSERT_TRUE(mtf.ValueFromRank(101, &value)); |
| ASSERT_EQ(905u, value); |
| |
| ASSERT_TRUE(mtf.ValueFromRank(101, &value)); |
| ASSERT_EQ(906u, value); |
| |
| ASSERT_TRUE(mtf.ValueFromRank(101, &value)); |
| ASSERT_EQ(907u, value); |
| |
| ASSERT_TRUE(mtf.ValueFromRank(201, &value)); |
| ASSERT_EQ(805u, value); |
| |
| ASSERT_TRUE(mtf.ValueFromRank(201, &value)); |
| ASSERT_EQ(806u, value); |
| |
| ASSERT_TRUE(mtf.ValueFromRank(201, &value)); |
| ASSERT_EQ(807u, value); |
| |
| ASSERT_TRUE(mtf.ValueFromRank(301, &value)); |
| ASSERT_EQ(705u, value); |
| |
| ASSERT_TRUE(mtf.ValueFromRank(301, &value)); |
| ASSERT_EQ(706u, value); |
| |
| ASSERT_TRUE(mtf.ValueFromRank(301, &value)); |
| ASSERT_EQ(707u, value); |
| |
| ASSERT_TRUE(mtf.RankFromValue(605, &rank)); |
| ASSERT_EQ(401u, rank); |
| |
| ASSERT_TRUE(mtf.RankFromValue(606, &rank)); |
| ASSERT_EQ(401u, rank); |
| |
| ASSERT_TRUE(mtf.RankFromValue(607, &rank)); |
| ASSERT_EQ(401u, rank); |
| |
| ASSERT_TRUE(mtf.ValueFromRank(1, &value)); |
| ASSERT_EQ(607u, value); |
| |
| ASSERT_TRUE(mtf.ValueFromRank(2, &value)); |
| ASSERT_EQ(606u, value); |
| |
| ASSERT_TRUE(mtf.ValueFromRank(3, &value)); |
| ASSERT_EQ(605u, value); |
| |
| ASSERT_TRUE(mtf.ValueFromRank(4, &value)); |
| ASSERT_EQ(707u, value); |
| |
| ASSERT_TRUE(mtf.ValueFromRank(5, &value)); |
| ASSERT_EQ(706u, value); |
| |
| ASSERT_TRUE(mtf.ValueFromRank(6, &value)); |
| ASSERT_EQ(705u, value); |
| |
| ASSERT_TRUE(mtf.ValueFromRank(7, &value)); |
| ASSERT_EQ(807u, value); |
| |
| ASSERT_TRUE(mtf.ValueFromRank(8, &value)); |
| ASSERT_EQ(806u, value); |
| |
| ASSERT_TRUE(mtf.ValueFromRank(9, &value)); |
| ASSERT_EQ(805u, value); |
| |
| ASSERT_TRUE(mtf.ValueFromRank(10, &value)); |
| ASSERT_EQ(907u, value); |
| |
| ASSERT_TRUE(mtf.ValueFromRank(11, &value)); |
| ASSERT_EQ(906u, value); |
| |
| ASSERT_TRUE(mtf.ValueFromRank(12, &value)); |
| ASSERT_EQ(905u, value); |
| |
| ASSERT_TRUE(mtf.ValueFromRank(13, &value)); |
| ASSERT_EQ(6u, value); |
| |
| ASSERT_TRUE(mtf.ValueFromRank(14, &value)); |
| ASSERT_EQ(5u, value); |
| |
| ASSERT_TRUE(mtf.ValueFromRank(15, &value)); |
| ASSERT_EQ(4u, value); |
| |
| ASSERT_TRUE(mtf.ValueFromRank(16, &value)); |
| ASSERT_EQ(3u, value); |
| |
| ASSERT_TRUE(mtf.ValueFromRank(17, &value)); |
| ASSERT_EQ(2u, value); |
| |
| ASSERT_TRUE(mtf.ValueFromRank(18, &value)); |
| ASSERT_EQ(1u, value); |
| |
| ASSERT_TRUE(mtf.ValueFromRank(19, &value)); |
| ASSERT_EQ(999u, value); |
| |
| ASSERT_TRUE(mtf.ValueFromRank(20, &value)); |
| ASSERT_EQ(998u, value); |
| |
| ASSERT_TRUE(mtf.ValueFromRank(21, &value)); |
| ASSERT_EQ(997u, value); |
| |
| ASSERT_TRUE(mtf.RankFromValue(997, &rank)); |
| ASSERT_EQ(1u, rank); |
| |
| ASSERT_TRUE(mtf.RankFromValue(998, &rank)); |
| ASSERT_EQ(2u, rank); |
| |
| ASSERT_TRUE(mtf.RankFromValue(996, &rank)); |
| ASSERT_EQ(22u, rank); |
| |
| ASSERT_TRUE(mtf.Remove(995)); |
| |
| ASSERT_TRUE(mtf.RankFromValue(994, &rank)); |
| ASSERT_EQ(23u, rank); |
| |
| for (uint32_t i = 10; i < 1000; ++i) { |
| if (i != 995) { |
| ASSERT_TRUE(mtf.Remove(i)); |
| } else { |
| ASSERT_FALSE(mtf.Remove(i)); |
| } |
| } |
| |
| CheckTree(mtf, |
| std::string(R"( |
| 6H4S9T1029----8H2S3T8-------7H1S1T7-------D3 |
| 9H1S1T9-------D3 |
| 2H3S5T1033----4H2S3T1031----5H1S1T1030----D4 |
| 3H1S1T1032----D4 |
| 1H1S1T1034----D3 |
| )") |
| .substr(1), |
| /* print_timestamp = */ true); |
| |
| ASSERT_TRUE(mtf.Insert(1000)); |
| ASSERT_TRUE(mtf.ValueFromRank(1, &value)); |
| ASSERT_EQ(1000u, value); |
| } |
| |
| } // namespace |
| } // namespace comp |
| } // namespace spvtools |
