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)
131 for (; cnt > 1; cnt -= 2, values++)
132 swap (values, &values[cnt - 1]);
135 /* Arranges the CNT elements in VALUES into the lexicographically
136 next greater permutation. Returns true if successful.
137 If VALUES is already the lexicographically greatest
138 permutation of its elements (i.e. ordered from greatest to
139 smallest), arranges them into the lexicographically least
140 permutation (i.e. ordered from smallest to largest) and
143 next_permutation (int *values, size_t cnt)
151 if (values[i] < values[i + 1])
154 for (j = cnt - 1; values[i] >= values[j]; j--)
156 swap (values + i, values + j);
157 reverse (values + (i + 1), cnt - (i + 1));
162 reverse (values, cnt);
170 factorial (unsigned n)
178 /* Returns the number of permutations of the CNT values in
179 VALUES. If VALUES contains duplicates, they must be
182 expected_perms (int *values, size_t cnt)
187 perm_cnt = factorial (cnt);
188 for (i = 0; i < cnt; i = j)
190 for (j = i + 1; j < cnt; j++)
191 if (values[i] != values[j])
193 perm_cnt /= factorial (j - i);
198 /* Tests whether PARTS is a K-part integer composition of N.
199 Returns true if so, false otherwise. */
201 is_k_composition (int n, int k, const int parts[])
207 for (i = 0; i < k; i++)
209 if (parts[i] < 1 || parts[i] > n)
216 /* Advances the K-part integer composition of N stored in PARTS
217 to the next lexicographically greater one.
218 Returns true if successful, false if the composition was
219 already the greatest K-part composition of N (in which case
220 PARTS is unaltered). */
222 next_k_composition (int n UNUSED, int k, int parts[])
226 assert (is_k_composition (n, k, parts));
230 for (i = k - 1; i > 0; i--)
241 assert (is_k_composition (n, k, parts));
245 /* Advances *K and PARTS to the next integer composition of N.
246 Compositions are ordered from shortest to longest and in
247 lexicographical order within a given length.
248 Before the first call, initialize *K to 0.
249 After each successful call, *K contains the length of the
250 current composition and the *K elements in PARTS contain its
252 Returns true if successful, false if the set of compositions
253 has been exhausted. */
255 next_composition (int n, int *k, int parts[])
257 if (*k >= 1 && next_k_composition (n, *k, parts))
262 for (i = 0; i < *k; i++)
272 /* Inserts sequences without duplicates into a heap, and then
273 ensures that they appear as the minimum element in the correct
274 order as we delete them. Exhaustively tests every input
275 permutation up to 'max_elems' elements. */
277 test_insert_no_dups_delete_min (void)
279 const int max_elems = 8;
282 for (cnt = 0; cnt <= max_elems; cnt++)
285 struct element *elements;
287 unsigned int permutation_cnt;
290 values = xnmalloc (cnt, sizeof *values);
291 elements = xnmalloc (cnt, sizeof *elements);
292 for (i = 0; i < cnt; i++)
295 h = heap_create (compare_elements, &aux_data);
297 while (permutation_cnt == 0 || next_permutation (values, cnt))
301 for (i = 0; i < cnt; i++)
302 elements[i].x = values[i];
304 check (heap_is_empty (h));
305 for (i = 0; i < cnt; i++)
307 heap_insert (h, &elements[i].node);
308 check (heap_node_to_element (heap_minimum (h))->x
309 == min_int (values, i + 1));
310 check (heap_count (h) == i + 1);
313 for (i = 0; i < cnt; i++)
315 check (heap_node_to_element (heap_minimum (h))->x == i);
316 heap_delete (h, heap_minimum (h));
318 check (heap_is_empty (h));
321 check (permutation_cnt == factorial (cnt));
328 /* Inserts sequences with duplicates into a heap, and then
329 ensures that they appear as the minimum element in the correct
330 order as we delete them. Exhaustively tests every input
331 permutation up to 'max_elems' elements.
333 See Usenet article <87mz4utika.fsf@blp.benpfaff.org> for
334 details of the algorithm used here. */
336 test_insert_with_dups_delete_min (void)
338 const int max_elems = 7;
341 for (cnt = 1; cnt <= max_elems; cnt++)
343 unsigned int composition_cnt;
348 struct element *elements;
351 dups = xnmalloc (cnt, sizeof *dups);
352 values = xnmalloc (cnt, sizeof *values);
353 sorted_values = xnmalloc (cnt, sizeof *sorted_values);
354 elements = xnmalloc (cnt, sizeof *elements);
358 while (next_composition (cnt, &unique_cnt, dups))
362 unsigned int permutation_cnt;
365 for (i = 0; i < unique_cnt; i++)
366 for (j = 0; j < dups[i]; j++)
369 sorted_values[k] = i;
374 h = heap_create (compare_elements, &aux_data);
376 while (permutation_cnt == 0 || next_permutation (values, cnt))
380 for (i = 0; i < cnt; i++)
381 elements[i].x = values[i];
384 check (heap_is_empty (h));
385 for (i = 0; i < cnt; i++)
387 heap_insert (h, &elements[i].node);
390 check (heap_node_to_element (heap_minimum (h))->x == min);
391 check (heap_count (h) == i + 1);
394 for (i = 0; i < cnt; i++)
396 struct element *min = heap_node_to_element (heap_minimum (h));
397 check (min->x == sorted_values[i]);
398 heap_delete (h, heap_minimum (h));
400 check (heap_is_empty (h));
403 check (permutation_cnt == expected_perms (values, cnt));
408 check (composition_cnt == 1 << (cnt - 1));
412 free (sorted_values);
417 /* Inserts a sequence without duplicates into a heap, then
418 deletes them in a different order. */
420 test_insert_no_dups_delete_random (void)
422 const int max_elems = 5;
425 for (cnt = 0; cnt <= max_elems; cnt++)
428 struct element *elements;
429 int *insert, *delete;
430 unsigned int insert_perm_cnt;
433 insert = xnmalloc (cnt, sizeof *insert);
434 delete = xnmalloc (cnt, sizeof *delete);
435 elements = xnmalloc (cnt, sizeof *elements);
436 for (i = 0; i < cnt; i++)
443 h = heap_create (compare_elements, &aux_data);
445 while (insert_perm_cnt == 0 || next_permutation (insert, cnt))
447 unsigned int delete_perm_cnt = 0;
449 while (delete_perm_cnt == 0 || next_permutation (delete, cnt))
454 check (heap_is_empty (h));
456 for (i = 0; i < cnt; i++)
458 heap_insert (h, &elements[insert[i]].node);
461 check (heap_node_to_element (heap_minimum (h))->x == min);
462 check (heap_count (h) == i + 1);
465 for (i = 0; i < cnt; i++)
467 int new_min = min_int (delete + i + 1, cnt - i - 1);
468 heap_delete (h, &elements[delete[i]].node);
469 check (heap_count (h) == cnt - i - 1);
470 if (!heap_is_empty (h))
471 check (heap_node_to_element (heap_minimum (h))->x == new_min);
473 check (heap_is_empty (h));
476 check (delete_perm_cnt == factorial (cnt));
479 check (insert_perm_cnt == factorial (cnt));
487 /* Inserts a set of values into a heap, then changes them to a
488 different random set of values, then removes them in sorted
493 const int max_elems = 8;
496 for (cnt = 0; cnt <= max_elems; cnt++)
499 struct element *elements;
500 int *insert, *delete;
501 unsigned int insert_perm_cnt;
504 insert = xnmalloc (cnt, sizeof *insert);
505 delete = xnmalloc (cnt, sizeof *delete);
506 elements = xnmalloc (cnt, sizeof *elements);
507 for (i = 0; i < cnt; i++)
510 h = heap_create (compare_elements, &aux_data);
512 while (insert_perm_cnt == 0 || next_permutation (insert, cnt))
514 for (i = 0; i < cnt; i++)
515 elements[i].x = insert[i];
517 check (heap_is_empty (h));
518 for (i = 0; i < cnt; i++)
520 int new_min = min_int (insert, i + 1);
521 heap_insert (h, &elements[i].node);
522 check (heap_node_to_element (heap_minimum (h))->x == new_min);
523 check (heap_count (h) == i + 1);
526 for (i = 0; i < cnt; i++)
527 delete[i] = insert[i];
528 for (i = 0; i < cnt; i++)
530 int old_value, old_min, new_min;
531 old_min = min_int (delete, cnt);
532 old_value = delete[i];
533 elements[i].x = delete[i] = rand () % (cnt + 2) - 1;
534 new_min = min_int (delete, cnt);
535 heap_changed (h, &elements[i].node);
536 check (heap_node_to_element (heap_minimum (h))->x
537 == min_int (delete, cnt));
540 for (i = 0; i < cnt; i++)
542 int new_min = min_int (delete + i + 1, cnt - i - 1);
543 heap_delete (h, &elements[i].node);
544 check (heap_count (h) == cnt - i - 1);
545 if (!heap_is_empty (h))
546 check (heap_node_to_element (heap_minimum (h))->x == new_min);
548 check (heap_is_empty (h));
551 check (insert_perm_cnt == factorial (cnt));
559 /* Performs a random sequence of insertions and deletions in a
562 test_random_insert_delete (void)
564 const int max_elems = 64;
565 const int num_actions = 250000;
568 struct element *elements;
573 values = xnmalloc (max_elems, sizeof *values);
574 elements = xnmalloc (max_elems, sizeof *elements);
578 h = heap_create (compare_elements, &aux_data);
579 for (i = 0; i < num_actions; i++)
581 enum { INSERT, DELETE } action;
586 if (insert_chance < 9)
589 else if (cnt == max_elems)
592 if (insert_chance > 0)
596 action = rand () % 10 < insert_chance ? INSERT : DELETE;
598 if (action == INSERT)
603 new_value = rand () % max_elems;
604 values[cnt] = new_value;
605 elements[cnt].x = new_value;
607 heap_insert (h, &elements[cnt].node);
609 old_min = min_int (values, cnt);
613 else if (action == DELETE)
617 int old_min, new_min;
619 old_min = min_int (values, cnt);
621 del_idx = rand () % cnt;
622 del_value = values[del_idx];
623 heap_delete (h, &elements[del_idx].node);
628 values[del_idx] = values[cnt];
629 elements[del_idx] = elements[cnt];
630 heap_moved (h, &elements[del_idx].node);
633 new_min = min_int (values, cnt);
638 check (heap_count (h) == cnt);
639 check (heap_is_empty (h) == (cnt == 0));
641 check (heap_node_to_element (heap_minimum (h))->x
642 == min_int (values, cnt));
651 /* Runs TEST_FUNCTION and prints a message about NAME. */
653 run_test (void (*test_function) (void), const char *name)
664 run_test (test_insert_no_dups_delete_min,
665 "insert (no dups), delete minimum values");
666 run_test (test_insert_with_dups_delete_min,
667 "insert with dups, delete minimum values");
668 run_test (test_insert_no_dups_delete_random,
669 "insert (no dups), delete in random order");
670 run_test (test_inc_dec, "increase and decrease values");
671 run_test (test_random_insert_delete, "random insertions and deletions");