1 /* -*- Mode: C++; tab-width: 9; indent-tabs-mode: nil; c-basic-offset: 2 -*- */
2 /* vim: set ts=8 sts=2 et sw=2 tw=80: */
3 /* This Source Code Form is subject to the terms of the Mozilla Public
4 * License, v. 2.0. If a copy of the MPL was not distributed with this file,
5 * You can obtain one at http://mozilla.org/MPL/2.0/. */
6
7 #include "mozilla/ArrayUtils.h"
8 #include "mozilla/Assertions.h"
9 #include "mozilla/SplayTree.h"
10 #include "mozilla/Unused.h"
11
12 using mozilla::SplayTree;
13 using mozilla::SplayTreeNode;
14
15 // The following array contains the values 0..999 in random order, as computed
16 // with the following Python program:
17 //
18 // from random import shuffle
19 // x = range(1000)
20 // shuffle(x)
21 // print(x);
22 //
23 static int gValues[] = {
24 778, 999, 248, 795, 607, 177, 725, 33, 215, 565, 436, 821, 941, 802, 322, 54,
25 151, 416, 531, 65, 818, 99, 340, 401, 274, 767, 278, 617, 425, 629, 833, 878,
26 440, 984, 724, 519, 100, 369, 490, 131, 422, 169, 932, 476, 823, 521, 390,
27 781, 747, 218, 376, 461, 717, 532, 471, 298, 720, 608, 334, 788, 161, 500,
28 280, 963, 430, 484, 779, 572, 96, 333, 650, 158, 199, 137, 991, 399, 882,
29 689, 358, 548, 196, 718, 211, 388, 133, 188, 321, 892, 25, 694, 735, 886,
30 872, 785, 195, 275, 696, 975, 393, 619, 894, 18, 281, 191, 792, 846, 861,
31 351, 542, 806, 570, 702, 931, 585, 444, 284, 217, 132, 251, 253, 302, 808,
32 224, 37, 63, 863, 409, 49, 780, 790, 31, 638, 890, 186, 114, 152, 949, 491,
33 207, 392, 170, 460, 794, 482, 877, 407, 263, 909, 249, 710, 614, 51, 431,
34 915, 62, 332, 74, 495, 901, 23, 365, 752, 89, 660, 745, 741, 547, 669, 449,
35 465, 605, 107, 774, 205, 852, 266, 247, 690, 835, 765, 410, 140, 122, 400,
36 510, 664, 105, 935, 230, 134, 106, 959, 375, 884, 361, 527, 715, 840, 272,
37 232, 102, 415, 903, 117, 313, 153, 463, 464, 876, 406, 967, 713, 381, 836,
38 555, 190, 859, 172, 483, 61, 633, 294, 993, 72, 337, 11, 896, 523, 101, 916,
39 244, 566, 706, 533, 439, 201, 222, 695, 739, 553, 571, 289, 918, 209, 189,
40 357, 814, 670, 866, 910, 579, 246, 636, 750, 891, 494, 758, 341, 626, 426,
41 772, 254, 682, 588, 104, 347, 184, 977, 126, 498, 165, 955, 241, 516, 235,
42 497, 121, 123, 791, 844, 259, 995, 283, 602, 417, 221, 308, 855, 429, 86,
43 345, 928, 44, 679, 796, 363, 402, 445, 492, 450, 964, 749, 925, 847, 637,
44 982, 648, 635, 481, 564, 867, 940, 291, 159, 290, 929, 59, 712, 986, 611,
45 954, 820, 103, 622, 316, 142, 204, 225, 678, 314, 84, 578, 315, 141, 990,
46 880, 504, 969, 412, 746, 47, 517, 124, 848, 466, 438, 674, 979, 782, 651,
47 181, 26, 435, 832, 386, 951, 229, 642, 655, 91, 162, 921, 647, 113, 686, 56,
48 805, 763, 245, 581, 287, 998, 525, 641, 135, 634, 237, 728, 112, 828, 228,
49 899, 1, 723, 16, 613, 144, 659, 97, 185, 312, 292, 733, 624, 276, 387, 926,
50 339, 768, 960, 610, 807, 656, 851, 219, 582, 709, 927, 514, 680, 870, 597,
51 536, 77, 164, 512, 149, 900, 85, 335, 997, 8, 705, 777, 653, 815, 311, 701,
52 507, 202, 530, 827, 541, 958, 82, 874, 55, 487, 383, 885, 684, 180, 829, 760,
53 109, 194, 540, 816, 906, 657, 469, 446, 857, 907, 38, 600, 618, 797, 950,
54 822, 277, 842, 116, 513, 255, 424, 643, 163, 372, 129, 67, 118, 754, 529,
55 917, 687, 473, 174, 538, 939, 663, 775, 474, 242, 883, 20, 837, 293, 584,
56 943, 32, 176, 904, 14, 448, 893, 888, 744, 171, 714, 454, 691, 261, 934, 606,
57 789, 825, 671, 397, 338, 317, 612, 737, 130, 41, 923, 574, 136, 980, 850, 12,
58 729, 197, 403, 57, 783, 360, 146, 75, 432, 447, 192, 799, 740, 267, 214, 250,
59 367, 853, 968, 120, 736, 391, 881, 784, 665, 68, 398, 350, 839, 268, 697,
60 567, 428, 738, 48, 182, 70, 220, 865, 418, 374, 148, 945, 353, 539, 589, 307,
61 427, 506, 265, 558, 128, 46, 336, 299, 349, 309, 377, 304, 420, 30, 34, 875,
62 948, 212, 394, 442, 719, 273, 269, 157, 502, 675, 751, 838, 897, 862, 831,
63 676, 590, 811, 966, 854, 477, 15, 598, 573, 108, 98, 81, 408, 421, 296, 73,
64 644, 456, 362, 666, 550, 331, 368, 193, 470, 203, 769, 342, 36, 604, 60, 970,
65 748, 813, 522, 515, 90, 672, 243, 793, 947, 595, 632, 912, 475, 258, 80, 873,
66 623, 524, 546, 262, 727, 216, 505, 330, 373, 58, 297, 609, 908, 150, 206,
67 703, 755, 260, 511, 213, 198, 766, 898, 992, 488, 405, 974, 770, 936, 743,
68 554, 0, 499, 976, 94, 160, 919, 434, 324, 156, 757, 830, 677, 183, 630, 871,
69 640, 938, 518, 344, 366, 742, 552, 306, 535, 200, 652, 496, 233, 419, 787,
70 318, 981, 371, 166, 143, 384, 88, 508, 698, 812, 559, 658, 549, 208, 599,
71 621, 961, 668, 563, 93, 154, 587, 560, 389, 3, 210, 326, 4, 924, 300, 2, 804,
72 914, 801, 753, 654, 27, 236, 19, 708, 451, 985, 596, 478, 922, 240, 127, 994,
73 983, 385, 472, 40, 528, 288, 111, 543, 568, 155, 625, 759, 937, 956, 545,
74 953, 962, 382, 479, 809, 557, 501, 354, 414, 343, 378, 843, 379, 178, 556,
75 800, 803, 592, 627, 942, 576, 920, 704, 707, 726, 223, 119, 404, 24, 879,
76 722, 868, 5, 238, 817, 520, 631, 946, 462, 457, 295, 480, 957, 441, 145, 286,
77 303, 688, 17, 628, 493, 364, 226, 110, 615, 69, 320, 534, 593, 721, 411, 285,
78 869, 952, 849, 139, 356, 346, 28, 887, 810, 92, 798, 544, 458, 996, 692, 396,
79 667, 328, 173, 22, 773, 50, 645, 987, 42, 685, 734, 700, 683, 601, 580, 639,
80 913, 323, 858, 179, 761, 6, 841, 905, 234, 730, 29, 21, 575, 586, 902, 443,
81 826, 646, 257, 125, 649, 53, 453, 252, 13, 87, 971, 227, 485, 168, 380, 711,
82 79, 732, 325, 52, 468, 76, 551, 39, 395, 327, 973, 459, 45, 583, 989, 147,
83 455, 776, 944, 569, 889, 256, 35, 175, 834, 756, 933, 860, 526, 845, 864,
84 764, 771, 282, 9, 693, 352, 731, 7, 577, 264, 319, 138, 467, 819, 930, 231,
85 115, 988, 978, 762, 486, 301, 616, 10, 78, 603, 452, 965, 279, 972, 413, 895,
86 591, 662, 594, 348, 423, 489, 43, 699, 433, 509, 355, 270, 66, 83, 95, 561,
87 661, 562, 329, 620, 370, 64, 187, 503, 716, 856, 310, 786, 167, 71, 239, 359,
88 537, 437, 305, 673, 824, 911, 681, 271
89 };
90
91 struct SplayInt : SplayTreeNode<SplayInt>
92 {
SplayIntSplayInt93 explicit SplayInt(int aValue) : mValue(aValue) {}
94
compareSplayInt95 static int compare(const SplayInt& aOne, const SplayInt& aTwo)
96 {
97 if (aOne.mValue < aTwo.mValue) {
98 return -1;
99 }
100 if (aOne.mValue > aTwo.mValue) {
101 return 1;
102 }
103 return 0;
104 }
105
106 int mValue;
107 };
108
109 struct SplayNoCopy : SplayTreeNode<SplayNoCopy>
110 {
111 SplayNoCopy(const SplayNoCopy&) = delete;
112 SplayNoCopy(SplayNoCopy&&) = delete;
113
compareSplayNoCopy114 static int compare(const SplayNoCopy&, const SplayNoCopy&) { return 0; }
115 };
116
117 static SplayTree<SplayNoCopy, SplayNoCopy> testNoCopy;
118
119 int
main()120 main()
121 {
122 mozilla::Unused << testNoCopy;
123
124 SplayTree<SplayInt, SplayInt> tree;
125
126 MOZ_RELEASE_ASSERT(tree.empty());
127
128 MOZ_RELEASE_ASSERT(!tree.find(SplayInt(0)));
129
130 static const int N = mozilla::ArrayLength(gValues);
131
132 // Insert the values, and check each one is findable just after insertion.
133 for (int i = 0; i < N; i++) {
134 tree.insert(new SplayInt(gValues[i]));
135 SplayInt* inserted = tree.find(SplayInt(gValues[i]));
136 MOZ_RELEASE_ASSERT(inserted);
137 MOZ_RELEASE_ASSERT(tree.findOrInsert(SplayInt(gValues[i])) == inserted);
138 tree.checkCoherency();
139 }
140
141 // Check they're all findable after all insertions.
142 for (int i = 0; i < N; i++) {
143 MOZ_RELEASE_ASSERT(tree.find(SplayInt(gValues[i])));
144 MOZ_RELEASE_ASSERT(tree.findOrInsert(SplayInt(gValues[i])));
145 tree.checkCoherency();
146 }
147
148 // Check that non-inserted values cannot be found.
149 MOZ_RELEASE_ASSERT(!tree.find(SplayInt(-1)));
150 MOZ_RELEASE_ASSERT(!tree.find(SplayInt(N)));
151 MOZ_RELEASE_ASSERT(!tree.find(SplayInt(0x7fffffff)));
152
153 // Remove the values, and check each one is not findable just after removal.
154 for (int i = 0; i < N; i++) {
155 SplayInt* removed = tree.remove(SplayInt(gValues[i]));
156 MOZ_RELEASE_ASSERT(removed->mValue == gValues[i]);
157 MOZ_RELEASE_ASSERT(!tree.find(*removed));
158 delete removed;
159 tree.checkCoherency();
160 }
161
162 MOZ_RELEASE_ASSERT(tree.empty());
163
164 // Insert the values, and check each one is findable just after insertion.
165 for (int i = 0; i < N; i++) {
166 SplayInt* inserted = tree.findOrInsert(SplayInt(gValues[i]));
167 MOZ_RELEASE_ASSERT(tree.find(SplayInt(gValues[i])) == inserted);
168 MOZ_RELEASE_ASSERT(tree.findOrInsert(SplayInt(gValues[i])) == inserted);
169 tree.checkCoherency();
170 }
171
172 // Check they're all findable after all insertions.
173 for (int i = 0; i < N; i++) {
174 MOZ_RELEASE_ASSERT(tree.find(SplayInt(gValues[i])));
175 MOZ_RELEASE_ASSERT(tree.findOrInsert(SplayInt(gValues[i])));
176 tree.checkCoherency();
177 }
178
179 // Check that non-inserted values cannot be found.
180 MOZ_RELEASE_ASSERT(!tree.find(SplayInt(-1)));
181 MOZ_RELEASE_ASSERT(!tree.find(SplayInt(N)));
182 MOZ_RELEASE_ASSERT(!tree.find(SplayInt(0x7fffffff)));
183
184 // Remove the values, and check each one is not findable just after removal.
185 for (int i = 0; i < N; i++) {
186 SplayInt* removed = tree.remove(SplayInt(gValues[i]));
187 MOZ_RELEASE_ASSERT(removed->mValue == gValues[i]);
188 MOZ_RELEASE_ASSERT(!tree.find(*removed));
189 delete removed;
190 tree.checkCoherency();
191 }
192
193 MOZ_RELEASE_ASSERT(tree.empty());
194
195 // Reinsert the values, in reverse order to last time.
196 for (int i = 0; i < N; i++) {
197 tree.insert(new SplayInt(gValues[N - i - 1]));
198 tree.checkCoherency();
199 }
200
201 // Remove the minimum value repeatedly.
202 for (int i = 0; i < N; i++) {
203 SplayInt* removed = tree.removeMin();
204 MOZ_RELEASE_ASSERT(removed->mValue == i);
205 delete removed;
206 tree.checkCoherency();
207 }
208
209 MOZ_RELEASE_ASSERT(tree.empty());
210
211 return 0;
212 }
213