/D

# std.algorithm.searching

This is a submodule of `std.algorithm`. It contains generic searching algorithms.

Cheat Sheet
Function Name Description
`all` `all!"a > 0"([1, 2, 3, 4])` returns `true` because all elements are positive
`any` `any!"a > 0"([1, 2, -3, -4])` returns `true` because at least one element is positive
`balancedParens` `balancedParens("((1 + 1) / 2)")` returns `true` because the string has balanced parentheses.
`boyerMooreFinder` `find("hello world", boyerMooreFinder("or"))` returns `"orld"` using the Boyer-Moore algorithm.
`canFind` `canFind("hello world", "or")` returns `true`.
`count` Counts elements that are equal to a specified value or satisfy a predicate. `count([1, 2, 1], 1)` returns `2` and `count!"a < 0"([1, -3, 0])` returns `1`.
`countUntil` `countUntil(a, b)` returns the number of steps taken in `a` to reach `b`; for example, `countUntil("hello!", "o")` returns `4`.
`commonPrefix` `commonPrefix("parakeet", "parachute")` returns `"para"`.
`endsWith` `endsWith("rocks", "ks")` returns `true`.
`find` `find("hello world", "or")` returns `"orld"` using linear search. (For binary search refer to `std.range.SortedRange`.)
`findAdjacent` `findAdjacent([1, 2, 3, 3, 4])` returns the subrange starting with two equal adjacent elements, i.e. `[3, 3, 4]`.
`findAmong` `findAmong("abcd", "qcx")` returns `"cd"` because `'c'` is among `"qcx"`.
`findSkip` If `a = "abcde"`, then `findSkip(a, "x")` returns `false` and leaves `a` unchanged, whereas `findSkip(a, "c")` advances `a` to `"de"` and returns `true`.
`findSplit` `findSplit("abcdefg", "de")` returns the three ranges `"abc"`, `"de"`, and `"fg"`.
`findSplitAfter` `findSplitAfter("abcdefg", "de")` returns the two ranges `"abcde"` and `"fg"`.
`findSplitBefore` `findSplitBefore("abcdefg", "de")` returns the two ranges `"abc"` and `"defg"`.
`minCount` `minCount([2, 1, 1, 4, 1])` returns `tuple(1, 3)`.
`maxCount` `maxCount([2, 4, 1, 4, 1])` returns `tuple(4, 2)`.
`minElement` Selects the minimal element of a range. `minElement([3, 4, 1, 2])` returns `1`.
`maxElement` Selects the maximal element of a range. `maxElement([3, 4, 1, 2])` returns `4`.
`minIndex` Index of the minimal element of a range. `minElement([3, 4, 1, 2])` returns `2`.
`maxIndex` Index of the maximal element of a range. `maxElement([3, 4, 1, 2])` returns `1`.
`minPos` `minPos([2, 3, 1, 3, 4, 1])` returns the subrange `[1, 3, 4, 1]`, i.e., positions the range at the first occurrence of its minimal element.
`maxPos` `maxPos([2, 3, 1, 3, 4, 1])` returns the subrange `[4, 1]`, i.e., positions the range at the first occurrence of its maximal element.
`skipOver` Assume `a = "blah"`. Then `skipOver(a, "bi")` leaves `a` unchanged and returns `false`, whereas `skipOver(a, "bl")` advances `a` to refer to `"ah"` and returns `true`.
`startsWith` `startsWith("hello, world", "hello")` returns `true`.
`until` Lazily iterates a range until a specific value is found.
Authors:
Andrei Alexandrescu
Source
std/algorithm/searching.d
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)
Constraints: if (isInputRange!Range);

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`. This is sometimes called `exists` in other languages.

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)
Constraints: 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)
Constraints: 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));
s = "f(x) = ⌈x⌉";
assert(balancedParens(s, '⌈', '⌉'));
```
struct BoyerMooreFinder(alias pred, Range);

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

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);
writeln(r); // "TGCCTGA"

// continue search in haystack
r = bmFinder.beFound(r[2 .. \$]);
writeln(r); // "TGA"
```
this(Range needle);
scope Range beFound(Range haystack);
@property size_t length();
alias opDollar = length;
auto commonPrefix(alias pred = "a == b", R1, R2)(R1 r1, R2 r2)
Constraints: if (isForwardRange!R1 && isInputRange!R2 && !isNarrowString!R1 && is(typeof(binaryFun!pred(r1.front, r2.front))));

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

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

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

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.
`std.range.takeExactly`
Examples:
```writeln(commonPrefix("hello, world", "hello, there")); // "hello, "
```
size_t count(alias pred = "a == b", Range, E)(Range haystack, E needle)
Constraints: if (isInputRange!Range && !isInfinite!Range && is(typeof(binaryFun!pred(haystack.front, needle)) : bool));

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

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

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

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`.

The fourth version counts the number of elements in a range. It is an optimization for the third version: if the given range has the `length` property the count is returned right away, otherwise performs Ο(`haystack.length`) to walk the range.

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 ];
writeln(count(a)); // 9
writeln(count(a, 2)); // 3
writeln(count!("a > b")(a, 2)); // 5
// count range in range
writeln(count("ababab", "abab")); // 1
writeln(count("ababab", "abx")); // 0
// fuzzy count range in range
writeln(count!( (a, b) => toLower(a) == toLower(b))("AbcAdFaBf", "ab")); // 2
// count predicate in range
writeln(count!("a > 1")(a)); // 8
```
ptrdiff_t countUntil(alias pred = "a == b", R, Rs...)(R haystack, Rs needles)
Constraints: if (isForwardRange!R && (Rs.length > 0) && (isForwardRange!(Rs[0]) == isInputRange!(Rs[0])) && is(typeof(startsWith!pred(haystack, needles[0]))) && (Rs.length == 1 || is(typeof(countUntil!pred(haystack, needles[1..\$])))));

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

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

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. If only `pred` is provided, `pred(haystack)` is tested for each element.
`std.string.indexOf`
Examples:
```writeln(countUntil("hello world", "world")); // 6
writeln(countUntil("hello world", 'r')); // 8
writeln(countUntil("hello world", "programming")); // -1
writeln(countUntil("日本語", "本語")); // 1
writeln(countUntil("日本語", '語')); // 2
writeln(countUntil("日本語", "五")); // -1
writeln(countUntil("日本語", '五')); // -1
writeln(countUntil([0, 7, 12, 22, 9], [12, 22])); // 2
writeln(countUntil([0, 7, 12, 22, 9], 9)); // 4
writeln(countUntil!"a > b"([0, 7, 12, 22, 9], 20)); // 3
```
Examples:
```import std.ascii : isDigit;
import std.uni : isWhite;

writeln(countUntil!(std.uni.isWhite)("hello world")); // 5
writeln(countUntil!(std.ascii.isDigit)("hello world")); // -1
writeln(countUntil!"a > 20"([0, 7, 12, 22, 9])); // 3
```
uint endsWith(alias pred = "a == b", Range, Needles...)(Range doesThisEnd, Needles withOneOfThese)
Constraints: if (isBidirectionalRange!Range && (Needles.length > 1) && is(typeof(.endsWith!pred(doesThisEnd, withOneOfThese[0])) : bool) && is(typeof(.endsWith!pred(doesThisEnd, withOneOfThese[1..\$])) : uint));

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

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

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

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"));
writeln(endsWith("abc", "a", 'c')); // 2
writeln(endsWith("abc", "c", "a")); // 1
writeln(endsWith("abc", "c", "c")); // 1
writeln(endsWith("abc", "bc", "c")); // 2
writeln(endsWith("abc", "x", "c", "b")); // 2
writeln(endsWith("abc", "x", "aa", "bc")); // 3
writeln(endsWith("abc", "x", "aaa", "sab")); // 0
writeln(endsWith("abc", "x", "aaa", 'c', "sab")); // 3
```
InputRange find(alias pred = "a == b", InputRange, Element)(InputRange haystack, scope Element needle)
Constraints: if (isInputRange!InputRange && is(typeof(binaryFun!pred(haystack.front, needle)) : bool));

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

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

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

The predicate is passed to `std.functional.binaryFun`, and can either accept a string, or any callable that can be executed via `pred(element, element)`.

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

If no `needle` is provided, `pred(haystack.front)` will be evaluated on each element of the input range.

If `input` is a forward range, `needle` can be a forward range too. In this case `startsWith!pred(haystack, needle)` is evaluated on each evaluation.

Note
`find` behaves similar to `dropWhile` in other languages.
Complexity
`find` performs Ο(`walkLength(haystack)`) evaluations of `pred`. There are specializations that improve performance by taking advantage of bidirectional or random access ranges (where possible).
Parameters:
 pred The predicate for comparing each element with the needle, defaulting to equality `"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.
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`.
`findAdjacent`, `findAmong`, `findSkip`, `findSplit`, `startsWith`
Examples:
```import std.range.primitives;

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

writeln(find("hello, world", ',')); // ", world"
```
Examples:
Case-insensitive find of a string
```import std.range.primitives;
import std.uni : toLower;

string[] s = ["Hello", "world", "!"];
writeln(s.find!( (a, b) => toLower(a) == b)("hello")); // s
```
Examples:
```auto arr = [ 1, 2, 3, 4, 1 ];
writeln(find!("a > 2")(arr)); // [3, 4, 1]

// with predicate alias
bool pred(int x) { return x + 1 > 1.5; }
writeln(find!(pred)(arr)); // arr
```
Examples:
```import std.container : SList;
import std.range.primitives : empty;
import std.typecons : Tuple;

assert(find("hello, world", "World").empty);
writeln(find("hello, world", "wo")); // "world"
writeln([1, 2, 3, 4].find(SList!int(2, 3)[])); // [2, 3, 4]
alias C = Tuple!(int, "x", int, "y");
auto a = [C(1,0), C(2,0), C(3,1), C(4,0)];
writeln(a.find!"a.x == b"([2, 3])); // [C(2, 0), C(3, 1), C(4, 0)]
writeln(a[1 .. \$].find!"a.x == b"([2, 3])); // [C(2, 0), C(3, 1), C(4, 0)]
```
Tuple!(Range, size_t) find(alias pred = "a == b", Range, Ranges...)(Range haystack, Ranges needles)
Constraints: if (Ranges.length > 1 && is(typeof(startsWith!pred(haystack, needles))));

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 `int`s or arrays of `int`s in an array of `int`s. 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 ];
writeln(find(a, 4)); // [4, 2, 3]
writeln(find(a, [1, 4])); // [1, 4, 2, 3]
writeln(find(a, [1, 3], 4)); // tuple([4, 2, 3], 2)
// Mixed types allowed if comparable
writeln(find(a, 5, [1.2, 3.5], 2.0)); // tuple([2, 3], 3)
```
RandomAccessRange find(RandomAccessRange, alias pred, InputRange)(RandomAccessRange haystack, scope BoyerMooreFinder!(pred, InputRange) needle);

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

writeln(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.

`std.algorithm.comparison.among` for checking a value against multiple possibilities.
Examples:
```writeln(canFind([0, 1, 2, 3], 2)); // true
assert(canFind([0, 1, 2, 3], [1, 2], [2, 3]));
writeln(canFind([0, 1, 2, 3], [1, 2], [2, 3])); // 1
assert(canFind([0, 1, 2, 3], [1, 7], [2, 3]));
writeln(canFind([0, 1, 2, 3], [1, 7], [2, 3])); // 2

writeln(canFind([0, 1, 2, 3], 4)); // false
assert(!canFind([0, 1, 2, 3], [1, 3], [2, 4]));
writeln(canFind([0, 1, 2, 3], [1, 3], [2, 4])); // 0
```
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"));
```
Examples:
Search for mutliple items in an array of items (search for needles in an array of hay stacks)
```string s1 = "aaa111aaa";
string s2 = "aaa222aaa";
string s3 = "aaa333aaa";
string s4 = "aaa444aaa";
const hay = [s1, s2, s3, s4];
assert(hay.canFind!(e => (e.canFind("111", "222"))));
```
bool canFind(Range)(Range haystack)
Constraints: 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)
Constraints: 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)
Constraints: 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)
Constraints: 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.
STL's `adjacent_find`
Examples:
```int[] a = [ 11, 10, 10, 9, 8, 8, 7, 8, 9 ];
writeln(r); // [10, 10, 9, 8, 8, 7, 8, 9]
auto p = findAdjacent!("a < b")(a);
writeln(p); // [7, 8, 9]
```
InputRange findAmong(alias pred = "a == b", InputRange, ForwardRange)(InputRange seq, ForwardRange choices)
Constraints: 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.
`find`, `algorithm.comparison.among.std`
Examples:
```int[] a = [ -1, 0, 1, 2, 3, 4, 5 ];
int[] b = [ 3, 1, 2 ];
writeln(findAmong(a, b)); // a[2 .. &dollar;]
```
bool findSkip(alias pred = "a == b", R1, R2)(ref R1 haystack, R2 needle)
Constraints: if (isForwardRange!R1 && isForwardRange!R2 && is(typeof(binaryFun!pred(haystack.front, needle.front))));

size_t findSkip(alias pred, R1)(ref R1 haystack)
Constraints: if (isForwardRange!R1 && ifTestable!(typeof(haystack.front), unaryFun!pred));

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

If no needle is provided, the `haystack` is advanced as long as `pred` evaluates to `true`. Similarly, the haystack is positioned so as `pred` evaluates to `false` for `haystack.front`.

Parameters:
 R1 `haystack` The forward range to search in. R2 `needle` The forward range to search for. pred Custom predicate for comparison of haystack and needle
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. If no needle is provided, it returns the number of times `pred(haystack.front)` returned true.
`find`
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");

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);
```
Examples:
```import std.ascii : isWhite;
string s = "    abc";
assert(findSkip!isWhite(s) && s == "abc");
assert(!findSkip!isWhite(s) && s == "abc");

s = "  ";
writeln(findSkip!isWhite(s)); // 2
```
auto findSplit(alias pred = "a == b", R1, R2)(R1 haystack, R2 needle)
Constraints: if (isForwardRange!R1 && isForwardRange!R2);

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

auto findSplitAfter(alias pred = "a == b", R1, R2)(R1 haystack, R2 needle)
Constraints: 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 and `false` otherwise.
`find`
Examples:
Returning a subtype of `std.typecons.Tuple` enables the following convenient idiom:
```// findSplit returns a triplet
if (auto split = "dlang-rocks".findSplit("-"))
{
writeln(split[0]); // "dlang"
writeln(split[1]); // "-"
writeln(split[2]); // "rocks"
}
else assert(0);

// works with const aswell
if (const split = "dlang-rocks".findSplit("-"))
{
writeln(split[0]); // "dlang"
writeln(split[1]); // "-"
writeln(split[2]); // "rocks"
}
else assert(0);
```
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);
writeln(r[0]); // a
assert(r[1].empty);
assert(r[2].empty);
r = findSplit(a, " ");
writeln(r[0]); // "Carl"
writeln(r[1]); // " "
writeln(r[2]); // "Sagan Memorial Station"
if (const r1 = findSplitBefore(a, "Sagan"))
{
assert(r1);
writeln(r1[0]); // "Carl "
writeln(r1[1]); // "Sagan Memorial Station"
}
if (const r2 = findSplitAfter(a, "Sagan"))
{
assert(r2);
writeln(r2[0]); // "Carl Sagan"
writeln(r2[1]); // " Memorial Station"
}
```
Examples:
Use `std.range.only` to find single elements:
```import std.range : only;
writeln([1, 2, 3, 4].findSplitBefore(only(3))[0]); // [1, 2]
```
Tuple!(ElementType!Range, size_t) minCount(alias pred = "a < b", Range)(Range range)
Constraints: if (isInputRange!Range && !isInfinite!Range && is(typeof(binaryFun!pred(range.front, range.front))));

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

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`.
`std.algorithm.comparison.min`, `minIndex`, `minElement`, `minPos`
Examples:
```import std.conv : text;
import std.typecons : tuple;

int[] a = [ 2, 3, 4, 1, 2, 4, 1, 1, 2 ];
// Minimum is 1 and occurs 3 times
writeln(a.minCount); // tuple(1, 3)
// Maximum is 4 and occurs 2 times
writeln(a.maxCount); // tuple(4, 2)
```
auto minElement(alias map = (a) => a, Range)(Range r)
Constraints: if (isInputRange!Range && !isInfinite!Range);

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

Iterates the passed range and returns the minimal element. A custom mapping function can be passed to `map`. In other languages this is sometimes called `argmin`.

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.
`maxElement`, `std.algorithm.comparison.min`, `minCount`, `minIndex`, `minPos`
Examples:
```import std.range : enumerate;
import std.typecons : tuple;

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

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

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

// can be seeded
int[] arr;
writeln(arr.minElement(1)); // 1
```
auto maxElement(alias map = (a) => a, Range)(Range r)
Constraints: if (isInputRange!Range && !isInfinite!Range);

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

Iterates the passed range and returns the maximal element. A custom mapping function can be passed to `map`. In other languages this is sometimes called `argmax`.

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.
`minElement`, `std.algorithm.comparison.max`, `maxCount`, `maxIndex`, `maxPos`
Examples:
```import std.range : enumerate;
import std.typecons : tuple;
writeln([2, 1, 4, 3].maxElement); // 4

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

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

// can be seeded
int[] arr;
writeln(arr.minElement(1)); // 1
```
Range minPos(alias pred = "a < b", Range)(Range range)
Constraints: if (isForwardRange!Range && !isInfinite!Range && is(typeof(binaryFun!pred(range.front, range.front))));

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

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 forward 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`.
`std.algorithm.comparison.max`, `minCount`, `minIndex`, `minElement`
Examples:
```int[] a = [ 2, 3, 4, 1, 2, 4, 1, 1, 2 ];
// Minimum is 1 and first occurs in position 3
writeln(a.minPos); // [1, 2, 4, 1, 1, 2]
// Maximum is 4 and first occurs in position 2
writeln(a.maxPos); // [4, 1, 2, 4, 1, 1, 2]
```
sizediff_t minIndex(alias pred = "a < b", Range)(Range range)
Constraints: if (isInputRange!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
Ο(`range.length`) Exactly `range.length - 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.
`maxIndex`, `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
writeln(a.minIndex); // 3
// Get maximum index with minIndex
writeln(a.minIndex!"a > b"); // 2

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

// Works with more custom types
struct Dog { int age; }
Dog[] dogs = [Dog(10), Dog(5), Dog(15)];
writeln(dogs.minIndex!"a.age < b.age"); // 1
```
sizediff_t maxIndex(alias pred = "a < b", Range)(Range range)
Constraints: 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
Ο(`range`) Exactly `range.length - 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.
`minIndex`, `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];
writeln(a.maxIndex); // 2

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

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

Skip over the initial portion of the first given range (`haystack`) that matches any of the additionally given ranges (`needles`) fully, or if no second range is given skip over the elements that fulfill pred. 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"`.
Examples:
```import std.algorithm.comparison : equal;

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

string[]  r1 = ["abc", "def", "hij"];
dstring[] r2 = ["abc"d];
assert(!skipOver!((a, b) => a.equal(b))(r1, ["def"d]), r1[0]);
writeln(r1); // ["abc", "def", "hij"]
assert(skipOver!((a, b) => a.equal(b))(r1, r2));
writeln(r1); // ["def", "hij"]
```
Examples:
```import std.ascii : isWhite;
import std.range.primitives : empty;

auto s2 = "\t\tvalue";
auto s3 = "";
auto s4 = "\t\t\t";
assert(s2.skipOver!isWhite && s2 == "value");
assert(!s3.skipOver!isWhite);
assert(s4.skipOver!isWhite && s3.empty);
```
Examples:
```auto s = "Hello world";
assert(!skipOver(s, "hello", "HellO"));
writeln(s); // "Hello world"

// the range is skipped over the longest matching needle is skipped
assert(skipOver(s, "foo", "hell", "Hello "));
writeln(s); // "world"
```
Examples:
```import std.algorithm.comparison : equal;

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

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

auto s2 = "";
assert(!s2.skipOver('a'));
```
Examples:
Partial instantiation
```import std.ascii : isWhite;
import std.range.primitives : empty;

alias whitespaceSkiper = skipOver!isWhite;

auto s2 = "\t\tvalue";
auto s3 = "";
auto s4 = "\t\t\t";
assert(whitespaceSkiper(s2) && s2 == "value");
assert(!whitespaceSkiper(s2));
assert(whitespaceSkiper(s4) && s3.empty);
```
bool skipOver(Haystack, Needles...)(ref Haystack haystack, Needles needles)
Constraints: if (is(typeof(binaryFun!pred(haystack.front, needles[0].front))) && isForwardRange!Haystack && allSatisfy!(isInputRange, Needles) && !is(CommonType!(staticMap!(ElementType, staticMap!(Unqual, Needles))) == void));

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

bool skipOver(R, Es...)(ref R r, Es es)
Constraints: if (isInputRange!R && is(typeof(binaryFun!pred(r.front, es[0]))));
Parameters:
 Haystack `haystack` The forward range to move forward. Needles `needles` The input ranges representing the prefix of `r1` to skip over. Es `es` The element to match.
Returns:
`true` if the prefix of `haystack` matches any range of `needles` fully or `pred` evaluates to true, and `haystack` has been advanced to the point past this segment; otherwise false, and `haystack` is left in its original position.
Note
By definition, empty ranges are matched fully and if `needles` contains an empty range, `skipOver` will return `true`.
uint startsWith(alias pred = (a, b) => a == b, Range, Needles...)(Range doesThisStart, Needles withOneOfThese)
Constraints: if (isInputRange!Range && (Needles.length > 1) && is(typeof(.startsWith!pred(doesThisStart, withOneOfThese[0])) : bool) && is(typeof(.startsWith!pred(doesThisStart, withOneOfThese[1..\$])) : uint));

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

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

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

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"));
writeln(startsWith("abc", 'a', "b")); // 1
writeln(startsWith("abc", "b", "a")); // 2
writeln(startsWith("abc", "a", "a")); // 1
writeln(startsWith("abc", "ab", "a")); // 2
writeln(startsWith("abc", "x", "a", "b")); // 2
writeln(startsWith("abc", "x", "aa", "ab")); // 3
writeln(startsWith("abc", "x", "aaa", "sab")); // 0
writeln(startsWith("abc", "x", "aaa", "a", "sab")); // 3

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

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)
Constraints: 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.

This is similar to `takeWhile` in other languages.

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

© 1999–2019 The D Language Foundation