// Written in the D programming language./**This is a submodule of $(MREF std, algorithm).It contains generic iteration algorithms. $(SCRIPT inhibitQuickIndex = 1;)$(BOOKTABLE Cheat Sheet,$(TR $(TH Function Name) $(TH Description))$(T2 cache,        Eagerly evaluates and caches another range's `front`.)$(T2 lazyCache,        Lazily evaluates and caches another range's `front`, unlike `cache`.)$(T2 cacheBidirectional,        As above, but also provides `back` and `popBack`.)$(T2 chunkBy,        `chunkBy!((a,b) => a[1] == b[1])([[1, 1], [1, 2], [2, 2], [2, 1]])`        returns a range containing 3 subranges: the first with just        `[1, 1]`; the second with the elements `[1, 2]` and `[2, 2]`;        and the third with just `[2, 1]`.)$(T2 cumulativeFold,        `cumulativeFold!((a, b) => a + b)([1, 2, 3, 4])` returns a        lazily-evaluated range containing the successive reduced values `1`,        `3`, `6`, `10`.)$(T2 each,        `each!writeln([1, 2, 3])` eagerly prints the numbers `1`, `2`        and `3` on their own lines.)$(T2 filter,        `filter!(a => a > 0)([1, -1, 2, 0, -3])` iterates over elements `1`        and `2`.)$(T2 filterBidirectional,        Similar to `filter`, but also provides `back` and `popBack` at        a small increase in cost.)$(T2 fold,        `fold!((a, b) => a + b)([1, 2, 3, 4])` returns `10`.)$(T2 group,        `group([5, 2, 2, 3, 3])` returns a range containing the tuples        `tuple(5, 1)`, `tuple(2, 2)`, and `tuple(3, 2)`.)$(T2 joiner,        `joiner(["hello", "world!"], "; ")` returns a range that iterates        over the characters `"hello; world!"`. No new string is created -        the existing inputs are iterated.)$(T2 map,        `map!(a => a * 2)([1, 2, 3])` lazily returns a range with the numbers        `2`, `4`, `6`.)$(T2 mean,        Colloquially known as the average, `mean([1, 2, 3])` returns `2`.)$(T2 permutations,        Lazily computes all permutations using Heap's algorithm.)$(T2 reduce,        `reduce!((a, b) => a + b)([1, 2, 3, 4])` returns `10`.        This is the old implementation of `fold`.)$(T2 splitWhen,        Lazily splits a range by comparing adjacent elements.)$(T2 splitter,        Lazily splits a range by a separator, element predicate or whitespace.)$(T2 substitute,        `[1, 2].substitute(1, 0.1)` returns `[0.1, 2]`.)$(T2 sum,        Same as `fold`, but specialized for accurate summation.)$(T2 uniq,        Iterates over the unique elements in a range, which is assumed sorted.)) 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/iteration.d) Macros:T2=$(TR $(TDNW $(LREF $1)) $(TD $+)) */module std.algorithm.iteration; import std.functional : unaryFun, binaryFun;import std.range.primitives;import std.traits;import std.typecons : Flag, Yes, No; /++`cache` eagerly evaluates $(REF_ALTTEXT front, front, std,range,primitives) of `range`on each construction or call to $(REF_ALTTEXT popFront, popFront, std,range,primitives),to store the result in a _cache.The result is then directly returned when $(REF_ALTTEXT front, front, std,range,primitives) is called,rather than re-evaluated. This can be a useful function to place in a chain, after functionsthat have expensive evaluation, as a lazy alternative to $(REF array, std,array).In particular, it can be placed after a call to $(LREF map), or before a call$(REF filter, std,range) or $(REF tee, std,range) `cache` may provide$(REF_ALTTEXT bidirectional range, isBidirectionalRange, std,range,primitives)iteration if needed, but since this comes at an increased cost, it must be explicitly requested via thecall to `cacheBidirectional`. Furthermore, a bidirectional _cache willevaluate the "center" element twice, when there is only one element left inthe range. `cache` does not provide random access primitives,as `cache` would be unable to _cache the random accesses.If `Range` provides slicing primitives,then `cache` will provide the same slicing primitives,but `hasSlicing!Cache` will not yield true (as the $(REF hasSlicing, std,range,primitives)trait also checks for random access). Params:    range = an $(REF_ALTTEXT input range, isInputRange, std,range,primitives) Returns:    An $(REF_ALTTEXT input range, isInputRange, std,range,primitives) with the cached values of range+/auto cache(Range)(Range range)if (isInputRange!Range){    return _Cache!(Range, false)(range);} /// dittoauto cacheBidirectional(Range)(Range range)if (isBidirectionalRange!Range){    return _Cache!(Range, true)(range);} ///@safe unittest{    import std.algorithm.comparison : equal;    import std.range, std.stdio;    import std.typecons : tuple;     ulong counter = 0;    double fun(int x)    {        ++counter;        // http://en.wikipedia.org/wiki/Quartic_function        return ( (x + 4.0) * (x + 1.0) * (x - 1.0) * (x - 3.0) ) / 14.0 + 0.5;    }    // Without cache, with array (greedy)    auto result1 = iota(-4, 5).map!(a =>tuple(a, fun(a)))()                             .filter!(a => a[1] < 0)()                             .map!(a => a[0])()                             .array();     // the values of x that have a negative y are:    assert(equal(result1, [-3, -2, 2]));     // Check how many times fun was evaluated.    // As many times as the number of items in both source and result.    assert(counter == iota(-4, 5).length + result1.length);     counter = 0;    // Without array, with cache (lazy)    auto result2 = iota(-4, 5).map!(a =>tuple(a, fun(a)))()                             .cache()                             .filter!(a => a[1] < 0)()                             .map!(a => a[0])();     // the values of x that have a negative y are:    assert(equal(result2, [-3, -2, 2]));     // Check how many times fun was evaluated.    // Only as many times as the number of items in source.    assert(counter == iota(-4, 5).length);} // https://issues.dlang.org/show_bug.cgi?id=15891@safe pure unittest{    assert([1].map!(x=>[x].map!(y=>y)).cache.front.front == 1);} /++Tip: `cache` is eager when evaluating elements. If calling front on theunderlying range has a side effect, it will be observable before callingfront on the actual cached range. Furthermore, care should be taken composing `cache` with $(REF take, std,range).By placing `take` before `cache`, then `cache` will be "aware"of when the range ends, and correctly stop caching elements when needed.If calling front has no side effect though, placing `take` after `cache`may yield a faster range. Either way, the resulting ranges will be equivalent, but maybe not at thesame cost or side effects.+/@safe unittest{    import std.algorithm.comparison : equal;    import std.range;    int i = 0;     auto r = iota(0, 4).tee!((a){i = a;}, No.pipeOnPop);    auto r1 = r.take(3).cache();    auto r2 = r.cache().take(3);     assert(equal(r1, [0, 1, 2]));    assert(i == 2); //The last "seen" element was 2. The data in cache has been cleared.     assert(equal(r2, [0, 1, 2]));    assert(i == 3); //cache has accessed 3. It is still stored internally by cache.} @safe unittest{    import std.algorithm.comparison : equal;    import std.range;    auto a = [1, 2, 3, 4];    assert(equal(a.map!(a => (a - 1) * a)().cache(),                      [ 0, 2, 6, 12]));    assert(equal(a.map!(a => (a - 1) * a)().cacheBidirectional().retro(), [12, 6, 2,  0]));    auto r1 = [1, 2, 3, 4].cache()             [1 .. $];    auto r2 = [1, 2, 3, 4].cacheBidirectional()[1 .. $];    assert(equal(r1, [2, 3, 4]));    assert(equal(r2, [2, 3, 4]));} @safe unittest{    import std.algorithm.comparison : equal;     //immutable test    static struct S    {        int i;        this(int i)        {            //this.i = i;        }    }    immutable(S)[] s = [S(1), S(2), S(3)];    assert(equal(s.cache(),              s));    assert(equal(s.cacheBidirectional(), s));} @safe pure nothrow unittest{    import std.algorithm.comparison : equal;     //safety etc    auto a = [1, 2, 3, 4];    assert(equal(a.cache(),              a));    assert(equal(a.cacheBidirectional(), a));} @safe unittest{    char[][] stringbufs = ["hello".dup, "world".dup];    auto strings = stringbufs.map!((a)=>a.idup)().cache();    assert(strings.front is strings.front);} @safe unittest{    import std.range : cycle;    import std.algorithm.comparison : equal;     auto c = [1, 2, 3].cycle().cache();    c = c[1 .. $];    auto d = c[0 .. 1];    assert(d.equal([2]));} @safe unittest{    static struct Range    {        bool initialized = false;        bool front() @property {return initialized = true;}        void popFront() {initialized = false;}        enum empty = false;    }    auto r = Range().cache();    assert(r.source.initialized == true);} private struct _Cache(R, bool bidir){    import core.exception : RangeError;     private    {        import std.algorithm.internal : algoFormat;        import std.meta : AliasSeq;         alias E  = ElementType!R;        alias UE = Unqual!E;         R source;         static if (bidir) alias CacheTypes = AliasSeq!(UE, UE);        else              alias CacheTypes = AliasSeq!UE;        CacheTypes caches;         static assert(isAssignable!(UE, E) && is(UE : E),            algoFormat(                "Cannot instantiate range with %s because %s elements are not assignable to %s.",                R.stringof,                E.stringof,                UE.stringof            )        );    }     this(R range)    {        source = range;        if (!range.empty)        {            caches[0] = source.front;            static if (bidir)                caches[1] = source.back;        }        else        {            // needed, because the compiler cannot deduce, that 'caches' is initialized            // see https://issues.dlang.org/show_bug.cgi?id=15891            caches[0] = UE.init;            static if (bidir)                caches[1] = UE.init;        }    }     static if (isInfinite!R)        enum empty = false;    else        bool empty() @property        {            return source.empty;        }     mixin ImplementLength!source;     E front() @property    {        version (assert) if (empty) throw new RangeError();        return caches[0];    }    static if (bidir) E back() @property    {        version (assert) if (empty) throw new RangeError();        return caches[1];    }     void popFront()    {        version (assert) if (empty) throw new RangeError();        source.popFront();        if (!source.empty)            caches[0] = source.front;        else        {            // see https://issues.dlang.org/show_bug.cgi?id=15891            caches[0] = UE.init;            static if (bidir)                caches[1] = UE.init;        }    }    static if (bidir) void popBack()    {        version (assert) if (empty) throw new RangeError();        source.popBack();        if (!source.empty)            caches[1] = source.back;        else        {            // see https://issues.dlang.org/show_bug.cgi?id=15891            caches[0] = UE.init;            caches[1] = UE.init;        }    }     static if (isForwardRange!R)    {        private this(R source, ref CacheTypes caches)        {            this.source = source;            this.caches = caches;        }        typeof(this) save() @property        {            return typeof(this)(source.save, caches);        }    }     static if (hasSlicing!R)    {        enum hasEndSlicing = is(typeof(source[size_t.max .. $]));         static if (hasEndSlicing)        {            private static struct DollarToken{}            enum opDollar = DollarToken.init;             auto opSlice(size_t low, DollarToken)            {                return typeof(this)(source[low .. $]);            }        }         static if (!isInfinite!R)        {            typeof(this) opSlice(size_t low, size_t high)            {                return typeof(this)(source[low .. high]);            }        }        else static if (hasEndSlicing)        {            auto opSlice(size_t low, size_t high)            in            {                assert(low <= high, "Bounds error when slicing cache.");            }            do            {                import std.range : takeExactly;                return this[low .. $].takeExactly(high - low);            }        }    }} /** * Similar to `cache`, but lazily evaluates the elements. Unlike `cache`, * this function does not eagerly evaluate the front of the range until * it's explicitly requested. * * This can be useful when evaluation of range elements has side effects that * should be delayed until actually needed. * * See_Also: cache * * Params: *    range = an $(REF_ALTTEXT input range, isInputRange, std,range,primitives) * * Returns: *    An $(REF_ALTTEXT input range, isInputRange, std,range,primitives) with the lazily cached values of range */ auto lazyCache(Range)(Range range)if (isInputRange!Range){    return LazyCache!(Range, isBidirectionalRange!Range)(range);} ///@safe unittest{    import std.algorithm.comparison : equal;    import std.range, std.stdio;    import std.typecons : tuple;     ulong counter = 0;    double fun(int x)    {        ++counter;        // http://en.wikipedia.org/wiki/Quartic_function        return ( (x + 4.0) * (x + 1.0) * (x - 1.0) * (x - 3.0) ) / 14.0 + 0.5;    }    // With lazyCache, front won't be evaluated until requested    counter = 0;    auto result = iota(-4, 5).map!(a => tuple(a, fun(a)))()                            .lazyCache();    // At this point, no elements have been evaluated yet    assert(counter == 0);    // Now access the first element    auto firstElement = result.front;    // Only now the first element is evaluated    assert(counter == 1);    // Process the result lazily    auto filtered = result.filter!(a => a[1] < 0)()                         .map!(a => a[0])();    // Values are calculated as we iterate    assert(equal(filtered, [-3, -2, 2]));    // Only elements we actually accessed were evaluated    assert(counter == iota(-4, 5).length);} private struct LazyCache(R, bool bidir){    import core.exception : RangeError;     private    {        import std.algorithm.internal : algoFormat;        import std.meta : AliasSeq;         alias E  = ElementType!R;        alias UE = Unqual!E;         R source;         static if (bidir) alias CacheTypes = AliasSeq!(UE, UE);        else              alias CacheTypes = AliasSeq!UE;        CacheTypes caches;        // Flags to track if front/back have been cached        bool frontCached = false;        static if (bidir) bool backCached = false;

Lines 1–500 of 8315. Load more