1 /* Copyright (c) 2007-2014 Massachusetts Institute of Technology
2 *
3 * Permission is hereby granted, free of charge, to any person obtaining
4 * a copy of this software and associated documentation files (the
5 * "Software"), to deal in the Software without restriction, including
6 * without limitation the rights to use, copy, modify, merge, publish,
7 * distribute, sublicense, and/or sell copies of the Software, and to
8 * permit persons to whom the Software is furnished to do so, subject to
9 * the following conditions:
10 *
11 * The above copyright notice and this permission notice shall be
12 * included in all copies or substantial portions of the Software.
13 *
14 * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,
15 * EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF
16 * MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND
17 * NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE
18 * LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION
19 * OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION
20 * WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
21 */
22
23 #include <stdio.h>
24 #include <stdlib.h>
25 #include <math.h>
26 #include <time.h>
27 #include "redblack.h"
28
29 #include "nlopt_config.h"
30 /* workaround for Solaris + gcc 3.4.x bug (see configure.ac) */
31 #if defined(__GNUC__) && defined(REPLACEMENT_HUGE_VAL)
32 # undef HUGE_VAL
33 # define HUGE_VAL REPLACEMENT_HUGE_VAL
34 #endif
35
comp(rb_key k1,rb_key k2)36 static int comp(rb_key k1, rb_key k2)
37 {
38 if (*k1 < *k2)
39 return -1;
40 if (*k1 > *k2)
41 return +1;
42 return 0;
43 }
44
main(int argc,char ** argv)45 int main(int argc, char **argv)
46 {
47 int N, M;
48 int *k;
49 double kd;
50 rb_tree t;
51 rb_node *n;
52 int i, j;
53
54 if (argc < 2) {
55 fprintf(stderr, "Usage: redblack_test Ntest [rand seed]\n");
56 return 1;
57 }
58
59 N = atoi(argv[1]);
60 k = (int *) malloc(N * sizeof(int));
61 nlopt_rb_tree_init(&t, comp);
62
63 srand((unsigned) (argc > 2 ? atoi(argv[2]) : time(NULL)));
64 for (i = 0; i < N; ++i) {
65 double *newk = (double *) malloc(sizeof(double));
66 *newk = (k[i] = rand() % N);
67 if (!nlopt_rb_tree_insert(&t, newk)) {
68 fprintf(stderr, "error in nlopt_rb_tree_insert\n");
69 return 1;
70 }
71 if (!nlopt_rb_tree_check(&t)) {
72 fprintf(stderr, "nlopt_rb_tree_check_failed after insert!\n");
73 return 1;
74 }
75 }
76
77 if (t.N != N) {
78 fprintf(stderr, "incorrect N (%d) in tree (vs. %d)\n", t.N, N);
79 return 1;
80 }
81
82 for (i = 0; i < N; ++i) {
83 kd = k[i];
84 if (!nlopt_rb_tree_find(&t, &kd)) {
85 fprintf(stderr, "nlopt_rb_tree_find lost %d!\n", k[i]);
86 return 1;
87 }
88 }
89
90 n = nlopt_rb_tree_min(&t);
91 for (i = 0; i < N; ++i) {
92 if (!n) {
93 fprintf(stderr, "not enough successors %d\n!", i);
94 return 1;
95 }
96 printf("%d: %g\n", i, n->k[0]);
97 n = nlopt_rb_tree_succ(n);
98 }
99 if (n) {
100 fprintf(stderr, "too many successors!\n");
101 return 1;
102 }
103
104 n = nlopt_rb_tree_max(&t);
105 for (i = 0; i < N; ++i) {
106 if (!n) {
107 fprintf(stderr, "not enough predecessors %d\n!", i);
108 return 1;
109 }
110 printf("%d: %g\n", i, n->k[0]);
111 n = nlopt_rb_tree_pred(n);
112 }
113 if (n) {
114 fprintf(stderr, "too many predecessors!\n");
115 return 1;
116 }
117
118 for (M = N; M > 0; --M) {
119 int knew = rand() % N; /* random new key */
120 j = rand() % M; /* random original key to replace */
121 for (i = 0; i < N; ++i)
122 if (k[i] >= 0)
123 if (j-- == 0)
124 break;
125 if (i >= N)
126 abort();
127 kd = k[i];
128 if (!(n = nlopt_rb_tree_find(&t, &kd))) {
129 fprintf(stderr, "nlopt_rb_tree_find lost %d!\n", k[i]);
130 return 1;
131 }
132 n->k[0] = knew;
133 if (!nlopt_rb_tree_resort(&t, n)) {
134 fprintf(stderr, "error in nlopt_rb_tree_resort\n");
135 return 1;
136 }
137 if (!nlopt_rb_tree_check(&t)) {
138 fprintf(stderr, "nlopt_rb_tree_check_failed after change %d!\n", N - M + 1);
139 return 1;
140 }
141 k[i] = -1 - knew;
142 }
143
144 if (t.N != N) {
145 fprintf(stderr, "incorrect N (%d) in tree (vs. %d)\n", t.N, N);
146 return 1;
147 }
148
149 for (i = 0; i < N; ++i)
150 k[i] = -1 - k[i]; /* undo negation above */
151
152 for (i = 0; i < N; ++i) {
153 rb_node *le, *gt;
154 double lek, gtk;
155 kd = 0.01 * (rand() % (N * 150) - N * 25);
156 le = nlopt_rb_tree_find_le(&t, &kd);
157 gt = nlopt_rb_tree_find_gt(&t, &kd);
158 n = nlopt_rb_tree_min(&t);
159 lek = le ? le->k[0] : -HUGE_VAL;
160 gtk = gt ? gt->k[0] : +HUGE_VAL;
161 printf("%g <= %g < %g\n", lek, kd, gtk);
162 if (n->k[0] > kd) {
163 if (le) {
164 fprintf(stderr, "found invalid le %g for %g\n", lek, kd);
165 return 1;
166 }
167 if (gt != n) {
168 fprintf(stderr, "gt is not first node for k=%g\n", kd);
169 return 1;
170 }
171 } else {
172 rb_node *succ = n;
173 do {
174 n = succ;
175 succ = nlopt_rb_tree_succ(n);
176 } while (succ && succ->k[0] <= kd);
177 if (n != le) {
178 fprintf(stderr, "nlopt_rb_tree_find_le gave wrong result for k=%g\n", kd);
179 return 1;
180 }
181 if (succ != gt) {
182 fprintf(stderr, "nlopt_rb_tree_find_gt gave wrong result for k=%g\n", kd);
183 return 1;
184 }
185 }
186 }
187
188 for (M = N; M > 0; --M) {
189 j = rand() % M;
190 for (i = 0; i < N; ++i)
191 if (k[i] >= 0)
192 if (j-- == 0)
193 break;
194 if (i >= N)
195 abort();
196 kd = k[i];
197 if (!(n = nlopt_rb_tree_find(&t, &kd))) {
198 fprintf(stderr, "nlopt_rb_tree_find lost %d!\n", k[i]);
199 return 1;
200 }
201 n = nlopt_rb_tree_remove(&t, n);
202 free(n->k);
203 free(n);
204 if (!nlopt_rb_tree_check(&t)) {
205 fprintf(stderr, "nlopt_rb_tree_check_failed after remove!\n");
206 return 1;
207 }
208 k[i] = -1 - k[i];
209 }
210
211 if (t.N != 0) {
212 fprintf(stderr, "nonzero N (%d) in tree at end\n", t.N);
213 return 1;
214 }
215
216 nlopt_rb_tree_destroy(&t);
217 free(k);
218
219 printf("SUCCESS.\n");
220 return 0;
221 }
222