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.
TestInsert(uint32_t val)32 void TestInsert(uint32_t val) { InsertNode(CreateNode(val, val)); }
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_) 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.
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()) 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).
GetTotalNodeCount() const57 size_t GetTotalNodeCount() const {
58 assert(nodes_.size());
59 return nodes_.size() - 1;
60 }
61
GetLastAccessedValue() const62 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
PrintTreeInternal(std::ostream & out,uint32_t node,size_t depth,bool print_timestamp) const76 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
CheckTree(const MoveToFrontTester & mtf,const std::string & expected,bool print_timestamp=false)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
TEST(MoveToFront,EmptyTree)114 TEST(MoveToFront, EmptyTree) {
115 MoveToFrontTester mtf;
116 CheckTree(mtf, std::string());
117 }
118
TEST(MoveToFront,InsertLeftRotation)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
TEST(MoveToFront,InsertRightRotation)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
TEST(MoveToFront,InsertRightLeftRotation)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
TEST(MoveToFront,InsertLeftRightRotation)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
TEST(MoveToFront,RemoveSingleton)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
TEST(MoveToFront,RemoveRootWithScapegoat)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
TEST(MoveToFront,RemoveRightRotation)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
TEST(MoveToFront,RemoveLeftRotation)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
TEST(MoveToFront,RemoveLeftRightRotation)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
TEST(MoveToFront,RemoveRightLeftRotation)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
TEST(MoveToFront,MultipleOperations)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
TEST(MoveToFront,BiggerScaleTreeTest)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
TEST(MoveToFront,RankFromValue)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
TEST(MoveToFront,ValueFromRank)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
TEST(MoveToFront,Remove)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
TEST(MoveToFront,LargerScale)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