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.
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[]));
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);
assert(count!((a, b) => std.uni.toLower(a) == std.uni.toLower(b))("AbcAdFaBf", "ab") == 2);
assert(count!("a > 1")(a) == 8);
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);
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"));
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.
Возвращает: 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.
Возвращает: 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
.
Возвращает: true
, если needle
была обнаружена, в этом случае haystack
позиционировуется после конца первого появления needle
; в противном случае
false
, haystack
оставляется нетронутым.
Примеры: import std.range.primitives : empty;
string s = "abcdef";
assert(findSkip(s, "cd") && s == "ef");
s = "abcdef";
assert(!findSkip(s, "cxd") && s == "abcdef");
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 ];
assert(a.minCount == tuple(1, 3));
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));
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));
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 ];
assert(a.minPos == [ 1, 2, 4, 1, 1, 2 ]);
assert(a.maxPos == [ 4, 1, 2, 4, 1, 1, 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][]));