std.algorithm.searching - D Programming Language (original) (raw)

template all(alias pred = "a")

Checks if all of the elements satisfy 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 && (__traits(isTemplate, pred) || is(typeof(unaryFun!pred(range.front)))));

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

template any(alias pred = "a")

Checks if any of the elements satisfies pred.!any can be used to verify that none of the elements satisfypred. 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[])); 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 && (__traits(isTemplate, pred) || is(typeof(unaryFun!pred(range.front)))));

Returns true if and only if the input range range is non-empty and any value found in range satisfies the predicatepred. 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:

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

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"; r = bmFinder.beFound(r); writeln(r); r = bmFinder.beFound(r[2 .. $]); writeln(r);

Range beFound(Range haystack) scope;

@property size_t 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:

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 oftakeExactly(r1, n), where n is the number of elements in the common prefix of both ranges.

Examples:

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

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

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

Counts matches of needle in haystack.

The first overload counts each element e in haystack for which pred(e, needle) is true. pred defaults to equality. Performs Ο(haystack.length) evaluations of pred.

The second overload counts the number of times needle was matched inhaystack. pred compares elements in each range. Throws an exception if needle.empty is true, 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, not2.

NoteRegardless of the overload, count will not accept infinite ranges for haystack.

Parameters:

Returns:

The number of matches in haystack.

Examples:

int[] a = [ 1, 2, 4, 3, 2, 5, 3, 2, 4 ]; writeln(count(a, 2)); writeln(count!("a > b")(a, 2));

Examples:

import std.uni : toLower; writeln(count("abcadfabf", "ab")); writeln(count("ababab", "abab")); writeln(count("ababab", "abx")); writeln(count!((a, b) => toLower(a) == toLower(b))("AbcAdFaBf", "ab"));

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

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

Counts all elements or elements satisfying a predicate in haystack.

The first overload counts each element e in haystack for which pred(e) is true. Performs Ο(haystack.length) evaluations of pred.

The second overload counts the number of elements in a range. If the given range has the length property, that is returned right away, otherwise performs Ο(haystack.length) to walk the range.

Parameters:

Returns:

The number of elements in haystack (for which pred returned true).

Examples:

int[] a = [ 1, 2, 4, 3, 2, 5, 3, 2, 4 ]; writeln(count(a)); writeln(count!("a > 2")(a));

auto countUntil(alias pred = "a == b", R, Rs...)(R haystack, Rs needles)
if (isForwardRange!R && (Rs.length > 0) && (isForwardRange!(Rs[0]) == isInputRange!(Rs[0])) && allSatisfy!(canTestStartsWith!(pred, R), Rs));

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

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

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

Parameters:

Returns:

The number of elements which must be popped from the front ofhaystack before reaching an element for whichstartsWith!pred(haystack, needles) is true. IfstartsWith!pred(haystack, needles) is not true for any element inhaystack, then -1 is returned. If more than one needle is provided,countUntil will wrap the result in a tuple similar toTuple!(ptrdiff_t, "steps", ptrdiff_t needle)

Examples:

writeln(countUntil("hello world", "world")); writeln(countUntil("hello world", 'r')); writeln(countUntil("hello world", "programming")); writeln(countUntil("日本語", "本語")); writeln(countUntil("日本語", '語')); writeln(countUntil("日本語", "五")); writeln(countUntil("日本語", '五')); writeln(countUntil([0, 7, 12, 22, 9], [12, 22])); writeln(countUntil([0, 7, 12, 22, 9], 9)); writeln(countUntil!"a > b"([0, 7, 12, 22, 9], 20)); auto res = "...hello".countUntil("ha", "he"); writeln(res.steps); writeln(res.needle); res = "hello".countUntil("ha", "hu"); writeln(res.steps); writeln(res.needle);

Examples:

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

writeln(countUntil!(isWhite)("hello world")); writeln(countUntil!(isDigit)("hello world")); writeln(countUntil!"a > 20"([0, 7, 12, 22, 9]));

uint endsWith(alias pred = "a == b", Range, Needles...)(Range doesThisEnd, Needles withOneOfThese)
if (isBidirectionalRange!Range && (Needles.length > 1) && allSatisfy!(canTestStartsWith!(pred, Range), Needles));

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:

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 ofdoesThisStart 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')); writeln(endsWith("abc", "c", "a")); writeln(endsWith("abc", "c", "c")); writeln(endsWith("abc", "bc", "c")); writeln(endsWith("abc", "x", "c", "b")); writeln(endsWith("abc", "x", "aa", "bc")); writeln(endsWith("abc", "x", "aaa", "sab")); writeln(endsWith("abc", "x", "aaa", 'c', "sab"));

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

Finds an element e of an input rangewhere pred(e) is true.

• find behaves similarly to dropWhile in other languages.
• To find the last matching element in abidirectional haystack, call find!pred(retro(haystack)). See std.range.retro.

Complexity find performs Ο(walkLength(haystack)) evaluations of pred.

Parameters:

Returns:

haystack advanced such that the front element satisfies pred. If no such element exists, returns an empty haystack.

Examples:

auto arr = [ 1, 2, 3, 4, 1 ]; writeln(find!("a > 2")(arr)); bool pred(int e) => e + 1 > 1.5; writeln(find!(pred)(arr));

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

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

Finds an individual element in an input range. Elements of haystack are compared with needle by using predicatepred with pred(haystack.front, needle). 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).

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

Note: To find the first element not matching the needle, use predicate "a != b".

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:

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.

Examples:

import std.range.primitives;

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

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

Examples:

Case-insensitive find of a string

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

string[] s = ["Hello", "world", "!"]; writeln(s.find!((e, n) => toLower(e) == n)("hello"));

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")); writeln([1, 2, 3, 4].find(SList!int(2, 3)[])); 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])); writeln(a[1 .. $].find!"a.x == b"([2, 3]));

Tuple!(Range, size_t) find(alias pred = "a == b", Range, Needles...)(Range haystack, Needles needles)
if (Needles.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:

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 floator 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)); writeln(find(a, [1, 4])); writeln(find(a, [1, 3], 4)); writeln(find(a, 5, [1.2, 3.5], 2.0));

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

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

Parameters:

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

For more information about pred see find.

Examples:

const arr = [0, 1, 2, 3]; assert(canFind(arr, 2)); assert(!canFind(arr, 4));

assert(arr.canFind(3, 2)); assert(arr.canFind(3, 2) == 2); writeln(arr.canFind([1, 3], 2)); assert(canFind(arr, [1, 2], [2, 3])); writeln(canFind(arr, [1, 2], [2, 3])); assert(canFind(arr, [1, 7], [2, 3])); writeln(canFind(arr, [1, 7], [2, 3])); assert(!canFind(arr, [1, 3], [2, 4])); writeln(canFind(arr, [1, 3], [2, 4]));

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 elem, string needle) => elem.startsWith(needle))(words, "bees"));

Examples:

Search for multiple items in an array of items (search for needles in an array of haystacks)

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)
if (is(typeof(find!pred(haystack))));

Returns true if and only if pred(e) is true for any value e in the input range range. 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, Needles...)(Range haystack, scope Needles needles)
if (Needles.length > 1 && 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 tobool for the same effect or used to get which needle was found first without having to deal with the tuple that 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.

For more information about pred see find.

Parameters:

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.

Examples:

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

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 eitherfind!(pred)(choices, seq.front) is true, or seq becomes empty. Performs Ο(seq.length * choices.length) evaluations of pred.

For more information about pred see find.

Parameters:

Returns:

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

Examples:

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

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

size_t findSkip(alias pred, R1)(ref R1 haystack)
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 forhaystack.front.

For more information about pred see find.

Parameters:

Returns:

true if the needle was found, in which case haystack is positioned after the end of the first occurrence of needle; otherwisefalse, leaving haystack untouched. If no needle is provided, it returns the number of times pred(haystack.front) returned true.

Examples:

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

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

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 ofhaystack that matches needle
• result[2] is the portion of haystackafter the match.

If needle was not found, result[0] comprehends haystackentirely 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
• 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
• 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 aforward range and the type of result[0] (and result[1] for findSplit) is the same as the result of std.range.takeExactly.

For more information about pred see find.

Parameters:

Returns:

A sub-type of std.typecons.Tuple of the split portions of haystack (see above for details). This sub-type of Tuple defines opCast!bool, which returns true when the separating needle was found and false otherwise.

Examples:

Returning a subtype of std.typecons.Tuple enables the following convenient idiom:

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

if (const split = [2, 3, 2, 3, 4, 1].findSplitBefore!"a > b"([2, 2])) { writeln(split[0]); writeln(split[1]); } 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]); assert(r[1].empty); assert(r[2].empty); r = findSplit(a, " "); writeln(r[0]); writeln(r[1]); writeln(r[2]); if (const r1 = findSplitBefore(a, "Sagan")) { assert(r1); writeln(r1[0]); writeln(r1[1]); } if (const r2 = findSplitAfter(a, "Sagan")) { assert(r2); writeln(r2[0]); writeln(r2[1]); }

Examples:

Use std.range.only to find single elements:

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

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 ain range (note the swapped arguments to pred).

These functions may be used for computing arbitrary extrema by choosing predappropriately. 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 algorithms 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:

Returns:

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

LimitationsIf at least one of the arguments is NaN, the result is an unspecified value. See std.algorithm.searching.maxElementfor examples on how to cope with NaNs.

Throws:

Exception if range.empty.

Examples:

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

int[] a = [ 2, 3, 4, 1, 2, 4, 1, 1, 2 ]; writeln(a.minCount); writeln(a.maxCount);

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

auto minElement(alias map = (a) => 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. In other languages this is sometimes called argmin.

ComplexityO(n) Exactly n - 1 comparisons are needed.

Parameters:

PreconditionIf a seed is not given, r must not be empty.

Returns:

The minimal element of the passed-in range.

Note If at least one of the arguments is NaN, the result is an unspecified value.

If you want to ignore NaNs, you can use std.algorithm.iteration.filter and std.math.isNaN to remove them, before applying minElement. Add a suitable seed, to avoid error messages if all elements are NaNs:

.filter!(a=>!a.isNaN).minElement();

If you want to get NaN as a result if a NaN is present in the range, you can use std.algorithm.iteration.fold and std.math.isNaN:

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

Examples:

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

writeln([2, 7, 1, 3].minElement); writeln([5, 3, 7, 9].enumerate.minElement!"a.value"); writeln([[0, 4], [1, 2]].minElement!"a[1]"); int[] arr; writeln(arr.minElement(1));

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

auto maxElement(alias map = (a) => 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 maximal element. A custom mapping function can be passed to map. In other languages this is sometimes called argmax.

ComplexityO(n) Exactly n - 1 comparisons are needed.

Parameters:

PreconditionIf a seed is not given, r must not be empty.

Returns:

The maximal element of the passed-in range.

NoteIf at least one of the arguments is NaN, the result is an unspecified value. See std.algorithm.searching.minElement for examples on how to cope with NaNs.

Examples:

import std.range : enumerate; import std.typecons : tuple; writeln([2, 1, 4, 3].maxElement); writeln([2, 1, 4, 3].enumerate.maxElement!"a.value"); writeln([[0, 4], [1, 2]].maxElement!"a[1]"); int[] arr; writeln(arr.minElement(1));

ElementType!Range[2] extrema(Range)(Range r)
if (isInputRange!Range && !isInfinite!Range);

Returns an array of the minimum and maximum element in r. Performs < 3n/2 comparisons, unlike the naive < 2n.

Parameters:

Examples:

writeln(extrema([5, 2, 9, 4, 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) isfalse for all values a in range. Conversely, the maximum is a value x inrange 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 predappropriately. 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:

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.

LimitationsIf at least one of the arguments is NaN, the result is an unspecified value. See std.algorithm.searching.maxElementfor examples on how to cope with NaNs.

Examples:

int[] a = [ 2, 3, 4, 1, 2, 4, 1, 1, 2 ]; writeln(a.minPos); writeln(a.maxPos);

ptrdiff_t minIndex(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 minimum element.

Parameters:

Complexity Ο(range.length) Exactly range.length - 1 comparisons are needed.

Returns:

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

LimitationsIf at least one of the arguments is NaN, the result is an unspecified value. See std.algorithm.searching.maxElement for examples on how to cope with NaNs.

Examples:

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

writeln(a.minIndex); writeln(a.minIndex!"a > b"); int[] b; writeln(b.minIndex); struct Dog { int age; } Dog[] dogs = [Dog(10), Dog(5), Dog(15)]; writeln(dogs.minIndex!"a.age < b.age");

ptrdiff_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 Ο(range) Exactly range.length - 1 comparisons are needed.

Parameters:

Returns:

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

LimitationsIf at least one of the arguments is NaN, the result is an unspecified value. See std.algorithm.searching.maxElement for examples on how to cope with NaNs.

Examples:

int[] a = [2, 3, 4, 1, 2, 4, 1, 1, 2]; writeln(a.maxIndex); int[] b; writeln(b.maxIndex); struct Dog { int age; } Dog[] dogs = [Dog(10), Dog(15), Dog(5)]; writeln(dogs.maxIndex!"a.age < b.age");

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:

Examples:

import std.algorithm.comparison : equal;

auto s1 = "Hello world"; assert(!skipOver(s1, "Ha")); writeln(s1); 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); assert(skipOver!((a, b) => a.equal(b))(r1, r2)); writeln(r1);

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:

Variadic skipOver

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

Examples:

import std.algorithm.comparison : equal;

auto s1 = "Hello world"; assert(!skipOver(s1, 'a')); writeln(s1); 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); assert(skipOver!((a, b) => a.equal(b))(r, e)); writeln(r); 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)
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)
if (isForwardRange!R && ifTestable!(typeof(r1.front), unaryFun!pred));

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

Parameters:

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.

NoteBy 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)
if (isInputRange!Range && (Needles.length > 1) && allSatisfy!(canTestStartsWith!(pred, Range), Needles));

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 giveninput range starts with (one of) the given needle(s) or, if no needles are given, if its front element fulfils predicate pred.

For more information about pred see find.

Parameters:

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 ofdoesThisStart 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")); writeln(startsWith("abc", "b", "a")); writeln(startsWith("abc", "a", "a")); writeln(startsWith("abc", "ab", "a")); writeln(startsWith("abc", "x", "a", "b")); writeln(startsWith("abc", "x", "aa", "ab")); writeln(startsWith("abc", "x", "aaa", "sab")); writeln(startsWith("abc", "x", "aaa", "a", "sab")); 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]));

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 including the entire sentinel.

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 whichpred(e, sentinel) is true.

This is similar to takeWhile in other languages.

Parameters:

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

Copyright © 1999-2025 by the D Language Foundation | Page generated byDdoc on Sun Jun 15 08:06:04 2025