// -*- 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(const Type *f, ulong n); // Return index of maximum for strictly convex sequence, // otherwise return 0. // "strictly convex" means "strongly unimodal" and there // is at least one upstep and downstep in the sequence. ulong test_strictly_concave(const Type *f, ulong n); // Return index of minimum for strictly concave sequence, // otherwise return 0 bool is_strictly_convex(const Type *f, ulong n); bool is_strictly_concave(const Type *f, ulong n); bool is_weakly_convex(const Type *f, ulong n); // Return whether sequence is weakly convex (weakly unimodal). bool is_weakly_concave(const 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(const 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 >= 1 and nb >= 1 void merge_sort_rec(Type *f, ulong n, Type *t); void merge_sort(Type *f, ulong n, Type *tmp=nullptr); void merge_sort_rec4(Type *f, ulong n, Type *t); void merge_sort4(Type *f, ulong n, Type *tmp=nullptr); // ========== 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() const Type *median3_ptr(const Type *x, const Type *y, const Type *z,; int (*cmp)(const Type &, const Type &)) // Return (pointer to) median of the input values wrt. cmp() // ========== 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. //. // todo: 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(). 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/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 sorted in // ascending (indeed non-decreasing) order. bool is_sorted_desc(const Type *f, ulong n); // Return whether the sequence f[0], f[1], ..., f[n-1] is sorted in // descending (indeed non-increasing) order. 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=nullptr, bool skq=true); // Sort f[] according to key[] in ascending order: // f[k] precedes f[j] if key[k] [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/uniquefunc.h: ========== ulong test_unique(const Type *f, ulong n, int (*cmp)(const Type &, const Type &)); // 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. bool is_unique(const Type *f, ulong n, int (*cmp)(const Type &, const Type &)); // 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, int (*cmp)(const Type &, const Type &)); // 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, int (*cmp)(const Type &, const Type &)); // 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 bool u_unique(const Type *f, ulong n); // Return whether elements in unordered array f[] are unique. // Algorithm is O(n^2), so use for small n only.