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

This is a submodule of mir.ndslice.
It contains basic multidimensional iteration algorithms.

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

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

//| 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!fmuladd;
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.
// LDC is LLVM D Compiler
version(LDC)
    import ldc.intrinsics : fmax = llvm_maxnum, fmin = llvm_minnum;
// std.math prevents vectorization for now
else
    import std.math : fmax, fmin;
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 find(alias pred)
Finds a backward index for which pred(slices[0].backward(index), ..., slices[$-1].backward(index)) equals 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:
The variable passing by reference to be filled with the multidimensional backward index for which 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)
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 && 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)
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 && 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.
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(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.