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>
40 #include <libpspp/compiler.h>
44 /* Currently running test. */
45 static const char *test_name;
47 /* Exit with a failure code.
48 (Place a breakpoint on this function while debugging.) */
55 /* If OK is not true, prints a message about failure on the
56 current source file and the given LINE and terminates. */
58 check_func (bool ok, int line)
62 printf ("Check failed in %s test at %s, line %d\n",
63 test_name, __FILE__, line);
68 /* Verifies that EXPR evaluates to true.
69 If not, prints a message citing the calling line number and
71 #define check(EXPR) check_func ((EXPR), __LINE__)
73 /* Node type and support routines. */
75 /* Test data block. */
78 struct tower_node node; /* Embedded tower block. */
79 int x; /* Primary value. */
82 /* Returns the `struct block' that NODE is embedded within. */
84 tower_node_to_block (const struct tower_node *node)
86 return tower_data (node, struct block, node);
89 /* Swaps *A and *B. */
98 /* Reverses the order of the CNT integers starting at VALUES. */
100 reverse (int *values, size_t cnt)
106 swap (&values[i++], &values[--j]);
109 /* Arranges the CNT blocks in VALUES into the lexicographically
110 next greater permutation. Returns true if successful.
111 If VALUES is already the lexicographically greatest
112 permutation of its blocks (i.e. ordered from greatest to
113 smallest), arranges them into the lexicographically least
114 permutation (i.e. ordered from smallest to largest) and
117 next_permutation (int *values, size_t cnt)
125 if (values[i] < values[i + 1])
128 for (j = cnt - 1; values[i] >= values[j]; j--)
130 swap (values + i, values + j);
131 reverse (values + (i + 1), cnt - (i + 1));
136 reverse (values, cnt);
144 factorial (unsigned int n)
146 unsigned int value = 1;
147 /* Disallow N values that overflow on 32-bit machines. */
154 /* Returns C(n, k), the number of ways that K choices can be made
155 from N items when order is unimportant. */
157 binomial_cofficient (unsigned int n, unsigned int k)
160 return factorial (n) / factorial (k) / factorial (n - k);
163 /* Tests whether PARTS is a K-part integer composition of N.
164 Returns true if so, false otherwise. */
166 is_k_composition (int n, int k, const int parts[])
172 for (i = 0; i < k; i++)
174 if (parts[i] < 1 || parts[i] > n)
181 /* Advances the K-part integer composition of N stored in PARTS
182 to the next lexicographically greater one.
183 Returns true if successful, false if the composition was
184 already the greatest K-part composition of N (in which case
185 PARTS is unaltered). */
187 next_k_composition (int n UNUSED, int k, int parts[])
191 assert (is_k_composition (n, k, parts));
195 for (i = k - 1; i > 0; i--)
206 assert (is_k_composition (n, k, parts));
210 /* Sets the K integers in PARTS to the lexicographically first
211 K-part composition of N. */
213 first_k_composition (int n, int k, int parts[])
219 for (i = 0; i < k; i++)
221 parts[k - 1] += n - k;
224 /* Advances *K and PARTS to the next integer composition of N.
225 Compositions are ordered from shortest to longest and in
226 lexicographical order within a given length.
227 Before the first call, initialize *K to 0.
228 After each successful call, *K contains the length of the
229 current composition and the *K blocks in PARTS contain its
231 Returns true if successful, false if the set of compositions
232 has been exhausted. */
234 next_composition (int n, int *k, int parts[])
236 if (*k >= 1 && next_k_composition (n, *k, parts))
240 first_k_composition (n, ++*k, parts);
247 /* A block expected to be found in a tower. */
248 struct expected_block
250 int height; /* Expected height of bottom of block. */
251 int x; /* Expected value for `x' member. */
254 /* Checks that tower T contains the BLOCK_CNT blocks described by
257 check_tower (struct tower *t,
258 struct expected_block blocks[], size_t block_cnt)
261 struct tower_node *node;
264 check (tower_is_empty (t) == (block_cnt == 0));
267 for (i = 0; i < block_cnt; i++)
269 unsigned long int level;
270 for (level = total_height;
271 level < total_height + blocks[i].height;
274 struct tower_node *found;
275 unsigned long int block_start;
276 found = tower_lookup (t, level, &block_start);
277 check (found != NULL);
278 check (tower_node_to_block (found)->x == blocks[i].x);
279 check (block_start == total_height);
281 total_height += blocks[i].height;
283 check (tower_height (t) == total_height);
285 for (node = tower_first (t), i = 0;
287 node = tower_next (t, node), i++)
289 check (tower_node_get_height (node) == blocks[i].height);
290 check (tower_node_to_block (node)->x == blocks[i].x);
292 check (i == block_cnt);
294 for (node = tower_last (t), i = block_cnt - 1;
296 node = tower_prev (t, node), i--)
298 check (tower_node_get_height (node) == blocks[i].height);
299 check (tower_node_to_block (node)->x == blocks[i].x);
301 check (i == SIZE_MAX);
304 /* Tests inserting all possible sets of block heights into a
305 tower in all possible orders, up to a specified maximum tower
310 const int max_height = 7;
313 for (cnt = 1; cnt <= max_height; cnt++)
315 unsigned int composition_cnt;
316 struct expected_block *expected;
320 struct block *blocks;
322 expected = xnmalloc (cnt, sizeof *expected);
323 heights = xnmalloc (cnt, sizeof *heights);
324 order = xnmalloc (cnt, sizeof *order);
325 blocks = xnmalloc (cnt, sizeof *blocks);
329 while (next_composition (cnt, &block_cnt, heights))
332 unsigned int permutation_cnt;
334 for (i = 0; i < block_cnt; i++)
338 while (permutation_cnt == 0 || next_permutation (order, block_cnt))
342 /* Inserts the block_cnt blocks with the given
343 heights[] into T in the order given by order[]. */
345 for (i = 0; i < block_cnt; i++)
354 for (j = 0; j < i; j++)
356 && (under == NULL || under->x > order[j]))
357 under = &blocks[order[j]];
359 tower_insert (&t, heights[idx], &blocks[idx].node,
360 under != NULL ? &under->node : NULL);
363 /* Check that the result is what we expect. */
364 for (i = 0; i < block_cnt; i++)
366 expected[i].height = heights[i];
369 check_tower (&t, expected, block_cnt);
373 check (permutation_cnt == factorial (block_cnt));
377 check (composition_cnt == 1 << (cnt - 1));
386 /* Tests deleting blocks from towers that initially contain all
387 possible sets of block heights into a tower in all possible
388 orders, up to a specified maximum tower height. */
392 const int max_height = 7;
395 for (cnt = 1; cnt <= max_height; cnt++)
397 unsigned int composition_cnt;
398 struct expected_block *expected;
402 struct block *blocks;
404 expected = xnmalloc (cnt, sizeof *expected);
405 heights = xnmalloc (cnt, sizeof *heights);
406 order = xnmalloc (cnt, sizeof *order);
407 blocks = xnmalloc (cnt, sizeof *blocks);
411 while (next_composition (cnt, &block_cnt, heights))
414 unsigned int permutation_cnt;
416 for (i = 0; i < block_cnt; i++)
420 while (permutation_cnt == 0 || next_permutation (order, block_cnt))
424 /* Insert blocks into tower in ascending order. */
426 for (i = 0; i < block_cnt; i++)
429 tower_insert (&t, heights[i], &blocks[i].node, NULL);
431 expected[i].height = heights[i];
433 check_tower (&t, expected, block_cnt);
435 /* Delete blocks from tower in the order of
437 for (i = 0; i < block_cnt; i++)
441 tower_delete (&t, &blocks[idx].node);
444 assert (j < block_cnt - i);
445 if (expected[j].x == idx)
447 memcpy (&expected[j], &expected[j + 1],
448 sizeof *expected * (block_cnt - i - j - 1));
452 check_tower (&t, expected, block_cnt - i - 1);
457 check (permutation_cnt == factorial (block_cnt));
461 check (composition_cnt == 1 << (cnt - 1));
470 /* Tests towers containing all possible block heights, resizing
471 the blocks to all possible heights that conserve the total
472 tower height, up to a maximum total tower height. */
476 const int max_height = 9;
479 for (cnt = 1; cnt <= max_height; cnt++)
481 unsigned int composition_cnt;
482 struct expected_block *expected;
483 int *heights, *new_heights;
486 struct block *blocks;
488 expected = xnmalloc (cnt, sizeof *expected);
489 heights = xnmalloc (cnt, sizeof *heights);
490 new_heights = xnmalloc (cnt, sizeof *new_heights);
491 order = xnmalloc (cnt, sizeof *order);
492 blocks = xnmalloc (cnt, sizeof *blocks);
496 while (next_composition (cnt, &block_cnt, heights))
499 unsigned int resizes = 0;
501 for (resizes = 0, first_k_composition (cnt, block_cnt, new_heights);
503 || next_k_composition (cnt, block_cnt, new_heights));
508 /* Insert blocks into tower in ascending order. */
510 for (i = 0; i < block_cnt; i++)
513 tower_insert (&t, heights[i], &blocks[i].node, NULL);
515 expected[i].height = heights[i];
517 check_tower (&t, expected, block_cnt);
519 /* Resize all the blocks. */
520 for (i = 0; i < block_cnt; i++)
522 if (expected[i].height != new_heights[i] || rand () % 2)
523 tower_resize (&t, &blocks[i].node, new_heights[i]);
524 expected[i].height = new_heights[i];
526 check_tower (&t, expected, block_cnt);
528 check (resizes == binomial_cofficient (cnt - 1, block_cnt - 1));
532 check (composition_cnt == 1 << (cnt - 1));
542 /* Tests splicing all possible contiguous sets of blocks out of one
543 tower into a second, initially empty tower. */
545 test_splice_out (void)
547 const int max_height = 9;
550 for (cnt = 1; cnt <= max_height; cnt++)
552 unsigned int composition_cnt;
553 struct expected_block *expected;
554 int *heights, *new_heights;
557 struct block *blocks;
559 expected = xnmalloc (cnt, sizeof *expected);
560 heights = xnmalloc (cnt, sizeof *heights);
561 new_heights = xnmalloc (cnt, sizeof *new_heights);
562 order = xnmalloc (cnt, sizeof *order);
563 blocks = xnmalloc (cnt, sizeof *blocks);
567 while (next_composition (cnt, &block_cnt, heights))
571 for (i = 0; i < block_cnt; i++)
572 for (j = i; j <= block_cnt; j++)
574 struct tower src, dst;
580 /* Insert blocks into SRC and DST in ascending order. */
581 for (k = 0; k < block_cnt; k++)
584 tower_insert (&src, heights[k], &blocks[k].node, NULL);
586 expected[k].height = heights[k];
588 check_tower (&src, expected, block_cnt);
590 /* Splice blocks I...J into DST. */
591 tower_splice (&dst, NULL, &src, &blocks[i].node,
592 j < block_cnt ? &blocks[j].node : NULL);
593 check_tower (&dst, &expected[i], j - i);
594 memmove (&expected[i], &expected[j],
595 sizeof *expected * (block_cnt - j));
596 check_tower (&src, expected, block_cnt - (j - i));
600 check (composition_cnt == 1 << (cnt - 1));
610 /* Tests splicing all of the contents of a tower into all
611 possible positions in a second tower. */
613 test_splice_in (void)
615 const int max_height = 9;
618 for (cnt = 1; cnt <= max_height; cnt++)
620 unsigned int composition_cnt;
621 struct expected_block *expected;
622 int *heights, *new_heights;
625 struct block *blocks;
627 expected = xnmalloc (cnt, sizeof *expected);
628 heights = xnmalloc (cnt, sizeof *heights);
629 new_heights = xnmalloc (cnt, sizeof *new_heights);
630 order = xnmalloc (cnt, sizeof *order);
631 blocks = xnmalloc (cnt, sizeof *blocks);
635 while (next_composition (cnt, &block_cnt, heights))
639 for (i = 0; i < block_cnt; i++)
640 for (j = i; j <= block_cnt; j++)
642 struct tower src, dst;
648 /* Insert blocks into SRC and DST in ascending order. */
649 for (k = 0; k < block_cnt; k++)
652 tower_insert (k >= i && k < j ? &src : &dst,
653 heights[k], &blocks[k].node, NULL);
655 expected[k].height = heights[k];
658 /* Splice SRC into DST. */
659 tower_splice (&dst, j < block_cnt ? &blocks[j].node : NULL,
660 &src, i != j ? &blocks[i].node : NULL, NULL);
661 check_tower (&dst, expected, block_cnt);
665 check (composition_cnt == 1 << (cnt - 1));
678 /* Runs TEST_FUNCTION and prints a message about NAME. */
680 run_test (void (*test_function) (void), const char *name)
691 run_test (test_insert, "insert");
692 run_test (test_delete, "delete");
693 run_test (test_resize, "resize");
694 run_test (test_splice_out, "splice out");
695 run_test (test_splice_in, "splice in");