Unofficial Dub Package Documentation 
1 #!/usr/bin/env rdmd-dev-module
2 
3 /** Extensions to std.algorithm.
4     Copyright: Per Nordlöw 2014-.
5     License: $(WEB boost.org/LICENSE_1_0.txt, Boost License 1.0).
6     Authors: $(WEB Per Nordlöw)
7 */
8 module algorithm_ex;
9 
10 /* version = print; */
11 
12 import std.algorithm : min, max;
13 import std.traits : isArray, Unqual, isIntegral, CommonType, isIterable, isStaticArray, isFloatingPoint, arity, isSomeString, isSomeChar, isExpressionTuple;
14 import std.range : ElementType, isInputRange, isForwardRange, isBidirectionalRange, isRandomAccessRange, front;
15 import traits_ex : allSameType;
16 import std.functional : unaryFun, binaryFun;
17 import std.algorithm.searching : find;
18 
19 version(print) import dbg;
20 
21 auto typestringof(T)(in T a) { return T.stringof; }
22 
23 import std.range : dropOne;
24 alias tail = dropOne;
25 
26 /** Returns: First Argument (element of $(D a)) whose implicit conversion to
27     bool is true.
28 
29     Similar to behaviour of or operator in dynamic languages such as Lisp's (or
30     a...) and Python's a or ....
31 
32     TODO Is inout Conversion!T the correct return value?
33 
34     NOTE: Lazy parameters are currently marked as throw which makes it
35     impossible to mark either() as nothrow. Issue at
36     https://issues.dlang.org/show_bug.cgi?id=12647
37 */
38 CommonType!Ts either(Ts...)(lazy Ts a)
39     if (a.length >= 1)
40 {
41     auto a0 = a[0]();           // evaluate only once
42     static if (Ts.length == 1)
43     {
44         return a0;
45     }
46     else
47     {
48         return a0 ? a0 : either(a[1 .. $]); // recurse
49     }
50 }
51 
52 T either_r(T)(lazy T a)
53 {
54     return a;
55 }
56 
57 CommonType!(A, Bs) either_r(A, Bs...)(lazy A a, lazy Bs bs)
58     if (bs.length >= 1)
59 {
60     auto a_ = a();
61     return a_ ? a_ : either_r(bs);
62 }
63 
64 /** This overload enables, when possible, lvalue return.
65     TODO should we limit this template to a.length >= 2
66  */
67 auto ref either(Ts...)(ref Ts a)
68     if (a.length >= 1 && allSameType!Ts)
69 {
70     static if (Ts.length == 1)
71     {
72         return a[0];
73     }
74     else
75     {
76         return a[0] ? a[0] : either(a[1 .. $]); // recurse
77     }
78 }
79 @safe pure /*TODO nothrow*/ unittest
80 {
81     immutable p = 1, q = 2;
82     auto pq = either(p, q);
83     assert(pq == 1);
84 
85     assert(either(3) == 3);
86     assert(either(3, 4) == 3);
87     assert(either(0, 4) == 4);
88     assert(either(0, 0) == 0);
89     assert(either(``, `a`) == ``);
90     string s = null;
91     assert(either(s, `a`) == `a`);
92     assert(either(`a`, ``) == `a`);
93     immutable a2 = [1, 2];
94     assert(either(a2) == a2);
95     assert(either([0, 1], [1, 2]) == [0, 1]);
96     assert(either([0, 1], [1]) == [0, 1]);
97     assert(either(`a`, `b`) == `a`);
98 
99     int x = 1, y = 2;
100     either(x, y) = 3;
101     assert(x == 3);
102     assert(y == 2);
103 }
104 
105 /** Returns: Last Argument if all arguments implicitly bool-convert to true
106     otherwise CommonType!T.init.
107 
108     Similar to behaviour and operator in dynamic languages such as of Lisp's
109     (and a...) and Python's a and ....
110 
111     TODO Is inout Conversion!T the correct return value?
112 */
113 CommonType!T every(T...)(lazy T a)
114     if (T.length >= 1)
115 {
116     auto a0 = a[0]();           // evaluate only once
117     static if (T.length == 1)
118     {
119         return a0;
120     }
121     else
122     {
123         return a0 ? every(a[1 .. $]) : CommonType!T.init; // recurse
124     }
125 }
126 
127 @safe pure /*TODO nothrow*/ unittest
128 {
129     assert(every(3) == 3);
130     assert(every(3, 4) == 4);
131     assert(every(0, 4) == 0);
132     assert(every(0, 0) == 0);
133     assert(every([0, 1], [1, 2]) == [1, 2]);
134     assert(every([0, 1], [1]) == [1]);
135     assert(every(`a`, `b`) == `b`);
136     assert(every(``, `b`) == `b`);
137     assert(every(cast(string)null, `b`) == cast(string)null);
138 }
139 
140 version(none) // WARNING disabled because I don't see any use of this for.
141 {
142     /** This overload enables, when possible, lvalue return.
143     */
144     auto ref every(T...)(ref T a)
145     if (T.length >= 1 && allSameType!T)
146     {
147         static if (T.length == 1)
148         {
149             return a[0];
150         }
151         else
152         {
153             return a[0] ? every(a[1 .. $]) : a[0]; // recurse
154         }
155     }
156 
157     unittest
158     {
159         immutable p = 1, q = 2;
160         assert(every(p, q) == 2);
161 
162         int x = 1, y = 2;
163         every(x, y) = 3;
164         assert(x == 1);
165         assert(y == 3);
166     }
167 }
168 
169 /** Evaluate all $(D parts) possibly digesting $(D whole).
170     If all values of $(D parts) implicitly convert to bool true return the
171     values as an array, otherwise restore whole and return null.
172 */
173 CommonType!T[] tryEvery(S, T...)(ref S whole,
174                                  lazy T parts)
175     if (T.length >= 1)
176 {
177     auto wholeBackup = whole;
178     bool all = true;
179     alias R = typeof(return);
180     R results;
181     foreach (result; parts) // evaluate each part
182     {
183         if (result)
184         {
185             results ~= result;
186         }
187         else
188         {
189             all = false;
190             break;
191         }
192     }
193     if (all)
194     {
195         return results;        // ok that whole has been changed in caller scope
196     }
197     else
198     {
199         whole = wholeBackup; // restore whole in caller scope if any failed
200         return R.init;
201     }
202 }
203 
204 unittest
205 {
206     auto whole = `xyz`;
207     import std.algorithm: skipOver;
208 
209     assert(whole.tryEvery(whole.skipOver('x'),
210                           whole.skipOver('z')) == []); // failing match
211     assert(whole == `xyz`); // should restore whole
212 
213     assert(whole.tryEvery(whole.skipOver('x'),
214                           whole.skipOver('y'),
215                           whole.skipOver('w')) == []); // failing match
216     assert(whole == `xyz`); // should restore whole
217 
218     assert(whole.tryEvery(whole.skipOver('x'),
219                           whole.skipOver('y')) == [true, true]); // successful match
220     assert(whole == `z`); // should digest matching part
221 }
222 
223 import std.traits : isInstanceOf;
224 
225 /** Returns: Minimum Element in $(D range).
226     See also: http://forum.dlang.org/thread/jufggxqwzhlsmhshtnfj@forum.dlang.org?page=3
227  */
228 auto minElement(alias F = min, R)(in R range)
229     if (isInputRange!R)
230 {
231     import std.algorithm : reduce;
232     import std.range : SortedRange;
233     enum M = ElementType!R.max;
234 
235     // TODO Expose predFun in SortedRange so we can check with static if (R.predFun == binaryFun!`a < b`)
236     // TODO or add members minElement and maxElement to SortedRange that wraps this logic.
237 
238     // static if (isInstanceOf!(SortedRange, R))
239     // {
240     //     return r.empty ? M : r.front;
241     // }
242     // else static if (isInstanceOf!(SortedRange, R))
243     // {
244     //     return r.empty ? M : r.back; // TODO if R has member back (R.Range isBidirectionalRange)
245     // }
246     // else
247     // {
248     //     return reduce!F(M, range);
249     // }
250     return reduce!F(M, range);
251 }
252 alias smallest = minElement;
253 unittest { assert([4, 1, 2, 3].minElement == 1); }
254 
255 /** Returns: Maximum Element in X.
256     See also: http://forum.dlang.org/thread/jufggxqwzhlsmhshtnfj@forum.dlang.org?page=3
257 */
258 auto maxElement(alias F = max, R)(in R range)
259     if (isInputRange!R)
260 {
261     import std.algorithm : reduce;
262     return reduce!F(ElementType!R.min, range);
263 }
264 alias largest = maxElement;
265 unittest { assert([4, 1, 2, 3].maxElement == 4); }
266 
267 /** Returns: Minmum and Maximum Element in X. */
268 auto minmaxElement(alias F = min, alias G = max, R)(in R range)
269     if (isInputRange!R)
270 {
271     import std.typecons : tuple;
272     import std.algorithm : reduce;
273     return reduce!(F, G)(tuple(Unqual!(ElementType!R).max,
274                                Unqual!(ElementType!R).min), range);
275 }
276 unittest { assert([1, 2, 3].minmaxElement == tuple(1, 3)); }
277 
278 import std.typecons : Nullable;
279 
280 /** Returns: true iff $(D a) has a value containing meaningful information.
281  */
282 bool hasContents(T)(in T a) // @safe @nogc pure nothrow
283 {
284     static if (isInstanceOf!(Nullable, T))
285         return !a.isNull;
286     else static if (isArray!T || isSomeString!T)
287         return cast(bool)a.length; // see: http://stackoverflow.com/questions/18563414/empty-string-should-implicit-convert-to-bool-true/18566334?noredirect=1#18566334
288     else
289         return cast(bool)a;
290 }
291 
292 /** Reset $(D a) to its default value.
293     See also: std.typecons.Nullable.nullify
294  */
295 auto ref reset(T)(ref T a) @trusted // pure nothrow
296 {
297     static if (isInstanceOf!(Nullable, T))
298         a.nullify();
299     else
300         return a = T.init;
301 }
302 unittest {
303     int x = 42;
304     x.reset;
305     assert(x == x.init);
306 }
307 
308 unittest
309 {
310     import std.typecons : Nullable;
311     auto n = Nullable!(size_t,
312                        size_t.max)();
313     import predicates : isUntouched;
314     assert(n.isUntouched);
315     n = 0;
316     assert(!n.isUntouched);
317     assert(n == 0);
318     n.reset;
319     assert(n.isUntouched);
320 }
321 
322 import std.typecons : Tuple, tuple;
323 
324 /** Find $(D needles) In Order in $(D haystack). */
325 auto findInOrder(alias pred = `a == b`,
326                  alias finder = find,
327                  R,
328                  E...)(R haystack,
329                        E needles) /* @trusted pure nothrow */
330 {
331     import std.range : empty;
332     auto hit = haystack; // reference
333     foreach (needle; needles) // for every needle in order
334     {
335         hit = finder!pred(hit, needle);
336         if (hit.empty)
337         {
338             break;
339         }
340     }
341     return hit;
342 }
343 unittest
344 {
345     import std.range : empty;
346     assert(`a b c`.findInOrder(`a`, `b`, `c`));
347     assert(`b a`.findInOrder(`a`, `b`).empty);
348 }
349 
350 /** Returns: Slice Overlap of $(D a) and $(D b) in order given by arguments.
351  */
352 inout(T[]) overlapInOrder(T)(inout(T[]) a,
353                              inout(T[]) b) /* @trusted pure nothrow */
354 {
355     if (a.ptr <= b.ptr &&       // if a-start lies at or before b-start
356         b.ptr < a.ptr + a.length) // if b-start lies before b-end
357     {
358         import std.algorithm: min, max;
359         const low = max(a.ptr, b.ptr) - a.ptr;
360         const n = min(b.length,
361                       (b.ptr - a.ptr + 1)); // overlap length
362         return a[low..low + n];
363     }
364     else
365     {
366         return [];
367     }
368 }
369 
370 /** Returns: Slice Overlap of $(D a) and $(D b) in any order.
371     Deprecated by: std.array.overlap
372  */
373 inout(T[]) overlap(T)(inout(T[]) a,
374                       inout(T[]) b) /* @safe pure nothrow */
375 {
376     if (inout(T[]) ab = overlapInOrder(a, b))
377     {
378         return ab;
379     }
380     else if (inout(T[]) ba = overlapInOrder(b, a))
381     {
382         return ba;
383     }
384     else
385     {
386         return [];
387     }
388 }
389 
390 unittest
391 {
392     auto x = [-11_111, 11, 22, 333_333];
393     const y = [-22_222, 441, 555, 66];
394 
395     assert(!overlap(x, y));
396     assert(!overlap(y, x));
397 
398     auto x01 = x[0..1];
399     auto x12 = x[1..2];
400     auto x23 = x[2..3];
401 
402     // sub-ranges should overlap completely
403     assert(overlap(x, x12) == x12);
404     assert(overlap(x, x01) == x01);
405     assert(overlap(x, x23) == x23);
406     // and commutate f(a,b) == f(b,a)
407     assert(overlap(x01, x) == x01);
408     assert(overlap(x12, x) == x12);
409     assert(overlap(x23, x) == x23);
410 }
411 
412 /** Helper for overlap().
413     Copied from std.array with simplified return expression.
414  */
415 bool overlaps(T)(const(T)[] r1, const(T)[] r2) @trusted // pure nothrow
416 {
417     alias U = inout(T);
418     static U* max(U* a, U* b) nothrow { return a > b ? a : b; }
419     static U* min(U* a, U* b) nothrow { return a < b ? a : b; }
420 
421     auto b = max(r1.ptr, r2.ptr);
422     auto e = min(r1.ptr + r1.length,
423                  r2.ptr + r2.length);
424     return b < e;
425 }
426 
427 /** Returns: If range is a palindrome larger than $(D minLength).
428     See also: http://forum.dlang.org/thread/dlfeiszyweafpjiocplf@forum.dlang.org#post-vpzuaqxvtdpzpeuorxdl:40forum.dlang.org
429     See also: https://stackoverflow.com/questions/21849580/equality-operator-in-favour-of-std-range-equal
430     TODO: Test graphemes in `string` and `wstring`.
431 */
432 bool isSymmetric(R)(R range, size_t minLength = 0) // TODO good value for minLength?
433     if (isBidirectionalRange!(R))
434 {
435     static if (isRandomAccessRange!R) // arrays excluding `char[]` and `wchar[]`
436     {
437         if (range.length < minLength) { return false; }
438     }
439     size_t i = 0;
440     import std.range : empty;
441     while (!range.empty)
442     {
443         import std.range.primitives: front, back, popFront, popBack;
444         if (range.front != range.back) return false;
445         range.popFront(); i++;
446         if (range.empty) break;
447         range.popBack(); i++;
448     }
449     return i >= minLength;
450 }
451 
452 unittest
453 {
454     assert(`dallassallad`.isSymmetric);
455     assert(!`ab`.isSymmetric);
456     assert(`a`.isSymmetric);
457     assert(`åäå`.isSymmetric);
458     assert(`áá`.isSymmetric);
459     assert(`åäå`.isSymmetric(3));
460     assert(!`åäå`.isSymmetric(4));
461     assert(``.isSymmetric);
462     assert([1, 2, 2, 1].isSymmetric);
463     assert(![1, 2, 2, 1].isSymmetric(5));
464 }
465 alias isPalindrome = isSymmetric;
466 
467 import traits_ex : areEquable;
468 
469 /** Return true if $(D s1) is an Anagram of $(D s2).
470     Equal arguments are not considered to be an anagrams of each other.
471 
472     TODO Is there a faster way of calculating anagrams?
473     TODO Allow const input
474     TODO Move to std.algorithm.sorting.
475     TODO Should requirement isInputRange be relaxed?
476 
477     Note that implementations in http://rosettacode.org/wiki/Anagrams#D doesn't
478     correctly handle multi-byte encoded characters in string and wstring.
479  */
480 auto isAnagramOf(R1, R2)(R1 r1, R2 r2) // TODO nothrow
481     if (isInputRange!R1 &&
482         isInputRange!R2 &&
483         areEquable!(ElementType!R1,
484                     ElementType!R2))
485 {
486     const sortLimit = 0;
487     import std.range : empty;
488     if (r1.empty || r2.empty) { return false; }
489     if (r1.length + r2.length < sortLimit)
490     {
491         import std.algorithm.comparison : equal;
492         import sort_ex : sorted;
493         return equal(r1.sorted,
494                      r2.sorted);
495     }
496     else
497     {
498         alias E1 = ElementType!R1;
499         alias E2 = ElementType!R2;
500         alias C = CommonType!(E1, E2);
501 
502         alias T = Tuple!(size_t, // R1 histogram bin count
503                          size_t); // R2 histogram bin count
504 
505         import std.traits : isNarrowString;
506         import std.utf : byUTF;
507 
508         // TODO functionize
509         static if (isNarrowString!R1)
510             auto s1 = r1.byUTF!dchar;
511         else
512             auto s1 = r1;
513 
514         static if (isNarrowString!R2)
515             auto s2 = r2.byUTF!dchar;
516         else
517             auto s2 = r2;
518 
519         // histogram
520         T[C] hist;              // TODO use non-GC-allocating AA
521 
522         // create histograms
523         foreach (const ref e1; s1)
524         {
525             // TODO functionize to hist.initOrUpdate(e1, T(0,1), (ref AA aa){ aa[0] += 1; })
526             if (auto hit = e1 in hist)
527                 (*hit)[0] += 1;
528             else
529                 hist[e1] = T(1, 0);
530         }
531         foreach (const ref e2; s2)
532         {
533             // TODO functionize to hist.initOrUpdate(e2, T(0,1), (ref AA aa){ aa[1] += 1; })
534             if (auto hit = e2 in hist)
535                 (*hit)[1] += 1;
536             else
537                 hist[e2] = T(0, 1);
538         }
539 
540         // check histograms
541         foreach (const ref e; hist) // TODO nothrow
542         {
543             if (e[0] != e[1])
544             {
545                 return false;
546             }
547         }
548         return true;
549     }
550 }
551 alias isPermutationOf = isAnagramOf; // TODO Only define isAnagramOf for strings?
552 
553 ///
554 @safe pure unittest // TODO nothrow
555 {
556     assert([1, 2, 3, 4, 5].isPermutationOf([1, 2, 4, 5, 3]));
557     assert(![1, 2, 3, 4, 5].isPermutationOf([1, 4, 5, 3]));
558 }
559 
560 ///
561 @safe pure unittest
562 {
563     assert(!``w.isAnagramOf(``));
564     assert(`äöå`w.isAnagramOf(`åäö`));
565     assert(`äöå`.isAnagramOf(`åäö`w));
566     assert(`äöå`w.isAnagramOf(`åäö`w));
567 
568     assert(`äöå`d.isAnagramOf(`åäö`));
569     assert(`äöå`.isAnagramOf(`åäö`d));
570     assert(`äöå`d.isAnagramOf(`åäö`d));
571 }
572 
573 ///
574 @safe pure unittest
575 {
576     assert(`äöå`.isAnagramOf(`åäö`));
577     assert(!`äöå`.isAnagramOf(`xyz`));
578     assert(!`äöå`.isAnagramOf(``));
579     assert(!``.isAnagramOf(`åäö`));
580 }
581 @safe pure unittest
582 {
583     assert(`xyzxyzxyzxyzxyzxyzxyzxyz`.isAnagramOf(`xyzxyzxyzxyzxyzxyzxyzxyz`));
584     assert(`xyzxyzxyzxyzxyzxyzxyzxyz`.isAnagramOf(`xxyyzzxxyyzzxxyyzzxxyyzz`));
585 }
586 
587 ///
588 @safe pure unittest
589 {
590     import std.conv: to;
591 
592     auto x = `äöå`.to!(dchar[]);
593 
594     auto y = sort(x);
595     alias Y = typeof(y);
596 
597     const z = `åäö`;
598 
599     assert(y.isAnagramOf(z));
600     assert(z.isAnagramOf(y));
601 }
602 
603 /* ref Unqual!T unqual(T)(in T x) pure nothrow if isStuct!T { return cast(Unqual!T)x; } */
604 /* unittest { */
605 /*     const int x; */
606 /*     unqual(x) = 1; */
607 /* } */
608 
609 enum Reduction
610 {
611     forwardDifference,
612     backwardDifference,
613     sum,
614 }
615 
616 /** Generalized Windowed Reduce.
617     See also: https://stackoverflow.com/questions/21004944/forward-difference-algorithm
618     See also: http://forum.dlang.org/thread/ujouqtqeehkegmtaxebg@forum.dlang.org#post-lczzsypupcfigttghkwx:40forum.dlang.org
619     See also: http://rosettacode.org/wiki/Forward_difference#D
620 */
621 auto ref windowedReduce(Reduction reduction = Reduction.forwardDifference, R)(R range)
622     if (isInputRange!R)
623 {
624     import std.algorithm.iteration: map;
625     import std.range: zip, dropOne;
626     auto ref op(T)(T a, T b) @safe pure nothrow
627     {
628         static      if (reduction == Reduction.forwardDifference)  return b - a; // TODO final static switch
629         else static if (reduction == Reduction.backwardDifference) return a - b;
630         else static if (reduction == Reduction.sum)                return a + b;
631     }
632     return range.zip(range.dropOne).map!(a => op(a[0], a[1])); // a is a tuple here
633 }
634 // NOTE: Disabled for now because this solution cannot be made nothrow
635 /* auto ref windowedReduce(Reduction reduction = Reduction.forwardDifference, uint N = 0, R)(R range) */
636 /*     @safe pure /\* nothrow *\/ if (isInputRange!R) */
637 /* { */
638 /*     auto ref helper(R range) @safe pure /\* nothrow *\/ { */
639 /*         import std.algorithm.iteration: map; */
640 /*         import std.range: zip, dropOne; */
641 /*         //  Note: that a[0] and a[1] indexes Zip tuple */
642 /*         static if (reduction == Reduction.forwardDifference) */
643 /*             return range.zip(range.dropOne).map!(a => a[1] - a[0]); */
644 /*         static if (reduction == Reduction.backwardDifference) */
645 /*             return range.zip(range.dropOne).map!(a => a[0] - a[1]); */
646 /*         static if (reduction == Reduction.sum) */
647 /*             return range.zip(range.dropOne).map!(a => a[0] + a[1]); */
648 /*     } */
649 /*     static if (N != 0) { */
650 /*         return windowedReduce!(reduction, N - 1)(helper(range)); */
651 /*     } else { */
652 /*         return helper(range); */
653 /*     } */
654 /* } */
655 
656 /* unittest { */
657 /*     import std.range: front; */
658 /*     dln([1].windowedReduce!(Reduction.forwardDifference)); */
659 /*     dln([1, 22].windowedReduce!(Reduction.forwardDifference)); */
660 /*     dln([1, 22, 333].windowedReduce!(Reduction.forwardDifference)); */
661 /* } */
662 
663 unittest
664 {
665     import std.datetime: Clock, SysTime, Duration;
666     import std.algorithm.iteration: map;
667     SysTime[] times;
668     const n = 4;
669     foreach (i; 0..n)
670         times ~= Clock.currTime;
671     version(print) dln(times);
672     auto spans = times.windowedReduce!(Reduction.forwardDifference);
673     version(print) dln(spans);
674     // dln(*(cast(ulong*)&(spans.front)));
675     version(print) dln(Duration.sizeof);
676 }
677 
678 @safe pure unittest
679 {
680     immutable i = [1, 4, 9, 17];
681     import std.algorithm: equal;
682     assert(i.windowedReduce!(Reduction.forwardDifference).equal ([+3, +5, +8]));
683     assert(i.windowedReduce!(Reduction.backwardDifference).equal([-3, -5, -8]));
684     assert(i.windowedReduce!(Reduction.sum).equal ([+5, +13, +26]));
685     assert([1].windowedReduce.empty);
686     version(print) dln(i.windowedReduce!(Reduction.sum));
687 }
688 
689 /* TODO Assert that ElementType!R only value semantics.  */
690 auto ref packBitParallelRunLengths(R)(in R x)
691     if (isInputRange!R)
692 {
693     import std.bitmanip: BitArray;
694     import core.bitop: bt;
695     alias E = ElementType!R; // element type
696     enum nBits = 8*E.sizeof;
697 
698     BitArray[nBits] runs;
699 
700     // allocate runs
701     foreach (ref run; runs)
702     {
703         run.length = x.length;
704     }
705 
706     /* string toString() @property @trusted const { */
707     /*     typeof(return) y; */
708     /*     import std.conv: to; */
709     /*     foreach (run; runs) { */
710     /*         y ~= run.to!string ~ "\n"; */
711     /*     } */
712     /*     return y; */
713     /* } */
714 
715     /* size_t[nBits] counts; */
716 
717     import bitset: BitSet;
718     foreach (eltIx, elt; x)
719     {
720         /* BitSet!nBits bits; */
721         foreach (bitIndex; 0..nBits)
722         {
723             import bitop_ex: getBit;
724             runs[bitIndex][eltIx] = elt.getBit(bitIndex);
725         }
726     }
727     return runs;
728 }
729 alias packBPRL = packBitParallelRunLengths;
730 
731 pure unittest
732 {
733     /* import backtrace.backtrace; */
734     /* import std.stdio: stderr; */
735     /* backtrace.backtrace.install(stderr); */
736     const x = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10];
737     const xPacked = x.packBitParallelRunLengths;
738     version(print) dln(xPacked);
739 }
740 
741 /** Compute Forward Difference of $(D range).
742 
743     TODO Is there a difference between whether R r is immutable, const or
744     mutable?
745 
746     TODO If r contains only one element return empty range.
747 
748     See also: https://stackoverflow.com/questions/21004944/forward-difference-algorithm
749     See also: http://forum.dlang.org/thread/ujouqtqeehkegmtaxebg@forum.dlang.org#post-lczzsypupcfigttghkwx:40forum.dlang.org
750     See also: http://rosettacode.org/wiki/Forward_difference#D
751 */
752 auto forwardDifference(R)(R r)
753     if (isInputRange!R)
754 {
755     import std.range: front, empty, popFront, dropOne;
756 
757     struct ForwardDifference
758     {
759         R _range;
760         alias E = ElementType!R;                       // Input ElementType
761         alias D = typeof(_range.front - _range.front); // Element Difference Type. TODO Use this as ElementType of range
762         D _front;
763         bool _initialized = false;
764 
765         this(R range) in { assert(!range.empty); }
766         body
767         {
768             auto tmp = range;
769             if (tmp.dropOne.empty) // TODO This may be an unneccesary cost but is practical to remove extra logic
770                 _range = R.init; // return empty range
771             else
772                 _range = range; // store range internally (by reference)
773         }
774 
775         @property:
776         auto ref front()
777         {
778             if (!_initialized) { popFront(); }
779             return _front;
780         }
781         auto ref moveFront()
782         {
783             popFront();
784             return _front;
785         }
786         void popFront()
787         {
788             if (empty is false)
789             {
790                 _initialized = true;
791                 E rf = _range.front;
792                 _range.popFront();
793                 if (_range.empty is false)
794                 {
795                     _front = _range.front - rf;
796                 }
797             }
798         }
799         bool empty()
800         {
801             return _range.empty;
802         }
803     }
804 
805     return ForwardDifference(r);
806 }
807 
808 unittest
809 {
810     import msgpack;
811     import std.array: array;
812 
813     auto x = [long.max, 0, 1];
814     auto y = x.forwardDifference;
815 
816     version(print) dln(y);
817     version(print) dln(y.pack);
818     version(print) dln(y.array.pack);
819 }
820 
821 import std.traits: isCallable, ReturnType, arity, ParameterTypeTuple;
822 import traits_ex: arityMin0;
823 
824 /** Create Range of Elements Generated by $(D fun).
825 
826     Use for example to generate random instances of return value of fun.
827 
828     TODO I believe we need arityMin, arityMax trait here
829 */
830 auto apply(alias fun, N)(N n)
831     if (// TODO isCallable!fun &&
832         arityMin0!fun &&
833         !is(ReturnType!fun == void) &&
834         isIntegral!N)
835 {
836     import std.range: iota;
837     import std.algorithm.iteration: map;
838     return n.iota.map!(n => fun);
839 }
840 
841 unittest
842 {
843     import std.datetime: Clock, SysTime, Duration;
844     import std.algorithm.iteration: map;
845     import std.array: array;
846     const n = 3;
847     auto times = n.apply!(Clock.currTime).array;
848     version(print) dln(times);
849     auto spans = times.forwardDifference;
850     version(print) dln(spans);
851 }
852 
853 /** In Place Ordering (in Sorted Order) of all Elements $(D t).
854     See also: https://stackoverflow.com/questions/21102646/in-place-ordering-of-elements/
855     See also: http://forum.dlang.org/thread/eweortsmcmibppmvtriw@forum.dlang.org#post-eweortsmcmibppmvtriw:40forum.dlang.org
856 */
857 void orderInPlace(T...)(ref T t) @trusted
858 {
859     import std.algorithm: sort, swap;
860     static if (t.length == 2)
861     {
862         if (t[0] > t[1])
863         {
864             swap(t[0], t[1]);
865         }
866     }
867     else
868     {                           // generic version
869         T[0][T.length] buffer;      // static buffer to capture elements
870         foreach (idx, a; t)
871             buffer[idx] = a;
872         auto sorted = sort(buffer[]);
873         foreach (idx, a; t)
874             t[idx] = sorted[idx];
875     }
876 }
877 unittest {
878     auto x = 2, y = 1;
879     orderInPlace(x, y);
880     assert(x == 1);
881     assert(y == 2);
882 }
883 unittest {
884     auto x = 3, y = 1, z = 2;
885     orderInPlace(x, y, z);
886     assert(x == 1);
887     assert(y == 2);
888     assert(z == 3);
889 }
890 
891 import std.algorithm: SwapStrategy;
892 
893 /** Allow Static Arrays to be sorted without [].
894     See also: http://forum.dlang.org/thread/jhzurojjnlkatjdgcfhg@forum.dlang.org
895 */
896 template sort(alias less = `a < b`, SwapStrategy ss = SwapStrategy.unstable)
897 {
898     import std.algorithm: stdSort = sort;
899     auto sort(Arr)(ref Arr arr)
900         if (isStaticArray!Arr)
901     {
902         return stdSort!(less, ss)(arr[]);
903     }
904     auto sort(Range)(Range r)
905         if (!isStaticArray!Range)
906     {
907         return stdSort!(less, ss)(r);
908     }
909 }
910 unittest
911 {
912     int[5] a = [ 9, 5, 1, 7, 3 ];
913     int[]  b = [ 4, 2, 1, 6, 3 ];
914     sort(a);
915     sort(b);
916 }
917 
918 /** Stable Variant of Quick Sort.
919     See also: http://forum.dlang.org/thread/gjuvmrypvxeebvztszpr@forum.dlang.org
920 */
921 auto ref stableSort(T)(auto ref T a) pure
922     if (isRandomAccessRange!T)
923 {
924     if (a.length >= 2)
925     {
926         import std.algorithm: partition3, sort;
927         auto parts = partition3(a, a[$ / 2]); // mid element as pivot
928         parts[0].sort();
929         parts[2].sort();
930     }
931     return a;
932 }
933 
934 unittest
935 {
936     import random_ex: randInPlace;
937     const n = 2^^16;
938     auto a = new int[n];
939     a.randInPlace;
940     auto b = a.dup;
941     a[].stableSort;
942     import std.algorithm: sort;
943     sort(b);
944     assert(a == b);
945 }
946 
947 /** Execute Expression $(D expr) the same way $(D n) times. */
948 void doTimes(uint n, lazy void expr)
949 {
950     while (n--) expr();
951 }
952 
953 /** Execute Expression $(D expr) $(I inline) the same way $(D n) times.
954     $(D n) must be a constant known at compile time.
955 */
956 void doTimes(uint n)(lazy void expr)
957 {
958     import range_ex: iota;
959     foreach (i; iota!(0, n)) expr();
960 }
961 
962 unittest
963 {
964     int i = 0;
965     doTimes!4(i++);
966     assert(i == 4);
967 }
968 
969 alias loop = doTimes;
970 alias doN = doTimes;
971 alias repeat = doTimes;
972 
973 /** Execute Expression $(D action) the same way $(D n) times. */
974 void times(alias action, N)(N n)
975     if (isCallable!action &&
976         isIntegral!N &&
977         arity!action <= 1)
978 {
979     static if (arity!action == 1 && // if one argument and
980                isIntegral!(ParameterTypeTuple!action[0])) // its an integer
981     {
982         foreach (i; 0 .. n)
983             action(i); // use it as action input
984     }
985     else
986     {
987         foreach (i; 0 .. n)
988             action();
989     }
990 }
991 
992 unittest
993 {
994     enum n = 10;
995     int sum = 0;
996     10.times!({ sum++; });
997     assert(sum == n);
998 }
999 
1000 private string genNaryFun(string fun, V...)() @safe pure
1001 {
1002     string code;
1003     import std.string: format;
1004     foreach (n, v; V)
1005         code ~= "alias values[%d] %s;".format(n, cast(char)('a'+n));
1006     code ~= `return ` ~ fun ~ `;`;
1007     return code;
1008 }
1009 template naryFun(string fun)
1010 {
1011     auto naryFun(V...)(V values)
1012     {
1013         mixin(genNaryFun!(fun, V));
1014     }
1015 }
1016 unittest {
1017     alias test = naryFun!`a + b + c`;
1018     assert(test(1, 2, 3) == 6);
1019 }
1020 
1021 import std.typetuple : allSatisfy;
1022 
1023 /** Zip $(D ranges) together with operation $(D fun).
1024     TODO Remove when Issue 8715 is fixed providing zipWith
1025 */
1026 auto zipWith(alias fun, Ranges...)(Ranges ranges)
1027     if (Ranges.length >= 2 &&
1028         allSatisfy!(isInputRange, Ranges))
1029 {
1030     import std.range: zip;
1031     import std.algorithm.iteration: map;
1032     static if (ranges.length < 2)
1033         static assert(false, `Need at least 2 range arguments.`);
1034     else static if (ranges.length == 2)
1035         return zip(ranges).map!(a => binaryFun!fun(a.expand));
1036     else
1037         return zip(ranges).map!(a => naryFun!fun(a.expand));
1038     // return zip(ranges).map!(a => fun(a.expand));
1039 }
1040 unittest {
1041     auto x = [1, 2, 3];
1042     import std.array: array;
1043     assert(zipWith!`a+b`(x, x).array == [2, 4, 6]);
1044     assert(zipWith!((a, b) => a + b)(x, x).array == [2, 4, 6]);
1045     assert(zipWith!`a+b+c`(x, x, x).array == [3, 6, 9]);
1046 }
1047 
1048 auto zipWith(fun, StoppingPolicy, Ranges...)(StoppingPolicy sp,
1049                                              Ranges ranges)
1050     if (Ranges.length &&
1051         allSatisfy!(isInputRange, Ranges))
1052 {
1053     import std.range: zip;
1054     import std.algorithm.iteration: map;
1055     return zip(sp, ranges).map!fun;
1056 }
1057 
1058 /** Pair. TODO std.typecons */
1059 alias Pair(T, U) = Tuple!(T, U);
1060 /** Instantiator for $(D Pair). */
1061 auto pair(T, U)(in T t, in U u) { return Pair!(T, U)(t, u); }
1062 
1063 /** Triple. TODO std.typecons */
1064 alias Triple(T, U, V) = Tuple!(T, U, V);
1065 /** Instantiator for $(D Triple). */
1066 auto triple(T, U, V)(in T t, in U u, in V v) { return Triple!(T, U, V)(t, u, v); }
1067 
1068 /** Quadruple. TODO std.typecons */
1069 alias Quadruple(T, U, V, W) = Tuple!(T, U, V, W);
1070 /** Instantiator for $(D Quadruple). */
1071 auto quadruple(T, U, V, W)(in T t, in U u, in V v, in W w) { return Quadruple!(T, U, V, W)(t, u, v, w); }
1072 
1073 /** Limit/Span (Min,Max) Pair.
1074     Todo: Decide on either Span, MinMax or Limits
1075     See also: https://stackoverflow.com/questions/21241878/generic-span-type-in-phobos
1076 */
1077 struct Limits(T)
1078 {
1079     import std.algorithm: min, max;
1080 
1081     @property @safe pure:
1082 
1083     /** Expand Limits to include $(D a). */
1084     auto ref include(in T a) nothrow {
1085         _lims[0] = min(_lims[0], a);
1086         _lims[1] = max(_lims[1], a);
1087         return this;
1088     }
1089     alias expand = include;
1090 
1091     auto ref reset() nothrow {
1092         _lims[0] = T.max;
1093         _lims[1] = T.min;
1094     }
1095 
1096     string toString() const {
1097         import std.conv: to;
1098         return (`[` ~ to!string(_lims[0]) ~
1099                 `...` ~ to!string(_lims[1]) ~ `]`) ;
1100     }
1101 
1102     auto _lims = tuple(T.max, T.min);
1103 
1104     alias _lims this;
1105 }
1106 
1107 auto limits(T)() { return Limits!T(); }
1108 unittest {
1109     /* import std.file: SysTime; */
1110     /* SysTime st; */
1111     Limits!int x;
1112     x.expand(-10);
1113     x.expand(10);
1114     assert(x[0] == -10);
1115     assert(x[1] == +10);
1116     version(print) dln(x);
1117 }
1118 
1119 /* import rational: Rational; */
1120 
1121 /* template getTypeString(T) { */
1122 /*     static if (is(T == Rational)) */
1123 /*         string getTypeString(T)() @safe pure nothrow { */
1124 /*             return x`211A`; */
1125 /*         } */
1126 /* } */
1127 /* unittest { */
1128 /*     import rational: Rational; */
1129 /*     dln(getTypeString!Rational); */
1130 /* } */
1131 
1132 /** Check if $(D a) and $(D b) are colinear. */
1133 bool areColinear(T)(T a, T b)
1134 {
1135     // a and b are colinear if a.x / a.y == b.x / b.y
1136     // We can avoid the division by multiplying out.
1137     return a.x * b.y == a.y * b.x;
1138 }
1139 
1140 /* /\** TODO Remove when each is standard in Phobos. *\/ */
1141 /* void each(R)(R range, delegate x) @safe pure /\* nothrow *\/ if (isInputRange!R) { */
1142 /*     foreach (ref elt; range) { */
1143 /*         x(elt); */
1144 /*     } */
1145 /* } */
1146 /* unittest { */
1147 /*     version(print) [1, 2, 3, 4].each(a => dln(a)); */
1148 /* } */
1149 
1150 enum isIntLike(T) = is(typeof({T t = 0; t = t+t;})); // More if needed
1151 
1152 /** $(LUCKY Fibonacci) Numbers (Infinite Range).
1153     See also: http://forum.dlang.org/thread/dqlrfoxzsppylcgljyyf@forum.dlang.org#post-mailman.1072.1350619455.5162.digitalmars-d-learn:40puremagic.com
1154     See also: https://www.reddit.com/r/programming/comments/rif9x/uniform_function_call_syntax_for_the_d/
1155 */
1156 auto fibonacci(T = int)(T nth = 0)
1157     if (isIntLike!T)
1158 {
1159     struct Fibonacci
1160     {
1161         T a, b;
1162         T front() { return b; }
1163         void popFront()
1164         {
1165             T c = a+b;
1166             a = b;
1167             b = c;
1168         }
1169         bool empty() const { return false; }
1170     }
1171     return nth == 0 ? Fibonacci(0, 1) : Fibonacci(1, 1);
1172 }
1173 
1174 unittest
1175 {
1176     import std.range: take;
1177     import std.algorithm: equal;
1178     assert(fibonacci.take(10).equal([1, 1, 2, 3, 5, 8, 13, 21, 34, 55]));
1179     assert(1.fibonacci.take(9).equal([1, 2, 3, 5, 8, 13, 21, 34, 55]));
1180 }
1181 
1182 /** Expand Static $(D array) into a parameter arguments (AliasSeq!).
1183     See also: http://forum.dlang.org/thread/hwellpcaomwbpnpofzlx@forum.dlang.org?page=1
1184 */
1185 template expand(alias array, size_t idx = 0)
1186     if (isStaticArray!(typeof(array)))
1187 {
1188     @property ref delay() { return array[idx]; }
1189     static if (idx + 1 < array.length)
1190     {
1191         import std.meta : AliasSeq;
1192         alias expand = AliasSeq!(delay, expand!(array, idx + 1));
1193     }
1194     else
1195     {
1196         alias expand = delay;
1197     }
1198 }
1199 
1200 unittest
1201 {
1202     static void foo(int a, int b, int c)
1203     {
1204         import std.stdio: writefln;
1205         version(print) writefln("a: %s, b: %s, c: %s", a, b, c);
1206     }
1207     int[3] arr = [1, 2, 3];
1208     foo(expand!arr);
1209 }
1210 
1211 /** Python Style To-String-Conversion Alias. */
1212 string str(T)(in T a) @safe pure
1213 {
1214     import std.conv: to;
1215     return to!string(a);
1216 }
1217 
1218 /** Python Style Length Alias. */
1219 auto len(T)(in T a)
1220 {
1221     return a.length;
1222 }
1223 
1224 unittest
1225 {
1226     import std.algorithm.iteration: map;
1227     import std.array: array;
1228     assert(([42].map!str).array == [`42`]);
1229 }
1230 
1231 import std.range: InputRange, OutputRange;
1232 alias Source = InputRange; // nicer alias
1233 alias Sink = OutputRange; // nicer alias
1234 
1235 /* belongs to std.range */
1236 import std.range: cycle, retro;
1237 import std.functional: compose;
1238 alias retroCycle = compose!(cycle, retro);
1239 
1240 import std.traits: isAggregateType, hasMember;
1241 
1242 /** Generic Member Setter.
1243     See also: http://forum.dlang.org/thread/fdjkijrtduraaajlxxne@forum.dlang.org
1244 */
1245 auto ref T set(string member, T, U)(auto ref T a, in U value)
1246     if (isAggregateType!T &&
1247         hasMember!(T, member))
1248 {
1249     __traits(getMember, a, member) = value;
1250     return a;
1251 }
1252 
1253 unittest
1254 {
1255     class C { int x, y, z, w; }
1256     auto c = new C().set!`x`(11).set!`w`(44);
1257     assert(c.x == 11);
1258     assert(c.w == 44);
1259 }
1260 
1261 /* Check if $(D part) is part of $(D whole).
1262    See also: http://forum.dlang.org/thread/ls9dbk$jkq$1@digitalmars.com
1263    TODO Standardize name and remove alises.
1264    TODO Use partOf if generalized to InputRange.
1265  */
1266 bool sliceOf(T)(in T[] part,
1267                 in T[] whole)
1268 {
1269     return (whole.ptr <= part.ptr &&
1270             part.ptr + part.length <=
1271             whole.ptr + whole.length);
1272 }
1273 alias containedIn = sliceOf;
1274 alias partOf = sliceOf;
1275 alias coveredBy = sliceOf;
1276 alias includedIn = sliceOf;
1277 
1278 /* See also: http://forum.dlang.org/thread/cjpplpzdzebfxhyqtskw@forum.dlang.org#post-cjpplpzdzebfxhyqtskw:40forum.dlang.org */
1279 auto dropWhile(alias pred = `a == b`, R, E)(R range, E element)
1280     if (isInputRange!R &&
1281         is (typeof(binaryFun!pred(range.front, element)) : bool))
1282 {
1283     alias predFun = binaryFun!pred;
1284     return range.find!(a => !predFun(a, element));
1285 }
1286 alias dropAllOf = dropWhile;
1287 alias stripFront = dropWhile;
1288 alias lstrip = dropWhile;       // Python style
1289 
1290 import std.algorithm.searching: until;
1291 alias takeUntil = until;
1292 
1293 alias dropUntil = find;
1294 
1295 unittest
1296 {
1297     assert([1, 2, 3].dropWhile(1) == [2, 3]);
1298     assert([1, 1, 1, 2, 3].dropWhile(1) == [2, 3]);
1299     assert([1, 2, 3].dropWhile(2) == [1, 2, 3]);
1300     assert(`aabc`.dropWhile('a') == `bc`); // TODO Remove restriction on cast to dchar
1301 }
1302 
1303 /* See also: http://forum.dlang.org/thread/cjpplpzdzebfxhyqtskw@forum.dlang.org#post-cjpplpzdzebfxhyqtskw:40forum.dlang.org */
1304 auto takeWhile(alias pred = `a == b`, R, E)(R range, E element)
1305     if (isInputRange!R &&
1306         is (typeof(binaryFun!pred(range.front, element)) : bool))
1307 {
1308     import std.algorithm: until;
1309     alias predFun = binaryFun!pred;
1310     return range.until!(a => !predFun(a, element));
1311 }
1312 alias takeAllOf = takeWhile;
1313 
1314 unittest
1315 {
1316     import std.algorithm: equal;
1317     assert(equal([1, 1, 2, 3].takeWhile(1),
1318                  [1, 1]));
1319 }
1320 
1321 /** Simpler variant of Phobos' $(D split). */
1322 auto split(alias pred, R)(R haystack)
1323     if (isForwardRange!R)
1324 {
1325     import std.range : empty;
1326     static if (isSomeString!R ||
1327                isRandomAccessRange!R)
1328     {
1329         auto balance = find!pred(haystack);
1330         immutable pos1 = haystack.length - balance.length;
1331         immutable pos2 = balance.empty ? pos1 : pos1 + 1;
1332         return tuple(haystack[0 .. pos1],
1333                      haystack[pos1 .. pos2],
1334                      haystack[pos2 .. haystack.length]);
1335     }
1336     else
1337     {
1338         auto original = haystack.save;
1339         auto h = haystack.save;
1340         size_t pos1, pos2;
1341         while (!h.empty)
1342         {
1343             if (unaryFun!pred(h.front))
1344             {
1345                 h.popFront();
1346                 ++pos2;
1347             }
1348             else
1349             {
1350                 haystack.popFront();
1351                 h = haystack.save;
1352                 pos2 = ++pos1;
1353             }
1354         }
1355         return tuple(takeExactly(original, pos1),
1356                      takeExactly(haystack, pos2 - pos1),
1357                      h);
1358     }
1359 }
1360 
1361 unittest
1362 {
1363     import std.algorithm: equal;
1364     import std.ascii: isDigit;
1365     assert(`aa1bb`.split!(a => a.isDigit) == tuple(`aa`, `1`, `bb`));
1366     assert(`aa1`.split!(a => a.isDigit) == tuple(`aa`, `1`, ``));
1367     assert(`1bb`.split!(a => a.isDigit) == tuple(``, `1`, `bb`));
1368 }
1369 
1370 /** Simpler variant of Phobos' $(D splitBefore). */
1371 auto splitBefore(alias pred, R)(R haystack)
1372     if (isForwardRange!R)
1373 {
1374     static if (isSomeString!R ||
1375                sRandomAccessRange!R)
1376     {
1377         auto balance = find!pred(haystack);
1378         immutable pos = haystack.length - balance.length;
1379         return tuple(haystack[0 .. pos],
1380                      haystack[pos .. haystack.length]);
1381     }
1382     else
1383     {
1384         auto original = haystack.save;
1385         auto h = haystack.save;
1386         size_t pos;
1387         import std.range : empty;
1388         while (!h.empty)
1389         {
1390             if (unaryFun!pred(h.front))
1391             {
1392                 h.popFront();
1393             }
1394             else
1395             {
1396                 haystack.popFront();
1397                 h = haystack.save;
1398                 ++pos;
1399             }
1400         }
1401         return tuple(takeExactly(original, pos),
1402                      haystack);
1403     }
1404 }
1405 
1406 unittest
1407 {
1408     import std.algorithm: equal;
1409     import std.ascii: isDigit;
1410     assert(`11ab`.splitBefore!(a => !a.isDigit) == tuple(`11`, `ab`));
1411     assert(`ab`.splitBefore!(a => !a.isDigit) == tuple(``, `ab`));
1412 }
1413 
1414 auto splitAfter(alias pred, R)(R haystack)
1415     if (isForwardRange!R)
1416 {
1417     static if (isSomeString!R || isRandomAccessRange!R)
1418     {
1419         import std.range : empty;
1420         auto balance = find!pred(haystack);
1421         immutable pos = balance.empty ? 0 : haystack.length - balance.length + 1;
1422         return tuple(haystack[0 .. pos], haystack[pos .. haystack.length]);
1423     }
1424     else
1425     {
1426         static assert(false, `How to implement this?`);
1427         // import std.range : empty;
1428         /* auto original = haystack.save; */
1429         /* auto h = haystack.save; */
1430         /* size_t pos1, pos2; */
1431         /* while (!n.empty) */
1432         /* { */
1433         /*     if (h.empty) */
1434         /*     { */
1435         /*         // Failed search */
1436         /*         return tuple(takeExactly(original, 0), original); */
1437         /*     } */
1438         /*     if (binaryFun!pred(h.front, n.front)) */
1439         /*     { */
1440         /*         h.popFront(); */
1441         /*         n.popFront(); */
1442         /*         ++pos2; */
1443         /*     } */
1444         /*     else */
1445         /*     { */
1446         /*         haystack.popFront(); */
1447         /*         n = needle.save; */
1448         /*         h = haystack.save; */
1449         /*         pos2 = ++pos1; */
1450         /*     } */
1451         /* } */
1452         /* return tuple(takeExactly(original, pos2), h); */
1453     }
1454 }
1455 
1456 unittest
1457 {
1458     import std.algorithm: equal;
1459     import std.ascii: isDigit;
1460     assert(`aa1bb`.splitAfter!(a => a.isDigit) == tuple(`aa1`, `bb`));
1461     assert(`aa1`.splitAfter!(a => a.isDigit) == tuple(`aa1`, ``));
1462 }
1463 
1464 auto moveUntil(alias pred, R)(ref R r)
1465     if (isInputRange!R)
1466 {
1467     auto split = r.splitBefore!pred;
1468     r = split[1];
1469     return split[0];
1470 }
1471 
1472 unittest
1473 {
1474     auto r = `xxx111`;
1475     auto id = r.moveUntil!(a => a == '1');
1476     assert(id == `xxx`);
1477     assert(r == `111`);
1478 }
1479 
1480 auto moveWhile(alias pred, R)(ref R r)
1481     if (isInputRange!R)
1482 {
1483     return r.moveUntil!(a => !pred(a));
1484 }
1485 
1486 unittest
1487 {
1488     auto r = `xxx111`;
1489     auto id = r.moveWhile!(a => a == 'x');
1490     assert(id == `xxx`);
1491     assert(r == `111`);
1492 }
1493 
1494 /** Variant of $(D findSplitBefore) that destructively pops everything up to,
1495     not including, $(D needle) from $(D haystack).
1496 */
1497 auto findPopBefore(alias pred = `a == b`, R1, R2)(ref R1 haystack,
1498                                                   R2 needle)
1499     if (isForwardRange!R1 &&
1500         isForwardRange!R2)
1501 {
1502     import std.range : empty;
1503     if (haystack.empty || needle.empty)
1504     {
1505         return R1.init; // TODO correct?
1506     }
1507     import std.algorithm.searching : findSplitBefore;
1508     if (auto split = findSplitBefore!pred(haystack, needle)) // TODO If which case are empty and what return value should they lead to?
1509     {
1510         haystack = split[1];
1511         return split[0];
1512     }
1513     else
1514     {
1515         return R1.init; // TODO correct?
1516     }
1517 }
1518 
1519 unittest
1520 {
1521     auto haystack = `xy`;
1522     auto needle = `z`;
1523     auto pop = haystack.findPopBefore(needle);
1524     assert(pop == `xy`);
1525 }
1526 
1527 unittest
1528 {
1529     auto haystack = `xyz`;
1530     auto needle = `y`;
1531     auto pop = haystack.findPopBefore(needle);
1532     assert(pop == `x`);
1533     assert(haystack == `yz`);
1534 }
1535 
1536 /** Variant of $(D findSplitAfter) that destructively pops everything up to,
1537     including, $(D needle) from $(D haystack).
1538 */
1539 auto findPopAfter(alias pred = `a == b`, R1, R2)(ref R1 haystack,
1540                                                  R2 needle)
1541     if (isForwardRange!R1 &&
1542         isForwardRange!R2)
1543 {
1544     import std.range : empty;
1545     if (haystack.empty || needle.empty)
1546     {
1547         return R1.init; // TODO correct?
1548     }
1549     import std.algorithm.searching : findSplitAfter;
1550     auto split = findSplitAfter!pred(haystack, needle);// TODO use new interface to findSplitAfter
1551     if (split[0].empty)
1552     {
1553         return R1.init; // TODO correct?
1554     }
1555     else
1556     {
1557         haystack = split[1];
1558         return split[0];
1559     }
1560 }
1561 
1562 unittest
1563 {
1564     auto source = `xyz`;
1565     auto haystack = source;
1566     auto needle = `y`;
1567     auto pop = haystack.findPopAfter(needle);
1568     assert(pop == `xy`);
1569     assert(haystack == `z`);
1570 }
1571 
1572 unittest
1573 {
1574     auto source = `xy`;
1575     auto haystack = source;
1576     auto needle = `z`;
1577     auto pop = haystack.findPopAfter(needle);
1578     assert(pop is null);
1579     assert(!pop);
1580     assert(haystack == source);
1581 }
1582 
1583 /** Find First Occurrence any of $(D needles) in $(D haystack).
1584     Like to std.algorithm.find but takes an array of needles as argument instead
1585     of a variadic list of key needle arguments.
1586    Return found range plus index into needles starting at 1 upon.
1587  */
1588 Tuple!(R, size_t) findFirstOfAnyInOrder(alias pred = `a == b`, R)(R haystack, const R[] needles)
1589 {
1590     import std.algorithm: find;
1591     switch (needles.length)
1592     {
1593         case 1:
1594             import std.range : empty;
1595             auto hit = haystack.find(needles[0]);
1596             return tuple(hit, hit.empty ? 0UL : 1UL);
1597         case 2:
1598             return haystack.find(needles[0],
1599                                  needles[1]);
1600         case 3:
1601             return haystack.find(needles[0],
1602                                  needles[1],
1603                                  needles[2]);
1604         case 4:
1605             return haystack.find(needles[0],
1606                                  needles[1],
1607                                  needles[2],
1608                                  needles[3]);
1609         case 5:
1610             return haystack.find(needles[0],
1611                                  needles[1],
1612                                  needles[2],
1613                                  needles[3],
1614                                  needles[4]);
1615         case 6:
1616             return haystack.find(needles[0],
1617                                  needles[1],
1618                                  needles[2],
1619                                  needles[3],
1620                                  needles[4],
1621                                  needles[5]);
1622         case 7:
1623             return haystack.find(needles[0],
1624                                  needles[1],
1625                                  needles[2],
1626                                  needles[3],
1627                                  needles[4],
1628                                  needles[5],
1629                                  needles[6]);
1630         case 8:
1631             return haystack.find(needles[0],
1632                                  needles[1],
1633                                  needles[2],
1634                                  needles[3],
1635                                  needles[4],
1636                                  needles[5],
1637                                  needles[6],
1638                                  needles[7]);
1639         default:
1640             import std.conv: to;
1641             assert(false, `Too many keys ` ~ needles.length.to!string);
1642     }
1643 }
1644 
1645 unittest
1646 {
1647     assert(`abc`.findFirstOfAnyInOrder([`x`]) == tuple(``, 0UL));
1648     assert(`abc`.findFirstOfAnyInOrder([`a`]) == tuple(`abc`, 1UL));
1649     assert(`abc`.findFirstOfAnyInOrder([`c`]) == tuple(`c`, 1UL));
1650     assert(`abc`.findFirstOfAnyInOrder([`a`, `b`]) == tuple(`abc`, 1UL));
1651     assert(`abc`.findFirstOfAnyInOrder([`a`, `b`]) == tuple(`abc`, 1UL));
1652     assert(`abc`.findFirstOfAnyInOrder([`x`, `b`]) == tuple(`bc`, 2UL));
1653 }
1654 
1655 Tuple!(R, size_t)[] findAllOfAnyInOrder(alias pred = `a == b`, R)(R haystack, R[] needles)
1656 {
1657     // TODO Return some clever lazy range that calls each possible haystack.findFirstOfAnyInOrder(needles);
1658     return typeof(return).init;
1659 }
1660 
1661 /** Return true if all arguments $(D args) are strictly ordered,
1662     that is args[0] < args[1] < args[2] < ... .
1663     TODO: CT-variant
1664     See also: http://forum.dlang.org/thread/wzsdhzycwqyrvqmmttix@forum.dlang.org?page=2#post-vprvhifglfegnlvzqmjj:40forum.dlang.org
1665 */
1666 bool areStrictlyOrdered(Ts...)(Ts args)
1667     if (args.length >= 2 &&
1668         haveCommonType!Ts)
1669 {
1670     foreach (i, arg; args[1..$])
1671         if (args[i] >= arg) return false;
1672     return true;
1673 }
1674 
1675 unittest
1676 {
1677     static assert(!__traits(compiles, areStrictlyOrdered()));
1678     static assert(!__traits(compiles, areStrictlyOrdered(1)));
1679     assert(areStrictlyOrdered(1, 2, 3));
1680     assert(!areStrictlyOrdered(1, 3, 2));
1681     assert(!areStrictlyOrdered(1, 2, 2));
1682     assert(areStrictlyOrdered('a', 'b', 'c'));
1683 }
1684 
1685 /** Return true if all arguments $(D args) are unstrictly ordered,
1686     that is args[0] <= args[1] <= args[2] <= ... .
1687     TODO: CT-variant
1688     See also: http://forum.dlang.org/thread/wzsdhzycwqyrvqmmttix@forum.dlang.org?page=2#post-vprvhifglfegnlvzqmjj:40forum.dlang.org
1689 */
1690 bool areUnstrictlyOrdered(Ts...)(Ts args)
1691     if (args.length >= 2 &&
1692         haveCommonType!Ts)
1693 {
1694     foreach (i, arg; args[1..$])
1695         if (args[i] > arg) return false;
1696     return true;
1697 }
1698 
1699 unittest
1700 {
1701     static assert(!__traits(compiles, areUnstrictlyOrdered()));
1702     static assert(!__traits(compiles, areUnstrictlyOrdered(1)));
1703     assert(areUnstrictlyOrdered(1, 2, 2, 3));
1704     assert(!areUnstrictlyOrdered(1, 3, 2));
1705     assert(areUnstrictlyOrdered('a', 'b', 'c'));
1706 }
1707 
1708 import core.checkedint: addu, subu, mulu;
1709 
1710 alias sadd = addu;
1711 alias ssub = subu;
1712 alias smul = mulu;
1713 
1714 /** Append Arguments $(args) to $(D data).
1715     TODO Add support for other Random Access Ranges such as std.container.Array
1716     See also: http://forum.dlang.org/thread/mevnosveagdiswkxtbrv@forum.dlang.org?page=1
1717  */
1718 ref R append(R, Args...)(ref R data,
1719                          auto ref Args args)
1720     if (args.length >= 1)
1721 {
1722     alias E = ElementType!R;
1723 
1724     import std.traits : isAssignable;
1725     enum isElementType(U) = isAssignable!(E, U);
1726 
1727     import std.meta : allSatisfy;
1728 
1729     static if (args.length == 1)
1730     {
1731         data ~= args[0];
1732     }
1733     else static if (isRandomAccessRange!R &&
1734                     allSatisfy!(isElementType, Args))
1735     {
1736         data.length += args.length;
1737         foreach (i, arg; args)
1738         {
1739             data[$ - args.length + i] = arg;
1740         }
1741     }
1742     else
1743     {
1744         static size_t estimateLength(Args args)
1745         {
1746             size_t result;
1747             import std.traits : isArray;
1748             foreach (arg; args)
1749             {
1750                 alias A = typeof(arg);
1751                 import std.range : hasLength;
1752                 static if (isArray!A &&
1753                            is(E == ElementType!A) &&
1754                            hasLength!A)
1755                 {
1756                     result += arg.length;
1757                 }
1758                 else
1759                 {
1760                     result += 1;
1761                 }
1762             }
1763             // import std.stdio;
1764             // writeln(args, ` : `, result);
1765             return result;
1766         }
1767 
1768         import std.range: appender;
1769         auto app = appender!(R)(data);
1770 
1771         app.reserve(data.length + estimateLength(args));
1772 
1773         foreach (arg; args)
1774         {
1775             app.put(arg);
1776         }
1777         data = app.data;
1778     }
1779 
1780     return data;
1781 }
1782 
1783 unittest
1784 {
1785     int[] data;
1786     import std.range: only, iota;
1787 
1788     data.append(-1, 0, only(1, 2, 3), iota(4, 9));
1789     assert(data == [-1, 0, 1, 2, 3, 4, 5, 6, 7, 8]);
1790 
1791     data.append(9, 10);
1792     assert(data == [-1, 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10]);
1793 
1794     data.append([11, 12], [13, 14]);
1795     assert(data == [-1, 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14]);
1796 
1797     // int[3] d;
1798     // data.append(d, d);
1799 
1800     static assert(!__traits(compiles, { data.append(); }));
1801 }
1802 
1803 unittest
1804 {
1805     import std.container: Array;
1806     import std.algorithm: equal;
1807 
1808     Array!int data;
1809 
1810     data.append(-1);
1811     assert(equal(data[], [-1]));
1812 
1813     static assert(!__traits(compiles, { data.append(); }));
1814 }
1815 
1816 import std.algorithm: aggregate;
1817 
1818 /** Distinct Elements of $(D r).
1819 
1820    See also: http://forum.dlang.org/thread/jufggxqwzhlsmhshtnfj@forum.dlang.org?page=2
1821    See also: http://dpaste.dzfl.pl/7b4b37b490a7
1822 */
1823 auto distinct(R)(R r)
1824     if (isInputRange!(Unqual!R))
1825 {
1826     import std.traits: ForeachType;
1827     bool[ForeachType!R] seen; // TODO Use containers.hashset.HashSet
1828     import std.algorithm.iteration: filter;
1829     return r.filter!((k)
1830                      {
1831                          if (k !in seen)
1832                              return false;
1833                          else
1834                              return seen[k] = true;
1835                      });
1836 }
1837 
1838 // unittest
1839 // {
1840 //     immutable first = [1, 0, 2, 1, 3];
1841 //     immutable second = [1,5,6];
1842 //     import std.algorithm.comparison: equal;
1843 //     import std.range: chain, take;
1844 //     assert(equal(first.chain(second).distinct.take(5),
1845 //                  [1, 0, 2, 3, 5]));
1846 // }
1847 
1848 T[n] s(T, size_t n)(auto ref T[n] values) @property @safe pure nothrow
1849 {
1850     return values;
1851 }
1852 
1853 @safe pure nothrow unittest
1854 {
1855     enum n = 3;
1856     auto a = [1, 2, 3];
1857     auto x = [1, 2, 3].s;
1858     static assert(is(typeof(x) == int[3]));
1859     static assert(is(typeof([1, 2, 3].s) == int[3]));
1860     assert([1, 2, 3].s[2] == 3);
1861 }
1862 
1863 /**
1864 */
1865 auto staticArray() @property @safe
1866 {
1867     static struct _staticArray
1868     {
1869         T[n] s(T, size_t n)(auto ref T[n] values) @safe @property { return values; }
1870 
1871         T[0][n] opIndex(size_t n = T.length, T...)(T items)
1872         {
1873             typeof(return) arr;
1874             foreach (index,item; items)
1875                 arr[index] = item;
1876 
1877             return (values) { return values; }(arr);//s!(T[0], n)(arr);
1878         }
1879     }
1880     return _staticArray();
1881 }
1882 
1883 /**
1884 */
1885 bool isAmong(alias pred = (a, b) => a == b,
1886              Value,
1887              Values...)(Value value,
1888                         Values values)
1889     if (Values.length != 0)
1890 {
1891     import std.algorithm.comparison : among;
1892     return value.among!pred(values) != 0;
1893 }
1894 
1895 @safe pure nothrow @nogc unittest
1896 {
1897     assert(`b`.isAmong(`a`, `b`));
1898     assert(!`c`.isAmong(`a`, `b`));
1899 }
1900 
1901 import std.traits : isExpressionTuple;
1902 import traits_ex : haveCommonType;
1903 
1904 /**
1905    */
1906 template isAmong(values...)
1907     if (isExpressionTuple!values)
1908 {
1909     bool isAmong(Value)(Value value)
1910         if (haveCommonType!(Value, values))
1911     {
1912         switch (value)
1913         {
1914             foreach (uint i, v; values)
1915             case v:
1916                 return true;
1917         default:
1918             return false;
1919         }
1920     }
1921 }
1922 
1923 /// Ditto
1924 @safe pure nothrow @nogc unittest
1925 {
1926     assert(`b`.isAmong!(`a`, `b`));
1927     assert(!`c`.isAmong!(`a`, `b`));
1928 }
1929 
1930 import std.algorithm.setops : cartesianProduct;
1931 
1932 /** More descriptive alias.
1933  */
1934 alias elementCombinations = cartesianProduct;
1935 
1936 /** Reset all members in aggregate instance $(D c).
1937     See also: http://forum.dlang.org/post/ckitmpguywfitgadfpkv@forum.dlang.org
1938     See also: http://forum.dlang.org/post/fbs8b5$5bu$1@digitalmars.com
1939 */
1940 void resetAllMembers(T)(T c)
1941     if (is(T == class))
1942 {
1943     foreach (ref m; c.tupleof)
1944     {
1945         import std.traits : isMutable;
1946         alias M = typeof(m);
1947         static if (isMutable!M)
1948         {
1949             m = M.init;
1950         }
1951     }
1952 }
1953 
1954 unittest
1955 {
1956     class C
1957     {
1958         this (int a, int b, string c)
1959         {
1960             this.a = a;
1961             this.b = b;
1962             this.c = c;
1963         }
1964         int a; int b; string c;
1965     }
1966     void f(C c)
1967     {
1968         c.resetAllMembers();
1969     }
1970     auto c = new C(1, 2, "3");
1971     assert(c.a == 1);
1972     assert(c.b == 2);
1973     assert(c.c == "3");
1974     f(c);
1975     assert(c.a == 0);
1976     assert(c.b == 0);
1977     assert(c.c == null);
1978 }
1979 
1980 /** Returns: `true` if `r` contains strictly values that are strictly increase
1981     with the increment `step`.
1982     See also: http://forum.dlang.org/post/mqjyhvqxepgfljpkxvmd@forum.dlang.org
1983  */
1984 bool isLinearRamp(R)(R r, size_t step = 1)
1985     if (isInputRange!R &&
1986         isIntegral!(ElementType!R))
1987 {
1988     import std.algorithm : findAdjacent;
1989     import std.range : empty;
1990     return r.findAdjacent!((a, b) => a + step != b).empty;
1991 }
1992 
1993 bool hasHoles(R)(R r)
1994     if (isInputRange!R &&
1995         isIntegral!(ElementType!R))
1996 {
1997     return !r.isLinearRamp;
1998 }
1999 
2000 @safe pure nothrow unittest
2001 {
2002     assert([1].isLinearRamp);
2003     assert([1, 2, 3].isLinearRamp);
2004     assert(![1, 1].isLinearRamp);
2005     assert(![1, 2, 1].isLinearRamp);
2006     assert(![1, 2, 4].isLinearRamp);
2007 }
2008 
2009 /** Check if `r` counts to exactly `exactCount` elements.
2010  */
2011 bool countsExactly(R)(R r, size_t exactCount) @("complexity", "O(exactCount)")
2012     if (isInputRange!R)
2013 {
2014     import std.range : hasLength;
2015     static if (hasLength!R)
2016     {
2017         return r.length == exactCount;
2018     }
2019     else
2020     {
2021         size_t n;
2022         import std.range : empty;
2023         while (!r.empty)
2024         {
2025             r.popFront;
2026             if (++n > exactCount) { return false; }
2027         }
2028         return n == exactCount;
2029     }
2030 }
2031 
2032 /** Check if `r` counts to at least `minCount` elements.
2033  */
2034 bool countsAtLeast(R)(R r, size_t minCount) @("complexity", "O(minCount)")
2035     if (isInputRange!R)
2036 {
2037     import std.range : hasLength;
2038     static if (hasLength!R)
2039     {
2040         return r.length >= minCount;
2041     }
2042     else
2043     {
2044         size_t n;
2045         import std.range : empty;
2046         while (!r.empty)
2047         {
2048             r.popFront;
2049             if (++n >= minCount) { return true; }
2050         }
2051         return false;
2052     }
2053 }
2054 
2055 /** Check if `r` counts to at most `maxCount` elements.
2056  */
2057 bool countsAtMost(R)(R r, size_t maxCount) @("complexity", "O(maxCount)")
2058     if (isInputRange!R)
2059 {
2060     import std.range : hasLength;
2061     static if (hasLength!R)
2062     {
2063         return r.length <= maxCount;
2064     }
2065     else
2066     {
2067         size_t n;
2068         import std.range : empty;
2069         while (!r.empty)
2070         {
2071             r.popFront;
2072             if (++n > maxCount) { return false; }
2073         }
2074         return true;
2075     }
2076 }
2077 
2078 ///
2079 @safe pure nothrow unittest
2080 {
2081     static void test(R)(R x) if (isInputRange!R)
2082     {
2083         import std.algorithm : count;
2084         const n = x.count;
2085 
2086         // below
2087         foreach (const i; 0 .. n)
2088         {
2089             assert(x.countsAtLeast(i));
2090             assert(!x.countsExactly(i));
2091             assert(!x.countsAtMost(i));
2092         }
2093 
2094         // at
2095         assert(x.countsAtLeast(n));
2096         assert(x.countsExactly(n));
2097         assert(x.countsAtMost(n));
2098 
2099         // above
2100         foreach (const i; n + 1 .. n + 10)
2101         {
2102             assert(!x.countsAtLeast(i));
2103             assert(!x.countsExactly(i));
2104             assert(x.countsAtMost(i));
2105         }
2106     }
2107 
2108     import std.algorithm : filter;
2109     import std.range : iota;
2110     import std.array : array;
2111 
2112     test(3.iota.filter!(x => true));
2113     test(3.iota.array);
2114 }
2115 
2116 /** This function returns the index of the `value` if it exist among `values`,
2117     `size_t.max` otherwise.
2118 */
2119 size_t binarySearch(T, U)(const T[] values, in U value)
2120     if (is(typeof(T[0].init == U.init))) // TODO SortedRange support
2121 {
2122     // value is not in the array if the array is empty
2123     if (values.length == 0) { return size_t.max; }
2124 
2125     immutable mid = values.length / 2; // mid offset
2126     if (value == values[mid])
2127     {
2128         return mid; // direct hit
2129     }
2130     else if (value < values[mid])
2131     {
2132         return binarySearch(values[0 .. mid], value); // recurse left
2133     }
2134     else
2135     {
2136         auto index = binarySearch(values[mid + 1 .. $], value); // recurse right
2137         if (index != size_t.max)
2138         {
2139             index += mid + 1; // adjust the index; it is 0-based in the right-hand side slice.
2140         }
2141         return index;
2142     }
2143 }

Page generated by adrdox