123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242243244245246247248249250251252253254255256257258259260261262263264265266267268269270271272273274275276277278279280281282283284285286287288289290291292293294295296297298299300301302303304305306307308309310311312313314315316317318319320321322323324325326327328329330331332333334335336337338339340341342343344345346347348349350351352353354355356357358359360361362363364365366367368369370371372373374375376377378379380381382383384385386387388389390391392393394395396397398399400401402403404405406407408409410411412413414415416417418419420421422423424425426427428429430431432433434435436437438439440441442443444445446447448449450451452453454455456457458459460461462463464465466467468469470471472473474475476477478479480481482483484485486487488489490491492493494495496497498499500501502503504505506507508509510511512513514515516517518519520521522523524525526527528529530531532533534535536537538539540541542543544545546547548549550551552553554555556557558559560561562563564565566567568569570571572573574575576577578579580581582583584585586587588589590591592593594595596597598599600601602603604605606607608609610611612613614615616617618619620621622623624625626627628629630631632633634635636637638639640641642643644645646647648649650651652653654655656657658659660661662663664665666667668669670671672673674675676677678679680681682683684685686687688689690691692693694695696697698699700701702703704705706707708709710711712713714715716717718719720721722723724725726727728729730731732733734735736737738739740741742743744745746747748749750751752753754755756757758759760761762763764765766767768769770771772773774775776777778779780781782783784785786787788789790791792793794795796797798799800801802803804805806807808809810811812813814815816817818819820821822823824825826827828829 |
- // 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
|