Report a bug
If you spot a problem with this page, click here to create a GitHub issue.
Improve this page
Quickly fork, edit online, and submit a pull request for this page. Requires a signed-in GitHub account. This works well for small changes. If you'd like to make larger changes you may want to consider using a local clone.

mir.ndslice.sorting

This is a submodule of mir.ndslice.

Note The combination of pairwise  with lambda "a <= b" ("a < b") and all  can be used to check if an ndslice is sorted (strictly monotonic). topology iota  can be used to make an index. topology map  and topology zip  can be used to create Schwartzian transform. See also the examples in the module.

See Also:
flattened 
isSorted and isStrictlyMonotonic
Authors:
Andrei Alexandrescu (Phobos), Ilya Yaroshenko (API, rework, Mir adoptation)
Examples:
Check if ndslice is sorted, or strictly monotonic.
import mir.algorithm.iteration: all;
import mir.ndslice.slice: sliced;
import mir.ndslice.sorting: sort;
import mir.ndslice.topology: pairwise;

auto arr = [1, 1, 2].sliced;

assert(arr.pairwise!"a <= b".all);
assert(!arr.pairwise!"a < b".all);

arr = [4, 3, 2, 1].sliced;

assert(!arr.pairwise!"a <= b".all);
assert(!arr.pairwise!"a < b".all);

sort(arr);

assert(arr.pairwise!"a <= b".all);
assert(arr.pairwise!"a < b".all);
Examples:
Create index
import mir.algorithm.iteration: all;
import mir.ndslice.allocation: slice;
import mir.ndslice.slice: sliced;
import mir.ndslice.sorting: sort;
import mir.ndslice.topology: iota, pairwise;

auto arr = [4, 2, 3, 1].sliced;

auto index = arr.length.iota.slice;
index.sort!((a, b) => arr[a] < arr[b]);

assert(arr[index].pairwise!"a <= b".all);
Examples:
Schwartzian transform
import mir.algorithm.iteration: all;
import mir.ndslice.allocation: slice;
import mir.ndslice.slice: sliced;
import mir.ndslice.sorting: sort;
import mir.ndslice.topology: zip, map, pairwise;

alias transform = (a) => (a - 3) ^^ 2;

auto arr = [4, 2, 3, 1].sliced;

arr.map!transform.slice.zip(arr).sort!((l, r) => l.a < r.a);

assert(arr.map!transform.pairwise!"a <= b".all);
template sort(alias less = "a < b")
Sorts ndslice, array, or series.
See Also:
Examples:
import mir.algorithm.iteration: all;
import mir.ndslice.slice;
import mir.ndslice.sorting: sort;
import mir.ndslice.topology: pairwise;

int[10] arr = [7,1,3,2,9,0,5,4,8,6];

auto data = arr[].sliced(arr.length);
data.sort();
assert(data.pairwise!"a <= b".all);
Examples:
one-dimensional series
import mir.series;

auto index = [4, 2, 1, 3, 0].sliced;
auto data = [5.6, 3.4, 2.1, 7.8, 0.1].sliced;
auto series = index.series(data);
series.sort;
assert(series.index == [0, 1, 2, 3, 4]);
assert(series.data == [0.1, 2.1, 3.4, 7.8, 5.6]);
/// initial index and data are the same
assert(index.iterator is series.index.iterator);
assert(data.iterator is series.data.iterator);

foreach(obs; series)
{
    static assert(is(typeof(obs) == Observation!(int, double)));
}
Examples:
two-dimensional series
import mir.series;
import mir.ndslice.allocation: uninitSlice;

auto index = [4, 2, 3, 1].sliced;
auto data =
    [2.1, 3.4, 
     5.6, 7.8,
     3.9, 9.0,
     4.0, 2.0].sliced(4, 2);
auto series = index.series(data);

series.sort(
    uninitSlice!size_t(series.length), // index buffer
    uninitSlice!double(series.length), // data buffer
    );

assert(series.index == [1, 2, 3, 4]);
assert(series.data ==
    [[4.0, 2.0],
     [5.6, 7.8],
     [3.9, 9.0],
     [2.1, 3.4]]);
/// initial index and data are the same
assert(index.iterator is series.index.iterator);
assert(data.iterator is series.data.iterator);
Slice!(Iterator, N, kind) sort(Iterator, size_t N, SliceKind kind)(Slice!(Iterator, N, kind) slice);
Sort n-dimensional slice.
T[] sort(T)(T[] ar);
Sort for arrays
Series!(IndexIterator, Iterator, N, kind) sort(IndexIterator, Iterator, size_t N, SliceKind kind)(Series!(IndexIterator, Iterator, N, kind) series)
if (N == 1);
Sort for one-dimensional Series.
Series!(IndexIterator, Iterator, N, kind) sort(IndexIterator, Iterator, size_t N, SliceKind kind, SortIndexIterator, DataIterator)(Series!(IndexIterator, Iterator, N, kind) series, Slice!SortIndexIterator indexBuffer, Slice!DataIterator dataBuffer);
Sort for n-dimensional Series.
template assumeSortedContains(alias test = "a < b")
Returns:
true if a sorted array contains the value.
Parameters:
test strict ordering symmetric predicate
For non-symmetric predicates please use a structure with two opCalls or an alias of two global functions, that correponds to (array[i], value) and (value, array[i]) cases.
See Also:
bool assumeSortedContains(Iterator, SliceKind kind, V)(auto ref Slice!(Iterator, 1, kind) slice, auto ref scope const V v);

bool assumeSortedContains(T, V)(scope T[] ar, auto ref scope const V v);
Parameters:
Slice!(Iterator, 1, kind) slice sorted one-dimensional slice or array.
V v value to test with. It is passed to second argument.
template assumeSortedEqualIndex(alias test = "a < b")
Returns:
the smallest index of a sorted array such that the index corresponds to the arrays element at the index according to the predicate and -1 if the array doesn't contain corresponding element.
Parameters:
test strict ordering symmetric predicate.
For non-symmetric predicates please use a structure with two opCalls or an alias of two global functions, that correponds to (array[i], value) and (value, array[i]) cases.
See Also:
Examples:
// sorted: a < b
auto a = [0, 1, 2, 3, 4, 6];

assert(a.assumeSortedEqualIndex(2) == 2);
assert(a.assumeSortedEqualIndex(5) == -1);

// <= non strict predicates doesn't work
assert(a.assumeSortedEqualIndex!"a <= b"(2) == -1);
sizediff_t assumeSortedEqualIndex(Iterator, SliceKind kind, V)(auto ref Slice!(Iterator, 1, kind) slice, auto ref scope const V v);

sizediff_t assumeSortedEqualIndex(T, V)(scope T[] ar, auto ref scope const V v);
Parameters:
Slice!(Iterator, 1, kind) slice sorted one-dimensional slice or array.
V v value to test with. It is passed to second argument.
template transitionIndex(alias test = "a < b")
Computes transition index using binary search. It is low-level API for lower and upper bounds of a sorted array.
Parameters:
test ordering predicate for ((array[i], value)) pairs.
Examples:
// sorted: a < b
auto a = [0, 1, 2, 3, 4, 6];

auto i = a.transitionIndex(2);
assert(i == 2);
auto lowerBound = a[0 .. i];

auto j = a.transitionIndex!"a <= b"(2);
assert(j == 3);
auto upperBound = a[j .. $];

assert(a.transitionIndex(a[$-1]) == a.length - 1);
assert(a.transitionIndex!"a <= b"(a[$-1]) == a.length);
size_t transitionIndex(Iterator, SliceKind kind, V)(auto ref Slice!(Iterator, 1, kind) slice, auto ref scope const V v);

size_t transitionIndex(T, V)(scope T[] ar, auto ref scope const V v);
Parameters:
Slice!(Iterator, 1, kind) slice sorted one-dimensional slice or array.
V v value to test with. It is passed to second argument.
Slice!(I*) makeIndex(I = size_t, alias less = "a < b", Iterator, SliceKind kind)(Slice!(Iterator, 1, kind) r);
Computes an index for r based on the comparison less. The index is a sorted array of indices into the original range. This technique is similar to sorting, but it is more flexible because (1) it allows "sorting" of immutable collections, (2) allows binary search even if the original collection does not offer random access, (3) allows multiple indices, each on a different predicate, and (4) may be faster when dealing with large objects. However, using an index may also be slower under certain circumstances due to the extra indirection, and is always larger than a sorting-based solution because it needs space for the index in addition to the original collection. The complexity is the same as sort's.
Parameters:
less The comparison to use.
Slice!(Iterator, 1, kind) r The slice/array to index.
Returns:
Index slice/array.
I[] makeIndex(I = size_t, alias less = "a < b", T)(scope T[] r);
Examples:
import mir.algorithm.iteration: all;
import mir.ndslice.topology: indexed, pairwise;

immutable arr = [ 2, 3, 1, 5, 0 ];
auto index = arr.makeIndex;

assert(arr.indexed(index).pairwise!"a < b".all);
template pivotPartition(alias less = "a < b")
Partitions slice around pivot using comparison function less, algorithm akin to Hoare partition. Specifically, permutes elements of slice and returns an index k < slice.length such that:
  • slice[pivot] is swapped to slice[k]
  • All elements e in subrange slice[0 .. k] satisfy !less(slice[k], e) (i.e. slice[k] is greater than or equal to each element to its left according to predicate less)
  • All elements e in subrange slice[k .. $] satisfy !less(e, slice[k]) (i.e. slice[k] is less than or equal to each element to its right according to predicate less)
If slice contains equivalent elements, multiple permutations of slice may satisfy these constraints. In such cases, pivotPartition attempts to distribute equivalent elements fairly to the left and right of k such that k stays close to slice.length / 2.
Parameters:
less The predicate used for comparison
Returns:
The new position of the pivot
See Also:
Engineering of a Quicksort Partitioning Algorithm, D. Abhyankar, Journal of Global Research in Computer Science, February 2011. ACCU 2016 Keynote, Andrei Alexandrescu.
Examples:
pivotPartition with 1-dimensional Slice
import mir.ndslice.slice: sliced;
import mir.algorithm.iteration: all;

auto x = [5, 3, 2, 6, 4, 1, 3, 7].sliced;
size_t pivot = pivotPartition(x, x.length / 2);

assert(x[0 .. pivot].all!(a => a <= x[pivot]));
assert(x[pivot .. $].all!(a => a >= x[pivot]));
Examples:
pivotPartition with 2-dimensional Slice
import mir.ndslice.fuse: fuse;
import mir.ndslice.topology: flattened;
import mir.algorithm.iteration: all;

auto x = [
    [5, 3, 2, 6],
    [4, 1, 3, 7]
].fuse;

size_t pivot = pivotPartition(x, x.elementCount / 2);

auto xFlattened = x.flattened;
assert(xFlattened[0 .. pivot].all!(a => a <= xFlattened[pivot]));
assert(xFlattened[pivot .. $].all!(a => a >= xFlattened[pivot]));
size_t pivotPartition(Iterator, size_t N, SliceKind kind)(Slice!(Iterator, N, kind) slice, size_t pivot);
Parameters:
Slice!(Iterator, N, kind) slice slice being partitioned
size_t pivot The index of the pivot for partitioning, must be less than slice.length or 0 if slice.length is 0
template partitionAt(alias less = "a < b")
Partitions slice, such that all elements e1 from slice[0] to slice[nth] satisfy !less(slice[nth], e1), and all elements e2 from slice[nth] to slice[slice.length] satisfy !less(e2, slice[nth]). This effectively reorders slice such that slice[nth] refers to the element that would fall there if the range were fully sorted. Performs an expected Ο(slice.length) evaluations of less and swap, with a worst case of Ο(slice.length^^2).
This function implements the [Fast, Deterministic Selection](https://erdani.com/research/sea2017.pdf) algorithm that is implemented in the [topN](https://dlang.org/library/std/algorithm/sorting/top_n.html) function in D's standard library (as of version 2.092.0).
Parameters:
less The predicate to sort by.
Examples:
Partition 1-dimensional slice at nth
import mir.ndslice.slice: sliced;

size_t nth = 2;
auto x = [3, 1, 5, 2, 0].sliced;
x.partitionAt(nth);
assert(x[nth] == 2);
Examples:
Partition 2-dimensional slice
import mir.ndslice.slice: sliced;

size_t nth = 4;
auto x = [3, 1, 5, 2, 0, 7].sliced(3, 2);
x.partitionAt(nth);
assert(x[2, 0] == 5);
Examples:
Can supply alternate ordering function
import mir.ndslice.slice: sliced;

size_t nth = 2;
auto x = [3, 1, 5, 2, 0].sliced;
x.partitionAt!("a > b")(nth);
assert(x[nth] == 2);
nothrow @nogc @trusted void partitionAt(Iterator, size_t N, SliceKind kind)(Slice!(Iterator, N, kind) slice, size_t nth);
Parameters:
Slice!(Iterator, N, kind) slice n-dimensional slice
size_t nth The index of the element that should be in sorted position after the function is finished.