The OpenD Programming Language

std.algorithm.searching

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

Cheat Sheet
Function NameDescription
allall!"a > 0"([1, 2, 3, 4]) returns true because all elements are positive
anyany!"a > 0"([1, 2, -3, -4]) returns true because at least one element is positive
balancedParensbalancedParens("((1 + 1) / 2)", '(', ')') returns true because the string has balanced parentheses.
boyerMooreFinderfind("hello world", boyerMooreFinder("or")) returns "orld" using the Boyer-Moore _algorithm.
canFindcanFind("hello world", "or") returns true.
countCounts 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.
countUntilcountUntil(a, b) returns the number of steps taken in a to reach b; for example, countUntil("hello!", "o") returns 4.
commonPrefixcommonPrefix("parakeet", "parachute") returns "para".
endsWithendsWith("rocks", "ks") returns true.
findfind("hello world", "or") returns "orld" using linear search. (For binary search refer to std.range.SortedRange.)
findAdjacentfindAdjacent([1, 2, 3, 3, 4]) returns the subrange starting with two equal adjacent elements, i.e. [3, 3, 4].
findAmongfindAmong("abcd", "qcx") returns "cd" because 'c' is among "qcx".
findSkipIf a = "abcde", then findSkip(a, "x") returns false and leaves a unchanged, whereas findSkip(a, "c") advances a to "de" and returns true.
findSplitfindSplit("abcdefg", "de") returns a tuple of three ranges "abc", "de", and "fg".
findSplitAfterfindSplitAfter("abcdefg", "de") returns a tuple of two ranges "abcde" and "fg".
findSplitBeforefindSplitBefore("abcdefg", "de") returns a tuple of two ranges "abc" and "defg".
minCountminCount([2, 1, 1, 4, 1]) returns tuple(1, 3).
maxCountmaxCount([2, 4, 1, 4, 1]) returns tuple(4, 2).
minElementSelects the minimal element of a range. minElement([3, 4, 1, 2]) returns 1.
maxElementSelects the maximal element of a range. maxElement([3, 4, 1, 2]) returns 4.
minIndexIndex of the minimal element of a range. minIndex([3, 4, 1, 2]) returns 2.
maxIndexIndex of the maximal element of a range. maxIndex([3, 4, 1, 2]) returns 1.
minPosminPos([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.
maxPosmaxPos([2, 3, 1, 3, 4, 1]) returns the subrange [4, 1], i.e., positions the range at the first occurrence of its maximal element.
skipOverAssume 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.
startsWithstartsWith("hello, world", "hello") returns true.
untilLazily 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)

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

$(PANEL $(UL $(LI `find` behaves similarly to `dropWhile` in other languages.) $(LI To _find the *last* matching element in a $(REF_ALTTEXT bidirectional, isBidirectionalRange, std,range,primitives) `haystack`, call `find!pred(retro(haystack))`. See $(REF retro, std,range).) ))

find
InputRange find(InputRange haystack, Element needle)
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). 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).

find
Tuple!(Range, size_t) find(Range haystack, Needles 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.

Meta