"Fossies" - the Fresh Open Source Software Archive

Member "dmd2/src/phobos/std/range/package.d" (20 Nov 2020, 391510 Bytes) of package /linux/misc/dmd.2.094.2.linux.tar.xz:


As a special service "Fossies" has tried to format the requested source page into HTML format using (guessed) D source code syntax highlighting (style: standard) with prefixed line numbers and code folding option. Alternatively you can here view or download the uninterpreted source code file.

    1 // Written in the D programming language.
    2 
    3 /**
    4 This module defines the notion of a range. Ranges generalize the concept of
    5 arrays, lists, or anything that involves sequential access. This abstraction
    6 enables the same set of algorithms (see $(MREF std, algorithm)) to be used
    7 with a vast variety of different concrete types. For example,
    8 a linear search algorithm such as $(REF find, std, algorithm, searching)
    9 works not just for arrays, but for linked-lists, input files,
   10 incoming network data, etc.
   11 
   12 Guides:
   13 
   14 There are many articles available that can bolster understanding ranges:
   15 
   16 $(UL
   17     $(LI Ali Çehreli's $(HTTP ddili.org/ders/d.en/ranges.html, tutorial on ranges)
   18         for the basics of working with and creating range-based code.)
   19     $(LI Jonathan M. Davis $(LINK2 http://dconf.org/2015/talks/davis.html, $(I Introduction to Ranges))
   20         talk at DConf 2015 a vivid introduction from its core constructs to practical advice.)
   21     $(LI The DLang Tour's $(LINK2 http://tour.dlang.org/tour/en/basics/ranges, chapter on ranges)
   22         for an interactive introduction.)
   23     $(LI H. S. Teoh's $(LINK2 http://wiki.dlang.org/Component_programming_with_ranges, tutorial on
   24         component programming with ranges) for a real-world showcase of the influence
   25         of range-based programming on complex algorithms.)
   26     $(LI Andrei Alexandrescu's article
   27         $(LINK2 http://www.informit.com/articles/printerfriendly.aspx?p=1407357$(AMP)rll=1,
   28         $(I On Iteration)) for conceptual aspect of ranges and the motivation
   29     )
   30 )
   31 
   32 Submodules:
   33 
   34 This module has two submodules:
   35 
   36 The $(MREF std, range, primitives) submodule
   37 provides basic range functionality. It defines several templates for testing
   38 whether a given object is a range, what kind of range it is, and provides
   39 some common range operations.
   40 
   41 The $(MREF std, range, interfaces) submodule
   42 provides object-based interfaces for working with ranges via runtime
   43 polymorphism.
   44 
   45 The remainder of this module provides a rich set of range creation and
   46 composition templates that let you construct new ranges out of existing ranges:
   47 
   48 
   49 $(SCRIPT inhibitQuickIndex = 1;)
   50 $(DIVC quickindex,
   51 $(BOOKTABLE ,
   52     $(TR $(TD $(LREF chain))
   53         $(TD Concatenates several ranges into a single range.
   54     ))
   55     $(TR $(TD $(LREF choose))
   56         $(TD Chooses one of two ranges at runtime based on a boolean condition.
   57     ))
   58     $(TR $(TD $(LREF chooseAmong))
   59         $(TD Chooses one of several ranges at runtime based on an index.
   60     ))
   61     $(TR $(TD $(LREF chunks))
   62         $(TD Creates a range that returns fixed-size chunks of the original
   63         range.
   64     ))
   65     $(TR $(TD $(LREF cycle))
   66         $(TD Creates an infinite range that repeats the given forward range
   67         indefinitely. Good for implementing circular buffers.
   68     ))
   69     $(TR $(TD $(LREF drop))
   70         $(TD Creates the range that results from discarding the first $(I n)
   71         elements from the given range.
   72     ))
   73     $(TR $(TD $(LREF dropBack))
   74         $(TD Creates the range that results from discarding the last $(I n)
   75         elements from the given range.
   76     ))
   77     $(TR $(TD $(LREF dropExactly))
   78         $(TD Creates the range that results from discarding exactly $(I n)
   79         of the first elements from the given range.
   80     ))
   81     $(TR $(TD $(LREF dropBackExactly))
   82         $(TD Creates the range that results from discarding exactly $(I n)
   83         of the last elements from the given range.
   84     ))
   85     $(TR $(TD $(LREF dropOne))
   86         $(TD Creates the range that results from discarding
   87         the first element from the given range.
   88     ))
   89     $(TR $(TD $(D $(LREF dropBackOne)))
   90         $(TD Creates the range that results from discarding
   91         the last element from the given range.
   92     ))
   93     $(TR $(TD $(LREF enumerate))
   94         $(TD Iterates a range with an attached index variable.
   95     ))
   96     $(TR $(TD $(LREF evenChunks))
   97         $(TD Creates a range that returns a number of chunks of
   98         approximately equal length from the original range.
   99     ))
  100     $(TR $(TD $(LREF frontTransversal))
  101         $(TD Creates a range that iterates over the first elements of the
  102         given ranges.
  103     ))
  104     $(TR $(TD $(LREF generate))
  105         $(TD Creates a range by successive calls to a given function. This
  106         allows to create ranges as a single delegate.
  107     ))
  108     $(TR $(TD $(LREF indexed))
  109         $(TD Creates a range that offers a view of a given range as though
  110         its elements were reordered according to a given range of indices.
  111     ))
  112     $(TR $(TD $(LREF iota))
  113         $(TD Creates a range consisting of numbers between a starting point
  114         and ending point, spaced apart by a given interval.
  115     ))
  116     $(TR $(TD $(LREF lockstep))
  117         $(TD Iterates $(I n) ranges in lockstep, for use in a `foreach`
  118         loop. Similar to `zip`, except that `lockstep` is designed
  119         especially for `foreach` loops.
  120     ))
  121     $(TR $(TD $(LREF nullSink))
  122         $(TD An output range that discards the data it receives.
  123     ))
  124     $(TR $(TD $(LREF only))
  125         $(TD Creates a range that iterates over the given arguments.
  126     ))
  127     $(TR $(TD $(LREF padLeft))
  128         $(TD Pads a range to a specified length by adding a given element to
  129         the front of the range. Is lazy if the range has a known length.
  130     ))
  131     $(TR $(TD $(LREF padRight))
  132         $(TD Lazily pads a range to a specified length by adding a given element to
  133         the back of the range.
  134     ))
  135     $(TR $(TD $(LREF radial))
  136         $(TD Given a random-access range and a starting point, creates a
  137         range that alternately returns the next left and next right element to
  138         the starting point.
  139     ))
  140     $(TR $(TD $(LREF recurrence))
  141         $(TD Creates a forward range whose values are defined by a
  142         mathematical recurrence relation.
  143     ))
  144     $(TR $(TD $(LREF refRange))
  145         $(TD Pass a range by reference. Both the original range and the RefRange
  146         will always have the exact same elements.
  147         Any operation done on one will affect the other.
  148     ))
  149     $(TR $(TD $(LREF repeat))
  150         $(TD Creates a range that consists of a single element repeated $(I n)
  151         times, or an infinite range repeating that element indefinitely.
  152     ))
  153     $(TR $(TD $(LREF retro))
  154         $(TD Iterates a bidirectional range backwards.
  155     ))
  156     $(TR $(TD $(LREF roundRobin))
  157         $(TD Given $(I n) ranges, creates a new range that return the $(I n)
  158         first elements of each range, in turn, then the second element of each
  159         range, and so on, in a round-robin fashion.
  160     ))
  161     $(TR $(TD $(LREF sequence))
  162         $(TD Similar to `recurrence`, except that a random-access range is
  163         created.
  164     ))
  165     $(TR $(TD $(D $(LREF slide)))
  166         $(TD Creates a range that returns a fixed-size sliding window
  167         over the original range. Unlike chunks,
  168         it advances a configurable number of items at a time,
  169         not one chunk at a time.
  170     ))
  171     $(TR $(TD $(LREF stride))
  172         $(TD Iterates a range with stride $(I n).
  173     ))
  174     $(TR $(TD $(LREF tail))
  175         $(TD Return a range advanced to within `n` elements of the end of
  176         the given range.
  177     ))
  178     $(TR $(TD $(LREF take))
  179         $(TD Creates a sub-range consisting of only up to the first $(I n)
  180         elements of the given range.
  181     ))
  182     $(TR $(TD $(LREF takeExactly))
  183         $(TD Like `take`, but assumes the given range actually has $(I n)
  184         elements, and therefore also defines the `length` property.
  185     ))
  186     $(TR $(TD $(LREF takeNone))
  187         $(TD Creates a random-access range consisting of zero elements of the
  188         given range.
  189     ))
  190     $(TR $(TD $(LREF takeOne))
  191         $(TD Creates a random-access range consisting of exactly the first
  192         element of the given range.
  193     ))
  194     $(TR $(TD $(LREF tee))
  195         $(TD Creates a range that wraps a given range, forwarding along
  196         its elements while also calling a provided function with each element.
  197     ))
  198     $(TR $(TD $(LREF transposed))
  199         $(TD Transposes a range of ranges.
  200     ))
  201     $(TR $(TD $(LREF transversal))
  202         $(TD Creates a range that iterates over the $(I n)'th elements of the
  203         given random-access ranges.
  204     ))
  205     $(TR $(TD $(LREF zip))
  206         $(TD Given $(I n) ranges, creates a range that successively returns a
  207         tuple of all the first elements, a tuple of all the second elements,
  208         etc.
  209     ))
  210 ))
  211 
  212 Sortedness:
  213 
  214 Ranges whose elements are sorted afford better efficiency with certain
  215 operations. For this, the $(LREF assumeSorted) function can be used to
  216 construct a $(LREF SortedRange) from a pre-sorted range. The $(REF
  217 sort, std, algorithm, sorting) function also conveniently
  218 returns a $(LREF SortedRange). $(LREF SortedRange) objects provide some additional
  219 range operations that take advantage of the fact that the range is sorted.
  220 
  221 Source: $(PHOBOSSRC std/range/package.d)
  222 
  223 License: $(HTTP boost.org/LICENSE_1_0.txt, Boost License 1.0).
  224 
  225 Authors: $(HTTP erdani.com, Andrei Alexandrescu), David Simcha,
  226          $(HTTP jmdavisprog.com, Jonathan M Davis), and Jack Stouffer. Credit
  227          for some of the ideas in building this module goes to
  228          $(HTTP fantascienza.net/leonardo/so/, Leonardo Maffi).
  229  */
  230 module std.range;
  231 
  232 public import std.array;
  233 public import std.range.interfaces;
  234 public import std.range.primitives;
  235 public import std.typecons : Flag, Yes, No;
  236 
  237 import std.internal.attributes : betterC;
  238 import std.meta : allSatisfy, staticMap;
  239 import std.traits : CommonType, isCallable, isFloatingPoint, isIntegral,
  240     isPointer, isSomeFunction, isStaticArray, Unqual, isInstanceOf;
  241 
  242 
  243 /**
  244 Iterates a bidirectional range backwards. The original range can be
  245 accessed by using the `source` property. Applying retro twice to
  246 the same range yields the original range.
  247 
  248 Params:
  249     r = the bidirectional range to iterate backwards
  250 
  251 Returns:
  252     A bidirectional range with length if `r` also provides a length. Or,
  253     if `r` is a random access range, then the return value will be random
  254     access as well.
  255 See_Also:
  256     $(REF reverse, std,algorithm,mutation) for mutating the source range directly.
  257  */
  258 auto retro(Range)(Range r)
  259 if (isBidirectionalRange!(Unqual!Range))
  260 {
  261     // Check for retro(retro(r)) and just return r in that case
  262     static if (is(typeof(retro(r.source)) == Range))
  263     {
  264         return r.source;
  265     }
  266     else
  267     {
  268         static struct Result()
  269         {
  270             private alias R = Unqual!Range;
  271 
  272             // User code can get and set source, too
  273             R source;
  274 
  275             static if (hasLength!R)
  276             {
  277                 size_t retroIndex(size_t n)
  278                 {
  279                     return source.length - n - 1;
  280                 }
  281             }
  282 
  283         public:
  284             alias Source = R;
  285 
  286             @property bool empty() { return source.empty; }
  287             @property auto save()
  288             {
  289                 return Result(source.save);
  290             }
  291             @property auto ref front() { return source.back; }
  292             void popFront() { source.popBack(); }
  293             @property auto ref back() { return source.front; }
  294             void popBack() { source.popFront(); }
  295 
  296             static if (is(typeof(source.moveBack())))
  297             {
  298                 ElementType!R moveFront()
  299                 {
  300                     return source.moveBack();
  301                 }
  302             }
  303 
  304             static if (is(typeof(source.moveFront())))
  305             {
  306                 ElementType!R moveBack()
  307                 {
  308                     return source.moveFront();
  309                 }
  310             }
  311 
  312             static if (hasAssignableElements!R)
  313             {
  314                 @property void front(ElementType!R val)
  315                 {
  316                     source.back = val;
  317                 }
  318 
  319                 @property void back(ElementType!R val)
  320                 {
  321                     source.front = val;
  322                 }
  323             }
  324 
  325             static if (isRandomAccessRange!(R) && hasLength!(R))
  326             {
  327                 auto ref opIndex(size_t n) { return source[retroIndex(n)]; }
  328 
  329                 static if (hasAssignableElements!R)
  330                 {
  331                     void opIndexAssign(ElementType!R val, size_t n)
  332                     {
  333                         source[retroIndex(n)] = val;
  334                     }
  335                 }
  336 
  337                 static if (is(typeof(source.moveAt(0))))
  338                 {
  339                     ElementType!R moveAt(size_t index)
  340                     {
  341                         return source.moveAt(retroIndex(index));
  342                     }
  343                 }
  344 
  345                 static if (hasSlicing!R)
  346                     typeof(this) opSlice(size_t a, size_t b)
  347                     {
  348                         return typeof(this)(source[source.length - b .. source.length - a]);
  349                     }
  350             }
  351 
  352             static if (hasLength!R)
  353             {
  354                 @property auto length()
  355                 {
  356                     return source.length;
  357                 }
  358 
  359                 alias opDollar = length;
  360             }
  361         }
  362 
  363         return Result!()(r);
  364     }
  365 }
  366 
  367 
  368 ///
  369 pure @safe nothrow @nogc unittest
  370 {
  371     import std.algorithm.comparison : equal;
  372     int[5] a = [ 1, 2, 3, 4, 5 ];
  373     int[5] b = [ 5, 4, 3, 2, 1 ];
  374     assert(equal(retro(a[]), b[]));
  375     assert(retro(a[]).source is a[]);
  376     assert(retro(retro(a[])) is a[]);
  377 }
  378 
  379 pure @safe nothrow unittest
  380 {
  381     import std.algorithm.comparison : equal;
  382     static assert(isBidirectionalRange!(typeof(retro("hello"))));
  383     int[] a;
  384     static assert(is(typeof(a) == typeof(retro(retro(a)))));
  385     assert(retro(retro(a)) is a);
  386     static assert(isRandomAccessRange!(typeof(retro([1, 2, 3]))));
  387     void test(int[] input, int[] witness)
  388     {
  389         auto r = retro(input);
  390         assert(r.front == witness.front);
  391         assert(r.back == witness.back);
  392         assert(equal(r, witness));
  393     }
  394     test([ 1 ], [ 1 ]);
  395     test([ 1, 2 ], [ 2, 1 ]);
  396     test([ 1, 2, 3 ], [ 3, 2, 1 ]);
  397     test([ 1, 2, 3, 4 ], [ 4, 3, 2, 1 ]);
  398     test([ 1, 2, 3, 4, 5 ], [ 5, 4, 3, 2, 1 ]);
  399     test([ 1, 2, 3, 4, 5, 6 ], [ 6, 5, 4, 3, 2, 1 ]);
  400 
  401     immutable foo = [1,2,3].idup;
  402     auto r = retro(foo);
  403     assert(equal(r, [3, 2, 1]));
  404 }
  405 
  406 pure @safe nothrow unittest
  407 {
  408     import std.internal.test.dummyrange : AllDummyRanges, propagatesRangeType,
  409         ReturnBy;
  410 
  411     foreach (DummyType; AllDummyRanges)
  412     {
  413         static if (!isBidirectionalRange!DummyType)
  414         {
  415             static assert(!__traits(compiles, Retro!DummyType));
  416         }
  417         else
  418         {
  419             DummyType dummyRange;
  420             dummyRange.reinit();
  421 
  422             auto myRetro = retro(dummyRange);
  423             static assert(propagatesRangeType!(typeof(myRetro), DummyType));
  424             assert(myRetro.front == 10);
  425             assert(myRetro.back == 1);
  426             assert(myRetro.moveFront() == 10);
  427             assert(myRetro.moveBack() == 1);
  428 
  429             static if (isRandomAccessRange!DummyType && hasLength!DummyType)
  430             {
  431                 assert(myRetro[0] == myRetro.front);
  432                 assert(myRetro.moveAt(2) == 8);
  433 
  434                 static if (DummyType.r == ReturnBy.Reference)
  435                 {
  436                     {
  437                         myRetro[9]++;
  438                         scope(exit) myRetro[9]--;
  439                         assert(dummyRange[0] == 2);
  440                         myRetro.front++;
  441                         scope(exit) myRetro.front--;
  442                         assert(myRetro.front == 11);
  443                         myRetro.back++;
  444                         scope(exit) myRetro.back--;
  445                         assert(myRetro.back == 3);
  446                     }
  447 
  448                     {
  449                         myRetro.front = 0xFF;
  450                         scope(exit) myRetro.front = 10;
  451                         assert(dummyRange.back == 0xFF);
  452 
  453                         myRetro.back = 0xBB;
  454                         scope(exit) myRetro.back = 1;
  455                         assert(dummyRange.front == 0xBB);
  456 
  457                         myRetro[1] = 11;
  458                         scope(exit) myRetro[1] = 8;
  459                         assert(dummyRange[8] == 11);
  460                     }
  461                 }
  462             }
  463         }
  464     }
  465 }
  466 
  467 pure @safe nothrow @nogc unittest
  468 {
  469     import std.algorithm.comparison : equal;
  470     auto LL = iota(1L, 4L);
  471     auto r = retro(LL);
  472     long[3] excepted = [3, 2, 1];
  473     assert(equal(r, excepted[]));
  474 }
  475 
  476 // https://issues.dlang.org/show_bug.cgi?id=12662
  477 pure @safe nothrow @nogc unittest
  478 {
  479     int[3] src = [1,2,3];
  480     int[] data = src[];
  481     foreach_reverse (x; data) {}
  482     foreach (x; data.retro) {}
  483 }
  484 
  485 
  486 /**
  487 Iterates range `r` with stride `n`. If the range is a
  488 random-access range, moves by indexing into the range; otherwise,
  489 moves by successive calls to `popFront`. Applying stride twice to
  490 the same range results in a stride with a step that is the
  491 product of the two applications. It is an error for `n` to be 0.
  492 
  493 Params:
  494     r = the $(REF_ALTTEXT input range, isInputRange, std,range,primitives) to stride over
  495     n = the number of elements to skip over
  496 
  497 Returns:
  498     At minimum, an input range. The resulting range will adopt the
  499     range primitives of the underlying range as long as
  500     $(REF hasLength, std,range,primitives) is `true`.
  501  */
  502 auto stride(Range)(Range r, size_t n)
  503 if (isInputRange!(Unqual!Range))
  504 in
  505 {
  506     assert(n != 0, "stride cannot have step zero.");
  507 }
  508 do
  509 {
  510     import std.algorithm.comparison : min;
  511 
  512     static if (is(typeof(stride(r.source, n)) == Range))
  513     {
  514         // stride(stride(r, n1), n2) is stride(r, n1 * n2)
  515         return stride(r.source, r._n * n);
  516     }
  517     else
  518     {
  519         static struct Result
  520         {
  521             private alias R = Unqual!Range;
  522             public R source;
  523             private size_t _n;
  524 
  525             // Chop off the slack elements at the end
  526             static if (hasLength!R &&
  527                     (isRandomAccessRange!R && hasSlicing!R
  528                             || isBidirectionalRange!R))
  529                 private void eliminateSlackElements()
  530                 {
  531                     auto slack = source.length % _n;
  532 
  533                     if (slack)
  534                     {
  535                         slack--;
  536                     }
  537                     else if (!source.empty)
  538                     {
  539                         slack = min(_n, source.length) - 1;
  540                     }
  541                     else
  542                     {
  543                         slack = 0;
  544                     }
  545                     if (!slack) return;
  546                     static if (isRandomAccessRange!R && hasLength!R && hasSlicing!R)
  547                     {
  548                         source = source[0 .. source.length - slack];
  549                     }
  550                     else static if (isBidirectionalRange!R)
  551                     {
  552                         foreach (i; 0 .. slack)
  553                         {
  554                             source.popBack();
  555                         }
  556                     }
  557                 }
  558 
  559             static if (isForwardRange!R)
  560             {
  561                 @property auto save()
  562                 {
  563                     return Result(source.save, _n);
  564                 }
  565             }
  566 
  567             static if (isInfinite!R)
  568             {
  569                 enum bool empty = false;
  570             }
  571             else
  572             {
  573                 @property bool empty()
  574                 {
  575                     return source.empty;
  576                 }
  577             }
  578 
  579             @property auto ref front()
  580             {
  581                 return source.front;
  582             }
  583 
  584             static if (is(typeof(.moveFront(source))))
  585             {
  586                 ElementType!R moveFront()
  587                 {
  588                     return source.moveFront();
  589                 }
  590             }
  591 
  592             static if (hasAssignableElements!R)
  593             {
  594                 @property void front(ElementType!R val)
  595                 {
  596                     source.front = val;
  597                 }
  598             }
  599 
  600             void popFront()
  601             {
  602                 source.popFrontN(_n);
  603             }
  604 
  605             static if (isBidirectionalRange!R && hasLength!R)
  606             {
  607                 void popBack()
  608                 {
  609                     popBackN(source, _n);
  610                 }
  611 
  612                 @property auto ref back()
  613                 {
  614                     eliminateSlackElements();
  615                     return source.back;
  616                 }
  617 
  618                 static if (is(typeof(.moveBack(source))))
  619                 {
  620                     ElementType!R moveBack()
  621                     {
  622                         eliminateSlackElements();
  623                         return source.moveBack();
  624                     }
  625                 }
  626 
  627                 static if (hasAssignableElements!R)
  628                 {
  629                     @property void back(ElementType!R val)
  630                     {
  631                         eliminateSlackElements();
  632                         source.back = val;
  633                     }
  634                 }
  635             }
  636 
  637             static if (isRandomAccessRange!R && hasLength!R)
  638             {
  639                 auto ref opIndex(size_t n)
  640                 {
  641                     return source[_n * n];
  642                 }
  643 
  644                 /**
  645                    Forwards to $(D moveAt(source, n)).
  646                 */
  647                 static if (is(typeof(source.moveAt(0))))
  648                 {
  649                     ElementType!R moveAt(size_t n)
  650                     {
  651                         return source.moveAt(_n * n);
  652                     }
  653                 }
  654 
  655                 static if (hasAssignableElements!R)
  656                 {
  657                     void opIndexAssign(ElementType!R val, size_t n)
  658                     {
  659                         source[_n * n] = val;
  660                     }
  661                 }
  662             }
  663 
  664             static if (hasSlicing!R && hasLength!R)
  665                 typeof(this) opSlice(size_t lower, size_t upper)
  666                 {
  667                     assert(upper >= lower && upper <= length);
  668                     immutable translatedUpper = (upper == 0) ? 0 :
  669                         (upper * _n - (_n - 1));
  670                     immutable translatedLower = min(lower * _n, translatedUpper);
  671 
  672                     assert(translatedLower <= translatedUpper);
  673 
  674                     return typeof(this)(source[translatedLower .. translatedUpper], _n);
  675                 }
  676 
  677             static if (hasLength!R)
  678             {
  679                 @property auto length()
  680                 {
  681                     return (source.length + _n - 1) / _n;
  682                 }
  683 
  684                 alias opDollar = length;
  685             }
  686         }
  687         return Result(r, n);
  688     }
  689 }
  690 
  691 ///
  692 pure @safe nothrow unittest
  693 {
  694     import std.algorithm.comparison : equal;
  695 
  696     int[] a = [ 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11 ];
  697     assert(equal(stride(a, 3), [ 1, 4, 7, 10 ][]));
  698     assert(stride(stride(a, 2), 3) == stride(a, 6));
  699 }
  700 
  701 pure @safe nothrow @nogc unittest
  702 {
  703     import std.algorithm.comparison : equal;
  704 
  705     int[4] testArr = [1,2,3,4];
  706     static immutable result = [1, 3];
  707     assert(equal(testArr[].stride(2), result));
  708 }
  709 
  710 debug pure nothrow @system unittest
  711 {//check the contract
  712     int[4] testArr = [1,2,3,4];
  713     bool passed = false;
  714     scope (success) assert(passed);
  715     import core.exception : AssertError;
  716     //std.exception.assertThrown won't do because it can't infer nothrow
  717     // https://issues.dlang.org/show_bug.cgi?id=12647
  718     try
  719     {
  720         auto unused = testArr[].stride(0);
  721     }
  722     catch (AssertError unused)
  723     {
  724         passed = true;
  725     }
  726 }
  727 
  728 pure @safe nothrow unittest
  729 {
  730     import std.algorithm.comparison : equal;
  731     import std.internal.test.dummyrange : AllDummyRanges, propagatesRangeType,
  732         ReturnBy;
  733 
  734     static assert(isRandomAccessRange!(typeof(stride([1, 2, 3], 2))));
  735     void test(size_t n, int[] input, int[] witness)
  736     {
  737         assert(equal(stride(input, n), witness));
  738     }
  739     test(1, [], []);
  740     int[] arr = [ 1, 2, 3, 4, 5, 6, 7, 8, 9, 10 ];
  741     assert(stride(stride(arr, 2), 3) is stride(arr, 6));
  742     test(1, arr, arr);
  743     test(2, arr, [1, 3, 5, 7, 9]);
  744     test(3, arr, [1, 4, 7, 10]);
  745     test(4, arr, [1, 5, 9]);
  746 
  747     // Test slicing.
  748     auto s1 = stride(arr, 1);
  749     assert(equal(s1[1 .. 4], [2, 3, 4]));
  750     assert(s1[1 .. 4].length == 3);
  751     assert(equal(s1[1 .. 5], [2, 3, 4, 5]));
  752     assert(s1[1 .. 5].length == 4);
  753     assert(s1[0 .. 0].empty);
  754     assert(s1[3 .. 3].empty);
  755     // assert(s1[$ .. $].empty);
  756     assert(s1[s1.opDollar .. s1.opDollar].empty);
  757 
  758     auto s2 = stride(arr, 2);
  759     assert(equal(s2[0 .. 2], [1,3]));
  760     assert(s2[0 .. 2].length == 2);
  761     assert(equal(s2[1 .. 5], [3, 5, 7, 9]));
  762     assert(s2[1 .. 5].length == 4);
  763     assert(s2[0 .. 0].empty);
  764     assert(s2[3 .. 3].empty);
  765     // assert(s2[$ .. $].empty);
  766     assert(s2[s2.opDollar .. s2.opDollar].empty);
  767 
  768     // Test fix for https://issues.dlang.org/show_bug.cgi?id=5035
  769     auto m = [1, 2, 3, 4, 1, 2, 3, 4, 1, 2, 3, 4]; // 3 rows, 4 columns
  770     auto col = stride(m, 4);
  771     assert(equal(col, [1, 1, 1]));
  772     assert(equal(retro(col), [1, 1, 1]));
  773 
  774     immutable int[] immi = [ 1, 2, 3 ];
  775     static assert(isRandomAccessRange!(typeof(stride(immi, 1))));
  776 
  777     // Check for infiniteness propagation.
  778     static assert(isInfinite!(typeof(stride(repeat(1), 3))));
  779 
  780     foreach (DummyType; AllDummyRanges)
  781     {
  782         DummyType dummyRange;
  783         dummyRange.reinit();
  784 
  785         auto myStride = stride(dummyRange, 4);
  786 
  787         // Should fail if no length and bidirectional b/c there's no way
  788         // to know how much slack we have.
  789         static if (hasLength!DummyType || !isBidirectionalRange!DummyType)
  790         {
  791             static assert(propagatesRangeType!(typeof(myStride), DummyType));
  792         }
  793         assert(myStride.front == 1);
  794         assert(myStride.moveFront() == 1);
  795         assert(equal(myStride, [1, 5, 9]));
  796 
  797         static if (hasLength!DummyType)
  798         {
  799             assert(myStride.length == 3);
  800         }
  801 
  802         static if (isBidirectionalRange!DummyType && hasLength!DummyType)
  803         {
  804             assert(myStride.back == 9);
  805             assert(myStride.moveBack() == 9);
  806         }
  807 
  808         static if (isRandomAccessRange!DummyType && hasLength!DummyType)
  809         {
  810             assert(myStride[0] == 1);
  811             assert(myStride[1] == 5);
  812             assert(myStride.moveAt(1) == 5);
  813             assert(myStride[2] == 9);
  814 
  815             static assert(hasSlicing!(typeof(myStride)));
  816         }
  817 
  818         static if (DummyType.r == ReturnBy.Reference)
  819         {
  820             // Make sure reference is propagated.
  821 
  822             {
  823                 myStride.front++;
  824                 scope(exit) myStride.front--;
  825                 assert(dummyRange.front == 2);
  826             }
  827             {
  828                 myStride.front = 4;
  829                 scope(exit) myStride.front = 1;
  830                 assert(dummyRange.front == 4);
  831             }
  832 
  833             static if (isBidirectionalRange!DummyType && hasLength!DummyType)
  834             {
  835                 {
  836                     myStride.back++;
  837                     scope(exit) myStride.back--;
  838                     assert(myStride.back == 10);
  839                 }
  840                 {
  841                     myStride.back = 111;
  842                     scope(exit) myStride.back = 9;
  843                     assert(myStride.back == 111);
  844                 }
  845 
  846                 static if (isRandomAccessRange!DummyType)
  847                 {
  848                     {
  849                         myStride[1]++;
  850                         scope(exit) myStride[1]--;
  851                         assert(dummyRange[4] == 6);
  852                     }
  853                     {
  854                         myStride[1] = 55;
  855                         scope(exit) myStride[1] = 5;
  856                         assert(dummyRange[4] == 55);
  857                     }
  858                 }
  859             }
  860         }
  861     }
  862 }
  863 
  864 pure @safe nothrow unittest
  865 {
  866     import std.algorithm.comparison : equal;
  867 
  868     auto LL = iota(1L, 10L);
  869     auto s = stride(LL, 3);
  870     assert(equal(s, [1L, 4L, 7L]));
  871 }
  872 
  873 /**
  874 Spans multiple ranges in sequence. The function `chain` takes any
  875 number of ranges and returns a $(D Chain!(R1, R2,...)) object. The
  876 ranges may be different, but they must have the same element type. The
  877 result is a range that offers the `front`, `popFront`, and $(D
  878 empty) primitives. If all input ranges offer random access and $(D
  879 length), `Chain` offers them as well.
  880 
  881 If only one range is offered to `Chain` or `chain`, the $(D
  882 Chain) type exits the picture by aliasing itself directly to that
  883 range's type.
  884 
  885 Params:
  886     rs = the $(REF_ALTTEXT input ranges, isInputRange, std,range,primitives) to chain together
  887 
  888 Returns:
  889     An input range at minimum. If all of the ranges in `rs` provide
  890     a range primitive, the returned range will also provide that range
  891     primitive.
  892 
  893 See_Also: $(LREF only) to chain values to a range
  894  */
  895 auto chain(Ranges...)(Ranges rs)
  896 if (Ranges.length > 0 &&
  897     allSatisfy!(isInputRange, staticMap!(Unqual, Ranges)) &&
  898     !is(CommonType!(staticMap!(ElementType, staticMap!(Unqual, Ranges))) == void))
  899 {
  900     static if (Ranges.length == 1)
  901     {
  902         return rs[0];
  903     }
  904     else
  905     {
  906         static struct Result
  907         {
  908         private:
  909             alias R = staticMap!(Unqual, Ranges);
  910             alias RvalueElementType = CommonType!(staticMap!(.ElementType, R));
  911             private template sameET(A)
  912             {
  913                 enum sameET = is(.ElementType!A == RvalueElementType);
  914             }
  915 
  916             enum bool allSameType = allSatisfy!(sameET, R);
  917             alias ElementType = RvalueElementType;
  918 
  919             static if (allSameType && allSatisfy!(hasLvalueElements, R))
  920             {
  921                 static ref RvalueElementType fixRef(ref RvalueElementType val)
  922                 {
  923                     return val;
  924                 }
  925             }
  926             else
  927             {
  928                 static RvalueElementType fixRef(RvalueElementType val)
  929                 {
  930                     return val;
  931                 }
  932             }
  933 
  934             // This is the entire state
  935             R source;
  936             // TODO: use a vtable (or more) instead of linear iteration
  937 
  938         public:
  939             this(R input)
  940             {
  941                 foreach (i, v; input)
  942                 {
  943                     source[i] = v;
  944                 }
  945             }
  946 
  947             import std.meta : anySatisfy;
  948 
  949             static if (anySatisfy!(isInfinite, R))
  950             {
  951                 // Propagate infiniteness.
  952                 enum bool empty = false;
  953             }
  954             else
  955             {
  956                 @property bool empty()
  957                 {
  958                     foreach (i, Unused; R)
  959                     {
  960                         if (!source[i].empty) return false;
  961                     }
  962                     return true;
  963                 }
  964             }
  965 
  966             static if (allSatisfy!(isForwardRange, R))
  967                 @property auto save()
  968                 {
  969                     auto saveSource(size_t len)()
  970                     {
  971                         import std.typecons : tuple;
  972                         static assert(len > 0);
  973                         static if (len == 1)
  974                         {
  975                             return tuple(source[0].save);
  976                         }
  977                         else
  978                         {
  979                             return saveSource!(len - 1)() ~
  980                                 tuple(source[len - 1].save);
  981                         }
  982                     }
  983                     return Result(saveSource!(R.length).expand);
  984                 }
  985 
  986             void popFront()
  987             {
  988                 foreach (i, Unused; R)
  989                 {
  990                     if (source[i].empty) continue;
  991                     source[i].popFront();
  992                     return;
  993                 }
  994             }
  995 
  996             @property auto ref front()
  997             {
  998                 foreach (i, Unused; R)
  999                 {
 1000                     if (source[i].empty) continue;
 1001                     return fixRef(source[i].front);
 1002                 }
 1003                 assert(false);
 1004             }
 1005 
 1006             static if (allSameType && allSatisfy!(hasAssignableElements, R))
 1007             {
 1008                 // @@@BUG@@@
 1009                 //@property void front(T)(T v) if (is(T : RvalueElementType))
 1010 
 1011                 @property void front(RvalueElementType v)
 1012                 {
 1013                     foreach (i, Unused; R)
 1014                     {
 1015                         if (source[i].empty) continue;
 1016                         source[i].front = v;
 1017                         return;
 1018                     }
 1019                     assert(false);
 1020                 }
 1021             }
 1022 
 1023             static if (allSatisfy!(hasMobileElements, R))
 1024             {
 1025                 RvalueElementType moveFront()
 1026                 {
 1027                     foreach (i, Unused; R)
 1028                     {
 1029                         if (source[i].empty) continue;
 1030                         return source[i].moveFront();
 1031                     }
 1032                     assert(false);
 1033                 }
 1034             }
 1035 
 1036             static if (allSatisfy!(isBidirectionalRange, R))
 1037             {
 1038                 @property auto ref back()
 1039                 {
 1040                     foreach_reverse (i, Unused; R)
 1041                     {
 1042                         if (source[i].empty) continue;
 1043                         return fixRef(source[i].back);
 1044                     }
 1045                     assert(false);
 1046                 }
 1047 
 1048                 void popBack()
 1049                 {
 1050                     foreach_reverse (i, Unused; R)
 1051                     {
 1052                         if (source[i].empty) continue;
 1053                         source[i].popBack();
 1054                         return;
 1055                     }
 1056                 }
 1057 
 1058                 static if (allSatisfy!(hasMobileElements, R))
 1059                 {
 1060                     RvalueElementType moveBack()
 1061                     {
 1062                         foreach_reverse (i, Unused; R)
 1063                         {
 1064                             if (source[i].empty) continue;
 1065                             return source[i].moveBack();
 1066                         }
 1067                         assert(false);
 1068                     }
 1069                 }
 1070 
 1071                 static if (allSameType && allSatisfy!(hasAssignableElements, R))
 1072                 {
 1073                     @property void back(RvalueElementType v)
 1074                     {
 1075                         foreach_reverse (i, Unused; R)
 1076                         {
 1077                             if (source[i].empty) continue;
 1078                             source[i].back = v;
 1079                             return;
 1080                         }
 1081                         assert(false);
 1082                     }
 1083                 }
 1084             }
 1085 
 1086             static if (allSatisfy!(hasLength, R))
 1087             {
 1088                 @property size_t length()
 1089                 {
 1090                     size_t result;
 1091                     foreach (i, Unused; R)
 1092                     {
 1093                         result += source[i].length;
 1094                     }
 1095                     return result;
 1096                 }
 1097 
 1098                 alias opDollar = length;
 1099             }
 1100 
 1101             static if (allSatisfy!(isRandomAccessRange, R))
 1102             {
 1103                 auto ref opIndex(size_t index)
 1104                 {
 1105                     foreach (i, Range; R)
 1106                     {
 1107                         static if (isInfinite!(Range))
 1108                         {
 1109                             return source[i][index];
 1110                         }
 1111                         else
 1112                         {
 1113                             immutable length = source[i].length;
 1114                             if (index < length) return fixRef(source[i][index]);
 1115                             index -= length;
 1116                         }
 1117                     }
 1118                     assert(false);
 1119                 }
 1120 
 1121                 static if (allSatisfy!(hasMobileElements, R))
 1122                 {
 1123                     RvalueElementType moveAt(size_t index)
 1124                     {
 1125                         foreach (i, Range; R)
 1126                         {
 1127                             static if (isInfinite!(Range))
 1128                             {
 1129                                 return source[i].moveAt(index);
 1130                             }
 1131                             else
 1132                             {
 1133                                 immutable length = source[i].length;
 1134                                 if (index < length) return source[i].moveAt(index);
 1135                                 index -= length;
 1136                             }
 1137                         }
 1138                         assert(false);
 1139                     }
 1140                 }
 1141 
 1142                 static if (allSameType && allSatisfy!(hasAssignableElements, R))
 1143                     void opIndexAssign(ElementType v, size_t index)
 1144                     {
 1145                         foreach (i, Range; R)
 1146                         {
 1147                             static if (isInfinite!(Range))
 1148                             {
 1149                                 source[i][index] = v;
 1150                             }
 1151                             else
 1152                             {
 1153                                 immutable length = source[i].length;
 1154                                 if (index < length)
 1155                                 {
 1156                                     source[i][index] = v;
 1157                                     return;
 1158                                 }
 1159                                 index -= length;
 1160                             }
 1161                         }
 1162                         assert(false);
 1163                     }
 1164             }
 1165 
 1166             static if (allSatisfy!(hasLength, R) && allSatisfy!(hasSlicing, R))
 1167                 auto opSlice(size_t begin, size_t end) return scope
 1168                 {
 1169                     auto result = this;
 1170                     foreach (i, Unused; R)
 1171                     {
 1172                         immutable len = result.source[i].length;
 1173                         if (len < begin)
 1174                         {
 1175                             result.source[i] = result.source[i]
 1176                                 [len .. len];
 1177                             begin -= len;
 1178                         }
 1179                         else
 1180                         {
 1181                             result.source[i] = result.source[i]
 1182                                 [begin .. len];
 1183                             break;
 1184                         }
 1185                     }
 1186                     auto cut = length;
 1187                     cut = cut <= end ? 0 : cut - end;
 1188                     foreach_reverse (i, Unused; R)
 1189                     {
 1190                         immutable len = result.source[i].length;
 1191                         if (cut > len)
 1192                         {
 1193                             result.source[i] = result.source[i]
 1194                                 [0 .. 0];
 1195                             cut -= len;
 1196                         }
 1197                         else
 1198                         {
 1199                             result.source[i] = result.source[i]
 1200                                 [0 .. len - cut];
 1201                             break;
 1202                         }
 1203                     }
 1204                     return result;
 1205                 }
 1206         }
 1207         return Result(rs);
 1208     }
 1209 }
 1210 
 1211 ///
 1212 pure @safe nothrow unittest
 1213 {
 1214     import std.algorithm.comparison : equal;
 1215 
 1216     int[] arr1 = [ 1, 2, 3, 4 ];
 1217     int[] arr2 = [ 5, 6 ];
 1218     int[] arr3 = [ 7 ];
 1219     auto s = chain(arr1, arr2, arr3);
 1220     assert(s.length == 7);
 1221     assert(s[5] == 6);
 1222     assert(equal(s, [1, 2, 3, 4, 5, 6, 7][]));
 1223 }
 1224 
 1225 /**
 1226  * Range primitives are carried over to the returned range if
 1227  * all of the ranges provide them
 1228  */
 1229 pure @safe nothrow unittest
 1230 {
 1231     import std.algorithm.comparison : equal;
 1232     import std.algorithm.sorting : sort;
 1233 
 1234     int[] arr1 = [5, 2, 8];
 1235     int[] arr2 = [3, 7, 9];
 1236     int[] arr3 = [1, 4, 6];
 1237 
 1238     // in-place sorting across all of the arrays
 1239     auto s = arr1.chain(arr2, arr3).sort;
 1240 
 1241     assert(s.equal([1, 2, 3, 4, 5, 6, 7, 8, 9]));
 1242     assert(arr1.equal([1, 2, 3]));
 1243     assert(arr2.equal([4, 5, 6]));
 1244     assert(arr3.equal([7, 8, 9]));
 1245 }
 1246 
 1247 /**
 1248 Due to safe type promotion in D, chaining together different
 1249 character ranges results in a `uint` range.
 1250 
 1251 Use $(REF_ALTTEXT byChar, byChar,std,utf), $(REF_ALTTEXT byWchar, byWchar,std,utf),
 1252 and $(REF_ALTTEXT byDchar, byDchar,std,utf) on the ranges
 1253 to get the type you need.
 1254  */
 1255 pure @safe nothrow unittest
 1256 {
 1257     import std.utf : byChar, byCodeUnit;
 1258 
 1259     auto s1 = "string one";
 1260     auto s2 = "string two";
 1261     // s1 and s2 front is dchar because of auto-decoding
 1262     static assert(is(typeof(s1.front) == dchar) && is(typeof(s2.front) == dchar));
 1263 
 1264     auto r1 = s1.chain(s2);
 1265     // chains of ranges of the same character type give that same type
 1266     static assert(is(typeof(r1.front) == dchar));
 1267 
 1268     auto s3 = "string three".byCodeUnit;
 1269     static assert(is(typeof(s3.front) == immutable char));
 1270     auto r2 = s1.chain(s3);
 1271     // chaining ranges of mixed character types gives `dchar`
 1272     static assert(is(typeof(r2.front) == dchar));
 1273 
 1274     // use byChar on character ranges to correctly convert them to UTF-8
 1275     auto r3 = s1.byChar.chain(s3);
 1276     static assert(is(typeof(r3.front) == immutable char));
 1277 }
 1278 
 1279 pure @safe nothrow unittest
 1280 {
 1281     import std.algorithm.comparison : equal;
 1282     import std.internal.test.dummyrange : AllDummyRanges, dummyLength,
 1283                                           propagatesRangeType;
 1284 
 1285     {
 1286         int[] arr1 = [ 1, 2, 3, 4 ];
 1287         int[] arr2 = [ 5, 6 ];
 1288         int[] arr3 = [ 7 ];
 1289         int[] witness = [ 1, 2, 3, 4, 5, 6, 7 ];
 1290         auto s1 = chain(arr1);
 1291         static assert(isRandomAccessRange!(typeof(s1)));
 1292         auto s2 = chain(arr1, arr2);
 1293         static assert(isBidirectionalRange!(typeof(s2)));
 1294         static assert(isRandomAccessRange!(typeof(s2)));
 1295         s2.front = 1;
 1296         auto s = chain(arr1, arr2, arr3);
 1297         assert(s[5] == 6);
 1298         assert(equal(s, witness));
 1299         assert(s[5] == 6);
 1300     }
 1301     {
 1302         int[] arr1 = [ 1, 2, 3, 4 ];
 1303         int[] witness = [ 1, 2, 3, 4 ];
 1304         assert(equal(chain(arr1), witness));
 1305     }
 1306     {
 1307         uint[] foo = [1,2,3,4,5];
 1308         uint[] bar = [1,2,3,4,5];
 1309         auto c = chain(foo, bar);
 1310         c[3] = 42;
 1311         assert(c[3] == 42);
 1312         assert(c.moveFront() == 1);
 1313         assert(c.moveBack() == 5);
 1314         assert(c.moveAt(4) == 5);
 1315         assert(c.moveAt(5) == 1);
 1316     }
 1317 
 1318 
 1319     // Make sure https://issues.dlang.org/show_bug.cgi?id=3311 is fixed.
 1320     // elements are mutable.
 1321     assert(equal(chain(iota(0, 3), iota(0, 3)), [0, 1, 2, 0, 1, 2]));
 1322 
 1323     // Test the case where infinite ranges are present.
 1324     auto inf = chain([0,1,2][], cycle([4,5,6][]), [7,8,9][]); // infinite range
 1325     assert(inf[0] == 0);
 1326     assert(inf[3] == 4);
 1327     assert(inf[6] == 4);
 1328     assert(inf[7] == 5);
 1329     static assert(isInfinite!(typeof(inf)));
 1330 
 1331     immutable int[] immi = [ 1, 2, 3 ];
 1332     immutable float[] immf = [ 1, 2, 3 ];
 1333     static assert(is(typeof(chain(immi, immf))));
 1334 
 1335     // Check that chain at least instantiates and compiles with every possible
 1336     // pair of DummyRange types, in either order.
 1337 
 1338     foreach (DummyType1; AllDummyRanges)
 1339     (){ // workaround slow optimizations for large functions
 1340         // https://issues.dlang.org/show_bug.cgi?id=2396
 1341         DummyType1 dummy1;
 1342         foreach (DummyType2; AllDummyRanges)
 1343         {
 1344             DummyType2 dummy2;
 1345             auto myChain = chain(dummy1, dummy2);
 1346 
 1347             static assert(
 1348                 propagatesRangeType!(typeof(myChain), DummyType1, DummyType2)
 1349             );
 1350 
 1351             assert(myChain.front == 1);
 1352             foreach (i; 0 .. dummyLength)
 1353             {
 1354                 myChain.popFront();
 1355             }
 1356             assert(myChain.front == 1);
 1357 
 1358             static if (isBidirectionalRange!DummyType1 &&
 1359                       isBidirectionalRange!DummyType2) {
 1360                 assert(myChain.back == 10);
 1361             }
 1362 
 1363             static if (isRandomAccessRange!DummyType1 &&
 1364                       isRandomAccessRange!DummyType2) {
 1365                 assert(myChain[0] == 1);
 1366             }
 1367 
 1368             static if (hasLvalueElements!DummyType1 && hasLvalueElements!DummyType2)
 1369             {
 1370                 static assert(hasLvalueElements!(typeof(myChain)));
 1371             }
 1372             else
 1373             {
 1374                 static assert(!hasLvalueElements!(typeof(myChain)));
 1375             }
 1376         }
 1377     }();
 1378 }
 1379 
 1380 pure @safe nothrow @nogc unittest
 1381 {
 1382     class Foo{}
 1383     immutable(Foo)[] a;
 1384     immutable(Foo)[] b;
 1385     assert(chain(a, b).empty);
 1386 }
 1387 
 1388 // https://issues.dlang.org/show_bug.cgi?id=18657
 1389 pure @safe unittest
 1390 {
 1391     import std.algorithm.comparison : equal;
 1392     string s = "foo";
 1393     auto r = refRange(&s).chain("bar");
 1394     assert(equal(r.save, "foobar"));
 1395     assert(equal(r, "foobar"));
 1396 }
 1397 
 1398 /**
 1399 Choose one of two ranges at runtime depending on a Boolean condition.
 1400 
 1401 The ranges may be different, but they must have compatible element types (i.e.
 1402 `CommonType` must exist for the two element types). The result is a range
 1403 that offers the weakest capabilities of the two (e.g. `ForwardRange` if $(D
 1404 R1) is a random-access range and `R2` is a forward range).
 1405 
 1406 Params:
 1407     condition = which range to choose: `r1` if `true`, `r2` otherwise
 1408     r1 = the "true" range
 1409     r2 = the "false" range
 1410 
 1411 Returns:
 1412     A range type dependent on `R1` and `R2`.
 1413  */
 1414 auto choose(R1, R2)(bool condition, return scope R1 r1, return scope R2 r2)
 1415 if (isInputRange!(Unqual!R1) && isInputRange!(Unqual!R2) &&
 1416     !is(CommonType!(ElementType!(Unqual!R1), ElementType!(Unqual!R2)) == void))
 1417 {
 1418     return ChooseResult!(R1, R2)(condition, r1, r2);
 1419 }
 1420 
 1421 ///
 1422 @safe nothrow pure @nogc unittest
 1423 {
 1424     import std.algorithm.comparison : equal;
 1425     import std.algorithm.iteration : filter, map;
 1426 
 1427     auto data1 = only(1, 2, 3, 4).filter!(a => a != 3);
 1428     auto data2 = only(5, 6, 7, 8).map!(a => a + 1);
 1429 
 1430     // choose() is primarily useful when you need to select one of two ranges
 1431     // with different types at runtime.
 1432     static assert(!is(typeof(data1) == typeof(data2)));
 1433 
 1434     auto chooseRange(bool pickFirst)
 1435     {
 1436         // The returned range is a common wrapper type that can be used for
 1437         // returning or storing either range without running into a type error.
 1438         return choose(pickFirst, data1, data2);
 1439 
 1440         // Simply returning the chosen range without using choose() does not
 1441         // work, because map() and filter() return different types.
 1442         //return pickFirst ? data1 : data2; // does not compile
 1443     }
 1444 
 1445     auto result = chooseRange(true);
 1446     assert(result.equal(only(1, 2, 4)));
 1447 
 1448     result = chooseRange(false);
 1449     assert(result.equal(only(6, 7, 8, 9)));
 1450 }
 1451 
 1452 
 1453 private struct ChooseResult(R1, R2)
 1454 {
 1455     import std.traits : hasElaborateCopyConstructor, hasElaborateDestructor;
 1456 
 1457     private union
 1458     {
 1459         R1 r1;
 1460         R2 r2;
 1461     }
 1462     private bool r1Chosen;
 1463 
 1464     private static auto ref actOnChosen(alias foo, ExtraArgs ...)(ref ChooseResult r,
 1465             auto ref ExtraArgs extraArgs)
 1466     {
 1467         if (r.r1Chosen)
 1468         {
 1469             ref get1(return ref ChooseResult r) @trusted { return r.r1; }
 1470             return foo(get1(r), extraArgs);
 1471         }
 1472         else
 1473         {
 1474             ref get2(return ref ChooseResult r) @trusted { return r.r2; }
 1475             return foo(get2(r), extraArgs);
 1476         }
 1477     }
 1478 
 1479     this(bool r1Chosen, return scope R1 r1, return scope R2 r2) @trusted
 1480     {
 1481         // @trusted because of assignment of r1 and r2 which overlap each other
 1482         import std.conv : emplace;
 1483 
 1484         // This should be the only place r1Chosen is ever assigned
 1485         // independently
 1486         this.r1Chosen = r1Chosen;
 1487         if (r1Chosen)
 1488         {
 1489             this.r2 = R2.init;
 1490             emplace(&this.r1, r1);
 1491         }
 1492         else
 1493         {
 1494             this.r1 = R1.init;
 1495             emplace(&this.r2, r2);
 1496         }
 1497     }
 1498 
 1499     void opAssign(ChooseResult r)
 1500     {
 1501         static if (hasElaborateDestructor!R1 || hasElaborateDestructor!R2)
 1502             if (r1Chosen != r.r1Chosen)
 1503             {
 1504                 // destroy the current item
 1505                 actOnChosen!((ref r) => destroy(r))(this);
 1506             }
 1507         r1Chosen = r.r1Chosen;
 1508         if (r1Chosen)
 1509         {
 1510             ref get1(return ref ChooseResult r) @trusted { return r.r1; }
 1511             get1(this) = get1(r);
 1512         }
 1513         else
 1514         {
 1515             ref get2(return ref ChooseResult r) @trusted { return r.r2; }
 1516             get2(this) = get2(r);
 1517         }
 1518     }
 1519 
 1520     // Carefully defined postblit to postblit the appropriate range
 1521     static if (hasElaborateCopyConstructor!R1
 1522         || hasElaborateCopyConstructor!R2)
 1523     this(this)
 1524     {
 1525         actOnChosen!((ref r) {
 1526                 static if (hasElaborateCopyConstructor!(typeof(r))) r.__postblit();
 1527             })(this);
 1528     }
 1529 
 1530     static if (hasElaborateDestructor!R1 || hasElaborateDestructor!R2)
 1531     ~this()
 1532     {
 1533         actOnChosen!((ref r) => destroy(r))(this);
 1534     }
 1535 
 1536     static if (isInfinite!R1 && isInfinite!R2)
 1537         // Propagate infiniteness.
 1538         enum bool empty = false;
 1539     else
 1540         @property bool empty()
 1541         {
 1542             return actOnChosen!(r => r.empty)(this);
 1543         }
 1544 
 1545     @property auto ref front()
 1546     {
 1547         static auto ref getFront(R)(ref R r) { return r.front; }
 1548         return actOnChosen!getFront(this);
 1549     }
 1550 
 1551     void popFront()
 1552     {
 1553         return actOnChosen!((ref r) { r.popFront; })(this);
 1554     }
 1555 
 1556     static if (isForwardRange!R1 && isForwardRange!R2)
 1557     @property auto save() return scope
 1558     {
 1559         if (r1Chosen)
 1560         {
 1561             ref R1 getR1() @trusted { return r1; }
 1562             return ChooseResult(r1Chosen, getR1.save, R2.init);
 1563         }
 1564         else
 1565         {
 1566             ref R2 getR2() @trusted { return r2; }
 1567             return ChooseResult(r1Chosen, R1.init, getR2.save);
 1568         }
 1569     }
 1570 
 1571     @property void front(T)(T v)
 1572     if (is(typeof({ r1.front = v; r2.front = v; })))
 1573     {
 1574         actOnChosen!((ref r, T v) { r.front = v; })(this, v);
 1575     }
 1576 
 1577     static if (hasMobileElements!R1 && hasMobileElements!R2)
 1578         auto moveFront()
 1579         {
 1580             return actOnChosen!((ref r) => r.moveFront)(this);
 1581         }
 1582 
 1583     static if (isBidirectionalRange!R1 && isBidirectionalRange!R2)
 1584     {
 1585         @property auto ref back()
 1586         {
 1587             static auto ref getBack(R)(ref R r) { return r.back; }
 1588             return actOnChosen!getBack(this);
 1589         }
 1590 
 1591         void popBack()
 1592         {
 1593             actOnChosen!((ref r) { r.popBack; })(this);
 1594         }
 1595 
 1596         static if (hasMobileElements!R1 && hasMobileElements!R2)
 1597             auto moveBack()
 1598             {
 1599                 return actOnChosen!((ref r) => r.moveBack)(this);
 1600             }
 1601 
 1602         @property void back(T)(T v)
 1603         if (is(typeof({ r1.back = v; r2.back = v; })))
 1604         {
 1605             actOnChosen!((ref r, T v) { r.back = v; })(this, v);
 1606         }
 1607     }
 1608 
 1609     static if (hasLength!R1 && hasLength!R2)
 1610     {
 1611         @property size_t length()
 1612         {
 1613             return actOnChosen!(r => r.length)(this);
 1614         }
 1615         alias opDollar = length;
 1616     }
 1617 
 1618     static if (isRandomAccessRange!R1 && isRandomAccessRange!R2)
 1619     {
 1620         auto ref opIndex(size_t index)
 1621         {
 1622             static auto ref get(R)(ref R r, size_t index) { return r[index]; }
 1623             return actOnChosen!get(this, index);
 1624         }
 1625 
 1626         static if (hasMobileElements!R1 && hasMobileElements!R2)
 1627             auto moveAt(size_t index)
 1628             {
 1629                 return actOnChosen!((ref r, size_t index) => r.moveAt(index))
 1630                     (this, index);
 1631             }
 1632 
 1633         void opIndexAssign(T)(T v, size_t index)
 1634         if (is(typeof({ r1[1] = v; r2[1] = v; })))
 1635         {
 1636             return actOnChosen!((ref r, size_t index, T v) { r[index] = v; })
 1637                 (this, index, v);
 1638         }
 1639     }
 1640 
 1641     static if (hasSlicing!R1 && hasSlicing!R2)
 1642         auto opSlice(size_t begin, size_t end)
 1643         {
 1644             alias Slice1 = typeof(R1.init[0 .. 1]);
 1645             alias Slice2 = typeof(R2.init[0 .. 1]);
 1646             return actOnChosen!((r, size_t begin, size_t end) {
 1647                     static if (is(typeof(r) == Slice1))
 1648                         return choose(true, r[begin .. end], Slice2.init);
 1649                     else
 1650                         return choose(false, Slice1.init, r[begin .. end]);
 1651                 })(this, begin, end);
 1652         }
 1653 }
 1654 
 1655 // https://issues.dlang.org/show_bug.cgi?id=18657
 1656 pure @safe unittest
 1657 {
 1658     import std.algorithm.comparison : equal;
 1659     string s = "foo";
 1660     auto r = choose(true, refRange(&s), "bar");
 1661     assert(equal(r.save, "foo"));
 1662     assert(equal(r, "foo"));
 1663 }
 1664 
 1665 @safe unittest
 1666 {
 1667     static void* p;
 1668     static struct R
 1669     {
 1670         void* q;
 1671         int front;
 1672         bool empty;
 1673         void popFront() {}
 1674         @property R save() { p = q; return this; }
 1675             // `p = q;` is only there to prevent inference of `scope return`.
 1676     }
 1677     R r;
 1678     choose(true, r, r).save;
 1679 }
 1680 
 1681 // Make sure ChooseResult.save doesn't trust @system user code.
 1682 @system unittest // copy is @system
 1683 {
 1684     static struct R
 1685     {
 1686         int front;
 1687         bool empty;
 1688         void popFront() {}
 1689         this(this) @system {}
 1690         @property R save() { return R(front, empty); }
 1691     }
 1692     choose(true, R(), R()).save;
 1693     choose(true, [0], R()).save;
 1694     choose(true, R(), [0]).save;
 1695 }
 1696 
 1697 @safe unittest // copy is @system
 1698 {
 1699     static struct R
 1700     {
 1701         int front;
 1702         bool empty;
 1703         void popFront() {}
 1704         this(this) @system {}
 1705         @property R save() { return R(front, empty); }
 1706     }
 1707     static assert(!__traits(compiles, choose(true, R(), R()).save));
 1708     static assert(!__traits(compiles, choose(true, [0], R()).save));
 1709     static assert(!__traits(compiles, choose(true, R(), [0]).save));
 1710 }
 1711 
 1712 @system unittest // .save is @system
 1713 {
 1714     static struct R
 1715     {
 1716         int front;
 1717         bool empty;
 1718         void popFront() {}
 1719         @property R save() @system { return this; }
 1720     }
 1721     choose(true, R(), R()).save;
 1722     choose(true, [0], R()).save;
 1723     choose(true, R(), [0]).save;
 1724 }
 1725 
 1726 @safe unittest // .save is @system
 1727 {
 1728     static struct R
 1729     {
 1730         int front;
 1731         bool empty;
 1732         void popFront() {}
 1733         @property R save() @system { return this; }
 1734     }
 1735     static assert(!__traits(compiles, choose(true, R(), R()).save));
 1736     static assert(!__traits(compiles, choose(true, [0], R()).save));
 1737     static assert(!__traits(compiles, choose(true, R(), [0]).save));
 1738 }
 1739 
 1740 //https://issues.dlang.org/show_bug.cgi?id=19738
 1741 @safe nothrow pure @nogc unittest
 1742 {
 1743     static struct EvilRange
 1744     {
 1745         enum empty = true;
 1746         int front;
 1747         void popFront() @safe {}
 1748         auto opAssign(const ref EvilRange other)
 1749         {
 1750             *(cast(uint*) 0xcafebabe) = 0xdeadbeef;
 1751             return this;
 1752         }
 1753     }
 1754 
 1755     static assert(!__traits(compiles, () @safe
 1756     {
 1757         auto c1 = choose(true, EvilRange(), EvilRange());
 1758         auto c2 = c1;
 1759         c1 = c2;
 1760     }));
 1761 }
 1762 
 1763 
 1764 // https://issues.dlang.org/show_bug.cgi?id=20495
 1765 @safe unittest
 1766 {
 1767     static struct KillableRange
 1768     {
 1769         int *item;
 1770         ref int front() { return *item; }
 1771         bool empty() { return *item > 10; }
 1772         void popFront() { ++(*item); }
 1773         this(this)
 1774         {
 1775             assert(item is null || cast(size_t) item > 1000);
 1776             item = new int(*item);
 1777         }
 1778         KillableRange save() { return this; }
 1779     }
 1780 
 1781     auto kr = KillableRange(new int(1));
 1782     int[] x = [1,2,3,4,5]; // length is first
 1783 
 1784     auto chosen = choose(true, x, kr);
 1785     auto chosen2 = chosen.save;
 1786 }
 1787 
 1788 /**
 1789 Choose one of multiple ranges at runtime.
 1790 
 1791 The ranges may be different, but they must have compatible element types. The
 1792 result is a range that offers the weakest capabilities of all `Ranges`.
 1793 
 1794 Params:
 1795     index = which range to choose, must be less than the number of ranges
 1796     rs = two or more ranges
 1797 
 1798 Returns:
 1799     The indexed range. If rs consists of only one range, the return type is an
 1800     alias of that range's type.
 1801  */
 1802 auto chooseAmong(Ranges...)(size_t index, return scope Ranges rs)
 1803 if (Ranges.length >= 2
 1804         && allSatisfy!(isInputRange, staticMap!(Unqual, Ranges))
 1805         && !is(CommonType!(staticMap!(ElementType, Ranges)) == void))
 1806 {
 1807     static if (Ranges.length == 2)
 1808         return choose(index == 0, rs[0], rs[1]);
 1809     else
 1810         return choose(index == 0, rs[0], chooseAmong(index - 1, rs[1 .. $]));
 1811 }
 1812 
 1813 ///
 1814 @safe nothrow pure @nogc unittest
 1815 {
 1816     auto test()
 1817     {
 1818         import std.algorithm.comparison : equal;
 1819 
 1820         int[4] sarr1 = [1, 2, 3, 4];
 1821         int[2] sarr2 = [5, 6];
 1822         int[1] sarr3 = [7];
 1823         auto arr1 = sarr1[];
 1824         auto arr2 = sarr2[];
 1825         auto arr3 = sarr3[];
 1826 
 1827         {
 1828             auto s = chooseAmong(0, arr1, arr2, arr3);
 1829             auto t = s.save;
 1830             assert(s.length == 4);
 1831             assert(s[2] == 3);
 1832             s.popFront();
 1833             assert(equal(t, only(1, 2, 3, 4)));
 1834         }
 1835         {
 1836             auto s = chooseAmong(1, arr1, arr2, arr3);
 1837             assert(s.length == 2);
 1838             s.front = 8;
 1839             assert(equal(s, only(8, 6)));
 1840         }
 1841         {
 1842             auto s = chooseAmong(1, arr1, arr2, arr3);
 1843             assert(s.length == 2);
 1844             s[1] = 9;
 1845             assert(equal(s, only(8, 9)));
 1846         }
 1847         {
 1848             auto s = chooseAmong(1, arr2, arr1, arr3)[1 .. 3];
 1849             assert(s.length == 2);
 1850             assert(equal(s, only(2, 3)));
 1851         }
 1852         {
 1853             auto s = chooseAmong(0, arr1, arr2, arr3);
 1854             assert(s.length == 4);
 1855             assert(s.back == 4);
 1856             s.popBack();
 1857             s.back = 5;
 1858             assert(equal(s, only(1, 2, 5)));
 1859             s.back = 3;
 1860             assert(equal(s, only(1, 2, 3)));
 1861         }
 1862         {
 1863             uint[5] foo = [1, 2, 3, 4, 5];
 1864             uint[5] bar = [6, 7, 8, 9, 10];
 1865             auto c = chooseAmong(1, foo[], bar[]);
 1866             assert(c[3] == 9);
 1867             c[3] = 42;
 1868             assert(c[3] == 42);
 1869             assert(c.moveFront() == 6);
 1870             assert(c.moveBack() == 10);
 1871             assert(c.moveAt(4) == 10);
 1872         }
 1873         {
 1874             import std.range : cycle;
 1875             auto s = chooseAmong(0, cycle(arr2), cycle(arr3));
 1876             assert(isInfinite!(typeof(s)));
 1877             assert(!s.empty);
 1878             assert(s[100] == 8);
 1879             assert(s[101] == 9);
 1880             assert(s[0 .. 3].equal(only(8, 9, 8)));
 1881         }
 1882         return 0;
 1883     }
 1884     // works at runtime
 1885     auto a = test();
 1886     // and at compile time
 1887     static b = test();
 1888 }
 1889 
 1890 @safe nothrow pure @nogc unittest
 1891 {
 1892     int[3] a = [1, 2, 3];
 1893     long[3] b = [4, 5, 6];
 1894     auto c = chooseAmong(0, a[], b[]);
 1895     c[0] = 42;
 1896     assert(c[0] == 42);
 1897 }
 1898 
 1899 @safe nothrow pure @nogc unittest
 1900 {
 1901     static struct RefAccessRange
 1902     {
 1903         int[] r;
 1904         ref front() @property { return r[0]; }
 1905         ref back() @property { return r[$ - 1]; }
 1906         void popFront() { r = r[1 .. $]; }
 1907         void popBack() { r = r[0 .. $ - 1]; }
 1908         auto empty() @property { return r.empty; }
 1909         ref opIndex(size_t i) { return r[i]; }
 1910         auto length() @property { return r.length; }
 1911         alias opDollar = length;
 1912         auto save() { return this; }
 1913     }
 1914     static assert(isRandomAccessRange!RefAccessRange);
 1915     static assert(isRandomAccessRange!RefAccessRange);
 1916     int[4] a = [4, 3, 2, 1];
 1917     int[2] b = [6, 5];
 1918     auto c = chooseAmong(0, RefAccessRange(a[]), RefAccessRange(b[]));
 1919 
 1920     void refFunc(ref int a, int target) { assert(a == target); }
 1921 
 1922     refFunc(c[2], 2);
 1923     refFunc(c.front, 4);
 1924     refFunc(c.back, 1);
 1925 }
 1926 
 1927 
 1928 /**
 1929 $(D roundRobin(r1, r2, r3)) yields `r1.front`, then `r2.front`,
 1930 then `r3.front`, after which it pops off one element from each and
 1931 continues again from `r1`. For example, if two ranges are involved,
 1932 it alternately yields elements off the two ranges. `roundRobin`
 1933 stops after it has consumed all ranges (skipping over the ones that
 1934 finish early).
 1935  */
 1936 auto roundRobin(Rs...)(Rs rs)
 1937 if (Rs.length > 1 && allSatisfy!(isInputRange, staticMap!(Unqual, Rs)))
 1938 {
 1939     struct Result
 1940     {
 1941         import std.conv : to;
 1942 
 1943         public Rs source;
 1944         private size_t _current = size_t.max;
 1945 
 1946         @property bool empty()
 1947         {
 1948             foreach (i, Unused; Rs)
 1949             {
 1950                 if (!source[i].empty) return false;
 1951             }
 1952             return true;
 1953         }
 1954 
 1955         @property auto ref front()
 1956         {
 1957             final switch (_current)
 1958             {
 1959                 foreach (i, R; Rs)
 1960                 {
 1961                     case i:
 1962                         assert(
 1963                             !source[i].empty,
 1964                             "Attempting to fetch the front of an empty roundRobin"
 1965                         );
 1966                         return source[i].front;
 1967                 }
 1968             }
 1969             assert(0);
 1970         }
 1971 
 1972         void popFront()
 1973         {
 1974             final switch (_current)
 1975             {
 1976                 foreach (i, R; Rs)
 1977                 {
 1978                     case i:
 1979                         source[i].popFront();
 1980                         break;
 1981                 }
 1982             }
 1983 
 1984             auto next = _current == (Rs.length - 1) ? 0 : (_current + 1);
 1985             final switch (next)
 1986             {
 1987                 foreach (i, R; Rs)
 1988                 {
 1989                     case i:
 1990                         if (!source[i].empty)
 1991                         {
 1992                             _current = i;
 1993                             return;
 1994                         }
 1995                         if (i == _current)
 1996                         {
 1997                             _current = _current.max;
 1998                             return;
 1999                         }
 2000                         goto case (i + 1) % Rs.length;
 2001                 }
 2002             }
 2003         }
 2004 
 2005         static if (allSatisfy!(isForwardRange, staticMap!(Unqual, Rs)))
 2006             @property auto save()
 2007             {
 2008                 auto saveSource(size_t len)()
 2009                 {
 2010                     import std.typecons : tuple;
 2011                     static assert(len > 0);
 2012                     static if (len == 1)
 2013                     {
 2014                         return tuple(source[0].save);
 2015                     }
 2016                     else
 2017                     {
 2018                         return saveSource!(len - 1)() ~
 2019                             tuple(source[len - 1].save);
 2020                     }
 2021                 }
 2022                 return Result(saveSource!(Rs.length).expand, _current);
 2023             }
 2024 
 2025         static if (allSatisfy!(hasLength, Rs))
 2026         {
 2027             @property size_t length()
 2028             {
 2029                 size_t result;
 2030                 foreach (i, R; Rs)
 2031                 {
 2032                     result += source[i].length;
 2033                 }
 2034                 return result;
 2035             }
 2036 
 2037             alias opDollar = length;
 2038         }
 2039     }
 2040 
 2041     return Result(rs, 0);
 2042 }
 2043 
 2044 ///
 2045 @safe unittest
 2046 {
 2047     import std.algorithm.comparison : equal;
 2048 
 2049     int[] a = [ 1, 2, 3 ];
 2050     int[] b = [ 10, 20, 30, 40 ];
 2051     auto r = roundRobin(a, b);
 2052     assert(equal(r, [ 1, 10, 2, 20, 3, 30, 40 ]));
 2053 }
 2054 
 2055 /**
 2056  * roundRobin can be used to create "interleave" functionality which inserts
 2057  * an element between each element in a range.
 2058  */
 2059 @safe unittest
 2060 {
 2061     import std.algorithm.comparison : equal;
 2062 
 2063     auto interleave(R, E)(R range, E element)
 2064     if ((isInputRange!R && hasLength!R) || isForwardRange!R)
 2065     {
 2066         static if (hasLength!R)
 2067             immutable len = range.length;
 2068         else
 2069             immutable len = range.save.walkLength;
 2070 
 2071         return roundRobin(
 2072             range,
 2073             element.repeat(len - 1)
 2074         );
 2075     }
 2076 
 2077     assert(interleave([1, 2, 3], 0).equal([1, 0, 2, 0, 3]));
 2078 }
 2079 
 2080 pure @safe unittest
 2081 {
 2082     import std.algorithm.comparison : equal;
 2083     string f = "foo", b = "bar";
 2084     auto r = roundRobin(refRange(&f), refRange(&b));
 2085     assert(equal(r.save, "fboaor"));
 2086     assert(equal(r.save, "fboaor"));
 2087 }
 2088 
 2089 /**
 2090 Iterates a random-access range starting from a given point and
 2091 progressively extending left and right from that point. If no initial
 2092 point is given, iteration starts from the middle of the
 2093 range. Iteration spans the entire range.
 2094 
 2095 When `startingIndex` is 0 the range will be fully iterated in order
 2096 and in reverse order when `r.length` is given.
 2097 
 2098 Params:
 2099     r = a random access range with length and slicing
 2100     startingIndex = the index to begin iteration from
 2101 
 2102 Returns:
 2103     A forward range with length
 2104  */
 2105 auto radial(Range, I)(Range r, I startingIndex)
 2106 if (isRandomAccessRange!(Unqual!Range) && hasLength!(Unqual!Range) && hasSlicing!(Unqual!Range) && isIntegral!I)
 2107 {
 2108     if (startingIndex != r.length) ++startingIndex;
 2109     return roundRobin(retro(r[0 .. startingIndex]), r[startingIndex .. r.length]);
 2110 }
 2111 
 2112 /// Ditto
 2113 auto radial(R)(R r)
 2114 if (isRandomAccessRange!(Unqual!R) && hasLength!(Unqual!R) && hasSlicing!(Unqual!R))
 2115 {
 2116     return .radial(r, (r.length - !r.empty) / 2);
 2117 }
 2118 
 2119 ///
 2120 @safe unittest
 2121 {
 2122     import std.algorithm.comparison : equal;
 2123     int[] a = [ 1, 2, 3, 4, 5 ];
 2124     assert(equal(radial(a), [ 3, 4, 2, 5, 1 ]));
 2125     a = [ 1, 2, 3, 4 ];
 2126     assert(equal(radial(a), [ 2, 3, 1, 4 ]));
 2127 
 2128     // If the left end is reached first, the remaining elements on the right
 2129     // are concatenated in order:
 2130     a = [ 0, 1, 2, 3, 4, 5 ];
 2131     assert(equal(radial(a, 1), [ 1, 2, 0, 3, 4, 5 ]));
 2132 
 2133     // If the right end is reached first, the remaining elements on the left
 2134     // are concatenated in reverse order:
 2135     assert(equal(radial(a, 4), [ 4, 5, 3, 2, 1, 0 ]));
 2136 }
 2137 
 2138 @safe unittest
 2139 {
 2140     import std.algorithm.comparison : equal;
 2141     import std.conv : text;
 2142     import std.exception : enforce;
 2143     import std.internal.test.dummyrange : DummyRange, Length, RangeType, ReturnBy;
 2144 
 2145     void test(int[] input, int[] witness)
 2146     {
 2147         enforce(equal(radial(input), witness),
 2148                 text(radial(input), " vs. ", witness));
 2149     }
 2150     test([], []);
 2151     test([ 1 ], [ 1 ]);
 2152     test([ 1, 2 ], [ 1, 2 ]);
 2153     test([ 1, 2, 3 ], [ 2, 3, 1 ]);
 2154     test([ 1, 2, 3, 4 ], [ 2, 3, 1, 4 ]);
 2155     test([ 1, 2, 3, 4, 5 ], [ 3, 4, 2, 5, 1 ]);
 2156     test([ 1, 2, 3, 4, 5, 6 ], [ 3, 4, 2, 5, 1, 6 ]);
 2157 
 2158     int[] a = [ 1, 2, 3, 4, 5 ];
 2159     assert(equal(radial(a, 1), [ 2, 3, 1, 4, 5 ]));
 2160     assert(equal(radial(a, 0), [ 1, 2, 3, 4, 5 ])); // only right subrange
 2161     assert(equal(radial(a, a.length), [ 5, 4, 3, 2, 1 ])); // only left subrange
 2162     static assert(isForwardRange!(typeof(radial(a, 1))));
 2163 
 2164     auto r = radial([1,2,3,4,5]);
 2165     for (auto rr = r.save; !rr.empty; rr.popFront())
 2166     {
 2167         assert(rr.front == moveFront(rr));
 2168     }
 2169     r.front = 5;
 2170     assert(r.front == 5);
 2171 
 2172     // Test instantiation without lvalue elements.
 2173     DummyRange!(ReturnBy.Value, Length.Yes, RangeType.Random) dummy;
 2174     assert(equal(radial(dummy, 4), [5, 6, 4, 7, 3, 8, 2, 9, 1, 10]));
 2175 
 2176     // immutable int[] immi = [ 1, 2 ];
 2177     // static assert(is(typeof(radial(immi))));
 2178 }
 2179 
 2180 @safe unittest
 2181 {
 2182     import std.algorithm.comparison : equal;
 2183 
 2184     auto LL = iota(1L, 6L);
 2185     auto r = radial(LL);
 2186     assert(equal(r, [3L, 4L, 2L, 5L, 1L]));
 2187 }
 2188 
 2189 /**
 2190 Lazily takes only up to `n` elements of a range. This is
 2191 particularly useful when using with infinite ranges.
 2192 
 2193 Unlike $(LREF takeExactly), `take` does not require that there
 2194 are `n` or more elements in `input`. As a consequence, length
 2195 information is not applied to the result unless `input` also has
 2196 length information.
 2197 
 2198 Params:
 2199     input = an $(REF_ALTTEXT input range, isInputRange, std,range,primitives)
 2200     to iterate over up to `n` times
 2201     n = the number of elements to take
 2202 
 2203 Returns:
 2204     At minimum, an input range. If the range offers random access
 2205     and `length`, `take` offers them as well.
 2206  */
 2207 Take!R take(R)(R input, size_t n)
 2208 if (isInputRange!(Unqual!R))
 2209 {
 2210     alias U = Unqual!R;
 2211     static if (is(R T == Take!T))
 2212     {
 2213         import std.algorithm.comparison : min;
 2214         return R(input.source, min(n, input._maxAvailable));
 2215     }
 2216     else static if (!isInfinite!U && hasSlicing!U)
 2217     {
 2218         import std.algorithm.comparison : min;
 2219         return input[0 .. min(n, input.length)];
 2220     }
 2221     else
 2222     {
 2223         return Take!R(input, n);
 2224     }
 2225 }
 2226 
 2227 /// ditto
 2228 struct Take(Range)
 2229 if (isInputRange!(Unqual!Range) &&
 2230     //take _cannot_ test hasSlicing on infinite ranges, because hasSlicing uses
 2231     //take for slicing infinite ranges.
 2232     !((!isInfinite!(Unqual!Range) && hasSlicing!(Unqual!Range)) || is(Range T == Take!T)))
 2233 {
 2234     private alias R = Unqual!Range;
 2235 
 2236     /// User accessible in read and write
 2237     public R source;
 2238 
 2239     private size_t _maxAvailable;
 2240 
 2241     alias Source = R;
 2242 
 2243     /// Range primitives
 2244     @property bool empty()
 2245     {
 2246         return _maxAvailable == 0 || source.empty;
 2247     }
 2248 
 2249     /// ditto
 2250     @property auto ref front()
 2251     {
 2252         assert(!empty,
 2253             "Attempting to fetch the front of an empty "
 2254             ~ Take.stringof);
 2255         return source.front;
 2256     }
 2257 
 2258     /// ditto
 2259     void popFront()
 2260     {
 2261         assert(!empty,
 2262             "Attempting to popFront() past the end of a "
 2263             ~ Take.stringof);
 2264         source.popFront();
 2265         --_maxAvailable;
 2266     }
 2267 
 2268     static if (isForwardRange!R)
 2269         /// ditto
 2270         @property Take save()
 2271         {
 2272             return Take(source.save, _maxAvailable);
 2273         }
 2274 
 2275     static if (hasAssignableElements!R)
 2276         /// ditto
 2277         @property void front(ElementType!R v)
 2278         {
 2279             assert(!empty,
 2280                 "Attempting to assign to the front of an empty "
 2281                 ~ Take.stringof);
 2282             // This has to return auto instead of void because of
 2283             // https://issues.dlang.org/show_bug.cgi?id=4706
 2284             source.front = v;
 2285         }
 2286 
 2287     static if (hasMobileElements!R)
 2288     {
 2289         /// ditto
 2290         auto moveFront()
 2291         {
 2292             assert(!empty,
 2293                 "Attempting to move the front of an empty "
 2294                 ~ Take.stringof);
 2295             return source.moveFront();
 2296         }
 2297     }
 2298 
 2299     static if (isInfinite!R)
 2300     {
 2301         /// ditto
 2302         @property size_t length() const
 2303         {
 2304             return _maxAvailable;
 2305         }
 2306 
 2307         /// ditto
 2308         alias opDollar = length;
 2309 
 2310         //Note: Due to Take/hasSlicing circular dependency,
 2311         //This needs to be a restrained template.
 2312         /// ditto
 2313         auto opSlice()(size_t i, size_t j)
 2314         if (hasSlicing!R)
 2315         {
 2316             assert(i <= j, "Invalid slice bounds");
 2317             assert(j <= length, "Attempting to slice past the end of a "
 2318                 ~ Take.stringof);
 2319             return source[i .. j];
 2320         }
 2321     }
 2322     else static if (hasLength!R)
 2323     {
 2324         /// ditto
 2325         @property size_t length()
 2326         {
 2327             import std.algorithm.comparison : min;
 2328             return min(_maxAvailable, source.length);
 2329         }
 2330 
 2331         alias opDollar = length;
 2332     }
 2333 
 2334     static if (isRandomAccessRange!R)
 2335     {
 2336         /// ditto
 2337         void popBack()
 2338         {
 2339             assert(!empty,
 2340                 "Attempting to popBack() past the beginning of a "
 2341                 ~ Take.stringof);
 2342             --_maxAvailable;
 2343         }
 2344 
 2345         /// ditto
 2346         @property auto ref back()
 2347         {
 2348             assert(!empty,
 2349                 "Attempting to fetch the back of an empty "
 2350                 ~ Take.stringof);
 2351             return source[this.length - 1];
 2352         }
 2353 
 2354         /// ditto
 2355         auto ref opIndex(size_t index)
 2356         {
 2357             assert(index < length,
 2358                 "Attempting to index out of the bounds of a "
 2359                 ~ Take.stringof);
 2360             return source[index];
 2361         }
 2362 
 2363         static if (hasAssignableElements!R)
 2364         {
 2365             /// ditto
 2366             @property void back(ElementType!R v)
 2367             {
 2368                 // This has to return auto instead of void because of
 2369                 // https://issues.dlang.org/show_bug.cgi?id=4706
 2370                 assert(!empty,
 2371                     "Attempting to assign to the back of an empty "
 2372                     ~ Take.stringof);
 2373                 source[this.length - 1] = v;
 2374             }
 2375 
 2376             /// ditto
 2377             void opIndexAssign(ElementType!R v, size_t index)
 2378             {
 2379                 assert(index < length,
 2380                     "Attempting to index out of the bounds of a "
 2381                     ~ Take.stringof);
 2382                 source[index] = v;
 2383             }
 2384         }
 2385 
 2386         static if (hasMobileElements!R)
 2387         {
 2388             /// ditto
 2389             auto moveBack()
 2390             {
 2391                 assert(!empty,
 2392                     "Attempting to move the back of an empty "
 2393                     ~ Take.stringof);
 2394                 return source.moveAt(this.length - 1);
 2395             }
 2396 
 2397             /// ditto
 2398             auto moveAt(size_t index)
 2399             {
 2400                 assert(index < length,
 2401                     "Attempting to index out of the bounds of a "
 2402                     ~ Take.stringof);
 2403                 return source.moveAt(index);
 2404             }
 2405         }
 2406     }
 2407 
 2408     /**
 2409     Access to maximal length of the range.
 2410     Note: the actual length of the range depends on the underlying range.
 2411     If it has fewer elements, it will stop before maxLength is reached.
 2412     */
 2413     @property size_t maxLength() const
 2414     {
 2415         return _maxAvailable;
 2416     }
 2417 }
 2418 
 2419 /// ditto
 2420 template Take(R)
 2421 if (isInputRange!(Unqual!R) &&
 2422     ((!isInfinite!(Unqual!R) && hasSlicing!(Unqual!R)) || is(R T == Take!T)))
 2423 {
 2424     alias Take = R;
 2425 }
 2426 
 2427 ///
 2428 pure @safe nothrow unittest
 2429 {
 2430     import std.algorithm.comparison : equal;
 2431 
 2432     int[] arr1 = [ 1, 2, 3, 4, 5, 6, 7, 8, 9, 10 ];
 2433     auto s = take(arr1, 5);
 2434     assert(s.length == 5);
 2435     assert(s[4] == 5);
 2436     assert(equal(s, [ 1, 2, 3, 4, 5 ][]));
 2437 }
 2438 
 2439 /**
 2440  * If the range runs out before `n` elements, `take` simply returns the entire
 2441  * range (unlike $(LREF takeExactly), which will cause an assertion failure if
 2442  * the range ends prematurely):
 2443  */
 2444 pure @safe nothrow unittest
 2445 {
 2446     import std.algorithm.comparison : equal;
 2447 
 2448     int[] arr2 = [ 1, 2, 3 ];
 2449     auto t = take(arr2, 5);
 2450     assert(t.length == 3);
 2451     assert(equal(t, [ 1, 2, 3 ]));
 2452 }
 2453 
 2454 pure @safe nothrow unittest
 2455 {
 2456     import std.algorithm.comparison : equal;
 2457     import std.internal.test.dummyrange : AllDummyRanges;
 2458 
 2459     int[] arr1 = [ 1, 2, 3, 4, 5, 6, 7, 8, 9, 10 ];
 2460     auto s = take(arr1, 5);
 2461     assert(s.length == 5);
 2462     assert(s[4] == 5);
 2463     assert(equal(s, [ 1, 2, 3, 4, 5 ][]));
 2464     assert(equal(retro(s), [ 5, 4, 3, 2, 1 ][]));
 2465 
 2466     // Test fix for bug 4464.
 2467     static assert(is(typeof(s) == Take!(int[])));
 2468     static assert(is(typeof(s) == int[]));
 2469 
 2470     // Test using narrow strings.
 2471     import std.exception : assumeWontThrow;
 2472 
 2473     auto myStr = "This is a string.";
 2474     auto takeMyStr = take(myStr, 7);
 2475     assert(assumeWontThrow(equal(takeMyStr, "This is")));
 2476     // Test fix for bug 5052.
 2477     auto takeMyStrAgain = take(takeMyStr, 4);
 2478     assert(assumeWontThrow(equal(takeMyStrAgain, "This")));
 2479     static assert(is (typeof(takeMyStrAgain) == typeof(takeMyStr)));
 2480     takeMyStrAgain = take(takeMyStr, 10);
 2481     assert(assumeWontThrow(equal(takeMyStrAgain, "This is")));
 2482 
 2483     foreach (DummyType; AllDummyRanges)
 2484     {
 2485         DummyType dummy;
 2486         auto t = take(dummy, 5);
 2487         alias T = typeof(t);
 2488 
 2489         static if (isRandomAccessRange!DummyType)
 2490         {
 2491             static assert(isRandomAccessRange!T);
 2492             assert(t[4] == 5);
 2493 
 2494             assert(moveAt(t, 1) == t[1]);
 2495             assert(t.back == moveBack(t));
 2496         }
 2497         else static if (isForwardRange!DummyType)
 2498         {
 2499             static assert(isForwardRange!T);
 2500         }
 2501 
 2502         for (auto tt = t; !tt.empty; tt.popFront())
 2503         {
 2504             assert(tt.front == moveFront(tt));
 2505         }
 2506 
 2507         // Bidirectional ranges can't be propagated properly if they don't
 2508         // also have random access.
 2509 
 2510         assert(equal(t, [1,2,3,4,5]));
 2511 
 2512         //Test that take doesn't wrap the result of take.
 2513         assert(take(t, 4) == take(dummy, 4));
 2514     }
 2515 
 2516     immutable myRepeat = repeat(1);
 2517     static assert(is(Take!(typeof(myRepeat))));
 2518 }
 2519 
 2520 pure @safe nothrow @nogc unittest
 2521 {
 2522     //check for correct slicing of Take on an infinite range
 2523     import std.algorithm.comparison : equal;
 2524     foreach (start; 0 .. 4)
 2525         foreach (stop; start .. 4)
 2526             assert(iota(4).cycle.take(4)[start .. stop]
 2527                 .equal(iota(start, stop)));
 2528 }
 2529 
 2530 pure @safe nothrow @nogc unittest
 2531 {
 2532     // Check that one can declare variables of all Take types,
 2533     // and that they match the return type of the corresponding
 2534     // take().
 2535     // See https://issues.dlang.org/show_bug.cgi?id=4464
 2536     int[] r1;
 2537     Take!(int[]) t1;
 2538     t1 = take(r1, 1);
 2539     assert(t1.empty);
 2540 
 2541     string r2;
 2542     Take!string t2;
 2543     t2 = take(r2, 1);
 2544     assert(t2.empty);
 2545 
 2546     Take!(Take!string) t3;
 2547     t3 = take(t2, 1);
 2548     assert(t3.empty);
 2549 }
 2550 
 2551 pure @safe nothrow @nogc unittest
 2552 {
 2553     alias R1 = typeof(repeat(1));
 2554     alias R2 = typeof(cycle([1]));
 2555     alias TR1 = Take!R1;
 2556     alias TR2 = Take!R2;
 2557     static assert(isBidirectionalRange!TR1);
 2558     static assert(isBidirectionalRange!TR2);
 2559 }
 2560 
 2561 // https://issues.dlang.org/show_bug.cgi?id=12731
 2562 pure @safe nothrow @nogc unittest
 2563 {
 2564     auto a = repeat(1);
 2565     auto s = a[1 .. 5];
 2566     s = s[1 .. 3];
 2567     assert(s.length == 2);
 2568     assert(s[0] == 1);
 2569     assert(s[1] == 1);
 2570 }
 2571 
 2572 // https://issues.dlang.org/show_bug.cgi?id=13151
 2573 pure @safe nothrow @nogc unittest
 2574 {
 2575     import std.algorithm.comparison : equal;
 2576 
 2577     auto r = take(repeat(1, 4), 3);
 2578     assert(r.take(2).equal(repeat(1, 2)));
 2579 }
 2580 
 2581 
 2582 /**
 2583 Similar to $(LREF take), but assumes that `range` has at least $(D
 2584 n) elements. Consequently, the result of $(D takeExactly(range, n))
 2585 always defines the `length` property (and initializes it to `n`)
 2586 even when `range` itself does not define `length`.
 2587 
 2588 The result of `takeExactly` is identical to that of $(LREF take) in
 2589 cases where the original range defines `length` or is infinite.
 2590 
 2591 Unlike $(LREF take), however, it is illegal to pass a range with less than
 2592 `n` elements to `takeExactly`; this will cause an assertion failure.
 2593  */
 2594 auto takeExactly(R)(R range, size_t n)
 2595 if (isInputRange!R)
 2596 {
 2597     static if (is(typeof(takeExactly(range._input, n)) == R))
 2598     {
 2599         assert(n <= range._n,
 2600                "Attempted to take more than the length of the range with takeExactly.");
 2601         // takeExactly(takeExactly(r, n1), n2) has the same type as
 2602         // takeExactly(r, n1) and simply returns takeExactly(r, n2)
 2603         range._n = n;
 2604         return range;
 2605     }
 2606     //Also covers hasSlicing!R for finite ranges.
 2607     else static if (hasLength!R)
 2608     {
 2609         assert(n <= range.length,
 2610                "Attempted to take more than the length of the range with takeExactly.");
 2611         return take(range, n);
 2612     }
 2613     else static if (isInfinite!R)
 2614         return Take!R(range, n);
 2615     else
 2616     {
 2617         static struct Result
 2618         {
 2619             R _input;
 2620             private size_t _n;
 2621 
 2622             @property bool empty() const { return !_n; }
 2623             @property auto ref front()
 2624             {
 2625                 assert(_n > 0, "front() on an empty " ~ Result.stringof);
 2626                 return _input.front;
 2627             }
 2628             void popFront() { _input.popFront(); --_n; }
 2629             @property size_t length() const { return _n; }
 2630             alias opDollar = length;
 2631 
 2632             @property auto _takeExactly_Result_asTake()
 2633             {
 2634                 return take(_input, _n);
 2635             }
 2636 
 2637             alias _takeExactly_Result_asTake this;
 2638 
 2639             static if (isForwardRange!R)
 2640                 @property auto save()
 2641                 {
 2642                     return Result(_input.save, _n);
 2643                 }
 2644 
 2645             static if (hasMobileElements!R)
 2646             {
 2647                 auto moveFront()
 2648                 {
 2649                     assert(!empty,
 2650                         "Attempting to move the front of an empty "
 2651                         ~ typeof(this).stringof);
 2652                     return _input.moveFront();
 2653                 }
 2654             }
 2655 
 2656             static if (hasAssignableElements!R)
 2657             {
 2658                 @property auto ref front(ElementType!R v)
 2659                 {
 2660                     assert(!empty,
 2661                         "Attempting to assign to the front of an empty "
 2662                         ~ typeof(this).stringof);
 2663                     return _input.front = v;
 2664                 }
 2665             }
 2666         }
 2667 
 2668         return Result(range, n);
 2669     }
 2670 }
 2671 
 2672 ///
 2673 pure @safe nothrow unittest
 2674 {
 2675     import std.algorithm.comparison : equal;
 2676 
 2677     auto a = [ 1, 2, 3, 4, 5 ];
 2678 
 2679     auto b = takeExactly(a, 3);
 2680     assert(equal(b, [1, 2, 3]));
 2681     static assert(is(typeof(b.length) == size_t));
 2682     assert(b.length == 3);
 2683     assert(b.front == 1);
 2684     assert(b.back == 3);
 2685 }
 2686 
 2687 pure @safe nothrow unittest
 2688 {
 2689     import std.algorithm.comparison : equal;
 2690     import std.algorithm.iteration : filter;
 2691 
 2692     auto a = [ 1, 2, 3, 4, 5 ];
 2693     auto b = takeExactly(a, 3);
 2694     assert(equal(b, [1, 2, 3]));
 2695     auto c = takeExactly(b, 2);
 2696     assert(equal(c, [1, 2]));
 2697 
 2698 
 2699 
 2700     auto d = filter!"a > 2"(a);
 2701     auto e = takeExactly(d, 3);
 2702     assert(equal(e, [3, 4, 5]));
 2703     static assert(is(typeof(e.length) == size_t));
 2704     assert(e.length == 3);
 2705     assert(e.front == 3);
 2706 
 2707     assert(equal(takeExactly(e, 3), [3, 4, 5]));
 2708 }
 2709 
 2710 pure @safe nothrow unittest
 2711 {
 2712     import std.algorithm.comparison : equal;
 2713     import std.internal.test.dummyrange : AllDummyRanges;
 2714 
 2715     auto a = [ 1, 2, 3, 4, 5 ];
 2716     //Test that take and takeExactly are the same for ranges which define length
 2717     //but aren't sliceable.
 2718     struct L
 2719     {
 2720         @property auto front() { return _arr[0]; }
 2721         @property bool empty() { return _arr.empty; }
 2722         void popFront() { _arr.popFront(); }
 2723         @property size_t length() { return _arr.length; }
 2724         int[] _arr;
 2725     }
 2726     static assert(is(typeof(take(L(a), 3)) == typeof(takeExactly(L(a), 3))));
 2727     assert(take(L(a), 3) == takeExactly(L(a), 3));
 2728 
 2729     //Test that take and takeExactly are the same for ranges which are sliceable.
 2730     static assert(is(typeof(take(a, 3)) == typeof(takeExactly(a, 3))));
 2731     assert(take(a, 3) == takeExactly(a, 3));
 2732 
 2733     //Test that take and takeExactly are the same for infinite ranges.
 2734     auto inf = repeat(1);
 2735     static assert(is(typeof(take(inf, 5)) == Take!(typeof(inf))));
 2736     assert(take(inf, 5) == takeExactly(inf, 5));
 2737 
 2738     //Test that take and takeExactly are _not_ the same for ranges which don't
 2739     //define length.
 2740     static assert(!is(typeof(take(filter!"true"(a), 3)) == typeof(takeExactly(filter!"true"(a), 3))));
 2741 
 2742     foreach (DummyType; AllDummyRanges)
 2743     {
 2744         {
 2745             DummyType dummy;
 2746             auto t = takeExactly(dummy, 5);
 2747 
 2748             //Test that takeExactly doesn't wrap the result of takeExactly.
 2749             assert(takeExactly(t, 4) == takeExactly(dummy, 4));
 2750         }
 2751 
 2752         static if (hasMobileElements!DummyType)
 2753         {
 2754             {
 2755                 auto t = takeExactly(DummyType.init, 4);
 2756                 assert(t.moveFront() == 1);
 2757                 assert(equal(t, [1, 2, 3, 4]));
 2758             }
 2759         }
 2760 
 2761         static if (hasAssignableElements!DummyType)
 2762         {
 2763             {
 2764                 auto t = takeExactly(DummyType.init, 4);
 2765                 t.front = 9;
 2766                 assert(equal(t, [9, 2, 3, 4]));
 2767             }
 2768         }
 2769     }
 2770 }
 2771 
 2772 pure @safe nothrow unittest
 2773 {
 2774     import std.algorithm.comparison : equal;
 2775     import std.internal.test.dummyrange : DummyRange, Length, RangeType, ReturnBy;
 2776 
 2777     alias DummyType = DummyRange!(ReturnBy.Value, Length.No, RangeType.Forward);
 2778     auto te = takeExactly(DummyType(), 5);
 2779     Take!DummyType t = te;
 2780     assert(equal(t, [1, 2, 3, 4, 5]));
 2781     assert(equal(t, te));
 2782 }
 2783 
 2784 // https://issues.dlang.org/show_bug.cgi?id=18092
 2785 // can't combine take and takeExactly
 2786 @safe unittest
 2787 {
 2788     import std.algorithm.comparison : equal;
 2789     import std.internal.test.dummyrange : AllDummyRanges;
 2790 
 2791     static foreach (Range; AllDummyRanges)
 2792     {{
 2793         Range r;
 2794         assert(r.take(6).takeExactly(2).equal([1, 2]));
 2795         assert(r.takeExactly(6).takeExactly(2).equal([1, 2]));
 2796         assert(r.takeExactly(6).take(2).equal([1, 2]));
 2797     }}
 2798 }
 2799 
 2800 /**
 2801 Returns a range with at most one element; for example, $(D
 2802 takeOne([42, 43, 44])) returns a range consisting of the integer $(D
 2803 42). Calling `popFront()` off that range renders it empty.
 2804 
 2805 In effect `takeOne(r)` is somewhat equivalent to $(D take(r, 1)) but in
 2806 certain interfaces it is important to know statically that the range may only
 2807 have at most one element.
 2808 
 2809 The type returned by `takeOne` is a random-access range with length
 2810 regardless of `R`'s capabilities, as long as it is a forward range.
 2811 (another feature that distinguishes `takeOne` from `take`). If
 2812 (D R) is an input range but not a forward range, return type is an input
 2813 range with all random-access capabilities except save.
 2814  */
 2815 auto takeOne(R)(R source)
 2816 if (isInputRange!R)
 2817 {
 2818     static if (hasSlicing!R)
 2819     {
 2820         return source[0 .. !source.empty];
 2821     }
 2822     else
 2823     {
 2824         static struct Result
 2825         {
 2826             private R _source;
 2827             private bool _empty = true;
 2828             @property bool empty() const { return _empty; }
 2829             @property auto ref front()
 2830             {
 2831                 assert(!empty, "Attempting to fetch the front of an empty takeOne");
 2832                 return _source.front;
 2833             }
 2834             void popFront()
 2835             {
 2836                 assert(!empty, "Attempting to popFront an empty takeOne");
 2837                 _source.popFront();
 2838                 _empty = true;
 2839             }
 2840             void popBack()
 2841             {
 2842                 assert(!empty, "Attempting to popBack an empty takeOne");
 2843                 _source.popFront();
 2844                 _empty = true;
 2845             }
 2846             static if (isForwardRange!(Unqual!R))
 2847             {
 2848                 @property auto save() { return Result(_source.save, empty); }
 2849             }
 2850             @property auto ref back()
 2851             {
 2852                 assert(!empty, "Attempting to fetch the back of an empty takeOne");
 2853                 return _source.front;
 2854             }
 2855             @property size_t length() const { return !empty; }
 2856             alias opDollar = length;
 2857             auto ref opIndex(size_t n)
 2858             {
 2859                 assert(n < length, "Attempting to index a takeOne out of bounds");
 2860                 return _source.front;
 2861             }
 2862             auto opSlice(size_t m, size_t n)
 2863             {
 2864                 assert(
 2865                     m <= n,
 2866                     "Attempting to slice a takeOne range with a larger first argument than the second."
 2867                 );
 2868                 assert(
 2869                     n <= length,
 2870                     "Attempting to slice using an out of bounds index on a takeOne range."
 2871                     );
 2872                 return n > m ? this : Result(_source, true);
 2873             }
 2874             // Non-standard property
 2875             @property R source() { return _source; }
 2876         }
 2877 
 2878         return Result(source, source.empty);
 2879     }
 2880 }
 2881 
 2882 ///
 2883 pure @safe nothrow unittest
 2884 {
 2885     auto s = takeOne([42, 43, 44]);
 2886     static assert(isRandomAccessRange!(typeof(s)));
 2887     assert(s.length == 1);
 2888     assert(!s.empty);
 2889     assert(s.front == 42);
 2890     s.front = 43;
 2891     assert(s.front == 43);
 2892     assert(s.back == 43);
 2893     assert(s[0] == 43);
 2894     s.popFront();
 2895     assert(s.length == 0);
 2896     assert(s.empty);
 2897 }
 2898 
 2899 pure @safe nothrow @nogc unittest
 2900 {
 2901     struct NonForwardRange
 2902     {
 2903         enum empty = false;
 2904         int front() { return 42; }
 2905         void popFront() {}
 2906     }
 2907 
 2908     static assert(!isForwardRange!NonForwardRange);
 2909 
 2910     auto s = takeOne(NonForwardRange());
 2911     assert(s.length == 1);
 2912     assert(!s.empty);
 2913     assert(s.front == 42);
 2914     assert(s.back == 42);
 2915     assert(s[0] == 42);
 2916 
 2917     auto t = s[0 .. 0];
 2918     assert(t.empty);
 2919     assert(t.length == 0);
 2920 
 2921     auto u = s[1 .. 1];
 2922     assert(u.empty);
 2923     assert(u.length == 0);
 2924 
 2925     auto v = s[0 .. 1];
 2926     s.popFront();
 2927     assert(s.length == 0);
 2928     assert(s.empty);
 2929     assert(!v.empty);
 2930     assert(v.front == 42);
 2931     v.popBack();
 2932     assert(v.empty);
 2933     assert(v.length == 0);
 2934 }
 2935 
 2936 pure @safe nothrow @nogc unittest
 2937 {
 2938     struct NonSlicingForwardRange
 2939     {
 2940         enum empty = false;
 2941         int front() { return 42; }
 2942         void popFront() {}
 2943         @property auto save() { return this; }
 2944     }
 2945 
 2946     static assert(isForwardRange!NonSlicingForwardRange);
 2947     static assert(!hasSlicing!NonSlicingForwardRange);
 2948 
 2949     auto s = takeOne(NonSlicingForwardRange());
 2950     assert(s.length == 1);
 2951     assert(!s.empty);
 2952     assert(s.front == 42);
 2953     assert(s.back == 42);
 2954     assert(s[0] == 42);
 2955     auto t = s.save;
 2956     s.popFront();
 2957     assert(s.length == 0);
 2958     assert(s.empty);
 2959     assert(!t.empty);
 2960     assert(t.front == 42);
 2961     t.popBack();
 2962     assert(t.empty);
 2963     assert(t.length == 0);
 2964 }
 2965 
 2966 // Test that asserts trigger correctly
 2967 @system unittest
 2968 {
 2969     import std.exception : assertThrown;
 2970     import core.exception : AssertError;
 2971 
 2972     struct NonForwardRange
 2973     {
 2974         enum empty = false;
 2975         int front() { return 42; }
 2976         void popFront() {}
 2977     }
 2978 
 2979     auto s = takeOne(NonForwardRange());
 2980 
 2981     assertThrown!AssertError(s[1]);
 2982     assertThrown!AssertError(s[0 .. 2]);
 2983 
 2984     size_t one = 1;     // Avoid style warnings triggered by literals
 2985     size_t zero = 0;
 2986     assertThrown!AssertError(s[one .. zero]);
 2987 
 2988     s.popFront;
 2989     assert(s.empty);
 2990     assertThrown!AssertError(s.front);
 2991     assertThrown!AssertError(s.back);
 2992     assertThrown!AssertError(s.popFront);
 2993     assertThrown!AssertError(s.popBack);
 2994 }
 2995 
 2996 // https://issues.dlang.org/show_bug.cgi?id=16999
 2997 pure @safe unittest
 2998 {
 2999     auto myIota = new class
 3000     {
 3001         int front = 0;
 3002         @safe void popFront(){front++;}
 3003         enum empty = false;
 3004     };
 3005     auto iotaPart = myIota.takeOne;
 3006     int sum;
 3007     foreach (var; chain(iotaPart, iotaPart, iotaPart))
 3008     {
 3009         sum += var;
 3010     }
 3011     assert(sum == 3);
 3012     assert(iotaPart.front == 3);
 3013 }
 3014 
 3015 /++
 3016     Returns an empty range which is statically known to be empty and is
 3017     guaranteed to have `length` and be random access regardless of `R`'s
 3018     capabilities.
 3019   +/
 3020 auto takeNone(R)()
 3021 if (isInputRange!R)
 3022 {
 3023     return typeof(takeOne(R.init)).init;
 3024 }
 3025 
 3026 ///
 3027 pure @safe nothrow @nogc unittest
 3028 {
 3029     auto range = takeNone!(int[])();
 3030     assert(range.length == 0);
 3031     assert(range.empty);
 3032 }
 3033 
 3034 pure @safe nothrow @nogc unittest
 3035 {
 3036     enum ctfe = takeNone!(int[])();
 3037     static assert(ctfe.length == 0);
 3038     static assert(ctfe.empty);
 3039 }
 3040 
 3041 
 3042 /++
 3043     Creates an empty range from the given range in $(BIGOH 1). If it can, it
 3044     will return the same range type. If not, it will return
 3045     $(D takeExactly(range, 0)).
 3046   +/
 3047 auto takeNone(R)(R range)
 3048 if (isInputRange!R)
 3049 {
 3050     import std.traits : isDynamicArray;
 3051     //Makes it so that calls to takeNone which don't use UFCS still work with a
 3052     //member version if it's defined.
 3053     static if (is(typeof(R.takeNone)))
 3054         auto retval = range.takeNone();
 3055     // https://issues.dlang.org/show_bug.cgi?id=8339
 3056     else static if (isDynamicArray!R)/+ ||
 3057                    (is(R == struct) && __traits(compiles, {auto r = R.init;}) && R.init.empty))+/
 3058     {
 3059         auto retval = R.init;
 3060     }
 3061     //An infinite range sliced at [0 .. 0] would likely still not be empty...
 3062     else static if (hasSlicing!R && !isInfinite!R)
 3063         auto retval = range[0 .. 0];
 3064     else
 3065         auto retval = takeExactly(range, 0);
 3066 
 3067     // https://issues.dlang.org/show_bug.cgi?id=7892 prevents this from being
 3068     // done in an out block.
 3069     assert(retval.empty);
 3070     return retval;
 3071 }
 3072 
 3073 ///
 3074 pure @safe nothrow unittest
 3075 {
 3076     import std.algorithm.iteration : filter;
 3077     assert(takeNone([42, 27, 19]).empty);
 3078     assert(takeNone("dlang.org").empty);
 3079     assert(takeNone(filter!"true"([42, 27, 19])).empty);
 3080 }
 3081 
 3082 @safe unittest
 3083 {
 3084     import std.algorithm.iteration : filter;
 3085     import std.meta : AliasSeq;
 3086 
 3087     struct Dummy
 3088     {
 3089         mixin template genInput()
 3090         {
 3091         @safe:
 3092             @property bool empty() { return _arr.empty; }
 3093             @property auto front() { return _arr.front; }
 3094             void popFront() { _arr.popFront(); }
 3095             static assert(isInputRange!(typeof(this)));
 3096         }
 3097     }
 3098     alias genInput = Dummy.genInput;
 3099 
 3100     static struct NormalStruct
 3101     {
 3102         //Disabled to make sure that the takeExactly version is used.
 3103         @disable this();
 3104         this(int[] arr) { _arr = arr; }
 3105         mixin genInput;
 3106         int[] _arr;
 3107     }
 3108 
 3109     static struct SliceStruct
 3110     {
 3111         @disable this();
 3112         this(int[] arr) { _arr = arr; }
 3113         mixin genInput;
 3114         @property auto save() { return this; }
 3115         auto opSlice(size_t i, size_t j) { return typeof(this)(_arr[i .. j]); }
 3116         @property size_t length() { return _arr.length; }
 3117         int[] _arr;
 3118     }
 3119 
 3120     static struct InitStruct
 3121     {
 3122         mixin genInput;
 3123         int[] _arr;
 3124     }
 3125 
 3126     static struct TakeNoneStruct
 3127     {
 3128         this(int[] arr) { _arr = arr; }
 3129         @disable this();
 3130         mixin genInput;
 3131         auto takeNone() { return typeof(this)(null); }
 3132         int[] _arr;
 3133     }
 3134 
 3135     static class NormalClass
 3136     {
 3137         this(int[] arr) {_arr = arr;}
 3138         mixin genInput;
 3139         int[] _arr;
 3140     }
 3141 
 3142     static class SliceClass
 3143     {
 3144     @safe:
 3145         this(int[] arr) { _arr = arr; }
 3146         mixin genInput;
 3147         @property auto save() { return new typeof(this)(_arr); }
 3148         auto opSlice(size_t i, size_t j) { return new typeof(this)(_arr[i .. j]); }
 3149         @property size_t length() { return _arr.length; }
 3150         int[] _arr;
 3151     }
 3152 
 3153     static class TakeNoneClass
 3154     {
 3155     @safe:
 3156         this(int[] arr) { _arr = arr; }
 3157         mixin genInput;
 3158         auto takeNone() { return new typeof(this)(null); }
 3159         int[] _arr;
 3160     }
 3161 
 3162     import std.format : format;
 3163 
 3164     static foreach (range; AliasSeq!([1, 2, 3, 4, 5],
 3165                              "hello world",
 3166                              "hello world"w,
 3167                              "hello world"d,
 3168                              SliceStruct([1, 2, 3]),
 3169                              // https://issues.dlang.org/show_bug.cgi?id=8339
 3170                              // forces this to be takeExactly `InitStruct([1, 2, 3]),
 3171                              TakeNoneStruct([1, 2, 3])))
 3172     {
 3173         static assert(takeNone(range).empty, typeof(range).stringof);
 3174         assert(takeNone(range).empty);
 3175         static assert(is(typeof(range) == typeof(takeNone(range))), typeof(range).stringof);
 3176     }
 3177 
 3178     static foreach (range; AliasSeq!(NormalStruct([1, 2, 3]),
 3179                              InitStruct([1, 2, 3])))
 3180     {
 3181         static assert(takeNone(range).empty, typeof(range).stringof);
 3182         assert(takeNone(range).empty);
 3183         static assert(is(typeof(takeExactly(range, 0)) == typeof(takeNone(range))), typeof(range).stringof);
 3184     }
 3185 
 3186     //Don't work in CTFE.
 3187     auto normal = new NormalClass([1, 2, 3]);
 3188     assert(takeNone(normal).empty);
 3189     static assert(is(typeof(takeExactly(normal, 0)) == typeof(takeNone(normal))), typeof(normal).stringof);
 3190 
 3191     auto slice = new SliceClass([1, 2, 3]);
 3192     assert(takeNone(slice).empty);
 3193     static assert(is(SliceClass == typeof(takeNone(slice))), typeof(slice).stringof);
 3194 
 3195     auto taken = new TakeNoneClass([1, 2, 3]);
 3196     assert(takeNone(taken).empty);
 3197     static assert(is(TakeNoneClass == typeof(takeNone(taken))), typeof(taken).stringof);
 3198 
 3199     auto filtered = filter!"true"([1, 2, 3, 4, 5]);
 3200     assert(takeNone(filtered).empty);
 3201     // https://issues.dlang.org/show_bug.cgi?id=8339 and
 3202     // https://issues.dlang.org/show_bug.cgi?id=5941 force this to be takeExactly
 3203     //static assert(is(typeof(filtered) == typeof(takeNone(filtered))), typeof(filtered).stringof);
 3204 }
 3205 
 3206 /++
 3207  + Return a range advanced to within `_n` elements of the end of
 3208  + `range`.
 3209  +
 3210  + Intended as the range equivalent of the Unix
 3211  + $(HTTP en.wikipedia.org/wiki/Tail_%28Unix%29, _tail) utility. When the length
 3212  + of `range` is less than or equal to `_n`, `range` is returned
 3213  + as-is.
 3214  +
 3215  + Completes in $(BIGOH 1) steps for ranges that support slicing and have
 3216  + length. Completes in $(BIGOH range.length) time for all other ranges.
 3217  +
 3218  + Params:
 3219  +    range = range to get _tail of
 3220  +    n = maximum number of elements to include in _tail
 3221  +
 3222  + Returns:
 3223  +    Returns the _tail of `range` augmented with length information
 3224  +/
 3225 auto tail(Range)(Range range, size_t n)
 3226 if (isInputRange!Range && !isInfinite!Range &&
 3227     (hasLength!Range || isForwardRange!Range))
 3228 {
 3229     static if (hasLength!Range)
 3230     {
 3231         immutable length = range.length;
 3232         if (n >= length)
 3233             return range.takeExactly(length);
 3234         else
 3235             return range.drop(length - n).takeExactly(n);
 3236     }
 3237     else
 3238     {
 3239         Range scout = range.save;
 3240         foreach (immutable i; 0 .. n)
 3241         {
 3242             if (scout.empty)
 3243                 return range.takeExactly(i);
 3244             scout.popFront();
 3245         }
 3246 
 3247         auto tail = range.save;
 3248         while (!scout.empty)
 3249         {
 3250             assert(!tail.empty);
 3251             scout.popFront();
 3252             tail.popFront();
 3253         }
 3254 
 3255         return tail.takeExactly(n);
 3256     }
 3257 }
 3258 
 3259 ///
 3260 pure @safe nothrow unittest
 3261 {
 3262     // tail -c n
 3263     assert([1, 2, 3].tail(1) == [3]);
 3264     assert([1, 2, 3].tail(2) == [2, 3]);
 3265     assert([1, 2, 3].tail(3) == [1, 2, 3]);
 3266     assert([1, 2, 3].tail(4) == [1, 2, 3]);
 3267     assert([1, 2, 3].tail(0).length == 0);
 3268 
 3269     // tail --lines=n
 3270     import std.algorithm.comparison : equal;
 3271     import std.algorithm.iteration : joiner;
 3272     import std.exception : assumeWontThrow;
 3273     import std.string : lineSplitter;
 3274     assert("one\ntwo\nthree"
 3275         .lineSplitter
 3276         .tail(2)
 3277         .joiner("\n")
 3278         .equal("two\nthree")
 3279         .assumeWontThrow);
 3280 }
 3281 
 3282 // @nogc prevented by https://issues.dlang.org/show_bug.cgi?id=15408
 3283 pure nothrow @safe /+@nogc+/ unittest
 3284 {
 3285     import std.algorithm.comparison : equal;
 3286     import std.internal.test.dummyrange : AllDummyRanges, DummyRange, Length,
 3287         RangeType, ReturnBy;
 3288 
 3289     static immutable cheatsheet = [6, 7, 8, 9, 10];
 3290 
 3291     foreach (R; AllDummyRanges)
 3292     {
 3293         static if (isInputRange!R && !isInfinite!R &&
 3294                    (hasLength!R || isForwardRange!R))
 3295         {
 3296             assert(R.init.tail(5).equal(cheatsheet));
 3297             static assert(R.init.tail(5).equal(cheatsheet));
 3298 
 3299             assert(R.init.tail(0).length == 0);
 3300             assert(R.init.tail(10).equal(R.init));
 3301             assert(R.init.tail(11).equal(R.init));
 3302         }
 3303     }
 3304 
 3305     // Infinite ranges are not supported
 3306     static assert(!__traits(compiles, repeat(0).tail(0)));
 3307 
 3308     // Neither are non-forward ranges without length
 3309     static assert(!__traits(compiles, DummyRange!(ReturnBy.Value, Length.No,
 3310         RangeType.Input).init.tail(5)));
 3311 }
 3312 
 3313 pure @safe nothrow @nogc unittest
 3314 {
 3315     static immutable input = [1, 2, 3];
 3316     static immutable expectedOutput = [2, 3];
 3317     assert(input.tail(2) == expectedOutput);
 3318 }
 3319 
 3320 /++
 3321     Convenience function which calls
 3322     $(REF popFrontN, std, range, primitives)`(range, n)` and returns `range`.
 3323     `drop` makes it easier to pop elements from a range
 3324     and then pass it to another function within a single expression,
 3325     whereas `popFrontN` would require multiple statements.
 3326 
 3327     `dropBack` provides the same functionality but instead calls
 3328     $(REF popBackN, std, range, primitives)`(range, n)`
 3329 
 3330     Note: `drop` and `dropBack` will only pop $(I up to)
 3331     `n` elements but will stop if the range is empty first.
 3332     In other languages this is sometimes called `skip`.
 3333 
 3334     Params:
 3335         range = the $(REF_ALTTEXT input range, isInputRange, std,range,primitives) to drop from
 3336         n = the number of elements to drop
 3337 
 3338     Returns:
 3339         `range` with up to `n` elements dropped
 3340 
 3341     See_Also:
 3342         $(REF popFront, std, range, primitives), $(REF popBackN, std, range, primitives)
 3343   +/
 3344 R drop(R)(R range, size_t n)
 3345 if (isInputRange!R)
 3346 {
 3347     range.popFrontN(n);
 3348     return range;
 3349 }
 3350 
 3351 ///
 3352 @safe unittest
 3353 {
 3354     import std.algorithm.comparison : equal;
 3355 
 3356     assert([0, 2, 1, 5, 0, 3].drop(3) == [5, 0, 3]);
 3357     assert("hello world".drop(6) == "world");
 3358     assert("hello world".drop(50).empty);
 3359     assert("hello world".take(6).drop(3).equal("lo "));
 3360 }
 3361 
 3362 /// ditto
 3363 R dropBack(R)(R range, size_t n)
 3364 if (isBidirectionalRange!R)
 3365 {
 3366     range.popBackN(n);
 3367     return range;
 3368 }
 3369 
 3370 ///
 3371 @safe unittest
 3372 {
 3373     import std.algorithm.comparison : equal;
 3374 
 3375     assert([0, 2, 1, 5, 0, 3].dropBack(3) == [0, 2, 1]);
 3376     assert("hello world".dropBack(6) == "hello");
 3377     assert("hello world".dropBack(50).empty);
 3378     assert("hello world".drop(4).dropBack(4).equal("o w"));
 3379 }
 3380 
 3381 @safe unittest
 3382 {
 3383     import std.algorithm.comparison : equal;
 3384     import std.container.dlist : DList;
 3385 
 3386     //Remove all but the first two elements
 3387     auto a = DList!int(0, 1, 9, 9, 9, 9);
 3388     a.remove(a[].drop(2));
 3389     assert(a[].equal(a[].take(2)));
 3390 }
 3391 
 3392 @safe unittest
 3393 {
 3394     import std.algorithm.comparison : equal;
 3395     import std.algorithm.iteration : filter;
 3396 
 3397     assert(drop("", 5).empty);
 3398     assert(equal(drop(filter!"true"([0, 2, 1, 5, 0, 3]), 3), [5, 0, 3]));
 3399 }
 3400 
 3401 @safe unittest
 3402 {
 3403     import std.algorithm.comparison : equal;
 3404     import std.container.dlist : DList;
 3405 
 3406     //insert before the last two elements
 3407     auto a = DList!int(0, 1, 2, 5, 6);
 3408     a.insertAfter(a[].dropBack(2), [3, 4]);
 3409     assert(a[].equal(iota(0, 7)));
 3410 }
 3411 
 3412 /++
 3413     Similar to $(LREF drop) and `dropBack` but they call
 3414     $(D range.$(LREF popFrontExactly)(n)) and `range.popBackExactly(n)`
 3415     instead.
 3416 
 3417     Note: Unlike `drop`, `dropExactly` will assume that the
 3418     range holds at least `n` elements. This makes `dropExactly`
 3419     faster than `drop`, but it also means that if `range` does
 3420     not contain at least `n` elements, it will attempt to call `popFront`
 3421     on an empty range, which is undefined behavior. So, only use
 3422     `popFrontExactly` when it is guaranteed that `range` holds at least
 3423     `n` elements.
 3424 
 3425     Params:
 3426         range = the $(REF_ALTTEXT input range, isInputRange, std,range,primitives) to drop from
 3427         n = the number of elements to drop
 3428 
 3429     Returns:
 3430         `range` with `n` elements dropped
 3431 
 3432     See_Also:
 3433         $(REF popFrontExcatly, std, range, primitives),
 3434         $(REF popBackExcatly, std, range, primitives)
 3435 +/
 3436 R dropExactly(R)(R range, size_t n)
 3437 if (isInputRange!R)
 3438 {
 3439     popFrontExactly(range, n);
 3440     return range;
 3441 }
 3442 /// ditto
 3443 R dropBackExactly(R)(R range, size_t n)
 3444 if (isBidirectionalRange!R)
 3445 {
 3446     popBackExactly(range, n);
 3447     return range;
 3448 }
 3449 
 3450 ///
 3451 @safe unittest
 3452 {
 3453     import std.algorithm.comparison : equal;
 3454     import std.algorithm.iteration : filterBidirectional;
 3455 
 3456     auto a = [1, 2, 3];
 3457     assert(a.dropExactly(2) == [3]);
 3458     assert(a.dropBackExactly(2) == [1]);
 3459 
 3460     string s = "日本語";
 3461     assert(s.dropExactly(2) == "語");
 3462     assert(s.dropBackExactly(2) == "日");
 3463 
 3464     auto bd = filterBidirectional!"true"([1, 2, 3]);
 3465     assert(bd.dropExactly(2).equal([3]));
 3466     assert(bd.dropBackExactly(2).equal([1]));
 3467 }
 3468 
 3469 /++
 3470     Convenience function which calls
 3471     `range.popFront()` and returns `range`. `dropOne`
 3472     makes it easier to pop an element from a range
 3473     and then pass it to another function within a single expression,
 3474     whereas `popFront` would require multiple statements.
 3475 
 3476     `dropBackOne` provides the same functionality but instead calls
 3477     `range.popBack()`.
 3478 +/
 3479 R dropOne(R)(R range)
 3480 if (isInputRange!R)
 3481 {
 3482     range.popFront();
 3483     return range;
 3484 }
 3485 /// ditto
 3486 R dropBackOne(R)(R range)
 3487 if (isBidirectionalRange!R)
 3488 {
 3489     range.popBack();
 3490     return range;
 3491 }
 3492 
 3493 ///
 3494 pure @safe nothrow unittest
 3495 {
 3496     import std.algorithm.comparison : equal;
 3497     import std.algorithm.iteration : filterBidirectional;
 3498     import std.container.dlist : DList;
 3499 
 3500     auto dl = DList!int(9, 1, 2, 3, 9);
 3501     assert(dl[].dropOne().dropBackOne().equal([1, 2, 3]));
 3502 
 3503     auto a = [1, 2, 3];
 3504     assert(a.dropOne() == [2, 3]);
 3505     assert(a.dropBackOne() == [1, 2]);
 3506 
 3507     string s = "日本語";
 3508     import std.exception : assumeWontThrow;
 3509     assert(assumeWontThrow(s.dropOne() == "本語"));
 3510     assert(assumeWontThrow(s.dropBackOne() == "日本"));
 3511 
 3512     auto bd = filterBidirectional!"true"([1, 2, 3]);
 3513     assert(bd.dropOne().equal([2, 3]));
 3514     assert(bd.dropBackOne().equal([1, 2]));
 3515 }
 3516 
 3517 /**
 3518 Create a range which repeats one value.
 3519 
 3520 Params:
 3521     value = the _value to repeat
 3522     n = the number of times to repeat `value`
 3523 
 3524 Returns:
 3525     If `n` is not defined, an infinite random access range
 3526     with slicing.
 3527 
 3528     If `n` is defined, a random access range with slicing.
 3529 */
 3530 struct Repeat(T)
 3531 {
 3532 private:
 3533     //Store a non-qualified T when possible: This is to make Repeat assignable
 3534     static if ((is(T == class) || is(T == interface)) && (is(T == const) || is(T == immutable)))
 3535     {
 3536         import std.typecons : Rebindable;
 3537         alias UT = Rebindable!T;
 3538     }
 3539     else static if (is(T : Unqual!T) && is(Unqual!T : T))
 3540         alias UT = Unqual!T;
 3541     else
 3542         alias UT = T;
 3543     UT _value;
 3544 
 3545 public:
 3546     /// Range primitives
 3547     @property inout(T) front() inout { return _value; }
 3548 
 3549     /// ditto
 3550     @property inout(T) back() inout { return _value; }
 3551 
 3552     /// ditto
 3553     enum bool empty = false;
 3554 
 3555     /// ditto
 3556     void popFront() {}
 3557 
 3558     /// ditto
 3559     void popBack() {}
 3560 
 3561     /// ditto
 3562     @property auto save() inout { return this; }
 3563 
 3564     /// ditto
 3565     inout(T) opIndex(size_t) inout { return _value; }
 3566 
 3567     /// ditto
 3568     auto opSlice(size_t i, size_t j)
 3569     in
 3570     {
 3571         assert(
 3572             i <= j,
 3573             "Attempting to slice a Repeat with a larger first argument than the second."
 3574         );
 3575     }
 3576     do
 3577     {
 3578         return this.takeExactly(j - i);
 3579     }
 3580     private static struct DollarToken {}
 3581 
 3582     /// ditto
 3583     enum opDollar = DollarToken.init;
 3584 
 3585     /// ditto
 3586     auto opSlice(size_t, DollarToken) inout { return this; }
 3587 }
 3588 
 3589 /// Ditto
 3590 Repeat!T repeat(T)(T value) { return Repeat!T(value); }
 3591 
 3592 ///
 3593 pure @safe nothrow unittest
 3594 {
 3595     import std.algorithm.comparison : equal;
 3596 
 3597     assert(5.repeat().take(4).equal([5, 5, 5, 5]));
 3598 }
 3599 
 3600 pure @safe nothrow unittest
 3601 {
 3602     import std.algorithm.comparison : equal;
 3603 
 3604     auto  r = repeat(5);
 3605     alias R = typeof(r);
 3606     static assert(isBidirectionalRange!R);
 3607     static assert(isForwardRange!R);
 3608     static assert(isInfinite!R);
 3609     static assert(hasSlicing!R);
 3610 
 3611     assert(r.back == 5);
 3612     assert(r.front == 5);
 3613     assert(r.take(4).equal([ 5, 5, 5, 5 ]));
 3614     assert(r[0 .. 4].equal([ 5, 5, 5, 5 ]));
 3615 
 3616     R r2 = r[5 .. $];
 3617     assert(r2.back == 5);
 3618     assert(r2.front == 5);
 3619 }
 3620 
 3621 /// ditto
 3622 Take!(Repeat!T) repeat(T)(T value, size_t n)
 3623 {
 3624     return take(repeat(value), n);
 3625 }
 3626 
 3627 ///
 3628 pure @safe nothrow unittest
 3629 {
 3630     import std.algorithm.comparison : equal;
 3631 
 3632     assert(5.repeat(4).equal([5, 5, 5, 5]));
 3633 }
 3634 
 3635 // https://issues.dlang.org/show_bug.cgi?id=12007
 3636 pure @safe nothrow unittest
 3637 {
 3638     static class C{}
 3639     Repeat!(immutable int) ri;
 3640     ri = ri.save;
 3641     Repeat!(immutable C) rc;
 3642     rc = rc.save;
 3643 
 3644     import std.algorithm.setops : cartesianProduct;
 3645     import std.algorithm.comparison : equal;
 3646     import std.typecons : tuple;
 3647     immutable int[] A = [1,2,3];
 3648     immutable int[] B = [4,5,6];
 3649 
 3650     assert(equal(cartesianProduct(A,B),
 3651         [
 3652             tuple(1, 4), tuple(1, 5), tuple(1, 6),
 3653             tuple(2, 4), tuple(2, 5), tuple(2, 6),
 3654             tuple(3, 4), tuple(3, 5), tuple(3, 6),
 3655         ]));
 3656 }
 3657 
 3658 /**
 3659 Given callable ($(REF isCallable, std,traits)) `fun`, create as a range
 3660 whose front is defined by successive calls to `fun()`.
 3661 This is especially useful to call function with global side effects (random
 3662 functions), or to create ranges expressed as a single delegate, rather than
 3663 an entire `front`/`popFront`/`empty` structure.
 3664 `fun` maybe be passed either a template alias parameter (existing
 3665 function, delegate, struct type defining `static opCall`) or
 3666 a run-time value argument (delegate, function object).
 3667 The result range models an InputRange
 3668 ($(REF isInputRange, std,range,primitives)).
 3669 The resulting range will call `fun()` on construction, and every call to
 3670 `popFront`, and the cached value will be returned when `front` is called.
 3671 
 3672 Returns: an `inputRange` where each element represents another call to fun.
 3673 */
 3674 auto generate(Fun)(Fun fun)
 3675 if (isCallable!fun)
 3676 {
 3677     auto gen = Generator!(Fun)(fun);
 3678     gen.popFront(); // prime the first element
 3679     return gen;
 3680 }
 3681 
 3682 /// ditto
 3683 auto generate(alias fun)()
 3684 if (isCallable!fun)
 3685 {
 3686     auto gen = Generator!(fun)();
 3687     gen.popFront(); // prime the first element
 3688     return gen;
 3689 }
 3690 
 3691 ///
 3692 @safe pure nothrow unittest
 3693 {
 3694     import std.algorithm.comparison : equal;
 3695     import std.algorithm.iteration : map;
 3696 
 3697     int i = 1;
 3698     auto powersOfTwo = generate!(() => i *= 2)().take(10);
 3699     assert(equal(powersOfTwo, iota(1, 11).map!"2^^a"()));
 3700 }
 3701 
 3702 ///
 3703 @safe pure nothrow unittest
 3704 {
 3705     import std.algorithm.comparison : equal;
 3706 
 3707     //Returns a run-time delegate
 3708     auto infiniteIota(T)(T low, T high)
 3709     {
 3710         T i = high;
 3711         return (){if (i == high) i = low; return i++;};
 3712     }
 3713     //adapted as a range.
 3714     assert(equal(generate(infiniteIota(1, 4)).take(10), [1, 2, 3, 1, 2, 3, 1, 2, 3, 1]));
 3715 }
 3716 
 3717 ///
 3718 @safe unittest
 3719 {
 3720     import std.format : format;
 3721     import std.random : uniform;
 3722 
 3723     auto r = generate!(() => uniform(0, 6)).take(10);
 3724     format("%(%s %)", r);
 3725 }
 3726 
 3727 private struct Generator(Fun...)
 3728 {
 3729     static assert(Fun.length == 1);
 3730     static assert(isInputRange!Generator);
 3731     import std.traits : FunctionAttribute, functionAttributes, ReturnType;
 3732 
 3733 private:
 3734     static if (is(Fun[0]))
 3735         Fun[0] fun;
 3736     else
 3737         alias fun = Fun[0];
 3738 
 3739     enum returnByRef_ = (functionAttributes!fun & FunctionAttribute.ref_) ? true : false;
 3740     static if (returnByRef_)
 3741         ReturnType!fun *elem_;
 3742     else
 3743         ReturnType!fun elem_;
 3744 public:
 3745     /// Range primitives
 3746     enum empty = false;
 3747 
 3748     static if (returnByRef_)
 3749     {
 3750         /// ditto
 3751         ref front() @property
 3752         {
 3753             return *elem_;
 3754         }
 3755         /// ditto
 3756         void popFront()
 3757         {
 3758             elem_ = &fun();
 3759         }
 3760     }
 3761     else
 3762     {
 3763         /// ditto
 3764         auto front() @property
 3765         {
 3766             return elem_;
 3767         }
 3768         /// ditto
 3769         void popFront()
 3770         {
 3771             elem_ = fun();
 3772         }
 3773     }
 3774 }
 3775 
 3776 @safe nothrow unittest
 3777 {
 3778     import std.algorithm.comparison : equal;
 3779 
 3780     struct StaticOpCall
 3781     {
 3782         static ubyte opCall() { return 5 ; }
 3783     }
 3784 
 3785     assert(equal(generate!StaticOpCall().take(10), repeat(5).take(10)));
 3786 }
 3787 
 3788 @safe pure unittest
 3789 {
 3790     import std.algorithm.comparison : equal;
 3791 
 3792     struct OpCall
 3793     {
 3794         ubyte opCall() @safe pure { return 5 ; }
 3795     }
 3796 
 3797     OpCall op;
 3798     assert(equal(generate(op).take(10), repeat(5).take(10)));
 3799 }
 3800 
 3801 // verify ref mechanism works
 3802 @system nothrow unittest
 3803 {
 3804     int[10] arr;
 3805     int idx;
 3806 
 3807     ref int fun() {
 3808         auto x = idx++;
 3809         idx %= arr.length;
 3810         return arr[x];
 3811     }
 3812     int y = 1;
 3813     foreach (ref x; generate!(fun).take(20))
 3814     {
 3815         x += y++;
 3816     }
 3817     import std.algorithm.comparison : equal;
 3818     assert(equal(arr[], iota(12, 32, 2)));
 3819 }
 3820 
 3821 // assure front isn't the mechanism to make generate go to the next element.
 3822 @safe unittest
 3823 {
 3824     int i;
 3825     auto g = generate!(() => ++i);
 3826     auto f = g.front;
 3827     assert(f == g.front);
 3828     g = g.drop(5); // reassign because generate caches
 3829     assert(g.front == f + 5);
 3830 }
 3831 
 3832 /**
 3833 Repeats the given forward range ad infinitum. If the original range is
 3834 infinite (fact that would make `Cycle` the identity application),
 3835 `Cycle` detects that and aliases itself to the range type
 3836 itself. That works for non-forward ranges too.
 3837 If the original range has random access, `Cycle` offers
 3838 random access and also offers a constructor taking an initial position
 3839 `index`. `Cycle` works with static arrays in addition to ranges,
 3840 mostly for performance reasons.
 3841 
 3842 Note: The input range must not be empty.
 3843 
 3844 Tip: This is a great way to implement simple circular buffers.
 3845 */
 3846 struct Cycle(R)
 3847 if (isForwardRange!R && !isInfinite!R)
 3848 {
 3849     static if (isRandomAccessRange!R && hasLength!R)
 3850     {
 3851         private R _original;
 3852         private size_t _index;
 3853 
 3854         /// Range primitives
 3855         this(R input, size_t index = 0)
 3856         {
 3857             _original = input;
 3858             _index = index % _original.length;
 3859         }
 3860 
 3861         /// ditto
 3862         @property auto ref front()
 3863         {
 3864             return _original[_index];
 3865         }
 3866 
 3867         static if (is(typeof((cast(const R)_original)[_index])))
 3868         {
 3869             /// ditto
 3870             @property auto ref front() const
 3871             {
 3872                 return _original[_index];
 3873             }
 3874         }
 3875 
 3876         static if (hasAssignableElements!R)
 3877         {
 3878             /// ditto
 3879             @property void front(ElementType!R val)
 3880             {
 3881                 _original[_index] = val;
 3882             }
 3883         }
 3884 
 3885         /// ditto
 3886         enum bool empty = false;
 3887 
 3888         /// ditto
 3889         void popFront()
 3890         {
 3891             ++_index;
 3892             if (_index >= _original.length)
 3893                 _index = 0;
 3894         }
 3895 
 3896         /// ditto
 3897         auto ref opIndex(size_t n)
 3898         {
 3899             return _original[(n + _index) % _original.length];
 3900         }
 3901 
 3902         static if (is(typeof((cast(const R)_original)[_index])) &&
 3903                    is(typeof((cast(const R)_original).length)))
 3904         {
 3905             /// ditto
 3906             auto ref opIndex(size_t n) const
 3907             {
 3908                 return _original[(n + _index) % _original.length];
 3909             }
 3910         }
 3911 
 3912         static if (hasAssignableElements!R)
 3913         {
 3914             /// ditto
 3915             void opIndexAssign(ElementType!R val, size_t n)
 3916             {
 3917                 _original[(n + _index) % _original.length] = val;
 3918             }
 3919         }
 3920 
 3921         /// ditto
 3922         @property Cycle save()
 3923         {
 3924             //No need to call _original.save, because Cycle never actually modifies _original
 3925             return Cycle(_original, _index);
 3926         }
 3927 
 3928         private static struct DollarToken {}
 3929 
 3930         /// ditto
 3931         enum opDollar = DollarToken.init;
 3932 
 3933         static if (hasSlicing!R)
 3934         {
 3935             /// ditto
 3936             auto opSlice(size_t i, size_t j)
 3937             in
 3938             {
 3939                 assert(i <= j);
 3940             }
 3941             do
 3942             {
 3943                 return this[i .. $].takeExactly(j - i);
 3944             }
 3945 
 3946             /// ditto
 3947             auto opSlice(size_t i, DollarToken)
 3948             {
 3949                 return typeof(this)(_original, _index + i);
 3950             }
 3951         }
 3952     }
 3953     else
 3954     {
 3955         private R _original;
 3956         private R _current;
 3957 
 3958         /// ditto
 3959         this(R input)
 3960         {
 3961             _original = input;
 3962             _current = input.save;
 3963         }
 3964 
 3965         private this(R original, R current)
 3966         {
 3967             _original = original;
 3968             _current = current;
 3969         }
 3970 
 3971         /// ditto
 3972         @property auto ref front()
 3973         {
 3974             return _current.front;
 3975         }
 3976 
 3977         static if (is(typeof((cast(const R)_current).front)))
 3978         {
 3979             /// ditto
 3980             @property auto ref front() const
 3981             {
 3982                 return _current.front;
 3983             }
 3984         }
 3985 
 3986         static if (hasAssignableElements!R)
 3987         {
 3988             /// ditto
 3989             @property auto front(ElementType!R val)
 3990             {
 3991                 return _current.front = val;
 3992             }
 3993         }
 3994 
 3995         /// ditto
 3996         enum bool empty = false;
 3997 
 3998         /// ditto
 3999         void popFront()
 4000         {
 4001             _current.popFront();
 4002             if (_current.empty)
 4003                 _current = _original.save;
 4004         }
 4005 
 4006         /// ditto
 4007         @property Cycle save()
 4008         {
 4009             //No need to call _original.save, because Cycle never actually modifies _original
 4010             return Cycle(_original, _current.save);
 4011         }
 4012     }
 4013 }
 4014 
 4015 /// ditto
 4016 template Cycle(R)
 4017 if (isInfinite!R)
 4018 {
 4019     alias Cycle = R;
 4020 }
 4021 
 4022 /// ditto
 4023 struct Cycle(R)
 4024 if (isStaticArray!R)
 4025 {
 4026     private alias ElementType = typeof(R.init[0]);
 4027     private ElementType* _ptr;
 4028     private size_t _index;
 4029 
 4030 nothrow:
 4031 
 4032     /// Range primitives
 4033     this(ref R input, size_t index = 0) @system
 4034     {
 4035         _ptr = input.ptr;
 4036         _index = index % R.length;
 4037     }
 4038 
 4039     /// ditto
 4040     @property ref inout(ElementType) front() inout @safe
 4041     {
 4042         static ref auto trustedPtrIdx(typeof(_ptr) p, size_t idx) @trusted
 4043         {
 4044             return p[idx];
 4045         }
 4046         return trustedPtrIdx(_ptr, _index);
 4047     }
 4048 
 4049     /// ditto
 4050     enum bool empty = false;
 4051 
 4052     /// ditto
 4053     void popFront() @safe
 4054     {
 4055         ++_index;
 4056         if (_index >= R.length)
 4057             _index = 0;
 4058     }
 4059 
 4060     /// ditto
 4061     ref inout(ElementType) opIndex(size_t n) inout @safe
 4062     {
 4063         static ref auto trustedPtrIdx(typeof(_ptr) p, size_t idx) @trusted
 4064         {
 4065             return p[idx % R.length];
 4066         }
 4067         return trustedPtrIdx(_ptr, n + _index);
 4068     }
 4069 
 4070     /// ditto
 4071     @property inout(Cycle) save() inout @safe
 4072     {
 4073         return this;
 4074     }
 4075 
 4076     private static struct DollarToken {}
 4077     /// ditto
 4078     enum opDollar = DollarToken.init;
 4079 
 4080     /// ditto
 4081     auto opSlice(size_t i, size_t j) @safe
 4082     in
 4083     {
 4084         assert(
 4085             i <= j,
 4086             "Attempting to slice a Repeat with a larger first argument than the second."
 4087         );
 4088     }
 4089     do
 4090     {
 4091         return this[i .. $].takeExactly(j - i);
 4092     }
 4093 
 4094     /// ditto
 4095     inout(typeof(this)) opSlice(size_t i, DollarToken) inout @safe
 4096     {
 4097         static auto trustedCtor(typeof(_ptr) p, size_t idx) @trusted
 4098         {
 4099             return cast(inout) Cycle(*cast(R*)(p), idx);
 4100         }
 4101         return trustedCtor(_ptr, _index + i);
 4102     }
 4103 }
 4104 
 4105 /// Ditto
 4106 auto cycle(R)(R input)
 4107 if (isInputRange!R)
 4108 {
 4109     static assert(isForwardRange!R || isInfinite!R,
 4110         "Cycle requires a forward range argument unless it's statically known"
 4111          ~ " to be infinite");
 4112     assert(!input.empty, "Attempting to pass an empty input to cycle");
 4113     static if (isInfinite!R) return input;
 4114     else return Cycle!R(input);
 4115 }
 4116 
 4117 ///
 4118 @safe unittest
 4119 {
 4120     import std.algorithm.comparison : equal;
 4121     import std.range : cycle, take;
 4122 
 4123     // Here we create an infinitive cyclic sequence from [1, 2]
 4124     // (i.e. get here [1, 2, 1, 2, 1, 2 and so on]) then
 4125     // take 5 elements of this sequence (so we have [1, 2, 1, 2, 1])
 4126     // and compare them with the expected values for equality.
 4127     assert(cycle([1, 2]).take(5).equal([ 1, 2, 1, 2, 1 ]));
 4128 }
 4129 
 4130 /// Ditto
 4131 Cycle!R cycle(R)(R input, size_t index = 0)
 4132 if (isRandomAccessRange!R && !isInfinite!R)
 4133 {
 4134     assert(!input.empty, "Attempting to pass an empty input to cycle");
 4135     return Cycle!R(input, index);
 4136 }
 4137 
 4138 /// Ditto
 4139 Cycle!R cycle(R)(ref R input, size_t index = 0) @system
 4140 if (isStaticArray!R)
 4141 {
 4142     return Cycle!R(input, index);
 4143 }
 4144 
 4145 @safe nothrow unittest
 4146 {
 4147     import std.algorithm.comparison : equal;
 4148     import std.internal.test.dummyrange : AllDummyRanges;
 4149 
 4150     static assert(isForwardRange!(Cycle!(uint[])));
 4151 
 4152     // Make sure ref is getting propagated properly.
 4153     int[] nums = [1,2,3];
 4154     auto c2 = cycle(nums);
 4155     c2[3]++;
 4156     assert(nums[0] == 2);
 4157 
 4158     immutable int[] immarr = [1, 2, 3];
 4159 
 4160     foreach (DummyType; AllDummyRanges)
 4161     {
 4162         static if (isForwardRange!DummyType)
 4163         {
 4164             DummyType dummy;
 4165             auto cy = cycle(dummy);
 4166             static assert(isForwardRange!(typeof(cy)));
 4167             auto t = take(cy, 20);
 4168             assert(equal(t, [1,2,3,4,5,6,7,8,9,10,1,2,3,4,5,6,7,8,9,10]));
 4169 
 4170             const cRange = cy;
 4171             assert(cRange.front == 1);
 4172 
 4173             static if (hasAssignableElements!DummyType)
 4174             {
 4175                 {
 4176                     cy.front = 66;
 4177                     scope(exit) cy.front = 1;
 4178                     assert(dummy.front == 66);
 4179                 }
 4180 
 4181                 static if (isRandomAccessRange!DummyType)
 4182                 {
 4183                     {
 4184                         cy[10] = 66;
 4185                         scope(exit) cy[10] = 1;
 4186                         assert(dummy.front == 66);
 4187                     }
 4188 
 4189                     assert(cRange[10] == 1);
 4190                 }
 4191             }
 4192 
 4193             static if (hasSlicing!DummyType)
 4194             {
 4195                 auto slice = cy[5 .. 15];
 4196                 assert(equal(slice, [6, 7, 8, 9, 10, 1, 2, 3, 4, 5]));
 4197                 static assert(is(typeof(slice) == typeof(takeExactly(cy, 5))));
 4198 
 4199                 auto infSlice = cy[7 .. $];
 4200                 assert(equal(take(infSlice, 5), [8, 9, 10, 1, 2]));
 4201                 static assert(isInfinite!(typeof(infSlice)));
 4202             }
 4203         }
 4204     }
 4205 }
 4206 
 4207 @system nothrow unittest // For static arrays.
 4208 {
 4209     import std.algorithm.comparison : equal;
 4210 
 4211     int[3] a = [ 1, 2, 3 ];
 4212     static assert(isStaticArray!(typeof(a)));
 4213     auto c = cycle(a);
 4214     assert(a.ptr == c._ptr);
 4215     assert(equal(take(cycle(a), 5), [ 1, 2, 3, 1, 2 ][]));
 4216     static assert(isForwardRange!(typeof(c)));
 4217 
 4218     // Test qualifiers on slicing.
 4219     alias C = typeof(c);
 4220     static assert(is(typeof(c[1 .. $]) == C));
 4221     const cConst = c;
 4222     static assert(is(typeof(cConst[1 .. $]) == const(C)));
 4223 }
 4224 
 4225 @safe nothrow unittest // For infinite ranges
 4226 {
 4227     struct InfRange
 4228     {
 4229         void popFront() { }
 4230         @property int front() { return 0; }
 4231         enum empty = false;
 4232         auto save() { return this; }
 4233     }
 4234     struct NonForwardInfRange
 4235     {
 4236         void popFront() { }
 4237         @property int front() { return 0; }
 4238         enum empty = false;
 4239     }
 4240 
 4241     InfRange i;
 4242     NonForwardInfRange j;
 4243     auto c = cycle(i);
 4244     assert(c == i);
 4245     //make sure it can alias out even non-forward infinite ranges
 4246     static assert(is(typeof(j.cycle) == typeof(j)));
 4247 }
 4248 
 4249 @safe unittest
 4250 {
 4251     import std.algorithm.comparison : equal;
 4252 
 4253     int[5] arr = [0, 1, 2, 3, 4];
 4254     auto cleD = cycle(arr[]); //Dynamic
 4255     assert(equal(cleD[5 .. 10], arr[]));
 4256 
 4257     //n is a multiple of 5 worth about 3/4 of size_t.max
 4258     auto n = size_t.max/4 + size_t.max/2;
 4259     n -= n % 5;
 4260 
 4261     //Test index overflow
 4262     foreach (_ ; 0 .. 10)
 4263     {
 4264         cleD = cleD[n .. $];
 4265         assert(equal(cleD[5 .. 10], arr[]));
 4266     }
 4267 }
 4268 
 4269 @system @nogc nothrow unittest
 4270 {
 4271     import std.algorithm.comparison : equal;
 4272 
 4273     int[5] arr = [0, 1, 2, 3, 4];
 4274     auto cleS = cycle(arr);   //Static
 4275     assert(equal(cleS[5 .. 10], arr[]));
 4276 
 4277     //n is a multiple of 5 worth about 3/4 of size_t.max
 4278     auto n = size_t.max/4 + size_t.max/2;
 4279     n -= n % 5;
 4280 
 4281     //Test index overflow
 4282     foreach (_ ; 0 .. 10)
 4283     {
 4284         cleS = cleS[n .. $];
 4285         assert(equal(cleS[5 .. 10], arr[]));
 4286     }
 4287 }
 4288 
 4289 @system unittest
 4290 {
 4291     import std.algorithm.comparison : equal;
 4292 
 4293     int[1] arr = [0];
 4294     auto cleS = cycle(arr);
 4295     cleS = cleS[10 .. $];
 4296     assert(equal(cleS[5 .. 10], 0.repeat(5)));
 4297     assert(cleS.front == 0);
 4298 }
 4299 
 4300 // https://issues.dlang.org/show_bug.cgi?id=10845
 4301 @system unittest
 4302 {
 4303     import std.algorithm.comparison : equal;
 4304     import std.algorithm.iteration : filter;
 4305 
 4306     auto a = inputRangeObject(iota(3).filter!"true");
 4307     assert(equal(cycle(a).take(10), [0, 1, 2, 0, 1, 2, 0, 1, 2, 0]));
 4308 }
 4309 
 4310 // https://issues.dlang.org/show_bug.cgi?id=12177
 4311 @safe unittest
 4312 {
 4313     static assert(__traits(compiles, recurrence!q{a[n - 1] ~ a[n - 2]}("1", "0")));
 4314 }
 4315 
 4316 // https://issues.dlang.org/show_bug.cgi?id=13390
 4317 @system unittest
 4318 {
 4319     import core.exception : AssertError;
 4320     import std.exception : assertThrown;
 4321     assertThrown!AssertError(cycle([0, 1, 2][0 .. 0]));
 4322 }
 4323 
 4324 // https://issues.dlang.org/show_bug.cgi?id=18657
 4325 pure @safe unittest
 4326 {
 4327     import std.algorithm.comparison : equal;
 4328     string s = "foo";
 4329     auto r = refRange(&s).cycle.take(4);
 4330     assert(equal(r.save, "foof"));
 4331     assert(equal(r.save, "foof"));
 4332 }
 4333 
 4334 private alias lengthType(R) = typeof(R.init.length.init);
 4335 
 4336 /**
 4337    Iterate several ranges in lockstep. The element type is a proxy tuple
 4338    that allows accessing the current element in the `n`th range by
 4339    using `e[n]`.
 4340 
 4341    `zip` is similar to $(LREF lockstep), but `lockstep` doesn't
 4342    bundle its elements and uses the `opApply` protocol.
 4343    `lockstep` allows reference access to the elements in
 4344    `foreach` iterations.
 4345 
 4346     Params:
 4347         sp = controls what `zip` will do if the ranges are different lengths
 4348         ranges = the ranges to zip together
 4349     Returns:
 4350         At minimum, an input range. `Zip` offers the lowest range facilities
 4351         of all components, e.g. it offers random access iff all ranges offer
 4352         random access, and also offers mutation and swapping if all ranges offer
 4353         it. Due to this, `Zip` is extremely powerful because it allows manipulating
 4354         several ranges in lockstep.
 4355     Throws:
 4356         An `Exception` if all of the ranges are not the same length and
 4357         `sp` is set to `StoppingPolicy.requireSameLength`.
 4358 
 4359     Limitations: The `@nogc` and `nothrow` attributes cannot be inferred for
 4360     the `Zip` struct because $(LREF StoppingPolicy) can vary at runtime. This
 4361     limitation is not shared by the anonymous range returned by the `zip`
 4362     function when not given an explicit `StoppingPolicy` as an argument.
 4363 */
 4364 struct Zip(Ranges...)
 4365 if (Ranges.length && allSatisfy!(isInputRange, Ranges))
 4366 {
 4367     import std.format : format; //for generic mixins
 4368     import std.typecons : Tuple;
 4369 
 4370     alias R = Ranges;
 4371     private R ranges;
 4372     alias ElementType = Tuple!(staticMap!(.ElementType, R));
 4373     private StoppingPolicy stoppingPolicy = StoppingPolicy.shortest;
 4374 
 4375 /**
 4376    Builds an object. Usually this is invoked indirectly by using the
 4377    $(LREF zip) function.
 4378  */
 4379     this(R rs, StoppingPolicy s = StoppingPolicy.shortest)
 4380     {
 4381         ranges[] = rs[];
 4382         stoppingPolicy = s;
 4383     }
 4384 
 4385 /**
 4386    Returns `true` if the range is at end. The test depends on the
 4387    stopping policy.
 4388 */
 4389     static if (allSatisfy!(isInfinite, R))
 4390     {
 4391         // BUG:  Doesn't propagate infiniteness if only some ranges are infinite
 4392         //       and s == StoppingPolicy.longest.  This isn't fixable in the
 4393         //       current design since StoppingPolicy is known only at runtime.
 4394         enum bool empty = false;
 4395     }
 4396     else
 4397     {
 4398         ///
 4399         @property bool empty()
 4400         {
 4401             import std.exception : enforce;
 4402             import std.meta : anySatisfy;
 4403 
 4404             final switch (stoppingPolicy)
 4405             {
 4406             case StoppingPolicy.shortest:
 4407                 foreach (i, Unused; R)
 4408                 {
 4409                     if (ranges[i].empty) return true;
 4410                 }
 4411                 return false;
 4412             case StoppingPolicy.longest:
 4413                 static if (anySatisfy!(isInfinite, R))
 4414                 {
 4415                     return false;
 4416                 }
 4417                 else
 4418                 {
 4419                     foreach (i, Unused; R)
 4420                     {
 4421                         if (!ranges[i].empty) return false;
 4422                     }
 4423                     return true;
 4424                 }
 4425             case StoppingPolicy.requireSameLength:
 4426                 foreach (i, Unused; R[1 .. $])
 4427                 {
 4428                     enforce(ranges[0].empty ==
 4429                             ranges[i + 1].empty,
 4430                             "Inequal-length ranges passed to Zip");
 4431                 }
 4432                 return ranges[0].empty;
 4433             }
 4434             assert(false);
 4435         }
 4436     }
 4437 
 4438     static if (allSatisfy!(isForwardRange, R))
 4439     {
 4440         ///
 4441         @property Zip save()
 4442         {
 4443             //Zip(ranges[0].save, ranges[1].save, ..., stoppingPolicy)
 4444             return mixin (q{Zip(%(ranges[%s].save%|, %), stoppingPolicy)}.format(iota(0, R.length)));
 4445         }
 4446     }
 4447 
 4448     private .ElementType!(R[i]) tryGetInit(size_t i)()
 4449     {
 4450         alias E = .ElementType!(R[i]);
 4451         static if (!is(typeof({static E i;})))
 4452             throw new Exception("Range with non-default constructable elements exhausted.");
 4453         else
 4454             return E.init;
 4455     }
 4456 
 4457 /**
 4458    Returns the current iterated element.
 4459 */
 4460     @property ElementType front()
 4461     {
 4462         @property tryGetFront(size_t i)(){return ranges[i].empty ? tryGetInit!i() : ranges[i].front;}
 4463         //ElementType(tryGetFront!0, tryGetFront!1, ...)
 4464         return mixin(q{ElementType(%(tryGetFront!%s, %))}.format(iota(0, R.length)));
 4465     }
 4466 
 4467 /**
 4468    Sets the front of all iterated ranges.
 4469 */
 4470     static if (allSatisfy!(hasAssignableElements, R))
 4471     {
 4472         @property void front(ElementType v)
 4473         {
 4474             foreach (i, Unused; R)
 4475             {
 4476                 if (!ranges[i].empty)
 4477                 {
 4478                     ranges[i].front = v[i];
 4479                 }
 4480             }
 4481         }
 4482     }
 4483 
 4484 /**
 4485    Moves out the front.
 4486 */
 4487     static if (allSatisfy!(hasMobileElements, R))
 4488     {
 4489         ElementType moveFront()
 4490         {
 4491             @property tryMoveFront(size_t i)(){return ranges[i].empty ? tryGetInit!i() : ranges[i].moveFront();}
 4492             //ElementType(tryMoveFront!0, tryMoveFront!1, ...)
 4493             return mixin(q{ElementType(%(tryMoveFront!%s, %))}.format(iota(0, R.length)));
 4494         }
 4495     }
 4496 
 4497 /**
 4498    Returns the rightmost element.
 4499 */
 4500     static if (allSatisfy!(isBidirectionalRange, R))
 4501     {
 4502         @property ElementType back()
 4503         {
 4504             //TODO: Fixme! BackElement != back of all ranges in case of jagged-ness
 4505 
 4506             @property tryGetBack(size_t i)(){return ranges[i].empty ? tryGetInit!i() : ranges[i].back;}
 4507             //ElementType(tryGetBack!0, tryGetBack!1, ...)
 4508             return mixin(q{ElementType(%(tryGetBack!%s, %))}.format(iota(0, R.length)));
 4509         }
 4510 
 4511 /**
 4512    Moves out the back.
 4513 */
 4514         static if (allSatisfy!(hasMobileElements, R))
 4515         {
 4516             ElementType moveBack()
 4517             {
 4518                 //TODO: Fixme! BackElement != back of all ranges in case of jagged-ness
 4519 
 4520                 @property tryMoveBack(size_t i)(){return ranges[i].empty ? tryGetInit!i() : ranges[i].moveBack();}
 4521                 //ElementType(tryMoveBack!0, tryMoveBack!1, ...)
 4522                 return mixin(q{ElementType(%(tryMoveBack!%s, %))}.format(iota(0, R.length)));
 4523             }
 4524         }
 4525 
 4526 /**
 4527    Returns the current iterated element.
 4528 */
 4529         static if (allSatisfy!(hasAssignableElements, R))
 4530         {
 4531             @property void back(ElementType v)
 4532             {
 4533                 //TODO: Fixme! BackElement != back of all ranges in case of jagged-ness.
 4534                 //Not sure the call is even legal for StoppingPolicy.longest
 4535 
 4536                 foreach (i, Unused; R)
 4537                 {
 4538                     if (!ranges[i].empty)
 4539                     {
 4540                         ranges[i].back = v[i];
 4541                     }
 4542                 }
 4543             }
 4544         }
 4545     }
 4546 
 4547 /**
 4548    Advances to the next element in all controlled ranges.
 4549 */
 4550     void popFront()
 4551     {
 4552         import std.exception : enforce;
 4553 
 4554         final switch (stoppingPolicy)
 4555         {
 4556         case StoppingPolicy.shortest:
 4557             foreach (i, Unused; R)
 4558             {
 4559                 assert(!ranges[i].empty);
 4560                 ranges[i].popFront();
 4561             }
 4562             break;
 4563         case StoppingPolicy.longest:
 4564             foreach (i, Unused; R)
 4565             {
 4566                 if (!ranges[i].empty) ranges[i].popFront();
 4567             }
 4568             break;
 4569         case StoppingPolicy.requireSameLength:
 4570             foreach (i, Unused; R)
 4571             {
 4572                 enforce(!ranges[i].empty, "Invalid Zip object");
 4573                 ranges[i].popFront();
 4574             }
 4575             break;
 4576         }
 4577     }
 4578 
 4579 /**
 4580    Calls `popBack` for all controlled ranges.
 4581 */
 4582     static if (allSatisfy!(isBidirectionalRange, R))
 4583     {
 4584         void popBack()
 4585         {
 4586             //TODO: Fixme! In case of jaggedness, this is wrong.
 4587             import std.exception : enforce;
 4588 
 4589             final switch (stoppingPolicy)
 4590             {
 4591             case StoppingPolicy.shortest:
 4592                 foreach (i, Unused; R)
 4593                 {
 4594                     assert(!ranges[i].empty);
 4595                     ranges[i].popBack();
 4596                 }
 4597                 break;
 4598             case StoppingPolicy.longest:
 4599                 foreach (i, Unused; R)
 4600                 {
 4601                     if (!ranges[i].empty) ranges[i].popBack();
 4602                 }
 4603                 break;
 4604             case StoppingPolicy.requireSameLength:
 4605                 foreach (i, Unused; R)
 4606                 {
 4607                     enforce(!ranges[i].empty, "Invalid Zip object");
 4608                     ranges[i].popBack();
 4609                 }
 4610                 break;
 4611             }
 4612         }
 4613     }
 4614 
 4615 /**
 4616    Returns the length of this range. Defined only if all ranges define
 4617    `length`.
 4618 */
 4619     static if (allSatisfy!(hasLength, R))
 4620     {
 4621         @property auto length()
 4622         {
 4623             static if (Ranges.length == 1)
 4624                 return ranges[0].length;
 4625             else
 4626             {
 4627                 if (stoppingPolicy == StoppingPolicy.requireSameLength)
 4628                     return ranges[0].length;
 4629 
 4630                 //[min|max](ranges[0].length, ranges[1].length, ...)
 4631                 import std.algorithm.comparison : min, max;
 4632                 if (stoppingPolicy == StoppingPolicy.shortest)
 4633                     return mixin(q{min(%(ranges[%s].length%|, %))}.format(iota(0, R.length)));
 4634                 else
 4635                     return mixin(q{max(%(ranges[%s].length%|, %))}.format(iota(0, R.length)));
 4636             }
 4637         }
 4638 
 4639         alias opDollar = length;
 4640     }
 4641 
 4642 /**
 4643    Returns a slice of the range. Defined only if all range define
 4644    slicing.
 4645 */
 4646     static if (allSatisfy!(hasSlicing, R))
 4647     {
 4648         auto opSlice(size_t from, size_t to)
 4649         {
 4650             //Slicing an infinite range yields the type Take!R
 4651             //For finite ranges, the type Take!R aliases to R
 4652             alias ZipResult = Zip!(staticMap!(Take, R));
 4653 
 4654             //ZipResult(ranges[0][from .. to], ranges[1][from .. to], ..., stoppingPolicy)
 4655             return mixin (q{ZipResult(%(ranges[%s][from .. to]%|, %), stoppingPolicy)}.format(iota(0, R.length)));
 4656         }
 4657     }
 4658 
 4659 /**
 4660    Returns the `n`th element in the composite range. Defined if all
 4661    ranges offer random access.
 4662 */
 4663     static if (allSatisfy!(isRandomAccessRange, R))
 4664     {
 4665         ElementType opIndex(size_t n)
 4666         {
 4667             //TODO: Fixme! This may create an out of bounds access
 4668             //for StoppingPolicy.longest
 4669 
 4670             //ElementType(ranges[0][n], ranges[1][n], ...)
 4671             return mixin (q{ElementType(%(ranges[%s][n]%|, %))}.format(iota(0, R.length)));
 4672         }
 4673 
 4674 /**
 4675    Assigns to the `n`th element in the composite range. Defined if
 4676    all ranges offer random access.
 4677 */
 4678         static if (allSatisfy!(hasAssignableElements, R))
 4679         {
 4680             void opIndexAssign(ElementType v, size_t n)
 4681             {
 4682                 //TODO: Fixme! Not sure the call is even legal for StoppingPolicy.longest
 4683                 foreach (i, Range; R)
 4684                 {
 4685                     ranges[i][n] = v[i];
 4686                 }
 4687             }
 4688         }
 4689 
 4690 /**
 4691    Destructively reads the `n`th element in the composite
 4692    range. Defined if all ranges offer random access.
 4693 */
 4694         static if (allSatisfy!(hasMobileElements, R))
 4695         {
 4696             ElementType moveAt(size_t n)
 4697             {
 4698                 //TODO: Fixme! This may create an out of bounds access
 4699                 //for StoppingPolicy.longest
 4700 
 4701                 //ElementType(ranges[0].moveAt(n), ranges[1].moveAt(n), ..., )
 4702                 return mixin (q{ElementType(%(ranges[%s].moveAt(n)%|, %))}.format(iota(0, R.length)));
 4703             }
 4704         }
 4705     }
 4706 }
 4707 
 4708 /// Ditto
 4709 auto zip(Ranges...)(Ranges ranges)
 4710 if (Ranges.length && allSatisfy!(isInputRange, Ranges))
 4711 {
 4712     import std.meta : anySatisfy, templateOr;
 4713     static if (allSatisfy!(isInfinite, Ranges) || Ranges.length == 1)
 4714     {
 4715         return ZipShortest!(Ranges)(ranges);
 4716     }
 4717     else static if (allSatisfy!(isBidirectionalRange, Ranges))
 4718     {
 4719         static if (allSatisfy!(templateOr!(isInfinite, hasLength), Ranges)
 4720             && allSatisfy!(templateOr!(isInfinite, hasSlicing), Ranges)
 4721             && allSatisfy!(isBidirectionalRange, staticMap!(Take, Ranges)))
 4722         {
 4723             // If all the ranges are bidirectional, if possible slice them to
 4724             // the same length to simplify the implementation.
 4725             static assert(anySatisfy!(hasLength, Ranges));
 4726             static foreach (i, Range; Ranges)
 4727                 static if (hasLength!Range)
 4728                 {
 4729                     static if (!anySatisfy!(hasLength, Ranges[0 .. i]))
 4730                         size_t minLen = ranges[i].length;
 4731                     else
 4732                     {{
 4733                         const x = ranges[i].length;
 4734                         if (x < minLen) minLen = x;
 4735                     }}
 4736                 }
 4737             import std.format : format;
 4738             static if (!anySatisfy!(isInfinite, Ranges))
 4739                 return mixin(`ZipShortest!(Yes.allKnownSameLength, staticMap!(Take, Ranges))`~
 4740                     `(%(ranges[%s][0 .. minLen]%|, %))`.format(iota(0, Ranges.length)));
 4741             else
 4742                 return mixin(`ZipShortest!(Yes.allKnownSameLength, staticMap!(Take, Ranges))`~
 4743                     `(%(take(ranges[%s], minLen)%|, %))`.format(iota(0, Ranges.length)));
 4744         }
 4745         else static if (allSatisfy!(isRandomAccessRange, Ranges))
 4746         {
 4747             // We can't slice but we can still use random access to ensure
 4748             // "back" is retrieving the same index for each range.
 4749             return ZipShortest!(Ranges)(ranges);
 4750         }
 4751         else
 4752         {
 4753             // If bidirectional range operations would not be supported by
 4754             // ZipShortest that might have actually been a bug since Zip
 4755             // supported `back` without verifying that each range had the
 4756             // same length, but for the sake of backwards compatibility
 4757             // use the old Zip to continue supporting them.
 4758             return Zip!Ranges(ranges);
 4759         }
 4760     }
 4761     else
 4762     {
 4763         return ZipShortest!(Ranges)(ranges);
 4764     }
 4765 }
 4766 
 4767 ///
 4768 @nogc nothrow pure @safe unittest
 4769 {
 4770     import std.algorithm.comparison : equal;
 4771     import std.algorithm.iteration : map;
 4772 
 4773     // pairwise sum
 4774     auto arr = only(0, 1, 2);
 4775     auto part1 = zip(arr, arr.dropOne).map!"a[0] + a[1]";
 4776     assert(part1.equal(only(1, 3)));
 4777 }
 4778 
 4779 ///
 4780 nothrow pure @safe unittest
 4781 {
 4782     import std.conv : to;
 4783 
 4784     int[] a = [ 1, 2, 3 ];
 4785     string[] b = [ "a", "b", "c" ];
 4786     string[] result;
 4787 
 4788     foreach (tup; zip(a, b))
 4789     {
 4790         result ~= tup[0].to!string ~ tup[1];
 4791     }
 4792 
 4793     assert(result == [ "1a", "2b", "3c" ]);
 4794 
 4795     size_t idx = 0;
 4796     // unpacking tuple elements with foreach
 4797     foreach (e1, e2; zip(a, b))
 4798     {
 4799         assert(e1 == a[idx]);
 4800         assert(e2 == b[idx]);
 4801         ++idx;
 4802     }
 4803 }
 4804 
 4805 /// `zip` is powerful - the following code sorts two arrays in parallel:
 4806 nothrow pure @safe unittest
 4807 {
 4808     import std.algorithm.sorting : sort;
 4809 
 4810     int[] a = [ 1, 2, 3 ];
 4811     string[] b = [ "a", "c", "b" ];
 4812     zip(a, b).sort!((t1, t2) => t1[0] > t2[0]);
 4813 
 4814     assert(a == [ 3, 2, 1 ]);
 4815     // b is sorted according to a's sorting
 4816     assert(b == [ "b", "c", "a" ]);
 4817 }
 4818 
 4819 /// Ditto
 4820 auto zip(Ranges...)(StoppingPolicy sp, Ranges ranges)
 4821 if (Ranges.length && allSatisfy!(isInputRange, Ranges))
 4822 {
 4823     return Zip!Ranges(ranges, sp);
 4824 }
 4825 
 4826 /**
 4827    Dictates how iteration in a $(LREF zip) and $(LREF lockstep) should stop.
 4828    By default stop at the end of the shortest of all ranges.
 4829 */
 4830 enum StoppingPolicy
 4831 {
 4832     /// Stop when the shortest range is exhausted
 4833     shortest,
 4834     /// Stop when the longest range is exhausted
 4835     longest,
 4836     /// Require that all ranges are equal
 4837     requireSameLength,
 4838 }
 4839 
 4840 ///
 4841 pure @safe unittest
 4842 {
 4843     import std.algorithm.comparison : equal;
 4844     import std.exception : assertThrown;
 4845     import std.range.primitives;
 4846     import std.typecons : tuple;
 4847 
 4848     auto a = [1, 2, 3];
 4849     auto b = [4, 5, 6, 7];
 4850 
 4851     auto shortest = zip(StoppingPolicy.shortest, a, b);
 4852     assert(shortest.equal([
 4853         tuple(1, 4),
 4854         tuple(2, 5),
 4855         tuple(3, 6)
 4856     ]));
 4857 
 4858     auto longest = zip(StoppingPolicy.longest, a, b);
 4859     assert(longest.equal([
 4860         tuple(1, 4),
 4861         tuple(2, 5),
 4862         tuple(3, 6),
 4863         tuple(0, 7)
 4864     ]));
 4865 
 4866     auto same = zip(StoppingPolicy.requireSameLength, a, b);
 4867     same.popFrontN(3);
 4868     assertThrown!Exception(same.popFront);
 4869 }
 4870 
 4871 /+
 4872 Non-public. Like $(LREF Zip) with `StoppingPolicy.shortest`
 4873 except it properly implements `back` and `popBack` in the
 4874 case of uneven ranges or disables those operations when
 4875 it is not possible to guarantee they are correct.
 4876 +/
 4877 package template ZipShortest(Ranges...)
 4878 if (Ranges.length && __traits(compiles,
 4879     {
 4880         static assert(allSatisfy!(isInputRange, Ranges));
 4881     }))
 4882 {
 4883     alias ZipShortest = .ZipShortest!(
 4884         Ranges.length == 1 || allSatisfy!(isInfinite, Ranges)
 4885             ? Yes.allKnownSameLength
 4886             : No.allKnownSameLength,
 4887         Ranges);
 4888 }
 4889 /+ non-public, ditto +/
 4890 package struct ZipShortest(Flag!"allKnownSameLength" allKnownSameLength, Ranges...)
 4891 if (Ranges.length && allSatisfy!(isInputRange, Ranges))
 4892 {
 4893     import std.format : format; //for generic mixins
 4894     import std.meta : anySatisfy, templateOr;
 4895     import std.typecons : Tuple;
 4896 
 4897     deprecated("Use of an undocumented alias R.")
 4898     alias R = Ranges; // Unused here but defined in case library users rely on it.
 4899     private Ranges ranges;
 4900     alias ElementType = Tuple!(staticMap!(.ElementType, Ranges));
 4901 
 4902     /+
 4903        Builds an object. Usually this is invoked indirectly by using the
 4904        $(LREF zip) function.
 4905     +/
 4906     this(Ranges rs)
 4907     {
 4908         ranges[] = rs[];
 4909     }
 4910 
 4911     /+
 4912        Returns `true` if the range is at end.
 4913     +/
 4914     static if (allKnownSameLength ? anySatisfy!(isInfinite, Ranges)
 4915         : allSatisfy!(isInfinite, Ranges))
 4916     {
 4917         enum bool empty = false;
 4918     }
 4919     else
 4920     {
 4921         @property bool empty()
 4922         {
 4923             static if (allKnownSameLength)
 4924             {
 4925                 return ranges[0].empty;
 4926             }
 4927             else
 4928             {
 4929                 static foreach (i; 0 .. Ranges.length)
 4930                 {
 4931                     if (ranges[i].empty)
 4932                         return true;
 4933                 }
 4934                 return false;
 4935             }
 4936         }
 4937     }
 4938 
 4939     /+
 4940        Forward range primitive. Only present if each constituent range is a
 4941        forward range.
 4942     +/
 4943     static if (allSatisfy!(isForwardRange, Ranges))
 4944     @property typeof(this) save()
 4945     {
 4946         return mixin(`typeof(return)(%(ranges[%s].save%|, %))`.format(iota(0, Ranges.length)));
 4947     }
 4948 
 4949     /+
 4950        Returns the current iterated element.
 4951     +/
 4952     @property ElementType front()
 4953     {
 4954         return mixin(`typeof(return)(%(ranges[%s].front%|, %))`.format(iota(0, Ranges.length)));
 4955     }
 4956 
 4957     /+
 4958        Sets the front of all iterated ranges. Only present if each constituent
 4959        range has assignable elements.
 4960     +/
 4961     static if (allSatisfy!(hasAssignableElements, Ranges))
 4962     @property void front()(ElementType v)
 4963     {
 4964         static foreach (i; 0 .. Ranges.length)
 4965             ranges[i].front = v[i];
 4966     }
 4967 
 4968     /+
 4969        Moves out the front. Present if each constituent range has mobile elements.
 4970     +/
 4971     static if (allSatisfy!(hasMobileElements, Ranges))
 4972     ElementType moveFront()()
 4973     {
 4974         return mixin(`typeof(return)(%(ranges[%s].moveFront()%|, %))`.format(iota(0, Ranges.length)));
 4975     }
 4976 
 4977     private enum bool isBackWellDefined = allSatisfy!(isBidirectionalRange, Ranges)
 4978         && (allKnownSameLength
 4979             || allSatisfy!(isRandomAccessRange, Ranges)
 4980             // Could also add the case where there is one non-infinite bidirectional
 4981             // range that defines `length` and all others are infinite random access
 4982             // ranges. Adding this would require appropriate branches in
 4983             // back/moveBack/popBack.
 4984             );
 4985 
 4986     /+
 4987        Returns the rightmost element. Present if all constituent ranges are
 4988        bidirectional and either there is a compile-time guarantee that all
 4989        ranges have the same length (in `allKnownSameLength`) or all ranges
 4990        provide random access to elements.
 4991     +/
 4992     static if (isBackWellDefined)
 4993     @property ElementType back()
 4994     {
 4995         static if (allKnownSameLength)
 4996         {
 4997             return mixin(`typeof(return)(%(ranges[%s].back()%|, %))`.format(iota(0, Ranges.length)));
 4998         }
 4999         else
 5000         {
 5001             const backIndex = length - 1;
 5002             return mixin(`typeof(return)(%(ranges[%s][backIndex]%|, %))`.format(iota(0, Ranges.length)));
 5003         }
 5004     }
 5005 
 5006     /+
 5007        Moves out the back. Present if `back` is defined and
 5008        each constituent range has mobile elements.
 5009     +/
 5010     static if (isBackWellDefined && allSatisfy!(hasMobileElements, Ranges))
 5011     ElementType moveBack()()
 5012     {
 5013         static if (allKnownSameLength)
 5014         {
 5015             return mixin(`typeof(return)(%(ranges[%s].moveBack()%|, %))`.format(iota(0, Ranges.length)));
 5016         }
 5017         else
 5018         {
 5019             const backIndex = length - 1;
 5020             return mixin(`typeof(return)(%(ranges[%s].moveAt(backIndex)%|, %))`.format(iota(0, Ranges.length)));
 5021         }
 5022     }
 5023 
 5024     /+
 5025        Sets the rightmost element. Only present if `back` is defined and
 5026        each constituent range has assignable elements.
 5027     +/
 5028     static if (isBackWellDefined && allSatisfy!(hasAssignableElements, Ranges))
 5029     @property void back()(ElementType v)
 5030     {
 5031         static if (allKnownSameLength)
 5032         {
 5033             static foreach (i; 0 .. Ranges.length)
 5034                 ranges[i].back = v[i];
 5035         }
 5036         else
 5037         {
 5038             const backIndex = length - 1;
 5039             static foreach (i; 0 .. Ranges.length)
 5040                 ranges[i][backIndex] = v[i];
 5041         }
 5042     }
 5043 
 5044     /+
 5045        Calls `popFront` on each constituent range.
 5046     +/
 5047     void popFront()
 5048     {
 5049         static foreach (i; 0 .. Ranges.length)
 5050             ranges[i].popFront();
 5051     }
 5052 
 5053     /+
 5054        Pops the rightmost element. Present if `back` is defined.
 5055     +/
 5056     static if (isBackWellDefined)
 5057     void popBack()
 5058     {
 5059         static if (allKnownSameLength)
 5060         {
 5061             static foreach (i; 0 .. Ranges.length)
 5062                 ranges[i].popBack;
 5063         }
 5064         else
 5065         {
 5066             const len = length;
 5067             static foreach (i; 0 .. Ranges.length)
 5068                 static if (!isInfinite!(Ranges[i]))
 5069                     if (ranges[i].length == len)
 5070                         ranges[i].popBack();
 5071         }
 5072     }
 5073 
 5074     /+
 5075        Returns the length of this range. Defined if at least one
 5076        constituent range defines `length` and the other ranges all also
 5077        define `length` or are infinite, or if at least one constituent
 5078        range defines `length` and there is a compile-time guarantee that
 5079        all ranges have the same length (in `allKnownSameLength`).
 5080     +/
 5081     static if (allKnownSameLength
 5082         ? anySatisfy!(hasLength, Ranges)
 5083         : (anySatisfy!(hasLength, Ranges)
 5084             && allSatisfy!(templateOr!(isInfinite, hasLength), Ranges)))
 5085     {
 5086         @property size_t length()
 5087         {
 5088             static if (allKnownSameLength)
 5089             {
 5090                 static foreach (i, Range; Ranges)
 5091                 {
 5092                     static if (hasLength!Range && !anySatisfy!(hasLength, Ranges[0 .. i]))
 5093                         return ranges[i].length;
 5094                 }
 5095             }
 5096             else
 5097             {
 5098                 static foreach (i, Range; Ranges)
 5099                     static if (hasLength!Range)
 5100                     {
 5101                         static if (!anySatisfy!(hasLength, Ranges[0 .. i]))
 5102                             size_t minLen = ranges[i].length;
 5103                         else
 5104                         {{
 5105                             const x = ranges[i].length;
 5106                             if (x < minLen) minLen = x;
 5107                         }}
 5108                     }
 5109                 return minLen;
 5110             }
 5111         }
 5112 
 5113         alias opDollar = length;
 5114     }
 5115 
 5116     /+
 5117        Returns a slice of the range. Defined if all constituent ranges
 5118        support slicing.
 5119     +/
 5120     static if (allSatisfy!(hasSlicing, Ranges))
 5121     {
 5122         // Note: we will know that all elements of the resultant range
 5123         // will have the same length but we cannot change `allKnownSameLength`
 5124         // because the `hasSlicing` predicate tests that the result returned
 5125         // by `opSlice` has the same type as the receiver.
 5126         auto opSlice()(size_t from, size_t to)
 5127         {
 5128             //(ranges[0][from .. to], ranges[1][from .. to], ...)
 5129             enum sliceArgs = `(%(ranges[%s][from .. to]%|, %))`.format(iota(0, Ranges.length));
 5130             static if (__traits(compiles, mixin(`typeof(this)`~sliceArgs)))
 5131                 return mixin(`typeof(this)`~sliceArgs);
 5132             else
 5133                 // The type is different anyway so we might as well
 5134                 // explicitly set allKnownSameLength.
 5135                 return mixin(`ZipShortest!(Yes.allKnownSameLength, staticMap!(Take, Ranges))`
 5136                     ~sliceArgs);
 5137         }
 5138     }
 5139 
 5140     /+
 5141        Returns the `n`th element in the composite range. Defined if all
 5142        constituent ranges offer random access.
 5143     +/
 5144     static if (allSatisfy!(isRandomAccessRange, Ranges))
 5145     ElementType opIndex()(size_t n)
 5146     {
 5147         return mixin(`typeof(return)(%(ranges[%s][n]%|, %))`.format(iota(0, Ranges.length)));
 5148     }
 5149 
 5150     /+
 5151        Sets the `n`th element in the composite range. Defined if all
 5152        constituent ranges offer random access and have assignable elements.
 5153     +/
 5154     static if (allSatisfy!(isRandomAccessRange, Ranges)
 5155         && allSatisfy!(hasAssignableElements, Ranges))
 5156     void opIndexAssign()(ElementType v, size_t n)
 5157     {
 5158         static foreach (i; 0 .. Ranges.length)
 5159             ranges[i][n] = v[i];
 5160     }
 5161 
 5162     /+
 5163        Destructively reads the `n`th element in the composite
 5164        range. Defined if all constituent ranges offer random
 5165        access and have mobile elements.
 5166     +/
 5167     static if (allSatisfy!(isRandomAccessRange, Ranges)
 5168         && allSatisfy!(hasMobileElements, Ranges))
 5169     ElementType moveAt()(size_t n)
 5170     {
 5171         return mixin(`typeof(return)(%(ranges[%s].moveAt(n)%|, %))`.format(iota(0, Ranges.length)));
 5172     }
 5173 }
 5174 
 5175 pure @system unittest
 5176 {
 5177     import std.algorithm.comparison : equal;
 5178     import std.algorithm.iteration : filter, map;
 5179     import std.algorithm.mutation : swap;
 5180     import std.algorithm.sorting : sort;
 5181 
 5182     import std.exception : assertThrown, assertNotThrown;
 5183     import std