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.algorithm

Multidimensional iteration algorithms

This is a submodule of mir.ndslice.

Function

Function Name Description
all Checks if all elements satisfy to a predicate.
any Checks if at least one element satisfy to a predicate.
cmp Compares two slices.
count Counts elements in a slices according to a predicate.
each Iterates all elements.
equal Compares two slices for equality.
find Finds backward index.
findIndex Finds index.
isSymmetric Checks if the matrix is symmetric.
maxIndex Finds index of the maximum.
maxPos Finds backward index of the maximum.
minIndex Finds index of the minimum.
minmaxIndex Finds indexes of the minimum and the maximum.
minmaxPos Finds backward indexes of the minimum and the maximum.
minPos Finds backward index of the minimum.
reduce Accumulates all elements.
All operators are suitable to change slices using ref argument qualification in a function declaration. Note, that string lambdas in Mir are auto ref functions.
Authors:
Ilya Yaroshenko
template reduce(alias fun)
Implements the homonym function (also known as accumulate, compress, inject, or fold) present in various programming languages of functional flavor. The call reduce!(fun)(seed, slice1, ..., sliceN) first assigns seed to an internal variable result, also called the accumulator. Then, for each set of element x1, ..., xN in slice1, ..., sliceN, result = fun(result, x1, ..., xN) gets evaluated. Finally, result is returned.
reduce allows to iterate multiple slices in the lockstep.

Note: pack  can be used to specify dimensions.

Parameters:
fun A function.
Examples:
Single slice
import mir.ndslice.topology : iota;

//| 0 1 2 | => 3  |
//| 3 4 5 | => 12 | => 15
auto sl = iota(2, 3);

// sum of all element in the slice
auto res = size_t(0).reduce!"a + b"(sl);

assert(res == 15);
Examples:
Multiple slices, dot product
import mir.ndslice.allocation : slice;
import mir.ndslice.topology : as, iota;
import mir.ndslice.internal : fastmath;

//| 0 1 2 |
//| 3 4 5 |
auto a = iota([2, 3], 0).as!double.slice;
//| 1 2 3 |
//| 4 5 6 |
auto b = iota([2, 3], 1).as!double.slice;

alias dot = reduce!"a + b * c";
auto res = dot(0.0, a, b);

// check the result:
import mir.ndslice.topology : flattened;
import std.numeric : dotProduct;
assert(res == dotProduct(a.flattened, b.flattened));
Examples:
Zipped slices, dot product
import std.typecons : Yes;
import std.numeric : dotProduct;
import mir.ndslice.allocation : slice;
import mir.ndslice.topology : as, iota, zip, universal;
import mir.ndslice.internal : fastmath;

static @fastmath T fmuladd(T, Z)(const T a, Z z)
{
    return a + z.a * z.b;
}

// 0 1 2
// 3 4 5
auto sl1 = iota(2, 3).as!double.slice.universal;
// 1 2 3
// 4 5 6
auto sl2 = iota([2, 3], 1).as!double.slice;

// slices must have the same strides for `zip!true`.
assert(sl1.strides == sl2.strides);

auto z = zip!true(sl1, sl2);

auto dot = reduce!fmuladd(0.0, z);

assert(dot == dotProduct(iota(6), iota([6], 1)));
Examples:
Tensor mutation on-the-fly
import mir.ndslice.allocation : slice;
import mir.ndslice.topology : as, iota;
import mir.ndslice.internal : fastmath;

static @fastmath T fun(T)(const T a, ref T b)
{
    return a + b++;
}

//| 0 1 2 |
//| 3 4 5 |
auto sl = iota(2, 3).as!double.slice;

auto res = reduce!fun(double(0), sl);

assert(res == 15);

//| 1 2 3 |
//| 4 5 6 |
assert(sl == iota([2, 3], 1));
Examples:
Packed slices.
Computes minimum value of maximum values for each row.
import mir.math.common;
import mir.ndslice.allocation : slice;
import mir.ndslice.dynamic : transposed;
import mir.ndslice.topology : as, iota, pack, map, universal;

alias maxVal = (a) => reduce!fmax(-double.infinity, a);
alias minVal = (a) => reduce!fmin(double.infinity, a);
alias minimaxVal = (a) => minVal(a.pack!1.map!maxVal);

auto sl = iota(2, 3).as!double.slice;

// Vectorized computation: row stride equals 1.
//| 0 1 2 | => | 2 |
//| 3 4 5 | => | 5 | => 2
auto res = minimaxVal(sl);
assert(res == 2);

// Common computation: row stride does not equal 1.
//| 0 1 2 |    | 0 3 | => | 3 |
//| 3 4 5 | => | 1 4 | => | 4 |
//             | 2 5 | => | 5 | => 3
auto resT = minimaxVal(sl.universal.transposed);
assert(resT == 3);
auto reduce(S, Slices...)(S seed, Slices slices)
if (Slices.length && allSatisfy!(isSlice, Slices));
Parameters:
S seed An initial accumulation value.
Slices slices One or more slices.
Returns:
the accumulated result
template each(alias fun)
The call each!(fun)(slice1, ..., sliceN) evaluates fun for each set of elements x1, ..., xN in slice1, ..., sliceN respectively.
each allows to iterate multiple slices in the lockstep.
Parameters:
fun A function.

Note: transposed  and pack  can be used to specify dimensions.

See Also:
This is functionally similar to reduce but has not seed.
Examples:
Single slice, multiply-add
import mir.ndslice.allocation : slice;
import mir.ndslice.topology : as, iota;

//| 0 1 2 |
//| 3 4 5 |
auto sl = iota(2, 3).as!double.slice;

sl.each!((ref a) { a = a * 10 + 5; });

import std.stdio;
assert(sl ==
    [[ 5, 15, 25],
     [35, 45, 55]]);
Examples:
Swap two slices
import mir.utility : swap;
import mir.ndslice.allocation : slice;
import mir.ndslice.topology : as, iota;

//| 0 1 2 |
//| 3 4 5 |
auto a = iota([2, 3], 0).as!double.slice;
//| 10 11 12 |
//| 13 14 15 |
auto b = iota([2, 3], 10).as!double.slice;

each!swap(a, b);

assert(a == iota([2, 3], 10));
assert(b == iota([2, 3], 0));
Examples:
Swap two zipped slices
import mir.utility : swap;
import mir.ndslice.allocation : slice;
import mir.ndslice.topology : as, zip, iota;

//| 0 1 2 |
//| 3 4 5 |
auto a = iota([2, 3], 0).as!double.slice;
//| 10 11 12 |
//| 13 14 15 |
auto b = iota([2, 3], 10).as!double.slice;

auto z = zip(a, b);

z.each!(z => swap(z.a, z.b));

assert(a == iota([2, 3], 10));
assert(b == iota([2, 3], 0));
auto each(Slices...)(Slices slices)
if (Slices.length && allSatisfy!(isSlice, Slices));
Parameters:
Slices slices One or more slices.
template eachUploPair(alias fun)
The call eachUploPair!(fun)(matrix) evaluates fun for each pair (matrix[j, i], matrix[i, j]), i<=j.
Parameters:
fun A function.
Examples:
Transpose matrix in place.
import mir.ndslice.allocation: slice;
import mir.ndslice.topology: iota, universal;
import mir.ndslice.dynamic: transposed;
import mir.utility: swap;

auto m = iota(4, 4).slice;

m.eachUploPair!swap;

assert(m == iota(4, 4).universal.transposed);
Examples:
Reflect Upper matrix part to lower part.
import mir.ndslice.allocation: slice;
import mir.ndslice.topology: iota, universal;
import mir.ndslice.dynamic: transposed;
import mir.utility: swap;

// 0 1 2
// 3 4 5
// 6 7 8
auto m = iota(3, 3).slice;

m.eachUploPair!((u, ref l) { l = u; });

assert(m == [
    [0, 1, 2],
    [1, 4, 5],
    [2, 5, 8]]);
auto eachUploPair(SliceKind kind, Iterator)(Slice!(kind, [2], Iterator) matrix);
Parameters:
Slice!(kind, [2], Iterator) matrix Square matrix.
template isSymmetric(alias fun = "a == b")
Checks if the matrix is symmetric.
Examples:
import mir.ndslice.topology: iota;
assert(iota(2, 2).isSymmetric == false);

assert(
    [1, 2,
     2, 3].sliced(2, 2).isSymmetric == true);
bool isSymmetric(SliceKind kind, Iterator)(Slice!(kind, [2], Iterator) matrix);
Parameters:
Slice!(kind, [2], Iterator) matrix 2D ndslice.
template minmaxPos(alias pred = "a < b")
Finds a positions (ndslices) such that position[0].first is minimal and position[1].first is maximal elements in the slice.
Position is sub-ndslice of the same dimension in the right-)down-)etc(( corner.
Parameters:
pred A predicate.
Examples:
auto s = [
    2, 6, 4, -3,
    0, -4, -3, 3,
    -3, -2, 7, 2,
    ].sliced(3, 4);

auto pos = s.minmaxPos;

assert(pos[0] == s[$ - 2 .. $, $ - 3 .. $]);
assert(pos[1] == s[$ - 1 .. $, $ - 2 .. $]);

assert(pos[0].first == -4);
assert(s.backward(pos[0].shape) == -4);
assert(pos[1].first ==  7);
assert(s.backward(pos[1].shape) ==  7);
Slice!(kind == Contiguous && packs[0] > 1 ? Canonical : kind, packs, Iterator)[2] minmaxPos(SliceKind kind, size_t[] packs, Iterator)(Slice!(kind, packs, Iterator) slice);
Parameters:
Slice!(kind, packs, Iterator) slice ndslice.
Returns:
2 subslices with minimal and maximal first elements.
template minmaxIndex(alias pred = "a < b")
Finds a backward indexes such that slice[indexes[0]] is minimal and slice[indexes[1]] is maximal elements in the slice.
Parameters:
pred A predicate.
Examples:
auto s = [
    2, 6, 4, -3,
    0, -4, -3, 3,
    -3, -2, 7, 8,
    ].sliced(3, 4);

auto indexes = s.minmaxIndex;

assert(indexes == [[1, 1], [2, 3]]);
assert(s[indexes[0]] == -4);
assert(s[indexes[1]] ==  8);
size_t[packs[0]][2] minmaxIndex(SliceKind kind, size_t[] packs, Iterator)(Slice!(kind, packs, Iterator) slice);
Parameters:
Slice!(kind, packs, Iterator) slice ndslice.
Returns:
Subslice with minimal (maximal) first element.
template minPos(alias pred = "a < b")

template maxPos(alias pred = "a < b")
Finds a backward index such that slice.backward(index) is minimal(maximal).
Parameters:
pred A predicate.
Examples:
auto s = [
    2, 6, 4, -3,
    0, -4, -3, 3,
    -3, -2, 7, 2,
    ].sliced(3, 4);

auto pos = s.minPos;

assert(pos == s[$ - 2 .. $, $ - 3 .. $]);
assert(pos.first == -4);
assert(s.backward(pos.shape) == -4);

pos = s.maxPos;

assert(pos == s[$ - 1 .. $, $ - 2 .. $]);
assert(pos.first == 7);
assert(s.backward(pos.shape) == 7);
Slice!(kind == Contiguous && packs[0] > 1 ? Canonical : kind, packs, Iterator) minPos(SliceKind kind, size_t[] packs, Iterator)(Slice!(kind, packs, Iterator) slice);
Parameters:
Slice!(kind, packs, Iterator) slice ndslice.
Returns:
Multidimensional backward index such that element is minimal(maximal). Backward index equals zeros, if slice is empty.
template minIndex(alias pred = "a < b")

template maxIndex(alias pred = "a < b")
Finds an index such that slice[index] is minimal(maximal).
Parameters:
pred A predicate.
Examples:
auto s = [
    2, 6, 4, -3,
    0, -4, -3, 3,
    -3, -2, 7, 8,
    ].sliced(3, 4);

auto index = s.minIndex;

assert(index == [1, 1]);
assert(s[index] == -4);

index = s.maxIndex;

assert(index == [2, 3]);
assert(s[index] == 8);
Examples:
auto s = [
    -8, 6, 4, -3,
    0, -4, -3, 3,
    -3, -2, 7, 8,
    ].sliced(3, 4);

auto index = s.minIndex;

assert(index == [0, 0]);
assert(s[index] == -8);
size_t[packs[0]] minIndex(SliceKind kind, ptrdiff_t[] packs, Iterator)(Slice!(kind, packs, Iterator) slice);
Parameters:
Slice!(kind, packs, Iterator) slice ndslice.
Returns:
Multidimensional index such that element is minimal(maximal). Index elements equal to size_t.max, if slice is empty.
template findIndex(alias pred)
Finds an index such that pred(slices[0][index], ..., slices[$-1][index]) is true.
Parameters:
pred A predicate.
See Also:
Examples:
import mir.ndslice.topology : iota;
// 0 1 2
// 3 4 5
auto sl = iota(2, 3);
size_t[2] index = sl.findIndex!"a == 3";

assert(sl[index] == 3);

index = sl.findIndex!"a == 6";
assert(index[0] == size_t.max);
assert(index[1] == size_t.max);
size_t[isSlice!(Slices[0])[0]] findIndex(Slices...)(Slices slices)
if (Slices.length && allSatisfy!(isSlice, Slices));
Parameters:
Slices slices One or more slices.
Returns:
Multidimensional index such that the predicate is true. Index equals size_t.max, if the predicate evaluates false for all indexes.

Constraints: All slices must have the same shape.

template find(alias pred)
Finds a backward index such that pred(slices[0].backward(index), ..., slices[$-1].backward(index)) is true.
Parameters:
pred A predicate.

Optimization: To check if any element was found use the last dimension (row index). This will slightly optimize the code.

// $-1 instead of 0
if (backwardIndex[$-1])
{
    auto elem1 = slice1.backward(backwardIndex);
    //...
    auto elemK = sliceK.backward(backwardIndex);
}
else
{
    // not found
}

Examples:
import mir.ndslice.topology : iota;
// 0 1 2
// 3 4 5
auto sl = iota(2, 3);
size_t[2] bi = sl.find!"a == 3";
assert(sl.backward(bi) == 3);

bi = sl.find!"a == 6";
assert(bi[0] == 0);
assert(bi[1] == 0);
Examples:
Multiple slices
import mir.ndslice.topology : iota;

// 0 1 2
// 3 4 5
auto a = iota(2, 3);
// 10 11 12
// 13 14 15
auto b = iota([2, 3], 10);

size_t[2] bi = find!((a, b) => a * b == 39)(a, b);
assert(a.backward(bi) == 3);
assert(b.backward(bi) == 13);
Examples:
Zipped slices
import mir.ndslice.topology : iota, zip;

// 0 1 2
// 3 4 5
auto a = iota(2, 3);
// 10 11 12
// 13 14 15
auto b = iota([2, 3], 10);

size_t[2] bi = zip!true(a, b).find!"a.a * a.b == 39";

assert(a.backward(bi) == 3);
assert(b.backward(bi) == 13);
Examples:
Mutation on-the-fly
import mir.ndslice.allocation : slice;
import mir.ndslice.topology : as, iota;

// 0 1 2
// 3 4 5
auto sl = iota(2, 3).as!double.slice;

static bool pred(T)(ref T a)
{
    if (a == 5)
        return true;
    a = 8;
    return false;
}

size_t[2] bi = sl.find!pred;

assert(bi == [1, 1]);
assert(sl.backward(bi) == 5);

// sl was changed
assert(sl == [[8, 8, 8],
              [8, 8, 5]]);
size_t[isSlice!(Slices[0])[0]] find(Slices...)(Slices slices)
if (Slices.length && allSatisfy!(isSlice, Slices));
Parameters:
Slices slices One or more slices.
Returns:
Multidimensional backward index such that the predicate is true. Backward index equals zeros, if the predicate evaluates false for all indexes.

Constraints: All slices must have the same shape.

template any(alias pred = "a")
Like find, but only returns whether or not the search was successful.
Parameters:
pred The predicate.
Examples:
import mir.ndslice.topology : iota;
// 0 1 2
// 3 4 5
auto sl = iota(2, 3);

assert(sl.any!"a == 3");
assert(!sl.any!"a == 6");
Examples:
Multiple slices
import mir.ndslice.topology : iota;

// 0 1 2
// 3 4 5
auto a = iota(2, 3);
// 10 11 12
// 13 14 15
auto b = iota([2, 3], 10);

assert(any!((a, b) => a * b == 39)(a, b));
Examples:
Zipped slices
import mir.ndslice.topology : iota, zip;

// 0 1 2
// 3 4 5
auto a = iota(2, 3);
// 10 11 12
// 13 14 15
auto b = iota([2, 3], 10);

// slices must have the same strides

assert(zip!true(a, b).any!"a.a * a.b == 39");
Examples:
Mutation on-the-fly
import std.conv : to;
import mir.ndslice.allocation : slice;
import mir.ndslice.topology : as, iota;

// 0 1 2
// 3 4 5
auto sl = iota(2, 3).as!double.slice;

static bool pred(T)(ref T a)
{
    if (a == 5)
        return true;
    a = 8;
    return false;
}

assert(sl.any!pred);

// sl was changed
assert(sl == [[8, 8, 8],
              [8, 8, 5]]);
bool any(Slices...)(Slices slices)
if ((Slices.length == 1 || !__traits(isSame, pred, "a")) && Slices.length && allSatisfy!(isSlice, Slices));
Parameters:
Slices slices One or more slices.
Returns:
true if the search was successful and false otherwise.

Constraints: All slices must have the same shape.

template all(alias pred = "a")
Checks if all of the elements verify pred.
Parameters:
pred The predicate.
Examples:
import mir.ndslice.topology : iota;

// 0 1 2
// 3 4 5
auto sl = iota(2, 3);

assert(sl.all!"a < 6");
assert(!sl.all!"a < 5");
Examples:
Multiple slices
import mir.ndslice.topology : iota;

// 0 1 2
// 3 4 5
auto sl = iota(2, 3);

assert(all!"a - b == 0"(sl, sl));
Examples:
Zipped slices
import mir.ndslice.topology : iota, zip;

// 0 1 2
// 3 4 5
auto sl = iota(2, 3);


assert(zip!true(sl, sl).all!"a.a - a.b == 0");
Examples:
Mutation on-the-fly
import std.conv : to;
import mir.ndslice.allocation : slice;
import mir.ndslice.topology : as, iota;

// 0 1 2
// 3 4 5
auto sl = iota(2, 3).as!double.slice;

static bool pred(T)(ref T a)
{
    if (a < 4)
    {
        a = 8;
        return true;
    }
    return false;
}

assert(!sl.all!pred);

// sl was changed
assert(sl == [[8, 8, 8],
              [8, 4, 5]]);
bool all(Slices...)(Slices slices)
if ((Slices.length == 1 || !__traits(isSame, pred, "a")) && Slices.length && allSatisfy!(isSlice, Slices));
Parameters:
Slices slices One or more slices.
Returns:
true all of the elements verify pred and false otherwise.

Constraints: All slices must have the same shape.

template count(alias fun)
Counts elements in slices according to the fun.
Parameters:
fun A predicate.

Optimization: count!"a" has accelerated specialization for slices created with mir.ndslice.topology.bitwise.

Examples:
Single slice
import mir.ndslice.topology : iota;

//| 0 1 2 |
//| 3 4 5 |
auto sl = iota(2, 3);

assert(sl.count!"true" == 6);
assert(sl.count!"a" == 5);
assert(sl.count!"a % 2" == 3);
Examples:
Accelerated set bit count
import mir.ndslice.topology: iota, bitwise;
import mir.ndslice.allocation: slice;

//| 0 1 2 |
//| 3 4 5 |
auto sl = iota(2, 3).bitwise;

assert(sl.count!"true" == 6 * size_t.sizeof * 8);

// accelerated
assert(sl.count!"a" == 7);
assert(sl.slice.count!"a" == 7);

auto sl2 = iota!ubyte([6], 128).bitwise;
assert(sl2.count!"a" == 13);
assert(sl2[4 .. $].count!"a" == 13);
assert(sl2[4 .. $ - 1].count!"a" == 12);
assert(sl2[4 .. $ - 1].count!"a" == 12);
assert(sl2[41 .. $ - 1].count!"a" == 1);
size_t count(Slices...)(Slices slices)
if (Slices.length && allSatisfy!(isSlice, Slices));
Parameters:
Slices slices One or more slices.
Returns:
The number elements according to the fun.

Constraints: All slices must have the same shape.

template equal(alias pred)
Compares two or more slices for equality, as defined by predicate pred.
See Also:
Parameters:
pred The predicate.
Examples:
import mir.ndslice.allocation : slice;
import mir.ndslice.topology : iota;

// 0 1 2
// 3 4 5
auto sl1 = iota(2, 3);
// 1 2 3
// 4 5 6
auto sl2 = iota([2, 3], 1);

assert(equal!"a == b"(sl1, sl1));
assert(sl1 == sl1); //can also use opEquals for two Slices
assert(equal!"2 * a == b + c"(sl1, sl1, sl1));

assert(equal!"a < b"(sl1, sl2));

assert(!equal!"a == b"(sl1[0 .. $ - 1], sl1));
assert(!equal!"a == b"(sl1[0 .. $, 0 .. $ - 1], sl1));
bool equal(Slices...)(Slices slices)
if (Slices.length >= 2);
Parameters:
Slices slices Two or more slices.
Returns:
true any of the elements verify pred and false otherwise.
template cmp(alias pred = "a < b")
Performs three-way recursive lexicographical comparison on two slices according to predicate pred. Iterating sl1 and sl2 in lockstep, cmp compares each N-1 dimensional element e1 of sl1 with the corresponding element e2 in sl2 recursively. If one of the slices has been finished,cmp returns a negative value if sl1 has fewer elements than sl2, a positive value if sl1 has more elements than sl2, and 0 if the ranges have the same number of elements.
Parameters:
pred The predicate.
Examples:
import mir.ndslice.topology : iota;

// 0 1 2
// 3 4 5
auto sl1 = iota(2, 3);
// 1 2 3
// 4 5 6
auto sl2 = iota([2, 3], 1);

assert(cmp(sl1, sl1) == 0);
assert(cmp(sl1, sl2) < 0);
assert(cmp!"a >= b"(sl1, sl2) > 0);
ptrdiff_t cmp(SliceKind kindA, SliceKind kindB, size_t[] packsA, size_t[] packsB, IteratorA, IteratorB)(Slice!(kindA, packsA, IteratorA) sl1, Slice!(kindB, packsB, IteratorB) sl2)
if (packsA[0] == packsB[0]);
Parameters:
Slice!(kindA, packsA, IteratorA) sl1 First slice.
Slice!(kindB, packsB, IteratorB) sl2 Second slice.
Returns:
0 if both ranges compare equal. Negative value if the first differing element of sl1 is less than the corresponding element of sl2 according to pred. Positive value if the first differing element of sl2 is less than the corresponding element of sl1 according to pred.