/* PSPP - a program for statistical analysis.
- Copyright (C) 2007 Free Software Foundation, Inc.
+ Copyright (C) 2007, 2010, 2012 Free Software Foundation, Inc.
This program is free software: you can redistribute it and/or modify
it under the terms of the GNU General Public License as published by
#include "xalloc.h"
\f
-/* Currently running test. */
-static const char *test_name;
-
/* Exit with a failure code.
(Place a breakpoint on this function while debugging.) */
static void
{
if (!ok)
{
- printf ("Check failed in %s test at %s, line %d\n",
- test_name, __FILE__, line);
+ fprintf (stderr, "%s:%d: check failed\n", __FILE__, line);
check_die ();
}
}
expected_perms (int *values, size_t cnt)
{
size_t i, j;
- unsigned int perm_cnt;
+ unsigned int n_perms;
- perm_cnt = factorial (cnt);
+ n_perms = factorial (cnt);
for (i = 0; i < cnt; i = j)
{
for (j = i + 1; j < cnt; j++)
if (values[i] != values[j])
break;
- perm_cnt /= factorial (j - i);
+ n_perms /= factorial (j - i);
}
- return perm_cnt;
+ return n_perms;
}
/* Tests whether PARTS is a K-part integer composition of N.
struct heap *h;
struct element *elements;
int *values;
- unsigned int permutation_cnt;
+ unsigned int n_permutations;
int i;
values = xnmalloc (cnt, sizeof *values);
values[i] = i;
h = heap_create (compare_elements, &aux_data);
- permutation_cnt = 0;
- while (permutation_cnt == 0 || next_permutation (values, cnt))
+ n_permutations = 0;
+ while (n_permutations == 0 || next_permutation (values, cnt))
{
int i;
heap_delete (h, heap_minimum (h));
}
check (heap_is_empty (h));
- permutation_cnt++;
+ n_permutations++;
}
- check (permutation_cnt == factorial (cnt));
+ check (n_permutations == factorial (cnt));
heap_destroy (h);
free (values);
free (elements);
for (cnt = 1; cnt <= max_elems; cnt++)
{
- unsigned int composition_cnt;
+ unsigned int n_compositions;
int *dups;
- int unique_cnt;
+ int n_uniques;
int *values;
int *sorted_values;
struct element *elements;
sorted_values = xnmalloc (cnt, sizeof *sorted_values);
elements = xnmalloc (cnt, sizeof *elements);
- unique_cnt = 0;
- composition_cnt = 0;
- while (next_composition (cnt, &unique_cnt, dups))
+ n_uniques = 0;
+ n_compositions = 0;
+ while (next_composition (cnt, &n_uniques, dups))
{
struct heap *h;
int i, j, k;
- unsigned int permutation_cnt;
+ unsigned int n_permutations;
k = 0;
- for (i = 0; i < unique_cnt; i++)
+ for (i = 0; i < n_uniques; i++)
for (j = 0; j < dups[i]; j++)
{
values[k] = i;
check (k == cnt);
h = heap_create (compare_elements, &aux_data);
- permutation_cnt = 0;
- while (permutation_cnt == 0 || next_permutation (values, cnt))
+ n_permutations = 0;
+ while (n_permutations == 0 || next_permutation (values, cnt))
{
int min = INT_MAX;
heap_delete (h, heap_minimum (h));
}
check (heap_is_empty (h));
- permutation_cnt++;
+ n_permutations++;
}
- check (permutation_cnt == expected_perms (values, cnt));
+ check (n_permutations == expected_perms (values, cnt));
heap_destroy (h);
- composition_cnt++;
+ n_compositions++;
}
- check (composition_cnt == 1 << (cnt - 1));
+ check (n_compositions == 1 << (cnt - 1));
free (dups);
free (values);
struct heap *h;
struct element *elements;
int *insert, *delete;
- unsigned int insert_perm_cnt;
+ unsigned int insert_n_perms;
int i;
insert = xnmalloc (cnt, sizeof *insert);
}
h = heap_create (compare_elements, &aux_data);
- insert_perm_cnt = 0;
- while (insert_perm_cnt == 0 || next_permutation (insert, cnt))
+ insert_n_perms = 0;
+ while (insert_n_perms == 0 || next_permutation (insert, cnt))
{
- unsigned int delete_perm_cnt = 0;
+ unsigned int delete_n_perms = 0;
- while (delete_perm_cnt == 0 || next_permutation (delete, cnt))
+ while (delete_n_perms == 0 || next_permutation (delete, cnt))
{
int min;
int i;
check (heap_node_to_element (heap_minimum (h))->x == new_min);
}
check (heap_is_empty (h));
- delete_perm_cnt++;
+ delete_n_perms++;
}
- check (delete_perm_cnt == factorial (cnt));
- insert_perm_cnt++;
+ check (delete_n_perms == factorial (cnt));
+ insert_n_perms++;
}
- check (insert_perm_cnt == factorial (cnt));
+ check (insert_n_perms == factorial (cnt));
heap_destroy (h);
free (insert);
free (delete);
struct heap *h;
struct element *elements;
int *insert, *delete;
- unsigned int insert_perm_cnt;
+ unsigned int insert_n_perms;
int i;
insert = xnmalloc (cnt, sizeof *insert);
insert[i] = i;
h = heap_create (compare_elements, &aux_data);
- insert_perm_cnt = 0;
- while (insert_perm_cnt == 0 || next_permutation (insert, cnt))
+ insert_n_perms = 0;
+ while (insert_n_perms == 0 || next_permutation (insert, cnt))
{
for (i = 0; i < cnt; i++)
elements[i].x = insert[i];
delete[i] = insert[i];
for (i = 0; i < cnt; i++)
{
- int old_value, old_min, new_min;
- old_min = min_int (delete, cnt);
- old_value = delete[i];
elements[i].x = delete[i] = rand () % (cnt + 2) - 1;
- new_min = min_int (delete, cnt);
heap_changed (h, &elements[i].node);
check (heap_node_to_element (heap_minimum (h))->x
== min_int (delete, cnt));
check (heap_node_to_element (heap_minimum (h))->x == new_min);
}
check (heap_is_empty (h));
- insert_perm_cnt++;
+ insert_n_perms++;
}
- check (insert_perm_cnt == factorial (cnt));
+ check (insert_n_perms == factorial (cnt));
heap_destroy (h);
free (insert);
free (delete);
if (action == INSERT)
{
int new_value;
- int old_min;
new_value = rand () % max_elems;
values[cnt] = new_value;
heap_insert (h, &elements[cnt].node);
- old_min = min_int (values, cnt);
-
cnt++;
}
else if (action == DELETE)
{
int del_idx;
- int del_value;
- int old_min, new_min;
-
- old_min = min_int (values, cnt);
del_idx = rand () % cnt;
- del_value = values[del_idx];
heap_delete (h, &elements[del_idx].node);
cnt--;
elements[del_idx] = elements[cnt];
heap_moved (h, &elements[del_idx].node);
}
-
- new_min = min_int (values, cnt);
}
else
abort ();
\f
/* Main program. */
-/* Runs TEST_FUNCTION and prints a message about NAME. */
-static void
-run_test (void (*test_function) (void), const char *name)
-{
- test_name = name;
- putchar ('.');
- fflush (stdout);
- test_function ();
-}
+struct test
+ {
+ const char *name;
+ const char *description;
+ void (*function) (void);
+ };
+
+static const struct test tests[] =
+ {
+ {
+ "insert-no-dups-delete-min",
+ "insert (no dups), delete minimum values",
+ test_insert_no_dups_delete_min
+ },
+ {
+ "insert-with-dups-delete-min",
+ "insert with dups, delete minimum values",
+ test_insert_with_dups_delete_min
+ },
+ {
+ "insert-no-dups-delete-random",
+ "insert (no dups), delete in random order",
+ test_insert_no_dups_delete_random
+ },
+ {
+ "inc-dec",
+ "increase and decrease values",
+ test_inc_dec
+ },
+ {
+ "random-insert-delete",
+ "random insertions and deletions",
+ test_random_insert_delete
+ }
+ };
+
+enum { N_TESTS = sizeof tests / sizeof *tests };
int
-main (void)
+main (int argc, char *argv[])
{
- run_test (test_insert_no_dups_delete_min,
- "insert (no dups), delete minimum values");
- run_test (test_insert_with_dups_delete_min,
- "insert with dups, delete minimum values");
- run_test (test_insert_no_dups_delete_random,
- "insert (no dups), delete in random order");
- run_test (test_inc_dec, "increase and decrease values");
- run_test (test_random_insert_delete, "random insertions and deletions");
- putchar ('\n');
-
- return 0;
+ int i;
+
+ if (argc != 2)
+ {
+ fprintf (stderr, "exactly one argument required; use --help for help\n");
+ return EXIT_FAILURE;
+ }
+ else if (!strcmp (argv[1], "--help"))
+ {
+ printf ("%s: test heap library\n"
+ "usage: %s TEST-NAME\n"
+ "where TEST-NAME is one of the following:\n",
+ argv[0], argv[0]);
+ for (i = 0; i < N_TESTS; i++)
+ printf (" %s\n %s\n", tests[i].name, tests[i].description);
+ return 0;
+ }
+ else
+ {
+ for (i = 0; i < N_TESTS; i++)
+ if (!strcmp (argv[1], tests[i].name))
+ {
+ tests[i].function ();
+ return 0;
+ }
+
+ fprintf (stderr, "unknown test %s; use --help for help\n", argv[1]);
+ return EXIT_FAILURE;
+ }
}