/* A generally suitable random function. */
algo_random_func algo_default_random;
+/* Finds an element in ARRAY, which contains COUNT elements of
+ SIZE bytes each, using COMPARE for comparisons. Returns the
+ first element in ARRAY that matches TARGET, or a null pointer
+ on failure. AUX is passed to each comparison as auxiliary
+ data. */
+void *find (const void *array, size_t count, size_t size,
+ const void *target,
+ algo_compare_func *compare, void *aux);
+
+/* Counts and return the number of elements in ARRAY, which
+ contains COUNT elements of SIZE bytes each, which are equal to
+ ELEMENT as compared with COMPARE. AUX is passed as auxiliary
+ data to COMPARE. */
+size_t count_equal (const void *array, size_t count, size_t size,
+ const void *element,
+ algo_compare_func *compare, void *aux);
+
+/* 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. */
+size_t count_if (const void *array, size_t count, size_t size,
+ algo_predicate_func *predicate, void *aux);
+
/* Sorts ARRAY, which contains COUNT elements of SIZE bytes each,
using COMPARE for comparisons. AUX is passed to each
comparison as auxiliary data. */
void sort (void *array, size_t count, size_t size,
algo_compare_func *compare, void *aux);
+/* 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 is_sorted (const void *array, size_t count, size_t size,
+ algo_compare_func *compare, void *aux);
+
/* Makes the elements in ARRAY unique, by moving up duplicates,
and returns the new number of elements in the array. Sorted
arrays only. Arguments same as for sort() above. */
size_t partition (void *array, size_t count, size_t size,
algo_predicate_func *predicate, void *aux);
+/* 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
+ elements. AUX is passed as auxiliary data to PREDICATE. */
+int is_partitioned (const void *array, size_t count, size_t size,
+ size_t nonzero_cnt,
+ algo_predicate_func *predicate, void *aux);
+
/* Randomly reorders ARRAY, which contains COUNT elements of SIZE
bytes each. Uses RANDOM as a source of random data, passing
AUX as the auxiliary data. RANDOM may be null to use a
void *result,
algo_predicate_func *predicate, void *aux);
+/* Removes elements equal to ELEMENT from ARRAY, which consists
+ of COUNT elements of SIZE bytes each. Returns the number of
+ remaining elements. AUX is passed to COMPARE as auxiliary
+ data. */
+size_t remove_equal (void *array, size_t count, size_t size,
+ void *element,
+ algo_compare_func *compare, void *aux);
+
/* Copies the COUNT elements of SIZE bytes each from ARRAY to
RESULT, except that elements for which PREDICATE is true are
not copied. Returns the number of elements copied. AUX is
elements of SIZE bytes, according to COMPARE. Returns a
strcmp()-type result. AUX is passed to COMPARE as auxiliary
data. */
-int lexicographical_compare (const void *array1, size_t count1,
- const void *array2, size_t count2,
- size_t size,
- algo_compare_func *compare, void *aux);
+int lexicographical_compare_3way (const void *array1, size_t count1,
+ const void *array2, size_t count2,
+ size_t size,
+ algo_compare_func *compare, void *aux);
+
+/* Computes the generalized set difference, ARRAY1 minus ARRAY2,
+ into RESULT, and returns the number of elements written to
+ RESULT. If a value appears M times in ARRAY1 and N times in
+ ARRAY2, then it will appear max(M - N, 0) in RESULT. ARRAY1
+ and ARRAY2 must be sorted, and RESULT is sorted and stable.
+ ARRAY1 consists of COUNT1 elements, ARRAY2 of COUNT2 elements,
+ each SIZE bytes. AUX is passed to COMPARE as auxiliary
+ data. */
+size_t set_difference (const void *array1, size_t count1,
+ const void *array2, size_t count2,
+ size_t size,
+ void *result,
+ algo_compare_func *compare, void *aux);
+
+/* Finds the first pair of adjacent equal elements in ARRAY,
+ which has COUNT elements of SIZE bytes. Returns the first
+ element in ARRAY such that COMPARE returns zero when it and
+ its successor element are compared. AUX is passed to COMPARE
+ as auxiliary data. */
+void *adjacent_find_equal (const void *array, size_t count, size_t size,
+ algo_compare_func *compare, void *aux);
+
+/* ARRAY contains COUNT elements of SIZE bytes each. Initially
+ the first COUNT - 1 elements of these form a heap, followed by
+ a single element not part of the heap. This function adds the
+ final element, forming a heap of COUNT elements in ARRAY.
+ Uses COMPARE to compare elements, passing AUX as auxiliary
+ data. */
+void push_heap (void *array, size_t count, size_t size,
+ algo_compare_func *compare, void *aux);
+
+/* ARRAY contains COUNT elements of SIZE bytes each. Initially
+ all COUNT elements form a heap. This function moves the
+ largest element in the heap to the final position in ARRAY and
+ reforms a heap of the remaining COUNT - 1 elements at the
+ beginning of ARRAY. Uses COMPARE to compare elements, passing
+ AUX as auxiliary data. */
+void pop_heap (void *array, size_t count, size_t size,
+ algo_compare_func *compare, void *aux);
+
+/* Turns ARRAY, which contains COUNT elements of SIZE bytes, into
+ a heap. Uses COMPARE to compare elements, passing AUX as
+ auxiliary data. */
+void make_heap (void *array, size_t count, size_t size,
+ algo_compare_func *compare, void *aux);
+
+/* ARRAY contains COUNT elements of SIZE bytes each. Initially
+ all COUNT elements form a heap. This function turns the heap
+ into a fully sorted array. Uses COMPARE to compare elements,
+ passing AUX as auxiliary data. */
+void sort_heap (void *array, size_t count, size_t size,
+ algo_compare_func *compare, void *aux);
+
+/* 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 is_heap (const void *array, size_t count, size_t size,
+ algo_compare_func *compare, void *aux);
+
#endif /* sort-algo.h */
projects / pspp-builds.git / blobdiff