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 = [1, 2, 4, 3].sliced;
auto data = [2.1, 3.4, 5.6, 7.8].sliced;
auto series = index.series(data);
series.sort;
assert(series.index == [1, 2, 3, 4]);
assert(series.data == [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 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.
See Also:
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 .. $];
size_t transitionIndex(Iterator, SliceKind kind, V)(scope Slice!(Iterator, 1, kind) slice, V v);
Parameters:
Slice!(Iterator, 1, kind) slice sorted one-dimensional slice.
V v value to test with. It is passed to second argument.
size_t transitionIndex(T, V)(scope T[] ar, V v);
Parameters:
T[] ar sorted 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)(scope 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);