std.algorithm.iteration

Это подмодуль std.algorithm. Он содержит общие алгоритмы итерации.

Лицензия:

Лицензия Boost 1.0.

Авторы:

Andrei Alexandrescu

Исходный код

std/algorithm/iteration.d

auto cache(Range)(Range range)
Constraints: if (isInputRange!Range);

auto cacheBidirectional(Range)(Range range)
Constraints: if (isBidirectionalRange!Range);

cache жадно вычисляет front range при каждом создании или вызове popFront, чтобы сохранить результат в кэше. Результат затем напрямую возвращается при вызове front, а не перевычисляется.

Это может быть полезная функция для размещения в цепочке после функций с дорогостоящими вычислениями, как ленивая альтернатива std.array.array. В частности, она может быть размещена после вызова map или перед вызовом std.range.filter или std.range.tee

cache может предоставить итерацию по двунаправленному диапазону, если это необходимо, но поскольку это сопряжено с дополнительными затратами, оно должно быть явно запрошено через вызов cacheBidirectional. Кроме того, двухсторонний кэш будет вычислять элемент «центра» дважды, когда в диапазоне останется только один элемент.

cache не предоставляет примитивов произвольного доступа, так как cache не сможет кэшировать произвольные обращения. Если Range предоставляет примитивы срезов, то cache будет предоставлять те же примитивы срезов, но hasSlicing!Cache не вернёт true (так как признак std.range.primitives.hasSlicing также проверяет произвольный доступ).

Параметры:

Range range

входной диапазон

Возвращает:

Входной диапазон с кэшированными значениями диапазона

Примеры:

import std.algorithm.comparison : equal;
import std.range, std.stdio;
import std.typecons : tuple;

ulong counter = 0;
double fun(int x)
{
    ++counter;
    // http://en.wikipedia.org/wiki/Quartic_function
    return ( (x + 4.0) * (x + 1.0) * (x - 1.0) * (x - 3.0) ) / 14.0 + 0.5;
}
// Without cache, with array (greedy)
auto result1 = iota(-4, 5).map!(a =>tuple(a, fun(a)))()
                         .filter!(a => a[1] < 0)()
                         .map!(a => a[0])()
                         .array();

// the values of x that have a negative y are:
assert(equal(result1, [-3, -2, 2]));

// Check how many times fun was evaluated.
// As many times as the number of items in both source and result.
writeln(counter); // iota(-4, 5).length + result1.length

counter = 0;
// Without array, with cache (lazy)
auto result2 = iota(-4, 5).map!(a =>tuple(a, fun(a)))()
                         .cache()
                         .filter!(a => a[1] < 0)()
                         .map!(a => a[0])();

// the values of x that have a negative y are:
assert(equal(result2, [-3, -2, 2]));

// Check how many times fun was evaluated.
// Only as many times as the number of items in source.
writeln(counter); // iota(-4, 5).length

Примеры:

Подсказка: cache жадно вычисляет элементы. Если вызов front для базового диапазона имеет побочный эффект, он будет наблюдаться до вызова front для фактического кэшированного диапазона. Кроме того, следует соблюдать осторожность при составлении cache с std.range.take. Разместив take перед cache, cache будет «осведомлён» о том, когда диапазон заканчивается, и корректно прекратит кэширование элементов при необходимости. Если вызов front не имеет побочных эффектов, размещение take после cache может привести к более быстрому диапазону. В любом случае, результирующие диапазоны будут эквивалентны, но возможно, не с теми же затратами или побочными эффектами.

import std.algorithm.comparison : equal;
import std.range;
int i = 0;

auto r = iota(0, 4).tee!((a){i = a;}, No.pipeOnPop);
auto r1 = r.take(3).cache();
auto r2 = r.cache().take(3);

assert(equal(r1, [0, 1, 2]));
assert(i == 2); //The last "seen" element was 2. The data in cache has been cleared.

assert(equal(r2, [0, 1, 2]));
assert(i == 3); //cache has accessed 3. It is still stored internally by cache.

template map(fun...) if (fun.length >= 1)

Реализует одноимённую функцию (также известную как transform) присутствующую во многих функциональных языках. Вызов map!(fun)(range) возвращает диапазон, элементы которого получаются путём применения fun(a) слева направо ко всем элементам a в range. Исходные диапазоны не изменяются. Вычисление выполняется лениво.

Параметры:

fun	одна или несколько функций преобразования

См. также:

Map (higher-order function)

Примеры:

import std.algorithm.comparison : equal;
import std.range : chain, only;
auto squares =
    chain(only(1, 2, 3, 4), only(5, 6)).map!(a => a * a);
assert(equal(squares, only(1, 4, 9, 16, 25, 36)));

Примеры:

Несколько функций могут быть переданы map. В этом случае тип элемента map — кортеж, содержащий по одному элементу для каждой функции.

auto sums = [2, 4, 6, 8];
auto products = [1, 4, 9, 16];

size_t i = 0;
foreach (result; [ 1, 2, 3, 4 ].map!("a + a", "a * a"))
{
    writeln(result[0]); // sums[i]
    writeln(result[1]); // products[i]
    ++i;
}

Примеры:

Вы можете использовать псевдоним map для некоторых функций(и) и использовать его отдельно:

import std.algorithm.comparison : equal;
import std.conv : to;

alias stringize = map!(to!string);
assert(equal(stringize([ 1, 2, 3, 4 ]), [ "1", "2", "3", "4" ]));

auto map(Range)(Range r)
Constraints: if (isInputRange!(Unqual!Range));

Параметры:

Range r

входной диапазон

Возвращает:

Диапазон с применением каждой fun ко всем элементам. Если есть более одной fun, тип элемента будет Tuple, содержащий по одному элементу для каждой fun.

template each(alias fun = "a")

Жадного перебирает r и вызывает fun над каждым элементом.

Если не указана функция для вызова, each по умолчанию ничего не делает, но потребляет весь диапазон. r.front будет вычислено, но этого можно избежать, указав лямбда-функцию с параметром lazy.

each также поддерживает типы на основе opApply, поэтому работает с, например, std.parallelism.parallel.

Обычно итерация выполняется по всему диапазону. Если требуется частичная итерация (преждевременная остановка), fun должен возвращать значение типа std.typecons.Flag!"each" (Yes.each для продолжения итерации или No.each для остановки итерации).

Параметры:

fun	функция для применения к каждому элементу диапазона
Range r	диапазон или итерируемый объект, по которому each итерируется

Возвращает:

Yes.each если весь диапазон был итерирован, No.each в случае преждевременной остановки.

См. также:

std.range.tee

Примеры:

import std.range : iota;
import std.typecons : Flag, Yes, No;

long[] arr;
iota(5).each!(n => arr ~= n);
writeln(arr); // [0, 1, 2, 3, 4]
iota(5).each!((n) { arr ~= n; return No.each; });
writeln(arr); // [0, 1, 2, 3, 4, 0]

// If the range supports it, the value can be mutated in place
arr.each!((ref n) => n++);
writeln(arr); // [1, 2, 3, 4, 5, 1]

arr.each!"a++";
writeln(arr); // [2, 3, 4, 5, 6, 2]

// by-ref lambdas are not allowed for non-ref ranges
static assert(!is(typeof(arr.map!(n => n).each!((ref n) => n++))));

// The default predicate consumes the range
auto m = arr.map!(n => n);
(&m).each();
assert(m.empty);

// Indexes are also available for in-place mutations
arr[] = 0;
arr.each!"a=i"();
writeln(arr); // [0, 1, 2, 3, 4, 5]

// opApply iterators work as well
static class S
{
    int x;
    int opApply(scope int delegate(ref int _x) dg) { return dg(x); }
}

auto s = new S;
s.each!"a++";
writeln(s.x); // 1

Примеры:

each работает с итерируемыми объектами, предоставляющими переменную индекса, вместе с каждым элементом

import std.range : iota, lockstep;

auto arr = [1, 2, 3, 4];

// 1 ref parameter
arr.each!((ref e) => e = 0);
writeln(arr.sum); // 0

// 1 ref parameter and index
arr.each!((i, ref e) => e = cast(int) i);
writeln(arr.sum); // 4.iota.sum

Flag!"each" each(Range)(Range r)
Constraints: if (!isForeachIterable!Range && (isRangeIterable!Range || __traits(compiles, typeof(r.front).length)));

Flag!"each" each(Iterable)(auto ref Iterable r)
Constraints: if (isForeachIterable!Iterable || __traits(compiles, Parameters!(Parameters!(r.opApply))));

Параметры:

Range r

диапазон или итерируемый объект, по которому each итерируется

template filter(alias predicate) if (is(typeof(unaryFun!predicate)))

Реализует функцию высшего порядка filter. Предикат передаётся в std.functional.unaryFun и может принимать строку или любой вызываемый объект, который можно выполнить через pred(element).

Параметры:

predicate

Функция для применения к каждому элементу диапазона

Возвращает:

filter!(predicate)(range) возвращает новый диапазон, содержащий только элементы x в range, для которых predicate(x) возвращает true.

См. также:

Filter (higher-order function)

Примеры:

import std.algorithm.comparison : equal;
import std.math : approxEqual;
import std.range;

int[] arr = [ 1, 2, 3, 4, 5 ];

// Filter below 3
auto small = filter!(a => a < 3)(arr);
assert(equal(small, [ 1, 2 ]));

// Filter again, but with Uniform Function Call Syntax (UFCS)
auto sum = arr.filter!(a => a < 3);
assert(equal(sum, [ 1, 2 ]));

// In combination with chain() to span multiple ranges
int[] a = [ 3, -2, 400 ];
int[] b = [ 100, -101, 102 ];
auto r = chain(a, b).filter!(a => a > 0);
assert(equal(r, [ 3, 400, 100, 102 ]));

// Mixing convertible types is fair game, too
double[] c = [ 2.5, 3.0 ];
auto r1 = chain(c, a, b).filter!(a => cast(int) a != a);
assert(approxEqual(r1, [ 2.5 ]));

auto filter(Range)(Range range)
Constraints: if (isInputRange!(Unqual!Range));

Параметры:

Range range

Входной диапазон элементов

Возвращает:

Диапазон, содержащий только элементы x в range, для которых predicate(x) возвращает true.

template filterBidirectional(alias pred)

Аналогично filter, за исключением того, что он определяет двунаправленный диапазон. Есть недостаток в скорости - конструктор тратит время на поиск последнего элемента в диапазоне, удовлетворяющего условию фильтрации (в дополнение к поиску первого). Преимущество заключается в том, что отфильтрованный диапазон можно обходить в обоих направлениях. Также к отфильтрованному диапазону можно применить std.range.retro.

Предикат передаётся в std.functional.unaryFun и может принимать строку или любой вызываемый объект, который можно выполнить через pred(element).

Параметры:

pred	Функция для применения к каждому элементу диапазона

Примеры:

import std.algorithm.comparison : equal;
import std.range;

int[] arr = [ 1, 2, 3, 4, 5 ];
auto small = filterBidirectional!("a < 3")(arr);
static assert(isBidirectionalRange!(typeof(small)));
writeln(small.back); // 2
assert(equal(small, [ 1, 2 ]));
assert(equal(retro(small), [ 2, 1 ]));
// In combination with chain() to span multiple ranges
int[] a = [ 3, -2, 400 ];
int[] b = [ 100, -101, 102 ];
auto r = filterBidirectional!("a > 0")(chain(a, b));
writeln(r.back); // 102

auto filterBidirectional(Range)(Range r)
Constraints: if (isBidirectionalRange!(Unqual!Range));

Параметры:

Range r

Двунаправленный диапазон элементов

Возвращает:

Диапазон, содержащий только элементы в r, для которых pred возвращает true.

Group!(pred, Range) group(alias pred = "a == b", Range)(Range r);

struct Group(alias pred, R) if (isInputRange!R);

Элементы, последовательно эквивалентные друг другу, объединяются в один кортеж, содержащий элемент и количество его повторений.

Аналогично uniq, group генерирует диапазон, который перебирает уникальные последовательные элементы заданного диапазона. Каждый элемент этого диапазона — это кортеж, содержащий элемент и количество его повторений в исходном диапазоне. Эквивалентность элементов оценивается с помощью предиката pred, который по умолчанию равен "a == b". Предикат передается в std.functional.binaryFun и может принимать строку или любой вызываемый объект, который может быть выполнен с помощью pred(element, element).

Параметры:

pred	Бинарный предикат для определения эквивалентности двух элементов.
R	Тип диапазона
Диапазон r	Вводной диапазон для итерации.

Возвращает:

Диапазон элементов типа Tuple!(ElementType!R, uint), представляющий каждый последовательно уникальный элемент и соответствующее количество его вхождений в данном ряду. Это будет диапазон ввода, если R является диапазоном ввода, и диапазон вперед во всех остальных случаях.

См. также:

chunkBy, который разбивает диапазон ввода на поддиапазоны эквивалентных смежных элементов.

Примеры:

import std.algorithm.comparison : equal;
import std.typecons : tuple, Tuple;

int[] arr = [ 1, 2, 2, 2, 2, 3, 4, 4, 4, 5 ];
assert(equal(group(arr), [ tuple(1, 1u), tuple(2, 4u), tuple(3, 1u),
    tuple(4, 3u), tuple(5, 1u) ][]));

Примеры:

Используя group, можно легко сгенерировать ассоциативный массив с количеством каждого уникального элемента в диапазоне.

import std.algorithm.sorting : sort;
import std.array : assocArray;

uint[string] result;
auto range = ["a", "b", "a", "c", "b", "c", "c", "d", "e"];
result = range.sort!((a, b) => a < b)
    .group
    .assocArray;

writeln(result); // ["a":2U, "b":2U, "c":3U, "d":1U, "e":1U]

auto chunkBy(alias pred, Range)(Range r)
Constraints: if (isInputRange!Range);

Разбивает диапазон ввода на поддиапазоны эквивалентных смежных элементов. В других языках это часто называется partitionBy, groupBy или sliceWhen.

Эквивалентность определяется предикатом pred, который может быть бинарным, передаваемым в std.functional.binaryFun, или унарным, передаваемым в std.functional.unaryFun. В бинарном виде два элемента диапазона a и b считаются эквивалентными, если pred(a,b) истинно. В унарном виде два элемента считаются эквивалентными, если pred(a) == pred(b) истинно.

Этот предикат должен быть отношением эквивалентности, то есть он должен быть рефлексивным (pred(x,x) всегда истинно), симметричным (pred(x,y) == pred(y,x)) и транзитивным (pred(x,y) && pred(y,z) подразумевает pred(x,z)). Если это не так, диапазон, возвращаемый chunkBy, может привести к ошибке во время выполнения или вести себя непредсказуемо.

Параметры:

pred	Предикат для определения эквивалентности.
Диапазон r	Вводной диапазон для разделения на поддиапазоны.

Возвращает:

При бинарном предикате возвращается диапазон диапазонов, в котором все элементы в данном поддиапазоне эквивалентны в соответствии с заданным предикатом. При унарном предикате возвращается диапазон кортежей, где кортеж состоит из результата унарного предиката для каждого поддиапазона и самого поддиапазона.

Примечания

Эквивалентные элементы, разделенные промежуточным неэквивалентным элементом, будут отображаться в отдельных поддиапазонах; эта функция учитывает только смежную эквивалентность. Элементы в поддиапазонах всегда будут отображаться в том же порядке, в котором они появляются в исходном диапазоне.

См. также:

group, который сводит смежные эквивалентные элементы в один элемент.

Примеры:

Использование с бинарным предикатом:

import std.algorithm.comparison : equal;

// Grouping by particular attribute of each element:
auto data = [
    [1, 1],
    [1, 2],
    [2, 2],
    [2, 3]
];

auto r1 = data.chunkBy!((a,b) => a[0] == b[0]);
assert(r1.equal!equal([
    [[1, 1], [1, 2]],
    [[2, 2], [2, 3]]
]));

auto r2 = data.chunkBy!((a,b) => a[1] == b[1]);
assert(r2.equal!equal([
    [[1, 1]],
    [[1, 2], [2, 2]],
    [[2, 3]]
]));

Примеры:

Использование с унарным предикатом:

import std.algorithm.comparison : equal;
import std.range.primitives;
import std.typecons : tuple;

// Grouping by particular attribute of each element:
auto range =
[
    [1, 1],
    [1, 1],
    [1, 2],
    [2, 2],
    [2, 3],
    [2, 3],
    [3, 3]
];

auto byX = chunkBy!(a => a[0])(range);
auto expected1 =
[
    tuple(1, [[1, 1], [1, 1], [1, 2]]),
    tuple(2, [[2, 2], [2, 3], [2, 3]]),
    tuple(3, [[3, 3]])
];
foreach (e; byX)
{
    assert(!expected1.empty);
    writeln(e[0]); // expected1.front[0]
    assert(e[1].equal(expected1.front[1]));
    expected1.popFront();
}

auto byY = chunkBy!(a => a[1])(range);
auto expected2 =
[
    tuple(1, [[1, 1], [1, 1]]),
    tuple(2, [[1, 2], [2, 2]]),
    tuple(3, [[2, 3], [2, 3], [3, 3]])
];
foreach (e; byY)
{
    assert(!expected2.empty);
    writeln(e[0]); // expected2.front[0]
    assert(e[1].equal(expected2.front[1]));
    expected2.popFront();
}

auto joiner(RoR, Separator)(RoR r, Separator sep)
Constraints: if (isInputRange!RoR && isInputRange!(ElementType!RoR) && isForwardRange!Separator && is(ElementType!Separator : ElementType!(ElementType!RoR)));

auto joiner(RoR)(RoR r)
Constraints: if (isInputRange!RoR && isInputRange!(ElementType!RoR));

Лениво объединяет диапазон диапазонов с разделителем. Сам разделитель — это диапазон. Если разделитель не указан, то диапазоны объединяются напрямую без чего-либо между ними (в других языках это часто называется flatten).

Параметры:

RoR r	Вводной диапазон диапазонов, которые нужно объединить.
Separator sep	Диапазон вперед элементов, которые будут служить разделителями в объединенном диапазоне.

Возвращает:

Диапазон элементов в объединенном диапазоне. Это будет диапазон вперед, если и внешний, и внутренний диапазоны RoR являются диапазонами вперед; в противном случае это будет только диапазон ввода. Направленность диапазона передается, если разделитель не указан.

См. также:

std.range.chain, который объединяет последовательность диапазонов с совместимыми элементами в один диапазон.

Примеры:

import std.algorithm.comparison : equal;
import std.conv : text;

assert(["abc", "def"].joiner.equal("abcdef"));
assert(["Mary", "has", "a", "little", "lamb"]
    .joiner("...")
    .equal("Mary...has...a...little...lamb"));
assert(["", "abc"].joiner("xyz").equal("xyzabc"));
assert([""].joiner("xyz").equal(""));
assert(["", ""].joiner("xyz").equal("xyz"));

Примеры:

import std.algorithm.comparison : equal;
import std.range : repeat;

assert([""].joiner.equal(""));
assert(["", ""].joiner.equal(""));
assert(["", "abc"].joiner.equal("abc"));
assert(["abc", ""].joiner.equal("abc"));
assert(["abc", "def"].joiner.equal("abcdef"));
assert(["Mary", "has", "a", "little", "lamb"].joiner.equal("Maryhasalittlelamb"));
assert("abc".repeat(3).joiner.equal("abcabcabc"));

Примеры:

joiner позволяет изменять значения на месте!

import std.algorithm.comparison : equal;
auto a = [ [1, 2, 3], [42, 43] ];
auto j = joiner(a);
j.front = 44;
writeln(a); // [[44, 2, 3], [42, 43]]
assert(equal(j, [44, 2, 3, 42, 43]));

Примеры:

Вставка символов полностью ленивым способом в строку

import std.algorithm.comparison : equal;
import std.range : chain, cycle, iota, only, retro, take, zip;
import std.format : format;

static immutable number = "12345678";
static immutable delimiter = ",";
auto formatted = number.retro
    .zip(3.iota.cycle.take(number.length))
    .map!(z => chain(z[0].only, z[1] == 2 ? delimiter : null))
    .joiner
    .retro;
static immutable expected = "12,345,678";
assert(formatted.equal(expected));

Примеры:

joiner может быть двунаправленным

import std.algorithm.comparison : equal;
import std.range : retro;

auto a = [[1, 2, 3], [4, 5]];
auto j = a.joiner;
j.back = 44;
writeln(a); // [[1, 2, 3], [4, 44]]
assert(equal(j.retro, [44, 4, 3, 2, 1]));

template reduce(fun...) if (fun.length >= 1)

Реализует одноименную функцию (также известную как accumulate, compress, inject, или foldl), присутствующую в различных функциональных языках программирования. Также существует fold, которая делает то же самое, но с обратным порядком параметров. Вызов reduce!(fun)(seed, range) сначала присваивает seed внутренней переменной result, также называемой аккумулятором. Затем для каждого элемента x в range вычисляется result = fun(result, x). Наконец, возвращается result. Версия с одним аргументом reduce!(fun)(range) работает аналогично, но использует первый элемент диапазона в качестве начального значения (диапазон должен быть непустым).

Возвращает:

накопленный result

Параметры:

fun	одна или несколько функций

См. также:

Fold (higher-order function) fold функционально эквивалентна reduce с обратным порядком аргументов и без необходимости использования tuple для нескольких начальных значений. Это упрощает использование в цепочках UFCS. sum аналогично reduce!((a, b) => a + b), которая предлагает попарное суммирование чисел с плавающей точкой.

Примеры:

Многие агрегатные операции с диапазонами оказываются легко решаемыми с помощью reduce. Приведенный ниже пример демонстрирует замечательную мощь и гибкость reduce.

import std.algorithm.comparison : max, min;
import std.math : approxEqual;
import std.range;

int[] arr = [ 1, 2, 3, 4, 5 ];
// Sum all elements
auto sum = reduce!((a,b) => a + b)(0, arr);
writeln(sum); // 15

// Sum again, using a string predicate with "a" and "b"
sum = reduce!"a + b"(0, arr);
writeln(sum); // 15

// Compute the maximum of all elements
auto largest = reduce!(max)(arr);
writeln(largest); // 5

// Max again, but with Uniform Function Call Syntax (UFCS)
largest = arr.reduce!(max);
writeln(largest); // 5

// Compute the number of odd elements
auto odds = reduce!((a,b) => a + (b & 1))(0, arr);
writeln(odds); // 3

// Compute the sum of squares
auto ssquares = reduce!((a,b) => a + b * b)(0, arr);
writeln(ssquares); // 55

// Chain multiple ranges into seed
int[] a = [ 3, 4 ];
int[] b = [ 100 ];
auto r = reduce!("a + b")(chain(a, b));
writeln(r); // 107

// Mixing convertible types is fair game, too
double[] c = [ 2.5, 3.0 ];
auto r1 = reduce!("a + b")(chain(a, b, c));
assert(approxEqual(r1, 112.5));

// To minimize nesting of parentheses, Uniform Function Call Syntax can be used
auto r2 = chain(a, b, c).reduce!("a + b");
assert(approxEqual(r2, 112.5));

Примеры:

Иногда очень полезно вычислить несколько агрегатов за один проход. Одно преимущество заключается в том, что вычисление быстрее, поскольку накладные расходы на циклы совместно используются. Именно поэтому reduce принимает несколько функций. Если переданы две или более функций, reduce возвращает объект std.typecons.Tuple с одним членом на каждую переданную функцию. Соответственно, количество начальных значений должно быть увеличено.

import std.algorithm.comparison : max, min;
import std.math : approxEqual, sqrt;
import std.typecons : tuple, Tuple;

double[] a = [ 3.0, 4, 7, 11, 3, 2, 5 ];
// Compute minimum and maximum in one pass
auto r = reduce!(min, max)(a);
// The type of r is Tuple!(int, int)
assert(approxEqual(r[0], 2));  // minimum
assert(approxEqual(r[1], 11)); // maximum

// Compute sum and sum of squares in one pass
r = reduce!("a + b", "a + b * b")(tuple(0.0, 0.0), a);
assert(approxEqual(r[0], 35));  // sum
assert(approxEqual(r[1], 233)); // sum of squares
// Compute average and standard deviation from the above
auto avg = r[0] / a.length;
writeln(avg); // 5
auto stdev = sqrt(r[1] / a.length - avg * avg);
writeln(cast(int)stdev); // 2

auto reduce(R)(R r)
Constraints: if (isIterable!R);

Версия без начального значения. Первый элемент r используется как значение начального значения.

Для каждой функции f в fun, соответствующий тип начального значения S равен Unqual!(typeof(f(e, e))), где e — элемент r: ElementType!R для диапазонов и ForeachType!R в противном случае.

После определения S, S s = e; и s = f(s, e); должны быть допустимы.

Параметры:

R r	Итерируемое значение, как определено в isIterable

Возвращает:

конечный результат применения аккумулятора к итерируемому объекту

Исключения:

Exception если r пуст

auto reduce(S, R)(S seed, R r)
Constraints: if (isIterable!R);

Версия с начальным значением. Начальное значение должно быть единственным значением, если fun — это одна функция. Если fun — это несколько функций, то seed должно быть объектом std.typecons.Tuple с одним полем на каждую функцию в f.

Для удобства, если начальное значение является константой или имеет квалифицированные поля, то reduce будет работать с неквалифицированной копией. Если это произойдет, возвращаемый тип не будет идеально соответствовать S.

Используйте fold вместо reduce для использования версии с начальным значением в цепочке UFCS.

Параметры:

S seed	Начальное значение аккумулятора
R r	Итерируемое значение, как определено в isIterable

Возвращает:

конечный результат применения аккумулятора к итерируемому объекту

template fold(fun...) if (fun.length >= 1)

Реализует одноимённую функцию (также известную как accumulate, compress, inject, или foldl) присутствующую в различных функциональных языках программирования. Вызов fold!(fun)(range, seed) сначала присваивает seed внутренней переменной result, также называемой аккумулятором. Затем, для каждого элемента x в range, вычисляется result = fun(result, x). Наконец, возвращается result. Версия с одним аргументом fold!(fun)(range) работает аналогично, но использует первый элемент диапазона в качестве начального значения (диапазон должен быть непустым).

Параметры:

fun	функция(и), применяемые к элементам

См. также:

Fold (функция высшего порядка) sum похожа на fold!((a, b) => a + b), которая обеспечивает точное суммирование чисел с плавающей точкой. Это функционально эквивалентно reduce с обратным порядком аргументов и без необходимости использования tuple для нескольких начальных значений.

Примеры:

immutable arr = [1, 2, 3, 4, 5];

// Sum all elements
writeln(arr.fold!((a, b) => a + b)); // 15

// Sum all elements with explicit seed
writeln(arr.fold!((a, b) => a + b)(6)); // 21

import std.algorithm.comparison : min, max;
import std.typecons : tuple;

// Compute minimum and maximum at the same time
writeln(arr.fold!(min, max)); // tuple(1, 5)

// Compute minimum and maximum at the same time with seeds
writeln(arr.fold!(min, max)(0, 7)); // tuple(0, 7)

// Can be used in a UFCS chain
writeln(arr.map!(a => a + 1).fold!((a, b) => a + b)); // 20

// Return the last element of any range
writeln(arr.fold!((a, b) => b)); // 5

auto fold(R, S...)(R r, S seed);

Параметры:

R r	входной диапазон для применения fold
S seed	начальное значение аккумулятора

Возвращает:

накопленное значение result

template cumulativeFold(fun...) if (fun.length >= 1)

Аналогично fold, но возвращает диапазон, содержащий последовательные уменьшенные значения. Вызов cumulativeFold!(fun)(range, seed) сначала присваивает seed внутренней переменной result, также называемой аккумулятором. Возвращаемый диапазон содержит значения result = fun(result, x) лениво вычисленные для каждого элемента x в range. Наконец, последний элемент имеет то же значение, что и fold!(fun)(seed, range). Версия с одним аргументом cumulativeFold!(fun)(range) работает аналогично, но возвращает первый элемент без изменений и использует его как начальное значение для последующих элементов. Эта функция также известна как partial_sum, accumulate, scan, Сумма накопленных значений.

Параметры:

fun	одна или несколько функций для использования в качестве операции fold

Возвращает:

Функция возвращает диапазон, содержащий последовательные уменьшенные значения. Если передано более одной fun, тип элемента будет std.typecons.Tuple содержащий один элемент для каждой fun.

См. также:

Префиксная сумма

Примечание

В функциональных языках программирования это обычно называется scan, scanl, scanLeft или reductions.

Примеры:

import std.algorithm.comparison : max, min;
import std.array : array;
import std.math : approxEqual;
import std.range : chain;

int[] arr = [1, 2, 3, 4, 5];
// Partial sum of all elements
auto sum = cumulativeFold!((a, b) => a + b)(arr, 0);
writeln(sum.array); // [1, 3, 6, 10, 15]

// Partial sum again, using a string predicate with "a" and "b"
auto sum2 = cumulativeFold!"a + b"(arr, 0);
writeln(sum2.array); // [1, 3, 6, 10, 15]

// Compute the partial maximum of all elements
auto largest = cumulativeFold!max(arr);
writeln(largest.array); // [1, 2, 3, 4, 5]

// Partial max again, but with Uniform Function Call Syntax (UFCS)
largest = arr.cumulativeFold!max;
writeln(largest.array); // [1, 2, 3, 4, 5]

// Partial count of odd elements
auto odds = arr.cumulativeFold!((a, b) => a + (b & 1))(0);
writeln(odds.array); // [1, 1, 2, 2, 3]

// Compute the partial sum of squares
auto ssquares = arr.cumulativeFold!((a, b) => a + b * b)(0);
writeln(ssquares.array); // [1, 5, 14, 30, 55]

// Chain multiple ranges into seed
int[] a = [3, 4];
int[] b = [100];
auto r = cumulativeFold!"a + b"(chain(a, b));
writeln(r.array); // [3, 7, 107]

// Mixing convertible types is fair game, too
double[] c = [2.5, 3.0];
auto r1 = cumulativeFold!"a + b"(chain(a, b, c));
assert(approxEqual(r1, [3, 7, 107, 109.5, 112.5]));

// To minimize nesting of parentheses, Uniform Function Call Syntax can be used
auto r2 = chain(a, b, c).cumulativeFold!"a + b";
assert(approxEqual(r2, [3, 7, 107, 109.5, 112.5]));

Примеры:

Иногда очень полезно вычислять несколько агрегатов за один проход. Одним из преимуществ является то, что вычисление быстрее, потому что накладные расходы на циклы совместно используются. Именно поэтому cumulativeFold принимает несколько функций. Если передано две или более функций, cumulativeFold возвращает объект std.typecons.Tuple с одним членом на каждую переданную функцию. Соответственно увеличивается количество начальных значений.

import std.algorithm.comparison : max, min;
import std.algorithm.iteration : map;
import std.math : approxEqual;
import std.typecons : tuple;

double[] a = [3.0, 4, 7, 11, 3, 2, 5];
// Compute minimum and maximum in one pass
auto r = a.cumulativeFold!(min, max);
// The type of r is Tuple!(int, int)
assert(approxEqual(r.map!"a[0]", [3, 3, 3, 3, 3, 2, 2]));     // minimum
assert(approxEqual(r.map!"a[1]", [3, 4, 7, 11, 11, 11, 11])); // maximum

// Compute sum and sum of squares in one pass
auto r2 = a.cumulativeFold!("a + b", "a + b * b")(tuple(0.0, 0.0));
assert(approxEqual(r2.map!"a[0]", [3, 7, 14, 25, 28, 30, 35]));      // sum
assert(approxEqual(r2.map!"a[1]", [9, 25, 74, 195, 204, 208, 233])); // sum of squares

auto cumulativeFold(R)(R range)
Ограничения: if (isInputRange!(Unqual!R));

Версия без начального значения. Первый элемент r используется как значение начального значения. Для каждой функции f в fun, соответствующий тип начального значения S равен Unqual!(typeof(f(e, e))), где e — элемент r: ElementType!R. После определения S, S s = e; и s = f(s, e); должны быть допустимыми.

Параметры:

R range

входной диапазон

Возвращает:

диапазон, содержащий последовательные уменьшенные значения.

auto cumulativeFold(R, S)(R range, S seed)
Ограничения: if (isInputRange!(Unqual!R));

Версия с начальным значением. Начальное значение должно быть единственным значением, если fun является единственной функцией. Если fun — это несколько функций, то seed должно быть std.typecons.Tuple с одним полем на каждую функцию в f. Для удобства, если начальное значение равно const, или имеет квалифицированные поля, то cumulativeFold будет работать с неквалифицированной копией. Если это произойдёт, тип возвращаемого значения не будет идеально соответствовать S.

Параметры:

R range	входной диапазон
S seed	начальное значение аккумулятора

Возвращает:

диапазон, содержащий последовательные уменьшенные значения.

auto splitter(alias pred = "a == b", Range, Separator)(Range r, Separator s)
Ограничения: if (is(typeof(binaryFun!pred(r.front, s)) : bool) && (hasSlicing!Range && hasLength!Range || isNarrowString!Range));

auto splitter(alias pred = "a == b", Range, Separator)(Range r, Separator s)
Ограничения: if (is(typeof(binaryFun!pred(r.front, s.front)) : bool) && (hasSlicing!Range || isNarrowString!Range) && isForwardRange!Separator && (hasLength!Separator || isNarrowString!Separator));

auto splitter(alias isTerminator, Range)(Range r)
Ограничения: if (isForwardRange!Range && is(typeof(unaryFun!isTerminator(r.front))));

Лениво разбивает диапазон, используя элемент или диапазон в качестве разделителя. Диапазоны разделителей могут быть любым типом узкого строкового типа или нарезки диапазона.

Два соседних разделителя считаются окружающими пустой элемент в разделяемом диапазоне. Используйте filter!(a => !a.empty) для результата, чтобы сжать пустые элементы.

Предикат передаётся в std.functional.binaryFun и принимает любую вызываемую функцию, которая может быть выполнена через pred(element, s).

Примечания

Если требуется разделение строки на пробелы и сжатие токенов, рассмотрите использование splitter без указания разделителя.

Если разделитель не передан, предикат isTerminator определяет, следует ли принимать элемент из r.

Параметры:

pred	Предикат для сравнения каждого элемента с разделителем, по умолчанию "a == b".
Range r	входной диапазон для разделения. Должен поддерживать нарезку и .length или быть узким строковым типом.
Separator s	Элемент (или диапазон), рассматриваемый как разделитель между сегментами диапазона, подлежащими разделению.
isTerminator	Предикат для определения места разделения диапазона, когда разделитель не передан

Ограничения

Предикат pred должен принимать элемент из r и разделитель s.

Возвращает:

Вводной диапазон поддиапазонов элементов между разделителями. Если r является прямым диапазоном или двунаправленным диапазоном, возвращаемый диапазон будет аналогичным. Если в качестве разделителя используется диапазон, двунаправленность невозможна. Если задан пустой диапазон, результатом является пустой диапазон. Если задан диапазон с одним разделителем, результатом является диапазон с двумя пустыми элементами.

См. также:

std.regex.splitter для версии, которая разделяет по разделителю, определяемому регулярным выражением, и std.array.split для версии, которая разделяет нетерпеливо.

Примеры:

Базовое разделение символов и чисел.

import std.algorithm.comparison : equal;

assert("a|bc|def".splitter('|').equal([ "a", "bc", "def" ]));

int[] a = [1, 0, 2, 3, 0, 4, 5, 6];
int[][] w = [ [1], [2, 3], [4, 5, 6] ];
assert(a.splitter(0).equal(w));

Примеры:

Соседние разделители.

import std.algorithm.comparison : equal;

assert("|ab|".splitter('|').equal([ "", "ab", "" ]));
assert("ab".splitter('|').equal([ "ab" ]));

assert("a|b||c".splitter('|').equal([ "a", "b", "", "c" ]));
assert("hello  world".splitter(' ').equal([ "hello", "", "world" ]));

auto a = [ 1, 2, 0, 0, 3, 0, 4, 5, 0 ];
auto w = [ [1, 2], [], [3], [4, 5], [] ];
assert(a.splitter(0).equal(w));

Примеры:

Пустые и состоящие только из разделителей диапазоны.

import std.algorithm.comparison : equal;
import std.range : empty;

assert("".splitter('|').empty);
assert("|".splitter('|').equal([ "", "" ]));
assert("||".splitter('|').equal([ "", "", "" ]));

Примеры:

Использование диапазона для разделения

import std.algorithm.comparison : equal;

assert("a=>bc=>def".splitter("=>").equal([ "a", "bc", "def" ]));
assert("a|b||c".splitter("||").equal([ "a|b", "c" ]));
assert("hello  world".splitter("  ").equal([ "hello", "world" ]));

int[] a = [ 1, 2, 0, 0, 3, 0, 4, 5, 0 ];
int[][] w = [ [1, 2], [3, 0, 4, 5, 0] ];
assert(a.splitter([0, 0]).equal(w));

a = [ 0, 0 ];
assert(a.splitter([0, 0]).equal([ (int[]).init, (int[]).init ]));

a = [ 0, 0, 1 ];
assert(a.splitter([0, 0]).equal([ [], [1] ]));

Примеры:

Пользовательские предикатные функции.

import std.algorithm.comparison : equal;
import std.ascii : toLower;

assert("abXcdxef".splitter!"a.toLower == b"('x').equal(
             [ "ab", "cd", "ef" ]));

auto w = [ [0], [1], [2] ];
assert(w.splitter!"a.front == b"(1).equal([ [[0]], [[2]] ]));

Примеры:

Использование splitter без разделителя

import std.algorithm.comparison : equal;
import std.range.primitives : front;

assert(equal(splitter!(a => a == '|')("a|bc|def"), [ "a", "bc", "def" ]));
assert(equal(splitter!(a => a == ' ')("hello  world"), [ "hello", "", "world" ]));

int[] a = [ 1, 2, 0, 0, 3, 0, 4, 5, 0 ];
int[][] w = [ [1, 2], [], [3], [4, 5], [] ];
assert(equal(splitter!(a => a == 0)(a), w));

a = [ 0 ];
assert(equal(splitter!(a => a == 0)(a), [ (int[]).init, (int[]).init ]));

a = [ 0, 1 ];
assert(equal(splitter!(a => a == 0)(a), [ [], [1] ]));

w = [ [0], [1], [2] ];
assert(equal(splitter!(a => a.front == 1)(w), [ [[0]], [[2]] ]));

Примеры:

Разделители в начале, конце или отсутствие разделителей.

import std.algorithm.comparison : equal;

assert("|ab|".splitter('|').equal([ "", "ab", "" ]));
assert("ab".splitter('|').equal([ "ab" ]));

Примеры:

Splitter возвращает двунаправленные диапазоны, если разделитель является одним элементом

import std.algorithm.comparison : equal;
import std.range : retro;
assert("a|bc|def".splitter('|').retro.equal([ "def", "bc", "a" ]));

Примеры:

Ленивое разделение по словам

import std.ascii : isWhite;
import std.algorithm.comparison : equal;
import std.algorithm.iteration : splitter;

string str = "Hello World!";
assert(str.splitter!(isWhite).equal(["Hello", "World!"]));

auto splitter(Range)(Range s)
Ограничения: if (isSomeString!Range || isRandomAccessRange!Range && hasLength!Range && hasSlicing!Range && !isConvertibleToString!Range && isSomeChar!(ElementEncodingType!Range));

Лениво разделяет диапазон символов s на слова, используя пробелы в качестве разделителей.

Эта функция специфична для диапазонов символов и, в отличие от splitter!(std.uni.isWhite), объединяет последовательности пробелов (не будут создаваться пустые токены).

Параметры:

Диапазон s

Диапазон символов, подлежащий разделению. Должен быть строкой или диапазоном с произвольным доступом типов символов.

Возвращаемое значение:

Диапазон ввода (входной диапазон) срезов исходного диапазона, разделенных пробелами.

Примеры:

import std.algorithm.comparison : equal;
auto a = " a     bcd   ef gh ";
assert(equal(splitter(a), ["a", "bcd", "ef", "gh"][]));

шаблон substitute(substs...) if (substs.length >= 2 && isExpressions!substs)

auto substitute(alias pred = (a, b) => a == b, R, Substs...)(R r, Substs substs)
Ограничения: if (isInputRange!R && (Substs.length >= 2) && !is(CommonType!Substs == void));

Возвращает диапазон со всеми вхождениями substs в r. заменёнными на их замены.

Поддерживаются также замены одиночных значений ('ö'.substitute!('ä', 'a', 'ö', 'o', 'ü', 'u)) и выполняются за Ο(1).

Параметры:

R r	входной диапазон
Значение value	одиночное значение, которое может быть заменено за Ο(1)
Substs substs	набор замен/подстановок
pred	функция равенства для проверки, совпадают ли элемент(ы) с заменой

Возвращаемое значение:

Диапазон с выполненными заменами.

См. также:

std.array.replace для жадного алгоритма замены или std.string.translate, и std.string.tr для строковых алгоритмов с таблицами трансляции.

Примеры:

import std.algorithm.comparison : equal;

// substitute single elements
assert("do_it".substitute('_', ' ').equal("do it"));

// substitute multiple, single elements
assert("do_it".substitute('_', ' ',
                           'd', 'g',
                           'i', 't',
                           't', 'o')
              .equal("go to"));

// substitute subranges
assert("do_it".substitute("_", " ",
                          "do", "done")
              .equal("done it"));

// substitution works for any ElementType
int[] x = [1, 2, 3];
auto y = x.substitute(1, 0.1);
assert(y.equal([0.1, 2, 3]));
static assert(is(typeof(y.front) == double));

import std.range : retro;
assert([1, 2, 3].substitute(1, 0.1).retro.equal([3, 2, 0.1]));

Примеры:

Используйте более быструю перегрузку времени компиляции

import std.algorithm.comparison : equal;

// substitute subranges of a range
assert("apple_tree".substitute!("apple", "banana",
                                "tree", "shrub").equal("banana_shrub"));

// substitute subranges of a range
assert("apple_tree".substitute!('a', 'b',
                                't', 'f').equal("bpple_free"));

// substitute values
writeln('a'.substitute!('a', 'b', 't', 'f')); // 'b'

Примеры:

Несколько подстановок

import std.algorithm.comparison : equal;
import std.range.primitives : ElementType;

int[3] x = [1, 2, 3];
auto y = x[].substitute(1, 0.1)
            .substitute(0.1, 0.2);
static assert(is(typeof(y.front) == double));
assert(y.equal([0.2, 2, 3]));

auto z = "42".substitute('2', '3')
             .substitute('3', '1');
static assert(is(ElementType!(typeof(z)) == dchar));
assert(equal(z, "41"));

auto substitute(Value)(Value value)
Ограничения: if (isInputRange!Value || !is(CommonType!(Value, typeof(substs[0])) == void));

Замена одиночных значений с подстановками на этапе компиляции.

Сложность

Ο(1) из-за switch гарантирующего Ο(1);

auto sum(R)(R r)
Ограничения: if (isInputRange!R && !isInfinite!R && is(typeof(r.front + r.front)));

auto sum(R, E)(R r, E seed)
Ограничения: if (isInputRange!R && !isInfinite!R && is(typeof(seed = seed + r.front)));

Суммирует элементы r, что должно быть конечным входным диапазоном. Хотя концептуально sum(r) эквивалентно fold!((a, b) => a + b)(r, 0), sum использует специализированные алгоритмы для максимальной точности, как показано ниже.

• Если std.range.primitives.ElementType!R — тип с плавающей точкой, а R — диапазон с произвольным доступом с длиной и нарезкой, то sum использует алгоритм попарного суммирования.
• Если ElementType!R — тип с плавающей точкой, а R — конечный входной диапазон (но не диапазон с произвольным доступом с нарезкой), то sum использует алгоритм суммирования Кахана.
• Во всех остальных случаях выполняется простое суммирование по элементам.

Для входных данных с плавающей точкой вычисления производятся в точности real для real входных данных и в точности double в противном случае (обратите внимание, что это специальный случай, отличающийся от поведения fold, которое сохраняло бы точность float для float диапазона). Для всех других типов вычисления производятся в том же типе, полученном в результате сложения двух элементов диапазона, который может быть другим типом, чем сами элементы (например, в случае преобразования целых типов).

Семена могут быть переданы в sum. Семена не только используются в качестве начального значения, но и изменяют все вышеперечисленные параметры, определяя используемый алгоритм и точность суммирования. Если семя не передается, оно создается со значением typeof(r.front + r.front)(0), или typeof(r.front + r.front).zero если нет конструктора, принимающего int.

Обратите внимание, что эти специализированные алгоритмы суммирования выполняют более примитивные операции, чем обычное суммирование. Поэтому, если в определенных случаях требуется максимальная скорость за счет точности, можно использовать fold!((a, b) => a + b)(r, 0), который не специализирован для суммирования.

Параметры:

E seed	начальное значение суммирования
R r	конечный входной диапазон

Возвращаемое значение:

Сумма всех элементов в диапазоне r.

Примеры:

Аналогично

import std.range;

//simple integral sumation
writeln(sum([1, 2, 3, 4])); // 10

//with integral promotion
writeln(sum([false, true, true, false, true])); // 3
writeln(sum(ubyte.max.repeat(100))); // 25500

//The result may overflow
writeln(uint.max.repeat(3).sum()); // 4294967293U
//But a seed can be used to change the sumation primitive
writeln(uint.max.repeat(3).sum(ulong.init)); // 12884901885UL

//Floating point sumation
writeln(sum([1.0, 2.0, 3.0, 4.0])); // 10

//Floating point operations have double precision minimum
static assert(is(typeof(sum([1F, 2F, 3F, 4F])) == double));
writeln(sum([1F, 2, 3, 4])); // 10

//Force pair-wise floating point sumation on large integers
import std.math : approxEqual;
assert(iota(ulong.max / 2, ulong.max / 2 + 4096).sum(0.0)
           .approxEqual((ulong.max / 2) * 4096.0 + 4096^^2 / 2));

T mean(T = double, R)(R r)
Ограничения: if (isInputRange!R && isNumeric!(ElementType!R) && !isInfinite!R);

auto mean(R, T)(R r, T seed)
Ограничения: if (isInputRange!R && !isNumeric!(ElementType!R) && is(typeof(r.front + seed)) && is(typeof(r.front / size_t(1))) && !isInfinite!R);

Находит среднее значение (в разговорной речи — среднее арифметическое) диапазона.

Для встроенных числовых типов используется точный алгоритм вычисления среднего значения Кнута и Уэлфорда. Для пользовательских типов используется суммирование по элементам. Кроме того, требуется дополнительный параметр seed, чтобы правильно инициализировать суммирование, что эквивалентно 0.

Первый перегруз этого метода вернет T.init если диапазон пустой. Однако второй перегруз вернет seed для пустых диапазонов.

Этот метод имеет сложность Ο(r.length).

Параметры:

T	Тип возвращаемого значения.
R r	входной диапазон
T seed	Для пользовательских типов. Должно быть эквивалентно 0.

Возвращаемое значение:

Среднее значение r когда r не пустой.

Примеры:

import std.math : approxEqual, isNaN;

static immutable arr1 = [1, 2, 3];
static immutable arr2 = [1.5, 2.5, 12.5];

assert(arr1.mean.approxEqual(2));
assert(arr2.mean.approxEqual(5.5));

assert(arr1[0 .. 0].mean.isNaN);

auto uniq(alias pred = "a == b", Range)(Range r)
Ограничения: if (isInputRange!Range && is(typeof(binaryFun!pred(r.front, r.front)) == bool));

Лениво итерирует уникальные последовательные элементы данного диапазона (функциональность аналогична системной утилите uniq). Эквивалентность элементов оценивается с помощью предиката pred, по умолчанию "a == b". Предикат передаётся в std.functional.binaryFun и может принимать строку или любой вызываемый объект, который можно выполнить с помощью pred(element, element). Если заданный диапазон двунаправленный, uniq также возвращает двунаправленный диапазон.

Параметры:

pred	Предикат для определения эквивалентности элементов диапазона.
Range r	входной диапазон элементов для фильтрации.

Возвращаемое значение:

входной диапазон последовательно уникальных элементов в исходном диапазоне. Если r также является диапазоном вперёд или двунаправленным, возвращаемый диапазон будет аналогичным.

Примеры:

import std.algorithm.comparison : equal;
import std.algorithm.mutation : copy;

int[] arr = [ 1, 2, 2, 2, 2, 3, 4, 4, 4, 5 ];
assert(equal(uniq(arr), [ 1, 2, 3, 4, 5 ][]));

// Filter duplicates in-place using copy
arr.length -= arr.uniq().copy(arr).length;
writeln(arr); // [1, 2, 3, 4, 5]

// Note that uniqueness is only determined consecutively; duplicated
// elements separated by an intervening different element will not be
// eliminated:
assert(equal(uniq([ 1, 1, 2, 1, 1, 3, 1]), [1, 2, 1, 3, 1]));

Permutations!Range permutations(Range)(Range r)
Ограничения: if (isRandomAccessRange!Range && hasLength!Range);

struct Permutations(Range) if (isRandomAccessRange!Range && hasLength!Range);

Лениво вычисляет все перестановки r с использованием алгоритма Хита.

Параметры:

Range	тип диапазона
Range r	диапазон с произвольным доступом для поиска перестановок.

Возвращаемое значение:

диапазон вперёд элементов, которые представляют собой std.range.indexed представление по r.

См. также:

std.algorithm.sorting.nextPermutation.

Примеры:

import std.algorithm.comparison : equal;
import std.range : iota;
assert(equal!equal(iota(3).permutations,
    [[0, 1, 2],
     [1, 0, 2],
     [2, 0, 1],
     [0, 2, 1],
     [1, 2, 0],
     [2, 1, 0]]));