/* PSPP - computes sample statistics.
Copyright (C) 1997-9, 2000 Free Software Foundation, Inc.
- Written by Ben Pfaff <blp@gnu.org>.
This program is free software; you can redistribute it and/or
modify it under the terms of the GNU General Public License as
#include <config.h>
#include "array.h"
-#include <gsl/gsl_rng.h>
#include <limits.h>
#include <stdlib.h>
#include <string.h>
#include "alloc.h"
+#include <libpspp/assertion.h>
-/* Some of the assertions in this file are very expensive. We
- don't use them by default. */
-#ifdef EXTRA_CHECKS
-#define expensive_assert(X) assert(X)
-#else
-#define expensive_assert(X) ((void) 0)
-#endif
#include "message.h"
+
+#include "minmax.h"
\f
/* Finds an element in ARRAY, which contains COUNT elements of
SIZE bytes each, using COMPARE for comparisons. Returns the
void *
find (const void *array, size_t count, size_t size,
const void *target,
- algo_compare_func *compare, void *aux)
+ algo_compare_func *compare, const void *aux)
{
const char *element = array;
size_t
count_equal (const void *array, size_t count, size_t size,
const void *element,
- algo_compare_func *compare, void *aux)
+ algo_compare_func *compare, const void *aux)
{
const char *first = array;
size_t equal_cnt = 0;
/* Counts and return the number of elements in ARRAY, which
contains COUNT elements of SIZE bytes each, for which
- PREDICATE returns nonzero. AUX is passed as auxiliary data to
+ PREDICATE returns true. AUX is passed as auxiliary data to
PREDICATE. */
size_t
count_if (const void *array, size_t count, size_t size,
- algo_predicate_func *predicate, void *aux)
+ algo_predicate_func *predicate, const void *aux)
{
const char *first = array;
- size_t nonzero_cnt = 0;
+ size_t true_cnt = 0;
while (count-- > 0)
{
if (predicate (first, aux) != 0)
- nonzero_cnt++;
+ true_cnt++;
first += size;
}
- return nonzero_cnt;
+ return true_cnt;
}
\f
/* Byte-wise swap two items of size SIZE. */
arrays only. Arguments same as for sort() above. */
size_t
unique (void *array, size_t count, size_t size,
- algo_compare_func *compare, void *aux)
+ algo_compare_func *compare, const void *aux)
{
char *first = array;
char *last = first + size * count;
/* Helper function that calls sort(), then unique(). */
size_t
sort_unique (void *array, size_t count, size_t size,
- algo_compare_func *compare, void *aux)
+ algo_compare_func *compare, const void *aux)
{
sort (array, count, size, compare, aux);
return unique (array, count, size, compare, aux);
}
\f
/* Reorders ARRAY, which contains COUNT elements of SIZE bytes
- each, so that the elements for which PREDICATE returns nonzero
+ each, so that the elements for which PREDICATE returns true
precede those for which PREDICATE returns zero. AUX is
passed to each predicate as auxiliary data. Returns the
- number of elements for which PREDICATE returns nonzero. Not
+ number of elements for which PREDICATE returns true. Not
stable. */
size_t
partition (void *array, size_t count, size_t size,
- algo_predicate_func *predicate, void *aux)
+ algo_predicate_func *predicate, const void *aux)
{
- size_t nonzero_cnt = count;
+ size_t true_cnt = count;
char *first = array;
- char *last = first + nonzero_cnt * size;
+ char *last = first + true_cnt * size;
for (;;)
{
first += size;
}
- nonzero_cnt--;
+ true_cnt--;
/* Move LAST backward to point to last element that passes
PREDICATE. */
else if (predicate (last, aux))
break;
else
- nonzero_cnt--;
+ true_cnt--;
}
/* By swapping FIRST and LAST we extend the starting and
}
done:
- assert (is_partitioned (array, count, size, nonzero_cnt, predicate, aux));
- return nonzero_cnt;
+ assert (is_partitioned (array, count, size, true_cnt, predicate, aux));
+ return true_cnt;
}
/* Checks whether ARRAY, which contains COUNT elements of SIZE
- bytes each, is partitioned such that PREDICATE returns nonzero
- for the first NONZERO_CNT elements and zero for the remaining
+ bytes each, is partitioned such that PREDICATE returns true
+ for the first TRUE_CNT elements and zero for the remaining
elements. AUX is passed as auxiliary data to PREDICATE. */
-int
+bool
is_partitioned (const void *array, size_t count, size_t size,
- size_t nonzero_cnt,
- algo_predicate_func *predicate, void *aux)
+ size_t true_cnt,
+ algo_predicate_func *predicate, const void *aux)
{
const char *first = array;
size_t idx;
- assert (nonzero_cnt <= count);
- for (idx = 0; idx < nonzero_cnt; idx++)
+ assert (true_cnt <= count);
+ for (idx = 0; idx < true_cnt; idx++)
if (predicate (first + idx * size, aux) == 0)
- return 0;
- for (idx = nonzero_cnt; idx < count; idx++)
+ return false;
+ for (idx = true_cnt; idx < count; idx++)
if (predicate (first + idx * size, aux) != 0)
- return 0;
- return 1;
+ return false;
+ return true;
}
\f
/* Copies the COUNT elements of SIZE bytes each from ARRAY to
size_t
copy_if (const void *array, size_t count, size_t size,
void *result,
- algo_predicate_func *predicate, void *aux)
+ algo_predicate_func *predicate, const void *aux)
{
const char *input = array;
const char *last = input + size * count;
remove_range (array, count, size, idx, 1);
}
+/* Makes room for N elements starting at IDX in ARRAY, which
+ initially consists of COUNT elements of SIZE bytes each, by
+ shifting elements IDX...COUNT (exclusive) to the right by N
+ positions. */
+void
+insert_range (void *array_, size_t count, size_t size,
+ size_t idx, size_t n)
+{
+ char *array = array_;
+
+ assert (idx <= count);
+ memmove (array + (idx + n) * size, array + idx * size, (count - idx) * size);
+}
+
+/* Makes room for a new element at IDX in ARRAY, which initially
+ consists of COUNT elements of SIZE bytes each, by shifting
+ elements IDX...COUNT (exclusive) to the right by one
+ positions. */
+void
+insert_element (void *array, size_t count, size_t size,
+ size_t idx)
+{
+ insert_range (array, count, size, idx, 1);
+}
+
/* Moves an element in ARRAY, which consists of COUNT elements of
SIZE bytes each, from OLD_IDX to NEW_IDX, shifting around
other elements as needed. Runs in O(abs(OLD_IDX - NEW_IDX))
}
}
+/* Moves N elements in ARRAY starting at OLD_IDX, which consists
+ of COUNT elements of SIZE bytes each, so that they now start
+ at NEW_IDX, shifting around other elements as needed. */
+void
+move_range (void *array_, size_t count, size_t size,
+ size_t old_idx, size_t new_idx, size_t n)
+{
+ assert (array_ != NULL || count == 0);
+ assert (n <= count);
+ assert (old_idx + n <= count);
+ assert (new_idx + n <= count);
+
+ if (old_idx != new_idx && n > 0)
+ {
+ char *array = array_;
+ char *range = xmalloc (size * n);
+ char *new = array + new_idx * size;
+ char *old = array + old_idx * size;
+
+ memcpy (range, old, size * n);
+ if (new < old)
+ memmove (new + size * n, new, (old_idx - new_idx) * size);
+ else
+ memmove (old, old + size * n, (new_idx - old_idx) * size);
+ memcpy (new, range, size * n);
+
+ free (range);
+ }
+}
+
/* A predicate and its auxiliary data. */
struct pred_aux
{
algo_predicate_func *predicate;
- void *aux;
+ const void *aux;
};
-static int
-not (const void *data, void *pred_aux_)
+static bool
+not (const void *data, const void *pred_aux_)
{
const struct pred_aux *pred_aux = pred_aux_;
size_t
remove_equal (void *array, size_t count, size_t size,
void *element,
- algo_compare_func *compare, void *aux)
+ algo_compare_func *compare, const void *aux)
{
char *first = array;
char *last = first + count * size;
size_t
remove_copy_if (const void *array, size_t count, size_t size,
void *result,
- algo_predicate_func *predicate, void *aux)
+ algo_predicate_func *predicate, const void *aux)
{
struct pred_aux pred_aux;
pred_aux.predicate = predicate;
void *
binary_search (const void *array, size_t count, size_t size,
void *value,
- algo_compare_func *compare, void *aux)
+ algo_compare_func *compare, const void *aux)
{
- assert (array != NULL);
+ assert (array != NULL || count == 0);
assert (count <= INT_MAX);
assert (compare != NULL);
lexicographical_compare_3way (const void *array1, size_t count1,
const void *array2, size_t count2,
size_t size,
- algo_compare_func *compare, void *aux)
+ algo_compare_func *compare, const void *aux)
{
const char *first1 = array1;
const char *first2 = array2;
void
sort (void *array, size_t count, size_t size,
- algo_compare_func *compare, void *aux)
+ algo_compare_func *compare, const void *aux)
{
char *const first = array;
const size_t max_thresh = MAX_THRESH * size;
of the array to sort, and END_PTR points at the very last element in
the array (*not* one beyond it!). */
-#define min(x, y) ((x) < (y) ? (x) : (y))
-
{
char *const end_ptr = &first[size * (count - 1)];
char *tmp_ptr = first;
- char *thresh = min(end_ptr, first + max_thresh);
+ char *thresh = MIN (end_ptr, first + max_thresh);
register char *run_ptr;
/* Find smallest element in first threshold and place it at the
/* Tests whether ARRAY, which contains COUNT elements of SIZE
bytes each, is sorted in order according to COMPARE. AUX is
passed to COMPARE as auxiliary data. */
-int
+bool
is_sorted (const void *array, size_t count, size_t size,
- algo_compare_func *compare, void *aux)
+ algo_compare_func *compare, const void *aux)
{
const char *first = array;
size_t idx;
for (idx = 0; idx + 1 < count; idx++)
if (compare (first + idx * size, first + (idx + 1) * size, aux) > 0)
- return 0;
+ return false;
- return 1;
+ return true;
}
\f
/* Computes the generalized set difference, ARRAY1 minus ARRAY2,
const void *array2, size_t count2,
size_t size,
void *result_,
- algo_compare_func *compare, void *aux)
+ algo_compare_func *compare, const void *aux)
{
const char *first1 = array1;
const char *last1 = first1 + count1 * size;
data. */
void *
adjacent_find_equal (const void *array, size_t count, size_t size,
- algo_compare_func *compare, void *aux)
+ algo_compare_func *compare, const void *aux)
{
const char *first = array;
const char *last = first + count * size;
data. */
void
push_heap (void *array, size_t count, size_t size,
- algo_compare_func *compare, void *aux)
+ algo_compare_func *compare, const void *aux)
{
char *first = array;
size_t i;
static void
heapify (void *array, size_t count, size_t size,
size_t idx,
- algo_compare_func *compare, void *aux)
+ algo_compare_func *compare, const void *aux)
{
char *first = array;
AUX as auxiliary data. */
void
pop_heap (void *array, size_t count, size_t size,
- algo_compare_func *compare, void *aux)
+ algo_compare_func *compare, const void *aux)
{
char *first = array;
auxiliary data. */
void
make_heap (void *array, size_t count, size_t size,
- algo_compare_func *compare, void *aux)
+ algo_compare_func *compare, const void *aux)
{
size_t idx;
passing AUX as auxiliary data. */
void
sort_heap (void *array, size_t count, size_t size,
- algo_compare_func *compare, void *aux)
+ algo_compare_func *compare, const void *aux)
{
char *first = array;
size_t idx;
}
/* ARRAY contains COUNT elements of SIZE bytes each. This
- function tests whether ARRAY is a heap and returns 1 if so, 0
- otherwise. Uses COMPARE to compare elements, passing AUX as
- auxiliary data. */
-int
+ function tests whether ARRAY is a heap and returns true if so,
+ false otherwise. Uses COMPARE to compare elements, passing
+ AUX as auxiliary data. */
+bool
is_heap (const void *array, size_t count, size_t size,
- algo_compare_func *compare, void *aux)
+ algo_compare_func *compare, const void *aux)
{
const char *first = array;
size_t child;
size_t parent = child / 2;
if (compare (first + (parent - 1) * size,
first + (child - 1) * size, aux) < 0)
- return 0;
+ return false;
}
- return 1;
+ return true;
}
projects / pspp-builds.git / blobdiff