1 /* PSPP - computes sample statistics.
2 Copyright (C) 2007 Free Software Foundation, Inc.
4 This program is free software; you can redistribute it and/or
5 modify it under the terms of the GNU General Public License as
6 published by the Free Software Foundation; either version 2 of the
7 License, or (at your option) any later version.
9 This program is distributed in the hope that it will be useful, but
10 WITHOUT ANY WARRANTY; without even the implied warranty of
11 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
12 General Public License for more details.
14 You should have received a copy of the GNU General Public License
15 along with this program; if not, write to the Free Software
16 Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA
19 /* This is a test program for the routines defined in tower.c.
20 This test program aims to be as comprehensive as possible.
21 With -DNDEBUG, "gcov -b" should report 100% coverage of lines
22 and branches in tower.c routines. (Without -DNDEBUG, branches
23 caused by failed assertions will not be taken.) "valgrind
24 --leak-check=yes --show-reachable=yes" should give a clean
25 report, both with and without -DNDEBUG. */
31 #include <libpspp/tower.h>
39 #include <libpspp/compiler.h>
43 /* Currently running test. */
44 static const char *test_name;
46 /* Exit with a failure code.
47 (Place a breakpoint on this function while debugging.) */
54 /* If OK is not true, prints a message about failure on the
55 current source file and the given LINE and terminates. */
57 check_func (bool ok, int line)
61 printf ("Check failed in %s test at %s, line %d\n",
62 test_name, __FILE__, line);
67 /* Verifies that EXPR evaluates to true.
68 If not, prints a message citing the calling line number and
70 #define check(EXPR) check_func ((EXPR), __LINE__)
72 /* Node type and support routines. */
74 /* Test data block. */
77 struct tower_node node; /* Embedded tower block. */
78 int x; /* Primary value. */
81 /* Returns the `struct block' that NODE is embedded within. */
83 tower_node_to_block (const struct tower_node *node)
85 return tower_data (node, struct block, node);
88 /* Swaps *A and *B. */
97 /* Reverses the order of the CNT integers starting at VALUES. */
99 reverse (int *values, size_t cnt)
105 swap (&values[i++], &values[--j]);
108 /* Arranges the CNT blocks in VALUES into the lexicographically
109 next greater permutation. Returns true if successful.
110 If VALUES is already the lexicographically greatest
111 permutation of its blocks (i.e. ordered from greatest to
112 smallest), arranges them into the lexicographically least
113 permutation (i.e. ordered from smallest to largest) and
116 next_permutation (int *values, size_t cnt)
124 if (values[i] < values[i + 1])
127 for (j = cnt - 1; values[i] >= values[j]; j--)
129 swap (values + i, values + j);
130 reverse (values + (i + 1), cnt - (i + 1));
135 reverse (values, cnt);
143 factorial (unsigned int n)
145 unsigned int value = 1;
146 /* Disallow N values that overflow on 32-bit machines. */
153 /* Returns C(n, k), the number of ways that K choices can be made
154 from N items when order is unimportant. */
156 binomial_cofficient (unsigned int n, unsigned int k)
159 return factorial (n) / factorial (k) / factorial (n - k);
162 /* Tests whether PARTS is a K-part integer composition of N.
163 Returns true if so, false otherwise. */
165 is_k_composition (int n, int k, const int parts[])
171 for (i = 0; i < k; i++)
173 if (parts[i] < 1 || parts[i] > n)
180 /* Advances the K-part integer composition of N stored in PARTS
181 to the next lexicographically greater one.
182 Returns true if successful, false if the composition was
183 already the greatest K-part composition of N (in which case
184 PARTS is unaltered). */
186 next_k_composition (int n UNUSED, int k, int parts[])
190 assert (is_k_composition (n, k, parts));
194 for (i = k - 1; i > 0; i--)
205 assert (is_k_composition (n, k, parts));
209 /* Sets the K integers in PARTS to the lexicographically first
210 K-part composition of N. */
212 first_k_composition (int n, int k, int parts[])
218 for (i = 0; i < k; i++)
220 parts[k - 1] += n - k;
223 /* Advances *K and PARTS to the next integer composition of N.
224 Compositions are ordered from shortest to longest and in
225 lexicographical order within a given length.
226 Before the first call, initialize *K to 0.
227 After each successful call, *K contains the length of the
228 current composition and the *K blocks in PARTS contain its
230 Returns true if successful, false if the set of compositions
231 has been exhausted. */
233 next_composition (int n, int *k, int parts[])
235 if (*k >= 1 && next_k_composition (n, *k, parts))
239 first_k_composition (n, ++*k, parts);
246 /* A block expected to be found in a tower. */
247 struct expected_block
249 int height; /* Expected height of bottom of block. */
250 int x; /* Expected value for `x' member. */
253 /* Checks that tower T contains the BLOCK_CNT blocks described by
256 check_tower (struct tower *t,
257 struct expected_block blocks[], size_t block_cnt)
260 struct tower_node *node;
263 check (tower_is_empty (t) == (block_cnt == 0));
266 for (i = 0; i < block_cnt; i++)
268 unsigned long int level;
269 for (level = total_height;
270 level < total_height + blocks[i].height;
273 struct tower_node *found;
274 unsigned long int block_start;
275 found = tower_lookup (t, level, &block_start);
276 check (found != NULL);
277 check (tower_node_to_block (found)->x == blocks[i].x);
278 check (block_start == total_height);
280 total_height += blocks[i].height;
282 check (tower_height (t) == total_height);
284 for (node = tower_first (t), i = 0;
286 node = tower_next (t, node), i++)
288 check (tower_node_get_height (node) == blocks[i].height);
289 check (tower_node_to_block (node)->x == blocks[i].x);
291 check (i == block_cnt);
294 /* Tests inserting all possible sets of block heights into a
295 tower in all possible orders, up to a specified maximum tower
300 const int max_height = 7;
303 for (cnt = 1; cnt <= max_height; cnt++)
305 unsigned int composition_cnt;
306 struct expected_block *expected;
310 struct block *blocks;
312 expected = xnmalloc (cnt, sizeof *expected);
313 heights = xnmalloc (cnt, sizeof *heights);
314 order = xnmalloc (cnt, sizeof *order);
315 blocks = xnmalloc (cnt, sizeof *blocks);
319 while (next_composition (cnt, &block_cnt, heights))
322 unsigned int permutation_cnt;
324 for (i = 0; i < block_cnt; i++)
328 while (permutation_cnt == 0 || next_permutation (order, block_cnt))
332 /* Inserts the block_cnt blocks with the given
333 heights[] into T in the order given by order[]. */
335 for (i = 0; i < block_cnt; i++)
344 for (j = 0; j < i; j++)
346 && (under == NULL || under->x > order[j]))
347 under = &blocks[order[j]];
349 tower_insert (&t, heights[idx], &blocks[idx].node,
350 under != NULL ? &under->node : NULL);
353 /* Check that the result is what we expect. */
354 for (i = 0; i < block_cnt; i++)
356 expected[i].height = heights[i];
359 check_tower (&t, expected, block_cnt);
363 check (permutation_cnt == factorial (block_cnt));
367 check (composition_cnt == 1 << (cnt - 1));
376 /* Tests deleting blocks from towers that initially contain all
377 possible sets of block heights into a tower in all possible
378 orders, up to a specified maximum tower height. */
382 const int max_height = 7;
385 for (cnt = 1; cnt <= max_height; cnt++)
387 unsigned int composition_cnt;
388 struct expected_block *expected;
392 struct block *blocks;
394 expected = xnmalloc (cnt, sizeof *expected);
395 heights = xnmalloc (cnt, sizeof *heights);
396 order = xnmalloc (cnt, sizeof *order);
397 blocks = xnmalloc (cnt, sizeof *blocks);
401 while (next_composition (cnt, &block_cnt, heights))
404 unsigned int permutation_cnt;
406 for (i = 0; i < block_cnt; i++)
410 while (permutation_cnt == 0 || next_permutation (order, block_cnt))
414 /* Insert blocks into tower in ascending order. */
416 for (i = 0; i < block_cnt; i++)
419 tower_insert (&t, heights[i], &blocks[i].node, NULL);
421 expected[i].height = heights[i];
423 check_tower (&t, expected, block_cnt);
425 /* Delete blocks from tower in the order of
427 for (i = 0; i < block_cnt; i++)
431 tower_delete (&t, &blocks[idx].node);
434 assert (j < block_cnt - i);
435 if (expected[j].x == idx)
437 memcpy (&expected[j], &expected[j + 1],
438 sizeof *expected * (block_cnt - i - j - 1));
442 check_tower (&t, expected, block_cnt - i - 1);
447 check (permutation_cnt == factorial (block_cnt));
451 check (composition_cnt == 1 << (cnt - 1));
460 /* Tests towers containing all possible block heights, resizing
461 the blocks to all possible heights that conserve the total
462 tower height, up to a maximum total tower height. */
466 const int max_height = 9;
469 for (cnt = 1; cnt <= max_height; cnt++)
471 unsigned int composition_cnt;
472 struct expected_block *expected;
473 int *heights, *new_heights;
476 struct block *blocks;
478 expected = xnmalloc (cnt, sizeof *expected);
479 heights = xnmalloc (cnt, sizeof *heights);
480 new_heights = xnmalloc (cnt, sizeof *new_heights);
481 order = xnmalloc (cnt, sizeof *order);
482 blocks = xnmalloc (cnt, sizeof *blocks);
486 while (next_composition (cnt, &block_cnt, heights))
489 unsigned int resizes = 0;
491 for (resizes = 0, first_k_composition (cnt, block_cnt, new_heights);
493 || next_k_composition (cnt, block_cnt, new_heights));
498 /* Insert blocks into tower in ascending order. */
500 for (i = 0; i < block_cnt; i++)
503 tower_insert (&t, heights[i], &blocks[i].node, NULL);
505 expected[i].height = heights[i];
507 check_tower (&t, expected, block_cnt);
509 /* Resize all the blocks. */
510 for (i = 0; i < block_cnt; i++)
512 if (expected[i].height != new_heights[i] || rand () % 2)
513 tower_resize (&t, &blocks[i].node, new_heights[i]);
514 expected[i].height = new_heights[i];
516 check_tower (&t, expected, block_cnt);
518 check (resizes == binomial_cofficient (cnt - 1, block_cnt - 1));
522 check (composition_cnt == 1 << (cnt - 1));
532 /* Tests splicing all possible contiguous sets of blocks out of one
533 tower into a second, initially empty tower. */
535 test_splice_out (void)
537 const int max_height = 9;
540 for (cnt = 1; cnt <= max_height; cnt++)
542 unsigned int composition_cnt;
543 struct expected_block *expected;
544 int *heights, *new_heights;
547 struct block *blocks;
549 expected = xnmalloc (cnt, sizeof *expected);
550 heights = xnmalloc (cnt, sizeof *heights);
551 new_heights = xnmalloc (cnt, sizeof *new_heights);
552 order = xnmalloc (cnt, sizeof *order);
553 blocks = xnmalloc (cnt, sizeof *blocks);
557 while (next_composition (cnt, &block_cnt, heights))
561 for (i = 0; i < block_cnt; i++)
562 for (j = i; j <= block_cnt; j++)
564 struct tower src, dst;
570 /* Insert blocks into SRC and DST in ascending order. */
571 for (k = 0; k < block_cnt; k++)
574 tower_insert (&src, heights[k], &blocks[k].node, NULL);
576 expected[k].height = heights[k];
578 check_tower (&src, expected, block_cnt);
580 /* Splice blocks I...J into DST. */
581 tower_splice (&dst, NULL, &src, &blocks[i].node,
582 j < block_cnt ? &blocks[j].node : NULL);
583 check_tower (&dst, &expected[i], j - i);
584 memmove (&expected[i], &expected[j],
585 sizeof *expected * (block_cnt - j));
586 check_tower (&src, expected, block_cnt - (j - i));
590 check (composition_cnt == 1 << (cnt - 1));
600 /* Tests splicing all of the contents of a tower into all
601 possible positions in a second tower. */
603 test_splice_in (void)
605 const int max_height = 9;
608 for (cnt = 1; cnt <= max_height; cnt++)
610 unsigned int composition_cnt;
611 struct expected_block *expected;
612 int *heights, *new_heights;
615 struct block *blocks;
617 expected = xnmalloc (cnt, sizeof *expected);
618 heights = xnmalloc (cnt, sizeof *heights);
619 new_heights = xnmalloc (cnt, sizeof *new_heights);
620 order = xnmalloc (cnt, sizeof *order);
621 blocks = xnmalloc (cnt, sizeof *blocks);
625 while (next_composition (cnt, &block_cnt, heights))
629 for (i = 0; i < block_cnt; i++)
630 for (j = i; j <= block_cnt; j++)
632 struct tower src, dst;
638 /* Insert blocks into SRC and DST in ascending order. */
639 for (k = 0; k < block_cnt; k++)
642 tower_insert (k >= i && k < j ? &src : &dst,
643 heights[k], &blocks[k].node, NULL);
645 expected[k].height = heights[k];
648 /* Splice SRC into DST. */
649 tower_splice (&dst, j < block_cnt ? &blocks[j].node : NULL,
650 &src, i != j ? &blocks[i].node : NULL, NULL);
651 check_tower (&dst, expected, block_cnt);
655 check (composition_cnt == 1 << (cnt - 1));
668 /* Runs TEST_FUNCTION and prints a message about NAME. */
670 run_test (void (*test_function) (void), const char *name)
681 run_test (test_insert, "insert");
682 run_test (test_delete, "delete");
683 run_test (test_resize, "resize");
684 run_test (test_splice_out, "splice out");
685 run_test (test_splice_in, "splice in");