mir.ndslice.sorting

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);

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);

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:

flattened .

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:

transitionIndex.

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:

transitionIndex.

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.

See Also:

assumeSortedEqualIndex .

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.

Can be combined with indexed  to create a view that is sorted based on the index.

Parameters:

less	The comparison to use.
Slice!(Iterator, 1, kind) r	The slice/array to index.

Returns:

Index slice/array.

See Also:

numpy.argsort

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);

Examples:

Sort based on index created from a separate array

import mir.algorithm.iteration: equal;
import mir.ndslice.topology: indexed;

immutable arr0 = [ 2, 3, 1, 5,  0 ];
immutable arr1 = [ 1, 5, 4, 2, -1 ];

auto index = makeIndex(arr0);
assert(index.equal([4, 2, 0, 1, 3]));
auto view = arr1.indexed(index);
assert(view.equal([-1, 4, 1, 5, 2]));

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 algorithm that is implemented in the topN function in D's standard library (as of version 2.092.0).

Parameters:

less	The predicate to sort by.

See Also:

pivotPartition, https://erdani.com/research/sea2017.pdf

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.