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