1 | /* GtkRBTree tests. |
2 | * |
3 | * Copyright (C) 2011, Red Hat, Inc. |
4 | * Authors: Benjamin Otte <otte@gnome.org> |
5 | * |
6 | * This library is free software; you can redistribute it and/or |
7 | * modify it under the terms of the GNU Lesser General Public |
8 | * License as published by the Free Software Foundation; either |
9 | * version 2 of the License, or (at your option) any later version. |
10 | * |
11 | * This library is distributed in the hope that it will be useful, |
12 | * but WITHOUT ANY WARRANTY; without even the implied warranty of |
13 | * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU |
14 | * Lesser General Public License for more details. |
15 | * |
16 | * You should have received a copy of the GNU Lesser General Public |
17 | * License along with this library. If not, see <http://www.gnu.org/licenses/>. |
18 | */ |
19 | |
20 | #include <locale.h> |
21 | |
22 | #include <gtk/gtk.h> |
23 | |
24 | #define LARGE_VALUE (1000 * 1000) |
25 | |
26 | static GtkBitset * |
27 | create_powers_of_10 (void) |
28 | { |
29 | GtkBitset *set; |
30 | guint i; |
31 | |
32 | set = gtk_bitset_new_empty (); |
33 | for (i = 1; i <= LARGE_VALUE; i *= 10) |
34 | gtk_bitset_add (self: set, value: i); |
35 | |
36 | return set; |
37 | } |
38 | |
39 | static GtkBitset * |
40 | create_powers_of_10_ranges (void) |
41 | { |
42 | GtkBitset *set; |
43 | guint i, j; |
44 | |
45 | set = gtk_bitset_new_empty (); |
46 | for (i = 1, j = 0; i <= LARGE_VALUE; i *= 10, j++) |
47 | gtk_bitset_add_range (self: set, start: i - j, n_items: 2 * j); |
48 | |
49 | return set; |
50 | } |
51 | |
52 | static GtkBitset * |
53 | create_large_range (void) |
54 | { |
55 | GtkBitset *set; |
56 | |
57 | set = gtk_bitset_new_empty (); |
58 | gtk_bitset_add_range (self: set, start: 0, LARGE_VALUE); |
59 | |
60 | return set; |
61 | } |
62 | |
63 | static GtkBitset * |
64 | create_large_rectangle (void) |
65 | { |
66 | GtkBitset *set; |
67 | |
68 | set = gtk_bitset_new_empty (); |
69 | gtk_bitset_add_rectangle (self: set, start: 0, width: 900, height: 900, stride: 1000); |
70 | |
71 | return set; |
72 | } |
73 | |
74 | static struct { |
75 | GtkBitset * (* create) (void); |
76 | guint n_elements; |
77 | guint minimum; |
78 | guint maximum; |
79 | } bitsets[] = |
80 | { |
81 | { gtk_bitset_new_empty, 0, G_MAXUINT, 0 }, |
82 | { create_powers_of_10, 7, 1, LARGE_VALUE }, |
83 | { create_powers_of_10_ranges, 42, 9, LARGE_VALUE + 5, }, |
84 | { create_large_range, LARGE_VALUE, 0, LARGE_VALUE - 1 }, |
85 | { create_large_rectangle, 900 * 900, 0, 899899 } |
86 | }; |
87 | |
88 | /* UTILITIES */ |
89 | |
90 | /* TEST */ |
91 | |
92 | static void |
93 | test_is_empty (void) |
94 | { |
95 | guint i; |
96 | GtkBitset *set; |
97 | |
98 | for (i = 0; i < G_N_ELEMENTS (bitsets); i++) |
99 | { |
100 | set = bitsets[i].create(); |
101 | |
102 | if (bitsets[i].n_elements == 0) |
103 | g_assert_true (gtk_bitset_is_empty (set)); |
104 | else |
105 | g_assert_false (gtk_bitset_is_empty (set)); |
106 | |
107 | gtk_bitset_unref (self: set); |
108 | } |
109 | } |
110 | |
111 | static void |
112 | test_minimum (void) |
113 | { |
114 | guint i; |
115 | GtkBitset *set; |
116 | GtkBitsetIter iter; |
117 | gboolean success; |
118 | guint value; |
119 | |
120 | for (i = 0; i < G_N_ELEMENTS (bitsets); i++) |
121 | { |
122 | set = bitsets[i].create(); |
123 | |
124 | g_assert_cmpint (gtk_bitset_get_minimum (set), ==, bitsets[i].minimum); |
125 | |
126 | success = gtk_bitset_iter_init_first (iter: &iter, set, value: &value); |
127 | if (success) |
128 | { |
129 | g_assert_false (bitsets[i].n_elements == 0); |
130 | g_assert_cmpint (value, ==, bitsets[i].minimum); |
131 | } |
132 | else |
133 | { |
134 | g_assert_true (bitsets[i].n_elements == 0); |
135 | g_assert_cmpint (value, ==, 0); |
136 | } |
137 | g_assert_cmpint (gtk_bitset_iter_is_valid (&iter), ==, success); |
138 | g_assert_cmpint (gtk_bitset_iter_get_value (&iter), ==, value); |
139 | |
140 | gtk_bitset_unref (self: set); |
141 | } |
142 | } |
143 | |
144 | static void |
145 | test_maximum (void) |
146 | { |
147 | guint i; |
148 | GtkBitset *set; |
149 | GtkBitsetIter iter; |
150 | gboolean success; |
151 | guint value; |
152 | |
153 | for (i = 0; i < G_N_ELEMENTS (bitsets); i++) |
154 | { |
155 | set = bitsets[i].create(); |
156 | |
157 | g_assert_cmpint (gtk_bitset_get_maximum (set), ==, bitsets[i].maximum); |
158 | |
159 | success = gtk_bitset_iter_init_last (iter: &iter, set, value: &value); |
160 | if (success) |
161 | { |
162 | g_assert_false (bitsets[i].n_elements == 0); |
163 | g_assert_cmpint (value, ==, bitsets[i].maximum); |
164 | } |
165 | else |
166 | { |
167 | g_assert_true (bitsets[i].n_elements == 0); |
168 | g_assert_cmpint (value, ==, 0); |
169 | } |
170 | g_assert_cmpint (gtk_bitset_iter_is_valid (&iter), ==, success); |
171 | g_assert_cmpint (gtk_bitset_iter_get_value (&iter), ==, value); |
172 | |
173 | gtk_bitset_unref (self: set); |
174 | } |
175 | } |
176 | |
177 | static void |
178 | test_equals (void) |
179 | { |
180 | guint i, j; |
181 | GtkBitset *iset, *jset; |
182 | |
183 | for (i = 0; i < G_N_ELEMENTS (bitsets); i++) |
184 | { |
185 | iset = bitsets[i].create(); |
186 | |
187 | g_assert_true (gtk_bitset_equals (iset, iset)); |
188 | |
189 | for (j = 0; j < G_N_ELEMENTS (bitsets); j++) |
190 | { |
191 | jset = bitsets[j].create(); |
192 | |
193 | if (i == j) |
194 | g_assert_true (gtk_bitset_equals (iset, jset)); |
195 | else |
196 | g_assert_false (gtk_bitset_equals (iset, jset)); |
197 | |
198 | gtk_bitset_unref (self: jset); |
199 | } |
200 | |
201 | gtk_bitset_unref (self: iset); |
202 | } |
203 | } |
204 | |
205 | static void |
206 | test_union (void) |
207 | { |
208 | guint i, j, k, min, max; |
209 | GtkBitset *iset, *jset, *testset; |
210 | |
211 | for (i = 0; i < G_N_ELEMENTS (bitsets); i++) |
212 | { |
213 | iset = bitsets[i].create(); |
214 | |
215 | g_assert_true (gtk_bitset_equals (iset, iset)); |
216 | |
217 | for (j = 0; j < G_N_ELEMENTS (bitsets); j++) |
218 | { |
219 | jset = bitsets[j].create(); |
220 | |
221 | testset = gtk_bitset_copy (self: iset); |
222 | gtk_bitset_union (self: testset, other: jset); |
223 | |
224 | min = MIN (gtk_bitset_get_minimum (iset), gtk_bitset_get_minimum (jset)); |
225 | g_assert_cmpint (min, <=, gtk_bitset_get_minimum (testset)); |
226 | max = MAX (gtk_bitset_get_maximum (iset), gtk_bitset_get_maximum (jset)); |
227 | g_assert_cmpint (max, >=, gtk_bitset_get_maximum (testset)); |
228 | |
229 | for (k = min; k <= max; k++) |
230 | { |
231 | g_assert_cmpint (gtk_bitset_contains (iset, k) || gtk_bitset_contains (jset, k), ==, gtk_bitset_contains (testset, k)); |
232 | } |
233 | |
234 | gtk_bitset_unref (self: testset); |
235 | gtk_bitset_unref (self: jset); |
236 | } |
237 | |
238 | gtk_bitset_unref (self: iset); |
239 | } |
240 | } |
241 | |
242 | static void |
243 | test_intersect (void) |
244 | { |
245 | guint i, j, k, min, max; |
246 | GtkBitset *iset, *jset, *testset; |
247 | |
248 | for (i = 0; i < G_N_ELEMENTS (bitsets); i++) |
249 | { |
250 | iset = bitsets[i].create(); |
251 | |
252 | g_assert_true (gtk_bitset_equals (iset, iset)); |
253 | |
254 | for (j = 0; j < G_N_ELEMENTS (bitsets); j++) |
255 | { |
256 | jset = bitsets[j].create(); |
257 | |
258 | testset = gtk_bitset_copy (self: iset); |
259 | gtk_bitset_intersect (self: testset, other: jset); |
260 | |
261 | min = MIN (gtk_bitset_get_minimum (iset), gtk_bitset_get_minimum (jset)); |
262 | g_assert_cmpint (min, <=, gtk_bitset_get_minimum (testset)); |
263 | max = MAX (gtk_bitset_get_maximum (iset), gtk_bitset_get_maximum (jset)); |
264 | g_assert_cmpint (max, >=, gtk_bitset_get_maximum (testset)); |
265 | |
266 | for (k = min; k <= max; k++) |
267 | { |
268 | g_assert_cmpint (gtk_bitset_contains (iset, k) && gtk_bitset_contains (jset, k), ==, gtk_bitset_contains (testset, k)); |
269 | } |
270 | |
271 | gtk_bitset_unref (self: testset); |
272 | gtk_bitset_unref (self: jset); |
273 | } |
274 | |
275 | gtk_bitset_unref (self: iset); |
276 | } |
277 | } |
278 | |
279 | static void |
280 | test_difference (void) |
281 | { |
282 | guint i, j, k, min, max; |
283 | GtkBitset *iset, *jset, *testset; |
284 | |
285 | for (i = 0; i < G_N_ELEMENTS (bitsets); i++) |
286 | { |
287 | iset = bitsets[i].create(); |
288 | |
289 | g_assert_true (gtk_bitset_equals (iset, iset)); |
290 | |
291 | for (j = 0; j < G_N_ELEMENTS (bitsets); j++) |
292 | { |
293 | jset = bitsets[j].create(); |
294 | |
295 | testset = gtk_bitset_copy (self: iset); |
296 | gtk_bitset_difference (self: testset, other: jset); |
297 | |
298 | min = MIN (gtk_bitset_get_minimum (iset), gtk_bitset_get_minimum (jset)); |
299 | g_assert_cmpint (min, <=, gtk_bitset_get_minimum (testset)); |
300 | max = MAX (gtk_bitset_get_maximum (iset), gtk_bitset_get_maximum (jset)); |
301 | g_assert_cmpint (max, >=, gtk_bitset_get_maximum (testset)); |
302 | |
303 | for (k = min; k <= max; k++) |
304 | { |
305 | g_assert_cmpint (gtk_bitset_contains (iset, k) ^ gtk_bitset_contains (jset, k), ==, gtk_bitset_contains (testset, k)); |
306 | } |
307 | |
308 | gtk_bitset_unref (self: testset); |
309 | gtk_bitset_unref (self: jset); |
310 | } |
311 | |
312 | gtk_bitset_unref (self: iset); |
313 | } |
314 | } |
315 | |
316 | static void |
317 | test_subtract (void) |
318 | { |
319 | guint i, j, k, min, max; |
320 | GtkBitset *iset, *jset, *testset; |
321 | |
322 | for (i = 0; i < G_N_ELEMENTS (bitsets); i++) |
323 | { |
324 | iset = bitsets[i].create(); |
325 | |
326 | g_assert_true (gtk_bitset_equals (iset, iset)); |
327 | |
328 | for (j = 0; j < G_N_ELEMENTS (bitsets); j++) |
329 | { |
330 | jset = bitsets[j].create(); |
331 | |
332 | testset = gtk_bitset_copy (self: iset); |
333 | gtk_bitset_subtract (self: testset, other: jset); |
334 | |
335 | min = MIN (gtk_bitset_get_minimum (iset), gtk_bitset_get_minimum (jset)); |
336 | g_assert_cmpint (min, <=, gtk_bitset_get_minimum (testset)); |
337 | max = MAX (gtk_bitset_get_maximum (iset), gtk_bitset_get_maximum (jset)); |
338 | g_assert_cmpint (max, >=, gtk_bitset_get_maximum (testset)); |
339 | |
340 | for (k = min; k <= max; k++) |
341 | { |
342 | g_assert_cmpint (gtk_bitset_contains (iset, k) && !gtk_bitset_contains (jset, k), ==, gtk_bitset_contains (testset, k)); |
343 | } |
344 | |
345 | gtk_bitset_unref (self: testset); |
346 | gtk_bitset_unref (self: jset); |
347 | } |
348 | |
349 | gtk_bitset_unref (self: iset); |
350 | } |
351 | } |
352 | |
353 | static void |
354 | test_shift_left (void) |
355 | { |
356 | guint i, j, k, min, max; |
357 | GtkBitset *iset, *testset; |
358 | |
359 | for (i = 0; i < G_N_ELEMENTS (bitsets); i++) |
360 | { |
361 | iset = bitsets[i].create(); |
362 | |
363 | for (j = 1; j < 10000000; j *= 10) |
364 | { |
365 | testset = gtk_bitset_copy (self: iset); |
366 | |
367 | gtk_bitset_shift_left (self: testset, amount: j); |
368 | |
369 | min = MIN (gtk_bitset_get_minimum (iset), gtk_bitset_get_minimum (testset)); |
370 | max = MAX (gtk_bitset_get_maximum (iset), gtk_bitset_get_maximum (testset)); |
371 | |
372 | for (k = min; k <= max; k++) |
373 | { |
374 | if (k >= j) |
375 | g_assert_cmpint (gtk_bitset_contains (iset, k), ==, gtk_bitset_contains (testset, k - j)); |
376 | } |
377 | |
378 | gtk_bitset_unref (self: testset); |
379 | } |
380 | |
381 | gtk_bitset_unref (self: iset); |
382 | } |
383 | } |
384 | |
385 | static void |
386 | test_shift_right (void) |
387 | { |
388 | guint i, j, k, min, max; |
389 | GtkBitset *iset, *testset; |
390 | |
391 | for (i = 0; i < G_N_ELEMENTS (bitsets); i++) |
392 | { |
393 | iset = bitsets[i].create(); |
394 | |
395 | for (j = 1; j < 10000000; j *= 10) |
396 | { |
397 | testset = gtk_bitset_copy (self: iset); |
398 | |
399 | gtk_bitset_shift_right (self: testset, amount: j); |
400 | |
401 | min = MIN (gtk_bitset_get_minimum (iset), gtk_bitset_get_minimum (testset)); |
402 | max = MAX (gtk_bitset_get_maximum (iset), gtk_bitset_get_maximum (testset)); |
403 | |
404 | for (k = min; k <= max; k++) |
405 | { |
406 | if (k <= G_MAXUINT - j) |
407 | g_assert_cmpint (gtk_bitset_contains (iset, k), ==, gtk_bitset_contains (testset, k + j)); |
408 | } |
409 | |
410 | gtk_bitset_unref (self: testset); |
411 | } |
412 | |
413 | gtk_bitset_unref (self: iset); |
414 | } |
415 | } |
416 | |
417 | static void |
418 | test_slice (void) |
419 | { |
420 | GtkBitset *set; |
421 | guint i; |
422 | |
423 | set = gtk_bitset_new_empty (); |
424 | |
425 | gtk_bitset_add_range (self: set, start: 10, n_items: 30); |
426 | |
427 | gtk_bitset_splice (self: set, position: 20, removed: 10, added: 20); |
428 | |
429 | for (i = 0; i < 60; i++) |
430 | g_assert_cmpint (gtk_bitset_contains (set, i), ==, (i >= 10 && i < 20) || |
431 | (i >= 40 && i < 50)); |
432 | |
433 | gtk_bitset_splice (self: set, position: 25, removed: 10, added: 0); |
434 | |
435 | for (i = 0; i < 60; i++) |
436 | g_assert_cmpint (gtk_bitset_contains (set, i), ==, (i >= 10 && i < 20) || |
437 | (i >= 30 && i < 40)); |
438 | |
439 | gtk_bitset_unref (self: set); |
440 | } |
441 | |
442 | static void |
443 | test_rectangle (void) |
444 | { |
445 | GtkBitset *set; |
446 | GString *s; |
447 | guint i, j; |
448 | |
449 | set = gtk_bitset_new_empty (); |
450 | |
451 | gtk_bitset_add_rectangle (self: set, start: 8, width: 5, height: 5, stride: 7); |
452 | gtk_bitset_remove_rectangle (self: set, start: 16, width: 3, height: 3, stride: 7); |
453 | gtk_bitset_add_rectangle (self: set, start: 24, width: 1, height: 1, stride: 7); |
454 | |
455 | s = g_string_new (init: "" ); |
456 | for (i = 0; i < 7; i++) |
457 | { |
458 | for (j = 0; j < 7; j++) |
459 | g_string_append_printf (string: s, format: "%c " , |
460 | gtk_bitset_contains (self: set, value: i * 7 + j) ? '*' : ' '); |
461 | g_string_append (string: s, val: "\n" ); |
462 | } |
463 | g_assert_cmpstr (s->str, ==, |
464 | " \n" |
465 | " * * * * * \n" |
466 | " * * \n" |
467 | " * * * \n" |
468 | " * * \n" |
469 | " * * * * * \n" |
470 | " \n" ); |
471 | |
472 | g_string_free (string: s, TRUE); |
473 | gtk_bitset_unref (self: set); |
474 | } |
475 | |
476 | static void |
477 | test_iter (void) |
478 | { |
479 | GtkBitset *set; |
480 | GtkBitsetIter iter; |
481 | gboolean ret; |
482 | guint value; |
483 | |
484 | set = gtk_bitset_new_empty (); |
485 | |
486 | ret = gtk_bitset_iter_init_first (iter: &iter, set, value: &value); |
487 | g_assert_false (ret); |
488 | |
489 | g_assert_false (gtk_bitset_iter_is_valid (&iter)); |
490 | g_assert_cmpuint (gtk_bitset_iter_get_value (&iter), ==, 0); |
491 | g_assert_false (gtk_bitset_iter_previous (&iter, &value)); |
492 | g_assert_false (gtk_bitset_iter_next (&iter, &value)); |
493 | |
494 | ret = gtk_bitset_iter_init_last (iter: &iter, set, value: &value); |
495 | g_assert_false (ret); |
496 | |
497 | g_assert_false (gtk_bitset_iter_is_valid (&iter)); |
498 | g_assert_cmpuint (gtk_bitset_iter_get_value (&iter), ==, 0); |
499 | g_assert_false (gtk_bitset_iter_previous (&iter, &value)); |
500 | g_assert_false (gtk_bitset_iter_next (&iter, &value)); |
501 | |
502 | ret = gtk_bitset_iter_init_at (iter: &iter, set, target: 0, value: &value); |
503 | |
504 | g_assert_false (gtk_bitset_iter_is_valid (&iter)); |
505 | g_assert_cmpuint (gtk_bitset_iter_get_value (&iter), ==, 0); |
506 | g_assert_false (gtk_bitset_iter_previous (&iter, &value)); |
507 | g_assert_false (gtk_bitset_iter_next (&iter, &value)); |
508 | |
509 | gtk_bitset_add_range_closed (self: set, first: 10, last: 20); |
510 | |
511 | ret = gtk_bitset_iter_init_first (iter: &iter, set, value: &value); |
512 | g_assert_true (ret); |
513 | g_assert_true (gtk_bitset_iter_is_valid (&iter)); |
514 | g_assert_cmpuint (value, ==, 10); |
515 | g_assert_cmpuint (gtk_bitset_iter_get_value (&iter), ==, 10); |
516 | |
517 | ret = gtk_bitset_iter_next (iter: &iter, value: &value); |
518 | g_assert_true (ret); |
519 | g_assert_cmpuint (value, ==, 11); |
520 | |
521 | ret = gtk_bitset_iter_next (iter: &iter, NULL); |
522 | g_assert_true (ret); |
523 | g_assert_cmpuint (gtk_bitset_iter_get_value (&iter), ==, 12); |
524 | |
525 | ret = gtk_bitset_iter_init_last (iter: &iter, set, value: &value); |
526 | g_assert_true (ret); |
527 | g_assert_true (gtk_bitset_iter_is_valid (&iter)); |
528 | g_assert_cmpuint (value, ==, 20); |
529 | |
530 | ret = gtk_bitset_iter_init_at (iter: &iter, set, target: 5, NULL); |
531 | g_assert_true (ret); |
532 | g_assert_true (gtk_bitset_iter_is_valid (&iter)); |
533 | g_assert_cmpuint (gtk_bitset_iter_get_value (&iter), ==, 10); |
534 | |
535 | ret = gtk_bitset_iter_previous (iter: &iter, NULL); |
536 | g_assert_false (ret); |
537 | |
538 | g_assert_false (gtk_bitset_iter_is_valid (&iter)); |
539 | |
540 | ret = gtk_bitset_iter_init_at (iter: &iter, set, target: 100, NULL); |
541 | g_assert_false (ret); |
542 | |
543 | gtk_bitset_unref (self: set); |
544 | } |
545 | |
546 | static void |
547 | test_splice_overflow (void) |
548 | { |
549 | GtkBitset *set, *compare; |
550 | |
551 | set = gtk_bitset_new_range (start: 3, n_items: 1); |
552 | gtk_bitset_splice (self: set, position: 0, removed: 0, added: 13); |
553 | |
554 | compare = gtk_bitset_new_range (start: 16, n_items: 1); |
555 | g_assert_true (gtk_bitset_equals (set, compare)); |
556 | |
557 | gtk_bitset_unref (self: compare); |
558 | gtk_bitset_unref (self: set); |
559 | } |
560 | |
561 | int |
562 | main (int argc, char *argv[]) |
563 | { |
564 | (g_test_init) (argc: &argc, argv: &argv, NULL); |
565 | setlocale (LC_ALL, locale: "C" ); |
566 | |
567 | g_test_add_func (testpath: "/bitset/is_empty" , test_func: test_is_empty); |
568 | g_test_add_func (testpath: "/bitset/minimum" , test_func: test_minimum); |
569 | g_test_add_func (testpath: "/bitset/maximum" , test_func: test_maximum); |
570 | g_test_add_func (testpath: "/bitset/equals" , test_func: test_equals); |
571 | g_test_add_func (testpath: "/bitset/union" , test_func: test_union); |
572 | g_test_add_func (testpath: "/bitset/intersect" , test_func: test_intersect); |
573 | g_test_add_func (testpath: "/bitset/difference" , test_func: test_difference); |
574 | g_test_add_func (testpath: "/bitset/subtract" , test_func: test_subtract); |
575 | g_test_add_func (testpath: "/bitset/shift-left" , test_func: test_shift_left); |
576 | g_test_add_func (testpath: "/bitset/shift-right" , test_func: test_shift_right); |
577 | g_test_add_func (testpath: "/bitset/slice" , test_func: test_slice); |
578 | g_test_add_func (testpath: "/bitset/rectangle" , test_func: test_rectangle); |
579 | g_test_add_func (testpath: "/bitset/iter" , test_func: test_iter); |
580 | g_test_add_func (testpath: "/bitset/splice-overflow" , test_func: test_splice_overflow); |
581 | |
582 | return g_test_run (); |
583 | } |
584 | |