Traits
Methods to manipulate indices of Vec<usize> type.
Functions
Binary search of an explicitly sorted list in ascending order. Returns an index of the first item that is greater than val. When none are greater, returns s.len() (invalid index but logical). The complement index (the result subtracted from s.len()), gives the first item in descending order that is not greater than val. Note that both complements of binsearch and binsearchdesc, in their respective opposite orderings, refer to the same preceding item iff there exists precisely one item equal to val. However, there can be more than one such items or none. Example use: looking up cummulative probability density functions.
Binary search of an explicitly sorted list in descending order. Returns an index of the first item that is smaller than val. When none are smaller, returns s.len() (invalid index but logical). The complement index (the result subtracted from s.len()), gives the first item in ascending order that is not smaller than val. Note that both complements of binsearch and binsearchdesc, in their respective opposite orderings, refer to the same preceding item iff there exists precisely one item equal to val. However, there can be more than one such items or none. Example use: looking up cummulative probability density functions.
Sets difference: deleting elements of the second from the first. Two ascending explicitly sorted generic vectors.
Sets difference: deleting elements of the second from the first. Two ascending index sorted generic vectors.
Intersects two ascending explicitly sorted generic vectors.
Intersects two ascending index-sorted generic vectors. Returns a single explicitly ordered set.
Maximum value T of slice &[T]
Finds the first occurence of item m in slice s by full iteration.
Returns Some(index) to the slice or None (when it has gone to the end).
Note that it uses only partial order and thus accepts any item that is neither
greater nor smaller than m (equality by default).
Suitable for small unordered sets.
For longer lists or repeated membership tests, it is better to
index sort them and then use faster binary memsearch (see below).
Binary search of an explicitly sorted list (in ascending order).
Returns Some(index) of any item that is
neither smaller nor greater than val.
When none are found, returns None.
Example use: membership of an ascending ordered set.
Binary search of an indexed list (in ascending order).
Returns Some(index) of any item that is
neither smaller nor greater than val.
When none are found, returns None.
Example use: membership of an indexed ordered set.
Binary search of an explicitly sorted list (in descending order).
Returns Some(index) of any item that is
neither smaller nor greater than val.
When none are found, returns None.
Example use: membership of an descending ordered set.
Binary search of an indexed list (in descending order).
Returns Some(index) of any item that is
neither smaller nor greater than val.
When none are found, returns None.
Example use: membership of an indexed descending set.
Merges two ascending sorted generic vectors, by classical selection and copying of their head items into the result. Consider using merge_indexed instead, especially for non-primitive end types T.
Merges two ascending sort indices. Data is not shuffled at all, v2 is just concatenated onto v1 in one go and both remain in their original order. Returns the concatenated vector and a new valid sort index into it.
Doubly recursive non-destructive merge sort.
The data is not moved or mutated.
Efficiency is comparable to quicksort.
Returns a vector of indices to s from i to i+n,
such that the indexed values are in ascending sort order (a sort index).
Only the index values are being moved.
Minimum, minimum’s first index, maximum, maximum’s first index
Minimum and maximum (T,T) of a slice &[T]
Minimum value T of slice &[T]
Counts occurrences of val, using previously obtained
ascending explicit sort sasc and descending sort sdesc.
This is to facilitate counting of many
different values without ever having to repeat the sorting.
This function is very efficient at counting
numerous repetitions in large sets (e.g. probabilities in stats).
Binary search from both ends is deployed: O(2log(n)).
Fast ranking of many T items, with only n*(log(n)+1) complexity.
Ranking is done by inverting the sort index.
Sort index is in sorted order, giving data positions.
Ranking is in data order, giving sorted order positions.
Thus sort index and ranks are in an inverse relationship.
They are easily converted by .invindex() (for: invert index).
Reverse a generic slice by reverse iteration. Creates a new Vec. Its naive use for descending sort etc. is to be avoided for efficiency reasons.
Removes repetitions from an explicitly ordered set.
A wrapper for mergesort, to obtain the sort index of the (whole) input vector. Simpler than sortm.
Immutable sort. Returns new sorted vector (ascending or descending). Is a wrapper for mergesort. Passes the boolean flag ‘ascending’ onto ‘unindex’. Mergesort by itself always produces only an ascending index.
Unites two ascending explicitly sorted generic vectors, by classical selection and copying of their head items into the result. This is the union of two ordered sets.
Unites two ascending index-sorted generic vectors. This is the union of two index ordered sets. Returns a single explicitly ordered set.