1 // Written in the D programming language.
2 /**
3 This is a submodule of $(MREF std, algorithm).
4 It contains generic comparison algorithms.
5 
6 $(SCRIPT inhibitQuickIndex = 1;)
7 $(BOOKTABLE Cheat Sheet,
8 $(TR $(TH Function Name) $(TH Description))
9 $(T2 among,
10         Checks if a value is among a set of values, e.g.
11         `if (v.among(1, 2, 3)) // `v` is 1, 2 or 3`)
12 $(T2 castSwitch,
13         `(new A()).castSwitch((A a)=>1,(B b)=>2)` returns `1`.)
14 $(T2 clamp,
15         `clamp(1, 3, 6)` returns `3`. `clamp(4, 3, 6)` returns `4`.)
16 $(T2 cmp,
17         `cmp("abc", "abcd")` is `-1`, `cmp("abc", "aba")` is `1`,
18         and `cmp("abc", "abc")` is `0`.)
19 $(T2 either,
20         Return first parameter `p` that passes an `if (p)` test, e.g.
21         `either(0, 42, 43)` returns `42`.)
22 $(T2 equal,
23         Compares ranges for element-by-element equality, e.g.
24         `equal([1, 2, 3], [1.0, 2.0, 3.0])` returns `true`.)
25 $(T2 isPermutation,
26         `isPermutation([1, 2], [2, 1])` returns `true`.)
27 $(T2 isSameLength,
28         `isSameLength([1, 2, 3], [4, 5, 6])` returns `true`.)
29 $(T2 levenshteinDistance,
30         `levenshteinDistance("kitten", "sitting")` returns `3` by using
31         the $(LINK2 https://en.wikipedia.org/wiki/Levenshtein_distance,
32         Levenshtein distance algorithm).)
33 $(T2 levenshteinDistanceAndPath,
34         `levenshteinDistanceAndPath("kitten", "sitting")` returns
35         `tuple(3, "snnnsni")` by using the
36         $(LINK2 https://en.wikipedia.org/wiki/Levenshtein_distance,
37         Levenshtein distance algorithm).)
38 $(T2 max,
39         `max(3, 4, 2)` returns `4`.)
40 $(T2 min,
41         `min(3, 4, 2)` returns `2`.)
42 $(T2 mismatch,
43         `mismatch("oh hi", "ohayo")` returns `tuple(" hi", "ayo")`.)
44 $(T2 predSwitch,
45         `2.predSwitch(1, "one", 2, "two", 3, "three")` returns `"two"`.)
46 )
47 
48 Copyright: Andrei Alexandrescu 2008-.
49 
50 License: $(HTTP boost.org/LICENSE_1_0.txt, Boost License 1.0).
51 
52 Authors: $(HTTP erdani.com, Andrei Alexandrescu)
53 
54 Source: $(PHOBOSSRC std/algorithm/comparison.d)
55 
56 Macros:
57 T2=$(TR $(TDNW $(LREF $1)) $(TD $+))
58  */
59 module std.algorithm.comparison;
60 
61 import std.functional : unaryFun, binaryFun, lessThan, greaterThan;
62 import std.range.primitives;
63 import std.traits;
64 import std.meta : allSatisfy, anySatisfy;
65 import std.typecons : tuple, Tuple, Flag, Yes;
66 
67 import std.internal.attributes : betterC;
68 
69 /**
70 Find `value` _among `values`, returning the 1-based index
71 of the first matching value in `values`, or `0` if `value`
72 is not _among `values`. The predicate `pred` is used to
73 compare values, and uses equality by default.
74 
75 Params:
76     pred = The predicate used to compare the values.
77     value = The value to search for.
78     values = The values to compare the value to.
79 
80 Returns:
81     0 if value was not found among the values, otherwise the index of the
82     found value plus one is returned.
83 
84 See_Also:
85 $(REF_ALTTEXT find, find, std,algorithm,searching) and $(REF_ALTTEXT canFind, canFind, std,algorithm,searching) for finding a value in a
86 range.
87 */
88 uint among(alias pred = (a, b) => a == b, Value, Values...)
89     (Value value, Values values)
90 if (Values.length != 0)
91 {
92     foreach (uint i, ref v; values)
93     {
94         import std.functional : binaryFun;
95         if (binaryFun!pred(value, v)) return i + 1;
96     }
97     return 0;
98 }
99 
100 /// Ditto
101 template among(values...)
102 if (isExpressionTuple!values)
103 {
104     uint among(Value)(Value value)
105         if (!is(CommonType!(Value, values) == void))
106     {
107         switch (value)
108         {
109             foreach (uint i, v; values)
110                 case v:
111                     return i + 1;
112             default:
113                 return 0;
114         }
115     }
116 }
117 
118 ///
119 @safe @nogc @betterC unittest
120 {
121     assert(3.among(1, 42, 24, 3, 2));
122 
123     if (auto pos = "bar".among("foo", "bar", "baz"))
124         assert(pos == 2);
125     else
126         assert(false);
127 
128     // 42 is larger than 24
129     assert(42.among!((lhs, rhs) => lhs > rhs)(43, 24, 100) == 2);
130 }
131 
132 /**
133 Alternatively, `values` can be passed at compile-time, allowing for a more
134 efficient search, but one that only supports matching on equality:
135 */
136 @safe @nogc @betterC unittest
137 {
138     assert(3.among!(2, 3, 4));
139     assert("bar".among!("foo", "bar", "baz") == 2);
140 }
141 
142 @safe unittest
143 {
144     import std.meta : AliasSeq;
145 
146     if (auto pos = 3.among(1, 2, 3))
147         assert(pos == 3);
148     else
149         assert(false);
150     assert(!4.among(1, 2, 3));
151 
152     auto position = "hello".among("hello", "world");
153     assert(position);
154     assert(position == 1);
155 
156     alias values = AliasSeq!("foo", "bar", "baz");
157     auto arr = [values];
158     assert(arr[0 .. "foo".among(values)] == ["foo"]);
159     assert(arr[0 .. "bar".among(values)] == ["foo", "bar"]);
160     assert(arr[0 .. "baz".among(values)] == arr);
161     assert("foobar".among(values) == 0);
162 
163     if (auto pos = 3.among!(1, 2, 3))
164         assert(pos == 3);
165     else
166         assert(false);
167     assert(!4.among!(1, 2, 3));
168 
169     position = "hello".among!("hello", "world");
170     assert(position);
171     assert(position == 1);
172 
173     static assert(!__traits(compiles, "a".among!("a", 42)));
174     static assert(!__traits(compiles, (Object.init).among!(42, "a")));
175 }
176 
177 // Used in castSwitch to find the first choice that overshadows the last choice
178 // in a tuple.
179 private template indexOfFirstOvershadowingChoiceOnLast(choices...)
180 {
181     alias firstParameterTypes = Parameters!(choices[0]);
182     alias lastParameterTypes = Parameters!(choices[$ - 1]);
183 
184     static if (lastParameterTypes.length == 0)
185     {
186         // If the last is null-typed choice, check if the first is null-typed.
187         enum isOvershadowing = firstParameterTypes.length == 0;
188     }
189     else static if (firstParameterTypes.length == 1)
190     {
191         // If the both first and last are not null-typed, check for overshadowing.
192         enum isOvershadowing =
193             is(firstParameterTypes[0] == Object) // Object overshadows all other classes!(this is needed for interfaces)
194             || is(lastParameterTypes[0] : firstParameterTypes[0]);
195     }
196     else
197     {
198         // If the first is null typed and the last is not - the is no overshadowing.
199         enum isOvershadowing = false;
200     }
201 
202     static if (isOvershadowing)
203     {
204         enum indexOfFirstOvershadowingChoiceOnLast = 0;
205     }
206     else
207     {
208         enum indexOfFirstOvershadowingChoiceOnLast =
209             1 + indexOfFirstOvershadowingChoiceOnLast!(choices[1..$]);
210     }
211 }
212 
213 /**
214 Executes and returns one of a collection of handlers based on the type of the
215 switch object.
216 
217 The first choice that `switchObject` can be casted to the type
218 of argument it accepts will be called with `switchObject` casted to that
219 type, and the value it'll return will be returned by `castSwitch`.
220 
221 If a choice's return type is void, the choice must throw an exception, unless
222 all the choices are void. In that case, castSwitch itself will return void.
223 
224 Throws: If none of the choice matches, a `SwitchError` will be thrown.  $(D
225 SwitchError) will also be thrown if not all the choices are void and a void
226 choice was executed without throwing anything.
227 
228 Params:
229     choices = The `choices` needs to be composed of function or delegate
230         handlers that accept one argument. There can also be a choice that
231         accepts zero arguments. That choice will be invoked if the $(D
232         switchObject) is null.
233     switchObject = the object against which the tests are being made.
234 
235 Returns:
236     The value of the selected choice.
237 
238 Note: `castSwitch` can only be used with object types.
239 */
240 auto castSwitch(choices...)(Object switchObject)
241 {
242     import core.exception : SwitchError;
243     import std.format : format;
244 
245     // Check to see if all handlers return void.
246     enum areAllHandlersVoidResult = {
247         bool result = true;
248         foreach (index, choice; choices)
249         {
250             result &= is(ReturnType!choice : void); // void or noreturn
251         }
252         return result;
253     }();
254 
255     if (switchObject !is null)
256     {
257         // Checking for exact matches:
258         const classInfo = typeid(switchObject);
259         foreach (index, choice; choices)
260         {
261             static assert(isCallable!choice,
262                     "A choice handler must be callable");
263 
264             alias choiceParameterTypes = Parameters!choice;
265             static assert(choiceParameterTypes.length <= 1,
266                     "A choice handler can not have more than one argument.");
267 
268             static if (choiceParameterTypes.length == 1)
269             {
270                 alias CastClass = choiceParameterTypes[0];
271                 static assert(is(CastClass == class) || is(CastClass == interface),
272                         "A choice handler can have only class or interface typed argument.");
273 
274                 // Check for overshadowing:
275                 immutable indexOfOvershadowingChoice =
276                     indexOfFirstOvershadowingChoiceOnLast!(choices[0 .. index + 1]);
277                 static assert(indexOfOvershadowingChoice == index,
278                         "choice number %d(type %s) is overshadowed by choice number %d(type %s)".format(
279                             index + 1, CastClass.stringof, indexOfOvershadowingChoice + 1,
280                             Parameters!(choices[indexOfOvershadowingChoice])[0].stringof));
281 
282                 if (classInfo == typeid(CastClass))
283                 {
284                     static if (is(ReturnType!(choice) == void))
285                     {
286                         choice(cast(CastClass) switchObject);
287                         static if (areAllHandlersVoidResult)
288                         {
289                             return;
290                         }
291                         else
292                         {
293                             throw new SwitchError("Handlers that return void should throw");
294                         }
295                     }
296                     else
297                     {
298                         return choice(cast(CastClass) switchObject);
299                     }
300                 }
301             }
302         }
303 
304         // Checking for derived matches:
305         foreach (choice; choices)
306         {
307             alias choiceParameterTypes = Parameters!choice;
308             static if (choiceParameterTypes.length == 1)
309             {
310                 if (auto castedObject = cast(choiceParameterTypes[0]) switchObject)
311                 {
312                     static if (is(ReturnType!(choice) == void))
313                     {
314                         choice(castedObject);
315                         static if (areAllHandlersVoidResult)
316                         {
317                             return;
318                         }
319                         else
320                         {
321                             throw new SwitchError("Handlers that return void should throw");
322                         }
323                     }
324                     else
325                     {
326                         return choice(castedObject);
327                     }
328                 }
329             }
330         }
331     }
332     else // If switchObject is null:
333     {
334         // Checking for null matches:
335         foreach (index, choice; choices)
336         {
337             static if (Parameters!(choice).length == 0)
338             {
339                 immutable indexOfOvershadowingChoice =
340                     indexOfFirstOvershadowingChoiceOnLast!(choices[0 .. index + 1]);
341 
342                 // Check for overshadowing:
343                 static assert(indexOfOvershadowingChoice == index,
344                         "choice number %d(null reference) is overshadowed by choice number %d(null reference)".format(
345                             index + 1, indexOfOvershadowingChoice + 1));
346 
347                 if (switchObject is null)
348                 {
349                     static if (is(ReturnType!(choice) == void))
350                     {
351                         choice();
352                         static if (areAllHandlersVoidResult)
353                         {
354                             return;
355                         }
356                         else
357                         {
358                             throw new SwitchError("Handlers that return void should throw");
359                         }
360                     }
361                     else
362                     {
363                         return choice();
364                     }
365                 }
366             }
367         }
368     }
369 
370     // In case nothing matched:
371     throw new SwitchError("Input not matched by any choice");
372 }
373 
374 ///
375 @system unittest
376 {
377     import std.algorithm.iteration : map;
378     import std.format : format;
379 
380     class A
381     {
382         int a;
383         this(int a) {this.a = a;}
384         @property int i() { return a; }
385     }
386     interface I { }
387     class B : I { }
388 
389     Object[] arr = [new A(1), new B(), null];
390 
391     auto results = arr.map!(castSwitch!(
392                                 (A a) => "A with a value of %d".format(a.a),
393                                 (I i) => "derived from I",
394                                 ()    => "null reference",
395                             ))();
396 
397     // A is handled directly:
398     assert(results[0] == "A with a value of 1");
399     // B has no handler - it is handled by the handler of I:
400     assert(results[1] == "derived from I");
401     // null is handled by the null handler:
402     assert(results[2] == "null reference");
403 }
404 
405 /// Using with void handlers:
406 @system unittest
407 {
408     import std.exception : assertThrown;
409 
410     class A { }
411     class B { }
412     // Void handlers are allowed if they throw:
413     assertThrown!Exception(
414         new B().castSwitch!(
415             (A a) => 1,
416             (B d)    { throw new Exception("B is not allowed!"); }
417         )()
418     );
419 
420     // Void handlers are also allowed if all the handlers are void:
421     new A().castSwitch!(
422         (A a) { },
423         (B b) { assert(false); },
424     )();
425 }
426 
427 @system unittest
428 {
429     import core.exception : SwitchError;
430     import std.exception : assertThrown;
431 
432     interface I { }
433     class A : I { }
434     class B { }
435 
436     // Nothing matches:
437     assertThrown!SwitchError((new A()).castSwitch!(
438                                  (B b) => 1,
439                                  () => 2,
440                              )());
441 
442     // Choices with multiple arguments are not allowed:
443     static assert(!__traits(compiles,
444                             (new A()).castSwitch!(
445                                 (A a, B b) => 0,
446                             )()));
447 
448     // Only callable handlers allowed:
449     static assert(!__traits(compiles,
450                             (new A()).castSwitch!(
451                                 1234,
452                             )()));
453 
454     // Only object arguments allowed:
455     static assert(!__traits(compiles,
456                             (new A()).castSwitch!(
457                                 (int x) => 0,
458                             )()));
459 
460     // Object overshadows regular classes:
461     static assert(!__traits(compiles,
462                             (new A()).castSwitch!(
463                                 (Object o) => 0,
464                                 (A a) => 1,
465                             )()));
466 
467     // Object overshadows interfaces:
468     static assert(!__traits(compiles,
469                             (new A()).castSwitch!(
470                                 (Object o) => 0,
471                                 (I i) => 1,
472                             )()));
473 
474     // No multiple null handlers allowed:
475     static assert(!__traits(compiles,
476                             (new A()).castSwitch!(
477                                 () => 0,
478                                 () => 1,
479                             )()));
480 
481     // No non-throwing void handlers allowed(when there are non-void handlers):
482     assertThrown!SwitchError((new A()).castSwitch!(
483                                  (A a)    {},
484                                  (B b) => 2,
485                              )());
486 
487     // All-void handlers work for the null case:
488     null.castSwitch!(
489         (Object o) { assert(false); },
490         ()         { },
491     )();
492 
493     // Throwing void handlers work for the null case:
494     assertThrown!Exception(null.castSwitch!(
495                                (Object o) => 1,
496                                ()            { throw new Exception("null"); },
497                            )());
498 }
499 
500 @system unittest
501 {
502     interface I { }
503     class B : I { }
504     class C : I { }
505 
506     assert((new B()).castSwitch!(
507             (B b) => "class B",
508             (I i) => "derived from I",
509     ) == "class B");
510 
511     assert((new C()).castSwitch!(
512             (B b) => "class B",
513             (I i) => "derived from I",
514     ) == "derived from I");
515 }
516 
517 // https://issues.dlang.org/show_bug.cgi?id=22384
518 @system unittest
519 {
520     // Use explicit methods to enforce return types
521     static void objectSkip(Object) {}
522     static void defaultSkip() {}
523 
524     static noreturn objectError(Object) { assert(false); }
525     static noreturn defaultError() { assert(false); }
526 
527     {
528         alias test = castSwitch!(objectSkip, defaultError);
529         static assert(is(ReturnType!test == void));
530     }{
531         alias test = castSwitch!(objectError, defaultSkip);
532         static assert(is(ReturnType!test == void));
533     }{
534         alias test = castSwitch!(objectError, defaultError);
535         static assert(is(ReturnType!test == noreturn));
536     }
537 
538     // Also works with non-void handlers
539     static int objectValue(Object) { return 1;}
540     static int defaultValue() { return 2; }
541 
542     {
543         alias test = castSwitch!(objectValue, defaultError);
544         static assert(is(ReturnType!test == int));
545     }{
546         alias test = castSwitch!(objectError, defaultValue);
547         static assert(is(ReturnType!test == int));
548     }
549 
550     // No confusion w.r.t. void callbacks
551     alias FP = void function();
552     static FP objectFunc(Object) { return &defaultSkip; }
553     static FP defaultFunc() { return &defaultSkip; }
554 
555     {
556         alias test = castSwitch!(objectFunc, defaultError);
557         static assert(is(ReturnType!test == FP));
558     }{
559         alias test = castSwitch!(objectError, defaultFunc);
560         static assert(is(ReturnType!test == FP));
561     }
562 }
563 
564 /** Clamps `val` into the given bounds. Result has the same type as `val`.
565 
566 Params:
567     val = The value to _clamp.
568     lower = The _lower bound of the _clamp.
569     upper = The _upper bound of the _clamp.
570 
571 Returns:
572     `lower` if `val` is less than `lower`, `upper` if `val` is greater than
573     `upper`, and `val` in all other cases. Comparisons are made
574     correctly (using $(REF lessThan, std,functional) and the return value
575     is converted to the return type using the standard integer coversion rules
576     $(REF greaterThan, std,functional)) even if the signedness of `T1`, `T2`,
577     and `T3` are different.
578 */
579 T1 clamp(T1, T2, T3)(T1 val, T2 lower, T3 upper)
580 {
581     static assert(is(T2 : T1), "T2 of type '", T2.stringof
582             , "' must be implicitly convertible to type of T1 '"
583             , T1.stringof, "'");
584     static assert(is(T3 : T1), "T3 of type '", T3.stringof
585             , "' must be implicitly convertible to type of T1 '"
586             , T1.stringof, "'");
587 
588     assert(!lower.greaterThan(upper), "Lower can't be greater than upper.");
589 
590     // `if (is(typeof(val.lessThan(lower) ? lower : val.greaterThan(upper) ? upper : val) : T1))
591     // because of https://issues.dlang.org/show_bug.cgi?id=16235.
592     // Once that is fixed, we can simply use the ternary in both the template constraint
593     // and the template body
594     if (val.lessThan(lower))
595         return lower;
596     else if (val.greaterThan(upper))
597         return upper;
598     return val;
599 }
600 
601 ///
602 @safe @nogc @betterC unittest
603 {
604     assert(clamp(2, 1, 3) == 2);
605     assert(clamp(0, 1, 3) == 1);
606     assert(clamp(4, 1, 3) == 3);
607 
608     assert(clamp(1, 1, 1) == 1);
609 
610     assert(clamp(5, -1, 2u) == 2);
611 
612     auto x = clamp(42, uint.max, uint.max);
613     static assert(is(typeof(x) == int));
614     assert(x == -1);
615 }
616 
617 @safe unittest
618 {
619     int a = 1;
620     short b = 6;
621     double c = 2;
622     static assert(is(typeof(clamp(c,a,b)) == double));
623     assert(clamp(c,   a, b) == c);
624     assert(clamp(a-c, a, b) == a);
625     assert(clamp(b+c, a, b) == b);
626     // mixed sign
627     a = -5;
628     uint f = 5;
629     static assert(is(typeof(clamp(f, a, b)) == uint));
630     assert(clamp(f, a, b) == f);
631     // similar type deduction for (u)long
632     static assert(is(typeof(clamp(-1L, -2L, 2UL)) == long));
633 
634     // user-defined types
635     import std.datetime : Date;
636     assert(clamp(Date(1982, 1, 4), Date(1012, 12, 21), Date(2012, 12, 21)) == Date(1982, 1, 4));
637     assert(clamp(Date(1982, 1, 4), Date.min, Date.max) == Date(1982, 1, 4));
638     // UFCS style
639     assert(Date(1982, 1, 4).clamp(Date.min, Date.max) == Date(1982, 1, 4));
640 
641     // Stability
642     struct A {
643         int x, y;
644         int opCmp(ref const A rhs) const { return (x > rhs.x) - (x < rhs.x); }
645     }
646     A x, lo, hi;
647     x.y = 42;
648     assert(x.clamp(lo, hi).y == 42);
649 }
650 
651 // https://issues.dlang.org/show_bug.cgi?id=23268
652 @safe pure nothrow @nogc unittest
653 {
654     static assert(__traits(compiles, clamp(short.init, short.init, cast(const) short.init)));
655 }
656 
657 // cmp
658 /**********************************
659 Performs a lexicographical comparison on two
660 $(REF_ALTTEXT input ranges, isInputRange, std,range,primitives).
661 Iterating `r1` and `r2` in lockstep, `cmp` compares each element
662 `e1` of `r1` with the corresponding element `e2` in `r2`. If one
663 of the ranges has been finished, `cmp` returns a negative value
664 if `r1` has fewer elements than `r2`, a positive value if `r1`
665 has more elements than `r2`, and `0` if the ranges have the same
666 number of elements.
667 
668 If the ranges are strings, `cmp` performs UTF decoding
669 appropriately and compares the ranges one code point at a time.
670 
671 A custom predicate may be specified, in which case `cmp` performs
672 a three-way lexicographical comparison using `pred`. Otherwise
673 the elements are compared using `opCmp`.
674 
675 Params:
676     pred = Predicate used for comparison. Without a predicate
677         specified the ordering implied by `opCmp` is used.
678     r1 = The first range.
679     r2 = The second range.
680 
681 Returns:
682     `0` if the ranges compare equal. A negative value if `r1` is a prefix of `r2` or
683     the first differing element of `r1` is less than the corresponding element of `r2`
684     according to `pred`. A positive value if `r2` is a prefix of `r1` or the first
685     differing element of `r2` is less than the corresponding element of `r1`
686     according to `pred`.
687 
688 Note:
689     An earlier version of the documentation incorrectly stated that `-1` is the
690     only negative value returned and `1` is the only positive value returned.
691     Whether that is true depends on the types being compared.
692 */
693 auto cmp(R1, R2)(R1 r1, R2 r2)
694 if (isInputRange!R1 && isInputRange!R2)
695 {
696     alias E1 = ElementEncodingType!R1;
697     alias E2 = ElementEncodingType!R2;
698 
699     static if (isDynamicArray!R1 && isDynamicArray!R2
700         && __traits(isUnsigned, E1) && __traits(isUnsigned, E2)
701         && E1.sizeof == 1 && E2.sizeof == 1
702         // Both or neither must auto-decode.
703         && (is(immutable E1 == immutable char) == is(immutable E2 == immutable char)))
704     {
705         // dstrcmp algorithm is correct for both ubyte[] and for char[].
706         import core.internal.string : dstrcmp;
707         return dstrcmp(cast(const char[]) r1, cast(const char[]) r2);
708     }
709     else static if (!(isSomeString!R1 && isSomeString!R2))
710     {
711         for (;; r1.popFront(), r2.popFront())
712         {
713             static if (is(typeof(r1.front.opCmp(r2.front)) R))
714                 alias Result = R;
715             else
716                 alias Result = int;
717             if (r2.empty) return Result(!r1.empty);
718             if (r1.empty) return Result(-1);
719             static if (is(typeof(r1.front.opCmp(r2.front))))
720             {
721                 auto c = r1.front.opCmp(r2.front);
722                 if (c != 0) return c;
723             }
724             else
725             {
726                 auto a = r1.front, b = r2.front;
727                 if (auto result = (b < a) - (a < b)) return result;
728             }
729         }
730     }
731     else
732     {
733         static if (typeof(r1[0]).sizeof == typeof(r2[0]).sizeof)
734         {
735             return () @trusted
736             {
737                 auto p1 = r1.ptr, p2 = r2.ptr,
738                     pEnd = p1 + min(r1.length, r2.length);
739                 for (; p1 != pEnd; ++p1, ++p2)
740                 {
741                     if (*p1 != *p2) return cast(int) *p1 - cast(int) *p2;
742                 }
743                 static if (typeof(r1[0]).sizeof >= 2 && size_t.sizeof <= uint.sizeof)
744                     return cast(int) r1.length - cast(int) r2.length;
745                 else
746                     return int(r1.length > r2.length) - int(r1.length < r2.length);
747             }();
748         }
749         else
750         {
751             import std.utf : decode;
752 
753             for (size_t i1, i2;;)
754             {
755                 if (i1 == r1.length) return -int(i2 < r2.length);
756                 if (i2 == r2.length) return int(1);
757                 immutable c1 = decode(r1, i1),
758                     c2 = decode(r2, i2);
759                 if (c1 != c2) return cast(int) c1 - cast(int) c2;
760             }
761         }
762     }
763 }
764 
765 /// ditto
766 int cmp(alias pred, R1, R2)(R1 r1, R2 r2)
767 if (isInputRange!R1 && isInputRange!R2)
768 {
769     static if (!(isSomeString!R1 && isSomeString!R2))
770     {
771         for (;; r1.popFront(), r2.popFront())
772         {
773             if (r2.empty) return !r1.empty;
774             if (r1.empty) return -1;
775             auto a = r1.front, b = r2.front;
776             if (binaryFun!pred(a, b)) return -1;
777             if (binaryFun!pred(b, a)) return 1;
778         }
779     }
780     else
781     {
782         import std.utf : decode;
783 
784         for (size_t i1, i2;;)
785         {
786             if (i1 == r1.length) return -int(i2 < r2.length);
787             if (i2 == r2.length) return 1;
788             immutable c1 = decode(r1, i1),
789                 c2 = decode(r2, i2);
790             if (c1 != c2)
791             {
792                 if (binaryFun!pred(c2, c1)) return 1;
793                 if (binaryFun!pred(c1, c2)) return -1;
794             }
795         }
796     }
797 }
798 
799 ///
800 pure @safe unittest
801 {
802     int result;
803 
804     result = cmp("abc", "abc");
805     assert(result == 0);
806     result = cmp("", "");
807     assert(result == 0);
808     result = cmp("abc", "abcd");
809     assert(result < 0);
810     result = cmp("abcd", "abc");
811     assert(result > 0);
812     result = cmp("abc"d, "abd");
813     assert(result < 0);
814     result = cmp("bbc", "abc"w);
815     assert(result > 0);
816     result = cmp("aaa", "aaaa"d);
817     assert(result < 0);
818     result = cmp("aaaa", "aaa"d);
819     assert(result > 0);
820     result = cmp("aaa", "aaa"d);
821     assert(result == 0);
822     result = cmp("aaa"d, "aaa"d);
823     assert(result == 0);
824     result = cmp(cast(int[])[], cast(int[])[]);
825     assert(result == 0);
826     result = cmp([1, 2, 3], [1, 2, 3]);
827     assert(result == 0);
828     result = cmp([1, 3, 2], [1, 2, 3]);
829     assert(result > 0);
830     result = cmp([1, 2, 3], [1L, 2, 3, 4]);
831     assert(result < 0);
832     result = cmp([1L, 2, 3], [1, 2]);
833     assert(result > 0);
834 }
835 
836 /// Example predicate that compares individual elements in reverse lexical order
837 pure @safe unittest
838 {
839     int result;
840 
841     result = cmp!"a > b"("abc", "abc");
842     assert(result == 0);
843     result = cmp!"a > b"("", "");
844     assert(result == 0);
845     result = cmp!"a > b"("abc", "abcd");
846     assert(result < 0);
847     result = cmp!"a > b"("abcd", "abc");
848     assert(result > 0);
849     result = cmp!"a > b"("abc"d, "abd");
850     assert(result > 0);
851     result = cmp!"a > b"("bbc", "abc"w);
852     assert(result < 0);
853     result = cmp!"a > b"("aaa", "aaaa"d);
854     assert(result < 0);
855     result = cmp!"a > b"("aaaa", "aaa"d);
856     assert(result > 0);
857     result = cmp!"a > b"("aaa", "aaa"d);
858     assert(result == 0);
859     result = cmp("aaa"d, "aaa"d);
860     assert(result == 0);
861     result = cmp!"a > b"(cast(int[])[], cast(int[])[]);
862     assert(result == 0);
863     result = cmp!"a > b"([1, 2, 3], [1, 2, 3]);
864     assert(result == 0);
865     result = cmp!"a > b"([1, 3, 2], [1, 2, 3]);
866     assert(result < 0);
867     result = cmp!"a > b"([1, 2, 3], [1L, 2, 3, 4]);
868     assert(result < 0);
869     result = cmp!"a > b"([1L, 2, 3], [1, 2]);
870     assert(result > 0);
871 }
872 
873 // cmp for string with custom predicate fails if distinct chars can compare equal
874 // https://issues.dlang.org/show_bug.cgi?id=18286
875 @nogc nothrow pure @safe unittest
876 {
877     static bool ltCi(dchar a, dchar b)// less than, case insensitive
878     {
879         import std.ascii : toUpper;
880         return toUpper(a) < toUpper(b);
881     }
882     static assert(cmp!ltCi("apple2", "APPLE1") > 0);
883     static assert(cmp!ltCi("apple1", "APPLE2") < 0);
884     static assert(cmp!ltCi("apple", "APPLE1") < 0);
885     static assert(cmp!ltCi("APPLE", "apple1") < 0);
886     static assert(cmp!ltCi("apple", "APPLE") == 0);
887 }
888 
889 // for non-string ranges check that opCmp is evaluated only once per pair.
890 // https://issues.dlang.org/show_bug.cgi?id=18280
891 @nogc nothrow @safe unittest
892 {
893     static int ctr = 0;
894     struct S
895     {
896         int opCmp(ref const S rhs) const
897         {
898             ++ctr;
899             return 0;
900         }
901         bool opEquals(T)(T o) const { return false; }
902         size_t toHash() const { return 0; }
903     }
904     immutable S[4] a;
905     immutable S[4] b;
906     immutable result = cmp(a[], b[]);
907     assert(result == 0, "neither should compare greater than the other!");
908     assert(ctr == a.length, "opCmp should be called exactly once per pair of items!");
909 }
910 
911 nothrow pure @safe @nogc unittest
912 {
913     import std.array : staticArray;
914     // Test cmp when opCmp returns float.
915     struct F
916     {
917         float value;
918         float opCmp(const ref F rhs) const
919         {
920             return value - rhs.value;
921         }
922         bool opEquals(T)(T o) const { return false; }
923         size_t toHash() const { return 0; }
924     }
925     auto result = cmp([F(1), F(2), F(3)].staticArray[], [F(1), F(2), F(3)].staticArray[]);
926     assert(result == 0);
927     assert(is(typeof(result) == float));
928     result = cmp([F(1), F(3), F(2)].staticArray[], [F(1), F(2), F(3)].staticArray[]);
929     assert(result > 0);
930     result = cmp([F(1), F(2), F(3)].staticArray[], [F(1), F(2), F(3), F(4)].staticArray[]);
931     assert(result < 0);
932     result = cmp([F(1), F(2), F(3)].staticArray[], [F(1), F(2)].staticArray[]);
933     assert(result > 0);
934 }
935 
936 nothrow pure @safe unittest
937 {
938     // Parallelism (was broken by inferred return type "immutable int")
939     import std.parallelism : task;
940     auto t = task!cmp("foo", "bar");
941 }
942 
943 // equal
944 /**
945 Compares two or more ranges for equality, as defined by predicate `pred`
946 (which is `==` by default).
947 */
948 template equal(alias pred = "a == b")
949 {
950     /++
951     Compares two or more ranges for equality. The ranges may have
952     different element types, as long as all are comparable by means of
953     the `pred`.
954     Performs $(BIGOH min(rs[0].length, rs[1].length, ...)) evaluations of `pred`. However, if
955     `equal` is invoked with the default predicate, the implementation may take the liberty
956     to use faster implementations that have the theoretical worst-case
957     $(BIGOH max(rs[0].length, rs[1].length, ...)).
958 
959     At least one of the ranges must be finite. If one range involved is infinite, the result is
960     (statically known to be) `false`.
961 
962     If the ranges have different kinds of UTF code unit (`char`, `wchar`, or
963     `dchar`), then they are compared using UTF decoding to avoid
964     accidentally integer-promoting units.
965 
966     Params:
967         rs = The ranges to be compared.
968 
969     Returns:
970         `true` if and only if all ranges compare _equal element
971         for element, according to binary predicate `pred`.
972     +/
973     bool equal(Ranges...)(Ranges rs)
974     if (rs.length > 1
975         && allSatisfy!(isInputRange, Ranges)
976         && !allSatisfy!(isInfinite, Ranges)
977         && is(typeof(binaryFun!pred(rs[0].front, rs[1].front)))
978         && (rs.length == 2 || is(typeof(equal!pred(rs[1 .. $])) == bool))
979         )
980     {
981         alias ElementEncodingTypes = staticMap!(ElementEncodingType, Ranges);
982         enum differentSize(T) = T.sizeof != ElementEncodingTypes[0].sizeof;
983         enum useCodePoint = allSatisfy!(isSomeChar, ElementEncodingTypes) &&
984             anySatisfy!(differentSize, ElementEncodingTypes);
985         enum bool comparableWithEq(alias r) = is(typeof(rs[0] == r));
986 
987         static if (anySatisfy!(isInfinite, Ranges))
988         {
989             return false;
990         }
991         else static if (useCodePoint)
992         {
993             import std.utf : byDchar;
994             static bool allByDchar(size_t done, Ranges...)(auto ref Ranges rs)
995             {
996                 static if (done == rs.length)
997                     return equalLoop(rs);
998                 else
999                     return allByDchar!(done + 1)(rs[0 .. done], rs[done].byDchar, rs[done + 1 .. $]);
1000             }
1001             return allByDchar!0(rs);
1002         }
1003         else static if (is(typeof(pred) == string) && pred == "a == b" &&
1004                 allSatisfy!(isArray, Ranges) && allSatisfy!(comparableWithEq, rs))
1005         {
1006             static foreach (r; rs[1 .. $])
1007                 if (rs[0] != r)
1008                     return false;
1009             return true;
1010         }
1011         // if one of the arguments is a string and the other isn't, then auto-decoding
1012         // can be avoided if they have the same ElementEncodingType
1013         // TODO: generalize this
1014         else static if (rs.length == 2 && is(typeof(pred) == string) && pred == "a == b" &&
1015                 isAutodecodableString!(Ranges[0]) != isAutodecodableString!(Ranges[1]) &&
1016                 is(immutable ElementEncodingType!(Ranges[0]) == immutable ElementEncodingType!(Ranges[1])))
1017         {
1018             import std.utf : byCodeUnit;
1019             static if (isAutodecodableString!(Ranges[0]))
1020                 return equal(rs[0].byCodeUnit, rs[1]);
1021             else
1022                 return equal(rs[1].byCodeUnit, rs[0]);
1023         }
1024         else
1025         {
1026             static foreach (i, R; Ranges)
1027             {
1028                 static if (hasLength!R)
1029                 {
1030                     static if (!is(typeof(firstLength)))
1031                     {
1032                         // Found the first range that has length
1033                         auto firstLength = rs[i].length;
1034                     }
1035                     else
1036                     {
1037                         // Compare the length of the current range against the first with length
1038                         if (firstLength != rs[i].length)
1039                             return false;
1040                     }
1041                 }
1042             }
1043             return equalLoop(rs);
1044         }
1045     }
1046 
1047     private bool equalLoop(Rs...)(ref Rs rs)
1048     {
1049         for (; !rs[0].empty; rs[0].popFront)
1050             static foreach (r; rs[1 .. $])
1051                 if (r.empty || !binaryFun!pred(rs[0].front, r.front))
1052                     return false;
1053                 else
1054                     r.popFront;
1055         static foreach (r; rs[1 .. $])
1056             if (!r.empty)
1057                 return false;
1058         return true;
1059     }
1060 }
1061 
1062 ///
1063 @safe @nogc unittest
1064 {
1065     import std.algorithm.comparison : equal;
1066     import std.math.operations : isClose;
1067 
1068     int[4] a = [ 1, 2, 4, 3 ];
1069     assert(!equal(a[], a[1..$]));
1070     assert(equal(a[], a[]));
1071     assert(equal!((a, b) => a == b)(a[], a[]));
1072 
1073     // different types
1074     double[4] b = [ 1.0, 2, 4, 3];
1075     assert(!equal(a[], b[1..$]));
1076     assert(equal(a[], b[]));
1077 
1078     // predicated: ensure that two vectors are approximately equal
1079     double[4] c = [ 1.0000000005, 2, 4, 3];
1080     assert(equal!isClose(b[], c[]));
1081 }
1082 
1083 @safe @nogc unittest
1084 {
1085     import std.algorithm.comparison : equal;
1086     import std.math.operations : isClose;
1087 
1088     auto s1 = "abc", s2 = "abc"w;
1089     assert(equal(s1, s2, s2));
1090     assert(equal(s1, s2, s2, s1));
1091     assert(!equal(s1, s2, s2[1 .. $]));
1092 
1093     int[4] a = [ 1, 2, 4, 3 ];
1094     assert(!equal(a[], a[1..$], a[]));
1095     assert(equal(a[], a[], a[]));
1096     assert(equal!((a, b) => a == b)(a[], a[], a[]));
1097 
1098     // different types
1099     double[4] b = [ 1.0, 2, 4, 3];
1100     assert(!equal(a[], b[1..$], b[]));
1101     assert(equal(a[], b[], a[], b[]));
1102 
1103     // predicated: ensure that two vectors are approximately equal
1104     double[4] c = [ 1.0000000005, 2, 4, 3];
1105     assert(equal!isClose(b[], c[], b[]));
1106 }
1107 
1108 /++
1109 Tip: `equal` can itself be used as a predicate to other functions.
1110 This can be very useful when the element type of a range is itself a
1111 range. In particular, `equal` can be its own predicate, allowing
1112 range of range (of range...) comparisons.
1113  +/
1114 @safe unittest
1115 {
1116     import std.algorithm.comparison : equal;
1117     import std.range : iota, chunks;
1118     assert(equal!(equal!equal)(
1119         [[[0, 1], [2, 3]], [[4, 5], [6, 7]]],
1120         iota(0, 8).chunks(2).chunks(2)
1121     ));
1122 }
1123 
1124 @safe unittest
1125 {
1126     import std.algorithm.iteration : map;
1127     import std.internal.test.dummyrange : ReferenceForwardRange,
1128         ReferenceInputRange, ReferenceInfiniteForwardRange;
1129     import std.math.operations : isClose;
1130 
1131     // various strings
1132     assert(equal("æøå", "æøå")); //UTF8 vs UTF8
1133     assert(!equal("???", "æøå")); //UTF8 vs UTF8
1134     assert(equal("æøå"w, "æøå"d)); //UTF16 vs UTF32
1135     assert(!equal("???"w, "æøå"d));//UTF16 vs UTF32
1136     assert(equal("æøå"d, "æøå"d)); //UTF32 vs UTF32
1137     assert(!equal("???"d, "æøå"d));//UTF32 vs UTF32
1138     assert(!equal("hello", "world"));
1139 
1140     // same strings, but "explicit non default" comparison (to test the non optimized array comparison)
1141     assert( equal!("a == b")("æøå", "æøå")); //UTF8 vs UTF8
1142     assert(!equal!("a == b")("???", "æøå")); //UTF8 vs UTF8
1143     assert( equal!("a == b")("æøå"w, "æøå"d)); //UTF16 vs UTF32
1144     assert(!equal!("a == b")("???"w, "æøå"d));//UTF16 vs UTF32
1145     assert( equal!("a == b")("æøå"d, "æøå"d)); //UTF32 vs UTF32
1146     assert(!equal!("a == b")("???"d, "æøå"d));//UTF32 vs UTF32
1147     assert(!equal!("a == b")("hello", "world"));
1148 
1149     //Array of string
1150     assert(equal(["hello", "world"], ["hello", "world"]));
1151     assert(!equal(["hello", "world"], ["hello"]));
1152     assert(!equal(["hello", "world"], ["hello", "Bob!"]));
1153 
1154     //Should not compile, because "string == dstring" is illegal
1155     static assert(!is(typeof(equal(["hello", "world"], ["hello"d, "world"d]))));
1156     //However, arrays of non-matching string can be compared using equal!equal. Neat-o!
1157     equal!equal(["hello", "world"], ["hello"d, "world"d]);
1158 
1159     //Tests, with more fancy map ranges
1160     int[] a = [ 1, 2, 4, 3 ];
1161     assert(equal([2, 4, 8, 6], map!"a*2"(a)));
1162     double[] b = [ 1.0, 2, 4, 3];
1163     double[] c = [ 1.0000000005, 2, 4, 3];
1164     assert(equal!isClose(map!"a*2"(b), map!"a*2"(c)));
1165     assert(!equal([2, 4, 1, 3], map!"a*2"(a)));
1166     assert(!equal([2, 4, 1], map!"a*2"(a)));
1167     assert(!equal!isClose(map!"a*3"(b), map!"a*2"(c)));
1168 
1169     //Tests with some fancy reference ranges.
1170     ReferenceInputRange!int cir = new ReferenceInputRange!int([1, 2, 4, 3]);
1171     ReferenceForwardRange!int cfr = new ReferenceForwardRange!int([1, 2, 4, 3]);
1172     assert(equal(cir, a));
1173     cir = new ReferenceInputRange!int([1, 2, 4, 3]);
1174     assert(equal(cir, cfr.save));
1175     assert(equal(cfr.save, cfr.save));
1176     cir = new ReferenceInputRange!int([1, 2, 8, 1]);
1177     assert(!equal(cir, cfr));
1178 
1179     //Test with an infinite range
1180     auto ifr = new ReferenceInfiniteForwardRange!int;
1181     assert(!equal(a, ifr));
1182     assert(!equal(ifr, a));
1183     //Test InputRange without length
1184     assert(!equal(ifr, cir));
1185     assert(!equal(cir, ifr));
1186 }
1187 
1188 @safe @nogc pure unittest
1189 {
1190     import std.utf : byChar, byDchar, byWchar;
1191 
1192     assert(equal("æøå".byChar, "æøå"));
1193     assert(equal("æøå".byChar, "æøå"w));
1194     assert(equal("æøå".byChar, "æøå"d));
1195     assert(equal("æøå", "æøå".byChar));
1196     assert(equal("æøå"w, "æøå".byChar));
1197     assert(equal("æøå"d, "æøå".byChar));
1198 
1199     assert(equal("æøå".byWchar, "æøå"));
1200     assert(equal("æøå".byWchar, "æøå"w));
1201     assert(equal("æøå".byWchar, "æøå"d));
1202     assert(equal("æøå", "æøå".byWchar));
1203     assert(equal("æøå"w, "æøå".byWchar));
1204     assert(equal("æøå"d, "æøå".byWchar));
1205 
1206     assert(equal("æøå".byDchar, "æøå"));
1207     assert(equal("æøå".byDchar, "æøå"w));
1208     assert(equal("æøå".byDchar, "æøå"d));
1209     assert(equal("æøå", "æøå".byDchar));
1210     assert(equal("æøå"w, "æøå".byDchar));
1211     assert(equal("æøå"d, "æøå".byDchar));
1212 }
1213 
1214 @safe @nogc pure unittest
1215 {
1216     struct R(bool _empty) {
1217         enum empty = _empty;
1218         @property char front(){assert(0);}
1219         void popFront(){assert(0);}
1220     }
1221     alias I = R!false;
1222     static assert(!__traits(compiles, I().equal(I())));
1223     // strings have fixed length so don't need to compare elements
1224     assert(!I().equal("foo"));
1225     assert(!"bar".equal(I()));
1226 
1227     alias E = R!true;
1228     assert(E().equal(E()));
1229     assert(E().equal(""));
1230     assert("".equal(E()));
1231     assert(!E().equal("foo"));
1232     assert(!"bar".equal(E()));
1233 }
1234 
1235 // levenshteinDistance
1236 /**
1237 Encodes $(HTTP realityinteractive.com/rgrzywinski/archives/000249.html,
1238 edit operations) necessary to transform one sequence into
1239 another. Given sequences `s` (source) and `t` (target), a
1240 sequence of `EditOp` encodes the steps that need to be taken to
1241 convert `s` into `t`. For example, if `s = "cat"` and $(D
1242 "cars"), the minimal sequence that transforms `s` into `t` is:
1243 skip two characters, replace 't' with 'r', and insert an 's'. Working
1244 with edit operations is useful in applications such as spell-checkers
1245 (to find the closest word to a given misspelled word), approximate
1246 searches, diff-style programs that compute the difference between
1247 files, efficient encoding of patches, DNA sequence analysis, and
1248 plagiarism detection.
1249 */
1250 
1251 enum EditOp : char
1252 {
1253     /** Current items are equal; no editing is necessary. */
1254     none = 'n',
1255     /** Substitute current item in target with current item in source. */
1256     substitute = 's',
1257     /** Insert current item from the source into the target. */
1258     insert = 'i',
1259     /** Remove current item from the target. */
1260     remove = 'r'
1261 }
1262 
1263 ///
1264 @safe unittest
1265 {
1266     with(EditOp)
1267     {
1268         assert(levenshteinDistanceAndPath("foo", "foobar")[1] == [none, none, none, insert, insert, insert]);
1269         assert(levenshteinDistanceAndPath("banana", "fazan")[1] == [substitute, none, substitute, none, none, remove]);
1270     }
1271 }
1272 
1273 private struct Levenshtein(Range, alias equals, CostType = size_t)
1274 {
1275     EditOp[] path()
1276     {
1277         import std.algorithm.mutation : reverse;
1278 
1279         EditOp[] result;
1280         size_t i = rows - 1, j = cols - 1;
1281         // restore the path
1282         while (i || j)
1283         {
1284             auto cIns = j == 0 ? CostType.max : matrix(i,j - 1);
1285             auto cDel = i == 0 ? CostType.max : matrix(i - 1,j);
1286             auto cSub = i == 0 || j == 0
1287                 ? CostType.max
1288                 : matrix(i - 1,j - 1);
1289             switch (min_index(cSub, cIns, cDel))
1290             {
1291             case 0:
1292                 result ~= matrix(i - 1,j - 1) == matrix(i,j)
1293                     ? EditOp.none
1294                     : EditOp.substitute;
1295                 --i;
1296                 --j;
1297                 break;
1298             case 1:
1299                 result ~= EditOp.insert;
1300                 --j;
1301                 break;
1302             default:
1303                 result ~= EditOp.remove;
1304                 --i;
1305                 break;
1306             }
1307         }
1308         reverse(result);
1309         return result;
1310     }
1311 
1312     ~this() {
1313         FreeMatrix();
1314     }
1315 
1316 private:
1317     CostType _deletionIncrement = 1,
1318         _insertionIncrement = 1,
1319         _substitutionIncrement = 1;
1320     CostType[] _matrix;
1321     size_t rows, cols;
1322 
1323     // Treat _matrix as a rectangular array
1324     ref CostType matrix(size_t row, size_t col) { return _matrix[row * cols + col]; }
1325 
1326     void AllocMatrix(size_t r, size_t c) @trusted {
1327         import core.checkedint : mulu;
1328         bool overflow;
1329         const rc = mulu(r, c, overflow);
1330         assert(!overflow, "Overflow during multiplication to determine number "
1331                 ~ " of matrix elements");
1332         rows = r;
1333         cols = c;
1334         if (_matrix.length < rc)
1335         {
1336             import core.exception : onOutOfMemoryError;
1337             import core.stdc.stdlib : realloc;
1338             const nbytes = mulu(rc, _matrix[0].sizeof, overflow);
1339             assert(!overflow, "Overflow during multiplication to determine "
1340                 ~ " number of bytes of matrix");
1341             auto m = cast(CostType *) realloc(_matrix.ptr, nbytes);
1342             if (!m)
1343                 onOutOfMemoryError();
1344             _matrix = m[0 .. r * c];
1345             InitMatrix();
1346         }
1347     }
1348 
1349     void FreeMatrix() @trusted {
1350         import core.stdc.stdlib : free;
1351 
1352         free(_matrix.ptr);
1353         _matrix = null;
1354     }
1355 
1356     void InitMatrix() {
1357         foreach (r; 0 .. rows)
1358             matrix(r,0) = r * _deletionIncrement;
1359         foreach (c; 0 .. cols)
1360             matrix(0,c) = c * _insertionIncrement;
1361     }
1362 
1363     static uint min_index(CostType i0, CostType i1, CostType i2)
1364     {
1365         if (i0 <= i1)
1366         {
1367             return i0 <= i2 ? 0 : 2;
1368         }
1369         else
1370         {
1371             return i1 <= i2 ? 1 : 2;
1372         }
1373     }
1374 
1375     CostType distanceWithPath(Range s, Range t)
1376     {
1377         auto slen = walkLength(s.save), tlen = walkLength(t.save);
1378         AllocMatrix(slen + 1, tlen + 1);
1379         foreach (i; 1 .. rows)
1380         {
1381             auto sfront = s.front;
1382             auto tt = t.save;
1383             foreach (j; 1 .. cols)
1384             {
1385                 auto cSub = matrix(i - 1,j - 1)
1386                     + (equals(sfront, tt.front) ? 0 : _substitutionIncrement);
1387                 tt.popFront();
1388                 auto cIns = matrix(i,j - 1) + _insertionIncrement;
1389                 auto cDel = matrix(i - 1,j) + _deletionIncrement;
1390                 switch (min_index(cSub, cIns, cDel))
1391                 {
1392                 case 0:
1393                     matrix(i,j) = cSub;
1394                     break;
1395                 case 1:
1396                     matrix(i,j) = cIns;
1397                     break;
1398                 default:
1399                     matrix(i,j) = cDel;
1400                     break;
1401                 }
1402             }
1403             s.popFront();
1404         }
1405         return matrix(slen,tlen);
1406     }
1407 
1408     CostType distanceLowMem(Range s, Range t, CostType slen, CostType tlen)
1409     {
1410         CostType lastdiag, olddiag;
1411         AllocMatrix(slen + 1, 1);
1412         foreach (y; 1 .. slen + 1)
1413         {
1414             _matrix[y] = y;
1415         }
1416         foreach (x; 1 .. tlen + 1)
1417         {
1418             auto tfront = t.front;
1419             auto ss = s.save;
1420             _matrix[0] = x;
1421             lastdiag = x - 1;
1422             foreach (y; 1 .. rows)
1423             {
1424                 olddiag = _matrix[y];
1425                 auto cSub = lastdiag + (equals(ss.front, tfront) ? 0 : _substitutionIncrement);
1426                 ss.popFront();
1427                 auto cIns = _matrix[y - 1] + _insertionIncrement;
1428                 auto cDel = _matrix[y] + _deletionIncrement;
1429                 switch (min_index(cSub, cIns, cDel))
1430                 {
1431                 case 0:
1432                     _matrix[y] = cSub;
1433                     break;
1434                 case 1:
1435                     _matrix[y] = cIns;
1436                     break;
1437                 default:
1438                     _matrix[y] = cDel;
1439                     break;
1440                 }
1441                 lastdiag = olddiag;
1442             }
1443             t.popFront();
1444         }
1445         return _matrix[slen];
1446     }
1447 }
1448 
1449 /**
1450 Returns the $(HTTP wikipedia.org/wiki/Levenshtein_distance, Levenshtein
1451 distance) between `s` and `t`. The Levenshtein distance computes
1452 the minimal amount of edit operations necessary to transform `s`
1453 into `t`.  Performs $(BIGOH s.length * t.length) evaluations of $(D
1454 equals) and occupies $(BIGOH min(s.length, t.length)) storage.
1455 
1456 Params:
1457     equals = The binary predicate to compare the elements of the two ranges.
1458     s = The original range.
1459     t = The transformation target
1460 
1461 Returns:
1462     The minimal number of edits to transform s into t.
1463 
1464 Does not allocate GC memory.
1465 */
1466 size_t levenshteinDistance(alias equals = (a,b) => a == b, Range1, Range2)
1467     (Range1 s, Range2 t)
1468 if (isForwardRange!(Range1) && isForwardRange!(Range2))
1469 {
1470     alias eq = binaryFun!(equals);
1471 
1472     for (;;)
1473     {
1474         if (s.empty) return t.walkLength;
1475         if (t.empty) return s.walkLength;
1476         if (eq(s.front, t.front))
1477         {
1478             s.popFront();
1479             t.popFront();
1480             continue;
1481         }
1482         static if (isBidirectionalRange!(Range1) && isBidirectionalRange!(Range2))
1483         {
1484             if (eq(s.back, t.back))
1485             {
1486                 s.popBack();
1487                 t.popBack();
1488                 continue;
1489             }
1490         }
1491         break;
1492     }
1493 
1494     auto slen = walkLength(s.save);
1495     auto tlen = walkLength(t.save);
1496 
1497     if (slen == 1 && tlen == 1)
1498     {
1499         return eq(s.front, t.front) ? 0 : 1;
1500     }
1501 
1502     if (slen < tlen)
1503     {
1504         Levenshtein!(Range1, eq, size_t) lev;
1505         return lev.distanceLowMem(s, t, slen, tlen);
1506     }
1507     else
1508     {
1509         Levenshtein!(Range2, eq, size_t) lev;
1510         return lev.distanceLowMem(t, s, tlen, slen);
1511     }
1512 }
1513 
1514 ///
1515 @safe unittest
1516 {
1517     import std.algorithm.iteration : filter;
1518     import std.uni : toUpper;
1519 
1520     assert(levenshteinDistance("cat", "rat") == 1);
1521     assert(levenshteinDistance("parks", "spark") == 2);
1522     assert(levenshteinDistance("abcde", "abcde") == 0);
1523     assert(levenshteinDistance("abcde", "abCde") == 1);
1524     assert(levenshteinDistance("kitten", "sitting") == 3);
1525     assert(levenshteinDistance!((a, b) => toUpper(a) == toUpper(b))
1526         ("parks", "SPARK") == 2);
1527     assert(levenshteinDistance("parks".filter!"true", "spark".filter!"true") == 2);
1528     assert(levenshteinDistance("ID", "I♥D") == 1);
1529 }
1530 
1531 @safe @nogc nothrow unittest
1532 {
1533     assert(levenshteinDistance("cat"d, "rat"d) == 1);
1534 }
1535 
1536 /// ditto
1537 size_t levenshteinDistance(alias equals = (a,b) => a == b, Range1, Range2)
1538     (auto ref Range1 s, auto ref Range2 t)
1539 if (isConvertibleToString!Range1 || isConvertibleToString!Range2)
1540 {
1541     import std.meta : staticMap;
1542     alias Types = staticMap!(convertToString, Range1, Range2);
1543     return levenshteinDistance!(equals, Types)(s, t);
1544 }
1545 
1546 @safe unittest
1547 {
1548     static struct S { string s; alias s this; }
1549     assert(levenshteinDistance(S("cat"), S("rat")) == 1);
1550     assert(levenshteinDistance("cat", S("rat")) == 1);
1551     assert(levenshteinDistance(S("cat"), "rat") == 1);
1552 }
1553 
1554 @safe @nogc nothrow unittest
1555 {
1556     static struct S { dstring s; alias s this; }
1557     assert(levenshteinDistance(S("cat"d), S("rat"d)) == 1);
1558     assert(levenshteinDistance("cat"d, S("rat"d)) == 1);
1559     assert(levenshteinDistance(S("cat"d), "rat"d) == 1);
1560 }
1561 
1562 /**
1563 Returns the Levenshtein distance and the edit path between `s` and
1564 `t`.
1565 
1566 Params:
1567     equals = The binary predicate to compare the elements of the two ranges.
1568     s = The original range.
1569     t = The transformation target
1570 
1571 Returns:
1572     Tuple with the first element being the minimal amount of edits to transform s into t and
1573     the second element being the sequence of edits to effect this transformation.
1574 
1575 Allocates GC memory for the returned EditOp[] array.
1576 */
1577 Tuple!(size_t, EditOp[])
1578 levenshteinDistanceAndPath(alias equals = (a,b) => a == b, Range1, Range2)
1579     (Range1 s, Range2 t)
1580 if (isForwardRange!(Range1) && isForwardRange!(Range2))
1581 {
1582     Levenshtein!(Range1, binaryFun!(equals)) lev;
1583     auto d = lev.distanceWithPath(s, t);
1584     return tuple(d, lev.path());
1585 }
1586 
1587 ///
1588 @safe unittest
1589 {
1590     string a = "Saturday", b = "Sundays";
1591     auto p = levenshteinDistanceAndPath(a, b);
1592     assert(p[0] == 4);
1593     assert(equal(p[1], "nrrnsnnni"));
1594 }
1595 
1596 @safe unittest
1597 {
1598     assert(levenshteinDistance("a", "a") == 0);
1599     assert(levenshteinDistance("a", "b") == 1);
1600     assert(levenshteinDistance("aa", "ab") == 1);
1601     assert(levenshteinDistance("aa", "abc") == 2);
1602     assert(levenshteinDistance("Saturday", "Sunday") == 3);
1603     assert(levenshteinDistance("kitten", "sitting") == 3);
1604 }
1605 
1606 /// ditto
1607 Tuple!(size_t, EditOp[])
1608 levenshteinDistanceAndPath(alias equals = (a,b) => a == b, Range1, Range2)
1609     (auto ref Range1 s, auto ref Range2 t)
1610 if (isConvertibleToString!Range1 || isConvertibleToString!Range2)
1611 {
1612     import std.meta : staticMap;
1613     alias Types = staticMap!(convertToString, Range1, Range2);
1614     return levenshteinDistanceAndPath!(equals, Types)(s, t);
1615 }
1616 
1617 @safe unittest
1618 {
1619     static struct S { string s; alias s this; }
1620     assert(levenshteinDistanceAndPath(S("cat"), S("rat"))[0] == 1);
1621     assert(levenshteinDistanceAndPath("cat", S("rat"))[0] == 1);
1622     assert(levenshteinDistanceAndPath(S("cat"), "rat")[0] == 1);
1623 }
1624 
1625 
1626 // max
1627 /**
1628 Iterates the passed arguments and returns the maximum value.
1629 
1630 Params:
1631     args = The values to select the maximum from. At least two arguments must
1632     be passed, and they must be comparable with `<`.
1633 
1634 Returns:
1635     The maximum of the passed-in values. The type of the returned value is
1636     the type among the passed arguments that is able to store the largest value.
1637     If at least one of the arguments is NaN, the result is an unspecified value.
1638     See $(REF maxElement, std,algorithm,searching) for examples on how to cope
1639     with NaNs.
1640 
1641 See_Also:
1642     $(REF maxElement, std,algorithm,searching)
1643 */
1644 auto max(T...)(T args)
1645 if (T.length >= 2 && !is(CommonType!T == void))
1646 {
1647     // Get left-hand side of the comparison.
1648     static if (T.length == 2)
1649         alias a = args[0];
1650     else
1651         auto a = max(args[0 .. ($ + 1) / 2]);
1652     alias T0 = typeof(a);
1653 
1654     // Get right-hand side.
1655     static if (T.length <= 3)
1656         alias b = args[$ - 1];
1657     else
1658         auto b = max(args[($ + 1) / 2 .. $]);
1659     alias T1 = typeof(b);
1660 
1661     static assert(is(typeof(a < b)),
1662         "Invalid arguments: Cannot compare types " ~ T0.stringof ~
1663         " and " ~ T1.stringof ~ " for ordering.");
1664 
1665     // Compute the returned type.
1666     static if (is(typeof(mostNegative!T0 < mostNegative!T1)))
1667         // Both are numeric (or character or Boolean), so we choose the one with the highest maximum.
1668         // (We use mostNegative for num/bool/char testing purposes even if it's not used otherwise.)
1669         alias Result = Select!(T1.max > T0.max, T1, T0);
1670     else
1671         // At least one is non-numeric, so just go with the common type.
1672         alias Result = CommonType!(T0, T1);
1673 
1674     // Perform the computation.
1675     import std.functional : lessThan;
1676     immutable chooseB = lessThan!(T0, T1)(a, b);
1677     return cast(Result) (chooseB ? b : a);
1678 }
1679 
1680 /// ditto
1681 T max(T, U)(T a, U b)
1682 if (is(T == U) && is(typeof(a < b)))
1683 {
1684    /* Handle the common case without all the template expansions
1685     * of the general case
1686     */
1687     return a < b ? b : a;
1688 }
1689 
1690 ///
1691 @safe @betterC @nogc unittest
1692 {
1693     int a = 5;
1694     short b = 6;
1695     double c = 2;
1696     auto d = max(a, b);
1697     assert(is(typeof(d) == int));
1698     assert(d == 6);
1699     auto e = min(a, b, c);
1700     assert(is(typeof(e) == double));
1701     assert(e == 2);
1702 }
1703 
1704 @safe unittest  // not @nogc due to `Date`
1705 {
1706     int a = 5;
1707     short b = 6;
1708     double c = 2;
1709     auto d = max(a, b);
1710     static assert(is(typeof(d) == int));
1711     assert(d == 6);
1712     auto e = max(a, b, c);
1713     static assert(is(typeof(e) == double));
1714     assert(e == 6);
1715     // mixed sign
1716     a = -5;
1717     uint f = 5;
1718     static assert(is(typeof(max(a, f)) == uint));
1719     assert(max(a, f) == 5);
1720 
1721     //Test user-defined types
1722     import std.datetime : Date;
1723     assert(max(Date(2012, 12, 21), Date(1982, 1, 4)) == Date(2012, 12, 21));
1724     assert(max(Date(1982, 1, 4), Date(2012, 12, 21)) == Date(2012, 12, 21));
1725     assert(max(Date(1982, 1, 4), Date.min) == Date(1982, 1, 4));
1726     assert(max(Date.min, Date(1982, 1, 4)) == Date(1982, 1, 4));
1727     assert(max(Date(1982, 1, 4), Date.max) == Date.max);
1728     assert(max(Date.max, Date(1982, 1, 4)) == Date.max);
1729     assert(max(Date.min, Date.max) == Date.max);
1730     assert(max(Date.max, Date.min) == Date.max);
1731 }
1732 
1733 // min
1734 /**
1735 Iterates the passed arguments and returns the minimum value.
1736 
1737 Params:
1738     args = The values to select the minimum from. At least two arguments must
1739     be passed, and they must be comparable with `<`.
1740 
1741 Returns:
1742     The minimum of the passed-in values. The type of the returned value is
1743     the type among the passed arguments that is able to store the smallest value.
1744     If at least one of the arguments is NaN, the result is an unspecified value.
1745     See $(REF minElement, std,algorithm,searching) for examples on how to cope
1746     with NaNs.
1747 
1748 See_Also:
1749     $(REF minElement, std,algorithm,searching)
1750 */
1751 auto min(T...)(T args)
1752 if (T.length >= 2 && !is(CommonType!T == void))
1753 {
1754     // Get the left-hand side of the comparison.
1755     static if (T.length <= 2)
1756         alias a = args[0];
1757     else
1758         auto a = min(args[0 .. ($ + 1) / 2]);
1759     alias T0 = typeof(a);
1760 
1761     // Get the right-hand side.
1762     static if (T.length <= 3)
1763         alias b = args[$ - 1];
1764     else
1765         auto b = min(args[($ + 1) / 2 .. $]);
1766     alias T1 = typeof(b);
1767 
1768     static assert(is(typeof(a < b)),
1769         "Invalid arguments: Cannot compare types " ~ T0.stringof ~
1770         " and " ~ T1.stringof ~ " for ordering.");
1771 
1772     // Compute the returned type.
1773     static if (is(typeof(mostNegative!T0 < mostNegative!T1)))
1774         // Both are numeric (or character or Boolean), so we choose the one with the lowest minimum.
1775         // If they have the same minimum, choose the one with the smallest size.
1776         // If both mostNegative and sizeof are equal, go for stability: pick the type of the first one.
1777         alias Result = Select!(mostNegative!T1 < mostNegative!T0 ||
1778                 mostNegative!T1 == mostNegative!T0 && T1.sizeof < T0.sizeof,
1779             T1, T0);
1780     else
1781         // At least one is non-numeric, so just go with the common type.
1782         alias Result = CommonType!(T0, T1);
1783 
1784     // Engage!
1785     import std.functional : lessThan;
1786     immutable chooseB = lessThan!(T1, T0)(b, a);
1787     return cast(Result) (chooseB ? b : a);
1788 }
1789 
1790 /// ditto
1791 T min(T, U)(T a, U b)
1792 if (is(T == U) && is(typeof(a < b)))
1793 {
1794    /* Handle the common case without all the template expansions
1795     * of the general case
1796     */
1797     return b < a ? b : a;
1798 }
1799 
1800 
1801 ///
1802 @safe @nogc @betterC unittest
1803 {
1804     int a = 5;
1805     short b = 6;
1806     double c = 2;
1807     auto d = min(a, b);
1808     static assert(is(typeof(d) == int));
1809     assert(d == 5);
1810     auto e = min(a, b, c);
1811     static assert(is(typeof(e) == double));
1812     assert(e == 2);
1813     ulong f = 0xffff_ffff_ffff;
1814     const uint g = min(f, 0xffff_0000);
1815     assert(g == 0xffff_0000);
1816     dchar h = 100;
1817     uint i = 101;
1818     static assert(is(typeof(min(h, i)) == dchar));
1819     static assert(is(typeof(min(i, h)) == uint));
1820     assert(min(h, i) == 100);
1821 }
1822 
1823 /**
1824 With arguments of mixed signedness, the return type is the one that can
1825 store the lowest values.
1826 */
1827 @safe @nogc @betterC unittest
1828 {
1829     int a = -10;
1830     uint f = 10;
1831     static assert(is(typeof(min(a, f)) == int));
1832     assert(min(a, f) == -10);
1833 }
1834 
1835 /// User-defined types that support comparison with < are supported.
1836 @safe unittest  // not @nogc due to `Date`
1837 {
1838     import std.datetime;
1839     assert(min(Date(2012, 12, 21), Date(1982, 1, 4)) == Date(1982, 1, 4));
1840     assert(min(Date(1982, 1, 4), Date(2012, 12, 21)) == Date(1982, 1, 4));
1841     assert(min(Date(1982, 1, 4), Date.min) == Date.min);
1842     assert(min(Date.min, Date(1982, 1, 4)) == Date.min);
1843     assert(min(Date(1982, 1, 4), Date.max) == Date(1982, 1, 4));
1844     assert(min(Date.max, Date(1982, 1, 4)) == Date(1982, 1, 4));
1845     assert(min(Date.min, Date.max) == Date.min);
1846     assert(min(Date.max, Date.min) == Date.min);
1847 }
1848 
1849 // min must be stable: when in doubt, return the first argument.
1850 @safe unittest
1851 {
1852     assert(min(1.0, double.nan) == 1.0);
1853     assert(min(double.nan, 1.0) is double.nan);
1854     static struct A {
1855         int x;
1856         string y;
1857         int opCmp(const A a) const { return int(x > a.x) - int(x < a.x); }
1858     }
1859     assert(min(A(1, "first"), A(1, "second")) == A(1, "first"));
1860 }
1861 
1862 // mismatch
1863 /**
1864 Sequentially compares elements in `rs` in lockstep, and
1865 stops at the first mismatch (according to `pred`, by default
1866 equality). Returns a tuple with the reduced ranges that start with the
1867 two mismatched values. Performs $(BIGOH min(r[0].length, r[1].length, ...))
1868 evaluations of `pred`.
1869 */
1870 Tuple!(Ranges)
1871 mismatch(alias pred = (a, b) => a == b, Ranges...)(Ranges rs)
1872 if (rs.length >= 2 && allSatisfy!(isInputRange, Ranges))
1873 {
1874     loop: for (; !rs[0].empty; rs[0].popFront)
1875     {
1876         static foreach (r; rs[1 .. $])
1877         {
1878             if (r.empty || !binaryFun!pred(rs[0].front, r.front))
1879                 break loop;
1880             r.popFront;
1881         }
1882     }
1883     return tuple(rs);
1884 }
1885 
1886 ///
1887 @safe @nogc unittest
1888 {
1889     int[6] x = [ 1,   5, 2, 7,   4, 3 ];
1890     double[6] y = [ 1.0, 5, 2, 7.3, 4, 8 ];
1891     auto m = mismatch(x[], y[]);
1892     assert(m[0] == x[3 .. $]);
1893     assert(m[1] == y[3 .. $]);
1894 
1895     auto m2 = mismatch(x[], y[], x[], y[]);
1896     assert(m2[0] == x[3 .. $]);
1897     assert(m2[1] == y[3 .. $]);
1898     assert(m2[2] == x[3 .. $]);
1899     assert(m2[3] == y[3 .. $]);
1900 }
1901 
1902 @safe @nogc unittest
1903 {
1904     import std.range : only;
1905 
1906     int[3] a = [ 1, 2, 3 ];
1907     int[4] b = [ 1, 2, 4, 5 ];
1908     auto mm = mismatch(a[], b[]);
1909     assert(equal(mm[0], only(3)));
1910     assert(equal(mm[1], only(4, 5)));
1911 }
1912 
1913 /**
1914 Returns one of a collection of expressions based on the value of the switch
1915 expression.
1916 
1917 `choices` needs to be composed of pairs of test expressions and return
1918 expressions. Each test-expression is compared with `switchExpression` using
1919 `pred`(`switchExpression` is the first argument) and if that yields true -
1920 the return expression is returned.
1921 
1922 Both the test and the return expressions are lazily evaluated.
1923 
1924 Params:
1925 
1926 switchExpression = The first argument for the predicate.
1927 
1928 choices = Pairs of test expressions and return expressions. The test
1929 expressions will be the second argument for the predicate, and the return
1930 expression will be returned if the predicate yields true with $(D
1931 switchExpression) and the test expression as arguments.  May also have a
1932 default return expression, that needs to be the last expression without a test
1933 expression before it. A return expression may be of void type only if it
1934 always throws.
1935 
1936 Returns: The return expression associated with the first test expression that
1937 made the predicate yield true, or the default return expression if no test
1938 expression matched.
1939 
1940 Throws: If there is no default return expression and the predicate does not
1941 yield true with any test expression - `SwitchError` is thrown. $(D
1942 SwitchError) is also thrown if a void return expression was executed without
1943 throwing anything.
1944 */
1945 auto predSwitch(alias pred = "a == b", T, R ...)(T switchExpression, lazy R choices)
1946 {
1947     import core.exception : SwitchError;
1948     alias predicate = binaryFun!(pred);
1949 
1950     foreach (index, ChoiceType; R)
1951     {
1952         //The even places in `choices` are for the predicate.
1953         static if (index % 2 == 1)
1954         {
1955             if (predicate(switchExpression, choices[index - 1]()))
1956             {
1957                 static if (is(typeof(choices[index]()) == void))
1958                 {
1959                     choices[index]();
1960                     throw new SwitchError("Choices that return void should throw");
1961                 }
1962                 else
1963                 {
1964                     return choices[index]();
1965                 }
1966             }
1967         }
1968     }
1969 
1970     //In case nothing matched:
1971     static if (R.length % 2 == 1) //If there is a default return expression:
1972     {
1973         static if (is(typeof(choices[$ - 1]()) == void))
1974         {
1975             choices[$ - 1]();
1976             throw new SwitchError("Choices that return void should throw");
1977         }
1978         else
1979         {
1980             return choices[$ - 1]();
1981         }
1982     }
1983     else //If there is no default return expression:
1984     {
1985         throw new SwitchError("Input not matched by any pattern");
1986     }
1987 }
1988 
1989 ///
1990 @safe unittest
1991 {
1992     string res = 2.predSwitch!"a < b"(
1993         1, "less than 1",
1994         5, "less than 5",
1995         10, "less than 10",
1996         "greater or equal to 10");
1997 
1998     assert(res == "less than 5");
1999 
2000     //The arguments are lazy, which allows us to use predSwitch to create
2001     //recursive functions:
2002     int factorial(int n)
2003     {
2004         return n.predSwitch!"a <= b"(
2005             -1, {throw new Exception("Can not calculate n! for n < 0");}(),
2006             0, 1, // 0! = 1
2007             n * factorial(n - 1) // n! = n * (n - 1)! for n >= 0
2008             );
2009     }
2010     assert(factorial(3) == 6);
2011 
2012     //Void return expressions are allowed if they always throw:
2013     import std.exception : assertThrown;
2014     assertThrown!Exception(factorial(-9));
2015 }
2016 
2017 @system unittest
2018 {
2019     import core.exception : SwitchError;
2020     import std.exception : assertThrown;
2021 
2022     //Nothing matches - with default return expression:
2023     assert(20.predSwitch!"a < b"(
2024         1, "less than 1",
2025         5, "less than 5",
2026         10, "less than 10",
2027         "greater or equal to 10") == "greater or equal to 10");
2028 
2029     //Nothing matches - without default return expression:
2030     assertThrown!SwitchError(20.predSwitch!"a < b"(
2031         1, "less than 1",
2032         5, "less than 5",
2033         10, "less than 10",
2034         ));
2035 
2036     //Using the default predicate:
2037     assert(2.predSwitch(
2038                 1, "one",
2039                 2, "two",
2040                 3, "three",
2041                 ) == "two");
2042 
2043     //Void return expressions must always throw:
2044     assertThrown!SwitchError(1.predSwitch(
2045                 0, "zero",
2046                 1, {}(), //A void return expression that doesn't throw
2047                 2, "two",
2048                 ));
2049 }
2050 
2051 /**
2052 Checks if two or more ranges have the same number of elements. This function is
2053 optimized to always take advantage of the `length` member of either range
2054 if it exists.
2055 
2056 If all ranges have a `length` member or at least one is infinite,
2057 `_isSameLength`'s complexity is $(BIGOH 1). Otherwise, complexity is
2058 $(BIGOH n), where `n` is the smallest of the lengths of ranges with unknown
2059 length.
2060 
2061 Infinite ranges are considered of the same length. An infinite range has never
2062 the same length as a finite range.
2063 
2064 Params:
2065     rs = two or more $(REF_ALTTEXT input ranges, isInputRange, std,range,primitives)
2066 
2067 Returns:
2068     `true` if both ranges have the same length, `false` otherwise.
2069 */
2070 bool isSameLength(Ranges...)(Ranges rs)
2071 if (allSatisfy!(isInputRange, Ranges))
2072 {
2073     static if (anySatisfy!(isInfinite, Ranges))
2074     {
2075         return allSatisfy!(isInfinite, Ranges);
2076     }
2077     else static if (anySatisfy!(hasLength, Ranges))
2078     {
2079         // Compute the O(1) length
2080         auto baselineLength = size_t.max;
2081         static foreach (i, R; Ranges)
2082         {
2083             static if (hasLength!R)
2084             {
2085                 if (baselineLength == size_t.max)
2086                     baselineLength = rs[i].length;
2087                 else if (rs[i].length != baselineLength)
2088                     return false;
2089             }
2090         }
2091         // Iterate all ranges without known length
2092         foreach (_; 0 .. baselineLength)
2093             static foreach (i, R; Ranges)
2094             {
2095                 static if (!hasLength!R)
2096                 {
2097                     // All must be non-empty
2098                     if (rs[i].empty)
2099                         return false;
2100                     rs[i].popFront;
2101                 }
2102             }
2103         static foreach (i, R; Ranges)
2104         {
2105             static if (!hasLength!R)
2106             {
2107                 // All must be now empty
2108                 if (!rs[i].empty)
2109                     return false;
2110             }
2111         }
2112         return true;
2113     }
2114     else
2115     {
2116         // All have unknown length, iterate in lockstep
2117         for (;;)
2118             static foreach (i, r; rs)
2119             {
2120                 if (r.empty)
2121                 {
2122                     // One is empty, so all must be empty
2123                     static if (i != 0)
2124                     {
2125                         return false;
2126                     }
2127                     else
2128                     {
2129                         static foreach (j, r1; rs[1 .. $])
2130                             if (!r1.empty)
2131                                 return false;
2132                         return true;
2133                     }
2134                 }
2135                 r.popFront;
2136             }
2137     }
2138 }
2139 
2140 ///
2141 @safe nothrow pure unittest
2142 {
2143     assert(isSameLength([1, 2, 3], [4, 5, 6]));
2144     assert(isSameLength([1, 2, 3], [4, 5, 6], [7, 8, 9]));
2145     assert(isSameLength([0.3, 90.4, 23.7, 119.2], [42.6, 23.6, 95.5, 6.3]));
2146     assert(isSameLength("abc", "xyz"));
2147     assert(isSameLength("abc", "xyz", [1, 2, 3]));
2148 
2149     int[] a;
2150     int[] b;
2151     assert(isSameLength(a, b));
2152     assert(isSameLength(a, b, a, a, b, b, b));
2153 
2154     assert(!isSameLength([1, 2, 3], [4, 5]));
2155     assert(!isSameLength([1, 2, 3], [4, 5, 6], [7, 8]));
2156     assert(!isSameLength([0.3, 90.4, 23.7], [42.6, 23.6, 95.5, 6.3]));
2157     assert(!isSameLength("abcd", "xyz"));
2158     assert(!isSameLength("abcd", "xyz", "123"));
2159     assert(!isSameLength("abcd", "xyz", "1234"));
2160 }
2161 
2162 // Test CTFE
2163 @safe @nogc pure @betterC unittest
2164 {
2165     static assert(isSameLength([1, 2, 3], [4, 5, 6]));
2166     static assert(isSameLength([1, 2, 3], [4, 5, 6], [7, 8, 9]));
2167     static assert(!isSameLength([0.3, 90.4, 23.7], [42.6, 23.6, 95.5, 6.3]));
2168     static assert(!isSameLength([1], [0.3, 90.4], [42]));
2169 }
2170 
2171 @safe @nogc pure unittest
2172 {
2173     import std.range : only;
2174     assert(isSameLength(only(1, 2, 3), only(4, 5, 6)));
2175     assert(isSameLength(only(1, 2, 3), only(4, 5, 6), only(7, 8, 9)));
2176     assert(isSameLength(only(0.3, 90.4, 23.7, 119.2), only(42.6, 23.6, 95.5, 6.3)));
2177     assert(!isSameLength(only(1, 3, 3), only(4, 5)));
2178     assert(!isSameLength(only(1, 3, 3), only(1, 3, 3), only(4, 5)));
2179     assert(!isSameLength(only(1, 3, 3), only(4, 5), only(1, 3, 3)));
2180 }
2181 
2182 @safe nothrow pure unittest
2183 {
2184     import std.internal.test.dummyrange;
2185 
2186     auto r1 = new ReferenceInputRange!int([1, 2, 3]);
2187     auto r2 = new ReferenceInputRange!int([4, 5, 6]);
2188     assert(isSameLength(r1, r2));
2189 
2190     auto r3 = new ReferenceInputRange!int([1, 2, 3, 4, 5, 6, 7, 8, 9, 10]);
2191     DummyRange!(ReturnBy.Reference, Length.Yes, RangeType.Input) r4;
2192     assert(isSameLength(r3, r4));
2193 
2194     DummyRange!(ReturnBy.Reference, Length.Yes, RangeType.Input) r5;
2195     auto r6 = new ReferenceInputRange!int([1, 2, 3, 4, 5, 6, 7, 8, 9, 10]);
2196     assert(isSameLength(r5, r6));
2197 
2198     auto r7 = new ReferenceInputRange!int([1, 2]);
2199     auto r8 = new ReferenceInputRange!int([4, 5, 6]);
2200     assert(!isSameLength(r7, r8));
2201 
2202     auto r9 = new ReferenceInputRange!int([1, 2, 3, 4, 5, 6, 7, 8]);
2203     DummyRange!(ReturnBy.Reference, Length.Yes, RangeType.Input) r10;
2204     assert(!isSameLength(r9, r10));
2205 
2206     DummyRange!(ReturnBy.Reference, Length.Yes, RangeType.Input) r11;
2207     auto r12 = new ReferenceInputRange!int([1, 2, 3, 4, 5, 6, 7, 8]);
2208     assert(!isSameLength(r11, r12));
2209 
2210     import std.algorithm.iteration : filter;
2211 
2212     assert(isSameLength(filter!"a >= 1"([1, 2, 3]), [4, 5, 6]));
2213     assert(!isSameLength(filter!"a > 1"([1, 2, 3]), [4, 5, 6]));
2214 
2215     assert(isSameLength(filter!"a > 1"([1, 2, 3]), filter!"a > 4"([4, 5, 6])));
2216     assert(isSameLength(filter!"a > 1"([1, 2, 3]),
2217         filter!"a > 4"([4, 5, 6]), filter!"a >= 5"([4, 5, 6])));
2218 }
2219 
2220 // Still functional but not documented anymore.
2221 alias AllocateGC = Flag!"allocateGC";
2222 
2223 /**
2224 Checks if both ranges are permutations of each other.
2225 
2226 This function can allocate if the `Yes.allocateGC` flag is passed. This has
2227 the benefit of have better complexity than the `Yes.allocateGC` option. However,
2228 this option is only available for ranges whose equality can be determined via each
2229 element's `toHash` method. If customized equality is needed, then the `pred`
2230 template parameter can be passed, and the function will automatically switch to
2231 the non-allocating algorithm. See $(REF binaryFun, std,functional) for more details on
2232 how to define `pred`.
2233 
2234 Non-allocating forward range option: $(BIGOH n^2)
2235 Non-allocating forward range option with custom `pred`: $(BIGOH n^2)
2236 Allocating forward range option: amortized $(BIGOH r1.length) + $(BIGOH r2.length)
2237 
2238 Params:
2239     pred = an optional parameter to change how equality is defined
2240     allocateGC = `Yes.allocateGC`/`No.allocateGC`
2241     r1 = A finite $(REF_ALTTEXT forward range, isForwardRange, std,range,primitives)
2242     r2 = A finite $(REF_ALTTEXT forward range, isForwardRange, std,range,primitives)
2243 
2244 Returns:
2245     `true` if all of the elements in `r1` appear the same number of times in `r2`.
2246     Otherwise, returns `false`.
2247 */
2248 
2249 bool isPermutation(Flag!"allocateGC" allocateGC, Range1, Range2)
2250 (Range1 r1, Range2 r2)
2251 if (allocateGC == Yes.allocateGC &&
2252     isForwardRange!Range1 &&
2253     isForwardRange!Range2 &&
2254     !isInfinite!Range1 &&
2255     !isInfinite!Range2)
2256 {
2257     alias E1 = Unqual!(ElementType!Range1);
2258     alias E2 = Unqual!(ElementType!Range2);
2259 
2260     if (!isSameLength(r1.save, r2.save))
2261     {
2262         return false;
2263     }
2264 
2265     // Skip the elements at the beginning where r1.front == r2.front,
2266     // they are in the same order and don't need to be counted.
2267     while (!r1.empty && !r2.empty && r1.front == r2.front)
2268     {
2269         r1.popFront();
2270         r2.popFront();
2271     }
2272 
2273     if (r1.empty && r2.empty)
2274     {
2275         return true;
2276     }
2277 
2278     int[CommonType!(E1, E2)] counts;
2279 
2280     foreach (item; r1)
2281     {
2282         ++counts[item];
2283     }
2284 
2285     foreach (item; r2)
2286     {
2287         if (--counts[item] < 0)
2288         {
2289             return false;
2290         }
2291     }
2292 
2293     return true;
2294 }
2295 
2296 /// ditto
2297 bool isPermutation(alias pred = "a == b", Range1, Range2)
2298 (Range1 r1, Range2 r2)
2299 if (is(typeof(binaryFun!(pred))) &&
2300     isForwardRange!Range1 &&
2301     isForwardRange!Range2 &&
2302     !isInfinite!Range1 &&
2303     !isInfinite!Range2)
2304 {
2305     import std.algorithm.searching : count;
2306 
2307     alias predEquals = binaryFun!(pred);
2308     alias E1 = Unqual!(ElementType!Range1);
2309     alias E2 = Unqual!(ElementType!Range2);
2310 
2311     if (!isSameLength(r1.save, r2.save))
2312     {
2313         return false;
2314     }
2315 
2316     // Skip the elements at the beginning where r1.front == r2.front,
2317     // they are in the same order and don't need to be counted.
2318     while (!r1.empty && !r2.empty && predEquals(r1.front, r2.front))
2319     {
2320         r1.popFront();
2321         r2.popFront();
2322     }
2323 
2324     if (r1.empty && r2.empty)
2325     {
2326         return true;
2327     }
2328 
2329     size_t r1_count;
2330     size_t r2_count;
2331 
2332     // At each element item, when computing the count of item, scan it while
2333     // also keeping track of the scanning index. If the first occurrence
2334     // of item in the scanning loop has an index smaller than the current index,
2335     // then you know that the element has been seen before
2336     size_t index;
2337     outloop: for (auto r1s1 = r1.save; !r1s1.empty; r1s1.popFront, index++)
2338     {
2339         auto item = r1s1.front;
2340         r1_count = 0;
2341         r2_count = 0;
2342 
2343         size_t i;
2344         for (auto r1s2 = r1.save; !r1s2.empty; r1s2.popFront, i++)
2345         {
2346             auto e = r1s2.front;
2347             if (predEquals(e, item) && i < index)
2348             {
2349                  continue outloop;
2350             }
2351             else if (predEquals(e, item))
2352             {
2353                 ++r1_count;
2354             }
2355         }
2356 
2357         r2_count = r2.save.count!pred(item);
2358 
2359         if (r1_count != r2_count)
2360         {
2361             return false;
2362         }
2363     }
2364 
2365     return true;
2366 }
2367 
2368 ///
2369 @safe pure unittest
2370 {
2371     import std.typecons : Yes;
2372 
2373     assert(isPermutation([1, 2, 3], [3, 2, 1]));
2374     assert(isPermutation([1.1, 2.3, 3.5], [2.3, 3.5, 1.1]));
2375     assert(isPermutation("abc", "bca"));
2376 
2377     assert(!isPermutation([1, 2], [3, 4]));
2378     assert(!isPermutation([1, 1, 2, 3], [1, 2, 2, 3]));
2379     assert(!isPermutation([1, 1], [1, 1, 1]));
2380 
2381     // Faster, but allocates GC handled memory
2382     assert(isPermutation!(Yes.allocateGC)([1.1, 2.3, 3.5], [2.3, 3.5, 1.1]));
2383     assert(!isPermutation!(Yes.allocateGC)([1, 2], [3, 4]));
2384 }
2385 
2386 // Test @nogc inference
2387 @safe @nogc pure unittest
2388 {
2389     static immutable arr1 = [1, 2, 3];
2390     static immutable arr2 = [3, 2, 1];
2391     assert(isPermutation(arr1, arr2));
2392 
2393     static immutable arr3 = [1, 1, 2, 3];
2394     static immutable arr4 = [1, 2, 2, 3];
2395     assert(!isPermutation(arr3, arr4));
2396 }
2397 
2398 @safe pure unittest
2399 {
2400     import std.internal.test.dummyrange;
2401 
2402     auto r1 = new ReferenceForwardRange!int([1, 2, 3, 4]);
2403     auto r2 = new ReferenceForwardRange!int([1, 2, 4, 3]);
2404     assert(isPermutation(r1, r2));
2405 
2406     auto r3 = new ReferenceForwardRange!int([1, 2, 3, 4]);
2407     auto r4 = new ReferenceForwardRange!int([4, 2, 1, 3]);
2408     assert(isPermutation!(Yes.allocateGC)(r3, r4));
2409 
2410     auto r5 = new ReferenceForwardRange!int([1, 2, 3]);
2411     auto r6 = new ReferenceForwardRange!int([4, 2, 1, 3]);
2412     assert(!isPermutation(r5, r6));
2413 
2414     auto r7 = new ReferenceForwardRange!int([4, 2, 1, 3]);
2415     auto r8 = new ReferenceForwardRange!int([1, 2, 3]);
2416     assert(!isPermutation!(Yes.allocateGC)(r7, r8));
2417 
2418     DummyRange!(ReturnBy.Reference, Length.Yes, RangeType.Random) r9;
2419     DummyRange!(ReturnBy.Reference, Length.Yes, RangeType.Random) r10;
2420     assert(isPermutation(r9, r10));
2421 
2422     DummyRange!(ReturnBy.Reference, Length.Yes, RangeType.Random) r11;
2423     DummyRange!(ReturnBy.Reference, Length.Yes, RangeType.Random) r12;
2424     assert(isPermutation!(Yes.allocateGC)(r11, r12));
2425 
2426     alias mytuple = Tuple!(int, int);
2427 
2428     assert(isPermutation!"a[0] == b[0]"(
2429         [mytuple(1, 4), mytuple(2, 5)],
2430         [mytuple(2, 3), mytuple(1, 2)]
2431     ));
2432 }
2433 
2434 /**
2435 Get the _first argument `a` that passes an `if (unaryFun!pred(a))` test.  If
2436 no argument passes the test, return the last argument.
2437 
2438 Similar to behaviour of the `or` operator in dynamic languages such as Lisp's
2439 `(or ...)` and Python's `a or b or ...` except that the last argument is
2440 returned upon no match.
2441 
2442 Simplifies logic, for instance, in parsing rules where a set of alternative
2443 matchers are tried. The _first one that matches returns it match result,
2444 typically as an abstract syntax tree (AST).
2445 
2446 Bugs:
2447 Lazy parameters are currently, too restrictively, inferred by DMD to
2448 always throw even though they don't need to be. This makes it impossible to
2449 currently mark `either` as `nothrow`. See issue at $(BUGZILLA 12647).
2450 
2451 Returns:
2452     The _first argument that passes the test `pred`.
2453 */
2454 CommonType!(T, Ts) either(alias pred = a => a, T, Ts...)(T first, lazy Ts alternatives)
2455 if (alternatives.length >= 1 &&
2456     !is(CommonType!(T, Ts) == void) &&
2457     allSatisfy!(ifTestable, T, Ts))
2458 {
2459     alias predFun = unaryFun!pred;
2460 
2461     if (predFun(first)) return first;
2462 
2463     foreach (e; alternatives[0 .. $ - 1])
2464         if (predFun(e)) return e;
2465 
2466     return alternatives[$ - 1];
2467 }
2468 
2469 ///
2470 @safe pure @betterC unittest
2471 {
2472     const a = 1;
2473     const b = 2;
2474     auto ab = either(a, b);
2475     static assert(is(typeof(ab) == const(int)));
2476     assert(ab == a);
2477 
2478     auto c = 2;
2479     const d = 3;
2480     auto cd = either!(a => a == 3)(c, d); // use predicate
2481     static assert(is(typeof(cd) == int));
2482     assert(cd == d);
2483 
2484     auto e = 0;
2485     const f = 2;
2486     auto ef = either(e, f);
2487     static assert(is(typeof(ef) == int));
2488     assert(ef == f);
2489 }
2490 
2491 ///
2492 @safe pure unittest
2493 {
2494     immutable p = 1;
2495     immutable q = 2;
2496     auto pq = either(p, q);
2497     static assert(is(typeof(pq) == immutable(int)));
2498     assert(pq == p);
2499 
2500     assert(either(3, 4) == 3);
2501     assert(either(0, 4) == 4);
2502     assert(either(0, 0) == 0);
2503     assert(either("", "a") == "");
2504 }
2505 
2506 ///
2507 @safe pure unittest
2508 {
2509     string r = null;
2510     assert(either(r, "a") == "a");
2511     assert(either("a", "") == "a");
2512 
2513     immutable s = [1, 2];
2514     assert(either(s, s) == s);
2515 
2516     assert(either([0, 1], [1, 2]) == [0, 1]);
2517     assert(either([0, 1], [1]) == [0, 1]);
2518     assert(either("a", "b") == "a");
2519 
2520     static assert(!__traits(compiles, either(1, "a")));
2521     static assert(!__traits(compiles, either(1.0, "a")));
2522     static assert(!__traits(compiles, either('a', "a")));
2523 }