-/* PSPP - computes sample statistics.
- Copyright (C) 1997-9, 2000 Free Software Foundation, Inc.
- Written by Ben Pfaff <blp@gnu.org>.
+/* PSPP - a program for statistical analysis.
+ Copyright (C) 1997-9, 2000, 2010, 2011 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 the Free Software Foundation; either version 2 of the
- License, or (at your option) any later version.
+ 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
+ the Free Software Foundation, either version 3 of the License, or
+ (at your option) any later version.
- This program is distributed in the hope that it will be useful, but
- WITHOUT ANY WARRANTY; without even the implied warranty of
- MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
- General Public License for more details.
+ This program is distributed in the hope that it will be useful,
+ but WITHOUT ANY WARRANTY; without even the implied warranty of
+ MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
+ GNU General Public License for more details.
You should have received a copy of the GNU General Public License
- along with this program; if not, write to the Free Software
- Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA
- 02110-1301, USA. */
+ along with this program. If not, see <http://www.gnu.org/licenses/>. */
/* Copyright (C) 2001 Free Software Foundation, Inc.
-
+
This file is part of the GNU ISO C++ Library. This library is free
software; you can redistribute it and/or modify it under the
terms of the GNU General Public License as published by the
MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
GNU General Public License for more details.
- You should have received a copy of the GNU General Public License along
- with this library; see the file COPYING. If not, write to the Free
- Software Foundation, 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301,
- USA.
+ You should have received a copy of the GNU General Public License
+ along with this program. If not, see <http://www.gnu.org/licenses/>.
As a special exception, you may use this file as part of a free software
library without restriction. Specifically, if other files instantiate
Lesser General Public License for more details.
You should have received a copy of the GNU Lesser General Public
- License along with the GNU C Library; if not, write to the Free
- Software Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA
- 02110-1301 USA. */
+ License along with the GNU C Library. If not, see
+ <http://www.gnu.org/licenses/>. */
#include <config.h>
+
#include "array.h"
-#include <gsl/gsl_rng.h>
+
#include <limits.h>
#include <stdlib.h>
#include <string.h>
-#include "alloc.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 "libpspp/assertion.h"
+
+#include "gl/xalloc.h"
+#include "gl/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;
- while (count-- > 0)
+ while (count-- > 0)
{
if (compare (target, element, aux) == 0)
return (void *) element;
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;
- while (count-- > 0)
+ while (count-- > 0)
{
if (compare (element, first, aux) == 0)
equal_cnt++;
-
+
first += size;
}
/* 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)
+ 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;
char *result = array;
- for (;;)
+ for (;;)
{
first += size;
- if (first >= last)
+ if (first >= last)
{
assert (adjacent_find_equal (array, count,
size, compare, aux) == NULL);
- return count;
+ return count;
}
- if (compare (result, first, aux))
+ if (compare (result, first, aux))
{
result += size;
if (result != first)
memcpy (result, first, size);
}
- else
+ else
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
+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 (;;)
{
/* Move FIRST forward to point to first element that fails
PREDICATE. */
- for (;;)
+ for (;;)
{
if (first == last)
goto done;
- else if (!predicate (first, aux))
+ else if (!predicate (first, aux))
break;
- first += size;
+ first += size;
}
- nonzero_cnt--;
+ true_cnt--;
/* Move LAST backward to point to last element that passes
PREDICATE. */
- for (;;)
+ for (;;)
{
last -= size;
if (first == last)
goto done;
- else if (predicate (last, aux))
+ else if (predicate (last, aux))
break;
else
- nonzero_cnt--;
+ true_cnt--;
}
-
+
/* By swapping FIRST and LAST we extend the starting and
ending sequences that pass and fail, respectively,
PREDICATE. */
}
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
RESULT, except that elements for which PREDICATE is false are
not copied. Returns the number of elements copied. AUX is
passed to PREDICATE as auxiliary data. */
-size_t
+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;
char *output = result;
size_t nonzero_cnt = 0;
-
+
while (input < last)
{
- if (predicate (input, aux))
+ if (predicate (input, aux))
{
memcpy (output, input, size);
output += size;
following them, if any, into its position. */
void
remove_range (void *array_, size_t count, size_t size,
- size_t idx, size_t n)
+ size_t idx, size_t n)
{
char *array = array_;
-
+
assert (array != NULL);
assert (idx <= count);
assert (idx + n <= count);
following it, if any, into its position. */
void
remove_element (void *array, size_t count, size_t size,
- size_t idx)
+ size_t idx)
{
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
+ position. */
+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))
time. */
void
move_element (void *array_, size_t count, size_t size,
- size_t old_idx, size_t new_idx)
+ size_t old_idx, size_t new_idx)
{
assert (array_ != NULL || count == 0);
assert (old_idx < count);
assert (new_idx < count);
-
- if (old_idx != new_idx)
+
+ if (old_idx != new_idx)
{
char *array = array_;
char *element = xmalloc (size);
}
}
+/* 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
+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;
result = first;
count--;
- for (;;)
+ for (;;)
{
first += size;
if (first >= last)
goto done;
- if (compare (first, element, aux) == 0)
+ if (compare (first, element, aux) == 0)
{
- count--;
+ count--;
continue;
}
-
+
memcpy (result, first, size);
result += size;
}
RESULT, except that elements for which PREDICATE is true are
not copied. Returns the number of elements copied. AUX is
passed to PREDICATE as auxiliary data. */
-size_t
+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);
- if (count != 0)
+ if (count != 0)
{
const char *first = array;
int low = 0;
int high = count - 1;
- while (low <= high)
+ while (low <= high)
{
int middle = (low + high) / 2;
const char *element = first + middle * size;
int cmp = compare (value, element, aux);
- if (cmp > 0)
+ if (cmp > 0)
low = middle + 1;
else if (cmp < 0)
high = middle - 1;
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 1;
+ return false;
+
+ 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;
const char *last2 = first2 + count2 * size;
char *result = result_;
size_t result_count = 0;
-
- while (first1 != last1 && first2 != last2)
+
+ while (first1 != last1 && first2 != last2)
{
int cmp = compare (first1, first2, aux);
if (cmp < 0)
}
}
- while (first1 != last1)
+ while (first1 != last1)
{
memcpy (result, first1, size);
first1 += 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;
- while (first < last && first + size < last)
+ while (first < last && first + size < last)
{
if (compare (first, first + size, aux) == 0)
return (void *) first;
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;
-
+
expensive_assert (count < 1 || is_heap (array, count - 1,
size, compare, aux));
- for (i = count; i > 1; i /= 2)
+ for (i = count; i > 1; i /= 2)
{
char *parent = first + (i / 2 - 1) * size;
char *element = first + (i - 1) * size;
if (compare (parent, element, aux) < 0)
SWAP (parent, element, size);
else
- break;
+ break;
}
expensive_assert (is_heap (array, count, size, compare, aux));
}
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;
-
- for (;;)
+
+ for (;;)
{
size_t left = 2 * idx;
size_t right = left + 1;
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;
-
+
for (idx = count / 2; idx >= 1; idx--)
heapify (array, count, size, idx, compare, aux);
expensive_assert (count < 1 || is_heap (array, count, size, compare, aux));
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;
-
+
for (child = 2; child <= count; 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