-
Notifications
You must be signed in to change notification settings - Fork 6
/
Copy pathrb-tests.lisp
202 lines (192 loc) · 10.2 KB
/
rb-tests.lisp
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
(in-package #:sdf/test)
(defun check/rb (&rest v)
(flet ((check-rb ()
(let ((rb (rb:make-tree))
(l nil))
(labels ((to-list (tree)
(let ((r nil))
(rb::walkn tree (lambda (a)
(when (rb::key a)
(assert (eql (rb::key a) (rb:value a))))
(push (rb:value a) r)))
(nreverse r)))
(ok ()
(assert (equalp (sort (copy-list l) '<)
(to-list rb))))
(add (x)
#++(format t "~& + ~s " x)
(rb:insert rb x)
(assert (not (member x l)))
(pushnew x l)
(ok)
#++(format t "~s~%"(to-list rb)))
(del (x)
(assert (member x l))
(alexandria:removef l x)
#++(format t " - ~s " x)
(let ((n (nth-value 1 (rb:find rb x))))
(assert n)
(rb:delete-node rb n)
#++(format t "~s~%" (to-list rb))
(ok))))
(loop for i in v
when (plusp i)
do (add i)
else do (del (- i)))
(when l
(let ((l2 (a:shuffle l)))
(loop for i in l2 do (del i))))
(assert (eql l nil))
(assert (not (rb:min rb)))))))
(finish (check-rb) "check rb ~s..." (subseq v 0 8))))
(define-test rb
(check/rb 122 138 139 -138 136 -139 132 -136 133 -132 126 130
124 -122 120 -124 70 -120 128 -126 -130 -128 118 111
109 101 99 95 93 62 60 58 57 56 53 48 51 42 45 37 35
32 30 23 21 27 26 91 90 86 89 83 82 115 116 -115 105
107 113 -118 106 -105 -113 -111 77 9 103 -109 71 -9
-103 -101 97 -99 73 -71 66 -70 -73 -77 76 -106 68
-66 -76 -107 69 -68 81 -116 -82 -81 -95 -97 85 -83
-85 -89 88 -86 -90 -88 25 -91 64 -93 -26 -25 28 -27
-21 -28 24 -23 -30 -24 33 -32 54 -56 -35 -33 39 -37
-64 -62 -39 -45 44 -42 -44 -51 50 -48 -50 -53 2 -60 1)
(check/rb 131 129 128 126 124 125 122 112 113 -122 117 -128
114 -124 120 -131 106 -126 105 -125 100 -112 101
-113 110 -129 108 -117 102 -114 111 -120 107 -106
89 -105 84 -100 82 -101 26 -82 97 -110 87 -102 94
-108 93 -107 74 -89 80 -111 71 -84 78 -94 62 -87 76
-93 58 -74 69 -80 67 -71 61 -67 64 -69 50 45 46 31
29 28 25 23 -97 -78 -26 -62 53 -61 60 -64 56 -60 54
-53 51 -50 7 -23 -25 -28 18 48 -46 -45 15 8 39 -76
37 -58 57 -56 2 -54 -37 -39 33 34 -48 -51 19 20 -18
-31 13 14 -15 -29 5 6 -7 -8 1)
(check/rb 101 91 89 96 99 95 84 66 93 -84 81 -89 77 -99 98
-101 97 -96 94 -95 68 -66 54 -93 92 -91 79 -81 78
-77 76 -98 75 -97 70 -94 69 -68 63 -54 24 -63 62
-92 46 -78 58 -79 57 -75 43 -70 51 -76 38 -69 48
-58 39 -46 45 -57 40 -43 42 -51 36 -38 37 -36 33
-42 18 15 14 3 27 26 11 9 -62 -48 -24 -39 6 -37 22
-33 20 -22 7 -6 19 -18 1 -9 -11 -26 4 16 -14)
(check/rb 87 80 85 -87 82 -80 83 -85 66 -82 76 75 77 -76
68 -75 73 -83 67 -66 72 -77 49 -68 51 47 43 45
39 41 64 -72 1 -49 48 -47 60 -45 57 -43 56 -41
61 -51 55 -39 28 36 20 23 32 33 35 -36 34 -28
21 -23 18 -20 14 -33 4 -32 26 -48 59 -60 58 -57
7 -56 12 -61 3 -55 54 -73 53 -64 11 10 9 8 6 5
2 -1)
(check/rb 1141 1136 1139 -1141 1137 -1136 1134 -1139 1119
-1137 1130 1128 1131 -1130 1124 -1128 1126
-1134 1120 -1119 1117 -1131 1092 -1124 1123
1122 1121 1104 1094 1099 1118 -1117 1079 -1092
1106 -1122 1102 -1104 1101 -1121 1096 -1099
1112 -1123 1111 -1094 1073 1090 1049 1052 1056
1039 1075 -1090 1058 -1073 1050 -1052 1068
-1049 1065 -1039 1064 -1056 1055 -1106 1046
-1102 1042 -1101 1037 -1096 1088 -1112 1081
-1111 1110 -1126 1109 -1118 1087 1086 1085 1084
1083 1082 1080 -1079 1078 -1120 1070 -1087 1061
-1086 1032 -1085 1028 -1084 1024 -1083 1020
-1082 1076 -1075 1047 -1058 1045 -1050 1067
-1068 1066 -1065 951 -1064 1063 -1070 1062
-1061 1030 -1032 1029 -1028 1022 -1024 1021
-1020 1006 1013 998 1000 987 988 974 975 956
957 1015 952 1004 -1006 1003 -1000 978 -987 977
-975 955 -956 1011 -952 997 -1055 994 -1046 991
-1042 992 -1037 989 -988 972 -1015 1014 -1013
983 -998 961 -974 958 -957 1012 -1088 906 -1081
-1003 -1004 -977 -978 -955 -1011 1010 -1076 981
-1047 980 -1045 923 -1067 960 -1066 692 -951
942 970 968 965 962 949 948 928 887 945 944 881
986 -1014 939 -983 933 -989 927 -961 912 -958
862 -972 971 -970 966 -968 950 -949 894 -948
946 -945 885 -944 943 -1063 964 -1062 947 -1030
925 -1029 888 -1022 909 -1021 900 -942 899 -965
896 -962 891 -928 886 -887 883 -881 877 -986
872 -939 870 -933 868 -912 863 -862 861 858 768
866 865 864 -971 -861 -858 -966 -950 -768 -866
-894 -946 -865 -864 -885 853 -900 851 -899 826
-886 893 -896 892 -891 884 -883 879 -877 847
-872 842 -870 833 -927 829 -868 844 -863 880
-879 845 -847 831 -833 830 -829 696 -844 843
-842 792 809 750 758 710 722 854 -853 839 -851
838 -893 817 -892 815 -826 813 -884 819 -838
818 -817 814 -813 794 -809 790 -792 752 -758
748 -750 712 -722 703 -710 811 -854 -839 799
787 -819 806 -818 804 -815 802 -814 800 -799
744 -806 784 -802 714 -804 798 -811 756 -787
-994 -997 -992 -991 904 -1012 903 -1010 823
-943 822 -880 796 -798 795 -794 782 -790 781
-800 777 -845 776 -964 773 -981 772 -980 763
-947 762 -843 754 -756 753 -752 746 -748 745
-744 741 -831 740 -925 737 -923 736 -960 726
-888 725 -830 678 -714 713 -712 701 -703 699
-784 695 -696 694 -909 691 -692 690 -906 684
683 679 702 716 -745 700 -699 719 -781 717 -796
681 -754 677 -678 -717 687 686 -719 -681 660
656 -716 -677 637 629 -700 672 -795 667 -782
659 -753 648 -746 635 -713 630 -701 662 -762
676 -822 652 -777 644 -741 518 -695 643 -725
674 -687 -672 -667 653 -686 651 -660 -648 -659
639 -656 638 -637 -635 -630 523 -629 626 624
615 614 610 554 540 538 525 621 521 520 -676
-626 -614 -652 -662 -610 -644 -538 -518 -520
-621 -643 504 -638 619 -674 617 -653 606 -651
580 -639 570 -523 607 558 516 542 547 529 608
-607 508 -516 544 -554 559 -608 543 -508 477
-504 502 -619 490 -606 605 -617 581 -580 571
-570 562 -823 557 -776 545 -763 535 -740 480
-726 397 -694 548 -547 546 -558 541 -542 707
-529 560 -559 489 -543 593 -544 592 -540 598
-624 596 -615 589 -525 588 -521 -502 -560 -489
-490 -548 -477 -546 -605 -541 -581 -571 -707
706 -903 494 -773 493 -772 483 -737 482 -736
417 -691 597 585 578 575 445 602 603 -904 601
-690 599 -598 595 -596 594 -593 591 -592 590
-589 565 -588 587 -597 586 -585 584 -684 579
-683 577 -578 576 -575 574 -679 569 -702 567
-602 566 -445 -599 -587 -586 -595 -594 -577
-591 -576 -567 -590 -566 -565 460 -562 459 -557
444 -545 443 -535 420 -480 418 -397 564 -706
456 -494 455 -493 440 -483 439 -482 382 -417
426 -460 425 -459 424 -444 423 -443 431 -420
430 -418 -425 -426 -423 -424 -431 -430 429 -603
411 -601 409 -584 374 -579 402 -574 365 -569
428 -564 395 -456 392 -455 388 -440 386 -439
381 -382 -428 -395 -388 -392 -381 -386 379 -429
362 -411 377 -409 372 -374 370 -402 367 -365
-377 -379 -372 -370 -362 -367 359 356 355 352
351 345 357 -356 354 -355 353 -352 347 -351 349
-359 346 -345 343 328 305 317 314 313 330 -343
319 -328 316 -317 315 -305 300 -314 297 -313
312 -357 208 -354 341 -353 279 -347 338 -349
163 -346 325 321 337 334 332 333 323 -325 322
-321 336 -337 335 -334 290 -333 287 -332 331
-330 212 -319 257 -316 261 -315 259 -300 256
-297 296 -323 295 -322 198 -336 292 -335 289
-290 288 -287 282 284 280 267 194 192 186 286
173 277 276 196 210 -312 199 -208 189 -192 182
-341 175 -279 269 -282 271 -267 190 -186 170
-173 197 -196 248 -194 246 -286 285 -284 251
-280 278 -277 242 -276 275 -338 164 -163 -269
-271 -189 -190 -197 -170 55 -212 41 -261 260
-259 274 -331 258 -257 9999 -256 255 240 252 236
234 231 230 227 265 223 243 219 232 -234 228
-227 220 -219 253 -255 237 -236 162 -265 264
-285 216 -252 250 -251 249 -248 247 -246 245
-278 131 -243 134 -242 241 -240 118 -231 117
-230 224 -223 217 -296 214 -295 51 -198 43 -292
37 -289 47 -288 119 -232 158 -228 149 -220 155
-253 146 -237 143 -162 161 -264 139 -250 137
-249 116 -245 135 -134 133 -216 113 -131 130
-133 111 -113 -130 -241 -118 -117 -111 -224 99
-119 151 -158 64 -149 148 -155 147 -146 66 -143
127 124 71 97 141 142 123 122 92 95 89 75 -161
-141 -139 -127 -122 -137 -97 -247 -92 -116 -89
-135 106 -148 102 104 85 -147 81 -99 79 78 73
-151 67 -66 65 16 63 -64 29 -123 76 -124 70 -71
109 -142 69 -95 1 -75 74 -73 13 -63 57 -104 56
-102 25 -79 22 -78 17 -65 2 -16 107 -106 -85 61
28 -81 21 -74 59 -67 14 -13 62 -61 9 -21 6 -14
3 -59 58 -107 4 -28 -199 -210))
#++
(test 'rb)