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 a tuple of three ranges `"abc"`, `"de"`, and `"fg"`.
findSplitAfter	`findSplitAfter("abcdefg", "de")` returns a tuple of two ranges `"abcde"` and `"fg"`.
findSplitBefore	`findSplitBefore("abcdefg", "de")` returns a tuple of 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. `minIndex([3, 4, 1, 2])` returns `2`.
maxIndex	Index of the maximal element of a range. `maxIndex([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.

Members

Aliases

OpenRight alias OpenRight = Flag!"openRight": Interval option specifier for until (below) and others.

Functions

balancedParens bool balancedParens(Range r, E lPar, E rPar, size_t maxNestingLevel): 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.
boyerMooreFinder BoyerMooreFinder!(binaryFun!(pred), Range) boyerMooreFinder(Range needle): Sets up Boyer-Moore matching for use with find below. By default, elements are compared for equality.
commonPrefix auto commonPrefix(R1 r1, R2 r2): Returns the common prefix of two ranges.
count size_t count(Range haystack, E needle)
size_t count(R1 haystack, R2 needle)
size_t count(R haystack): The first version counts the number of elements x in r for which pred(x, value) is true. pred defaults to equality. Performs O(haystack.length) evaluations of pred.
countUntil ptrdiff_t countUntil(R haystack, Rs needles)
ptrdiff_t countUntil(R haystack, N needle)
ptrdiff_t countUntil(R haystack): Counts elements in the given forward range until the given predicate is true for one of the given needles.
endsWith uint endsWith(Range doesThisEnd, Needles withOneOfThese)
bool endsWith(R1 doesThisEnd, R2 withThis)
bool endsWith(R doesThisEnd, E withThis)
bool endsWith(R doesThisEnd): Checks if the given range ends with (one of) the given needle(s). The reciprocal of startsWith.
find InputRange find(InputRange haystack, Element needle)
InputRange find(InputRange haystack)
R1 find(R1 haystack, R2 needle): 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 O(walkLength(haystack)) evaluations of pred.
find Tuple!(Range, size_t) find(Range haystack, Ranges 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.
find RandomAccessRange find(RandomAccessRange haystack, BoyerMooreFinder!(pred, InputRange) needle): Finds needle in haystack efficiently using the Boyer-Moore method.
findAdjacent Range findAdjacent(Range r): Advances r until it finds the first two adjacent elements a, b that satisfy pred(a, b). Performs O(r.length) evaluations of pred.
findAmong InputRange findAmong(InputRange seq, ForwardRange choices): Searches the given range for an element that matches one of the given choices.
findSkip bool findSkip(R1 haystack, R2 needle)
size_t findSkip(R1 haystack): Finds needle in haystack and positions haystack right after the first occurrence of needle.
findSplit auto findSplit(R1 haystack, R2 needle)
findSplitAfter auto findSplitAfter(R1 haystack, R2 needle)
findSplitBefore auto findSplitBefore(R1 haystack, R2 needle): These functions find the first occurrence of needle in haystack and then split haystack as follows.
maxCount Tuple!(ElementType!Range, size_t) maxCount(Range range): 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).
maxElement auto maxElement(Range r)
auto maxElement(Range r, RangeElementType seed): 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.
maxIndex ptrdiff_t maxIndex(Range range): Computes the index of the first occurrence of range's maximum element.
maxPos Range maxPos(Range range): 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.
minCount Tuple!(ElementType!Range, size_t) minCount(Range range): 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).
minElement auto minElement(Range r)
auto minElement(Range r, RangeElementType seed): 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.
minIndex ptrdiff_t minIndex(Range range): Computes the index of the first occurrence of range's minimum element.
minPos Range minPos(Range range): 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.
startsWith uint startsWith(Range doesThisStart, Needles withOneOfThese)
bool startsWith(R1 doesThisStart, R2 withThis)
bool startsWith(R doesThisStart, E withThis)
bool startsWith(R doesThisStart): 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.
until Until!(pred, Range, Sentinel) until(Range range, Sentinel sentinel, OpenRight openRight)
Until!(pred, Range, void) until(Range range, OpenRight openRight): Lazily iterates range until the element e for which pred(e, sentinel) is true.

Structs

BoyerMooreFinder struct BoyerMooreFinder(alias pred, Range): Sets up Boyer-Moore matching for use with find below. By default, elements are compared for equality.
Until struct Until(alias pred, Range, Sentinel): Lazily iterates range until the element e for which pred(e, sentinel) is true.

Templates

all template all(alias pred = "a"): Checks if _all of the elements satisfy pred.
any template any(alias pred = "a"): Checks if _any of the elements satisfies pred. !any can be used to verify that none of the elements satisfy pred. This is sometimes called exists in other languages.
canFind template canFind(alias pred = "a == b"): Convenience function. Like find, but only returns whether or not the search was successful.
skipOver 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.

std.algorithm.searching

Members

Aliases

Functions

Structs

Templates

Meta

Source

License

Copyright

Authors