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 = ⦥
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 }