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