root/trunk/phobos/std/range.d

Revision 2369, 143.9 kB (checked in by andrei, 3 years ago)

Fix for issue 5152

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