libphobos/src/std/range/package.d

// Written in the D programming language.

/**
This module defines the notion of a range. Ranges generalize the concept of
arrays, lists, or anything that involves sequential access. This abstraction
enables the same set of algorithms (see $(MREF std, algorithm)) to be used
with a vast variety of different concrete types. For example,
a linear search algorithm such as $(REF find, std, algorithm, searching)
works not just for arrays, but for linked-lists, input files,
incoming network data, etc.

Guides:

There are many articles available that can bolster understanding ranges:

$(UL
    $(LI Ali Çehreli's $(HTTP ddili.org/ders/d.en/ranges.html, tutorial on _ranges)
        for the basics of working with and creating range-based code.)
    $(LI Jonathan M. Davis $(LINK2 http://dconf.org/2015/talks/davis.html, $(I Introduction to Ranges))
        talk at DConf 2015 a vivid introduction from its core constructs to practical advice.)
    $(LI The DLang Tour's $(LINK2 http://tour.dlang.org/tour/en/basics/ranges, chapter on ranges)
        for an interactive introduction.)
    $(LI H. S. Teoh's $(LINK2 http://wiki.dlang.org/Component_programming_with_ranges, tutorial on
        component programming with ranges) for a real-world showcase of the influence
        of _range-based programming on complex algorithms.)
    $(LI Andrei Alexandrescu's article
        $(LINK2 http://www.informit.com/articles/printerfriendly.aspx?p=1407357$(AMP)rll=1,
        $(I On Iteration)) for conceptual aspect of ranges and the motivation
    )
)

Submodules:

This module has two submodules:

The $(MREF std, _range, primitives) submodule
provides basic _range functionality. It defines several templates for testing
whether a given object is a _range, what kind of _range it is, and provides
some common _range operations.

The $(MREF std, _range, interfaces) submodule
provides object-based interfaces for working with ranges via runtime
polymorphism.

The remainder of this module provides a rich set of _range creation and
composition templates that let you construct new ranges out of existing ranges:


$(SCRIPT inhibitQuickIndex = 1;)
$(BOOKTABLE ,
    $(TR $(TD $(LREF chain))
        $(TD Concatenates several ranges into a single _range.
    ))
    $(TR $(TD $(LREF choose))
        $(TD Chooses one of two ranges at runtime based on a boolean condition.
    ))
    $(TR $(TD $(LREF chooseAmong))
        $(TD Chooses one of several ranges at runtime based on an index.
    ))
    $(TR $(TD $(LREF chunks))
        $(TD Creates a _range that returns fixed-size chunks of the original
        _range.
    ))
    $(TR $(TD $(LREF cycle))
        $(TD Creates an infinite _range that repeats the given forward _range
        indefinitely. Good for implementing circular buffers.
    ))
    $(TR $(TD $(LREF drop))
        $(TD Creates the _range that results from discarding the first $(I n)
        elements from the given _range.
    ))
    $(TR $(TD $(LREF dropBack))
        $(TD Creates the _range that results from discarding the last $(I n)
        elements from the given _range.
    ))
    $(TR $(TD $(LREF dropExactly))
        $(TD Creates the _range that results from discarding exactly $(I n)
        of the first elements from the given _range.
    ))
    $(TR $(TD $(LREF dropBackExactly))
        $(TD Creates the _range that results from discarding exactly $(I n)
        of the last elements from the given _range.
    ))
    $(TR $(TD $(LREF dropOne))
        $(TD Creates the _range that results from discarding
        the first element from the given _range.
    ))
    $(TR $(TD $(D $(LREF dropBackOne)))
        $(TD Creates the _range that results from discarding
        the last element from the given _range.
    ))
    $(TR $(TD $(LREF enumerate))
        $(TD Iterates a _range with an attached index variable.
    ))
    $(TR $(TD $(LREF evenChunks))
        $(TD Creates a _range that returns a number of chunks of
        approximately equal length from the original _range.
    ))
    $(TR $(TD $(LREF frontTransversal))
        $(TD Creates a _range that iterates over the first elements of the
        given ranges.
    ))
    $(TR $(TD $(LREF generate))
        $(TD Creates a _range by successive calls to a given function. This
        allows to create ranges as a single delegate.
    ))
    $(TR $(TD $(LREF indexed))
        $(TD Creates a _range that offers a view of a given _range as though
        its elements were reordered according to a given _range of indices.
    ))
    $(TR $(TD $(LREF iota))
        $(TD Creates a _range consisting of numbers between a starting point
        and ending point, spaced apart by a given interval.
    ))
    $(TR $(TD $(LREF lockstep))
        $(TD Iterates $(I n) _ranges in lockstep, for use in a $(D foreach)
        loop. Similar to $(D zip), except that $(D lockstep) is designed
        especially for $(D foreach) loops.
    ))
    $(TR $(TD $(LREF NullSink))
        $(TD An output _range that discards the data it receives.
    ))
    $(TR $(TD $(LREF only))
        $(TD Creates a _range that iterates over the given arguments.
    ))
    $(TR $(TD $(LREF padLeft))
        $(TD Pads a _range to a specified length by adding a given element to
        the front of the _range. Is lazy if the _range has a known length.
    ))
    $(TR $(TD $(LREF padRight))
        $(TD Lazily pads a _range to a specified length by adding a given element to
        the back of the _range.
    ))
    $(TR $(TD $(LREF radial))
        $(TD Given a random-access _range and a starting point, creates a
        _range that alternately returns the next left and next right element to
        the starting point.
    ))
    $(TR $(TD $(LREF recurrence))
        $(TD Creates a forward _range whose values are defined by a
        mathematical recurrence relation.
    ))
    $(TR $(TD $(LREF refRange))
        $(TD Pass a _range by reference. Both the original _range and the RefRange
        will always have the exact same elements.
        Any operation done on one will affect the other.
    ))
    $(TR $(TD $(LREF repeat))
        $(TD Creates a _range that consists of a single element repeated $(I n)
        times, or an infinite _range repeating that element indefinitely.
    ))
    $(TR $(TD $(LREF retro))
        $(TD Iterates a bidirectional _range backwards.
    ))
    $(TR $(TD $(LREF roundRobin))
        $(TD Given $(I n) ranges, creates a new _range that return the $(I n)
        first elements of each _range, in turn, then the second element of each
        _range, and so on, in a round-robin fashion.
    ))
    $(TR $(TD $(LREF sequence))
        $(TD Similar to $(D recurrence), except that a random-access _range is
        created.
    ))
    $(COMMENT Explicitly undocumented to delay the release until 2.076
    $(TR $(TD $(D $(LREF slide)))
        $(TD Creates a _range that returns a fixed-size sliding window
        over the original _range. Unlike chunks,
        it advances a configurable number of items at a time,
        not one chunk at a time.
    ))
    )
    $(TR $(TD $(LREF stride))
        $(TD Iterates a _range with stride $(I n).
    ))
    $(TR $(TD $(LREF tail))
        $(TD Return a _range advanced to within $(D n) elements of the end of
        the given _range.
    ))
    $(TR $(TD $(LREF take))
        $(TD Creates a sub-_range consisting of only up to the first $(I n)
        elements of the given _range.
    ))
    $(TR $(TD $(LREF takeExactly))
        $(TD Like $(D take), but assumes the given _range actually has $(I n)
        elements, and therefore also defines the $(D length) property.
    ))
    $(TR $(TD $(LREF takeNone))
        $(TD Creates a random-access _range consisting of zero elements of the
        given _range.
    ))
    $(TR $(TD $(LREF takeOne))
        $(TD Creates a random-access _range consisting of exactly the first
        element of the given _range.
    ))
    $(TR $(TD $(LREF tee))
        $(TD Creates a _range that wraps a given _range, forwarding along
        its elements while also calling a provided function with each element.
    ))
    $(TR $(TD $(LREF transposed))
        $(TD Transposes a _range of ranges.
    ))
    $(TR $(TD $(LREF transversal))
        $(TD Creates a _range that iterates over the $(I n)'th elements of the
        given random-access ranges.
    ))
    $(TR $(TD $(LREF zip))
        $(TD Given $(I n) _ranges, creates a _range that successively returns a
        tuple of all the first elements, a tuple of all the second elements,
        etc.
    ))
)

Sortedness:

Ranges whose elements are sorted afford better efficiency with certain
operations. For this, the $(LREF assumeSorted) function can be used to
construct a $(LREF SortedRange) from a pre-sorted _range. The $(REF
sort, std, algorithm, sorting) function also conveniently
returns a $(LREF SortedRange). $(LREF SortedRange) objects provide some additional
_range operations that take advantage of the fact that the _range is sorted.

Source: $(PHOBOSSRC std/_range/_package.d)

License: $(HTTP boost.org/LICENSE_1_0.txt, Boost License 1.0).

Authors: $(HTTP erdani.com, Andrei Alexandrescu), David Simcha, Jonathan M Davis,
and Jack Stouffer. Credit for some of the ideas in building this module goes
to $(HTTP fantascienza.net/leonardo/so/, Leonardo Maffi).
 */
module std.range;

public import std.array;
public import std.range.interfaces;
public import std.range.primitives;
public import std.typecons : Flag, Yes, No;

import std.meta; // allSatisfy, staticMap
import std.traits; // CommonType, isCallable, isFloatingPoint, isIntegral,
    // isPointer, isSomeFunction, isStaticArray, Unqual


/**
Iterates a bidirectional range backwards. The original range can be
accessed by using the $(D source) property. Applying retro twice to
the same range yields the original range.

Params:
    r = the bidirectional range to iterate backwards

Returns:
    A bidirectional range with length if `r` also provides a length. Or,
    if `r` is a random access range, then the return value will be random
    access as well.
See_Also:
    $(REF reverse, std,algorithm,mutation) for mutating the source range directly.
 */
auto retro(Range)(Range r)
if (isBidirectionalRange!(Unqual!Range))
{
    // Check for retro(retro(r)) and just return r in that case
    static if (is(typeof(retro(r.source)) == Range))
    {
        return r.source;
    }
    else
    {
        static struct Result()
        {
            private alias R = Unqual!Range;

            // User code can get and set source, too
            R source;

            static if (hasLength!R)
            {
                size_t retroIndex(size_t n)
                {
                    return source.length - n - 1;
                }
            }

        public:
            alias Source = R;

            @property bool empty() { return source.empty; }
            @property auto save()
            {
                return Result(source.save);
            }
            @property auto ref front() { return source.back; }
            void popFront() { source.popBack(); }
            @property auto ref back() { return source.front; }
            void popBack() { source.popFront(); }

            static if (is(typeof(source.moveBack())))
            {
                ElementType!R moveFront()
                {
                    return source.moveBack();
                }
            }

            static if (is(typeof(source.moveFront())))
            {
                ElementType!R moveBack()
                {
                    return source.moveFront();
                }
            }

            static if (hasAssignableElements!R)
            {
                @property void front(ElementType!R val)
                {
                    source.back = val;
                }

                @property void back(ElementType!R val)
                {
                    source.front = val;
                }
            }

            static if (isRandomAccessRange!(R) && hasLength!(R))
            {
                auto ref opIndex(size_t n) { return source[retroIndex(n)]; }

                static if (hasAssignableElements!R)
                {
                    void opIndexAssign(ElementType!R val, size_t n)
                    {
                        source[retroIndex(n)] = val;
                    }
                }

                static if (is(typeof(source.moveAt(0))))
                {
                    ElementType!R moveAt(size_t index)
                    {
                        return source.moveAt(retroIndex(index));
                    }
                }

                static if (hasSlicing!R)
                    typeof(this) opSlice(size_t a, size_t b)
                    {
                        return typeof(this)(source[source.length - b .. source.length - a]);
                    }
            }

            static if (hasLength!R)
            {
                @property auto length()
                {
                    return source.length;
                }

                alias opDollar = length;
            }
        }

        return Result!()(r);
    }
}


///
pure @safe nothrow @nogc unittest
{
    import std.algorithm.comparison : equal;
    int[5] a = [ 1, 2, 3, 4, 5 ];
    int[5] b = [ 5, 4, 3, 2, 1 ];
    assert(equal(retro(a[]), b[]));
    assert(retro(a[]).source is a[]);
    assert(retro(retro(a[])) is a[]);
}

pure @safe nothrow unittest
{
    import std.algorithm.comparison : equal;
    static assert(isBidirectionalRange!(typeof(retro("hello"))));
    int[] a;
    static assert(is(typeof(a) == typeof(retro(retro(a)))));
    assert(retro(retro(a)) is a);
    static assert(isRandomAccessRange!(typeof(retro([1, 2, 3]))));
    void test(int[] input, int[] witness)
    {
        auto r = retro(input);
        assert(r.front == witness.front);
        assert(r.back == witness.back);
        assert(equal(r, witness));
    }
    test([ 1 ], [ 1 ]);
    test([ 1, 2 ], [ 2, 1 ]);
    test([ 1, 2, 3 ], [ 3, 2, 1 ]);
    test([ 1, 2, 3, 4 ], [ 4, 3, 2, 1 ]);
    test([ 1, 2, 3, 4, 5 ], [ 5, 4, 3, 2, 1 ]);
    test([ 1, 2, 3, 4, 5, 6 ], [ 6, 5, 4, 3, 2, 1 ]);

    immutable foo = [1,2,3].idup;
    auto r = retro(foo);
    assert(equal(r, [3, 2, 1]));
}

pure @safe nothrow unittest
{
    import std.internal.test.dummyrange : AllDummyRanges, propagatesRangeType,
        ReturnBy;

    foreach (DummyType; AllDummyRanges)
    {
        static if (!isBidirectionalRange!DummyType)
        {
            static assert(!__traits(compiles, Retro!DummyType));
        }
        else
        {
            DummyType dummyRange;
            dummyRange.reinit();

            auto myRetro = retro(dummyRange);
            static assert(propagatesRangeType!(typeof(myRetro), DummyType));
            assert(myRetro.front == 10);
            assert(myRetro.back == 1);
            assert(myRetro.moveFront() == 10);
            assert(myRetro.moveBack() == 1);

            static if (isRandomAccessRange!DummyType && hasLength!DummyType)
            {
                assert(myRetro[0] == myRetro.front);
                assert(myRetro.moveAt(2) == 8);

                static if (DummyType.r == ReturnBy.Reference)
                {
                    {
                        myRetro[9]++;
                        scope(exit) myRetro[9]--;
                        assert(dummyRange[0] == 2);
                        myRetro.front++;
                        scope(exit) myRetro.front--;
                        assert(myRetro.front == 11);
                        myRetro.back++;
                        scope(exit) myRetro.back--;
                        assert(myRetro.back == 3);
                    }

                    {
                        myRetro.front = 0xFF;
                        scope(exit) myRetro.front = 10;
                        assert(dummyRange.back == 0xFF);

                        myRetro.back = 0xBB;
                        scope(exit) myRetro.back = 1;
                        assert(dummyRange.front == 0xBB);

                        myRetro[1] = 11;
                        scope(exit) myRetro[1] = 8;
                        assert(dummyRange[8] == 11);
                    }
                }
            }
        }
    }
}

pure @safe nothrow @nogc unittest
{
    import std.algorithm.comparison : equal;
    auto LL = iota(1L, 4L);
    auto r = retro(LL);
    long[3] excepted = [3, 2, 1];
    assert(equal(r, excepted[]));
}

// Issue 12662
pure @safe nothrow @nogc unittest
{
    int[3] src = [1,2,3];
    int[] data = src[];
    foreach_reverse (x; data) {}
    foreach (x; data.retro) {}
}


/**
Iterates range $(D r) with stride $(D n). If the range is a
random-access range, moves by indexing into the range; otherwise,
moves by successive calls to $(D popFront). Applying stride twice to
the same range results in a stride with a step that is the
product of the two applications. It is an error for $(D n) to be 0.

Params:
    r = the input range to stride over
    n = the number of elements to skip over

Returns:
    At minimum, an input range. The resulting range will adopt the
    range primitives of the underlying range as long as
    $(REF hasLength, std,range,primitives) is `true`.
 */
auto stride(Range)(Range r, size_t n)
if (isInputRange!(Unqual!Range))
in
{
    assert(n != 0, "stride cannot have step zero.");
}
body
{
    import std.algorithm.comparison : min;

    static if (is(typeof(stride(r.source, n)) == Range))
    {
        // stride(stride(r, n1), n2) is stride(r, n1 * n2)
        return stride(r.source, r._n * n);
    }
    else
    {
        static struct Result
        {
            private alias R = Unqual!Range;
            public R source;
            private size_t _n;

            // Chop off the slack elements at the end
            static if (hasLength!R &&
                    (isRandomAccessRange!R && hasSlicing!R
                            || isBidirectionalRange!R))
                private void eliminateSlackElements()
                {
                    auto slack = source.length % _n;

                    if (slack)
                    {
                        slack--;
                    }
                    else if (!source.empty)
                    {
                        slack = min(_n, source.length) - 1;
                    }
                    else
                    {
                        slack = 0;
                    }
                    if (!slack) return;
                    static if (isRandomAccessRange!R && hasLength!R && hasSlicing!R)
                    {
                        source = source[0 .. source.length - slack];
                    }
                    else static if (isBidirectionalRange!R)
                    {
                        foreach (i; 0 .. slack)
                        {
                            source.popBack();
                        }
                    }
                }

            static if (isForwardRange!R)
            {
                @property auto save()
                {
                    return Result(source.save, _n);
                }
            }

            static if (isInfinite!R)
            {
                enum bool empty = false;
            }
            else
            {
                @property bool empty()
                {
                    return source.empty;
                }
            }

            @property auto ref front()
            {
                return source.front;
            }

            static if (is(typeof(.moveFront(source))))
            {
                ElementType!R moveFront()
                {
                    return source.moveFront();
                }
            }

            static if (hasAssignableElements!R)
            {
                @property void front(ElementType!R val)
                {
                    source.front = val;
                }
            }

            void popFront()
            {
                source.popFrontN(_n);
            }

            static if (isBidirectionalRange!R && hasLength!R)
            {
                void popBack()
                {
                    popBackN(source, _n);
                }

                @property auto ref back()
                {
                    eliminateSlackElements();
                    return source.back;
                }

                static if (is(typeof(.moveBack(source))))
                {
                    ElementType!R moveBack()
                    {
                        eliminateSlackElements();
                        return source.moveBack();
                    }
                }

                static if (hasAssignableElements!R)
                {
                    @property void back(ElementType!R val)
                    {
                        eliminateSlackElements();
                        source.back = val;
                    }
                }
            }

            static if (isRandomAccessRange!R && hasLength!R)
            {
                auto ref opIndex(size_t n)
                {
                    return source[_n * n];
                }

                /**
                   Forwards to $(D moveAt(source, n)).
                */
                static if (is(typeof(source.moveAt(0))))
                {
                    ElementType!R moveAt(size_t n)
                    {
                        return source.moveAt(_n * n);
                    }
                }

                static if (hasAssignableElements!R)
                {
                    void opIndexAssign(ElementType!R val, size_t n)
                    {
                        source[_n * n] = val;
                    }
                }
            }

            static if (hasSlicing!R && hasLength!R)
                typeof(this) opSlice(size_t lower, size_t upper)
                {
                    assert(upper >= lower && upper <= length);
                    immutable translatedUpper = (upper == 0) ? 0 :
                        (upper * _n - (_n - 1));
                    immutable translatedLower = min(lower * _n, translatedUpper);

                    assert(translatedLower <= translatedUpper);

                    return typeof(this)(source[translatedLower .. translatedUpper], _n);
                }

            static if (hasLength!R)
            {
                @property auto length()
                {
                    return (source.length + _n - 1) / _n;
                }

                alias opDollar = length;
            }
        }
        return Result(r, n);
    }
}

///
pure @safe nothrow unittest
{
    import std.algorithm.comparison : equal;

    int[] a = [ 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11 ];
    assert(equal(stride(a, 3), [ 1, 4, 7, 10 ][]));
    assert(stride(stride(a, 2), 3) == stride(a, 6));
}

pure @safe nothrow @nogc unittest
{
    import std.algorithm.comparison : equal;

    int[4] testArr = [1,2,3,4];
    static immutable result = [1, 3];
    assert(equal(testArr[].stride(2), result));
}

debug pure nothrow @system unittest
{//check the contract
    int[4] testArr = [1,2,3,4];
    bool passed = false;
    scope (success) assert(passed);
    import core.exception : AssertError;
    //std.exception.assertThrown won't do because it can't infer nothrow
    // @@@BUG@@@ 12647
    try
    {
        auto unused = testArr[].stride(0);
    }
    catch (AssertError unused)
    {
        passed = true;
    }
}

pure @safe nothrow unittest
{
    import std.algorithm.comparison : equal;
    import std.internal.test.dummyrange : AllDummyRanges, propagatesRangeType,
        ReturnBy;

    static assert(isRandomAccessRange!(typeof(stride([1, 2, 3], 2))));
    void test(size_t n, int[] input, int[] witness)
    {
        assert(equal(stride(input, n), witness));
    }
    test(1, [], []);
    int[] arr = [ 1, 2, 3, 4, 5, 6, 7, 8, 9, 10 ];
    assert(stride(stride(arr, 2), 3) is stride(arr, 6));
    test(1, arr, arr);
    test(2, arr, [1, 3, 5, 7, 9]);
    test(3, arr, [1, 4, 7, 10]);
    test(4, arr, [1, 5, 9]);

    // Test slicing.
    auto s1 = stride(arr, 1);
    assert(equal(s1[1 .. 4], [2, 3, 4]));
    assert(s1[1 .. 4].length == 3);
    assert(equal(s1[1 .. 5], [2, 3, 4, 5]));
    assert(s1[1 .. 5].length == 4);
    assert(s1[0 .. 0].empty);
    assert(s1[3 .. 3].empty);
    // assert(s1[$ .. $].empty);
    assert(s1[s1.opDollar .. s1.opDollar].empty);

    auto s2 = stride(arr, 2);
    assert(equal(s2[0 .. 2], [1,3]));
    assert(s2[0 .. 2].length == 2);
    assert(equal(s2[1 .. 5], [3, 5, 7, 9]));
    assert(s2[1 .. 5].length == 4);
    assert(s2[0 .. 0].empty);
    assert(s2[3 .. 3].empty);
    // assert(s2[$ .. $].empty);
    assert(s2[s2.opDollar .. s2.opDollar].empty);

    // Test fix for Bug 5035
    auto m = [1, 2, 3, 4, 1, 2, 3, 4, 1, 2, 3, 4]; // 3 rows, 4 columns
    auto col = stride(m, 4);
    assert(equal(col, [1, 1, 1]));
    assert(equal(retro(col), [1, 1, 1]));

    immutable int[] immi = [ 1, 2, 3 ];
    static assert(isRandomAccessRange!(typeof(stride(immi, 1))));

    // Check for infiniteness propagation.
    static assert(isInfinite!(typeof(stride(repeat(1), 3))));

    foreach (DummyType; AllDummyRanges)
    {
        DummyType dummyRange;
        dummyRange.reinit();

        auto myStride = stride(dummyRange, 4);

        // Should fail if no length and bidirectional b/c there's no way
        // to know how much slack we have.
        static if (hasLength!DummyType || !isBidirectionalRange!DummyType)
        {
            static assert(propagatesRangeType!(typeof(myStride), DummyType));
        }
        assert(myStride.front == 1);
        assert(myStride.moveFront() == 1);
        assert(equal(myStride, [1, 5, 9]));

        static if (hasLength!DummyType)
        {
            assert(myStride.length == 3);
        }

        static if (isBidirectionalRange!DummyType && hasLength!DummyType)
        {
            assert(myStride.back == 9);
            assert(myStride.moveBack() == 9);
        }

        static if (isRandomAccessRange!DummyType && hasLength!DummyType)
        {
            assert(myStride[0] == 1);
            assert(myStride[1] == 5);
            assert(myStride.moveAt(1) == 5);
            assert(myStride[2] == 9);

            static assert(hasSlicing!(typeof(myStride)));
        }

        static if (DummyType.r == ReturnBy.Reference)
        {
            // Make sure reference is propagated.

            {
                myStride.front++;
                scope(exit) myStride.front--;
                assert(dummyRange.front == 2);
            }
            {
                myStride.front = 4;
                scope(exit) myStride.front = 1;
                assert(dummyRange.front == 4);
            }

            static if (isBidirectionalRange!DummyType && hasLength!DummyType)
            {
                {
                    myStride.back++;
                    scope(exit) myStride.back--;
                    assert(myStride.back == 10);
                }
                {
                    myStride.back = 111;
                    scope(exit) myStride.back = 9;
                    assert(myStride.back == 111);
                }

                static if (isRandomAccessRange!DummyType)
                {
                    {
                        myStride[1]++;
                        scope(exit) myStride[1]--;
                        assert(dummyRange[4] == 6);
                    }
                    {
                        myStride[1] = 55;
                        scope(exit) myStride[1] = 5;
                        assert(dummyRange[4] == 55);
                    }
                }
            }
        }
    }
}

pure @safe nothrow unittest
{
    import std.algorithm.comparison : equal;

    auto LL = iota(1L, 10L);
    auto s = stride(LL, 3);
    assert(equal(s, [1L, 4L, 7L]));
}

/**
Spans multiple ranges in sequence. The function $(D chain) takes any
number of ranges and returns a $(D Chain!(R1, R2,...)) object. The
ranges may be different, but they must have the same element type. The
result is a range that offers the $(D front), $(D popFront), and $(D
empty) primitives. If all input ranges offer random access and $(D
length), $(D Chain) offers them as well.

If only one range is offered to $(D Chain) or $(D chain), the $(D
Chain) type exits the picture by aliasing itself directly to that
range's type.

Params:
    rs = the input ranges to chain together

Returns:
    An input range at minimum. If all of the ranges in `rs` provide
    a range primitive, the returned range will also provide that range
    primitive.

See_Also: $(LREF only) to chain values to a range
 */
auto chain(Ranges...)(Ranges rs)
if (Ranges.length > 0 &&
    allSatisfy!(isInputRange, staticMap!(Unqual, Ranges)) &&
    !is(CommonType!(staticMap!(ElementType, staticMap!(Unqual, Ranges))) == void))
{
    static if (Ranges.length == 1)
    {
        return rs[0];
    }
    else
    {
        static struct Result
        {
        private:
            alias R = staticMap!(Unqual, Ranges);
            alias RvalueElementType = CommonType!(staticMap!(.ElementType, R));
            private template sameET(A)
            {
                enum sameET = is(.ElementType!A == RvalueElementType);
            }

            enum bool allSameType = allSatisfy!(sameET, R);

            // This doesn't work yet
            static if (allSameType)
            {
                alias ElementType = ref RvalueElementType;
            }
            else
            {
                alias ElementType = RvalueElementType;
            }
            static if (allSameType && allSatisfy!(hasLvalueElements, R))
            {
                static ref RvalueElementType fixRef(ref RvalueElementType val)
                {
                    return val;
                }
            }
            else
            {
                static RvalueElementType fixRef(RvalueElementType val)
                {
                    return val;
                }
            }

            // This is the entire state
            R source;
            // TODO: use a vtable (or more) instead of linear iteration

        public:
            this(R input)
            {
                foreach (i, v; input)
                {
                    source[i] = v;
                }
            }

            import std.meta : anySatisfy;

            static if (anySatisfy!(isInfinite, R))
            {
                // Propagate infiniteness.
                enum bool empty = false;
            }
            else
            {
                @property bool empty()
                {
                    foreach (i, Unused; R)
                    {
                        if (!source[i].empty) return false;
                    }
                    return true;
                }
            }

            static if (allSatisfy!(isForwardRange, R))
                @property auto save()
                {
                    typeof(this) result = this;
                    foreach (i, Unused; R)
                    {
                        result.source[i] = result.source[i].save;
                    }
                    return result;
                }

            void popFront()
            {
                foreach (i, Unused; R)
                {
                    if (source[i].empty) continue;
                    source[i].popFront();
                    return;
                }
            }

            @property auto ref front()
            {
                foreach (i, Unused; R)
                {
                    if (source[i].empty) continue;
                    return fixRef(source[i].front);
                }
                assert(false);
            }

            static if (allSameType && allSatisfy!(hasAssignableElements, R))
            {
                // @@@BUG@@@
                //@property void front(T)(T v) if (is(T : RvalueElementType))

                @property void front(RvalueElementType v)
                {
                    foreach (i, Unused; R)
                    {
                        if (source[i].empty) continue;
                        source[i].front = v;
                        return;
                    }
                    assert(false);
                }
            }

            static if (allSatisfy!(hasMobileElements, R))
            {
                RvalueElementType moveFront()
                {
                    foreach (i, Unused; R)
                    {
                        if (source[i].empty) continue;
                        return source[i].moveFront();
                    }
                    assert(false);
                }
            }

            static if (allSatisfy!(isBidirectionalRange, R))
            {
                @property auto ref back()
                {
                    foreach_reverse (i, Unused; R)
                    {
                        if (source[i].empty) continue;
                        return fixRef(source[i].back);
                    }
                    assert(false);
                }

                void popBack()
                {
                    foreach_reverse (i, Unused; R)
                    {
                        if (source[i].empty) continue;
                        source[i].popBack();
                        return;
                    }
                }

                static if (allSatisfy!(hasMobileElements, R))
                {
                    RvalueElementType moveBack()
                    {
                        foreach_reverse (i, Unused; R)
                        {
                            if (source[i].empty) continue;
                            return source[i].moveBack();
                        }
                        assert(false);
                    }
                }

                static if (allSameType && allSatisfy!(hasAssignableElements, R))
                {
                    @property void back(RvalueElementType v)
                    {
                        foreach_reverse (i, Unused; R)
                        {
                            if (source[i].empty) continue;
                            source[i].back = v;
                            return;
                        }
                        assert(false);
                    }
                }
            }

            static if (allSatisfy!(hasLength, R))
            {
                @property size_t length()
                {
                    size_t result;
                    foreach (i, Unused; R)
                    {
                        result += source[i].length;
                    }
                    return result;
                }

                alias opDollar = length;
            }

            static if (allSatisfy!(isRandomAccessRange, R))
            {
                auto ref opIndex(size_t index)
                {
                    foreach (i, Range; R)
                    {
                        static if (isInfinite!(Range))
                        {
                            return source[i][index];
                        }
                        else
                        {
                            immutable length = source[i].length;
                            if (index < length) return fixRef(source[i][index]);
                            index -= length;
                        }
                    }
                    assert(false);
                }

                static if (allSatisfy!(hasMobileElements, R))
                {
                    RvalueElementType moveAt(size_t index)
                    {
                        foreach (i, Range; R)
                        {
                            static if (isInfinite!(Range))
                            {
                                return source[i].moveAt(index);
                            }
                            else
                            {
                                immutable length = source[i].length;
                                if (index < length) return source[i].moveAt(index);
                                index -= length;
                            }
                        }
                        assert(false);
                    }
                }

                static if (allSameType && allSatisfy!(hasAssignableElements, R))
                    void opIndexAssign(ElementType v, size_t index)
                    {
                        foreach (i, Range; R)
                        {
                            static if (isInfinite!(Range))
                            {
                                source[i][index] = v;
                            }
                            else
                            {
                                immutable length = source[i].length;
                                if (index < length)
                                {
                                    source[i][index] = v;
                                    return;
                                }
                                index -= length;
                            }
                        }
                        assert(false);
                    }
            }

            static if (allSatisfy!(hasLength, R) && allSatisfy!(hasSlicing, R))
                auto opSlice(size_t begin, size_t end)
                {
                    auto result = this;
                    foreach (i, Unused; R)
                    {
                        immutable len = result.source[i].length;
                        if (len < begin)
                        {
                            result.source[i] = result.source[i]
                                [len .. len];
                            begin -= len;
                        }
                        else
                        {
                            result.source[i] = result.source[i]
                                [begin .. len];
                            break;
                        }
                    }
                    auto cut = length;
                    cut = cut <= end ? 0 : cut - end;
                    foreach_reverse (i, Unused; R)
                    {
                        immutable len = result.source[i].length;
                        if (cut > len)
                        {
                            result.source[i] = result.source[i]
                                [0 .. 0];
                            cut -= len;
                        }
                        else
                        {
                            result.source[i] = result.source[i]
                                [0 .. len - cut];
                            break;
                        }
                    }
                    return result;
                }
        }
        return Result(rs);
    }
}

///
pure @safe nothrow unittest
{
    import std.algorithm.comparison : equal;

    int[] arr1 = [ 1, 2, 3, 4 ];
    int[] arr2 = [ 5, 6 ];
    int[] arr3 = [ 7 ];
    auto s = chain(arr1, arr2, arr3);
    assert(s.length == 7);
    assert(s[5] == 6);
    assert(equal(s, [1, 2, 3, 4, 5, 6, 7][]));
}

/**
 * Range primitives are carried over to the returned range if
 * all of the ranges provide them
 */
pure @safe nothrow unittest
{
    import std.algorithm.comparison : equal;
    import std.algorithm.sorting : sort;

    int[] arr1 = [5, 2, 8];
    int[] arr2 = [3, 7, 9];
    int[] arr3 = [1, 4, 6];

    // in-place sorting across all of the arrays
    auto s = arr1.chain(arr2, arr3).sort;

    assert(s.equal([1, 2, 3, 4, 5, 6, 7, 8, 9]));
    assert(arr1.equal([1, 2, 3]));
    assert(arr2.equal([4, 5, 6]));
    assert(arr3.equal([7, 8, 9]));
}

pure @safe nothrow unittest
{
    import std.algorithm.comparison : equal;
    import std.internal.test.dummyrange : AllDummyRanges, dummyLength,
                                          propagatesRangeType;

    {
        int[] arr1 = [ 1, 2, 3, 4 ];
        int[] arr2 = [ 5, 6 ];
        int[] arr3 = [ 7 ];
        int[] witness = [ 1, 2, 3, 4, 5, 6, 7 ];
        auto s1 = chain(arr1);
        static assert(isRandomAccessRange!(typeof(s1)));
        auto s2 = chain(arr1, arr2);
        static assert(isBidirectionalRange!(typeof(s2)));
        static assert(isRandomAccessRange!(typeof(s2)));
        s2.front = 1;
        auto s = chain(arr1, arr2, arr3);
        assert(s[5] == 6);
        assert(equal(s, witness));
        assert(s[5] == 6);
    }
    {
        int[] arr1 = [ 1, 2, 3, 4 ];
        int[] witness = [ 1, 2, 3, 4 ];
        assert(equal(chain(arr1), witness));
    }
    {
        uint[] foo = [1,2,3,4,5];
        uint[] bar = [1,2,3,4,5];
        auto c = chain(foo, bar);
        c[3] = 42;
        assert(c[3] == 42);
        assert(c.moveFront() == 1);
        assert(c.moveBack() == 5);
        assert(c.moveAt(4) == 5);
        assert(c.moveAt(5) == 1);
    }

    // Make sure bug 3311 is fixed.  ChainImpl should compile even if not all
    // elements are mutable.
    assert(equal(chain(iota(0, 3), iota(0, 3)), [0, 1, 2, 0, 1, 2]));

    // Test the case where infinite ranges are present.
    auto inf = chain([0,1,2][], cycle([4,5,6][]), [7,8,9][]); // infinite range
    assert(inf[0] == 0);
    assert(inf[3] == 4);
    assert(inf[6] == 4);
    assert(inf[7] == 5);
    static assert(isInfinite!(typeof(inf)));

    immutable int[] immi = [ 1, 2, 3 ];
    immutable float[] immf = [ 1, 2, 3 ];
    static assert(is(typeof(chain(immi, immf))));

    // Check that chain at least instantiates and compiles with every possible
    // pair of DummyRange types, in either order.

    foreach (DummyType1; AllDummyRanges)
    {
        DummyType1 dummy1;
        foreach (DummyType2; AllDummyRanges)
        {
            DummyType2 dummy2;
            auto myChain = chain(dummy1, dummy2);

            static assert(
                propagatesRangeType!(typeof(myChain), DummyType1, DummyType2)
            );

            assert(myChain.front == 1);
            foreach (i; 0 .. dummyLength)
            {
                myChain.popFront();
            }
            assert(myChain.front == 1);

            static if (isBidirectionalRange!DummyType1 &&
                      isBidirectionalRange!DummyType2) {
                assert(myChain.back == 10);
            }

            static if (isRandomAccessRange!DummyType1 &&
                      isRandomAccessRange!DummyType2) {
                assert(myChain[0] == 1);
            }

            static if (hasLvalueElements!DummyType1 && hasLvalueElements!DummyType2)
            {
                static assert(hasLvalueElements!(typeof(myChain)));
            }
            else
            {
                static assert(!hasLvalueElements!(typeof(myChain)));
            }
        }
    }
}

pure @safe nothrow @nogc unittest
{
    class Foo{}
    immutable(Foo)[] a;
    immutable(Foo)[] b;
    assert(chain(a, b).empty);
}

/**
Choose one of two ranges at runtime depending on a Boolean condition.

The ranges may be different, but they must have compatible element types (i.e.
$(D CommonType) must exist for the two element types). The result is a range
that offers the weakest capabilities of the two (e.g. $(D ForwardRange) if $(D
R1) is a random-access range and $(D R2) is a forward range).

Params:
    condition = which range to choose: $(D r1) if $(D true), $(D r2) otherwise
    r1 = the "true" range
    r2 = the "false" range

Returns:
    A range type dependent on $(D R1) and $(D R2).

Bugs:
    $(BUGZILLA 14660)
 */
auto choose(R1, R2)(bool condition, R1 r1, R2 r2)
if (isInputRange!(Unqual!R1) && isInputRange!(Unqual!R2) &&
    !is(CommonType!(ElementType!(Unqual!R1), ElementType!(Unqual!R2)) == void))
{
    static struct Result
    {
        import std.algorithm.comparison : max;
        import std.algorithm.internal : addressOf;
        import std.traits : hasElaborateCopyConstructor, hasElaborateDestructor;

        private union
        {
            void[max(R1.sizeof, R2.sizeof)] buffer = void;
            void* forAlignmentOnly = void;
        }
        private bool condition;
        private @property ref R1 r1()
        {
            assert(condition);
            return *cast(R1*) buffer.ptr;
        }
        private @property ref R2 r2()
        {
            assert(!condition);
            return *cast(R2*) buffer.ptr;
        }

        this(bool condition, R1 r1, R2 r2)
        {
            this.condition = condition;
            import std.conv : emplace;
            if (condition) emplace(addressOf(this.r1), r1);
            else emplace(addressOf(this.r2), r2);
        }

        // Carefully defined postblit to postblit the appropriate range
        static if (hasElaborateCopyConstructor!R1
            || hasElaborateCopyConstructor!R2)
        this(this)
        {
            if (condition)
            {
                static if (hasElaborateCopyConstructor!R1) r1.__postblit();
            }
            else
            {
                static if (hasElaborateCopyConstructor!R2) r2.__postblit();
            }
        }

        static if (hasElaborateDestructor!R1 || hasElaborateDestructor!R2)
        ~this()
        {
            if (condition) destroy(r1);
            else destroy(r2);
        }

        static if (isInfinite!R1 && isInfinite!R2)
            // Propagate infiniteness.
            enum bool empty = false;
        else
            @property bool empty()
            {
                return condition ? r1.empty : r2.empty;
            }

        @property auto ref front()
        {
            return condition ? r1.front : r2.front;
        }

        void popFront()
        {
            return condition ? r1.popFront : r2.popFront;
        }

        static if (isForwardRange!R1 && isForwardRange!R2)
            @property auto save()
            {
                auto result = this;
                if (condition) r1 = r1.save;
                else r2 = r2.save;
                return result;
            }

        @property void front(T)(T v)
        if (is(typeof({ r1.front = v; r2.front = v; })))
        {
            if (condition) r1.front = v; else r2.front = v;
        }

        static if (hasMobileElements!R1 && hasMobileElements!R2)
            auto moveFront()
            {
                return condition ? r1.moveFront : r2.moveFront;
            }

        static if (isBidirectionalRange!R1 && isBidirectionalRange!R2)
        {
            @property auto ref back()
            {
                return condition ? r1.back : r2.back;
            }

            void popBack()
            {
                return condition ? r1.popBack : r2.popBack;
            }

            static if (hasMobileElements!R1 && hasMobileElements!R2)
                auto moveBack()
                {
                    return condition ? r1.moveBack : r2.moveBack;
                }

            @property void back(T)(T v)
            if (is(typeof({ r1.back = v; r2.back = v; })))
            {
                if (condition) r1.back = v; else r2.back = v;
            }
        }

        static if (hasLength!R1 && hasLength!R2)
        {
            @property size_t length()
            {
                return condition ? r1.length : r2.length;
            }
            alias opDollar = length;
        }

        static if (isRandomAccessRange!R1 && isRandomAccessRange!R2)
        {
            auto ref opIndex(size_t index)
            {
                return condition ? r1[index] : r2[index];
            }

            static if (hasMobileElements!R1 && hasMobileElements!R2)
                auto moveAt(size_t index)
                {
                    return condition ? r1.moveAt(index) : r2.moveAt(index);
                }

            void opIndexAssign(T)(T v, size_t index)
            if (is(typeof({ r1[1] = v; r2[1] = v; })))
            {
                if (condition) r1[index] = v; else r2[index] = v;
            }
        }

        // BUG: this should work for infinite ranges, too
        static if (hasSlicing!R1 && hasSlicing!R2 &&
                !isInfinite!R2 && !isInfinite!R2)
            auto opSlice(size_t begin, size_t end)
            {
                auto result = this;
                if (condition) result.r1 = result.r1[begin .. end];
                else result.r2 = result.r2[begin .. end];
                return result;
            }
    }
    return Result(condition, r1, r2);
}

///
@system unittest
{
    import std.algorithm.comparison : equal;
    import std.algorithm.iteration : filter, map;

    auto data1 = [ 1, 2, 3, 4 ].filter!(a => a != 3);
    auto data2 = [ 5, 6, 7, 8 ].map!(a => a + 1);

    // choose() is primarily useful when you need to select one of two ranges
    // with different types at runtime.
    static assert(!is(typeof(data1) == typeof(data2)));

    auto chooseRange(bool pickFirst)
    {
        // The returned range is a common wrapper type that can be used for
        // returning or storing either range without running into a type error.
        return choose(pickFirst, data1, data2);

        // Simply returning the chosen range without using choose() does not
        // work, because map() and filter() return different types.
        //return pickFirst ? data1 : data2; // does not compile
    }

    auto result = chooseRange(true);
    assert(result.equal([ 1, 2, 4 ]));

    result = chooseRange(false);
    assert(result.equal([ 6, 7, 8, 9 ]));
}

/**
Choose one of multiple ranges at runtime.

The ranges may be different, but they must have compatible element types. The
result is a range that offers the weakest capabilities of all $(D Ranges).

Params:
    index = which range to choose, must be less than the number of ranges
    rs = two or more ranges

Returns:
    The indexed range. If rs consists of only one range, the return type is an
    alias of that range's type.
 */
auto chooseAmong(Ranges...)(size_t index, Ranges rs)
if (Ranges.length >= 2
        && allSatisfy!(isInputRange, staticMap!(Unqual, Ranges))
        && !is(CommonType!(staticMap!(ElementType, Ranges)) == void))
{
    static if (Ranges.length == 2)
        return choose(index == 0, rs[0], rs[1]);
    else
        return choose(index == 0, rs[0], chooseAmong(index - 1, rs[1 .. $]));
}

///
@system unittest
{
    import std.algorithm.comparison : equal;

    int[] arr1 = [ 1, 2, 3, 4 ];
    int[] arr2 = [ 5, 6 ];
    int[] arr3 = [ 7 ];

    {
        auto s = chooseAmong(0, arr1, arr2, arr3);
        auto t = s.save;
        assert(s.length == 4);
        assert(s[2] == 3);
        s.popFront();
        assert(equal(t, [1, 2, 3, 4][]));
    }
    {
        auto s = chooseAmong(1, arr1, arr2, arr3);
        assert(s.length == 2);
        s.front = 8;
        assert(equal(s, [8, 6][]));
    }
    {
        auto s = chooseAmong(1, arr1, arr2, arr3);
        assert(s.length == 2);
        s[1] = 9;
        assert(equal(s, [8, 9][]));
    }
    {
        auto s = chooseAmong(1, arr2, arr1, arr3)[1 .. 3];
        assert(s.length == 2);
        assert(equal(s, [2, 3][]));
    }
    {
        auto s = chooseAmong(0, arr1, arr2, arr3);
        assert(s.length == 4);
        assert(s.back == 4);
        s.popBack();
        s.back = 5;
        assert(equal(s, [1, 2, 5][]));
        s.back = 3;
        assert(equal(s, [1, 2, 3][]));
    }
    {
        uint[] foo = [1,2,3,4,5];
        uint[] bar = [6,7,8,9,10];
        auto c = chooseAmong(1,foo, bar);
        assert(c[3] == 9);
        c[3] = 42;
        assert(c[3] == 42);
        assert(c.moveFront() == 6);
        assert(c.moveBack() == 10);
        assert(c.moveAt(4) == 10);
    }
    {
        import std.range : cycle;
        auto s = chooseAmong(1, cycle(arr2), cycle(arr3));
        assert(isInfinite!(typeof(s)));
        assert(!s.empty);
        assert(s[100] == 7);
    }
}

@system unittest
{
    int[] a = [1, 2, 3];
    long[] b = [4, 5, 6];
    auto c = chooseAmong(0, a, b);
    c[0] = 42;
    assert(c[0] == 42);
}


/**
$(D roundRobin(r1, r2, r3)) yields $(D r1.front), then $(D r2.front),
then $(D r3.front), after which it pops off one element from each and
continues again from $(D r1). For example, if two ranges are involved,
it alternately yields elements off the two ranges. $(D roundRobin)
stops after it has consumed all ranges (skipping over the ones that
finish early).
 */
auto roundRobin(Rs...)(Rs rs)
if (Rs.length > 1 && allSatisfy!(isInputRange, staticMap!(Unqual, Rs)))
{
    struct Result
    {
        import std.conv : to;

        public Rs source;
        private size_t _current = size_t.max;

        @property bool empty()
        {
            foreach (i, Unused; Rs)
            {
                if (!source[i].empty) return false;
            }
            return true;
        }

        @property auto ref front()
        {
            final switch (_current)
            {
                foreach (i, R; Rs)
                {
                    case i:
                        assert(
                            !source[i].empty,
                            "Attempting to fetch the front of an empty roundRobin"
                        );
                        return source[i].front;
                }
            }
            assert(0);
        }

        void popFront()
        {
            final switch (_current)
            {
                foreach (i, R; Rs)
                {
                    case i:
                        source[i].popFront();
                        break;
                }
            }

            auto next = _current == (Rs.length - 1) ? 0 : (_current + 1);
            final switch (next)
            {
                foreach (i, R; Rs)
                {
                    case i:
                        if (!source[i].empty)
                        {
                            _current = i;
                            return;
                        }
                        if (i == _current)
                        {
                            _current = _current.max;
                            return;
                        }
                        goto case (i + 1) % Rs.length;
                }
            }
        }

        static if (allSatisfy!(isForwardRange, staticMap!(Unqual, Rs)))
            @property auto save()
            {
                Result result = this;
                foreach (i, Unused; Rs)
                {
                    result.source[i] = result.source[i].save;
                }
                return result;
            }

        static if (allSatisfy!(hasLength, Rs))
        {
            @property size_t length()
            {
                size_t result;
                foreach (i, R; Rs)
                {
                    result += source[i].length;
                }
                return result;
            }

            alias opDollar = length;
        }
    }

    return Result(rs, 0);
}

///
@safe unittest
{
    import std.algorithm.comparison : equal;

    int[] a = [ 1, 2, 3 ];
    int[] b = [ 10, 20, 30, 40 ];
    auto r = roundRobin(a, b);
    assert(equal(r, [ 1, 10, 2, 20, 3, 30, 40 ]));
}

/**
 * roundRobin can be used to create "interleave" functionality which inserts
 * an element between each element in a range.
 */
@safe unittest
{
    import std.algorithm.comparison : equal;

    auto interleave(R, E)(R range, E element)
    if ((isInputRange!R && hasLength!R) || isForwardRange!R)
    {
        static if (hasLength!R)
            immutable len = range.length;
        else
            immutable len = range.save.walkLength;

        return roundRobin(
            range,
            element.repeat(len - 1)
        );
    }

    assert(interleave([1, 2, 3], 0).equal([1, 0, 2, 0, 3]));
}

/**
Iterates a random-access range starting from a given point and
progressively extending left and right from that point. If no initial
point is given, iteration starts from the middle of the
range. Iteration spans the entire range.

When `startingIndex` is 0 the range will be fully iterated in order
and in reverse order when `r.length` is given.

Params:
    r = a random access range with length and slicing
    startingIndex = the index to begin iteration from

Returns:
    A forward range with length
 */
auto radial(Range, I)(Range r, I startingIndex)
if (isRandomAccessRange!(Unqual!Range) && hasLength!(Unqual!Range) && hasSlicing!(Unqual!Range) && isIntegral!I)
{
    if (startingIndex != r.length) ++startingIndex;
    return roundRobin(retro(r[0 .. startingIndex]), r[startingIndex .. r.length]);
}

/// Ditto
auto radial(R)(R r)
if (isRandomAccessRange!(Unqual!R) && hasLength!(Unqual!R) && hasSlicing!(Unqual!R))
{
    return .radial(r, (r.length - !r.empty) / 2);
}

///
@safe unittest
{
    import std.algorithm.comparison : equal;
    int[] a = [ 1, 2, 3, 4, 5 ];
    assert(equal(radial(a), [ 3, 4, 2, 5, 1 ]));
    a = [ 1, 2, 3, 4 ];
    assert(equal(radial(a), [ 2, 3, 1, 4 ]));

    // If the left end is reached first, the remaining elements on the right
    // are concatenated in order:
    a = [ 0, 1, 2, 3, 4, 5 ];
    assert(equal(radial(a, 1), [ 1, 2, 0, 3, 4, 5 ]));

    // If the right end is reached first, the remaining elements on the left
    // are concatenated in reverse order:
    assert(equal(radial(a, 4), [ 4, 5, 3, 2, 1, 0 ]));
}

@safe unittest
{
    import std.algorithm.comparison : equal;
    import std.conv : text;
    import std.exception : enforce;
    import std.internal.test.dummyrange : DummyRange, Length, RangeType, ReturnBy;

    void test(int[] input, int[] witness)
    {
        enforce(equal(radial(input), witness),
                text(radial(input), " vs. ", witness));
    }
    test([], []);
    test([ 1 ], [ 1 ]);
    test([ 1, 2 ], [ 1, 2 ]);
    test([ 1, 2, 3 ], [ 2, 3, 1 ]);
    test([ 1, 2, 3, 4 ], [ 2, 3, 1, 4 ]);
    test([ 1, 2, 3, 4, 5 ], [ 3, 4, 2, 5, 1 ]);
    test([ 1, 2, 3, 4, 5, 6 ], [ 3, 4, 2, 5, 1, 6 ]);

    int[] a = [ 1, 2, 3, 4, 5 ];
    assert(equal(radial(a, 1), [ 2, 3, 1, 4, 5 ]));
    assert(equal(radial(a, 0), [ 1, 2, 3, 4, 5 ])); // only right subrange
    assert(equal(radial(a, a.length), [ 5, 4, 3, 2, 1 ])); // only left subrange
    static assert(isForwardRange!(typeof(radial(a, 1))));

    auto r = radial([1,2,3,4,5]);
    for (auto rr = r.save; !rr.empty; rr.popFront())
    {
        assert(rr.front == moveFront(rr));
    }
    r.front = 5;
    assert(r.front == 5);

    // Test instantiation without lvalue elements.
    DummyRange!(ReturnBy.Value, Length.Yes, RangeType.Random) dummy;
    assert(equal(radial(dummy, 4), [5, 6, 4, 7, 3, 8, 2, 9, 1, 10]));

    // immutable int[] immi = [ 1, 2 ];
    // static assert(is(typeof(radial(immi))));
}

@safe unittest
{
    import std.algorithm.comparison : equal;

    auto LL = iota(1L, 6L);
    auto r = radial(LL);
    assert(equal(r, [3L, 4L, 2L, 5L, 1L]));
}

/**
Lazily takes only up to `n` elements of a range. This is
particularly useful when using with infinite ranges.

Unlike $(LREF takeExactly), `take` does not require that there
are `n` or more elements in `input`. As a consequence, length
information is not applied to the result unless `input` also has
length information.

Params:
    input = an input range to iterate over up to `n` times
    n = the number of elements to take

Returns:
    At minimum, an input range. If the range offers random access
    and `length`, `take` offers them as well.
 */
Take!R take(R)(R input, size_t n)
if (isInputRange!(Unqual!R))
{
    alias U = Unqual!R;
    static if (is(R T == Take!T))
    {
        import std.algorithm.comparison : min;
        return R(input.source, min(n, input._maxAvailable));
    }
    else static if (!isInfinite!U && hasSlicing!U)
    {
        import std.algorithm.comparison : min;
        return input[0 .. min(n, input.length)];
    }
    else
    {
        return Take!R(input, n);
    }
}

/// ditto
struct Take(Range)
if (isInputRange!(Unqual!Range) &&
    //take _cannot_ test hasSlicing on infinite ranges, because hasSlicing uses
    //take for slicing infinite ranges.
    !((!isInfinite!(Unqual!Range) && hasSlicing!(Unqual!Range)) || is(Range T == Take!T)))
{
    private alias R = Unqual!Range;

    /// User accessible in read and write
    public R source;

    private size_t _maxAvailable;

    alias Source = R;

    /// Range primitives
    @property bool empty()
    {
        return _maxAvailable == 0 || source.empty;
    }

    /// ditto
    @property auto ref front()
    {
        assert(!empty,
            "Attempting to fetch the front of an empty "
            ~ Take.stringof);
        return source.front;
    }

    /// ditto
    void popFront()
    {
        assert(!empty,
            "Attempting to popFront() past the end of a "
            ~ Take.stringof);
        source.popFront();
        --_maxAvailable;
    }

    static if (isForwardRange!R)
        /// ditto
        @property Take save()
        {
            return Take(source.save, _maxAvailable);
        }

    static if (hasAssignableElements!R)
        /// ditto
        @property void front(ElementType!R v)
        {
            assert(!empty,
                "Attempting to assign to the front of an empty "
                ~ Take.stringof);
            // This has to return auto instead of void because of Bug 4706.
            source.front = v;
        }

    static if (hasMobileElements!R)
    {
        /// ditto
        auto moveFront()
        {
            assert(!empty,
                "Attempting to move the front of an empty "
                ~ Take.stringof);
            return source.moveFront();
        }
    }

    static if (isInfinite!R)
    {
        /// ditto
        @property size_t length() const
        {
            return _maxAvailable;
        }

        /// ditto
        alias opDollar = length;

        //Note: Due to Take/hasSlicing circular dependency,
        //This needs to be a restrained template.
        /// ditto
        auto opSlice()(size_t i, size_t j)
        if (hasSlicing!R)
        {
            assert(i <= j, "Invalid slice bounds");
            assert(j <= length, "Attempting to slice past the end of a "
                ~ Take.stringof);
            return source[i .. j];
        }
    }
    else static if (hasLength!R)
    {
        /// ditto
        @property size_t length()
        {
            import std.algorithm.comparison : min;
            return min(_maxAvailable, source.length);
        }

        alias opDollar = length;
    }

    static if (isRandomAccessRange!R)
    {
        /// ditto
        void popBack()
        {
            assert(!empty,
                "Attempting to popBack() past the beginning of a "
                ~ Take.stringof);
            --_maxAvailable;
        }

        /// ditto
        @property auto ref back()
        {
            assert(!empty,
                "Attempting to fetch the back of an empty "
                ~ Take.stringof);
            return source[this.length - 1];
        }

        /// ditto
        auto ref opIndex(size_t index)
        {
            assert(index < length,
                "Attempting to index out of the bounds of a "
                ~ Take.stringof);
            return source[index];
        }

        static if (hasAssignableElements!R)
        {
            /// ditto
            @property void back(ElementType!R v)
            {
                // This has to return auto instead of void because of Bug 4706.
                assert(!empty,
                    "Attempting to assign to the back of an empty "
                    ~ Take.stringof);
                source[this.length - 1] = v;
            }

            /// ditto
            void opIndexAssign(ElementType!R v, size_t index)
            {
                assert(index < length,
                    "Attempting to index out of the bounds of a "
                    ~ Take.stringof);
                source[index] = v;
            }
        }

        static if (hasMobileElements!R)
        {
            /// ditto
            auto moveBack()
            {
                assert(!empty,
                    "Attempting to move the back of an empty "
                    ~ Take.stringof);
                return source.moveAt(this.length - 1);
            }

            /// ditto
            auto moveAt(size_t index)
            {
                assert(index < length,
                    "Attempting to index out of the bounds of a "
                    ~ Take.stringof);
                return source.moveAt(index);
            }
        }
    }

    /**
    Access to maximal length of the range.
    Note: the actual length of the range depends on the underlying range.
    If it has fewer elements, it will stop before maxLength is reached.
    */
    @property size_t maxLength() const
    {
        return _maxAvailable;
    }
}

/**
This template simply aliases itself to R and is useful for consistency in
generic code.
*/
template Take(R)
if (isInputRange!(Unqual!R) &&
    ((!isInfinite!(Unqual!R) && hasSlicing!(Unqual!R)) || is(R T == Take!T)))
{
    alias Take = R;
}

///
pure @safe nothrow unittest
{
    import std.algorithm.comparison : equal;

    int[] arr1 = [ 1, 2, 3, 4, 5, 6, 7, 8, 9, 10 ];
    auto s = take(arr1, 5);
    assert(s.length == 5);
    assert(s[4] == 5);
    assert(equal(s, [ 1, 2, 3, 4, 5 ][]));
}

/**
 * If the range runs out before `n` elements, `take` simply returns the entire
 * range (unlike $(LREF takeExactly), which will cause an assertion failure if
 * the range ends prematurely):
 */
pure @safe nothrow unittest
{
    import std.algorithm.comparison : equal;

    int[] arr2 = [ 1, 2, 3 ];
    auto t = take(arr2, 5);
    assert(t.length == 3);
    assert(equal(t, [ 1, 2, 3 ]));
}

pure @safe nothrow unittest
{
    import std.algorithm.comparison : equal;
    import std.internal.test.dummyrange : AllDummyRanges;

    int[] arr1 = [ 1, 2, 3, 4, 5, 6, 7, 8, 9, 10 ];
    auto s = take(arr1, 5);
    assert(s.length == 5);
    assert(s[4] == 5);
    assert(equal(s, [ 1, 2, 3, 4, 5 ][]));
    assert(equal(retro(s), [ 5, 4, 3, 2, 1 ][]));

    // Test fix for bug 4464.
    static assert(is(typeof(s) == Take!(int[])));
    static assert(is(typeof(s) == int[]));

    // Test using narrow strings.
    import std.exception : assumeWontThrow;

    auto myStr = "This is a string.";
    auto takeMyStr = take(myStr, 7);
    assert(assumeWontThrow(equal(takeMyStr, "This is")));
    // Test fix for bug 5052.
    auto takeMyStrAgain = take(takeMyStr, 4);
    assert(assumeWontThrow(equal(takeMyStrAgain, "This")));
    static assert(is (typeof(takeMyStrAgain) == typeof(takeMyStr)));
    takeMyStrAgain = take(takeMyStr, 10);
    assert(assumeWontThrow(equal(takeMyStrAgain, "This is")));

    foreach (DummyType; AllDummyRanges)
    {
        DummyType dummy;
        auto t = take(dummy, 5);
        alias T = typeof(t);

        static if (isRandomAccessRange!DummyType)
        {
            static assert(isRandomAccessRange!T);
            assert(t[4] == 5);

            assert(moveAt(t, 1) == t[1]);
            assert(t.back == moveBack(t));
        }
        else static if (isForwardRange!DummyType)
        {
            static assert(isForwardRange!T);
        }

        for (auto tt = t; !tt.empty; tt.popFront())
        {
            assert(tt.front == moveFront(tt));
        }

        // Bidirectional ranges can't be propagated properly if they don't
        // also have random access.

        assert(equal(t, [1,2,3,4,5]));

        //Test that take doesn't wrap the result of take.
        assert(take(t, 4) == take(dummy, 4));
    }

    immutable myRepeat = repeat(1);
    static assert(is(Take!(typeof(myRepeat))));
}

pure @safe nothrow @nogc unittest
{
    //check for correct slicing of Take on an infinite range
    import std.algorithm.comparison : equal;
    foreach (start; 0 .. 4)
        foreach (stop; start .. 4)
            assert(iota(4).cycle.take(4)[start .. stop]
                .equal(iota(start, stop)));
}

pure @safe nothrow @nogc unittest
{
    // Check that one can declare variables of all Take types,
    // and that they match the return type of the corresponding
    // take().  (See issue 4464.)
    int[] r1;
    Take!(int[]) t1;
    t1 = take(r1, 1);
    assert(t1.empty);

    string r2;
    Take!string t2;
    t2 = take(r2, 1);
    assert(t2.empty);

    Take!(Take!string) t3;
    t3 = take(t2, 1);
    assert(t3.empty);
}

pure @safe nothrow @nogc unittest
{
    alias R1 = typeof(repeat(1));
    alias R2 = typeof(cycle([1]));
    alias TR1 = Take!R1;
    alias TR2 = Take!R2;
    static assert(isBidirectionalRange!TR1);
    static assert(isBidirectionalRange!TR2);
}

pure @safe nothrow @nogc unittest //12731
{
    auto a = repeat(1);
    auto s = a[1 .. 5];
    s = s[1 .. 3];
    assert(s.length == 2);
    assert(s[0] == 1);
    assert(s[1] == 1);
}

pure @safe nothrow @nogc unittest //13151
{
    import std.algorithm.comparison : equal;

    auto r = take(repeat(1, 4), 3);
    assert(r.take(2).equal(repeat(1, 2)));
}


/**
Similar to $(LREF take), but assumes that $(D range) has at least $(D
n) elements. Consequently, the result of $(D takeExactly(range, n))
always defines the $(D length) property (and initializes it to $(D n))
even when $(D range) itself does not define $(D length).

The result of $(D takeExactly) is identical to that of $(LREF take) in
cases where the original range defines $(D length) or is infinite.

Unlike $(LREF take), however, it is illegal to pass a range with less than
$(D n) elements to $(D takeExactly); this will cause an assertion failure.
 */
auto takeExactly(R)(R range, size_t n)
if (isInputRange!R)
{
    static if (is(typeof(takeExactly(range._input, n)) == R))
    {
        assert(n <= range._n,
               "Attempted to take more than the length of the range with takeExactly.");
        // takeExactly(takeExactly(r, n1), n2) has the same type as
        // takeExactly(r, n1) and simply returns takeExactly(r, n2)
        range._n = n;
        return range;
    }
    //Also covers hasSlicing!R for finite ranges.
    else static if (hasLength!R)
    {
        assert(n <= range.length,
               "Attempted to take more than the length of the range with takeExactly.");
        return take(range, n);
    }
    else static if (isInfinite!R)
        return Take!R(range, n);
    else
    {
        static struct Result
        {
            R _input;
            private size_t _n;

            @property bool empty() const { return !_n; }
            @property auto ref front()
            {
                assert(_n > 0, "front() on an empty " ~ Result.stringof);
                return _input.front;
            }
            void popFront() { _input.popFront(); --_n; }
            @property size_t length() const { return _n; }
            alias opDollar = length;

            @property Take!R _takeExactly_Result_asTake()
            {
                return typeof(return)(_input, _n);
            }

            alias _takeExactly_Result_asTake this;

            static if (isForwardRange!R)
                @property auto save()
                {
                    return Result(_input.save, _n);
                }

            static if (hasMobileElements!R)
            {
                auto moveFront()
                {
                    assert(!empty,
                        "Attempting to move the front of an empty "
                        ~ typeof(this).stringof);
                    return _input.moveFront();
                }
            }

            static if (hasAssignableElements!R)
            {
                @property auto ref front(ElementType!R v)
                {
                    assert(!empty,
                        "Attempting to assign to the front of an empty "
                        ~ typeof(this).stringof);
                    return _input.front = v;
                }
            }
        }

        return Result(range, n);
    }
}

///
pure @safe nothrow unittest
{
    import std.algorithm.comparison : equal;

    auto a = [ 1, 2, 3, 4, 5 ];

    auto b = takeExactly(a, 3);
    assert(equal(b, [1, 2, 3]));
    static assert(is(typeof(b.length) == size_t));
    assert(b.length == 3);
    assert(b.front == 1);
    assert(b.back == 3);
}

pure @safe nothrow unittest
{
    import std.algorithm.comparison : equal;
    import std.algorithm.iteration : filter;

    auto a = [ 1, 2, 3, 4, 5 ];
    auto b = takeExactly(a, 3);
    assert(equal(b, [1, 2, 3]));
    auto c = takeExactly(b, 2);
    assert(equal(c, [1, 2]));



    auto d = filter!"a > 2"(a);
    auto e = takeExactly(d, 3);
    assert(equal(e, [3, 4, 5]));
    static assert(is(typeof(e.length) == size_t));
    assert(e.length == 3);
    assert(e.front == 3);

    assert(equal(takeExactly(e, 3), [3, 4, 5]));
}

pure @safe nothrow unittest
{
    import std.algorithm.comparison : equal;
    import std.internal.test.dummyrange : AllDummyRanges;

    auto a = [ 1, 2, 3, 4, 5 ];
    //Test that take and takeExactly are the same for ranges which define length
    //but aren't sliceable.
    struct L
    {
        @property auto front() { return _arr[0]; }
        @property bool empty() { return _arr.empty; }
        void popFront() { _arr.popFront(); }
        @property size_t length() { return _arr.length; }
        int[] _arr;
    }
    static assert(is(typeof(take(L(a), 3)) == typeof(takeExactly(L(a), 3))));
    assert(take(L(a), 3) == takeExactly(L(a), 3));

    //Test that take and takeExactly are the same for ranges which are sliceable.
    static assert(is(typeof(take(a, 3)) == typeof(takeExactly(a, 3))));
    assert(take(a, 3) == takeExactly(a, 3));

    //Test that take and takeExactly are the same for infinite ranges.
    auto inf = repeat(1);
    static assert(is(typeof(take(inf, 5)) == Take!(typeof(inf))));
    assert(take(inf, 5) == takeExactly(inf, 5));

    //Test that take and takeExactly are _not_ the same for ranges which don't
    //define length.
    static assert(!is(typeof(take(filter!"true"(a), 3)) == typeof(takeExactly(filter!"true"(a), 3))));

    foreach (DummyType; AllDummyRanges)
    {
        {
            DummyType dummy;
            auto t = takeExactly(dummy, 5);

            //Test that takeExactly doesn't wrap the result of takeExactly.
            assert(takeExactly(t, 4) == takeExactly(dummy, 4));
        }

        static if (hasMobileElements!DummyType)
        {
            {
                auto t = takeExactly(DummyType.init, 4);
                assert(t.moveFront() == 1);
                assert(equal(t, [1, 2, 3, 4]));
            }
        }

        static if (hasAssignableElements!DummyType)
        {
            {
                auto t = takeExactly(DummyType.init, 4);
                t.front = 9;
                assert(equal(t, [9, 2, 3, 4]));
            }
        }
    }
}

pure @safe nothrow unittest
{
    import std.algorithm.comparison : equal;
    import std.internal.test.dummyrange : DummyRange, Length, RangeType, ReturnBy;

    alias DummyType = DummyRange!(ReturnBy.Value, Length.No, RangeType.Forward);
    auto te = takeExactly(DummyType(), 5);
    Take!DummyType t = te;
    assert(equal(t, [1, 2, 3, 4, 5]));
    assert(equal(t, te));
}

/**
Returns a range with at most one element; for example, $(D
takeOne([42, 43, 44])) returns a range consisting of the integer $(D
42). Calling $(D popFront()) off that range renders it empty.

In effect $(D takeOne(r)) is somewhat equivalent to $(D take(r, 1)) but in
certain interfaces it is important to know statically that the range may only
have at most one element.

The type returned by $(D takeOne) is a random-access range with length
regardless of $(D R)'s capabilities, as long as it is a forward range.
(another feature that distinguishes $(D takeOne) from $(D take)). If
(D R) is an input range but not a forward range, return type is an input
range with all random-access capabilities except save.
 */
auto takeOne(R)(R source)
if (isInputRange!R)
{
    static if (hasSlicing!R)
    {
        return source[0 .. !source.empty];
    }
    else
    {
        static struct Result
        {
            private R _source;
            private bool _empty = true;
            @property bool empty() const { return _empty; }
            @property auto ref front()
            {
                assert(!empty, "Attempting to fetch the front of an empty takeOne");
                return _source.front;
            }
            void popFront()
            {
                assert(!empty, "Attempting to popFront an empty takeOne");
                _source.popFront();
                _empty = true;
            }
            void popBack()
            {
                assert(!empty, "Attempting to popBack an empty takeOne");
                _source.popFront();
                _empty = true;
            }
            static if (isForwardRange!(Unqual!R))
            {
                @property auto save() { return Result(_source.save, empty); }
            }
            @property auto ref back()
            {
                assert(!empty, "Attempting to fetch the back of an empty takeOne");
                return _source.front;
            }
            @property size_t length() const { return !empty; }
            alias opDollar = length;
            auto ref opIndex(size_t n)
            {
                assert(n < length, "Attempting to index a takeOne out of bounds");
                return _source.front;
            }
            auto opSlice(size_t m, size_t n)
            {
                assert(m <= n && n < length, "Attempting to index a takeOne out of bounds");
                return n > m ? this : Result(_source, false);
            }
            // Non-standard property
            @property R source() { return _source; }
        }

        return Result(source, source.empty);
    }
}

///
pure @safe nothrow unittest
{
    auto s = takeOne([42, 43, 44]);
    static assert(isRandomAccessRange!(typeof(s)));
    assert(s.length == 1);
    assert(!s.empty);
    assert(s.front == 42);
    s.front = 43;
    assert(s.front == 43);
    assert(s.back == 43);
    assert(s[0] == 43);
    s.popFront();
    assert(s.length == 0);
    assert(s.empty);
}

pure @safe nothrow @nogc unittest
{
    struct NonForwardRange
    {
        enum empty = false;
        int front() { return 42; }
        void popFront() {}
    }

    static assert(!isForwardRange!NonForwardRange);

    auto s = takeOne(NonForwardRange());
    assert(s.front == 42);
}

//guards against issue 16999
pure @safe unittest
{
    auto myIota = new class
    {
        int front = 0;
        @safe void popFront(){front++;}
        enum empty = false;
    };
    auto iotaPart = myIota.takeOne;
    int sum;
    foreach (var; chain(iotaPart, iotaPart, iotaPart))
    {
        sum += var;
    }
    assert(sum == 3);
    assert(iotaPart.front == 3);
}

/++
    Returns an empty range which is statically known to be empty and is
    guaranteed to have $(D length) and be random access regardless of $(D R)'s
    capabilities.
  +/
auto takeNone(R)()
if (isInputRange!R)
{
    return typeof(takeOne(R.init)).init;
}

///
pure @safe nothrow @nogc unittest
{
    auto range = takeNone!(int[])();
    assert(range.length == 0);
    assert(range.empty);
}

pure @safe nothrow @nogc unittest
{
    enum ctfe = takeNone!(int[])();
    static assert(ctfe.length == 0);
    static assert(ctfe.empty);
}


/++
    Creates an empty range from the given range in $(BIGOH 1). If it can, it
    will return the same range type. If not, it will return
    $(D takeExactly(range, 0)).
  +/
auto takeNone(R)(R range)
if (isInputRange!R)
{
    import std.traits : isDynamicArray;
    //Makes it so that calls to takeNone which don't use UFCS still work with a
    //member version if it's defined.
    static if (is(typeof(R.takeNone)))
        auto retval = range.takeNone();
    //@@@BUG@@@ 8339
    else static if (isDynamicArray!R)/+ ||
                   (is(R == struct) && __traits(compiles, {auto r = R.init;}) && R.init.empty))+/
    {
        auto retval = R.init;
    }
    //An infinite range sliced at [0 .. 0] would likely still not be empty...
    else static if (hasSlicing!R && !isInfinite!R)
        auto retval = range[0 .. 0];
    else
        auto retval = takeExactly(range, 0);

    //@@@BUG@@@ 7892 prevents this from being done in an out block.
    assert(retval.empty);
    return retval;
}

///
pure @safe nothrow unittest
{
    import std.algorithm.iteration : filter;
    assert(takeNone([42, 27, 19]).empty);
    assert(takeNone("dlang.org").empty);
    assert(takeNone(filter!"true"([42, 27, 19])).empty);
}

@safe unittest
{
    import std.algorithm.iteration : filter;
    import std.meta : AliasSeq;

    struct Dummy
    {
        mixin template genInput()
        {
        @safe:
            @property bool empty() { return _arr.empty; }
            @property auto front() { return _arr.front; }
            void popFront() { _arr.popFront(); }
            static assert(isInputRange!(typeof(this)));
        }
    }
    alias genInput = Dummy.genInput;

    static struct NormalStruct
    {
        //Disabled to make sure that the takeExactly version is used.
        @disable this();
        this(int[] arr) { _arr = arr; }
        mixin genInput;
        int[] _arr;
    }

    static struct SliceStruct
    {
        @disable this();
        this(int[] arr) { _arr = arr; }
        mixin genInput;
        @property auto save() { return this; }
        auto opSlice(size_t i, size_t j) { return typeof(this)(_arr[i .. j]); }
        @property size_t length() { return _arr.length; }
        int[] _arr;
    }

    static struct InitStruct
    {
        mixin genInput;
        int[] _arr;
    }

    static struct TakeNoneStruct
    {
        this(int[] arr) { _arr = arr; }
        @disable this();
        mixin genInput;
        auto takeNone() { return typeof(this)(null); }
        int[] _arr;
    }

    static class NormalClass
    {
        this(int[] arr) {_arr = arr;}
        mixin genInput;
        int[] _arr;
    }

    static class SliceClass
    {
    @safe:
        this(int[] arr) { _arr = arr; }
        mixin genInput;
        @property auto save() { return new typeof(this)(_arr); }
        auto opSlice(size_t i, size_t j) { return new typeof(this)(_arr[i .. j]); }
        @property size_t length() { return _arr.length; }
        int[] _arr;
    }

    static class TakeNoneClass
    {
    @safe:
        this(int[] arr) { _arr = arr; }
        mixin genInput;
        auto takeNone() { return new typeof(this)(null); }
        int[] _arr;
    }

    import std.format : format;

    foreach (range; AliasSeq!([1, 2, 3, 4, 5],
                             "hello world",
                             "hello world"w,
                             "hello world"d,
                             SliceStruct([1, 2, 3]),
                             //@@@BUG@@@ 8339 forces this to be takeExactly
                             //`InitStruct([1, 2, 3]),
                             TakeNoneStruct([1, 2, 3])))
    {
        static assert(takeNone(range).empty, typeof(range).stringof);
        assert(takeNone(range).empty);
        static assert(is(typeof(range) == typeof(takeNone(range))), typeof(range).stringof);
    }

    foreach (range; AliasSeq!(NormalStruct([1, 2, 3]),
                             InitStruct([1, 2, 3])))
    {
        static assert(takeNone(range).empty, typeof(range).stringof);
        assert(takeNone(range).empty);
        static assert(is(typeof(takeExactly(range, 0)) == typeof(takeNone(range))), typeof(range).stringof);
    }

    //Don't work in CTFE.
    auto normal = new NormalClass([1, 2, 3]);
    assert(takeNone(normal).empty);
    static assert(is(typeof(takeExactly(normal, 0)) == typeof(takeNone(normal))), typeof(normal).stringof);

    auto slice = new SliceClass([1, 2, 3]);
    assert(takeNone(slice).empty);
    static assert(is(SliceClass == typeof(takeNone(slice))), typeof(slice).stringof);

    auto taken = new TakeNoneClass([1, 2, 3]);
    assert(takeNone(taken).empty);
    static assert(is(TakeNoneClass == typeof(takeNone(taken))), typeof(taken).stringof);

    auto filtered = filter!"true"([1, 2, 3, 4, 5]);
    assert(takeNone(filtered).empty);
    //@@@BUG@@@ 8339 and 5941 force this to be takeExactly
    //static assert(is(typeof(filtered) == typeof(takeNone(filtered))), typeof(filtered).stringof);
}

/++
 + Return a _range advanced to within $(D _n) elements of the end of
 + $(D _range).
 +
 + Intended as the _range equivalent of the Unix
 + $(HTTP en.wikipedia.org/wiki/Tail_%28Unix%29, _tail) utility. When the length
 + of $(D _range) is less than or equal to $(D _n), $(D _range) is returned
 + as-is.
 +
 + Completes in $(BIGOH 1) steps for ranges that support slicing and have
 + length. Completes in $(BIGOH _range.length) time for all other ranges.
 +
 + Params:
 +    range = _range to get _tail of
 +    n = maximum number of elements to include in _tail
 +
 + Returns:
 +    Returns the _tail of $(D _range) augmented with length information
 +/
auto tail(Range)(Range range, size_t n)
if (isInputRange!Range && !isInfinite!Range &&
    (hasLength!Range || isForwardRange!Range))
{
    static if (hasLength!Range)
    {
        immutable length = range.length;
        if (n >= length)
            return range.takeExactly(length);
        else
            return range.drop(length - n).takeExactly(n);
    }
    else
    {
        Range scout = range.save;
        foreach (immutable i; 0 .. n)
        {
            if (scout.empty)
                return range.takeExactly(i);
            scout.popFront();
        }

        auto tail = range.save;
        while (!scout.empty)
        {
            assert(!tail.empty);
            scout.popFront();
            tail.popFront();
        }

        return tail.takeExactly(n);
    }
}

///
pure @safe nothrow unittest
{
    // tail -c n
    assert([1, 2, 3].tail(1) == [3]);
    assert([1, 2, 3].tail(2) == [2, 3]);
    assert([1, 2, 3].tail(3) == [1, 2, 3]);
    assert([1, 2, 3].tail(4) == [1, 2, 3]);
    assert([1, 2, 3].tail(0).length == 0);

    // tail --lines=n
    import std.algorithm.comparison : equal;
    import std.algorithm.iteration : joiner;
    import std.exception : assumeWontThrow;
    import std.string : lineSplitter;
    assert("one\ntwo\nthree"
        .lineSplitter
        .tail(2)
        .joiner("\n")
        .equal("two\nthree")
        .assumeWontThrow);
}

// @nogc prevented by @@@BUG@@@ 15408
pure nothrow @safe /+@nogc+/ unittest
{
    import std.algorithm.comparison : equal;
    import std.internal.test.dummyrange : AllDummyRanges, DummyRange, Length,
        RangeType, ReturnBy;

    static immutable cheatsheet = [6, 7, 8, 9, 10];

    foreach (R; AllDummyRanges)
    {
        static if (isInputRange!R && !isInfinite!R &&
                   (hasLength!R || isForwardRange!R))
        {
            assert(R.init.tail(5).equal(cheatsheet));
            static assert(R.init.tail(5).equal(cheatsheet));

            assert(R.init.tail(0).length == 0);
            assert(R.init.tail(10).equal(R.init));
            assert(R.init.tail(11).equal(R.init));
        }
    }

    // Infinite ranges are not supported
    static assert(!__traits(compiles, repeat(0).tail(0)));

    // Neither are non-forward ranges without length
    static assert(!__traits(compiles, DummyRange!(ReturnBy.Value, Length.No,
        RangeType.Input).init.tail(5)));
}

pure @safe nothrow @nogc unittest
{
    static immutable input = [1, 2, 3];
    static immutable expectedOutput = [2, 3];
    assert(input.tail(2) == expectedOutput);
}

/++
    Convenience function which calls
    $(REF popFrontN, std, _range, primitives)`(range, n)` and returns `range`.
    `drop` makes it easier to pop elements from a range
    and then pass it to another function within a single expression,
    whereas `popFrontN` would require multiple statements.

    `dropBack` provides the same functionality but instead calls
    $(REF popBackN, std, _range, primitives)`(range, n)`

    Note: `drop` and `dropBack` will only pop $(I up to)
    `n` elements but will stop if the range is empty first.
    In other languages this is sometimes called `skip`.

    Params:
        range = the input range to drop from
        n = the number of elements to drop

    Returns:
        `range` with up to `n` elements dropped

    See_Also:
        $(REF popFront, std, _range, primitives), $(REF popBackN, std, _range, primitives)
  +/
R drop(R)(R range, size_t n)
if (isInputRange!R)
{
    range.popFrontN(n);
    return range;
}
/// ditto
R dropBack(R)(R range, size_t n)
if (isBidirectionalRange!R)
{
    range.popBackN(n);
    return range;
}

///
@safe unittest
{
    import std.algorithm.comparison : equal;

    assert([0, 2, 1, 5, 0, 3].drop(3) == [5, 0, 3]);
    assert("hello world".drop(6) == "world");
    assert("hello world".drop(50).empty);
    assert("hello world".take(6).drop(3).equal("lo "));
}

@safe unittest
{
    import std.algorithm.comparison : equal;

    assert([0, 2, 1, 5, 0, 3].dropBack(3) == [0, 2, 1]);
    assert("hello world".dropBack(6) == "hello");
    assert("hello world".dropBack(50).empty);
    assert("hello world".drop(4).dropBack(4).equal("o w"));
}

@safe unittest
{
    import std.algorithm.comparison : equal;
    import std.container.dlist : DList;

    //Remove all but the first two elements
    auto a = DList!int(0, 1, 9, 9, 9, 9);
    a.remove(a[].drop(2));
    assert(a[].equal(a[].take(2)));
}

@safe unittest
{
    import std.algorithm.comparison : equal;
    import std.algorithm.iteration : filter;

    assert(drop("", 5).empty);
    assert(equal(drop(filter!"true"([0, 2, 1, 5, 0, 3]), 3), [5, 0, 3]));
}

@safe unittest
{
    import std.algorithm.comparison : equal;
    import std.container.dlist : DList;

    //insert before the last two elements
    auto a = DList!int(0, 1, 2, 5, 6);
    a.insertAfter(a[].dropBack(2), [3, 4]);
    assert(a[].equal(iota(0, 7)));
}

/++
    Similar to $(LREF drop) and $(D dropBack) but they call
    $(D range.$(LREF popFrontExactly)(n)) and $(D range.popBackExactly(n))
    instead.

    Note: Unlike $(D drop), $(D dropExactly) will assume that the
    range holds at least $(D n) elements. This makes $(D dropExactly)
    faster than $(D drop), but it also means that if $(D range) does
    not contain at least $(D n) elements, it will attempt to call $(D popFront)
    on an empty range, which is undefined behavior. So, only use
    $(D popFrontExactly) when it is guaranteed that $(D range) holds at least
    $(D n) elements.

    Params:
        range = the input range to drop from
        n = the number of elements to drop

    Returns:
        `range` with `n` elements dropped

    See_Also:
        $(REF popFrontExcatly, std, _range, primitives),
        $(REF popBackExcatly, std, _range, primitives)
+/
R dropExactly(R)(R range, size_t n)
if (isInputRange!R)
{
    popFrontExactly(range, n);
    return range;
}
/// ditto
R dropBackExactly(R)(R range, size_t n)
if (isBidirectionalRange!R)
{
    popBackExactly(range, n);
    return range;
}

///
@safe unittest
{
    import std.algorithm.comparison : equal;
    import std.algorithm.iteration : filterBidirectional;

    auto a = [1, 2, 3];
    assert(a.dropExactly(2) == [3]);
    assert(a.dropBackExactly(2) == [1]);

    string s = "日本語";
    assert(s.dropExactly(2) == "語");
    assert(s.dropBackExactly(2) == "日");

    auto bd = filterBidirectional!"true"([1, 2, 3]);
    assert(bd.dropExactly(2).equal([3]));
    assert(bd.dropBackExactly(2).equal([1]));
}

/++
    Convenience function which calls
    $(D range.popFront()) and returns $(D range). $(D dropOne)
    makes it easier to pop an element from a range
    and then pass it to another function within a single expression,
    whereas $(D popFront) would require multiple statements.

    $(D dropBackOne) provides the same functionality but instead calls
    $(D range.popBack()).
+/
R dropOne(R)(R range)
if (isInputRange!R)
{
    range.popFront();
    return range;
}
/// ditto
R dropBackOne(R)(R range)
if (isBidirectionalRange!R)
{
    range.popBack();
    return range;
}

///
pure @safe nothrow unittest
{
    import std.algorithm.comparison : equal;
    import std.algorithm.iteration : filterBidirectional;
    import std.container.dlist : DList;

    auto dl = DList!int(9, 1, 2, 3, 9);
    assert(dl[].dropOne().dropBackOne().equal([1, 2, 3]));

    auto a = [1, 2, 3];
    assert(a.dropOne() == [2, 3]);
    assert(a.dropBackOne() == [1, 2]);

    string s = "日本語";
    import std.exception : assumeWontThrow;
    assert(assumeWontThrow(s.dropOne() == "本語"));
    assert(assumeWontThrow(s.dropBackOne() == "日本"));

    auto bd = filterBidirectional!"true"([1, 2, 3]);
    assert(bd.dropOne().equal([2, 3]));
    assert(bd.dropBackOne().equal([1, 2]));
}

/**
Create a range which repeats one value forever.

Params:
    value = the value to repeat

Returns:
    An infinite random access range with slicing.
*/
struct Repeat(T)
{
private:
    //Store a non-qualified T when possible: This is to make Repeat assignable
    static if ((is(T == class) || is(T == interface)) && (is(T == const) || is(T == immutable)))
    {
        import std.typecons : Rebindable;
        alias UT = Rebindable!T;
    }
    else static if (is(T : Unqual!T) && is(Unqual!T : T))
        alias UT = Unqual!T;
    else
        alias UT = T;
    UT _value;

public:
    /// Range primitives
    @property inout(T) front() inout { return _value; }

    /// ditto
    @property inout(T) back() inout { return _value; }

    /// ditto
    enum bool empty = false;

    /// ditto
    void popFront() {}

    /// ditto
    void popBack() {}

    /// ditto
    @property auto save() inout { return this; }

    /// ditto
    inout(T) opIndex(size_t) inout { return _value; }

    /// ditto
    auto opSlice(size_t i, size_t j)
    in
    {
        assert(
            i <= j,
            "Attempting to slice a Repeat with a larger first argument than the second."
        );
    }
    body
    {
        return this.takeExactly(j - i);
    }
    private static struct DollarToken {}

    /// ditto
    enum opDollar = DollarToken.init;

    /// ditto
    auto opSlice(size_t, DollarToken) inout { return this; }
}

/// Ditto
Repeat!T repeat(T)(T value) { return Repeat!T(value); }

///
pure @safe nothrow unittest
{
    import std.algorithm.comparison : equal;

    assert(equal(5.repeat().take(4), [ 5, 5, 5, 5 ]));
}

pure @safe nothrow unittest
{
    import std.algorithm.comparison : equal;

    auto  r = repeat(5);
    alias R = typeof(r);
    static assert(isBidirectionalRange!R);
    static assert(isForwardRange!R);
    static assert(isInfinite!R);
    static assert(hasSlicing!R);

    assert(r.back == 5);
    assert(r.front == 5);
    assert(r.take(4).equal([ 5, 5, 5, 5 ]));
    assert(r[0 .. 4].equal([ 5, 5, 5, 5 ]));

    R r2 = r[5 .. $];
    assert(r2.back == 5);
    assert(r2.front == 5);
}

/**
   Repeats $(D value) exactly $(D n) times. Equivalent to $(D
   take(repeat(value), n)).
*/
Take!(Repeat!T) repeat(T)(T value, size_t n)
{
    return take(repeat(value), n);
}

///
pure @safe nothrow @nogc unittest
{
    import std.algorithm.comparison : equal;

    assert(equal(5.repeat(4), 5.repeat().take(4)));
}

pure @safe nothrow unittest //12007
{
    static class C{}
    Repeat!(immutable int) ri;
    ri = ri.save;
    Repeat!(immutable C) rc;
    rc = rc.save;

    import std.algorithm.setops : cartesianProduct;
    import std.algorithm.comparison : equal;
    import std.typecons : tuple;
    immutable int[] A = [1,2,3];
    immutable int[] B = [4,5,6];

    assert(equal(cartesianProduct(A,B),
        [
            tuple(1, 4), tuple(1, 5), tuple(1, 6),
            tuple(2, 4), tuple(2, 5), tuple(2, 6),
            tuple(3, 4), tuple(3, 5), tuple(3, 6),
        ]));
}

/**
Given callable ($(REF isCallable, std,traits)) `fun`, create as a range
whose front is defined by successive calls to `fun()`.
This is especially useful to call function with global side effects (random
functions), or to create ranges expressed as a single delegate, rather than
an entire `front`/`popFront`/`empty` structure.
`fun` maybe be passed either a template alias parameter (existing
function, delegate, struct type defining `static opCall`) or
a run-time value argument (delegate, function object).
The result range models an InputRange
($(REF isInputRange, std,range,primitives)).
The resulting range will call `fun()` on construction, and every call to
`popFront`, and the cached value will be returned when `front` is called.

Returns: an `inputRange` where each element represents another call to fun.
*/
auto generate(Fun)(Fun fun)
if (isCallable!fun)
{
    auto gen = Generator!(Fun)(fun);
    gen.popFront(); // prime the first element
    return gen;
}

/// ditto
auto generate(alias fun)()
if (isCallable!fun)
{
    auto gen = Generator!(fun)();
    gen.popFront(); // prime the first element
    return gen;
}

///
@safe pure unittest
{
    import std.algorithm.comparison : equal;
    import std.algorithm.iteration : map;

    int i = 1;
    auto powersOfTwo = generate!(() => i *= 2)().take(10);
    assert(equal(powersOfTwo, iota(1, 11).map!"2^^a"()));
}

///
@safe pure unittest
{
    import std.algorithm.comparison : equal;

    //Returns a run-time delegate
    auto infiniteIota(T)(T low, T high)
    {
        T i = high;
        return (){if (i == high) i = low; return i++;};
    }
    //adapted as a range.
    assert(equal(generate(infiniteIota(1, 4)).take(10), [1, 2, 3, 1, 2, 3, 1, 2, 3, 1]));
}

///
@safe unittest
{
    import std.format : format;
    import std.random : uniform;

    auto r = generate!(() => uniform(0, 6)).take(10);
    format("%(%s %)", r);
}

private struct Generator(Fun...)
{
    static assert(Fun.length == 1);
    static assert(isInputRange!Generator);

private:
    static if (is(Fun[0]))
        Fun[0] fun;
    else
        alias fun = Fun[0];

    enum returnByRef_ = (functionAttributes!fun & FunctionAttribute.ref_) ? true : false;
    static if (returnByRef_)
        ReturnType!fun *elem_;
    else
        ReturnType!fun elem_;
public:
    /// Range primitives
    enum empty = false;

    static if (returnByRef_)
    {
        /// ditto
        ref front() @property
        {
            return *elem_;
        }
        /// ditto
        void popFront()
        {
            elem_ = &fun();
        }
    }
    else
    {
        /// ditto
        auto front() @property
        {
            return elem_;
        }
        /// ditto
        void popFront()
        {
            elem_ = fun();
        }
    }
}

@safe unittest
{
    import std.algorithm.comparison : equal;

    struct StaticOpCall
    {
        static ubyte opCall() { return 5 ; }
    }

    assert(equal(generate!StaticOpCall().take(10), repeat(5).take(10)));
}

@safe pure unittest
{
    import std.algorithm.comparison : equal;

    struct OpCall
    {
        ubyte opCall() @safe pure { return 5 ; }
    }

    OpCall op;
    assert(equal(generate(op).take(10), repeat(5).take(10)));
}

// verify ref mechanism works
@system unittest
{
    int[10] arr;
    int idx;

    ref int fun() {
        auto x = idx++;
        idx %= arr.length;
        return arr[x];
    }
    int y = 1;
    foreach (ref x; generate!(fun).take(20))
    {
        x += y++;
    }
    import std.algorithm.comparison : equal;
    assert(equal(arr[], iota(12, 32, 2)));
}

// assure front isn't the mechanism to make generate go to the next element.
@safe unittest
{
    int i;
    auto g = generate!(() => ++i);
    auto f = g.front;
    assert(f == g.front);
    g = g.drop(5); // reassign because generate caches
    assert(g.front == f + 5);
}

/**
Repeats the given forward range ad infinitum. If the original range is
infinite (fact that would make $(D Cycle) the identity application),
$(D Cycle) detects that and aliases itself to the range type
itself. That works for non-forward ranges too.
If the original range has random access, $(D Cycle) offers
random access and also offers a constructor taking an initial position
$(D index). $(D Cycle) works with static arrays in addition to ranges,
mostly for performance reasons.

Note: The input range must not be empty.

Tip: This is a great way to implement simple circular buffers.
*/
struct Cycle(R)
if (isForwardRange!R && !isInfinite!R)
{
    static if (isRandomAccessRange!R && hasLength!R)
    {
        private R _original;
        private size_t _index;

        /// Range primitives
        this(R input, size_t index = 0)
        {
            _original = input;
            _index = index % _original.length;
        }

        /// ditto
        @property auto ref front()
        {
            return _original[_index];
        }

        static if (is(typeof((cast(const R)_original)[_index])))
        {
            /// ditto
            @property auto ref front() const
            {
                return _original[_index];
            }
        }

        static if (hasAssignableElements!R)
        {
            /// ditto
            @property void front(ElementType!R val)
            {
                _original[_index] = val;
            }
        }

        /// ditto
        enum bool empty = false;

        /// ditto
        void popFront()
        {
            ++_index;
            if (_index >= _original.length)
                _index = 0;
        }

        /// ditto
        auto ref opIndex(size_t n)
        {
            return _original[(n + _index) % _original.length];
        }

        static if (is(typeof((cast(const R)_original)[_index])) &&
                   is(typeof((cast(const R)_original).length)))
        {
            /// ditto
            auto ref opIndex(size_t n) const
            {
                return _original[(n + _index) % _original.length];
            }
        }

        static if (hasAssignableElements!R)
        {
            /// ditto
            void opIndexAssign(ElementType!R val, size_t n)
            {
                _original[(n + _index) % _original.length] = val;
            }
        }

        /// ditto
        @property Cycle save()
        {
            //No need to call _original.save, because Cycle never actually modifies _original
            return Cycle(_original, _index);
        }

        private static struct DollarToken {}

        /// ditto
        enum opDollar = DollarToken.init;

        static if (hasSlicing!R)
        {
            /// ditto
            auto opSlice(size_t i, size_t j)
            in
            {
                assert(i <= j);
            }
            body
            {
                return this[i .. $].takeExactly(j - i);
            }

            /// ditto
            auto opSlice(size_t i, DollarToken)
            {
                return typeof(this)(_original, _index + i);
            }
        }
    }
    else
    {
        private R _original;
        private R _current;

        /// ditto
        this(R input)
        {
            _original = input;
            _current = input.save;
        }

        /// ditto
        @property auto ref front()
        {
            return _current.front;
        }

        static if (is(typeof((cast(const R)_current).front)))
        {
            /// ditto
            @property auto ref front() const
            {
                return _current.front;
            }
        }

        static if (hasAssignableElements!R)
        {
            /// ditto
            @property auto front(ElementType!R val)
            {
                return _current.front = val;
            }
        }

        /// ditto
        enum bool empty = false;

        /// ditto
        void popFront()
        {
            _current.popFront();
            if (_current.empty)
                _current = _original.save;
        }

        /// ditto
        @property Cycle save()
        {
            //No need to call _original.save, because Cycle never actually modifies _original
            Cycle ret = this;
            ret._original = _original;
            ret._current =  _current.save;
            return ret;
        }
    }
}

/// ditto
template Cycle(R)
if (isInfinite!R)
{
    alias Cycle = R;
}

///
struct Cycle(R)
if (isStaticArray!R)
{
    private alias ElementType = typeof(R.init[0]);
    private ElementType* _ptr;
    private size_t _index;

nothrow:

    /// Range primitives
    this(ref R input, size_t index = 0) @system
    {
        _ptr = input.ptr;
        _index = index % R.length;
    }

    /// ditto
    @property ref inout(ElementType) front() inout @safe
    {
        static ref auto trustedPtrIdx(typeof(_ptr) p, size_t idx) @trusted
        {
            return p[idx];
        }
        return trustedPtrIdx(_ptr, _index);
    }

    /// ditto
    enum bool empty = false;

    /// ditto
    void popFront() @safe
    {
        ++_index;
        if (_index >= R.length)
            _index = 0;
    }

    /// ditto
    ref inout(ElementType) opIndex(size_t n) inout @safe
    {
        static ref auto trustedPtrIdx(typeof(_ptr) p, size_t idx) @trusted
        {
            return p[idx % R.length];
        }
        return trustedPtrIdx(_ptr, n + _index);
    }

    /// ditto
    @property inout(Cycle) save() inout @safe
    {
        return this;
    }

    private static struct DollarToken {}
    /// ditto
    enum opDollar = DollarToken.init;

    /// ditto
    auto opSlice(size_t i, size_t j) @safe
    in
    {
        assert(
            i <= j,
            "Attempting to slice a Repeat with a larger first argument than the second."
        );
    }
    body
    {
        return this[i .. $].takeExactly(j - i);
    }

    /// ditto
    inout(typeof(this)) opSlice(size_t i, DollarToken) inout @safe
    {
        static auto trustedCtor(typeof(_ptr) p, size_t idx) @trusted
        {
            return cast(inout) Cycle(*cast(R*)(p), idx);
        }
        return trustedCtor(_ptr, _index + i);
    }
}

/// Ditto
auto cycle(R)(R input)
if (isInputRange!R)
{
    static assert(isForwardRange!R || isInfinite!R,
        "Cycle requires a forward range argument unless it's statically known"
         ~ " to be infinite");
    assert(!input.empty, "Attempting to pass an empty input to cycle");
    static if (isInfinite!R) return input;
    else return Cycle!R(input);
}

///
@safe unittest
{
    import std.algorithm.comparison : equal;
    import std.range : cycle, take;

    // Here we create an infinitive cyclic sequence from [1, 2]
    // (i.e. get here [1, 2, 1, 2, 1, 2 and so on]) then
    // take 5 elements of this sequence (so we have [1, 2, 1, 2, 1])
    // and compare them with the expected values for equality.
    assert(cycle([1, 2]).take(5).equal([ 1, 2, 1, 2, 1 ]));
}

/// Ditto
Cycle!R cycle(R)(R input, size_t index = 0)
if (isRandomAccessRange!R && !isInfinite!R)
{
    assert(!input.empty, "Attempting to pass an empty input to cycle");
    return Cycle!R(input, index);
}

/// Ditto
Cycle!R cycle(R)(ref R input, size_t index = 0) @system
if (isStaticArray!R)
{
    return Cycle!R(input, index);
}

@safe unittest
{
    import std.algorithm.comparison : equal;
    import std.internal.test.dummyrange : AllDummyRanges;

    static assert(isForwardRange!(Cycle!(uint[])));

    // Make sure ref is getting propagated properly.
    int[] nums = [1,2,3];
    auto c2 = cycle(nums);
    c2[3]++;
    assert(nums[0] == 2);

    immutable int[] immarr = [1, 2, 3];

    foreach (DummyType; AllDummyRanges)
    {
        static if (isForwardRange!DummyType)
        {
            DummyType dummy;
            auto cy = cycle(dummy);
            static assert(isForwardRange!(typeof(cy)));
            auto t = take(cy, 20);
            assert(equal(t, [1,2,3,4,5,6,7,8,9,10,1,2,3,4,5,6,7,8,9,10]));

            const cRange = cy;
            assert(cRange.front == 1);

            static if (hasAssignableElements!DummyType)
            {
                {
                    cy.front = 66;
                    scope(exit) cy.front = 1;
                    assert(dummy.front == 66);
                }

                static if (isRandomAccessRange!DummyType)
                {
                    {
                        cy[10] = 66;
                        scope(exit) cy[10] = 1;
                        assert(dummy.front == 66);
                    }

                    assert(cRange[10] == 1);
                }
            }

            static if (hasSlicing!DummyType)
            {
                auto slice = cy[5 .. 15];
                assert(equal(slice, [6, 7, 8, 9, 10, 1, 2, 3, 4, 5]));
                static assert(is(typeof(slice) == typeof(takeExactly(cy, 5))));

                auto infSlice = cy[7 .. $];
                assert(equal(take(infSlice, 5), [8, 9, 10, 1, 2]));
                static assert(isInfinite!(typeof(infSlice)));
            }
        }
    }
}

@system unittest // For static arrays.
{
    import std.algorithm.comparison : equal;

    int[3] a = [ 1, 2, 3 ];
    static assert(isStaticArray!(typeof(a)));
    auto c = cycle(a);
    assert(a.ptr == c._ptr);
    assert(equal(take(cycle(a), 5), [ 1, 2, 3, 1, 2 ][]));
    static assert(isForwardRange!(typeof(c)));

    // Test qualifiers on slicing.
    alias C = typeof(c);
    static assert(is(typeof(c[1 .. $]) == C));
    const cConst = c;
    static assert(is(typeof(cConst[1 .. $]) == const(C)));
}

@safe unittest // For infinite ranges
{
    struct InfRange
    {
        void popFront() { }
        @property int front() { return 0; }
        enum empty = false;
        auto save() { return this; }
    }
    struct NonForwardInfRange
    {
        void popFront() { }
        @property int front() { return 0; }
        enum empty = false;
    }

    InfRange i;
    NonForwardInfRange j;
    auto c = cycle(i);
    assert(c == i);
    //make sure it can alias out even non-forward infinite ranges
    static assert(is(typeof(j.cycle) == typeof(j)));
}

@safe unittest
{
    import std.algorithm.comparison : equal;

    int[5] arr = [0, 1, 2, 3, 4];
    auto cleD = cycle(arr[]); //Dynamic
    assert(equal(cleD[5 .. 10], arr[]));

    //n is a multiple of 5 worth about 3/4 of size_t.max
    auto n = size_t.max/4 + size_t.max/2;
    n -= n % 5;

    //Test index overflow
    foreach (_ ; 0 .. 10)
    {
        cleD = cleD[n .. $];
        assert(equal(cleD[5 .. 10], arr[]));
    }
}

@system unittest
{
    import std.algorithm.comparison : equal;

    int[5] arr = [0, 1, 2, 3, 4];
    auto cleS = cycle(arr);   //Static
    assert(equal(cleS[5 .. 10], arr[]));

    //n is a multiple of 5 worth about 3/4 of size_t.max
    auto n = size_t.max/4 + size_t.max/2;
    n -= n % 5;

    //Test index overflow
    foreach (_ ; 0 .. 10)
    {
        cleS = cleS[n .. $];
        assert(equal(cleS[5 .. 10], arr[]));
    }
}

@system unittest
{
    import std.algorithm.comparison : equal;

    int[1] arr = [0];
    auto cleS = cycle(arr);
    cleS = cleS[10 .. $];
    assert(equal(cleS[5 .. 10], 0.repeat(5)));
    assert(cleS.front == 0);
}

@system unittest //10845
{
    import std.algorithm.comparison : equal;
    import std.algorithm.iteration : filter;

    auto a = inputRangeObject(iota(3).filter!"true");
    assert(equal(cycle(a).take(10), [0, 1, 2, 0, 1, 2, 0, 1, 2, 0]));
}

@safe unittest // 12177
{
    static assert(__traits(compiles, recurrence!q{a[n - 1] ~ a[n - 2]}("1", "0")));
}

// Issue 13390
@system unittest
{
    import core.exception : AssertError;
    import std.exception : assertThrown;
    assertThrown!AssertError(cycle([0, 1, 2][0 .. 0]));
}

private alias lengthType(R) = typeof(R.init.length.init);

/**
   Iterate several ranges in lockstep. The element type is a proxy tuple
   that allows accessing the current element in the $(D n)th range by
   using $(D e[n]).

   `zip` is similar to $(LREF lockstep), but `lockstep` doesn't
   bundle its elements and uses the `opApply` protocol.
   `lockstep` allows reference access to the elements in
   `foreach` iterations.

    Params:
        sp = controls what `zip` will do if the _ranges are different lengths
        ranges = the ranges to zip together
    Returns:
        At minimum, an input range. `Zip` offers the lowest range facilities
        of all components, e.g. it offers random access iff all ranges offer
        random access, and also offers mutation and swapping if all ranges offer
        it. Due to this, `Zip` is extremely powerful because it allows manipulating
        several ranges in lockstep.
    Throws:
        An `Exception` if all of the _ranges are not the same length and
        `sp` is set to `StoppingPolicy.requireSameLength`.
*/
struct Zip(Ranges...)
if (Ranges.length && allSatisfy!(isInputRange, Ranges))
{
    import std.format : format; //for generic mixins
    import std.typecons : Tuple;

    alias R = Ranges;
    private R ranges;
    alias ElementType = Tuple!(staticMap!(.ElementType, R));
    private StoppingPolicy stoppingPolicy = StoppingPolicy.shortest;

/**
   Builds an object. Usually this is invoked indirectly by using the
   $(LREF zip) function.
 */
    this(R rs, StoppingPolicy s = StoppingPolicy.shortest)
    {
        ranges[] = rs[];
        stoppingPolicy = s;
    }

/**
   Returns $(D true) if the range is at end. The test depends on the
   stopping policy.
*/
    static if (allSatisfy!(isInfinite, R))
    {
        // BUG:  Doesn't propagate infiniteness if only some ranges are infinite
        //       and s == StoppingPolicy.longest.  This isn't fixable in the
        //       current design since StoppingPolicy is known only at runtime.
        enum bool empty = false;
    }
    else
    {
        ///
        @property bool empty()
        {
            import std.exception : enforce;
            import std.meta : anySatisfy;

            final switch (stoppingPolicy)
            {
            case StoppingPolicy.shortest:
                foreach (i, Unused; R)
                {
                    if (ranges[i].empty) return true;
                }
                return false;
            case StoppingPolicy.longest:
                static if (anySatisfy!(isInfinite, R))
                {
                    return false;
                }
                else
                {
                    foreach (i, Unused; R)
                    {
                        if (!ranges[i].empty) return false;
                    }
                    return true;
                }
            case StoppingPolicy.requireSameLength:
                foreach (i, Unused; R[1 .. $])
                {
                    enforce(ranges[0].empty ==
                            ranges[i + 1].empty,
                            "Inequal-length ranges passed to Zip");
                }
                return ranges[0].empty;
            }
            assert(false);
        }
    }

    static if (allSatisfy!(isForwardRange, R))
    {
        ///
        @property Zip save()
        {
            //Zip(ranges[0].save, ranges[1].save, ..., stoppingPolicy)
            return mixin (q{Zip(%(ranges[%s].save%|, %), stoppingPolicy)}.format(iota(0, R.length)));
        }
    }

    private .ElementType!(R[i]) tryGetInit(size_t i)()
    {
        alias E = .ElementType!(R[i]);
        static if (!is(typeof({static E i;})))
            throw new Exception("Range with non-default constructable elements exhausted.");
        else
            return E.init;
    }

/**
   Returns the current iterated element.
*/
    @property ElementType front()
    {
        @property tryGetFront(size_t i)(){return ranges[i].empty ? tryGetInit!i() : ranges[i].front;}
        //ElementType(tryGetFront!0, tryGetFront!1, ...)
        return mixin(q{ElementType(%(tryGetFront!%s, %))}.format(iota(0, R.length)));
    }

/**
   Sets the front of all iterated ranges.
*/
    static if (allSatisfy!(hasAssignableElements, R))
    {
        @property void front(ElementType v)
        {
            foreach (i, Unused; R)
            {
                if (!ranges[i].empty)
                {
                    ranges[i].front = v[i];
                }
            }
        }
    }

/**
   Moves out the front.
*/
    static if (allSatisfy!(hasMobileElements, R))
    {
        ElementType moveFront()
        {
            @property tryMoveFront(size_t i)(){return ranges[i].empty ? tryGetInit!i() : ranges[i].moveFront();}
            //ElementType(tryMoveFront!0, tryMoveFront!1, ...)
            return mixin(q{ElementType(%(tryMoveFront!%s, %))}.format(iota(0, R.length)));
        }
    }

/**
   Returns the rightmost element.
*/
    static if (allSatisfy!(isBidirectionalRange, R))
    {
        @property ElementType back()
        {
            //TODO: Fixme! BackElement != back of all ranges in case of jagged-ness

            @property tryGetBack(size_t i)(){return ranges[i].empty ? tryGetInit!i() : ranges[i].back;}
            //ElementType(tryGetBack!0, tryGetBack!1, ...)
            return mixin(q{ElementType(%(tryGetBack!%s, %))}.format(iota(0, R.length)));
        }

/**
   Moves out the back.
*/
        static if (allSatisfy!(hasMobileElements, R))
        {
            ElementType moveBack()
            {
                //TODO: Fixme! BackElement != back of all ranges in case of jagged-ness

                @property tryMoveBack(size_t i)(){return ranges[i].empty ? tryGetInit!i() : ranges[i].moveFront();}
                //ElementType(tryMoveBack!0, tryMoveBack!1, ...)
                return mixin(q{ElementType(%(tryMoveBack!%s, %))}.format(iota(0, R.length)));
            }
        }

/**
   Returns the current iterated element.
*/
        static if (allSatisfy!(hasAssignableElements, R))
        {
            @property void back(ElementType v)
            {
                //TODO: Fixme! BackElement != back of all ranges in case of jagged-ness.
                //Not sure the call is even legal for StoppingPolicy.longest

                foreach (i, Unused; R)
                {
                    if (!ranges[i].empty)
                    {
                        ranges[i].back = v[i];
                    }
                }
            }
        }
    }

/**
   Advances to the next element in all controlled ranges.
*/
    void popFront()
    {
        import std.exception : enforce;

        final switch (stoppingPolicy)
        {
        case StoppingPolicy.shortest:
            foreach (i, Unused; R)
            {
                assert(!ranges[i].empty);
                ranges[i].popFront();
            }
            break;
        case StoppingPolicy.longest:
            foreach (i, Unused; R)
            {
                if (!ranges[i].empty) ranges[i].popFront();
            }
            break;
        case StoppingPolicy.requireSameLength:
            foreach (i, Unused; R)
            {
                enforce(!ranges[i].empty, "Invalid Zip object");
                ranges[i].popFront();
            }
            break;
        }
    }

/**
   Calls $(D popBack) for all controlled ranges.
*/
    static if (allSatisfy!(isBidirectionalRange, R))
    {
        void popBack()
        {
            //TODO: Fixme! In case of jaggedness, this is wrong.
            import std.exception : enforce;

            final switch (stoppingPolicy)
            {
            case StoppingPolicy.shortest:
                foreach (i, Unused; R)
                {
                    assert(!ranges[i].empty);
                    ranges[i].popBack();
                }
                break;
            case StoppingPolicy.longest:
                foreach (i, Unused; R)
                {
                    if (!ranges[i].empty) ranges[i].popBack();
                }
                break;
            case StoppingPolicy.requireSameLength:
                foreach (i, Unused; R)
                {
                    enforce(!ranges[i].empty, "Invalid Zip object");
                    ranges[i].popBack();
                }
                break;
            }
        }
    }

/**
   Returns the length of this range. Defined only if all ranges define
   $(D length).
*/
    static if (allSatisfy!(hasLength, R))
    {
        @property auto length()
        {
            static if (Ranges.length == 1)
                return ranges[0].length;
            else
            {
                if (stoppingPolicy == StoppingPolicy.requireSameLength)
                    return ranges[0].length;

                //[min|max](ranges[0].length, ranges[1].length, ...)
                import std.algorithm.comparison : min, max;
                if (stoppingPolicy == StoppingPolicy.shortest)
                    return mixin(q{min(%(ranges[%s].length%|, %))}.format(iota(0, R.length)));
                else
                    return mixin(q{max(%(ranges[%s].length%|, %))}.format(iota(0, R.length)));
            }
        }

        alias opDollar = length;
    }

/**
   Returns a slice of the range. Defined only if all range define
   slicing.
*/
    static if (allSatisfy!(hasSlicing, R))
    {
        auto opSlice(size_t from, size_t to)
        {
            //Slicing an infinite range yields the type Take!R
            //For finite ranges, the type Take!R aliases to R
            alias ZipResult = Zip!(staticMap!(Take, R));

            //ZipResult(ranges[0][from .. to], ranges[1][from .. to], ..., stoppingPolicy)
            return mixin (q{ZipResult(%(ranges[%s][from .. to]%|, %), stoppingPolicy)}.format(iota(0, R.length)));
        }
    }

/**
   Returns the $(D n)th element in the composite range. Defined if all
   ranges offer random access.
*/
    static if (allSatisfy!(isRandomAccessRange, R))
    {
        ElementType opIndex(size_t n)
        {
            //TODO: Fixme! This may create an out of bounds access
            //for StoppingPolicy.longest

            //ElementType(ranges[0][n], ranges[1][n], ...)
            return mixin (q{ElementType(%(ranges[%s][n]%|, %))}.format(iota(0, R.length)));
        }

/**
   Assigns to the $(D n)th element in the composite range. Defined if
   all ranges offer random access.
*/
        static if (allSatisfy!(hasAssignableElements, R))
        {
            void opIndexAssign(ElementType v, size_t n)
            {
                //TODO: Fixme! Not sure the call is even legal for StoppingPolicy.longest
                foreach (i, Range; R)
                {
                    ranges[i][n] = v[i];
                }
            }
        }

/**
   Destructively reads the $(D n)th element in the composite
   range. Defined if all ranges offer random access.
*/
        static if (allSatisfy!(hasMobileElements, R))
        {
            ElementType moveAt(size_t n)
            {
                //TODO: Fixme! This may create an out of bounds access
                //for StoppingPolicy.longest

                //ElementType(ranges[0].moveAt(n), ranges[1].moveAt(n), ..., )
                return mixin (q{ElementType(%(ranges[%s].moveAt(n)%|, %))}.format(iota(0, R.length)));
            }
        }
    }
}

/// Ditto
auto zip(Ranges...)(Ranges ranges)
if (Ranges.length && allSatisfy!(isInputRange, Ranges))
{
    return Zip!Ranges(ranges);
}

///
pure @safe unittest
{
    import std.algorithm.comparison : equal;
    import std.algorithm.iteration : map;

    // pairwise sum
    auto arr = [0, 1, 2];
    assert(zip(arr, arr.dropOne).map!"a[0] + a[1]".equal([1, 3]));
}

///
pure @safe unittest
{
    import std.conv : to;

    int[] a = [ 1, 2, 3 ];
    string[] b = [ "a", "b", "c" ];
    string[] result;

    foreach (tup; zip(a, b))
    {
        result ~= tup[0].to!string ~ tup[1];
    }

    assert(result == [ "1a", "2b", "3c" ]);

    size_t idx = 0;
    // unpacking tuple elements with foreach
    foreach (e1, e2; zip(a, b))
    {
        assert(e1 == a[idx]);
        assert(e2 == b[idx]);
        ++idx;
    }
}

/// $(D zip) is powerful - the following code sorts two arrays in parallel:
pure @safe unittest
{
    import std.algorithm.sorting : sort;

    int[] a = [ 1, 2, 3 ];
    string[] b = [ "a", "c", "b" ];
    zip(a, b).sort!((t1, t2) => t1[0] > t2[0]);

    assert(a == [ 3, 2, 1 ]);
    // b is sorted according to a's sorting
    assert(b == [ "b", "c", "a" ]);
}

/// Ditto
auto zip(Ranges...)(StoppingPolicy sp, Ranges ranges)
if (Ranges.length && allSatisfy!(isInputRange, Ranges))
{
    return Zip!Ranges(ranges, sp);
}

/**
   Dictates how iteration in a $(D Zip) should stop. By default stop at
   the end of the shortest of all ranges.
*/
enum StoppingPolicy
{
    /// Stop when the shortest range is exhausted
    shortest,
    /// Stop when the longest range is exhausted
    longest,
    /// Require that all ranges are equal
    requireSameLength,
}

@system unittest
{
    import std.algorithm.comparison : equal;
    import std.algorithm.iteration : filter, map;
    import std.algorithm.mutation : swap;
    import std.algorithm.sorting : sort;

    import std.exception : assertThrown, assertNotThrown;
    import std.typecons : tuple;

    int[] a = [ 1, 2, 3 ];
    float[] b = [ 1.0, 2.0, 3.0 ];
    foreach (e; zip(a, b))
    {
        assert(e[0] == e[1]);
    }

    swap(a[0], a[1]);