*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++)
{
- elements[i].x = delete[i] = rand () % (cnt + 2) - 1;
+ 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)
int new_value;
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);
- cnt++;
+ n++;
}
else if (action == DELETE)
{
int del_idx;
- del_idx = rand () % cnt;
+ 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);
}
}
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);