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 #endif /* sort-algo.h */