// Written in the D programming language./**This is a submodule of $(MREF std, algorithm).It contains generic searching algorithms. $(SCRIPT inhibitQuickIndex = 1;)$(BOOKTABLE Cheat Sheet,$(TR $(TH Function Name) $(TH Description))$(T2 all,        `all!"a > 0"([1, 2, 3, 4])` returns `true` because all elements        are positive)$(T2 any,        `any!"a > 0"([1, 2, -3, -4])` returns `true` because at least one        element is positive)$(T2 balancedParens,        `balancedParens("((1 + 1) / 2)", '(', ')')` returns `true` because the        string has balanced parentheses.)$(T2 boyerMooreFinder,        `find("hello world", boyerMooreFinder("or"))` returns `"orld"`        using the $(LINK2 https://en.wikipedia.org/wiki/Boyer%E2%80%93Moore_string_search_algorithm,        Boyer-Moore _algorithm).)$(T2 canFind,        `canFind("hello world", "or")` returns `true`.)$(T2 count,        Counts all elements or elements matching a predicate, specific element or sub-range.$(BR)        `count([1, 2, 1])` returns `3`,        `count([1, 2, 1], 1)` returns `2` and        `count!"a < 0"([1, -3, 0])` returns `1`.)$(T2 countUntil,        `countUntil(a, b)` returns the number of steps taken in `a` to        reach `b`; for example, `countUntil("hello!", "o")` returns        `4`.)$(T2 commonPrefix,        `commonPrefix("parakeet", "parachute")` returns `"para"`.)$(T2 endsWith,        `endsWith("rocks", "ks")` returns `true`.)$(T2 extrema, `extrema([2, 1, 3, 5, 4])` returns `[1, 5]`.)$(T2 find,        `find("hello world", "or")` returns `"orld"` using linear search.        (For binary search refer to $(REF SortedRange, std,range).))$(T2 findAdjacent,        `findAdjacent([1, 2, 3, 3, 4])` returns the subrange starting with        two equal adjacent elements, i.e. `[3, 3, 4]`.)$(T2 findAmong,        `findAmong("abcd", "qcx")` returns `"cd"` because `'c'` is        among `"qcx"`.)$(T2 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`.)$(T2 findSplit,        `findSplit("abcdefg", "de")` returns a tuple of three ranges `"abc"`,        `"de"`, and `"fg"`.)$(T2 findSplitAfter,`findSplitAfter("abcdefg", "de")` returns a tuple of two ranges `"abcde"`        and `"fg"`.)$(T2 findSplitBefore,        `findSplitBefore("abcdefg", "de")` returns a tuple of two ranges `"abc"`        and `"defg"`.)$(T2 minCount,        `minCount([2, 1, 1, 4, 1])` returns `tuple(1, 3)`.)$(T2 maxCount,        `maxCount([2, 4, 1, 4, 1])` returns `tuple(4, 2)`.)$(T2 minElement,        Selects the minimal element of a range.        `minElement([3, 4, 1, 2])` returns `1`.)$(T2 maxElement,        Selects the maximal element of a range.        `maxElement([3, 4, 1, 2])` returns `4`.)$(T2 minIndex,        Index of the minimal element of a range.        `minIndex([3, 4, 1, 2])` returns `2`.)$(T2 maxIndex,        Index of the maximal element of a range.        `maxIndex([3, 4, 1, 2])` returns `1`.)$(T2 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.)$(T2 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.)$(T2 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`.)$(T2 startsWith,        `startsWith("hello, world", "hello")` returns `true`.)$(T2 until,        Lazily iterates a range until a specific value is found.)) Copyright: Andrei Alexandrescu 2008-. License: $(HTTP boost.org/LICENSE_1_0.txt, Boost License 1.0). Authors: $(HTTP erdani.com, Andrei Alexandrescu) Source: $(PHOBOSSRC std/algorithm/searching.d) Macros:T2=$(TR $(TDNW $(LREF $1)) $(TD $+)) */module std.algorithm.searching; import std.functional : unaryFun, binaryFun;import std.meta : allSatisfy;import std.range.primitives;import std.traits;import std.typecons : Tuple, Flag, Yes, No, tuple; /++Checks if $(I _all) of the elements satisfy `pred`. +/template all(alias pred = "a"){    /++    Returns `true` if and only if the input range `range` is empty    or $(I _all) values found in `range` satisfy the predicate `pred`.    Performs (at most) $(BIGOH range.length) evaluations of `pred`.     +/    bool all(Range)(Range range)    if (isInputRange!Range &&        (__traits(isTemplate, pred) || is(typeof(unaryFun!pred(range.front)))))    {        import std.functional : not;         return find!(not!(unaryFun!pred))(range).empty;    }} ///@safe unittest{    assert( all!"a & 1"([1, 3, 5, 7, 9]));    assert(!all!"a & 1"([1, 2, 3, 5, 7, 9]));} /++`all` can also be used without a predicate, if its items can beevaluated to true or false in a conditional statement. This can be aconvenient way to quickly evaluate that $(I _all) of the elements of a rangeare true. +/@safe unittest{    int[3] vals = [5, 3, 18];    assert( all(vals[]));} @safe unittest{    int x = 1;    assert(all!(a => a > x)([2, 3]));    assert(all!"a == 0x00c9"("\xc3\x89")); // Test that `all` auto-decodes.} /++Checks if $(I _any) of the elements satisfies `pred`.`!any` can be used to verify that $(I none) of the elements satisfy`pred`.This is sometimes called `exists` in other languages. +/template any(alias pred = "a"){    /++    Returns `true` if and only if the input range `range` is non-empty    and $(I _any) value found in `range` satisfies the predicate    `pred`.    Performs (at most) $(BIGOH range.length) evaluations of `pred`.     +/    bool any(Range)(Range range)    if (isInputRange!Range &&        (__traits(isTemplate, pred) || is(typeof(unaryFun!pred(range.front)))))    {        return !find!pred(range).empty;    }} ///@safe unittest{    import std.ascii : isWhite;    assert( all!(any!isWhite)(["a a", "b b"]));    assert(!any!(all!isWhite)(["a a", "b b"]));} /++`any` can also be used without a predicate, if its items can beevaluated to true or false in a conditional statement. `!any` can be aconvenient way to quickly test that $(I none) of the elements of a rangeevaluate to true. +/@safe unittest{    int[3] vals1 = [0, 0, 0];    assert(!any(vals1[])); //none of vals1 evaluate to true     int[3] vals2 = [2, 0, 2];    assert( any(vals2[]));    assert(!all(vals2[]));     int[3] vals3 = [3, 3, 3];    assert( any(vals3[]));    assert( all(vals3[]));} @safe unittest{    auto a = [ 1, 2, 0, 4 ];    assert(any!"a == 2"(a));    assert(any!"a == 0x3000"("\xe3\x80\x80")); // Test that `any` auto-decodes.} // balancedParens/**Checks whether `r` has "balanced parentheses", i.e. all instancesof `lPar` are closed by corresponding instances of `rPar`. Theparameter `maxNestingLevel` controls the nesting level allowed. Themost common uses are the default or `0`. In the latter case, nonesting is allowed. Params:    r = The range to check.    lPar = The element corresponding with a left (opening) parenthesis.    rPar = The element corresponding with a right (closing) parenthesis.    maxNestingLevel = The maximum allowed nesting level. Returns:    true if the given range has balanced parenthesis within the given maximum    nesting level; false otherwise.*/bool balancedParens(Range, E)(Range r, E lPar, E rPar,        size_t maxNestingLevel = size_t.max)if (isInputRange!(Range) && is(typeof(r.front == lPar))){    size_t count;     static if (is(immutable ElementEncodingType!Range == immutable E) && isNarrowString!Range)    {        import std.utf : byCodeUnit;        auto rn = r.byCodeUnit;    }    else    {        alias rn = r;    }     for (; !rn.empty; rn.popFront())    {        if (rn.front == lPar)        {            if (count > maxNestingLevel) return false;            ++count;        }        else if (rn.front == rPar)        {            if (!count) return false;            --count;        }    }    return count == 0;} ///@safe pure unittest{    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, '⌈', '⌉'));} /** * Sets up Boyer-Moore matching for use with `find` below. * By default, elements are compared for equality. * * `BoyerMooreFinder` allocates GC memory. * * Params: * 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. */struct BoyerMooreFinder(alias pred, Range){private:    size_t[] skip;                              // GC allocated    ptrdiff_t[ElementType!(Range)] occ;         // GC allocated    Range needle;     ptrdiff_t occurrence(ElementType!(Range) c) scope    {        auto p = c in occ;        return p ? *p : -1;    } /*This helper function checks whether the last "portion" bytes of"needle" (which is "nlen" bytes long) exist within the "needle" atoffset "offset" (counted from the end of the string), and whether thecharacter preceding "offset" is not a match.  Notice that the rangebeing checked may reach beyond the beginning of the string. Such rangeis ignored. */    static bool needlematch(R)(R needle,                              size_t portion, size_t offset)    {        import std.algorithm.comparison : equal;        ptrdiff_t virtual_begin = needle.length - offset - portion;        ptrdiff_t ignore = 0;        if (virtual_begin < 0)        {            ignore = -virtual_begin;            virtual_begin = 0;        }        if (virtual_begin > 0            && needle[virtual_begin - 1] == needle[$ - portion - 1])            return 0;         immutable delta = portion - ignore;        return equal(needle[needle.length - delta .. needle.length],                needle[virtual_begin .. virtual_begin + delta]);    } public:    ///    this(Range needle)    {        if (!needle.length) return;        this.needle = needle;        /* Populate table with the analysis of the needle */        /* But ignoring the last letter */        foreach (i, n ; needle[0 .. $ - 1])        {            this.occ[n] = i;        }        /* Preprocess #2: init skip[] */        /* Note: This step could be made a lot faster.         * A simple implementation is shown here. */        this.skip = new size_t[needle.length];        foreach (a; 0 .. needle.length)        {            size_t value = 0;            while (value < needle.length                   && !needlematch(needle, a, value))            {                ++value;            }            this.skip[needle.length - a - 1] = value;        }    }     ///    Range beFound(Range haystack) scope    {        import std.algorithm.comparison : max;         if (!needle.length) return haystack;        if (needle.length > haystack.length) return haystack[$ .. $];        /* Search: */        immutable limit = haystack.length - needle.length;        for (size_t hpos = 0; hpos <= limit; )        {            size_t npos = needle.length - 1;            while (pred(needle[npos], haystack[npos+hpos]))            {                if (npos == 0) return haystack[hpos .. $];                --npos;            }            hpos += max(skip[npos], cast(ptrdiff_t) npos - occurrence(haystack[npos+hpos]));        }        return haystack[$ .. $];    }     ///    @property size_t length()    {        return needle.length;    }     ///    alias opDollar = length;} /// DittoBoyerMooreFinder!(binaryFun!(pred), Range) boyerMooreFinder(alias pred = "a == b", Range)(Range needle)if ((isRandomAccessRange!(Range) && hasSlicing!Range) || isSomeString!Range){    return typeof(return)(needle);} ///@safe pure nothrow unittest{    auto bmFinder = boyerMooreFinder("TG");     string r = "TAGTGCCTGA";    // search for the first match in the haystack r    r = bmFinder.beFound(r);    assert(r == "TGCCTGA");     // continue search in haystack    r = bmFinder.beFound(r[2 .. $]);    assert(r == "TGA");} /**Returns the common prefix of two ranges. Params:    pred = The predicate to use in comparing elements for commonality. Defaults        to equality `"a == b"`.     r1 = A $(REF_ALTTEXT forward range, isForwardRange, std,range,primitives) of        elements.     r2 = An $(REF_ALTTEXT input range, isInputRange, std,range,primitives) of        elements. 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 of`takeExactly(r1, n)`, where `n` is the number of elements in the commonprefix of both ranges. See_Also:    $(REF takeExactly, std,range) */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)))){    import std.algorithm.comparison : min;    static if (isRandomAccessRange!R1 && isRandomAccessRange!R2 &&               hasLength!R1 && hasLength!R2 &&               hasSlicing!R1)    {        immutable limit = min(r1.length, r2.length);        foreach (i; 0 .. limit)        {            if (!binaryFun!pred(r1[i], r2[i]))            {                return r1[0 .. i];            }        }        return r1[0 .. limit];    }    else    {        import std.range : takeExactly;        auto result = r1.save;        size_t i = 0;        for (;             !r1.empty && !r2.empty && binaryFun!pred(r1.front, r2.front);             ++i, r1.popFront(), r2.popFront())        {}        return takeExactly(result, i);    }} ///@safe unittest{    assert(commonPrefix("hello, world", "hello, there") == "hello, ");} /// dittoauto commonPrefix(alias pred, R1, R2)(R1 r1, R2 r2)if (isNarrowString!R1 && isInputRange!R2 &&    is(typeof(binaryFun!pred(r1.front, r2.front)))){    import std.utf : decode;     auto result = r1.save;    immutable len = r1.length;    size_t i = 0;     for (size_t j = 0; i < len && !r2.empty; r2.popFront(), i = j)    {        immutable f = decode(r1, j);        if (!binaryFun!pred(f, r2.front))            break;    }     return result[0 .. i];

Lines 1–500 of 5639. Load more