std.algorithm.searching

Переместиться к: all · any · balancedParens · boyerMooreFinder · BoyerMooreFinder · canFind · commonPrefix · count · countUntil · endsWith · find · findAdjacent · findAmong · findSkip · findSplit · findSplitAfter · findSplitBefore · maxCount · maxElement · maxPos · minCount · minElement · minPos · OpenRight · skipOver · startsWith · until · Until

Это подмодуль std.algorithm. Он содержит типовые алгоритмы поиска.
Шпаргалка
Имя функции Описание
all all!"a > 0"([1, 2, 3, 4]) возвращает true, потому что все элементы положительны
any any!"a > 0"([1, 2, -3, -4]) возвращает true потому что, по крайней мере, один элемент является положительным
balancedParens balancedParens("((1 + 1) / 2)") возвращает true , потому что строка имеет сбалансированные круглые скобки.
boyerMooreFinder find("hello world", boyerMooreFinder("or")) возвращает "orld", используя Алгоритм Бойера — Мура.
canFind canFind("hello world", "or") возвращает true.
count Считает элементы, которые равняются определенному значению или удовлетворяют предикату. count([1, 2, 1], 1) возвращает 2, а count!"a < 0"([1, -3, 0]) возвращает 1.
countUntil countUntil(a, b) возвращает количество шагов, которые надо пройти в a , чтобы достигнуть b; например, countUntil("hello!", "o") возвращает 4.
commonPrefix commonPrefix("parakeet", "parachute") возвращает "para".
endsWith endsWith("rocks", "ks") возвращает true.
find find("hello world", "or") возвращает "orld", используя линейный поиск. (Для двоичного поиска обратитесь к std.range.sortedRange.)
findAdjacent findAdjacent([1, 2, 3, 3, 4]) возвращает поддиапазон, начинающийся с двух равных соседних элементов, т.е. [3, 3, 4].
findAmong findAmong("abcd", "qcx") возвращает "cd", потому что 'c' присутсвует в "qcx".
findSkip Если a = "abcde", то findSkip(a, "x") возвращает false и оставляет a без изменений, в то время как findSkip(a, "c") продвигает a до "de" и возвращает true.
findSplit findSplit("abcdefg", "de") возвращает три диапазона "abc", "de", и "fg".
findSplitAfter findSplitAfter("abcdefg", "de") возвращает два диапазона "abcde" и "fg".
findSplitBefore findSplitBefore("abcdefg", "de") возвращает два диапазона "abc" и "defg".
minCount minCount([2, 1, 1, 4, 1]) возвращает tuple(1, 3).
maxCount maxCount([2, 4, 1, 4, 1]) возвращает tuple(4, 2).
minElement Выбирает минимальный элемент диапазона. minElement([3, 4, 1, 2]) возвращает 1.
maxElement Выбирает максимальный элемент диапазона. maxElement([3, 4, 1, 2]) возвращает 4.
minPos minPos([2, 3, 1, 3, 4, 1]) возвращает поддиапазон [1, 3, 4, 1], то есть, позиционирует диапазон на первом появлении его минимального элемента.
maxPos maxPos([2, 3, 1, 3, 4, 1]) возвращает поддиапазон [4, 1], то есть, позиционирует диапазон на первом появлении его максимального элемента.
mismatch mismatch("parakeet", "parachute") возвращает два диапазона "keet" и "chute".
skipOver Пусть a = "blah". Тогда skipOver(a, "bi") оставляет a неизменной и возвращает false, тогда как skipOver(a, "bl") продвинет a до "ah" и возвращает true.
startsWith startsWith("hello, world", "hello") возвращает true.
until Лениво перебирает диапазон до конкретного значения.
Лицензия:
Boost License 1.0.
Авторы:
Andrei Alexandrescu

Исходный код: std/algorithm/searching.d

От переводчика:
Во многих функциях в качестве имён аргументов выбираются слова:
"haystack""стог сена" для диапазона, в котором ведётся поиск,
"needle""игла" для искомого элемента или поддиапазона,
"needles""иглы" для кортежа из нескольких искомых элементов или поддиапазонов.
Очевидна аналогия с выражением "Искать иголку в стоге сена". Изредка я буду переводить эти слова, чтобы предложения не распадались, но в основном оставляю без перевода.

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

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 в условном выражении. Он может быть удобным способом быстро выяснить, что все элементы диапазона являются истиной.
int[3] vals = [5, 3, 18];
assert( all(vals[]));
bool all(Range)(Range range)
if (isInputRange!Range && is(typeof(unaryFun!pred(range.front))));
Возвращает true тогда и только тогда, когда все значения v, найденные во входном диапазоне range удовлетворяют предикату pred. Выполняется за (самое большее) Ο(range.length) вычислений pred.

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

template any(alias pred = "a")
Проверяет, является ли какой-либо из элементов удовлетворяющим pred. !any можно использовать для проверки того, что ни один из элементов не удовлетворяет pred.
Примеры:
import std.ascii : isWhite;
assert( all!(any!isWhite)(["a a", "b b"]));
assert(!any!(all!isWhite)(["a a", "b b"]));
Примеры:
any может также использоваться без предиката, если элементы могут быть пересчитаны в true или false в условном выражении. !any может быть удобным способом быстро выяснить, что ни один из элементов диапазона не вычисляется в true.
int[3] vals1 = [0, 0, 0];
assert(!any(vals1[])); //ничего из vals1 не вычисляется в 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)
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)
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));
BoyerMooreFinder!(binaryFun!pred, Range) boyerMooreFinder(alias pred = "a == b", Range)(Range needle)
if (isRandomAccessRange!Range && hasSlicing!Range || isSomeString!Range);

struct BoyerMooreFinder(alias pred, Range);
Задаёт сопоставление Boyer-Moore для использования с функцией find, описанной ниже. По умолчанию, элементы сравниваются на равенство.
BoyerMooreFinder выделяет память, управляемую сборщиком мусора.
Параметры:
pred Предикат, используемый для сравнения элементов.
Range needle Диапазон с произвольным доступом с длиной и выделением среза.
Возвращает:
Экземпляр структуры BoyerMooreFinder, который может быть использован в функции find() для задействования сопоставляющего алгоритма Бойера — Мура для обнаружения иглы needle в заданном стогу.
auto commonPrefix(alias pred = "a == b", R1, R2)(R1 r1, R2 r2)
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)
if (isNarrowString!R1 && isInputRange!R2 && is(typeof(binaryFun!pred(r1.front, r2.front))));

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

auto commonPrefix(R1, R2)(R1 r1, R2 r2)
if (isNarrowString!R1 && isNarrowString!R2);
Возвращает общий префикс двух диапазонов.
Параметры:
pred Предикат, используемый при сравнении элементов на схожесть. По умолчанию устанавливается в равенство "a == b".
R1 r1 лидирующий диапазон элементов.
R2 r2 входной диапазон элементов.
Возвращает:
Срез r1, который содержит символы, с которых начинаются оба диапазона, если первый аргумент является строкой; в противном случае, тоже, что и результат takeExactly(r1, n), где n – количество элементов в общем префиксе обоих диапазонов.
Смотрите также:
Примеры:
assert(commonPrefix("hello, world", "hello, there") == "hello, ");
size_t count(alias pred = "a == b", Range, E)(Range haystack, E needle)
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)
if (isForwardRange!R1 && !isInfinite!R1 && isForwardRange!R2 && is(typeof(binaryFun!pred(haystack.front, needle.front)) : bool));

size_t count(alias pred = "true", R)(R haystack)
if (isInputRange!R && !isInfinite!R && is(typeof(unaryFun!pred(haystack.front)) : bool));
Первая версия считает количество элементов x в haystack, для которых pred(x, needle) возвращает true. По умолчанию pred устанавливается в равенство. Выполняется за Ο(haystack.length) вычислений pred.
Вторая версия возвращает количество вхождений иглы needle в стогу haystack. Бросает исключение, если needle.empty, так как количество пустых диапазонов в любом диапазоне бесконечно. Перекрытия при расчёте не учитываются, например count("aaa", "aa") – это 1, а не 2.
Третья версия считает элементы, для которых pred(x) возвращает true. Выполняется за Ο(haystack.length) вычислений pred.

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

Параметры:
pred Вычисляемый предикат.
Range haystack Диапазон для подсчета.
E needle Элемент или поддиапазон, количество которых считается в haystack.
Возвращает:
Количество позиций в haystack, для которых pred возвращает true.
Примеры:
import std.uni : toLower;

// количество элементов в диапазоне
int[] a = [ 1, 2, 4, 3, 2, 5, 3, 2, 4 ];
assert(count(a, 2) == 3);
assert(count!("a > b")(a, 2) == 5);
// количество диапазонов в диапазоне
assert(count("abcadfabf", "ab") == 2);
assert(count("ababab", "abab") == 1);
assert(count("ababab", "abx") == 0);
// неявное (fuzzy) количество диапазонов в диапазоне
assert(count!((a, b) => std.uni.toLower(a) == std.uni.toLower(b))("AbcAdFaBf", "ab") == 2);
// количество предикатов в диапазоне
assert(count!("a > 1")(a) == 8);

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

ptrdiff_t countUntil(alias pred = "a == b", R, Rs...)(R haystack, Rs needles)
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)
if (isInputRange!R && is(typeof(binaryFun!pred(haystack.front, needle)) : bool));
Подсчёт элементов в данном лидирующем диапазоне, пока данный предикат не станет true для одной из переданных needles.
Параметры:
pred Предикат для определения, когда остановить подсчет.
R haystack Входной диапазон для подсчета.
Rs needles Либо единичный элемент, либо лидирующий диапазон элементов, который будет анализироваться в свою очередь в отношении каждого элемента в haystack по данному предикату.
Возвращает:
Количество элементов, которые нужно вытолкнуть (popFront) спереди haystack перед достижением элемента, для которого startsWith!pred(haystack, needles) является истиной. Если startsWith!pred(haystack, needles) не является истиной для любого элемента в haystack, тогда возвращается -1.
Примеры:
assert(countUntil("hello world", "world") == 6);
assert(countUntil("hello world", 'r') == 8);
assert(countUntil("hello world", "programming") == -1);
assert(countUntil("日本語", "本語") == 1);
assert(countUntil("日本語", '語')   == 2);
assert(countUntil("日本語", "五") == -1);
assert(countUntil("日本語", '五') == -1);
assert(countUntil([0, 7, 12, 22, 9], [12, 22]) == 2);
assert(countUntil([0, 7, 12, 22, 9], 9) == 4);
assert(countUntil!"a > b"([0, 7, 12, 22, 9], 20) == 3);
Замечание от переводчика:
Изначально в описании выражение "для одной из переданных needles" ввело меня в ступор, ведь нужно полное совпадение, а не только одного элемента диапазона. На всякий случай я перепроверил:
countUntil([1, 2, 3, 4, 5, 6], [2,4]) возвращает -1, как и должно быть.
И только потом заметил многоточие в типе Rs..., т.е. в функцию можно передать несколько "игл" (кортеж), и тогда потребуется совпадение только с одной из них:
countUntil([1, 2, 3, 4, 5, 6], [2,4], [2,3]) возвращает 1.
Кроме того, дополнительную путаницу по поводу типа диапазона R добавляет описание параметров. Как я понял, для первого варианта функции (с кортежем) должен быть лидирующий диапазон, для второго варианта (с одним элементом) достаточно входного диапазона.
ptrdiff_t countUntil(alias pred, R)(R haystack)
if (isInputRange!R && is(typeof(unaryFun!pred(haystack.front)) : bool));
Подобно предыдущей перегрузке countUntil, за исключением того, что здесь вычисляется только предикат pred.
Параметры:
pred Предикат, определяющий, когда остановить подсчет.
R haystack Входной диапазон элементов для подсчета.
Возвращает:
Количество элементов, которые нужно вытолкнуть (popFront) из haystack перед тем, как pred(haystack.front) возвратит true.
Примеры:
import std.ascii : isDigit;
import std.uni : isWhite;

assert(countUntil!(std.uni.isWhite)("hello world") == 5);
assert(countUntil!(std.ascii.isDigit)("hello world") == -1);
assert(countUntil!"a > 20"([0, 7, 12, 22, 9]) == 3);
uint endsWith(alias pred = "a == b", Range, Needles...)(Range doesThisEnd, Needles withOneOfThese)
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)
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)
if (isBidirectionalRange!R && is(typeof(binaryFun!pred(doesThisEnd.back, withThis)) : bool));

bool endsWith(alias pred, R)(R doesThisEnd)
if (isInputRange!R && ifTestable!(typeof(doesThisEnd.front), unaryFun!pred));
Проверяет, заканчивается ли данный диапазон с (одной из) данной needle(s). Величина, взаимная к startsWith.
Параметры:
pred Предикат, используемый для сравнения элементов между диапазоном и needle(s).
Range doesThisEnd Двунаправленный диапазон для проверки.
Needles withOneOfThese Иглы, с которыми сверяет, могут быть единственными элементами, или двунаправленными диапазонами элементов.
R2 withThis Единичный элемент для проверки.
Возвращает:
0, если needle(s) не встречается в конце заданного диапазона; в противном случае положение соответсвующей needle, то есть 1, если диапазон заканчивается на withOneOfThese[0], 2, если оно заканчивается withOneOfThese[1], и так далее.
В случае, когда никакие параметры needle не заданы, 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"));
assert(endsWith("abc", "a", 'c') == 2);
assert(endsWith("abc", "c", "a") == 1);
assert(endsWith("abc", "c", "c") == 1);
assert(endsWith("abc", "bc", "c") == 2);
assert(endsWith("abc", "x", "c", "b") == 2);
assert(endsWith("abc", "x", "aa", "bc") == 3);
assert(endsWith("abc", "x", "aaa", "sab") == 0);
assert(endsWith("abc", "x", "aaa", 'c', "sab") == 3);

Переместиться к: 2 · 3 · 4 · 5

InputRange find(alias pred = "a == b", InputRange, Element)(InputRange haystack, scope Element needle)
if (isInputRange!InputRange && is(typeof(binaryFun!pred(haystack.front, needle)) : bool));
Находит индивидуальный элемент во входном дипазоне. Элементы haystack сравниваются с needle с использованием предиката pred. Выполняет Ο(walkLength(haystack)) вычислений pred.
Для того, чтобы найти последнее вхождение needle в haystack, вызовите find(retro(haystack), needle). Смотрите std.range.retro.
Параметры:
pred Предикат для сравнения каждого элемента с needle, заданный по-умолчанию на "a == b". Можно использовать отрицающий предикат "a != b" для поиска первого элемента, не соответсвующего needle.
InputRange haystack Входной диапазон, в котором ведётся поиск.
Element needle Искомый элемент.

Ограничения: isInputRange!InputRange && is(typeof(binaryFun!pred(haystack.front, needle) : bool))

Возвращает:
haystack, продвинутый настолько, что передний элемент – один из искомых; то есть, когда binaryFun!pred(haystack.front, needle) – истина. Если такая позиция не существует, возвращается пустой диапазон.
Смотрите также:
Примеры:
import std.algorithm.comparison : equal;
import std.container : SList;
import std.range.primitives : empty;

assert(find("hello, world", ',') == ", world");
assert(find([1, 2, 3, 5], 4) == []);
assert(equal(find(SList!int(1, 2, 3, 4, 5)[], 4), SList!int(4, 5)[]));
assert(find!"a > b"([1, 2, 3, 5], 2) == [3, 5]);

auto a = [ 1, 2, 3 ];
assert(find(a, 5).empty);       // не найдено
assert(!find(a, 2).empty);      // найдено

// Поиск строки без учета регистра
string[] s = [ "Hello", "world", "!" ];
assert(!find!("toLower(a) == b")(s, "hello").empty);
InputRange find(alias pred, InputRange)(InputRange haystack)
if (isInputRange!InputRange);
Продвигает входной диапазон haystack, вызывая haystack.popFront, либо до pred(haystack.front), либо до haystack.empty. Выполняет Ο(haystack.length) вычислений pred.
Для нахождения последнего элемента двунаправленного диапазона, удовлетворяющего pred, вызовите find!(pred)(retro(haystack)). Смотрите std.range.retro.
Параметры:
pred Предикат для определения, что данный элемент является искомым.
InputRange haystack Входной диапазон, в котором ведётся поиск.
Возвращает:
haystack, продвинутый настолько, что передний элемент – один из искомых; то есть, когда pred(haystack.front) – истина. Если такая позиция не существует, возвращается пустой диапазон.
Смотрите также:
Примеры:
auto arr = [ 1, 2, 3, 4, 1 ];
assert(find!("a > 2")(arr) == [ 3, 4, 1 ]);

//с предикатом-псевдонимом
bool pred(int x) { return x + 1 > 1.5; }
assert(find!(pred)(arr) == arr);
R1 find(alias pred = "a == b", R1, R2)(R1 haystack, scope R2 needle)
if (isForwardRange!R1 && isForwardRange!R2 && is(typeof(binaryFun!pred(haystack.front, needle.front)) : bool) && !isRandomAccessRange!R1);

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

R1 find(alias pred = "a == b", R1, R2)(R1 haystack, scope R2 needle)
if (isRandomAccessRange!R1 && isForwardRange!R2 && !isBidirectionalRange!R2 && is(typeof(binaryFun!pred(haystack.front, needle.front)) : bool));
Находит первое вхождение лидирующего диапазона в другом лидирующем диапазоне.
Выполняет Ο(walkLength(haystack) * walkLength(needle)) сравнений в худшем случае. Есть специализации, которые улучшают производительность за счет использования двунаправленности или произвольного доступа в данных диапазонах (где это возможно), в зависимости от статистики содержимого двух диапазонов.
Параметры:
pred Предикат, используемый для сравнения соответствующих элементов из haystack и needle. Устанавливается по умолчанию в простое равенство "a == b".
R1 haystack Лидирующий диапазон, в котором ведётся поиск.
R2 needle Искомый лидирующий диапазон.
Возвращает:
haystack, продвинутый так, что needle является его началом (если такой позиции не существует, возвращает haystack, продвинутый до конца).
Примеры:
import std.container : SList;
import std.range.primitives : empty;
import std.typecons : Tuple;

assert(find("hello, world", "World").empty);
assert(find("hello, world", "wo") == "world");
assert([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)];
assert(a.find!"a.x == b"([2, 3]) == [C(2,0), C(3,1), C(4,0)]);
assert(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)
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, и также начинающийся с единицы индекс того элемента в needles, с которым найдено соответствие (0, если ни одна из needles не соответствует; 1, если соответствует needles[0]; 2, если соответствует needles[1] ...). The first needle to be found will be the one that matches. Если несколько игл найдены в одной и той же точке в диапазоне, тогда соответствующей считается самая короткая (если несколько игл одинаковой длины обнаружены в одной и той же точке (например, "a" и 'a'), тогда соответствующей считается самая левая из списка аргументов).
Отношение между haystack и needles просто означает, что можно например, искать отдельные intы или массивы intов в массиве intов. Кроме того, если элементы индивидуально сравнимы, поиски разнородных типов также допустимы: в double[] можно искать int или short[], и, наоборот, в long[] можно искать float или double[]. Это делается для эффективного поиска без необходимости приводить одну сторону сравнения к типу другой стороны.
Сложность поиска – Ο(haystack.length * max(needles.length)) (Для needles , которые являются отдельными элементами, считается, что длина равна 1). Стратегия, используемая в поиске нескольких поддиапазонов, сразу максимизирует использование кэша путем перемещения в haystack несколько раз по возможности.
Примеры:
import std.typecons : tuple;
int[] a = [ 1, 4, 2, 3 ];
assert(find(a, 4) == [ 4, 2, 3 ]);
assert(find(a, [ 1, 4 ]) == [ 1, 4, 2, 3 ]);
assert(find(a, [ 1, 3 ], 4) == tuple([ 4, 2, 3 ], 2));
// Смешанные типы допускаются, если их можно сравнивать
assert(find(a, 5, [ 1.2, 3.5 ], 2.0) == tuple([ 2, 3 ], 3));
Range1 find(Range1, alias pred, Range2)(Range1 haystack, scope BoyerMooreFinder!(pred, Range2) needle);
Ищет needle в haystack эффективно, используя метод Бойера — Мура.
Параметры:
Range1 haystack Диапазон с произвольным доступом с длиной и поддержкой срезов.
BoyerMooreFinder!(pred, Range2) needle Экземпляр BoyerMooreFinder.
Возвращает:
haystack продвинутый так, что needle является передним элементом (если такой позиции не существует, возвращает haystack, продвинутый до конца).
Примеры:
import std.range.primitives : empty;
int[] a = [ -1, 0, 1, 2, 3, 4, 5 ];
int[] b = [ 1, 2, 3 ];

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

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

template canFind(alias pred = "a == b")
Удобная функция. Подобно find, но возвращает только, был ли поиск успешным.
Смотрите также:
among для проверки значения от нескольких возможностей.
Примеры:
assert(canFind([0, 1, 2, 3], 2) == true);
assert(canFind([0, 1, 2, 3], [1, 2], [2, 3]));
assert(canFind([0, 1, 2, 3], [1, 2], [2, 3]) == 1);
assert(canFind([0, 1, 2, 3], [1, 7], [2, 3]));
assert(canFind([0, 1, 2, 3], [1, 7], [2, 3]) == 2);

assert(canFind([0, 1, 2, 3], 4) == false);
assert(!canFind([0, 1, 2, 3], [1, 3], [2, 4]));
assert(canFind([0, 1, 2, 3], [1, 3], [2, 4]) == 0);
Примеры:
Пример, использующий заказной предикат. Заметьте, что needle появляется как второй аргумент предиката.
auto words = [
    "apple",
    "beeswax",
    "cardboard"
];
assert(!canFind(words, "bees"));
assert( canFind!((string a, string b) => a.startsWith(b))(words, "bees"));

Переместиться к: 2 · 3

bool canFind(Range)(Range haystack)
if (is(typeof(find!pred(haystack))));
Возвращает true , когда какое-либо значение v, обнаруженное во входном диапазоне haystack, удовлетворяет предикату pred. Выполняется за (самое большее) Ο(haystack.length) вычислений pred.
bool canFind(Range, Element)(Range haystack, scope Element needle)
if (is(typeof(find!pred(haystack, needle))));
Возвращает true, если needle можно найти в диапазоне. Выполняется за (самое большее) Ο(haystack.length) вычислений pred.
size_t canFind(Range, Ranges...)(Range haystack, scope Ranges needles)
if (Ranges.length > 1 && allSatisfy!(isForwardRange, Ranges) && is(typeof(find!pred(haystack, needles))));
Возвращает начинающийся с единицы индекс первой needle, найденной в haystack. Если needle не найдена, тогда возвращается 0.
Так, если используется непосредственно в условном выражении if или в цикле, результат будет истиной, если одна из игл обнаружена и ложью, если ничего не найдено, тогда как если результат используется в другом месте, он может либо быть приведен к типу bool для того же эффекта, или использоваться для выяснения, какая игла была обнаружена первой, без необходимости иметь дело с кортежем, возвращаемым LREF find для того же действия.
Range findAdjacent(alias pred = "a == b", Range)(Range r)
if (isForwardRange!Range);
Продвигает r , пока не найдёт первые два расположенных рядом элемента a, b, которые удовлетворяют предикату pred(a, b). Выполняется за Ο(r.length) вычислений pred.
Параметры:
pred Удовлетворяемый предикат.
Range r Лидирующий диапазон, в котором ведётся поиск.
Возвращает:
r , продвинутый до первого появления двух соседних элементов, которые удовлетворяют данному предикату. Если таких двух элементов нет, возвращает r, продвинутый до конца.
Смотрите также:
Примеры:
int[] a = [ 11, 10, 10, 9, 8, 8, 7, 8, 9 ];
auto r = findAdjacent(a);
assert(r == [ 10, 10, 9, 8, 8, 7, 8, 9 ]);
auto p = findAdjacent!("a < b")(a);
assert(p == [ 7, 8, 9 ]);
Range1 findAmong(alias pred = "a == b", Range1, Range2)(Range1 seq, Range2 choices)
if (isInputRange!Range1 && isForwardRange!Range2);
Ищет данный диапазон для элемента, который соответствует одному из данных choices.
Продвигает seq, вызывая seq.popFront, пока find!(pred)(choices, seq.front) не станет true, или seq не станет пустым. Выполняется за Ο(seq.length * choices.length) вычислений pred.
Параметры:
pred Предикат, используемый для определения соответсвия.
Range1 seq Входной диапазон , в котором ведётся поиск.
Range2 choices Лидирующий диапазон возможных выборов.
Возвращает:
seq, продвинутый к первому соответсвующему элементу, или до пустого состояния, если нет подходящих элементов.
Смотрите также:
Примеры:
int[] a = [ -1, 0, 1, 2, 3, 4, 5 ];
int[] b = [ 3, 1, 2 ];
assert(findAmong(a, b) == a[2 .. $]);
bool findSkip(alias pred = "a == b", R1, R2)(ref R1 haystack, R2 needle)
if (isForwardRange!R1 && isForwardRange!R2 && is(typeof(binaryFun!pred(haystack.front, needle.front))));
Находит needle в haystack и позиционирует haystack справа после первого появления needle.
Параметры:
R1 haystack Лидирующий диапазон, в котором ведётся поиск.
R2 needle Искомый лидирующий диапазон.
Возвращает:
true, если needle была обнаружена, в этом случае haystack позиционировуется после конца первого появления needle; в противном случае false, haystack оставляется нетронутым.
Примеры:
import std.range.primitives : empty;
// Needle найдена; s заменяется подстрокой, следующей за
// первым вхождением needle.
string s = "abcdef";
assert(findSkip(s, "cd") && s == "ef");

// Needle не обнаружена; s оставлен нетронутым.
s = "abcdef";
assert(!findSkip(s, "cxd") && s == "abcdef");

// Если needle встречается в конце диапазона, диапазон оставляется пустым.
s = "abcdef";
assert(findSkip(s, "def") && s.empty);
auto findSplit(alias pred = "a == b", R1, R2)(R1 haystack, R2 needle)
if (isForwardRange!R1 && isForwardRange!R2);

auto findSplitBefore(alias pred = "a == b", R1, R2)(R1 haystack, R2 needle)
if (isForwardRange!R1 && isForwardRange!R2);

auto findSplitAfter(alias pred = "a == b", R1, R2)(R1 haystack, R2 needle)
if (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 Предикат, используемый для сравнения needle с haystack.
R1 haystack Диапазон, в котором ведётся поиск.
R2 needle Что мы ищем.
Возвращает:
Подтип Tuple!() с разделёнными частями haystack (смотрите выше относительно деталей). В этом подтипе Tuple!() определен метод opCast для bool. Этот opCast возвращает true , когда разделяющая needle была обнаружена (!result[1].empty) и false в противном случае. Это дает удобную идиому, показанную в следующем примере.

Example:

if (const split = haystack.findSplit(needle))
{
     doSomethingWithSplit(split);
}

Примеры:
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);
assert(r[0] == a);
assert(r[1].empty);
assert(r[2].empty);
r = findSplit(a, " ");
assert(r[0] == "Carl");
assert(r[1] == " ");
assert(r[2] == "Sagan Memorial Station");
auto r1 = findSplitBefore(a, "Sagan");
assert(r1);
assert(r1[0] == "Carl ", r1[0]);
assert(r1[1] == "Sagan Memorial Station");
auto r2 = findSplitAfter(a, "Sagan");
assert(r2);
assert(r2[0] == "Carl Sagan");
assert(r2[1] == " Memorial Station");
Tuple!(ElementType!Range, size_t) minCount(alias pred = "a < b", Range)(Range range)
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)
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) – ложь). Трихотомия свойств неравенства не требуется: эти алгоритмы рассматривают элементы a и b равными (с целью подсчета), если pred ставит их в один и тот же класс эквивалентности, то есть !pred(a, b) && !pred(b, a).
Параметры:
pred Предикат упорядочения, используемый для определения экстремума (минимума или максимума).
Range range Входной диапазон для подсчёта.
Возвращает:
Минимальный, или, соответственно, максимальный элемент range вместе с количеством его вхождений в range.
Исключения:
Exception, если range.empty.
Примеры:
import std.conv : text;
import std.typecons : tuple;

debug(std_algorithm) scope(success)
    writeln("unittest @", __FILE__, ":", __LINE__, " done.");

int[] a = [ 2, 3, 4, 1, 2, 4, 1, 1, 2 ];
// Минимум - это 1, и встречается 3 раза
assert(a.minCount == tuple(1, 3));
// Максимум - это 4, и встречается 2 раза
assert(a.maxCount == tuple(4, 2));
auto minElement(alias map = "a", Range)(Range r)
if (isInputRange!Range && !isInfinite!Range);

auto minElement(alias map = "a", Range, RangeElementType = ElementType!Range)(Range r, RangeElementType seed)
if (isInputRange!Range && !isInfinite!Range && !is(CommonType!(ElementType!Range, RangeElementType) == void));
Итерирует переданный диапазон и возвращает минимальный элемент. Пользовательская отображающая функция может быть передана в map.

Сложность: O(n) Точно необходимо n - 1 сравнений.

Параметры:
map пользовательский accessor для ключа сравнения
Range r диапазон, из которого будет выбран минимальный элемент
RangeElementType seed пользовательское семя для использования в качестве начального элемента
Возвращает:
Минимальный элемент в переданном диапазоне.
Смотрите также:
Примеры:
import std.range : enumerate;
import std.typecons : tuple;

assert([2, 1, 4, 3].minElement == 1);

// позволяет получить также индекс элемента
assert([5, 3, 7, 9].enumerate.minElement!"a.value" == tuple(1, 3));

// любой заказной accessor может быть передан
assert([[0, 4], [1, 2]].minElement!"a[1]" == [1, 2]);

// можно задать семя
int[] arr;
assert(arr.minElement(1) == 1);
auto maxElement(alias map = "a", Range)(Range r)
if (isInputRange!Range && !isInfinite!Range && !is(CommonType!(ElementType!Range, RangeElementType) == void));

auto maxElement(alias map = "a", Range, RangeElementType = ElementType!Range)(Range r, RangeElementType seed)
if (isInputRange!Range && !isInfinite!Range);
Итерирует переданный диапазон и возвращает максимальный элемент. Пользовательская отображающая функция может быть передана в map.

Сложность: Необходимо точно n - 1 сравнений.

Параметры:
map пользовательский accessor для ключа сравнения
Range r диапазон, из которого будет выбран максимальный элемент
RangeElementType seed пользовательское семя для использования в качестве начального элемента
Возвращает:
Максимальный элемент в переданном диапазоне.
Смотрите также:
Примеры:
import std.range : enumerate;
import std.typecons : tuple;
assert([2, 1, 4, 3].maxElement == 4);

// позволяет получить также индекс элемента
assert([2, 1, 4, 3].enumerate.maxElement!"a.value" == tuple(2, 4));

// любой заказной accessor может быть передан
assert([[0, 4], [1, 2]].maxElement!"a[1]" == [0, 4]);

// можно задать семя
int[] arr;
assert(arr.minElement(1) == 1);
Range minPos(alias pred = "a < b", Range)(Range range)
if (isForwardRange!Range && !isInfinite!Range && is(typeof(binaryFun!pred(range.front, range.front))));

Range maxPos(alias pred = "a < b", Range)(Range range)
if (isForwardRange!Range && !isInfinite!Range && is(typeof(binaryFun!pred(range.front, range.front))));
Вычисляет поддиапазон диапазона 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) is false).
Параметры:
pred Предикат упорядочения, используемый для определения экстремального (минимального или максимального) элемента.
Range range Входной диапазон для поиска.
Возвращает:
Позиция минимального (или, соответственно, максимального) элемента лидирующего диапазона range, то есть поддиапазон диапазона range, начинающийся в позиции его минимального элемента (или, соответственно самого большого), и с тем же окончанием, как у range.
Примеры:
int[] a = [ 2, 3, 4, 1, 2, 4, 1, 1, 2 ];
// Минимум - это 1 и первое вхождение в позиции 3
assert(a.minPos == [ 1, 2, 4, 1, 1, 2 ]);
// Максимум - это 4 и первое вхождение в позиции 2
assert(a.maxPos == [ 4, 1, 2, 4, 1, 1, 2 ]);

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

bool skipOver(R1, R2)(ref R1 r1, R2 r2)
if (isForwardRange!R1 && isInputRange!R2 && is(typeof(r1.front == r2.front)));

bool skipOver(alias pred, R1, R2)(ref R1 r1, R2 r2)
if (is(typeof(binaryFun!pred(r1.front, r2.front))) && isForwardRange!R1 && isInputRange!R2);
Пропустить начальную часть первого данного диапазона, которой соответствует второй диапазон, или ничего не делать, если нет никакого совпадения.
Параметры:
pred Предикат, который определяет, являются ли элементы из каждого соответствующего диапазона совпадающими. Устанавливается по умолчанию в равенство "a == b".
R1 r1 Лидирующий диапазон для движения вперёд.
R2 r2 Входной диапазон представляющий начальный отрезок r1, который надо пропустить.
Возвращает:
true, если начальный сегмент r1 соответствует r2, и r1 продвинут к точке после этого сегмента; в противном случае false, и r1 оставлен в своей исходной позиции.
Примеры:
import std.algorithm.comparison : equal;

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

string[]  r1 = ["abc", "def", "hij"];
dstring[] r2 = ["abc"d];
assert(!skipOver!((a, b) => a.equal(b))(r1, ["def"d]));
assert(r1 == ["abc", "def", "hij"]);
assert(skipOver!((a, b) => a.equal(b))(r1, r2));
assert(r1 == ["def", "hij"]);
bool skipOver(R, E)(ref R r, E e)
if (isInputRange!R && is(typeof(r.front == e) : bool));

bool skipOver(alias pred, R, E)(ref R r, E e)
if (is(typeof(binaryFun!pred(r.front, e))) && isInputRange!R);
Пропустить первый элемент данного диапазона, если он соответствует данному элементу, в противном случае не делать ничего.
Параметры:
pred Предикат, который определяет, является ли элемент из диапазона соответствущим данному элементу.
R r Входной диапазон, в котором пропускается элемент.
E e Сопоставляемый элемент.
Возвращает:
true , если первый элемент соответствует данному элементу согласно данному предикату, и диапазон продвинут на один элемент; в противном случае false, и диапазон оставлен нетронутым.
Примеры:
import std.algorithm.comparison : equal;

auto s1 = "Hello world";
assert(!skipOver(s1, 'a'));
assert(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));
assert(r == ["abc", "def", "hij"]);
assert(skipOver!((a, b) => a.equal(b))(r, e));
assert(r == ["def", "hij"]);

auto s2 = "";
assert(!s2.skipOver('a'));
uint startsWith(alias pred = "a == b", Range, Needles...)(Range doesThisStart, Needles withOneOfThese)
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)
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)
if (isInputRange!R && is(typeof(binaryFun!pred(doesThisStart.front, withThis)) : bool));

bool startsWith(alias pred, R)(R doesThisStart)
if (isInputRange!R && ifTestable!(typeof(doesThisStart.front), unaryFun!pred));
Проверяет, начинается ли данный входной диапазон с (одной из) данной иглой(игл) или, если иглы не заданы, выполняет ли передний элемент предикат pred.
Параметры:
pred Предикат, используемый в сравнении элементов doesThisStart и иглы(игл). Обязателен, если не дано никаких игл.
Range doesThisStart Входной диапазон для проверки.
Needles withOneOfThese Иглы, на соответсвие которым должен быть проверен диапазон, могут быть индивидуальными элементами или входными диапазонами элементов.
R2 withThis Единственная игла для проверки, которая может быть или единственным элементом, или входным диапазоном элементов.
Возвращает:
0, если игла(иглы) не присутсвует в начале данного диапазона; в противном случае позиция соответсвующей иглы, то есть: 1, если диапазон начинается с withOneOfThese[0]; 2, если он начинается с withOneOfThese[1], и так далее.
В случае, когда doesThisStart начинается с нескольких диапазонов или элементов в withOneOfThese, тогда соответсвующим считается самый короткий (если есть два таких совпадения с одинаковой длиной (например, "a" и 'a'), тогда соответсвующим будет самый левый в списке аргументов).
В случае, когда никакие параметры-иглы не заданы, возвращается true, если передний (front) элемент 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"));
assert(startsWith("abc", 'a', "b") == 1);
assert(startsWith("abc", "b", "a") == 2);
assert(startsWith("abc", "a", "a") == 1);
assert(startsWith("abc", "ab", "a") == 2);
assert(startsWith("abc", "x", "a", "b") == 2);
assert(startsWith("abc", "x", "aa", "ab") == 3);
assert(startsWith("abc", "x", "aaa", "sab") == 0);
assert(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]));
assert(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)
if (!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) возвращает true.
Параметры:
pred Предикат, определяющий, когда остановиться.
Range range Входной диапазон, по которому проходит итерация.
Sentinel sentinel Останавливающий элемент.
OpenRight openRight Определяет, должен ли элемент, для которого данный предикат является истиной, быть включен в результирующий диапазон (No.openRight), или нет (Yes.openRight).
Возвращает:
Входной дипазон, который итерирует над элементами исходного диапазона, но заканчивается, когда заданный предикат становится истиной. Если оригинальный диапазон является лидирующим диапазоном или выше, этот диапазон будет лидирующим диапазоном.
Примеры:
import std.algorithm.comparison : equal;
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][]));