X-Git-Url: https://pintos-os.org/cgi-bin/gitweb.cgi?a=blobdiff_plain;f=src%2Falgorithm.h;h=f8f2b84d877dd8c43ea5a01055ce587a71aefe2c;hb=f9d47b5bba8416419cf3bcd3aa23c2d40a05fcac;hp=441130078c46e0ec3890bf67115aaa4ccdead1e5;hpb=6ad392174e035d6e0823fd7894a0488acf274b97;p=pspp-builds.git

diff --git a/src/algorithm.h b/src/algorithm.h
index 44113007..f8f2b84d 100644
--- a/src/algorithm.h
+++ b/src/algorithm.h
@@ -27,12 +27,33 @@ 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. */
@@ -51,6 +72,14 @@ size_t sort_unique (void *array, size_t count, size_t size,
 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
@@ -95,10 +124,10 @@ void *binary_search (const void *array, size_t count, size_t size,
    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
@@ -122,4 +151,43 @@ size_t set_difference (const void *array1, size_t count1,
 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 */