/* 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 ();
}
}
*b = t;
}
-/* Reverses the order of the CNT integers starting at VALUES. */
+/* Reverses the order of the N integers starting at VALUES. */
static void
-reverse (int *values, size_t cnt)
+reverse (int *values, size_t n)
{
size_t i = 0;
- size_t j = cnt;
+ size_t j = n;
while (j > i)
swap (&values[i++], &values[--j]);
}
-/* Arranges the CNT elements in VALUES into the lexicographically
+/* Arranges the N elements in VALUES into the lexicographically
next greater permutation. Returns true if successful.
If VALUES is already the lexicographically greatest
permutation of its elements (i.e. ordered from greatest to
permutation (i.e. ordered from smallest to largest) and
returns false. */
static bool
-next_permutation (int *values, size_t cnt)
+next_permutation (int *values, size_t n)
{
- if (cnt > 0)
+ if (n > 0)
{
- size_t i = cnt - 1;
+ size_t i = n - 1;
while (i != 0)
{
i--;
if (values[i] < values[i + 1])
{
size_t j;
- for (j = cnt - 1; values[i] >= values[j]; j--)
+ for (j = n - 1; values[i] >= values[j]; j--)
continue;
swap (values + i, values + j);
- reverse (values + (i + 1), cnt - (i + 1));
+ reverse (values + (i + 1), n - (i + 1));
return true;
}
}
- reverse (values, cnt);
+ reverse (values, n);
}
return false;
return value;
}
-/* Returns the number of permutations of the CNT values in
+/* Returns the number of permutations of the N values in
VALUES. If VALUES contains duplicates, they must be
adjacent. */
static unsigned int
-expected_perms (int *values, size_t cnt)
+expected_perms (int *values, size_t n)
{
size_t i, j;
- unsigned int perm_cnt;
+ unsigned int n_perms;
- perm_cnt = factorial (cnt);
- for (i = 0; i < cnt; i = j)
+ n_perms = factorial (n);
+ for (i = 0; i < n; i = j)
{
- for (j = i + 1; j < cnt; j++)
+ for (j = i + 1; j < n; 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.
test_insert_no_dups_delete_min (void)
{
const int max_elems = 8;
- int cnt;
+ int n;
- for (cnt = 0; cnt <= max_elems; cnt++)
+ for (n = 0; n <= max_elems; n++)
{
struct heap *h;
struct element *elements;
int *values;
- unsigned int permutation_cnt;
+ unsigned int n_permutations;
int i;
- values = xnmalloc (cnt, sizeof *values);
- elements = xnmalloc (cnt, sizeof *elements);
- for (i = 0; i < cnt; i++)
+ values = xnmalloc (n, sizeof *values);
+ elements = xnmalloc (n, sizeof *elements);
+ for (i = 0; i < n; i++)
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, n))
{
int i;
- for (i = 0; i < cnt; i++)
+ for (i = 0; i < n; i++)
elements[i].x = values[i];
check (heap_is_empty (h));
- for (i = 0; i < cnt; i++)
+ for (i = 0; i < n; i++)
{
heap_insert (h, &elements[i].node);
check (heap_node_to_element (heap_minimum (h))->x
check (heap_count (h) == i + 1);
}
- for (i = 0; i < cnt; i++)
+ for (i = 0; i < n; i++)
{
check (heap_node_to_element (heap_minimum (h))->x == 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 (n));
heap_destroy (h);
free (values);
free (elements);
test_insert_with_dups_delete_min (void)
{
const int max_elems = 7;
- int cnt;
-
- for (cnt = 1; cnt <= max_elems; cnt++)
+ for (int n_elems = 1; n_elems <= max_elems; n_elems++)
{
- unsigned int composition_cnt;
+ unsigned int n_compositions;
int *dups;
- int unique_cnt;
+ int n_uniques;
int *values;
int *sorted_values;
struct element *elements;
int n = 0;
- dups = xnmalloc (cnt, sizeof *dups);
- values = xnmalloc (cnt, sizeof *values);
- sorted_values = xnmalloc (cnt, sizeof *sorted_values);
- elements = xnmalloc (cnt, sizeof *elements);
+ dups = xnmalloc (n_elems, sizeof *dups);
+ values = xnmalloc (n_elems, sizeof *values);
+ sorted_values = xnmalloc (n_elems, sizeof *sorted_values);
+ elements = xnmalloc (n_elems, sizeof *elements);
- unique_cnt = 0;
- composition_cnt = 0;
- while (next_composition (cnt, &unique_cnt, dups))
+ n_uniques = 0;
+ n_compositions = 0;
+ while (next_composition (n_elems, &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;
sorted_values[k] = i;
k++;
}
- check (k == cnt);
+ check (k == n_elems);
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, n_elems))
{
int min = INT_MAX;
- for (i = 0; i < cnt; i++)
+ for (i = 0; i < n_elems; i++)
elements[i].x = values[i];
n++;
check (heap_is_empty (h));
- for (i = 0; i < cnt; i++)
+ for (i = 0; i < n_elems; i++)
{
heap_insert (h, &elements[i].node);
if (values[i] < min)
check (heap_count (h) == i + 1);
}
- for (i = 0; i < cnt; i++)
+ for (i = 0; i < n_elems; i++)
{
struct element *min = heap_node_to_element (heap_minimum (h));
check (min->x == sorted_values[i]);
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, n_elems));
heap_destroy (h);
- composition_cnt++;
+ n_compositions++;
}
- check (composition_cnt == 1 << (cnt - 1));
+ check (n_compositions == 1 << (n_elems - 1));
free (dups);
free (values);
test_insert_no_dups_delete_random (void)
{
const int max_elems = 5;
- int cnt;
+ int n;
- for (cnt = 0; cnt <= max_elems; cnt++)
+ for (n = 0; n <= max_elems; n++)
{
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);
- delete = xnmalloc (cnt, sizeof *delete);
- elements = xnmalloc (cnt, sizeof *elements);
- for (i = 0; i < cnt; i++)
+ insert = xnmalloc (n, sizeof *insert);
+ delete = xnmalloc (n, sizeof *delete);
+ elements = xnmalloc (n, sizeof *elements);
+ for (i = 0; i < n; i++)
{
insert[i] = i;
delete[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, n))
{
- 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, n))
{
int min;
int i;
check (heap_is_empty (h));
min = INT_MAX;
- for (i = 0; i < cnt; i++)
+ for (i = 0; i < n; i++)
{
heap_insert (h, &elements[insert[i]].node);
if (insert[i] < min)
check (heap_count (h) == i + 1);
}
- for (i = 0; i < cnt; i++)
+ for (i = 0; i < n; i++)
{
- int new_min = min_int (delete + i + 1, cnt - i - 1);
+ int new_min = min_int (delete + i + 1, n - i - 1);
heap_delete (h, &elements[delete[i]].node);
- check (heap_count (h) == cnt - i - 1);
+ check (heap_count (h) == n - i - 1);
if (!heap_is_empty (h))
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 (n));
+ insert_n_perms++;
}
- check (insert_perm_cnt == factorial (cnt));
+ check (insert_n_perms == factorial (n));
heap_destroy (h);
free (insert);
free (delete);
test_inc_dec (void)
{
const int max_elems = 8;
- int cnt;
+ int n;
- for (cnt = 0; cnt <= max_elems; cnt++)
+ for (n = 0; n <= max_elems; n++)
{
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);
- delete = xnmalloc (cnt, sizeof *delete);
- elements = xnmalloc (cnt, sizeof *elements);
- for (i = 0; i < cnt; i++)
+ insert = xnmalloc (n, sizeof *insert);
+ delete = xnmalloc (n, sizeof *delete);
+ elements = xnmalloc (n, sizeof *elements);
+ for (i = 0; i < n; i++)
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, n))
{
- for (i = 0; i < cnt; i++)
+ for (i = 0; i < n; i++)
elements[i].x = insert[i];
check (heap_is_empty (h));
- for (i = 0; i < cnt; i++)
+ for (i = 0; i < n; i++)
{
int new_min = min_int (insert, i + 1);
heap_insert (h, &elements[i].node);
check (heap_count (h) == i + 1);
}
- for (i = 0; i < cnt; i++)
+ for (i = 0; i < n; i++)
delete[i] = insert[i];
- for (i = 0; i < cnt; i++)
+ for (i = 0; i < n; 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);
+ elements[i].x = delete[i] = rand () % (n + 2) - 1;
heap_changed (h, &elements[i].node);
check (heap_node_to_element (heap_minimum (h))->x
- == min_int (delete, cnt));
+ == min_int (delete, n));
}
- for (i = 0; i < cnt; i++)
+ for (i = 0; i < n; i++)
{
- int new_min = min_int (delete + i + 1, cnt - i - 1);
+ int new_min = min_int (delete + i + 1, n - i - 1);
heap_delete (h, &elements[i].node);
- check (heap_count (h) == cnt - i - 1);
+ check (heap_count (h) == n - i - 1);
if (!heap_is_empty (h))
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 (n));
heap_destroy (h);
free (insert);
free (delete);
struct heap *h;
int *values;
struct element *elements;
- int cnt;
+ int n;
int insert_chance;
int i;
values = xnmalloc (max_elems, sizeof *values);
elements = xnmalloc (max_elems, sizeof *elements);
- cnt = 0;
+ n = 0;
insert_chance = 5;
h = heap_create (compare_elements, &aux_data);
{
enum { INSERT, DELETE } action;
- if (cnt == 0)
+ if (n == 0)
{
action = INSERT;
if (insert_chance < 9)
insert_chance++;
}
- else if (cnt == max_elems)
+ else if (n == max_elems)
{
action = DELETE;
if (insert_chance > 0)
if (action == INSERT)
{
int new_value;
- int old_min;
new_value = rand () % max_elems;
- values[cnt] = new_value;
- elements[cnt].x = new_value;
+ values[n] = new_value;
+ elements[n].x = new_value;
- heap_insert (h, &elements[cnt].node);
+ heap_insert (h, &elements[n].node);
- old_min = min_int (values, cnt);
-
- cnt++;
+ n++;
}
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];
+ del_idx = rand () % n;
heap_delete (h, &elements[del_idx].node);
- cnt--;
- if (del_idx != cnt)
+ n--;
+ if (del_idx != n)
{
- values[del_idx] = values[cnt];
- elements[del_idx] = elements[cnt];
+ values[del_idx] = values[n];
+ elements[del_idx] = elements[n];
heap_moved (h, &elements[del_idx].node);
}
-
- new_min = min_int (values, cnt);
}
else
abort ();
- check (heap_count (h) == cnt);
- check (heap_is_empty (h) == (cnt == 0));
- if (cnt > 0)
+ check (heap_count (h) == n);
+ check (heap_is_empty (h) == (n == 0));
+ if (n > 0)
check (heap_node_to_element (heap_minimum (h))->x
- == min_int (values, cnt));
+ == min_int (values, n));
}
heap_destroy (h);
free (elements);
\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;
+ }
}
projects / pspp / blobdiff