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 {
foreach(uint i,ref v;values)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.
indexOfFirstOvershadowingChoiceOnLast(choices...)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 */
castSwitch(choices...)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;
this(int a)383 this(int a) {this.a = a;}
i()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
objectSkip(Object)521 static void objectSkip(Object) {}
defaultSkip()522 static void defaultSkip() {}
523
objectError(Object)524 static noreturn objectError(Object) { assert(false); }
defaultError()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
objectValue(Object)539 static int objectValue(Object) { return 1;}
defaultValue()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();
objectFunc(Object)552 static FP objectFunc(Object) { return &defaultSkip; }
defaultFunc()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 if (is(typeof(val.lessThan(lower) ? lower : val.greaterThan(upper) ? upper : val) : T1))
581 in
582 {
583 assert(!lower.greaterThan(upper), "Lower can't be greater than upper.");
584 }
585 do
586 {
587 return val.lessThan(lower) ? lower : val.greaterThan(upper) ? upper : val;
588 }
589
590 ///
591 @safe @nogc @betterC unittest
592 {
593 assert(clamp(2, 1, 3) == 2);
594 assert(clamp(0, 1, 3) == 1);
595 assert(clamp(4, 1, 3) == 3);
596
597 assert(clamp(1, 1, 1) == 1);
598
599 assert(clamp(5, -1, 2u) == 2);
600
601 auto x = clamp(42, uint.max, uint.max);
602 static assert(is(typeof(x) == int));
603 assert(x == -1);
604 }
605
606 @safe unittest
607 {
608 int a = 1;
609 short b = 6;
610 double c = 2;
611 static assert(is(typeof(clamp(c,a,b)) == double));
612 assert(clamp(c, a, b) == c);
613 assert(clamp(a-c, a, b) == a);
614 assert(clamp(b+c, a, b) == b);
615 // mixed sign
616 a = -5;
617 uint f = 5;
618 static assert(is(typeof(clamp(f, a, b)) == uint));
619 assert(clamp(f, a, b) == f);
620 // similar type deduction for (u)long
621 static assert(is(typeof(clamp(-1L, -2L, 2UL)) == long));
622
623 // user-defined types
624 import std.datetime : Date;
625 assert(clamp(Date(1982, 1, 4), Date(1012, 12, 21), Date(2012, 12, 21)) == Date(1982, 1, 4));
626 assert(clamp(Date(1982, 1, 4), Date.min, Date.max) == Date(1982, 1, 4));
627 // UFCS style
628 assert(Date(1982, 1, 4).clamp(Date.min, Date.max) == Date(1982, 1, 4));
629
630 // Stability
631 struct A {
632 int x, y;
opCmpA633 int opCmp(ref const A rhs) const { return (x > rhs.x) - (x < rhs.x); }
634 }
635 A x, lo, hi;
636 x.y = 42;
637 assert(x.clamp(lo, hi).y == 42);
638 }
639
640 // cmp
641 /**********************************
642 Performs a lexicographical comparison on two
643 $(REF_ALTTEXT input ranges, isInputRange, std,range,primitives).
644 Iterating `r1` and `r2` in lockstep, `cmp` compares each element
645 `e1` of `r1` with the corresponding element `e2` in `r2`. If one
646 of the ranges has been finished, `cmp` returns a negative value
647 if `r1` has fewer elements than `r2`, a positive value if `r1`
648 has more elements than `r2`, and `0` if the ranges have the same
649 number of elements.
650
651 If the ranges are strings, `cmp` performs UTF decoding
652 appropriately and compares the ranges one code point at a time.
653
654 A custom predicate may be specified, in which case `cmp` performs
655 a three-way lexicographical comparison using `pred`. Otherwise
656 the elements are compared using `opCmp`.
657
658 Params:
659 pred = Predicate used for comparison. Without a predicate
660 specified the ordering implied by `opCmp` is used.
661 r1 = The first range.
662 r2 = The second range.
663
664 Returns:
665 `0` if the ranges compare equal. A negative value if `r1` is a prefix of `r2` or
666 the first differing element of `r1` is less than the corresponding element of `r2`
667 according to `pred`. A positive value if `r2` is a prefix of `r1` or the first
668 differing element of `r2` is less than the corresponding element of `r1`
669 according to `pred`.
670
671 Note:
672 An earlier version of the documentation incorrectly stated that `-1` is the
673 only negative value returned and `1` is the only positive value returned.
674 Whether that is true depends on the types being compared.
675 */
676 auto cmp(R1, R2)(R1 r1, R2 r2)
677 if (isInputRange!R1 && isInputRange!R2)
678 {
679 alias E1 = ElementEncodingType!R1;
680 alias E2 = ElementEncodingType!R2;
681
682 static if (isDynamicArray!R1 && isDynamicArray!R2
683 && __traits(isUnsigned, E1) && __traits(isUnsigned, E2)
684 && E1.sizeof == 1 && E2.sizeof == 1
685 // Both or neither must auto-decode.
686 && (is(immutable E1 == immutable char) == is(immutable E2 == immutable char)))
687 {
688 // dstrcmp algorithm is correct for both ubyte[] and for char[].
689 import core.internal.string : dstrcmp;
690 return dstrcmp(cast(const char[]) r1, cast(const char[]) r2);
691 }
692 else static if (!(isSomeString!R1 && isSomeString!R2))
693 {
694 for (;; r1.popFront(), r2.popFront())
695 {
696 static if (is(typeof(r1.front.opCmp(r2.front)) R))
697 alias Result = R;
698 else
699 alias Result = int;
700 if (r2.empty) return Result(!r1.empty);
701 if (r1.empty) return Result(-1);
702 static if (is(typeof(r1.front.opCmp(r2.front))))
703 {
704 auto c = r1.front.opCmp(r2.front);
705 if (c != 0) return c;
706 }
707 else
708 {
709 auto a = r1.front, b = r2.front;
710 if (auto result = (b < a) - (a < b)) return result;
711 }
712 }
713 }
714 else
715 {
716 static if (typeof(r1[0]).sizeof == typeof(r2[0]).sizeof)
717 {
718 return () @trusted
719 {
720 auto p1 = r1.ptr, p2 = r2.ptr,
721 pEnd = p1 + min(r1.length, r2.length);
722 for (; p1 != pEnd; ++p1, ++p2)
723 {
724 if (*p1 != *p2) return cast(int) *p1 - cast(int) *p2;
725 }
726 static if (typeof(r1[0]).sizeof >= 2 && size_t.sizeof <= uint.sizeof)
727 return cast(int) r1.length - cast(int) r2.length;
728 else
729 return int(r1.length > r2.length) - int(r1.length < r2.length);
730 }();
731 }
732 else
733 {
734 import std.utf : decode;
735
736 for (size_t i1, i2;;)
737 {
738 if (i1 == r1.length) return -int(i2 < r2.length);
739 if (i2 == r2.length) return int(1);
740 immutable c1 = decode(r1, i1),
741 c2 = decode(r2, i2);
742 if (c1 != c2) return cast(int) c1 - cast(int) c2;
743 }
744 }
745 }
746 }
747
748 /// ditto
749 int cmp(alias pred, R1, R2)(R1 r1, R2 r2)
750 if (isInputRange!R1 && isInputRange!R2)
751 {
752 static if (!(isSomeString!R1 && isSomeString!R2))
753 {
754 for (;; r1.popFront(), r2.popFront())
755 {
756 if (r2.empty) return !r1.empty;
757 if (r1.empty) return -1;
758 auto a = r1.front, b = r2.front;
759 if (binaryFun!pred(a, b)) return -1;
760 if (binaryFun!pred(b, a)) return 1;
761 }
762 }
763 else
764 {
765 import std.utf : decode;
766
767 for (size_t i1, i2;;)
768 {
769 if (i1 == r1.length) return -int(i2 < r2.length);
770 if (i2 == r2.length) return 1;
771 immutable c1 = decode(r1, i1),
772 c2 = decode(r2, i2);
773 if (c1 != c2)
774 {
775 if (binaryFun!pred(c2, c1)) return 1;
776 if (binaryFun!pred(c1, c2)) return -1;
777 }
778 }
779 }
780 }
781
782 ///
783 pure @safe unittest
784 {
785 int result;
786
787 result = cmp("abc", "abc");
788 assert(result == 0);
789 result = cmp("", "");
790 assert(result == 0);
791 result = cmp("abc", "abcd");
792 assert(result < 0);
793 result = cmp("abcd", "abc");
794 assert(result > 0);
795 result = cmp("abc"d, "abd");
796 assert(result < 0);
797 result = cmp("bbc", "abc"w);
798 assert(result > 0);
799 result = cmp("aaa", "aaaa"d);
800 assert(result < 0);
801 result = cmp("aaaa", "aaa"d);
802 assert(result > 0);
803 result = cmp("aaa", "aaa"d);
804 assert(result == 0);
805 result = cmp("aaa"d, "aaa"d);
806 assert(result == 0);
807 result = cmp(cast(int[])[], cast(int[])[]);
808 assert(result == 0);
809 result = cmp([1, 2, 3], [1, 2, 3]);
810 assert(result == 0);
811 result = cmp([1, 3, 2], [1, 2, 3]);
812 assert(result > 0);
813 result = cmp([1, 2, 3], [1L, 2, 3, 4]);
814 assert(result < 0);
815 result = cmp([1L, 2, 3], [1, 2]);
816 assert(result > 0);
817 }
818
819 /// Example predicate that compares individual elements in reverse lexical order
820 pure @safe unittest
821 {
822 int result;
823
824 result = cmp!"a > b"("abc", "abc");
825 assert(result == 0);
826 result = cmp!"a > b"("", "");
827 assert(result == 0);
828 result = cmp!"a > b"("abc", "abcd");
829 assert(result < 0);
830 result = cmp!"a > b"("abcd", "abc");
831 assert(result > 0);
832 result = cmp!"a > b"("abc"d, "abd");
833 assert(result > 0);
834 result = cmp!"a > b"("bbc", "abc"w);
835 assert(result < 0);
836 result = cmp!"a > b"("aaa", "aaaa"d);
837 assert(result < 0);
838 result = cmp!"a > b"("aaaa", "aaa"d);
839 assert(result > 0);
840 result = cmp!"a > b"("aaa", "aaa"d);
841 assert(result == 0);
842 result = cmp("aaa"d, "aaa"d);
843 assert(result == 0);
844 result = cmp!"a > b"(cast(int[])[], cast(int[])[]);
845 assert(result == 0);
846 result = cmp!"a > b"([1, 2, 3], [1, 2, 3]);
847 assert(result == 0);
848 result = cmp!"a > b"([1, 3, 2], [1, 2, 3]);
849 assert(result < 0);
850 result = cmp!"a > b"([1, 2, 3], [1L, 2, 3, 4]);
851 assert(result < 0);
852 result = cmp!"a > b"([1L, 2, 3], [1, 2]);
853 assert(result > 0);
854 }
855
856 // cmp for string with custom predicate fails if distinct chars can compare equal
857 // https://issues.dlang.org/show_bug.cgi?id=18286
858 @nogc nothrow pure @safe unittest
859 {
ltCi(dchar a,dchar b)860 static bool ltCi(dchar a, dchar b)// less than, case insensitive
861 {
862 import std.ascii : toUpper;
863 return toUpper(a) < toUpper(b);
864 }
865 static assert(cmp!ltCi("apple2", "APPLE1") > 0);
866 static assert(cmp!ltCi("apple1", "APPLE2") < 0);
867 static assert(cmp!ltCi("apple", "APPLE1") < 0);
868 static assert(cmp!ltCi("APPLE", "apple1") < 0);
869 static assert(cmp!ltCi("apple", "APPLE") == 0);
870 }
871
872 // for non-string ranges check that opCmp is evaluated only once per pair.
873 // https://issues.dlang.org/show_bug.cgi?id=18280
874 @nogc nothrow @safe unittest
875 {
876 static int ctr = 0;
877 struct S
878 {
opCmpS879 int opCmp(ref const S rhs) const
880 {
881 ++ctr;
882 return 0;
883 }
opEqualsS884 bool opEquals(T)(T o) const { return false; }
toHashS885 size_t toHash() const { return 0; }
886 }
887 immutable S[4] a;
888 immutable S[4] b;
889 immutable result = cmp(a[], b[]);
890 assert(result == 0, "neither should compare greater than the other!");
891 assert(ctr == a.length, "opCmp should be called exactly once per pair of items!");
892 }
893
894 nothrow pure @safe @nogc unittest
895 {
896 import std.array : staticArray;
897 // Test cmp when opCmp returns float.
898 struct F
899 {
900 float value;
opCmpF901 float opCmp(const ref F rhs) const
902 {
903 return value - rhs.value;
904 }
opEqualsF905 bool opEquals(T)(T o) const { return false; }
toHashF906 size_t toHash() const { return 0; }
907 }
908 auto result = cmp([F(1), F(2), F(3)].staticArray[], [F(1), F(2), F(3)].staticArray[]);
909 assert(result == 0);
910 assert(is(typeof(result) == float));
911 result = cmp([F(1), F(3), F(2)].staticArray[], [F(1), F(2), F(3)].staticArray[]);
912 assert(result > 0);
913 result = cmp([F(1), F(2), F(3)].staticArray[], [F(1), F(2), F(3), F(4)].staticArray[]);
914 assert(result < 0);
915 result = cmp([F(1), F(2), F(3)].staticArray[], [F(1), F(2)].staticArray[]);
916 assert(result > 0);
917 }
918
919 nothrow pure @safe unittest
920 {
921 // Parallelism (was broken by inferred return type "immutable int")
922 import std.parallelism : task;
923 auto t = task!cmp("foo", "bar");
924 }
925
926 // equal
927 /**
928 Compares two or more ranges for equality, as defined by predicate `pred`
929 (which is `==` by default).
930 */
931 template equal(alias pred = "a == b")
932 {
933 /++
934 Compares two or more ranges for equality. The ranges may have
935 different element types, as long as all are comparable by means of
936 the `pred`.
937 Performs $(BIGOH min(rs[0].length, rs[1].length, ...)) evaluations of `pred`. However, if
938 `equal` is invoked with the default predicate, the implementation may take the liberty
939 to use faster implementations that have the theoretical worst-case
940 $(BIGOH max(rs[0].length, rs[1].length, ...)).
941
942 At least one of the ranges must be finite. If one range involved is infinite, the result is
943 (statically known to be) `false`.
944
945 If the ranges have different kinds of UTF code unit (`char`, `wchar`, or
946 `dchar`), then they are compared using UTF decoding to avoid
947 accidentally integer-promoting units.
948
949 Params:
950 rs = The ranges to be compared.
951
952 Returns:
953 `true` if and only if all ranges compare _equal element
954 for element, according to binary predicate `pred`.
955 +/
956 bool equal(Ranges...)(Ranges rs)
957 if (rs.length > 1
958 && allSatisfy!(isInputRange, Ranges)
959 && !allSatisfy!(isInfinite, Ranges)
960 && is(typeof(binaryFun!pred(rs[0].front, rs[1].front)))
961 && (rs.length == 2 || is(typeof(equal!pred(rs[1 .. $])) == bool))
962 )
963 {
964 alias ElementEncodingTypes = staticMap!(ElementEncodingType, Ranges);
965 enum differentSize(T) = T.sizeof != ElementEncodingTypes[0].sizeof;
966 enum useCodePoint = allSatisfy!(isSomeChar, ElementEncodingTypes) &&
967 anySatisfy!(differentSize, ElementEncodingTypes);
968 enum bool comparableWithEq(alias r) = is(typeof(rs[0] == r));
969
970 static if (anySatisfy!(isInfinite, Ranges))
971 {
972 return false;
973 }
974 else static if (useCodePoint)
975 {
976 import std.utf : byDchar;
allByDchar(size_t done,Ranges...)977 static bool allByDchar(size_t done, Ranges...)(auto ref Ranges rs)
978 {
979 static if (done == rs.length)
980 return equalLoop(rs);
981 else
982 return allByDchar!(done + 1)(rs[0 .. done], rs[done].byDchar, rs[done + 1 .. $]);
983 }
984 return allByDchar!0(rs);
985 }
986 else static if (is(typeof(pred) == string) && pred == "a == b" &&
987 allSatisfy!(isArray, Ranges) && allSatisfy!(comparableWithEq, rs))
988 {
989 static foreach (r; rs[1 .. $])
990 if (rs[0] != r)
991 return false;
992 return true;
993 }
994 // if one of the arguments is a string and the other isn't, then auto-decoding
995 // can be avoided if they have the same ElementEncodingType
996 // TODO: generalize this
997 else static if (rs.length == 2 && is(typeof(pred) == string) && pred == "a == b" &&
998 isAutodecodableString!(Ranges[0]) != isAutodecodableString!(Ranges[1]) &&
999 is(immutable ElementEncodingType!(Ranges[0]) == immutable ElementEncodingType!(Ranges[1])))
1000 {
1001 import std.utf : byCodeUnit;
1002 static if (isAutodecodableString!(Ranges[0]))
1003 return equal(rs[0].byCodeUnit, rs[1]);
1004 else
1005 return equal(rs[1].byCodeUnit, rs[0]);
1006 }
1007 else
1008 {
foreach(i,R;Ranges)1009 static foreach (i, R; Ranges)
1010 {
1011 static if (hasLength!R)
1012 {
1013 static if (!is(typeof(firstLength)))
1014 {
1015 // Found the first range that has length
1016 auto firstLength = rs[i].length;
1017 }
1018 else
1019 {
1020 // Compare the length of the current range against the first with length
1021 if (firstLength != rs[i].length)
1022 return false;
1023 }
1024 }
1025 }
1026 return equalLoop(rs);
1027 }
1028 }
1029
equalLoop(Rs...)1030 private bool equalLoop(Rs...)(ref Rs rs)
1031 {
1032 for (; !rs[0].empty; rs[0].popFront)
1033 static foreach (r; rs[1 .. $])
1034 if (r.empty || !binaryFun!pred(rs[0].front, r.front))
1035 return false;
1036 else
1037 r.popFront;
1038 static foreach (r; rs[1 .. $])
1039 if (!r.empty)
1040 return false;
1041 return true;
1042 }
1043 }
1044
1045 ///
1046 @safe @nogc unittest
1047 {
1048 import std.algorithm.comparison : equal;
1049 import std.math.operations : isClose;
1050
1051 int[4] a = [ 1, 2, 4, 3 ];
1052 assert(!equal(a[], a[1..$]));
1053 assert(equal(a[], a[]));
1054 assert(equal!((a, b) => a == b)(a[], a[]));
1055
1056 // different types
1057 double[4] b = [ 1.0, 2, 4, 3];
1058 assert(!equal(a[], b[1..$]));
1059 assert(equal(a[], b[]));
1060
1061 // predicated: ensure that two vectors are approximately equal
1062 double[4] c = [ 1.0000000005, 2, 4, 3];
1063 assert(equal!isClose(b[], c[]));
1064 }
1065
1066 @safe @nogc unittest
1067 {
1068 import std.algorithm.comparison : equal;
1069 import std.math.operations : isClose;
1070
1071 auto s1 = "abc", s2 = "abc"w;
1072 assert(equal(s1, s2, s2));
1073 assert(equal(s1, s2, s2, s1));
1074 assert(!equal(s1, s2, s2[1 .. $]));
1075
1076 int[4] a = [ 1, 2, 4, 3 ];
1077 assert(!equal(a[], a[1..$], a[]));
1078 assert(equal(a[], a[], a[]));
1079 assert(equal!((a, b) => a == b)(a[], a[], a[]));
1080
1081 // different types
1082 double[4] b = [ 1.0, 2, 4, 3];
1083 assert(!equal(a[], b[1..$], b[]));
1084 assert(equal(a[], b[], a[], b[]));
1085
1086 // predicated: ensure that two vectors are approximately equal
1087 double[4] c = [ 1.0000000005, 2, 4, 3];
1088 assert(equal!isClose(b[], c[], b[]));
1089 }
1090
1091 /++
1092 Tip: `equal` can itself be used as a predicate to other functions.
1093 This can be very useful when the element type of a range is itself a
1094 range. In particular, `equal` can be its own predicate, allowing
1095 range of range (of range...) comparisons.
1096 +/
1097 @safe unittest
1098 {
1099 import std.algorithm.comparison : equal;
1100 import std.range : iota, chunks;
1101 assert(equal!(equal!equal)(
1102 [[[0, 1], [2, 3]], [[4, 5], [6, 7]]],
1103 iota(0, 8).chunks(2).chunks(2)
1104 ));
1105 }
1106
1107 @safe unittest
1108 {
1109 import std.algorithm.iteration : map;
1110 import std.internal.test.dummyrange : ReferenceForwardRange,
1111 ReferenceInputRange, ReferenceInfiniteForwardRange;
1112 import std.math.operations : isClose;
1113
1114 // various strings
1115 assert(equal("æøå", "æøå")); //UTF8 vs UTF8
1116 assert(!equal("???", "æøå")); //UTF8 vs UTF8
1117 assert(equal("æøå"w, "æøå"d)); //UTF16 vs UTF32
1118 assert(!equal("???"w, "æøå"d));//UTF16 vs UTF32
1119 assert(equal("æøå"d, "æøå"d)); //UTF32 vs UTF32
1120 assert(!equal("???"d, "æøå"d));//UTF32 vs UTF32
1121 assert(!equal("hello", "world"));
1122
1123 // same strings, but "explicit non default" comparison (to test the non optimized array comparison)
1124 assert( equal!("a == b")("æøå", "æøå")); //UTF8 vs UTF8
1125 assert(!equal!("a == b")("???", "æøå")); //UTF8 vs UTF8
1126 assert( equal!("a == b")("æøå"w, "æøå"d)); //UTF16 vs UTF32
1127 assert(!equal!("a == b")("???"w, "æøå"d));//UTF16 vs UTF32
1128 assert( equal!("a == b")("æøå"d, "æøå"d)); //UTF32 vs UTF32
1129 assert(!equal!("a == b")("???"d, "æøå"d));//UTF32 vs UTF32
1130 assert(!equal!("a == b")("hello", "world"));
1131
1132 //Array of string
1133 assert(equal(["hello", "world"], ["hello", "world"]));
1134 assert(!equal(["hello", "world"], ["hello"]));
1135 assert(!equal(["hello", "world"], ["hello", "Bob!"]));
1136
1137 //Should not compile, because "string == dstring" is illegal
1138 static assert(!is(typeof(equal(["hello", "world"], ["hello"d, "world"d]))));
1139 //However, arrays of non-matching string can be compared using equal!equal. Neat-o!
1140 equal!equal(["hello", "world"], ["hello"d, "world"d]);
1141
1142 //Tests, with more fancy map ranges
1143 int[] a = [ 1, 2, 4, 3 ];
1144 assert(equal([2, 4, 8, 6], map!"a*2"(a)));
1145 double[] b = [ 1.0, 2, 4, 3];
1146 double[] c = [ 1.0000000005, 2, 4, 3];
1147 assert(equal!isClose(map!"a*2"(b), map!"a*2"(c)));
1148 assert(!equal([2, 4, 1, 3], map!"a*2"(a)));
1149 assert(!equal([2, 4, 1], map!"a*2"(a)));
1150 assert(!equal!isClose(map!"a*3"(b), map!"a*2"(c)));
1151
1152 //Tests with some fancy reference ranges.
1153 ReferenceInputRange!int cir = new ReferenceInputRange!int([1, 2, 4, 3]);
1154 ReferenceForwardRange!int cfr = new ReferenceForwardRange!int([1, 2, 4, 3]);
1155 assert(equal(cir, a));
1156 cir = new ReferenceInputRange!int([1, 2, 4, 3]);
1157 assert(equal(cir, cfr.save));
1158 assert(equal(cfr.save, cfr.save));
1159 cir = new ReferenceInputRange!int([1, 2, 8, 1]);
1160 assert(!equal(cir, cfr));
1161
1162 //Test with an infinite range
1163 auto ifr = new ReferenceInfiniteForwardRange!int;
1164 assert(!equal(a, ifr));
1165 assert(!equal(ifr, a));
1166 //Test InputRange without length
1167 assert(!equal(ifr, cir));
1168 assert(!equal(cir, ifr));
1169 }
1170
1171 @safe @nogc pure unittest
1172 {
1173 import std.utf : byChar, byDchar, byWchar;
1174
1175 assert(equal("æøå".byChar, "æøå"));
1176 assert(equal("æøå".byChar, "æøå"w));
1177 assert(equal("æøå".byChar, "æøå"d));
1178 assert(equal("æøå", "æøå".byChar));
1179 assert(equal("æøå"w, "æøå".byChar));
1180 assert(equal("æøå"d, "æøå".byChar));
1181
1182 assert(equal("æøå".byWchar, "æøå"));
1183 assert(equal("æøå".byWchar, "æøå"w));
1184 assert(equal("æøå".byWchar, "æøå"d));
1185 assert(equal("æøå", "æøå".byWchar));
1186 assert(equal("æøå"w, "æøå".byWchar));
1187 assert(equal("æøå"d, "æøå".byWchar));
1188
1189 assert(equal("æøå".byDchar, "æøå"));
1190 assert(equal("æøå".byDchar, "æøå"w));
1191 assert(equal("æøå".byDchar, "æøå"d));
1192 assert(equal("æøå", "æøå".byDchar));
1193 assert(equal("æøå"w, "æøå".byDchar));
1194 assert(equal("æøå"d, "æøå".byDchar));
1195 }
1196
1197 @safe @nogc pure unittest
1198 {
R(bool _empty)1199 struct R(bool _empty) {
1200 enum empty = _empty;
1201 @property char front(){assert(0);}
1202 void popFront(){assert(0);}
1203 }
1204 alias I = R!false;
1205 static assert(!__traits(compiles, I().equal(I())));
1206 // strings have fixed length so don't need to compare elements
1207 assert(!I().equal("foo"));
1208 assert(!"bar".equal(I()));
1209
1210 alias E = R!true;
1211 assert(E().equal(E()));
1212 assert(E().equal(""));
1213 assert("".equal(E()));
1214 assert(!E().equal("foo"));
1215 assert(!"bar".equal(E()));
1216 }
1217
1218 // levenshteinDistance
1219 /**
1220 Encodes $(HTTP realityinteractive.com/rgrzywinski/archives/000249.html,
1221 edit operations) necessary to transform one sequence into
1222 another. Given sequences `s` (source) and `t` (target), a
1223 sequence of `EditOp` encodes the steps that need to be taken to
1224 convert `s` into `t`. For example, if `s = "cat"` and $(D
1225 "cars"), the minimal sequence that transforms `s` into `t` is:
1226 skip two characters, replace 't' with 'r', and insert an 's'. Working
1227 with edit operations is useful in applications such as spell-checkers
1228 (to find the closest word to a given misspelled word), approximate
1229 searches, diff-style programs that compute the difference between
1230 files, efficient encoding of patches, DNA sequence analysis, and
1231 plagiarism detection.
1232 */
1233
1234 enum EditOp : char
1235 {
1236 /** Current items are equal; no editing is necessary. */
1237 none = 'n',
1238 /** Substitute current item in target with current item in source. */
1239 substitute = 's',
1240 /** Insert current item from the source into the target. */
1241 insert = 'i',
1242 /** Remove current item from the target. */
1243 remove = 'r'
1244 }
1245
1246 ///
1247 @safe unittest
1248 {
with(EditOp)1249 with(EditOp)
1250 {
1251 assert(levenshteinDistanceAndPath("foo", "foobar")[1] == [none, none, none, insert, insert, insert]);
1252 assert(levenshteinDistanceAndPath("banana", "fazan")[1] == [substitute, none, substitute, none, none, remove]);
1253 }
1254 }
1255
1256 private struct Levenshtein(Range, alias equals, CostType = size_t)
1257 {
pathLevenshtein1258 EditOp[] path()
1259 {
1260 import std.algorithm.mutation : reverse;
1261
1262 EditOp[] result;
1263 size_t i = rows - 1, j = cols - 1;
1264 // restore the path
1265 while (i || j)
1266 {
1267 auto cIns = j == 0 ? CostType.max : matrix(i,j - 1);
1268 auto cDel = i == 0 ? CostType.max : matrix(i - 1,j);
1269 auto cSub = i == 0 || j == 0
1270 ? CostType.max
1271 : matrix(i - 1,j - 1);
1272 switch (min_index(cSub, cIns, cDel))
1273 {
1274 case 0:
1275 result ~= matrix(i - 1,j - 1) == matrix(i,j)
1276 ? EditOp.none
1277 : EditOp.substitute;
1278 --i;
1279 --j;
1280 break;
1281 case 1:
1282 result ~= EditOp.insert;
1283 --j;
1284 break;
1285 default:
1286 result ~= EditOp.remove;
1287 --i;
1288 break;
1289 }
1290 }
1291 reverse(result);
1292 return result;
1293 }
1294
~thisLevenshtein1295 ~this() {
1296 FreeMatrix();
1297 }
1298
1299 private:
1300 CostType _deletionIncrement = 1,
1301 _insertionIncrement = 1,
1302 _substitutionIncrement = 1;
1303 CostType[] _matrix;
1304 size_t rows, cols;
1305
1306 // Treat _matrix as a rectangular array
matrixLevenshtein1307 ref CostType matrix(size_t row, size_t col) { return _matrix[row * cols + col]; }
1308
AllocMatrixLevenshtein1309 void AllocMatrix(size_t r, size_t c) @trusted {
1310 import core.checkedint : mulu;
1311 bool overflow;
1312 const rc = mulu(r, c, overflow);
1313 assert(!overflow, "Overflow during multiplication to determine number "
1314 ~ " of matrix elements");
1315 rows = r;
1316 cols = c;
1317 if (_matrix.length < rc)
1318 {
1319 import core.exception : onOutOfMemoryError;
1320 import core.stdc.stdlib : realloc;
1321 const nbytes = mulu(rc, _matrix[0].sizeof, overflow);
1322 assert(!overflow, "Overflow during multiplication to determine "
1323 ~ " number of bytes of matrix");
1324 auto m = cast(CostType *) realloc(_matrix.ptr, nbytes);
1325 if (!m)
1326 onOutOfMemoryError();
1327 _matrix = m[0 .. r * c];
1328 InitMatrix();
1329 }
1330 }
1331
FreeMatrixLevenshtein1332 void FreeMatrix() @trusted {
1333 import core.stdc.stdlib : free;
1334
1335 free(_matrix.ptr);
1336 _matrix = null;
1337 }
1338
InitMatrixLevenshtein1339 void InitMatrix() {
1340 foreach (r; 0 .. rows)
1341 matrix(r,0) = r * _deletionIncrement;
1342 foreach (c; 0 .. cols)
1343 matrix(0,c) = c * _insertionIncrement;
1344 }
1345
min_indexLevenshtein1346 static uint min_index(CostType i0, CostType i1, CostType i2)
1347 {
1348 if (i0 <= i1)
1349 {
1350 return i0 <= i2 ? 0 : 2;
1351 }
1352 else
1353 {
1354 return i1 <= i2 ? 1 : 2;
1355 }
1356 }
1357
distanceWithPathLevenshtein1358 CostType distanceWithPath(Range s, Range t)
1359 {
1360 auto slen = walkLength(s.save), tlen = walkLength(t.save);
1361 AllocMatrix(slen + 1, tlen + 1);
1362 foreach (i; 1 .. rows)
1363 {
1364 auto sfront = s.front;
1365 auto tt = t.save;
1366 foreach (j; 1 .. cols)
1367 {
1368 auto cSub = matrix(i - 1,j - 1)
1369 + (equals(sfront, tt.front) ? 0 : _substitutionIncrement);
1370 tt.popFront();
1371 auto cIns = matrix(i,j - 1) + _insertionIncrement;
1372 auto cDel = matrix(i - 1,j) + _deletionIncrement;
1373 switch (min_index(cSub, cIns, cDel))
1374 {
1375 case 0:
1376 matrix(i,j) = cSub;
1377 break;
1378 case 1:
1379 matrix(i,j) = cIns;
1380 break;
1381 default:
1382 matrix(i,j) = cDel;
1383 break;
1384 }
1385 }
1386 s.popFront();
1387 }
1388 return matrix(slen,tlen);
1389 }
1390
distanceLowMemLevenshtein1391 CostType distanceLowMem(Range s, Range t, CostType slen, CostType tlen)
1392 {
1393 CostType lastdiag, olddiag;
1394 AllocMatrix(slen + 1, 1);
1395 foreach (y; 1 .. slen + 1)
1396 {
1397 _matrix[y] = y;
1398 }
1399 foreach (x; 1 .. tlen + 1)
1400 {
1401 auto tfront = t.front;
1402 auto ss = s.save;
1403 _matrix[0] = x;
1404 lastdiag = x - 1;
1405 foreach (y; 1 .. rows)
1406 {
1407 olddiag = _matrix[y];
1408 auto cSub = lastdiag + (equals(ss.front, tfront) ? 0 : _substitutionIncrement);
1409 ss.popFront();
1410 auto cIns = _matrix[y - 1] + _insertionIncrement;
1411 auto cDel = _matrix[y] + _deletionIncrement;
1412 switch (min_index(cSub, cIns, cDel))
1413 {
1414 case 0:
1415 _matrix[y] = cSub;
1416 break;
1417 case 1:
1418 _matrix[y] = cIns;
1419 break;
1420 default:
1421 _matrix[y] = cDel;
1422 break;
1423 }
1424 lastdiag = olddiag;
1425 }
1426 t.popFront();
1427 }
1428 return _matrix[slen];
1429 }
1430 }
1431
1432 /**
1433 Returns the $(HTTP wikipedia.org/wiki/Levenshtein_distance, Levenshtein
1434 distance) between `s` and `t`. The Levenshtein distance computes
1435 the minimal amount of edit operations necessary to transform `s`
1436 into `t`. Performs $(BIGOH s.length * t.length) evaluations of $(D
1437 equals) and occupies $(BIGOH min(s.length, t.length)) storage.
1438
1439 Params:
1440 equals = The binary predicate to compare the elements of the two ranges.
1441 s = The original range.
1442 t = The transformation target
1443
1444 Returns:
1445 The minimal number of edits to transform s into t.
1446
1447 Does not allocate GC memory.
1448 */
1449 size_t levenshteinDistance(alias equals = (a,b) => a == b, Range1, Range2)
1450 (Range1 s, Range2 t)
1451 if (isForwardRange!(Range1) && isForwardRange!(Range2))
1452 {
1453 alias eq = binaryFun!(equals);
1454
1455 for (;;)
1456 {
1457 if (s.empty) return t.walkLength;
1458 if (t.empty) return s.walkLength;
1459 if (eq(s.front, t.front))
1460 {
1461 s.popFront();
1462 t.popFront();
1463 continue;
1464 }
1465 static if (isBidirectionalRange!(Range1) && isBidirectionalRange!(Range2))
1466 {
1467 if (eq(s.back, t.back))
1468 {
1469 s.popBack();
1470 t.popBack();
1471 continue;
1472 }
1473 }
1474 break;
1475 }
1476
1477 auto slen = walkLength(s.save);
1478 auto tlen = walkLength(t.save);
1479
1480 if (slen == 1 && tlen == 1)
1481 {
1482 return eq(s.front, t.front) ? 0 : 1;
1483 }
1484
1485 if (slen < tlen)
1486 {
1487 Levenshtein!(Range1, eq, size_t) lev;
1488 return lev.distanceLowMem(s, t, slen, tlen);
1489 }
1490 else
1491 {
1492 Levenshtein!(Range2, eq, size_t) lev;
1493 return lev.distanceLowMem(t, s, tlen, slen);
1494 }
1495 }
1496
1497 ///
1498 @safe unittest
1499 {
1500 import std.algorithm.iteration : filter;
1501 import std.uni : toUpper;
1502
1503 assert(levenshteinDistance("cat", "rat") == 1);
1504 assert(levenshteinDistance("parks", "spark") == 2);
1505 assert(levenshteinDistance("abcde", "abcde") == 0);
1506 assert(levenshteinDistance("abcde", "abCde") == 1);
1507 assert(levenshteinDistance("kitten", "sitting") == 3);
1508 assert(levenshteinDistance!((a, b) => toUpper(a) == toUpper(b))
1509 ("parks", "SPARK") == 2);
1510 assert(levenshteinDistance("parks".filter!"true", "spark".filter!"true") == 2);
1511 assert(levenshteinDistance("ID", "I♥D") == 1);
1512 }
1513
1514 @safe @nogc nothrow unittest
1515 {
1516 assert(levenshteinDistance("cat"d, "rat"d) == 1);
1517 }
1518
1519 /// ditto
1520 size_t levenshteinDistance(alias equals = (a,b) => a == b, Range1, Range2)
1521 (auto ref Range1 s, auto ref Range2 t)
1522 if (isConvertibleToString!Range1 || isConvertibleToString!Range2)
1523 {
1524 import std.meta : staticMap;
1525 alias Types = staticMap!(convertToString, Range1, Range2);
1526 return levenshteinDistance!(equals, Types)(s, t);
1527 }
1528
1529 @safe unittest
1530 {
1531 static struct S { string s; alias s this; }
1532 assert(levenshteinDistance(S("cat"), S("rat")) == 1);
1533 assert(levenshteinDistance("cat", S("rat")) == 1);
1534 assert(levenshteinDistance(S("cat"), "rat") == 1);
1535 }
1536
1537 @safe @nogc nothrow unittest
1538 {
1539 static struct S { dstring s; alias s this; }
1540 assert(levenshteinDistance(S("cat"d), S("rat"d)) == 1);
1541 assert(levenshteinDistance("cat"d, S("rat"d)) == 1);
1542 assert(levenshteinDistance(S("cat"d), "rat"d) == 1);
1543 }
1544
1545 /**
1546 Returns the Levenshtein distance and the edit path between `s` and
1547 `t`.
1548
1549 Params:
1550 equals = The binary predicate to compare the elements of the two ranges.
1551 s = The original range.
1552 t = The transformation target
1553
1554 Returns:
1555 Tuple with the first element being the minimal amount of edits to transform s into t and
1556 the second element being the sequence of edits to effect this transformation.
1557
1558 Allocates GC memory for the returned EditOp[] array.
1559 */
1560 Tuple!(size_t, EditOp[])
1561 levenshteinDistanceAndPath(alias equals = (a,b) => a == b, Range1, Range2)
1562 (Range1 s, Range2 t)
1563 if (isForwardRange!(Range1) && isForwardRange!(Range2))
1564 {
1565 Levenshtein!(Range1, binaryFun!(equals)) lev;
1566 auto d = lev.distanceWithPath(s, t);
1567 return tuple(d, lev.path());
1568 }
1569
1570 ///
1571 @safe unittest
1572 {
1573 string a = "Saturday", b = "Sundays";
1574 auto p = levenshteinDistanceAndPath(a, b);
1575 assert(p[0] == 4);
1576 assert(equal(p[1], "nrrnsnnni"));
1577 }
1578
1579 @safe unittest
1580 {
1581 assert(levenshteinDistance("a", "a") == 0);
1582 assert(levenshteinDistance("a", "b") == 1);
1583 assert(levenshteinDistance("aa", "ab") == 1);
1584 assert(levenshteinDistance("aa", "abc") == 2);
1585 assert(levenshteinDistance("Saturday", "Sunday") == 3);
1586 assert(levenshteinDistance("kitten", "sitting") == 3);
1587 }
1588
1589 /// ditto
1590 Tuple!(size_t, EditOp[])
1591 levenshteinDistanceAndPath(alias equals = (a,b) => a == b, Range1, Range2)
1592 (auto ref Range1 s, auto ref Range2 t)
1593 if (isConvertibleToString!Range1 || isConvertibleToString!Range2)
1594 {
1595 import std.meta : staticMap;
1596 alias Types = staticMap!(convertToString, Range1, Range2);
1597 return levenshteinDistanceAndPath!(equals, Types)(s, t);
1598 }
1599
1600 @safe unittest
1601 {
1602 static struct S { string s; alias s this; }
1603 assert(levenshteinDistanceAndPath(S("cat"), S("rat"))[0] == 1);
1604 assert(levenshteinDistanceAndPath("cat", S("rat"))[0] == 1);
1605 assert(levenshteinDistanceAndPath(S("cat"), "rat")[0] == 1);
1606 }
1607
1608
1609 // max
1610 /**
1611 Iterates the passed arguments and returns the maximum value.
1612
1613 Params:
1614 args = The values to select the maximum from. At least two arguments must
1615 be passed, and they must be comparable with `<`.
1616
1617 Returns:
1618 The maximum of the passed-in values. The type of the returned value is
1619 the type among the passed arguments that is able to store the largest value.
1620 If at least one of the arguments is NaN, the result is an unspecified value.
1621 See $(REF maxElement, std,algorithm,searching) for examples on how to cope
1622 with NaNs.
1623
1624 See_Also:
1625 $(REF maxElement, std,algorithm,searching)
1626 */
1627 auto max(T...)(T args)
1628 if (T.length >= 2 && !is(CommonType!T == void))
1629 {
1630 // Get left-hand side of the comparison.
1631 static if (T.length == 2)
1632 alias a = args[0];
1633 else
1634 auto a = max(args[0 .. ($ + 1) / 2]);
1635 alias T0 = typeof(a);
1636
1637 // Get right-hand side.
1638 static if (T.length <= 3)
1639 alias b = args[$ - 1];
1640 else
1641 auto b = max(args[($ + 1) / 2 .. $]);
1642 alias T1 = typeof(b);
1643
1644 static assert(is(typeof(a < b)),
1645 "Invalid arguments: Cannot compare types " ~ T0.stringof ~
1646 " and " ~ T1.stringof ~ " for ordering.");
1647
1648 // Compute the returned type.
1649 static if (is(typeof(mostNegative!T0 < mostNegative!T1)))
1650 // Both are numeric (or character or Boolean), so we choose the one with the highest maximum.
1651 // (We use mostNegative for num/bool/char testing purposes even if it's not used otherwise.)
1652 alias Result = Select!(T1.max > T0.max, T1, T0);
1653 else
1654 // At least one is non-numeric, so just go with the common type.
1655 alias Result = CommonType!(T0, T1);
1656
1657 // Perform the computation.
1658 import std.functional : lessThan;
1659 immutable chooseB = lessThan!(T0, T1)(a, b);
1660 return cast(Result) (chooseB ? b : a);
1661 }
1662
1663 /// ditto
1664 T max(T, U)(T a, U b)
1665 if (is(T == U) && is(typeof(a < b)))
1666 {
1667 /* Handle the common case without all the template expansions
1668 * of the general case
1669 */
1670 return a < b ? b : a;
1671 }
1672
1673 ///
1674 @safe @betterC @nogc unittest
1675 {
1676 int a = 5;
1677 short b = 6;
1678 double c = 2;
1679 auto d = max(a, b);
1680 assert(is(typeof(d) == int));
1681 assert(d == 6);
1682 auto e = min(a, b, c);
1683 assert(is(typeof(e) == double));
1684 assert(e == 2);
1685 }
1686
1687 @safe unittest // not @nogc due to `Date`
1688 {
1689 int a = 5;
1690 short b = 6;
1691 double c = 2;
1692 auto d = max(a, b);
1693 static assert(is(typeof(d) == int));
1694 assert(d == 6);
1695 auto e = max(a, b, c);
1696 static assert(is(typeof(e) == double));
1697 assert(e == 6);
1698 // mixed sign
1699 a = -5;
1700 uint f = 5;
1701 static assert(is(typeof(max(a, f)) == uint));
1702 assert(max(a, f) == 5);
1703
1704 //Test user-defined types
1705 import std.datetime : Date;
1706 assert(max(Date(2012, 12, 21), Date(1982, 1, 4)) == Date(2012, 12, 21));
1707 assert(max(Date(1982, 1, 4), Date(2012, 12, 21)) == Date(2012, 12, 21));
1708 assert(max(Date(1982, 1, 4), Date.min) == Date(1982, 1, 4));
1709 assert(max(Date.min, Date(1982, 1, 4)) == Date(1982, 1, 4));
1710 assert(max(Date(1982, 1, 4), Date.max) == Date.max);
1711 assert(max(Date.max, Date(1982, 1, 4)) == Date.max);
1712 assert(max(Date.min, Date.max) == Date.max);
1713 assert(max(Date.max, Date.min) == Date.max);
1714 }
1715
1716 // min
1717 /**
1718 Iterates the passed arguments and returns the minimum value.
1719
1720 Params:
1721 args = The values to select the minimum from. At least two arguments must
1722 be passed, and they must be comparable with `<`.
1723
1724 Returns:
1725 The minimum of the passed-in values. The type of the returned value is
1726 the type among the passed arguments that is able to store the smallest value.
1727 If at least one of the arguments is NaN, the result is an unspecified value.
1728 See $(REF minElement, std,algorithm,searching) for examples on how to cope
1729 with NaNs.
1730
1731 See_Also:
1732 $(REF minElement, std,algorithm,searching)
1733 */
1734 auto min(T...)(T args)
1735 if (T.length >= 2 && !is(CommonType!T == void))
1736 {
1737 // Get the left-hand side of the comparison.
1738 static if (T.length <= 2)
1739 alias a = args[0];
1740 else
1741 auto a = min(args[0 .. ($ + 1) / 2]);
1742 alias T0 = typeof(a);
1743
1744 // Get the right-hand side.
1745 static if (T.length <= 3)
1746 alias b = args[$ - 1];
1747 else
1748 auto b = min(args[($ + 1) / 2 .. $]);
1749 alias T1 = typeof(b);
1750
1751 static assert(is(typeof(a < b)),
1752 "Invalid arguments: Cannot compare types " ~ T0.stringof ~
1753 " and " ~ T1.stringof ~ " for ordering.");
1754
1755 // Compute the returned type.
1756 static if (is(typeof(mostNegative!T0 < mostNegative!T1)))
1757 // Both are numeric (or character or Boolean), so we choose the one with the lowest minimum.
1758 // If they have the same minimum, choose the one with the smallest size.
1759 // If both mostNegative and sizeof are equal, go for stability: pick the type of the first one.
1760 alias Result = Select!(mostNegative!T1 < mostNegative!T0 ||
1761 mostNegative!T1 == mostNegative!T0 && T1.sizeof < T0.sizeof,
1762 T1, T0);
1763 else
1764 // At least one is non-numeric, so just go with the common type.
1765 alias Result = CommonType!(T0, T1);
1766
1767 // Engage!
1768 import std.functional : lessThan;
1769 immutable chooseB = lessThan!(T1, T0)(b, a);
1770 return cast(Result) (chooseB ? b : a);
1771 }
1772
1773 /// ditto
1774 T min(T, U)(T a, U b)
1775 if (is(T == U) && is(typeof(a < b)))
1776 {
1777 /* Handle the common case without all the template expansions
1778 * of the general case
1779 */
1780 return b < a ? b : a;
1781 }
1782
1783
1784 ///
1785 @safe @nogc @betterC unittest
1786 {
1787 int a = 5;
1788 short b = 6;
1789 double c = 2;
1790 auto d = min(a, b);
1791 static assert(is(typeof(d) == int));
1792 assert(d == 5);
1793 auto e = min(a, b, c);
1794 static assert(is(typeof(e) == double));
1795 assert(e == 2);
1796 ulong f = 0xffff_ffff_ffff;
1797 const uint g = min(f, 0xffff_0000);
1798 assert(g == 0xffff_0000);
1799 dchar h = 100;
1800 uint i = 101;
1801 static assert(is(typeof(min(h, i)) == dchar));
1802 static assert(is(typeof(min(i, h)) == uint));
1803 assert(min(h, i) == 100);
1804 }
1805
1806 /**
1807 With arguments of mixed signedness, the return type is the one that can
1808 store the lowest values.
1809 */
1810 @safe @nogc @betterC unittest
1811 {
1812 int a = -10;
1813 uint f = 10;
1814 static assert(is(typeof(min(a, f)) == int));
1815 assert(min(a, f) == -10);
1816 }
1817
1818 /// User-defined types that support comparison with < are supported.
1819 @safe unittest // not @nogc due to `Date`
1820 {
1821 import std.datetime;
1822 assert(min(Date(2012, 12, 21), Date(1982, 1, 4)) == Date(1982, 1, 4));
1823 assert(min(Date(1982, 1, 4), Date(2012, 12, 21)) == Date(1982, 1, 4));
1824 assert(min(Date(1982, 1, 4), Date.min) == Date.min);
1825 assert(min(Date.min, Date(1982, 1, 4)) == Date.min);
1826 assert(min(Date(1982, 1, 4), Date.max) == Date(1982, 1, 4));
1827 assert(min(Date.max, Date(1982, 1, 4)) == Date(1982, 1, 4));
1828 assert(min(Date.min, Date.max) == Date.min);
1829 assert(min(Date.max, Date.min) == Date.min);
1830 }
1831
1832 // min must be stable: when in doubt, return the first argument.
1833 @safe unittest
1834 {
1835 assert(min(1.0, double.nan) == 1.0);
1836 assert(min(double.nan, 1.0) is double.nan);
1837 static struct A {
1838 int x;
1839 string y;
opCmpA1840 int opCmp(const A a) const { return int(x > a.x) - int(x < a.x); }
1841 }
1842 assert(min(A(1, "first"), A(1, "second")) == A(1, "first"));
1843 }
1844
1845 // mismatch
1846 /**
1847 Sequentially compares elements in `rs` in lockstep, and
1848 stops at the first mismatch (according to `pred`, by default
1849 equality). Returns a tuple with the reduced ranges that start with the
1850 two mismatched values. Performs $(BIGOH min(r[0].length, r[1].length, ...))
1851 evaluations of `pred`.
1852 */
1853 Tuple!(Ranges)
1854 mismatch(alias pred = (a, b) => a == b, Ranges...)(Ranges rs)
1855 if (rs.length >= 2 && allSatisfy!(isInputRange, Ranges))
1856 {
1857 loop: for (; !rs[0].empty; rs[0].popFront)
1858 {
foreach(r;rs[1..$])1859 static foreach (r; rs[1 .. $])
1860 {
1861 if (r.empty || !binaryFun!pred(rs[0].front, r.front))
1862 break loop;
1863 r.popFront;
1864 }
1865 }
1866 return tuple(rs);
1867 }
1868
1869 ///
1870 @safe @nogc unittest
1871 {
1872 int[6] x = [ 1, 5, 2, 7, 4, 3 ];
1873 double[6] y = [ 1.0, 5, 2, 7.3, 4, 8 ];
1874 auto m = mismatch(x[], y[]);
1875 assert(m[0] == x[3 .. $]);
1876 assert(m[1] == y[3 .. $]);
1877
1878 auto m2 = mismatch(x[], y[], x[], y[]);
1879 assert(m2[0] == x[3 .. $]);
1880 assert(m2[1] == y[3 .. $]);
1881 assert(m2[2] == x[3 .. $]);
1882 assert(m2[3] == y[3 .. $]);
1883 }
1884
1885 @safe @nogc unittest
1886 {
1887 import std.range : only;
1888
1889 int[3] a = [ 1, 2, 3 ];
1890 int[4] b = [ 1, 2, 4, 5 ];
1891 auto mm = mismatch(a[], b[]);
1892 assert(equal(mm[0], only(3)));
1893 assert(equal(mm[1], only(4, 5)));
1894 }
1895
1896 /**
1897 Returns one of a collection of expressions based on the value of the switch
1898 expression.
1899
1900 `choices` needs to be composed of pairs of test expressions and return
1901 expressions. Each test-expression is compared with `switchExpression` using
1902 `pred`(`switchExpression` is the first argument) and if that yields true -
1903 the return expression is returned.
1904
1905 Both the test and the return expressions are lazily evaluated.
1906
1907 Params:
1908
1909 switchExpression = The first argument for the predicate.
1910
1911 choices = Pairs of test expressions and return expressions. The test
1912 expressions will be the second argument for the predicate, and the return
1913 expression will be returned if the predicate yields true with $(D
1914 switchExpression) and the test expression as arguments. May also have a
1915 default return expression, that needs to be the last expression without a test
1916 expression before it. A return expression may be of void type only if it
1917 always throws.
1918
1919 Returns: The return expression associated with the first test expression that
1920 made the predicate yield true, or the default return expression if no test
1921 expression matched.
1922
1923 Throws: If there is no default return expression and the predicate does not
1924 yield true with any test expression - `SwitchError` is thrown. $(D
1925 SwitchError) is also thrown if a void return expression was executed without
1926 throwing anything.
1927 */
1928 auto predSwitch(alias pred = "a == b", T, R ...)(T switchExpression, lazy R choices)
1929 {
1930 import core.exception : SwitchError;
1931 alias predicate = binaryFun!(pred);
1932
foreach(index,ChoiceType;R)1933 foreach (index, ChoiceType; R)
1934 {
1935 //The even places in `choices` are for the predicate.
1936 static if (index % 2 == 1)
1937 {
1938 if (predicate(switchExpression, choices[index - 1]()))
1939 {
1940 static if (is(typeof(choices[index]()) == void))
1941 {
1942 choices[index]();
1943 throw new SwitchError("Choices that return void should throw");
1944 }
1945 else
1946 {
1947 return choices[index]();
1948 }
1949 }
1950 }
1951 }
1952
1953 //In case nothing matched:
1954 static if (R.length % 2 == 1) //If there is a default return expression:
1955 {
1956 static if (is(typeof(choices[$ - 1]()) == void))
1957 {
1958 choices[$ - 1]();
1959 throw new SwitchError("Choices that return void should throw");
1960 }
1961 else
1962 {
1963 return choices[$ - 1]();
1964 }
1965 }
1966 else //If there is no default return expression:
1967 {
1968 throw new SwitchError("Input not matched by any pattern");
1969 }
1970 }
1971
1972 ///
1973 @safe unittest
1974 {
1975 string res = 2.predSwitch!"a < b"(
1976 1, "less than 1",
1977 5, "less than 5",
1978 10, "less than 10",
1979 "greater or equal to 10");
1980
1981 assert(res == "less than 5");
1982
1983 //The arguments are lazy, which allows us to use predSwitch to create
1984 //recursive functions:
factorial(int n)1985 int factorial(int n)
1986 {
1987 return n.predSwitch!"a <= b"(
1988 -1, {throw new Exception("Can not calculate n! for n < 0");}(),
1989 0, 1, // 0! = 1
1990 n * factorial(n - 1) // n! = n * (n - 1)! for n >= 0
1991 );
1992 }
1993 assert(factorial(3) == 6);
1994
1995 //Void return expressions are allowed if they always throw:
1996 import std.exception : assertThrown;
1997 assertThrown!Exception(factorial(-9));
1998 }
1999
2000 @system unittest
2001 {
2002 import core.exception : SwitchError;
2003 import std.exception : assertThrown;
2004
2005 //Nothing matches - with default return expression:
2006 assert(20.predSwitch!"a < b"(
2007 1, "less than 1",
2008 5, "less than 5",
2009 10, "less than 10",
2010 "greater or equal to 10") == "greater or equal to 10");
2011
2012 //Nothing matches - without default return expression:
2013 assertThrown!SwitchError(20.predSwitch!"a < b"(
2014 1, "less than 1",
2015 5, "less than 5",
2016 10, "less than 10",
2017 ));
2018
2019 //Using the default predicate:
2020 assert(2.predSwitch(
2021 1, "one",
2022 2, "two",
2023 3, "three",
2024 ) == "two");
2025
2026 //Void return expressions must always throw:
2027 assertThrown!SwitchError(1.predSwitch(
2028 0, "zero",
2029 1, {}(), //A void return expression that doesn't throw
2030 2, "two",
2031 ));
2032 }
2033
2034 /**
2035 Checks if two or more ranges have the same number of elements. This function is
2036 optimized to always take advantage of the `length` member of either range
2037 if it exists.
2038
2039 If all ranges have a `length` member or at least one is infinite,
2040 `_isSameLength`'s complexity is $(BIGOH 1). Otherwise, complexity is
2041 $(BIGOH n), where `n` is the smallest of the lengths of ranges with unknown
2042 length.
2043
2044 Infinite ranges are considered of the same length. An infinite range has never
2045 the same length as a finite range.
2046
2047 Params:
2048 rs = two or more $(REF_ALTTEXT input ranges, isInputRange, std,range,primitives)
2049
2050 Returns:
2051 `true` if both ranges have the same length, `false` otherwise.
2052 */
2053 bool isSameLength(Ranges...)(Ranges rs)
2054 if (allSatisfy!(isInputRange, Ranges))
2055 {
2056 static if (anySatisfy!(isInfinite, Ranges))
2057 {
2058 return allSatisfy!(isInfinite, Ranges);
2059 }
2060 else static if (anySatisfy!(hasLength, Ranges))
2061 {
2062 // Compute the O(1) length
2063 auto baselineLength = size_t.max;
foreach(i,R;Ranges)2064 static foreach (i, R; Ranges)
2065 {
2066 static if (hasLength!R)
2067 {
2068 if (baselineLength == size_t.max)
2069 baselineLength = rs[i].length;
2070 else if (rs[i].length != baselineLength)
2071 return false;
2072 }
2073 }
2074 // Iterate all ranges without known length
2075 foreach (_; 0 .. baselineLength)
foreach(i,R;Ranges)2076 static foreach (i, R; Ranges)
2077 {
2078 static if (!hasLength!R)
2079 {
2080 // All must be non-empty
2081 if (rs[i].empty)
2082 return false;
2083 rs[i].popFront;
2084 }
2085 }
foreach(i,R;Ranges)2086 static foreach (i, R; Ranges)
2087 {
2088 static if (!hasLength!R)
2089 {
2090 // All must be now empty
2091 if (!rs[i].empty)
2092 return false;
2093 }
2094 }
2095 return true;
2096 }
2097 else
2098 {
2099 // All have unknown length, iterate in lockstep
2100 for (;;)
foreach(i,r;rs)2101 static foreach (i, r; rs)
2102 {
2103 if (r.empty)
2104 {
2105 // One is empty, so all must be empty
2106 static if (i != 0)
2107 {
2108 return false;
2109 }
2110 else
2111 {
2112 static foreach (j, r1; rs[1 .. $])
2113 if (!r1.empty)
2114 return false;
2115 return true;
2116 }
2117 }
2118 r.popFront;
2119 }
2120 }
2121 }
2122
2123 ///
2124 @safe nothrow pure unittest
2125 {
2126 assert(isSameLength([1, 2, 3], [4, 5, 6]));
2127 assert(isSameLength([1, 2, 3], [4, 5, 6], [7, 8, 9]));
2128 assert(isSameLength([0.3, 90.4, 23.7, 119.2], [42.6, 23.6, 95.5, 6.3]));
2129 assert(isSameLength("abc", "xyz"));
2130 assert(isSameLength("abc", "xyz", [1, 2, 3]));
2131
2132 int[] a;
2133 int[] b;
2134 assert(isSameLength(a, b));
2135 assert(isSameLength(a, b, a, a, b, b, b));
2136
2137 assert(!isSameLength([1, 2, 3], [4, 5]));
2138 assert(!isSameLength([1, 2, 3], [4, 5, 6], [7, 8]));
2139 assert(!isSameLength([0.3, 90.4, 23.7], [42.6, 23.6, 95.5, 6.3]));
2140 assert(!isSameLength("abcd", "xyz"));
2141 assert(!isSameLength("abcd", "xyz", "123"));
2142 assert(!isSameLength("abcd", "xyz", "1234"));
2143 }
2144
2145 // Test CTFE
2146 @safe @nogc pure @betterC unittest
2147 {
2148 static assert(isSameLength([1, 2, 3], [4, 5, 6]));
2149 static assert(isSameLength([1, 2, 3], [4, 5, 6], [7, 8, 9]));
2150 static assert(!isSameLength([0.3, 90.4, 23.7], [42.6, 23.6, 95.5, 6.3]));
2151 static assert(!isSameLength([1], [0.3, 90.4], [42]));
2152 }
2153
2154 @safe @nogc pure unittest
2155 {
2156 import std.range : only;
2157 assert(isSameLength(only(1, 2, 3), only(4, 5, 6)));
2158 assert(isSameLength(only(1, 2, 3), only(4, 5, 6), only(7, 8, 9)));
2159 assert(isSameLength(only(0.3, 90.4, 23.7, 119.2), only(42.6, 23.6, 95.5, 6.3)));
2160 assert(!isSameLength(only(1, 3, 3), only(4, 5)));
2161 assert(!isSameLength(only(1, 3, 3), only(1, 3, 3), only(4, 5)));
2162 assert(!isSameLength(only(1, 3, 3), only(4, 5), only(1, 3, 3)));
2163 }
2164
2165 @safe nothrow pure unittest
2166 {
2167 import std.internal.test.dummyrange;
2168
2169 auto r1 = new ReferenceInputRange!int([1, 2, 3]);
2170 auto r2 = new ReferenceInputRange!int([4, 5, 6]);
2171 assert(isSameLength(r1, r2));
2172
2173 auto r3 = new ReferenceInputRange!int([1, 2, 3, 4, 5, 6, 7, 8, 9, 10]);
2174 DummyRange!(ReturnBy.Reference, Length.Yes, RangeType.Input) r4;
2175 assert(isSameLength(r3, r4));
2176
2177 DummyRange!(ReturnBy.Reference, Length.Yes, RangeType.Input) r5;
2178 auto r6 = new ReferenceInputRange!int([1, 2, 3, 4, 5, 6, 7, 8, 9, 10]);
2179 assert(isSameLength(r5, r6));
2180
2181 auto r7 = new ReferenceInputRange!int([1, 2]);
2182 auto r8 = new ReferenceInputRange!int([4, 5, 6]);
2183 assert(!isSameLength(r7, r8));
2184
2185 auto r9 = new ReferenceInputRange!int([1, 2, 3, 4, 5, 6, 7, 8]);
2186 DummyRange!(ReturnBy.Reference, Length.Yes, RangeType.Input) r10;
2187 assert(!isSameLength(r9, r10));
2188
2189 DummyRange!(ReturnBy.Reference, Length.Yes, RangeType.Input) r11;
2190 auto r12 = new ReferenceInputRange!int([1, 2, 3, 4, 5, 6, 7, 8]);
2191 assert(!isSameLength(r11, r12));
2192
2193 import std.algorithm.iteration : filter;
2194
2195 assert(isSameLength(filter!"a >= 1"([1, 2, 3]), [4, 5, 6]));
2196 assert(!isSameLength(filter!"a > 1"([1, 2, 3]), [4, 5, 6]));
2197
2198 assert(isSameLength(filter!"a > 1"([1, 2, 3]), filter!"a > 4"([4, 5, 6])));
2199 assert(isSameLength(filter!"a > 1"([1, 2, 3]),
2200 filter!"a > 4"([4, 5, 6]), filter!"a >= 5"([4, 5, 6])));
2201 }
2202
2203 // Still functional but not documented anymore.
2204 alias AllocateGC = Flag!"allocateGC";
2205
2206 /**
2207 Checks if both ranges are permutations of each other.
2208
2209 This function can allocate if the `Yes.allocateGC` flag is passed. This has
2210 the benefit of have better complexity than the `Yes.allocateGC` option. However,
2211 this option is only available for ranges whose equality can be determined via each
2212 element's `toHash` method. If customized equality is needed, then the `pred`
2213 template parameter can be passed, and the function will automatically switch to
2214 the non-allocating algorithm. See $(REF binaryFun, std,functional) for more details on
2215 how to define `pred`.
2216
2217 Non-allocating forward range option: $(BIGOH n^2)
2218 Non-allocating forward range option with custom `pred`: $(BIGOH n^2)
2219 Allocating forward range option: amortized $(BIGOH r1.length) + $(BIGOH r2.length)
2220
2221 Params:
2222 pred = an optional parameter to change how equality is defined
2223 allocateGC = `Yes.allocateGC`/`No.allocateGC`
2224 r1 = A finite $(REF_ALTTEXT forward range, isForwardRange, std,range,primitives)
2225 r2 = A finite $(REF_ALTTEXT forward range, isForwardRange, std,range,primitives)
2226
2227 Returns:
2228 `true` if all of the elements in `r1` appear the same number of times in `r2`.
2229 Otherwise, returns `false`.
2230 */
2231
2232 bool isPermutation(Flag!"allocateGC" allocateGC, Range1, Range2)
2233 (Range1 r1, Range2 r2)
2234 if (allocateGC == Yes.allocateGC &&
2235 isForwardRange!Range1 &&
2236 isForwardRange!Range2 &&
2237 !isInfinite!Range1 &&
2238 !isInfinite!Range2)
2239 {
2240 alias E1 = Unqual!(ElementType!Range1);
2241 alias E2 = Unqual!(ElementType!Range2);
2242
2243 if (!isSameLength(r1.save, r2.save))
2244 {
2245 return false;
2246 }
2247
2248 // Skip the elements at the beginning where r1.front == r2.front,
2249 // they are in the same order and don't need to be counted.
2250 while (!r1.empty && !r2.empty && r1.front == r2.front)
2251 {
2252 r1.popFront();
2253 r2.popFront();
2254 }
2255
2256 if (r1.empty && r2.empty)
2257 {
2258 return true;
2259 }
2260
2261 int[CommonType!(E1, E2)] counts;
2262
foreach(item;r1)2263 foreach (item; r1)
2264 {
2265 ++counts[item];
2266 }
2267
foreach(item;r2)2268 foreach (item; r2)
2269 {
2270 if (--counts[item] < 0)
2271 {
2272 return false;
2273 }
2274 }
2275
2276 return true;
2277 }
2278
2279 /// ditto
2280 bool isPermutation(alias pred = "a == b", Range1, Range2)
2281 (Range1 r1, Range2 r2)
2282 if (is(typeof(binaryFun!(pred))) &&
2283 isForwardRange!Range1 &&
2284 isForwardRange!Range2 &&
2285 !isInfinite!Range1 &&
2286 !isInfinite!Range2)
2287 {
2288 import std.algorithm.searching : count;
2289
2290 alias predEquals = binaryFun!(pred);
2291 alias E1 = Unqual!(ElementType!Range1);
2292 alias E2 = Unqual!(ElementType!Range2);
2293
2294 if (!isSameLength(r1.save, r2.save))
2295 {
2296 return false;
2297 }
2298
2299 // Skip the elements at the beginning where r1.front == r2.front,
2300 // they are in the same order and don't need to be counted.
2301 while (!r1.empty && !r2.empty && predEquals(r1.front, r2.front))
2302 {
2303 r1.popFront();
2304 r2.popFront();
2305 }
2306
2307 if (r1.empty && r2.empty)
2308 {
2309 return true;
2310 }
2311
2312 size_t r1_count;
2313 size_t r2_count;
2314
2315 // At each element item, when computing the count of item, scan it while
2316 // also keeping track of the scanning index. If the first occurrence
2317 // of item in the scanning loop has an index smaller than the current index,
2318 // then you know that the element has been seen before
2319 size_t index;
2320 outloop: for (auto r1s1 = r1.save; !r1s1.empty; r1s1.popFront, index++)
2321 {
2322 auto item = r1s1.front;
2323 r1_count = 0;
2324 r2_count = 0;
2325
2326 size_t i;
2327 for (auto r1s2 = r1.save; !r1s2.empty; r1s2.popFront, i++)
2328 {
2329 auto e = r1s2.front;
2330 if (predEquals(e, item) && i < index)
2331 {
2332 continue outloop;
2333 }
2334 else if (predEquals(e, item))
2335 {
2336 ++r1_count;
2337 }
2338 }
2339
2340 r2_count = r2.save.count!pred(item);
2341
2342 if (r1_count != r2_count)
2343 {
2344 return false;
2345 }
2346 }
2347
2348 return true;
2349 }
2350
2351 ///
2352 @safe pure unittest
2353 {
2354 import std.typecons : Yes;
2355
2356 assert(isPermutation([1, 2, 3], [3, 2, 1]));
2357 assert(isPermutation([1.1, 2.3, 3.5], [2.3, 3.5, 1.1]));
2358 assert(isPermutation("abc", "bca"));
2359
2360 assert(!isPermutation([1, 2], [3, 4]));
2361 assert(!isPermutation([1, 1, 2, 3], [1, 2, 2, 3]));
2362 assert(!isPermutation([1, 1], [1, 1, 1]));
2363
2364 // Faster, but allocates GC handled memory
2365 assert(isPermutation!(Yes.allocateGC)([1.1, 2.3, 3.5], [2.3, 3.5, 1.1]));
2366 assert(!isPermutation!(Yes.allocateGC)([1, 2], [3, 4]));
2367 }
2368
2369 // Test @nogc inference
2370 @safe @nogc pure unittest
2371 {
2372 static immutable arr1 = [1, 2, 3];
2373 static immutable arr2 = [3, 2, 1];
2374 assert(isPermutation(arr1, arr2));
2375
2376 static immutable arr3 = [1, 1, 2, 3];
2377 static immutable arr4 = [1, 2, 2, 3];
2378 assert(!isPermutation(arr3, arr4));
2379 }
2380
2381 @safe pure unittest
2382 {
2383 import std.internal.test.dummyrange;
2384
2385 auto r1 = new ReferenceForwardRange!int([1, 2, 3, 4]);
2386 auto r2 = new ReferenceForwardRange!int([1, 2, 4, 3]);
2387 assert(isPermutation(r1, r2));
2388
2389 auto r3 = new ReferenceForwardRange!int([1, 2, 3, 4]);
2390 auto r4 = new ReferenceForwardRange!int([4, 2, 1, 3]);
2391 assert(isPermutation!(Yes.allocateGC)(r3, r4));
2392
2393 auto r5 = new ReferenceForwardRange!int([1, 2, 3]);
2394 auto r6 = new ReferenceForwardRange!int([4, 2, 1, 3]);
2395 assert(!isPermutation(r5, r6));
2396
2397 auto r7 = new ReferenceForwardRange!int([4, 2, 1, 3]);
2398 auto r8 = new ReferenceForwardRange!int([1, 2, 3]);
2399 assert(!isPermutation!(Yes.allocateGC)(r7, r8));
2400
2401 DummyRange!(ReturnBy.Reference, Length.Yes, RangeType.Random) r9;
2402 DummyRange!(ReturnBy.Reference, Length.Yes, RangeType.Random) r10;
2403 assert(isPermutation(r9, r10));
2404
2405 DummyRange!(ReturnBy.Reference, Length.Yes, RangeType.Random) r11;
2406 DummyRange!(ReturnBy.Reference, Length.Yes, RangeType.Random) r12;
2407 assert(isPermutation!(Yes.allocateGC)(r11, r12));
2408
2409 alias mytuple = Tuple!(int, int);
2410
2411 assert(isPermutation!"a[0] == b[0]"(
2412 [mytuple(1, 4), mytuple(2, 5)],
2413 [mytuple(2, 3), mytuple(1, 2)]
2414 ));
2415 }
2416
2417 /**
2418 Get the _first argument `a` that passes an `if (unaryFun!pred(a))` test. If
2419 no argument passes the test, return the last argument.
2420
2421 Similar to behaviour of the `or` operator in dynamic languages such as Lisp's
2422 `(or ...)` and Python's `a or b or ...` except that the last argument is
2423 returned upon no match.
2424
2425 Simplifies logic, for instance, in parsing rules where a set of alternative
2426 matchers are tried. The _first one that matches returns it match result,
2427 typically as an abstract syntax tree (AST).
2428
2429 Bugs:
2430 Lazy parameters are currently, too restrictively, inferred by DMD to
2431 always throw even though they don't need to be. This makes it impossible to
2432 currently mark `either` as `nothrow`. See issue at $(BUGZILLA 12647).
2433
2434 Returns:
2435 The _first argument that passes the test `pred`.
2436 */
2437 CommonType!(T, Ts) either(alias pred = a => a, T, Ts...)(T first, lazy Ts alternatives)
2438 if (alternatives.length >= 1 &&
2439 !is(CommonType!(T, Ts) == void) &&
2440 allSatisfy!(ifTestable, T, Ts))
2441 {
2442 alias predFun = unaryFun!pred;
2443
2444 if (predFun(first)) return first;
2445
2446 foreach (e; alternatives[0 .. $ - 1])
2447 if (predFun(e)) return e;
2448
2449 return alternatives[$ - 1];
2450 }
2451
2452 ///
2453 @safe pure @betterC unittest
2454 {
2455 const a = 1;
2456 const b = 2;
2457 auto ab = either(a, b);
2458 static assert(is(typeof(ab) == const(int)));
2459 assert(ab == a);
2460
2461 auto c = 2;
2462 const d = 3;
2463 auto cd = either!(a => a == 3)(c, d); // use predicate
2464 static assert(is(typeof(cd) == int));
2465 assert(cd == d);
2466
2467 auto e = 0;
2468 const f = 2;
2469 auto ef = either(e, f);
2470 static assert(is(typeof(ef) == int));
2471 assert(ef == f);
2472 }
2473
2474 ///
2475 @safe pure unittest
2476 {
2477 immutable p = 1;
2478 immutable q = 2;
2479 auto pq = either(p, q);
2480 static assert(is(typeof(pq) == immutable(int)));
2481 assert(pq == p);
2482
2483 assert(either(3, 4) == 3);
2484 assert(either(0, 4) == 4);
2485 assert(either(0, 0) == 0);
2486 assert(either("", "a") == "");
2487 }
2488
2489 ///
2490 @safe pure unittest
2491 {
2492 string r = null;
2493 assert(either(r, "a") == "a");
2494 assert(either("a", "") == "a");
2495
2496 immutable s = [1, 2];
2497 assert(either(s, s) == s);
2498
2499 assert(either([0, 1], [1, 2]) == [0, 1]);
2500 assert(either([0, 1], [1]) == [0, 1]);
2501 assert(either("a", "b") == "a");
2502
2503 static assert(!__traits(compiles, either(1, "a")));
2504 static assert(!__traits(compiles, either(1.0, "a")));
2505 static assert(!__traits(compiles, either('a', "a")));
2506 }
2507