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