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 /* Sorts ARRAY, which contains COUNT elements of SIZE bytes each,
  22    using COMPARE for comparisons.  AUX is passed to each
  23    comparison as auxiliary data. */
  24 void sort (void *array, size_t count, size_t size,
  25            algo_compare_func *compare, void *aux);
  26
  27 /* Makes the elements in ARRAY unique, by moving up duplicates,
  28    and returns the new number of elements in the array.  Sorted
  29    arrays only.  Arguments same as for sort() above. */
  30 size_t unique (void *array, size_t count, size_t size,
  31                algo_compare_func *compare, void *aux);
  32
  33 /* Helper function that calls sort(), then unique(). */
  34 size_t sort_unique (void *array, size_t count, size_t size,
  35                     algo_compare_func *compare, void *aux);
  36
  37 /* Reorders ARRAY, which contains COUNT elements of SIZE bytes
  38    each, so that the elements for which PREDICATE returns nonzero
  39    precede those for which PREDICATE returns zero.  AUX is passed
  40    as auxiliary data to PREDICATE.  Returns the number of
  41    elements for which PREDICATE returns nonzero.  Not stable. */
  42 size_t partition (void *array, size_t count, size_t size,
  43                   algo_predicate_func *predicate, void *aux);
  44
  45 /* Randomly reorders ARRAY, which contains COUNT elements of SIZE
  46    bytes each.  Uses RANDOM as a source of random data, passing
  47    AUX as the auxiliary data.  RANDOM may be null to use a
  48    default random source. */
  49 void random_shuffle (void *array, size_t count, size_t size,
  50                      algo_random_func *random, void *aux);
  51
  52 /* Copies the COUNT elements of SIZE bytes each from ARRAY to
  53    RESULT, except that elements for which PREDICATE is false are
  54    not copied.  Returns the number of elements copied.  AUX is
  55    passed to PREDICATE as auxiliary data.  */
  56 size_t copy_if (const void *array, size_t count, size_t size,
  57                 void *result,
  58                 algo_predicate_func *predicate, void *aux);
  59
  60 /* Copies the COUNT elements of SIZE bytes each from ARRAY to
  61    RESULT, except that elements for which PREDICATE is true are
  62    not copied.  Returns the number of elements copied.  AUX is
  63    passed to PREDICATE as auxiliary data.  */
  64 size_t remove_copy_if (const void *array, size_t count, size_t size,
  65                        void *result,
  66                        algo_predicate_func *predicate, void *aux);
  67
  68 /* Searches ARRAY, which contains COUNT elements of SIZE bytes
  69    each, for VALUE, using a binary search.  ARRAY must ordered
  70    according to COMPARE.  AUX is passed to COMPARE as auxiliary
  71    data. */
  72 void *binary_search (const void *array, size_t count, size_t size,
  73                      void *value,
  74                      algo_compare_func *compare, void *aux);
  75
  76 /* Lexicographically compares ARRAY1, which contains COUNT1
  77    elements of SIZE bytes each, to ARRAY2, which contains COUNT2
  78    elements of SIZE bytes, according to COMPARE.  Returns a
  79    strcmp()-type result.  AUX is passed to COMPARE as auxiliary
  80    data. */
  81 int lexicographical_compare (const void *array1, size_t count1,
  82                              const void *array2, size_t count2,
  83                              size_t size,
  84                              algo_compare_func *compare, void *aux);
  85
  86 #endif /* sort-algo.h */