1 // Written in the D programming language.
2 /**
3 This is a submodule of $(MREF std, algorithm).
4 It contains generic iteration algorithms.
5 
6 $(SCRIPT inhibitQuickIndex = 1;)
7 $(BOOKTABLE Cheat Sheet,
8 $(TR $(TH Function Name) $(TH Description))
9 $(T2 cache,
10         Eagerly evaluates and caches another range's `front`.)
11 $(T2 cacheBidirectional,
12         As above, but also provides `back` and `popBack`.)
13 $(T2 chunkBy,
14         `chunkBy!((a,b) => a[1] == b[1])([[1, 1], [1, 2], [2, 2], [2, 1]])`
15         returns a range containing 3 subranges: the first with just
16         `[1, 1]`; the second with the elements `[1, 2]` and `[2, 2]`;
17         and the third with just `[2, 1]`.)
18 $(T2 cumulativeFold,
19         `cumulativeFold!((a, b) => a + b)([1, 2, 3, 4])` returns a
20         lazily-evaluated range containing the successive reduced values `1`,
21         `3`, `6`, `10`.)
22 $(T2 each,
23         `each!writeln([1, 2, 3])` eagerly prints the numbers `1`, `2`
24         and `3` on their own lines.)
25 $(T2 filter,
26         `filter!(a => a > 0)([1, -1, 2, 0, -3])` iterates over elements `1`
27         and `2`.)
28 $(T2 filterBidirectional,
29         Similar to `filter`, but also provides `back` and `popBack` at
30         a small increase in cost.)
31 $(T2 fold,
32         `fold!((a, b) => a + b)([1, 2, 3, 4])` returns `10`.)
33 $(T2 group,
34         `group([5, 2, 2, 3, 3])` returns a range containing the tuples
35         `tuple(5, 1)`, `tuple(2, 2)`, and `tuple(3, 2)`.)
36 $(T2 joiner,
37         `joiner(["hello", "world!"], "; ")` returns a range that iterates
38         over the characters `"hello; world!"`. No new string is created -
39         the existing inputs are iterated.)
40 $(T2 map,
41         `map!(a => a * 2)([1, 2, 3])` lazily returns a range with the numbers
42         `2`, `4`, `6`.)
43 $(T2 mean,
44         Colloquially known as the average, `mean([1, 2, 3])` returns `2`.)
45 $(T2 permutations,
46         Lazily computes all permutations using Heap's algorithm.)
47 $(T2 reduce,
48         `reduce!((a, b) => a + b)([1, 2, 3, 4])` returns `10`.
49         This is the old implementation of `fold`.)
50 $(T2 splitWhen,
51         Lazily splits a range by comparing adjacent elements.)
52 $(T2 splitter,
53         Lazily splits a range by a separator.)
54 $(T2 substitute,
55         `[1, 2].substitute(1, 0.1)` returns `[0.1, 2]`.)
56 $(T2 sum,
57         Same as `fold`, but specialized for accurate summation.)
58 $(T2 uniq,
59         Iterates over the unique elements in a range, which is assumed sorted.)
60 )
61 
62 Copyright: Andrei Alexandrescu 2008-.
63 
64 License: $(HTTP boost.org/LICENSE_1_0.txt, Boost License 1.0).
65 
66 Authors: $(HTTP erdani.com, Andrei Alexandrescu)
67 
68 Source: $(PHOBOSSRC std/algorithm/iteration.d)
69 
70 Macros:
71 T2=$(TR $(TDNW $(LREF $1)) $(TD $+))
72  */
73 module std.algorithm.iteration;
74 
75 import std.functional : unaryFun, binaryFun;
76 import std.range.primitives;
77 import std.traits;
78 import std.typecons : Flag, Yes, No;
79 
80 /++
81 `cache` eagerly evaluates $(REF_ALTTEXT front, front, std,range,primitives) of `range`
82 on each construction or call to $(REF_ALTTEXT popFront, popFront, std,range,primitives),
83 to store the result in a _cache.
84 The result is then directly returned when $(REF_ALTTEXT front, front, std,range,primitives) is called,
85 rather than re-evaluated.
86 
87 This can be a useful function to place in a chain, after functions
88 that have expensive evaluation, as a lazy alternative to $(REF array, std,array).
89 In particular, it can be placed after a call to $(LREF map), or before a call
90 $(REF filter, std,range) or $(REF tee, std,range)
91 
92 `cache` may provide
93 $(REF_ALTTEXT bidirectional range, isBidirectionalRange, std,range,primitives)
94 iteration if needed, but since this comes at an increased cost, it must be explicitly requested via the
95 call to `cacheBidirectional`. Furthermore, a bidirectional _cache will
96 evaluate the "center" element twice, when there is only one element left in
97 the range.
98 
99 `cache` does not provide random access primitives,
100 as `cache` would be unable to _cache the random accesses.
101 If `Range` provides slicing primitives,
102 then `cache` will provide the same slicing primitives,
103 but `hasSlicing!Cache` will not yield true (as the $(REF hasSlicing, std,range,primitives)
104 trait also checks for random access).
105 
106 Params:
107     range = an $(REF_ALTTEXT input range, isInputRange, std,range,primitives)
108 
109 Returns:
110     An $(REF_ALTTEXT input range, isInputRange, std,range,primitives) with the cached values of range
111 +/
112 auto cache(Range)(Range range)
113 if (isInputRange!Range)
114 {
115     return _Cache!(Range, false)(range);
116 }
117 
118 /// ditto
119 auto cacheBidirectional(Range)(Range range)
120 if (isBidirectionalRange!Range)
121 {
122     return _Cache!(Range, true)(range);
123 }
124 
125 ///
126 @safe unittest
127 {
128     import std.algorithm.comparison : equal;
129     import std.range, std.stdio;
130     import std.typecons : tuple;
131 
132     ulong counter = 0;
133     double fun(int x)
134     {
135         ++counter;
136         // http://en.wikipedia.org/wiki/Quartic_function
137         return ( (x + 4.0) * (x + 1.0) * (x - 1.0) * (x - 3.0) ) / 14.0 + 0.5;
138     }
139     // Without cache, with array (greedy)
140     auto result1 = iota(-4, 5).map!(a =>tuple(a, fun(a)))()
141                              .filter!(a => a[1] < 0)()
142                              .map!(a => a[0])()
143                              .array();
144 
145     // the values of x that have a negative y are:
146     assert(equal(result1, [-3, -2, 2]));
147 
148     // Check how many times fun was evaluated.
149     // As many times as the number of items in both source and result.
150     assert(counter == iota(-4, 5).length + result1.length);
151 
152     counter = 0;
153     // Without array, with cache (lazy)
154     auto result2 = iota(-4, 5).map!(a =>tuple(a, fun(a)))()
155                              .cache()
156                              .filter!(a => a[1] < 0)()
157                              .map!(a => a[0])();
158 
159     // the values of x that have a negative y are:
160     assert(equal(result2, [-3, -2, 2]));
161 
162     // Check how many times fun was evaluated.
163     // Only as many times as the number of items in source.
164     assert(counter == iota(-4, 5).length);
165 }
166 
167 // https://issues.dlang.org/show_bug.cgi?id=15891
168 @safe pure unittest
169 {
170     assert([1].map!(x=>[x].map!(y=>y)).cache.front.front == 1);
171 }
172 
173 /++
174 Tip: `cache` is eager when evaluating elements. If calling front on the
175 underlying range has a side effect, it will be observable before calling
176 front on the actual cached range.
177 
178 Furthermore, care should be taken composing `cache` with $(REF take, std,range).
179 By placing `take` before `cache`, then `cache` will be "aware"
180 of when the range ends, and correctly stop caching elements when needed.
181 If calling front has no side effect though, placing `take` after `cache`
182 may yield a faster range.
183 
184 Either way, the resulting ranges will be equivalent, but maybe not at the
185 same cost or side effects.
186 +/
187 @safe unittest
188 {
189     import std.algorithm.comparison : equal;
190     import std.range;
191     int i = 0;
192 
193     auto r = iota(0, 4).tee!((a){i = a;}, No.pipeOnPop);
194     auto r1 = r.take(3).cache();
195     auto r2 = r.cache().take(3);
196 
197     assert(equal(r1, [0, 1, 2]));
198     assert(i == 2); //The last "seen" element was 2. The data in cache has been cleared.
199 
200     assert(equal(r2, [0, 1, 2]));
201     assert(i == 3); //cache has accessed 3. It is still stored internally by cache.
202 }
203 
204 @safe unittest
205 {
206     import std.algorithm.comparison : equal;
207     import std.range;
208     auto a = [1, 2, 3, 4];
209     assert(equal(a.map!(a => (a - 1) * a)().cache(),                      [ 0, 2, 6, 12]));
210     assert(equal(a.map!(a => (a - 1) * a)().cacheBidirectional().retro(), [12, 6, 2,  0]));
211     auto r1 = [1, 2, 3, 4].cache()             [1 .. $];
212     auto r2 = [1, 2, 3, 4].cacheBidirectional()[1 .. $];
213     assert(equal(r1, [2, 3, 4]));
214     assert(equal(r2, [2, 3, 4]));
215 }
216 
217 @safe unittest
218 {
219     import std.algorithm.comparison : equal;
220 
221     //immutable test
222     static struct S
223     {
224         int i;
225         this(int i)
226         {
227             //this.i = i;
228         }
229     }
230     immutable(S)[] s = [S(1), S(2), S(3)];
231     assert(equal(s.cache(),              s));
232     assert(equal(s.cacheBidirectional(), s));
233 }
234 
235 @safe pure nothrow unittest
236 {
237     import std.algorithm.comparison : equal;
238 
239     //safety etc
240     auto a = [1, 2, 3, 4];
241     assert(equal(a.cache(),              a));
242     assert(equal(a.cacheBidirectional(), a));
243 }
244 
245 @safe unittest
246 {
247     char[][] stringbufs = ["hello".dup, "world".dup];
248     auto strings = stringbufs.map!((a)=>a.idup)().cache();
249     assert(strings.front is strings.front);
250 }
251 
252 @safe unittest
253 {
254     import std.range : cycle;
255     import std.algorithm.comparison : equal;
256 
257     auto c = [1, 2, 3].cycle().cache();
258     c = c[1 .. $];
259     auto d = c[0 .. 1];
260     assert(d.equal([2]));
261 }
262 
263 @safe unittest
264 {
265     static struct Range
266     {
267         bool initialized = false;
268         bool front() @property {return initialized = true;}
269         void popFront() {initialized = false;}
270         enum empty = false;
271     }
272     auto r = Range().cache();
273     assert(r.source.initialized == true);
274 }
275 
276 private struct _Cache(R, bool bidir)
277 {
278     import core.exception : RangeError;
279 
280     private
281     {
282         import std.algorithm.internal : algoFormat;
283         import std.meta : AliasSeq;
284 
285         alias E  = ElementType!R;
286         alias UE = Unqual!E;
287 
288         R source;
289 
290         static if (bidir) alias CacheTypes = AliasSeq!(UE, UE);
291         else              alias CacheTypes = AliasSeq!UE;
292         CacheTypes caches;
293 
294         static assert(isAssignable!(UE, E) && is(UE : E),
295             algoFormat(
296                 "Cannot instantiate range with %s because %s elements are not assignable to %s.",
297                 R.stringof,
298                 E.stringof,
299                 UE.stringof
300             )
301         );
302     }
303 
304     this(R range)
305     {
306         source = range;
307         if (!range.empty)
308         {
309             caches[0] = source.front;
310             static if (bidir)
311                 caches[1] = source.back;
312         }
313         else
314         {
315             // needed, because the compiler cannot deduce, that 'caches' is initialized
316             // see https://issues.dlang.org/show_bug.cgi?id=15891
317             caches[0] = UE.init;
318             static if (bidir)
319                 caches[1] = UE.init;
320         }
321     }
322 
323     static if (isInfinite!R)
324         enum empty = false;
325     else
326         bool empty() @property
327         {
328             return source.empty;
329         }
330 
331     mixin ImplementLength!source;
332 
333     E front() @property
334     {
335         version (assert) if (empty) throw new RangeError();
336         return caches[0];
337     }
338     static if (bidir) E back() @property
339     {
340         version (assert) if (empty) throw new RangeError();
341         return caches[1];
342     }
343 
344     void popFront()
345     {
346         version (assert) if (empty) throw new RangeError();
347         source.popFront();
348         if (!source.empty)
349             caches[0] = source.front;
350         else
351         {
352             // see https://issues.dlang.org/show_bug.cgi?id=15891
353             caches[0] = UE.init;
354             static if (bidir)
355                 caches[1] = UE.init;
356         }
357     }
358     static if (bidir) void popBack()
359     {
360         version (assert) if (empty) throw new RangeError();
361         source.popBack();
362         if (!source.empty)
363             caches[1] = source.back;
364         else
365         {
366             // see https://issues.dlang.org/show_bug.cgi?id=15891
367             caches[0] = UE.init;
368             caches[1] = UE.init;
369         }
370     }
371 
372     static if (isForwardRange!R)
373     {
374         private this(R source, ref CacheTypes caches)
375         {
376             this.source = source;
377             this.caches = caches;
378         }
379         typeof(this) save() @property
380         {
381             return typeof(this)(source.save, caches);
382         }
383     }
384 
385     static if (hasSlicing!R)
386     {
387         enum hasEndSlicing = is(typeof(source[size_t.max .. $]));
388 
389         static if (hasEndSlicing)
390         {
391             private static struct DollarToken{}
392             enum opDollar = DollarToken.init;
393 
394             auto opSlice(size_t low, DollarToken)
395             {
396                 return typeof(this)(source[low .. $]);
397             }
398         }
399 
400         static if (!isInfinite!R)
401         {
402             typeof(this) opSlice(size_t low, size_t high)
403             {
404                 return typeof(this)(source[low .. high]);
405             }
406         }
407         else static if (hasEndSlicing)
408         {
409             auto opSlice(size_t low, size_t high)
410             in
411             {
412                 assert(low <= high, "Bounds error when slicing cache.");
413             }
414             do
415             {
416                 import std.range : takeExactly;
417                 return this[low .. $].takeExactly(high - low);
418             }
419         }
420     }
421 }
422 
423 /**
424 Implements the homonym function (also known as `transform`) present
425 in many languages of functional flavor. The call `map!(fun)(range)`
426 returns a range of which elements are obtained by applying `fun(a)`
427 left to right for all elements `a` in `range`. The original ranges are
428 not changed. Evaluation is done lazily.
429 
430 Params:
431     fun = one or more transformation functions
432 
433 See_Also:
434     $(HTTP en.wikipedia.org/wiki/Map_(higher-order_function), Map (higher-order function))
435 */
436 template map(fun...)
437 if (fun.length >= 1)
438 {
439     /**
440     Params:
441         r = an $(REF_ALTTEXT input range, isInputRange, std,range,primitives)
442     Returns:
443         A range with each fun applied to all the elements. If there is more than one
444         fun, the element type will be `Tuple` containing one element for each fun.
445      */
446     auto map(Range)(Range r)
447     if (isInputRange!(Unqual!Range))
448     {
449         import std.meta : staticMap;
450         import std.functional : adjoin;
451 
452         alias RE = ElementType!(Range);
453 
454         alias _funs = staticMap!(unaryFun, fun);
455         alias _fun = adjoin!_funs;
456 
457         // Once https://issues.dlang.org/show_bug.cgi?id=5710 is fixed
458         // accross all compilers (as of 2020-04, it wasn't fixed in LDC and GDC),
459         // this validation loop can be moved into a template.
460         foreach (f; _funs)
461         {
462             static assert(!is(typeof(f(RE.init)) == void),
463                     "Mapping function(s) must not return void: " ~ _funs.stringof);
464         }
465 
466         return MapResult!(_fun, Range)(r);
467     }
468 }
469 
470 ///
471 @safe @nogc unittest
472 {
473     import std.algorithm.comparison : equal;
474     import std.range : chain, only;
475     auto squares =
476         chain(only(1, 2, 3, 4), only(5, 6)).map!(a => a * a);
477     assert(equal(squares, only(1, 4, 9, 16, 25, 36)));
478 }
479 
480 /**
481 Multiple functions can be passed to `map`. In that case, the
482 element type of `map` is a tuple containing one element for each
483 function.
484 */
485 @safe unittest
486 {
487     auto sums = [2, 4, 6, 8];
488     auto products = [1, 4, 9, 16];
489 
490     size_t i = 0;
491     foreach (result; [ 1, 2, 3, 4 ].map!("a + a", "a * a"))
492     {
493         assert(result[0] == sums[i]);
494         assert(result[1] == products[i]);
495         ++i;
496     }
497 }
498 
499 /**
500 You may alias `map` with some function(s) to a symbol and use
501 it separately:
502 */
503 @safe unittest
504 {
505     import std.algorithm.comparison : equal;
506     import std.conv : to;
507 
508     alias stringize = map!(to!string);
509     assert(equal(stringize([ 1, 2, 3, 4 ]), [ "1", "2", "3", "4" ]));
510 }
511 
512 // Verify workaround for https://issues.dlang.org/show_bug.cgi?id=15777
513 @safe unittest
514 {
515     import std.algorithm.mutation, std.string;
516     auto foo(string[] args)
517     {
518         return args.map!strip;
519     }
520 }
521 
522 private struct MapResult(alias fun, Range)
523 {
524     alias R = Unqual!Range;
525     R _input;
526 
527     static if (isBidirectionalRange!R)
528     {
529         @property auto ref back()()
530         {
531             assert(!empty, "Attempting to fetch the back of an empty map.");
532             return fun(_input.back);
533         }
534 
535         void popBack()()
536         {
537             assert(!empty, "Attempting to popBack an empty map.");
538             _input.popBack();
539         }
540     }
541 
542     this(R input)
543     {
544         _input = input;
545     }
546 
547     static if (isInfinite!R)
548     {
549         // Propagate infinite-ness.
550         enum bool empty = false;
551     }
552     else
553     {
554         @property bool empty()
555         {
556             return _input.empty;
557         }
558     }
559 
560     void popFront()
561     {
562         assert(!empty, "Attempting to popFront an empty map.");
563         _input.popFront();
564     }
565 
566     @property auto ref front()
567     {
568         assert(!empty, "Attempting to fetch the front of an empty map.");
569         return fun(_input.front);
570     }
571 
572     static if (isRandomAccessRange!R)
573     {
574         static if (is(typeof(Range.init[ulong.max])))
575             private alias opIndex_t = ulong;
576         else
577             private alias opIndex_t = uint;
578 
579         auto ref opIndex(opIndex_t index)
580         {
581             return fun(_input[index]);
582         }
583     }
584 
585     mixin ImplementLength!_input;
586 
587     static if (hasSlicing!R)
588     {
589         static if (is(typeof(_input[ulong.max .. ulong.max])))
590             private alias opSlice_t = ulong;
591         else
592             private alias opSlice_t = uint;
593 
594         static if (hasLength!R)
595         {
596             auto opSlice(opSlice_t low, opSlice_t high)
597             {
598                 return typeof(this)(_input[low .. high]);
599             }
600         }
601         else static if (is(typeof(_input[opSlice_t.max .. $])))
602         {
603             struct DollarToken{}
604             enum opDollar = DollarToken.init;
605             auto opSlice(opSlice_t low, DollarToken)
606             {
607                 return typeof(this)(_input[low .. $]);
608             }
609 
610             auto opSlice(opSlice_t low, opSlice_t high)
611             {
612                 import std.range : takeExactly;
613                 return this[low .. $].takeExactly(high - low);
614             }
615         }
616     }
617 
618     static if (isForwardRange!R)
619     {
620         @property auto save()
621         {
622             return typeof(this)(_input.save);
623         }
624     }
625 }
626 
627 @safe unittest
628 {
629     import std.algorithm.comparison : equal;
630     import std.conv : to;
631     import std.functional : adjoin;
632 
633     alias stringize = map!(to!string);
634     assert(equal(stringize([ 1, 2, 3, 4 ]), [ "1", "2", "3", "4" ]));
635 
636     uint counter;
637     alias count = map!((a) { return counter++; });
638     assert(equal(count([ 10, 2, 30, 4 ]), [ 0, 1, 2, 3 ]));
639 
640     counter = 0;
641     adjoin!((a) { return counter++; }, (a) { return counter++; })(1);
642     alias countAndSquare = map!((a) { return counter++; }, (a) { return counter++; });
643     //assert(equal(countAndSquare([ 10, 2 ]), [ tuple(0u, 100), tuple(1u, 4) ]));
644 }
645 
646 @safe unittest
647 {
648     import std.algorithm.comparison : equal;
649     import std.ascii : toUpper;
650     import std.internal.test.dummyrange;
651     import std.range;
652     import std.typecons : tuple;
653     import std.random : uniform, Random = Xorshift;
654 
655     int[] arr1 = [ 1, 2, 3, 4 ];
656     const int[] arr1Const = arr1;
657     int[] arr2 = [ 5, 6 ];
658     auto squares = map!("a * a")(arr1Const);
659     assert(squares[$ - 1] == 16);
660     assert(equal(squares, [ 1, 4, 9, 16 ][]));
661     assert(equal(map!("a * a")(chain(arr1, arr2)), [ 1, 4, 9, 16, 25, 36 ][]));
662 
663     // Test the caching stuff.
664     assert(squares.back == 16);
665     auto squares2 = squares.save;
666     assert(squares2.back == 16);
667 
668     assert(squares2.front == 1);
669     squares2.popFront();
670     assert(squares2.front == 4);
671     squares2.popBack();
672     assert(squares2.front == 4);
673     assert(squares2.back == 9);
674 
675     assert(equal(map!("a * a")(chain(arr1, arr2)), [ 1, 4, 9, 16, 25, 36 ][]));
676 
677     uint i;
678     foreach (e; map!("a", "a * a")(arr1))
679     {
680         assert(e[0] == ++i);
681         assert(e[1] == i * i);
682     }
683 
684     // Test length.
685     assert(squares.length == 4);
686     assert(map!"a * a"(chain(arr1, arr2)).length == 6);
687 
688     // Test indexing.
689     assert(squares[0] == 1);
690     assert(squares[1] == 4);
691     assert(squares[2] == 9);
692     assert(squares[3] == 16);
693 
694     // Test slicing.
695     auto squareSlice = squares[1 .. squares.length - 1];
696     assert(equal(squareSlice, [4, 9][]));
697     assert(squareSlice.back == 9);
698     assert(squareSlice[1] == 9);
699 
700     // Test on a forward range to make sure it compiles when all the fancy
701     // stuff is disabled.
702     auto fibsSquares = map!"a * a"(recurrence!("a[n-1] + a[n-2]")(1, 1));
703     assert(fibsSquares.front == 1);
704     fibsSquares.popFront();
705     fibsSquares.popFront();
706     assert(fibsSquares.front == 4);
707     fibsSquares.popFront();
708     assert(fibsSquares.front == 9);
709 
710     auto repeatMap = map!"a"(repeat(1));
711     auto gen = Random(123_456_789);
712     auto index = uniform(0, 1024, gen);
713     static assert(isInfinite!(typeof(repeatMap)));
714     assert(repeatMap[index] == 1);
715 
716     auto intRange = map!"a"([1,2,3]);
717     static assert(isRandomAccessRange!(typeof(intRange)));
718     assert(equal(intRange, [1, 2, 3]));
719 
720     foreach (DummyType; AllDummyRanges)
721     {
722         DummyType d;
723         auto m = map!"a * a"(d);
724 
725         static assert(propagatesRangeType!(typeof(m), DummyType));
726         assert(equal(m, [1,4,9,16,25,36,49,64,81,100]));
727     }
728 
729     //Test string access
730     string  s1 = "hello world!";
731     dstring s2 = "日本語";
732     dstring s3 = "hello world!"d;
733     auto ms1 = map!(toUpper)(s1);
734     auto ms2 = map!(toUpper)(s2);
735     auto ms3 = map!(toUpper)(s3);
736     static assert(!is(ms1[0])); //narrow strings can't be indexed
737     assert(ms2[0] == '日');
738     assert(ms3[0] == 'H');
739     static assert(!is(ms1[0 .. 1])); //narrow strings can't be sliced
740     assert(equal(ms2[0 .. 2], "日本"w));
741     assert(equal(ms3[0 .. 2], "HE"));
742 
743     // https://issues.dlang.org/show_bug.cgi?id=5753
744     static void voidFun(int) {}
745     static int nonvoidFun(int) { return 0; }
746     static assert(!__traits(compiles, map!voidFun([1])));
747     static assert(!__traits(compiles, map!(voidFun, voidFun)([1])));
748     static assert(!__traits(compiles, map!(nonvoidFun, voidFun)([1])));
749     static assert(!__traits(compiles, map!(voidFun, nonvoidFun)([1])));
750     static assert(!__traits(compiles, map!(a => voidFun(a))([1])));
751 
752     // https://issues.dlang.org/show_bug.cgi?id=15480
753     auto dd = map!(z => z * z, c => c * c * c)([ 1, 2, 3, 4 ]);
754     assert(dd[0] == tuple(1, 1));
755     assert(dd[1] == tuple(4, 8));
756     assert(dd[2] == tuple(9, 27));
757     assert(dd[3] == tuple(16, 64));
758     assert(dd.length == 4);
759 }
760 
761 // Verify fix for: https://issues.dlang.org/show_bug.cgi?id=16034
762 @safe unittest
763 {
764     struct One
765     {
766         int entry = 1;
767         @disable this(this);
768     }
769 
770     One[] ones = [One(), One()];
771 
772     import std.algorithm.comparison : equal;
773 
774     assert(ones.map!`a.entry + 1`.equal([2, 2]));
775 }
776 
777 
778 @safe unittest
779 {
780     import std.algorithm.comparison : equal;
781     import std.range;
782     auto LL = iota(1L, 4L);
783     auto m = map!"a*a"(LL);
784     assert(equal(m, [1L, 4L, 9L]));
785 }
786 
787 @safe unittest
788 {
789     import std.range : iota;
790 
791     // https://issues.dlang.org/show_bug.cgi?id=10130 - map of iota with const step.
792     const step = 2;
793     assert(map!(i => i)(iota(0, 10, step)).walkLength == 5);
794 
795     // Need these to all by const to repro the float case, due to the
796     // CommonType template used in the float specialization of iota.
797     const floatBegin = 0.0;
798     const floatEnd = 1.0;
799     const floatStep = 0.02;
800     assert(map!(i => i)(iota(floatBegin, floatEnd, floatStep)).walkLength == 50);
801 }
802 
803 @safe unittest
804 {
805     import std.algorithm.comparison : equal;
806     import std.range;
807     //slicing infinites
808     auto rr = iota(0, 5).cycle().map!"a * a"();
809     alias RR = typeof(rr);
810     static assert(hasSlicing!RR);
811     rr = rr[6 .. $]; //Advances 1 cycle and 1 unit
812     assert(equal(rr[0 .. 5], [1, 4, 9, 16, 0]));
813 }
814 
815 @safe unittest
816 {
817     import std.range;
818     struct S {int* p;}
819     auto m = immutable(S).init.repeat().map!"a".save;
820     assert(m.front == immutable(S)(null));
821 }
822 
823 // Issue 20928
824 @safe unittest
825 {
826     struct Always3
827     {
828         enum empty = false;
829         auto save() { return this; }
830         long front() { return 3; }
831         void popFront() {}
832         long opIndex(ulong i) { return 3; }
833         long opIndex(ulong i) immutable { return 3; }
834     }
835 
836     import std.algorithm.iteration : map;
837     Always3.init.map!(e => e)[ulong.max];
838 }
839 
840 // each
841 /**
842 Eagerly iterates over `r` and calls `fun` with _each element.
843 
844 If no function to call is specified, `each` defaults to doing nothing but
845 consuming the entire range. `r.front` will be evaluated, but that can be avoided
846 by specifying a lambda with a `lazy` parameter.
847 
848 `each` also supports `opApply`-based types, so it works with e.g. $(REF
849 parallel, std,parallelism).
850 
851 Normally the entire range is iterated. If partial iteration (early stopping) is
852 desired, `fun` needs to return a value of type $(REF Flag,
853 std,typecons)`!"each"` (`Yes.each` to continue iteration, or `No.each` to stop
854 iteration).
855 
856 Params:
857     fun = function to apply to _each element of the range
858     r = range or iterable over which `each` iterates
859 
860 Returns: `Yes.each` if the entire range was iterated, `No.each` in case of early
861 stopping.
862 
863 See_Also: $(REF tee, std,range)
864  */
865 template each(alias fun = "a")
866 {
867     import std.meta : AliasSeq;
868     import std.traits : Parameters;
869     import std.typecons : Flag, Yes, No;
870 
871 private:
872     alias BinaryArgs = AliasSeq!(fun, "i", "a");
873 
874     enum isRangeUnaryIterable(R) =
875         is(typeof(unaryFun!fun(R.init.front)));
876 
877     enum isRangeBinaryIterable(R) =
878         is(typeof(binaryFun!BinaryArgs(0, R.init.front)));
879 
880     enum isRangeIterable(R) =
881         isInputRange!R &&
882         (isRangeUnaryIterable!R || isRangeBinaryIterable!R);
883 
884     enum isForeachUnaryIterable(R) =
885         is(typeof((R r) {
886             foreach (ref a; r)
887                 cast(void) unaryFun!fun(a);
888         }));
889 
890     enum isForeachUnaryWithIndexIterable(R) =
891         is(typeof((R r) {
892             foreach (i, ref a; r)
893                 cast(void) binaryFun!BinaryArgs(i, a);
894         }));
895 
896     enum isForeachBinaryIterable(R) =
897         is(typeof((R r) {
898             foreach (ref a, ref b; r)
899                 cast(void) binaryFun!fun(a, b);
900         }));
901 
902     enum isForeachIterable(R) =
903         (!isForwardRange!R || isDynamicArray!R) &&
904         (isForeachUnaryIterable!R || isForeachBinaryIterable!R ||
905          isForeachUnaryWithIndexIterable!R);
906 
907 public:
908     /**
909     Params:
910         r = range or iterable over which each iterates
911      */
912     Flag!"each" each(Range)(Range r)
913     if (!isForeachIterable!Range && (
914         isRangeIterable!Range ||
915         __traits(compiles, typeof(r.front).length)))
916     {
917         static if (isRangeIterable!Range)
918         {
919             debug(each) pragma(msg, "Using while for ", Range.stringof);
920             static if (isRangeUnaryIterable!Range)
921             {
922                 while (!r.empty)
923                 {
924                     static if (!is(typeof(unaryFun!fun(r.front)) == Flag!"each"))
925                     {
926                         cast(void) unaryFun!fun(r.front);
927                     }
928                     else
929                     {
930                         if (unaryFun!fun(r.front) == No.each) return No.each;
931                     }
932 
933                     r.popFront();
934                 }
935             }
936             else // if (isRangeBinaryIterable!Range)
937             {
938                 size_t i = 0;
939                 while (!r.empty)
940                 {
941                     static if (!is(typeof(binaryFun!BinaryArgs(i, r.front)) == Flag!"each"))
942                     {
943                         cast(void) binaryFun!BinaryArgs(i, r.front);
944                     }
945                     else
946                     {
947                         if (binaryFun!BinaryArgs(i, r.front) == No.each) return No.each;
948                     }
949                     r.popFront();
950                     i++;
951                 }
952             }
953         }
954         else
955         {
956             // range interface with >2 parameters.
957             for (auto range = r; !range.empty; range.popFront())
958             {
959                 static if (!is(typeof(fun(r.front.expand)) == Flag!"each"))
960                 {
961                     cast(void) fun(range.front.expand);
962                 }
963                 else
964                 {
965                     if (fun(range.front.expand)) return No.each;
966                 }
967             }
968         }
969         return Yes.each;
970     }
971 
972     /// ditto
973     Flag!"each" each(Iterable)(auto ref Iterable r)
974     if (isForeachIterable!Iterable ||
975         __traits(compiles, Parameters!(Parameters!(r.opApply))))
976     {
977         static if (isForeachIterable!Iterable)
978         {
979             static if (isForeachUnaryIterable!Iterable)
980             {
981                 debug(each) pragma(msg, "Using foreach UNARY for ", Iterable.stringof);
982                 {
983                     foreach (ref e; r)
984                     {
985                         static if (!is(typeof(unaryFun!fun(e)) == Flag!"each"))
986                         {
987                             cast(void) unaryFun!fun(e);
988                         }
989                         else
990                         {
991                             if (unaryFun!fun(e) == No.each) return No.each;
992                         }
993                     }
994                 }
995             }
996             else static if (isForeachBinaryIterable!Iterable)
997             {
998                 debug(each) pragma(msg, "Using foreach BINARY for ", Iterable.stringof);
999                 foreach (ref a, ref b; r)
1000                 {
1001                     static if (!is(typeof(binaryFun!fun(a, b)) == Flag!"each"))
1002                     {
1003                         cast(void) binaryFun!fun(a, b);
1004                     }
1005                     else
1006                     {
1007                         if (binaryFun!fun(a, b) == No.each) return No.each;
1008                     }
1009                 }
1010             }
1011             else static if (isForeachUnaryWithIndexIterable!Iterable)
1012             {
1013                 debug(each) pragma(msg, "Using foreach INDEX for ", Iterable.stringof);
1014                 foreach (i, ref e; r)
1015                 {
1016                     static if (!is(typeof(binaryFun!BinaryArgs(i, e)) == Flag!"each"))
1017                     {
1018                         cast(void) binaryFun!BinaryArgs(i, e);
1019                     }
1020                     else
1021                     {
1022                         if (binaryFun!BinaryArgs(i, e) == No.each) return No.each;
1023                     }
1024                 }
1025             }
1026             else
1027             {
1028                 static assert(0, "Invalid foreach iteratable type " ~ Iterable.stringof ~ " met.");
1029             }
1030             return Yes.each;
1031         }
1032         else
1033         {
1034             // opApply with >2 parameters. count the delegate args.
1035             // only works if it is not templated (otherwise we cannot count the args)
1036             auto result = Yes.each;
1037             auto dg(Parameters!(Parameters!(r.opApply)) params)
1038             {
1039                 static if (!is(typeof(binaryFun!BinaryArgs(i, e)) == Flag!"each"))
1040                 {
1041                     fun(params);
1042                     return 0; // tells opApply to continue iteration
1043                 }
1044                 else
1045                 {
1046                     result = fun(params);
1047                     return result == Yes.each ? 0 : -1;
1048                 }
1049             }
1050             r.opApply(&dg);
1051             return result;
1052         }
1053     }
1054 }
1055 
1056 ///
1057 @safe unittest
1058 {
1059     import std.range : iota;
1060     import std.typecons : No;
1061 
1062     int[] arr;
1063     iota(5).each!(n => arr ~= n);
1064     assert(arr == [0, 1, 2, 3, 4]);
1065 
1066     // stop iterating early
1067     iota(5).each!((n) { arr ~= n; return No.each; });
1068     assert(arr == [0, 1, 2, 3, 4, 0]);
1069 
1070     // If the range supports it, the value can be mutated in place
1071     arr.each!((ref n) => n++);
1072     assert(arr == [1, 2, 3, 4, 5, 1]);
1073 
1074     arr.each!"a++";
1075     assert(arr == [2, 3, 4, 5, 6, 2]);
1076 
1077     auto m = arr.map!(n => n);
1078     // by-ref lambdas are not allowed for non-ref ranges
1079     static assert(!__traits(compiles, m.each!((ref n) => n++)));
1080 
1081     // The default predicate consumes the range
1082     (&m).each();
1083     assert(m.empty);
1084 }
1085 
1086 /// `each` can pass an index variable for iterable objects which support this
1087 @safe unittest
1088 {
1089     auto arr = new size_t[4];
1090 
1091     arr.each!"a=i"();
1092     assert(arr == [0, 1, 2, 3]);
1093 
1094     arr.each!((i, ref e) => e = i * 2);
1095     assert(arr == [0, 2, 4, 6]);
1096 }
1097 
1098 /// opApply iterators work as well
1099 @system unittest
1100 {
1101     static class S
1102     {
1103         int x;
1104         int opApply(scope int delegate(ref int _x) dg) { return dg(x); }
1105     }
1106 
1107     auto s = new S;
1108     s.each!"a++";
1109     assert(s.x == 1);
1110 }
1111 
1112 // binary foreach with two ref args
1113 @system unittest
1114 {
1115     import std.range : lockstep;
1116 
1117     auto a = [ 1, 2, 3 ];
1118     auto b = [ 2, 3, 4 ];
1119 
1120     a.lockstep(b).each!((ref x, ref y) { ++x; ++y; });
1121 
1122     assert(a == [ 2, 3, 4 ]);
1123     assert(b == [ 3, 4, 5 ]);
1124 }
1125 
1126 // https://issues.dlang.org/show_bug.cgi?id=15358
1127 // application of `each` with >2 args (opApply)
1128 @system unittest
1129 {
1130     import std.range : lockstep;
1131     auto a = [0,1,2];
1132     auto b = [3,4,5];
1133     auto c = [6,7,8];
1134 
1135     lockstep(a, b, c).each!((ref x, ref y, ref z) { ++x; ++y; ++z; });
1136 
1137     assert(a == [1,2,3]);
1138     assert(b == [4,5,6]);
1139     assert(c == [7,8,9]);
1140 }
1141 
1142 // https://issues.dlang.org/show_bug.cgi?id=15358
1143 // application of `each` with >2 args (range interface)
1144 @safe unittest
1145 {
1146     import std.range : zip;
1147     auto a = [0,1,2];
1148     auto b = [3,4,5];
1149     auto c = [6,7,8];
1150 
1151     int[] res;
1152 
1153     zip(a, b, c).each!((x, y, z) { res ~= x + y + z; });
1154 
1155     assert(res == [9, 12, 15]);
1156 }
1157 
1158 // https://issues.dlang.org/show_bug.cgi?id=16255
1159 // `each` on opApply doesn't support ref
1160 @safe unittest
1161 {
1162     int[] dynamicArray = [1, 2, 3, 4, 5];
1163     int[5] staticArray = [1, 2, 3, 4, 5];
1164 
1165     dynamicArray.each!((ref x) => x++);
1166     assert(dynamicArray == [2, 3, 4, 5, 6]);
1167 
1168     staticArray.each!((ref x) => x++);
1169     assert(staticArray == [2, 3, 4, 5, 6]);
1170 
1171     staticArray[].each!((ref x) => x++);
1172     assert(staticArray == [3, 4, 5, 6, 7]);
1173 }
1174 
1175 // https://issues.dlang.org/show_bug.cgi?id=16255
1176 // `each` on opApply doesn't support ref
1177 @system unittest
1178 {
1179     struct S
1180     {
1181        int x;
1182        int opApply(int delegate(ref int _x) dg) { return dg(x); }
1183     }
1184 
1185     S s;
1186     foreach (ref a; s) ++a;
1187     assert(s.x == 1);
1188     s.each!"++a";
1189     assert(s.x == 2);
1190 }
1191 
1192 // https://issues.dlang.org/show_bug.cgi?id=15357
1193 // `each` should behave similar to foreach
1194 @safe unittest
1195 {
1196     import std.range : iota;
1197 
1198     auto arr = [1, 2, 3, 4];
1199 
1200     // 1 ref parameter
1201     arr.each!((ref e) => e = 0);
1202     assert(arr.sum == 0);
1203 
1204     // 1 ref parameter and index
1205     arr.each!((i, ref e) => e = cast(int) i);
1206     assert(arr.sum == 4.iota.sum);
1207 }
1208 
1209 // https://issues.dlang.org/show_bug.cgi?id=15357
1210 // `each` should behave similar to foreach
1211 @system unittest
1212 {
1213     import std.range : iota, lockstep;
1214 
1215     // 2 ref parameters and index
1216     auto arrA = [1, 2, 3, 4];
1217     auto arrB = [5, 6, 7, 8];
1218     lockstep(arrA, arrB).each!((ref a, ref b) {
1219         a = 0;
1220         b = 1;
1221     });
1222     assert(arrA.sum == 0);
1223     assert(arrB.sum == 4);
1224 
1225     // 3 ref parameters
1226     auto arrC = [3, 3, 3, 3];
1227     lockstep(arrA, arrB, arrC).each!((ref a, ref b, ref c) {
1228         a = 1;
1229         b = 2;
1230         c = 3;
1231     });
1232     assert(arrA.sum == 4);
1233     assert(arrB.sum == 8);
1234     assert(arrC.sum == 12);
1235 }
1236 
1237 // https://issues.dlang.org/show_bug.cgi?id=15357
1238 // `each` should behave similar to foreach
1239 @system unittest
1240 {
1241     import std.range : lockstep;
1242     import std.typecons : Tuple;
1243 
1244     auto a = "abc";
1245     auto b = "def";
1246 
1247     // print each character with an index
1248     {
1249         alias Element = Tuple!(size_t, "index", dchar, "value");
1250         Element[] rForeach, rEach;
1251         foreach (i, c ; a) rForeach ~= Element(i, c);
1252         a.each!((i, c) => rEach ~= Element(i, c));
1253         assert(rForeach == rEach);
1254         assert(rForeach == [Element(0, 'a'), Element(1, 'b'), Element(2, 'c')]);
1255     }
1256 
1257     // print pairs of characters
1258     {
1259         alias Element = Tuple!(dchar, "a", dchar, "b");
1260         Element[] rForeach, rEach;
1261         foreach (c1, c2 ; a.lockstep(b)) rForeach ~= Element(c1, c2);
1262         a.lockstep(b).each!((c1, c2) => rEach ~= Element(c1, c2));
1263         assert(rForeach == rEach);
1264         assert(rForeach == [Element('a', 'd'), Element('b', 'e'), Element('c', 'f')]);
1265     }
1266 }
1267 
1268 // filter
1269 /**
1270 `filter!(predicate)(range)` returns a new range containing only elements `x` in `range` for
1271 which `predicate(x)` returns `true`.
1272 
1273 The predicate is passed to $(REF unaryFun, std,functional), and can be either a string, or
1274 any callable that can be executed via `pred(element)`.
1275 
1276 Params:
1277     predicate = Function to apply to each element of range
1278 
1279 Returns:
1280     An input range that contains the filtered elements. If `range` is at least a forward range, the return value of `filter`
1281     will also be a forward range.
1282 
1283 See_Also:
1284     $(HTTP en.wikipedia.org/wiki/Filter_(higher-order_function), Filter (higher-order function)),
1285     $(REF filterBidirectional, std,algorithm,iteration)
1286  */
1287 template filter(alias predicate)
1288 if (is(typeof(unaryFun!predicate)))
1289 {
1290     /**
1291     Params:
1292         range = An $(REF_ALTTEXT input range, isInputRange, std,range,primitives)
1293         of elements
1294     Returns:
1295         A range containing only elements `x` in `range` for
1296         which `predicate(x)` returns `true`.
1297      */
1298     auto filter(Range)(Range range)
1299     if (isInputRange!(Unqual!Range))
1300     {
1301         return FilterResult!(unaryFun!predicate, Range)(range);
1302     }
1303 }
1304 
1305 ///
1306 @safe unittest
1307 {
1308     import std.algorithm.comparison : equal;
1309     import std.math.operations : isClose;
1310     import std.range;
1311 
1312     int[] arr = [ 1, 2, 3, 4, 5 ];
1313 
1314     // Filter below 3
1315     auto small = filter!(a => a < 3)(arr);
1316     assert(equal(small, [ 1, 2 ]));
1317 
1318     // Filter again, but with Uniform Function Call Syntax (UFCS)
1319     auto sum = arr.filter!(a => a < 3);
1320     assert(equal(sum, [ 1, 2 ]));
1321 
1322     // In combination with chain() to span multiple ranges
1323     int[] a = [ 3, -2, 400 ];
1324     int[] b = [ 100, -101, 102 ];
1325     auto r = chain(a, b).filter!(a => a > 0);
1326     assert(equal(r, [ 3, 400, 100, 102 ]));
1327 
1328     // Mixing convertible types is fair game, too
1329     double[] c = [ 2.5, 3.0 ];
1330     auto r1 = chain(c, a, b).filter!(a => cast(int) a != a);
1331     assert(isClose(r1, [ 2.5 ]));
1332 }
1333 
1334 private struct FilterResult(alias pred, Range)
1335 {
1336     alias R = Unqual!Range;
1337     R _input;
1338     private bool _primed;
1339 
1340     private void prime()
1341     {
1342         if (_primed) return;
1343         while (!_input.empty && !pred(_input.front))
1344         {
1345             _input.popFront();
1346         }
1347         _primed = true;
1348     }
1349 
1350     this(R r)
1351     {
1352         _input = r;
1353     }
1354 
1355     private this(R r, bool primed)
1356     {
1357         _input = r;
1358         _primed = primed;
1359     }
1360 
1361     auto opSlice() { return this; }
1362 
1363     static if (isInfinite!Range)
1364     {
1365         enum bool empty = false;
1366     }
1367     else
1368     {
1369         @property bool empty() { prime; return _input.empty; }
1370     }
1371 
1372     void popFront()
1373     {
1374         prime;
1375         do
1376         {
1377             _input.popFront();
1378         } while (!_input.empty && !pred(_input.front));
1379     }
1380 
1381     @property auto ref front()
1382     {
1383         prime;
1384         assert(!empty, "Attempting to fetch the front of an empty filter.");
1385         return _input.front;
1386     }
1387 
1388     static if (isForwardRange!R)
1389     {
1390         @property auto save()
1391         {
1392             return typeof(this)(_input.save, _primed);
1393         }
1394     }
1395 }
1396 
1397 @safe unittest
1398 {
1399     import std.algorithm.comparison : equal;
1400     import std.internal.test.dummyrange;
1401     import std.range;
1402 
1403     auto shouldNotLoop4ever = repeat(1).filter!(x => x % 2 == 0);
1404     static assert(isInfinite!(typeof(shouldNotLoop4ever)));
1405     assert(!shouldNotLoop4ever.empty);
1406 
1407     int[] a = [ 3, 4, 2 ];
1408     auto r = filter!("a > 3")(a);
1409     static assert(isForwardRange!(typeof(r)));
1410     assert(equal(r, [ 4 ][]));
1411 
1412     a = [ 1, 22, 3, 42, 5 ];
1413     auto under10 = filter!("a < 10")(a);
1414     assert(equal(under10, [1, 3, 5][]));
1415     static assert(isForwardRange!(typeof(under10)));
1416     under10.front = 4;
1417     assert(equal(under10, [4, 3, 5][]));
1418     under10.front = 40;
1419     assert(equal(under10, [40, 3, 5][]));
1420     under10.front = 1;
1421 
1422     auto infinite = filter!"a > 2"(repeat(3));
1423     static assert(isInfinite!(typeof(infinite)));
1424     static assert(isForwardRange!(typeof(infinite)));
1425     assert(infinite.front == 3);
1426 
1427     foreach (DummyType; AllDummyRanges)
1428     {
1429         DummyType d;
1430         auto f = filter!"a & 1"(d);
1431         assert(equal(f, [1,3,5,7,9]));
1432 
1433         static if (isForwardRange!DummyType)
1434         {
1435             static assert(isForwardRange!(typeof(f)));
1436         }
1437     }
1438 
1439     // With delegates
1440     int x = 10;
1441     int overX(int a) { return a > x; }
1442     typeof(filter!overX(a)) getFilter()
1443     {
1444         return filter!overX(a);
1445     }
1446     auto r1 = getFilter();
1447     assert(equal(r1, [22, 42]));
1448 
1449     // With chain
1450     auto nums = [0,1,2,3,4];
1451     assert(equal(filter!overX(chain(a, nums)), [22, 42]));
1452 
1453     // With copying of inner struct Filter to Map
1454     auto arr = [1,2,3,4,5];
1455     auto m = map!"a + 1"(filter!"a < 4"(arr));
1456     assert(equal(m, [2, 3, 4]));
1457 }
1458 
1459 @safe unittest
1460 {
1461     import std.algorithm.comparison : equal;
1462 
1463     int[] a = [ 3, 4 ];
1464     const aConst = a;
1465     auto r = filter!("a > 3")(aConst);
1466     assert(equal(r, [ 4 ][]));
1467 
1468     a = [ 1, 22, 3, 42, 5 ];
1469     auto under10 = filter!("a < 10")(a);
1470     assert(equal(under10, [1, 3, 5][]));
1471     assert(equal(under10.save, [1, 3, 5][]));
1472     assert(equal(under10.save, under10));
1473 }
1474 
1475 @safe unittest
1476 {
1477     import std.algorithm.comparison : equal;
1478     import std.functional : compose, pipe;
1479 
1480     assert(equal(compose!(map!"2 * a", filter!"a & 1")([1,2,3,4,5]),
1481                     [2,6,10]));
1482     assert(equal(pipe!(filter!"a & 1", map!"2 * a")([1,2,3,4,5]),
1483             [2,6,10]));
1484 }
1485 
1486 @safe unittest
1487 {
1488     import std.algorithm.comparison : equal;
1489 
1490     int x = 10;
1491     int underX(int a) { return a < x; }
1492     const(int)[] list = [ 1, 2, 10, 11, 3, 4 ];
1493     assert(equal(filter!underX(list), [ 1, 2, 3, 4 ]));
1494 }
1495 
1496 // https://issues.dlang.org/show_bug.cgi?id=19823
1497 @safe unittest
1498 {
1499     import std.algorithm.comparison : equal;
1500     import std.range : dropOne;
1501 
1502     auto a = [1, 2, 3, 4];
1503     assert(a.filter!(a => a != 1).dropOne.equal([3, 4]));
1504     assert(a.filter!(a => a != 2).dropOne.equal([3, 4]));
1505     assert(a.filter!(a => a != 3).dropOne.equal([2, 4]));
1506     assert(a.filter!(a => a != 4).dropOne.equal([2, 3]));
1507     assert(a.filter!(a => a == 1).dropOne.empty);
1508     assert(a.filter!(a => a == 2).dropOne.empty);
1509     assert(a.filter!(a => a == 3).dropOne.empty);
1510     assert(a.filter!(a => a == 4).dropOne.empty);
1511 }
1512 
1513 /**
1514  * Similar to `filter`, except it defines a
1515  * $(REF_ALTTEXT bidirectional range, isBidirectionalRange, std,range,primitives).
1516  * There is a speed disadvantage - the constructor spends time
1517  * finding the last element in the range that satisfies the filtering
1518  * condition (in addition to finding the first one). The advantage is
1519  * that the filtered range can be spanned from both directions. Also,
1520  * $(REF retro, std,range) can be applied against the filtered range.
1521  *
1522  * The predicate is passed to $(REF unaryFun, std,functional), and can either
1523  * accept a string, or any callable that can be executed via `pred(element)`.
1524  *
1525  * Params:
1526  *     pred = Function to apply to each element of range
1527  */
1528 template filterBidirectional(alias pred)
1529 {
1530     /**
1531     Params:
1532         r = Bidirectional range of elements
1533     Returns:
1534         A range containing only the elements in `r` for which `pred` returns `true`.
1535      */
1536     auto filterBidirectional(Range)(Range r)
1537     if (isBidirectionalRange!(Unqual!Range))
1538     {
1539         return FilterBidiResult!(unaryFun!pred, Range)(r);
1540     }
1541 }
1542 
1543 ///
1544 @safe unittest
1545 {
1546     import std.algorithm.comparison : equal;
1547     import std.range;
1548 
1549     int[] arr = [ 1, 2, 3, 4, 5 ];
1550     auto small = filterBidirectional!("a < 3")(arr);
1551     static assert(isBidirectionalRange!(typeof(small)));
1552     assert(small.back == 2);
1553     assert(equal(small, [ 1, 2 ]));
1554     assert(equal(retro(small), [ 2, 1 ]));
1555     // In combination with chain() to span multiple ranges
1556     int[] a = [ 3, -2, 400 ];
1557     int[] b = [ 100, -101, 102 ];
1558     auto r = filterBidirectional!("a > 0")(chain(a, b));
1559     assert(r.back == 102);
1560 }
1561 
1562 private struct FilterBidiResult(alias pred, Range)
1563 {
1564     alias R = Unqual!Range;
1565     R _input;
1566 
1567     this(R r)
1568     {
1569         _input = r;
1570         while (!_input.empty && !pred(_input.front)) _input.popFront();
1571         while (!_input.empty && !pred(_input.back)) _input.popBack();
1572     }
1573 
1574     @property bool empty() { return _input.empty; }
1575 
1576     void popFront()
1577     {
1578         do
1579         {
1580             _input.popFront();
1581         } while (!_input.empty && !pred(_input.front));
1582     }
1583 
1584     @property auto ref front()
1585     {
1586         assert(!empty, "Attempting to fetch the front of an empty filterBidirectional.");
1587         return _input.front;
1588     }
1589 
1590     void popBack()
1591     {
1592         do
1593         {
1594             _input.popBack();
1595         } while (!_input.empty && !pred(_input.back));
1596     }
1597 
1598     @property auto ref back()
1599     {
1600         assert(!empty, "Attempting to fetch the back of an empty filterBidirectional.");
1601         return _input.back;
1602     }
1603 
1604     @property auto save()
1605     {
1606         return typeof(this)(_input.save);
1607     }
1608 }
1609 
1610 /**
1611 Groups consecutively equivalent elements into a single tuple of the element and
1612 the number of its repetitions.
1613 
1614 Similarly to `uniq`, `group` produces a range that iterates over unique
1615 consecutive elements of the given range. Each element of this range is a tuple
1616 of the element and the number of times it is repeated in the original range.
1617 Equivalence of elements is assessed by using the predicate `pred`, which
1618 defaults to `"a == b"`.  The predicate is passed to $(REF binaryFun, std,functional),
1619 and can either accept a string, or any callable that can be executed via
1620 `pred(element, element)`.
1621 
1622 Params:
1623     pred = Binary predicate for determining equivalence of two elements.
1624     R = The range type
1625     r = The $(REF_ALTTEXT input range, isInputRange, std,range,primitives) to
1626         iterate over.
1627 
1628 Returns: A range of elements of type `Tuple!(ElementType!R, uint)`,
1629 representing each consecutively unique element and its respective number of
1630 occurrences in that run.  This will be an input range if `R` is an input
1631 range, and a forward range in all other cases.
1632 
1633 See_Also: $(LREF chunkBy), which chunks an input range into subranges
1634     of equivalent adjacent elements.
1635 */
1636 Group!(pred, Range) group(alias pred = "a == b", Range)(Range r)
1637 {
1638     return typeof(return)(r);
1639 }
1640 
1641 /// ditto
1642 struct Group(alias pred, R)
1643 if (isInputRange!R)
1644 {
1645     import std.typecons : Rebindable, tuple, Tuple;
1646 
1647     private alias comp = binaryFun!pred;
1648 
1649     private alias E = ElementType!R;
1650     static if ((is(E == class) || is(E == interface)) &&
1651                (is(E == const) || is(E == immutable)))
1652     {
1653         private alias MutableE = Rebindable!E;
1654     }
1655     else static if (is(E : Unqual!E))
1656     {
1657         private alias MutableE = Unqual!E;
1658     }
1659     else
1660     {
1661         private alias MutableE = E;
1662     }
1663 
1664     private R _input;
1665     private Tuple!(MutableE, uint) _current;
1666 
1667     ///
1668     this(R input)
1669     {
1670         _input = input;
1671         if (!_input.empty) popFront();
1672     }
1673 
1674     private this(R input, Tuple!(MutableE, uint) current)
1675     {
1676         _input = input;
1677         _current = current;
1678     }
1679 
1680     ///
1681     void popFront()
1682     {
1683         if (_input.empty)
1684         {
1685             _current[1] = 0;
1686         }
1687         else
1688         {
1689             _current = tuple(_input.front, 1u);
1690             _input.popFront();
1691             while (!_input.empty && comp(_current[0], _input.front))
1692             {
1693                 ++_current[1];
1694                 _input.popFront();
1695             }
1696         }
1697     }
1698 
1699     static if (isInfinite!R)
1700     {
1701         ///
1702         enum bool empty = false;  // Propagate infiniteness.
1703     }
1704     else
1705     {
1706         ///
1707         @property bool empty()
1708         {
1709             return _current[1] == 0;
1710         }
1711     }
1712 
1713     /// Returns: the front of the range
1714     @property auto ref front()
1715     {
1716         assert(!empty, "Attempting to fetch the front of an empty Group.");
1717         return _current;
1718     }
1719 
1720     static if (isForwardRange!R)
1721     {
1722         ///
1723         @property typeof(this) save()
1724         {
1725             return Group(_input.save, _current);
1726         }
1727     }
1728 }
1729 
1730 ///
1731 @safe unittest
1732 {
1733     import std.algorithm.comparison : equal;
1734     import std.typecons : tuple, Tuple;
1735 
1736     int[] arr = [ 1, 2, 2, 2, 2, 3, 4, 4, 4, 5 ];
1737     assert(equal(group(arr), [ tuple(1, 1u), tuple(2, 4u), tuple(3, 1u),
1738         tuple(4, 3u), tuple(5, 1u) ][]));
1739 }
1740 
1741 /**
1742  * Using group, an associative array can be easily generated with the count of each
1743  * unique element in the range.
1744  */
1745 @safe unittest
1746 {
1747     import std.algorithm.sorting : sort;
1748     import std.array : assocArray;
1749 
1750     uint[string] result;
1751     auto range = ["a", "b", "a", "c", "b", "c", "c", "d", "e"];
1752     result = range.sort!((a, b) => a < b)
1753         .group
1754         .assocArray;
1755 
1756     assert(result == ["a": 2U, "b": 2U, "c": 3U, "d": 1U, "e": 1U]);
1757 }
1758 
1759 @safe unittest
1760 {
1761     import std.algorithm.comparison : equal;
1762     import std.internal.test.dummyrange;
1763     import std.typecons : tuple, Tuple;
1764 
1765     int[] arr = [ 1, 2, 2, 2, 2, 3, 4, 4, 4, 5 ];
1766     assert(equal(group(arr), [ tuple(1, 1u), tuple(2, 4u), tuple(3, 1u),
1767                             tuple(4, 3u), tuple(5, 1u) ][]));
1768     static assert(isForwardRange!(typeof(group(arr))));
1769 
1770     foreach (DummyType; AllDummyRanges)
1771     {
1772         DummyType d;
1773         auto g = group(d);
1774 
1775         static assert(d.rt == RangeType.Input || isForwardRange!(typeof(g)));
1776 
1777         assert(equal(g, [tuple(1, 1u), tuple(2, 1u), tuple(3, 1u), tuple(4, 1u),
1778             tuple(5, 1u), tuple(6, 1u), tuple(7, 1u), tuple(8, 1u),
1779             tuple(9, 1u), tuple(10, 1u)]));
1780     }
1781 }
1782 
1783 @safe unittest
1784 {
1785     import std.algorithm.comparison : equal;
1786     import std.typecons : tuple;
1787 
1788     // https://issues.dlang.org/show_bug.cgi?id=13857
1789     immutable(int)[] a1 = [1,1,2,2,2,3,4,4,5,6,6,7,8,9,9,9];
1790     auto g1 = group(a1);
1791     assert(equal(g1, [ tuple(1, 2u), tuple(2, 3u), tuple(3, 1u),
1792                        tuple(4, 2u), tuple(5, 1u), tuple(6, 2u),
1793                        tuple(7, 1u), tuple(8, 1u), tuple(9, 3u)
1794                      ]));
1795 
1796     // https://issues.dlang.org/show_bug.cgi?id=13162
1797     immutable(ubyte)[] a2 = [1, 1, 1, 0, 0, 0];
1798     auto g2 = a2.group;
1799     assert(equal(g2, [ tuple(1, 3u), tuple(0, 3u) ]));
1800 
1801     // https://issues.dlang.org/show_bug.cgi?id=10104
1802     const a3 = [1, 1, 2, 2];
1803     auto g3 = a3.group;
1804     assert(equal(g3, [ tuple(1, 2u), tuple(2, 2u) ]));
1805 
1806     interface I {}
1807     static class C : I { override size_t toHash() const nothrow @safe { return 0; } }
1808     const C[] a4 = [new const C()];
1809     auto g4 = a4.group!"a is b";
1810     assert(g4.front[1] == 1);
1811 
1812     immutable I[] a5 = [new immutable C()];
1813     auto g5 = a5.group!"a is b";
1814     assert(g5.front[1] == 1);
1815 
1816     const(int[][]) a6 = [[1], [1]];
1817     auto g6 = a6.group;
1818     assert(equal(g6.front[0], [1]));
1819 }
1820 
1821 @safe unittest
1822 {
1823     import std.algorithm.comparison : equal;
1824     import std.typecons : tuple;
1825 
1826     int[] arr = [ 1, 2, 2, 2, 2, 3, 4, 4, 4, 5 ];
1827     auto r = arr.group;
1828     assert(r.equal([ tuple(1,1u), tuple(2, 4u), tuple(3, 1u), tuple(4, 3u), tuple(5, 1u) ]));
1829     r.popFront;
1830     assert(r.equal([ tuple(2, 4u), tuple(3, 1u), tuple(4, 3u), tuple(5, 1u) ]));
1831     auto s = r.save;
1832     r.popFrontN(2);
1833     assert(r.equal([ tuple(4, 3u), tuple(5, 1u) ]));
1834     assert(s.equal([ tuple(2, 4u), tuple(3, 1u), tuple(4, 3u), tuple(5, 1u) ]));
1835     s.popFront;
1836     auto t = s.save;
1837     r.popFront;
1838     s.popFront;
1839     assert(r.equal([ tuple(5, 1u) ]));
1840     assert(s.equal([ tuple(4, 3u), tuple(5, 1u) ]));
1841     assert(t.equal([ tuple(3, 1u), tuple(4, 3u), tuple(5, 1u) ]));
1842 }
1843 
1844 // https://issues.dlang.org/show_bug.cgi?id=18657
1845 pure @safe unittest
1846 {
1847     import std.algorithm.comparison : equal;
1848     import std.range : refRange;
1849     string s = "foo";
1850     auto r = refRange(&s).group;
1851     assert(equal(r.save, "foo".group));
1852     assert(equal(r, "foo".group));
1853 }
1854 
1855 // Used by implementation of chunkBy for non-forward input ranges.
1856 private struct ChunkByChunkImpl(alias pred, Range)
1857 if (isInputRange!Range && !isForwardRange!Range)
1858 {
1859     alias fun = binaryFun!pred;
1860 
1861     private Range *r;
1862     private ElementType!Range prev;
1863 
1864     this(ref Range range, ElementType!Range _prev)
1865     {
1866         r = &range;
1867         prev = _prev;
1868     }
1869 
1870     @property bool empty()
1871     {
1872         return r.empty || !fun(prev, r.front);
1873     }
1874 
1875     @property ElementType!Range front()
1876     {
1877         assert(!empty, "Attempting to fetch the front of an empty chunkBy chunk.");
1878         return r.front;
1879     }
1880 
1881     void popFront()
1882     {
1883         assert(!empty, "Attempting to popFront an empty chunkBy chunk.");
1884         r.popFront();
1885     }
1886 }
1887 
1888 private template ChunkByImplIsUnary(alias pred, Range)
1889 {
1890     alias e = lvalueOf!(ElementType!Range);
1891 
1892     static if (is(typeof(binaryFun!pred(e, e)) : bool))
1893         enum ChunkByImplIsUnary = false;
1894     else static if (is(typeof(unaryFun!pred(e) == unaryFun!pred(e)) : bool))
1895         enum ChunkByImplIsUnary = true;
1896     else
1897         static assert(0, "chunkBy expects either a binary predicate or "~
1898                          "a unary predicate on range elements of type: "~
1899                          ElementType!Range.stringof);
1900 }
1901 
1902 // Implementation of chunkBy for non-forward input ranges.
1903 private struct ChunkByImpl(alias pred, Range)
1904 if (isInputRange!Range && !isForwardRange!Range)
1905 {
1906     enum bool isUnary = ChunkByImplIsUnary!(pred, Range);
1907 
1908     static if (isUnary)
1909         alias eq = binaryFun!((a, b) => unaryFun!pred(a) == unaryFun!pred(b));
1910     else
1911         alias eq = binaryFun!pred;
1912 
1913     private Range r;
1914     private ElementType!Range _prev;
1915     private bool openChunk = false;
1916 
1917     this(Range _r)
1918     {
1919         r = _r;
1920         if (!empty)
1921         {
1922             // Check reflexivity if predicate is claimed to be an equivalence
1923             // relation.
1924             assert(eq(r.front, r.front),
1925                    "predicate is not reflexive");
1926 
1927             // _prev's type may be a nested struct, so must be initialized
1928             // directly in the constructor (cannot call savePred()).
1929             _prev = r.front;
1930         }
1931         else
1932         {
1933             // We won't use _prev, but must be initialized.
1934             _prev = typeof(_prev).init;
1935         }
1936     }
1937     @property bool empty() { return r.empty && !openChunk; }
1938 
1939     @property auto front()
1940     {
1941         assert(!empty, "Attempting to fetch the front of an empty chunkBy.");
1942         openChunk = true;
1943         static if (isUnary)
1944         {
1945             import std.typecons : tuple;
1946             return tuple(unaryFun!pred(_prev),
1947                          ChunkByChunkImpl!(eq, Range)(r, _prev));
1948         }
1949         else
1950         {
1951             return ChunkByChunkImpl!(eq, Range)(r, _prev);
1952         }
1953     }
1954 
1955     void popFront()
1956     {
1957         assert(!empty, "Attempting to popFront an empty chunkBy.");
1958         openChunk = false;
1959         while (!r.empty)
1960         {
1961             if (!eq(_prev, r.front))
1962             {
1963                 _prev = r.front;
1964                 break;
1965             }
1966             r.popFront();
1967         }
1968     }
1969 }
1970 // Outer range for forward range version of chunkBy
1971 private struct ChunkByOuter(Range, bool eqEquivalenceAssured)
1972 {
1973     size_t groupNum;
1974     Range  current;
1975     Range  next;
1976     static if (!eqEquivalenceAssured)
1977     {
1978         bool nextUpdated;
1979     }
1980 }
1981 
1982 // Inner range for forward range version of chunkBy
1983 private struct ChunkByGroup(alias eq, Range, bool eqEquivalenceAssured)
1984 {
1985     import std.typecons : RefCounted;
1986 
1987     alias OuterRange = ChunkByOuter!(Range, eqEquivalenceAssured);
1988 
1989     private size_t groupNum;
1990     static if (eqEquivalenceAssured)
1991     {
1992         private Range  start;
1993     }
1994     private Range  current;
1995 
1996     // using union prevents RefCounted destructor from propagating @system to
1997     // user code
1998     union { private RefCounted!(OuterRange) mothership; }
1999     private @trusted ref cargo() { return mothership.refCountedPayload; }
2000 
2001     private this(ref RefCounted!(OuterRange) origin)
2002     {
2003         () @trusted { mothership = origin; }();
2004         groupNum = cargo.groupNum;
2005         current = cargo.current.save;
2006         assert(!current.empty, "Passed range 'r' must not be empty");
2007 
2008         static if (eqEquivalenceAssured)
2009         {
2010             start = cargo.current.save;
2011 
2012             // Check for reflexivity.
2013             assert(eq(start.front, current.front),
2014                 "predicate is not reflexive");
2015         }
2016     }
2017 
2018     // Cannot be a copy constructor due to https://issues.dlang.org/show_bug.cgi?id=22239
2019     this(this) scope @trusted
2020     {
2021         import core.lifetime : emplace;
2022         // since mothership has to be in a union, we have to manually trigger
2023         // an increment to the reference count.
2024         auto temp = mothership;
2025         mothership = temp;
2026 
2027         // prevents the reference count from falling back with brute force
2028         emplace(&temp);
2029     }
2030 
2031     @property bool empty() { return groupNum == size_t.max; }
2032     @property auto ref front() { return current.front; }
2033 
2034     void popFront()
2035     {
2036         static if (!eqEquivalenceAssured)
2037         {
2038             auto prevElement = current.front;
2039         }
2040 
2041         current.popFront();
2042 
2043         static if (eqEquivalenceAssured)
2044         {
2045             //this requires transitivity from the predicate.
2046             immutable nowEmpty = current.empty || !eq(start.front, current.front);
2047         }
2048         else
2049         {
2050             immutable nowEmpty = current.empty || !eq(prevElement, current.front);
2051         }
2052 
2053 
2054         if (nowEmpty)
2055         {
2056             if (groupNum == cargo.groupNum)
2057             {
2058                 // If parent range hasn't moved on yet, help it along by
2059                 // saving location of start of next Group.
2060                 cargo.next = current.save;
2061                 static if (!eqEquivalenceAssured)
2062                 {
2063                     cargo.nextUpdated = true;
2064                 }
2065             }
2066 
2067             groupNum = size_t.max;
2068         }
2069     }
2070 
2071     @property auto save()
2072     {
2073         auto copy = this;
2074         copy.current = current.save;
2075         return copy;
2076     }
2077 
2078     @trusted ~this()
2079     {
2080         mothership.destroy;
2081     }
2082 }
2083 
2084 private enum GroupingOpType{binaryEquivalent, binaryAny, unary}
2085 
2086 // Single-pass implementation of chunkBy for forward ranges.
2087 private struct ChunkByImpl(alias pred, alias eq, GroupingOpType opType, Range)
2088 if (isForwardRange!Range)
2089 {
2090     import std.typecons : RefCounted;
2091 
2092     enum bool eqEquivalenceAssured = opType != GroupingOpType.binaryAny;
2093     alias OuterRange = ChunkByOuter!(Range, eqEquivalenceAssured);
2094     alias InnerRange = ChunkByGroup!(eq, Range, eqEquivalenceAssured);
2095 
2096     static assert(isForwardRange!InnerRange);
2097 
2098     // using union prevents RefCounted destructor from propagating @system to
2099     // user code
2100     union { private RefCounted!OuterRange _impl; }
2101     private @trusted ref impl() { return _impl; }
2102     private @trusted ref implPL() { return _impl.refCountedPayload; }
2103 
2104     this(Range r)
2105     {
2106         import core.lifetime : move;
2107 
2108         auto savedR = r.save;
2109 
2110         static if (eqEquivalenceAssured) () @trusted
2111         {
2112             _impl = RefCounted!OuterRange(0, r, savedR.move);
2113         }();
2114         else () @trusted
2115         {
2116             _impl = RefCounted!OuterRange(0, r, savedR.move, false);
2117         }();
2118     }
2119 
2120     // Cannot be a copy constructor due to https://issues.dlang.org/show_bug.cgi?id=22239
2121     this(this) scope @trusted
2122     {
2123         import core.lifetime : emplace;
2124         // since _impl has to be in a union, we have to manually trigger
2125         // an increment to the reference count.
2126         auto temp = _impl;
2127         _impl = temp;
2128 
2129         // prevents the reference count from falling back with brute force
2130         emplace(&temp);
2131     }
2132 
2133     @property bool empty() { return implPL.current.empty; }
2134 
2135     static if (opType == GroupingOpType.unary) @property auto front()
2136     {
2137         import std.typecons : tuple;
2138 
2139         return tuple(unaryFun!pred(implPL.current.front), InnerRange(impl));
2140     }
2141     else @property auto front()
2142     {
2143         return InnerRange(impl);
2144     }
2145 
2146     static if (eqEquivalenceAssured) void popFront()
2147     {
2148         // Scan for next group. If we're lucky, one of our Groups would have
2149         // already set .next to the start of the next group, in which case the
2150         // loop is skipped.
2151         while (!implPL.next.empty && eq(implPL.current.front, implPL.next.front))
2152         {
2153             implPL.next.popFront();
2154         }
2155 
2156         implPL.current = implPL.next.save;
2157 
2158         // Indicate to any remaining Groups that we have moved on.
2159         implPL.groupNum++;
2160     }
2161     else void popFront()
2162     {
2163         if (implPL.nextUpdated)
2164         {
2165             implPL.current = implPL.next.save;
2166         }
2167         else while (true)
2168         {
2169             auto prevElement = implPL.current.front;
2170             implPL.current.popFront();
2171             if (implPL.current.empty) break;
2172             if (!eq(prevElement, implPL.current.front)) break;
2173         }
2174 
2175         implPL.nextUpdated = false;
2176         // Indicate to any remaining Groups that we have moved on.
2177         implPL.groupNum++;
2178     }
2179 
2180     @property auto save()
2181     {
2182         // Note: the new copy of the range will be detached from any existing
2183         // satellite Groups, and will not benefit from the .next acceleration.
2184         return typeof(this)(implPL.current.save);
2185     }
2186 
2187     static assert(isForwardRange!(typeof(this)), typeof(this).stringof
2188             ~ " must be a forward range");
2189 
2190     @trusted ~this()
2191     {
2192         _impl.destroy;
2193     }
2194 }
2195 
2196 //Test for https://issues.dlang.org/show_bug.cgi?id=14909
2197 @safe unittest
2198 {
2199     import std.algorithm.comparison : equal;
2200     import std.typecons : tuple;
2201     import std.stdio;
2202     auto n = 3;
2203     auto s = [1,2,3].chunkBy!(a => a+n);
2204     auto t = s.save.map!(x=>x[0]);
2205     auto u = s.map!(x=>x[1]);
2206     assert(t.equal([4,5,6]));
2207     assert(u.equal!equal([[1],[2],[3]]));
2208 }
2209 
2210 //Testing inferring @system correctly
2211 @safe unittest
2212 {
2213     struct DeadlySave
2214     {
2215         int front;
2216         @safe void popFront(){front++;}
2217         @safe bool empty(){return front >= 5;}
2218         @system auto save(){return this;}
2219     }
2220 
2221     auto test1()
2222     {
2223         DeadlySave src;
2224         return src.walkLength;
2225 
2226     }
2227 
2228     auto test2()
2229     {
2230         DeadlySave src;
2231         return src.chunkBy!((a,b) => a % 2 == b % 2).walkLength;
2232     }
2233 
2234     static assert(isSafe!test1);
2235     static assert(!isSafe!test2);
2236 }
2237 
2238 //Test for https://issues.dlang.org/show_bug.cgi?id=18751
2239 @safe unittest
2240 {
2241     import std.algorithm.comparison : equal;
2242 
2243     string[] data = [ "abc", "abc", "def" ];
2244     int[] indices = [ 0, 1, 2 ];
2245 
2246     auto chunks = indices.chunkBy!((i, j) => data[i] == data[j]);
2247     assert(chunks.equal!equal([ [ 0, 1 ], [ 2 ] ]));
2248 }
2249 
2250 //Additional test for fix for issues 14909 and 18751
2251 @safe unittest
2252 {
2253     import std.algorithm.comparison : equal;
2254     auto v = [2,4,8,3,6,9,1,5,7];
2255     auto i = 2;
2256     assert(v.chunkBy!((a,b) => a % i == b % i).equal!equal([[2,4,8],[3],[6],[9,1,5,7]]));
2257 }
2258 
2259 @system unittest
2260 {
2261     import std.algorithm.comparison : equal;
2262 
2263     size_t popCount = 0;
2264     static class RefFwdRange
2265     {
2266         int[]  impl;
2267         size_t* pcount;
2268 
2269         @safe nothrow:
2270 
2271         this(int[] data, size_t* pcount) { impl = data; this.pcount = pcount; }
2272         @property bool empty() { return impl.empty; }
2273         @property auto ref front() { return impl.front; }
2274         void popFront()
2275         {
2276             impl.popFront();
2277             (*pcount)++;
2278         }
2279         @property auto save() { return new RefFwdRange(impl, pcount); }
2280     }
2281     static assert(isForwardRange!RefFwdRange);
2282 
2283     auto testdata = new RefFwdRange([1, 3, 5, 2, 4, 7, 6, 8, 9], &popCount);
2284     auto groups = testdata.chunkBy!((a,b) => (a % 2) == (b % 2));
2285     auto outerSave1 = groups.save;
2286 
2287     // Sanity test
2288     assert(groups.equal!equal([[1, 3, 5], [2, 4], [7], [6, 8], [9]]));
2289     assert(groups.empty);
2290 
2291     // Performance test for single-traversal use case: popFront should not have
2292     // been called more times than there are elements if we traversed the
2293     // segmented range exactly once.
2294     assert(popCount == 9);
2295 
2296     // Outer range .save test
2297     groups = outerSave1.save;
2298     assert(!groups.empty);
2299 
2300     // Inner range .save test
2301     auto grp1 = groups.front.save;
2302     auto grp1b = grp1.save;
2303     assert(grp1b.equal([1, 3, 5]));
2304     assert(grp1.save.equal([1, 3, 5]));
2305 
2306     // Inner range should remain consistent after outer range has moved on.
2307     groups.popFront();
2308     assert(grp1.save.equal([1, 3, 5]));
2309 
2310     // Inner range should not be affected by subsequent inner ranges.
2311     assert(groups.front.equal([2, 4]));
2312     assert(grp1.save.equal([1, 3, 5]));
2313 }
2314 
2315 /**
2316  * Chunks an input range into subranges of equivalent adjacent elements.
2317  * In other languages this is often called `partitionBy`, `groupBy`
2318  * or `sliceWhen`.
2319  *
2320  * Equivalence is defined by the predicate `pred`, which can be either
2321  * binary, which is passed to $(REF binaryFun, std,functional), or unary, which is
2322  * passed to $(REF unaryFun, std,functional). In the binary form, two range elements
2323  * `a` and `b` are considered equivalent if `pred(a,b)` is true. In
2324  * unary form, two elements are considered equivalent if `pred(a) == pred(b)`
2325  * is true.
2326  *
2327  * This predicate must be an equivalence relation, that is, it must be
2328  * reflexive (`pred(x,x)` is always true), symmetric
2329  * (`pred(x,y) == pred(y,x)`), and transitive (`pred(x,y) && pred(y,z)`
2330  * implies `pred(x,z)`). If this is not the case, the range returned by
2331  * chunkBy may assert at runtime or behave erratically. Use $(LREF splitWhen)
2332  * if you want to chunk by a predicate that is not an equivalence relation.
2333  *
2334  * Params:
2335  *  pred = Predicate for determining equivalence.
2336  *  r = An $(REF_ALTTEXT input range, isInputRange, std,range,primitives) to be chunked.
2337  *
2338  * Returns: With a binary predicate, a range of ranges is returned in which
2339  * all elements in a given subrange are equivalent under the given predicate.
2340  * With a unary predicate, a range of tuples is returned, with the tuple
2341  * consisting of the result of the unary predicate for each subrange, and the
2342  * subrange itself. Copying the range currently has reference semantics, but this may
2343  * change in the future.
2344  *
2345  * Notes:
2346  *
2347  * Equivalent elements separated by an intervening non-equivalent element will
2348  * appear in separate subranges; this function only considers adjacent
2349  * equivalence. Elements in the subranges will always appear in the same order
2350  * they appear in the original range.
2351  *
2352  * See_also:
2353  * $(LREF group), which collapses adjacent equivalent elements into a single
2354  * element.
2355  */
2356 auto chunkBy(alias pred, Range)(Range r)
2357 if (isInputRange!Range)
2358 {
2359     static if (ChunkByImplIsUnary!(pred, Range))
2360     {
2361         enum opType = GroupingOpType.unary;
2362         alias eq = binaryFun!((a, b) => unaryFun!pred(a) == unaryFun!pred(b));
2363     }
2364     else
2365     {
2366         enum opType = GroupingOpType.binaryEquivalent;
2367         alias eq = binaryFun!pred;
2368     }
2369     static if (isForwardRange!Range)
2370         return ChunkByImpl!(pred, eq, opType, Range)(r);
2371     else
2372         return ChunkByImpl!(pred, Range)(r);
2373 }
2374 
2375 /// Showing usage with binary predicate:
2376 @safe unittest
2377 {
2378     import std.algorithm.comparison : equal;
2379 
2380     // Grouping by particular attribute of each element:
2381     auto data = [
2382         [1, 1],
2383         [1, 2],
2384         [2, 2],
2385         [2, 3]
2386     ];
2387 
2388     auto r1 = data.chunkBy!((a,b) => a[0] == b[0]);
2389     assert(r1.equal!equal([
2390         [[1, 1], [1, 2]],
2391         [[2, 2], [2, 3]]
2392     ]));
2393 
2394     auto r2 = data.chunkBy!((a,b) => a[1] == b[1]);
2395     assert(r2.equal!equal([
2396         [[1, 1]],
2397         [[1, 2], [2, 2]],
2398         [[2, 3]]
2399     ]));
2400 }
2401 
2402 /// Showing usage with unary predicate:
2403 /* FIXME: pure nothrow*/ @safe unittest
2404 {
2405     import std.algorithm.comparison : equal;
2406     import std.range.primitives;
2407     import std.typecons : tuple;
2408 
2409     // Grouping by particular attribute of each element:
2410     auto range =
2411     [
2412         [1, 1],
2413         [1, 1],
2414         [1, 2],
2415         [2, 2],
2416         [2, 3],
2417         [2, 3],
2418         [3, 3]
2419     ];
2420 
2421     auto byX = chunkBy!(a => a[0])(range);
2422     auto expected1 =
2423     [
2424         tuple(1, [[1, 1], [1, 1], [1, 2]]),
2425         tuple(2, [[2, 2], [2, 3], [2, 3]]),
2426         tuple(3, [[3, 3]])
2427     ];
2428     foreach (e; byX)
2429     {
2430         assert(!expected1.empty);
2431         assert(e[0] == expected1.front[0]);
2432         assert(e[1].equal(expected1.front[1]));
2433         expected1.popFront();
2434     }
2435 
2436     auto byY = chunkBy!(a => a[1])(range);
2437     auto expected2 =
2438     [
2439         tuple(1, [[1, 1], [1, 1]]),
2440         tuple(2, [[1, 2], [2, 2]]),
2441         tuple(3, [[2, 3], [2, 3], [3, 3]])
2442     ];
2443     foreach (e; byY)
2444     {
2445         assert(!expected2.empty);
2446         assert(e[0] == expected2.front[0]);
2447         assert(e[1].equal(expected2.front[1]));
2448         expected2.popFront();
2449     }
2450 }
2451 
2452 /*FIXME: pure @safe nothrow*/ @system unittest
2453 {
2454     import std.algorithm.comparison : equal;
2455     import std.typecons : tuple;
2456 
2457     struct Item { int x, y; }
2458 
2459     // Force R to have only an input range API with reference semantics, so
2460     // that we're not unknowingly making use of array semantics outside of the
2461     // range API.
2462     class RefInputRange(R)
2463     {
2464         R data;
2465         this(R _data) pure @safe nothrow { data = _data; }
2466         @property bool empty() pure @safe nothrow { return data.empty; }
2467         @property auto front() pure @safe nothrow { assert(!empty); return data.front; }
2468         void popFront() pure @safe nothrow { assert(!empty); data.popFront(); }
2469     }
2470     auto refInputRange(R)(R range) { return new RefInputRange!R(range); }
2471 
2472     // An input range API with value semantics.
2473     struct ValInputRange(R)
2474     {
2475         R data;
2476         this(R _data) pure @safe nothrow { data = _data; }
2477         @property bool empty() pure @safe nothrow { return data.empty; }
2478         @property auto front() pure @safe nothrow { assert(!empty); return data.front; }
2479         void popFront() pure @safe nothrow { assert(!empty); data.popFront(); }
2480     }
2481     auto valInputRange(R)(R range) { return ValInputRange!R(range); }
2482 
2483     {
2484         auto arr = [ Item(1,2), Item(1,3), Item(2,3) ];
2485         static assert(isForwardRange!(typeof(arr)));
2486 
2487         auto byX = chunkBy!(a => a.x)(arr);
2488         static assert(isForwardRange!(typeof(byX)));
2489 
2490         auto byX_subrange1 = byX.front[1].save;
2491         auto byX_subrange2 = byX.front[1].save;
2492         static assert(isForwardRange!(typeof(byX_subrange1)));
2493         static assert(isForwardRange!(typeof(byX_subrange2)));
2494 
2495         byX.popFront();
2496         assert(byX_subrange1.equal([ Item(1,2), Item(1,3) ]));
2497         byX_subrange1.popFront();
2498         assert(byX_subrange1.equal([ Item(1,3) ]));
2499         assert(byX_subrange2.equal([ Item(1,2), Item(1,3) ]));
2500 
2501         auto byY = chunkBy!(a => a.y)(arr);
2502         static assert(isForwardRange!(typeof(byY)));
2503 
2504         auto byY2 = byY.save;
2505         static assert(is(typeof(byY) == typeof(byY2)));
2506         byY.popFront();
2507         assert(byY.front[0] == 3);
2508         assert(byY.front[1].equal([ Item(1,3), Item(2,3) ]));
2509         assert(byY2.front[0] == 2);
2510         assert(byY2.front[1].equal([ Item(1,2) ]));
2511     }
2512 
2513     // Test non-forward input ranges with reference semantics.
2514     {
2515         auto range = refInputRange([ Item(1,1), Item(1,2), Item(2,2) ]);
2516         auto byX = chunkBy!(a => a.x)(range);
2517         assert(byX.front[0] == 1);
2518         assert(byX.front[1].equal([ Item(1,1), Item(1,2) ]));
2519         byX.popFront();
2520         assert(byX.front[0] == 2);
2521         assert(byX.front[1].equal([ Item(2,2) ]));
2522         byX.popFront();
2523         assert(byX.empty);
2524         assert(range.empty);
2525 
2526         range = refInputRange([ Item(1,1), Item(1,2), Item(2,2) ]);
2527         auto byY = chunkBy!(a => a.y)(range);
2528         assert(byY.front[0] == 1);
2529         assert(byY.front[1].equal([ Item(1,1) ]));
2530         byY.popFront();
2531         assert(byY.front[0] == 2);
2532         assert(byY.front[1].equal([ Item(1,2), Item(2,2) ]));
2533         byY.popFront();
2534         assert(byY.empty);
2535         assert(range.empty);
2536     }
2537 
2538     // Test non-forward input ranges with value semantics.
2539     {
2540         auto range = valInputRange([ Item(1,1), Item(1,2), Item(2,2) ]);
2541         auto byX = chunkBy!(a => a.x)(range);
2542         assert(byX.front[0] == 1);
2543         assert(byX.front[1].equal([ Item(1,1), Item(1,2) ]));
2544         byX.popFront();
2545         assert(byX.front[0] == 2);
2546         assert(byX.front[1].equal([ Item(2,2) ]));
2547         byX.popFront();
2548         assert(byX.empty);
2549         assert(!range.empty);    // Opposite of refInputRange test
2550 
2551         range = valInputRange([ Item(1,1), Item(1,2), Item(2,2) ]);
2552         auto byY = chunkBy!(a => a.y)(range);
2553         assert(byY.front[0] == 1);
2554         assert(byY.front[1].equal([ Item(1,1) ]));
2555         byY.popFront();
2556         assert(byY.front[0] == 2);
2557         assert(byY.front[1].equal([ Item(1,2), Item(2,2) ]));
2558         byY.popFront();
2559         assert(byY.empty);
2560         assert(!range.empty);    // Opposite of refInputRange test
2561     }
2562 
2563     /* https://issues.dlang.org/show_bug.cgi?id=19532
2564      * General behavior of non-forward input ranges.
2565      *
2566      * - If the same chunk is retrieved multiple times via front, the separate chunk
2567      *   instances refer to a shared range segment that advances as a single range.
2568      * - Emptying a chunk via popFront does not implicitly popFront the chunk off
2569      *   main range. The chunk is still available via front, it is just empty.
2570      */
2571     {
2572         import std.algorithm.comparison : equal;
2573         import core.exception : AssertError;
2574         import std.exception : assertThrown;
2575 
2576         auto a = [[0, 0], [0, 1],
2577                   [1, 2], [1, 3], [1, 4],
2578                   [2, 5], [2, 6],
2579                   [3, 7],
2580                   [4, 8]];
2581 
2582         // Value input range
2583         {
2584             auto r = valInputRange(a).chunkBy!((a, b) => a[0] == b[0]);
2585 
2586             size_t numChunks = 0;
2587             while (!r.empty)
2588             {
2589                 ++numChunks;
2590                 auto chunk = r.front;
2591                 while (!chunk.empty)
2592                 {
2593                     assert(r.front.front[1] == chunk.front[1]);
2594                     chunk.popFront;
2595                 }
2596                 assert(!r.empty);
2597                 assert(r.front.empty);
2598                 r.popFront;
2599             }
2600 
2601             assert(numChunks == 5);
2602 
2603             // Now front and popFront should assert.
2604             bool thrown = false;
2605             try r.front;
2606             catch (AssertError) thrown = true;
2607             assert(thrown);
2608 
2609             thrown = false;
2610             try r.popFront;
2611             catch (AssertError) thrown = true;
2612             assert(thrown);
2613         }
2614 
2615         // Reference input range
2616         {
2617             auto r = refInputRange(a).chunkBy!((a, b) => a[0] == b[0]);
2618 
2619             size_t numChunks = 0;
2620             while (!r.empty)
2621             {
2622                 ++numChunks;
2623                 auto chunk = r.front;
2624                 while (!chunk.empty)
2625                 {
2626                     assert(r.front.front[1] == chunk.front[1]);
2627                     chunk.popFront;
2628                 }
2629                 assert(!r.empty);
2630                 assert(r.front.empty);
2631                 r.popFront;
2632             }
2633 
2634             assert(numChunks == 5);
2635 
2636             // Now front and popFront should assert.
2637             bool thrown = false;
2638             try r.front;
2639             catch (AssertError) thrown = true;
2640             assert(thrown);
2641 
2642             thrown = false;
2643             try r.popFront;
2644             catch (AssertError) thrown = true;
2645             assert(thrown);
2646         }
2647 
2648         // Ensure that starting with an empty range doesn't create an empty chunk.
2649         {
2650             int[] emptyRange = [];
2651 
2652             auto r1 = valInputRange(emptyRange).chunkBy!((a, b) => a == b);
2653             auto r2 = refInputRange(emptyRange).chunkBy!((a, b) => a == b);
2654 
2655             assert(r1.empty);
2656             assert(r2.empty);
2657 
2658             bool thrown = false;
2659             try r1.front;
2660             catch (AssertError) thrown = true;
2661             assert(thrown);
2662 
2663             thrown = false;
2664             try r1.popFront;
2665             catch (AssertError) thrown = true;
2666             assert(thrown);
2667 
2668             thrown = false;
2669             try r2.front;
2670             catch (AssertError) thrown = true;
2671             assert(thrown);
2672 
2673             thrown = false;
2674             try r2.popFront;
2675             catch (AssertError) thrown = true;
2676             assert(thrown);
2677         }
2678     }
2679 
2680     // https://issues.dlang.org/show_bug.cgi?id=19532 - Using roundRobin/chunkBy
2681     {
2682         import std.algorithm.comparison : equal;
2683         import std.range : roundRobin;
2684 
2685         auto a0 = [0, 1, 3, 6];
2686         auto a1 = [0, 2, 4, 6, 7];
2687         auto a2 = [1, 2, 4, 6, 8, 8, 9];
2688 
2689         auto expected =
2690             [[0, 0], [1, 1], [2, 2], [3], [4, 4], [6, 6, 6], [7], [8, 8], [9]];
2691 
2692         auto r1 = roundRobin(valInputRange(a0), valInputRange(a1), valInputRange(a2))
2693             .chunkBy!((a, b) => a == b);
2694         assert(r1.equal!equal(expected));
2695 
2696         auto r2 = roundRobin(refInputRange(a0), refInputRange(a1), refInputRange(a2))
2697             .chunkBy!((a, b) => a == b);
2698         assert(r2.equal!equal(expected));
2699 
2700         auto r3 = roundRobin(a0, a1, a2).chunkBy!((a, b) => a == b);
2701         assert(r3.equal!equal(expected));
2702     }
2703 
2704     // https://issues.dlang.org/show_bug.cgi?id=19532 - Using merge/chunkBy
2705     {
2706         import std.algorithm.comparison : equal;
2707         import std.algorithm.sorting : merge;
2708 
2709         auto a0 = [2, 3, 5];
2710         auto a1 = [2, 4, 5];
2711         auto a2 = [1, 2, 4, 5];
2712 
2713         auto expected = [[1], [2, 2, 2], [3], [4, 4], [5, 5, 5]];
2714 
2715         auto r1 = merge(valInputRange(a0), valInputRange(a1), valInputRange(a2))
2716             .chunkBy!((a, b) => a == b);
2717         assert(r1.equal!equal(expected));
2718 
2719         auto r2 = merge(refInputRange(a0), refInputRange(a1), refInputRange(a2))
2720             .chunkBy!((a, b) => a == b);
2721         assert(r2.equal!equal(expected));
2722 
2723         auto r3 = merge(a0, a1, a2).chunkBy!((a, b) => a == b);
2724         assert(r3.equal!equal(expected));
2725     }
2726 
2727     // https://issues.dlang.org/show_bug.cgi?id=19532 - Using chunkBy/map-fold
2728     {
2729         import std.algorithm.comparison : equal;
2730         import std.algorithm.iteration : fold, map;
2731 
2732         auto a = [0, 0, 1, 1, 1, 2, 2, 3, 3, 4, 4, 5, 6, 6, 6, 7, 8, 8, 9];
2733         auto expected = [0, 3, 4, 6, 8, 5, 18, 7, 16, 9];
2734 
2735         auto r1 = a
2736             .chunkBy!((a, b) => a == b)
2737             .map!(c => c.fold!((a, b) => a + b));
2738         assert(r1.equal(expected));
2739 
2740         auto r2 = valInputRange(a)
2741             .chunkBy!((a, b) => a == b)
2742             .map!(c => c.fold!((a, b) => a + b));
2743         assert(r2.equal(expected));
2744 
2745         auto r3 = refInputRange(a)
2746             .chunkBy!((a, b) => a == b)
2747             .map!(c => c.fold!((a, b) => a + b));
2748         assert(r3.equal(expected));
2749     }
2750 
2751     // https://issues.dlang.org/show_bug.cgi?id=16169
2752     // https://issues.dlang.org/show_bug.cgi?id=17966
2753     // https://issues.dlang.org/show_bug.cgi?id=19532
2754     // Using multiwayMerge/chunkBy
2755     {
2756         import std.algorithm.comparison : equal;
2757         import std.algorithm.setops : multiwayMerge;
2758 
2759         {
2760             auto a0 = [2, 3, 5];
2761             auto a1 = [2, 4, 5];
2762             auto a2 = [1, 2, 4, 5];
2763 
2764             auto expected = [[1], [2, 2, 2], [3], [4, 4], [5, 5, 5]];
2765             auto r = multiwayMerge([a0, a1, a2]).chunkBy!((a, b) => a == b);
2766             assert(r.equal!equal(expected));
2767         }
2768         {
2769             auto a0 = [2, 3, 5];
2770             auto a1 = [2, 4, 5];
2771             auto a2 = [1, 2, 4, 5];
2772 
2773             auto expected = [[1], [2, 2, 2], [3], [4, 4], [5, 5, 5]];
2774             auto r =
2775                 multiwayMerge([valInputRange(a0), valInputRange(a1), valInputRange(a2)])
2776                 .chunkBy!((a, b) => a == b);
2777             assert(r.equal!equal(expected));
2778         }
2779         {
2780             auto a0 = [2, 3, 5];
2781             auto a1 = [2, 4, 5];
2782             auto a2 = [1, 2, 4, 5];
2783 
2784             auto expected = [[1], [2, 2, 2], [3], [4, 4], [5, 5, 5]];
2785             auto r =
2786                 multiwayMerge([refInputRange(a0), refInputRange(a1), refInputRange(a2)])
2787                 .chunkBy!((a, b) => a == b);
2788             assert(r.equal!equal(expected));
2789         }
2790     }
2791 
2792     // https://issues.dlang.org/show_bug.cgi?id=20496
2793     {
2794         auto r = [1,1,1,2,2,2,3,3,3];
2795         r.chunkBy!((ref e1, ref e2) => e1 == e2);
2796     }
2797 }
2798 
2799 
2800 
2801 // https://issues.dlang.org/show_bug.cgi?id=13805
2802 @safe unittest
2803 {
2804     [""].map!((s) => s).chunkBy!((x, y) => true);
2805 }
2806 
2807 /**
2808 Splits a forward range into subranges in places determined by a binary
2809 predicate.
2810 
2811 When iterating, one element of `r` is compared with `pred` to the next
2812 element. If `pred` return true, a new subrange is started for the next element.
2813 Otherwise, they are part of the same subrange.
2814 
2815 If the elements are compared with an inequality (!=) operator, consider
2816 $(LREF chunkBy) instead, as it's likely faster to execute.
2817 
2818 Params:
2819 pred = Predicate for determining where to split. The earlier element in the
2820 source range is always given as the first argument.
2821 r = A $(REF_ALTTEXT forward range, isForwardRange, std,range,primitives) to be split.
2822 Returns: a range of subranges of `r`, split such that within a given subrange,
2823 calling `pred` with any pair of adjacent elements as arguments returns `false`.
2824 Copying the range currently has reference semantics, but this may change in the future.
2825 
2826 See_also:
2827 $(LREF splitter), which uses elements as splitters instead of element-to-element
2828 relations.
2829 */
2830 
2831 auto splitWhen(alias pred, Range)(Range r)
2832 if (isForwardRange!Range)
2833 {   import std.functional : not;
2834     return ChunkByImpl!(not!pred, not!pred, GroupingOpType.binaryAny, Range)(r);
2835 }
2836 
2837 ///
2838 nothrow pure @safe unittest
2839 {
2840     import std.algorithm.comparison : equal;
2841     import std.range : dropExactly;
2842     auto source = [4, 3, 2, 11, 0, -3, -3, 5, 3, 0];
2843 
2844     auto result1 = source.splitWhen!((a,b) => a <= b);
2845     assert(result1.save.equal!equal([
2846         [4, 3, 2],
2847         [11, 0, -3],
2848         [-3],
2849         [5, 3, 0]
2850     ]));
2851 
2852     //splitWhen, like chunkBy, is currently a reference range (this may change
2853     //in future). Remember to call `save` when appropriate.
2854     auto result2 = result1.dropExactly(2);
2855     assert(result1.save.equal!equal([
2856         [-3],
2857         [5, 3, 0]
2858     ]));
2859 }
2860 
2861 //ensure we don't iterate the underlying range twice
2862 nothrow @safe unittest
2863 {
2864     import std.algorithm.comparison : equal;
2865     import std.math.algebraic : abs;
2866 
2867     struct SomeRange
2868     {
2869         int[] elements;
2870         static int popfrontsSoFar;
2871 
2872         auto front(){return elements[0];}
2873         nothrow @safe void popFront()
2874         {   popfrontsSoFar++;
2875             elements = elements[1 .. $];
2876         }
2877         auto empty(){return elements.length == 0;}
2878         auto save(){return this;}
2879     }
2880 
2881     auto result = SomeRange([10, 9, 8, 5, 0, 1, 0, 8, 11, 10, 8, 12])
2882         .splitWhen!((a, b) => abs(a - b) >= 3);
2883 
2884     assert(result.equal!equal([
2885         [10, 9, 8],
2886         [5],
2887         [0, 1, 0],
2888         [8],
2889         [11, 10, 8],
2890         [12]
2891     ]));
2892 
2893     assert(SomeRange.popfrontsSoFar == 12);
2894 }
2895 
2896 // Issue 13595
2897 @safe unittest
2898 {
2899     import std.algorithm.comparison : equal;
2900     auto r = [1, 2, 3, 4, 5, 6, 7, 8, 9].splitWhen!((x, y) => ((x*y) % 3) > 0);
2901     assert(r.equal!equal([
2902         [1],
2903         [2, 3, 4],
2904         [5, 6, 7],
2905         [8, 9]
2906     ]));
2907 }
2908 
2909 nothrow pure @safe unittest
2910 {
2911     // Grouping by maximum adjacent difference:
2912     import std.math.algebraic : abs;
2913     import std.algorithm.comparison : equal;
2914     auto r3 = [1, 3, 2, 5, 4, 9, 10].splitWhen!((a, b) => abs(a-b) >= 3);
2915     assert(r3.equal!equal([
2916         [1, 3, 2],
2917         [5, 4],
2918         [9, 10]
2919     ]));
2920 }
2921 
2922 // empty range splitWhen
2923 @nogc nothrow pure @system unittest
2924 {
2925     int[1] sliceable;
2926     auto result = sliceable[0 .. 0].splitWhen!((a,b) => a+b > 10);
2927     assert(result.empty);
2928 }
2929 
2930 // joiner
2931 /**
2932 Lazily joins a range of ranges with a separator. The separator itself
2933 is a range. If a separator is not provided, then the ranges are
2934 joined directly without anything in between them (often called `flatten`
2935 in other languages).
2936 
2937 Params:
2938     r = An $(REF_ALTTEXT input range, isInputRange, std,range,primitives) of input
2939         ranges to be joined.
2940     sep = A $(REF_ALTTEXT forward range, isForwardRange, std,range,primitives) of
2941         element(s) to serve as separators in the joined range.
2942 
2943 Returns:
2944 A range of elements in the joined range. This will be a bidirectional range if
2945 both outer and inner ranges of `RoR` are at least bidirectional ranges. Else if
2946 both outer and inner ranges of `RoR` are forward ranges, the returned range will
2947 be likewise. Otherwise it will be only an input range. The
2948 $(REF_ALTTEXT range bidirectionality, isBidirectionalRange, std,range,primitives)
2949 is propagated if no separator is specified.
2950 
2951 See_also:
2952 $(REF chain, std,range), which chains a sequence of ranges with compatible elements
2953 into a single range.
2954 
2955 Note:
2956 When both outer and inner ranges of `RoR` are bidirectional and the joiner is
2957 iterated from the back to the front, the separator will still be consumed from
2958 front to back, even if it is a bidirectional range too.
2959  */
2960 auto joiner(RoR, Separator)(RoR r, Separator sep)
2961 {
2962     static assert(isInputRange!RoR, "The type of RoR '", RoR.stringof
2963             , " must be an InputRange (isInputRange!", RoR.stringof, ").");
2964     static assert(isInputRange!(ElementType!RoR), "The ElementyType of RoR '"
2965             , ElementType!(RoR).stringof, "' must be an InputRange "
2966             , "(isInputRange!(ElementType!(", RoR.stringof , "))).");
2967     static assert(isForwardRange!Separator, "The type of the Separator '"
2968             , Separator.stringof, "' must be a ForwardRange (isForwardRange!("
2969             , Separator.stringof, ")).");
2970     static assert(is(ElementType!Separator : ElementType!(ElementType!RoR))
2971             , "The type of the elements of the separator range does not match "
2972             , "the type of the elements that are joined. Separator type '"
2973             , ElementType!(Separator).stringof, "' is not implicitly"
2974             , "convertible to range element type '"
2975             , ElementType!(ElementType!RoR).stringof, "' (is(ElementType!"
2976             , Separator.stringof, " : ElementType!(ElementType!", RoR.stringof
2977             , "))).");
2978 
2979     static struct Result
2980     {
2981         private RoR _items;
2982         private ElementType!RoR _current;
2983         bool inputStartsWithEmpty = false;
2984         static if (isBidirectional)
2985         {
2986             private ElementType!RoR _currentBack;
2987             bool inputEndsWithEmpty = false;
2988         }
2989         enum isBidirectional = isBidirectionalRange!RoR &&
2990                                isBidirectionalRange!(ElementType!RoR);
2991         static if (isRandomAccessRange!Separator)
2992         {
2993             static struct CurrentSep
2994             {
2995                 private Separator _sep;
2996                 private size_t sepIndex;
2997                 private size_t sepLength; // cache the length for performance
2998                 auto front() { return _sep[sepIndex]; }
2999                 void popFront() { sepIndex++; }
3000                 auto empty() { return sepIndex >= sepLength; }
3001                 auto save()
3002                 {
3003                     auto copy = this;
3004                     copy._sep = _sep;
3005                     return copy;
3006                 }
3007                 void reset()
3008                 {
3009                     sepIndex = 0;
3010                 }
3011 
3012                 void initialize(Separator sep)
3013                 {
3014                     _sep = sep;
3015                     sepIndex = sepLength = _sep.length;
3016                 }
3017             }
3018         }
3019         else
3020         {
3021             static struct CurrentSep
3022             {
3023                 private Separator _sep;
3024                 Separator payload;
3025 
3026                 alias payload this;
3027 
3028                 auto save()
3029                 {
3030                     auto copy = this;
3031                     copy._sep = _sep;
3032                     return copy;
3033                 }
3034 
3035                 void reset()
3036                 {
3037                     payload = _sep.save;
3038                 }
3039 
3040                 void initialize(Separator sep)
3041                 {
3042                     _sep = sep;
3043                 }
3044             }
3045         }
3046 
3047         private CurrentSep _currentSep;
3048         static if (isBidirectional)
3049         {
3050             private CurrentSep _currentBackSep;
3051         }
3052 
3053         private void setItem()
3054         {
3055             if (!_items.empty)
3056             {
3057                 // If we're exporting .save, we must not consume any of the
3058                 // subranges, since RoR.save does not guarantee that the states
3059                 // of the subranges are also saved.
3060                 static if (isForwardRange!RoR &&
3061                            isForwardRange!(ElementType!RoR))
3062                     _current = _items.front.save;
3063                 else
3064                     _current = _items.front;
3065             }
3066         }
3067 
3068         private void useSeparator()
3069         {
3070             // Separator must always come after an item.
3071             assert(_currentSep.empty,
3072                     "Attempting to reset a non-empty separator");
3073             assert(!_items.empty,
3074                     "Attempting to use a separator in an empty joiner");
3075             _items.popFront();
3076 
3077             // If there are no more items, we're done, since separators are not
3078             // terminators.
3079             if (_items.empty) return;
3080 
3081             if (_currentSep._sep.empty)
3082             {
3083                 // Advance to the next range in the
3084                 // input
3085                 while (_items.front.empty)
3086                 {
3087                     _items.popFront();
3088                     if (_items.empty) return;
3089                 }
3090                 setItem;
3091             }
3092             else
3093             {
3094                 _currentSep.reset;
3095                 assert(!_currentSep.empty, "separator must not be empty");
3096             }
3097         }
3098 
3099         this(RoR items, Separator sep)
3100         {
3101             _items = items;
3102             _currentSep.initialize(sep);
3103             static if (isBidirectional)
3104                 _currentBackSep.initialize(sep);
3105 
3106             //mixin(useItem); // _current should be initialized in place
3107             if (_items.empty)
3108             {
3109                 _current = _current.init;   // set invalid state
3110                 static if (isBidirectional)
3111                     _currentBack = _currentBack.init;
3112             }
3113             else
3114             {
3115                 // If we're exporting .save, we must not consume any of the
3116                 // subranges, since RoR.save does not guarantee that the states
3117                 // of the subranges are also saved.
3118                 static if (isForwardRange!RoR &&
3119                            isForwardRange!(ElementType!RoR))
3120                     _current = _items.front.save;
3121                 else
3122                     _current = _items.front;
3123 
3124                 static if (isBidirectional)
3125                 {
3126                     _currentBack = _items.back.save;
3127 
3128                     if (_currentBack.empty)
3129                     {
3130                         // No data in the currentBack item - toggle to use
3131                         // the separator
3132                         inputEndsWithEmpty = true;
3133                     }
3134                 }
3135 
3136                 if (_current.empty)
3137                 {
3138                     // No data in the current item - toggle to use the separator
3139                     inputStartsWithEmpty = true;
3140 
3141                     // If RoR contains a single empty element,
3142                     // the returned Result will always be empty
3143                     import std.range : dropOne;
3144                     static if (hasLength!RoR)
3145                     {
3146                         if (_items.length == 1)
3147                             _items.popFront;
3148                     }
3149                     else static if (isForwardRange!RoR)
3150                     {
3151                         if (_items.save.dropOne.empty)
3152                             _items.popFront;
3153                     }
3154                     else
3155                     {
3156                         auto _itemsCopy = _items;
3157                         if (_itemsCopy.dropOne.empty)
3158                             _items.popFront;
3159                     }
3160                 }
3161             }
3162         }
3163 
3164         @property auto empty()
3165         {
3166             return _items.empty;
3167         }
3168 
3169         //no data in the first item of the initial range - use the separator
3170         private enum useSepIfFrontIsEmpty = q{
3171             if (inputStartsWithEmpty)
3172             {
3173                 useSeparator();
3174                 inputStartsWithEmpty = false;
3175             }
3176         };
3177 
3178         @property ElementType!(ElementType!RoR) front()
3179         {
3180             mixin(useSepIfFrontIsEmpty);
3181             if (!_currentSep.empty) return _currentSep.front;
3182             assert(!_current.empty, "Attempting to fetch the front of an empty joiner.");
3183             return _current.front;
3184         }
3185 
3186         void popFront()
3187         {
3188             assert(!_items.empty, "Attempting to popFront an empty joiner.");
3189             // Using separator?
3190             mixin(useSepIfFrontIsEmpty);
3191 
3192             if (!_currentSep.empty)
3193             {
3194                 _currentSep.popFront();
3195                 if (_currentSep.empty && !_items.empty)
3196                 {
3197                     setItem;
3198                     if (_current.empty)
3199                     {
3200                         // No data in the current item - toggle to use the separator
3201                         useSeparator();
3202                     }
3203                 }
3204             }
3205             else
3206             {
3207                 // we're using the range
3208                 _current.popFront();
3209                 if (_current.empty)
3210                     useSeparator();
3211             }
3212         }
3213 
3214         static if (isForwardRange!RoR && isForwardRange!(ElementType!RoR))
3215         {
3216             @property auto save()
3217             {
3218                 Result copy = this;
3219                 copy._items = _items.save;
3220                 copy._current = _current.save;
3221                 copy._currentSep = _currentSep.save;
3222                 static if (isBidirectional)
3223                 {
3224                     copy._currentBack = _currentBack;
3225                     copy._currentBackSep = _currentBackSep;
3226                 }
3227                 return copy;
3228             }
3229         }
3230 
3231         static if (isBidirectional)
3232         {
3233             //no data in the last item of the initial range - use the separator
3234             private enum useSepIfBackIsEmpty = q{
3235                 if (inputEndsWithEmpty)
3236                 {
3237                     useBackSeparator;
3238                     inputEndsWithEmpty = false;
3239                 }
3240             };
3241 
3242             private void setBackItem()
3243             {
3244                 if (!_items.empty)
3245                 {
3246                     _currentBack = _items.back.save;
3247                 }
3248             }
3249 
3250             private void useBackSeparator()
3251             {
3252                 // Separator must always come after an item.
3253                 assert(_currentBackSep.empty,
3254                         "Attempting to reset a non-empty separator");
3255                 assert(!_items.empty,
3256                         "Attempting to use a separator in an empty joiner");
3257                 _items.popBack();
3258 
3259                 // If there are no more items, we're done, since separators are not
3260                 // terminators.
3261                 if (_items.empty) return;
3262 
3263                 if (_currentBackSep._sep.empty)
3264                 {
3265                     // Advance to the next range in the
3266                     // input
3267                     while (_items.back.empty)
3268                     {
3269                         _items.popBack();
3270                         if (_items.empty) return;
3271                     }
3272                     setBackItem;
3273                 }
3274                 else
3275                 {
3276                     _currentBackSep.reset;
3277                     assert(!_currentBackSep.empty, "separator must not be empty");
3278                 }
3279             }
3280 
3281             @property ElementType!(ElementType!RoR) back()
3282             {
3283                 mixin(useSepIfBackIsEmpty);
3284 
3285                 if (!_currentBackSep.empty) return _currentBackSep.front;
3286                 assert(!_currentBack.empty, "Attempting to fetch the back of an empty joiner.");
3287                 return _currentBack.back;
3288             }
3289 
3290             void popBack()
3291             {
3292                 assert(!_items.empty, "Attempting to popBack an empty joiner.");
3293 
3294                 mixin(useSepIfBackIsEmpty);
3295 
3296                 if (!_currentBackSep.empty)
3297                 {
3298                     _currentBackSep.popFront();
3299                     if (_currentBackSep.empty && !_items.empty)
3300                     {
3301                         setBackItem;
3302                         if (_currentBack.empty)
3303                         {
3304                             // No data in the current item - toggle to use the separator
3305                             useBackSeparator();
3306                         }
3307                     }
3308                 }
3309                 else
3310                 {
3311                     // we're using the range
3312                     _currentBack.popBack();
3313                     if (_currentBack.empty)
3314                         useBackSeparator();
3315                 }
3316             }
3317         }
3318     }
3319     return Result(r, sep);
3320 }
3321 
3322 ///
3323 @safe unittest
3324 {
3325     import std.algorithm.comparison : equal;
3326     import std.conv : text;
3327 
3328     assert(["abc", "def"].joiner.equal("abcdef"));
3329     assert(["Mary", "has", "a", "little", "lamb"]
3330         .joiner("...")
3331         .equal("Mary...has...a...little...lamb"));
3332     assert(["", "abc"].joiner("xyz").equal("xyzabc"));
3333     assert([""].joiner("xyz").equal(""));
3334     assert(["", ""].joiner("xyz").equal("xyz"));
3335 }
3336 
3337 @safe pure nothrow unittest
3338 {
3339     //joiner with separator can return a bidirectional range
3340     assert(isBidirectionalRange!(typeof(["abc", "def"].joiner("..."))));
3341 }
3342 
3343 @system unittest
3344 {
3345     import std.algorithm.comparison : equal;
3346     import std.range.interfaces;
3347     import std.range.primitives;
3348     // joiner() should work for non-forward ranges too.
3349     auto r = inputRangeObject(["abc", "def"]);
3350     assert(equal(joiner(r, "xyz"), "abcxyzdef"));
3351 }
3352 
3353 @system unittest
3354 {
3355     import std.algorithm.comparison : equal;
3356     import std.range;
3357 
3358     // Related to https://issues.dlang.org/show_bug.cgi?id=8061
3359     auto r = joiner([
3360         inputRangeObject("abc"),
3361         inputRangeObject("def"),
3362     ], "-*-");
3363 
3364     assert(equal(r, "abc-*-def"));
3365 
3366     // Test case where separator is specified but is empty.
3367     auto s = joiner([
3368         inputRangeObject("abc"),
3369         inputRangeObject("def"),
3370     ], "");
3371 
3372     assert(equal(s, "abcdef"));
3373 
3374     // Test empty separator with some empty elements
3375     auto t = joiner([
3376         inputRangeObject("abc"),
3377         inputRangeObject(""),
3378         inputRangeObject("def"),
3379         inputRangeObject(""),
3380     ], "");
3381 
3382     assert(equal(t, "abcdef"));
3383 
3384     // Test empty elements with non-empty separator
3385     auto u = joiner([
3386         inputRangeObject(""),
3387         inputRangeObject("abc"),
3388         inputRangeObject(""),
3389         inputRangeObject("def"),
3390         inputRangeObject(""),
3391     ], "+-");
3392 
3393     assert(equal(u, "+-abc+-+-def+-"));
3394 
3395     // https://issues.dlang.org/show_bug.cgi?id=13441: only(x) as separator
3396     string[][] lines = [null];
3397     lines
3398         .joiner(only("b"))
3399         .array();
3400 }
3401 
3402 @safe unittest
3403 {
3404     import std.algorithm.comparison : equal;
3405 
3406     // Transience correctness test
3407     struct TransientRange
3408     {
3409     @safe:
3410         int[][] src;
3411         int[] buf;
3412 
3413         this(int[][] _src)
3414         {
3415             src = _src;
3416             buf.length = 100;
3417         }
3418         @property bool empty() { return src.empty; }
3419         @property int[] front()
3420         {
3421             assert(src.front.length <= buf.length);
3422             buf[0 .. src.front.length] = src.front[0..$];
3423             return buf[0 .. src.front.length];
3424         }
3425         void popFront() { src.popFront(); }
3426     }
3427 
3428     // Test embedded empty elements
3429     auto tr1 = TransientRange([[], [1,2,3], [], [4]]);
3430     assert(equal(joiner(tr1, [0]), [0,1,2,3,0,0,4]));
3431 
3432     // Test trailing empty elements
3433     auto tr2 = TransientRange([[], [1,2,3], []]);
3434     assert(equal(joiner(tr2, [0]), [0,1,2,3,0]));
3435 
3436     // Test no empty elements
3437     auto tr3 = TransientRange([[1,2], [3,4]]);
3438     assert(equal(joiner(tr3, [0,1]), [1,2,0,1,3,4]));
3439 
3440     // Test consecutive empty elements
3441     auto tr4 = TransientRange([[1,2], [], [], [], [3,4]]);
3442     assert(equal(joiner(tr4, [0,1]), [1,2,0,1,0,1,0,1,0,1,3,4]));
3443 
3444     // Test consecutive trailing empty elements
3445     auto tr5 = TransientRange([[1,2], [3,4], [], []]);
3446     assert(equal(joiner(tr5, [0,1]), [1,2,0,1,3,4,0,1,0,1]));
3447 }
3448 
3449 @safe unittest
3450 {
3451     static assert(isInputRange!(typeof(joiner([""], ""))));
3452     static assert(isForwardRange!(typeof(joiner([""], ""))));
3453 }
3454 
3455 @safe pure unittest
3456 {
3457     {
3458         import std.algorithm.comparison : equal;
3459         auto r = joiner(["abc", "def", "ghi"], "?!");
3460         char[] res;
3461         while (!r.empty)
3462         {
3463             res ~= r.back;
3464             r.popBack;
3465         }
3466         assert(res.equal("ihg?!fed?!cba"));
3467     }
3468 
3469     {
3470         wchar[] sep = ['Ș', 'Ț'];
3471         auto r = joiner(["","abc",""],sep);
3472         wchar[] resFront;
3473         wchar[] resBack;
3474 
3475         auto rCopy = r.save;
3476         while (!r.empty)
3477         {
3478             resFront ~= r.front;
3479             r.popFront;
3480         }
3481 
3482         while (!rCopy.empty)
3483         {
3484             resBack ~= rCopy.back;
3485             rCopy.popBack;
3486         }
3487 
3488         import std.algorithm.comparison : equal;
3489 
3490         assert(resFront.equal("ȘȚabcȘȚ"));
3491         assert(resBack.equal("ȘȚcbaȘȚ"));
3492     }
3493 
3494     {
3495         import std.algorithm.comparison : equal;
3496         auto r = [""];
3497         r.popBack;
3498         assert(r.joiner("AB").equal(""));
3499     }
3500 
3501     {
3502         auto r = ["", "", "", "abc", ""].joiner("../");
3503         auto rCopy = r.save;
3504 
3505         char[] resFront;
3506         char[] resBack;
3507 
3508         while (!r.empty)
3509         {
3510             resFront ~= r.front;
3511             r.popFront;
3512         }
3513 
3514         while (!rCopy.empty)
3515         {
3516             resBack ~= rCopy.back;
3517             rCopy.popBack;
3518         }
3519 
3520         import std.algorithm.comparison : equal;
3521 
3522         assert(resFront.equal("../../../abc../"));
3523         assert(resBack.equal("../cba../../../"));
3524     }
3525 
3526     {
3527         auto r = ["", "abc", ""].joiner("./");
3528         auto rCopy = r.save;
3529         r.popBack;
3530         rCopy.popFront;
3531 
3532         auto rRev = r.save;
3533         auto rCopyRev = rCopy.save;
3534 
3535         char[] r1, r2, r3, r4;
3536 
3537         while (!r.empty)
3538         {
3539             r1 ~= r.back;
3540             r.popBack;
3541         }
3542 
3543         while (!rCopy.empty)
3544         {
3545             r2 ~= rCopy.front;
3546             rCopy.popFront;
3547         }
3548 
3549         while (!rRev.empty)
3550         {
3551             r3 ~= rRev.front;
3552             rRev.popFront;
3553         }
3554 
3555         while (!rCopyRev.empty)
3556         {
3557             r4 ~= rCopyRev.back;
3558             rCopyRev.popBack;
3559         }
3560 
3561         import std.algorithm.comparison : equal;
3562 
3563         assert(r1.equal("/cba./"));
3564         assert(r2.equal("/abc./"));
3565         assert(r3.equal("./abc"));
3566         assert(r4.equal("./cba"));
3567     }
3568 }
3569 
3570 @system unittest
3571 {
3572     import std.range;
3573     import std.algorithm.comparison : equal;
3574 
3575     assert(inputRangeObject([""]).joiner("lz").equal(""));
3576 }
3577 
3578 @safe pure unittest
3579 {
3580     struct inputRangeStrings
3581     {
3582         private string[] strings;
3583 
3584         string front()
3585         {
3586             return strings[0];
3587         }
3588 
3589         void popFront()
3590         {
3591             strings = strings[1..$];
3592         }
3593 
3594         bool empty() const
3595         {
3596            return strings.length == 0;
3597         }
3598     }
3599 
3600     auto arr = inputRangeStrings([""]);
3601 
3602     import std.algorithm.comparison : equal;
3603 
3604     assert(arr.joiner("./").equal(""));
3605 }
3606 
3607 @safe pure unittest
3608 {
3609     auto r = joiner(["", "", "abc", "", ""], "");
3610     char[] res;
3611     while (!r.empty)
3612     {
3613         res ~= r.back;
3614         r.popBack;
3615     }
3616 
3617     import std.algorithm.comparison : equal;
3618 
3619     assert(res.equal("cba"));
3620 }
3621 
3622 /// Ditto
3623 auto joiner(RoR)(RoR r)
3624 if (isInputRange!RoR && isInputRange!(Unqual!(ElementType!RoR)))
3625 {
3626     static struct Result
3627     {
3628     private:
3629         RoR _items;
3630         Unqual!(ElementType!RoR) _current;
3631         enum isBidirectional = isForwardRange!RoR && isForwardRange!(ElementType!RoR) &&
3632                                isBidirectionalRange!RoR && isBidirectionalRange!(ElementType!RoR);
3633         static if (isBidirectional)
3634         {
3635             Unqual!(ElementType!RoR) _currentBack;
3636             bool reachedFinalElement;
3637         }
3638 
3639         this(RoR items, ElementType!RoR current)
3640         {
3641             _items = items;
3642             _current = current;
3643             static if (isBidirectional && hasNested!Result)
3644                 _currentBack = typeof(_currentBack).init;
3645         }
3646 
3647         void replaceCurrent(typeof(_current) current) @trusted
3648         {
3649             import core.lifetime : move;
3650 
3651             current.move(_current);
3652         }
3653 
3654         static if (isBidirectional)
3655         {
3656             void replaceCurrentBack(typeof(_currentBack) currentBack) @trusted
3657             {
3658                 import core.lifetime : move;
3659 
3660                 currentBack.move(_currentBack);
3661             }
3662         }
3663 
3664     public:
3665         this(RoR r)
3666         {
3667             _items = r;
3668             // field _current must be initialized in constructor, because it is nested struct
3669             _current = typeof(_current).init;
3670 
3671             static if (isBidirectional && hasNested!Result)
3672                 _currentBack = typeof(_currentBack).init;
3673             mixin(popFrontEmptyElements);
3674             static if (isBidirectional)
3675                 mixin(popBackEmptyElements);
3676         }
3677         static if (isInfinite!RoR)
3678         {
3679             enum bool empty = false;
3680         }
3681         else
3682         {
3683             @property auto empty()
3684             {
3685                 return _items.empty;
3686             }
3687         }
3688         @property auto ref front()
3689         {
3690             assert(!empty, "Attempting to fetch the front of an empty joiner.");
3691             return _current.front;
3692         }
3693         void popFront()
3694         {
3695             assert(!_current.empty, "Attempting to popFront an empty joiner.");
3696             _current.popFront();
3697             if (_current.empty)
3698             {
3699                 assert(!_items.empty, "Attempting to popFront an empty joiner.");
3700                 _items.popFront();
3701                 mixin(popFrontEmptyElements);
3702             }
3703         }
3704 
3705         private enum popFrontEmptyElements = q{
3706             // Skip over empty subranges.
3707             while (!_items.empty && _items.front.empty)
3708             {
3709                 _items.popFront();
3710             }
3711             if (!_items.empty)
3712             {
3713                 // We cannot export .save method unless we ensure subranges are not
3714                 // consumed when a .save'd copy of ourselves is iterated over. So
3715                 // we need to .save each subrange we traverse.
3716                 static if (isForwardRange!RoR && isForwardRange!(ElementType!RoR))
3717                     replaceCurrent(_items.front.save);
3718                 else
3719                     replaceCurrent(_items.front);
3720             }
3721             else
3722             {
3723                 replaceCurrent(typeof(_current).init);
3724             }
3725         };
3726 
3727         static if (isForwardRange!RoR && isForwardRange!(ElementType!RoR))
3728         {
3729             @property auto save()
3730             {
3731                 // the null check is important if it is a class range, since null.save will segfault; issue #22359
3732                 // could not just compare x is y here without static if due to a compiler assertion failure
3733                 static if (is(typeof(null) : typeof(_current)))
3734                     auto r = Result(_items.save, _current is null ? null : _current.save);
3735                 else
3736                     auto r = Result(_items.save, _current.save);
3737                 static if (isBidirectional)
3738                 {
3739                     static if (is(typeof(null) : typeof(_currentBack)))
3740                         r.replaceCurrentBack(_currentBack is null ? null : _currentBack.save);
3741                     else
3742                         r.replaceCurrentBack(_currentBack.save);
3743                     r.reachedFinalElement = reachedFinalElement;
3744                 }
3745                 return r;
3746             }
3747         }
3748 
3749         static if (hasAssignableElements!(ElementType!RoR))
3750         {
3751             @property void front(ElementType!(ElementType!RoR) element)
3752             {
3753                 assert(!empty, "Attempting to assign to front of an empty joiner.");
3754                 _current.front = element;
3755             }
3756 
3757             @property void front(ref ElementType!(ElementType!RoR) element)
3758             {
3759                 assert(!empty, "Attempting to assign to front of an empty joiner.");
3760                 _current.front = element;
3761             }
3762         }
3763 
3764         static if (isBidirectional)
3765         {
3766             bool checkFinalElement()
3767             {
3768                 import std.range : dropOne;
3769 
3770                 if (reachedFinalElement)
3771                     return true;
3772 
3773                 static if (hasLength!(typeof(_items)))
3774                 {
3775                     if (_items.length == 1)
3776                         reachedFinalElement = true;
3777                 }
3778                 else
3779                 {
3780                     if (_items.save.dropOne.empty)
3781                         reachedFinalElement = true;
3782                 }
3783 
3784                 return false;
3785             }
3786 
3787             @property auto ref back()
3788             {
3789                 assert(!empty, "Attempting to fetch the back of an empty joiner.");
3790                 if (reachedFinalElement)
3791                     return _current.back;
3792                 else
3793                     return _currentBack.back;
3794             }
3795 
3796             void popBack()
3797             {
3798                 assert(!_current.empty, "Attempting to popBack an empty joiner.");
3799                 if (checkFinalElement)
3800                     _current.popBack();
3801                 else
3802                     _currentBack.popBack();
3803 
3804                 bool isEmpty = reachedFinalElement ? _current.empty : _currentBack.empty;
3805                 if (isEmpty)
3806                 {
3807                     assert(!_items.empty, "Attempting to popBack an empty joiner.");
3808                     _items.popBack();
3809                     mixin(popBackEmptyElements);
3810                 }
3811             }
3812 
3813             private enum popBackEmptyElements = q{
3814                 // Skip over empty subranges.
3815                 while (!_items.empty && _items.back.empty)
3816                 {
3817                     _items.popBack();
3818                 }
3819                 if (!_items.empty)
3820                 {
3821                     checkFinalElement;
3822                     // We cannot export .save method unless we ensure subranges are not
3823                     // consumed when a .save'd copy of ourselves is iterated over. So
3824                     // we need to .save each subrange we traverse.
3825                     static if (isForwardRange!RoR && isForwardRange!(ElementType!RoR))
3826                     {
3827                         if (reachedFinalElement)
3828                             replaceCurrent(_items.back.save);
3829                         else
3830                             replaceCurrentBack(_items.back.save);
3831                     }
3832                     else
3833                     {
3834                         if (reachedFinalElement)
3835                             replaceCurrent(_items.back);
3836                         else
3837                             replaceCurrentBack(_items.back);
3838                     }
3839                 }
3840                 else
3841                 {
3842                     replaceCurrent(typeof(_current).init);
3843                     replaceCurrentBack(typeof(_currentBack).init);
3844                 }
3845             };
3846 
3847             static if (hasAssignableElements!(ElementType!RoR))
3848             {
3849                 @property void back(ElementType!(ElementType!RoR) element)
3850                 {
3851                     assert(!empty, "Attempting to assign to back of an empty joiner.");
3852                     if (reachedFinalElement)
3853                         _current.back = element;
3854                     else
3855                         _currentBack.back = element;
3856                 }
3857 
3858                 @property void back(ref ElementType!(ElementType!RoR) element)
3859                 {
3860                     assert(!empty, "Attempting to assign to back of an empty joiner.");
3861                     if (reachedFinalElement)
3862                         _current.back = element;
3863                     else
3864                         _currentBack.back = element;
3865                 }
3866             }
3867         }
3868     }
3869     return Result(r);
3870 }
3871 
3872 ///
3873 @safe unittest
3874 {
3875     import std.algorithm.comparison : equal;
3876     import std.range : repeat;
3877 
3878     assert([""].joiner.equal(""));
3879     assert(["", ""].joiner.equal(""));
3880     assert(["", "abc"].joiner.equal("abc"));
3881     assert(["abc", ""].joiner.equal("abc"));
3882     assert(["abc", "def"].joiner.equal("abcdef"));
3883     assert(["Mary", "has", "a", "little", "lamb"].joiner.equal("Maryhasalittlelamb"));
3884     assert("abc".repeat(3).joiner.equal("abcabcabc"));
3885 }
3886 
3887 /// joiner allows in-place mutation!
3888 @safe unittest
3889 {
3890     import std.algorithm.comparison : equal;
3891     auto a = [ [1, 2, 3], [42, 43] ];
3892     auto j = joiner(a);
3893     j.front = 44;
3894     assert(a == [ [44, 2, 3], [42, 43] ]);
3895     assert(equal(j, [44, 2, 3, 42, 43]));
3896 }
3897 
3898 /// insert characters fully lazily into a string
3899 @safe pure unittest
3900 {
3901     import std.algorithm.comparison : equal;
3902     import std.range : chain, cycle, iota, only, retro, take, zip;
3903     import std.format : format;
3904 
3905     static immutable number = "12345678";
3906     static immutable delimiter = ",";
3907     auto formatted = number.retro
3908         .zip(3.iota.cycle.take(number.length))
3909         .map!(z => chain(z[0].only, z[1] == 2 ? delimiter : null))
3910         .joiner
3911         .retro;
3912     static immutable expected = "12,345,678";
3913     assert(formatted.equal(expected));
3914 }
3915 
3916 @safe unittest
3917 {
3918     import std.range.interfaces : inputRangeObject;
3919     static assert(isInputRange!(typeof(joiner([""]))));
3920     static assert(isForwardRange!(typeof(joiner([""]))));
3921 }
3922 
3923 @system unittest
3924 {
3925     // this test is system because the virtual interface call to save
3926     // is flexible and thus cannot be inferred safe automatically
3927 
3928     // https://issues.dlang.org/show_bug.cgi?id=22359
3929     import std.range;
3930     ForwardRange!int bug(int[][] r)
3931     {
3932         import std.range : inputRangeObject;
3933         import std.algorithm.iteration : map, joiner;
3934 
3935         auto range = inputRangeObject(r);
3936 
3937         return range.map!(a =>inputRangeObject(a)).joiner.inputRangeObject;
3938     }
3939     auto f = bug([[]]);
3940     f.save(); // should not segfault
3941 }
3942 
3943 @safe unittest
3944 {
3945     // Initial version of PR #6115 caused a compilation failure for
3946     // https://github.com/BlackEdder/ggplotd/blob/d4428c08db5ffdc05dfd29690bf7da9073ea1dc5/source/ggplotd/stat.d#L562-L583
3947     import std.range : zip;
3948     int[] xCoords = [1, 2, 3];
3949     int[] yCoords = [4, 5, 6];
3950     auto coords = zip(xCoords, xCoords[1..$]).map!( (xr) {
3951             return zip(yCoords, yCoords[1..$]).map!( (yr) {
3952                     return [
3953                     [[xr[0], xr[0], xr[1]],
3954                      [yr[0], yr[1], yr[1]]],
3955                     [[xr[0], xr[1], xr[1]],
3956                      [yr[0], yr[0], yr[1]]]
3957                      ];
3958             }).joiner;
3959     }).joiner;
3960 }
3961 
3962 @system unittest
3963 {
3964     import std.algorithm.comparison : equal;
3965     import std.range.interfaces : inputRangeObject;
3966     import std.range : retro;
3967 
3968     // https://issues.dlang.org/show_bug.cgi?id=8240
3969     assert(equal(joiner([inputRangeObject("")]), ""));
3970     assert(equal(joiner([inputRangeObject("")]).retro, ""));
3971 
3972     // https://issues.dlang.org/show_bug.cgi?id=8792
3973     auto b = [[1], [2], [3]];
3974     auto jb = joiner(b);
3975     auto js = jb.save;
3976     assert(equal(jb, js));
3977 
3978     auto js2 = jb.save;
3979     jb.popFront();
3980     assert(!equal(jb, js));
3981     assert(equal(js2, js));
3982     js.popFront();
3983     assert(equal(jb, js));
3984     assert(!equal(js2, js));
3985 }
3986 
3987 // https://issues.dlang.org/show_bug.cgi?id=19213
3988 @system unittest
3989 {
3990     auto results = [[1,2], [3,4]].map!(q => q.chunkBy!"a").joiner;
3991     int i = 1;
3992     foreach (ref e; results)
3993         assert(e[0] == i++);
3994 }
3995 
3996 /// joiner can be bidirectional
3997 @safe unittest
3998 {
3999     import std.algorithm.comparison : equal;
4000     import std.range : retro;
4001 
4002     auto a = [[1, 2, 3], [4, 5]];
4003     auto j = a.joiner;
4004     j.back = 44;
4005     assert(a == [[1, 2, 3], [4, 44]]);
4006     assert(equal(j.retro, [44, 4, 3, 2, 1]));
4007 }
4008 
4009 // bidirectional joiner: test for filtering empty elements
4010 @safe unittest
4011 {
4012     import std.algorithm.comparison : equal;
4013     import std.range : retro;
4014 
4015     alias El = (e) => new int(e);
4016     auto a = [null, [null, El(1), null, El(2), null, El(3), null], null, [null, El(4), null, El(5), null]];
4017     auto j = a.joiner;
4018 
4019     alias deref = a => a is null ? -1 : *a;
4020     auto expected = [-1, 5, -1, 4, -1, -1, 3, -1, 2, -1, 1, -1];
4021     // works with .save.
4022     assert(j.save.retro.map!deref.equal(expected));
4023     // and without .save
4024     assert(j.retro.map!deref.equal(expected));
4025     assert(j.retro.map!deref.equal(expected));
4026 }
4027 
4028 // bidirectional joiner is @nogc
4029 @safe @nogc unittest
4030 {
4031     import std.algorithm.comparison : equal;
4032     import std.range : iota, only, retro;
4033 
4034     auto a = only(iota(1, 4), iota(4, 6));
4035     auto j = a.joiner;
4036     static immutable expected = [5 , 4, 3, 2, 1];
4037     assert(equal(j.retro, expected));
4038 }
4039 
4040 // bidirectional joiner supports assignment to the back
4041 @safe unittest
4042 {
4043     import std.algorithm.comparison : equal;
4044     import std.range : popBackN;
4045 
4046     auto a = [[1, 2, 3], [4, 5]];
4047     auto j = a.joiner;
4048     j.back = 55;
4049     assert(a == [[1, 2, 3], [4, 55]]);
4050     j.popBackN(2);
4051     j.back = 33;
4052     assert(a == [[1, 2, 33], [4, 55]]);
4053 }
4054 
4055 // bidirectional joiner works with auto-decoding
4056 @safe unittest
4057 {
4058     import std.algorithm.comparison : equal;
4059     import std.range : retro;
4060 
4061     auto a = ["😀😐", "😠"];
4062     auto j = a.joiner;
4063     assert(j.retro.equal("😠😐😀"));
4064 }
4065 
4066 // test two-side iteration
4067 @safe unittest
4068 {
4069     import std.algorithm.comparison : equal;
4070     import std.range : popBackN;
4071 
4072     auto arrs = [
4073         [[1], [2], [3], [4], [5]],
4074         [[1], [2, 3, 4], [5]],
4075         [[1, 2, 3, 4, 5]],
4076     ];
4077     foreach (arr; arrs)
4078     {
4079         auto a = arr.joiner;
4080         assert(a.front == 1);
4081         assert(a.back == 5);
4082         a.popFront;
4083         assert(a.front == 2);
4084         assert(a.back == 5);
4085         a.popBack;
4086         assert(a.front == 2);
4087         assert(a.back == 4);
4088         a.popFront;
4089         assert(a.front == 3);
4090         assert(a.back == 4);
4091         a.popBack;
4092         assert(a.front == 3);
4093         assert(a.back == 3);
4094         a.popBack;
4095         assert(a.empty);
4096     }
4097 }
4098 
4099 @safe unittest
4100 {
4101     import std.algorithm.comparison : equal;
4102 
4103     struct TransientRange
4104     {
4105     @safe:
4106         int[] _buf;
4107         int[][] _values;
4108         this(int[][] values)
4109         {
4110             _values = values;
4111             _buf = new int[128];
4112         }
4113         @property bool empty()
4114         {
4115             return _values.length == 0;
4116         }
4117         @property auto front()
4118         {
4119             foreach (i; 0 .. _values.front.length)
4120             {
4121                 _buf[i] = _values[0][i];
4122             }
4123             return _buf[0 .. _values.front.length];
4124         }
4125         void popFront()
4126         {
4127             _values = _values[1 .. $];
4128         }
4129     }
4130 
4131     auto rr = TransientRange([[1,2], [3,4,5], [], [6,7]]);
4132 
4133     // Can't use array() or equal() directly because they fail with transient
4134     // .front.
4135     int[] result;
4136     foreach (c; rr.joiner())
4137     {
4138         result ~= c;
4139     }
4140 
4141     assert(equal(result, [1,2,3,4,5,6,7]));
4142 }
4143 
4144 @safe unittest
4145 {
4146     import std.algorithm.comparison : equal;
4147     import std.algorithm.internal : algoFormat;
4148 
4149     struct TransientRange
4150     {
4151     @safe:
4152         dchar[] _buf;
4153         dstring[] _values;
4154         this(dstring[] values)
4155         {
4156             _buf.length = 128;
4157             _values = values;
4158         }
4159         @property bool empty()
4160         {
4161             return _values.length == 0;
4162         }
4163         @property auto front()
4164         {
4165             foreach (i; 0 .. _values.front.length)
4166             {
4167                 _buf[i] = _values[0][i];
4168             }
4169             return _buf[0 .. _values.front.length];
4170         }
4171         void popFront()
4172         {
4173             _values = _values[1 .. $];
4174         }
4175     }
4176 
4177     auto rr = TransientRange(["abc"d, "12"d, "def"d, "34"d]);
4178 
4179     // Can't use array() or equal() directly because they fail with transient
4180     // .front.
4181     dchar[] result;
4182     foreach (c; rr.joiner())
4183     {
4184         result ~= c;
4185     }
4186 
4187     import std.conv : to;
4188     assert(equal(result, "abc12def34"d),
4189         //Convert to string for assert's message
4190         to!string("Unexpected result: '%s'"d.algoFormat(result)));
4191 }
4192 
4193 // https://issues.dlang.org/show_bug.cgi?id=8061
4194 @system unittest
4195 {
4196     import std.conv : to;
4197     import std.range.interfaces;
4198 
4199     auto r = joiner([inputRangeObject("ab"), inputRangeObject("cd")]);
4200     assert(isForwardRange!(typeof(r)));
4201 
4202     auto str = to!string(r);
4203     assert(str == "abcd");
4204 }
4205 
4206 @safe unittest
4207 {
4208     import std.range : repeat;
4209 
4210     class AssignableRange
4211     {
4212     @safe:
4213         int element;
4214         @property int front()
4215         {
4216             return element;
4217         }
4218         alias back = front;
4219 
4220         enum empty = false;
4221 
4222         auto save()
4223         {
4224             return this;
4225         }
4226 
4227         void popFront() {}
4228         alias popBack = popFront;
4229 
4230         @property void front(int newValue)
4231         {
4232             element = newValue;
4233         }
4234         alias back = front;
4235     }
4236 
4237     static assert(isInputRange!AssignableRange);
4238     static assert(is(ElementType!AssignableRange == int));
4239     static assert(hasAssignableElements!AssignableRange);
4240     static assert(!hasLvalueElements!AssignableRange);
4241 
4242     auto range = new AssignableRange();
4243     assert(range.element == 0);
4244     {
4245         auto joined = joiner(repeat(range));
4246         joined.front = 5;
4247         assert(range.element == 5);
4248         assert(joined.front == 5);
4249 
4250         joined.popFront;
4251         int byRef = 7;
4252         joined.front = byRef;
4253         assert(range.element == byRef);
4254         assert(joined.front == byRef);
4255     }
4256     {
4257         auto joined = joiner(repeat(range));
4258         joined.back = 5;
4259         assert(range.element == 5);
4260         assert(joined.back == 5);
4261 
4262         joined.popBack;
4263         int byRef = 7;
4264         joined.back = byRef;
4265         assert(range.element == byRef);
4266         assert(joined.back == byRef);
4267     }
4268 }
4269 
4270 // https://issues.dlang.org/show_bug.cgi?id=19850
4271 @safe pure unittest
4272 {
4273     assert([[0]].joiner.save.back == 0);
4274 }
4275 
4276 // https://issues.dlang.org/show_bug.cgi?id=22561
4277 @safe pure unittest
4278 {
4279     import std.range : only;
4280 
4281     static immutable struct S { int[] array; }
4282     assert([only(S(null))].joiner.front == S(null));
4283 }
4284 
4285 // https://issues.dlang.org/show_bug.cgi?id=22785
4286 @safe unittest
4287 {
4288 
4289     import std.algorithm.iteration : joiner, map;
4290     import std.array : array;
4291 
4292     static immutable struct S
4293     {
4294         int value;
4295     }
4296 
4297     static immutable struct T
4298     {
4299         S[] arr;
4300     }
4301 
4302     auto range = [T([S(3)]), T([S(4), S(5)])];
4303 
4304     assert(range.map!"a.arr".joiner.array == [S(3), S(4), S(5)]);
4305 }
4306 
4307 /++
4308 Implements the homonym function (also known as `accumulate`, $(D
4309 compress), `inject`, or `foldl`) present in various programming
4310 languages of functional flavor. There is also $(LREF fold) which does
4311 the same thing but with the opposite parameter order.
4312 The call `reduce!(fun)(seed, range)` first assigns `seed` to
4313 an internal variable `result`, also called the accumulator.
4314 Then, for each element `x` in `range`, `result = fun(result, x)`
4315 gets evaluated. Finally, `result` is returned.
4316 The one-argument version `reduce!(fun)(range)`
4317 works similarly, but it uses the first element of the range as the
4318 seed (the range must be non-empty).
4319 
4320 Returns:
4321     the accumulated `result`
4322 
4323 Params:
4324     fun = one or more functions
4325 
4326 See_Also:
4327     $(HTTP en.wikipedia.org/wiki/Fold_(higher-order_function), Fold (higher-order function))
4328 
4329     $(LREF fold) is functionally equivalent to $(LREF _reduce) with the argument
4330     order reversed, and without the need to use $(REF_ALTTEXT `tuple`,tuple,std,typecons)
4331     for multiple seeds. This makes it easier to use in UFCS chains.
4332 
4333     $(LREF sum) is similar to `reduce!((a, b) => a + b)` that offers
4334     pairwise summing of floating point numbers.
4335 +/
4336 template reduce(fun...)
4337 if (fun.length >= 1)
4338 {
4339     import std.meta : staticMap;
4340 
4341     alias binfuns = staticMap!(binaryFun, fun);
4342     static if (fun.length > 1)
4343         import std.typecons : tuple, isTuple;
4344 
4345     /++
4346     No-seed version. The first element of `r` is used as the seed's value.
4347 
4348     For each function `f` in `fun`, the corresponding
4349     seed type `S` is `Unqual!(typeof(f(e, e)))`, where `e` is an
4350     element of `r`: `ElementType!R` for ranges,
4351     and `ForeachType!R` otherwise.
4352 
4353     Once S has been determined, then `S s = e;` and `s = f(s, e);`
4354     must both be legal.
4355 
4356     Params:
4357         r = an iterable value as defined by `isIterable`
4358 
4359     Returns:
4360         the final result of the accumulator applied to the iterable
4361 
4362     Throws: `Exception` if `r` is empty
4363     +/
4364     auto reduce(R)(R r)
4365     if (isIterable!R)
4366     {
4367         import std.exception : enforce;
4368         alias E = Select!(isInputRange!R, ElementType!R, ForeachType!R);
4369         alias Args = staticMap!(ReduceSeedType!E, binfuns);
4370 
4371         static if (isInputRange!R)
4372         {
4373             // no need to throw if range is statically known to be non-empty
4374             static if (!__traits(compiles,
4375             {
4376                 static assert(r.length > 0);
4377             }))
4378                 enforce(!r.empty, "Cannot reduce an empty input range w/o an explicit seed value.");
4379 
4380             Args result = r.front;
4381             r.popFront();
4382             return reduceImpl!false(r, result);
4383         }
4384         else
4385         {
4386             auto result = Args.init;
4387             return reduceImpl!true(r, result);
4388         }
4389     }
4390 
4391     /++
4392     Seed version. The seed should be a single value if `fun` is a
4393     single function. If `fun` is multiple functions, then `seed`
4394     should be a $(REF Tuple, std,typecons), with one field per function in `f`.
4395 
4396     For convenience, if the seed is const, or has qualified fields, then
4397     `reduce` will operate on an unqualified copy. If this happens
4398     then the returned type will not perfectly match `S`.
4399 
4400     Use `fold` instead of `reduce` to use the seed version in a UFCS chain.
4401 
4402     Params:
4403         seed = the initial value of the accumulator
4404         r = an iterable value as defined by `isIterable`
4405 
4406     Returns:
4407         the final result of the accumulator applied to the iterable
4408     +/
4409     auto reduce(S, R)(S seed, R r)
4410     if (isIterable!R)
4411     {
4412         static if (fun.length == 1)
4413             return reducePreImpl(r, seed);
4414         else
4415         {
4416             import std.algorithm.internal : algoFormat;
4417             static assert(isTuple!S, algoFormat("Seed %s should be a Tuple", S.stringof));
4418             return reducePreImpl(r, seed.expand);
4419         }
4420     }
4421 
4422     private auto reducePreImpl(R, Args...)(R r, ref Args args)
4423     {
4424         alias Result = staticMap!(Unqual, Args);
4425         static if (is(Result == Args))
4426             alias result = args;
4427         else
4428             Result result = args;
4429         return reduceImpl!false(r, result);
4430     }
4431 
4432     private auto reduceImpl(bool mustInitialize, R, Args...)(R r, ref Args args)
4433     if (isIterable!R)
4434     {
4435         import std.algorithm.internal : algoFormat;
4436         static assert(Args.length == fun.length,
4437             algoFormat("Seed %s does not have the correct amount of fields (should be %s)", Args.stringof, fun.length));
4438         alias E = Select!(isInputRange!R, ElementType!R, ForeachType!R);
4439 
4440         static if (mustInitialize) bool initialized = false;
4441         foreach (/+auto ref+/ E e; r) // https://issues.dlang.org/show_bug.cgi?id=4707
4442         {
4443             foreach (i, f; binfuns)
4444             {
4445                 static assert(!is(typeof(f(args[i], e))) || is(typeof(args[i] = f(args[i], e))),
4446                     algoFormat(
4447                         "Incompatible function/seed/element: %s/%s/%s",
4448                         fullyQualifiedName!f,
4449                         Args[i].stringof,
4450                         E.stringof
4451                     )
4452                 );
4453             }
4454 
4455             static if (mustInitialize) if (initialized == false)
4456             {
4457                 import core.internal.lifetime : emplaceRef;
4458                 foreach (i, f; binfuns)
4459                     emplaceRef!(Args[i])(args[i], e);
4460                 initialized = true;
4461                 continue;
4462             }
4463 
4464             foreach (i, f; binfuns)
4465                 args[i] = f(args[i], e);
4466         }
4467         static if (mustInitialize)
4468         // no need to throw if range is statically known to be non-empty
4469         static if (!__traits(compiles,
4470         {
4471             static assert(r.length > 0);
4472         }))
4473         {
4474             if (!initialized)
4475                 throw new Exception("Cannot reduce an empty iterable w/o an explicit seed value.");
4476         }
4477 
4478         static if (Args.length == 1)
4479             return args[0];
4480         else
4481             return tuple(args);
4482     }
4483 }
4484 
4485 /**
4486 Many aggregate range operations turn out to be solved with `reduce`
4487 quickly and easily. The example below illustrates `reduce`'s
4488 remarkable power and flexibility.
4489 */
4490 @safe unittest
4491 {
4492     import std.algorithm.comparison : max, min;
4493     import std.math.operations : isClose;
4494     import std.range;
4495 
4496     int[] arr = [ 1, 2, 3, 4, 5 ];
4497     // Sum all elements
4498     auto sum = reduce!((a,b) => a + b)(0, arr);
4499     assert(sum == 15);
4500 
4501     // Sum again, using a string predicate with "a" and "b"
4502     sum = reduce!"a + b"(0, arr);
4503     assert(sum == 15);
4504 
4505     // Compute the maximum of all elements
4506     auto largest = reduce!(max)(arr);
4507     assert(largest == 5);
4508 
4509     // Max again, but with Uniform Function Call Syntax (UFCS)
4510     largest = arr.reduce!(max);
4511     assert(largest == 5);
4512 
4513     // Compute the number of odd elements
4514     auto odds = reduce!((a,b) => a + (b & 1))(0, arr);
4515     assert(odds == 3);
4516 
4517     // Compute the sum of squares
4518     auto ssquares = reduce!((a,b) => a + b * b)(0, arr);
4519     assert(ssquares == 55);
4520 
4521     // Chain multiple ranges into seed
4522     int[] a = [ 3, 4 ];
4523     int[] b = [ 100 ];
4524     auto r = reduce!("a + b")(chain(a, b));
4525     assert(r == 107);
4526 
4527     // Mixing convertible types is fair game, too
4528     double[] c = [ 2.5, 3.0 ];
4529     auto r1 = reduce!("a + b")(chain(a, b, c));
4530     assert(isClose(r1, 112.5));
4531 
4532     // To minimize nesting of parentheses, Uniform Function Call Syntax can be used
4533     auto r2 = chain(a, b, c).reduce!("a + b");
4534     assert(isClose(r2, 112.5));
4535 }
4536 
4537 /**
4538 Sometimes it is very useful to compute multiple aggregates in one pass.
4539 One advantage is that the computation is faster because the looping overhead
4540 is shared. That's why `reduce` accepts multiple functions.
4541 If two or more functions are passed, `reduce` returns a
4542 $(REF Tuple, std,typecons) object with one member per passed-in function.
4543 The number of seeds must be correspondingly increased.
4544 */
4545 @safe unittest
4546 {
4547     import std.algorithm.comparison : max, min;
4548     import std.math.operations : isClose;
4549     import std.math.algebraic : sqrt;
4550     import std.typecons : tuple, Tuple;
4551 
4552     double[] a = [ 3.0, 4, 7, 11, 3, 2, 5 ];
4553     // Compute minimum and maximum in one pass
4554     auto r = reduce!(min, max)(a);
4555     // The type of r is Tuple!(int, int)
4556     assert(isClose(r[0], 2));  // minimum
4557     assert(isClose(r[1], 11)); // maximum
4558 
4559     // Compute sum and sum of squares in one pass
4560     r = reduce!("a + b", "a + b * b")(tuple(0.0, 0.0), a);
4561     assert(isClose(r[0], 35));  // sum
4562     assert(isClose(r[1], 233)); // sum of squares
4563     // Compute average and standard deviation from the above
4564     auto avg = r[0] / a.length;
4565     assert(avg == 5);
4566     auto stdev = sqrt(r[1] / a.length - avg * avg);
4567     assert(cast(int) stdev == 2);
4568 }
4569 
4570 @safe unittest
4571 {
4572     import std.algorithm.comparison : max, min;
4573     import std.range : chain;
4574     import std.typecons : tuple, Tuple;
4575 
4576     double[] a = [ 3, 4 ];
4577     auto r = reduce!("a + b")(0.0, a);
4578     assert(r == 7);
4579     r = reduce!("a + b")(a);
4580     assert(r == 7);
4581     r = reduce!(min)(a);
4582     assert(r == 3);
4583     double[] b = [ 100 ];
4584     auto r1 = reduce!("a + b")(chain(a, b));
4585     assert(r1 == 107);
4586 
4587     // two funs
4588     auto r2 = reduce!("a + b", "a - b")(tuple(0.0, 0.0), a);
4589     assert(r2[0] == 7 && r2[1] == -7);
4590     auto r3 = reduce!("a + b", "a - b")(a);
4591     assert(r3[0] == 7 && r3[1] == -1);
4592 
4593     a = [ 1, 2, 3, 4, 5 ];
4594     // Stringize with commas
4595     string rep = reduce!("a ~ `, ` ~ to!(string)(b)")("", a);
4596     assert(rep[2 .. $] == "1, 2, 3, 4, 5", "["~rep[2 .. $]~"]");
4597 }
4598 
4599 @safe unittest
4600 {
4601     import std.algorithm.comparison : max, min;
4602     import std.exception : assertThrown;
4603     import std.range : iota;
4604     import std.typecons : tuple, Tuple;
4605 
4606     // Test the opApply case.
4607     static struct OpApply
4608     {
4609         bool actEmpty;
4610 
4611         int opApply(scope int delegate(ref int) @safe dg)
4612         {
4613             int res;
4614             if (actEmpty) return res;
4615 
4616             foreach (i; 0 .. 100)
4617             {
4618                 res = dg(i);
4619                 if (res) break;
4620             }
4621             return res;
4622         }
4623     }
4624 
4625     OpApply oa;
4626     auto hundredSum = reduce!"a + b"(iota(100));
4627     assert(reduce!"a + b"(5, oa) == hundredSum + 5);
4628     assert(reduce!"a + b"(oa) == hundredSum);
4629     assert(reduce!("a + b", max)(oa) == tuple(hundredSum, 99));
4630     assert(reduce!("a + b", max)(tuple(5, 0), oa) == tuple(hundredSum + 5, 99));
4631 
4632     // Test for throwing on empty range plus no seed.
4633     assertThrown(reduce!"a + b"([1, 2][0 .. 0]));
4634 
4635     oa.actEmpty = true;
4636     assertThrown(reduce!"a + b"(oa));
4637 }
4638 
4639 @safe unittest
4640 {
4641     const float a = 0.0;
4642     const float[] b = [ 1.2, 3, 3.3 ];
4643     float[] c = [ 1.2, 3, 3.3 ];
4644     auto r = reduce!"a + b"(a, b);
4645     r = reduce!"a + b"(a, c);
4646     assert(r == 7.5);
4647 }
4648 
4649 @safe unittest
4650 {
4651     // https://issues.dlang.org/show_bug.cgi?id=10408
4652     // Two-function reduce of a const array.
4653     import std.algorithm.comparison : max, min;
4654     import std.typecons : tuple, Tuple;
4655 
4656     const numbers = [10, 30, 20];
4657     immutable m = reduce!(min)(numbers);
4658     assert(m == 10);
4659     immutable minmax = reduce!(min, max)(numbers);
4660     assert(minmax == tuple(10, 30));
4661 }
4662 
4663 @safe unittest
4664 {
4665     // https://issues.dlang.org/show_bug.cgi?id=10709
4666     import std.typecons : tuple, Tuple;
4667 
4668     enum foo = "a + 0.5 * b";
4669     auto r = [0, 1, 2, 3];
4670     auto r1 = reduce!foo(r);
4671     auto r2 = reduce!(foo, foo)(r);
4672     assert(r1 == 3);
4673     assert(r2 == tuple(3, 3));
4674 }
4675 
4676 @safe unittest
4677 {
4678     static struct OpApply
4679     {
4680         int opApply(int delegate(ref int) @safe dg)
4681         {
4682             int[] a = [1, 2, 3];
4683 
4684             int res = 0;
4685             foreach (ref e; a)
4686             {
4687                 res = dg(e);
4688                 if (res) break;
4689             }
4690             return res;
4691         }
4692     }
4693     //test CTFE and functions with context
4694     int fun(int a, int b) @safe {return a + b + 1;}
4695     auto foo()
4696     {
4697         import std.algorithm.comparison : max;
4698         import std.typecons : tuple, Tuple;
4699 
4700         auto a = reduce!(fun)([1, 2, 3]);
4701         auto b = reduce!(fun, fun)([1, 2, 3]);
4702         auto c = reduce!(fun)(0, [1, 2, 3]);
4703         auto d = reduce!(fun, fun)(tuple(0, 0), [1, 2, 3]);
4704         auto e = reduce!(fun)(0, OpApply());
4705         auto f = reduce!(fun, fun)(tuple(0, 0), OpApply());
4706 
4707         return max(a, b.expand, c, d.expand, e, f.expand);
4708     }
4709     auto a = foo();
4710     assert(a == 9);
4711     enum b = foo();
4712     assert(b == 9);
4713 }
4714 
4715 @safe unittest
4716 {
4717     import std.algorithm.comparison : max, min;
4718     import std.typecons : tuple, Tuple;
4719 
4720     //http://forum.dlang.org/post/oghtttkopzjshsuflelk@forum.dlang.org
4721     //Seed is tuple of const.
4722     static auto minmaxElement(alias F = min, alias G = max, R)(in R range)
4723     @safe pure nothrow
4724     if (isInputRange!R)
4725     {
4726         return reduce!(F, G)(tuple(ElementType!R.max,
4727                                    ElementType!R.min), range);
4728     }
4729     assert(minmaxElement([1, 2, 3]) == tuple(1, 3));
4730 }
4731 
4732 // https://issues.dlang.org/show_bug.cgi?id=12569
4733 @safe unittest
4734 {
4735     import std.algorithm.comparison : max, min;
4736     import std.typecons : tuple;
4737     dchar c = 'a';
4738     reduce!(min, max)(tuple(c, c), "hello"); // OK
4739     static assert(!is(typeof(reduce!(min, max)(tuple(c), "hello"))));
4740     static assert(!is(typeof(reduce!(min, max)(tuple(c, c, c), "hello"))));
4741 
4742 
4743     //"Seed dchar should be a Tuple"
4744     static assert(!is(typeof(reduce!(min, max)(c, "hello"))));
4745     //"Seed (dchar) does not have the correct amount of fields (should be 2)"
4746     static assert(!is(typeof(reduce!(min, max)(tuple(c), "hello"))));
4747     //"Seed (dchar, dchar, dchar) does not have the correct amount of fields (should be 2)"
4748     static assert(!is(typeof(reduce!(min, max)(tuple(c, c, c), "hello"))));
4749     //"Incompatible function/seed/element: all(alias pred = "a")/int/dchar"
4750     static assert(!is(typeof(reduce!all(1, "hello"))));
4751     static assert(!is(typeof(reduce!(all, all)(tuple(1, 1), "hello"))));
4752 }
4753 
4754 // https://issues.dlang.org/show_bug.cgi?id=13304
4755 @safe unittest
4756 {
4757     int[] data;
4758     static assert(is(typeof(reduce!((a, b) => a + b)(data))));
4759     assert(data.length == 0);
4760 }
4761 
4762 // https://issues.dlang.org/show_bug.cgi?id=13880
4763 // reduce shouldn't throw if the length is statically known
4764 pure nothrow @safe @nogc unittest
4765 {
4766     import std.algorithm.comparison : min;
4767     int[5] arr;
4768     arr[2] = -1;
4769     assert(arr.reduce!min == -1);
4770 
4771     int[0] arr0;
4772     assert(reduce!min(42, arr0) == 42);
4773 }
4774 
4775 //Helper for Reduce
4776 private template ReduceSeedType(E)
4777 {
4778     static template ReduceSeedType(alias fun)
4779     {
4780         import std.algorithm.internal : algoFormat;
4781 
4782         alias ReduceSeedType = Unqual!(typeof(fun(lvalueOf!E, lvalueOf!E)));
4783 
4784         //Check the Seed type is useable.
4785         ReduceSeedType s = ReduceSeedType.init;
4786         static assert(is(typeof({ReduceSeedType s = lvalueOf!E;})) &&
4787             is(typeof(lvalueOf!ReduceSeedType = fun(lvalueOf!ReduceSeedType, lvalueOf!E))),
4788             algoFormat(
4789                 "Unable to deduce an acceptable seed type for %s with element type %s.",
4790                 fullyQualifiedName!fun,
4791                 E.stringof
4792             )
4793         );
4794     }
4795 }
4796 
4797 
4798 /++
4799 Implements the homonym function (also known as `accumulate`, $(D
4800 compress), `inject`, or `foldl`) present in various programming
4801 languages of functional flavor, iteratively calling one or more predicates.
4802 
4803 $(P Each predicate in `fun` must take two arguments:)
4804 * An accumulator value
4805 * An element of the range `r`
4806 $(P Each predicate must return a value which implicitly converts to the
4807 type of the accumulator.)
4808 
4809 $(P For a single predicate,
4810 the call `fold!(fun)(range, seed)` will:)
4811 
4812 * Use `seed` to initialize an internal variable `result` (also called
4813   the accumulator).
4814 * For each element `e` in $(D range), evaluate `result = fun(result, e)`.
4815 * Return $(D result).
4816 
4817 $(P The one-argument version `fold!(fun)(range)`
4818 works similarly, but it uses the first element of the range as the
4819 seed (the range must be non-empty) and iterates over the remaining
4820 elements.)
4821 
4822 Multiple results are produced when using multiple predicates.
4823 
4824 Params:
4825     fun = the predicate function(s) to apply to the elements
4826 
4827 See_Also:
4828     * $(HTTP en.wikipedia.org/wiki/Fold_(higher-order_function), Fold (higher-order function))
4829 
4830     * $(LREF sum) is similar to `fold!((a, b) => a + b)` that offers
4831       precise summing of floating point numbers.
4832 
4833     * `fold` is functionally equivalent to $(LREF reduce) with the argument order
4834       reversed, and without the need to use $(REF_ALTTEXT `tuple`,tuple,std,typecons)
4835       for multiple seeds.
4836 +/
4837 template fold(fun...)
4838 if (fun.length >= 1)
4839 {
4840     /**
4841     Params:
4842         r = the $(REF_ALTTEXT input range, isInputRange, std,range,primitives) to fold
4843         seeds = the initial values of each accumulator (optional), one for each predicate
4844     Returns:
4845         Either the accumulated result for a single predicate, or a
4846         $(REF_ALTTEXT `Tuple`,Tuple,std,typecons) of results.
4847      */
4848     auto fold(R, S...)(R r, S seeds)
4849     {
4850         static if (S.length < 2)
4851         {
4852             return reduce!fun(seeds, r);
4853         }
4854         else
4855         {
4856             import std.typecons : tuple;
4857             return reduce!fun(tuple(seeds), r);
4858         }
4859     }
4860 }
4861 
4862 ///
4863 @safe pure unittest
4864 {
4865     immutable arr = [1, 2, 3, 4, 5];
4866 
4867     // Sum all elements
4868     assert(arr.fold!((a, e) => a + e) == 15);
4869 
4870     // Sum all elements with explicit seed
4871     assert(arr.fold!((a, e) => a + e)(6) == 21);
4872 
4873     import std.algorithm.comparison : min, max;
4874     import std.typecons : tuple;
4875 
4876     // Compute minimum and maximum at the same time
4877     assert(arr.fold!(min, max) == tuple(1, 5));
4878 
4879     // Compute minimum and maximum at the same time with seeds
4880     assert(arr.fold!(min, max)(0, 7) == tuple(0, 7));
4881 
4882     // Can be used in a UFCS chain
4883     assert(arr.map!(a => a + 1).fold!((a, e) => a + e) == 20);
4884 
4885     // Return the last element of any range
4886     assert(arr.fold!((a, e) => e) == 5);
4887 }
4888 
4889 @safe @nogc pure nothrow unittest
4890 {
4891     int[1] arr;
4892     static assert(!is(typeof(arr.fold!())));
4893     static assert(!is(typeof(arr.fold!(a => a))));
4894     static assert(is(typeof(arr.fold!((a, b) => a))));
4895     static assert(is(typeof(arr.fold!((a, b) => a)(1))));
4896     assert(arr.length == 1);
4897 }
4898 
4899 /++
4900 Similar to `fold`, but returns a range containing the successive reduced values.
4901 The call `cumulativeFold!(fun)(range, seed)` first assigns `seed` to an
4902 internal variable `result`, also called the accumulator.
4903 The returned range contains the values `result = fun(result, x)` lazily
4904 evaluated for each element `x` in `range`. Finally, the last element has the
4905 same value as `fold!(fun)(seed, range)`.
4906 The one-argument version `cumulativeFold!(fun)(range)` works similarly, but
4907 it returns the first element unchanged and uses it as seed for the next
4908 elements.
4909 This function is also known as
4910     $(HTTP en.cppreference.com/w/cpp/algorithm/partial_sum, partial_sum),
4911     $(HTTP docs.python.org/3/library/itertools.html#itertools.accumulate, accumulate),
4912     $(HTTP hackage.haskell.org/package/base-4.8.2.0/docs/Prelude.html#v:scanl, scan),
4913     $(HTTP mathworld.wolfram.com/CumulativeSum.html, Cumulative Sum).
4914 
4915 Params:
4916     fun = one or more functions to use as fold operation
4917 
4918 Returns:
4919     The function returns a range containing the consecutive reduced values. If
4920     there is more than one `fun`, the element type will be $(REF Tuple,
4921     std,typecons) containing one element for each `fun`.
4922 
4923 See_Also:
4924     $(HTTP en.wikipedia.org/wiki/Prefix_sum, Prefix Sum)
4925 
4926 Note:
4927 
4928     In functional programming languages this is typically called `scan`, `scanl`,
4929     `scanLeft` or `reductions`.
4930 +/
4931 template cumulativeFold(fun...)
4932 if (fun.length >= 1)
4933 {
4934     import std.meta : staticMap;
4935     private alias binfuns = staticMap!(binaryFun, fun);
4936 
4937     /++
4938     No-seed version. The first element of `r` is used as the seed's value.
4939     For each function `f` in `fun`, the corresponding seed type `S` is
4940     `Unqual!(typeof(f(e, e)))`, where `e` is an element of `r`:
4941     `ElementType!R`.
4942     Once `S` has been determined, then `S s = e;` and `s = f(s, e);` must
4943     both be legal.
4944 
4945     Params:
4946         range = An $(REF_ALTTEXT input range, isInputRange, std,range,primitives)
4947     Returns:
4948         a range containing the consecutive reduced values.
4949     +/
4950     auto cumulativeFold(R)(R range)
4951     if (isInputRange!(Unqual!R))
4952     {
4953         return cumulativeFoldImpl(range);
4954     }
4955 
4956     /++
4957     Seed version. The seed should be a single value if `fun` is a single
4958     function. If `fun` is multiple functions, then `seed` should be a
4959     $(REF Tuple, std,typecons), with one field per function in `f`.
4960     For convenience, if the seed is `const`, or has qualified fields, then
4961     `cumulativeFold` will operate on an unqualified copy. If this happens
4962     then the returned type will not perfectly match `S`.
4963 
4964     Params:
4965         range = An $(REF_ALTTEXT input range, isInputRange, std,range,primitives)
4966         seed = the initial value of the accumulator
4967     Returns:
4968         a range containing the consecutive reduced values.
4969     +/
4970     auto cumulativeFold(R, S)(R range, S seed)
4971     if (isInputRange!(Unqual!R))
4972     {
4973         static if (fun.length == 1)
4974             return cumulativeFoldImpl(range, seed);
4975         else
4976             return cumulativeFoldImpl(range, seed.expand);
4977     }
4978 
4979     private auto cumulativeFoldImpl(R, Args...)(R range, ref Args args)
4980     {
4981         import std.algorithm.internal : algoFormat;
4982 
4983         static assert(Args.length == 0 || Args.length == fun.length,
4984             algoFormat("Seed %s does not have the correct amount of fields (should be %s)",
4985                 Args.stringof, fun.length));
4986 
4987         static if (args.length)
4988             alias State = staticMap!(Unqual, Args);
4989         else
4990             alias State = staticMap!(ReduceSeedType!(ElementType!R), binfuns);
4991 
4992         foreach (i, f; binfuns)
4993         {
4994             static assert(!__traits(compiles, f(args[i], e)) || __traits(compiles,
4995                     { args[i] = f(args[i], e); }()),
4996                 algoFormat("Incompatible function/seed/element: %s/%s/%s",
4997                     fullyQualifiedName!f, Args[i].stringof, E.stringof));
4998         }
4999 
5000         static struct Result
5001         {
5002         private:
5003             R source;
5004             State state;
5005 
5006             this(R range, ref Args args)
5007             {
5008                 source = range;
5009                 if (source.empty)
5010                     return;
5011 
5012                 foreach (i, f; binfuns)
5013                 {
5014                     static if (args.length)
5015                         state[i] = f(args[i], source.front);
5016                     else
5017                         state[i] = source.front;
5018                 }
5019             }
5020 
5021         public:
5022             @property bool empty()
5023             {
5024                 return source.empty;
5025             }
5026 
5027             @property auto front()
5028             {
5029                 assert(!empty, "Attempting to fetch the front of an empty cumulativeFold.");
5030                 static if (fun.length > 1)
5031                 {
5032                     import std.typecons : tuple;
5033                     return tuple(state);
5034                 }
5035                 else
5036                 {
5037                     return state[0];
5038                 }
5039             }
5040 
5041             void popFront()
5042             {
5043                 assert(!empty, "Attempting to popFront an empty cumulativeFold.");
5044                 source.popFront;
5045 
5046                 if (source.empty)
5047                     return;
5048 
5049                 foreach (i, f; binfuns)
5050                     state[i] = f(state[i], source.front);
5051             }
5052 
5053             static if (isForwardRange!R)
5054             {
5055                 @property auto save()
5056                 {
5057                     auto result = this;
5058                     result.source = source.save;
5059                     return result;
5060                 }
5061             }
5062 
5063             mixin ImplementLength!source;
5064         }
5065 
5066         return Result(range, args);
5067     }
5068 }
5069 
5070 ///
5071 @safe unittest
5072 {
5073     import std.algorithm.comparison : max, min;
5074     import std.array : array;
5075     import std.math.operations : isClose;
5076     import std.range : chain;
5077 
5078     int[] arr = [1, 2, 3, 4, 5];
5079     // Partial sum of all elements
5080     auto sum = cumulativeFold!((a, b) => a + b)(arr, 0);
5081     assert(sum.array == [1, 3, 6, 10, 15]);
5082 
5083     // Partial sum again, using a string predicate with "a" and "b"
5084     auto sum2 = cumulativeFold!"a + b"(arr, 0);
5085     assert(sum2.array == [1, 3, 6, 10, 15]);
5086 
5087     // Compute the partial maximum of all elements
5088     auto largest = cumulativeFold!max(arr);
5089     assert(largest.array == [1, 2, 3, 4, 5]);
5090 
5091     // Partial max again, but with Uniform Function Call Syntax (UFCS)
5092     largest = arr.cumulativeFold!max;
5093     assert(largest.array == [1, 2, 3, 4, 5]);
5094 
5095     // Partial count of odd elements
5096     auto odds = arr.cumulativeFold!((a, b) => a + (b & 1))(0);
5097     assert(odds.array == [1, 1, 2, 2, 3]);
5098 
5099     // Compute the partial sum of squares
5100     auto ssquares = arr.cumulativeFold!((a, b) => a + b * b)(0);
5101     assert(ssquares.array == [1, 5, 14, 30, 55]);
5102 
5103     // Chain multiple ranges into seed
5104     int[] a = [3, 4];
5105     int[] b = [100];
5106     auto r = cumulativeFold!"a + b"(chain(a, b));
5107     assert(r.array == [3, 7, 107]);
5108 
5109     // Mixing convertible types is fair game, too
5110     double[] c = [2.5, 3.0];
5111     auto r1 = cumulativeFold!"a + b"(chain(a, b, c));
5112     assert(isClose(r1, [3, 7, 107, 109.5, 112.5]));
5113 
5114     // To minimize nesting of parentheses, Uniform Function Call Syntax can be used
5115     auto r2 = chain(a, b, c).cumulativeFold!"a + b";
5116     assert(isClose(r2, [3, 7, 107, 109.5, 112.5]));
5117 }
5118 
5119 /**
5120 Sometimes it is very useful to compute multiple aggregates in one pass.
5121 One advantage is that the computation is faster because the looping overhead
5122 is shared. That's why `cumulativeFold` accepts multiple functions.
5123 If two or more functions are passed, `cumulativeFold` returns a $(REF Tuple,
5124 std,typecons) object with one member per passed-in function.
5125 The number of seeds must be correspondingly increased.
5126 */
5127 @safe unittest
5128 {
5129     import std.algorithm.comparison : max, min;
5130     import std.algorithm.iteration : map;
5131     import std.math.operations : isClose;
5132     import std.typecons : tuple;
5133 
5134     double[] a = [3.0, 4, 7, 11, 3, 2, 5];
5135     // Compute minimum and maximum in one pass
5136     auto r = a.cumulativeFold!(min, max);
5137     // The type of r is Tuple!(int, int)
5138     assert(isClose(r.map!"a[0]", [3, 3, 3, 3, 3, 2, 2]));     // minimum
5139     assert(isClose(r.map!"a[1]", [3, 4, 7, 11, 11, 11, 11])); // maximum
5140 
5141     // Compute sum and sum of squares in one pass
5142     auto r2 = a.cumulativeFold!("a + b", "a + b * b")(tuple(0.0, 0.0));
5143     assert(isClose(r2.map!"a[0]", [3, 7, 14, 25, 28, 30, 35]));      // sum
5144     assert(isClose(r2.map!"a[1]", [9, 25, 74, 195, 204, 208, 233])); // sum of squares
5145 }
5146 
5147 @safe unittest
5148 {
5149     import std.algorithm.comparison : equal, max, min;
5150     import std.conv : to;
5151     import std.range : chain;
5152     import std.typecons : tuple;
5153 
5154     double[] a = [3, 4];
5155     auto r = a.cumulativeFold!("a + b")(0.0);
5156     assert(r.equal([3, 7]));
5157     auto r2 = cumulativeFold!("a + b")(a);
5158     assert(r2.equal([3, 7]));
5159     auto r3 = cumulativeFold!(min)(a);
5160     assert(r3.equal([3, 3]));
5161     double[] b = [100];
5162     auto r4 = cumulativeFold!("a + b")(chain(a, b));
5163     assert(r4.equal([3, 7, 107]));
5164 
5165     // two funs
5166     auto r5 = cumulativeFold!("a + b", "a - b")(a, tuple(0.0, 0.0));
5167     assert(r5.equal([tuple(3, -3), tuple(7, -7)]));
5168     auto r6 = cumulativeFold!("a + b", "a - b")(a);
5169     assert(r6.equal([tuple(3, 3), tuple(7, -1)]));
5170 
5171     a = [1, 2, 3, 4, 5];
5172     // Stringize with commas
5173     auto rep = cumulativeFold!("a ~ `, ` ~ to!string(b)")(a, "");
5174     assert(rep.map!"a[2 .. $]".equal(["1", "1, 2", "1, 2, 3", "1, 2, 3, 4", "1, 2, 3, 4, 5"]));
5175 
5176     // Test for empty range
5177     a = [];
5178     assert(a.cumulativeFold!"a + b".empty);
5179     assert(a.cumulativeFold!"a + b"(2.0).empty);
5180 }
5181 
5182 @safe unittest
5183 {
5184     import std.algorithm.comparison : max, min;
5185     import std.array : array;
5186     import std.math.operations : isClose;
5187     import std.typecons : tuple;
5188 
5189     const float a = 0.0;
5190     const float[] b = [1.2, 3, 3.3];
5191     float[] c = [1.2, 3, 3.3];
5192 
5193     auto r = cumulativeFold!"a + b"(b, a);
5194     assert(isClose(r, [1.2, 4.2, 7.5]));
5195 
5196     auto r2 = cumulativeFold!"a + b"(c, a);
5197     assert(isClose(r2, [1.2, 4.2, 7.5]));
5198 
5199     const numbers = [10, 30, 20];
5200     enum m = numbers.cumulativeFold!(min).array;
5201     assert(m == [10, 10, 10]);
5202     enum minmax = numbers.cumulativeFold!(min, max).array;
5203     assert(minmax == [tuple(10, 10), tuple(10, 30), tuple(10, 30)]);
5204 }
5205 
5206 @safe unittest
5207 {
5208     import std.math.operations : isClose;
5209     import std.typecons : tuple;
5210 
5211     enum foo = "a + 0.5 * b";
5212     auto r = [0, 1, 2, 3];
5213     auto r1 = r.cumulativeFold!foo;
5214     auto r2 = r.cumulativeFold!(foo, foo);
5215     assert(isClose(r1, [0, 0.5, 1.5, 3]));
5216     assert(isClose(r2.map!"a[0]", [0, 0.5, 1.5, 3]));
5217     assert(isClose(r2.map!"a[1]", [0, 0.5, 1.5, 3]));
5218 }
5219 
5220 @safe unittest
5221 {
5222     import std.algorithm.comparison : equal, max, min;
5223     import std.array : array;
5224     import std.typecons : tuple;
5225 
5226     //Seed is tuple of const.
5227     static auto minmaxElement(alias F = min, alias G = max, R)(in R range)
5228     @safe pure nothrow
5229     if (isInputRange!R)
5230     {
5231         return range.cumulativeFold!(F, G)(tuple(ElementType!R.max, ElementType!R.min));
5232     }
5233 
5234     assert(minmaxElement([1, 2, 3]).equal([tuple(1, 1), tuple(1, 2), tuple(1, 3)]));
5235 }
5236 
5237 // https://issues.dlang.org/show_bug.cgi?id=12569
5238 @safe unittest
5239 {
5240     import std.algorithm.comparison : equal, max, min;
5241     import std.typecons : tuple;
5242 
5243     dchar c = 'a';
5244 
5245     assert(cumulativeFold!(min, max)("hello", tuple(c, c)).equal([tuple('a', 'h'),
5246         tuple('a', 'h'), tuple('a', 'l'), tuple('a', 'l'), tuple('a', 'o')]));
5247     static assert(!__traits(compiles, cumulativeFold!(min, max)("hello", tuple(c))));
5248     static assert(!__traits(compiles, cumulativeFold!(min, max)("hello", tuple(c, c, c))));
5249 
5250     //"Seed dchar should be a Tuple"
5251     static assert(!__traits(compiles, cumulativeFold!(min, max)("hello", c)));
5252     //"Seed (dchar) does not have the correct amount of fields (should be 2)"
5253     static assert(!__traits(compiles, cumulativeFold!(min, max)("hello", tuple(c))));
5254     //"Seed (dchar, dchar, dchar) does not have the correct amount of fields (should be 2)"
5255     static assert(!__traits(compiles, cumulativeFold!(min, max)("hello", tuple(c, c, c))));
5256     //"Incompatible function/seed/element: all(alias pred = "a")/int/dchar"
5257     static assert(!__traits(compiles, cumulativeFold!all("hello", 1)));
5258     static assert(!__traits(compiles, cumulativeFold!(all, all)("hello", tuple(1, 1))));
5259 }
5260 
5261 // https://issues.dlang.org/show_bug.cgi?id=13304
5262 @safe unittest
5263 {
5264     int[] data;
5265     assert(data.cumulativeFold!((a, b) => a + b).empty);
5266 }
5267 
5268 @safe unittest
5269 {
5270     import std.algorithm.comparison : equal;
5271     import std.internal.test.dummyrange : AllDummyRanges, propagatesLength,
5272         propagatesRangeType, RangeType;
5273 
5274     foreach (DummyType; AllDummyRanges)
5275     {
5276         DummyType d;
5277         auto m = d.cumulativeFold!"a * b";
5278 
5279         static assert(propagatesLength!(typeof(m), DummyType));
5280         static if (DummyType.rt <= RangeType.Forward)
5281             static assert(propagatesRangeType!(typeof(m), DummyType));
5282 
5283         assert(m.equal([1, 2, 6, 24, 120, 720, 5040, 40_320, 362_880, 3_628_800]));
5284     }
5285 }
5286 
5287 // splitter
5288 /**
5289 Lazily splits a range using an element or range as a separator.
5290 Separator ranges can be any narrow string type or sliceable range type.
5291 
5292 Two adjacent separators are considered to surround an empty element in
5293 the split range. Use `filter!(a => !a.empty)` on the result to compress
5294 empty elements.
5295 
5296 The predicate is passed to $(REF binaryFun, std,functional) and accepts
5297 any callable function that can be executed via `pred(element, s)`.
5298 
5299 Notes:
5300     If splitting a string on whitespace and token compression is desired,
5301     consider using `splitter` without specifying a separator.
5302 
5303     If no separator is passed, the $(REF_ALTTEXT, unary, unaryFun, std,functional)
5304     predicate `isTerminator` decides whether to accept an element of `r`.
5305 
5306 Params:
5307     pred = The predicate for comparing each element with the separator,
5308         defaulting to `"a == b"`.
5309     r = The $(REF_ALTTEXT input range, isInputRange, std,range,primitives) to be
5310         split. Must support slicing and `.length` or be a narrow string type.
5311     s = The element (or range) to be treated as the separator
5312         between range segments to be split.
5313     isTerminator = The predicate for deciding where to split the range when no separator is passed
5314     keepSeparators = The flag for deciding if the separators are kept
5315 
5316 Constraints:
5317     The predicate `pred` needs to accept an element of `r` and the
5318     separator `s`.
5319 
5320 Returns:
5321     An input range of the subranges of elements between separators. If `r`
5322     is a $(REF_ALTTEXT forward range, isForwardRange, std,range,primitives)
5323     or $(REF_ALTTEXT bidirectional range, isBidirectionalRange, std,range,primitives),
5324     the returned range will be likewise.
5325     When a range is used a separator, bidirectionality isn't possible.
5326 
5327     If keepSeparators is equal to Yes.keepSeparators the output will also contain the
5328     separators.
5329 
5330     If an empty range is given, the result is an empty range. If a range with
5331     one separator is given, the result is a range with two empty elements.
5332 
5333 See_Also:
5334  $(REF _splitter, std,regex) for a version that splits using a regular expression defined separator,
5335  $(REF _split, std,array) for a version that splits eagerly and
5336  $(LREF splitWhen), which compares adjacent elements instead of element against separator.
5337 */
5338 auto splitter(alias pred = "a == b",
5339               Flag!"keepSeparators" keepSeparators = No.keepSeparators,
5340               Range,
5341               Separator)(Range r, Separator s)
5342 if (is(typeof(binaryFun!pred(r.front, s)) : bool)
5343         && ((hasSlicing!Range && hasLength!Range) || isNarrowString!Range))
5344 {
5345     import std.algorithm.searching : find;
5346     import std.conv : unsigned;
5347 
5348     struct Result
5349     {
5350     private:
5351         Range _input;
5352         Separator _separator;
5353         // Do we need hasLength!Range? popFront uses _input.length...
5354         enum size_t _unComputed = size_t.max - 1, _atEnd = size_t.max;
5355         size_t _frontLength = _unComputed;
5356         size_t _backLength = _unComputed;
5357 
5358         static if (isNarrowString!Range)
5359         {
5360             size_t _separatorLength;
5361         }
5362         else
5363         {
5364             enum _separatorLength = 1;
5365         }
5366 
5367         static if (keepSeparators)
5368         {
5369             bool _wasSeparator = true;
5370         }
5371 
5372         static if (isBidirectionalRange!Range)
5373         {
5374             size_t lastIndexOf(Range haystack, Separator needle)
5375             {
5376                 import std.range : retro;
5377                 auto r = haystack.retro().find!pred(needle);
5378                 return r.retro().length - 1;
5379             }
5380         }
5381 
5382     public:
5383         this(Range input, Separator separator)
5384         {
5385             _input = input;
5386             _separator = separator;
5387 
5388             static if (isNarrowString!Range)
5389             {
5390                 import std.utf : codeLength;
5391 
5392                 _separatorLength = codeLength!(ElementEncodingType!Range)(separator);
5393             }
5394             if (_input.empty)
5395                 _frontLength = _atEnd;
5396         }
5397 
5398         static if (isInfinite!Range)
5399         {
5400             enum bool empty = false;
5401         }
5402         else
5403         {
5404             @property bool empty()
5405             {
5406                 return _frontLength == _atEnd;
5407             }
5408         }
5409 
5410         @property Range front()
5411         {
5412             assert(!empty, "Attempting to fetch the front of an empty splitter.");
5413             static if (keepSeparators)
5414             {
5415                 if (!_wasSeparator)
5416                 {
5417                     _frontLength = _separatorLength;
5418                     _wasSeparator = true;
5419                 }
5420                 else if (_frontLength == _unComputed)
5421                 {
5422                     auto r = _input.find!pred(_separator);
5423                     _frontLength = _input.length - r.length;
5424                     _wasSeparator = false;
5425                 }
5426             }
5427             else
5428             {
5429                 if (_frontLength == _unComputed)
5430                 {
5431                     auto r = _input.find!pred(_separator);
5432                     _frontLength = _input.length - r.length;
5433                 }
5434             }
5435             return _input[0 .. _frontLength];
5436         }
5437 
5438         void popFront()
5439         {
5440             assert(!empty, "Attempting to popFront an empty splitter.");
5441             if (_frontLength == _unComputed)
5442             {
5443                 front;
5444             }
5445             assert(_frontLength <= _input.length, "The front position must"
5446                     ~ " not exceed the input.length");
5447             static if (keepSeparators)
5448             {
5449                 if (_frontLength == _input.length && !_wasSeparator)
5450                 {
5451                     _frontLength = _atEnd;
5452 
5453                     _backLength = _atEnd;
5454                 }
5455                 else
5456                 {
5457                     _input = _input[_frontLength .. _input.length];
5458                     _frontLength = _unComputed;
5459                 }
5460             }
5461             else
5462             {
5463                 if (_frontLength == _input.length)
5464                 {
5465                     // no more input and need to fetch => done
5466                     _frontLength = _atEnd;
5467 
5468                     // Probably don't need this, but just for consistency:
5469                     _backLength = _atEnd;
5470                 }
5471                 else
5472                 {
5473                     _input = _input[_frontLength + _separatorLength .. _input.length];
5474                     _frontLength = _unComputed;
5475                 }
5476             }
5477         }
5478 
5479         static if (isForwardRange!Range)
5480         {
5481             @property typeof(this) save()
5482             {
5483                 auto ret = this;
5484                 ret._input = _input.save;
5485                 return ret;
5486             }
5487         }
5488 
5489         static if (isBidirectionalRange!Range)
5490         {
5491             @property Range back()
5492             {
5493                 assert(!empty, "Attempting to fetch the back of an empty splitter.");
5494                 static if (keepSeparators)
5495                 {
5496                     if (!_wasSeparator)
5497                     {
5498                         _backLength = _separatorLength;
5499                         _wasSeparator = true;
5500                     }
5501                     else if (_backLength == _unComputed)
5502                     {
5503                         immutable lastIndex = lastIndexOf(_input, _separator);
5504                         if (lastIndex == -1)
5505                         {
5506                             _backLength = _input.length;
5507                         }
5508                         else
5509                         {
5510                             _backLength = _input.length - lastIndex - 1;
5511                         }
5512                         _wasSeparator = false;
5513                     }
5514                 }
5515                 else
5516                 {
5517                     if (_backLength == _unComputed)
5518                     {
5519                         immutable lastIndex = lastIndexOf(_input, _separator);
5520                         if (lastIndex == -1)
5521                         {
5522                             _backLength = _input.length;
5523                         }
5524                         else
5525                         {
5526                             _backLength = _input.length - lastIndex - 1;
5527                         }
5528                     }
5529                 }
5530                 return _input[_input.length - _backLength .. _input.length];
5531             }
5532 
5533             void popBack()
5534             {
5535                 assert(!empty, "Attempting to popBack an empty splitter.");
5536                 if (_backLength == _unComputed)
5537                 {
5538                     // evaluate back to make sure it's computed
5539                     back;
5540                 }
5541                 assert(_backLength <= _input.length, "The end index must not"
5542                         ~ " exceed the length of the input");
5543                 static if (keepSeparators)
5544                 {
5545                     if (_backLength == _input.length && !_wasSeparator)
5546                     {
5547                         _frontLength = _atEnd;
5548                         _backLength = _atEnd;
5549                     }
5550                     else
5551                     {
5552                         _input = _input[0 .. _input.length - _backLength];
5553                         _backLength = _unComputed;
5554                     }
5555                 }
5556                 else
5557                 {
5558                     if (_backLength == _input.length)
5559                     {
5560                         // no more input and need to fetch => done
5561                         _frontLength = _atEnd;
5562                         _backLength = _atEnd;
5563                     }
5564                     else
5565                     {
5566                         _input = _input[0 .. _input.length - _backLength - _separatorLength];
5567                         _backLength = _unComputed;
5568                     }
5569                 }
5570             }
5571         }
5572     }
5573 
5574     return Result(r, s);
5575 }
5576 
5577 /// Basic splitting with characters and numbers.
5578 @safe unittest
5579 {
5580     import std.algorithm.comparison : equal;
5581 
5582     assert("a|bc|def".splitter('|').equal([ "a", "bc", "def" ]));
5583 
5584     int[] a = [1, 0, 2, 3, 0, 4, 5, 6];
5585     int[][] w = [ [1], [2, 3], [4, 5, 6] ];
5586     assert(a.splitter(0).equal(w));
5587 }
5588 
5589 /// Basic splitting with characters and numbers and keeping sentinels.
5590 @safe unittest
5591 {
5592     import std.algorithm.comparison : equal;
5593     import std.typecons : Yes;
5594 
5595     assert("a|bc|def".splitter!("a == b", Yes.keepSeparators)('|')
5596         .equal([ "a", "|", "bc", "|", "def" ]));
5597 
5598     int[] a = [1, 0, 2, 3, 0, 4, 5, 6];
5599     int[][] w = [ [1], [0], [2, 3], [0], [4, 5, 6] ];
5600     assert(a.splitter!("a == b", Yes.keepSeparators)(0).equal(w));
5601 }
5602 
5603 /// Adjacent separators.
5604 @safe unittest
5605 {
5606     import std.algorithm.comparison : equal;
5607 
5608     assert("|ab|".splitter('|').equal([ "", "ab", "" ]));
5609     assert("ab".splitter('|').equal([ "ab" ]));
5610 
5611     assert("a|b||c".splitter('|').equal([ "a", "b", "", "c" ]));
5612     assert("hello  world".splitter(' ').equal([ "hello", "", "world" ]));
5613 
5614     auto a = [ 1, 2, 0, 0, 3, 0, 4, 5, 0 ];
5615     auto w = [ [1, 2], [], [3], [4, 5], [] ];
5616     assert(a.splitter(0).equal(w));
5617 }
5618 
5619 /// Adjacent separators and keeping sentinels.
5620 @safe unittest
5621 {
5622     import std.algorithm.comparison : equal;
5623     import std.typecons : Yes;
5624 
5625     assert("|ab|".splitter!("a == b", Yes.keepSeparators)('|')
5626         .equal([ "", "|", "ab", "|", "" ]));
5627     assert("ab".splitter!("a == b", Yes.keepSeparators)('|')
5628         .equal([ "ab" ]));
5629 
5630     assert("a|b||c".splitter!("a == b", Yes.keepSeparators)('|')
5631         .equal([ "a", "|", "b", "|", "", "|", "c" ]));
5632     assert("hello  world".splitter!("a == b", Yes.keepSeparators)(' ')
5633         .equal([ "hello", " ", "", " ", "world" ]));
5634 
5635     auto a = [ 1, 2, 0, 0, 3, 0, 4, 5, 0 ];
5636     auto w = [ [1, 2], [0], [], [0], [3], [0], [4, 5], [0], [] ];
5637     assert(a.splitter!("a == b", Yes.keepSeparators)(0).equal(w));
5638 }
5639 
5640 /// Empty and separator-only ranges.
5641 @safe unittest
5642 {
5643     import std.algorithm.comparison : equal;
5644     import std.range : empty;
5645 
5646     assert("".splitter('|').empty);
5647     assert("|".splitter('|').equal([ "", "" ]));
5648     assert("||".splitter('|').equal([ "", "", "" ]));
5649 }
5650 
5651 /// Empty and separator-only ranges and keeping sentinels.
5652 @safe unittest
5653 {
5654     import std.algorithm.comparison : equal;
5655     import std.typecons : Yes;
5656     import std.range : empty;
5657 
5658     assert("".splitter!("a == b", Yes.keepSeparators)('|').empty);
5659     assert("|".splitter!("a == b", Yes.keepSeparators)('|')
5660         .equal([ "", "|", "" ]));
5661     assert("||".splitter!("a == b", Yes.keepSeparators)('|')
5662         .equal([ "", "|", "", "|", "" ]));
5663 }
5664 
5665 /// Use a range for splitting
5666 @safe unittest
5667 {
5668     import std.algorithm.comparison : equal;
5669 
5670     assert("a=>bc=>def".splitter("=>").equal([ "a", "bc", "def" ]));
5671     assert("a|b||c".splitter("||").equal([ "a|b", "c" ]));
5672     assert("hello  world".splitter("  ").equal([ "hello", "world" ]));
5673 
5674     int[] a = [ 1, 2, 0, 0, 3, 0, 4, 5, 0 ];
5675     int[][] w = [ [1, 2], [3, 0, 4, 5, 0] ];
5676     assert(a.splitter([0, 0]).equal(w));
5677 
5678     a = [ 0, 0 ];
5679     assert(a.splitter([0, 0]).equal([ (int[]).init, (int[]).init ]));
5680 
5681     a = [ 0, 0, 1 ];
5682     assert(a.splitter([0, 0]).equal([ [], [1] ]));
5683 }
5684 
5685 /// Use a range for splitting
5686 @safe unittest
5687 {
5688     import std.algorithm.comparison : equal;
5689     import std.typecons : Yes;
5690 
5691     assert("a=>bc=>def".splitter!("a == b", Yes.keepSeparators)("=>")
5692         .equal([ "a", "=>", "bc", "=>", "def" ]));
5693     assert("a|b||c".splitter!("a == b", Yes.keepSeparators)("||")
5694         .equal([ "a|b", "||", "c" ]));
5695     assert("hello  world".splitter!("a == b", Yes.keepSeparators)("  ")
5696         .equal([ "hello", "  ",  "world" ]));
5697 
5698     int[] a = [ 1, 2, 0, 0, 3, 0, 4, 5, 0 ];
5699     int[][] w = [ [1, 2], [0, 0], [3, 0, 4, 5, 0] ];
5700     assert(a.splitter!("a == b", Yes.keepSeparators)([0, 0]).equal(w));
5701 
5702     a = [ 0, 0 ];
5703     assert(a.splitter!("a == b", Yes.keepSeparators)([0, 0])
5704         .equal([ (int[]).init, [0, 0], (int[]).init ]));
5705 
5706     a = [ 0, 0, 1 ];
5707     assert(a.splitter!("a == b", Yes.keepSeparators)([0, 0])
5708         .equal([ [], [0, 0], [1] ]));
5709 }
5710 
5711 /// Custom predicate functions.
5712 @safe unittest
5713 {
5714     import std.algorithm.comparison : equal;
5715     import std.ascii : toLower;
5716 
5717     assert("abXcdxef".splitter!"a.toLower == b"('x').equal(
5718                  [ "ab", "cd", "ef" ]));
5719 
5720     auto w = [ [0], [1], [2] ];
5721     assert(w.splitter!"a.front == b"(1).equal([ [[0]], [[2]] ]));
5722 }
5723 
5724 /// Custom predicate functions.
5725 @safe unittest
5726 {
5727     import std.algorithm.comparison : equal;
5728     import std.typecons : Yes;
5729     import std.ascii : toLower;
5730 
5731     assert("abXcdxef".splitter!("a.toLower == b", Yes.keepSeparators)('x')
5732         .equal([ "ab", "X", "cd", "x", "ef" ]));
5733 
5734     auto w = [ [0], [1], [2] ];
5735     assert(w.splitter!("a.front == b", Yes.keepSeparators)(1)
5736         .equal([ [[0]], [[1]], [[2]] ]));
5737 }
5738 
5739 /// Use splitter without a separator
5740 @safe unittest
5741 {
5742     import std.algorithm.comparison : equal;
5743     import std.range.primitives : front;
5744 
5745     assert(equal(splitter!(a => a == '|')("a|bc|def"), [ "a", "bc", "def" ]));
5746     assert(equal(splitter!(a => a == ' ')("hello  world"), [ "hello", "", "world" ]));
5747 
5748     int[] a = [ 1, 2, 0, 0, 3, 0, 4, 5, 0 ];
5749     int[][] w = [ [1, 2], [], [3], [4, 5], [] ];
5750     assert(equal(splitter!(a => a == 0)(a), w));
5751 
5752     a = [ 0 ];
5753     assert(equal(splitter!(a => a == 0)(a), [ (int[]).init, (int[]).init ]));
5754 
5755     a = [ 0, 1 ];
5756     assert(equal(splitter!(a => a == 0)(a), [ [], [1] ]));
5757 
5758     w = [ [0], [1], [2] ];
5759     assert(equal(splitter!(a => a.front == 1)(w), [ [[0]], [[2]] ]));
5760 }
5761 
5762 /// Leading separators, trailing separators, or no separators.
5763 @safe unittest
5764 {
5765     import std.algorithm.comparison : equal;
5766 
5767     assert("|ab|".splitter('|').equal([ "", "ab", "" ]));
5768     assert("ab".splitter('|').equal([ "ab" ]));
5769 }
5770 
5771 /// Leading separators, trailing separators, or no separators.
5772 @safe unittest
5773 {
5774     import std.algorithm.comparison : equal;
5775     import std.typecons : Yes;
5776 
5777     assert("|ab|".splitter!("a == b", Yes.keepSeparators)('|')
5778         .equal([ "", "|", "ab", "|", "" ]));
5779     assert("ab".splitter!("a == b", Yes.keepSeparators)('|')
5780         .equal([ "ab" ]));
5781 }
5782 
5783 /// Splitter returns bidirectional ranges if the delimiter is a single element
5784 @safe unittest
5785 {
5786     import std.algorithm.comparison : equal;
5787     import std.range : retro;
5788     assert("a|bc|def".splitter('|').retro.equal([ "def", "bc", "a" ]));
5789 }
5790 
5791 /// Splitter returns bidirectional ranges if the delimiter is a single element
5792 @safe unittest
5793 {
5794     import std.algorithm.comparison : equal;
5795     import std.typecons : Yes;
5796     import std.range : retro;
5797     assert("a|bc|def".splitter!("a == b", Yes.keepSeparators)('|')
5798         .retro.equal([ "def", "|", "bc", "|", "a" ]));
5799 }
5800 
5801 /// Splitting by word lazily
5802 @safe unittest
5803 {
5804     import std.ascii : isWhite;
5805     import std.algorithm.comparison : equal;
5806     import std.algorithm.iteration : splitter;
5807 
5808     string str = "Hello World!";
5809     assert(str.splitter!(isWhite).equal(["Hello", "World!"]));
5810 }
5811 
5812 @safe unittest
5813 {
5814     import std.algorithm;
5815     import std.array : array;
5816     import std.internal.test.dummyrange;
5817     import std.range : retro;
5818 
5819     assert(equal(splitter("hello  world", ' '), [ "hello", "", "world" ]));
5820     assert(equal(splitter("žlutoučkýřkůň", 'ř'), [ "žlutoučký", "kůň" ]));
5821     int[] a = [ 1, 2, 0, 0, 3, 0, 4, 5, 0 ];
5822     int[][] w = [ [1, 2], [], [3], [4, 5], [] ];
5823     static assert(isForwardRange!(typeof(splitter(a, 0))));
5824 
5825     assert(equal(splitter(a, 0), w));
5826     a = null;
5827     assert(equal(splitter(a, 0),  (int[][]).init));
5828     a = [ 0 ];
5829     assert(equal(splitter(a, 0), [ (int[]).init, (int[]).init ][]));
5830     a = [ 0, 1 ];
5831     assert(equal(splitter(a, 0), [ [], [1] ]));
5832     assert(equal(splitter(a, 0), [ [], [1] ][]));
5833 
5834     // Thoroughly exercise the bidirectional stuff.
5835     auto str = "abc abcd abcde ab abcdefg abcdefghij ab ac ar an at ada";
5836     assert(equal(
5837         retro(splitter(str, 'a')),
5838         retro(array(splitter(str, 'a')))
5839     ));
5840 
5841     // Test interleaving front and back.
5842     auto split = splitter(str, 'a');
5843     assert(split.front == "");
5844     assert(split.back == "");
5845     split.popBack();
5846     assert(split.back == "d");
5847     split.popFront();
5848     assert(split.front == "bc ");
5849     assert(split.back == "d");
5850     split.popFront();
5851     split.popBack();
5852     assert(split.back == "t ");
5853     split.popBack();
5854     split.popBack();
5855     split.popFront();
5856     split.popFront();
5857     assert(split.front == "b ");
5858     assert(split.back == "r ");
5859 
5860     // https://issues.dlang.org/show_bug.cgi?id=4408
5861     foreach (DummyType; AllDummyRanges)
5862     {
5863         static if (isRandomAccessRange!DummyType)
5864         {
5865             static assert(isBidirectionalRange!DummyType);
5866             DummyType d;
5867             auto s = splitter(d, 5);
5868             assert(equal(s.front, [1,2,3,4]));
5869             assert(equal(s.back, [6,7,8,9,10]));
5870 
5871             auto s2 = splitter(d, [4, 5]);
5872             assert(equal(s2.front, [1,2,3]));
5873         }
5874     }
5875 }
5876 @safe unittest
5877 {
5878     import std.algorithm;
5879     import std.range;
5880     auto L = retro(iota(1L, 10L));
5881     auto s = splitter(L, 5L);
5882     assert(equal(s.front, [9L, 8L, 7L, 6L]));
5883     s.popFront();
5884     assert(equal(s.front, [4L, 3L, 2L, 1L]));
5885     s.popFront();
5886     assert(s.empty);
5887 }
5888 
5889 // https://issues.dlang.org/show_bug.cgi?id=18470
5890 @safe unittest
5891 {
5892     import std.algorithm.comparison : equal;
5893 
5894     const w = [[0], [1], [2]];
5895     assert(w.splitter!((a, b) => a.front() == b)(1).equal([[[0]], [[2]]]));
5896 }
5897 
5898 // https://issues.dlang.org/show_bug.cgi?id=18470
5899 @safe unittest
5900 {
5901     import std.algorithm.comparison : equal;
5902     import std.ascii : toLower;
5903 
5904     assert("abXcdxef".splitter!"a.toLower == b"('x').equal(["ab", "cd", "ef"]));
5905     assert("abXcdxef".splitter!((a, b) => a.toLower == b)('x').equal(["ab", "cd", "ef"]));
5906 }
5907 
5908 /// ditto
5909 auto splitter(alias pred = "a == b",
5910               Flag!"keepSeparators" keepSeparators = No.keepSeparators,
5911               Range,
5912               Separator)(Range r, Separator s)
5913 if (is(typeof(binaryFun!pred(r.front, s.front)) : bool)
5914         && (hasSlicing!Range || isNarrowString!Range)
5915         && isForwardRange!Separator
5916         && (hasLength!Separator || isNarrowString!Separator))
5917 {
5918     import std.algorithm.searching : find;
5919     import std.conv : unsigned;
5920 
5921     static struct Result
5922     {
5923     private:
5924         Range _input;
5925         Separator _separator;
5926         // _frontLength == size_t.max means empty
5927         size_t _frontLength = size_t.max;
5928 
5929         static if (keepSeparators)
5930         {
5931             bool _wasSeparator = true;
5932         }
5933 
5934         @property auto separatorLength() { return _separator.length; }
5935 
5936         void ensureFrontLength()
5937         {
5938             if (_frontLength != _frontLength.max) return;
5939             static if (keepSeparators)
5940             {
5941                 assert(!_input.empty || _wasSeparator, "The input must not be empty");
5942                 if (_wasSeparator)
5943                 {
5944                     _frontLength = _input.length -
5945                         find!pred(_input, _separator).length;
5946                     _wasSeparator = false;
5947                 }
5948                 else
5949                 {
5950                     _frontLength = separatorLength();
5951                     _wasSeparator = true;
5952                 }
5953             }
5954             else
5955             {
5956                 assert(!_input.empty, "The input must not be empty");
5957                 // compute front length
5958                 _frontLength = (_separator.empty) ? 1 :
5959                            _input.length - find!pred(_input, _separator).length;
5960             }
5961         }
5962 
5963     public:
5964         this(Range input, Separator separator)
5965         {
5966             _input = input;
5967             _separator = separator;
5968         }
5969 
5970         @property Range front()
5971         {
5972             assert(!empty, "Attempting to fetch the front of an empty splitter.");
5973             ensureFrontLength();
5974             return _input[0 .. _frontLength];
5975         }
5976 
5977         static if (isInfinite!Range)
5978         {
5979             enum bool empty = false;  // Propagate infiniteness
5980         }
5981         else
5982         {
5983             @property bool empty()
5984             {
5985                 static if (keepSeparators)
5986                 {
5987                     return _frontLength == size_t.max && _input.empty && !_wasSeparator;
5988                 }
5989                 else
5990                 {
5991                     return _frontLength == size_t.max && _input.empty;
5992                 }
5993             }
5994         }
5995 
5996         void popFront()
5997         {
5998             assert(!empty, "Attempting to popFront an empty splitter.");
5999             ensureFrontLength();
6000 
6001             static if (keepSeparators)
6002             {
6003                 _input = _input[_frontLength .. _input.length];
6004             }
6005             else
6006             {
6007                 if (_frontLength == _input.length)
6008                 {
6009                     // done, there's no separator in sight
6010                     _input = _input[_frontLength .. _frontLength];
6011                     _frontLength = _frontLength.max;
6012                     return;
6013                 }
6014                 if (_frontLength + separatorLength == _input.length)
6015                 {
6016                     // Special case: popping the first-to-last item; there is
6017                     // an empty item right after this.
6018                     _input = _input[_input.length .. _input.length];
6019                     _frontLength = 0;
6020                     return;
6021                 }
6022                 // Normal case, pop one item and the separator, get ready for
6023                 // reading the next item
6024                 _input = _input[_frontLength + separatorLength .. _input.length];
6025             }
6026             // mark _frontLength as uninitialized
6027             _frontLength = _frontLength.max;
6028         }
6029 
6030         static if (isForwardRange!Range)
6031         {
6032             @property typeof(this) save()
6033             {
6034                 auto ret = this;
6035                 ret._input = _input.save;
6036                 return ret;
6037             }
6038         }
6039     }
6040 
6041     return Result(r, s);
6042 }
6043 
6044 @safe unittest
6045 {
6046     import std.algorithm.comparison : equal;
6047     import std.typecons : Tuple;
6048 
6049     alias C = Tuple!(int, "x", int, "y");
6050     auto a = [C(1,0), C(2,0), C(3,1), C(4,0)];
6051     assert(equal(splitter!"a.x == b"(a, [2, 3]), [ [C(1,0)], [C(4,0)] ]));
6052 }
6053 
6054 @safe unittest
6055 {
6056     import std.algorithm.comparison : equal;
6057     import std.array : split;
6058     import std.conv : text;
6059 
6060     auto s = ",abc, de, fg,hi,";
6061     auto sp0 = splitter(s, ',');
6062     assert(equal(sp0, ["", "abc", " de", " fg", "hi", ""][]));
6063 
6064     auto s1 = ", abc, de,  fg, hi, ";
6065     auto sp1 = splitter(s1, ", ");
6066     assert(equal(sp1, ["", "abc", "de", " fg", "hi", ""][]));
6067     static assert(isForwardRange!(typeof(sp1)));
6068 
6069     int[] a = [ 1, 2, 0, 3, 0, 4, 5, 0 ];
6070     int[][] w = [ [1, 2], [3], [4, 5], [] ];
6071     uint i;
6072     foreach (e; splitter(a, 0))
6073     {
6074         assert(i < w.length);
6075         assert(e == w[i++]);
6076     }
6077     assert(i == w.length);
6078 
6079     wstring names = ",peter,paul,jerry,";
6080     auto words = split(names, ",");
6081     assert(walkLength(words) == 5, text(walkLength(words)));
6082 }
6083 
6084 @safe unittest
6085 {
6086     int[][] a = [ [1], [2], [0], [3], [0], [4], [5], [0] ];
6087     int[][][] w = [ [[1], [2]], [[3]], [[4], [5]], [] ];
6088     uint i;
6089     foreach (e; splitter!"a.front == 0"(a, 0))
6090     {
6091         assert(i < w.length);
6092         assert(e == w[i++]);
6093     }
6094     assert(i == w.length);
6095 }
6096 
6097 @safe unittest
6098 {
6099     import std.algorithm.comparison : equal;
6100     auto s6 = ",";
6101     auto sp6 = splitter(s6, ',');
6102     foreach (e; sp6) {}
6103     assert(equal(sp6, ["", ""][]));
6104 }
6105 
6106 // https://issues.dlang.org/show_bug.cgi?id=10773
6107 @safe unittest
6108 {
6109     import std.algorithm.comparison : equal;
6110 
6111     auto s = splitter("abc", "");
6112     assert(s.equal(["a", "b", "c"]));
6113 }
6114 
6115 @safe unittest
6116 {
6117     import std.algorithm.comparison : equal;
6118 
6119     // Test by-reference separator
6120     static class RefSep {
6121     @safe:
6122         string _impl;
6123         this(string s) { _impl = s; }
6124         @property empty() { return _impl.empty; }
6125         @property auto front() { return _impl.front; }
6126         void popFront() { _impl = _impl[1..$]; }
6127         @property RefSep save() scope { return new RefSep(_impl); }
6128         @property auto length() { return _impl.length; }
6129     }
6130     auto sep = new RefSep("->");
6131     auto data = "i->am->pointing";
6132     auto words = splitter(data, sep);
6133     assert(words.equal([ "i", "am", "pointing" ]));
6134 }
6135 
6136 /// ditto
6137 auto splitter(alias isTerminator, Range)(Range r)
6138 if (isForwardRange!Range && is(typeof(unaryFun!isTerminator(r.front))))
6139 {
6140     return SplitterResult!(unaryFun!isTerminator, Range)(r);
6141 }
6142 
6143 private struct SplitterResult(alias isTerminator, Range)
6144 {
6145     import std.algorithm.searching : find;
6146     enum fullSlicing = (hasLength!Range && hasSlicing!Range) || isSomeString!Range;
6147 
6148     private Range _input;
6149     private size_t _end = 0;
6150     static if (!fullSlicing)
6151         private Range _next;
6152 
6153     private void findTerminator()
6154     {
6155         static if (fullSlicing)
6156         {
6157             auto r = find!isTerminator(_input.save);
6158             _end = _input.length - r.length;
6159         }
6160         else
6161             for ( _end = 0; !_next.empty ; _next.popFront)
6162             {
6163                 if (isTerminator(_next.front))
6164                     break;
6165                 ++_end;
6166             }
6167     }
6168 
6169     this(Range input)
6170     {
6171         _input = input;
6172         static if (!fullSlicing)
6173             _next = _input.save;
6174 
6175         if (!_input.empty)
6176             findTerminator();
6177         else
6178             _end = size_t.max;
6179     }
6180 
6181     static if (fullSlicing)
6182     {
6183         private this(Range input, size_t end)
6184         {
6185             _input = input;
6186             _end = end;
6187         }
6188     }
6189     else
6190     {
6191         private this(Range input, size_t end, Range next)
6192         {
6193             _input = input;
6194             _end = end;
6195             _next = next;
6196         }
6197     }
6198 
6199     static if (isInfinite!Range)
6200     {
6201         enum bool empty = false;  // Propagate infiniteness.
6202     }
6203     else
6204     {
6205         @property bool empty()
6206         {
6207             return _end == size_t.max;
6208         }
6209     }
6210 
6211     @property auto front()
6212     {
6213         version (assert)
6214         {
6215             import core.exception : RangeError;
6216             if (empty)
6217                 throw new RangeError();
6218         }
6219         static if (fullSlicing)
6220             return _input[0 .. _end];
6221         else
6222         {
6223             import std.range : takeExactly;
6224             return _input.takeExactly(_end);
6225         }
6226     }
6227 
6228     void popFront()
6229     {
6230         version (assert)
6231         {
6232             import core.exception : RangeError;
6233             if (empty)
6234                 throw new RangeError();
6235         }
6236 
6237         static if (fullSlicing)
6238         {
6239             _input = _input[_end .. _input.length];
6240             if (_input.empty)
6241             {
6242                 _end = size_t.max;
6243                 return;
6244             }
6245             _input.popFront();
6246         }
6247         else
6248         {
6249             if (_next.empty)
6250             {
6251                 _input = _next;
6252                 _end = size_t.max;
6253                 return;
6254             }
6255             _next.popFront();
6256             _input = _next.save;
6257         }
6258         findTerminator();
6259     }
6260 
6261     @property typeof(this) save()
6262     {
6263         static if (fullSlicing)
6264             return SplitterResult(_input.save, _end);
6265         else
6266             return SplitterResult(_input.save, _end, _next.save);
6267     }
6268 }
6269 
6270 @safe unittest
6271 {
6272     import std.algorithm.comparison : equal;
6273     import std.range : iota;
6274 
6275     auto L = iota(1L, 10L);
6276     auto s = splitter(L, [5L, 6L]);
6277     assert(equal(s.front, [1L, 2L, 3L, 4L]));
6278     s.popFront();
6279     assert(equal(s.front, [7L, 8L, 9L]));
6280     s.popFront();
6281     assert(s.empty);
6282 }
6283 
6284 @safe unittest
6285 {
6286     import std.algorithm.comparison : equal;
6287     import std.algorithm.internal : algoFormat;
6288     import std.internal.test.dummyrange;
6289 
6290     void compare(string sentence, string[] witness)
6291     {
6292         auto r = splitter!"a == ' '"(sentence);
6293         assert(equal(r.save, witness), algoFormat("got: %(%s, %) expected: %(%s, %)", r, witness));
6294     }
6295 
6296     compare(" Mary  has a little lamb.   ",
6297             ["", "Mary", "", "has", "a", "little", "lamb.", "", "", ""]);
6298     compare("Mary  has a little lamb.   ",
6299             ["Mary", "", "has", "a", "little", "lamb.", "", "", ""]);
6300     compare("Mary  has a little lamb.",
6301             ["Mary", "", "has", "a", "little", "lamb."]);
6302     compare("", (string[]).init);
6303     compare(" ", ["", ""]);
6304 
6305     static assert(isForwardRange!(typeof(splitter!"a == ' '"("ABC"))));
6306 
6307     foreach (DummyType; AllDummyRanges)
6308     {
6309         static if (isRandomAccessRange!DummyType)
6310         {
6311             auto rangeSplit = splitter!"a == 5"(DummyType.init);
6312             assert(equal(rangeSplit.front, [1,2,3,4]));
6313             rangeSplit.popFront();
6314             assert(equal(rangeSplit.front, [6,7,8,9,10]));
6315         }
6316     }
6317 }
6318 
6319 @safe unittest
6320 {
6321     import std.algorithm.comparison : equal;
6322     import std.algorithm.internal : algoFormat;
6323     import std.range;
6324 
6325     struct Entry
6326     {
6327         int low;
6328         int high;
6329         int[][] result;
6330     }
6331     Entry[] entries = [
6332         Entry(0, 0, []),
6333         Entry(0, 1, [[0]]),
6334         Entry(1, 2, [[], []]),
6335         Entry(2, 7, [[2], [4], [6]]),
6336         Entry(1, 8, [[], [2], [4], [6], []]),
6337     ];
6338     foreach ( entry ; entries )
6339     {
6340         auto a = iota(entry.low, entry.high).filter!"true"();
6341         auto b = splitter!"a%2"(a);
6342         assert(equal!equal(b.save, entry.result), algoFormat("got: %(%s, %) expected: %(%s, %)", b, entry.result));
6343     }
6344 }
6345 
6346 @safe unittest
6347 {
6348     import std.algorithm.comparison : equal;
6349     import std.uni : isWhite;
6350 
6351     // https://issues.dlang.org/show_bug.cgi?id=6791
6352     assert(equal(
6353         splitter("là dove terminava quella valle"),
6354         ["là", "dove", "terminava", "quella", "valle"]
6355     ));
6356     assert(equal(
6357         splitter!(isWhite)("là dove terminava quella valle"),
6358         ["là", "dove", "terminava", "quella", "valle"]
6359     ));
6360     assert(equal(splitter!"a=='本'"("日本語"), ["日", "語"]));
6361 }
6362 
6363 // https://issues.dlang.org/show_bug.cgi?id=18657
6364 pure @safe unittest
6365 {
6366     import std.algorithm.comparison : equal;
6367     import std.range : refRange;
6368     string s = "foobar";
6369     auto r = refRange(&s).splitter!(c => c == 'b');
6370     assert(equal!equal(r.save, ["foo", "ar"]));
6371     assert(equal!equal(r.save, ["foo", "ar"]));
6372 }
6373 
6374 /++
6375 Lazily splits the character-based range `s` into words, using whitespace as the
6376 delimiter.
6377 
6378 This function is character-range specific and, contrary to
6379 `splitter!(std.uni.isWhite)`, runs of whitespace will be merged together
6380 (no empty tokens will be produced).
6381 
6382 Params:
6383     s = The character-based range to be split. Must be a string, or a
6384     random-access range of character types.
6385 
6386 Returns:
6387     An $(REF_ALTTEXT input range, isInputRange, std,range,primitives) of slices of
6388     the original range split by whitespace.
6389  +/
6390 auto splitter(Range)(Range s)
6391 if (isSomeString!Range ||
6392     isRandomAccessRange!Range && hasLength!Range && hasSlicing!Range &&
6393     !isConvertibleToString!Range &&
6394     isSomeChar!(ElementEncodingType!Range))
6395 {
6396     import std.algorithm.searching : find;
6397     static struct Result
6398     {
6399     private:
6400         import core.exception : RangeError;
6401         Range _s;
6402         size_t _frontLength;
6403 
6404         void getFirst()
6405         {
6406             import std.uni : isWhite;
6407             import std.traits : Unqual;
6408 
6409             static if (is(immutable ElementEncodingType!Range == immutable wchar) &&
6410                        is(immutable ElementType!Range == immutable dchar))
6411             {
6412                 // all unicode whitespace characters fit into a wchar. However,
6413                 // this range is a wchar array, so we will treat it like a
6414                 // wchar array instead of decoding each code point.
6415                 _frontLength = _s.length; // default condition, no spaces
6416                 foreach (i; 0 .. _s.length)
6417                     if (isWhite(_s[i]))
6418                     {
6419                         _frontLength = i;
6420                         break;
6421                     }
6422             }
6423             else static if (is(immutable ElementType!Range == immutable dchar) ||
6424                             is(immutable ElementType!Range == immutable wchar))
6425             {
6426                 // dchar or wchar range, we can just use find.
6427                 auto r = find!(isWhite)(_s.save);
6428                 _frontLength = _s.length - r.length;
6429             }
6430             else
6431             {
6432                 // need to decode the characters until we find a space. This is
6433                 // ported from std.string.stripLeft.
6434                 static import std.ascii;
6435                 static import std.uni;
6436                 import std.utf : decodeFront;
6437 
6438                 auto input = _s.save;
6439                 size_t iLength = input.length;
6440 
6441                 while (!input.empty)
6442                 {
6443                     auto c = input.front;
6444                     if (std.ascii.isASCII(c))
6445                     {
6446                         if (std.ascii.isWhite(c))
6447                             break;
6448                         input.popFront();
6449                         --iLength;
6450                     }
6451                     else
6452                     {
6453                         auto dc = decodeFront(input);
6454                         if (std.uni.isWhite(dc))
6455                             break;
6456                         iLength = input.length;
6457                     }
6458                 }
6459 
6460                 // sanity check
6461                 assert(iLength <= _s.length, "The current index must not"
6462                         ~ " exceed the length of the input");
6463 
6464                 _frontLength = _s.length - iLength;
6465             }
6466         }
6467 
6468     public:
6469         this(Range s)
6470         {
6471             import std.string : stripLeft;
6472             _s = s.stripLeft();
6473             getFirst();
6474         }
6475 
6476         @property auto front()
6477         {
6478             version (assert) if (empty) throw new RangeError();
6479             return _s[0 .. _frontLength];
6480         }
6481 
6482         void popFront()
6483         {
6484             import std.string : stripLeft;
6485             version (assert) if (empty) throw new RangeError();
6486             _s = _s[_frontLength .. $].stripLeft();
6487             getFirst();
6488         }
6489 
6490         @property bool empty() const
6491         {
6492             return _s.empty;
6493         }
6494 
6495         @property inout(Result) save() inout @safe pure nothrow
6496         {
6497             return this;
6498         }
6499     }
6500     return Result(s);
6501 }
6502 
6503 ///
6504 @safe pure unittest
6505 {
6506     import std.algorithm.comparison : equal;
6507     auto a = " a     bcd   ef gh ";
6508     assert(equal(splitter(a), ["a", "bcd", "ef", "gh"][]));
6509 }
6510 
6511 @safe pure unittest
6512 {
6513     import std.algorithm.comparison : equal;
6514     import std.meta : AliasSeq;
6515     static foreach (S; AliasSeq!(string, wstring, dstring))
6516     {{
6517         import std.conv : to;
6518         S a = " a  \u2028   bcd   ef gh ";
6519         assert(equal(splitter(a), [to!S("a"), to!S("bcd"), to!S("ef"), to!S("gh")]));
6520         a = "";
6521         assert(splitter(a).empty);
6522     }}
6523 
6524     immutable string s = " a     bcd   ef gh ";
6525     assert(equal(splitter(s), ["a", "bcd", "ef", "gh"][]));
6526 }
6527 
6528 @safe unittest
6529 {
6530     import std.conv : to;
6531     import std.string : strip;
6532 
6533     // TDPL example, page 8
6534     uint[string] dictionary;
6535     char[][3] lines;
6536     lines[0] = "line one".dup;
6537     lines[1] = "line \ttwo".dup;
6538     lines[2] = "yah            last   line\ryah".dup;
6539     foreach (line; lines)
6540     {
6541        foreach (word; splitter(strip(line)))
6542        {
6543             if (word in dictionary) continue; // Nothing to do
6544             auto newID = dictionary.length;
6545             dictionary[to!string(word)] = cast(uint) newID;
6546         }
6547     }
6548     assert(dictionary.length == 5);
6549     assert(dictionary["line"]== 0);
6550     assert(dictionary["one"]== 1);
6551     assert(dictionary["two"]== 2);
6552     assert(dictionary["yah"]== 3);
6553     assert(dictionary["last"]== 4);
6554 
6555 }
6556 
6557 @safe unittest
6558 {
6559     // do it with byCodeUnit
6560     import std.conv : to;
6561     import std.string : strip;
6562     import std.utf : byCodeUnit;
6563 
6564     alias BCU = typeof("abc".byCodeUnit());
6565 
6566     // TDPL example, page 8
6567     uint[BCU] dictionary;
6568     BCU[3] lines;
6569     lines[0] = "line one".byCodeUnit;
6570     lines[1] = "line \ttwo".byCodeUnit;
6571     lines[2] = "yah            last   line\ryah".byCodeUnit;
6572     foreach (line; lines)
6573     {
6574        foreach (word; splitter(strip(line)))
6575        {
6576            static assert(is(typeof(word) == BCU));
6577             if (word in dictionary) continue; // Nothing to do
6578             auto newID = dictionary.length;
6579             dictionary[word] = cast(uint) newID;
6580         }
6581     }
6582     assert(dictionary.length == 5);
6583     assert(dictionary["line".byCodeUnit]== 0);
6584     assert(dictionary["one".byCodeUnit]== 1);
6585     assert(dictionary["two".byCodeUnit]== 2);
6586     assert(dictionary["yah".byCodeUnit]== 3);
6587     assert(dictionary["last".byCodeUnit]== 4);
6588 }
6589 
6590 // https://issues.dlang.org/show_bug.cgi?id=19238
6591 @safe pure unittest
6592 {
6593     import std.utf : byCodeUnit;
6594     import std.algorithm.comparison : equal;
6595     auto range = "hello    world".byCodeUnit.splitter;
6596     static assert(is(typeof(range.front()) == typeof("hello".byCodeUnit())));
6597     assert(range.equal(["hello".byCodeUnit, "world".byCodeUnit]));
6598 
6599     // test other space types, including unicode
6600     auto u = " a\t\v\r bcd\u3000 \u2028\t\nef\U00010001 gh";
6601     assert(equal(splitter(u), ["a", "bcd", "ef\U00010001", "gh"][]));
6602     assert(equal(splitter(u.byCodeUnit), ["a".byCodeUnit, "bcd".byCodeUnit,
6603                  "ef\U00010001".byCodeUnit, "gh".byCodeUnit][]));
6604 }
6605 
6606 @safe unittest
6607 {
6608     import std.algorithm.comparison : equal;
6609     import std.algorithm.internal : algoFormat;
6610     import std.array : split;
6611     import std.conv : text;
6612 
6613     // Check consistency:
6614     // All flavors of split should produce the same results
6615     foreach (input; [(int[]).init,
6616                      [0],
6617                      [0, 1, 0],
6618                      [1, 1, 0, 0, 1, 1],
6619                     ])
6620     {
6621         foreach (s; [0, 1])
6622         {
6623             auto result = split(input, s);
6624 
6625             assert(equal(result, split(input, [s])), algoFormat(`"[%(%s,%)]"`, split(input, [s])));
6626             //assert(equal(result, split(input, [s].filter!"true"())));                          //Not yet implemented
6627             assert(equal(result, split!((a) => a == s)(input)), text(split!((a) => a == s)(input)));
6628 
6629             //assert(equal!equal(result, split(input.filter!"true"(), s)));                      //Not yet implemented
6630             //assert(equal!equal(result, split(input.filter!"true"(), [s])));                    //Not yet implemented
6631             //assert(equal!equal(result, split(input.filter!"true"(), [s].filter!"true"())));    //Not yet implemented
6632             assert(equal!equal(result, split!((a) => a == s)(input.filter!"true"())));
6633 
6634             assert(equal(result, splitter(input, s)));
6635             assert(equal(result, splitter(input, [s])));
6636             //assert(equal(result, splitter(input, [s].filter!"true"())));                       //Not yet implemented
6637             assert(equal(result, splitter!((a) => a == s)(input)));
6638 
6639             //assert(equal!equal(result, splitter(input.filter!"true"(), s)));                   //Not yet implemented
6640             //assert(equal!equal(result, splitter(input.filter!"true"(), [s])));                 //Not yet implemented
6641             //assert(equal!equal(result, splitter(input.filter!"true"(), [s].filter!"true"()))); //Not yet implemented
6642             assert(equal!equal(result, splitter!((a) => a == s)(input.filter!"true"())));
6643         }
6644     }
6645     foreach (input; [string.init,
6646                      " ",
6647                      "  hello ",
6648                      "hello   hello",
6649                      " hello   what heck   this ?  "
6650                     ])
6651     {
6652         foreach (s; [' ', 'h'])
6653         {
6654             auto result = split(input, s);
6655 
6656             assert(equal(result, split(input, [s])));
6657             //assert(equal(result, split(input, [s].filter!"true"())));                          //Not yet implemented
6658             assert(equal(result, split!((a) => a == s)(input)));
6659 
6660             //assert(equal!equal(result, split(input.filter!"true"(), s)));                      //Not yet implemented
6661             //assert(equal!equal(result, split(input.filter!"true"(), [s])));                    //Not yet implemented
6662             //assert(equal!equal(result, split(input.filter!"true"(), [s].filter!"true"())));    //Not yet implemented
6663             assert(equal!equal(result, split!((a) => a == s)(input.filter!"true"())));
6664 
6665             assert(equal(result, splitter(input, s)));
6666             assert(equal(result, splitter(input, [s])));
6667             //assert(equal(result, splitter(input, [s].filter!"true"())));                       //Not yet implemented
6668             assert(equal(result, splitter!((a) => a == s)(input)));
6669 
6670             //assert(equal!equal(result, splitter(input.filter!"true"(), s)));                   //Not yet implemented
6671             //assert(equal!equal(result, splitter(input.filter!"true"(), [s])));                 //Not yet implemented
6672             //assert(equal!equal(result, splitter(input.filter!"true"(), [s].filter!"true"()))); //Not yet implemented
6673             assert(equal!equal(result, splitter!((a) => a == s)(input.filter!"true"())));
6674         }
6675     }
6676 }
6677 
6678 // In same combinations substitute needs to calculate the auto-decoded length
6679 // of its needles
6680 private template hasDifferentAutodecoding(Range, Needles...)
6681 {
6682     import std.meta : anySatisfy;
6683     /* iff
6684        - the needles needs auto-decoding, but the incoming range doesn't (or vice versa)
6685        - both (range, needle) need auto-decoding and don't share the same common type
6686     */
6687     enum needlesAreNarrow = anySatisfy!(isNarrowString, Needles);
6688     enum sourceIsNarrow = isNarrowString!Range;
6689     enum hasDifferentAutodecoding = sourceIsNarrow != needlesAreNarrow ||
6690                                     (sourceIsNarrow && needlesAreNarrow &&
6691                                     is(CommonType!(Range, Needles) == void));
6692 }
6693 
6694 @safe nothrow @nogc pure unittest
6695 {
6696     import std.meta : AliasSeq; // used for better clarity
6697 
6698     static assert(!hasDifferentAutodecoding!(string, AliasSeq!(string, string)));
6699     static assert(!hasDifferentAutodecoding!(wstring, AliasSeq!(wstring, wstring)));
6700     static assert(!hasDifferentAutodecoding!(dstring, AliasSeq!(dstring, dstring)));
6701 
6702     // the needles needs auto-decoding, but the incoming range doesn't (or vice versa)
6703     static assert(hasDifferentAutodecoding!(string, AliasSeq!(wstring, wstring)));
6704     static assert(hasDifferentAutodecoding!(string, AliasSeq!(dstring, dstring)));
6705     static assert(hasDifferentAutodecoding!(wstring, AliasSeq!(string, string)));
6706     static assert(hasDifferentAutodecoding!(wstring, AliasSeq!(dstring, dstring)));
6707     static assert(hasDifferentAutodecoding!(dstring, AliasSeq!(string, string)));
6708     static assert(hasDifferentAutodecoding!(dstring, AliasSeq!(wstring, wstring)));
6709 
6710     // both (range, needle) need auto-decoding and don't share the same common type
6711     static foreach (T; AliasSeq!(string, wstring, dstring))
6712     {
6713         static assert(hasDifferentAutodecoding!(T, AliasSeq!(wstring, string)));
6714         static assert(hasDifferentAutodecoding!(T, AliasSeq!(dstring, string)));
6715         static assert(hasDifferentAutodecoding!(T, AliasSeq!(wstring, dstring)));
6716     }
6717 }
6718 
6719 // substitute
6720 /**
6721 Returns a range with all occurrences of `substs` in `r`.
6722 replaced with their substitution.
6723 
6724 Single value replacements (`'ö'.substitute!('ä', 'a', 'ö', 'o', 'ü', 'u)`) are
6725 supported as well and in $(BIGOH 1).
6726 
6727 Params:
6728     r = an $(REF_ALTTEXT input range, isInputRange, std,range,primitives)
6729     value = a single value which can be substituted in $(BIGOH 1)
6730     substs = a set of replacements/substitutions
6731     pred = the equality function to test if element(s) are equal to
6732     a substitution
6733 
6734 Returns: a range with the substitutions replaced.
6735 
6736 See_Also:
6737 $(REF replace, std, array) for an eager replace algorithm or
6738 $(REF translate, std, string), and $(REF tr, std, string)
6739 for string algorithms with translation tables.
6740 */
6741 template substitute(substs...)
6742 if (substs.length >= 2 && isExpressions!substs)
6743 {
6744     import std.range.primitives : ElementType;
6745     import std.traits : CommonType;
6746 
6747     static assert(!(substs.length & 1), "The number of substitution parameters must be even");
6748 
6749     /**
6750       Substitute single values with compile-time substitution mappings.
6751       Complexity: $(BIGOH 1) due to D's `switch` guaranteeing $(BIGOH 1);
6752     */
6753     auto substitute(Value)(Value value)
6754     if (isInputRange!Value || !is(CommonType!(Value, typeof(substs[0])) == void))
6755     {
6756         static if (isInputRange!Value)
6757         {
6758             static if (!is(CommonType!(ElementType!Value, typeof(substs[0])) == void))
6759             {
6760                 // Substitute single range elements with compile-time substitution mappings
6761                 return value.map!(a => substitute(a));
6762             }
6763             else static if (isInputRange!Value &&
6764                     !is(CommonType!(ElementType!Value, ElementType!(typeof(substs[0]))) == void))
6765             {
6766                 // not implemented yet, fallback to runtime variant for now
6767                 return .substitute(value, substs);
6768             }
6769             else
6770             {
6771                 static assert(0, `Compile-time substitutions must be elements or ranges of the same type of ` ~
6772                     Value.stringof ~ `.`);
6773             }
6774         }
6775         // Substitute single values with compile-time substitution mappings.
6776         else // static if (!is(CommonType!(Value, typeof(substs[0])) == void))
6777         {
6778             switch (value)
6779             {
6780                 static foreach (i; 0 .. substs.length / 2)
6781                     case substs[2 * i]:
6782                         return substs[2 * i + 1];
6783 
6784                 default: return value;
6785             }
6786         }
6787     }
6788 }
6789 
6790 /// ditto
6791 auto substitute(alias pred = (a, b) => a == b, R, Substs...)(R r, Substs substs)
6792 if (isInputRange!R && Substs.length >= 2 && !is(CommonType!(Substs) == void))
6793 {
6794     import std.range.primitives : ElementType;
6795     import std.meta : allSatisfy;
6796     import std.traits : CommonType;
6797 
6798     static assert(!(Substs.length & 1), "The number of substitution parameters must be even");
6799 
6800     enum n = Substs.length / 2;
6801 
6802     // Substitute individual elements
6803     static if (!is(CommonType!(ElementType!R, Substs) == void))
6804     {
6805         import std.functional : binaryFun;
6806 
6807         // Imitate a value closure to be @nogc
6808         static struct ReplaceElement
6809         {
6810             private Substs substs;
6811 
6812             this(Substs substs)
6813             {
6814                 this.substs = substs;
6815             }
6816 
6817             auto opCall(E)(E e)
6818             {
6819                 static foreach (i; 0 .. n)
6820                     if (binaryFun!pred(e, substs[2 * i]))
6821                         return substs[2 * i + 1];
6822 
6823                 return e;
6824             }
6825         }
6826         auto er = ReplaceElement(substs);
6827         return r.map!er;
6828     }
6829     // Substitute subranges
6830     else static if (!is(CommonType!(ElementType!R, ElementType!(Substs[0])) == void)  &&
6831                         allSatisfy!(isForwardRange, Substs))
6832     {
6833         import std.range : choose, take;
6834         import std.meta : Stride;
6835 
6836         auto replaceElement(E)(E e)
6837         {
6838             alias ReturnA = typeof(e[0]);
6839             alias ReturnB = typeof(substs[0 .. 1].take(1));
6840 
6841             // 1-based index
6842             const auto hitNr = e[1];
6843             switch (hitNr)
6844             {
6845                 // no hit
6846                 case 0:
6847                     // use choose trick for non-common range
6848                     static if (is(CommonType!(ReturnA, ReturnB) == void))
6849                         return choose(1, e[0], ReturnB.init);
6850                     else
6851                         return e[0];
6852 
6853                 // all replacements
6854                 static foreach (i; 0 .. n)
6855                     case i + 1:
6856                         // use choose trick for non-common ranges
6857                         static if (is(CommonType!(ReturnA, ReturnB) == void))
6858                             return choose(0, e[0], substs[2 * i + 1].take(size_t.max));
6859                         else
6860                             return substs[2 * i + 1].take(size_t.max);
6861                 default:
6862                     assert(0, "hitNr should always be found.");
6863             }
6864         }
6865 
6866         alias Ins = Stride!(2, Substs);
6867 
6868         static struct SubstituteSplitter
6869         {
6870             import std.range : drop;
6871             import std.typecons : Tuple;
6872 
6873             private
6874             {
6875                 typeof(R.init.drop(0)) rest;
6876                 Ins needles;
6877 
6878                 typeof(R.init.take(0)) skip; // skip before next hit
6879                 alias Hit = size_t; // 0 iff no hit, otherwise hit in needles[index-1]
6880                 alias E = Tuple!(typeof(skip), Hit);
6881                 Hit hitNr; // hit number: 0 means no hit, otherwise index+1 to needles that matched
6882                 bool hasHit; // is there a replacement hit which should be printed?
6883 
6884                 enum hasDifferentAutodecoding = .hasDifferentAutodecoding!(typeof(rest), Ins);
6885 
6886                 // calculating the needle length for narrow strings might be expensive -> cache it
6887                  static if (hasDifferentAutodecoding)
6888                      ptrdiff_t[n] needleLengths = -1;
6889             }
6890 
6891             this(R haystack, Ins needles)
6892             {
6893                 this.rest = haystack.drop(0);
6894                 this.needles = needles;
6895                 if (!haystack.empty)
6896                 {
6897                     hasHit = true;
6898                     popFront;
6899                 }
6900                 static if (hasNested!(typeof(skip)))
6901                     skip = rest.take(0);
6902             }
6903 
6904             /*  If `skip` is non-empty, it's returned as (skip, 0) tuple
6905                 otherwise a similar (<empty>, hitNr) tuple is returned.
6906                 `replaceElement` maps based on the second item (`hitNr`).
6907             */
6908             @property auto ref front()
6909             {
6910                 assert(!empty, "Attempting to fetch the front of an empty substitute.");
6911                 return !skip.empty ? E(skip, 0) : E(typeof(skip).init, hitNr);
6912             }
6913 
6914             static if (isInfinite!R)
6915                 enum empty = false; // propagate infiniteness
6916             else
6917                 @property bool empty()
6918                 {
6919                     return skip.empty && !hasHit;
6920                 }
6921 
6922             /* If currently in a skipping phase => reset.
6923                Otherwise try to find the next occurrence of `needles`
6924                   If valid match
6925                     - if there are elements before the match, set skip with these elements
6926                       (on the next popFront, the range will be in the skip state once)
6927                     - `rest`: advance to the end of the match
6928                     - set hasHit
6929                Otherwise skip to the end
6930             */
6931             void popFront()
6932             {
6933                 assert(!empty, "Attempting to popFront an empty substitute.");
6934                 if (!skip.empty)
6935                 {
6936                     skip = typeof(skip).init; // jump over skip
6937                 }
6938                 else
6939                 {
6940                     import std.algorithm.searching : countUntil, find;
6941 
6942                     auto match = rest.find!pred(needles);
6943 
6944                     static if (needles.length >= 2) // variadic version of find (returns a tuple)
6945                     {
6946                         // find with variadic needles returns a (range, needleNr) tuple
6947                         // needleNr is a 1-based index
6948                         auto hitValue = match[0];
6949                         hitNr = match[1];
6950                     }
6951                     else
6952                     {
6953                         // find with one needle returns the range
6954                         auto hitValue = match;
6955                         hitNr = match.empty ? 0 : 1;
6956                     }
6957 
6958                     if (hitNr == 0) // no more hits
6959                     {
6960                         skip = rest.take(size_t.max);
6961                         hasHit = false;
6962                         rest = typeof(rest).init;
6963                     }
6964                     else
6965                     {
6966                         auto hitLength = size_t.max;
6967                         switchL: switch (hitNr - 1)
6968                         {
6969                             static foreach (i; 0 .. n)
6970                             {
6971                                 case i:
6972                                     static if (hasDifferentAutodecoding)
6973                                     {
6974                                         import std.utf : codeLength;
6975 
6976                                         // cache calculated needle length
6977                                         if (needleLengths[i] != -1)
6978                                             hitLength = needleLengths[i];
6979                                         else
6980                                             hitLength = needleLengths[i] = codeLength!dchar(needles[i]);
6981                                     }
6982                                     else
6983                                     {
6984                                         hitLength = needles[i].length;
6985                                     }
6986                                     break switchL;
6987                             }
6988                             default:
6989                                 assert(0, "hitNr should always be found");
6990                         }
6991 
6992                         const pos = rest.countUntil(hitValue);
6993                         if (pos > 0) // match not at start of rest
6994                             skip = rest.take(pos);
6995 
6996                         hasHit = true;
6997 
6998                         // iff the source range and the substitutions are narrow strings,
6999                         // we can avoid calling the auto-decoding `popFront` (via drop)
7000                         static if (isNarrowString!(typeof(hitValue)) && !hasDifferentAutodecoding)
7001                             rest = hitValue[hitLength .. $];
7002                         else
7003                             rest = hitValue.drop(hitLength);
7004                     }
7005                 }
7006             }
7007         }
7008 
7009         // extract inputs
7010         Ins ins;
7011         static foreach (i; 0 .. n)
7012             ins[i] = substs[2 * i];
7013 
7014         return SubstituteSplitter(r, ins)
7015                 .map!(a => replaceElement(a))
7016                 .joiner;
7017     }
7018     else
7019     {
7020         static assert(0, "The substitutions must either substitute a single element or a save-able subrange.");
7021     }
7022 }
7023 
7024 ///
7025 @safe pure unittest
7026 {
7027     import std.algorithm.comparison : equal;
7028 
7029     // substitute single elements
7030     assert("do_it".substitute('_', ' ').equal("do it"));
7031 
7032     // substitute multiple, single elements
7033     assert("do_it".substitute('_', ' ',
7034                                'd', 'g',
7035                                'i', 't',
7036                                't', 'o')
7037                   .equal("go to"));
7038 
7039     // substitute subranges
7040     assert("do_it".substitute("_", " ",
7041                               "do", "done")
7042                   .equal("done it"));
7043 
7044     // substitution works for any ElementType
7045     int[] x = [1, 2, 3];
7046     auto y = x.substitute(1, 0.1);
7047     assert(y.equal([0.1, 2, 3]));
7048     static assert(is(typeof(y.front) == double));
7049 
7050     import std.range : retro;
7051     assert([1, 2, 3].substitute(1, 0.1).retro.equal([3, 2, 0.1]));
7052 }
7053 
7054 /// Use the faster compile-time overload
7055 @safe pure unittest
7056 {
7057     import std.algorithm.comparison : equal;
7058 
7059     // substitute subranges of a range
7060     assert("apple_tree".substitute!("apple", "banana",
7061                                     "tree", "shrub").equal("banana_shrub"));
7062 
7063     // substitute subranges of a range
7064     assert("apple_tree".substitute!('a', 'b',
7065                                     't', 'f').equal("bpple_free"));
7066 
7067     // substitute values
7068     assert('a'.substitute!('a', 'b', 't', 'f') == 'b');
7069 }
7070 
7071 /// Multiple substitutes
7072 @safe pure unittest
7073 {
7074     import std.algorithm.comparison : equal;
7075     import std.range.primitives : ElementType;
7076 
7077     int[3] x = [1, 2, 3];
7078     auto y = x[].substitute(1, 0.1)
7079                 .substitute(0.1, 0.2);
7080     static assert(is(typeof(y.front) == double));
7081     assert(y.equal([0.2, 2, 3]));
7082 
7083     auto z = "42".substitute('2', '3')
7084                  .substitute('3', '1');
7085     static assert(is(ElementType!(typeof(z)) == dchar));
7086     assert(equal(z, "41"));
7087 }
7088 
7089 // Test the first example with compile-time overloads
7090 @safe pure unittest
7091 {
7092     import std.algorithm.comparison : equal;
7093 
7094     // substitute single elements
7095     assert("do_it".substitute!('_', ' ').equal("do it"));
7096 
7097     // substitute multiple, single elements
7098     assert("do_it".substitute!('_', ' ',
7099                                'd', 'g',
7100                                'i', 't',
7101                                't', 'o')
7102                   .equal(`go to`));
7103 
7104     // substitute subranges
7105     assert("do_it".substitute!("_", " ",
7106                                "do", "done")
7107                   .equal("done it"));
7108 
7109     // substitution works for any ElementType
7110     int[3] x = [1, 2, 3];
7111     auto y = x[].substitute!(1, 0.1);
7112     assert(y.equal([0.1, 2, 3]));
7113     static assert(is(typeof(y.front) == double));
7114 
7115     import std.range : retro;
7116     assert([1, 2, 3].substitute!(1, 0.1).retro.equal([3, 2, 0.1]));
7117 }
7118 
7119 // test infinite ranges
7120 @safe pure nothrow unittest
7121 {
7122     import std.algorithm.comparison : equal;
7123     import std.range : cycle, take;
7124 
7125     int[] x = [1, 2, 3];
7126     assert(x.cycle.substitute!(1, 0.1).take(4).equal([0.1, 2, 3, 0.1]));
7127     assert(x.cycle.substitute(1, 0.1).take(4).equal([0.1, 2, 3, 0.1]));
7128 }
7129 
7130 // test infinite ranges
7131 @safe pure nothrow unittest
7132 {
7133     import std.algorithm.comparison : equal;
7134     import std.internal.test.dummyrange : AllDummyRanges;
7135 
7136     foreach (R; AllDummyRanges)
7137     {
7138         assert(R.init
7139                 .substitute!(2, 22, 3, 33, 5, 55, 9, 99)
7140                 .equal([1, 22, 33, 4, 55, 6, 7, 8, 99, 10]));
7141 
7142         assert(R.init
7143                 .substitute(2, 22, 3, 33, 5, 55, 9, 99)
7144                 .equal([1, 22, 33, 4, 55, 6, 7, 8, 99, 10]));
7145     }
7146 }
7147 
7148 // test multiple replacements
7149 @safe pure unittest
7150 {
7151     import std.algorithm.comparison : equal;
7152 
7153     assert("alpha.beta.gamma"
7154             .substitute("alpha", "1",
7155                         "gamma", "3",
7156                         "beta", "2").equal("1.2.3"));
7157 
7158     assert("alpha.beta.gamma."
7159             .substitute("alpha", "1",
7160                         "gamma", "3",
7161                         "beta", "2").equal("1.2.3."));
7162 
7163     assert("beta.beta.beta"
7164             .substitute("alpha", "1",
7165                         "gamma", "3",
7166                         "beta", "2").equal("2.2.2"));
7167 
7168     assert("alpha.alpha.alpha"
7169             .substitute("alpha", "1",
7170                         "gamma", "3",
7171                         "beta", "2").equal("1.1.1"));
7172 }
7173 
7174 // test combination of subrange + element replacement
7175 @safe pure unittest
7176 {
7177     import std.algorithm.comparison : equal;
7178 
7179     assert(("abcDe".substitute("a", "AA",
7180                                "b", "DD")
7181                    .substitute('A', 'y',
7182                                'D', 'x',
7183                                'e', '1'))
7184            .equal("yyxxcx1"));
7185 }
7186 
7187 // test const + immutable storage groups
7188 @safe pure unittest
7189 {
7190     import std.algorithm.comparison : equal;
7191 
7192     auto xyz_abc(T)(T value)
7193     {
7194         immutable a = "a";
7195         const b = "b";
7196         auto c = "c";
7197         return value.substitute!("x", a,
7198                                  "y", b,
7199                                  "z", c);
7200     }
7201     assert(xyz_abc("_x").equal("_a"));
7202     assert(xyz_abc(".y.").equal(".b."));
7203     assert(xyz_abc("z").equal("c"));
7204     assert(xyz_abc("w").equal("w"));
7205 }
7206 
7207 // test with narrow strings (auto-decoding) and subranges
7208 @safe pure unittest
7209 {
7210     import std.algorithm.comparison : equal;
7211 
7212     assert("äöü€".substitute("ä", "b", "ü", "u").equal("böu€"));
7213     assert("äöü€".substitute!("ä", "b", "ü", "u").equal("böu€"));
7214     assert("ä...öü€".substitute("ä", "b", "ü", "u").equal("b...öu€"));
7215 
7216     auto expected = "emoticons😄😅.😇😈Rock";
7217     assert("emoticons😄😅😆😇😈rock"
7218             .substitute("r", "R", "😆", ".").equal(expected));
7219     assert("emoticons😄😅😆😇😈rock"
7220             .substitute!("r", "R", "😆", ".").equal(expected));
7221 }
7222 
7223 // test with narrow strings (auto-decoding) and single elements
7224 @safe pure unittest
7225 {
7226     import std.algorithm.comparison : equal;
7227 
7228     assert("äöü€".substitute('ä', 'b', 'ü', 'u').equal("böu€"));
7229     assert("äöü€".substitute!('ä', 'b', 'ü', 'u').equal("böu€"));
7230 
7231     auto expected = "emoticons😄😅.😇😈Rock";
7232     assert("emoticons😄😅😆😇😈rock"
7233             .substitute('r', 'R', '😆', '.').equal(expected));
7234     assert("emoticons😄😅😆😇😈rock"
7235             .substitute!('r', 'R', '😆', '.').equal(expected));
7236 }
7237 
7238 // test auto-decoding {n,w,d} strings X {n,w,d} strings
7239 @safe pure unittest
7240 {
7241     import std.algorithm.comparison : equal;
7242 
7243     assert("ääöü€".substitute("ä", "b", "ü", "u").equal("bböu€"));
7244     assert("ääöü€".substitute("ä"w, "b"w, "ü"w, "u"w).equal("bböu€"));
7245     assert("ääöü€".substitute("ä"d, "b"d, "ü"d, "u"d).equal("bböu€"));
7246 
7247     assert("ääöü€"w.substitute("ä", "b", "ü", "u").equal("bböu€"));
7248     assert("ääöü€"w.substitute("ä"w, "b"w, "ü"w, "u"w).equal("bböu€"));
7249     assert("ääöü€"w.substitute("ä"d, "b"d, "ü"d, "u"d).equal("bböu€"));
7250 
7251     assert("ääöü€"d.substitute("ä", "b", "ü", "u").equal("bböu€"));
7252     assert("ääöü€"d.substitute("ä"w, "b"w, "ü"w, "u"w).equal("bböu€"));
7253     assert("ääöü€"d.substitute("ä"d, "b"d, "ü"d, "u"d).equal("bböu€"));
7254 
7255     // auto-decoding is done before by a different range
7256     assert("ääöü€".filter!(a => true).substitute("ä", "b", "ü", "u").equal("bböu€"));
7257     assert("ääöü€".filter!(a => true).substitute("ä"w, "b"w, "ü"w, "u"w).equal("bböu€"));
7258     assert("ääöü€".filter!(a => true).substitute("ä"d, "b"d, "ü"d, "u"d).equal("bböu€"));
7259 }
7260 
7261 // test repeated replacement
7262 @safe pure nothrow unittest
7263 {
7264     import std.algorithm.comparison : equal;
7265 
7266     assert([1, 2, 3, 1, 1, 2].substitute(1, 0).equal([0, 2, 3, 0, 0, 2]));
7267     assert([1, 2, 3, 1, 1, 2].substitute!(1, 0).equal([0, 2, 3, 0, 0, 2]));
7268     assert([1, 2, 3, 1, 1, 2].substitute(1, 2, 2, 9).equal([2, 9, 3, 2, 2, 9]));
7269 }
7270 
7271 // test @nogc for single element replacements
7272 @safe @nogc unittest
7273 {
7274     import std.algorithm.comparison : equal;
7275 
7276     static immutable arr = [1, 2, 3, 1, 1, 2];
7277     static immutable expected = [0, 2, 3, 0, 0, 2];
7278 
7279     assert(arr.substitute!(1, 0).equal(expected));
7280     assert(arr.substitute(1, 0).equal(expected));
7281 }
7282 
7283 // test different range types
7284 @safe pure nothrow unittest
7285 {
7286     import std.algorithm.comparison : equal;
7287     import std.internal.test.dummyrange : AllDummyRanges;
7288 
7289     static foreach (DummyType; AllDummyRanges)
7290     {{
7291         DummyType dummyRange;
7292 
7293         // single substitution
7294         dummyRange.substitute (2, 22).equal([1, 22, 3, 4, 5, 6, 7, 8, 9, 10]);
7295         dummyRange.substitute!(2, 22).equal([1, 22, 3, 4, 5, 6, 7, 8, 9, 10]);
7296 
7297         // multiple substitution
7298         dummyRange.substitute (2, 22, 5, 55, 7, 77).equal([1, 22, 3, 4, 55, 6, 77, 8, 9, 10]);
7299         dummyRange.substitute!(2, 22, 5, 55, 7, 77).equal([1, 22, 3, 4, 55, 6, 77, 8, 9, 10]);
7300     }}
7301 }
7302 
7303 // https://issues.dlang.org/show_bug.cgi?id=19207
7304 @safe pure nothrow unittest
7305 {
7306     import std.algorithm.comparison : equal;
7307     assert([1, 2, 3, 4].substitute([1], [7]).equal([7, 2, 3, 4]));
7308     assert([1, 2, 3, 4].substitute([2], [7]).equal([1, 7, 3, 4]));
7309     assert([1, 2, 3, 4].substitute([4], [7]).equal([1, 2, 3, 7]));
7310     assert([1, 2, 3, 4].substitute([2, 3], [7]).equal([1, 7, 4]));
7311     assert([1, 2, 3, 4].substitute([3, 4], [7, 8]).equal([1, 2, 7, 8]));
7312 }
7313 
7314 // tests recognizing empty base ranges
7315 nothrow pure @safe unittest
7316 {
7317     import std.utf : byCodeUnit;
7318     import std.algorithm.comparison : equal;
7319 
7320     assert("".byCodeUnit.substitute('4', 'A').empty);
7321     assert("".byCodeUnit.substitute('0', 'O', '5', 'S', '1', 'l').empty);
7322     assert("".byCodeUnit.substitute("PKM".byCodeUnit, "PoKeMon".byCodeUnit).empty);
7323     assert("".byCodeUnit.substitute
7324     (   "ding".byCodeUnit,
7325         "dong".byCodeUnit,
7326         "click".byCodeUnit,
7327         "clack".byCodeUnit,
7328         "ping".byCodeUnit,
7329         "latency".byCodeUnit
7330     ).empty);
7331 }
7332 
7333 // sum
7334 /**
7335 Sums elements of `r`, which must be a finite
7336 $(REF_ALTTEXT input range, isInputRange, std,range,primitives). Although
7337 conceptually `sum(r)` is equivalent to $(LREF fold)!((a, b) => a +
7338 b)(r, 0), `sum` uses specialized algorithms to maximize accuracy,
7339 as follows.
7340 
7341 $(UL
7342 $(LI If $(REF ElementType, std,range,primitives)!R is a floating-point
7343 type and `R` is a
7344 $(REF_ALTTEXT random-access range, isRandomAccessRange, std,range,primitives) with
7345 length and slicing, then `sum` uses the
7346 $(HTTP en.wikipedia.org/wiki/Pairwise_summation, pairwise summation)
7347 algorithm.)
7348 $(LI If `ElementType!R` is a floating-point type and `R` is a
7349 finite input range (but not a random-access range with slicing), then
7350 `sum` uses the $(HTTP en.wikipedia.org/wiki/Kahan_summation,
7351 Kahan summation) algorithm.)
7352 $(LI In all other cases, a simple element by element addition is done.)
7353 )
7354 
7355 For floating point inputs, calculations are made in
7356 $(DDLINK spec/type, Types, `real`)
7357 precision for `real` inputs and in `double` precision otherwise
7358 (Note this is a special case that deviates from `fold`'s behavior,
7359 which would have kept `float` precision for a `float` range).
7360 For all other types, the calculations are done in the same type obtained
7361 from from adding two elements of the range, which may be a different
7362 type from the elements themselves (for example, in case of
7363 $(DDSUBLINK spec/type,integer-promotions, integral promotion)).
7364 
7365 A seed may be passed to `sum`. Not only will this seed be used as an initial
7366 value, but its type will override all the above, and determine the algorithm
7367 and precision used for summation. If a seed is not passed, one is created with
7368 the value of `typeof(r.front + r.front)(0)`, or `typeof(r.front + r.front).zero`
7369 if no constructor exists that takes an int.
7370 
7371 Note that these specialized summing algorithms execute more primitive operations
7372 than vanilla summation. Therefore, if in certain cases maximum speed is required
7373 at expense of precision, one can use `fold!((a, b) => a + b)(r, 0)`, which
7374 is not specialized for summation.
7375 
7376 Params:
7377     seed = the initial value of the summation
7378     r = a finite input range
7379 
7380 Returns:
7381     The sum of all the elements in the range r.
7382  */
7383 auto sum(R)(R r)
7384 if (isInputRange!R && !isInfinite!R && is(typeof(r.front + r.front)))
7385 {
7386     alias E = Unqual!(ElementType!R);
7387     static if (isFloatingPoint!E)
7388         alias Seed = typeof(E.init  + 0.0); //biggest of double/real
7389     else
7390         alias Seed = typeof(r.front + r.front);
7391     static if (is(typeof(Unqual!Seed(0))))
7392         enum seedValue = Unqual!Seed(0);
7393     else static if (is(typeof({ Unqual!Seed tmp = Seed.zero; })))
7394         enum Unqual!Seed seedValue = Seed.zero;
7395     else
7396         static assert(false,
7397             "Could not initiate an initial value for " ~ (Unqual!Seed).stringof
7398             ~ ". Please supply an initial value manually.");
7399     return sum(r, seedValue);
7400 }
7401 /// ditto
7402 auto sum(R, E)(R r, E seed)
7403 if (isInputRange!R && !isInfinite!R && is(typeof(seed = seed + r.front)))
7404 {
7405     static if (isFloatingPoint!E)
7406     {
7407         static if (hasLength!R && hasSlicing!R)
7408         {
7409             if (r.empty) return seed;
7410             return seed + sumPairwise!E(r);
7411         }
7412         else
7413             return sumKahan!E(seed, r);
7414     }
7415     else
7416     {
7417         return reduce!"a + b"(seed, r);
7418     }
7419 }
7420 
7421 /// Ditto
7422 @safe pure nothrow unittest
7423 {
7424     import std.range;
7425 
7426     //simple integral sumation
7427     assert(sum([ 1, 2, 3, 4]) == 10);
7428 
7429     //with integral promotion
7430     assert(sum([false, true, true, false, true]) == 3);
7431     assert(sum(ubyte.max.repeat(100)) == 25500);
7432 
7433     //The result may overflow
7434     assert(uint.max.repeat(3).sum()           ==  4294967293U );
7435     //But a seed can be used to change the sumation primitive
7436     assert(uint.max.repeat(3).sum(ulong.init) == 12884901885UL);
7437 
7438     //Floating point sumation
7439     assert(sum([1.0, 2.0, 3.0, 4.0]) == 10);
7440 
7441     //Floating point operations have double precision minimum
7442     static assert(is(typeof(sum([1F, 2F, 3F, 4F])) == double));
7443     assert(sum([1F, 2, 3, 4]) == 10);
7444 
7445     //Force pair-wise floating point sumation on large integers
7446     import std.math.operations : isClose;
7447     assert(iota(ulong.max / 2, ulong.max / 2 + 4096).sum(0.0)
7448                .isClose((ulong.max / 2) * 4096.0 + 4096^^2 / 2));
7449 }
7450 
7451 // Pairwise summation http://en.wikipedia.org/wiki/Pairwise_summation
7452 private auto sumPairwise(F, R)(R data)
7453 if (isInputRange!R && !isInfinite!R)
7454 {
7455     import core.bitop : bsf;
7456     // Works for r with at least length < 2^^(64 + log2(16)), in keeping with the use of size_t
7457     // elsewhere in std.algorithm and std.range on 64 bit platforms. The 16 in log2(16) comes
7458     // from the manual unrolling in sumPairWise16
7459     F[64] store = void;
7460     size_t idx = 0;
7461 
7462     void collapseStore(T)(T k)
7463     {
7464         auto lastToKeep = idx - cast(uint) bsf(k+1);
7465         while (idx > lastToKeep)
7466         {
7467             store[idx - 1] += store[idx];
7468             --idx;
7469         }
7470     }
7471 
7472     static if (hasLength!R)
7473     {
7474         foreach (k; 0 .. data.length / 16)
7475         {
7476             static if (isRandomAccessRange!R && hasSlicing!R)
7477             {
7478                 store[idx] = sumPairwise16!F(data);
7479                 data = data[16 .. data.length];
7480             }
7481             else store[idx] = sumPairwiseN!(16, false, F)(data);
7482 
7483             collapseStore(k);
7484             ++idx;
7485         }
7486 
7487         size_t i = 0;
7488         foreach (el; data)
7489         {
7490             store[idx] = el;
7491             collapseStore(i);
7492             ++idx;
7493             ++i;
7494         }
7495     }
7496     else
7497     {
7498         size_t k = 0;
7499         while (!data.empty)
7500         {
7501             store[idx] = sumPairwiseN!(16, true, F)(data);
7502             collapseStore(k);
7503             ++idx;
7504             ++k;
7505         }
7506     }
7507 
7508     F s = store[idx - 1];
7509     foreach_reverse (j; 0 .. idx - 1)
7510         s += store[j];
7511 
7512     return s;
7513 }
7514 
7515 private auto sumPairwise16(F, R)(R r)
7516 if (isRandomAccessRange!R)
7517 {
7518     return (((cast(F) r[ 0] + r[ 1]) + (cast(F) r[ 2] + r[ 3]))
7519           + ((cast(F) r[ 4] + r[ 5]) + (cast(F) r[ 6] + r[ 7])))
7520          + (((cast(F) r[ 8] + r[ 9]) + (cast(F) r[10] + r[11]))
7521           + ((cast(F) r[12] + r[13]) + (cast(F) r[14] + r[15])));
7522 }
7523 
7524 private auto sumPair(bool needEmptyChecks, F, R)(ref R r)
7525 if (isForwardRange!R && !isRandomAccessRange!R)
7526 {
7527     static if (needEmptyChecks) if (r.empty) return F(0);
7528     F s0 = r.front;
7529     r.popFront();
7530     static if (needEmptyChecks) if (r.empty) return s0;
7531     s0 += r.front;
7532     r.popFront();
7533     return s0;
7534 }
7535 
7536 private auto sumPairwiseN(size_t N, bool needEmptyChecks, F, R)(ref R r)
7537 if (isForwardRange!R && !isRandomAccessRange!R)
7538 {
7539     import std.math.traits : isPowerOf2;
7540     static assert(isPowerOf2(N), "N must be a power of 2");
7541     static if (N == 2) return sumPair!(needEmptyChecks, F)(r);
7542     else return sumPairwiseN!(N/2, needEmptyChecks, F)(r)
7543         + sumPairwiseN!(N/2, needEmptyChecks, F)(r);
7544 }
7545 
7546 // Kahan algo http://en.wikipedia.org/wiki/Kahan_summation_algorithm
7547 private auto sumKahan(Result, R)(Result result, R r)
7548 {
7549     static assert(isFloatingPoint!Result && isMutable!Result, "The type of"
7550             ~ " Result must be a mutable floating point, not "
7551             ~ Result.stringof);
7552     Result c = 0;
7553     for (; !r.empty; r.popFront())
7554     {
7555         immutable y = r.front - c;
7556         immutable t = result + y;
7557         c = (t - result) - y;
7558         result = t;
7559     }
7560     return result;
7561 }
7562 
7563 @safe pure nothrow unittest
7564 {
7565     static assert(is(typeof(sum([cast( byte) 1])) ==  int));
7566     static assert(is(typeof(sum([cast(ubyte) 1])) ==  int));
7567     static assert(is(typeof(sum([  1,   2,   3,   4])) ==  int));
7568     static assert(is(typeof(sum([ 1U,  2U,  3U,  4U])) == uint));
7569     static assert(is(typeof(sum([ 1L,  2L,  3L,  4L])) ==  long));
7570     static assert(is(typeof(sum([1UL, 2UL, 3UL, 4UL])) == ulong));
7571 
7572     int[] empty;
7573     assert(sum(empty) == 0);
7574     assert(sum([42]) == 42);
7575     assert(sum([42, 43]) == 42 + 43);
7576     assert(sum([42, 43, 44]) == 42 + 43 + 44);
7577     assert(sum([42, 43, 44, 45]) == 42 + 43 + 44 + 45);
7578 }
7579 
7580 @safe pure nothrow unittest
7581 {
7582     static assert(is(typeof(sum([1.0, 2.0, 3.0, 4.0])) == double));
7583     static assert(is(typeof(sum([ 1F,  2F,  3F,  4F])) == double));
7584     const(float[]) a = [1F, 2F, 3F, 4F];
7585     assert(sum(a) == 10F);
7586     static assert(is(typeof(sum(a)) == double));
7587 
7588     double[] empty;
7589     assert(sum(empty) == 0);
7590     assert(sum([42.]) == 42);
7591     assert(sum([42., 43.]) == 42 + 43);
7592     assert(sum([42., 43., 44.]) == 42 + 43 + 44);
7593     assert(sum([42., 43., 44., 45.5]) == 42 + 43 + 44 + 45.5);
7594 }
7595 
7596 @safe pure nothrow unittest
7597 {
7598     import std.container;
7599     static assert(is(typeof(sum(SList!float()[])) == double));
7600     static assert(is(typeof(sum(SList!double()[])) == double));
7601     static assert(is(typeof(sum(SList!real()[])) == real));
7602 
7603     assert(sum(SList!double()[]) == 0);
7604     assert(sum(SList!double(1)[]) == 1);
7605     assert(sum(SList!double(1, 2)[]) == 1 + 2);
7606     assert(sum(SList!double(1, 2, 3)[]) == 1 + 2 + 3);
7607     assert(sum(SList!double(1, 2, 3, 4)[]) == 10);
7608 }
7609 
7610 // https://issues.dlang.org/show_bug.cgi?id=12434
7611 @safe pure nothrow unittest
7612 {
7613     immutable a = [10, 20];
7614     auto s1 = sum(a);
7615     assert(s1 == 30);
7616     auto s2 = a.map!(x => x).sum;
7617     assert(s2 == 30);
7618 }
7619 
7620 @system unittest
7621 {
7622     import std.bigint;
7623     import std.range;
7624 
7625     immutable BigInt[] a = BigInt("1_000_000_000_000_000_000").repeat(10).array();
7626     immutable ulong[]  b = (ulong.max/2).repeat(10).array();
7627     auto sa = a.sum();
7628     auto sb = b.sum(BigInt(0)); //reduce ulongs into bigint
7629     assert(sa == BigInt("10_000_000_000_000_000_000"));
7630     assert(sb == (BigInt(ulong.max/2) * 10));
7631 }
7632 
7633 @safe pure nothrow @nogc unittest
7634 {
7635     import std.range;
7636     foreach (n; iota(50))
7637         assert(repeat(1.0, n).sum == n);
7638 }
7639 
7640 // Issue 19525
7641 @safe unittest
7642 {
7643     import std.datetime : Duration, minutes;
7644     assert([1.minutes].sum() == 1.minutes);
7645 }
7646 
7647 /**
7648 Finds the mean (colloquially known as the average) of a range.
7649 
7650 For built-in numerical types, accurate Knuth & Welford mean calculation
7651 is used. For user-defined types, element by element summation is used.
7652 Additionally an extra parameter `seed` is needed in order to correctly
7653 seed the summation with the equivalent to `0`.
7654 
7655 The first overload of this function will return `T.init` if the range
7656 is empty. However, the second overload will return `seed` on empty ranges.
7657 
7658 This function is $(BIGOH r.length).
7659 
7660 Params:
7661     T = The type of the return value.
7662     r = An $(REF_ALTTEXT input range, isInputRange, std,range,primitives)
7663     seed = For user defined types. Should be equivalent to `0`.
7664 
7665 Returns:
7666     The mean of `r` when `r` is non-empty.
7667 */
7668 T mean(T = double, R)(R r)
7669 if (isInputRange!R &&
7670     isNumeric!(ElementType!R) &&
7671     !isInfinite!R)
7672 {
7673     if (r.empty)
7674         return T.init;
7675 
7676     Unqual!T meanRes = 0;
7677     size_t i = 1;
7678 
7679     // Knuth & Welford mean calculation
7680     // division per element is slower, but more accurate
7681     for (; !r.empty; r.popFront())
7682     {
7683         T delta = r.front - meanRes;
7684         meanRes += delta / i++;
7685     }
7686 
7687     return meanRes;
7688 }
7689 
7690 /// ditto
7691 auto mean(R, T)(R r, T seed)
7692 if (isInputRange!R &&
7693     !isNumeric!(ElementType!R) &&
7694     is(typeof(r.front + seed)) &&
7695     is(typeof(r.front / size_t(1))) &&
7696     !isInfinite!R)
7697 {
7698     import std.algorithm.iteration : sum, reduce;
7699 
7700     // per item division vis-a-vis the previous overload is too
7701     // inaccurate for integer division, which the user defined
7702     // types might be representing
7703     static if (hasLength!R)
7704     {
7705         if (r.length == 0)
7706             return seed;
7707 
7708         return sum(r, seed) / r.length;
7709     }
7710     else
7711     {
7712         import std.typecons : tuple;
7713 
7714         if (r.empty)
7715             return seed;
7716 
7717         auto pair = reduce!((a, b) => tuple(a[0] + 1, a[1] + b))
7718             (tuple(size_t(0), seed), r);
7719         return pair[1] / pair[0];
7720     }
7721 }
7722 
7723 ///
7724 @safe @nogc pure nothrow unittest
7725 {
7726     import std.math.operations : isClose;
7727     import std.math.traits : isNaN;
7728 
7729     static immutable arr1 = [1, 2, 3];
7730     static immutable arr2 = [1.5, 2.5, 12.5];
7731 
7732     assert(arr1.mean.isClose(2));
7733     assert(arr2.mean.isClose(5.5));
7734 
7735     assert(arr1[0 .. 0].mean.isNaN);
7736 }
7737 
7738 @safe pure nothrow unittest
7739 {
7740     import std.internal.test.dummyrange : ReferenceInputRange;
7741     import std.math.operations : isClose;
7742 
7743     auto r1 = new ReferenceInputRange!int([1, 2, 3]);
7744     assert(r1.mean.isClose(2));
7745 
7746     auto r2 = new ReferenceInputRange!double([1.5, 2.5, 12.5]);
7747     assert(r2.mean.isClose(5.5));
7748 }
7749 
7750 // Test user defined types
7751 @system pure unittest
7752 {
7753     import std.bigint : BigInt;
7754     import std.internal.test.dummyrange : ReferenceInputRange;
7755     import std.math.operations : isClose;
7756 
7757     auto bigint_arr = [BigInt("1"), BigInt("2"), BigInt("3"), BigInt("6")];
7758     auto bigint_arr2 = new ReferenceInputRange!BigInt([
7759         BigInt("1"), BigInt("2"), BigInt("3"), BigInt("6")
7760     ]);
7761     assert(bigint_arr.mean(BigInt(0)) == BigInt("3"));
7762     assert(bigint_arr2.mean(BigInt(0)) == BigInt("3"));
7763 
7764     BigInt[] bigint_arr3 = [];
7765     assert(bigint_arr3.mean(BigInt(0)) == BigInt(0));
7766 
7767     struct MyFancyDouble
7768     {
7769        double v;
7770        alias v this;
7771     }
7772 
7773     // both overloads
7774     auto d_arr = [MyFancyDouble(10), MyFancyDouble(15), MyFancyDouble(30)];
7775     assert(mean!(double)(cast(double[]) d_arr).isClose(18.33333333));
7776     assert(mean(d_arr, MyFancyDouble(0)).isClose(18.33333333));
7777 }
7778 
7779 // uniq
7780 /**
7781 Lazily iterates unique consecutive elements of the given range, which is
7782 assumed to be sorted (functionality akin to the
7783 $(HTTP wikipedia.org/wiki/_Uniq, _uniq) system
7784 utility). Equivalence of elements is assessed by using the predicate
7785 `pred`, by default `"a == b"`. The predicate is passed to
7786 $(REF binaryFun, std,functional), and can either accept a string, or any callable
7787 that can be executed via `pred(element, element)`. If the given range is
7788 bidirectional, `uniq` also yields a
7789 $(REF_ALTTEXT bidirectional range, isBidirectionalRange, std,range,primitives).
7790 
7791 Params:
7792     pred = Predicate for determining equivalence between range elements.
7793     r = An $(REF_ALTTEXT input range, isInputRange, std,range,primitives) of
7794         elements to filter.
7795 
7796 Returns:
7797     An $(REF_ALTTEXT input range, isInputRange, std,range,primitives) of
7798     consecutively unique elements in the original range. If `r` is also a
7799     forward range or bidirectional range, the returned range will be likewise.
7800 */
7801 auto uniq(alias pred = "a == b", Range)(Range r)
7802 if (isInputRange!Range && is(typeof(binaryFun!pred(r.front, r.front)) == bool))
7803 {
7804     return UniqResult!(binaryFun!pred, Range)(r);
7805 }
7806 
7807 ///
7808 @safe unittest
7809 {
7810     import std.algorithm.comparison : equal;
7811     import std.algorithm.mutation : copy;
7812 
7813     int[] arr = [ 1, 2, 2, 2, 2, 3, 4, 4, 4, 5 ];
7814     assert(equal(uniq(arr), [ 1, 2, 3, 4, 5 ][]));
7815 
7816     // Filter duplicates in-place using copy
7817     arr.length -= arr.uniq().copy(arr).length;
7818     assert(arr == [ 1, 2, 3, 4, 5 ]);
7819 
7820     // Note that uniqueness is only determined consecutively; duplicated
7821     // elements separated by an intervening different element will not be
7822     // eliminated:
7823     assert(equal(uniq([ 1, 1, 2, 1, 1, 3, 1]), [1, 2, 1, 3, 1]));
7824 }
7825 
7826 private struct UniqResult(alias pred, Range)
7827 {
7828     Range _input;
7829 
7830     this(Range input)
7831     {
7832         _input = input;
7833     }
7834 
7835     auto opSlice()
7836     {
7837         return this;
7838     }
7839 
7840     void popFront()
7841     {
7842         assert(!empty, "Attempting to popFront an empty uniq.");
7843         auto last = _input.front;
7844         do
7845         {
7846             _input.popFront();
7847         }
7848         while (!_input.empty && pred(last, _input.front));
7849     }
7850 
7851     @property ElementType!Range front()
7852     {
7853         assert(!empty, "Attempting to fetch the front of an empty uniq.");
7854         return _input.front;
7855     }
7856 
7857     static if (isBidirectionalRange!Range)
7858     {
7859         void popBack()
7860         {
7861             assert(!empty, "Attempting to popBack an empty uniq.");
7862             auto last = _input.back;
7863             do
7864             {
7865                 _input.popBack();
7866             }
7867             while (!_input.empty && pred(last, _input.back));
7868         }
7869 
7870         @property ElementType!Range back()
7871         {
7872             assert(!empty, "Attempting to fetch the back of an empty uniq.");
7873             return _input.back;
7874         }
7875     }
7876 
7877     static if (isInfinite!Range)
7878     {
7879         enum bool empty = false;  // Propagate infiniteness.
7880     }
7881     else
7882     {
7883         @property bool empty() { return _input.empty; }
7884     }
7885 
7886     static if (isForwardRange!Range)
7887     {
7888         @property typeof(this) save() {
7889             return typeof(this)(_input.save);
7890         }
7891     }
7892 }
7893 
7894 @safe unittest
7895 {
7896     import std.algorithm.comparison : equal;
7897     import std.internal.test.dummyrange;
7898     import std.range;
7899 
7900     int[] arr = [ 1, 2, 2, 2, 2, 3, 4, 4, 4, 5 ];
7901     auto r = uniq(arr);
7902     static assert(isForwardRange!(typeof(r)));
7903 
7904     assert(equal(r, [ 1, 2, 3, 4, 5 ][]));
7905     assert(equal(retro(r), retro([ 1, 2, 3, 4, 5 ][])));
7906 
7907     foreach (DummyType; AllDummyRanges)
7908     {
7909         DummyType d;
7910         auto u = uniq(d);
7911         assert(equal(u, [1,2,3,4,5,6,7,8,9,10]));
7912 
7913         static assert(d.rt == RangeType.Input || isForwardRange!(typeof(u)));
7914 
7915         static if (d.rt >= RangeType.Bidirectional)
7916         {
7917             assert(equal(retro(u), [10,9,8,7,6,5,4,3,2,1]));
7918         }
7919     }
7920 }
7921 
7922 // https://issues.dlang.org/show_bug.cgi?id=17264
7923 @safe unittest
7924 {
7925     import std.algorithm.comparison : equal;
7926 
7927     const(int)[] var = [0, 1, 1, 2];
7928     assert(var.uniq.equal([0, 1, 2]));
7929 }
7930 
7931 /**
7932 Lazily computes all _permutations of `r` using $(HTTP
7933 en.wikipedia.org/wiki/Heap%27s_algorithm, Heap's algorithm).
7934 
7935 Params:
7936     Range = the range type
7937     r = the $(REF_ALTTEXT random access range, isRandomAccessRange, std,range,primitives)
7938     to find the permutations for.
7939 Returns:
7940     A $(REF_ALTTEXT forward range, isForwardRange, std,range,primitives)
7941     of elements of which are an $(REF indexed, std,range) view into `r`.
7942 
7943 See_Also:
7944 $(REF nextPermutation, std,algorithm,sorting).
7945 */
7946 Permutations!Range permutations(Range)(Range r)
7947 {
7948     static assert(isRandomAccessRange!Range, Range.stringof,
7949             " must be a RandomAccessRange");
7950     static assert(hasLength!Range, Range.stringof
7951             , " must have a length");
7952 
7953     return typeof(return)(r);
7954 }
7955 
7956 /// ditto
7957 struct Permutations(Range)
7958 {
7959     static assert(isRandomAccessRange!Range, Range.stringof,
7960             " must be a RandomAccessRange");
7961     static assert(hasLength!Range, Range.stringof
7962             , " must have a length");
7963 
7964     private size_t[] _indices, _state;
7965     private Range _r;
7966     private bool _empty;
7967 
7968     ///
7969     this(Range r)
7970     {
7971         import std.array : array;
7972         import std.range : iota;
7973 
7974         this._r = r;
7975         _state = r.length ? new size_t[r.length-1] : null;
7976         _indices = iota(size_t(r.length)).array;
7977         _empty = r.length == 0;
7978     }
7979     private this(size_t[] indices, size_t[] state, Range r, bool empty_)
7980     {
7981         _indices = indices;
7982         _state = state;
7983         _r = r;
7984         _empty = empty_;
7985     }
7986     /// Returns: `true` if the range is empty, `false` otherwise.
7987     @property bool empty() const pure nothrow @safe @nogc
7988     {
7989         return _empty;
7990     }
7991 
7992     /// Returns: the front of the range
7993     @property auto front()
7994     {
7995         import std.range : indexed;
7996         return _r.indexed(_indices);
7997     }
7998 
7999     ///
8000     void popFront()
8001     {
8002         void next(int n)
8003         {
8004             import std.algorithm.mutation : swap;
8005 
8006             if (n > _indices.length)
8007             {
8008                 _empty = true;
8009                 return;
8010             }
8011 
8012             if (n % 2 == 1)
8013                 swap(_indices[0], _indices[n-1]);
8014             else
8015                 swap(_indices[_state[n-2]], _indices[n-1]);
8016 
8017             if (++_state[n-2] == n)
8018             {
8019                 _state[n-2] = 0;
8020                 next(n+1);
8021             }
8022         }
8023 
8024         next(2);
8025     }
8026     /// Returns: an independent copy of the permutations range.
8027     auto save()
8028     {
8029         return typeof(this)(_indices.dup, _state.dup, _r.save, _empty);
8030     }
8031 }
8032 
8033 ///
8034 @safe unittest
8035 {
8036     import std.algorithm.comparison : equal;
8037     import std.range : iota;
8038     assert(equal!equal(iota(3).permutations,
8039         [[0, 1, 2],
8040          [1, 0, 2],
8041          [2, 0, 1],
8042          [0, 2, 1],
8043          [1, 2, 0],
8044          [2, 1, 0]]));
8045 }
8046 
8047 @safe unittest
8048 {
8049     import std.algorithm.comparison : equal;
8050     import std.range : ElementType;
8051     import std.array : array;
8052     auto p = [1, 2, 3].permutations;
8053     auto x = p.save.front;
8054     p.popFront;
8055     auto y = p.front;
8056     assert(x != y);
8057 }