std.algorithm.searching

template all(alias pred = "a")

Checks if all of the elements verify pred.

Examples:

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

Examples:

all can also be used without a predicate, if its items can be evaluated to true or false in a conditional statement. This can be a convenient way to quickly evaluate that all of the elements of a range are true.

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

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

Returns true if and only if all values v found in the input range range satisfy the predicate pred. Performs (at most) Ο(range.length) evaluations of pred.

template any(alias pred = "a")

Checks if any of the elements verifies pred. !any can be used to verify that none of the elements verify pred.

Examples:

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

Examples:

any can also be used without a predicate, if its items can be evaluated to true or false in a conditional statement. !any can be a convenient way to quickly test that none of the elements of a range evaluate to 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)
if (isInputRange!Range && is(typeof(unaryFun!pred(range.front))));

Returns true if and only if any value v found in the input range range satisfies the predicate pred. Performs (at most) Ο(range.length) evaluations of 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)));

Checks whether r has "balanced parentheses", i.e. all instances of lPar are closed by corresponding instances of rPar. The parameter maxNestingLevel controls the nesting level allowed. The most common uses are the default or 0. In the latter case, no nesting is allowed.

Parameters:

Range r	The range to check.
E lPar	The element corresponding with a left (opening) parenthesis.
E rPar	The element corresponding with a right (closing) parenthesis.
size_t maxNestingLevel	The maximum allowed nesting level.

Returns:

true if the given range has balanced parenthesis within the given maximum nesting level; false otherwise.

Examples:

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));

struct BoyerMooreFinder(alias pred, Range);

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

Sets up Boyer-Moore matching for use with find below. By default, elements are compared for equality.

BoyerMooreFinder allocates GC memory.

Parameters:

pred	Predicate used to compare elements.
Range needle	A random-access range with length and slicing.

Returns:

An instance of BoyerMooreFinder that can be used with find() to invoke the Boyer-Moore matching algorithm for finding of needle in a given haystack.

Examples:

auto bmFinder = boyerMooreFinder("TG");

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

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

this(Range needle);

Range beFound(Range haystack);

@property size_t length();

alias opDollar = length;

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);

Returns the common prefix of two ranges.

Parameters:

pred	The predicate to use in comparing elements for commonality. Defaults to equality "a == b".
R1 r1	A forward range of elements.
R2 r2	An input range of elements.

Returns:

A slice of r1 which contains the characters that both ranges start with, if the first argument is a string; otherwise, the same as the result of takeExactly(r1, n), where n is the number of elements in the common prefix of both ranges.

See Also:

std.range.takeExactly

Examples:

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));

The first version counts the number of elements x in r for which pred(x, value) is true. pred defaults to equality. Performs Ο(haystack.length) evaluations of pred.

The second version returns the number of times needle occurs in haystack. Throws an exception if needle.empty, as the count of the empty range in any range would be infinite. Overlapped counts are not considered, for example count("aaa", "aa") is 1, not 2.

The third version counts the elements for which pred(x) is true. Performs Ο(haystack.length) evaluations of pred.

Note: Regardless of the overload, count will not accept infinite ranges for haystack.

Parameters:

pred	The predicate to evaluate.
Range haystack	The range to count.
E needle	The element or sub-range to count in the haystack.

Returns:

The number of positions in the haystack for which pred returned true.

Examples:

import std.uni : toLower;

// count elements in range
int[] a = [ 1, 2, 4, 3, 2, 5, 3, 2, 4 ];
assert(count(a, 2) == 3);
assert(count!("a > b")(a, 2) == 5);
// count range in range
assert(count("abcadfabf", "ab") == 2);
assert(count("ababab", "abab") == 1);
assert(count("ababab", "abx") == 0);
// fuzzy count range in range
assert(count!((a, b) => std.uni.toLower(a) == std.uni.toLower(b))("AbcAdFaBf", "ab") == 2);
// count predicate in range
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));

Counts elements in the given forward range until the given predicate is true for one of the given needles.

Parameters:

pred	The predicate for determining when to stop counting.
R haystack	The input range to be counted.
Rs needles	Either a single element, or a forward range of elements, to be evaluated in turn against each element in haystack under the given predicate.

Returns:

The number of elements which must be popped from the front of haystack before reaching an element for which startsWith!pred(haystack, needles) is true. If startsWith!pred(haystack, needles) is not true for any element in haystack, then -1 is returned.

Examples:

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);

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

Similar to the previous overload of countUntil, except that this one evaluates only the predicate pred.

Parameters:

pred	Predicate to when to stop counting.
R haystack	An input range of elements to be counted.

Returns:

The number of elements which must be popped from haystack before pred(haystack.front) is true.

Examples:

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));

Checks if the given range ends with (one of) the given needle(s). The reciprocal of startsWith.

Parameters:

pred	The predicate to use for comparing elements between the range and the needle(s).
Range doesThisEnd	The bidirectional range to check.
Needles withOneOfThese	The needles to check against, which may be single elements, or bidirectional ranges of elements.
R2 withThis	The single element to check.

Returns:

0 if the needle(s) do not occur at the end of the given range; otherwise the position of the matching needle, that is, 1 if the range ends with withOneOfThese[0], 2 if it ends with withOneOfThese[1], and so on.

In the case when no needle parameters are given, return true iff back of doesThisStart fulfils predicate pred.

Examples:

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);

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

Finds an individual element in an input range. Elements of haystack are compared with needle by using predicate pred. Performs Ο(walkLength(haystack)) evaluations of pred.

To find the last occurrence of needle in haystack, call find(retro(haystack), needle). See std.range.retro.

Parameters:

pred	The predicate for comparing each element with the needle, defaulting to "a == b". The negated predicate "a != b" can be used to search instead for the first element not matching the needle.
InputRange haystack	The input range searched in.
Element needle	The element searched for.

Constraints: isInputRange!InputRange && is(typeof(binaryFun!pred(haystack.front, needle) : bool))

Returns:

haystack advanced such that the front element is the one searched for; that is, until binaryFun!pred(haystack.front, needle) is true. If no such position exists, returns an empty haystack.

See Also:

STL's find

Examples:

import std.algorithm.comparison : equal;
import std.container : SList;
import std.range.primitives : empty;
import std.range;

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

auto r = assumeSorted!"a > b"([10, 7, 3, 1, 0, 0]);
assert(find(r, 3) == assumeSorted!"a > b"([3, 1, 0, 0]));
assert(find!"a > b"(r, 8) == r);
assert(find!"a < b"(r, 5) == assumeSorted!"a > b"([3, 1, 0, 0]));

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);       // not found
assert(!find(a, 2).empty);      // found

// Case-insensitive find of a string
string[] s = [ "Hello", "world", "!" ];
assert(!find!("toLower(a) == b")(s, "hello").empty);

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

Advances the input range haystack by calling haystack.popFront until either pred(haystack.front), or haystack.empty. Performs Ο(haystack.length) evaluations of pred.

To find the last element of a bidirectional haystack satisfying pred, call find!(pred)(retro(haystack)). See std.range.retro.

Parameters:

pred	The predicate for determining if a given element is the one being searched for.
InputRange haystack	The input range to search in.

Returns:

haystack advanced such that the front element is the one searched for; that is, until binaryFun!pred(haystack.front, needle) is true. If no such position exists, returns an empty haystack.

See Also:

STL's find_if

Examples:

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

// with predicate alias
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));

Finds the first occurrence of a forward range in another forward range.

Performs Ο(walkLength(haystack) * walkLength(needle)) comparisons in the worst case. There are specializations that improve performance by taking advantage of bidirectional or random access in the given ranges (where possible), depending on the statistics of the two ranges' content.

Parameters:

pred	The predicate to use for comparing respective elements from the haystack and the needle. Defaults to simple equality "a == b".
R1 haystack	The forward range searched in.
R2 needle	The forward range searched for.

Returns:

haystack advanced such that needle is a prefix of it (if no such position exists, returns haystack advanced to termination).

Examples:

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))));

Finds two or more needles into a haystack. The predicate pred is used throughout to compare elements. By default, elements are compared for equality.

Parameters:

pred	The predicate to use for comparing elements.
Range haystack	The target of the search. Must be an input range. If any of needles is a range with elements comparable to elements in haystack, then haystack must be a forward range such that the search can backtrack.
Ranges needles	One or more items to search for. Each of needles must be either comparable to one element in haystack, or be itself a forward range with elements comparable with elements in haystack.

Returns:

A tuple containing haystack positioned to match one of the needles and also the 1-based index of the matching element in needles (0 if none of needles matched, 1 if needles[0] matched, 2 if needles[1] matched...). The first needle to be found will be the one that matches. If multiple needles are found at the same spot in the range, then the shortest one is the one which matches (if multiple needles of the same length are found at the same spot (e.g "a" and 'a'), then the left-most of them in the argument list matches).

The relationship between haystack and needles simply means that one can e.g. search for individual ints or arrays of ints in an array of ints. In addition, if elements are individually comparable, searches of heterogeneous types are allowed as well: a double[] can be searched for an int or a short[], and conversely a long can be searched for a float or a double[]. This makes for efficient searches without the need to coerce one side of the comparison into the other's side type.

The complexity of the search is Ο(haystack.length * max(needles.length)). (For needles that are individual items, length is considered to be 1.) The strategy used in searching several subranges at once maximizes cache usage by moving in haystack as few times as possible.

Examples:

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));
// Mixed types allowed if comparable
assert(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);

Finds needle in haystack efficiently using the Boyer-Moore method.

Parameters:

RandomAccessRange haystack	A random-access range with length and slicing.
BoyerMooreFinder!(pred, InputRange) needle	A BoyerMooreFinder.

Returns:

haystack advanced such that needle is a prefix of it (if no such position exists, returns haystack advanced to termination).

Examples:

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")

Convenience function. Like find, but only returns whether or not the search was successful.

See Also:

among for checking a value against multiple possibilities.

Examples:

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);

Examples:

Example using a custom predicate. Note that the needle appears as the second argument of the predicate.

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))));

Returns true if and only if any value v found in the input range range satisfies the predicate pred. Performs (at most) Ο(haystack.length) evaluations of pred.

bool canFind(Range, Element)(Range haystack, scope Element needle)
if (is(typeof(find!pred(haystack, needle))));

Returns true if and only if needle can be found in range. Performs Ο(haystack.length) evaluations of pred.

size_t canFind(Range, Ranges...)(Range haystack, scope Ranges needles)
if (Ranges.length > 1 && allSatisfy!(isForwardRange, Ranges) && is(typeof(find!pred(haystack, needles))));

Returns the 1-based index of the first needle found in haystack. If no needle is found, then 0 is returned.

So, if used directly in the condition of an if statement or loop, the result will be true if one of the needles is found and false if none are found, whereas if the result is used elsewhere, it can either be cast to bool for the same effect or used to get which needle was found first without having to deal with the tuple that LREF find returns for the same operation.

Range findAdjacent(alias pred = "a == b", Range)(Range r)
if (isForwardRange!Range);

Advances r until it finds the first two adjacent elements a, b that satisfy pred(a, b). Performs Ο(r.length) evaluations of pred.

Parameters:

pred	The predicate to satisfy.
Range r	A forward range to search in.

Returns:

r advanced to the first occurrence of two adjacent elements that satisfy the given predicate. If there are no such two elements, returns r advanced until empty.

See Also:

STL's adjacent_find

Examples:

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 ]);

InputRange findAmong(alias pred = "a == b", InputRange, ForwardRange)(InputRange seq, ForwardRange choices)
if (isInputRange!InputRange && isForwardRange!ForwardRange);

Searches the given range for an element that matches one of the given choices.

Advances seq by calling seq.popFront until either find!(pred)(choices, seq.front) is true, or seq becomes empty. Performs Ο(seq.length * choices.length) evaluations of pred.

Parameters:

pred	The predicate to use for determining a match.
InputRange seq	The input range to search.
ForwardRange choices	A forward range of possible choices.

Returns:

seq advanced to the first matching element, or until empty if there are no matching elements.

See Also:

STL's find_first_of

Examples:

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))));

Finds needle in haystack and positions haystack right after the first occurrence of needle.

Parameters:

R1 haystack	The forward range to search in.
R2 needle	The forward range to search for.

Returns:

true if the needle was found, in which case haystack is positioned after the end of the first occurrence of needle; otherwise false, leaving haystack untouched.

Examples:

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);

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);

These functions find the first occurrence of needle in haystack and then split haystack as follows.

findSplit returns a tuple result containing three ranges. result[0] is the portion of haystack before needle, result[1] is the portion of haystack that matches needle, and result[2] is the portion of haystack after the match. If needle was not found, result[0] comprehends haystack entirely and result[1] and result[2] are empty.

findSplitBefore returns a tuple result containing two ranges. result[0] is the portion of haystack before needle, and result[1] is the balance of haystack starting with the match. If needle was not found, result[0] comprehends haystack entirely and result[1] is empty.

findSplitAfter returns a tuple result containing two ranges. result[0] is the portion of haystack up to and including the match, and result[1] is the balance of haystack starting after the match. If needle was not found, result[0] is empty and result[1] is haystack.

In all cases, the concatenation of the returned ranges spans the entire haystack.

If haystack is a random-access range, all three components of the tuple have the same type as haystack. Otherwise, haystack must be a forward range and the type of result[0] and result[1] is the same as std.range.takeExactly.

Parameters:

pred	Predicate to use for comparing needle against haystack.
R1 haystack	The range to search.
R2 needle	What to look for.

Returns:

A sub-type of Tuple!() of the split portions of haystack (see above for details). This sub-type of Tuple!() has opCast defined for bool. This opCast returns true when the separating needle was found (!result[1].empty) and false otherwise. This enables the convenient idiom shown in the following example.

Example:

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

Examples:

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 ");
assert(r1[1] == "Sagan Memorial Station");
auto r2 = findSplitAfter(a, "Sagan");
assert(r2);
assert(r2[0] == "Carl Sagan");
assert(r2[1] == " Memorial Station");

Examples:

Use std.range.only to find single elements:

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

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))));

Computes the minimum (respectively maximum) of range along with its number of occurrences. Formally, the minimum is a value x in range such that pred(a, x) is false for all values a in range. Conversely, the maximum is a value x in range such that pred(x, a) is false for all values a in range (note the swapped arguments to pred).

These functions may be used for computing arbitrary extrema by choosing pred appropriately. For corrrect functioning, pred must be a strict partial order, i.e. transitive (if pred(a, b) && pred(b, c) then pred(a, c)) and irreflexive (pred(a, a) is false). The trichotomy property of inequality is not required: these algoritms consider elements a and b equal (for the purpose of counting) if pred puts them in the same equivalence class, i.e. !pred(a, b) && !pred(b, a).

Parameters:

pred	The ordering predicate to use to determine the extremum (minimum or maximum).
Range range	The input range to count.

Returns:

The minimum, respectively maximum element of a range together with the number it occurs in the range.

Throws:

Exception if range.empty.

Examples:

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 ];
// Minimum is 1 and occurs 3 times
assert(a.minCount == tuple(1, 3));
// Maximum is 4 and occurs 2 times
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));

Iterates the passed range and returns the minimal element. A custom mapping function can be passed to map.

Complexity: O(n) Exactly n - 1 comparisons are needed.

Parameters:

map	custom accessor for the comparison key
Range r	range from which the minimal element will be selected
RangeElementType seed	custom seed to use as initial element

Returns:

The minimal element of the passed-in range.

See Also:

std.algorithm.comparison.min

Examples:

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

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

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

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

// can be seeded
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);

Iterates the passed range and returns the maximal element. A custom mapping function can be passed to map.

Complexity: Exactly n - 1 comparisons are needed.

Parameters:

map	custom accessor for the comparison key
Range r	range from which the maximum will be selected
RangeElementType seed	custom seed to use as initial element

Returns:

The maximal element of the passed-in range.

See Also:

std.algorithm.comparison.max

Examples:

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

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

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

// can be seeded
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))));

Computes a subrange of range starting at the first occurrence of range's minimum (respectively maximum) and with the same ending as range, or the empty range if range itself is empty.

Formally, the minimum is a value x in range such that pred(a, x) is false for all values a in range. Conversely, the maximum is a value x in range such that pred(x, a) is false for all values a in range (note the swapped arguments to pred).

These functions may be used for computing arbitrary extrema by choosing pred appropriately. For corrrect functioning, pred must be a strict partial order, i.e. transitive (if pred(a, b) && pred(b, c) then pred(a, c)) and irreflexive (pred(a, a) is false).

Parameters:

pred	The ordering predicate to use to determine the extremum (minimum or maximum) element.
Range range	The input range to search.

Returns:

The position of the minimum (respectively maximum) element of forward range range, i.e. a subrange of range starting at the position of its smallest (respectively largest) element and with the same ending as range.

Examples:

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

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

Computes the index of the first occurrence of range's minimum element.

Parameters:

pred	The ordering predicate to use to determine the minimum element.
Range range	The input range to search.

Complexity: O(n) Exactly n - 1 comparisons are needed.

Returns:

The index of the first encounter of the minimum element in range. If the range is empty, -1 is returned.

See Also:

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

Examples:

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

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

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

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

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

Computes the index of the first occurrence of range's maximum element.

Complexity: O(n) Exactly n - 1 comparisons are needed.

Parameters:

pred	The ordering predicate to use to determine the maximum element.
Range range	The input range to search.

Returns:

The index of the first encounter of the maximum in range. If the range is empty, -1 is returned.

See Also:

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

Examples:

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

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

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

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);

Skip over the initial portion of the first given range that matches the second range, or do nothing if there is no match.

Parameters:

pred	The predicate that determines whether elements from each respective range match. Defaults to equality "a == b".
R1 r1	The forward range to move forward.
R2 r2	The input range representing the initial segment of r1 to skip over.

Returns:

true if the initial segment of r1 matches r2, and r1 has been advanced to the point past this segment; otherwise false, and r1 is left in its original position.

Examples:

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);

Skip over the first element of the given range if it matches the given element, otherwise do nothing.

Parameters:

pred	The predicate that determines whether an element from the range matches the given element.
R r	The input range to skip over.
E e	The element to match.

Returns:

true if the first element matches the given element according to the given predicate, and the range has been advanced by one element; otherwise false, and the range is left untouched.

Examples:

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));

Checks whether the given input range starts with (one of) the given needle(s) or, if no needles are given, if its front element fulfils predicate pred.

Parameters:

pred	Predicate to use in comparing the elements of the haystack and the needle(s). Mandatory if no needles are given.
Range doesThisStart	The input range to check.
Needles withOneOfThese	The needles against which the range is to be checked, which may be individual elements or input ranges of elements.
R2 withThis	The single needle to check, which may be either a single element or an input range of elements.

Returns:

0 if the needle(s) do not occur at the beginning of the given range; otherwise the position of the matching needle, that is, 1 if the range starts with withOneOfThese[0], 2 if it starts with withOneOfThese[1], and so on.

In the case where doesThisStart starts with multiple of the ranges or elements in withOneOfThese, then the shortest one matches (if there are two which match which are of the same length (e.g. "a" and 'a'), then the left-most of them in the argument list matches).

In the case when no needle parameters are given, return true iff front of doesThisStart fulfils predicate pred.

Examples:

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;

Interval option specifier for until (below) and others.

If set to OpenRight.yes, then the interval is open to the right (last element is not included).

Otherwise if set to OpenRight.no, then the interval is closed to the right (last element included).

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);

Lazily iterates range until the element e for which pred(e, sentinel) is true.

Parameters:

pred	Predicate to determine when to stop.
Range range	The input range to iterate over.
Sentinel sentinel	The element to stop at.
OpenRight openRight	Determines whether the element for which the given predicate is true should be included in the resulting range (No.openRight), or not (Yes.openRight).

Returns:

An input range that iterates over the original range's elements, but ends when the specified predicate becomes true. If the original range is a forward range or higher, this range will be a forward range.

Examples:

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][]));