std.algorithm.searching

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

Copyright

Andrei Alexandrescu 2008-.

License

Boost License 1.0.

Authors

Andrei Alexandrescu

Source: std/algorithm/searching.d

var hasConstEmptyMember

tmpl all any canFind canTestStartsWith skipOver

alias OpenRight

struct BoyerMooreFinder FindSplitResult Until

fn balancedParens boyerMooreFinder commonPrefix count countUntil endsWith extrema extremum find findAdjacent findAmong findSkip findSplit findSplitAfter findSplitBefore maxCount maxElement maxIndex maxPos minCount minElement minIndex minPos simpleMindedFind skipAll startsWith until

Types 4

structBoyerMooreFinder(alias pred, 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.
`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.

Fields

size_t[] skip

ptrdiff_t[ElementType!(Range)] occ

Range needle

Methods

ptrdiff_t occurrence(ElementType!(Range) c) scope

bool needlematch(R)(R needle,
                               size_t portion,  size_t offset)

Range beFound(Range haystack) scope

size_t length() @property

Constructors

this(Range needle)

private structFindSplitResult(ubyte emptyRangeIndex, Types...)

Fields

Tuple!Types asTuple

Methods

void opAssign(typeof(asTuple) rhs)

Constructors

this(Types vals)

aliasOpenRight = Flag!"openRight"

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.

structUntil(alias pred, Range, Sentinel) if (isInputRange!Range)

ditto

Fields

private Range _input

private OpenRight _openRight

private bool _matchStarted

private bool _done

Methods

bool empty() @property

@property auto ref front()

private bool predSatisfied()

void popFront()

Functions 52

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

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

Ditto

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

Returns the common prefix of two ranges.

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

ditto

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

ditto

fnauto commonPrefix(R1, R2)(R1 r1, R2 r2) if (isNarrowString!R1 && isNarrowString!R2)ditto

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

Counts matches of `needle` in `haystack`.

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

Ditto

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

Counts all elements or elements satisfying a predicate in `haystack`.

fnsize_t count(R)(R haystack) if (isInputRange!R && !isInfinite!R)Ditto

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

Counts elements in the given input range until the given predicate is true for one of the given `needles` or `needle`.

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

ditto

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

Counts elements in the given input range until the given predicate is true for one of the elements of `haystack`.

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

Checks if the given range ends with (one of) the given needle(s). The reciprocal of `startsWith`.

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

Ditto

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

Ditto

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

Ditto

private fn

auto extremum(alias  map,  alias  selector =  "a < b",  Range)(Range r) if (isInputRange!Range && !isInfinite!Range &&
     is(typeof(unaryFun!map(ElementType!(Range).init))))

Iterates the passed range and selects the extreme element with `less`. If the extreme element occurs multiple time, the first occurrence will be returned.

private fn

auto extremum(alias  map,  alias  selector =  "a < b",  Range,
                       RangeElementType =  ElementType!Range)(Range r,  RangeElementType seedElement) if (isInputRange!Range && !isInfinite!Range &&
    !is(CommonType!(ElementType!Range,  RangeElementType)  ==  void)  &&
      is(typeof(unaryFun!map(ElementType!(Range).init))))

private fn

auto extremum(alias  selector =  "a < b",  Range)(Range r) if (isInputRange!Range && !isInfinite!Range &&
    !is(typeof(unaryFun!selector(ElementType!(Range).init))))

private fn

auto extremum(alias  selector =  "a < b",  Range,
                       RangeElementType =  ElementType!Range)(Range r,  RangeElementType seedElement) if (isInputRange!Range && !isInfinite!Range &&
    !is(CommonType!(ElementType!Range,  RangeElementType)  ==  void)  &&
    !is(typeof(unaryFun!selector(ElementType!(Range).init))))

fnInputRange find(alias pred, InputRange)(InputRange haystack) if (isInputRange!InputRange)Finds an element `e` of an input range where `pred(e)` is `true`. PANEL UL `find` behaves similarly to `dropWhile` in other languages. To find the last matching element in a bidirectional

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

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 binaryFun,...

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

ditto

private fnR1 simpleMindedFind(alias pred, R1, R2)(R1 haystack, scope R2 needle)

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.

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

Finds `needle` in `haystack` efficiently using the https://en.wikipedia.org/wiki/Boyer%E2%80%93Moorestringsearch_algorithm method.

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

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.

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

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

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

ditto

fnauto findSplit(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.

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

Ditto

auto findSplitAfter(alias  pred =  "a == b",  R1,  R2)(R1 haystack,  R2 needle) if (isForwardRange!R1 &&  isForwardRange!R2)

Ditto

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

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) is `false` for all values `a` in `rang...

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

Ditto

fnauto minElement(alias map = (a => a), Range)(Range r) if (isInputRange!Range && !isInfinite!Range)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`.

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

ditto

fnauto maxElement(alias map = (a => a), Range)(Range r) if (isInputRange!Range && !isInfinite!Range)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`.

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

ditto

fnElementType!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`. Params: r = The range to traverse.

Range minPos(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.

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

Ditto

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.

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.

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

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

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

Ditto

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

Ditto

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

Ditto

private fnvoid skipAll(alias pred = "a == b", R, Es...)(ref R r, Es es)

Until!(pred,  Range,  Sentinel) until(alias  pred =  "a == b",  Range,  Sentinel)(Range range,  Sentinel sentinel,  OpenRight openRight =  Yes.openRight) if (!is(Sentinel ==  OpenRight))

Lazily iterates `range` until the element `e` for which `pred(e, sentinel)` is true.

fnUntil!(pred, Range, void) until(alias pred, Range)(Range range, OpenRight openRight = Yes.openRight)Ditto

Variables 1

private enumvarhasConstEmptyMember = is(typeof(((const T * a) => (* a).empty)(null)) : bool)

Templates 5

tmplall(alias pred = "a")

Checks if _all of the elements satisfy pred.

Functions

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.

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

Functions

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 predicate pred. Performs (at most) range.length evaluations of pred.

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

Parameters

pred The predicate that determines whether elements from each respective range match. Defaults to equality "a == b".

Functions

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

Parameters

`haystack`	The forward range to move forward.
`needles`	The input ranges representing the prefix of `r1` to skip over.
`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.

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

Ditto

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

Ditto

tmplcanTestStartsWith(alias pred, Haystack)

std.algorithm.searching

Copyright

License

Authors

Types 4

Parameters

Returns

Functions 52

Variables 1

Templates 5

See Also

Parameters

Parameters

Returns

Note