std.algorithm.searching

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

Лицензия:

Boost License 1.0.

Авторы:

Andrei Alexandrescu

Источник

std/algorithm/searching.d

template all(alias pred = "a")

Проверяет, что все элементы удовлетворяют pred.

Примеры:

assert( all!"a & 1"([1, 3, 5, 7, 9]));
assert(!all!"a & 1"([1, 2, 3, 5, 7, 9]));

Примеры:

all также может быть использован без предиката, если его элементы могут быть оценены как true или false в условном операторе. Это может быть удобным способом быстро проверить, что все элементы диапазона равны true.

int[3] vals = [5, 3, 18];
assert( all(vals[]));

bool all(Range)(Range range)
Constraints: if (isInputRange!Range);

Возвращает true тогда и только тогда, когда все значения v в входном диапазоне range удовлетворяют предикату pred. Выполняет (как максимум) Ο(range.length) вычислений pred.

template any(alias pred = "a")

Проверяет, что хотя бы один элемент удовлетворяет pred. !any может быть использован, чтобы проверить, что ни один элемент не удовлетворяет pred. Иногда это называется exists на других языках.

Примеры:

import std.ascii : isWhite;
assert( all!(any!isWhite)(["a a", "b b"]));
assert(!any!(all!isWhite)(["a a", "b b"]));

Примеры:

any также может быть использован без предиката, если его элементы могут быть оценены как true или false в условном операторе. Это может быть удобным способом быстро проверить, что ни один из элементов диапазона не равен true.

int[3] vals1 = [0, 0, 0];
assert(!any(vals1[])); //none of vals1 evaluate to true

int[3] vals2 = [2, 0, 2];
assert( any(vals2[]));
assert(!all(vals2[]));

int[3] vals3 = [3, 3, 3];
assert( any(vals3[]));
assert( all(vals3[]));

bool any(Range)(Range range)
Constraints: if (isInputRange!Range && is(typeof(unaryFun!pred(range.front))));

Возвращает true тогда и только тогда, когда хотя бы одно значение v в входном диапазоне range удовлетворяет предикату pred. Выполняет (как максимум) Ο(range.length) вычислений pred.

bool balancedParens(Range, E)(Range r, E lPar, E rPar, size_t maxNestingLevel = size_t.max)
Constraints: if (isInputRange!Range && is(typeof(r.front == lPar)));

Проверяет, что r имеет "сбалансированные скобки", т.е. все вхождения lPar закрываются соответствующими вхождениями rPar. Параметр maxNestingLevel контролирует разрешенную глубину вложенности. Наиболее распространённые значения - по умолчанию или 0. В последнем случае вложенность не допускается.

Параметры:

Range r	Диапазон для проверки.
E lPar	Элемент, соответствующий левой (открывающей) скобке.
E rPar	Элемент, соответствующий правой (закрывающей) скобке.
size_t maxNestingLevel	Максимальная разрешенная глубина вложенности.

Возвращает:

true, если в заданном диапазоне скобки сбалансированы в рамках заданной максимальной глубины вложенности; в противном случае — false.

Примеры:

auto s = "1 + (2 * (3 + 1 / 2)";
assert(!balancedParens(s, '(', ')'));
s = "1 + (2 * (3 + 1) / 2)";
assert(balancedParens(s, '(', ')'));
s = "1 + (2 * (3 + 1) / 2)";
assert(!balancedParens(s, '(', ')', 0));
s = "1 + (2 * 3 + 1) / (2 - 5)";
assert(balancedParens(s, '(', ')', 0));
s = "f(x) = ⌈x⌉";
assert(balancedParens(s, '⌈', '⌉'));

struct BoyerMooreFinder(alias pred, Range);

BoyerMooreFinder!(binaryFun!pred, Range) boyerMooreFinder(alias pred = "a == b", Range)(Range needle)
Constraints: if (isRandomAccessRange!Range && hasSlicing!Range || isSomeString!Range);

Настраивает алгоритм Бойера-Мура для использования с find ниже. По умолчанию элементы сравниваются на равенство.

BoyerMooreFinder выделяет память GC.

Параметры:

pred	Предикат для сравнения элементов.
Range needle	Диапазон произвольного доступа с длиной и возможностью срезов.

Возвращает:

Экземпляр BoyerMooreFinder, который может быть использован с find() для вызова алгоритма Бойера-Мура для поиска needle в заданном массиве.

Примеры:

auto bmFinder = boyerMooreFinder("TG");

string r = "TAGTGCCTGA";
// search for the first match in the haystack r
r = bmFinder.beFound(r);
writeln(r); // "TGCCTGA"

// continue search in haystack
r = bmFinder.beFound(r[2 .. $]);
writeln(r); // "TGA"

this(Range needle);

scope Range beFound(Range haystack);

@property size_t length();

alias opDollar = length;

auto commonPrefix(alias pred = "a == b", R1, R2)(R1 r1, R2 r2)
Constraints: if (isForwardRange!R1 && isInputRange!R2 && !isNarrowString!R1 && is(typeof(binaryFun!pred(r1.front, r2.front))));

auto commonPrefix(alias pred, R1, R2)(R1 r1, R2 r2)
Constraints: if (isNarrowString!R1 && isInputRange!R2 && is(typeof(binaryFun!pred(r1.front, r2.front))));

auto commonPrefix(R1, R2)(R1 r1, R2 r2)
Constraints: if (isNarrowString!R1 && isInputRange!R2 && !isNarrowString!R2 && is(typeof(r1.front == r2.front)));

auto commonPrefix(R1, R2)(R1 r1, R2 r2)
Constraints: if (isNarrowString!R1 && isNarrowString!R2);

Возвращает общее префиксное подмножество двух диапазонов.

Параметры:

pred	Предикат для сравнения элементов на предмет общности. По умолчанию используется равенство "a == b".
R1 r1	Диапазон элементов.
R2 r2	Входной диапазон элементов.

Возвращает:

Срез r1 содержащий символы, с которых оба диапазона начинаются, если первый аргумент — строка; в противном случае, то же, что и результат takeExactly(r1, n), где n — количество элементов в общем префиксе обоих диапазонов.

См. также:

std.range.takeExactly

Примеры:

writeln(commonPrefix("hello, world", "hello, there")); // "hello, "

size_t count(alias pred = "a == b", Range, E)(Range haystack, E needle)
Constraints: if (isInputRange!Range && !isInfinite!Range && is(typeof(binaryFun!pred(haystack.front, needle)) : bool));

size_t count(alias pred = "a == b", R1, R2)(R1 haystack, R2 needle)
Constraints: if (isForwardRange!R1 && !isInfinite!R1 && isForwardRange!R2 && is(typeof(binaryFun!pred(haystack.front, needle.front)) : bool));

size_t count(alias pred, R)(R haystack)
Constraints: if (isInputRange!R && !isInfinite!R && is(typeof(unaryFun!pred(haystack.front)) : bool));

size_t count(R)(R haystack)
Constraints: if (isInputRange!R && !isInfinite!R);

Первый вариант подсчитывает количество элементов x в r для которых pred(x, value) равно true. pred по умолчанию равно равенству. Выполняет Ο(haystack.length) вычислений pred.

Второй вариант возвращает количество раз, когда needle встречается в haystack. Бросает исключение, если needle.empty, так как количество пустого диапазона в любом диапазоне будет бесконечным. Перекрывающиеся подсчеты не учитываются, например count("aaa", "aa") равно 1, а не 2.

Третий вариант подсчитывает элементы, для которых pred(x) равно true. Выполняет Ο(haystack.length) вычислений pred.

Четвёртый вариант подсчитывает количество элементов в диапазоне. Это оптимизация для третьего варианта: если заданный диапазон имеет свойство length, то счет возвращается сразу же, иначе выполняется Ο(haystack.length) для обхода диапазона.

Примечание

Независимо от перегрузки, count не будет принимать бесконечные диапазоны для haystack.

Параметры:

pred	Предикат для оценки.
Range haystack	Диапазон для подсчета.
E needle	Элемент или поддиапазон для подсчета в haystack.

Возвращает:

Количество позиций в haystack для которых pred вернул true.

Примеры:

import std.uni : toLower;

// count elements in range
int[] a = [ 1, 2, 4, 3, 2, 5, 3, 2, 4 ];
writeln(count(a)); // 9
writeln(count(a, 2)); // 3
writeln(count!("a > b")(a, 2)); // 5
// count range in range
writeln(count("abcadfabf", "ab")); // 2
writeln(count("ababab", "abab")); // 1
writeln(count("ababab", "abx")); // 0
// fuzzy count range in range
writeln(count!((a, b) => toLower(a) == toLower(b))("AbcAdFaBf", "ab")); // 2
// count predicate in range
writeln(count!("a > 1")(a)); // 8

ptrdiff_t countUntil(alias pred = "a == b", R, Rs...)(R haystack, Rs needles)
Constraints: if (isForwardRange!R && (Rs.length > 0) && (isForwardRange!(Rs[0]) == isInputRange!(Rs[0])) && is(typeof(startsWith!pred(haystack, needles[0]))) && (Rs.length == 1 || is(typeof(countUntil!pred(haystack, needles[1..$])))));

ptrdiff_t countUntil(alias pred = "a == b", R, N)(R haystack, N needle)
Constraints: if (isInputRange!R && is(typeof(binaryFun!pred(haystack.front, needle)) : bool));

ptrdiff_t countUntil(alias pred, R)(R haystack)
Constraints: if (isInputRange!R && is(typeof(unaryFun!pred(haystack.front)) : bool));

Подсчитывает элементы в заданном прямолинейном диапазоне до тех пор, пока заданный предикат не станет истинным для одного из заданных needles.

Параметры:

pred	Предикат для определения момента прекращения подсчёта.
R haystack	Диапазон ввода для подсчёта.
Rs needles	Либо отдельный элемент, либо прямолинейный диапазон элементов, которые поочерёдно будут оцениваться относительно каждого элемента в haystack в соответствии с заданным предикатом.

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

Количество элементов, которые необходимо удалить из начала haystack, прежде чем будет достигнут элемент, для которого startsWith!pred(haystack, needles) равно true. Если startsWith!pred(haystack, needles) не равно true ни для одного элемента в haystack, то возвращается -1. Если предоставлен только pred, то pred(haystack) проверяется для каждого элемента.

См. также:

std.string.indexOf

Примеры:

writeln(countUntil("hello world", "world")); // 6
writeln(countUntil("hello world", 'r')); // 8
writeln(countUntil("hello world", "programming")); // -1
writeln(countUntil("日本語", "本語")); // 1
writeln(countUntil("日本語", '語')); // 2
writeln(countUntil("日本語", "五")); // -1
writeln(countUntil("日本語", '五')); // -1
writeln(countUntil([0, 7, 12, 22, 9], [12, 22])); // 2
writeln(countUntil([0, 7, 12, 22, 9], 9)); // 4
writeln(countUntil!"a > b"([0, 7, 12, 22, 9], 20)); // 3

Примеры:

import std.ascii : isDigit;
import std.uni : isWhite;

writeln(countUntil!(std.uni.isWhite)("hello world")); // 5
writeln(countUntil!(std.ascii.isDigit)("hello world")); // -1
writeln(countUntil!"a > 20"([0, 7, 12, 22, 9])); // 3

uint endsWith(alias pred = "a == b", Range, Needles...)(Range doesThisEnd, Needles withOneOfThese)
Constraints: if (isBidirectionalRange!Range && (Needles.length > 1) && is(typeof(.endsWith!pred(doesThisEnd, withOneOfThese[0])) : bool) && is(typeof(.endsWith!pred(doesThisEnd, withOneOfThese[1..$])) : uint));

bool endsWith(alias pred = "a == b", R1, R2)(R1 doesThisEnd, R2 withThis)
Constraints: if (isBidirectionalRange!R1 && isBidirectionalRange!R2 && is(typeof(binaryFun!pred(doesThisEnd.back, withThis.back)) : bool));

bool endsWith(alias pred = "a == b", R, E)(R doesThisEnd, E withThis)
Constraints: if (isBidirectionalRange!R && is(typeof(binaryFun!pred(doesThisEnd.back, withThis)) : bool));

bool endsWith(alias pred, R)(R doesThisEnd)
Constraints: if (isInputRange!R && ifTestable!(typeof(doesThisEnd.front), unaryFun!pred));

Проверяет, заканчивается ли заданный диапазон (одним из) заданных искомых элементов. Обратная функция startsWith.

Параметры:

pred	Предикат для сравнения элементов между диапазоном и искомыми элементами.
Range doesThisEnd	Двунаправленный диапазон для проверки.
Needles withOneOfThese	Искомые элементы для проверки, которые могут быть отдельными элементами или двунаправленными диапазонами элементов.
R2 withThis	Отдельный элемент для проверки.

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

0, если искомые элементы не находятся в конце заданного диапазона; иначе позиция совпавшего искомого элемента, то есть 1, если диапазон заканчивается на withOneOfThese[0], 2, если он заканчивается на withOneOfThese[1], и так далее. В случае, когда не заданы параметры искомых элементов, возвращается true если конец doesThisStart удовлетворяет предикату pred.

Примеры:

import std.ascii : isAlpha;
assert("abc".endsWith!(a => a.isAlpha));
assert("abc".endsWith!isAlpha);

assert(!"ab1".endsWith!(a => a.isAlpha));

assert(!"ab1".endsWith!isAlpha);
assert(!"".endsWith!(a => a.isAlpha));

import std.algorithm.comparison : among;
assert("abc".endsWith!(a => a.among('c', 'd') != 0));
assert(!"abc".endsWith!(a => a.among('a', 'b') != 0));

assert(endsWith("abc", ""));
assert(!endsWith("abc", "b"));
writeln(endsWith("abc", "a", 'c')); // 2
writeln(endsWith("abc", "c", "a")); // 1
writeln(endsWith("abc", "c", "c")); // 1
writeln(endsWith("abc", "bc", "c")); // 2
writeln(endsWith("abc", "x", "c", "b")); // 2
writeln(endsWith("abc", "x", "aa", "bc")); // 3
writeln(endsWith("abc", "x", "aaa", "sab")); // 0
writeln(endsWith("abc", "x", "aaa", 'c', "sab")); // 3

InputRange find(alias pred = "a == b", InputRange, Element)(InputRange haystack, scope Element needle)
Constraints: if (isInputRange!InputRange && is(typeof(binaryFun!pred(haystack.front, needle)) : bool) && !is(typeof(binaryFun!pred(haystack.front, needle.front)) : bool));

InputRange find(alias pred, InputRange)(InputRange haystack)
Constraints: if (isInputRange!InputRange);

R1 find(alias pred = "a == b", R1, R2)(R1 haystack, scope R2 needle)
Constraints: if (isForwardRange!R1 && isForwardRange!R2 && is(typeof(binaryFun!pred(haystack.front, needle.front)) : bool));

Находит отдельный элемент в диапазоне ввода. Элементы haystack сравниваются с needle с помощью предиката pred и pred(haystack.front, needle). find выполняет Ο(walkLength(haystack)) вычислений pred.

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

Чтобы найти последнее вхождение needle в двунаправленном haystack, вызовите find(retro(haystack), needle). См. std.range.retro.

Если needle не указан, pred(haystack.front) будет вычисляться для каждого элемента диапазона ввода.

Если input является прямолинейным диапазоном, needle также может быть прямолинейным диапазоном. В этом случае startsWith!pred(haystack, needle) вычисляется при каждой проверке.

Примечание

find работает аналогично dropWhile в других языках.

Сложность

find выполняет Ο(walkLength(haystack)) вычислений pred. Существуют специализации, которые улучшают производительность, используя преимущества двунаправленных или случайных диапазонов (если это возможно).

Параметры:

pred	Предикат для сравнения каждого элемента с искомым элементом, по умолчанию сравнивающий на равенство "a == b". Отрицательный предикат "a != b" можно использовать для поиска вместо первого элемента, не соответствующего искомому элементу.
InputRange haystack	Диапазон ввода для поиска.
Element needle	Искомый элемент.

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

haystack перемещён таким образом, что передний элемент является искомым; то есть, до тех пор, пока binaryFun!pred(haystack.front, needle) не будет true. Если такой позиции не существует, возвращается пустой haystack.

См. также:

findAdjacent, findAmong, findSkip, findSplit, startsWith

Примеры:

import std.range.primitives;

auto arr = [1, 2, 4, 4, 4, 4, 5, 6, 9];
writeln(arr.find(4)); // [4, 4, 4, 4, 5, 6, 9]
writeln(arr.find(1)); // arr
writeln(arr.find(9)); // [9]
writeln(arr.find!((a, b) => a > b)(4)); // [5, 6, 9]
writeln(arr.find!((a, b) => a < b)(4)); // arr
assert(arr.find(0).empty);
assert(arr.find(10).empty);
assert(arr.find(8).empty);

writeln(find("hello, world", ',')); // ", world"

Примеры:

Регистронезависимый поиск строки

import std.range.primitives;
import std.uni : toLower;

string[] s = ["Hello", "world", "!"];
writeln(s.find!((a, b) => toLower(a) == b)("hello")); // s

Примеры:

auto arr = [ 1, 2, 3, 4, 1 ];
writeln(find!("a > 2")(arr)); // [3, 4, 1]

// with predicate alias
bool pred(int x) { return x + 1 > 1.5; }
writeln(find!(pred)(arr)); // arr

Примеры:

import std.container : SList;
import std.range.primitives : empty;
import std.typecons : Tuple;

assert(find("hello, world", "World").empty);
writeln(find("hello, world", "wo")); // "world"
writeln([1, 2, 3, 4].find(SList!int(2, 3)[])); // [2, 3, 4]
alias C = Tuple!(int, "x", int, "y");
auto a = [C(1,0), C(2,0), C(3,1), C(4,0)];
writeln(a.find!"a.x == b"([2, 3])); // [C(2, 0), C(3, 1), C(4, 0)]
writeln(a[1 .. $].find!"a.x == b"([2, 3])); // [C(2, 0), C(3, 1), C(4, 0)]

Tuple!(Range, size_t) find(alias pred = "a == b", Range, Ranges...)(Range haystack, Ranges needles)
Constraints: if (Ranges.length > 1 && is(typeof(startsWith!pred(haystack, needles))));

Находит два или более needles в haystack. Предикат pred используется для сравнения элементов. По умолчанию элементы сравниваются на равенство.

Параметры:

pred	Предикат для сравнения элементов.
Range haystack	Цель поиска. Должен быть диапазон ввода. Если любой из needles является диапазоном с элементами, сравнимыми с элементами в haystack, то haystack должен быть прямолинейным диапазоном, чтобы поиск мог отступать назад.
Ranges needles	Один или несколько элементов поиска. Каждый из needles должен быть либо сравним с одним элементом в haystack, либо сам быть прямолинейным диапазоном с элементами, сравнимыми с элементами в haystack.

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

Кортеж, содержащий haystack, позицию совпадения с одним из искомых элементов, а также индекс совпавшего элемента в needles (0, если ни один из needles не совпал, 1, если совпал needles[0], 2, если совпал needles[1], и так далее). Первый искомый элемент, который будет найден, будет тем, который совпадёт. Если несколько искомых элементов найдены в одном и том же месте в диапазоне, то кратчайший из них является совпавшим (если несколько искомых элементов одинаковой длины найдены в одном и том же месте (например, "a" и 'a'), то совпадает левее них в списке аргументов). Связь между haystack и needles означает, что можно, например, искать отдельные int или массивы int в массиве int . Кроме того, если элементы сравнимы по отдельности, разрешены поиски гетерогенных типов: за double[] может быть найдено int или short[], и наоборот, за long может быть найдено float или double[]. Это позволяет выполнять эффективный поиск без необходимости приведения одного из сторон сравнения к типу другой стороны. Сложность поиска составляет Ο(haystack.length * max(needles.length)). (Для искомых элементов, представляющих собой отдельные элементы, длина считается равной 1.) Стратегия поиска нескольких поддиапазонов одновременно максимально использует кэш, перемещаясь в haystack как можно реже.

Примеры:

import std.typecons : tuple;
int[] a = [ 1, 4, 2, 3 ];
writeln(find(a, 4)); // [4, 2, 3]
writeln(find(a, [1, 4])); // [1, 4, 2, 3]
writeln(find(a, [1, 3], 4)); // tuple([4, 2, 3], 2)
// Mixed types allowed if comparable
writeln(find(a, 5, [1.2, 3.5], 2.0)); // tuple([2, 3], 3)

RandomAccessRange find(RandomAccessRange, alias pred, InputRange)(RandomAccessRange haystack, scope BoyerMooreFinder!(pred, InputRange) needle);

Эффективно находит needle в haystack с помощью алгоритма Бойера-Мура.

Параметры:

RandomAccessRange haystack	Диапазон с произвольным доступом, имеющий длину и возможность срезов.
BoyerMooreFinder!(pred, InputRange) needle	BoyerMooreFinder.

Возвращает:

haystack сдвинутый так, что needle является его префиксом (если такая позиция не существует, возвращает haystack сдвинутый до конца).

Примеры:

import std.range.primitives : empty;
int[] a = [ -1, 0, 1, 2, 3, 4, 5 ];
int[] b = [ 1, 2, 3 ];

writeln(find(a, boyerMooreFinder(b))); // [1, 2, 3, 4, 5]
assert(find(b, boyerMooreFinder(a)).empty);

шаблон canFind(псевдоним pred = "a == b")

Удобная функция. Похожа на функцию find, но возвращает только результат поиска (успешно или нет).

См. также:

std.algorithm.comparison.among для проверки значения по отношению к нескольким вариантам.

Примеры:

writeln(canFind([0, 1, 2, 3], 2)); // true
assert(canFind([0, 1, 2, 3], [1, 2], [2, 3]));
writeln(canFind([0, 1, 2, 3], [1, 2], [2, 3])); // 1
assert(canFind([0, 1, 2, 3], [1, 7], [2, 3]));
writeln(canFind([0, 1, 2, 3], [1, 7], [2, 3])); // 2

writeln(canFind([0, 1, 2, 3], 4)); // false
assert(!canFind([0, 1, 2, 3], [1, 3], [2, 4]));
writeln(canFind([0, 1, 2, 3], [1, 3], [2, 4])); // 0

Примеры:

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

auto words = [
    "apple",
    "beeswax",
    "cardboard"
];
assert(!canFind(words, "bees"));
assert( canFind!((string a, string b) => a.startsWith(b))(words, "bees"));

Примеры:

Поиск нескольких элементов в массиве элементов (поиск иглы в стоге сена)

string s1 = "aaa111aaa";
string s2 = "aaa222aaa";
string s3 = "aaa333aaa";
string s4 = "aaa444aaa";
const hay = [s1, s2, s3, s4];
assert(hay.canFind!(e => (e.canFind("111", "222"))));

bool canFind(Range)(Range haystack)
Ограничения: если (is(typeof(find!pred(haystack))));

Возвращает true тогда и только тогда, когда любое значение v в входящем диапазоне range удовлетворяет предикату pred. Выполняет (по максимуму) Ο(haystack.length) вычислений pred.

bool canFind(Range, Element)(Range haystack, scope Element needle)
Ограничения: если (is(typeof(find!pred(haystack, needle))));

Возвращает true тогда и только тогда, когда needle можно найти в range. Выполняет Ο(haystack.length) вычислений pred.

size_t canFind(Range, Ranges...)(Range haystack, scope Ranges needles)
Ограничения: если (Ranges.length > 1 && allSatisfy!(isForwardRange, Ranges) && is(typeof(find!pred(haystack, needles))));

Возвращает индекс (с учётом начала с 1) первого найденного элемента needle в haystack. Если ни один элемент needle не найден, то возвращается 0.

Таким образом, при использовании непосредственно в условии оператора if или цикла, результат будет true если один из элементов needle найден и false если ни один не найден, в то время как если результат используется где-то ещё, его можно привести к типу bool для того же эффекта или использовать для получения того, какой элемент needle был найден первым, не имея дело с кортежем, который LREF find возвращает для той же операции.

Range findAdjacent(псевдоним pred = "a == b", Range)(Range r)
Ограничения: если (isForwardRange!Range);

Сдвигает r до тех пор, пока не найдёт первые два смежных элемента a, b удовлетворяющие условию pred(a, b). Выполняет Ο(r.length) вычислений pred.

Параметры:

pred	Предикат для проверки.
Range r	диапазон следования для поиска.

Возвращает:

r сдвинутый до первой пары смежных элементов, удовлетворяющих заданному предикату. Если таких элементов нет, возвращает r сдвинутый до конца.

См. также:

STL's adjacent_find

Примеры:

int[] a = [ 11, 10, 10, 9, 8, 8, 7, 8, 9 ];
auto r = findAdjacent(a);
writeln(r); // [10, 10, 9, 8, 8, 7, 8, 9]
auto p = findAdjacent!("a < b")(a);
writeln(p); // [7, 8, 9]

InputRange findAmong(псевдоним pred = "a == b", InputRange, ForwardRange)(InputRange seq, ForwardRange choices)
Ограничения: если (isInputRange!InputRange && isForwardRange!ForwardRange);

Ищет в данном диапазоне элемент, соответствующий одному из заданных вариантов.

Сдвигает seq вызывая seq.popFront до тех пор, пока find!(pred)(choices, seq.front) не будет true, или seq не станет пустым. Выполняет Ο(seq.length * choices.length) вычислений pred.

Параметры:

pred	Предикат для определения соответствия.
InputRange seq	Диапазон входных данных для поиска.
ForwardRange choices	Диапазон следования возможных вариантов.

Возвращает:

seq сдвинутый до первого соответствующего элемента, или пустой, если соответствующих элементов нет.

См. также:

find, algorithm.comparison.among.std

Примеры:

int[] a = [ -1, 0, 1, 2, 3, 4, 5 ];
int[] b = [ 3, 1, 2 ];
writeln(findAmong(a, b)); // a[2 .. $]

bool findSkip(псевдоним pred = "a == b", R1, R2)(ref R1 haystack, R2 needle)
Ограничения: если (isForwardRange!R1 && isForwardRange!R2 && is(typeof(binaryFun!pred(haystack.front, needle.front))));

size_t findSkip(псевдоним pred, R1)(ref R1 haystack)
Ограничения: если (isForwardRange!R1 && ifTestable!(typeof(haystack.front), unaryFun!pred));

Находит needle в haystack и позиционирует haystack сразу после первого вхождения needle.

Если иголка не задана, haystack сдвигается до тех пор, пока pred возвращает true. Аналогично, стог сена позиционируется таким образом, что pred возвращает false для haystack.front.

Параметры:

R1 haystack	Диапазон следования для поиска.
R2 needle	Диапазон следования для поиска.
pred	Пользовательский предикат для сравнения стога сена и иголки.

Возвращает:

true если иголка была найдена, в этом случае haystack позиционируется после конца первого вхождения needle; в противном случае false, оставляя haystack без изменений. Если иголка не задана, возвращает количество раз, когда pred(haystack.front) возвращает true.

См. также:

find

Примеры:

import std.range.primitives : empty;
// Needle is found; s is replaced by the substring following the first
// occurrence of the needle.
string s = "abcdef";
assert(findSkip(s, "cd") && s == "ef");

// Needle is not found; s is left untouched.
s = "abcdef";
assert(!findSkip(s, "cxd") && s == "abcdef");

// If the needle occurs at the end of the range, the range is left empty.
s = "abcdef";
assert(findSkip(s, "def") && s.empty);

Примеры:

import std.ascii : isWhite;
string s = "    abc";
assert(findSkip!isWhite(s) && s == "abc");
assert(!findSkip!isWhite(s) && s == "abc");

s = "  ";
writeln(findSkip!isWhite(s)); // 2

auto findSplit(псевдоним pred = "a == b", R1, R2)(R1 haystack, R2 needle)
Ограничения: если (isForwardRange!R1 && isForwardRange!R2);

auto findSplitBefore(псевдоним pred = "a == b", R1, R2)(R1 haystack, R2 needle)
Ограничения: если (isForwardRange!R1 && isForwardRange!R2);

auto findSplitAfter(псевдоним pred = "a == b", R1, R2)(R1 haystack, R2 needle)
Ограничения: если (isForwardRange!R1 && isForwardRange!R2);

Эти функции находят первое вхождение needle в haystack и затем разбивают haystack следующим образом.

findSplit возвращает кортеж result содержащий три диапазона. result[0] — это часть haystack перед needle, result[1] — это часть haystack которая соответствует needle, а result[2] — это часть haystack после совпадения. Если needle не найдено, result[0] охватывает haystack целиком, а result[1] и result[2] пустые.

findSplitBefore возвращает кортеж result содержащий два диапазона. result[0] — это часть haystack перед needle, а result[1] — это остаток haystack начиная с совпадения. Если needle не найдено, result[0] охватывает haystack целиком, а result[1] пусто.

findSplitAfter возвращает кортеж result содержащий два диапазона. result[0] — это часть haystack вплоть до и включая совпадение, а result[1] — это остаток haystack начиная после совпадения. Если needle не найдено, result[0] пусто, а result[1] — это haystack.

Во всех случаях конкатенация возвращаемых диапазонов охватывает весь haystack.

Если haystack — это диапазон с произвольным доступом, все три компонента кортежа имеют тот же тип, что и haystack. В противном случае, haystack должен быть диапазоном вперёд, а тип result[0] и result[1] такой же, как у std.range.takeExactly.

Параметры:

pred	Предикат для сравнения искомого элемента с исходным диапазоном.
R1 haystack	Диапазон для поиска.
R2 needle	Что искать.

Возвращает:

Подтип Tuple!() из разбитых частей haystack (см. подробности выше). Этот подтип Tuple!() имеет opCast определён для bool. Этот opCast возвращает true когда разделитель needle найден и false в противном случае.

См. также:

find

Примеры:

Возвращение подтипа std.typecons.Tuple позволяет использовать следующее удобное выражение:

// findSplit returns a triplet
if (auto split = "dlang-rocks".findSplit("-"))
{
    writeln(split[0]); // "dlang"
    writeln(split[1]); // "-"
    writeln(split[2]); // "rocks"
}
else assert(0);

// works with const aswell
if (const split = "dlang-rocks".findSplit("-"))
{
    writeln(split[0]); // "dlang"
    writeln(split[1]); // "-"
    writeln(split[2]); // "rocks"
}
else assert(0);

Примеры:

import std.range.primitives : empty;

auto a = "Carl Sagan Memorial Station";
auto r = findSplit(a, "Velikovsky");
import std.typecons : isTuple;
static assert(isTuple!(typeof(r.asTuple)));
static assert(isTuple!(typeof(r)));
assert(!r);
writeln(r[0]); // a
assert(r[1].empty);
assert(r[2].empty);
r = findSplit(a, " ");
writeln(r[0]); // "Carl"
writeln(r[1]); // " "
writeln(r[2]); // "Sagan Memorial Station"
if (const r1 = findSplitBefore(a, "Sagan"))
{
    assert(r1);
    writeln(r1[0]); // "Carl "
    writeln(r1[1]); // "Sagan Memorial Station"
}
if (const r2 = findSplitAfter(a, "Sagan"))
{
    assert(r2);
    writeln(r2[0]); // "Carl Sagan"
    writeln(r2[1]); // " Memorial Station"
}

Примеры:

Используйте std.range.only для поиска отдельных элементов:

import std.range : only;
writeln([1, 2, 3, 4].findSplitBefore(only(3))[0]); // [1, 2]

Tuple!(ElementType!Range, size_t) minCount(alias pred = "a < b", Range)(Range range)
Constraints: if (isInputRange!Range && !isInfinite!Range && is(typeof(binaryFun!pred(range.front, range.front))));

Tuple!(ElementType!Range, size_t) maxCount(alias pred = "a < b", Range)(Range range)
Constraints: if (isInputRange!Range && !isInfinite!Range && is(typeof(binaryFun!pred(range.front, range.front))));

Вычисляет минимум (соответственно максимум) range вместе с количеством его вхождений. Формально, минимум — это значение x в range такое, что pred(a, x) меньше или равно false для всех значений a в range. Обратно, максимум — это значение x в range такое, что pred(x, a) больше или равно false для всех значений a в range (обратите внимание на переставленные аргументы в pred).

Эти функции могут быть использованы для вычисления произвольных экстремумов, выбрав подходящее pred. Для корректной работы pred должен быть строго частичным порядком, т. е. транзитивным (если pred(a, b) && pred(b, c) то pred(a, c) ) и иррефлексивным (pred(a, a) не равно false). Свойство трихотомии неравенства не требуется: эти алгоритмы рассматривают элементы a и b равными (для подсчёта), если pred помещает их в один класс эквивалентности, т. е. !pred(a, b) && !pred(b, a).

Параметры:

pred	Предикат упорядочения для определения экстремума (минимума или максимума).
Range range	Диапазон входных данных для подсчёта.

Возвращает:

Минимальный, соответственно максимальный элемент диапазона вместе с количеством его вхождений в диапазон.

Ограничения

Если хотя бы один из аргументов — NaN, результат неопределён. См. std.algorithm.searching.maxElement для примеров, как обойти NaN.

Исключения:

Exception если range.empty.

См. также:

std.algorithm.comparison.min, minIndex, minElement, minPos

Примеры:

import std.conv : text;
import std.typecons : tuple;

int[] a = [ 2, 3, 4, 1, 2, 4, 1, 1, 2 ];
// Minimum is 1 and occurs 3 times
writeln(a.minCount); // tuple(1, 3)
// Maximum is 4 and occurs 2 times
writeln(a.maxCount); // tuple(4, 2)

auto minElement(alias map = (a) => a, Range)(Range r)
Constraints: if (isInputRange!Range && !isInfinite!Range);

auto minElement(alias map = (a) => a, Range, RangeElementType = ElementType!Range)(Range r, RangeElementType seed)
Constraints: if (isInputRange!Range && !isInfinite!Range && !is(CommonType!(ElementType!Range, RangeElementType) == void));

Итерирует переданный диапазон и возвращает минимальный элемент. Можно передать пользовательскую функцию отображения для map. В других языках это иногда называется argmin.

Сложность

O(n) Необходимо точно n - 1 сравнений.

Параметры:

map	Пользовательский аксессор для ключа сравнения
Range r	Диапазон, из которого будет выбран минимальный элемент
RangeElementType seed	Пользовательское начальное значение для использования в качестве начального элемента

Возвращает:

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

Примечание

Если хотя бы один из аргументов — NaN, результат неопределён.

Если вы хотите игнорировать NaN, вы можете использовать std.algorithm.iteration.filter и std.math.isNaN для их удаления перед применением minElement. Добавьте подходящее начальное значение, чтобы избежать сообщений об ошибках, если все элементы — NaN:

<range>.filter!(a=>!a.isNaN).minElement(<seed>);

Если вы хотите получить NaN в качестве результата, если в диапазоне присутствует NaN, вы можете использовать std.algorithm.iteration.fold и std.math.isNaN:

<range>.fold!((a,b)=>a.isNaN || b.isNaN ? real.nan : a < b ? a : b);

См. также:

maxElement, std.algorithm.comparison.min, minCount, minIndex, minPos

Примеры:

import std.range : enumerate;
import std.typecons : tuple;

writeln([2, 7, 1, 3].minElement); // 1

// allows to get the index of an element too
writeln([5, 3, 7, 9].enumerate.minElement!"a.value"); // tuple(1, 3)

// any custom accessor can be passed
writeln([[0, 4], [1, 2]].minElement!"a[1]"); // [1, 2]

// can be seeded
int[] arr;
writeln(arr.minElement(1)); // 1

auto maxElement(alias map = (a) => a, Range)(Range r)
Constraints: if (isInputRange!Range && !isInfinite!Range);

auto maxElement(alias map = (a) => a, Range, RangeElementType = ElementType!Range)(Range r, RangeElementType seed)
Constraints: if (isInputRange!Range && !isInfinite!Range && !is(CommonType!(ElementType!Range, RangeElementType) == void));

Итерирует переданный диапазон и возвращает максимальный элемент. Можно передать пользовательскую функцию отображения для map. В других языках это иногда называется argmax.

Сложность

O(n) Необходимо точно n - 1 сравнений.

Параметры:

map	Пользовательский аксессор для ключа сравнения
Range r	Диапазон, из которого будет выбран максимальный элемент
RangeElementType seed	Пользовательское начальное значение для использования в качестве начального элемента

Возвращает:

Максимальный элемент переданного диапазона.

Примечание

Если хотя бы один из аргументов — NaN, результат неопределён. См. std.algorithm.searching.minElement для примеров, как обойти NaN.

См. также:

minElement, std.algorithm.comparison.max, maxCount, maxIndex, maxPos

Примеры:

import std.range : enumerate;
import std.typecons : tuple;
writeln([2, 1, 4, 3].maxElement); // 4

// allows to get the index of an element too
writeln([2, 1, 4, 3].enumerate.maxElement!"a.value"); // tuple(2, 4)

// any custom accessor can be passed
writeln([[0, 4], [1, 2]].maxElement!"a[1]"); // [0, 4]

// can be seeded
int[] arr;
writeln(arr.minElement(1)); // 1

Range minPos(alias pred = "a < b", Range)(Range range)
Constraints: if (isForwardRange!Range && !isInfinite!Range && is(typeof(binaryFun!pred(range.front, range.front))));

Range maxPos(alias pred = "a < b", Range)(Range range)
Constraints: if (isForwardRange!Range && !isInfinite!Range && is(typeof(binaryFun!pred(range.front, range.front))));

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

Формально, минимальное значение — это значение x в range, такое что pred(a, x) является false для всех значений a в range. Обратно, максимальное значение — это значение x в range, такое что pred(x, a) является false для всех значений a в range (обратите внимание на переставленные аргументы в pred).

Эти функции могут использоваться для вычисления произвольных экстремумов, соответствующим образом выбрав pred. Для корректной работы pred должно быть строгим частичным порядком, то есть транзитивным (если pred(a, b) && pred(b, c) то pred(a, c)) и иррефлексивным (pred(a, a) не равно false).

Параметры:

pred	Предикат упорядочения, используемый для определения экстремального элемента (минимального или максимального).
Диапазон range	Прямой диапазон для поиска.

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

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

Ограничения

Если хотя бы один из аргументов — NaN, результат является неопределённым. См. std.algorithm.searching.maxElement для примеров обработки NaN.

См. также:

std.algorithm.comparison.max, minCount, minIndex, minElement

Примеры:

int[] a = [ 2, 3, 4, 1, 2, 4, 1, 1, 2 ];
// Minimum is 1 and first occurs in position 3
writeln(a.minPos); // [1, 2, 4, 1, 1, 2]
// Maximum is 4 and first occurs in position 2
writeln(a.maxPos); // [4, 1, 2, 4, 1, 1, 2]

ptrdiff_t minIndex(alias pred = "a < b", Range)(Range range)
Constraints: if (isInputRange!Range && !isInfinite!Range && is(typeof(binaryFun!pred(range.front, range.front))));

Вычисляет индекс первого вхождения минимального элемента range.

Параметры:

pred	Предикат упорядочения, используемый для определения минимального элемента.
Диапазон range	входной диапазон для поиска.

Сложность

Ο(range.length) Требуется ровно range.length - 1 сравнений.

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

Индекс первого вхождения минимального элемента в range. Если range пуст, возвращается -1.

Ограничения

Если хотя бы один из аргументов — NaN, результат является неопределённым. См. std.algorithm.searching.maxElement для примеров обработки NaN.

См. также:

maxIndex, std.algorithm.comparison.min, minCount, minElement, minPos

Примеры:

int[] a = [2, 3, 4, 1, 2, 4, 1, 1, 2];

// Minimum is 1 and first occurs in position 3
writeln(a.minIndex); // 3
// Get maximum index with minIndex
writeln(a.minIndex!"a > b"); // 2

// Range is empty, so return value is -1
int[] b;
writeln(b.minIndex); // -1

// Works with more custom types
struct Dog { int age; }
Dog[] dogs = [Dog(10), Dog(5), Dog(15)];
writeln(dogs.minIndex!"a.age < b.age"); // 1

ptrdiff_t maxIndex(alias pred = "a < b", Range)(Range range)
Constraints: if (isInputRange!Range && !isInfinite!Range && is(typeof(binaryFun!pred(range.front, range.front))));

Вычисляет индекс первого вхождения максимального элемента range.

Сложность

Ο(range) Требуется ровно range.length - 1 сравнений.

Параметры:

pred	Предикат упорядочения, используемый для определения максимального элемента.
Диапазон range	входной диапазон для поиска.

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

Индекс первого вхождения максимального элемента в range. Если range пуст, возвращается -1.

Ограничения

Если хотя бы один из аргументов — NaN, результат является неопределённым. См. std.algorithm.searching.maxElement для примеров обработки NaN.

См. также:

minIndex, std.algorithm.comparison.max, maxCount, maxElement, maxPos

Примеры:

// Maximum is 4 and first occurs in position 2
int[] a = [2, 3, 4, 1, 2, 4, 1, 1, 2];
writeln(a.maxIndex); // 2

// Empty range
int[] b;
writeln(b.maxIndex); // -1

// Works with more custom types
struct Dog { int age; }
Dog[] dogs = [Dog(10), Dog(15), Dog(5)];
writeln(dogs.maxIndex!"a.age < b.age"); // 1

template skipOver(alias pred = (a, b) => a == b)

Пропускает начальную часть первого заданного диапазона (haystack) что соответствует любому из дополнительных диапазонов (needles) полностью, или, если второй диапазон не задан, пропускает элементы, удовлетворяющие pred. Ничего не делает, если соответствия нет.

Параметры:

pred	Предикат, определяющий соответствие элементов из каждого соответствующего диапазона. По умолчанию — равенство "a == b".

Примеры:

import std.algorithm.comparison : equal;

auto s1 = "Hello world";
assert(!skipOver(s1, "Ha"));
writeln(s1); // "Hello world"
assert(skipOver(s1, "Hell") && s1 == "o world", s1);

string[]  r1 = ["abc", "def", "hij"];
dstring[] r2 = ["abc"d];
assert(!skipOver!((a, b) => a.equal(b))(r1, ["def"d]), r1[0]);
writeln(r1); // ["abc", "def", "hij"]
assert(skipOver!((a, b) => a.equal(b))(r1, r2));
writeln(r1); // ["def", "hij"]

Примеры:

import std.ascii : isWhite;
import std.range.primitives : empty;

auto s2 = "\t\tvalue";
auto s3 = "";
auto s4 = "\t\t\t";
assert(s2.skipOver!isWhite && s2 == "value");
assert(!s3.skipOver!isWhite);
assert(s4.skipOver!isWhite && s3.empty);

Примеры:

Многоаргументный skipOver

auto s = "Hello world";
assert(!skipOver(s, "hello", "HellO"));
writeln(s); // "Hello world"

// the range is skipped over the longest matching needle is skipped
assert(skipOver(s, "foo", "hell", "Hello "));
writeln(s); // "world"

Примеры:

import std.algorithm.comparison : equal;

auto s1 = "Hello world";
assert(!skipOver(s1, 'a'));
writeln(s1); // "Hello world"
assert(skipOver(s1, 'H') && s1 == "ello world");

string[] r = ["abc", "def", "hij"];
dstring e = "abc"d;
assert(!skipOver!((a, b) => a.equal(b))(r, "def"d));
writeln(r); // ["abc", "def", "hij"]
assert(skipOver!((a, b) => a.equal(b))(r, e));
writeln(r); // ["def", "hij"]

auto s2 = "";
assert(!s2.skipOver('a'));

Примеры:

Частичная инициализация

import std.ascii : isWhite;
import std.range.primitives : empty;

alias whitespaceSkiper = skipOver!isWhite;

auto s2 = "\t\tvalue";
auto s3 = "";
auto s4 = "\t\t\t";
assert(whitespaceSkiper(s2) && s2 == "value");
assert(!whitespaceSkiper(s2));
assert(whitespaceSkiper(s4) && s3.empty);

bool skipOver(Haystack, Needles...)(ref Haystack haystack, Needles needles)
Constraints: if (is(typeof(binaryFun!pred(haystack.front, needles[0].front))) && isForwardRange!Haystack && allSatisfy!(isInputRange, Needles) && !is(CommonType!(staticMap!(ElementType, staticMap!(Unqual, Needles))) == void));

bool skipOver(R)(ref R r1)
Constraints: if (isForwardRange!R && ifTestable!(typeof(r1.front), unaryFun!pred));

bool skipOver(R, Es...)(ref R r, Es es)
Constraints: if (isInputRange!R && is(typeof(binaryFun!pred(r.front, es[0]))));

Параметры:

Haystack haystack	Прямой диапазон для перемещения вперёд.
Needles needles	Вводные диапазоны, представляющие префикс r1 для пропуска.
Es es	Элемент для соответствия.

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

true если префикс haystack соответствует любому диапазону needles полностью или pred истинно, и haystack продвинут до точки за этим сегментом; в противном случае ложь, и haystack остаётся на своём исходном месте.

Примечание

По определению, пустые диапазоны соответствуют полностью, и если needles содержит пустой диапазон, skipOver вернёт true.

uint startsWith(alias pred = (a, b) => a == b, Range, Needles...)(Range doesThisStart, Needles withOneOfThese)
Constraints: if (isInputRange!Range && (Needles.length > 1) && is(typeof(.startsWith!pred(doesThisStart, withOneOfThese[0])) : bool) && is(typeof(.startsWith!pred(doesThisStart, withOneOfThese[1..$])) : uint));

bool startsWith(alias pred = "a == b", R1, R2)(R1 doesThisStart, R2 withThis)
Constraints: if (isInputRange!R1 && isInputRange!R2 && is(typeof(binaryFun!pred(doesThisStart.front, withThis.front)) : bool));

bool startsWith(alias pred = "a == b", R, E)(R doesThisStart, E withThis)
Constraints: if (isInputRange!R && is(typeof(binaryFun!pred(doesThisStart.front, withThis)) : bool));

bool startsWith(alias pred, R)(R doesThisStart)
Constraints: if (isInputRange!R && ifTestable!(typeof(doesThisStart.front), unaryFun!pred));

Проверяет, начинается ли заданный входной диапазон с (одного из) заданных иголок или, если иглы не заданы, если его первый элемент удовлетворяет предикату pred.

Параметры:

pred	Предикат для сравнения элементов стога и иглы(л). Обязателен, если иглы не заданы.
Диапазон doesThisStart	Вводной диапазон для проверки.
Needles withOneOfThese	Иглы, по которым проверяется диапазон, которые могут быть отдельными элементами или входными диапазонами элементов.
R2 withThis	Единственная игла для проверки, которая может быть либо отдельным элементом, либо входным диапазоном элементов.

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

0, если игла(ы) не встречаются в начале заданного диапазона; в противном случае позиция соответствующей иглы, то есть 1, если диапазон начинается с withOneOfThese[0], 2, если он начинается с withOneOfThese[1], и так далее. В случае, когда doesThisStart начинается с нескольких диапазонов или элементов в withOneOfThese, соответствует наиболее короткому. (Если есть два совпадающих диапазона одинаковой длины (например, "a" и 'a'), то соответствует самый левый из них в списке аргументов). В случае, когда параметры игл не заданы, возвращает true если первый элемент doesThisStart удовлетворяет предикату pred.

Примеры:

import std.ascii : isAlpha;

assert("abc".startsWith!(a => a.isAlpha));
assert("abc".startsWith!isAlpha);
assert(!"1ab".startsWith!(a => a.isAlpha));
assert(!"".startsWith!(a => a.isAlpha));

import std.algorithm.comparison : among;
assert("abc".startsWith!(a => a.among('a', 'b') != 0));
assert(!"abc".startsWith!(a => a.among('b', 'c') != 0));

assert(startsWith("abc", ""));
assert(startsWith("abc", "a"));
assert(!startsWith("abc", "b"));
writeln(startsWith("abc", 'a', "b")); // 1
writeln(startsWith("abc", "b", "a")); // 2
writeln(startsWith("abc", "a", "a")); // 1
writeln(startsWith("abc", "ab", "a")); // 2
writeln(startsWith("abc", "x", "a", "b")); // 2
writeln(startsWith("abc", "x", "aa", "ab")); // 3
writeln(startsWith("abc", "x", "aaa", "sab")); // 0
writeln(startsWith("abc", "x", "aaa", "a", "sab")); // 3

import std.typecons : Tuple;
alias C = Tuple!(int, "x", int, "y");
assert(startsWith!"a.x == b"([ C(1,1), C(1,2), C(2,2) ], [1, 1]));
writeln(startsWith!"a.x == b"([C(1, 1), C(2, 1), C(2, 2)], [1, 1], [1, 2], [1, 3])); // 2

alias OpenRight = std.typecons.Flag!"openRight".Flag;

Спецификатор опции интервала для until (ниже) и других.

Если установлено значение OpenRight.yes, то интервал открыт справа (последний элемент не включается).

В противном случае, если установлено значение OpenRight.no, то интервал закрыт справа (последний элемент включается).

Until!(pred, Range, Sentinel) until(alias pred = "a == b", Range, Sentinel)(Range range, Sentinel sentinel, OpenRight openRight = Yes.openRight)
Ограничения: если (!is(Sentinel == OpenRight));

Until!(pred, Range, void) until(alias pred, Range)(Range range, OpenRight openRight = Yes.openRight);

struct Until(alias pred, Range, Sentinel) if (isInputRange!Range);

Лениво итерирует range до тех пор, пока не будет найден элемент e, для которого pred(e, sentinel) истинно.

Это аналогично takeWhile в других языках.

Параметры:

pred	Предикат, определяющий, когда следует остановиться.
Range range	Входной диапазон для итерации.
Sentinel sentinel	Элемент, на котором следует остановиться.
OpenRight openRight	Определяет, следует ли включать элемент, для которого заданный предикат истинен, в результирующий диапазон (No.openRight), или нет (Yes.openRight).

Возвращает:

Входной диапазон, который итерирует элементы исходного диапазона, но останавливается, когда указанный предикат становится истинным. Если исходный диапазон является диапазоном с однонаправленной итерацией или выше, этот диапазон также будет с однонаправленной итерацией.

Примеры:

import std.algorithm.comparison : equal;
import std.typecons : No;
int[] a = [ 1, 2, 4, 7, 7, 2, 4, 7, 3, 5];
assert(equal(a.until(7), [1, 2, 4]));
assert(equal(a.until(7, No.openRight), [1, 2, 4, 7]));