Report a bug
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.

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.
Examples:
```import mir.algorithm.iteration: all;
import mir.ndslice.slice;
import mir.ndslice.sorting: sort;
import mir.ndslice.topology: pairwise;

int 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 one-dimensional series.
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.
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.
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 indexes, 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);
```