src/algorithm.h

   1 #ifndef SORT_ALGO_H
   2 #define SORT_ALGO_H 1
   3
   4 #include <stddef.h>
   5
   6 /* Compares A and B, given auxiliary data AUX, and returns a
   7    strcmp()-type result. */
   8 typedef int algo_compare_func (const void *a, const void *b, void *aux);
   9
  10 /* Tests a predicate on DATA, given auxiliary data AUX, and
  11    returns nonzero if true or zero if false. */
  12 typedef int algo_predicate_func (const void *data, void *aux);
  13
  14 /* Returns a random number in the range 0 through MAX exclusive,
  15    given auxiliary data AUX. */
  16 typedef unsigned algo_random_func (unsigned max, void *aux);
  17
  18 /* A generally suitable random function. */
  19 algo_random_func algo_default_random;
  20
  21 /* Finds an element in ARRAY, which contains COUNT elements of
  22    SIZE bytes each, using COMPARE for comparisons.  Returns the
  23    first element in ARRAY that matches TARGET, or a null pointer
  24    on failure.  AUX is passed to each comparison as auxiliary
  25    data. */
  26 void *find (const void *array, size_t count, size_t size,
  27             const void *target,
  28             algo_compare_func *compare, void *aux);
  29
  30 /* Sorts ARRAY, which contains COUNT elements of SIZE bytes each,
  31    using COMPARE for comparisons.  AUX is passed to each
  32    comparison as auxiliary data. */
  33 void sort (void *array, size_t count, size_t size,
  34            algo_compare_func *compare, void *aux);
  35
  36 /* Makes the elements in ARRAY unique, by moving up duplicates,
  37    and returns the new number of elements in the array.  Sorted
  38    arrays only.  Arguments same as for sort() above. */
  39 size_t unique (void *array, size_t count, size_t size,
  40                algo_compare_func *compare, void *aux);
  41
  42 /* Helper function that calls sort(), then unique(). */
  43 size_t sort_unique (void *array, size_t count, size_t size,
  44                     algo_compare_func *compare, void *aux);
  45
  46 /* Reorders ARRAY, which contains COUNT elements of SIZE bytes
  47    each, so that the elements for which PREDICATE returns nonzero
  48    precede those for which PREDICATE returns zero.  AUX is passed
  49    as auxiliary data to PREDICATE.  Returns the number of
  50    elements for which PREDICATE returns nonzero.  Not stable. */
  51 size_t partition (void *array, size_t count, size_t size,
  52                   algo_predicate_func *predicate, void *aux);
  53
  54 /* Randomly reorders ARRAY, which contains COUNT elements of SIZE
  55    bytes each.  Uses RANDOM as a source of random data, passing
  56    AUX as the auxiliary data.  RANDOM may be null to use a
  57    default random source. */
  58 void random_shuffle (void *array, size_t count, size_t size,
  59                      algo_random_func *random, void *aux);
  60
  61 /* Copies the COUNT elements of SIZE bytes each from ARRAY to
  62    RESULT, except that elements for which PREDICATE is false are
  63    not copied.  Returns the number of elements copied.  AUX is
  64    passed to PREDICATE as auxiliary data.  */
  65 size_t copy_if (const void *array, size_t count, size_t size,
  66                 void *result,
  67                 algo_predicate_func *predicate, void *aux);
  68
  69 /* Removes elements equal to ELEMENT from ARRAY, which consists
  70    of COUNT elements of SIZE bytes each.  Returns the number of
  71    remaining elements.  AUX is passed to COMPARE as auxiliary
  72    data. */
  73 size_t remove_equal (void *array, size_t count, size_t size,
  74                      void *element,
  75                      algo_compare_func *compare, void *aux);
  76
  77 /* Copies the COUNT elements of SIZE bytes each from ARRAY to
  78    RESULT, except that elements for which PREDICATE is true are
  79    not copied.  Returns the number of elements copied.  AUX is
  80    passed to PREDICATE as auxiliary data.  */
  81 size_t remove_copy_if (const void *array, size_t count, size_t size,
  82                        void *result,
  83                        algo_predicate_func *predicate, void *aux);
  84
  85 /* Searches ARRAY, which contains COUNT elements of SIZE bytes
  86    each, for VALUE, using a binary search.  ARRAY must ordered
  87    according to COMPARE.  AUX is passed to COMPARE as auxiliary
  88    data. */
  89 void *binary_search (const void *array, size_t count, size_t size,
  90                      void *value,
  91                      algo_compare_func *compare, void *aux);
  92
  93 /* Lexicographically compares ARRAY1, which contains COUNT1
  94    elements of SIZE bytes each, to ARRAY2, which contains COUNT2
  95    elements of SIZE bytes, according to COMPARE.  Returns a
  96    strcmp()-type result.  AUX is passed to COMPARE as auxiliary
  97    data. */
  98 int lexicographical_compare (const void *array1, size_t count1,
  99                              const void *array2, size_t count2,
 100                              size_t size,
 101                              algo_compare_func *compare, void *aux);
 102
 103 /* Computes the generalized set difference, ARRAY1 minus ARRAY2,
 104    into RESULT, and returns the number of elements written to
 105    RESULT.  If a value appears M times in ARRAY1 and N times in
 106    ARRAY2, then it will appear max(M - N, 0) in RESULT.  ARRAY1
 107    and ARRAY2 must be sorted, and RESULT is sorted and stable.
 108    ARRAY1 consists of COUNT1 elements, ARRAY2 of COUNT2 elements,
 109    each SIZE bytes.  AUX is passed to COMPARE as auxiliary
 110    data. */
 111 size_t set_difference (const void *array1, size_t count1,
 112                        const void *array2, size_t count2,
 113                        size_t size,
 114                        void *result,
 115                        algo_compare_func *compare, void *aux);
 116
 117 /* Finds the first pair of adjacent equal elements in ARRAY,
 118    which has COUNT elements of SIZE bytes.  Returns the first
 119    element in ARRAY such that COMPARE returns zero when it and
 120    its successor element are compared.  AUX is passed to COMPARE
 121    as auxiliary data. */
 122 void *adjacent_find_equal (const void *array, size_t count, size_t size,
 123                            algo_compare_func *compare, void *aux);
 124
 125 #endif /* sort-algo.h */