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