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 heap.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 heap.c routines, except for the is_heap
23 function, which is not called at all with -DNDEBUG. (Without
24 -DNDEBUG, branches caused by failed assertions will also not
25 be taken.) "valgrind --leak-check=yes --show-reachable=yes"
26 should give a clean report, both with and without -DNDEBUG. */
32 #include <libpspp/heap.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 element. */
78 struct heap_node node; /* Embedded heap element. */
79 int x; /* Primary value. */
84 /* Returns the `struct element' that NODE is embedded within. */
85 static struct element *
86 heap_node_to_element (const struct heap_node *node)
88 return heap_data (node, struct element, node);
91 /* Compares the `x' values in A and B and returns a strcmp-type
92 return value. Verifies that AUX points to aux_data. */
94 compare_elements (const struct heap_node *a_, const struct heap_node *b_,
97 const struct element *a = heap_node_to_element (a_);
98 const struct element *b = heap_node_to_element (b_);
100 check (aux == &aux_data);
101 return a->x < b->x ? -1 : a->x > b->x;
104 /* Returns the smallest of the N integers in ARRAY. */
106 min_int (int *array, size_t n)
112 for (i = 0; i < n; i++)
118 /* Swaps *A and *B. */
120 swap (int *a, int *b)
127 /* Reverses the order of the CNT integers starting at VALUES. */
129 reverse (int *values, size_t cnt)
135 swap (&values[i++], &values[--j]);
138 /* Arranges the CNT elements in VALUES into the lexicographically
139 next greater permutation. Returns true if successful.
140 If VALUES is already the lexicographically greatest
141 permutation of its elements (i.e. ordered from greatest to
142 smallest), arranges them into the lexicographically least
143 permutation (i.e. ordered from smallest to largest) and
146 next_permutation (int *values, size_t cnt)
154 if (values[i] < values[i + 1])
157 for (j = cnt - 1; values[i] >= values[j]; j--)
159 swap (values + i, values + j);
160 reverse (values + (i + 1), cnt - (i + 1));
165 reverse (values, cnt);
173 factorial (unsigned int n)
175 unsigned int value = 1;
181 /* Returns the number of permutations of the CNT values in
182 VALUES. If VALUES contains duplicates, they must be
185 expected_perms (int *values, size_t cnt)
188 unsigned int perm_cnt;
190 perm_cnt = factorial (cnt);
191 for (i = 0; i < cnt; i = j)
193 for (j = i + 1; j < cnt; j++)
194 if (values[i] != values[j])
196 perm_cnt /= factorial (j - i);
201 /* Tests whether PARTS is a K-part integer composition of N.
202 Returns true if so, false otherwise. */
204 is_k_composition (int n, int k, const int parts[])
210 for (i = 0; i < k; i++)
212 if (parts[i] < 1 || parts[i] > n)
219 /* Advances the K-part integer composition of N stored in PARTS
220 to the next lexicographically greater one.
221 Returns true if successful, false if the composition was
222 already the greatest K-part composition of N (in which case
223 PARTS is unaltered). */
225 next_k_composition (int n UNUSED, int k, int parts[])
229 assert (is_k_composition (n, k, parts));
233 for (i = k - 1; i > 0; i--)
244 assert (is_k_composition (n, k, parts));
248 /* Advances *K and PARTS to the next integer composition of N.
249 Compositions are ordered from shortest to longest and in
250 lexicographical order within a given length.
251 Before the first call, initialize *K to 0.
252 After each successful call, *K contains the length of the
253 current composition and the *K elements in PARTS contain its
255 Returns true if successful, false if the set of compositions
256 has been exhausted. */
258 next_composition (int n, int *k, int parts[])
260 if (*k >= 1 && next_k_composition (n, *k, parts))
265 for (i = 0; i < *k; i++)
275 /* Inserts sequences without duplicates into a heap, and then
276 ensures that they appear as the minimum element in the correct
277 order as we delete them. Exhaustively tests every input
278 permutation up to 'max_elems' elements. */
280 test_insert_no_dups_delete_min (void)
282 const int max_elems = 8;
285 for (cnt = 0; cnt <= max_elems; cnt++)
288 struct element *elements;
290 unsigned int permutation_cnt;
293 values = xnmalloc (cnt, sizeof *values);
294 elements = xnmalloc (cnt, sizeof *elements);
295 for (i = 0; i < cnt; i++)
298 h = heap_create (compare_elements, &aux_data);
300 while (permutation_cnt == 0 || next_permutation (values, cnt))
304 for (i = 0; i < cnt; i++)
305 elements[i].x = values[i];
307 check (heap_is_empty (h));
308 for (i = 0; i < cnt; i++)
310 heap_insert (h, &elements[i].node);
311 check (heap_node_to_element (heap_minimum (h))->x
312 == min_int (values, i + 1));
313 check (heap_count (h) == i + 1);
316 for (i = 0; i < cnt; i++)
318 check (heap_node_to_element (heap_minimum (h))->x == i);
319 heap_delete (h, heap_minimum (h));
321 check (heap_is_empty (h));
324 check (permutation_cnt == factorial (cnt));
331 /* Inserts sequences with duplicates into a heap, and then
332 ensures that they appear as the minimum element in the correct
333 order as we delete them. Exhaustively tests every input
334 permutation up to 'max_elems' elements.
336 See Usenet article <87mz4utika.fsf@blp.benpfaff.org> for
337 details of the algorithm used here. */
339 test_insert_with_dups_delete_min (void)
341 const int max_elems = 7;
344 for (cnt = 1; cnt <= max_elems; cnt++)
346 unsigned int composition_cnt;
351 struct element *elements;
354 dups = xnmalloc (cnt, sizeof *dups);
355 values = xnmalloc (cnt, sizeof *values);
356 sorted_values = xnmalloc (cnt, sizeof *sorted_values);
357 elements = xnmalloc (cnt, sizeof *elements);
361 while (next_composition (cnt, &unique_cnt, dups))
365 unsigned int permutation_cnt;
368 for (i = 0; i < unique_cnt; i++)
369 for (j = 0; j < dups[i]; j++)
372 sorted_values[k] = i;
377 h = heap_create (compare_elements, &aux_data);
379 while (permutation_cnt == 0 || next_permutation (values, cnt))
383 for (i = 0; i < cnt; i++)
384 elements[i].x = values[i];
387 check (heap_is_empty (h));
388 for (i = 0; i < cnt; i++)
390 heap_insert (h, &elements[i].node);
393 check (heap_node_to_element (heap_minimum (h))->x == min);
394 check (heap_count (h) == i + 1);
397 for (i = 0; i < cnt; i++)
399 struct element *min = heap_node_to_element (heap_minimum (h));
400 check (min->x == sorted_values[i]);
401 heap_delete (h, heap_minimum (h));
403 check (heap_is_empty (h));
406 check (permutation_cnt == expected_perms (values, cnt));
411 check (composition_cnt == 1 << (cnt - 1));
415 free (sorted_values);
420 /* Inserts a sequence without duplicates into a heap, then
421 deletes them in a different order. */
423 test_insert_no_dups_delete_random (void)
425 const int max_elems = 5;
428 for (cnt = 0; cnt <= max_elems; cnt++)
431 struct element *elements;
432 int *insert, *delete;
433 unsigned int insert_perm_cnt;
436 insert = xnmalloc (cnt, sizeof *insert);
437 delete = xnmalloc (cnt, sizeof *delete);
438 elements = xnmalloc (cnt, sizeof *elements);
439 for (i = 0; i < cnt; i++)
446 h = heap_create (compare_elements, &aux_data);
448 while (insert_perm_cnt == 0 || next_permutation (insert, cnt))
450 unsigned int delete_perm_cnt = 0;
452 while (delete_perm_cnt == 0 || next_permutation (delete, cnt))
457 check (heap_is_empty (h));
459 for (i = 0; i < cnt; i++)
461 heap_insert (h, &elements[insert[i]].node);
464 check (heap_node_to_element (heap_minimum (h))->x == min);
465 check (heap_count (h) == i + 1);
468 for (i = 0; i < cnt; i++)
470 int new_min = min_int (delete + i + 1, cnt - i - 1);
471 heap_delete (h, &elements[delete[i]].node);
472 check (heap_count (h) == cnt - i - 1);
473 if (!heap_is_empty (h))
474 check (heap_node_to_element (heap_minimum (h))->x == new_min);
476 check (heap_is_empty (h));
479 check (delete_perm_cnt == factorial (cnt));
482 check (insert_perm_cnt == factorial (cnt));
490 /* Inserts a set of values into a heap, then changes them to a
491 different random set of values, then removes them in sorted
496 const int max_elems = 8;
499 for (cnt = 0; cnt <= max_elems; cnt++)
502 struct element *elements;
503 int *insert, *delete;
504 unsigned int insert_perm_cnt;
507 insert = xnmalloc (cnt, sizeof *insert);
508 delete = xnmalloc (cnt, sizeof *delete);
509 elements = xnmalloc (cnt, sizeof *elements);
510 for (i = 0; i < cnt; i++)
513 h = heap_create (compare_elements, &aux_data);
515 while (insert_perm_cnt == 0 || next_permutation (insert, cnt))
517 for (i = 0; i < cnt; i++)
518 elements[i].x = insert[i];
520 check (heap_is_empty (h));
521 for (i = 0; i < cnt; i++)
523 int new_min = min_int (insert, i + 1);
524 heap_insert (h, &elements[i].node);
525 check (heap_node_to_element (heap_minimum (h))->x == new_min);
526 check (heap_count (h) == i + 1);
529 for (i = 0; i < cnt; i++)
530 delete[i] = insert[i];
531 for (i = 0; i < cnt; i++)
533 int old_value, old_min, new_min;
534 old_min = min_int (delete, cnt);
535 old_value = delete[i];
536 elements[i].x = delete[i] = rand () % (cnt + 2) - 1;
537 new_min = min_int (delete, cnt);
538 heap_changed (h, &elements[i].node);
539 check (heap_node_to_element (heap_minimum (h))->x
540 == min_int (delete, cnt));
543 for (i = 0; i < cnt; i++)
545 int new_min = min_int (delete + i + 1, cnt - i - 1);
546 heap_delete (h, &elements[i].node);
547 check (heap_count (h) == cnt - i - 1);
548 if (!heap_is_empty (h))
549 check (heap_node_to_element (heap_minimum (h))->x == new_min);
551 check (heap_is_empty (h));
554 check (insert_perm_cnt == factorial (cnt));
562 /* Performs a random sequence of insertions and deletions in a
565 test_random_insert_delete (void)
567 const int max_elems = 64;
568 const int num_actions = 250000;
571 struct element *elements;
576 values = xnmalloc (max_elems, sizeof *values);
577 elements = xnmalloc (max_elems, sizeof *elements);
581 h = heap_create (compare_elements, &aux_data);
582 for (i = 0; i < num_actions; i++)
584 enum { INSERT, DELETE } action;
589 if (insert_chance < 9)
592 else if (cnt == max_elems)
595 if (insert_chance > 0)
599 action = rand () % 10 < insert_chance ? INSERT : DELETE;
601 if (action == INSERT)
606 new_value = rand () % max_elems;
607 values[cnt] = new_value;
608 elements[cnt].x = new_value;
610 heap_insert (h, &elements[cnt].node);
612 old_min = min_int (values, cnt);
616 else if (action == DELETE)
620 int old_min, new_min;
622 old_min = min_int (values, cnt);
624 del_idx = rand () % cnt;
625 del_value = values[del_idx];
626 heap_delete (h, &elements[del_idx].node);
631 values[del_idx] = values[cnt];
632 elements[del_idx] = elements[cnt];
633 heap_moved (h, &elements[del_idx].node);
636 new_min = min_int (values, cnt);
641 check (heap_count (h) == cnt);
642 check (heap_is_empty (h) == (cnt == 0));
644 check (heap_node_to_element (heap_minimum (h))->x
645 == min_int (values, cnt));
654 /* Runs TEST_FUNCTION and prints a message about NAME. */
656 run_test (void (*test_function) (void), const char *name)
667 run_test (test_insert_no_dups_delete_min,
668 "insert (no dups), delete minimum values");
669 run_test (test_insert_with_dups_delete_min,
670 "insert with dups, delete minimum values");
671 run_test (test_insert_no_dups_delete_random,
672 "insert (no dups), delete in random order");
673 run_test (test_inc_dec, "increase and decrease values");
674 run_test (test_random_insert_delete, "random insertions and deletions");