View source code
Display the source code in std/algorithm/searching.d from which this
page was generated on github.
Report a bug
If you spot a problem with this page, click here to create a
Bugzilla issue.
Improve this page
Quickly fork, edit online, and submit a pull request for this page.
Requires a signed-in GitHub account. This works well for small changes.
If you'd like to make larger changes you may want to consider using
local clone.
Module std.algorithm.searching
This is a submodule of std
.
It contains generic searching algorithms.
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 .) |
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. |
Functions
Name | Description |
---|---|
balancedParens(r, lPar, rPar, 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(needle)
|
Sets up Boyer-Moore matching for use with find below.
By default, elements are compared for equality.
|
commonPrefix(r1, r2)
|
Returns the common prefix of two ranges. |
count(haystack, needle)
|
The first version counts the number of elements x in r for
which pred(x, value) is true . pred defaults to
equality. Performs Ο(haystack ) evaluations of pred .
|
countUntil(haystack, needles)
|
Counts elements in the given
forward range
until the given predicate is true for one of the given needles .
|
endsWith(doesThisEnd, withOneOfThese)
|
Checks if the given range ends with (one of) the given needle(s).
The reciprocal of startsWith .
|
find(haystack, needle)
|
Finds an individual element in an input range.
Elements of haystack are compared with needle by using predicate
pred with pred(haystack .
find performs Ο(walkLength(haystack) ) evaluations of pred .
|
find(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.
|
find(haystack, needle)
|
Finds needle in haystack efficiently using the
Boyer-Moore method.
|
findAdjacent(r)
|
Advances r until it finds the first two adjacent elements a ,
b that satisfy pred(a, b) . Performs Ο(r )
evaluations of pred .
|
findAmong(seq, choices)
|
Searches the given range for an element that matches one of the given choices. |
findSkip(haystack, needle)
|
Finds needle in haystack and positions haystack
right after the first occurrence of needle .
|
findSplit(haystack, needle)
|
These functions find the first occurrence of needle in haystack and then
split haystack as follows.
|
findSplitAfter(haystack, needle)
|
These functions find the first occurrence of needle in haystack and then
split haystack as follows.
|
findSplitBefore(haystack, needle)
|
These functions find the first occurrence of needle in haystack and then
split haystack as follows.
|
maxCount(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(r)
|
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(range)
|
Computes the index of the first occurrence of range 's maximum element.
|
maxPos(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(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(r)
|
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(range)
|
Computes the index of the first occurrence of range 's minimum element.
|
minPos(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(doesThisStart, withOneOfThese)
|
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(range, sentinel, openRight)
|
Lazily iterates range until the element e for which
pred(e, sentinel) is true.
|
Structs
Name | Description |
---|---|
BoyerMooreFinder
|
Sets up Boyer-Moore matching for use with find below.
By default, elements are compared for equality.
|
Until
|
Lazily iterates range until the element e for which
pred(e, sentinel) is true.
|
Templates
Name | Description |
---|---|
all
|
Checks if all of the elements verify pred .
|
any
|
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.
|
canFind
|
Convenience function. Like find, but only returns whether or not the search was successful. |
skipOver
|
Skip over the initial portion of the first given range that matches the second range, or if no second range is given skip over the elements that fullfil pred. Do nothing if there is no match. |
Aliases
Name | Type | Description |
---|---|---|
OpenRight
|
Flag!("openRight")
|
Interval option specifier for until (below) and others.
|
Authors
License
Copyright © 1999-2018 by the D Language Foundation | Page generated by ddox.