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