1// Written in the D programming language. 2/** 3This is a submodule of $(MREF std, algorithm). 4It 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 48Copyright: Andrei Alexandrescu 2008-. 49 50License: $(HTTP boost.org/LICENSE_1_0.txt, Boost License 1.0). 51 52Authors: $(HTTP erdani.com, Andrei Alexandrescu) 53 54Source: $(PHOBOSSRC std/algorithm/comparison.d) 55 56Macros: 57T2=$(TR $(TDNW $(LREF $1)) $(TD $+)) 58 */ 59module std.algorithm.comparison; 60 61import std.functional : unaryFun, binaryFun, lessThan, greaterThan; 62import std.range.primitives; 63import std.traits; 64import std.meta : allSatisfy, anySatisfy; 65import std.typecons : tuple, Tuple, Flag, Yes; 66 67import std.internal.attributes : betterC; 68 69/** 70Find `value` _among `values`, returning the 1-based index 71of the first matching value in `values`, or `0` if `value` 72is not _among `values`. The predicate `pred` is used to 73compare values, and uses equality by default. 74 75Params: 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 80Returns: 81 0 if value was not found among the values, otherwise the index of the 82 found value plus one is returned. 83 84See_Also: 85$(REF_ALTTEXT find, find, std,algorithm,searching) and $(REF_ALTTEXT canFind, canFind, std,algorithm,searching) for finding a value in a 86range. 87*/ 88uint among(alias pred = (a, b) => a == b, Value, Values...) 89 (Value value, Values values) 90if (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 101template among(values...) 102if (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/** 133Alternatively, `values` can be passed at compile-time, allowing for a more 134efficient 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. 179private 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/** 214Executes and returns one of a collection of handlers based on the type of the 215switch object. 216 217The first choice that `switchObject` can be casted to the type 218of argument it accepts will be called with `switchObject` casted to that 219type, and the value it'll return will be returned by `castSwitch`. 220 221If a choice's return type is void, the choice must throw an exception, unless 222all the choices are void. In that case, castSwitch itself will return void. 223 224Throws: If none of the choice matches, a `SwitchError` will be thrown. $(D 225SwitchError) will also be thrown if not all the choices are void and a void 226choice was executed without throwing anything. 227 228Params: 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 235Returns: 236 The value of the selected choice. 237 238Note: `castSwitch` can only be used with object types. 239*/ 240auto 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 566Params: 567 val = The value to _clamp. 568 lower = The _lower bound of the _clamp. 569 upper = The _upper bound of the _clamp. 570 571Returns: 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*/ 579T1 clamp(T1, T2, T3)(T1 val, T2 lower, T3 upper) 580if (is(typeof(val.lessThan(lower) ? lower : val.greaterThan(upper) ? upper : val) : T1)) 581in 582{ 583 assert(!lower.greaterThan(upper), "Lower can't be greater than upper."); 584} 585do 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; 633 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/********************************** 642Performs a lexicographical comparison on two 643$(REF_ALTTEXT input ranges, isInputRange, std,range,primitives). 644Iterating `r1` and `r2` in lockstep, `cmp` compares each element 645`e1` of `r1` with the corresponding element `e2` in `r2`. If one 646of the ranges has been finished, `cmp` returns a negative value 647if `r1` has fewer elements than `r2`, a positive value if `r1` 648has more elements than `r2`, and `0` if the ranges have the same 649number of elements. 650 651If the ranges are strings, `cmp` performs UTF decoding 652appropriately and compares the ranges one code point at a time. 653 654A custom predicate may be specified, in which case `cmp` performs 655a three-way lexicographical comparison using `pred`. Otherwise 656the elements are compared using `opCmp`. 657 658Params: 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 664Returns: 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 671Note: 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*/ 676auto cmp(R1, R2)(R1 r1, R2 r2) 677if (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 749int cmp(alias pred, R1, R2)(R1 r1, R2 r2) 750if (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/// 783pure @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 820pure @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{ 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 { 879 int opCmp(ref const S rhs) const 880 { 881 ++ctr; 882 return 0; 883 } 884 bool opEquals(T)(T o) const { return false; } 885 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 894nothrow pure @safe @nogc unittest 895{ 896 import std.array : staticArray; 897 // Test cmp when opCmp returns float. 898 struct F 899 { 900 float value; 901 float opCmp(const ref F rhs) const 902 { 903 return value - rhs.value; 904 } 905 bool opEquals(T)(T o) const { return false; } 906 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 919nothrow 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/** 928Compares two or more ranges for equality, as defined by predicate `pred` 929(which is `==` by default). 930*/ 931template 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; 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 { 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 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/++ 1092Tip: `equal` can itself be used as a predicate to other functions. 1093This can be very useful when the element type of a range is itself a 1094range. In particular, `equal` can be its own predicate, allowing 1095range 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{ 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/** 1220Encodes $(HTTP realityinteractive.com/rgrzywinski/archives/000249.html, 1221edit operations) necessary to transform one sequence into 1222another. Given sequences `s` (source) and `t` (target), a 1223sequence of `EditOp` encodes the steps that need to be taken to 1224convert `s` into `t`. For example, if `s = "cat"` and $(D 1225"cars"), the minimal sequence that transforms `s` into `t` is: 1226skip two characters, replace 't' with 'r', and insert an 's'. Working 1227with edit operations is useful in applications such as spell-checkers 1228(to find the closest word to a given misspelled word), approximate 1229searches, diff-style programs that compute the difference between 1230files, efficient encoding of patches, DNA sequence analysis, and 1231plagiarism detection. 1232*/ 1233 1234enum 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{ 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 1256private struct Levenshtein(Range, alias equals, CostType = size_t) 1257{ 1258 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 1295 ~this() { 1296 FreeMatrix(); 1297 } 1298 1299private: 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 1307 ref CostType matrix(size_t row, size_t col) { return _matrix[row * cols + col]; } 1308 1309 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 1332 void FreeMatrix() @trusted { 1333 import core.stdc.stdlib : free; 1334 1335 free(_matrix.ptr); 1336 _matrix = null; 1337 } 1338 1339 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 1346 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 1358 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 1391 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/** 1433Returns the $(HTTP wikipedia.org/wiki/Levenshtein_distance, Levenshtein 1434distance) between `s` and `t`. The Levenshtein distance computes 1435the minimal amount of edit operations necessary to transform `s` 1436into `t`. Performs $(BIGOH s.length * t.length) evaluations of $(D 1437equals) and occupies $(BIGOH min(s.length, t.length)) storage. 1438 1439Params: 1440 equals = The binary predicate to compare the elements of the two ranges. 1441 s = The original range. 1442 t = The transformation target 1443 1444Returns: 1445 The minimal number of edits to transform s into t. 1446 1447Does not allocate GC memory. 1448*/ 1449size_t levenshteinDistance(alias equals = (a,b) => a == b, Range1, Range2) 1450 (Range1 s, Range2 t) 1451if (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 1520size_t levenshteinDistance(alias equals = (a,b) => a == b, Range1, Range2) 1521 (auto ref Range1 s, auto ref Range2 t) 1522if (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/** 1546Returns the Levenshtein distance and the edit path between `s` and 1547`t`. 1548 1549Params: 1550 equals = The binary predicate to compare the elements of the two ranges. 1551 s = The original range. 1552 t = The transformation target 1553 1554Returns: 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 1558Allocates GC memory for the returned EditOp[] array. 1559*/ 1560Tuple!(size_t, EditOp[]) 1561levenshteinDistanceAndPath(alias equals = (a,b) => a == b, Range1, Range2) 1562 (Range1 s, Range2 t) 1563if (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 1590Tuple!(size_t, EditOp[]) 1591levenshteinDistanceAndPath(alias equals = (a,b) => a == b, Range1, Range2) 1592 (auto ref Range1 s, auto ref Range2 t) 1593if (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/** 1611Iterates the passed arguments and returns the maximum value. 1612 1613Params: 1614 args = The values to select the maximum from. At least two arguments must 1615 be passed, and they must be comparable with `<`. 1616 1617Returns: 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 1624See_Also: 1625 $(REF maxElement, std,algorithm,searching) 1626*/ 1627auto max(T...)(T args) 1628if (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 1664T max(T, U)(T a, U b) 1665if (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/** 1718Iterates the passed arguments and returns the minimum value. 1719 1720Params: 1721 args = The values to select the minimum from. At least two arguments must 1722 be passed, and they must be comparable with `<`. 1723 1724Returns: 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 1731See_Also: 1732 $(REF minElement, std,algorithm,searching) 1733*/ 1734auto min(T...)(T args) 1735if (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 1774T min(T, U)(T a, U b) 1775if (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/** 1807With arguments of mixed signedness, the return type is the one that can 1808store 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; 1840 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/** 1847Sequentially compares elements in `rs` in lockstep, and 1848stops at the first mismatch (according to `pred`, by default 1849equality). Returns a tuple with the reduced ranges that start with the 1850two mismatched values. Performs $(BIGOH min(r[0].length, r[1].length, ...)) 1851evaluations of `pred`. 1852*/ 1853Tuple!(Ranges) 1854mismatch(alias pred = (a, b) => a == b, Ranges...)(Ranges rs) 1855if (rs.length >= 2 && allSatisfy!(isInputRange, Ranges)) 1856{ 1857 loop: for (; !rs[0].empty; rs[0].popFront) 1858 { 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/** 1897Returns one of a collection of expressions based on the value of the switch 1898expression. 1899 1900`choices` needs to be composed of pairs of test expressions and return 1901expressions. Each test-expression is compared with `switchExpression` using 1902`pred`(`switchExpression` is the first argument) and if that yields true - 1903the return expression is returned. 1904 1905Both the test and the return expressions are lazily evaluated. 1906 1907Params: 1908 1909switchExpression = The first argument for the predicate. 1910 1911choices = Pairs of test expressions and return expressions. The test 1912expressions will be the second argument for the predicate, and the return 1913expression will be returned if the predicate yields true with $(D 1914switchExpression) and the test expression as arguments. May also have a 1915default return expression, that needs to be the last expression without a test 1916expression before it. A return expression may be of void type only if it 1917always throws. 1918 1919Returns: The return expression associated with the first test expression that 1920made the predicate yield true, or the default return expression if no test 1921expression matched. 1922 1923Throws: If there is no default return expression and the predicate does not 1924yield true with any test expression - `SwitchError` is thrown. $(D 1925SwitchError) is also thrown if a void return expression was executed without 1926throwing anything. 1927*/ 1928auto predSwitch(alias pred = "a == b", T, R ...)(T switchExpression, lazy R choices) 1929{ 1930 import core.exception : SwitchError; 1931 alias predicate = binaryFun!(pred); 1932 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: 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/** 2035Checks if two or more ranges have the same number of elements. This function is 2036optimized to always take advantage of the `length` member of either range 2037if it exists. 2038 2039If 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 2042length. 2043 2044Infinite ranges are considered of the same length. An infinite range has never 2045the same length as a finite range. 2046 2047Params: 2048 rs = two or more $(REF_ALTTEXT input ranges, isInputRange, std,range,primitives) 2049 2050Returns: 2051 `true` if both ranges have the same length, `false` otherwise. 2052*/ 2053bool isSameLength(Ranges...)(Ranges rs) 2054if (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; 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) 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 } 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 (;;) 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. 2204alias AllocateGC = Flag!"allocateGC"; 2205 2206/** 2207Checks if both ranges are permutations of each other. 2208 2209This function can allocate if the `Yes.allocateGC` flag is passed. This has 2210the benefit of have better complexity than the `Yes.allocateGC` option. However, 2211this option is only available for ranges whose equality can be determined via each 2212element's `toHash` method. If customized equality is needed, then the `pred` 2213template parameter can be passed, and the function will automatically switch to 2214the non-allocating algorithm. See $(REF binaryFun, std,functional) for more details on 2215how to define `pred`. 2216 2217Non-allocating forward range option: $(BIGOH n^2) 2218Non-allocating forward range option with custom `pred`: $(BIGOH n^2) 2219Allocating forward range option: amortized $(BIGOH r1.length) + $(BIGOH r2.length) 2220 2221Params: 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 2227Returns: 2228 `true` if all of the elements in `r1` appear the same number of times in `r2`. 2229 Otherwise, returns `false`. 2230*/ 2231 2232bool isPermutation(Flag!"allocateGC" allocateGC, Range1, Range2) 2233(Range1 r1, Range2 r2) 2234if (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 2263 foreach (item; r1) 2264 { 2265 ++counts[item]; 2266 } 2267 2268 foreach (item; r2) 2269 { 2270 if (--counts[item] < 0) 2271 { 2272 return false; 2273 } 2274 } 2275 2276 return true; 2277} 2278 2279/// ditto 2280bool isPermutation(alias pred = "a == b", Range1, Range2) 2281(Range1 r1, Range2 r2) 2282if (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/** 2418Get the _first argument `a` that passes an `if (unaryFun!pred(a))` test. If 2419no argument passes the test, return the last argument. 2420 2421Similar 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 2423returned upon no match. 2424 2425Simplifies logic, for instance, in parsing rules where a set of alternative 2426matchers are tried. The _first one that matches returns it match result, 2427typically as an abstract syntax tree (AST). 2428 2429Bugs: 2430Lazy parameters are currently, too restrictively, inferred by DMD to 2431always throw even though they don't need to be. This makes it impossible to 2432currently mark `either` as `nothrow`. See issue at $(BUGZILLA 12647). 2433 2434Returns: 2435 The _first argument that passes the test `pred`. 2436*/ 2437CommonType!(T, Ts) either(alias pred = a => a, T, Ts...)(T first, lazy Ts alternatives) 2438if (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