1 // Written in the D programming language. 2 /** 3 This is a submodule of $(MREF std, algorithm). 4 It contains generic iteration algorithms. 5 6 $(SCRIPT inhibitQuickIndex = 1;) 7 $(BOOKTABLE Cheat Sheet, 8 $(TR $(TH Function Name) $(TH Description)) 9 $(T2 cache, 10 Eagerly evaluates and caches another range's `front`.) 11 $(T2 cacheBidirectional, 12 As above, but also provides `back` and `popBack`.) 13 $(T2 chunkBy, 14 `chunkBy!((a,b) => a[1] == b[1])([[1, 1], [1, 2], [2, 2], [2, 1]])` 15 returns a range containing 3 subranges: the first with just 16 `[1, 1]`; the second with the elements `[1, 2]` and `[2, 2]`; 17 and the third with just `[2, 1]`.) 18 $(T2 cumulativeFold, 19 `cumulativeFold!((a, b) => a + b)([1, 2, 3, 4])` returns a 20 lazily-evaluated range containing the successive reduced values `1`, 21 `3`, `6`, `10`.) 22 $(T2 each, 23 `each!writeln([1, 2, 3])` eagerly prints the numbers `1`, `2` 24 and `3` on their own lines.) 25 $(T2 filter, 26 `filter!(a => a > 0)([1, -1, 2, 0, -3])` iterates over elements `1` 27 and `2`.) 28 $(T2 filterBidirectional, 29 Similar to `filter`, but also provides `back` and `popBack` at 30 a small increase in cost.) 31 $(T2 fold, 32 `fold!((a, b) => a + b)([1, 2, 3, 4])` returns `10`.) 33 $(T2 group, 34 `group([5, 2, 2, 3, 3])` returns a range containing the tuples 35 `tuple(5, 1)`, `tuple(2, 2)`, and `tuple(3, 2)`.) 36 $(T2 joiner, 37 `joiner(["hello", "world!"], "; ")` returns a range that iterates 38 over the characters `"hello; world!"`. No new string is created - 39 the existing inputs are iterated.) 40 $(T2 map, 41 `map!(a => a * 2)([1, 2, 3])` lazily returns a range with the numbers 42 `2`, `4`, `6`.) 43 $(T2 mean, 44 Colloquially known as the average, `mean([1, 2, 3])` returns `2`.) 45 $(T2 permutations, 46 Lazily computes all permutations using Heap's algorithm.) 47 $(T2 reduce, 48 `reduce!((a, b) => a + b)([1, 2, 3, 4])` returns `10`. 49 This is the old implementation of `fold`.) 50 $(T2 splitter, 51 Lazily splits a range by a separator.) 52 $(T2 substitute, 53 `[1, 2].substitute(1, 0.1)` returns `[0.1, 2]`.) 54 $(T2 sum, 55 Same as `fold`, but specialized for accurate summation.) 56 $(T2 uniq, 57 Iterates over the unique elements in a range, which is assumed sorted.) 58 ) 59 60 Copyright: Andrei Alexandrescu 2008-. 61 62 License: $(HTTP boost.org/LICENSE_1_0.txt, Boost License 1.0). 63 64 Authors: $(HTTP erdani.com, Andrei Alexandrescu) 65 66 Source: $(PHOBOSSRC std/algorithm/iteration.d) 67 68 Macros: 69 T2=$(TR $(TDNW $(LREF $1)) $(TD $+)) 70 */ 71 module std.algorithm.iteration; 72 73 import std.functional : unaryFun, binaryFun; 74 import std.range.primitives; 75 import std.traits; 76 import std.typecons : Flag; 77 78 private template aggregate(fun...) 79 if (fun.length >= 1) 80 { 81 /* --Intentionally not ddoc-- 82 * Aggregates elements in each subrange of the given range of ranges using 83 * the given aggregating function(s). 84 * Params: 85 * fun = One or more aggregating functions (binary functions that return a 86 * single _aggregate value of their arguments). 87 * ror = A range of ranges to be aggregated. 88 * 89 * Returns: 90 * A range representing the aggregated value(s) of each subrange 91 * of the original range. If only one aggregating function is specified, 92 * each element will be the aggregated value itself; if multiple functions 93 * are specified, each element will be a tuple of the aggregated values of 94 * each respective function. 95 */ 96 auto aggregate(RoR)(RoR ror) 97 if (isInputRange!RoR && isIterable!(ElementType!RoR)) 98 { 99 return ror.map!(reduce!fun); 100 } 101 102 @safe unittest 103 { 104 import std.algorithm.comparison : equal, max, min; 105 106 auto data = [[4, 2, 1, 3], [4, 9, -1, 3, 2], [3]]; 107 108 // Single aggregating function 109 auto agg1 = data.aggregate!max; 110 assert(agg1.equal([4, 9, 3])); 111 112 // Multiple aggregating functions 113 import std.typecons : tuple; 114 auto agg2 = data.aggregate!(max, min); 115 assert(agg2.equal([ 116 tuple(4, 1), 117 tuple(9, -1), 118 tuple(3, 3) 119 ])); 120 } 121 } 122 123 /++ 124 `cache` eagerly evaluates $(REF_ALTTEXT front, front, std,range,primitives) of `range` 125 on each construction or call to $(REF_ALTTEXT popFront, popFront, std,range,primitives), 126 to store the result in a _cache. 127 The result is then directly returned when $(REF_ALTTEXT front, front, std,range,primitives) is called, 128 rather than re-evaluated. 129 130 This can be a useful function to place in a chain, after functions 131 that have expensive evaluation, as a lazy alternative to $(REF array, std,array). 132 In particular, it can be placed after a call to $(LREF map), or before a call 133 $(REF filter, std,range) or $(REF tee, std,range) 134 135 `cache` may provide 136 $(REF_ALTTEXT bidirectional range, isBidirectionalRange, std,range,primitives) 137 iteration if needed, but since this comes at an increased cost, it must be explicitly requested via the 138 call to `cacheBidirectional`. Furthermore, a bidirectional _cache will 139 evaluate the "center" element twice, when there is only one element left in 140 the range. 141 142 `cache` does not provide random access primitives, 143 as `cache` would be unable to _cache the random accesses. 144 If `Range` provides slicing primitives, 145 then `cache` will provide the same slicing primitives, 146 but `hasSlicing!Cache` will not yield true (as the $(REF hasSlicing, std,range,primitives) 147 trait also checks for random access). 148 149 Params: 150 range = an $(REF_ALTTEXT input range, isInputRange, std,range,primitives) 151 152 Returns: 153 An $(REF_ALTTEXT input range, isInputRange, std,range,primitives) with the cached values of range 154 +/ 155 auto cache(Range)(Range range) 156 if (isInputRange!Range) 157 { 158 return _Cache!(Range, false)(range); 159 } 160 161 /// ditto 162 auto cacheBidirectional(Range)(Range range) 163 if (isBidirectionalRange!Range) 164 { 165 return _Cache!(Range, true)(range); 166 } 167 168 /// 169 @safe unittest 170 { 171 import std.algorithm.comparison : equal; 172 import std.range, std.stdio; 173 import std.typecons : tuple; 174 175 ulong counter = 0; 176 double fun(int x) 177 { 178 ++counter; 179 // http://en.wikipedia.org/wiki/Quartic_function 180 return ( (x + 4.0) * (x + 1.0) * (x - 1.0) * (x - 3.0) ) / 14.0 + 0.5; 181 } 182 // Without cache, with array (greedy) 183 auto result1 = iota(-4, 5).map!(a =>tuple(a, fun(a)))() 184 .filter!(a => a[1] < 0)() 185 .map!(a => a[0])() 186 .array(); 187 188 // the values of x that have a negative y are: 189 assert(equal(result1, [-3, -2, 2])); 190 191 // Check how many times fun was evaluated. 192 // As many times as the number of items in both source and result. 193 assert(counter == iota(-4, 5).length + result1.length); 194 195 counter = 0; 196 // Without array, with cache (lazy) 197 auto result2 = iota(-4, 5).map!(a =>tuple(a, fun(a)))() 198 .cache() 199 .filter!(a => a[1] < 0)() 200 .map!(a => a[0])(); 201 202 // the values of x that have a negative y are: 203 assert(equal(result2, [-3, -2, 2])); 204 205 // Check how many times fun was evaluated. 206 // Only as many times as the number of items in source. 207 assert(counter == iota(-4, 5).length); 208 } 209 210 // https://issues.dlang.org/show_bug.cgi?id=15891 211 @safe pure unittest 212 { 213 assert([1].map!(x=>[x].map!(y=>y)).cache.front.front == 1); 214 } 215 216 /++ 217 Tip: `cache` is eager when evaluating elements. If calling front on the 218 underlying range has a side effect, it will be observable before calling 219 front on the actual cached range. 220 221 Furthermore, care should be taken composing `cache` with $(REF take, std,range). 222 By placing `take` before `cache`, then `cache` will be "aware" 223 of when the range ends, and correctly stop caching elements when needed. 224 If calling front has no side effect though, placing `take` after `cache` 225 may yield a faster range. 226 227 Either way, the resulting ranges will be equivalent, but maybe not at the 228 same cost or side effects. 229 +/ 230 @safe unittest 231 { 232 import std.algorithm.comparison : equal; 233 import std.range; 234 int i = 0; 235 236 auto r = iota(0, 4).tee!((a){i = a;}, No.pipeOnPop); 237 auto r1 = r.take(3).cache(); 238 auto r2 = r.cache().take(3); 239 240 assert(equal(r1, [0, 1, 2])); 241 assert(i == 2); //The last "seen" element was 2. The data in cache has been cleared. 242 243 assert(equal(r2, [0, 1, 2])); 244 assert(i == 3); //cache has accessed 3. It is still stored internally by cache. 245 } 246 247 @safe unittest 248 { 249 import std.algorithm.comparison : equal; 250 import std.range; 251 auto a = [1, 2, 3, 4]; 252 assert(equal(a.map!(a => (a - 1) * a)().cache(), [ 0, 2, 6, 12])); 253 assert(equal(a.map!(a => (a - 1) * a)().cacheBidirectional().retro(), [12, 6, 2, 0])); 254 auto r1 = [1, 2, 3, 4].cache() [1 .. $]; 255 auto r2 = [1, 2, 3, 4].cacheBidirectional()[1 .. $]; 256 assert(equal(r1, [2, 3, 4])); 257 assert(equal(r2, [2, 3, 4])); 258 } 259 260 @safe unittest 261 { 262 import std.algorithm.comparison : equal; 263 264 //immutable test 265 static struct S 266 { 267 int i; 268 this(int i) 269 { 270 //this.i = i; 271 } 272 } 273 immutable(S)[] s = [S(1), S(2), S(3)]; 274 assert(equal(s.cache(), s)); 275 assert(equal(s.cacheBidirectional(), s)); 276 } 277 278 @safe pure nothrow unittest 279 { 280 import std.algorithm.comparison : equal; 281 282 //safety etc 283 auto a = [1, 2, 3, 4]; 284 assert(equal(a.cache(), a)); 285 assert(equal(a.cacheBidirectional(), a)); 286 } 287 288 @safe unittest 289 { 290 char[][] stringbufs = ["hello".dup, "world".dup]; 291 auto strings = stringbufs.map!((a)=>a.idup)().cache(); 292 assert(strings.front is strings.front); 293 } 294 295 @safe unittest 296 { 297 import std.range : cycle; 298 import std.algorithm.comparison : equal; 299 300 auto c = [1, 2, 3].cycle().cache(); 301 c = c[1 .. $]; 302 auto d = c[0 .. 1]; 303 assert(d.equal([2])); 304 } 305 306 @safe unittest 307 { 308 static struct Range 309 { 310 bool initialized = false; 311 bool front() @property {return initialized = true;} 312 void popFront() {initialized = false;} 313 enum empty = false; 314 } 315 auto r = Range().cache(); 316 assert(r.source.initialized == true); 317 } 318 319 private struct _Cache(R, bool bidir) 320 { 321 import core.exception : RangeError; 322 323 private 324 { 325 import std.algorithm.internal : algoFormat; 326 import std.meta : AliasSeq; 327 328 alias E = ElementType!R; 329 alias UE = Unqual!E; 330 331 R source; 332 333 static if (bidir) alias CacheTypes = AliasSeq!(UE, UE); 334 else alias CacheTypes = AliasSeq!UE; 335 CacheTypes caches; 336 337 static assert(isAssignable!(UE, E) && is(UE : E), 338 algoFormat( 339 "Cannot instantiate range with %s because %s elements are not assignable to %s.", 340 R.stringof, 341 E.stringof, 342 UE.stringof 343 ) 344 ); 345 } 346 347 this(R range) 348 { 349 source = range; 350 if (!range.empty) 351 { 352 caches[0] = source.front; 353 static if (bidir) 354 caches[1] = source.back; 355 } 356 else 357 { 358 // needed, because the compiler cannot deduce, that 'caches' is initialized 359 // see https://issues.dlang.org/show_bug.cgi?id=15891 360 caches[0] = UE.init; 361 static if (bidir) 362 caches[1] = UE.init; 363 } 364 } 365 366 static if (isInfinite!R) 367 enum empty = false; 368 else 369 bool empty() @property 370 { 371 return source.empty; 372 } 373 374 static if (hasLength!R) auto length() @property 375 { 376 return source.length; 377 } 378 379 E front() @property 380 { 381 version (assert) if (empty) throw new RangeError(); 382 return caches[0]; 383 } 384 static if (bidir) E back() @property 385 { 386 version (assert) if (empty) throw new RangeError(); 387 return caches[1]; 388 } 389 390 void popFront() 391 { 392 version (assert) if (empty) throw new RangeError(); 393 source.popFront(); 394 if (!source.empty) 395 caches[0] = source.front; 396 else 397 { 398 // see https://issues.dlang.org/show_bug.cgi?id=15891 399 caches[0] = UE.init; 400 static if (bidir) 401 caches[1] = UE.init; 402 } 403 } 404 static if (bidir) void popBack() 405 { 406 version (assert) if (empty) throw new RangeError(); 407 source.popBack(); 408 if (!source.empty) 409 caches[1] = source.back; 410 else 411 { 412 // see https://issues.dlang.org/show_bug.cgi?id=15891 413 caches[0] = UE.init; 414 caches[1] = UE.init; 415 } 416 } 417 418 static if (isForwardRange!R) 419 { 420 private this(R source, ref CacheTypes caches) 421 { 422 this.source = source; 423 this.caches = caches; 424 } 425 typeof(this) save() @property 426 { 427 return typeof(this)(source.save, caches); 428 } 429 } 430 431 static if (hasSlicing!R) 432 { 433 enum hasEndSlicing = is(typeof(source[size_t.max .. $])); 434 435 static if (hasEndSlicing) 436 { 437 private static struct DollarToken{} 438 enum opDollar = DollarToken.init; 439 440 auto opSlice(size_t low, DollarToken) 441 { 442 return typeof(this)(source[low .. $]); 443 } 444 } 445 446 static if (!isInfinite!R) 447 { 448 typeof(this) opSlice(size_t low, size_t high) 449 { 450 return typeof(this)(source[low .. high]); 451 } 452 } 453 else static if (hasEndSlicing) 454 { 455 auto opSlice(size_t low, size_t high) 456 in 457 { 458 assert(low <= high, "Bounds error when slicing cache."); 459 } 460 do 461 { 462 import std.range : takeExactly; 463 return this[low .. $].takeExactly(high - low); 464 } 465 } 466 } 467 } 468 469 /** 470 Implements the homonym function (also known as `transform`) present 471 in many languages of functional flavor. The call `map!(fun)(range)` 472 returns a range of which elements are obtained by applying `fun(a)` 473 left to right for all elements `a` in `range`. The original ranges are 474 not changed. Evaluation is done lazily. 475 476 Params: 477 fun = one or more transformation functions 478 479 See_Also: 480 $(HTTP en.wikipedia.org/wiki/Map_(higher-order_function), Map (higher-order function)) 481 */ 482 template map(fun...) 483 if (fun.length >= 1) 484 { 485 /** 486 Params: 487 r = an $(REF_ALTTEXT input range, isInputRange, std,range,primitives) 488 Returns: 489 A range with each fun applied to all the elements. If there is more than one 490 fun, the element type will be `Tuple` containing one element for each fun. 491 */ 492 auto map(Range)(Range r) if (isInputRange!(Unqual!Range)) 493 { 494 import std.meta : AliasSeq, staticMap; 495 496 alias RE = ElementType!(Range); 497 static if (fun.length > 1) 498 { 499 import std.functional : adjoin; 500 import std.meta : staticIndexOf; 501 502 alias _funs = staticMap!(unaryFun, fun); 503 alias _fun = adjoin!_funs; 504 505 // Once https://issues.dlang.org/show_bug.cgi?id=5710 is fixed 506 // accross all compilers (as of 2020-04, it wasn't fixed in LDC and GDC), 507 // this validation loop can be moved into a template. 508 foreach (f; _funs) 509 { 510 static assert(!is(typeof(f(RE.init)) == void), 511 "Mapping function(s) must not return void: " ~ _funs.stringof); 512 } 513 } 514 else 515 { 516 alias _fun = unaryFun!fun; 517 alias _funs = AliasSeq!(_fun); 518 519 // Do the validation separately for single parameters due to 520 // https://issues.dlang.org/show_bug.cgi?id=15777. 521 static assert(!is(typeof(_fun(RE.init)) == void), 522 "Mapping function(s) must not return void: " ~ _funs.stringof); 523 } 524 525 return MapResult!(_fun, Range)(r); 526 } 527 } 528 529 /// 530 @safe @nogc unittest 531 { 532 import std.algorithm.comparison : equal; 533 import std.range : chain, only; 534 auto squares = 535 chain(only(1, 2, 3, 4), only(5, 6)).map!(a => a * a); 536 assert(equal(squares, only(1, 4, 9, 16, 25, 36))); 537 } 538 539 /** 540 Multiple functions can be passed to `map`. In that case, the 541 element type of `map` is a tuple containing one element for each 542 function. 543 */ 544 @safe unittest 545 { 546 auto sums = [2, 4, 6, 8]; 547 auto products = [1, 4, 9, 16]; 548 549 size_t i = 0; 550 foreach (result; [ 1, 2, 3, 4 ].map!("a + a", "a * a")) 551 { 552 assert(result[0] == sums[i]); 553 assert(result[1] == products[i]); 554 ++i; 555 } 556 } 557 558 /** 559 You may alias `map` with some function(s) to a symbol and use 560 it separately: 561 */ 562 @safe unittest 563 { 564 import std.algorithm.comparison : equal; 565 import std.conv : to; 566 567 alias stringize = map!(to!string); 568 assert(equal(stringize([ 1, 2, 3, 4 ]), [ "1", "2", "3", "4" ])); 569 } 570 571 // Verify workaround for https://issues.dlang.org/show_bug.cgi?id=15777 572 @safe unittest 573 { 574 import std.algorithm.mutation, std..string; 575 auto foo(string[] args) 576 { 577 return args.map!strip; 578 } 579 } 580 581 private struct MapResult(alias fun, Range) 582 { 583 alias R = Unqual!Range; 584 R _input; 585 586 static if (isBidirectionalRange!R) 587 { 588 @property auto ref back()() 589 { 590 assert(!empty, "Attempting to fetch the back of an empty map."); 591 return fun(_input.back); 592 } 593 594 void popBack()() 595 { 596 assert(!empty, "Attempting to popBack an empty map."); 597 _input.popBack(); 598 } 599 } 600 601 this(R input) 602 { 603 _input = input; 604 } 605 606 static if (isInfinite!R) 607 { 608 // Propagate infinite-ness. 609 enum bool empty = false; 610 } 611 else 612 { 613 @property bool empty() 614 { 615 return _input.empty; 616 } 617 } 618 619 void popFront() 620 { 621 assert(!empty, "Attempting to popFront an empty map."); 622 _input.popFront(); 623 } 624 625 @property auto ref front() 626 { 627 assert(!empty, "Attempting to fetch the front of an empty map."); 628 return fun(_input.front); 629 } 630 631 static if (isRandomAccessRange!R) 632 { 633 static if (is(typeof(Range.init[ulong.max]))) 634 private alias opIndex_t = ulong; 635 else 636 private alias opIndex_t = uint; 637 638 auto ref opIndex(opIndex_t index) 639 { 640 return fun(_input[index]); 641 } 642 } 643 644 static if (hasLength!R) 645 { 646 @property auto length() 647 { 648 return _input.length; 649 } 650 651 alias opDollar = length; 652 } 653 654 static if (hasSlicing!R) 655 { 656 static if (is(typeof(_input[ulong.max .. ulong.max]))) 657 private alias opSlice_t = ulong; 658 else 659 private alias opSlice_t = uint; 660 661 static if (hasLength!R) 662 { 663 auto opSlice(opSlice_t low, opSlice_t high) 664 { 665 return typeof(this)(_input[low .. high]); 666 } 667 } 668 else static if (is(typeof(_input[opSlice_t.max .. $]))) 669 { 670 struct DollarToken{} 671 enum opDollar = DollarToken.init; 672 auto opSlice(opSlice_t low, DollarToken) 673 { 674 return typeof(this)(_input[low .. $]); 675 } 676 677 auto opSlice(opSlice_t low, opSlice_t high) 678 { 679 import std.range : takeExactly; 680 return this[low .. $].takeExactly(high - low); 681 } 682 } 683 } 684 685 static if (isForwardRange!R) 686 { 687 @property auto save() 688 { 689 return typeof(this)(_input.save); 690 } 691 } 692 } 693 694 @safe unittest 695 { 696 import std.algorithm.comparison : equal; 697 import std.conv : to; 698 import std.functional : adjoin; 699 700 alias stringize = map!(to!string); 701 assert(equal(stringize([ 1, 2, 3, 4 ]), [ "1", "2", "3", "4" ])); 702 703 uint counter; 704 alias count = map!((a) { return counter++; }); 705 assert(equal(count([ 10, 2, 30, 4 ]), [ 0, 1, 2, 3 ])); 706 707 counter = 0; 708 adjoin!((a) { return counter++; }, (a) { return counter++; })(1); 709 alias countAndSquare = map!((a) { return counter++; }, (a) { return counter++; }); 710 //assert(equal(countAndSquare([ 10, 2 ]), [ tuple(0u, 100), tuple(1u, 4) ])); 711 } 712 713 @safe unittest 714 { 715 import std.algorithm.comparison : equal; 716 import std.ascii : toUpper; 717 import std.internal.test.dummyrange; 718 import std.range; 719 import std.typecons : tuple; 720 import std.random : uniform, Random = Xorshift; 721 722 int[] arr1 = [ 1, 2, 3, 4 ]; 723 const int[] arr1Const = arr1; 724 int[] arr2 = [ 5, 6 ]; 725 auto squares = map!("a * a")(arr1Const); 726 assert(squares[$ - 1] == 16); 727 assert(equal(squares, [ 1, 4, 9, 16 ][])); 728 assert(equal(map!("a * a")(chain(arr1, arr2)), [ 1, 4, 9, 16, 25, 36 ][])); 729 730 // Test the caching stuff. 731 assert(squares.back == 16); 732 auto squares2 = squares.save; 733 assert(squares2.back == 16); 734 735 assert(squares2.front == 1); 736 squares2.popFront(); 737 assert(squares2.front == 4); 738 squares2.popBack(); 739 assert(squares2.front == 4); 740 assert(squares2.back == 9); 741 742 assert(equal(map!("a * a")(chain(arr1, arr2)), [ 1, 4, 9, 16, 25, 36 ][])); 743 744 uint i; 745 foreach (e; map!("a", "a * a")(arr1)) 746 { 747 assert(e[0] == ++i); 748 assert(e[1] == i * i); 749 } 750 751 // Test length. 752 assert(squares.length == 4); 753 assert(map!"a * a"(chain(arr1, arr2)).length == 6); 754 755 // Test indexing. 756 assert(squares[0] == 1); 757 assert(squares[1] == 4); 758 assert(squares[2] == 9); 759 assert(squares[3] == 16); 760 761 // Test slicing. 762 auto squareSlice = squares[1 .. squares.length - 1]; 763 assert(equal(squareSlice, [4, 9][])); 764 assert(squareSlice.back == 9); 765 assert(squareSlice[1] == 9); 766 767 // Test on a forward range to make sure it compiles when all the fancy 768 // stuff is disabled. 769 auto fibsSquares = map!"a * a"(recurrence!("a[n-1] + a[n-2]")(1, 1)); 770 assert(fibsSquares.front == 1); 771 fibsSquares.popFront(); 772 fibsSquares.popFront(); 773 assert(fibsSquares.front == 4); 774 fibsSquares.popFront(); 775 assert(fibsSquares.front == 9); 776 777 auto repeatMap = map!"a"(repeat(1)); 778 auto gen = Random(123_456_789); 779 auto index = uniform(0, 1024, gen); 780 static assert(isInfinite!(typeof(repeatMap))); 781 assert(repeatMap[index] == 1); 782 783 auto intRange = map!"a"([1,2,3]); 784 static assert(isRandomAccessRange!(typeof(intRange))); 785 assert(equal(intRange, [1, 2, 3])); 786 787 foreach (DummyType; AllDummyRanges) 788 { 789 DummyType d; 790 auto m = map!"a * a"(d); 791 792 static assert(propagatesRangeType!(typeof(m), DummyType)); 793 assert(equal(m, [1,4,9,16,25,36,49,64,81,100])); 794 } 795 796 //Test string access 797 string s1 = "hello world!"; 798 dstring s2 = "日本語"; 799 dstring s3 = "hello world!"d; 800 auto ms1 = map!(std.ascii.toUpper)(s1); 801 auto ms2 = map!(std.ascii.toUpper)(s2); 802 auto ms3 = map!(std.ascii.toUpper)(s3); 803 static assert(!is(ms1[0])); //narrow strings can't be indexed 804 assert(ms2[0] == '日'); 805 assert(ms3[0] == 'H'); 806 static assert(!is(ms1[0 .. 1])); //narrow strings can't be sliced 807 assert(equal(ms2[0 .. 2], "日本"w)); 808 assert(equal(ms3[0 .. 2], "HE")); 809 810 // https://issues.dlang.org/show_bug.cgi?id=5753 811 static void voidFun(int) {} 812 static int nonvoidFun(int) { return 0; } 813 static assert(!__traits(compiles, map!voidFun([1]))); 814 static assert(!__traits(compiles, map!(voidFun, voidFun)([1]))); 815 static assert(!__traits(compiles, map!(nonvoidFun, voidFun)([1]))); 816 static assert(!__traits(compiles, map!(voidFun, nonvoidFun)([1]))); 817 static assert(!__traits(compiles, map!(a => voidFun(a))([1]))); 818 819 // https://issues.dlang.org/show_bug.cgi?id=15480 820 auto dd = map!(z => z * z, c => c * c * c)([ 1, 2, 3, 4 ]); 821 assert(dd[0] == tuple(1, 1)); 822 assert(dd[1] == tuple(4, 8)); 823 assert(dd[2] == tuple(9, 27)); 824 assert(dd[3] == tuple(16, 64)); 825 assert(dd.length == 4); 826 } 827 828 @safe unittest 829 { 830 import std.algorithm.comparison : equal; 831 import std.range; 832 auto LL = iota(1L, 4L); 833 auto m = map!"a*a"(LL); 834 assert(equal(m, [1L, 4L, 9L])); 835 } 836 837 @safe unittest 838 { 839 import std.range : iota; 840 841 // https://issues.dlang.org/show_bug.cgi?id=10130 - map of iota with const step. 842 const step = 2; 843 assert(map!(i => i)(iota(0, 10, step)).walkLength == 5); 844 845 // Need these to all by const to repro the float case, due to the 846 // CommonType template used in the float specialization of iota. 847 const floatBegin = 0.0; 848 const floatEnd = 1.0; 849 const floatStep = 0.02; 850 assert(map!(i => i)(iota(floatBegin, floatEnd, floatStep)).walkLength == 50); 851 } 852 853 @safe unittest 854 { 855 import std.algorithm.comparison : equal; 856 import std.range; 857 //slicing infinites 858 auto rr = iota(0, 5).cycle().map!"a * a"(); 859 alias RR = typeof(rr); 860 static assert(hasSlicing!RR); 861 rr = rr[6 .. $]; //Advances 1 cycle and 1 unit 862 assert(equal(rr[0 .. 5], [1, 4, 9, 16, 0])); 863 } 864 865 @safe unittest 866 { 867 import std.range; 868 struct S {int* p;} 869 auto m = immutable(S).init.repeat().map!"a".save; 870 assert(m.front == immutable(S)(null)); 871 } 872 873 // Issue 20928 874 @safe unittest 875 { 876 struct Always3 877 { 878 enum empty = false; 879 auto save() { return this; } 880 long front() { return 3; } 881 void popFront() {} 882 long opIndex(ulong i) { return 3; } 883 long opIndex(ulong i) immutable { return 3; } 884 } 885 886 import std.algorithm.iteration : map; 887 Always3.init.map!(e => e)[ulong.max]; 888 } 889 890 // each 891 /** 892 Eagerly iterates over `r` and calls `fun` over _each element. 893 894 If no function to call is specified, `each` defaults to doing nothing but 895 consuming the entire range. `r.front` will be evaluated, but that can be avoided 896 by specifying a lambda with a `lazy` parameter. 897 898 `each` also supports `opApply`-based types, so it works with e.g. $(REF 899 parallel, std,parallelism). 900 901 Normally the entire range is iterated. If partial iteration (early stopping) is 902 desired, `fun` needs to return a value of type $(REF Flag, 903 std,typecons)`!"each"` (`Yes.each` to continue iteration, or `No.each` to stop 904 iteration). 905 906 Params: 907 fun = function to apply to _each element of the range 908 r = range or iterable over which `each` iterates 909 910 Returns: `Yes.each` if the entire range was iterated, `No.each` in case of early 911 stopping. 912 913 See_Also: $(REF tee, std,range) 914 */ 915 template each(alias fun = "a") 916 { 917 import std.meta : AliasSeq; 918 import std.traits : Parameters; 919 import std.typecons : Flag, Yes, No; 920 921 private: 922 alias BinaryArgs = AliasSeq!(fun, "i", "a"); 923 924 enum isRangeUnaryIterable(R) = 925 is(typeof(unaryFun!fun(R.init.front))); 926 927 enum isRangeBinaryIterable(R) = 928 is(typeof(binaryFun!BinaryArgs(0, R.init.front))); 929 930 enum isRangeIterable(R) = 931 isInputRange!R && 932 (isRangeUnaryIterable!R || isRangeBinaryIterable!R); 933 934 enum isForeachUnaryIterable(R) = 935 is(typeof((R r) { 936 foreach (ref a; r) 937 cast(void) unaryFun!fun(a); 938 })); 939 940 enum isForeachUnaryWithIndexIterable(R) = 941 is(typeof((R r) { 942 foreach (i, ref a; r) 943 cast(void) binaryFun!BinaryArgs(i, a); 944 })); 945 946 enum isForeachBinaryIterable(R) = 947 is(typeof((R r) { 948 foreach (ref a, ref b; r) 949 cast(void) binaryFun!fun(a, b); 950 })); 951 952 enum isForeachIterable(R) = 953 (!isForwardRange!R || isDynamicArray!R) && 954 (isForeachUnaryIterable!R || isForeachBinaryIterable!R || 955 isForeachUnaryWithIndexIterable!R); 956 957 public: 958 /** 959 Params: 960 r = range or iterable over which each iterates 961 */ 962 Flag!"each" each(Range)(Range r) 963 if (!isForeachIterable!Range && ( 964 isRangeIterable!Range || 965 __traits(compiles, typeof(r.front).length))) 966 { 967 static if (isRangeIterable!Range) 968 { 969 debug(each) pragma(msg, "Using while for ", Range.stringof); 970 static if (isRangeUnaryIterable!Range) 971 { 972 while (!r.empty) 973 { 974 static if (!is(typeof(unaryFun!fun(r.front)) == Flag!"each")) 975 { 976 cast(void) unaryFun!fun(r.front); 977 } 978 else 979 { 980 if (unaryFun!fun(r.front) == No.each) return No.each; 981 } 982 983 r.popFront(); 984 } 985 } 986 else // if (isRangeBinaryIterable!Range) 987 { 988 size_t i = 0; 989 while (!r.empty) 990 { 991 static if (!is(typeof(binaryFun!BinaryArgs(i, r.front)) == Flag!"each")) 992 { 993 cast(void) binaryFun!BinaryArgs(i, r.front); 994 } 995 else 996 { 997 if (binaryFun!BinaryArgs(i, r.front) == No.each) return No.each; 998 } 999 r.popFront(); 1000 i++; 1001 } 1002 } 1003 } 1004 else 1005 { 1006 // range interface with >2 parameters. 1007 for (auto range = r; !range.empty; range.popFront()) 1008 { 1009 static if (!is(typeof(fun(r.front.expand)) == Flag!"each")) 1010 { 1011 cast(void) fun(range.front.expand); 1012 } 1013 else 1014 { 1015 if (fun(range.front.expand)) return No.each; 1016 } 1017 } 1018 } 1019 return Yes.each; 1020 } 1021 1022 /// ditto 1023 Flag!"each" each(Iterable)(auto ref Iterable r) 1024 if (isForeachIterable!Iterable || 1025 __traits(compiles, Parameters!(Parameters!(r.opApply)))) 1026 { 1027 static if (isForeachIterable!Iterable) 1028 { 1029 static if (isForeachUnaryIterable!Iterable) 1030 { 1031 debug(each) pragma(msg, "Using foreach UNARY for ", Iterable.stringof); 1032 { 1033 foreach (ref e; r) 1034 { 1035 static if (!is(typeof(unaryFun!fun(e)) == Flag!"each")) 1036 { 1037 cast(void) unaryFun!fun(e); 1038 } 1039 else 1040 { 1041 if (unaryFun!fun(e) == No.each) return No.each; 1042 } 1043 } 1044 } 1045 } 1046 else static if (isForeachBinaryIterable!Iterable) 1047 { 1048 debug(each) pragma(msg, "Using foreach BINARY for ", Iterable.stringof); 1049 foreach (ref a, ref b; r) 1050 { 1051 static if (!is(typeof(binaryFun!fun(a, b)) == Flag!"each")) 1052 { 1053 cast(void) binaryFun!fun(a, b); 1054 } 1055 else 1056 { 1057 if (binaryFun!fun(a, b) == No.each) return No.each; 1058 } 1059 } 1060 } 1061 else static if (isForeachUnaryWithIndexIterable!Iterable) 1062 { 1063 debug(each) pragma(msg, "Using foreach INDEX for ", Iterable.stringof); 1064 foreach (i, ref e; r) 1065 { 1066 static if (!is(typeof(binaryFun!BinaryArgs(i, e)) == Flag!"each")) 1067 { 1068 cast(void) binaryFun!BinaryArgs(i, e); 1069 } 1070 else 1071 { 1072 if (binaryFun!BinaryArgs(i, e) == No.each) return No.each; 1073 } 1074 } 1075 } 1076 else 1077 { 1078 static assert(0, "Invalid foreach iteratable type " ~ Iterable.stringof ~ " met."); 1079 } 1080 return Yes.each; 1081 } 1082 else 1083 { 1084 // opApply with >2 parameters. count the delegate args. 1085 // only works if it is not templated (otherwise we cannot count the args) 1086 auto result = Yes.each; 1087 auto dg(Parameters!(Parameters!(r.opApply)) params) 1088 { 1089 static if (!is(typeof(binaryFun!BinaryArgs(i, e)) == Flag!"each")) 1090 { 1091 fun(params); 1092 return 0; // tells opApply to continue iteration 1093 } 1094 else 1095 { 1096 result = fun(params); 1097 return result == Yes.each ? 0 : -1; 1098 } 1099 } 1100 r.opApply(&dg); 1101 return result; 1102 } 1103 } 1104 } 1105 1106 /// 1107 @system unittest 1108 { 1109 import std.range : iota; 1110 import std.typecons : Flag, Yes, No; 1111 1112 long[] arr; 1113 iota(5).each!(n => arr ~= n); 1114 assert(arr == [0, 1, 2, 3, 4]); 1115 iota(5).each!((n) { arr ~= n; return No.each; }); 1116 assert(arr == [0, 1, 2, 3, 4, 0]); 1117 1118 // If the range supports it, the value can be mutated in place 1119 arr.each!((ref n) => n++); 1120 assert(arr == [1, 2, 3, 4, 5, 1]); 1121 1122 arr.each!"a++"; 1123 assert(arr == [2, 3, 4, 5, 6, 2]); 1124 1125 // by-ref lambdas are not allowed for non-ref ranges 1126 static assert(!is(typeof(arr.map!(n => n).each!((ref n) => n++)))); 1127 1128 // The default predicate consumes the range 1129 auto m = arr.map!(n => n); 1130 (&m).each(); 1131 assert(m.empty); 1132 1133 // Indexes are also available for in-place mutations 1134 arr[] = 0; 1135 arr.each!"a=i"(); 1136 assert(arr == [0, 1, 2, 3, 4, 5]); 1137 1138 // opApply iterators work as well 1139 static class S 1140 { 1141 int x; 1142 int opApply(scope int delegate(ref int _x) dg) { return dg(x); } 1143 } 1144 1145 auto s = new S; 1146 s.each!"a++"; 1147 assert(s.x == 1); 1148 } 1149 1150 // binary foreach with two ref args 1151 @system unittest 1152 { 1153 import std.range : lockstep; 1154 1155 auto a = [ 1, 2, 3 ]; 1156 auto b = [ 2, 3, 4 ]; 1157 1158 a.lockstep(b).each!((ref x, ref y) { ++x; ++y; }); 1159 1160 assert(a == [ 2, 3, 4 ]); 1161 assert(b == [ 3, 4, 5 ]); 1162 } 1163 1164 // https://issues.dlang.org/show_bug.cgi?id=15358 1165 // application of `each` with >2 args (opApply) 1166 @system unittest 1167 { 1168 import std.range : lockstep; 1169 auto a = [0,1,2]; 1170 auto b = [3,4,5]; 1171 auto c = [6,7,8]; 1172 1173 lockstep(a, b, c).each!((ref x, ref y, ref z) { ++x; ++y; ++z; }); 1174 1175 assert(a == [1,2,3]); 1176 assert(b == [4,5,6]); 1177 assert(c == [7,8,9]); 1178 } 1179 1180 // https://issues.dlang.org/show_bug.cgi?id=15358 1181 // application of `each` with >2 args (range interface) 1182 @safe unittest 1183 { 1184 import std.range : zip; 1185 auto a = [0,1,2]; 1186 auto b = [3,4,5]; 1187 auto c = [6,7,8]; 1188 1189 int[] res; 1190 1191 zip(a, b, c).each!((x, y, z) { res ~= x + y + z; }); 1192 1193 assert(res == [9, 12, 15]); 1194 } 1195 1196 // https://issues.dlang.org/show_bug.cgi?id=16255 1197 // `each` on opApply doesn't support ref 1198 @safe unittest 1199 { 1200 int[] dynamicArray = [1, 2, 3, 4, 5]; 1201 int[5] staticArray = [1, 2, 3, 4, 5]; 1202 1203 dynamicArray.each!((ref x) => x++); 1204 assert(dynamicArray == [2, 3, 4, 5, 6]); 1205 1206 staticArray.each!((ref x) => x++); 1207 assert(staticArray == [2, 3, 4, 5, 6]); 1208 1209 staticArray[].each!((ref x) => x++); 1210 assert(staticArray == [3, 4, 5, 6, 7]); 1211 } 1212 1213 // https://issues.dlang.org/show_bug.cgi?id=16255 1214 // `each` on opApply doesn't support ref 1215 @system unittest 1216 { 1217 struct S 1218 { 1219 int x; 1220 int opApply(int delegate(ref int _x) dg) { return dg(x); } 1221 } 1222 1223 S s; 1224 foreach (ref a; s) ++a; 1225 assert(s.x == 1); 1226 s.each!"++a"; 1227 assert(s.x == 2); 1228 } 1229 1230 // https://issues.dlang.org/show_bug.cgi?id=15357 1231 // `each` should behave similar to foreach 1232 /// `each` works with iterable objects which provide an index variable, along with each element 1233 @safe unittest 1234 { 1235 import std.range : iota, lockstep; 1236 1237 auto arr = [1, 2, 3, 4]; 1238 1239 // 1 ref parameter 1240 arr.each!((ref e) => e = 0); 1241 assert(arr.sum == 0); 1242 1243 // 1 ref parameter and index 1244 arr.each!((i, ref e) => e = cast(int) i); 1245 assert(arr.sum == 4.iota.sum); 1246 } 1247 1248 // https://issues.dlang.org/show_bug.cgi?id=15357 1249 // `each` should behave similar to foreach 1250 @system unittest 1251 { 1252 import std.range : iota, lockstep; 1253 1254 // 2 ref parameters and index 1255 auto arrA = [1, 2, 3, 4]; 1256 auto arrB = [5, 6, 7, 8]; 1257 lockstep(arrA, arrB).each!((ref a, ref b) { 1258 a = 0; 1259 b = 1; 1260 }); 1261 assert(arrA.sum == 0); 1262 assert(arrB.sum == 4); 1263 1264 // 3 ref parameters 1265 auto arrC = [3, 3, 3, 3]; 1266 lockstep(arrA, arrB, arrC).each!((ref a, ref b, ref c) { 1267 a = 1; 1268 b = 2; 1269 c = 3; 1270 }); 1271 assert(arrA.sum == 4); 1272 assert(arrB.sum == 8); 1273 assert(arrC.sum == 12); 1274 } 1275 1276 // https://issues.dlang.org/show_bug.cgi?id=15357 1277 // `each` should behave similar to foreach 1278 @system unittest 1279 { 1280 import std.range : lockstep; 1281 import std.typecons : Tuple; 1282 1283 auto a = "abc"; 1284 auto b = "def"; 1285 1286 // print each character with an index 1287 { 1288 alias Element = Tuple!(size_t, "index", dchar, "value"); 1289 Element[] rForeach, rEach; 1290 foreach (i, c ; a) rForeach ~= Element(i, c); 1291 a.each!((i, c) => rEach ~= Element(i, c)); 1292 assert(rForeach == rEach); 1293 assert(rForeach == [Element(0, 'a'), Element(1, 'b'), Element(2, 'c')]); 1294 } 1295 1296 // print pairs of characters 1297 { 1298 alias Element = Tuple!(dchar, "a", dchar, "b"); 1299 Element[] rForeach, rEach; 1300 foreach (c1, c2 ; a.lockstep(b)) rForeach ~= Element(c1, c2); 1301 a.lockstep(b).each!((c1, c2) => rEach ~= Element(c1, c2)); 1302 assert(rForeach == rEach); 1303 assert(rForeach == [Element('a', 'd'), Element('b', 'e'), Element('c', 'f')]); 1304 } 1305 } 1306 1307 // filter 1308 /** 1309 Implements the higher order filter function. The predicate is passed to 1310 $(REF unaryFun, std,functional), and can either accept a string, or any callable 1311 that can be executed via `pred(element)`. 1312 1313 Params: 1314 predicate = Function to apply to each element of range 1315 1316 Returns: 1317 `filter!(predicate)(range)` returns a new range containing only elements `x` in `range` for 1318 which `predicate(x)` returns `true`. 1319 1320 See_Also: 1321 $(HTTP en.wikipedia.org/wiki/Filter_(higher-order_function), Filter (higher-order function)) 1322 */ 1323 template filter(alias predicate) 1324 if (is(typeof(unaryFun!predicate))) 1325 { 1326 /** 1327 Params: 1328 range = An $(REF_ALTTEXT input range, isInputRange, std,range,primitives) 1329 of elements 1330 Returns: 1331 A range containing only elements `x` in `range` for 1332 which `predicate(x)` returns `true`. 1333 */ 1334 auto filter(Range)(Range range) if (isInputRange!(Unqual!Range)) 1335 { 1336 return FilterResult!(unaryFun!predicate, Range)(range); 1337 } 1338 } 1339 1340 /// 1341 @safe unittest 1342 { 1343 import std.algorithm.comparison : equal; 1344 import std.math : approxEqual; 1345 import std.range; 1346 1347 int[] arr = [ 1, 2, 3, 4, 5 ]; 1348 1349 // Filter below 3 1350 auto small = filter!(a => a < 3)(arr); 1351 assert(equal(small, [ 1, 2 ])); 1352 1353 // Filter again, but with Uniform Function Call Syntax (UFCS) 1354 auto sum = arr.filter!(a => a < 3); 1355 assert(equal(sum, [ 1, 2 ])); 1356 1357 // In combination with chain() to span multiple ranges 1358 int[] a = [ 3, -2, 400 ]; 1359 int[] b = [ 100, -101, 102 ]; 1360 auto r = chain(a, b).filter!(a => a > 0); 1361 assert(equal(r, [ 3, 400, 100, 102 ])); 1362 1363 // Mixing convertible types is fair game, too 1364 double[] c = [ 2.5, 3.0 ]; 1365 auto r1 = chain(c, a, b).filter!(a => cast(int) a != a); 1366 assert(approxEqual(r1, [ 2.5 ])); 1367 } 1368 1369 private struct FilterResult(alias pred, Range) 1370 { 1371 alias R = Unqual!Range; 1372 R _input; 1373 private bool _primed; 1374 1375 private void prime() 1376 { 1377 if (_primed) return; 1378 while (!_input.empty && !pred(_input.front)) 1379 { 1380 _input.popFront(); 1381 } 1382 _primed = true; 1383 } 1384 1385 this(R r) 1386 { 1387 _input = r; 1388 } 1389 1390 private this(R r, bool primed) 1391 { 1392 _input = r; 1393 _primed = primed; 1394 } 1395 1396 auto opSlice() { return this; } 1397 1398 static if (isInfinite!Range) 1399 { 1400 enum bool empty = false; 1401 } 1402 else 1403 { 1404 @property bool empty() { prime; return _input.empty; } 1405 } 1406 1407 void popFront() 1408 { 1409 prime; 1410 do 1411 { 1412 _input.popFront(); 1413 } while (!_input.empty && !pred(_input.front)); 1414 } 1415 1416 @property auto ref front() 1417 { 1418 prime; 1419 assert(!empty, "Attempting to fetch the front of an empty filter."); 1420 return _input.front; 1421 } 1422 1423 static if (isForwardRange!R) 1424 { 1425 @property auto save() 1426 { 1427 return typeof(this)(_input.save, _primed); 1428 } 1429 } 1430 } 1431 1432 @safe unittest 1433 { 1434 import std.algorithm.comparison : equal; 1435 import std.internal.test.dummyrange; 1436 import std.range; 1437 1438 auto shouldNotLoop4ever = repeat(1).filter!(x => x % 2 == 0); 1439 static assert(isInfinite!(typeof(shouldNotLoop4ever))); 1440 assert(!shouldNotLoop4ever.empty); 1441 1442 int[] a = [ 3, 4, 2 ]; 1443 auto r = filter!("a > 3")(a); 1444 static assert(isForwardRange!(typeof(r))); 1445 assert(equal(r, [ 4 ][])); 1446 1447 a = [ 1, 22, 3, 42, 5 ]; 1448 auto under10 = filter!("a < 10")(a); 1449 assert(equal(under10, [1, 3, 5][])); 1450 static assert(isForwardRange!(typeof(under10))); 1451 under10.front = 4; 1452 assert(equal(under10, [4, 3, 5][])); 1453 under10.front = 40; 1454 assert(equal(under10, [40, 3, 5][])); 1455 under10.front = 1; 1456 1457 auto infinite = filter!"a > 2"(repeat(3)); 1458 static assert(isInfinite!(typeof(infinite))); 1459 static assert(isForwardRange!(typeof(infinite))); 1460 assert(infinite.front == 3); 1461 1462 foreach (DummyType; AllDummyRanges) 1463 { 1464 DummyType d; 1465 auto f = filter!"a & 1"(d); 1466 assert(equal(f, [1,3,5,7,9])); 1467 1468 static if (isForwardRange!DummyType) 1469 { 1470 static assert(isForwardRange!(typeof(f))); 1471 } 1472 } 1473 1474 // With delegates 1475 int x = 10; 1476 int overX(int a) { return a > x; } 1477 typeof(filter!overX(a)) getFilter() 1478 { 1479 return filter!overX(a); 1480 } 1481 auto r1 = getFilter(); 1482 assert(equal(r1, [22, 42])); 1483 1484 // With chain 1485 auto nums = [0,1,2,3,4]; 1486 assert(equal(filter!overX(chain(a, nums)), [22, 42])); 1487 1488 // With copying of inner struct Filter to Map 1489 auto arr = [1,2,3,4,5]; 1490 auto m = map!"a + 1"(filter!"a < 4"(arr)); 1491 assert(equal(m, [2, 3, 4])); 1492 } 1493 1494 @safe unittest 1495 { 1496 import std.algorithm.comparison : equal; 1497 1498 int[] a = [ 3, 4 ]; 1499 const aConst = a; 1500 auto r = filter!("a > 3")(aConst); 1501 assert(equal(r, [ 4 ][])); 1502 1503 a = [ 1, 22, 3, 42, 5 ]; 1504 auto under10 = filter!("a < 10")(a); 1505 assert(equal(under10, [1, 3, 5][])); 1506 assert(equal(under10.save, [1, 3, 5][])); 1507 assert(equal(under10.save, under10)); 1508 } 1509 1510 @safe unittest 1511 { 1512 import std.algorithm.comparison : equal; 1513 import std.functional : compose, pipe; 1514 1515 assert(equal(compose!(map!"2 * a", filter!"a & 1")([1,2,3,4,5]), 1516 [2,6,10])); 1517 assert(equal(pipe!(filter!"a & 1", map!"2 * a")([1,2,3,4,5]), 1518 [2,6,10])); 1519 } 1520 1521 @safe unittest 1522 { 1523 import std.algorithm.comparison : equal; 1524 1525 int x = 10; 1526 int underX(int a) { return a < x; } 1527 const(int)[] list = [ 1, 2, 10, 11, 3, 4 ]; 1528 assert(equal(filter!underX(list), [ 1, 2, 3, 4 ])); 1529 } 1530 1531 // https://issues.dlang.org/show_bug.cgi?id=19823 1532 @safe unittest 1533 { 1534 import std.algorithm.comparison : equal; 1535 import std.range : dropOne; 1536 1537 auto a = [1, 2, 3, 4]; 1538 assert(a.filter!(a => a != 1).dropOne.equal([3, 4])); 1539 assert(a.filter!(a => a != 2).dropOne.equal([3, 4])); 1540 assert(a.filter!(a => a != 3).dropOne.equal([2, 4])); 1541 assert(a.filter!(a => a != 4).dropOne.equal([2, 3])); 1542 assert(a.filter!(a => a == 1).dropOne.empty); 1543 assert(a.filter!(a => a == 2).dropOne.empty); 1544 assert(a.filter!(a => a == 3).dropOne.empty); 1545 assert(a.filter!(a => a == 4).dropOne.empty); 1546 } 1547 1548 /** 1549 * Similar to `filter`, except it defines a 1550 * $(REF_ALTTEXT bidirectional range, isBidirectionalRange, std,range,primitives). 1551 * There is a speed disadvantage - the constructor spends time 1552 * finding the last element in the range that satisfies the filtering 1553 * condition (in addition to finding the first one). The advantage is 1554 * that the filtered range can be spanned from both directions. Also, 1555 * $(REF retro, std,range) can be applied against the filtered range. 1556 * 1557 * The predicate is passed to $(REF unaryFun, std,functional), and can either 1558 * accept a string, or any callable that can be executed via `pred(element)`. 1559 * 1560 * Params: 1561 * pred = Function to apply to each element of range 1562 */ 1563 template filterBidirectional(alias pred) 1564 { 1565 /** 1566 Params: 1567 r = Bidirectional range of elements 1568 Returns: 1569 A range containing only the elements in `r` for which `pred` returns `true`. 1570 */ 1571 auto filterBidirectional(Range)(Range r) if (isBidirectionalRange!(Unqual!Range)) 1572 { 1573 return FilterBidiResult!(unaryFun!pred, Range)(r); 1574 } 1575 } 1576 1577 /// 1578 @safe unittest 1579 { 1580 import std.algorithm.comparison : equal; 1581 import std.range; 1582 1583 int[] arr = [ 1, 2, 3, 4, 5 ]; 1584 auto small = filterBidirectional!("a < 3")(arr); 1585 static assert(isBidirectionalRange!(typeof(small))); 1586 assert(small.back == 2); 1587 assert(equal(small, [ 1, 2 ])); 1588 assert(equal(retro(small), [ 2, 1 ])); 1589 // In combination with chain() to span multiple ranges 1590 int[] a = [ 3, -2, 400 ]; 1591 int[] b = [ 100, -101, 102 ]; 1592 auto r = filterBidirectional!("a > 0")(chain(a, b)); 1593 assert(r.back == 102); 1594 } 1595 1596 private struct FilterBidiResult(alias pred, Range) 1597 { 1598 alias R = Unqual!Range; 1599 R _input; 1600 1601 this(R r) 1602 { 1603 _input = r; 1604 while (!_input.empty && !pred(_input.front)) _input.popFront(); 1605 while (!_input.empty && !pred(_input.back)) _input.popBack(); 1606 } 1607 1608 @property bool empty() { return _input.empty; } 1609 1610 void popFront() 1611 { 1612 do 1613 { 1614 _input.popFront(); 1615 } while (!_input.empty && !pred(_input.front)); 1616 } 1617 1618 @property auto ref front() 1619 { 1620 assert(!empty, "Attempting to fetch the front of an empty filterBidirectional."); 1621 return _input.front; 1622 } 1623 1624 void popBack() 1625 { 1626 do 1627 { 1628 _input.popBack(); 1629 } while (!_input.empty && !pred(_input.back)); 1630 } 1631 1632 @property auto ref back() 1633 { 1634 assert(!empty, "Attempting to fetch the back of an empty filterBidirectional."); 1635 return _input.back; 1636 } 1637 1638 @property auto save() 1639 { 1640 return typeof(this)(_input.save); 1641 } 1642 } 1643 1644 /** 1645 Groups consecutively equivalent elements into a single tuple of the element and 1646 the number of its repetitions. 1647 1648 Similarly to `uniq`, `group` produces a range that iterates over unique 1649 consecutive elements of the given range. Each element of this range is a tuple 1650 of the element and the number of times it is repeated in the original range. 1651 Equivalence of elements is assessed by using the predicate `pred`, which 1652 defaults to `"a == b"`. The predicate is passed to $(REF binaryFun, std,functional), 1653 and can either accept a string, or any callable that can be executed via 1654 `pred(element, element)`. 1655 1656 Params: 1657 pred = Binary predicate for determining equivalence of two elements. 1658 R = The range type 1659 r = The $(REF_ALTTEXT input range, isInputRange, std,range,primitives) to 1660 iterate over. 1661 1662 Returns: A range of elements of type `Tuple!(ElementType!R, uint)`, 1663 representing each consecutively unique element and its respective number of 1664 occurrences in that run. This will be an input range if `R` is an input 1665 range, and a forward range in all other cases. 1666 1667 See_Also: $(LREF chunkBy), which chunks an input range into subranges 1668 of equivalent adjacent elements. 1669 */ 1670 Group!(pred, Range) group(alias pred = "a == b", Range)(Range r) 1671 { 1672 return typeof(return)(r); 1673 } 1674 1675 /// ditto 1676 struct Group(alias pred, R) 1677 if (isInputRange!R) 1678 { 1679 import std.typecons : Rebindable, tuple, Tuple; 1680 1681 private alias comp = binaryFun!pred; 1682 1683 private alias E = ElementType!R; 1684 static if ((is(E == class) || is(E == interface)) && 1685 (is(E == const) || is(E == immutable))) 1686 { 1687 private alias MutableE = Rebindable!E; 1688 } 1689 else static if (is(E : Unqual!E)) 1690 { 1691 private alias MutableE = Unqual!E; 1692 } 1693 else 1694 { 1695 private alias MutableE = E; 1696 } 1697 1698 private R _input; 1699 private Tuple!(MutableE, uint) _current; 1700 1701 /// 1702 this(R input) 1703 { 1704 _input = input; 1705 if (!_input.empty) popFront(); 1706 } 1707 1708 private this(R input, Tuple!(MutableE, uint) current) 1709 { 1710 _input = input; 1711 _current = current; 1712 } 1713 1714 /// 1715 void popFront() 1716 { 1717 if (_input.empty) 1718 { 1719 _current[1] = 0; 1720 } 1721 else 1722 { 1723 _current = tuple(_input.front, 1u); 1724 _input.popFront(); 1725 while (!_input.empty && comp(_current[0], _input.front)) 1726 { 1727 ++_current[1]; 1728 _input.popFront(); 1729 } 1730 } 1731 } 1732 1733 static if (isInfinite!R) 1734 { 1735 /// 1736 enum bool empty = false; // Propagate infiniteness. 1737 } 1738 else 1739 { 1740 /// 1741 @property bool empty() 1742 { 1743 return _current[1] == 0; 1744 } 1745 } 1746 1747 /// Returns: the front of the range 1748 @property auto ref front() 1749 { 1750 assert(!empty, "Attempting to fetch the front of an empty Group."); 1751 return _current; 1752 } 1753 1754 static if (isForwardRange!R) 1755 { 1756 /// 1757 @property typeof(this) save() 1758 { 1759 return Group(_input.save, _current); 1760 } 1761 } 1762 } 1763 1764 /// 1765 @safe unittest 1766 { 1767 import std.algorithm.comparison : equal; 1768 import std.typecons : tuple, Tuple; 1769 1770 int[] arr = [ 1, 2, 2, 2, 2, 3, 4, 4, 4, 5 ]; 1771 assert(equal(group(arr), [ tuple(1, 1u), tuple(2, 4u), tuple(3, 1u), 1772 tuple(4, 3u), tuple(5, 1u) ][])); 1773 } 1774 1775 /** 1776 * Using group, an associative array can be easily generated with the count of each 1777 * unique element in the range. 1778 */ 1779 @safe unittest 1780 { 1781 import std.algorithm.sorting : sort; 1782 import std.array : assocArray; 1783 1784 uint[string] result; 1785 auto range = ["a", "b", "a", "c", "b", "c", "c", "d", "e"]; 1786 result = range.sort!((a, b) => a < b) 1787 .group 1788 .assocArray; 1789 1790 assert(result == ["a": 2U, "b": 2U, "c": 3U, "d": 1U, "e": 1U]); 1791 } 1792 1793 @safe unittest 1794 { 1795 import std.algorithm.comparison : equal; 1796 import std.internal.test.dummyrange; 1797 import std.typecons : tuple, Tuple; 1798 1799 int[] arr = [ 1, 2, 2, 2, 2, 3, 4, 4, 4, 5 ]; 1800 assert(equal(group(arr), [ tuple(1, 1u), tuple(2, 4u), tuple(3, 1u), 1801 tuple(4, 3u), tuple(5, 1u) ][])); 1802 static assert(isForwardRange!(typeof(group(arr)))); 1803 1804 foreach (DummyType; AllDummyRanges) 1805 { 1806 DummyType d; 1807 auto g = group(d); 1808 1809 static assert(d.rt == RangeType.Input || isForwardRange!(typeof(g))); 1810 1811 assert(equal(g, [tuple(1, 1u), tuple(2, 1u), tuple(3, 1u), tuple(4, 1u), 1812 tuple(5, 1u), tuple(6, 1u), tuple(7, 1u), tuple(8, 1u), 1813 tuple(9, 1u), tuple(10, 1u)])); 1814 } 1815 } 1816 1817 @safe unittest 1818 { 1819 import std.algorithm.comparison : equal; 1820 import std.typecons : tuple; 1821 1822 // https://issues.dlang.org/show_bug.cgi?id=13857 1823 immutable(int)[] a1 = [1,1,2,2,2,3,4,4,5,6,6,7,8,9,9,9]; 1824 auto g1 = group(a1); 1825 assert(equal(g1, [ tuple(1, 2u), tuple(2, 3u), tuple(3, 1u), 1826 tuple(4, 2u), tuple(5, 1u), tuple(6, 2u), 1827 tuple(7, 1u), tuple(8, 1u), tuple(9, 3u) 1828 ])); 1829 1830 // https://issues.dlang.org/show_bug.cgi?id=13162 1831 immutable(ubyte)[] a2 = [1, 1, 1, 0, 0, 0]; 1832 auto g2 = a2.group; 1833 assert(equal(g2, [ tuple(1, 3u), tuple(0, 3u) ])); 1834 1835 // https://issues.dlang.org/show_bug.cgi?id=10104 1836 const a3 = [1, 1, 2, 2]; 1837 auto g3 = a3.group; 1838 assert(equal(g3, [ tuple(1, 2u), tuple(2, 2u) ])); 1839 1840 interface I {} 1841 class C : I { override size_t toHash() const nothrow @safe { return 0; } } 1842 const C[] a4 = [new const C()]; 1843 auto g4 = a4.group!"a is b"; 1844 assert(g4.front[1] == 1); 1845 1846 immutable I[] a5 = [new immutable C()]; 1847 auto g5 = a5.group!"a is b"; 1848 assert(g5.front[1] == 1); 1849 1850 const(int[][]) a6 = [[1], [1]]; 1851 auto g6 = a6.group; 1852 assert(equal(g6.front[0], [1])); 1853 } 1854 1855 @safe unittest 1856 { 1857 import std.algorithm.comparison : equal; 1858 import std.typecons : tuple; 1859 1860 int[] arr = [ 1, 2, 2, 2, 2, 3, 4, 4, 4, 5 ]; 1861 auto r = arr.group; 1862 assert(r.equal([ tuple(1,1u), tuple(2, 4u), tuple(3, 1u), tuple(4, 3u), tuple(5, 1u) ])); 1863 r.popFront; 1864 assert(r.equal([ tuple(2, 4u), tuple(3, 1u), tuple(4, 3u), tuple(5, 1u) ])); 1865 auto s = r.save; 1866 r.popFrontN(2); 1867 assert(r.equal([ tuple(4, 3u), tuple(5, 1u) ])); 1868 assert(s.equal([ tuple(2, 4u), tuple(3, 1u), tuple(4, 3u), tuple(5, 1u) ])); 1869 s.popFront; 1870 auto t = s.save; 1871 r.popFront; 1872 s.popFront; 1873 assert(r.equal([ tuple(5, 1u) ])); 1874 assert(s.equal([ tuple(4, 3u), tuple(5, 1u) ])); 1875 assert(t.equal([ tuple(3, 1u), tuple(4, 3u), tuple(5, 1u) ])); 1876 } 1877 1878 // https://issues.dlang.org/show_bug.cgi?id=18657 1879 pure @safe unittest 1880 { 1881 import std.algorithm.comparison : equal; 1882 import std.range : refRange; 1883 string s = "foo"; 1884 auto r = refRange(&s).group; 1885 assert(equal(r.save, "foo".group)); 1886 assert(equal(r, "foo".group)); 1887 } 1888 1889 // Used by implementation of chunkBy for non-forward input ranges. 1890 private struct ChunkByChunkImpl(alias pred, Range) 1891 if (isInputRange!Range && !isForwardRange!Range) 1892 { 1893 alias fun = binaryFun!pred; 1894 1895 private Range *r; 1896 private ElementType!Range prev; 1897 1898 this(ref Range range, ElementType!Range _prev) 1899 { 1900 r = ⦥ 1901 prev = _prev; 1902 } 1903 1904 @property bool empty() 1905 { 1906 return r.empty || !fun(prev, r.front); 1907 } 1908 1909 @property ElementType!Range front() 1910 { 1911 assert(!empty, "Attempting to fetch the front of an empty chunkBy chunk."); 1912 return r.front; 1913 } 1914 1915 void popFront() 1916 { 1917 assert(!empty, "Attempting to popFront an empty chunkBy chunk."); 1918 r.popFront(); 1919 } 1920 } 1921 1922 private template ChunkByImplIsUnary(alias pred, Range) 1923 { 1924 alias e = lvalueOf!(ElementType!Range); 1925 1926 static if (is(typeof(binaryFun!pred(e, e)) : bool)) 1927 enum ChunkByImplIsUnary = false; 1928 else static if (is(typeof(unaryFun!pred(e) == unaryFun!pred(e)) : bool)) 1929 enum ChunkByImplIsUnary = true; 1930 else 1931 static assert(0, "chunkBy expects either a binary predicate or "~ 1932 "a unary predicate on range elements of type: "~ 1933 ElementType!Range.stringof); 1934 } 1935 1936 // Implementation of chunkBy for non-forward input ranges. 1937 private struct ChunkByImpl(alias pred, Range) 1938 if (isInputRange!Range && !isForwardRange!Range) 1939 { 1940 enum bool isUnary = ChunkByImplIsUnary!(pred, Range); 1941 1942 static if (isUnary) 1943 alias eq = binaryFun!((a, b) => unaryFun!pred(a) == unaryFun!pred(b)); 1944 else 1945 alias eq = binaryFun!pred; 1946 1947 private Range r; 1948 private ElementType!Range _prev; 1949 private bool openChunk = false; 1950 1951 this(Range _r) 1952 { 1953 r = _r; 1954 if (!empty) 1955 { 1956 // Check reflexivity if predicate is claimed to be an equivalence 1957 // relation. 1958 assert(eq(r.front, r.front), 1959 "predicate is not reflexive"); 1960 1961 // _prev's type may be a nested struct, so must be initialized 1962 // directly in the constructor (cannot call savePred()). 1963 _prev = r.front; 1964 } 1965 else 1966 { 1967 // We won't use _prev, but must be initialized. 1968 _prev = typeof(_prev).init; 1969 } 1970 } 1971 @property bool empty() { return r.empty && !openChunk; } 1972 1973 @property auto front() 1974 { 1975 assert(!empty, "Attempting to fetch the front of an empty chunkBy."); 1976 openChunk = true; 1977 static if (isUnary) 1978 { 1979 import std.typecons : tuple; 1980 return tuple(unaryFun!pred(_prev), 1981 ChunkByChunkImpl!(eq, Range)(r, _prev)); 1982 } 1983 else 1984 { 1985 return ChunkByChunkImpl!(eq, Range)(r, _prev); 1986 } 1987 } 1988 1989 void popFront() 1990 { 1991 assert(!empty, "Attempting to popFront an empty chunkBy."); 1992 openChunk = false; 1993 while (!r.empty) 1994 { 1995 if (!eq(_prev, r.front)) 1996 { 1997 _prev = r.front; 1998 break; 1999 } 2000 r.popFront(); 2001 } 2002 } 2003 } 2004 2005 // Single-pass implementation of chunkBy for forward ranges. 2006 private struct ChunkByImpl(alias pred, Range) 2007 if (isForwardRange!Range) 2008 { 2009 import std.typecons : RefCounted; 2010 2011 enum bool isUnary = ChunkByImplIsUnary!(pred, Range); 2012 2013 static if (isUnary) 2014 alias eq = binaryFun!((a, b) => unaryFun!pred(a) == unaryFun!pred(b)); 2015 else 2016 alias eq = binaryFun!pred; 2017 2018 // Outer range 2019 static struct Impl 2020 { 2021 size_t groupNum; 2022 Range current; 2023 Range next; 2024 } 2025 2026 // Inner range 2027 static struct Group 2028 { 2029 private size_t groupNum; 2030 private Range start; 2031 private Range current; 2032 2033 private RefCounted!Impl mothership; 2034 2035 this(RefCounted!Impl origin) 2036 { 2037 groupNum = origin.groupNum; 2038 2039 start = origin.current.save; 2040 current = origin.current.save; 2041 assert(!start.empty, "Passed range 'r' must not be empty"); 2042 2043 mothership = origin; 2044 2045 // Note: this requires reflexivity. 2046 assert(eq(start.front, current.front), 2047 "predicate is not reflexive"); 2048 } 2049 2050 @property bool empty() { return groupNum == size_t.max; } 2051 @property auto ref front() { return current.front; } 2052 2053 void popFront() 2054 { 2055 current.popFront(); 2056 2057 // Note: this requires transitivity. 2058 if (current.empty || !eq(start.front, current.front)) 2059 { 2060 if (groupNum == mothership.groupNum) 2061 { 2062 // If parent range hasn't moved on yet, help it along by 2063 // saving location of start of next Group. 2064 mothership.next = current.save; 2065 } 2066 2067 groupNum = size_t.max; 2068 } 2069 } 2070 2071 @property auto save() 2072 { 2073 auto copy = this; 2074 copy.current = current.save; 2075 return copy; 2076 } 2077 } 2078 static assert(isForwardRange!Group); 2079 2080 private RefCounted!Impl impl; 2081 2082 this(Range r) 2083 { 2084 impl = RefCounted!Impl(0, r, r.save); 2085 } 2086 2087 @property bool empty() { return impl.current.empty; } 2088 2089 @property auto front() 2090 { 2091 static if (isUnary) 2092 { 2093 import std.typecons : tuple; 2094 return tuple(unaryFun!pred(impl.current.front), Group(impl)); 2095 } 2096 else 2097 { 2098 return Group(impl); 2099 } 2100 } 2101 2102 void popFront() 2103 { 2104 // Scan for next group. If we're lucky, one of our Groups would have 2105 // already set .next to the start of the next group, in which case the 2106 // loop is skipped. 2107 while (!impl.next.empty && eq(impl.current.front, impl.next.front)) 2108 { 2109 impl.next.popFront(); 2110 } 2111 2112 impl.current = impl.next.save; 2113 2114 // Indicate to any remaining Groups that we have moved on. 2115 impl.groupNum++; 2116 } 2117 2118 @property auto save() 2119 { 2120 // Note: the new copy of the range will be detached from any existing 2121 // satellite Groups, and will not benefit from the .next acceleration. 2122 return typeof(this)(impl.current.save); 2123 } 2124 2125 static assert(isForwardRange!(typeof(this)), typeof(this).stringof 2126 ~ " must be a forward range"); 2127 } 2128 2129 @system unittest 2130 { 2131 import std.algorithm.comparison : equal; 2132 2133 size_t popCount = 0; 2134 class RefFwdRange 2135 { 2136 int[] impl; 2137 2138 @safe nothrow: 2139 2140 this(int[] data) { impl = data; } 2141 @property bool empty() { return impl.empty; } 2142 @property auto ref front() { return impl.front; } 2143 void popFront() 2144 { 2145 impl.popFront(); 2146 popCount++; 2147 } 2148 @property auto save() { return new RefFwdRange(impl); } 2149 } 2150 static assert(isForwardRange!RefFwdRange); 2151 2152 auto testdata = new RefFwdRange([1, 3, 5, 2, 4, 7, 6, 8, 9]); 2153 auto groups = testdata.chunkBy!((a,b) => (a % 2) == (b % 2)); 2154 auto outerSave1 = groups.save; 2155 2156 // Sanity test 2157 assert(groups.equal!equal([[1, 3, 5], [2, 4], [7], [6, 8], [9]])); 2158 assert(groups.empty); 2159 2160 // Performance test for single-traversal use case: popFront should not have 2161 // been called more times than there are elements if we traversed the 2162 // segmented range exactly once. 2163 assert(popCount == 9); 2164 2165 // Outer range .save test 2166 groups = outerSave1.save; 2167 assert(!groups.empty); 2168 2169 // Inner range .save test 2170 auto grp1 = groups.front.save; 2171 auto grp1b = grp1.save; 2172 assert(grp1b.equal([1, 3, 5])); 2173 assert(grp1.save.equal([1, 3, 5])); 2174 2175 // Inner range should remain consistent after outer range has moved on. 2176 groups.popFront(); 2177 assert(grp1.save.equal([1, 3, 5])); 2178 2179 // Inner range should not be affected by subsequent inner ranges. 2180 assert(groups.front.equal([2, 4])); 2181 assert(grp1.save.equal([1, 3, 5])); 2182 } 2183 2184 /** 2185 * Chunks an input range into subranges of equivalent adjacent elements. 2186 * In other languages this is often called `partitionBy`, `groupBy` 2187 * or `sliceWhen`. 2188 * 2189 * Equivalence is defined by the predicate `pred`, which can be either 2190 * binary, which is passed to $(REF binaryFun, std,functional), or unary, which is 2191 * passed to $(REF unaryFun, std,functional). In the binary form, two range elements 2192 * `a` and `b` are considered equivalent if `pred(a,b)` is true. In 2193 * unary form, two elements are considered equivalent if `pred(a) == pred(b)` 2194 * is true. 2195 * 2196 * This predicate must be an equivalence relation, that is, it must be 2197 * reflexive (`pred(x,x)` is always true), symmetric 2198 * (`pred(x,y) == pred(y,x)`), and transitive (`pred(x,y) && pred(y,z)` 2199 * implies `pred(x,z)`). If this is not the case, the range returned by 2200 * chunkBy may assert at runtime or behave erratically. 2201 * 2202 * Params: 2203 * pred = Predicate for determining equivalence. 2204 * r = An $(REF_ALTTEXT input range, isInputRange, std,range,primitives) to be chunked. 2205 * 2206 * Returns: With a binary predicate, a range of ranges is returned in which 2207 * all elements in a given subrange are equivalent under the given predicate. 2208 * With a unary predicate, a range of tuples is returned, with the tuple 2209 * consisting of the result of the unary predicate for each subrange, and the 2210 * subrange itself. 2211 * 2212 * Notes: 2213 * 2214 * Equivalent elements separated by an intervening non-equivalent element will 2215 * appear in separate subranges; this function only considers adjacent 2216 * equivalence. Elements in the subranges will always appear in the same order 2217 * they appear in the original range. 2218 * 2219 * See_also: 2220 * $(LREF group), which collapses adjacent equivalent elements into a single 2221 * element. 2222 */ 2223 auto chunkBy(alias pred, Range)(Range r) 2224 if (isInputRange!Range) 2225 { 2226 return ChunkByImpl!(pred, Range)(r); 2227 } 2228 2229 /// Showing usage with binary predicate: 2230 /*FIXME: @safe*/ @system unittest 2231 { 2232 import std.algorithm.comparison : equal; 2233 2234 // Grouping by particular attribute of each element: 2235 auto data = [ 2236 [1, 1], 2237 [1, 2], 2238 [2, 2], 2239 [2, 3] 2240 ]; 2241 2242 auto r1 = data.chunkBy!((a,b) => a[0] == b[0]); 2243 assert(r1.equal!equal([ 2244 [[1, 1], [1, 2]], 2245 [[2, 2], [2, 3]] 2246 ])); 2247 2248 auto r2 = data.chunkBy!((a,b) => a[1] == b[1]); 2249 assert(r2.equal!equal([ 2250 [[1, 1]], 2251 [[1, 2], [2, 2]], 2252 [[2, 3]] 2253 ])); 2254 } 2255 2256 version (none) // this example requires support for non-equivalence relations 2257 @safe unittest 2258 { 2259 // Grouping by maximum adjacent difference: 2260 import std.math : abs; 2261 auto r3 = [1, 3, 2, 5, 4, 9, 10].chunkBy!((a, b) => abs(a-b) < 3); 2262 assert(r3.equal!equal([ 2263 [1, 3, 2], 2264 [5, 4], 2265 [9, 10] 2266 ])); 2267 2268 } 2269 2270 /// Showing usage with unary predicate: 2271 /* FIXME: pure @safe nothrow*/ @system unittest 2272 { 2273 import std.algorithm.comparison : equal; 2274 import std.range.primitives; 2275 import std.typecons : tuple; 2276 2277 // Grouping by particular attribute of each element: 2278 auto range = 2279 [ 2280 [1, 1], 2281 [1, 1], 2282 [1, 2], 2283 [2, 2], 2284 [2, 3], 2285 [2, 3], 2286 [3, 3] 2287 ]; 2288 2289 auto byX = chunkBy!(a => a[0])(range); 2290 auto expected1 = 2291 [ 2292 tuple(1, [[1, 1], [1, 1], [1, 2]]), 2293 tuple(2, [[2, 2], [2, 3], [2, 3]]), 2294 tuple(3, [[3, 3]]) 2295 ]; 2296 foreach (e; byX) 2297 { 2298 assert(!expected1.empty); 2299 assert(e[0] == expected1.front[0]); 2300 assert(e[1].equal(expected1.front[1])); 2301 expected1.popFront(); 2302 } 2303 2304 auto byY = chunkBy!(a => a[1])(range); 2305 auto expected2 = 2306 [ 2307 tuple(1, [[1, 1], [1, 1]]), 2308 tuple(2, [[1, 2], [2, 2]]), 2309 tuple(3, [[2, 3], [2, 3], [3, 3]]) 2310 ]; 2311 foreach (e; byY) 2312 { 2313 assert(!expected2.empty); 2314 assert(e[0] == expected2.front[0]); 2315 assert(e[1].equal(expected2.front[1])); 2316 expected2.popFront(); 2317 } 2318 } 2319 2320 /*FIXME: pure @safe nothrow*/ @system unittest 2321 { 2322 import std.algorithm.comparison : equal; 2323 import std.typecons : tuple; 2324 2325 struct Item { int x, y; } 2326 2327 // Force R to have only an input range API with reference semantics, so 2328 // that we're not unknowingly making use of array semantics outside of the 2329 // range API. 2330 class RefInputRange(R) 2331 { 2332 R data; 2333 this(R _data) pure @safe nothrow { data = _data; } 2334 @property bool empty() pure @safe nothrow { return data.empty; } 2335 @property auto front() pure @safe nothrow { assert(!empty); return data.front; } 2336 void popFront() pure @safe nothrow { assert(!empty); data.popFront(); } 2337 } 2338 auto refInputRange(R)(R range) { return new RefInputRange!R(range); } 2339 2340 // An input range API with value semantics. 2341 struct ValInputRange(R) 2342 { 2343 R data; 2344 this(R _data) pure @safe nothrow { data = _data; } 2345 @property bool empty() pure @safe nothrow { return data.empty; } 2346 @property auto front() pure @safe nothrow { assert(!empty); return data.front; } 2347 void popFront() pure @safe nothrow { assert(!empty); data.popFront(); } 2348 } 2349 auto valInputRange(R)(R range) { return ValInputRange!R(range); } 2350 2351 { 2352 auto arr = [ Item(1,2), Item(1,3), Item(2,3) ]; 2353 static assert(isForwardRange!(typeof(arr))); 2354 2355 auto byX = chunkBy!(a => a.x)(arr); 2356 static assert(isForwardRange!(typeof(byX))); 2357 2358 auto byX_subrange1 = byX.front[1].save; 2359 auto byX_subrange2 = byX.front[1].save; 2360 static assert(isForwardRange!(typeof(byX_subrange1))); 2361 static assert(isForwardRange!(typeof(byX_subrange2))); 2362 2363 byX.popFront(); 2364 assert(byX_subrange1.equal([ Item(1,2), Item(1,3) ])); 2365 byX_subrange1.popFront(); 2366 assert(byX_subrange1.equal([ Item(1,3) ])); 2367 assert(byX_subrange2.equal([ Item(1,2), Item(1,3) ])); 2368 2369 auto byY = chunkBy!(a => a.y)(arr); 2370 static assert(isForwardRange!(typeof(byY))); 2371 2372 auto byY2 = byY.save; 2373 static assert(is(typeof(byY) == typeof(byY2))); 2374 byY.popFront(); 2375 assert(byY.front[0] == 3); 2376 assert(byY.front[1].equal([ Item(1,3), Item(2,3) ])); 2377 assert(byY2.front[0] == 2); 2378 assert(byY2.front[1].equal([ Item(1,2) ])); 2379 } 2380 2381 // Test non-forward input ranges with reference semantics. 2382 { 2383 auto range = refInputRange([ Item(1,1), Item(1,2), Item(2,2) ]); 2384 auto byX = chunkBy!(a => a.x)(range); 2385 assert(byX.front[0] == 1); 2386 assert(byX.front[1].equal([ Item(1,1), Item(1,2) ])); 2387 byX.popFront(); 2388 assert(byX.front[0] == 2); 2389 assert(byX.front[1].equal([ Item(2,2) ])); 2390 byX.popFront(); 2391 assert(byX.empty); 2392 assert(range.empty); 2393 2394 range = refInputRange([ Item(1,1), Item(1,2), Item(2,2) ]); 2395 auto byY = chunkBy!(a => a.y)(range); 2396 assert(byY.front[0] == 1); 2397 assert(byY.front[1].equal([ Item(1,1) ])); 2398 byY.popFront(); 2399 assert(byY.front[0] == 2); 2400 assert(byY.front[1].equal([ Item(1,2), Item(2,2) ])); 2401 byY.popFront(); 2402 assert(byY.empty); 2403 assert(range.empty); 2404 } 2405 2406 // Test non-forward input ranges with value semantics. 2407 { 2408 auto range = valInputRange([ Item(1,1), Item(1,2), Item(2,2) ]); 2409 auto byX = chunkBy!(a => a.x)(range); 2410 assert(byX.front[0] == 1); 2411 assert(byX.front[1].equal([ Item(1,1), Item(1,2) ])); 2412 byX.popFront(); 2413 assert(byX.front[0] == 2); 2414 assert(byX.front[1].equal([ Item(2,2) ])); 2415 byX.popFront(); 2416 assert(byX.empty); 2417 assert(!range.empty); // Opposite of refInputRange test 2418 2419 range = valInputRange([ Item(1,1), Item(1,2), Item(2,2) ]); 2420 auto byY = chunkBy!(a => a.y)(range); 2421 assert(byY.front[0] == 1); 2422 assert(byY.front[1].equal([ Item(1,1) ])); 2423 byY.popFront(); 2424 assert(byY.front[0] == 2); 2425 assert(byY.front[1].equal([ Item(1,2), Item(2,2) ])); 2426 byY.popFront(); 2427 assert(byY.empty); 2428 assert(!range.empty); // Opposite of refInputRange test 2429 } 2430 2431 /* https://issues.dlang.org/show_bug.cgi?id=19532 2432 * General behavior of non-forward input ranges. 2433 * 2434 * - If the same chunk is retrieved multiple times via front, the separate chunk 2435 * instances refer to a shared range segment that advances as a single range. 2436 * - Emptying a chunk via popFront does not implicitly popFront the chunk off 2437 * main range. The chunk is still available via front, it is just empty. 2438 */ 2439 { 2440 import std.algorithm.comparison : equal; 2441 import core.exception : AssertError; 2442 import std.exception : assertThrown; 2443 2444 auto a = [[0, 0], [0, 1], 2445 [1, 2], [1, 3], [1, 4], 2446 [2, 5], [2, 6], 2447 [3, 7], 2448 [4, 8]]; 2449 2450 // Value input range 2451 { 2452 auto r = valInputRange(a).chunkBy!((a, b) => a[0] == b[0]); 2453 2454 size_t numChunks = 0; 2455 while (!r.empty) 2456 { 2457 ++numChunks; 2458 auto chunk = r.front; 2459 while (!chunk.empty) 2460 { 2461 assert(r.front.front[1] == chunk.front[1]); 2462 chunk.popFront; 2463 } 2464 assert(!r.empty); 2465 assert(r.front.empty); 2466 r.popFront; 2467 } 2468 2469 assert(numChunks == 5); 2470 2471 // Now front and popFront should assert. 2472 bool thrown = false; 2473 try r.front; 2474 catch (AssertError) thrown = true; 2475 assert(thrown); 2476 2477 thrown = false; 2478 try r.popFront; 2479 catch (AssertError) thrown = true; 2480 assert(thrown); 2481 } 2482 2483 // Reference input range 2484 { 2485 auto r = refInputRange(a).chunkBy!((a, b) => a[0] == b[0]); 2486 2487 size_t numChunks = 0; 2488 while (!r.empty) 2489 { 2490 ++numChunks; 2491 auto chunk = r.front; 2492 while (!chunk.empty) 2493 { 2494 assert(r.front.front[1] == chunk.front[1]); 2495 chunk.popFront; 2496 } 2497 assert(!r.empty); 2498 assert(r.front.empty); 2499 r.popFront; 2500 } 2501 2502 assert(numChunks == 5); 2503 2504 // Now front and popFront should assert. 2505 bool thrown = false; 2506 try r.front; 2507 catch (AssertError) thrown = true; 2508 assert(thrown); 2509 2510 thrown = false; 2511 try r.popFront; 2512 catch (AssertError) thrown = true; 2513 assert(thrown); 2514 } 2515 2516 // Ensure that starting with an empty range doesn't create an empty chunk. 2517 { 2518 int[] emptyRange = []; 2519 2520 auto r1 = valInputRange(emptyRange).chunkBy!((a, b) => a == b); 2521 auto r2 = refInputRange(emptyRange).chunkBy!((a, b) => a == b); 2522 2523 assert(r1.empty); 2524 assert(r2.empty); 2525 2526 bool thrown = false; 2527 try r1.front; 2528 catch (AssertError) thrown = true; 2529 assert(thrown); 2530 2531 thrown = false; 2532 try r1.popFront; 2533 catch (AssertError) thrown = true; 2534 assert(thrown); 2535 2536 thrown = false; 2537 try r2.front; 2538 catch (AssertError) thrown = true; 2539 assert(thrown); 2540 2541 thrown = false; 2542 try r2.popFront; 2543 catch (AssertError) thrown = true; 2544 assert(thrown); 2545 } 2546 } 2547 2548 // https://issues.dlang.org/show_bug.cgi?id=19532 - Using roundRobin/chunkBy 2549 { 2550 import std.algorithm.comparison : equal; 2551 import std.range : roundRobin; 2552 2553 auto a0 = [0, 1, 3, 6]; 2554 auto a1 = [0, 2, 4, 6, 7]; 2555 auto a2 = [1, 2, 4, 6, 8, 8, 9]; 2556 2557 auto expected = 2558 [[0, 0], [1, 1], [2, 2], [3], [4, 4], [6, 6, 6], [7], [8, 8], [9]]; 2559 2560 auto r1 = roundRobin(valInputRange(a0), valInputRange(a1), valInputRange(a2)) 2561 .chunkBy!((a, b) => a == b); 2562 assert(r1.equal!equal(expected)); 2563 2564 auto r2 = roundRobin(refInputRange(a0), refInputRange(a1), refInputRange(a2)) 2565 .chunkBy!((a, b) => a == b); 2566 assert(r2.equal!equal(expected)); 2567 2568 auto r3 = roundRobin(a0, a1, a2).chunkBy!((a, b) => a == b); 2569 assert(r3.equal!equal(expected)); 2570 } 2571 2572 // https://issues.dlang.org/show_bug.cgi?id=19532 - Using merge/chunkBy 2573 { 2574 import std.algorithm.comparison : equal; 2575 import std.algorithm.sorting : merge; 2576 2577 auto a0 = [2, 3, 5]; 2578 auto a1 = [2, 4, 5]; 2579 auto a2 = [1, 2, 4, 5]; 2580 2581 auto expected = [[1], [2, 2, 2], [3], [4, 4], [5, 5, 5]]; 2582 2583 auto r1 = merge(valInputRange(a0), valInputRange(a1), valInputRange(a2)) 2584 .chunkBy!((a, b) => a == b); 2585 assert(r1.equal!equal(expected)); 2586 2587 auto r2 = merge(refInputRange(a0), refInputRange(a1), refInputRange(a2)) 2588 .chunkBy!((a, b) => a == b); 2589 assert(r2.equal!equal(expected)); 2590 2591 auto r3 = merge(a0, a1, a2).chunkBy!((a, b) => a == b); 2592 assert(r3.equal!equal(expected)); 2593 } 2594 2595 // https://issues.dlang.org/show_bug.cgi?id=19532 - Using chunkBy/map-fold 2596 { 2597 import std.algorithm.comparison : equal; 2598 import std.algorithm.iteration : fold, map; 2599 2600 auto a = [0, 0, 1, 1, 1, 2, 2, 3, 3, 4, 4, 5, 6, 6, 6, 7, 8, 8, 9]; 2601 auto expected = [0, 3, 4, 6, 8, 5, 18, 7, 16, 9]; 2602 2603 auto r1 = a 2604 .chunkBy!((a, b) => a == b) 2605 .map!(c => c.fold!((a, b) => a + b)); 2606 assert(r1.equal(expected)); 2607 2608 auto r2 = valInputRange(a) 2609 .chunkBy!((a, b) => a == b) 2610 .map!(c => c.fold!((a, b) => a + b)); 2611 assert(r2.equal(expected)); 2612 2613 auto r3 = refInputRange(a) 2614 .chunkBy!((a, b) => a == b) 2615 .map!(c => c.fold!((a, b) => a + b)); 2616 assert(r3.equal(expected)); 2617 } 2618 2619 // https://issues.dlang.org/show_bug.cgi?id=16169 2620 // https://issues.dlang.org/show_bug.cgi?id=17966 2621 // https://issues.dlang.org/show_bug.cgi?id=19532 2622 // Using multiwayMerge/chunkBy 2623 { 2624 import std.algorithm.comparison : equal; 2625 import std.algorithm.setops : multiwayMerge; 2626 2627 { 2628 auto a0 = [2, 3, 5]; 2629 auto a1 = [2, 4, 5]; 2630 auto a2 = [1, 2, 4, 5]; 2631 2632 auto expected = [[1], [2, 2, 2], [3], [4, 4], [5, 5, 5]]; 2633 auto r = multiwayMerge([a0, a1, a2]).chunkBy!((a, b) => a == b); 2634 assert(r.equal!equal(expected)); 2635 } 2636 { 2637 auto a0 = [2, 3, 5]; 2638 auto a1 = [2, 4, 5]; 2639 auto a2 = [1, 2, 4, 5]; 2640 2641 auto expected = [[1], [2, 2, 2], [3], [4, 4], [5, 5, 5]]; 2642 auto r = 2643 multiwayMerge([valInputRange(a0), valInputRange(a1), valInputRange(a2)]) 2644 .chunkBy!((a, b) => a == b); 2645 assert(r.equal!equal(expected)); 2646 } 2647 { 2648 auto a0 = [2, 3, 5]; 2649 auto a1 = [2, 4, 5]; 2650 auto a2 = [1, 2, 4, 5]; 2651 2652 auto expected = [[1], [2, 2, 2], [3], [4, 4], [5, 5, 5]]; 2653 auto r = 2654 multiwayMerge([refInputRange(a0), refInputRange(a1), refInputRange(a2)]) 2655 .chunkBy!((a, b) => a == b); 2656 assert(r.equal!equal(expected)); 2657 } 2658 } 2659 2660 // https://issues.dlang.org/show_bug.cgi?id=20496 2661 { 2662 auto r = [1,1,1,2,2,2,3,3,3]; 2663 r.chunkBy!((ref e1, ref e2) => e1 == e2); 2664 } 2665 } 2666 2667 // https://issues.dlang.org/show_bug.cgi?id=13595 2668 version (none) // This requires support for non-equivalence relations 2669 @system unittest 2670 { 2671 import std.algorithm.comparison : equal; 2672 auto r = [1, 2, 3, 4, 5, 6, 7, 8, 9].chunkBy!((x, y) => ((x*y) % 3) == 0); 2673 assert(r.equal!equal([ 2674 [1], 2675 [2, 3, 4], 2676 [5, 6, 7], 2677 [8, 9] 2678 ])); 2679 } 2680 2681 // https://issues.dlang.org/show_bug.cgi?id=13805 2682 @system unittest 2683 { 2684 [""].map!((s) => s).chunkBy!((x, y) => true); 2685 } 2686 2687 // joiner 2688 /** 2689 Lazily joins a range of ranges with a separator. The separator itself 2690 is a range. If a separator is not provided, then the ranges are 2691 joined directly without anything in between them (often called `flatten` 2692 in other languages). 2693 2694 Params: 2695 r = An $(REF_ALTTEXT input range, isInputRange, std,range,primitives) of input 2696 ranges to be joined. 2697 sep = A $(REF_ALTTEXT forward range, isForwardRange, std,range,primitives) of 2698 element(s) to serve as separators in the joined range. 2699 2700 Returns: 2701 A range of elements in the joined range. This will be a forward range if 2702 both outer and inner ranges of `RoR` are forward ranges; otherwise it will 2703 be only an input range. The 2704 $(REF_ALTTEXT range bidirectionality, isBidirectionalRange, std,range,primitives) 2705 is propagated if no separator is specified. 2706 2707 See_also: 2708 $(REF chain, std,range), which chains a sequence of ranges with compatible elements 2709 into a single range. 2710 */ 2711 auto joiner(RoR, Separator)(RoR r, Separator sep) 2712 if (isInputRange!RoR && isInputRange!(ElementType!RoR) 2713 && isForwardRange!Separator 2714 && is(ElementType!Separator : ElementType!(ElementType!RoR))) 2715 { 2716 static struct Result 2717 { 2718 private RoR _items; 2719 private ElementType!RoR _current; 2720 static if (isRandomAccessRange!Separator) 2721 { 2722 static struct CurrentSep 2723 { 2724 private Separator _sep; 2725 private size_t sepIndex; 2726 private size_t sepLength; // cache the length for performance 2727 auto front() { return _sep[sepIndex]; } 2728 void popFront() { sepIndex++; } 2729 auto empty() { return sepIndex >= sepLength; } 2730 auto save() 2731 { 2732 auto copy = this; 2733 copy._sep = _sep; 2734 return copy; 2735 } 2736 void reset() 2737 { 2738 sepIndex = 0; 2739 } 2740 2741 void initialize(Separator sep) 2742 { 2743 _sep = sep; 2744 sepIndex = sepLength = _sep.length; 2745 } 2746 } 2747 } 2748 else 2749 { 2750 static struct CurrentSep 2751 { 2752 private Separator _sep; 2753 Separator payload; 2754 2755 alias payload this; 2756 2757 auto save() 2758 { 2759 auto copy = this; 2760 copy._sep = _sep; 2761 return copy; 2762 } 2763 2764 void reset() 2765 { 2766 payload = _sep.save; 2767 } 2768 2769 void initialize(Separator sep) 2770 { 2771 _sep = sep; 2772 } 2773 } 2774 } 2775 2776 private CurrentSep _currentSep; 2777 2778 private void setItem() 2779 { 2780 if (!_items.empty) 2781 { 2782 // If we're exporting .save, we must not consume any of the 2783 // subranges, since RoR.save does not guarantee that the states 2784 // of the subranges are also saved. 2785 static if (isForwardRange!RoR && 2786 isForwardRange!(ElementType!RoR)) 2787 _current = _items.front.save; 2788 else 2789 _current = _items.front; 2790 } 2791 } 2792 2793 private void useSeparator() 2794 { 2795 // Separator must always come after an item. 2796 assert(_currentSep.empty && !_items.empty, 2797 "joiner: internal error"); 2798 _items.popFront(); 2799 2800 // If there are no more items, we're done, since separators are not 2801 // terminators. 2802 if (_items.empty) return; 2803 2804 if (_currentSep._sep.empty) 2805 { 2806 // Advance to the next range in the 2807 // input 2808 while (_items.front.empty) 2809 { 2810 _items.popFront(); 2811 if (_items.empty) return; 2812 } 2813 setItem; 2814 } 2815 else 2816 { 2817 _currentSep.reset; 2818 assert(!_currentSep.empty, "seperator must not be empty"); 2819 } 2820 } 2821 2822 this(RoR items, Separator sep) 2823 { 2824 _items = items; 2825 _currentSep.initialize(sep); 2826 2827 //mixin(useItem); // _current should be initialized in place 2828 if (_items.empty) 2829 _current = _current.init; // set invalid state 2830 else 2831 { 2832 // If we're exporting .save, we must not consume any of the 2833 // subranges, since RoR.save does not guarantee that the states 2834 // of the subranges are also saved. 2835 static if (isForwardRange!RoR && 2836 isForwardRange!(ElementType!RoR)) 2837 _current = _items.front.save; 2838 else 2839 _current = _items.front; 2840 2841 if (_current.empty) 2842 { 2843 // No data in the current item - toggle to use the separator 2844 useSeparator(); 2845 } 2846 } 2847 } 2848 2849 @property auto empty() 2850 { 2851 return _items.empty; 2852 } 2853 2854 @property ElementType!(ElementType!RoR) front() 2855 { 2856 if (!_currentSep.empty) return _currentSep.front; 2857 assert(!_current.empty, "Attempting to fetch the front of an empty joiner."); 2858 return _current.front; 2859 } 2860 2861 void popFront() 2862 { 2863 assert(!_items.empty, "Attempting to popFront an empty joiner."); 2864 // Using separator? 2865 if (!_currentSep.empty) 2866 { 2867 _currentSep.popFront(); 2868 if (_currentSep.empty && !_items.empty) 2869 { 2870 setItem; 2871 if (_current.empty) 2872 { 2873 // No data in the current item - toggle to use the separator 2874 useSeparator(); 2875 } 2876 } 2877 } 2878 else 2879 { 2880 // we're using the range 2881 _current.popFront(); 2882 if (_current.empty) 2883 useSeparator(); 2884 } 2885 } 2886 2887 static if (isForwardRange!RoR && isForwardRange!(ElementType!RoR)) 2888 { 2889 @property auto save() 2890 { 2891 Result copy = this; 2892 copy._items = _items.save; 2893 copy._current = _current.save; 2894 copy._currentSep = _currentSep.save; 2895 return copy; 2896 } 2897 } 2898 } 2899 return Result(r, sep); 2900 } 2901 2902 /// 2903 @safe unittest 2904 { 2905 import std.algorithm.comparison : equal; 2906 import std.conv : text; 2907 2908 assert(["abc", "def"].joiner.equal("abcdef")); 2909 assert(["Mary", "has", "a", "little", "lamb"] 2910 .joiner("...") 2911 .equal("Mary...has...a...little...lamb")); 2912 assert(["", "abc"].joiner("xyz").equal("xyzabc")); 2913 assert([""].joiner("xyz").equal("")); 2914 assert(["", ""].joiner("xyz").equal("xyz")); 2915 } 2916 2917 @system unittest 2918 { 2919 import std.algorithm.comparison : equal; 2920 import std.range.interfaces; 2921 import std.range.primitives; 2922 // joiner() should work for non-forward ranges too. 2923 auto r = inputRangeObject(["abc", "def"]); 2924 assert(equal(joiner(r, "xyz"), "abcxyzdef")); 2925 } 2926 2927 @system unittest 2928 { 2929 import std.algorithm.comparison : equal; 2930 import std.range; 2931 2932 // Related to https://issues.dlang.org/show_bug.cgi?id=8061 2933 auto r = joiner([ 2934 inputRangeObject("abc"), 2935 inputRangeObject("def"), 2936 ], "-*-"); 2937 2938 assert(equal(r, "abc-*-def")); 2939 2940 // Test case where separator is specified but is empty. 2941 auto s = joiner([ 2942 inputRangeObject("abc"), 2943 inputRangeObject("def"), 2944 ], ""); 2945 2946 assert(equal(s, "abcdef")); 2947 2948 // Test empty separator with some empty elements 2949 auto t = joiner([ 2950 inputRangeObject("abc"), 2951 inputRangeObject(""), 2952 inputRangeObject("def"), 2953 inputRangeObject(""), 2954 ], ""); 2955 2956 assert(equal(t, "abcdef")); 2957 2958 // Test empty elements with non-empty separator 2959 auto u = joiner([ 2960 inputRangeObject(""), 2961 inputRangeObject("abc"), 2962 inputRangeObject(""), 2963 inputRangeObject("def"), 2964 inputRangeObject(""), 2965 ], "+-"); 2966 2967 assert(equal(u, "+-abc+-+-def+-")); 2968 2969 // https://issues.dlang.org/show_bug.cgi?id=13441: only(x) as separator 2970 string[][] lines = [null]; 2971 lines 2972 .joiner(only("b")) 2973 .array(); 2974 } 2975 2976 @safe unittest 2977 { 2978 import std.algorithm.comparison : equal; 2979 2980 // Transience correctness test 2981 struct TransientRange 2982 { 2983 @safe: 2984 int[][] src; 2985 int[] buf; 2986 2987 this(int[][] _src) 2988 { 2989 src = _src; 2990 buf.length = 100; 2991 } 2992 @property bool empty() { return src.empty; } 2993 @property int[] front() 2994 { 2995 assert(src.front.length <= buf.length); 2996 buf[0 .. src.front.length] = src.front[0..$]; 2997 return buf[0 .. src.front.length]; 2998 } 2999 void popFront() { src.popFront(); } 3000 } 3001 3002 // Test embedded empty elements 3003 auto tr1 = TransientRange([[], [1,2,3], [], [4]]); 3004 assert(equal(joiner(tr1, [0]), [0,1,2,3,0,0,4])); 3005 3006 // Test trailing empty elements 3007 auto tr2 = TransientRange([[], [1,2,3], []]); 3008 assert(equal(joiner(tr2, [0]), [0,1,2,3,0])); 3009 3010 // Test no empty elements 3011 auto tr3 = TransientRange([[1,2], [3,4]]); 3012 assert(equal(joiner(tr3, [0,1]), [1,2,0,1,3,4])); 3013 3014 // Test consecutive empty elements 3015 auto tr4 = TransientRange([[1,2], [], [], [], [3,4]]); 3016 assert(equal(joiner(tr4, [0,1]), [1,2,0,1,0,1,0,1,0,1,3,4])); 3017 3018 // Test consecutive trailing empty elements 3019 auto tr5 = TransientRange([[1,2], [3,4], [], []]); 3020 assert(equal(joiner(tr5, [0,1]), [1,2,0,1,3,4,0,1,0,1])); 3021 } 3022 3023 @safe unittest 3024 { 3025 static assert(isInputRange!(typeof(joiner([""], "")))); 3026 static assert(isForwardRange!(typeof(joiner([""], "")))); 3027 } 3028 3029 /// Ditto 3030 auto joiner(RoR)(RoR r) 3031 if (isInputRange!RoR && isInputRange!(ElementType!RoR)) 3032 { 3033 static struct Result 3034 { 3035 private: 3036 RoR _items; 3037 ElementType!RoR _current; 3038 enum isBidirectional = isForwardRange!RoR && isForwardRange!(ElementType!RoR) && 3039 isBidirectionalRange!RoR && isBidirectionalRange!(ElementType!RoR); 3040 static if (isBidirectional) 3041 { 3042 ElementType!RoR _currentBack; 3043 bool reachedFinalElement; 3044 } 3045 3046 this(RoR items, ElementType!RoR current) 3047 { 3048 _items = items; 3049 _current = current; 3050 static if (isBidirectional && hasNested!Result) 3051 _currentBack = typeof(_currentBack).init; 3052 } 3053 3054 public: 3055 this(RoR r) 3056 { 3057 _items = r; 3058 3059 static if (isBidirectional && hasNested!Result) 3060 _currentBack = typeof(_currentBack).init; 3061 // field _current must be initialized in constructor, because it is nested struct 3062 mixin(popFrontEmptyElements); 3063 static if (isBidirectional) 3064 mixin(popBackEmptyElements); 3065 } 3066 static if (isInfinite!RoR) 3067 { 3068 enum bool empty = false; 3069 } 3070 else 3071 { 3072 @property auto empty() 3073 { 3074 return _items.empty; 3075 } 3076 } 3077 @property auto ref front() 3078 { 3079 assert(!empty, "Attempting to fetch the front of an empty joiner."); 3080 return _current.front; 3081 } 3082 void popFront() 3083 { 3084 assert(!_current.empty, "Attempting to popFront an empty joiner."); 3085 _current.popFront(); 3086 if (_current.empty) 3087 { 3088 assert(!_items.empty, "Attempting to popFront an empty joiner."); 3089 _items.popFront(); 3090 mixin(popFrontEmptyElements); 3091 } 3092 } 3093 3094 private enum popFrontEmptyElements = q{ 3095 // Skip over empty subranges. 3096 while (!_items.empty && _items.front.empty) 3097 { 3098 _items.popFront(); 3099 } 3100 if (!_items.empty) 3101 { 3102 // We cannot export .save method unless we ensure subranges are not 3103 // consumed when a .save'd copy of ourselves is iterated over. So 3104 // we need to .save each subrange we traverse. 3105 static if (isForwardRange!RoR && isForwardRange!(ElementType!RoR)) 3106 _current = _items.front.save; 3107 else 3108 _current = _items.front; 3109 } 3110 else 3111 { 3112 _current = typeof(_current).init; 3113 } 3114 }; 3115 3116 static if (isForwardRange!RoR && isForwardRange!(ElementType!RoR)) 3117 { 3118 @property auto save() 3119 { 3120 auto r = Result(_items.save, _current.save); 3121 static if (isBidirectional) 3122 { 3123 r._currentBack = _currentBack.save; 3124 r.reachedFinalElement = reachedFinalElement; 3125 } 3126 return r; 3127 } 3128 } 3129 3130 static if (hasAssignableElements!(ElementType!RoR)) 3131 { 3132 @property void front(ElementType!(ElementType!RoR) element) 3133 { 3134 assert(!empty, "Attempting to assign to front of an empty joiner."); 3135 _current.front = element; 3136 } 3137 3138 @property void front(ref ElementType!(ElementType!RoR) element) 3139 { 3140 assert(!empty, "Attempting to assign to front of an empty joiner."); 3141 _current.front = element; 3142 } 3143 } 3144 3145 static if (isBidirectional) 3146 { 3147 bool checkFinalElement() 3148 { 3149 import std.range : dropOne; 3150 3151 if (reachedFinalElement) 3152 return true; 3153 3154 static if (hasLength!(typeof(_items))) 3155 { 3156 if (_items.length == 1) 3157 reachedFinalElement = true; 3158 } 3159 else 3160 { 3161 if (_items.save.dropOne.empty) 3162 reachedFinalElement = true; 3163 } 3164 3165 return false; 3166 } 3167 3168 @property auto ref back() 3169 { 3170 assert(!empty, "Attempting to fetch the back of an empty joiner."); 3171 if (reachedFinalElement) 3172 return _current.back; 3173 else 3174 return _currentBack.back; 3175 } 3176 3177 void popBack() 3178 { 3179 assert(!_current.empty, "Attempting to popBack an empty joiner."); 3180 if (checkFinalElement) 3181 _current.popBack(); 3182 else 3183 _currentBack.popBack(); 3184 3185 bool isEmpty = reachedFinalElement ? _current.empty : _currentBack.empty; 3186 if (isEmpty) 3187 { 3188 assert(!_items.empty, "Attempting to popBack an empty joiner."); 3189 _items.popBack(); 3190 mixin(popBackEmptyElements); 3191 } 3192 } 3193 3194 private enum popBackEmptyElements = q{ 3195 // Skip over empty subranges. 3196 while (!_items.empty && _items.back.empty) 3197 { 3198 _items.popBack(); 3199 } 3200 if (!_items.empty) 3201 { 3202 checkFinalElement; 3203 // We cannot export .save method unless we ensure subranges are not 3204 // consumed when a .save'd copy of ourselves is iterated over. So 3205 // we need to .save each subrange we traverse. 3206 static if (isForwardRange!RoR && isForwardRange!(ElementType!RoR)) 3207 { 3208 if (reachedFinalElement) 3209 _current = _items.back.save; 3210 else 3211 _currentBack = _items.back.save; 3212 } 3213 else 3214 { 3215 if (reachedFinalElement) 3216 _current = _items.back; 3217 else 3218 _currentBack = _items.back; 3219 } 3220 } 3221 else 3222 { 3223 _current = typeof(_current).init; 3224 _currentBack = typeof(_currentBack).init; 3225 } 3226 }; 3227 3228 static if (hasAssignableElements!(ElementType!RoR)) 3229 { 3230 @property void back(ElementType!(ElementType!RoR) element) 3231 { 3232 assert(!empty, "Attempting to assign to back of an empty joiner."); 3233 if (reachedFinalElement) 3234 _current.back = element; 3235 else 3236 _currentBack.back = element; 3237 } 3238 3239 @property void back(ref ElementType!(ElementType!RoR) element) 3240 { 3241 assert(!empty, "Attempting to assign to back of an empty joiner."); 3242 if (reachedFinalElement) 3243 _current.back = element; 3244 else 3245 _currentBack.back = element; 3246 } 3247 } 3248 } 3249 } 3250 return Result(r); 3251 } 3252 3253 /// 3254 @safe unittest 3255 { 3256 import std.algorithm.comparison : equal; 3257 import std.range : repeat; 3258 3259 assert([""].joiner.equal("")); 3260 assert(["", ""].joiner.equal("")); 3261 assert(["", "abc"].joiner.equal("abc")); 3262 assert(["abc", ""].joiner.equal("abc")); 3263 assert(["abc", "def"].joiner.equal("abcdef")); 3264 assert(["Mary", "has", "a", "little", "lamb"].joiner.equal("Maryhasalittlelamb")); 3265 assert("abc".repeat(3).joiner.equal("abcabcabc")); 3266 } 3267 3268 /// joiner allows in-place mutation! 3269 @safe unittest 3270 { 3271 import std.algorithm.comparison : equal; 3272 auto a = [ [1, 2, 3], [42, 43] ]; 3273 auto j = joiner(a); 3274 j.front = 44; 3275 assert(a == [ [44, 2, 3], [42, 43] ]); 3276 assert(equal(j, [44, 2, 3, 42, 43])); 3277 } 3278 3279 /// insert characters fully lazily into a string 3280 @safe pure unittest 3281 { 3282 import std.algorithm.comparison : equal; 3283 import std.range : chain, cycle, iota, only, retro, take, zip; 3284 import std.format : format; 3285 3286 static immutable number = "12345678"; 3287 static immutable delimiter = ","; 3288 auto formatted = number.retro 3289 .zip(3.iota.cycle.take(number.length)) 3290 .map!(z => chain(z[0].only, z[1] == 2 ? delimiter : null)) 3291 .joiner 3292 .retro; 3293 static immutable expected = "12,345,678"; 3294 assert(formatted.equal(expected)); 3295 } 3296 3297 @safe unittest 3298 { 3299 import std.range.interfaces : inputRangeObject; 3300 static assert(isInputRange!(typeof(joiner([""])))); 3301 static assert(isForwardRange!(typeof(joiner([""])))); 3302 } 3303 3304 @safe unittest 3305 { 3306 // Initial version of PR #6115 caused a compilation failure for 3307 // https://github.com/BlackEdder/ggplotd/blob/d4428c08db5ffdc05dfd29690bf7da9073ea1dc5/source/ggplotd/stat.d#L562-L583 3308 import std.range : zip; 3309 int[] xCoords = [1, 2, 3]; 3310 int[] yCoords = [4, 5, 6]; 3311 auto coords = zip(xCoords, xCoords[1..$]).map!( (xr) { 3312 return zip(yCoords, yCoords[1..$]).map!( (yr) { 3313 return [ 3314 [[xr[0], xr[0], xr[1]], 3315 [yr[0], yr[1], yr[1]]], 3316 [[xr[0], xr[1], xr[1]], 3317 [yr[0], yr[0], yr[1]]] 3318 ]; 3319 }).joiner; 3320 }).joiner; 3321 } 3322 3323 @system unittest 3324 { 3325 import std.algorithm.comparison : equal; 3326 import std.range.interfaces : inputRangeObject; 3327 import std.range : retro; 3328 3329 // https://issues.dlang.org/show_bug.cgi?id=8240 3330 assert(equal(joiner([inputRangeObject("")]), "")); 3331 assert(equal(joiner([inputRangeObject("")]).retro, "")); 3332 3333 // https://issues.dlang.org/show_bug.cgi?id=8792 3334 auto b = [[1], [2], [3]]; 3335 auto jb = joiner(b); 3336 auto js = jb.save; 3337 assert(equal(jb, js)); 3338 3339 auto js2 = jb.save; 3340 jb.popFront(); 3341 assert(!equal(jb, js)); 3342 assert(equal(js2, js)); 3343 js.popFront(); 3344 assert(equal(jb, js)); 3345 assert(!equal(js2, js)); 3346 } 3347 3348 // https://issues.dlang.org/show_bug.cgi?id=19213 3349 @system unittest 3350 { 3351 auto results = [[1,2], [3,4]].map!(q => q.chunkBy!"a").joiner; 3352 int i = 1; 3353 foreach (ref e; results) 3354 assert(e[0] == i++); 3355 } 3356 3357 /// joiner can be bidirectional 3358 @safe unittest 3359 { 3360 import std.algorithm.comparison : equal; 3361 import std.range : retro; 3362 3363 auto a = [[1, 2, 3], [4, 5]]; 3364 auto j = a.joiner; 3365 j.back = 44; 3366 assert(a == [[1, 2, 3], [4, 44]]); 3367 assert(equal(j.retro, [44, 4, 3, 2, 1])); 3368 } 3369 3370 // bidirectional joiner: test for filtering empty elements 3371 @safe unittest 3372 { 3373 import std.algorithm.comparison : equal; 3374 import std.range : retro; 3375 3376 alias El = (e) => new int(e); 3377 auto a = [null, [null, El(1), null, El(2), null, El(3), null], null, [null, El(4), null, El(5), null]]; 3378 auto j = a.joiner; 3379 3380 alias deref = a => a is null ? -1 : *a; 3381 auto expected = [-1, 5, -1, 4, -1, -1, 3, -1, 2, -1, 1, -1]; 3382 // works with .save. 3383 assert(j.save.retro.map!deref.equal(expected)); 3384 // and without .save 3385 assert(j.retro.map!deref.equal(expected)); 3386 assert(j.retro.map!deref.equal(expected)); 3387 } 3388 3389 // bidirectional joiner is @nogc 3390 @safe @nogc unittest 3391 { 3392 import std.algorithm.comparison : equal; 3393 import std.range : iota, only, retro; 3394 3395 auto a = only(iota(1, 4), iota(4, 6)); 3396 auto j = a.joiner; 3397 static immutable expected = [5 , 4, 3, 2, 1]; 3398 assert(equal(j.retro, expected)); 3399 } 3400 3401 // bidirectional joiner supports assignment to the back 3402 @safe unittest 3403 { 3404 import std.algorithm.comparison : equal; 3405 import std.range : popBackN; 3406 3407 auto a = [[1, 2, 3], [4, 5]]; 3408 auto j = a.joiner; 3409 j.back = 55; 3410 assert(a == [[1, 2, 3], [4, 55]]); 3411 j.popBackN(2); 3412 j.back = 33; 3413 assert(a == [[1, 2, 33], [4, 55]]); 3414 } 3415 3416 // bidirectional joiner works with auto-decoding 3417 @safe unittest 3418 { 3419 import std.algorithm.comparison : equal; 3420 import std.range : retro; 3421 3422 auto a = ["😀😐", "😠"]; 3423 auto j = a.joiner; 3424 assert(j.retro.equal("😠😐😀")); 3425 } 3426 3427 // test two-side iteration 3428 @safe unittest 3429 { 3430 import std.algorithm.comparison : equal; 3431 import std.range : popBackN; 3432 3433 auto arrs = [ 3434 [[1], [2], [3], [4], [5]], 3435 [[1], [2, 3, 4], [5]], 3436 [[1, 2, 3, 4, 5]], 3437 ]; 3438 foreach (arr; arrs) 3439 { 3440 auto a = arr.joiner; 3441 assert(a.front == 1); 3442 assert(a.back == 5); 3443 a.popFront; 3444 assert(a.front == 2); 3445 assert(a.back == 5); 3446 a.popBack; 3447 assert(a.front == 2); 3448 assert(a.back == 4); 3449 a.popFront; 3450 assert(a.front == 3); 3451 assert(a.back == 4); 3452 a.popBack; 3453 assert(a.front == 3); 3454 assert(a.back == 3); 3455 a.popBack; 3456 assert(a.empty); 3457 } 3458 } 3459 3460 @safe unittest 3461 { 3462 import std.algorithm.comparison : equal; 3463 3464 struct TransientRange 3465 { 3466 @safe: 3467 int[] _buf; 3468 int[][] _values; 3469 this(int[][] values) 3470 { 3471 _values = values; 3472 _buf = new int[128]; 3473 } 3474 @property bool empty() 3475 { 3476 return _values.length == 0; 3477 } 3478 @property auto front() 3479 { 3480 foreach (i; 0 .. _values.front.length) 3481 { 3482 _buf[i] = _values[0][i]; 3483 } 3484 return _buf[0 .. _values.front.length]; 3485 } 3486 void popFront() 3487 { 3488 _values = _values[1 .. $]; 3489 } 3490 } 3491 3492 auto rr = TransientRange([[1,2], [3,4,5], [], [6,7]]); 3493 3494 // Can't use array() or equal() directly because they fail with transient 3495 // .front. 3496 int[] result; 3497 foreach (c; rr.joiner()) 3498 { 3499 result ~= c; 3500 } 3501 3502 assert(equal(result, [1,2,3,4,5,6,7])); 3503 } 3504 3505 @safe unittest 3506 { 3507 import std.algorithm.comparison : equal; 3508 import std.algorithm.internal : algoFormat; 3509 3510 struct TransientRange 3511 { 3512 @safe: 3513 dchar[] _buf; 3514 dstring[] _values; 3515 this(dstring[] values) 3516 { 3517 _buf.length = 128; 3518 _values = values; 3519 } 3520 @property bool empty() 3521 { 3522 return _values.length == 0; 3523 } 3524 @property auto front() 3525 { 3526 foreach (i; 0 .. _values.front.length) 3527 { 3528 _buf[i] = _values[0][i]; 3529 } 3530 return _buf[0 .. _values.front.length]; 3531 } 3532 void popFront() 3533 { 3534 _values = _values[1 .. $]; 3535 } 3536 } 3537 3538 auto rr = TransientRange(["abc"d, "12"d, "def"d, "34"d]); 3539 3540 // Can't use array() or equal() directly because they fail with transient 3541 // .front. 3542 dchar[] result; 3543 foreach (c; rr.joiner()) 3544 { 3545 result ~= c; 3546 } 3547 3548 import std.conv : to; 3549 assert(equal(result, "abc12def34"d), 3550 //Convert to string for assert's message 3551 to!string("Unexpected result: '%s'"d.algoFormat(result))); 3552 } 3553 3554 // https://issues.dlang.org/show_bug.cgi?id=8061 3555 @system unittest 3556 { 3557 import std.conv : to; 3558 import std.range.interfaces; 3559 3560 auto r = joiner([inputRangeObject("ab"), inputRangeObject("cd")]); 3561 assert(isForwardRange!(typeof(r))); 3562 3563 auto str = to!string(r); 3564 assert(str == "abcd"); 3565 } 3566 3567 @safe unittest 3568 { 3569 import std.range : repeat; 3570 3571 class AssignableRange 3572 { 3573 @safe: 3574 int element; 3575 @property int front() 3576 { 3577 return element; 3578 } 3579 alias back = front; 3580 3581 enum empty = false; 3582 3583 auto save() 3584 { 3585 return this; 3586 } 3587 3588 void popFront() {} 3589 alias popBack = popFront; 3590 3591 @property void front(int newValue) 3592 { 3593 element = newValue; 3594 } 3595 alias back = front; 3596 } 3597 3598 static assert(isInputRange!AssignableRange); 3599 static assert(is(ElementType!AssignableRange == int)); 3600 static assert(hasAssignableElements!AssignableRange); 3601 static assert(!hasLvalueElements!AssignableRange); 3602 3603 auto range = new AssignableRange(); 3604 assert(range.element == 0); 3605 { 3606 auto joined = joiner(repeat(range)); 3607 joined.front = 5; 3608 assert(range.element == 5); 3609 assert(joined.front == 5); 3610 3611 joined.popFront; 3612 int byRef = 7; 3613 joined.front = byRef; 3614 assert(range.element == byRef); 3615 assert(joined.front == byRef); 3616 } 3617 { 3618 auto joined = joiner(repeat(range)); 3619 joined.back = 5; 3620 assert(range.element == 5); 3621 assert(joined.back == 5); 3622 3623 joined.popBack; 3624 int byRef = 7; 3625 joined.back = byRef; 3626 assert(range.element == byRef); 3627 assert(joined.back == byRef); 3628 } 3629 } 3630 3631 // https://issues.dlang.org/show_bug.cgi?id=19850 3632 @safe pure unittest 3633 { 3634 assert([[0]].joiner.save.back == 0); 3635 } 3636 3637 /++ 3638 Implements the homonym function (also known as `accumulate`, $(D 3639 compress), `inject`, or `foldl`) present in various programming 3640 languages of functional flavor. There is also $(LREF fold) which does 3641 the same thing but with the opposite parameter order. 3642 The call `reduce!(fun)(seed, range)` first assigns `seed` to 3643 an internal variable `result`, also called the accumulator. 3644 Then, for each element `x` in `range`, `result = fun(result, x)` 3645 gets evaluated. Finally, `result` is returned. 3646 The one-argument version `reduce!(fun)(range)` 3647 works similarly, but it uses the first element of the range as the 3648 seed (the range must be non-empty). 3649 3650 Returns: 3651 the accumulated `result` 3652 3653 Params: 3654 fun = one or more functions 3655 3656 See_Also: 3657 $(HTTP en.wikipedia.org/wiki/Fold_(higher-order_function), Fold (higher-order function)) 3658 3659 $(LREF fold) is functionally equivalent to $(LREF _reduce) with the argument 3660 order reversed, and without the need to use $(REF_ALTTEXT `tuple`,tuple,std,typecons) 3661 for multiple seeds. This makes it easier to use in UFCS chains. 3662 3663 $(LREF sum) is similar to `reduce!((a, b) => a + b)` that offers 3664 pairwise summing of floating point numbers. 3665 +/ 3666 template reduce(fun...) 3667 if (fun.length >= 1) 3668 { 3669 import std.meta : staticMap; 3670 3671 alias binfuns = staticMap!(binaryFun, fun); 3672 static if (fun.length > 1) 3673 import std.typecons : tuple, isTuple; 3674 3675 /++ 3676 No-seed version. The first element of `r` is used as the seed's value. 3677 3678 For each function `f` in `fun`, the corresponding 3679 seed type `S` is `Unqual!(typeof(f(e, e)))`, where `e` is an 3680 element of `r`: `ElementType!R` for ranges, 3681 and `ForeachType!R` otherwise. 3682 3683 Once S has been determined, then `S s = e;` and `s = f(s, e);` 3684 must both be legal. 3685 3686 Params: 3687 r = an iterable value as defined by `isIterable` 3688 3689 Returns: 3690 the final result of the accumulator applied to the iterable 3691 3692 Throws: `Exception` if `r` is empty 3693 +/ 3694 auto reduce(R)(R r) 3695 if (isIterable!R) 3696 { 3697 import std.exception : enforce; 3698 alias E = Select!(isInputRange!R, ElementType!R, ForeachType!R); 3699 alias Args = staticMap!(ReduceSeedType!E, binfuns); 3700 3701 static if (isInputRange!R) 3702 { 3703 // no need to throw if range is statically known to be non-empty 3704 static if (!__traits(compiles, 3705 { 3706 static assert(r.length > 0); 3707 })) 3708 enforce(!r.empty, "Cannot reduce an empty input range w/o an explicit seed value."); 3709 3710 Args result = r.front; 3711 r.popFront(); 3712 return reduceImpl!false(r, result); 3713 } 3714 else 3715 { 3716 auto result = Args.init; 3717 return reduceImpl!true(r, result); 3718 } 3719 } 3720 3721 /++ 3722 Seed version. The seed should be a single value if `fun` is a 3723 single function. If `fun` is multiple functions, then `seed` 3724 should be a $(REF Tuple, std,typecons), with one field per function in `f`. 3725 3726 For convenience, if the seed is const, or has qualified fields, then 3727 `reduce` will operate on an unqualified copy. If this happens 3728 then the returned type will not perfectly match `S`. 3729 3730 Use `fold` instead of `reduce` to use the seed version in a UFCS chain. 3731 3732 Params: 3733 seed = the initial value of the accumulator 3734 r = an iterable value as defined by `isIterable` 3735 3736 Returns: 3737 the final result of the accumulator applied to the iterable 3738 +/ 3739 auto reduce(S, R)(S seed, R r) 3740 if (isIterable!R) 3741 { 3742 static if (fun.length == 1) 3743 return reducePreImpl(r, seed); 3744 else 3745 { 3746 import std.algorithm.internal : algoFormat; 3747 static assert(isTuple!S, algoFormat("Seed %s should be a Tuple", S.stringof)); 3748 return reducePreImpl(r, seed.expand); 3749 } 3750 } 3751 3752 private auto reducePreImpl(R, Args...)(R r, ref Args args) 3753 { 3754 alias Result = staticMap!(Unqual, Args); 3755 static if (is(Result == Args)) 3756 alias result = args; 3757 else 3758 Result result = args; 3759 return reduceImpl!false(r, result); 3760 } 3761 3762 private auto reduceImpl(bool mustInitialize, R, Args...)(R r, ref Args args) 3763 if (isIterable!R) 3764 { 3765 import std.algorithm.internal : algoFormat; 3766 static assert(Args.length == fun.length, 3767 algoFormat("Seed %s does not have the correct amount of fields (should be %s)", Args.stringof, fun.length)); 3768 alias E = Select!(isInputRange!R, ElementType!R, ForeachType!R); 3769 3770 static if (mustInitialize) bool initialized = false; 3771 foreach (/+auto ref+/ E e; r) // https://issues.dlang.org/show_bug.cgi?id=4707 3772 { 3773 foreach (i, f; binfuns) 3774 { 3775 static assert(!is(typeof(f(args[i], e))) || is(typeof(args[i] = f(args[i], e))), 3776 algoFormat( 3777 "Incompatible function/seed/element: %s/%s/%s", 3778 fullyQualifiedName!f, 3779 Args[i].stringof, 3780 E.stringof 3781 ) 3782 ); 3783 } 3784 3785 static if (mustInitialize) if (initialized == false) 3786 { 3787 import std.conv : emplaceRef; 3788 foreach (i, f; binfuns) 3789 emplaceRef!(Args[i])(args[i], e); 3790 initialized = true; 3791 continue; 3792 } 3793 3794 foreach (i, f; binfuns) 3795 args[i] = f(args[i], e); 3796 } 3797 static if (mustInitialize) 3798 // no need to throw if range is statically known to be non-empty 3799 static if (!__traits(compiles, 3800 { 3801 static assert(r.length > 0); 3802 })) 3803 { 3804 if (!initialized) 3805 throw new Exception("Cannot reduce an empty iterable w/o an explicit seed value."); 3806 } 3807 3808 static if (Args.length == 1) 3809 return args[0]; 3810 else 3811 return tuple(args); 3812 } 3813 } 3814 3815 /** 3816 Many aggregate range operations turn out to be solved with `reduce` 3817 quickly and easily. The example below illustrates `reduce`'s 3818 remarkable power and flexibility. 3819 */ 3820 @safe unittest 3821 { 3822 import std.algorithm.comparison : max, min; 3823 import std.math : approxEqual; 3824 import std.range; 3825 3826 int[] arr = [ 1, 2, 3, 4, 5 ]; 3827 // Sum all elements 3828 auto sum = reduce!((a,b) => a + b)(0, arr); 3829 assert(sum == 15); 3830 3831 // Sum again, using a string predicate with "a" and "b" 3832 sum = reduce!"a + b"(0, arr); 3833 assert(sum == 15); 3834 3835 // Compute the maximum of all elements 3836 auto largest = reduce!(max)(arr); 3837 assert(largest == 5); 3838 3839 // Max again, but with Uniform Function Call Syntax (UFCS) 3840 largest = arr.reduce!(max); 3841 assert(largest == 5); 3842 3843 // Compute the number of odd elements 3844 auto odds = reduce!((a,b) => a + (b & 1))(0, arr); 3845 assert(odds == 3); 3846 3847 // Compute the sum of squares 3848 auto ssquares = reduce!((a,b) => a + b * b)(0, arr); 3849 assert(ssquares == 55); 3850 3851 // Chain multiple ranges into seed 3852 int[] a = [ 3, 4 ]; 3853 int[] b = [ 100 ]; 3854 auto r = reduce!("a + b")(chain(a, b)); 3855 assert(r == 107); 3856 3857 // Mixing convertible types is fair game, too 3858 double[] c = [ 2.5, 3.0 ]; 3859 auto r1 = reduce!("a + b")(chain(a, b, c)); 3860 assert(approxEqual(r1, 112.5)); 3861 3862 // To minimize nesting of parentheses, Uniform Function Call Syntax can be used 3863 auto r2 = chain(a, b, c).reduce!("a + b"); 3864 assert(approxEqual(r2, 112.5)); 3865 } 3866 3867 /** 3868 Sometimes it is very useful to compute multiple aggregates in one pass. 3869 One advantage is that the computation is faster because the looping overhead 3870 is shared. That's why `reduce` accepts multiple functions. 3871 If two or more functions are passed, `reduce` returns a 3872 $(REF Tuple, std,typecons) object with one member per passed-in function. 3873 The number of seeds must be correspondingly increased. 3874 */ 3875 @safe unittest 3876 { 3877 import std.algorithm.comparison : max, min; 3878 import std.math : approxEqual, sqrt; 3879 import std.typecons : tuple, Tuple; 3880 3881 double[] a = [ 3.0, 4, 7, 11, 3, 2, 5 ]; 3882 // Compute minimum and maximum in one pass 3883 auto r = reduce!(min, max)(a); 3884 // The type of r is Tuple!(int, int) 3885 assert(approxEqual(r[0], 2)); // minimum 3886 assert(approxEqual(r[1], 11)); // maximum 3887 3888 // Compute sum and sum of squares in one pass 3889 r = reduce!("a + b", "a + b * b")(tuple(0.0, 0.0), a); 3890 assert(approxEqual(r[0], 35)); // sum 3891 assert(approxEqual(r[1], 233)); // sum of squares 3892 // Compute average and standard deviation from the above 3893 auto avg = r[0] / a.length; 3894 assert(avg == 5); 3895 auto stdev = sqrt(r[1] / a.length - avg * avg); 3896 assert(cast(int) stdev == 2); 3897 } 3898 3899 @safe unittest 3900 { 3901 import std.algorithm.comparison : max, min; 3902 import std.range : chain; 3903 import std.typecons : tuple, Tuple; 3904 3905 double[] a = [ 3, 4 ]; 3906 auto r = reduce!("a + b")(0.0, a); 3907 assert(r == 7); 3908 r = reduce!("a + b")(a); 3909 assert(r == 7); 3910 r = reduce!(min)(a); 3911 assert(r == 3); 3912 double[] b = [ 100 ]; 3913 auto r1 = reduce!("a + b")(chain(a, b)); 3914 assert(r1 == 107); 3915 3916 // two funs 3917 auto r2 = reduce!("a + b", "a - b")(tuple(0.0, 0.0), a); 3918 assert(r2[0] == 7 && r2[1] == -7); 3919 auto r3 = reduce!("a + b", "a - b")(a); 3920 assert(r3[0] == 7 && r3[1] == -1); 3921 3922 a = [ 1, 2, 3, 4, 5 ]; 3923 // Stringize with commas 3924 string rep = reduce!("a ~ `, ` ~ to!(string)(b)")("", a); 3925 assert(rep[2 .. $] == "1, 2, 3, 4, 5", "["~rep[2 .. $]~"]"); 3926 } 3927 3928 @safe unittest 3929 { 3930 import std.algorithm.comparison : max, min; 3931 import std.exception : assertThrown; 3932 import std.range : iota; 3933 import std.typecons : tuple, Tuple; 3934 3935 // Test the opApply case. 3936 static struct OpApply 3937 { 3938 bool actEmpty; 3939 3940 int opApply(scope int delegate(ref int) @safe dg) 3941 { 3942 int res; 3943 if (actEmpty) return res; 3944 3945 foreach (i; 0 .. 100) 3946 { 3947 res = dg(i); 3948 if (res) break; 3949 } 3950 return res; 3951 } 3952 } 3953 3954 OpApply oa; 3955 auto hundredSum = reduce!"a + b"(iota(100)); 3956 assert(reduce!"a + b"(5, oa) == hundredSum + 5); 3957 assert(reduce!"a + b"(oa) == hundredSum); 3958 assert(reduce!("a + b", max)(oa) == tuple(hundredSum, 99)); 3959 assert(reduce!("a + b", max)(tuple(5, 0), oa) == tuple(hundredSum + 5, 99)); 3960 3961 // Test for throwing on empty range plus no seed. 3962 assertThrown(reduce!"a + b"([1, 2][0 .. 0])); 3963 3964 oa.actEmpty = true; 3965 assertThrown(reduce!"a + b"(oa)); 3966 } 3967 3968 @safe unittest 3969 { 3970 const float a = 0.0; 3971 const float[] b = [ 1.2, 3, 3.3 ]; 3972 float[] c = [ 1.2, 3, 3.3 ]; 3973 auto r = reduce!"a + b"(a, b); 3974 r = reduce!"a + b"(a, c); 3975 assert(r == 7.5); 3976 } 3977 3978 @safe unittest 3979 { 3980 // https://issues.dlang.org/show_bug.cgi?id=10408 3981 // Two-function reduce of a const array. 3982 import std.algorithm.comparison : max, min; 3983 import std.typecons : tuple, Tuple; 3984 3985 const numbers = [10, 30, 20]; 3986 immutable m = reduce!(min)(numbers); 3987 assert(m == 10); 3988 immutable minmax = reduce!(min, max)(numbers); 3989 assert(minmax == tuple(10, 30)); 3990 } 3991 3992 @safe unittest 3993 { 3994 // https://issues.dlang.org/show_bug.cgi?id=10709 3995 import std.typecons : tuple, Tuple; 3996 3997 enum foo = "a + 0.5 * b"; 3998 auto r = [0, 1, 2, 3]; 3999 auto r1 = reduce!foo(r); 4000 auto r2 = reduce!(foo, foo)(r); 4001 assert(r1 == 3); 4002 assert(r2 == tuple(3, 3)); 4003 } 4004 4005 @safe unittest 4006 { 4007 static struct OpApply 4008 { 4009 int opApply(int delegate(ref int) @safe dg) 4010 { 4011 int[] a = [1, 2, 3]; 4012 4013 int res = 0; 4014 foreach (ref e; a) 4015 { 4016 res = dg(e); 4017 if (res) break; 4018 } 4019 return res; 4020 } 4021 } 4022 //test CTFE and functions with context 4023 int fun(int a, int b) @safe {return a + b + 1;} 4024 auto foo() 4025 { 4026 import std.algorithm.comparison : max; 4027 import std.typecons : tuple, Tuple; 4028 4029 auto a = reduce!(fun)([1, 2, 3]); 4030 auto b = reduce!(fun, fun)([1, 2, 3]); 4031 auto c = reduce!(fun)(0, [1, 2, 3]); 4032 auto d = reduce!(fun, fun)(tuple(0, 0), [1, 2, 3]); 4033 auto e = reduce!(fun)(0, OpApply()); 4034 auto f = reduce!(fun, fun)(tuple(0, 0), OpApply()); 4035 4036 return max(a, b.expand, c, d.expand, e, f.expand); 4037 } 4038 auto a = foo(); 4039 assert(a == 9); 4040 enum b = foo(); 4041 assert(b == 9); 4042 } 4043 4044 @safe unittest 4045 { 4046 import std.algorithm.comparison : max, min; 4047 import std.typecons : tuple, Tuple; 4048 4049 //http://forum.dlang.org/post/oghtttkopzjshsuflelk@forum.dlang.org 4050 //Seed is tuple of const. 4051 static auto minmaxElement(alias F = min, alias G = max, R)(in R range) 4052 @safe pure nothrow 4053 if (isInputRange!R) 4054 { 4055 return reduce!(F, G)(tuple(ElementType!R.max, 4056 ElementType!R.min), range); 4057 } 4058 assert(minmaxElement([1, 2, 3]) == tuple(1, 3)); 4059 } 4060 4061 // https://issues.dlang.org/show_bug.cgi?id=12569 4062 @safe unittest 4063 { 4064 import std.algorithm.comparison : max, min; 4065 import std.typecons : tuple; 4066 dchar c = 'a'; 4067 reduce!(min, max)(tuple(c, c), "hello"); // OK 4068 static assert(!is(typeof(reduce!(min, max)(tuple(c), "hello")))); 4069 static assert(!is(typeof(reduce!(min, max)(tuple(c, c, c), "hello")))); 4070 4071 4072 //"Seed dchar should be a Tuple" 4073 static assert(!is(typeof(reduce!(min, max)(c, "hello")))); 4074 //"Seed (dchar) does not have the correct amount of fields (should be 2)" 4075 static assert(!is(typeof(reduce!(min, max)(tuple(c), "hello")))); 4076 //"Seed (dchar, dchar, dchar) does not have the correct amount of fields (should be 2)" 4077 static assert(!is(typeof(reduce!(min, max)(tuple(c, c, c), "hello")))); 4078 //"Incompatible function/seed/element: all(alias pred = "a")/int/dchar" 4079 static assert(!is(typeof(reduce!all(1, "hello")))); 4080 static assert(!is(typeof(reduce!(all, all)(tuple(1, 1), "hello")))); 4081 } 4082 4083 // https://issues.dlang.org/show_bug.cgi?id=13304 4084 @safe unittest 4085 { 4086 int[] data; 4087 static assert(is(typeof(reduce!((a, b) => a + b)(data)))); 4088 assert(data.length == 0); 4089 } 4090 4091 // https://issues.dlang.org/show_bug.cgi?id=13880 4092 // reduce shouldn't throw if the length is statically known 4093 pure nothrow @safe @nogc unittest 4094 { 4095 import std.algorithm.comparison : min; 4096 int[5] arr; 4097 arr[2] = -1; 4098 assert(arr.reduce!min == -1); 4099 4100 int[0] arr0; 4101 assert(reduce!min(42, arr0) == 42); 4102 } 4103 4104 //Helper for Reduce 4105 private template ReduceSeedType(E) 4106 { 4107 static template ReduceSeedType(alias fun) 4108 { 4109 import std.algorithm.internal : algoFormat; 4110 4111 alias ReduceSeedType = Unqual!(typeof(fun(lvalueOf!E, lvalueOf!E))); 4112 4113 //Check the Seed type is useable. 4114 ReduceSeedType s = ReduceSeedType.init; 4115 static assert(is(typeof({ReduceSeedType s = lvalueOf!E;})) && 4116 is(typeof(lvalueOf!ReduceSeedType = fun(lvalueOf!ReduceSeedType, lvalueOf!E))), 4117 algoFormat( 4118 "Unable to deduce an acceptable seed type for %s with element type %s.", 4119 fullyQualifiedName!fun, 4120 E.stringof 4121 ) 4122 ); 4123 } 4124 } 4125 4126 4127 /++ 4128 Implements the homonym function (also known as `accumulate`, $(D 4129 compress), `inject`, or `foldl`) present in various programming 4130 languages of functional flavor. The call `fold!(fun)(range, seed)` 4131 first assigns `seed` to an internal variable `result`, 4132 also called the accumulator. Then, for each element `x` in $(D 4133 range), `result = fun(result, x)` gets evaluated. Finally, $(D 4134 result) is returned. The one-argument version `fold!(fun)(range)` 4135 works similarly, but it uses the first element of the range as the 4136 seed (the range must be non-empty). 4137 4138 Params: 4139 fun = the predicate function(s) to apply to the elements 4140 4141 See_Also: 4142 $(HTTP en.wikipedia.org/wiki/Fold_(higher-order_function), Fold (higher-order function)) 4143 4144 $(LREF sum) is similar to `fold!((a, b) => a + b)` that offers 4145 precise summing of floating point numbers. 4146 4147 This is functionally equivalent to $(LREF reduce) with the argument order 4148 reversed, and without the need to use $(REF_ALTTEXT `tuple`,tuple,std,typecons) 4149 for multiple seeds. 4150 +/ 4151 template fold(fun...) 4152 if (fun.length >= 1) 4153 { 4154 /** 4155 Params: 4156 r = the $(REF_ALTTEXT input range, isInputRange, std,range,primitives) to fold 4157 seed = the initial value of the accumulator 4158 Returns: 4159 the accumulated `result` 4160 */ 4161 auto fold(R, S...)(R r, S seed) 4162 { 4163 static if (S.length < 2) 4164 { 4165 return reduce!fun(seed, r); 4166 } 4167 else 4168 { 4169 import std.typecons : tuple; 4170 return reduce!fun(tuple(seed), r); 4171 } 4172 } 4173 } 4174 4175 /// 4176 @safe pure unittest 4177 { 4178 immutable arr = [1, 2, 3, 4, 5]; 4179 4180 // Sum all elements 4181 assert(arr.fold!((a, b) => a + b) == 15); 4182 4183 // Sum all elements with explicit seed 4184 assert(arr.fold!((a, b) => a + b)(6) == 21); 4185 4186 import std.algorithm.comparison : min, max; 4187 import std.typecons : tuple; 4188 4189 // Compute minimum and maximum at the same time 4190 assert(arr.fold!(min, max) == tuple(1, 5)); 4191 4192 // Compute minimum and maximum at the same time with seeds 4193 assert(arr.fold!(min, max)(0, 7) == tuple(0, 7)); 4194 4195 // Can be used in a UFCS chain 4196 assert(arr.map!(a => a + 1).fold!((a, b) => a + b) == 20); 4197 4198 // Return the last element of any range 4199 assert(arr.fold!((a, b) => b) == 5); 4200 } 4201 4202 @safe @nogc pure nothrow unittest 4203 { 4204 int[1] arr; 4205 static assert(!is(typeof(arr.fold!()))); 4206 static assert(!is(typeof(arr.fold!(a => a)))); 4207 static assert(is(typeof(arr.fold!((a, b) => a)))); 4208 static assert(is(typeof(arr.fold!((a, b) => a)(1)))); 4209 assert(arr.length == 1); 4210 } 4211 4212 /++ 4213 Similar to `fold`, but returns a range containing the successive reduced values. 4214 The call `cumulativeFold!(fun)(range, seed)` first assigns `seed` to an 4215 internal variable `result`, also called the accumulator. 4216 The returned range contains the values `result = fun(result, x)` lazily 4217 evaluated for each element `x` in `range`. Finally, the last element has the 4218 same value as `fold!(fun)(seed, range)`. 4219 The one-argument version `cumulativeFold!(fun)(range)` works similarly, but 4220 it returns the first element unchanged and uses it as seed for the next 4221 elements. 4222 This function is also known as 4223 $(HTTP en.cppreference.com/w/cpp/algorithm/partial_sum, partial_sum), 4224 $(HTTP docs.python.org/3/library/itertools.html#itertools.accumulate, accumulate), 4225 $(HTTP hackage.haskell.org/package/base-4.8.2.0/docs/Prelude.html#v:scanl, scan), 4226 $(HTTP mathworld.wolfram.com/CumulativeSum.html, Cumulative Sum). 4227 4228 Params: 4229 fun = one or more functions to use as fold operation 4230 4231 Returns: 4232 The function returns a range containing the consecutive reduced values. If 4233 there is more than one `fun`, the element type will be $(REF Tuple, 4234 std,typecons) containing one element for each `fun`. 4235 4236 See_Also: 4237 $(HTTP en.wikipedia.org/wiki/Prefix_sum, Prefix Sum) 4238 4239 Note: 4240 4241 In functional programming languages this is typically called `scan`, `scanl`, 4242 `scanLeft` or `reductions`. 4243 +/ 4244 template cumulativeFold(fun...) 4245 if (fun.length >= 1) 4246 { 4247 import std.meta : staticMap; 4248 private alias binfuns = staticMap!(binaryFun, fun); 4249 4250 /++ 4251 No-seed version. The first element of `r` is used as the seed's value. 4252 For each function `f` in `fun`, the corresponding seed type `S` is 4253 `Unqual!(typeof(f(e, e)))`, where `e` is an element of `r`: 4254 `ElementType!R`. 4255 Once `S` has been determined, then `S s = e;` and `s = f(s, e);` must 4256 both be legal. 4257 4258 Params: 4259 range = An $(REF_ALTTEXT input range, isInputRange, std,range,primitives) 4260 Returns: 4261 a range containing the consecutive reduced values. 4262 +/ 4263 auto cumulativeFold(R)(R range) 4264 if (isInputRange!(Unqual!R)) 4265 { 4266 return cumulativeFoldImpl(range); 4267 } 4268 4269 /++ 4270 Seed version. The seed should be a single value if `fun` is a single 4271 function. If `fun` is multiple functions, then `seed` should be a 4272 $(REF Tuple, std,typecons), with one field per function in `f`. 4273 For convenience, if the seed is `const`, or has qualified fields, then 4274 `cumulativeFold` will operate on an unqualified copy. If this happens 4275 then the returned type will not perfectly match `S`. 4276 4277 Params: 4278 range = An $(REF_ALTTEXT input range, isInputRange, std,range,primitives) 4279 seed = the initial value of the accumulator 4280 Returns: 4281 a range containing the consecutive reduced values. 4282 +/ 4283 auto cumulativeFold(R, S)(R range, S seed) 4284 if (isInputRange!(Unqual!R)) 4285 { 4286 static if (fun.length == 1) 4287 return cumulativeFoldImpl(range, seed); 4288 else 4289 return cumulativeFoldImpl(range, seed.expand); 4290 } 4291 4292 private auto cumulativeFoldImpl(R, Args...)(R range, ref Args args) 4293 { 4294 import std.algorithm.internal : algoFormat; 4295 4296 static assert(Args.length == 0 || Args.length == fun.length, 4297 algoFormat("Seed %s does not have the correct amount of fields (should be %s)", 4298 Args.stringof, fun.length)); 4299 4300 static if (args.length) 4301 alias State = staticMap!(Unqual, Args); 4302 else 4303 alias State = staticMap!(ReduceSeedType!(ElementType!R), binfuns); 4304 4305 foreach (i, f; binfuns) 4306 { 4307 static assert(!__traits(compiles, f(args[i], e)) || __traits(compiles, 4308 { args[i] = f(args[i], e); }()), 4309 algoFormat("Incompatible function/seed/element: %s/%s/%s", 4310 fullyQualifiedName!f, Args[i].stringof, E.stringof)); 4311 } 4312 4313 static struct Result 4314 { 4315 private: 4316 R source; 4317 State state; 4318 4319 this(R range, ref Args args) 4320 { 4321 source = range; 4322 if (source.empty) 4323 return; 4324 4325 foreach (i, f; binfuns) 4326 { 4327 static if (args.length) 4328 state[i] = f(args[i], source.front); 4329 else 4330 state[i] = source.front; 4331 } 4332 } 4333 4334 public: 4335 @property bool empty() 4336 { 4337 return source.empty; 4338 } 4339 4340 @property auto front() 4341 { 4342 assert(!empty, "Attempting to fetch the front of an empty cumulativeFold."); 4343 static if (fun.length > 1) 4344 { 4345 import std.typecons : tuple; 4346 return tuple(state); 4347 } 4348 else 4349 { 4350 return state[0]; 4351 } 4352 } 4353 4354 void popFront() 4355 { 4356 assert(!empty, "Attempting to popFront an empty cumulativeFold."); 4357 source.popFront; 4358 4359 if (source.empty) 4360 return; 4361 4362 foreach (i, f; binfuns) 4363 state[i] = f(state[i], source.front); 4364 } 4365 4366 static if (isForwardRange!R) 4367 { 4368 @property auto save() 4369 { 4370 auto result = this; 4371 result.source = source.save; 4372 return result; 4373 } 4374 } 4375 4376 static if (hasLength!R) 4377 { 4378 @property size_t length() 4379 { 4380 return source.length; 4381 } 4382 } 4383 } 4384 4385 return Result(range, args); 4386 } 4387 } 4388 4389 /// 4390 @safe unittest 4391 { 4392 import std.algorithm.comparison : max, min; 4393 import std.array : array; 4394 import std.math : approxEqual; 4395 import std.range : chain; 4396 4397 int[] arr = [1, 2, 3, 4, 5]; 4398 // Partial sum of all elements 4399 auto sum = cumulativeFold!((a, b) => a + b)(arr, 0); 4400 assert(sum.array == [1, 3, 6, 10, 15]); 4401 4402 // Partial sum again, using a string predicate with "a" and "b" 4403 auto sum2 = cumulativeFold!"a + b"(arr, 0); 4404 assert(sum2.array == [1, 3, 6, 10, 15]); 4405 4406 // Compute the partial maximum of all elements 4407 auto largest = cumulativeFold!max(arr); 4408 assert(largest.array == [1, 2, 3, 4, 5]); 4409 4410 // Partial max again, but with Uniform Function Call Syntax (UFCS) 4411 largest = arr.cumulativeFold!max; 4412 assert(largest.array == [1, 2, 3, 4, 5]); 4413 4414 // Partial count of odd elements 4415 auto odds = arr.cumulativeFold!((a, b) => a + (b & 1))(0); 4416 assert(odds.array == [1, 1, 2, 2, 3]); 4417 4418 // Compute the partial sum of squares 4419 auto ssquares = arr.cumulativeFold!((a, b) => a + b * b)(0); 4420 assert(ssquares.array == [1, 5, 14, 30, 55]); 4421 4422 // Chain multiple ranges into seed 4423 int[] a = [3, 4]; 4424 int[] b = [100]; 4425 auto r = cumulativeFold!"a + b"(chain(a, b)); 4426 assert(r.array == [3, 7, 107]); 4427 4428 // Mixing convertible types is fair game, too 4429 double[] c = [2.5, 3.0]; 4430 auto r1 = cumulativeFold!"a + b"(chain(a, b, c)); 4431 assert(approxEqual(r1, [3, 7, 107, 109.5, 112.5])); 4432 4433 // To minimize nesting of parentheses, Uniform Function Call Syntax can be used 4434 auto r2 = chain(a, b, c).cumulativeFold!"a + b"; 4435 assert(approxEqual(r2, [3, 7, 107, 109.5, 112.5])); 4436 } 4437 4438 /** 4439 Sometimes it is very useful to compute multiple aggregates in one pass. 4440 One advantage is that the computation is faster because the looping overhead 4441 is shared. That's why `cumulativeFold` accepts multiple functions. 4442 If two or more functions are passed, `cumulativeFold` returns a $(REF Tuple, 4443 std,typecons) object with one member per passed-in function. 4444 The number of seeds must be correspondingly increased. 4445 */ 4446 @safe unittest 4447 { 4448 import std.algorithm.comparison : max, min; 4449 import std.algorithm.iteration : map; 4450 import std.math : approxEqual; 4451 import std.typecons : tuple; 4452 4453 double[] a = [3.0, 4, 7, 11, 3, 2, 5]; 4454 // Compute minimum and maximum in one pass 4455 auto r = a.cumulativeFold!(min, max); 4456 // The type of r is Tuple!(int, int) 4457 assert(approxEqual(r.map!"a[0]", [3, 3, 3, 3, 3, 2, 2])); // minimum 4458 assert(approxEqual(r.map!"a[1]", [3, 4, 7, 11, 11, 11, 11])); // maximum 4459 4460 // Compute sum and sum of squares in one pass 4461 auto r2 = a.cumulativeFold!("a + b", "a + b * b")(tuple(0.0, 0.0)); 4462 assert(approxEqual(r2.map!"a[0]", [3, 7, 14, 25, 28, 30, 35])); // sum 4463 assert(approxEqual(r2.map!"a[1]", [9, 25, 74, 195, 204, 208, 233])); // sum of squares 4464 } 4465 4466 @safe unittest 4467 { 4468 import std.algorithm.comparison : equal, max, min; 4469 import std.conv : to; 4470 import std.range : chain; 4471 import std.typecons : tuple; 4472 4473 double[] a = [3, 4]; 4474 auto r = a.cumulativeFold!("a + b")(0.0); 4475 assert(r.equal([3, 7])); 4476 auto r2 = cumulativeFold!("a + b")(a); 4477 assert(r2.equal([3, 7])); 4478 auto r3 = cumulativeFold!(min)(a); 4479 assert(r3.equal([3, 3])); 4480 double[] b = [100]; 4481 auto r4 = cumulativeFold!("a + b")(chain(a, b)); 4482 assert(r4.equal([3, 7, 107])); 4483 4484 // two funs 4485 auto r5 = cumulativeFold!("a + b", "a - b")(a, tuple(0.0, 0.0)); 4486 assert(r5.equal([tuple(3, -3), tuple(7, -7)])); 4487 auto r6 = cumulativeFold!("a + b", "a - b")(a); 4488 assert(r6.equal([tuple(3, 3), tuple(7, -1)])); 4489 4490 a = [1, 2, 3, 4, 5]; 4491 // Stringize with commas 4492 auto rep = cumulativeFold!("a ~ `, ` ~ to!string(b)")(a, ""); 4493 assert(rep.map!"a[2 .. $]".equal(["1", "1, 2", "1, 2, 3", "1, 2, 3, 4", "1, 2, 3, 4, 5"])); 4494 4495 // Test for empty range 4496 a = []; 4497 assert(a.cumulativeFold!"a + b".empty); 4498 assert(a.cumulativeFold!"a + b"(2.0).empty); 4499 } 4500 4501 @safe unittest 4502 { 4503 import std.algorithm.comparison : max, min; 4504 import std.array : array; 4505 import std.math : approxEqual; 4506 import std.typecons : tuple; 4507 4508 const float a = 0.0; 4509 const float[] b = [1.2, 3, 3.3]; 4510 float[] c = [1.2, 3, 3.3]; 4511 4512 auto r = cumulativeFold!"a + b"(b, a); 4513 assert(approxEqual(r, [1.2, 4.2, 7.5])); 4514 4515 auto r2 = cumulativeFold!"a + b"(c, a); 4516 assert(approxEqual(r2, [1.2, 4.2, 7.5])); 4517 4518 const numbers = [10, 30, 20]; 4519 enum m = numbers.cumulativeFold!(min).array; 4520 assert(m == [10, 10, 10]); 4521 enum minmax = numbers.cumulativeFold!(min, max).array; 4522 assert(minmax == [tuple(10, 10), tuple(10, 30), tuple(10, 30)]); 4523 } 4524 4525 @safe unittest 4526 { 4527 import std.math : approxEqual; 4528 import std.typecons : tuple; 4529 4530 enum foo = "a + 0.5 * b"; 4531 auto r = [0, 1, 2, 3]; 4532 auto r1 = r.cumulativeFold!foo; 4533 auto r2 = r.cumulativeFold!(foo, foo); 4534 assert(approxEqual(r1, [0, 0.5, 1.5, 3])); 4535 assert(approxEqual(r2.map!"a[0]", [0, 0.5, 1.5, 3])); 4536 assert(approxEqual(r2.map!"a[1]", [0, 0.5, 1.5, 3])); 4537 } 4538 4539 @safe unittest 4540 { 4541 import std.algorithm.comparison : equal, max, min; 4542 import std.array : array; 4543 import std.typecons : tuple; 4544 4545 //Seed is tuple of const. 4546 static auto minmaxElement(alias F = min, alias G = max, R)(in R range) 4547 @safe pure nothrow 4548 if (isInputRange!R) 4549 { 4550 return range.cumulativeFold!(F, G)(tuple(ElementType!R.max, ElementType!R.min)); 4551 } 4552 4553 assert(minmaxElement([1, 2, 3]).equal([tuple(1, 1), tuple(1, 2), tuple(1, 3)])); 4554 } 4555 4556 // https://issues.dlang.org/show_bug.cgi?id=12569 4557 @safe unittest 4558 { 4559 import std.algorithm.comparison : equal, max, min; 4560 import std.typecons : tuple; 4561 4562 dchar c = 'a'; 4563 4564 assert(cumulativeFold!(min, max)("hello", tuple(c, c)).equal([tuple('a', 'h'), 4565 tuple('a', 'h'), tuple('a', 'l'), tuple('a', 'l'), tuple('a', 'o')])); 4566 static assert(!__traits(compiles, cumulativeFold!(min, max)("hello", tuple(c)))); 4567 static assert(!__traits(compiles, cumulativeFold!(min, max)("hello", tuple(c, c, c)))); 4568 4569 //"Seed dchar should be a Tuple" 4570 static assert(!__traits(compiles, cumulativeFold!(min, max)("hello", c))); 4571 //"Seed (dchar) does not have the correct amount of fields (should be 2)" 4572 static assert(!__traits(compiles, cumulativeFold!(min, max)("hello", tuple(c)))); 4573 //"Seed (dchar, dchar, dchar) does not have the correct amount of fields (should be 2)" 4574 static assert(!__traits(compiles, cumulativeFold!(min, max)("hello", tuple(c, c, c)))); 4575 //"Incompatible function/seed/element: all(alias pred = "a")/int/dchar" 4576 static assert(!__traits(compiles, cumulativeFold!all("hello", 1))); 4577 static assert(!__traits(compiles, cumulativeFold!(all, all)("hello", tuple(1, 1)))); 4578 } 4579 4580 // https://issues.dlang.org/show_bug.cgi?id=13304 4581 @safe unittest 4582 { 4583 int[] data; 4584 assert(data.cumulativeFold!((a, b) => a + b).empty); 4585 } 4586 4587 @safe unittest 4588 { 4589 import std.algorithm.comparison : equal; 4590 import std.internal.test.dummyrange : AllDummyRanges, propagatesLength, 4591 propagatesRangeType, RangeType; 4592 4593 foreach (DummyType; AllDummyRanges) 4594 { 4595 DummyType d; 4596 auto m = d.cumulativeFold!"a * b"; 4597 4598 static assert(propagatesLength!(typeof(m), DummyType)); 4599 static if (DummyType.rt <= RangeType.Forward) 4600 static assert(propagatesRangeType!(typeof(m), DummyType)); 4601 4602 assert(m.equal([1, 2, 6, 24, 120, 720, 5040, 40_320, 362_880, 3_628_800])); 4603 } 4604 } 4605 4606 // splitter 4607 /** 4608 Lazily splits a range using an element or range as a separator. 4609 Separator ranges can be any narrow string type or sliceable range type. 4610 4611 Two adjacent separators are considered to surround an empty element in 4612 the split range. Use `filter!(a => !a.empty)` on the result to compress 4613 empty elements. 4614 4615 The predicate is passed to $(REF binaryFun, std,functional) and accepts 4616 any callable function that can be executed via `pred(element, s)`. 4617 4618 Notes: 4619 If splitting a string on whitespace and token compression is desired, 4620 consider using `splitter` without specifying a separator. 4621 4622 If no separator is passed, the $(REF_ALTTEXT, unary, unaryFun, std,functional) 4623 predicate `isTerminator` decides whether to accept an element of `r`. 4624 4625 Params: 4626 pred = The predicate for comparing each element with the separator, 4627 defaulting to `"a == b"`. 4628 r = The $(REF_ALTTEXT input range, isInputRange, std,range,primitives) to be 4629 split. Must support slicing and `.length` or be a narrow string type. 4630 s = The element (or range) to be treated as the separator 4631 between range segments to be split. 4632 isTerminator = The predicate for deciding where to split the range when no separator is passed 4633 4634 Constraints: 4635 The predicate `pred` needs to accept an element of `r` and the 4636 separator `s`. 4637 4638 Returns: 4639 An input range of the subranges of elements between separators. If `r` 4640 is a $(REF_ALTTEXT forward range, isForwardRange, std,range,primitives) 4641 or $(REF_ALTTEXT bidirectional range, isBidirectionalRange, std,range,primitives), 4642 the returned range will be likewise. 4643 When a range is used a separator, bidirectionality isn't possible. 4644 4645 If an empty range is given, the result is an empty range. If a range with 4646 one separator is given, the result is a range with two empty elements. 4647 4648 See_Also: 4649 $(REF _splitter, std,regex) for a version that splits using a regular 4650 expression defined separator and 4651 $(REF _split, std,array) for a version that splits eagerly. 4652 */ 4653 auto splitter(alias pred = "a == b", Range, Separator)(Range r, Separator s) 4654 if (is(typeof(binaryFun!pred(r.front, s)) : bool) 4655 && ((hasSlicing!Range && hasLength!Range) || isNarrowString!Range)) 4656 { 4657 import std.algorithm.searching : find; 4658 import std.conv : unsigned; 4659 4660 struct Result 4661 { 4662 private: 4663 Range _input; 4664 Separator _separator; 4665 // Do we need hasLength!Range? popFront uses _input.length... 4666 enum size_t _unComputed = size_t.max - 1, _atEnd = size_t.max; 4667 size_t _frontLength = _unComputed; 4668 size_t _backLength = _unComputed; 4669 4670 static if (isNarrowString!Range) 4671 { 4672 size_t _separatorLength; 4673 } 4674 else 4675 { 4676 enum _separatorLength = 1; 4677 } 4678 4679 static if (isBidirectionalRange!Range) 4680 { 4681 size_t lastIndexOf(Range haystack, Separator needle) 4682 { 4683 import std.range : retro; 4684 auto r = haystack.retro().find!pred(needle); 4685 return r.retro().length - 1; 4686 } 4687 } 4688 4689 public: 4690 this(Range input, Separator separator) 4691 { 4692 _input = input; 4693 _separator = separator; 4694 4695 static if (isNarrowString!Range) 4696 { 4697 import std.utf : codeLength; 4698 4699 _separatorLength = codeLength!(ElementEncodingType!Range)(separator); 4700 } 4701 if (_input.empty) 4702 _frontLength = _atEnd; 4703 } 4704 4705 static if (isInfinite!Range) 4706 { 4707 enum bool empty = false; 4708 } 4709 else 4710 { 4711 @property bool empty() 4712 { 4713 return _frontLength == _atEnd; 4714 } 4715 } 4716 4717 @property Range front() 4718 { 4719 assert(!empty, "Attempting to fetch the front of an empty splitter."); 4720 if (_frontLength == _unComputed) 4721 { 4722 auto r = _input.find!pred(_separator); 4723 _frontLength = _input.length - r.length; 4724 } 4725 return _input[0 .. _frontLength]; 4726 } 4727 4728 void popFront() 4729 { 4730 assert(!empty, "Attempting to popFront an empty splitter."); 4731 if (_frontLength == _unComputed) 4732 { 4733 front; 4734 } 4735 assert(_frontLength <= _input.length, "The front position must" 4736 ~ " not exceed the input.length"); 4737 if (_frontLength == _input.length) 4738 { 4739 // no more input and need to fetch => done 4740 _frontLength = _atEnd; 4741 4742 // Probably don't need this, but just for consistency: 4743 _backLength = _atEnd; 4744 } 4745 else 4746 { 4747 _input = _input[_frontLength + _separatorLength .. _input.length]; 4748 _frontLength = _unComputed; 4749 } 4750 } 4751 4752 static if (isForwardRange!Range) 4753 { 4754 @property typeof(this) save() 4755 { 4756 auto ret = this; 4757 ret._input = _input.save; 4758 return ret; 4759 } 4760 } 4761 4762 static if (isBidirectionalRange!Range) 4763 { 4764 @property Range back() 4765 { 4766 assert(!empty, "Attempting to fetch the back of an empty splitter."); 4767 if (_backLength == _unComputed) 4768 { 4769 immutable lastIndex = lastIndexOf(_input, _separator); 4770 if (lastIndex == -1) 4771 { 4772 _backLength = _input.length; 4773 } 4774 else 4775 { 4776 _backLength = _input.length - lastIndex - 1; 4777 } 4778 } 4779 return _input[_input.length - _backLength .. _input.length]; 4780 } 4781 4782 void popBack() 4783 { 4784 assert(!empty, "Attempting to popBack an empty splitter."); 4785 if (_backLength == _unComputed) 4786 { 4787 // evaluate back to make sure it's computed 4788 back; 4789 } 4790 assert(_backLength <= _input.length, "The end index must not" 4791 ~ " exceed the length of the input"); 4792 if (_backLength == _input.length) 4793 { 4794 // no more input and need to fetch => done 4795 _frontLength = _atEnd; 4796 _backLength = _atEnd; 4797 } 4798 else 4799 { 4800 _input = _input[0 .. _input.length - _backLength - _separatorLength]; 4801 _backLength = _unComputed; 4802 } 4803 } 4804 } 4805 } 4806 4807 return Result(r, s); 4808 } 4809 4810 /// Basic splitting with characters and numbers. 4811 @safe unittest 4812 { 4813 import std.algorithm.comparison : equal; 4814 4815 assert("a|bc|def".splitter('|').equal([ "a", "bc", "def" ])); 4816 4817 int[] a = [1, 0, 2, 3, 0, 4, 5, 6]; 4818 int[][] w = [ [1], [2, 3], [4, 5, 6] ]; 4819 assert(a.splitter(0).equal(w)); 4820 } 4821 4822 /// Adjacent separators. 4823 @safe unittest 4824 { 4825 import std.algorithm.comparison : equal; 4826 4827 assert("|ab|".splitter('|').equal([ "", "ab", "" ])); 4828 assert("ab".splitter('|').equal([ "ab" ])); 4829 4830 assert("a|b||c".splitter('|').equal([ "a", "b", "", "c" ])); 4831 assert("hello world".splitter(' ').equal([ "hello", "", "world" ])); 4832 4833 auto a = [ 1, 2, 0, 0, 3, 0, 4, 5, 0 ]; 4834 auto w = [ [1, 2], [], [3], [4, 5], [] ]; 4835 assert(a.splitter(0).equal(w)); 4836 } 4837 4838 /// Empty and separator-only ranges. 4839 @safe unittest 4840 { 4841 import std.algorithm.comparison : equal; 4842 import std.range : empty; 4843 4844 assert("".splitter('|').empty); 4845 assert("|".splitter('|').equal([ "", "" ])); 4846 assert("||".splitter('|').equal([ "", "", "" ])); 4847 } 4848 4849 /// Use a range for splitting 4850 @safe unittest 4851 { 4852 import std.algorithm.comparison : equal; 4853 4854 assert("a=>bc=>def".splitter("=>").equal([ "a", "bc", "def" ])); 4855 assert("a|b||c".splitter("||").equal([ "a|b", "c" ])); 4856 assert("hello world".splitter(" ").equal([ "hello", "world" ])); 4857 4858 int[] a = [ 1, 2, 0, 0, 3, 0, 4, 5, 0 ]; 4859 int[][] w = [ [1, 2], [3, 0, 4, 5, 0] ]; 4860 assert(a.splitter([0, 0]).equal(w)); 4861 4862 a = [ 0, 0 ]; 4863 assert(a.splitter([0, 0]).equal([ (int[]).init, (int[]).init ])); 4864 4865 a = [ 0, 0, 1 ]; 4866 assert(a.splitter([0, 0]).equal([ [], [1] ])); 4867 } 4868 4869 /// Custom predicate functions. 4870 @safe unittest 4871 { 4872 import std.algorithm.comparison : equal; 4873 import std.ascii : toLower; 4874 4875 assert("abXcdxef".splitter!"a.toLower == b"('x').equal( 4876 [ "ab", "cd", "ef" ])); 4877 4878 auto w = [ [0], [1], [2] ]; 4879 assert(w.splitter!"a.front == b"(1).equal([ [[0]], [[2]] ])); 4880 } 4881 4882 /// Use splitter without a separator 4883 @safe unittest 4884 { 4885 import std.algorithm.comparison : equal; 4886 import std.range.primitives : front; 4887 4888 assert(equal(splitter!(a => a == '|')("a|bc|def"), [ "a", "bc", "def" ])); 4889 assert(equal(splitter!(a => a == ' ')("hello world"), [ "hello", "", "world" ])); 4890 4891 int[] a = [ 1, 2, 0, 0, 3, 0, 4, 5, 0 ]; 4892 int[][] w = [ [1, 2], [], [3], [4, 5], [] ]; 4893 assert(equal(splitter!(a => a == 0)(a), w)); 4894 4895 a = [ 0 ]; 4896 assert(equal(splitter!(a => a == 0)(a), [ (int[]).init, (int[]).init ])); 4897 4898 a = [ 0, 1 ]; 4899 assert(equal(splitter!(a => a == 0)(a), [ [], [1] ])); 4900 4901 w = [ [0], [1], [2] ]; 4902 assert(equal(splitter!(a => a.front == 1)(w), [ [[0]], [[2]] ])); 4903 } 4904 4905 /// Leading separators, trailing separators, or no separators. 4906 @safe unittest 4907 { 4908 import std.algorithm.comparison : equal; 4909 4910 assert("|ab|".splitter('|').equal([ "", "ab", "" ])); 4911 assert("ab".splitter('|').equal([ "ab" ])); 4912 } 4913 4914 /// Splitter returns bidirectional ranges if the delimiter is a single element 4915 @safe unittest 4916 { 4917 import std.algorithm.comparison : equal; 4918 import std.range : retro; 4919 assert("a|bc|def".splitter('|').retro.equal([ "def", "bc", "a" ])); 4920 } 4921 4922 /// Splitting by word lazily 4923 @safe unittest 4924 { 4925 import std.ascii : isWhite; 4926 import std.algorithm.comparison : equal; 4927 import std.algorithm.iteration : splitter; 4928 4929 string str = "Hello World!"; 4930 assert(str.splitter!(isWhite).equal(["Hello", "World!"])); 4931 } 4932 4933 @safe unittest 4934 { 4935 import std.algorithm; 4936 import std.array : array; 4937 import std.internal.test.dummyrange; 4938 import std.range : retro; 4939 4940 assert(equal(splitter("hello world", ' '), [ "hello", "", "world" ])); 4941 assert(equal(splitter("žlutoučkýřkůň", 'ř'), [ "žlutoučký", "kůň" ])); 4942 int[] a = [ 1, 2, 0, 0, 3, 0, 4, 5, 0 ]; 4943 int[][] w = [ [1, 2], [], [3], [4, 5], [] ]; 4944 static assert(isForwardRange!(typeof(splitter(a, 0)))); 4945 4946 assert(equal(splitter(a, 0), w)); 4947 a = null; 4948 assert(equal(splitter(a, 0), (int[][]).init)); 4949 a = [ 0 ]; 4950 assert(equal(splitter(a, 0), [ (int[]).init, (int[]).init ][])); 4951 a = [ 0, 1 ]; 4952 assert(equal(splitter(a, 0), [ [], [1] ])); 4953 assert(equal(splitter(a, 0), [ [], [1] ][])); 4954 4955 // Thoroughly exercise the bidirectional stuff. 4956 auto str = "abc abcd abcde ab abcdefg abcdefghij ab ac ar an at ada"; 4957 assert(equal( 4958 retro(splitter(str, 'a')), 4959 retro(array(splitter(str, 'a'))) 4960 )); 4961 4962 // Test interleaving front and back. 4963 auto split = splitter(str, 'a'); 4964 assert(split.front == ""); 4965 assert(split.back == ""); 4966 split.popBack(); 4967 assert(split.back == "d"); 4968 split.popFront(); 4969 assert(split.front == "bc "); 4970 assert(split.back == "d"); 4971 split.popFront(); 4972 split.popBack(); 4973 assert(split.back == "t "); 4974 split.popBack(); 4975 split.popBack(); 4976 split.popFront(); 4977 split.popFront(); 4978 assert(split.front == "b "); 4979 assert(split.back == "r "); 4980 4981 // https://issues.dlang.org/show_bug.cgi?id=4408 4982 foreach (DummyType; AllDummyRanges) 4983 { 4984 static if (isRandomAccessRange!DummyType) 4985 { 4986 static assert(isBidirectionalRange!DummyType); 4987 DummyType d; 4988 auto s = splitter(d, 5); 4989 assert(equal(s.front, [1,2,3,4])); 4990 assert(equal(s.back, [6,7,8,9,10])); 4991 4992 auto s2 = splitter(d, [4, 5]); 4993 assert(equal(s2.front, [1,2,3])); 4994 } 4995 } 4996 } 4997 @safe unittest 4998 { 4999 import std.algorithm; 5000 import std.range; 5001 auto L = retro(iota(1L, 10L)); 5002 auto s = splitter(L, 5L); 5003 assert(equal(s.front, [9L, 8L, 7L, 6L])); 5004 s.popFront(); 5005 assert(equal(s.front, [4L, 3L, 2L, 1L])); 5006 s.popFront(); 5007 assert(s.empty); 5008 } 5009 5010 // https://issues.dlang.org/show_bug.cgi?id=18470 5011 @safe unittest 5012 { 5013 import std.algorithm.comparison : equal; 5014 5015 const w = [[0], [1], [2]]; 5016 assert(w.splitter!((a, b) => a.front() == b)(1).equal([[[0]], [[2]]])); 5017 } 5018 5019 // https://issues.dlang.org/show_bug.cgi?id=18470 5020 @safe unittest 5021 { 5022 import std.algorithm.comparison : equal; 5023 import std.ascii : toLower; 5024 5025 assert("abXcdxef".splitter!"a.toLower == b"('x').equal(["ab", "cd", "ef"])); 5026 assert("abXcdxef".splitter!((a, b) => a.toLower == b)('x').equal(["ab", "cd", "ef"])); 5027 } 5028 5029 /// ditto 5030 auto splitter(alias pred = "a == b", Range, Separator)(Range r, Separator s) 5031 if (is(typeof(binaryFun!pred(r.front, s.front)) : bool) 5032 && (hasSlicing!Range || isNarrowString!Range) 5033 && isForwardRange!Separator 5034 && (hasLength!Separator || isNarrowString!Separator)) 5035 { 5036 import std.algorithm.searching : find; 5037 import std.conv : unsigned; 5038 5039 static struct Result 5040 { 5041 private: 5042 Range _input; 5043 Separator _separator; 5044 // _frontLength == size_t.max means empty 5045 size_t _frontLength = size_t.max; 5046 5047 @property auto separatorLength() { return _separator.length; } 5048 5049 void ensureFrontLength() 5050 { 5051 if (_frontLength != _frontLength.max) return; 5052 assert(!_input.empty, "The input must not be empty"); 5053 // compute front length 5054 _frontLength = (_separator.empty) ? 1 : 5055 _input.length - find!pred(_input, _separator).length; 5056 } 5057 5058 public: 5059 this(Range input, Separator separator) 5060 { 5061 _input = input; 5062 _separator = separator; 5063 } 5064 5065 @property Range front() 5066 { 5067 assert(!empty, "Attempting to fetch the front of an empty splitter."); 5068 ensureFrontLength(); 5069 return _input[0 .. _frontLength]; 5070 } 5071 5072 static if (isInfinite!Range) 5073 { 5074 enum bool empty = false; // Propagate infiniteness 5075 } 5076 else 5077 { 5078 @property bool empty() 5079 { 5080 return _frontLength == size_t.max && _input.empty; 5081 } 5082 } 5083 5084 void popFront() 5085 { 5086 assert(!empty, "Attempting to popFront an empty splitter."); 5087 ensureFrontLength(); 5088 if (_frontLength == _input.length) 5089 { 5090 // done, there's no separator in sight 5091 _input = _input[_frontLength .. _frontLength]; 5092 _frontLength = _frontLength.max; 5093 return; 5094 } 5095 if (_frontLength + separatorLength == _input.length) 5096 { 5097 // Special case: popping the first-to-last item; there is 5098 // an empty item right after this. 5099 _input = _input[_input.length .. _input.length]; 5100 _frontLength = 0; 5101 return; 5102 } 5103 // Normal case, pop one item and the separator, get ready for 5104 // reading the next item 5105 _input = _input[_frontLength + separatorLength .. _input.length]; 5106 // mark _frontLength as uninitialized 5107 _frontLength = _frontLength.max; 5108 } 5109 5110 static if (isForwardRange!Range) 5111 { 5112 @property typeof(this) save() 5113 { 5114 auto ret = this; 5115 ret._input = _input.save; 5116 return ret; 5117 } 5118 } 5119 } 5120 5121 return Result(r, s); 5122 } 5123 5124 @safe unittest 5125 { 5126 import std.algorithm.comparison : equal; 5127 import std.typecons : Tuple; 5128 5129 alias C = Tuple!(int, "x", int, "y"); 5130 auto a = [C(1,0), C(2,0), C(3,1), C(4,0)]; 5131 assert(equal(splitter!"a.x == b"(a, [2, 3]), [ [C(1,0)], [C(4,0)] ])); 5132 } 5133 5134 @safe unittest 5135 { 5136 import std.algorithm.comparison : equal; 5137 import std.array : split; 5138 import std.conv : text; 5139 5140 auto s = ",abc, de, fg,hi,"; 5141 auto sp0 = splitter(s, ','); 5142 assert(equal(sp0, ["", "abc", " de", " fg", "hi", ""][])); 5143 5144 auto s1 = ", abc, de, fg, hi, "; 5145 auto sp1 = splitter(s1, ", "); 5146 assert(equal(sp1, ["", "abc", "de", " fg", "hi", ""][])); 5147 static assert(isForwardRange!(typeof(sp1))); 5148 5149 int[] a = [ 1, 2, 0, 3, 0, 4, 5, 0 ]; 5150 int[][] w = [ [1, 2], [3], [4, 5], [] ]; 5151 uint i; 5152 foreach (e; splitter(a, 0)) 5153 { 5154 assert(i < w.length); 5155 assert(e == w[i++]); 5156 } 5157 assert(i == w.length); 5158 5159 wstring names = ",peter,paul,jerry,"; 5160 auto words = split(names, ","); 5161 assert(walkLength(words) == 5, text(walkLength(words))); 5162 } 5163 5164 @safe unittest 5165 { 5166 int[][] a = [ [1], [2], [0], [3], [0], [4], [5], [0] ]; 5167 int[][][] w = [ [[1], [2]], [[3]], [[4], [5]], [] ]; 5168 uint i; 5169 foreach (e; splitter!"a.front == 0"(a, 0)) 5170 { 5171 assert(i < w.length); 5172 assert(e == w[i++]); 5173 } 5174 assert(i == w.length); 5175 } 5176 5177 @safe unittest 5178 { 5179 import std.algorithm.comparison : equal; 5180 auto s6 = ","; 5181 auto sp6 = splitter(s6, ','); 5182 foreach (e; sp6) {} 5183 assert(equal(sp6, ["", ""][])); 5184 } 5185 5186 // https://issues.dlang.org/show_bug.cgi?id=10773 5187 @safe unittest 5188 { 5189 import std.algorithm.comparison : equal; 5190 5191 auto s = splitter("abc", ""); 5192 assert(s.equal(["a", "b", "c"])); 5193 } 5194 5195 @safe unittest 5196 { 5197 import std.algorithm.comparison : equal; 5198 5199 // Test by-reference separator 5200 class RefSep { 5201 @safe: 5202 string _impl; 5203 this(string s) { _impl = s; } 5204 @property empty() { return _impl.empty; } 5205 @property auto front() { return _impl.front; } 5206 void popFront() { _impl = _impl[1..$]; } 5207 @property RefSep save() scope { return new RefSep(_impl); } 5208 @property auto length() { return _impl.length; } 5209 } 5210 auto sep = new RefSep("->"); 5211 auto data = "i->am->pointing"; 5212 auto words = splitter(data, sep); 5213 assert(words.equal([ "i", "am", "pointing" ])); 5214 } 5215 5216 /// ditto 5217 auto splitter(alias isTerminator, Range)(Range r) 5218 if (isForwardRange!Range && is(typeof(unaryFun!isTerminator(r.front)))) 5219 { 5220 return SplitterResult!(unaryFun!isTerminator, Range)(r); 5221 } 5222 5223 private struct SplitterResult(alias isTerminator, Range) 5224 { 5225 import std.algorithm.searching : find; 5226 enum fullSlicing = (hasLength!Range && hasSlicing!Range) || isSomeString!Range; 5227 5228 private Range _input; 5229 private size_t _end = 0; 5230 static if (!fullSlicing) 5231 private Range _next; 5232 5233 private void findTerminator() 5234 { 5235 static if (fullSlicing) 5236 { 5237 auto r = find!isTerminator(_input.save); 5238 _end = _input.length - r.length; 5239 } 5240 else 5241 for ( _end = 0; !_next.empty ; _next.popFront) 5242 { 5243 if (isTerminator(_next.front)) 5244 break; 5245 ++_end; 5246 } 5247 } 5248 5249 this(Range input) 5250 { 5251 _input = input; 5252 static if (!fullSlicing) 5253 _next = _input.save; 5254 5255 if (!_input.empty) 5256 findTerminator(); 5257 else 5258 _end = size_t.max; 5259 } 5260 5261 static if (fullSlicing) 5262 { 5263 private this(Range input, size_t end) 5264 { 5265 _input = input; 5266 _end = end; 5267 } 5268 } 5269 else 5270 { 5271 private this(Range input, size_t end, Range next) 5272 { 5273 _input = input; 5274 _end = end; 5275 _next = next; 5276 } 5277 } 5278 5279 static if (isInfinite!Range) 5280 { 5281 enum bool empty = false; // Propagate infiniteness. 5282 } 5283 else 5284 { 5285 @property bool empty() 5286 { 5287 return _end == size_t.max; 5288 } 5289 } 5290 5291 @property auto front() 5292 { 5293 version (assert) 5294 { 5295 import core.exception : RangeError; 5296 if (empty) 5297 throw new RangeError(); 5298 } 5299 static if (fullSlicing) 5300 return _input[0 .. _end]; 5301 else 5302 { 5303 import std.range : takeExactly; 5304 return _input.takeExactly(_end); 5305 } 5306 } 5307 5308 void popFront() 5309 { 5310 version (assert) 5311 { 5312 import core.exception : RangeError; 5313 if (empty) 5314 throw new RangeError(); 5315 } 5316 5317 static if (fullSlicing) 5318 { 5319 _input = _input[_end .. _input.length]; 5320 if (_input.empty) 5321 { 5322 _end = size_t.max; 5323 return; 5324 } 5325 _input.popFront(); 5326 } 5327 else 5328 { 5329 if (_next.empty) 5330 { 5331 _input = _next; 5332 _end = size_t.max; 5333 return; 5334 } 5335 _next.popFront(); 5336 _input = _next.save; 5337 } 5338 findTerminator(); 5339 } 5340 5341 @property typeof(this) save() 5342 { 5343 static if (fullSlicing) 5344 return SplitterResult(_input.save, _end); 5345 else 5346 return SplitterResult(_input.save, _end, _next.save); 5347 } 5348 } 5349 5350 @safe unittest 5351 { 5352 import std.algorithm.comparison : equal; 5353 import std.range : iota; 5354 5355 auto L = iota(1L, 10L); 5356 auto s = splitter(L, [5L, 6L]); 5357 assert(equal(s.front, [1L, 2L, 3L, 4L])); 5358 s.popFront(); 5359 assert(equal(s.front, [7L, 8L, 9L])); 5360 s.popFront(); 5361 assert(s.empty); 5362 } 5363 5364 @safe unittest 5365 { 5366 import std.algorithm.comparison : equal; 5367 import std.algorithm.internal : algoFormat; 5368 import std.internal.test.dummyrange; 5369 5370 void compare(string sentence, string[] witness) 5371 { 5372 auto r = splitter!"a == ' '"(sentence); 5373 assert(equal(r.save, witness), algoFormat("got: %(%s, %) expected: %(%s, %)", r, witness)); 5374 } 5375 5376 compare(" Mary has a little lamb. ", 5377 ["", "Mary", "", "has", "a", "little", "lamb.", "", "", ""]); 5378 compare("Mary has a little lamb. ", 5379 ["Mary", "", "has", "a", "little", "lamb.", "", "", ""]); 5380 compare("Mary has a little lamb.", 5381 ["Mary", "", "has", "a", "little", "lamb."]); 5382 compare("", (string[]).init); 5383 compare(" ", ["", ""]); 5384 5385 static assert(isForwardRange!(typeof(splitter!"a == ' '"("ABC")))); 5386 5387 foreach (DummyType; AllDummyRanges) 5388 { 5389 static if (isRandomAccessRange!DummyType) 5390 { 5391 auto rangeSplit = splitter!"a == 5"(DummyType.init); 5392 assert(equal(rangeSplit.front, [1,2,3,4])); 5393 rangeSplit.popFront(); 5394 assert(equal(rangeSplit.front, [6,7,8,9,10])); 5395 } 5396 } 5397 } 5398 5399 @safe unittest 5400 { 5401 import std.algorithm.comparison : equal; 5402 import std.algorithm.internal : algoFormat; 5403 import std.range; 5404 5405 struct Entry 5406 { 5407 int low; 5408 int high; 5409 int[][] result; 5410 } 5411 Entry[] entries = [ 5412 Entry(0, 0, []), 5413 Entry(0, 1, [[0]]), 5414 Entry(1, 2, [[], []]), 5415 Entry(2, 7, [[2], [4], [6]]), 5416 Entry(1, 8, [[], [2], [4], [6], []]), 5417 ]; 5418 foreach ( entry ; entries ) 5419 { 5420 auto a = iota(entry.low, entry.high).filter!"true"(); 5421 auto b = splitter!"a%2"(a); 5422 assert(equal!equal(b.save, entry.result), algoFormat("got: %(%s, %) expected: %(%s, %)", b, entry.result)); 5423 } 5424 } 5425 5426 @safe unittest 5427 { 5428 import std.algorithm.comparison : equal; 5429 import std.uni : isWhite; 5430 5431 // https://issues.dlang.org/show_bug.cgi?id=6791 5432 assert(equal( 5433 splitter("là dove terminava quella valle"), 5434 ["là", "dove", "terminava", "quella", "valle"] 5435 )); 5436 assert(equal( 5437 splitter!(std.uni.isWhite)("là dove terminava quella valle"), 5438 ["là", "dove", "terminava", "quella", "valle"] 5439 )); 5440 assert(equal(splitter!"a=='本'"("日本語"), ["日", "語"])); 5441 } 5442 5443 // https://issues.dlang.org/show_bug.cgi?id=18657 5444 pure @safe unittest 5445 { 5446 import std.algorithm.comparison : equal; 5447 import std.range : refRange; 5448 string s = "foobar"; 5449 auto r = refRange(&s).splitter!(c => c == 'b'); 5450 assert(equal!equal(r.save, ["foo", "ar"])); 5451 assert(equal!equal(r.save, ["foo", "ar"])); 5452 } 5453 5454 /++ 5455 Lazily splits the character-based range `s` into words, using whitespace as the 5456 delimiter. 5457 5458 This function is character-range specific and, contrary to 5459 `splitter!(std.uni.isWhite)`, runs of whitespace will be merged together 5460 (no empty tokens will be produced). 5461 5462 Params: 5463 s = The character-based range to be split. Must be a string, or a 5464 random-access range of character types. 5465 5466 Returns: 5467 An $(REF_ALTTEXT input range, isInputRange, std,range,primitives) of slices of 5468 the original range split by whitespace. 5469 +/ 5470 auto splitter(Range)(Range s) 5471 if (isSomeString!Range || 5472 isRandomAccessRange!Range && hasLength!Range && hasSlicing!Range && 5473 !isConvertibleToString!Range && 5474 isSomeChar!(ElementEncodingType!Range)) 5475 { 5476 import std.algorithm.searching : find; 5477 static struct Result 5478 { 5479 private: 5480 import core.exception : RangeError; 5481 Range _s; 5482 size_t _frontLength; 5483 5484 void getFirst() 5485 { 5486 import std.uni : isWhite; 5487 import std.traits : Unqual; 5488 5489 static if (is(immutable ElementEncodingType!Range == immutable wchar) && 5490 is(immutable ElementType!Range == immutable dchar)) 5491 { 5492 // all unicode whitespace characters fit into a wchar. However, 5493 // this range is a wchar array, so we will treat it like a 5494 // wchar array instead of decoding each code point. 5495 _frontLength = _s.length; // default condition, no spaces 5496 foreach (i; 0 .. _s.length) 5497 if (isWhite(_s[i])) 5498 { 5499 _frontLength = i; 5500 break; 5501 } 5502 } 5503 else static if (is(immutable ElementType!Range == immutable dchar) || 5504 is(immutable ElementType!Range == immutable wchar)) 5505 { 5506 // dchar or wchar range, we can just use find. 5507 auto r = find!(isWhite)(_s.save); 5508 _frontLength = _s.length - r.length; 5509 } 5510 else 5511 { 5512 // need to decode the characters until we find a space. This is 5513 // ported from std.string.stripLeft. 5514 static import std.ascii; 5515 static import std.uni; 5516 import std.utf : decodeFront; 5517 5518 auto input = _s.save; 5519 size_t iLength = input.length; 5520 5521 while (!input.empty) 5522 { 5523 auto c = input.front; 5524 if (std.ascii.isASCII(c)) 5525 { 5526 if (std.ascii.isWhite(c)) 5527 break; 5528 input.popFront(); 5529 --iLength; 5530 } 5531 else 5532 { 5533 auto dc = decodeFront(input); 5534 if (std.uni.isWhite(dc)) 5535 break; 5536 iLength = input.length; 5537 } 5538 } 5539 5540 // sanity check 5541 assert(iLength <= _s.length, "The current index must not" 5542 ~ " exceed the length of the input"); 5543 5544 _frontLength = _s.length - iLength; 5545 } 5546 } 5547 5548 public: 5549 this(Range s) 5550 { 5551 import std..string : stripLeft; 5552 _s = s.stripLeft(); 5553 getFirst(); 5554 } 5555 5556 @property auto front() 5557 { 5558 version (assert) if (empty) throw new RangeError(); 5559 return _s[0 .. _frontLength]; 5560 } 5561 5562 void popFront() 5563 { 5564 import std..string : stripLeft; 5565 version (assert) if (empty) throw new RangeError(); 5566 _s = _s[_frontLength .. $].stripLeft(); 5567 getFirst(); 5568 } 5569 5570 @property bool empty() const 5571 { 5572 return _s.empty; 5573 } 5574 5575 @property inout(Result) save() inout @safe pure nothrow 5576 { 5577 return this; 5578 } 5579 } 5580 return Result(s); 5581 } 5582 5583 /// 5584 @safe pure unittest 5585 { 5586 import std.algorithm.comparison : equal; 5587 auto a = " a bcd ef gh "; 5588 assert(equal(splitter(a), ["a", "bcd", "ef", "gh"][])); 5589 } 5590 5591 @safe pure unittest 5592 { 5593 import std.algorithm.comparison : equal; 5594 import std.meta : AliasSeq; 5595 static foreach (S; AliasSeq!(string, wstring, dstring)) 5596 {{ 5597 import std.conv : to; 5598 S a = " a \u2028 bcd ef gh "; 5599 assert(equal(splitter(a), [to!S("a"), to!S("bcd"), to!S("ef"), to!S("gh")])); 5600 a = ""; 5601 assert(splitter(a).empty); 5602 }} 5603 5604 immutable string s = " a bcd ef gh "; 5605 assert(equal(splitter(s), ["a", "bcd", "ef", "gh"][])); 5606 } 5607 5608 @safe unittest 5609 { 5610 import std.conv : to; 5611 import std..string : strip; 5612 5613 // TDPL example, page 8 5614 uint[string] dictionary; 5615 char[][3] lines; 5616 lines[0] = "line one".dup; 5617 lines[1] = "line \ttwo".dup; 5618 lines[2] = "yah last line\ryah".dup; 5619 foreach (line; lines) 5620 { 5621 foreach (word; splitter(strip(line))) 5622 { 5623 if (word in dictionary) continue; // Nothing to do 5624 auto newID = dictionary.length; 5625 dictionary[to!string(word)] = cast(uint) newID; 5626 } 5627 } 5628 assert(dictionary.length == 5); 5629 assert(dictionary["line"]== 0); 5630 assert(dictionary["one"]== 1); 5631 assert(dictionary["two"]== 2); 5632 assert(dictionary["yah"]== 3); 5633 assert(dictionary["last"]== 4); 5634 5635 } 5636 5637 @safe unittest 5638 { 5639 // do it with byCodeUnit 5640 import std.conv : to; 5641 import std..string : strip; 5642 import std.utf : byCodeUnit; 5643 5644 alias BCU = typeof("abc".byCodeUnit()); 5645 5646 // TDPL example, page 8 5647 uint[BCU] dictionary; 5648 BCU[3] lines; 5649 lines[0] = "line one".byCodeUnit; 5650 lines[1] = "line \ttwo".byCodeUnit; 5651 lines[2] = "yah last line\ryah".byCodeUnit; 5652 foreach (line; lines) 5653 { 5654 foreach (word; splitter(strip(line))) 5655 { 5656 static assert(is(typeof(word) == BCU)); 5657 if (word in dictionary) continue; // Nothing to do 5658 auto newID = dictionary.length; 5659 dictionary[word] = cast(uint) newID; 5660 } 5661 } 5662 assert(dictionary.length == 5); 5663 assert(dictionary["line".byCodeUnit]== 0); 5664 assert(dictionary["one".byCodeUnit]== 1); 5665 assert(dictionary["two".byCodeUnit]== 2); 5666 assert(dictionary["yah".byCodeUnit]== 3); 5667 assert(dictionary["last".byCodeUnit]== 4); 5668 } 5669 5670 // https://issues.dlang.org/show_bug.cgi?id=19238 5671 @safe pure unittest 5672 { 5673 import std.utf : byCodeUnit; 5674 import std.algorithm.comparison : equal; 5675 auto range = "hello world".byCodeUnit.splitter; 5676 static assert(is(typeof(range.front()) == typeof("hello".byCodeUnit()))); 5677 assert(range.equal(["hello".byCodeUnit, "world".byCodeUnit])); 5678 5679 // test other space types, including unicode 5680 auto u = " a\t\v\r bcd\u3000 \u2028\t\nef\U00010001 gh"; 5681 assert(equal(splitter(u), ["a", "bcd", "ef\U00010001", "gh"][])); 5682 assert(equal(splitter(u.byCodeUnit), ["a".byCodeUnit, "bcd".byCodeUnit, 5683 "ef\U00010001".byCodeUnit, "gh".byCodeUnit][])); 5684 } 5685 5686 @safe unittest 5687 { 5688 import std.algorithm.comparison : equal; 5689 import std.algorithm.internal : algoFormat; 5690 import std.array : split; 5691 import std.conv : text; 5692 5693 // Check consistency: 5694 // All flavors of split should produce the same results 5695 foreach (input; [(int[]).init, 5696 [0], 5697 [0, 1, 0], 5698 [1, 1, 0, 0, 1, 1], 5699 ]) 5700 { 5701 foreach (s; [0, 1]) 5702 { 5703 auto result = split(input, s); 5704 5705 assert(equal(result, split(input, [s])), algoFormat(`"[%(%s,%)]"`, split(input, [s]))); 5706 //assert(equal(result, split(input, [s].filter!"true"()))); //Not yet implemented 5707 assert(equal(result, split!((a) => a == s)(input)), text(split!((a) => a == s)(input))); 5708 5709 //assert(equal!equal(result, split(input.filter!"true"(), s))); //Not yet implemented 5710 //assert(equal!equal(result, split(input.filter!"true"(), [s]))); //Not yet implemented 5711 //assert(equal!equal(result, split(input.filter!"true"(), [s].filter!"true"()))); //Not yet implemented 5712 assert(equal!equal(result, split!((a) => a == s)(input.filter!"true"()))); 5713 5714 assert(equal(result, splitter(input, s))); 5715 assert(equal(result, splitter(input, [s]))); 5716 //assert(equal(result, splitter(input, [s].filter!"true"()))); //Not yet implemented 5717 assert(equal(result, splitter!((a) => a == s)(input))); 5718 5719 //assert(equal!equal(result, splitter(input.filter!"true"(), s))); //Not yet implemented 5720 //assert(equal!equal(result, splitter(input.filter!"true"(), [s]))); //Not yet implemented 5721 //assert(equal!equal(result, splitter(input.filter!"true"(), [s].filter!"true"()))); //Not yet implemented 5722 assert(equal!equal(result, splitter!((a) => a == s)(input.filter!"true"()))); 5723 } 5724 } 5725 foreach (input; [string.init, 5726 " ", 5727 " hello ", 5728 "hello hello", 5729 " hello what heck this ? " 5730 ]) 5731 { 5732 foreach (s; [' ', 'h']) 5733 { 5734 auto result = split(input, s); 5735 5736 assert(equal(result, split(input, [s]))); 5737 //assert(equal(result, split(input, [s].filter!"true"()))); //Not yet implemented 5738 assert(equal(result, split!((a) => a == s)(input))); 5739 5740 //assert(equal!equal(result, split(input.filter!"true"(), s))); //Not yet implemented 5741 //assert(equal!equal(result, split(input.filter!"true"(), [s]))); //Not yet implemented 5742 //assert(equal!equal(result, split(input.filter!"true"(), [s].filter!"true"()))); //Not yet implemented 5743 assert(equal!equal(result, split!((a) => a == s)(input.filter!"true"()))); 5744 5745 assert(equal(result, splitter(input, s))); 5746 assert(equal(result, splitter(input, [s]))); 5747 //assert(equal(result, splitter(input, [s].filter!"true"()))); //Not yet implemented 5748 assert(equal(result, splitter!((a) => a == s)(input))); 5749 5750 //assert(equal!equal(result, splitter(input.filter!"true"(), s))); //Not yet implemented 5751 //assert(equal!equal(result, splitter(input.filter!"true"(), [s]))); //Not yet implemented 5752 //assert(equal!equal(result, splitter(input.filter!"true"(), [s].filter!"true"()))); //Not yet implemented 5753 assert(equal!equal(result, splitter!((a) => a == s)(input.filter!"true"()))); 5754 } 5755 } 5756 } 5757 5758 // In same combinations substitute needs to calculate the auto-decoded length 5759 // of its needles 5760 private template hasDifferentAutodecoding(Range, Needles...) 5761 { 5762 import std.meta : anySatisfy; 5763 /* iff 5764 - the needles needs auto-decoding, but the incoming range doesn't (or vice versa) 5765 - both (range, needle) need auto-decoding and don't share the same common type 5766 */ 5767 enum needlesAreNarrow = anySatisfy!(isNarrowString, Needles); 5768 enum sourceIsNarrow = isNarrowString!Range; 5769 enum hasDifferentAutodecoding = sourceIsNarrow != needlesAreNarrow || 5770 (sourceIsNarrow && needlesAreNarrow && 5771 is(CommonType!(Range, Needles) == void)); 5772 } 5773 5774 @safe nothrow @nogc pure unittest 5775 { 5776 import std.meta : AliasSeq; // used for better clarity 5777 5778 static assert(!hasDifferentAutodecoding!(string, AliasSeq!(string, string))); 5779 static assert(!hasDifferentAutodecoding!(wstring, AliasSeq!(wstring, wstring))); 5780 static assert(!hasDifferentAutodecoding!(dstring, AliasSeq!(dstring, dstring))); 5781 5782 // the needles needs auto-decoding, but the incoming range doesn't (or vice versa) 5783 static assert(hasDifferentAutodecoding!(string, AliasSeq!(wstring, wstring))); 5784 static assert(hasDifferentAutodecoding!(string, AliasSeq!(dstring, dstring))); 5785 static assert(hasDifferentAutodecoding!(wstring, AliasSeq!(string, string))); 5786 static assert(hasDifferentAutodecoding!(wstring, AliasSeq!(dstring, dstring))); 5787 static assert(hasDifferentAutodecoding!(dstring, AliasSeq!(string, string))); 5788 static assert(hasDifferentAutodecoding!(dstring, AliasSeq!(wstring, wstring))); 5789 5790 // both (range, needle) need auto-decoding and don't share the same common type 5791 static foreach (T; AliasSeq!(string, wstring, dstring)) 5792 { 5793 static assert(hasDifferentAutodecoding!(T, AliasSeq!(wstring, string))); 5794 static assert(hasDifferentAutodecoding!(T, AliasSeq!(dstring, string))); 5795 static assert(hasDifferentAutodecoding!(T, AliasSeq!(wstring, dstring))); 5796 } 5797 } 5798 5799 // substitute 5800 /** 5801 Returns a range with all occurrences of `substs` in `r`. 5802 replaced with their substitution. 5803 5804 Single value replacements (`'ö'.substitute!('ä', 'a', 'ö', 'o', 'ü', 'u)`) are 5805 supported as well and in $(BIGOH 1). 5806 5807 Params: 5808 r = an $(REF_ALTTEXT input range, isInputRange, std,range,primitives) 5809 value = a single value which can be substituted in $(BIGOH 1) 5810 substs = a set of replacements/substitutions 5811 pred = the equality function to test if element(s) are equal to 5812 a substitution 5813 5814 Returns: a range with the substitutions replaced. 5815 5816 See_Also: 5817 $(REF replace, std, array) for an eager replace algorithm or 5818 $(REF translate, std, string), and $(REF tr, std, string) 5819 for string algorithms with translation tables. 5820 */ 5821 template substitute(substs...) 5822 if (substs.length >= 2 && isExpressions!substs) 5823 { 5824 import std.range.primitives : ElementType; 5825 import std.traits : CommonType; 5826 5827 static assert(!(substs.length & 1), "The number of substitution parameters must be even"); 5828 5829 /** 5830 Substitute single values with compile-time substitution mappings. 5831 Complexity: $(BIGOH 1) due to D's `switch` guaranteeing $(BIGOH 1); 5832 */ 5833 auto substitute(Value)(Value value) 5834 if (isInputRange!Value || !is(CommonType!(Value, typeof(substs[0])) == void)) 5835 { 5836 static if (isInputRange!Value) 5837 { 5838 static if (!is(CommonType!(ElementType!Value, typeof(substs[0])) == void)) 5839 { 5840 // Substitute single range elements with compile-time substitution mappings 5841 return value.map!(a => substitute(a)); 5842 } 5843 else static if (isInputRange!Value && 5844 !is(CommonType!(ElementType!Value, ElementType!(typeof(substs[0]))) == void)) 5845 { 5846 // not implemented yet, fallback to runtime variant for now 5847 return .substitute(value, substs); 5848 } 5849 else 5850 { 5851 static assert(0, `Compile-time substitutions must be elements or ranges of the same type of ` ~ 5852 Value.stringof ~ `.`); 5853 } 5854 } 5855 // Substitute single values with compile-time substitution mappings. 5856 else // static if (!is(CommonType!(Value, typeof(substs[0])) == void)) 5857 { 5858 switch (value) 5859 { 5860 static foreach (i; 0 .. substs.length / 2) 5861 case substs[2 * i]: 5862 return substs[2 * i + 1]; 5863 5864 default: return value; 5865 } 5866 } 5867 } 5868 } 5869 5870 /// ditto 5871 auto substitute(alias pred = (a, b) => a == b, R, Substs...)(R r, Substs substs) 5872 if (isInputRange!R && Substs.length >= 2 && !is(CommonType!(Substs) == void)) 5873 { 5874 import std.range.primitives : ElementType; 5875 import std.meta : allSatisfy; 5876 import std.traits : CommonType; 5877 5878 static assert(!(Substs.length & 1), "The number of substitution parameters must be even"); 5879 5880 enum n = Substs.length / 2; 5881 5882 // Substitute individual elements 5883 static if (!is(CommonType!(ElementType!R, Substs) == void)) 5884 { 5885 import std.functional : binaryFun; 5886 5887 // Imitate a value closure to be @nogc 5888 static struct ReplaceElement 5889 { 5890 private Substs substs; 5891 5892 this(Substs substs) 5893 { 5894 this.substs = substs; 5895 } 5896 5897 auto opCall(E)(E e) 5898 { 5899 static foreach (i; 0 .. n) 5900 if (binaryFun!pred(e, substs[2 * i])) 5901 return substs[2 * i + 1]; 5902 5903 return e; 5904 } 5905 } 5906 auto er = ReplaceElement(substs); 5907 return r.map!er; 5908 } 5909 // Substitute subranges 5910 else static if (!is(CommonType!(ElementType!R, ElementType!(Substs[0])) == void) && 5911 allSatisfy!(isForwardRange, Substs)) 5912 { 5913 import std.range : choose, take; 5914 import std.meta : Stride; 5915 5916 auto replaceElement(E)(E e) 5917 { 5918 alias ReturnA = typeof(e[0]); 5919 alias ReturnB = typeof(substs[0 .. 1].take(1)); 5920 5921 // 1-based index 5922 const auto hitNr = e[1]; 5923 switch (hitNr) 5924 { 5925 // no hit 5926 case 0: 5927 // use choose trick for non-common range 5928 static if (is(CommonType!(ReturnA, ReturnB) == void)) 5929 return choose(1, e[0], ReturnB.init); 5930 else 5931 return e[0]; 5932 5933 // all replacements 5934 static foreach (i; 0 .. n) 5935 case i + 1: 5936 // use choose trick for non-common ranges 5937 static if (is(CommonType!(ReturnA, ReturnB) == void)) 5938 return choose(0, e[0], substs[2 * i + 1].take(size_t.max)); 5939 else 5940 return substs[2 * i + 1].take(size_t.max); 5941 default: 5942 assert(0, "hitNr should always be found."); 5943 } 5944 } 5945 5946 alias Ins = Stride!(2, Substs); 5947 5948 static struct SubstituteSplitter 5949 { 5950 import std.range : drop; 5951 import std.typecons : Tuple; 5952 5953 private 5954 { 5955 typeof(R.init.drop(0)) rest; 5956 Ins needles; 5957 5958 typeof(R.init.take(0)) skip; // skip before next hit 5959 alias Hit = size_t; // 0 iff no hit, otherwise hit in needles[index-1] 5960 alias E = Tuple!(typeof(skip), Hit); 5961 Hit hitNr; // hit number: 0 means no hit, otherwise index+1 to needles that matched 5962 bool hasHit; // is there a replacement hit which should be printed? 5963 5964 enum hasDifferentAutodecoding = .hasDifferentAutodecoding!(typeof(rest), Ins); 5965 5966 // calculating the needle length for narrow strings might be expensive -> cache it 5967 static if (hasDifferentAutodecoding) 5968 ptrdiff_t[n] needleLengths = -1; 5969 } 5970 5971 this(R haystack, Ins needles) 5972 { 5973 this.rest = haystack.drop(0); 5974 this.needles = needles; 5975 if (!haystack.empty) 5976 { 5977 hasHit = true; 5978 popFront; 5979 } 5980 static if (hasNested!(typeof(skip))) 5981 skip = rest.take(0); 5982 } 5983 5984 /* If `skip` is non-empty, it's returned as (skip, 0) tuple 5985 otherwise a similar (<empty>, hitNr) tuple is returned. 5986 `replaceElement` maps based on the second item (`hitNr`). 5987 */ 5988 @property auto ref front() 5989 { 5990 assert(!empty, "Attempting to fetch the front of an empty substitute."); 5991 return !skip.empty ? E(skip, 0) : E(typeof(skip).init, hitNr); 5992 } 5993 5994 static if (isInfinite!R) 5995 enum empty = false; // propagate infiniteness 5996 else 5997 @property bool empty() 5998 { 5999 return skip.empty && !hasHit; 6000 } 6001 6002 /* If currently in a skipping phase => reset. 6003 Otherwise try to find the next occurrence of `needles` 6004 If valid match 6005 - if there are elements before the match, set skip with these elements 6006 (on the next popFront, the range will be in the skip state once) 6007 - `rest`: advance to the end of the match 6008 - set hasHit 6009 Otherwise skip to the end 6010 */ 6011 void popFront() 6012 { 6013 assert(!empty, "Attempting to popFront an empty substitute."); 6014 if (!skip.empty) 6015 { 6016 skip = typeof(skip).init; // jump over skip 6017 } 6018 else 6019 { 6020 import std.algorithm.searching : countUntil, find; 6021 6022 auto match = rest.find!pred(needles); 6023 6024 static if (needles.length >= 2) // variadic version of find (returns a tuple) 6025 { 6026 // find with variadic needles returns a (range, needleNr) tuple 6027 // needleNr is a 1-based index 6028 auto hitValue = match[0]; 6029 hitNr = match[1]; 6030 } 6031 else 6032 { 6033 // find with one needle returns the range 6034 auto hitValue = match; 6035 hitNr = match.empty ? 0 : 1; 6036 } 6037 6038 if (hitNr == 0) // no more hits 6039 { 6040 skip = rest.take(size_t.max); 6041 hasHit = false; 6042 rest = typeof(rest).init; 6043 } 6044 else 6045 { 6046 auto hitLength = size_t.max; 6047 switchL: switch (hitNr - 1) 6048 { 6049 static foreach (i; 0 .. n) 6050 { 6051 case i: 6052 static if (hasDifferentAutodecoding) 6053 { 6054 import std.utf : codeLength; 6055 6056 // cache calculated needle length 6057 if (needleLengths[i] != -1) 6058 hitLength = needleLengths[i]; 6059 else 6060 hitLength = needleLengths[i] = codeLength!dchar(needles[i]); 6061 } 6062 else 6063 { 6064 hitLength = needles[i].length; 6065 } 6066 break switchL; 6067 } 6068 default: 6069 assert(0, "hitNr should always be found"); 6070 } 6071 6072 const pos = rest.countUntil(hitValue); 6073 if (pos > 0) // match not at start of rest 6074 skip = rest.take(pos); 6075 6076 hasHit = true; 6077 6078 // iff the source range and the substitutions are narrow strings, 6079 // we can avoid calling the auto-decoding `popFront` (via drop) 6080 static if (isNarrowString!(typeof(hitValue)) && !hasDifferentAutodecoding) 6081 rest = hitValue[hitLength .. $]; 6082 else 6083 rest = hitValue.drop(hitLength); 6084 } 6085 } 6086 } 6087 } 6088 6089 // extract inputs 6090 Ins ins; 6091 static foreach (i; 0 .. n) 6092 ins[i] = substs[2 * i]; 6093 6094 return SubstituteSplitter(r, ins) 6095 .map!(a => replaceElement(a)) 6096 .joiner; 6097 } 6098 else 6099 { 6100 static assert(0, "The substitutions must either substitute a single element or a save-able subrange."); 6101 } 6102 } 6103 6104 /// 6105 @safe pure unittest 6106 { 6107 import std.algorithm.comparison : equal; 6108 6109 // substitute single elements 6110 assert("do_it".substitute('_', ' ').equal("do it")); 6111 6112 // substitute multiple, single elements 6113 assert("do_it".substitute('_', ' ', 6114 'd', 'g', 6115 'i', 't', 6116 't', 'o') 6117 .equal("go to")); 6118 6119 // substitute subranges 6120 assert("do_it".substitute("_", " ", 6121 "do", "done") 6122 .equal("done it")); 6123 6124 // substitution works for any ElementType 6125 int[] x = [1, 2, 3]; 6126 auto y = x.substitute(1, 0.1); 6127 assert(y.equal([0.1, 2, 3])); 6128 static assert(is(typeof(y.front) == double)); 6129 6130 import std.range : retro; 6131 assert([1, 2, 3].substitute(1, 0.1).retro.equal([3, 2, 0.1])); 6132 } 6133 6134 /// Use the faster compile-time overload 6135 @safe pure unittest 6136 { 6137 import std.algorithm.comparison : equal; 6138 6139 // substitute subranges of a range 6140 assert("apple_tree".substitute!("apple", "banana", 6141 "tree", "shrub").equal("banana_shrub")); 6142 6143 // substitute subranges of a range 6144 assert("apple_tree".substitute!('a', 'b', 6145 't', 'f').equal("bpple_free")); 6146 6147 // substitute values 6148 assert('a'.substitute!('a', 'b', 't', 'f') == 'b'); 6149 } 6150 6151 /// Multiple substitutes 6152 @safe pure unittest 6153 { 6154 import std.algorithm.comparison : equal; 6155 import std.range.primitives : ElementType; 6156 6157 int[3] x = [1, 2, 3]; 6158 auto y = x[].substitute(1, 0.1) 6159 .substitute(0.1, 0.2); 6160 static assert(is(typeof(y.front) == double)); 6161 assert(y.equal([0.2, 2, 3])); 6162 6163 auto z = "42".substitute('2', '3') 6164 .substitute('3', '1'); 6165 static assert(is(ElementType!(typeof(z)) == dchar)); 6166 assert(equal(z, "41")); 6167 } 6168 6169 // Test the first example with compile-time overloads 6170 @safe pure unittest 6171 { 6172 import std.algorithm.comparison : equal; 6173 6174 // substitute single elements 6175 assert("do_it".substitute!('_', ' ').equal("do it")); 6176 6177 // substitute multiple, single elements 6178 assert("do_it".substitute!('_', ' ', 6179 'd', 'g', 6180 'i', 't', 6181 't', 'o') 6182 .equal(`go to`)); 6183 6184 // substitute subranges 6185 assert("do_it".substitute!("_", " ", 6186 "do", "done") 6187 .equal("done it")); 6188 6189 // substitution works for any ElementType 6190 int[3] x = [1, 2, 3]; 6191 auto y = x[].substitute!(1, 0.1); 6192 assert(y.equal([0.1, 2, 3])); 6193 static assert(is(typeof(y.front) == double)); 6194 6195 import std.range : retro; 6196 assert([1, 2, 3].substitute!(1, 0.1).retro.equal([3, 2, 0.1])); 6197 } 6198 6199 // test infinite ranges 6200 @safe pure nothrow unittest 6201 { 6202 import std.algorithm.comparison : equal; 6203 import std.range : cycle, take; 6204 6205 int[] x = [1, 2, 3]; 6206 assert(x.cycle.substitute!(1, 0.1).take(4).equal([0.1, 2, 3, 0.1])); 6207 assert(x.cycle.substitute(1, 0.1).take(4).equal([0.1, 2, 3, 0.1])); 6208 } 6209 6210 // test infinite ranges 6211 @safe pure nothrow unittest 6212 { 6213 import std.algorithm.comparison : equal; 6214 import std.internal.test.dummyrange : AllDummyRanges; 6215 6216 foreach (R; AllDummyRanges) 6217 { 6218 assert(R.init 6219 .substitute!(2, 22, 3, 33, 5, 55, 9, 99) 6220 .equal([1, 22, 33, 4, 55, 6, 7, 8, 99, 10])); 6221 6222 assert(R.init 6223 .substitute(2, 22, 3, 33, 5, 55, 9, 99) 6224 .equal([1, 22, 33, 4, 55, 6, 7, 8, 99, 10])); 6225 } 6226 } 6227 6228 // test multiple replacements 6229 @safe pure unittest 6230 { 6231 import std.algorithm.comparison : equal; 6232 6233 assert("alpha.beta.gamma" 6234 .substitute("alpha", "1", 6235 "gamma", "3", 6236 "beta", "2").equal("1.2.3")); 6237 6238 assert("alpha.beta.gamma." 6239 .substitute("alpha", "1", 6240 "gamma", "3", 6241 "beta", "2").equal("1.2.3.")); 6242 6243 assert("beta.beta.beta" 6244 .substitute("alpha", "1", 6245 "gamma", "3", 6246 "beta", "2").equal("2.2.2")); 6247 6248 assert("alpha.alpha.alpha" 6249 .substitute("alpha", "1", 6250 "gamma", "3", 6251 "beta", "2").equal("1.1.1")); 6252 } 6253 6254 // test combination of subrange + element replacement 6255 @safe pure unittest 6256 { 6257 import std.algorithm.comparison : equal; 6258 6259 assert(("abcDe".substitute("a", "AA", 6260 "b", "DD") 6261 .substitute('A', 'y', 6262 'D', 'x', 6263 'e', '1')) 6264 .equal("yyxxcx1")); 6265 } 6266 6267 // test const + immutable storage groups 6268 @safe pure unittest 6269 { 6270 import std.algorithm.comparison : equal; 6271 6272 auto xyz_abc(T)(T value) 6273 { 6274 immutable a = "a"; 6275 const b = "b"; 6276 auto c = "c"; 6277 return value.substitute!("x", a, 6278 "y", b, 6279 "z", c); 6280 } 6281 assert(xyz_abc("_x").equal("_a")); 6282 assert(xyz_abc(".y.").equal(".b.")); 6283 assert(xyz_abc("z").equal("c")); 6284 assert(xyz_abc("w").equal("w")); 6285 } 6286 6287 // test with narrow strings (auto-decoding) and subranges 6288 @safe pure unittest 6289 { 6290 import std.algorithm.comparison : equal; 6291 6292 assert("äöü€".substitute("ä", "b", "ü", "u").equal("böu€")); 6293 assert("äöü€".substitute!("ä", "b", "ü", "u").equal("böu€")); 6294 assert("ä...öü€".substitute("ä", "b", "ü", "u").equal("b...öu€")); 6295 6296 auto expected = "emoticons😄😅.😇😈Rock"; 6297 assert("emoticons😄😅😆😇😈rock" 6298 .substitute("r", "R", "😆", ".").equal(expected)); 6299 assert("emoticons😄😅😆😇😈rock" 6300 .substitute!("r", "R", "😆", ".").equal(expected)); 6301 } 6302 6303 // test with narrow strings (auto-decoding) and single elements 6304 @safe pure unittest 6305 { 6306 import std.algorithm.comparison : equal; 6307 6308 assert("äöü€".substitute('ä', 'b', 'ü', 'u').equal("böu€")); 6309 assert("äöü€".substitute!('ä', 'b', 'ü', 'u').equal("böu€")); 6310 6311 auto expected = "emoticons😄😅.😇😈Rock"; 6312 assert("emoticons😄😅😆😇😈rock" 6313 .substitute('r', 'R', '😆', '.').equal(expected)); 6314 assert("emoticons😄😅😆😇😈rock" 6315 .substitute!('r', 'R', '😆', '.').equal(expected)); 6316 } 6317 6318 // test auto-decoding {n,w,d} strings X {n,w,d} strings 6319 @safe pure unittest 6320 { 6321 import std.algorithm.comparison : equal; 6322 6323 assert("ääöü€".substitute("ä", "b", "ü", "u").equal("bböu€")); 6324 assert("ääöü€".substitute("ä"w, "b"w, "ü"w, "u"w).equal("bböu€")); 6325 assert("ääöü€".substitute("ä"d, "b"d, "ü"d, "u"d).equal("bböu€")); 6326 6327 assert("ääöü€"w.substitute("ä", "b", "ü", "u").equal("bböu€")); 6328 assert("ääöü€"w.substitute("ä"w, "b"w, "ü"w, "u"w).equal("bböu€")); 6329 assert("ääöü€"w.substitute("ä"d, "b"d, "ü"d, "u"d).equal("bböu€")); 6330 6331 assert("ääöü€"d.substitute("ä", "b", "ü", "u").equal("bböu€")); 6332 assert("ääöü€"d.substitute("ä"w, "b"w, "ü"w, "u"w).equal("bböu€")); 6333 assert("ääöü€"d.substitute("ä"d, "b"d, "ü"d, "u"d).equal("bböu€")); 6334 6335 // auto-decoding is done before by a different range 6336 assert("ääöü€".filter!(a => true).substitute("ä", "b", "ü", "u").equal("bböu€")); 6337 assert("ääöü€".filter!(a => true).substitute("ä"w, "b"w, "ü"w, "u"w).equal("bböu€")); 6338 assert("ääöü€".filter!(a => true).substitute("ä"d, "b"d, "ü"d, "u"d).equal("bböu€")); 6339 } 6340 6341 // test repeated replacement 6342 @safe pure nothrow unittest 6343 { 6344 import std.algorithm.comparison : equal; 6345 6346 assert([1, 2, 3, 1, 1, 2].substitute(1, 0).equal([0, 2, 3, 0, 0, 2])); 6347 assert([1, 2, 3, 1, 1, 2].substitute!(1, 0).equal([0, 2, 3, 0, 0, 2])); 6348 assert([1, 2, 3, 1, 1, 2].substitute(1, 2, 2, 9).equal([2, 9, 3, 2, 2, 9])); 6349 } 6350 6351 // test @nogc for single element replacements 6352 @safe @nogc unittest 6353 { 6354 import std.algorithm.comparison : equal; 6355 6356 static immutable arr = [1, 2, 3, 1, 1, 2]; 6357 static immutable expected = [0, 2, 3, 0, 0, 2]; 6358 6359 assert(arr.substitute!(1, 0).equal(expected)); 6360 assert(arr.substitute(1, 0).equal(expected)); 6361 } 6362 6363 // test different range types 6364 @safe pure nothrow unittest 6365 { 6366 import std.algorithm.comparison : equal; 6367 import std.internal.test.dummyrange : AllDummyRanges; 6368 6369 static foreach (DummyType; AllDummyRanges) 6370 {{ 6371 DummyType dummyRange; 6372 6373 // single substitution 6374 dummyRange.substitute (2, 22).equal([1, 22, 3, 4, 5, 6, 7, 8, 9, 10]); 6375 dummyRange.substitute!(2, 22).equal([1, 22, 3, 4, 5, 6, 7, 8, 9, 10]); 6376 6377 // multiple substitution 6378 dummyRange.substitute (2, 22, 5, 55, 7, 77).equal([1, 22, 3, 4, 55, 6, 77, 8, 9, 10]); 6379 dummyRange.substitute!(2, 22, 5, 55, 7, 77).equal([1, 22, 3, 4, 55, 6, 77, 8, 9, 10]); 6380 }} 6381 } 6382 6383 // https://issues.dlang.org/show_bug.cgi?id=19207 6384 @safe pure nothrow unittest 6385 { 6386 import std.algorithm.comparison : equal; 6387 assert([1, 2, 3, 4].substitute([1], [7]).equal([7, 2, 3, 4])); 6388 assert([1, 2, 3, 4].substitute([2], [7]).equal([1, 7, 3, 4])); 6389 assert([1, 2, 3, 4].substitute([4], [7]).equal([1, 2, 3, 7])); 6390 assert([1, 2, 3, 4].substitute([2, 3], [7]).equal([1, 7, 4])); 6391 assert([1, 2, 3, 4].substitute([3, 4], [7, 8]).equal([1, 2, 7, 8])); 6392 } 6393 6394 // tests recognizing empty base ranges 6395 nothrow pure @safe unittest 6396 { 6397 import std.utf : byCodeUnit; 6398 import std.algorithm.comparison : equal; 6399 6400 assert("".byCodeUnit.substitute('4', 'A').empty); 6401 assert("".byCodeUnit.substitute('0', 'O', '5', 'S', '1', 'l').empty); 6402 assert("".byCodeUnit.substitute("PKM".byCodeUnit, "PoKeMon".byCodeUnit).empty); 6403 assert("".byCodeUnit.substitute 6404 ( "ding".byCodeUnit, 6405 "dong".byCodeUnit, 6406 "click".byCodeUnit, 6407 "clack".byCodeUnit, 6408 "ping".byCodeUnit, 6409 "latency".byCodeUnit 6410 ).empty); 6411 } 6412 6413 // sum 6414 /** 6415 Sums elements of `r`, which must be a finite 6416 $(REF_ALTTEXT input range, isInputRange, std,range,primitives). Although 6417 conceptually `sum(r)` is equivalent to $(LREF fold)!((a, b) => a + 6418 b)(r, 0), `sum` uses specialized algorithms to maximize accuracy, 6419 as follows. 6420 6421 $(UL 6422 $(LI If $(REF ElementType, std,range,primitives)!R is a floating-point 6423 type and `R` is a 6424 $(REF_ALTTEXT random-access range, isRandomAccessRange, std,range,primitives) with 6425 length and slicing, then `sum` uses the 6426 $(HTTP en.wikipedia.org/wiki/Pairwise_summation, pairwise summation) 6427 algorithm.) 6428 $(LI If `ElementType!R` is a floating-point type and `R` is a 6429 finite input range (but not a random-access range with slicing), then 6430 `sum` uses the $(HTTP en.wikipedia.org/wiki/Kahan_summation, 6431 Kahan summation) algorithm.) 6432 $(LI In all other cases, a simple element by element addition is done.) 6433 ) 6434 6435 For floating point inputs, calculations are made in 6436 $(DDLINK spec/type, Types, `real`) 6437 precision for `real` inputs and in `double` precision otherwise 6438 (Note this is a special case that deviates from `fold`'s behavior, 6439 which would have kept `float` precision for a `float` range). 6440 For all other types, the calculations are done in the same type obtained 6441 from from adding two elements of the range, which may be a different 6442 type from the elements themselves (for example, in case of 6443 $(DDSUBLINK spec/type,integer-promotions, integral promotion)). 6444 6445 A seed may be passed to `sum`. Not only will this seed be used as an initial 6446 value, but its type will override all the above, and determine the algorithm 6447 and precision used for summation. If a seed is not passed, one is created with 6448 the value of `typeof(r.front + r.front)(0)`, or `typeof(r.front + r.front).zero` 6449 if no constructor exists that takes an int. 6450 6451 Note that these specialized summing algorithms execute more primitive operations 6452 than vanilla summation. Therefore, if in certain cases maximum speed is required 6453 at expense of precision, one can use `fold!((a, b) => a + b)(r, 0)`, which 6454 is not specialized for summation. 6455 6456 Params: 6457 seed = the initial value of the summation 6458 r = a finite input range 6459 6460 Returns: 6461 The sum of all the elements in the range r. 6462 */ 6463 auto sum(R)(R r) 6464 if (isInputRange!R && !isInfinite!R && is(typeof(r.front + r.front))) 6465 { 6466 alias E = Unqual!(ElementType!R); 6467 static if (isFloatingPoint!E) 6468 alias Seed = typeof(E.init + 0.0); //biggest of double/real 6469 else 6470 alias Seed = typeof(r.front + r.front); 6471 static if (is(typeof(Unqual!Seed(0)))) 6472 enum seedValue = Unqual!Seed(0); 6473 else static if (is(typeof({ Unqual!Seed tmp = Seed.zero; }))) 6474 enum Unqual!Seed seedValue = Seed.zero; 6475 else 6476 static assert(false, 6477 "Could not initiate an initial value for " ~ (Unqual!Seed).stringof 6478 ~ ". Please supply an initial value manually."); 6479 return sum(r, seedValue); 6480 } 6481 /// ditto 6482 auto sum(R, E)(R r, E seed) 6483 if (isInputRange!R && !isInfinite!R && is(typeof(seed = seed + r.front))) 6484 { 6485 static if (isFloatingPoint!E) 6486 { 6487 static if (hasLength!R && hasSlicing!R) 6488 { 6489 if (r.empty) return seed; 6490 return seed + sumPairwise!E(r); 6491 } 6492 else 6493 return sumKahan!E(seed, r); 6494 } 6495 else 6496 { 6497 return reduce!"a + b"(seed, r); 6498 } 6499 } 6500 6501 /// Ditto 6502 @safe pure nothrow unittest 6503 { 6504 import std.range; 6505 6506 //simple integral sumation 6507 assert(sum([ 1, 2, 3, 4]) == 10); 6508 6509 //with integral promotion 6510 assert(sum([false, true, true, false, true]) == 3); 6511 assert(sum(ubyte.max.repeat(100)) == 25500); 6512 6513 //The result may overflow 6514 assert(uint.max.repeat(3).sum() == 4294967293U ); 6515 //But a seed can be used to change the sumation primitive 6516 assert(uint.max.repeat(3).sum(ulong.init) == 12884901885UL); 6517 6518 //Floating point sumation 6519 assert(sum([1.0, 2.0, 3.0, 4.0]) == 10); 6520 6521 //Floating point operations have double precision minimum 6522 static assert(is(typeof(sum([1F, 2F, 3F, 4F])) == double)); 6523 assert(sum([1F, 2, 3, 4]) == 10); 6524 6525 //Force pair-wise floating point sumation on large integers 6526 import std.math : approxEqual; 6527 assert(iota(ulong.max / 2, ulong.max / 2 + 4096).sum(0.0) 6528 .approxEqual((ulong.max / 2) * 4096.0 + 4096^^2 / 2)); 6529 } 6530 6531 // Pairwise summation http://en.wikipedia.org/wiki/Pairwise_summation 6532 private auto sumPairwise(F, R)(R data) 6533 if (isInputRange!R && !isInfinite!R) 6534 { 6535 import core.bitop : bsf; 6536 // Works for r with at least length < 2^^(64 + log2(16)), in keeping with the use of size_t 6537 // elsewhere in std.algorithm and std.range on 64 bit platforms. The 16 in log2(16) comes 6538 // from the manual unrolling in sumPairWise16 6539 F[64] store = void; 6540 size_t idx = 0; 6541 6542 void collapseStore(T)(T k) 6543 { 6544 auto lastToKeep = idx - cast(uint) bsf(k+1); 6545 while (idx > lastToKeep) 6546 { 6547 store[idx - 1] += store[idx]; 6548 --idx; 6549 } 6550 } 6551 6552 static if (hasLength!R) 6553 { 6554 foreach (k; 0 .. data.length / 16) 6555 { 6556 static if (isRandomAccessRange!R && hasSlicing!R) 6557 { 6558 store[idx] = sumPairwise16!F(data); 6559 data = data[16 .. data.length]; 6560 } 6561 else store[idx] = sumPairwiseN!(16, false, F)(data); 6562 6563 collapseStore(k); 6564 ++idx; 6565 } 6566 6567 size_t i = 0; 6568 foreach (el; data) 6569 { 6570 store[idx] = el; 6571 collapseStore(i); 6572 ++idx; 6573 ++i; 6574 } 6575 } 6576 else 6577 { 6578 size_t k = 0; 6579 while (!data.empty) 6580 { 6581 store[idx] = sumPairwiseN!(16, true, F)(data); 6582 collapseStore(k); 6583 ++idx; 6584 ++k; 6585 } 6586 } 6587 6588 F s = store[idx - 1]; 6589 foreach_reverse (j; 0 .. idx - 1) 6590 s += store[j]; 6591 6592 return s; 6593 } 6594 6595 private auto sumPairwise16(F, R)(R r) 6596 if (isRandomAccessRange!R) 6597 { 6598 return (((cast(F) r[ 0] + r[ 1]) + (cast(F) r[ 2] + r[ 3])) 6599 + ((cast(F) r[ 4] + r[ 5]) + (cast(F) r[ 6] + r[ 7]))) 6600 + (((cast(F) r[ 8] + r[ 9]) + (cast(F) r[10] + r[11])) 6601 + ((cast(F) r[12] + r[13]) + (cast(F) r[14] + r[15]))); 6602 } 6603 6604 private auto sumPair(bool needEmptyChecks, F, R)(ref R r) 6605 if (isForwardRange!R && !isRandomAccessRange!R) 6606 { 6607 static if (needEmptyChecks) if (r.empty) return F(0); 6608 F s0 = r.front; 6609 r.popFront(); 6610 static if (needEmptyChecks) if (r.empty) return s0; 6611 s0 += r.front; 6612 r.popFront(); 6613 return s0; 6614 } 6615 6616 private auto sumPairwiseN(size_t N, bool needEmptyChecks, F, R)(ref R r) 6617 if (isForwardRange!R && !isRandomAccessRange!R) 6618 { 6619 import std.math : isPowerOf2; 6620 static assert(isPowerOf2(N), "N must be a power of 2"); 6621 static if (N == 2) return sumPair!(needEmptyChecks, F)(r); 6622 else return sumPairwiseN!(N/2, needEmptyChecks, F)(r) 6623 + sumPairwiseN!(N/2, needEmptyChecks, F)(r); 6624 } 6625 6626 // Kahan algo http://en.wikipedia.org/wiki/Kahan_summation_algorithm 6627 private auto sumKahan(Result, R)(Result result, R r) 6628 { 6629 static assert(isFloatingPoint!Result && isMutable!Result, "The type of" 6630 ~ " Result must be a mutable floating point, not " 6631 ~ Result.stringof); 6632 Result c = 0; 6633 for (; !r.empty; r.popFront()) 6634 { 6635 immutable y = r.front - c; 6636 immutable t = result + y; 6637 c = (t - result) - y; 6638 result = t; 6639 } 6640 return result; 6641 } 6642 6643 @safe pure nothrow unittest 6644 { 6645 static assert(is(typeof(sum([cast( byte) 1])) == int)); 6646 static assert(is(typeof(sum([cast(ubyte) 1])) == int)); 6647 static assert(is(typeof(sum([ 1, 2, 3, 4])) == int)); 6648 static assert(is(typeof(sum([ 1U, 2U, 3U, 4U])) == uint)); 6649 static assert(is(typeof(sum([ 1L, 2L, 3L, 4L])) == long)); 6650 static assert(is(typeof(sum([1UL, 2UL, 3UL, 4UL])) == ulong)); 6651 6652 int[] empty; 6653 assert(sum(empty) == 0); 6654 assert(sum([42]) == 42); 6655 assert(sum([42, 43]) == 42 + 43); 6656 assert(sum([42, 43, 44]) == 42 + 43 + 44); 6657 assert(sum([42, 43, 44, 45]) == 42 + 43 + 44 + 45); 6658 } 6659 6660 @safe pure nothrow unittest 6661 { 6662 static assert(is(typeof(sum([1.0, 2.0, 3.0, 4.0])) == double)); 6663 static assert(is(typeof(sum([ 1F, 2F, 3F, 4F])) == double)); 6664 const(float[]) a = [1F, 2F, 3F, 4F]; 6665 assert(sum(a) == 10F); 6666 static assert(is(typeof(sum(a)) == double)); 6667 6668 double[] empty; 6669 assert(sum(empty) == 0); 6670 assert(sum([42.]) == 42); 6671 assert(sum([42., 43.]) == 42 + 43); 6672 assert(sum([42., 43., 44.]) == 42 + 43 + 44); 6673 assert(sum([42., 43., 44., 45.5]) == 42 + 43 + 44 + 45.5); 6674 } 6675 6676 @safe pure nothrow unittest 6677 { 6678 import std.container; 6679 static assert(is(typeof(sum(SList!float()[])) == double)); 6680 static assert(is(typeof(sum(SList!double()[])) == double)); 6681 static assert(is(typeof(sum(SList!real()[])) == real)); 6682 6683 assert(sum(SList!double()[]) == 0); 6684 assert(sum(SList!double(1)[]) == 1); 6685 assert(sum(SList!double(1, 2)[]) == 1 + 2); 6686 assert(sum(SList!double(1, 2, 3)[]) == 1 + 2 + 3); 6687 assert(sum(SList!double(1, 2, 3, 4)[]) == 10); 6688 } 6689 6690 // https://issues.dlang.org/show_bug.cgi?id=12434 6691 @safe pure nothrow unittest 6692 { 6693 immutable a = [10, 20]; 6694 auto s1 = sum(a); 6695 assert(s1 == 30); 6696 auto s2 = a.map!(x => x).sum; 6697 assert(s2 == 30); 6698 } 6699 6700 @system unittest 6701 { 6702 import std.bigint; 6703 import std.range; 6704 6705 immutable BigInt[] a = BigInt("1_000_000_000_000_000_000").repeat(10).array(); 6706 immutable ulong[] b = (ulong.max/2).repeat(10).array(); 6707 auto sa = a.sum(); 6708 auto sb = b.sum(BigInt(0)); //reduce ulongs into bigint 6709 assert(sa == BigInt("10_000_000_000_000_000_000")); 6710 assert(sb == (BigInt(ulong.max/2) * 10)); 6711 } 6712 6713 @safe pure nothrow @nogc unittest 6714 { 6715 import std.range; 6716 foreach (n; iota(50)) 6717 assert(repeat(1.0, n).sum == n); 6718 } 6719 6720 // Issue 19525 6721 @safe unittest 6722 { 6723 import std.datetime : Duration, minutes; 6724 assert([1.minutes].sum() == 1.minutes); 6725 } 6726 6727 /** 6728 Finds the mean (colloquially known as the average) of a range. 6729 6730 For built-in numerical types, accurate Knuth & Welford mean calculation 6731 is used. For user-defined types, element by element summation is used. 6732 Additionally an extra parameter `seed` is needed in order to correctly 6733 seed the summation with the equivalent to `0`. 6734 6735 The first overload of this function will return `T.init` if the range 6736 is empty. However, the second overload will return `seed` on empty ranges. 6737 6738 This function is $(BIGOH r.length). 6739 6740 Params: 6741 T = The type of the return value. 6742 r = An $(REF_ALTTEXT input range, isInputRange, std,range,primitives) 6743 seed = For user defined types. Should be equivalent to `0`. 6744 6745 Returns: 6746 The mean of `r` when `r` is non-empty. 6747 */ 6748 T mean(T = double, R)(R r) 6749 if (isInputRange!R && 6750 isNumeric!(ElementType!R) && 6751 !isInfinite!R) 6752 { 6753 if (r.empty) 6754 return T.init; 6755 6756 Unqual!T meanRes = 0; 6757 size_t i = 1; 6758 6759 // Knuth & Welford mean calculation 6760 // division per element is slower, but more accurate 6761 for (; !r.empty; r.popFront()) 6762 { 6763 T delta = r.front - meanRes; 6764 meanRes += delta / i++; 6765 } 6766 6767 return meanRes; 6768 } 6769 6770 /// ditto 6771 auto mean(R, T)(R r, T seed) 6772 if (isInputRange!R && 6773 !isNumeric!(ElementType!R) && 6774 is(typeof(r.front + seed)) && 6775 is(typeof(r.front / size_t(1))) && 6776 !isInfinite!R) 6777 { 6778 import std.algorithm.iteration : sum, reduce; 6779 6780 // per item division vis-a-vis the previous overload is too 6781 // inaccurate for integer division, which the user defined 6782 // types might be representing 6783 static if (hasLength!R) 6784 { 6785 if (r.length == 0) 6786 return seed; 6787 6788 return sum(r, seed) / r.length; 6789 } 6790 else 6791 { 6792 import std.typecons : tuple; 6793 6794 if (r.empty) 6795 return seed; 6796 6797 auto pair = reduce!((a, b) => tuple(a[0] + 1, a[1] + b)) 6798 (tuple(size_t(0), seed), r); 6799 return pair[1] / pair[0]; 6800 } 6801 } 6802 6803 /// 6804 @safe @nogc pure nothrow unittest 6805 { 6806 import std.math : approxEqual, isNaN; 6807 6808 static immutable arr1 = [1, 2, 3]; 6809 static immutable arr2 = [1.5, 2.5, 12.5]; 6810 6811 assert(arr1.mean.approxEqual(2)); 6812 assert(arr2.mean.approxEqual(5.5)); 6813 6814 assert(arr1[0 .. 0].mean.isNaN); 6815 } 6816 6817 @safe pure nothrow unittest 6818 { 6819 import std.internal.test.dummyrange : ReferenceInputRange; 6820 import std.math : approxEqual; 6821 6822 auto r1 = new ReferenceInputRange!int([1, 2, 3]); 6823 assert(r1.mean.approxEqual(2)); 6824 6825 auto r2 = new ReferenceInputRange!double([1.5, 2.5, 12.5]); 6826 assert(r2.mean.approxEqual(5.5)); 6827 } 6828 6829 // Test user defined types 6830 @system pure unittest 6831 { 6832 import std.bigint : BigInt; 6833 import std.internal.test.dummyrange : ReferenceInputRange; 6834 import std.math : approxEqual; 6835 6836 auto bigint_arr = [BigInt("1"), BigInt("2"), BigInt("3"), BigInt("6")]; 6837 auto bigint_arr2 = new ReferenceInputRange!BigInt([ 6838 BigInt("1"), BigInt("2"), BigInt("3"), BigInt("6") 6839 ]); 6840 assert(bigint_arr.mean(BigInt(0)) == BigInt("3")); 6841 assert(bigint_arr2.mean(BigInt(0)) == BigInt("3")); 6842 6843 BigInt[] bigint_arr3 = []; 6844 assert(bigint_arr3.mean(BigInt(0)) == BigInt(0)); 6845 6846 struct MyFancyDouble 6847 { 6848 double v; 6849 alias v this; 6850 } 6851 6852 // both overloads 6853 auto d_arr = [MyFancyDouble(10), MyFancyDouble(15), MyFancyDouble(30)]; 6854 assert(mean!(double)(cast(double[]) d_arr).approxEqual(18.333)); 6855 assert(mean(d_arr, MyFancyDouble(0)).approxEqual(18.333)); 6856 } 6857 6858 // uniq 6859 /** 6860 Lazily iterates unique consecutive elements of the given range (functionality 6861 akin to the $(HTTP wikipedia.org/wiki/_Uniq, _uniq) system 6862 utility). Equivalence of elements is assessed by using the predicate 6863 `pred`, by default `"a == b"`. The predicate is passed to 6864 $(REF binaryFun, std,functional), and can either accept a string, or any callable 6865 that can be executed via `pred(element, element)`. If the given range is 6866 bidirectional, `uniq` also yields a 6867 $(REF_ALTTEXT bidirectional range, isBidirectionalRange, std,range,primitives). 6868 6869 Params: 6870 pred = Predicate for determining equivalence between range elements. 6871 r = An $(REF_ALTTEXT input range, isInputRange, std,range,primitives) of 6872 elements to filter. 6873 6874 Returns: 6875 An $(REF_ALTTEXT input range, isInputRange, std,range,primitives) of 6876 consecutively unique elements in the original range. If `r` is also a 6877 forward range or bidirectional range, the returned range will be likewise. 6878 */ 6879 auto uniq(alias pred = "a == b", Range)(Range r) 6880 if (isInputRange!Range && is(typeof(binaryFun!pred(r.front, r.front)) == bool)) 6881 { 6882 return UniqResult!(binaryFun!pred, Range)(r); 6883 } 6884 6885 /// 6886 @safe unittest 6887 { 6888 import std.algorithm.comparison : equal; 6889 import std.algorithm.mutation : copy; 6890 6891 int[] arr = [ 1, 2, 2, 2, 2, 3, 4, 4, 4, 5 ]; 6892 assert(equal(uniq(arr), [ 1, 2, 3, 4, 5 ][])); 6893 6894 // Filter duplicates in-place using copy 6895 arr.length -= arr.uniq().copy(arr).length; 6896 assert(arr == [ 1, 2, 3, 4, 5 ]); 6897 6898 // Note that uniqueness is only determined consecutively; duplicated 6899 // elements separated by an intervening different element will not be 6900 // eliminated: 6901 assert(equal(uniq([ 1, 1, 2, 1, 1, 3, 1]), [1, 2, 1, 3, 1])); 6902 } 6903 6904 private struct UniqResult(alias pred, Range) 6905 { 6906 Range _input; 6907 6908 this(Range input) 6909 { 6910 _input = input; 6911 } 6912 6913 auto opSlice() 6914 { 6915 return this; 6916 } 6917 6918 void popFront() 6919 { 6920 assert(!empty, "Attempting to popFront an empty uniq."); 6921 auto last = _input.front; 6922 do 6923 { 6924 _input.popFront(); 6925 } 6926 while (!_input.empty && pred(last, _input.front)); 6927 } 6928 6929 @property ElementType!Range front() 6930 { 6931 assert(!empty, "Attempting to fetch the front of an empty uniq."); 6932 return _input.front; 6933 } 6934 6935 static if (isBidirectionalRange!Range) 6936 { 6937 void popBack() 6938 { 6939 assert(!empty, "Attempting to popBack an empty uniq."); 6940 auto last = _input.back; 6941 do 6942 { 6943 _input.popBack(); 6944 } 6945 while (!_input.empty && pred(last, _input.back)); 6946 } 6947 6948 @property ElementType!Range back() 6949 { 6950 assert(!empty, "Attempting to fetch the back of an empty uniq."); 6951 return _input.back; 6952 } 6953 } 6954 6955 static if (isInfinite!Range) 6956 { 6957 enum bool empty = false; // Propagate infiniteness. 6958 } 6959 else 6960 { 6961 @property bool empty() { return _input.empty; } 6962 } 6963 6964 static if (isForwardRange!Range) 6965 { 6966 @property typeof(this) save() { 6967 return typeof(this)(_input.save); 6968 } 6969 } 6970 } 6971 6972 @safe unittest 6973 { 6974 import std.algorithm.comparison : equal; 6975 import std.internal.test.dummyrange; 6976 import std.range; 6977 6978 int[] arr = [ 1, 2, 2, 2, 2, 3, 4, 4, 4, 5 ]; 6979 auto r = uniq(arr); 6980 static assert(isForwardRange!(typeof(r))); 6981 6982 assert(equal(r, [ 1, 2, 3, 4, 5 ][])); 6983 assert(equal(retro(r), retro([ 1, 2, 3, 4, 5 ][]))); 6984 6985 foreach (DummyType; AllDummyRanges) 6986 { 6987 DummyType d; 6988 auto u = uniq(d); 6989 assert(equal(u, [1,2,3,4,5,6,7,8,9,10])); 6990 6991 static assert(d.rt == RangeType.Input || isForwardRange!(typeof(u))); 6992 6993 static if (d.rt >= RangeType.Bidirectional) 6994 { 6995 assert(equal(retro(u), [10,9,8,7,6,5,4,3,2,1])); 6996 } 6997 } 6998 } 6999 7000 // https://issues.dlang.org/show_bug.cgi?id=17264 7001 @safe unittest 7002 { 7003 import std.algorithm.comparison : equal; 7004 7005 const(int)[] var = [0, 1, 1, 2]; 7006 assert(var.uniq.equal([0, 1, 2])); 7007 } 7008 7009 /** 7010 Lazily computes all _permutations of `r` using $(HTTP 7011 en.wikipedia.org/wiki/Heap%27s_algorithm, Heap's algorithm). 7012 7013 Params: 7014 Range = the range type 7015 r = the $(REF_ALTTEXT random access range, isRandomAccessRange, std,range,primitives) 7016 to find the permutations for. 7017 Returns: 7018 A $(REF_ALTTEXT forward range, isForwardRange, std,range,primitives) 7019 of elements of which are an $(REF indexed, std,range) view into `r`. 7020 7021 See_Also: 7022 $(REF nextPermutation, std,algorithm,sorting). 7023 */ 7024 Permutations!Range permutations(Range)(Range r) 7025 if (isRandomAccessRange!Range && hasLength!Range) 7026 { 7027 return typeof(return)(r); 7028 } 7029 7030 /// ditto 7031 struct Permutations(Range) 7032 if (isRandomAccessRange!Range && hasLength!Range) 7033 { 7034 private size_t[] _indices, _state; 7035 private Range _r; 7036 private bool _empty; 7037 7038 /// 7039 this(Range r) 7040 { 7041 import std.array : array; 7042 import std.range : iota; 7043 7044 this._r = r; 7045 _state = r.length ? new size_t[r.length-1] : null; 7046 _indices = iota(size_t(r.length)).array; 7047 _empty = r.length == 0; 7048 } 7049 7050 /// Returns: `true` if the range is empty, `false` otherwise. 7051 @property bool empty() const pure nothrow @safe @nogc 7052 { 7053 return _empty; 7054 } 7055 7056 /// Returns: the front of the range 7057 @property auto front() 7058 { 7059 import std.range : indexed; 7060 return _r.indexed(_indices); 7061 } 7062 7063 /// 7064 void popFront() 7065 { 7066 void next(int n) 7067 { 7068 import std.algorithm.mutation : swap; 7069 7070 if (n > _indices.length) 7071 { 7072 _empty = true; 7073 return; 7074 } 7075 7076 if (n % 2 == 1) 7077 swap(_indices[0], _indices[n-1]); 7078 else 7079 swap(_indices[_state[n-2]], _indices[n-1]); 7080 7081 if (++_state[n-2] == n) 7082 { 7083 _state[n-2] = 0; 7084 next(n+1); 7085 } 7086 } 7087 7088 next(2); 7089 } 7090 } 7091 7092 /// 7093 @safe unittest 7094 { 7095 import std.algorithm.comparison : equal; 7096 import std.range : iota; 7097 assert(equal!equal(iota(3).permutations, 7098 [[0, 1, 2], 7099 [1, 0, 2], 7100 [2, 0, 1], 7101 [0, 2, 1], 7102 [1, 2, 0], 7103 [2, 1, 0]])); 7104 }