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