std.algorithm.comparison

uint among(alias pred = (a, b) => a == b, Value, Values...)(Value value, Values values)
if (Values.length != 0);

template among(values...) if (isExpressionTuple!values)

Ищет value среди values, возвращая начинающийся с единицы индекс первого совпадающего значения в values, или 0, если value отсутсвует среди values. Предикат pred используется для сравнения значений и использует равенство по умолчанию.

Параметры:

pred	Предикат, используемый для сравнения значений.
Value value	Искомое значение.
Values values	Значения, которые сравниваются с value.

Возвращает:

0, если value не было обнаружено среди values, в противном случае возвращается индекс обнаруженного значения плюс один.

Смотрите также:

find и canFind для поиска значения в диапазоне.

Примеры:

assert(3.among(1, 42, 24, 3, 2));

if (auto pos = "bar".among("foo", "bar", "baz"))
    assert(pos == 2);
else
    assert(false);

// 42 больше, чем 24
assert(42.among!((lhs, rhs) => lhs > rhs)(43, 24, 100) == 2);

Примеры:

Кроме того, values могут быть переданы во время компиляции, что позволяет проводить более эффективный поиск, но в этом случае поддерживается сопоставление только на равенство:

assert(3.among!(2, 3, 4));
assert("bar".among!("foo", "bar", "baz") == 2);

auto castSwitch(choices...)(Object switchObject);

Выполняет и возвращает один из набора обработчиков, основанных на типе объекта переключателя.

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

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

Исключения:

Если ни один из вариантов не соответствует, будет брошен SwitchError. SwitchError также будет брошен, если не все варианты являются void и выбор void выполняется без выбрасывания исключения.

Параметры:

choices	Варианты choices должны состоять из обработчиков – функций или делегатов, которые принимают один аргумент. Также может быть вариант, который принимает нуль аргументов. Этот выбор будет вызываться, если switchObject равен null.
Object switchObject	объект, на котором выполняются тесты.

Возвращает:

Значение выбранного варианта.

Замечание: castSwitch может быть использован только с объектными типами.

Примеры:

import std.algorithm.iteration : map;
import std.format : format;

class A
{
    int a;
    this(int a) {this.a = a;}
    @property int i() { return a; }
}
interface I { }
class B : I { }

Object[] arr = [new A(1), new B(), null];

auto results = arr.map!(castSwitch!(
                            (A a) => "A with a value of %d".format(a.a),
                            (I i) => "derived from I",
                            ()    => "null reference",
                        ))();

// A обрабатывается непосредственно:
assert(results[0] == "A with a value of 1");
// B не имеет обработчика – применяется обработчик I:
assert(results[1] == "derived from I");
// для null применяется null-обработчик:
assert(results[2] == "null reference");

Примеры:

Использование void-обработчиков:

import std.exception : assertThrown;

class A { }
class B { }
// Void-обработчики допустимы, если они бросают исключение:
assertThrown!Exception(
    new B().castSwitch!(
        (A a) => 1,
        (B d)    { throw new Exception("B is not allowed!"); }
    )()
);

// Void-обработчики также допустимы, если все обработчики являются void:
new A().castSwitch!(
    (A a) { assert(true); },
    (B b) { assert(false); },
)();

auto clamp(T1, T2, T3)(T1 val, T2 lower, T3 upper);

Зажимает значение в заданных пределах.

Эта функция эквивалентна max(lower, min(upper,val)).

Параметры:

T1 val	Значение для зажимания.
T2 lower	Нижний предел.
T3 upper	Верхний предел.

Возвращает:

Возвращает val, если оно между lower и upper. В противном случае возвращает ближайший из двух.

Примеры:

assert(clamp(2, 1, 3) == 2);
assert(clamp(0, 1, 3) == 1);
assert(clamp(4, 1, 3) == 3);

assert(clamp(1, 1, 1) == 1);

assert(clamp(5, -1, 2u) == 2);

int cmp(alias pred = "a < b", R1, R2)(R1 r1, R2 r2)
if (isInputRange!R1 && isInputRange!R2 && !(isSomeString!R1 && isSomeString!R2));

int cmp(alias pred = "a < b", R1, R2)(R1 r1, R2 r2)
if (isSomeString!R1 && isSomeString!R2);

Выполняет трехпозиционное лексикографическое сравнение двух входных диапазонов согласно предикату pred. Итерируя r1 и r2 шаг-за-шагом, cmp сравнивает каждый элемент e1 в диапазоне r1 с соответствующим элементом e2 в r2. Если один из диапазонов завершается, cmp возвращает отрицательную величину, если r1 имеет меньше элементов, чем r2, положительную величину, если r1 имеет больше элементов, чем r2, и 0 если диапазоны имеют одинаковое количество элементов.

Если диапазоны являются строками, cmp выполняет обстоятельное UTF-декодирование и сравнивает диапазоны по одной кодовой точке (code point) за один раз.

Параметры:

pred	Предикат, используемый для сравнения.
R1 r1	Первый диапазон.
R2 r2	Второй диапазон.

Возвращает:

0, если оба сравниваемых диапазона равны. -1, если первый отличающийся элемент r1 меньше, чем соответствующий элемент r2 согласно предикату pred. 1, если первый отличающийся элемент r2 меньше, чем соответствующий элемент r1 согласно предикату pred.

Примеры:

int result;

result = cmp("abc", "abc");
assert(result == 0);
result = cmp("", "");
assert(result == 0);
result = cmp("abc", "abcd");
assert(result < 0);
result = cmp("abcd", "abc");
assert(result > 0);
result = cmp("abc"d, "abd");
assert(result < 0);
result = cmp("bbc", "abc"w);
assert(result > 0);
result = cmp("aaa", "aaaa"d);
assert(result < 0);
result = cmp("aaaa", "aaa"d);
assert(result > 0);
result = cmp("aaa", "aaa"d);
assert(result == 0);
result = cmp(cast(int[])[], cast(int[])[]);
assert(result == 0);
result = cmp([1, 2, 3], [1, 2, 3]);
assert(result == 0);
result = cmp([1, 3, 2], [1, 2, 3]);
assert(result > 0);
result = cmp([1, 2, 3], [1L, 2, 3, 4]);
assert(result < 0);
result = cmp([1L, 2, 3], [1, 2]);
assert(result > 0);

Переместиться к: equal

template equal(alias pred = "a == b")

Сравнивает два диапазона на равенство, как определено предикатом pred (который по-умолчанию задан в ==).

Примеры:

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

int[] a = [ 1, 2, 4, 3 ];
assert(!equal(a, a[1..$]));
assert(equal(a, a));
assert(equal!((a, b) => a == b)(a, a));

// различные типы
double[] b = [ 1.0, 2, 4, 3];
assert(!equal(a, b[1..$]));
assert(equal(a, b));

// с предикатом: убедиться, что два вектора приблизительно равны
double[] c = [ 1.005, 2, 4, 3];
assert(equal!approxEqual(b, c));

Примеры:

Позсказка: equal сама может использоваться, как предикат в других функциях. Это может быть очень полезным, когда тип элементов диапазона – сам является диапазоном. В частности, equal может быть собственным предикатом, допускающим сравнение диапазона диапазонов (диапазонов...) .

import std.range : iota, chunks;
import std.algorithm.comparison : equal;
assert(equal!(equal!equal)(
    [[[0, 1], [2, 3]], [[4, 5], [6, 7]]],
    iota(0, 8).chunks(2).chunks(2)
));

bool equal(Range1, Range2)(Range1 r1, Range2 r2)
if (isInputRange!Range1 && isInputRange!Range2 && is(typeof(binaryFun!pred(r1.front, r2.front))));

Эта функция сравнивает диапазоны на равенство. Диапазоны могут иметь различные типы элементов, до тех пор, пока pred(a, b) способен вычислить логическое значение для a в r1 и b в r2. Выполняет Ο(min(r1.length, r2.length)) вычислений pred.

Параметры:

Range1 r1	Первый диапазон для сравнения.
Range2 r2	Второй диапазон для сравнения.

Возвращает:

true тогда и только тогда, когда два диапазона равны элемент-в-элемент, в соответсвии с предикатом pred.

Смотрите также:

STL's equal

Переместиться к: insert · none · remove · substitute

enum EditOp: char;

Кодирует операции редактирования, необходимые для превращения одной последовательности в другую. Даны последовательности s (источник) и t (target), (цель), последовательность EditOp кодирует шаги, которые нужно педпринять, чтобы преобразовать s в t. Например, если s = "cat" и "cars", минимальная последовательность, которая превращает s в t: пропустить два символа, заменить 't на 'r', и вставить 's'. Работа с операциями редактирования полезна в таких приложениях, как например, программах контроля правописания (чтобы находить ближайшее к данному слову, написанному с орфографическими ошибками), приближенные поиски, diff-программы, которые вычисляют различие между файлами, эффективно кодируя патчи, анализа последовательности ДНК, и обнаружения плагиата.

none

Текущие элементы равны; никакого редактирования не требуется.

substitute

Заменить текущий элемент в цели на текущий элемент в источнике.

insert

Вставить текущий элемент из источника в цель.

remove

Удалить текущий элемент из цели.

size_t levenshteinDistance(alias equals = (a, b) => a == b, Range1, Range2)(Range1 s, Range2 t)
if (isForwardRange!Range1 && isForwardRange!Range2);

size_t levenshteinDistance(alias equals = (a, b) => a == b, Range1, Range2)(auto ref Range1 s, auto ref Range2 t)
if (isConvertibleToString!Range1 || isConvertibleToString!Range2);

Возвращает расстояние Левенштейна между s и t. Расстояние Левенштейна вычисляет минимальное количество действий редактирования, необходимых для преобразования s в t. Выполняется за Ο(s.length * t.length) операций сравнения и занимает область в памяти размером Ο(s.length * t.length).

Параметры:

equals	Двухаргументный предикат, который сравнивает элементы двух диапазонов.
Range1 s	Исходный диапазон.
Range2 t	Цель преобразования.

Возвращает:

Минимальное количество операций редактирования, преобразующих s в t.

Не распределяет память, управляемую сборщиком мусора.

Примеры:

import std.algorithm.iteration : filter;
import std.uni : toUpper;

assert(levenshteinDistance("cat", "rat") == 1);
assert(levenshteinDistance("parks", "spark") == 2);
assert(levenshteinDistance("abcde", "abcde") == 0);
assert(levenshteinDistance("abcde", "abCde") == 1);
assert(levenshteinDistance("kitten", "sitting") == 3);
assert(levenshteinDistance!((a, b) => toUpper(a) == toUpper(b))
    ("parks", "SPARK") == 2);
assert(levenshteinDistance("parks".filter!"true", "spark".filter!"true") == 2);
assert(levenshteinDistance("ID", "I♥D") == 1);

Tuple!(size_t, EditOp[]) levenshteinDistanceAndPath(alias equals = (a, b) => a == b, Range1, Range2)(Range1 s, Range2 t)
if (isForwardRange!Range1 && isForwardRange!Range2);

Tuple!(size_t, EditOp[]) levenshteinDistanceAndPath(alias equals = (a, b) => a == b, Range1, Range2)(auto ref Range1 s, auto ref Range2 t)
if (isConvertibleToString!Range1 || isConvertibleToString!Range2);

Возвращает расстояние Левенштейна и последовательность редактирования между s и t.

Параметры:

equals	Двухаргументный предикат, который сравнивает элементы двух диапазонов.
Range1 s	Исходный диапазон.
Range2 t	Цель преобразования.

Возвращает:

Кортеж, где первый элемент – минимальное количество операций редактирования для преобразования s в t, а второй – последовательность редактирования, выполняющая это преобразование.

Распределяет память, управляемую сборщиком мусора, для возвращаемого массива EditOp[].

Примеры:

string a = "Saturday", b = "Sundays";
auto p = levenshteinDistanceAndPath(a, b);
assert(p[0] == 4);
assert(equal(p[1], "nrrnsnnni"));

MaxType!T max(T...)(T args)
if (T.length >= 2);

Итерирует переданные аргументы и возвращает максимальное значение.

Параметры:

T args

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

Возвращает:

Максимальный из переданных аргументов. Тип возвращаемой величины является типом из числа переданных аргументов, который способен сохранить самое большое значение.

Смотрите также:

std.algorithm.searching.maxElement

Примеры:

int a = 5;
short b = 6;
double c = 2;
auto d = max(a, b);
assert(is(typeof(d) == int));
assert(d == 6);
auto e = min(a, b, c);
assert(is(typeof(e) == double));
assert(e == 2);

MinType!T min(T...)(T args)
if (T.length >= 2);

Итерирует переданные аргументы и возвращает минимальное значение.

Параметры:

T args

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

Возвращает:

Минимальный из переданных аргументов.

Смотрите также:

std.algorithm.searching.minElement

Примеры:

int a = 5;
short b = 6;
double c = 2;
auto d = min(a, b);
static assert(is(typeof(d) == int));
assert(d == 5);
auto e = min(a, b, c);
static assert(is(typeof(e) == double));
assert(e == 2);

// С аргументами со смешанной знаковостью, типом возвращаемого значения является тот,
// который может хранить самые меньшие значения.
a = -10;
uint f = 10;
static assert(is(typeof(min(a, f)) == int));
assert(min(a, f) == -10);

// Определенные пользователем типы, которые поддерживают сравнения с помощью <, поддерживаются.
import std.datetime;
assert(min(Date(2012, 12, 21), Date(1982, 1, 4)) == Date(1982, 1, 4));
assert(min(Date(1982, 1, 4), Date(2012, 12, 21)) == Date(1982, 1, 4));
assert(min(Date(1982, 1, 4), Date.min) == Date.min);
assert(min(Date.min, Date(1982, 1, 4)) == Date.min);
assert(min(Date(1982, 1, 4), Date.max) == Date(1982, 1, 4));
assert(min(Date.max, Date(1982, 1, 4)) == Date(1982, 1, 4));
assert(min(Date.min, Date.max) == Date.min);
assert(min(Date.max, Date.min) == Date.min);

Tuple!(Range1, Range2) mismatch(alias pred = "a == b", Range1, Range2)(Range1 r1, Range2 r2)
if (isInputRange!Range1 && isInputRange!Range2);

Последовательно сравнивает элементы в r1 и r2 шаг-за-шагом, и останавливается при первом несовпадении (в соответсвии с pred, по умолчанию равенство). Возвращает кортеж с сокращёнными диапазонами, которые начинаются с двух несовпадающих величин. Выполняет Ο(min(r1.length, r2.length)) вычислений pred.

Смотрите также:

STL's mismatch

Примеры:

int[]    x = [ 1,  5, 2, 7,   4, 3 ];
double[] y = [ 1.0, 5, 2, 7.3, 4, 8 ];
auto m = mismatch(x, y);
assert(m[0] == x[3 .. $]);
assert(m[1] == y[3 .. $]);

auto predSwitch(alias pred = "a == b", T, R...)(T switchExpression, lazy R choices);

Возвращает одно из набора выражений в зависимости от значения выражения switchExpression.

choices должны быть сформированы парами из тестирующих выражений и возвращаемых выражений. Каждое тестирующее выражение сравнивается со switchExpression, используя pred (switchExpression – это первый аргумент), и если получится true – возвратится возвращаемое выражение.

Как тестирующие, так и возвращаемые выражения вычисляются лениво.

Параметры:

T switchExpression

Первый аргумент для предиката.

R choices

Пары из тестирующих выражений и возвращаемых выражений. Тестирующие выражения будут вторым аргументом для предиката, а возвращаемое выражение будет возвращено, если результатом предиката со switchExpression и тестирующим выражением в качестве аргументов будет истина. Может также иметь возвращаемое выражение по-умолчанию, которое должно быть последним выражением без тестирующего выражения перед ним. Возвращаемое выражение может быть типа void, только если оно всегда бросает исключение.

Возвращает:

Возвращаемое выражение, связанное с первым тестирующим выражением, с которым предикат выдал true, или возвращаемое выражение по-умолчанию, если ни одно из тестирующих выражений не сработало.

Исключения:

Если нет возвращаемого выражения по-умолчанию, и предикат не дал истину ни с одним из тестирующих выражений – будет брошено исключение SwitchError. SwitchError также будет брошено, если возвращаемое выражение типа void при выполнении не бросило какого-либо исключения.

Примеры:

string res = 2.predSwitch!"a < b"(
    1, "less than 1",
    5, "less than 5",
    10, "less than 10",
    "greater or equal to 10");

assert(res == "less than 5");

//Аргументы ленивые, что позволяет нам использовать predSwitch для создания
//рекурсивных функций:
int factorial(int n)
{
    return n.predSwitch!"a <= b"(
        -1, {throw new Exception("Can not calculate n! for n < 0");}(),
        0, 1, // 0! = 1
        n * factorial(n - 1) // n! = n * (n - 1)! for n >= 0
        );
}
assert(factorial(3) == 6);

//Возвращающие void выражения допустимы, если они всегда бросают исключение:
import std.exception : assertThrown;
assertThrown!Exception(factorial(-9));

bool isSameLength(Range1, Range2)(Range1 r1, Range2 r2)
if (isInputRange!Range1 && isInputRange!Range2 && !isInfinite!Range1 && !isInfinite!Range2);

Проверяет, имеют ли два диапазона одно и то же количество элементов. Эта функция оптимизирована, чтобы всегда использвать свойство length (длина) каждого из диапазонов, если оно существует.

Если оба диапазона имеют свойство length, эта функция выполняется за Ο(1). В противном случае, время выполнения этой функции – Ο(min(r1.length, r2.length)).

Параметры:

Range1 r1	конечный входной диапазон
Range2 r2	конечный входной диапазон

Возвращает:

true, если оба диапазона имеют одинаковую длину, false в противном случае.

Примеры:

assert(isSameLength([1, 2, 3], [4, 5, 6]));
assert(isSameLength([0.3, 90.4, 23.7, 119.2], [42.6, 23.6, 95.5, 6.3]));
assert(isSameLength("abc", "xyz"));

int[] a;
int[] b;
assert(isSameLength(a, b));

assert(!isSameLength([1, 2, 3], [4, 5]));
assert(!isSameLength([0.3, 90.4, 23.7], [42.6, 23.6, 95.5, 6.3]));
assert(!isSameLength("abcd", "xyz"));

alias AllocateGC = std.typecons.Flag!"allocateGC".Flag;

Для удобства

bool isPermutation(AllocateGC allocate_gc, Range1, Range2)(Range1 r1, Range2 r2)
if (allocate_gc == Yes.allocateGC && isForwardRange!Range1 && isForwardRange!Range2 && !isInfinite!Range1 && !isInfinite!Range2);

bool isPermutation(alias pred = "a == b", Range1, Range2)(Range1 r1, Range2 r2)
if (is(typeof(binaryFun!pred)) && isForwardRange!Range1 && isForwardRange!Range2 && !isInfinite!Range1 && !isInfinite!Range2);

Проверяет, являются ли два диапазона перестановкой друг друга.

Эта функция может распределять память, если передан флаг Yes.allocateGC . Вариант без выделения памяти имеет большую сложность, чем с опцией Yes.allocateGC. Тем не менее, эта опция доступна только для диапазонов, чьё равенство можно определить через метод toHash каждого элемента. Если требуется равенство, настроенное по заказу пользователя, тогда можно передать параметр шаблона pred, и функция автоматически переключится на не-распределяющий алгоритм. Смотрите std.functional.binaryFun, если нужна дополнительная информация о том, как определять pred.

Время работы без распределения памяти (в том числе с заданным pred): Ο(n^2). Вариант, распределяющий память, работает за: Ο(r1.length) + Ο(r2.length)

Параметры:

pred	дополнительный параметр, изменяющий определение равенства
allocate_gc	Yes.allocateGC/No.allocateGC
Range1 r1	Конечный лидирующий диапазон
Range2 r2	Конечный лидирующий диапазон

Возвращает:

true, если все элементы из r1 появляются то же самое количество раз в r2. В противном случае, возвращает false.

Примеры:

assert(isPermutation([1, 2, 3], [3, 2, 1]));
assert(isPermutation([1.1, 2.3, 3.5], [2.3, 3.5, 1.1]));
assert(isPermutation("abc", "bca"));

assert(!isPermutation([1, 2], [3, 4]));
assert(!isPermutation([1, 1, 2, 3], [1, 2, 2, 3]));
assert(!isPermutation([1, 1], [1, 1, 1]));

// Быстрее, но распределяет память, управляемую сборщиком мусора
assert(isPermutation!(Yes.allocateGC)([1.1, 2.3, 3.5], [2.3, 3.5, 1.1]));
assert(!isPermutation!(Yes.allocateGC)([1, 2], [3, 4]));

CommonType!(T, Ts) either(alias pred = (a) => a, T, Ts...)(T first, lazy Ts alternatives)
if (alternatives.length >= 1 && !is(CommonType!(T, Ts) == void) && allSatisfy!(ifTestable, T, Ts));

Получить первый аргумент a, который пройдёт тест if (unaryFun!pred(a)). Если ни один аргумент не прошёл тест, возвращается последний аргумент.

Подобно поведению оператора or (или) в динамических языках, как например, в Lisp'е (or ...) и в Python'е a or b or ... , за исключением того, что последний аргумент возвращается при отсутствии совпадений.

Упрощает логику, например, в правилах синтаксического анализа, где испытываются множество альтернативных вычислителей. Первый из них, который соответствует, возвращает свой результат совпадения, как правило, в виде абстрактного синтаксического дерева (AST).

Недостатки:

Ленивые параметры к настоящему времени, слишком ограничены, DMD всегда бросает исключения, даже если они не потребовались. Это делает невозможным, к настоящему времени, помечать either как nothrow. Смотрите в Bugzilla issue 12647.

Возвращает:

Первый аргумент, который прошёл тест pred.

Примеры:

const a = 1;
const b = 2;
auto ab = either(a, b);
static assert(is(typeof(ab) == const(int)));
assert(ab == a);

auto c = 2;
const d = 3;
auto cd = either!(a => a == 3)(c, d); // используется предикат
static assert(is(typeof(cd) == int));
assert(cd == d);

auto e = 0;
const f = 2;
auto ef = either(e, f);
static assert(is(typeof(ef) == int));
assert(ef == f);

immutable p = 1;
immutable q = 2;
auto pq = either(p, q);
static assert(is(typeof(pq) == immutable(int)));
assert(pq == p);

assert(either(3, 4) == 3);
assert(either(0, 4) == 4);
assert(either(0, 0) == 0);
assert(either("", "a") == "");

string r = null;
assert(either(r, "a") == "a");
assert(either("a", "") == "a");

immutable s = [1, 2];
assert(either(s, s) == s);

assert(either([0, 1], [1, 2]) == [0, 1]);
assert(either([0, 1], [1]) == [0, 1]);
assert(either("a", "b") == "a");

static assert(!__traits(compiles, either(1, "a")));
static assert(!__traits(compiles, either(1.0, "a")));
static assert(!__traits(compiles, either('a', "a")));