// -*- C++ -*-
// automatically generated by autodoc

// ========== HEADER FILE src/sort/bsearch.h: ==========

ulong bsearch(const Type *f, ulong n, const Type v);
// Return index of first element in f[] that equals v
// Return n if there is no such element.
// f[] must be sorted in ascending order.
// Must have  n!=0

ulong bsearch_geq(const Type *f, ulong n, const Type v);
// Return index of first element in f[] that is >= v
// Return n if there is no such element.
// f[] must be sorted in ascending order.
// Must have  n!=0

ulong bsearch_leq(const Type *f, ulong n, const Type v);
// Return index of first element in f[] that is <= v
// Return n (word with all bits set) if there is no such element.
// f[] must be sorted in ascending order.
// Must have  n!=0

// ========== HEADER FILE src/sort/bsearchapprox.h: ==========

ulong bsearch_approx(const Type *f, ulong n, const Type v, Type da);
// Return index of first element x in f[] for which  |(x-v)| <= da
// Return n if there is no such element.
// f[] must be sorted in ascending order.
// da must be positive.
//
// Makes sense only with inexact types (float or double).
// Must have  n!=0

ulong bsearch_approx(const Type *f, ulong n, const Type v, Type da,;
                     int (*cmp)(const Type &, const Type &))
//
// Return index of first element x in f[] for which  |(x-v)| <= da
//    with respect to comparison function cmp().
// Return n if there is no such element.
// f[] must be sorted in ascending order.
// da must be positive.
//
// Makes sense only with inexact types (float or double).
// Must have  n!=0

// ========== HEADER FILE src/sort/bsearchfunc.h: ==========

ulong bsearch(const Type *f, ulong n, const Type v,;
              int (*cmp)(const Type &, const Type &))
// return index of first element in f[] that is == v
// return n if there is no such element
// f[] must be sorted in ascending order
// must have  n!=0

ulong bsearch_geq(const Type *f, ulong n, const Type v,;
                  int (*cmp)(const Type &, const Type &))
// return index of first element in f[] that is >= v
// return n if there is no such element
// f[] must be sorted in ascending order
// must have  n!=0

ulong bsearch_leq(const Type *f, ulong n, const Type v,;
                  int (*cmp)(const Type &, const Type &))
// return index of first element in f[] that is <= v
// return n if there is no such element
// f[] must be sorted in ascending order
// must have  n!=0

// ========== HEADER FILE src/sort/bsearchidx.h: ==========

ulong idx_bsearch(const Type *f, ulong n, const ulong *x, const Type v);
// Return minimal i so that f[x[i]] == v.
// Return n if there is no such i.
// f[x[]] must be (index-)sorted in ascending order:
// f[x[i]] <= f[x[i+i]]
// Must have  n!=0

ulong idx_bsearch_geq(const Type *f, ulong n, const ulong *x, const Type v);
// Return minimal i so that f[x[i]] >= v.
// Return n if there is no such i.
// f[x[]] must be (index-)sorted in ascending order:
// f[x[i]] <= f[x[i+i]]
// Must have  n!=0

// ========== HEADER FILE src/sort/bsearchidxfunc.h: ==========

ulong idx_bsearch(const Type *f, ulong n, const ulong *x, const Type v,;
                  int (*cmp)(const Type &, const Type &))
// Return index-ptr i of first element in f[] that is == v
// i.e. f[x[i]] == v, with i minimal.
// Return n if there is no such element
// f[x[]] must be (index-)sorted in ascending order:
// f[x[i]] <= f[x[i+i]]
// Must have  n!=0

ulong idx_bsearch_geq(const Type *f, ulong n, const ulong *x, const Type v,;
                      int (*cmp)(const Type &, const Type &))
// Return index-ptr of first element in f[] that is >= v
// i.e. f[x[i]] >= v, with i minimal.
// Return n if there is no such element
// f[x[]] must be (index-)sorted in ascending order:
// f[x[i]] <= f[x[i+i]]
// Must have  n!=0

// ========== HEADER FILE src/sort/bsearchptr.h: ==========

ulong ptr_bsearch(/*const Type *f,*/ ulong n, Type const*const*x, const Type v);
// Return index of ptr i to first element in f[] that is == v
// i.e. *x[i] == v, with i minimal.
// Return n if there is no such element
// x[] must be (ptr-)sorted in ascending order:
// *x[i] <= *x[i+i]
// Must have  n!=0

ulong ptr_bsearch_geq(/*const Type *f,*/ ulong n, Type const*const*x, const Type v);
// Return index of ptr of first element in f[] that is >= v
// i.e. *x[i] >= v, with i minimal.
// Return n if there is no such element
// x[] must be (ptr-)sorted in ascending order:
// *x[i] <= *x[i+i]
// Must have  n!=0

// ========== HEADER FILE src/sort/bsearchptrfunc.h: ==========

ulong ptr_bsearch(/*const Type *f,*/ ulong n, Type const*const*x, const Type v,;
                  int (*cmp)(const Type &, const Type &))
// Return index of ptr i to first element in f[] that is == v
// i.e. *x[i] == v, with i minimal.
// Return n if there is no such element.
// x[] must be (ptr-)sorted in ascending order:
// *x[i] <= *x[i+i]
// Must have  n!=0

ulong ptr_bsearch_geq(/*const Type *f,*/ ulong n, Type const*const*x, const Type v,;
                      int (*cmp)(const Type &, const Type &))
// Return index of ptr of first element in f[] that is >= v
// i.e. *x[i] >= v, with i minimal.
// Return n if there is no such element
// x[] must be (ptr-)sorted in ascending order:
// *x[i] <= *x[i+i]
// Must have  n!=0

// ========== HEADER FILE src/sort/convex.h: ==========

ulong test_strictly_convex(Type *f, ulong n);
// Return index of maximum for strictly convex sequence,
//   otherwise return 0

ulong test_strictly_concave(Type *f, ulong n);
// Return index of minimum for strictly concave sequence,
//   otherwise return 0

ulong last_weak_rise_idx(Type *f, ulong n);
// Return last index of maximal weakly rising prefix of f[].

ulong last_weak_fall_idx(Type *f, ulong n);
// Return last index of maximal weakly falling prefix of f[].

bool is_weakly_convex(Type *f, ulong n);
// Return whether sequence is weakly convex

bool is_weakly_concave(Type *f, ulong n);
// Return whether sequence is weakly concave

// ========== HEADER FILE src/sort/equivclasses.h: ==========

void equivalence_classes(const Type *s, ulong n, bool (*equiv_q)(Type,Type), ulong *q);
// Given an equivalence relation '==' (as function equiv_q())
//  and a set s[] with n elements,
// write to q[k] the index j of the first element s[j] such that s[k]==s[j].
// For the complexity C:  n<=C<=n*n
//  C=n*n if each element is in its own class
//  C=n   if all elements are in the same class

// ========== HEADER FILE src/sort/heapsort.h: ==========

void heap_sort(Type *x, ulong n);
// Sort x[] into ascending order.

void heap_sort_descending(Type *x, ulong n);
// Sort x[] into descending order.

// ========== HEADER FILE src/sort/merge-sort.h: ==========

void merge(Type * const restrict f, ulong na, ulong nb, Type * const restrict t);
// Merge the (sorted) arrays
//   A[] := f[0], f[1], ..., f[na-1]  and  B[] := f[na], f[na+1], ..., f[na+nb-1]
// into  t[] := t[0], t[1], ..., t[na+nb-1]  such that t[] is sorted.
// Must have: na>0 and nb>0

void merge_sort_rec(Type *f, ulong n, Type *t);

void merge_sort(Type *f, ulong n, Type *tmp=0);

void merge_sort_rec4(Type *f, ulong n, Type *t);

void merge_sort4(Type *f, ulong n, Type *tmp=0);

// ========== HEADER FILE src/sort/minmax.h: ==========

inline Type min(const Type *f, ulong n);
// Return minimum of array.

inline ulong min_idx(const Type *f, ulong n);
// Return index of minimum of array.

inline Type max(const Type *f, ulong n);
// Return maximum of array.

inline ulong max_idx(const Type *f, ulong n);
// Return index of maximum of array.

inline void min_max(const Type *f, ulong n, Type *mi, Type *ma);
// Set *mi to minimum of array
// and *ma to maximum of array.

// ========== HEADER FILE src/sort/minmaxfunc.h: ==========

Type min(const Type *f, ulong n, int (*cmp)(const Type &, const Type &));
// Return minimum (value) of array elements
// wrt. to comparison function

Type max(const Type *f, ulong n, int (*cmp)(const Type &, const Type &));
// Return maximum (value) of array elements
// wrt. to comparison function

bool is_partitioned(const Type *f, ulong n, ulong k, int (*cmp)(const Type &, const Type &));

// ========== HEADER FILE src/sort/minmaxidx.h: ==========

Type idx_min(const Type *f, ulong n, const ulong *x);
// Return minimum (value) of array elements
//   {f[x[0]], f[x[1]], ..., f[x[n-1]]}

Type idx_max(const Type *f, ulong n, const ulong *x);
// Return maximum (value) of array elements
//   {f[x[0]], f[x[1]], ..., f[x[n-1]]}

bool is_idx_partitioned(const Type *f, ulong n, const ulong *x, ulong k);

// ========== HEADER FILE src/sort/minmaxidxfunc.h: ==========

Type idx_min(const Type *f, ulong n, const ulong *x,;
             int (*cmp)(const Type &, const Type &))
// Return minimum (value) of array elements
//   {f[x[0]], f[x[1]], ..., f[x[n-1]]}
// with respect to comparison function cmp()

Type idx_max(const Type *f, ulong n, const ulong *x,;
             int (*cmp)(const Type &, const Type &))
// Return maximum (value) of array elements
//   {f[x[0]], f[x[1]], ..., f[x[n-1]]}
// with respect to comparison function cmp()

bool is_idx_partitioned(const Type *f, ulong n, const ulong *x, ulong k,;
                        int (*cmp)(const Type &, const Type &))

// ========== HEADER FILE src/sort/minmaxmed23.h: ==========

// minimum and maximum of 2 or 3 elements
// minimum, maximum and median of 3 elements
static inline Type  min2(const Type &x, const Type &y);
// Return minimum of the input values

static inline Type  max2(const Type &x, const Type &y);
// Return maximum of the input values

static inline Type  min3(const Type &x, const Type &y, const Type &z);
// Return minimum of the input values

static inline Type  max3(const Type &x, const Type &y, const Type &z);
// Return maximum of the input values

static inline Type  median3(const Type &x, const Type &y, const Type &z);
// Return median of the input values

// ========== HEADER FILE src/sort/minmaxmed23func.h: ==========

// minimum and maximum of 2 or 3 elements, with comparison function
// minimum, maximum and median of 3 elements, with comparison function
static inline Type  min2(const Type &x, const Type &y,;
                         int (*cmp)(const Type &, const Type &))
// Return minimum of the input values wrt. cmp()

static inline Type  max2(const Type &x, const Type &y,;
                         int (*cmp)(const Type &, const Type &))
// Return maximum of the input values wrt. cmp()

Type  min3(const Type &x, const Type &y, const Type &z,;
           int (*cmp)(const Type &, const Type &))
// Return minimum of the input values wrt. cmp()

Type  max3(const Type &x, const Type &y, const Type &z,;
           int (*cmp)(const Type &, const Type &))
// Return maximum of the input values wrt. cmp()

Type  median3(const Type &x, const Type &y, const Type &z,;
              int (*cmp)(const Type &, const Type &))
// Return median of the input values wrt. cmp()
//{ return  x<y ? (y<z ? y : (x<z ? z : x)) : (z<y ? y : (z<x ? z : x)); }

// ========== HEADER FILE src/sort/minmaxmed23idx.h: ==========

// minimum and maximum of 2 or 3 elements, index versions
// minimum, maximum and median of 3 elements, index versions
static inline ulong  idx_min2(const Type &x, const Type &y);
// Return index (0 or 1) of minimum of the input values

static inline ulong  idx_max2(const Type &x, const Type &y);
// Return index (0 or 1) of maximum of the input values

static inline ulong  idx_min3(const Type &x, const Type &y, const Type &z);
// Return index (0,1, or 2) of minimum of the input values

static inline ulong  idx_max3(const Type &x, const Type &y, const Type &z);
// Return index (0,1, or 2) of maximum of the input values

static inline void  idx_minmax3(Type x0, Type x1, Type x2, ulong &i, ulong &a);
// set i, a to index (0,1, or 2) of min and max, resp.
//.
// jjtodo: optimize

static inline ulong  idx_median3(const Type &x, const Type &y, const Type &z);
// Return index (0,1, or 2) of median of the input values

// ========== HEADER FILE src/sort/minmaxptr.h: ==========

Type ptr_min(/*const Type *f,*/ ulong n, Type const*const*x);
// Return minimum (value) of array elements
//   {*x[0], *x[1], ..., *x[n-1]}

Type ptr_max(/*const Type *f,*/ ulong n, Type const*const*x);
// Return maximum (value) of array elements
//   {*x[0], *x[1], ..., *x[n-1]}

bool is_ptr_partitioned(/*const Type *f,*/ ulong n, Type const*const*x, ulong k);

// ========== HEADER FILE src/sort/minmaxptrfunc.h: ==========

Type ptr_min(/*const Type *f,*/ ulong n, Type const*const*x,;
             int (*cmp)(const Type &, const Type &))
// Return minimum (value) of array elements
//   {*x[0], *x[1], ..., *x[n-1]}
// with respect to comparison function cmp().

Type ptr_max(/*const Type *f,*/ ulong n, Type const*const*x,;
             int (*cmp)(const Type &, const Type &))
// Return maximum (value) of array elements
//   {*x[0], *x[1], ..., *x[n-1]}
// with respect to comparison function cmp().
// Note that f is a dummy argument.

bool is_ptr_partitioned(/*const Type *f,*/ ulong n, Type const*const*x, ulong k,;
                        int (*cmp)(const Type &, const Type &))

// ========== HEADER FILE src/sort/monotone.h: ==========

int is_monotone(const Type *f, ulong n);
// Return
//   +1 for ascending order
//   -1 for descending order
//   else 0
// Note: a constant sequence is also monotone

int is_strictly_monotone(const Type *f, ulong n);
// Return
//   +1 for strictly ascending order
//   -1 for strictly descending order
//   else 0

// ========== HEADER FILE src/sort/quantize.h: ==========

void quantize(Type *f, ulong n, double q);
// In f[] set each element x to q*floor(1/q*(x+q/2))
// E.g.: q=1 ==> round to nearest integer
//       q=1/1000 ==> round to nearest multiple of 1/1000
// For inexact types (float or double).

// ========== HEADER FILE src/sort/radixsort.h: ==========

// ----- SRCFILE=src/sort/radixsort.cc: -----
bool is_counting_sorted(const ulong *f, ulong n, ulong b0, ulong m);
// Whether f[] is sorted wrt. bits b0,...,b0+z-1
//  where z is the number of bits set in m.
// m must contain a single run of bits starting at bit zero.

void counting_sort_core(const ulong * restrict f, ulong n, ulong * restrict g, ulong b0, ulong m);
// Write to g[] the array f[] sorted wrt. bits b0,...,b0+z-1
//  where z is the number of bits set in m.
// m must contain a single run of bits starting at bit zero.

void radix_sort(ulong *f, ulong n);

// ========== HEADER FILE src/sort/sort.h: ==========

bool is_sorted(const Type *f, ulong n);
// Return whether the sequence f[0], f[1], ..., f[n-1] is ascending.

bool is_falling(const Type *f, ulong n);
// Return whether the sequence f[0], f[1], ..., f[n-1] is descending.

void selection_sort(Type *f, ulong n);
// Sort f[] (ascending order).
// Algorithm is O(n*n), use for short arrays only.

bool is_partitioned(const Type *f, ulong n, ulong k);
// Return whether
//  max(f[0], ..., f[p]) <= min(f[p+1], ..., f[n-1])

ulong partition(Type *f, ulong n);
// Rearrange array, so that for some index p
// max(f[0], ..., f[p]) <= min(f[p+1], ..., f[n-1])

void quick_sort(Type *f, ulong n);
// Sort f[] (ascending order).

// ========== HEADER FILE src/sort/sort23.h: ==========

// Sorting 2 or 3 elements
static inline void sort2(Type &x1, Type &x2);
// sort x1, x2

static inline void sort3(Type &x0, Type &x1, Type &x2);
// sort x0, x1, x2
//{ sort2(x0,x1); sort2(x1,x2); sort2(x0,x1); }

// ========== HEADER FILE src/sort/sort23func.h: ==========

// Sorting 2 or 3 elements, with comparison function
inline void sort2(Type &x1, Type &x2,;
                  int (*cmp)(const Type &, const Type &))
// sort x1, x2 wrt. cmp()

inline void sort3(Type &x0, Type &x1, Type &x2,;
                  int (*cmp)(const Type &, const Type &))
// sort x0, x1, x2
// =^= { sort2(x0,x1); sort2(x1,x2); sort2(x0,x1); }

// ========== HEADER FILE src/sort/sortbykey.h: ==========

void sort_by_key(Type1 *f, ulong n, Type2 *key, ulong *tmp=0, bool skq=true);
// Sort f[] according to key[] in ascending order:
//   f[k] precedes f[j] if key[k]<key[j].
// If skq is true then key[] is also sorted.
//
// Example:
// Input: (elements of f[] as bit strings):
//    f[]  key[]
//    ...   0
//    ..1   1
//    .1.   1
//    .11   3
//    1..   1
//    1.1   3
//    11.   3
//    111   7
// After sort_by_key(f, n, key, 1):
//    ...   0
//    1..   1
//    .1.   1
//    ..1   1
//    .11   3
//    1.1   3
//    11.   3
//    111   7

// ========== HEADER FILE src/sort/sortfunc.h: ==========

bool is_sorted(const Type *f, ulong n, int (*cmp)(const Type &, const Type &));
// Return whether the sequence f[0], f[1], ..., f[n-1]
// is sorted in ascending order with respect to comparison function cmp().

void selection_sort(Type *f, ulong n, int (*cmp)(const Type &, const Type &));
// Sort f[] (ascending order) with respect to comparison function cmp().
// Algorithm is O(n*n), use for short arrays only.

ulong partition(Type *f, ulong n, int (*cmp)(const Type &, const Type &));
// rearrange array, so that for some index p
// max(f[0] ... f[p]) <= min(f[p+1] ... f[n-1]).
// min(), max() taken with respect to comparison function cmp().

void quick_sort(Type *f, ulong n, int (*cmp)(const Type &, const Type &));
// Sort f[] (ascending order)
// with respect to comparison function cmp().

// ========== HEADER FILE src/sort/sortidx.h: ==========

bool is_idx_sorted(const Type *f, ulong n, const ulong *x);
// Return whether the sequence f[x[0]], f[x[1]], ... f[x[n-1]] ascending.

void idx_selection_sort(const Type *f, ulong n, ulong *x);
// Sort x[] so that the sequence f[x[0]], f[x[1]], ... f[x[n-1]] ascending.
// Algorithm is O(n*n), use for short arrays only.

ulong idx_partition(const Type *f, ulong n, ulong *x);
// rearrange index array, so that for some index p
// max(f[x[0]] ... f[x[p]]) <= min(f[x[p+1]] ... f[x[n-1]])

void idx_quick_sort(const Type *f, ulong n, ulong *x);
// Sort x[] so that the sequence f[x[0]], f[x[1]], ... f[x[n-1]] is ascending.

// ========== HEADER FILE src/sort/sortidxfunc.h: ==========

bool is_idx_sorted(const Type *f, ulong n, const ulong *x,;
                   int (*cmp)(const Type &, const Type &))
// Return whether the sequence f[x[0]], f[x[1]], ... f[x[n-1]] is ascending
// with respect to comparison function cmp().

void idx_selection_sort(const Type *f, ulong n, ulong *x,;
                        int (*cmp)(const Type &, const Type &))
// Sort x[] so that the sequence f[x[0]], f[x[1]], ... f[x[n-1]]
// is ascending with respect to comparison function cmp().
// Algorithm is O(n*n), use for short arrays only.

ulong idx_partition(const Type *f, ulong n, ulong *x,;
                    int (*cmp)(const Type &, const Type &))
// Rearrange index array, so that for some index p
// max(f[x[0]] ... f[x[p]]) <= min(f[x[p+1]] ... f[x[n-1]])
// with respect to comparison function cmp().

void idx_quick_sort(const Type *f, ulong n, ulong *x,;
                    int (*cmp)(const Type &, const Type &))
// Sort x[] so that the sequence f[x[0]], f[x[1]], ... f[x[n-1]]
// is ascending with respect to comparison function cmp().

// ========== HEADER FILE src/sort/sortptr.h: ==========

bool is_ptr_sorted(/*const Type *f,*/ ulong n, Type const*const*x);
// Return whether the sequence *x[0], *x[1], ..., *x[n-1] is ascending.

void ptr_selection_sort(/*const Type *f,*/ ulong n, const Type **x);
// Sort x[] so that the sequence *x[0], *x[1], ..., *x[n-1] is ascending.
// Algorithm is O(n*n), use for short arrays only.

ulong ptr_partition(/*const Type *f,*/ ulong n, const Type **x);
// rearrange index array, so that for some index p
// max(f[x[0]], ..., f[x[p]]) <= min(f[x[p+1]], ..., f[x[n-1]]).

void ptr_quick_sort(/*const Type *f,*/ ulong n, const Type **x);
// Sort x[] so that the sequence *x[0], *x[1], ..., *x[n-1] is ascending.

// ========== HEADER FILE src/sort/sortptrfunc.h: ==========

bool is_ptr_sorted(/*const Type *f,*/ ulong n, Type const*const*x,;
                   int (*cmp)(const Type &, const Type &))
// Return whether the sequence *x[0], *x[1], ..., *x[n-1]
// is ascending with respect to comparison function cmp().

void ptr_selection_sort(/*const Type *f,*/ ulong n, const Type **x,;
                        int (*cmp)(const Type &, const Type &))
// Sort x[] so that the sequence *x[0], *x[1], ..., *x[n-1]
// is ascending with respect to comparison function cmp().
// Algorithm is O(n*n), use for short arrays only.

ulong ptr_partition(/*const Type *f,*/ ulong n, const Type **x,;
                    int (*cmp)(const Type &, const Type &))
// Rearrange index array, so that for some index p
// max(*x[0], ..., *x[p]) <= min(*x[p+1], ..., *x[n-1]).
// min(), max() taken with respect to comparison function cmp().

void ptr_quick_sort(/*const Type *f,*/ ulong n, const Type **x,;
                    int (*cmp)(const Type &, const Type &))
// Sort x[] so that the sequence *x[0], *x[1], ..., *x[n-1]
// is ascending with respect to comparison function cmp().

// ========== HEADER FILE src/sort/unique.h: ==========

ulong test_unique(const Type *f, ulong n);
// For a sorted array test whether all values are unique
//   (i.e. whether no value is repeated).
// Return 0 if all values are unique else return index of the second
// element in the first pair found.

ulong is_unique(const Type *f, ulong n);
// For a sorted array test whether all values are unique
//
// Return true if all values are unique, else return false.

ulong count_unique(const Type *f, ulong n);
// For a sorted array return the number of unique values
// the number of (not necessarily distinct) repeated
//   values is n - unique_count(f, n);

ulong unique(Type *f, ulong n);
// For a sorted array squeeze all repeated values
// and return the number of unique values.
// Example:  [1, 3, 3, 4, 5, 8, 8] --> [1, 3, 4, 5, 8]
// The routine also works for unsorted arrays as long
// as identical elements only appear in contiguous blocks.
// Example: [4, 4, 3, 7, 7] --> [4, 3, 7]
// The order is preserved.

// ========== HEADER FILE src/sort/usearch.h: ==========

inline ulong first_eq_idx(const Type *f, ulong n, Type v);
// Return index of first element == v
// Return n if all !=v

inline ulong first_eq_idx_large(const Type *f, ulong n, Type v);
// Return index of first element == v
// Return n if all !=v
// Unrolled version for large arrays.

inline ulong first_neq_idx(const Type *f, ulong n, Type v);
// Return index of first element != v
// Return n if all ==v

inline ulong first_geq_idx(const Type *f, ulong n, Type v);
// Return index of first element >=v
// Return n if no such element is found

inline ulong first_leq_idx(const Type *f, ulong n, Type v);
// Return index of first element <=v
// Return n if no such element is found

inline ulong last_eq_idx(const Type *f, ulong n, Type v);
// Return index of last element == v
// Return n if all !=v

inline ulong last_neq_idx(const Type *f, ulong n, Type v);
// Return index of last element != v
// Return n if all ==v

inline ulong last_geq_idx(const Type *f, ulong n, Type v);
// Return index of last element >= v
// Return n if all <v

inline ulong last_leq_idx(const Type *f, ulong n, Type v);
// Return index of last element <= v
// Return n if all >v