1 // Written in the D programming language. 2 /* 3 NYSL Version 0.9982 4 5 A. This software is "Everyone'sWare". It means: 6 Anybody who has this software can use it as if he/she is 7 the author. 8 9 A-1. Freeware. No fee is required. 10 A-2. You can freely redistribute this software. 11 A-3. You can freely modify this software. And the source 12 may be used in any software with no limitation. 13 A-4. When you release a modified version to public, you 14 must publish it with your name. 15 16 B. The author is not responsible for any kind of damages or loss 17 while using or misusing this software, which is distributed 18 "AS IS". No warranty of any kind is expressed or implied. 19 You use AT YOUR OWN RISK. 20 21 C. Copyrighted to Kazuki KOMATSU 22 23 D. Above three clauses are applied both to source and binary 24 form of this software. 25 */ 26 27 /** 28 このモジュールは、標準ライブラリのstd.rangeを強化します。 29 */ 30 31 module carbon.range; 32 33 34 import std.algorithm, 35 std.array, 36 std.range, 37 std.string, 38 std.traits; 39 40 debug import std.stdio; 41 42 import carbon.functional, 43 carbon.templates, 44 carbon.traits; 45 46 47 /** 48 true if isInputRange!R is true and isInputRange!R is false. 49 */ 50 enum isSimpleRange(R, alias I = isInputRange) = 51 I!(R) && !I!(ElementType!R); 52 53 54 /** 55 true if both isInputRange!R and isInputRange!R are true. 56 */ 57 enum isRangeOfRanges(R, alias I = isInputRange) = 58 I!(R) && I!(ElementType!R); 59 60 61 62 /** 63 あるレンジのN個の連続する要素のリストを返します。 64 65 Example: 66 ---- 67 auto r1 = [0, 1, 2, 3, 4, 5]; 68 auto s = segment!2(r1); 69 assert(equal(s, [tuple(0, 1), tuple(1, 2), tuple(2, 3), tuple(3, 4), tuple(4, 5)][])); 70 assert(s.length == 5); // .length 71 // back/popBack: 72 assert(equal(retro(s), retro([tuple(0, 1), tuple(1, 2), tuple(2, 3), tuple(3, 4), tuple(4, 5)][]))); 73 assert(s[3] == tuple(3, 4)); // opIndex 74 s[3] = tuple(0, 0); // opIndexAssign not ref opIndex 75 assert(s[2] == tuple(2, 0)); // it affects its neighbors. 76 assert(s[4] == tuple(0, 5)); 77 assert(r1 == [0, 1, 2, 0, 0, 5][]); // affects r1 back (no .dup internally) 78 79 80 auto st = ["a","b","c","d","e","f"]; 81 auto s2 = segment!3(st); 82 assert(s2.front == tuple("a","b","c")); 83 84 85 auto r1 = [0,1,2,3,4,5]; // regenerates r1 86 auto s3 = segment!1(r1); 87 assert(equal(s3, [tuple(0), tuple(1), tuple(2), tuple(3), tuple(4), tuple(5)][])); 88 auto r2 = map!"a*a"(r1); 89 auto s4 = segment!2(r2); // On a forward range 90 assert(equal(s4, [tuple(0,1), tuple(1,4), tuple(4,9), tuple(9,16), tuple(16,25)][])); 91 92 93 int[] e; 94 auto s5 = segment!2(e); 95 assert(s5.empty); 96 ---- 97 98 Authors: Komatsu Kazuki 99 */ 100 template SegmentType(size_t N, R) 101 if(isInputRange!(Unqual!R) && N > 0) 102 { 103 alias typeof(segment!N(R.init)) SegmentType; 104 } 105 106 107 ///ditto 108 template segment(size_t N : 1, Range) 109 if(isInputRange!(Unqual!Range)) 110 { 111 Segment segment(Range range) 112 { 113 return Segment(range); 114 } 115 116 alias Unqual!Range R; 117 alias ElementType!Range E; 118 119 struct Segment{ 120 private: 121 R _range; 122 123 public: 124 this(R range) 125 { 126 _range = range; 127 } 128 129 130 static if(isInfinite!R) 131 enum bool e = false; 132 else 133 @property bool empty() 134 { 135 return _range.empty; 136 } 137 138 139 void popFront() 140 { 141 _range.popFront(); 142 } 143 static if(isBidirectionalRange!R) 144 void popBack() 145 { 146 _range.popBack(); 147 } 148 149 150 static if(isForwardRange!R) 151 @property typeof(this) save() 152 { 153 typeof(this) dst = this; 154 dst._range = dst._range.save; 155 return dst; 156 } 157 158 static if(hasLength!R) 159 { 160 @property size_t length() 161 { 162 return _range.length; 163 } 164 165 alias length opDollar; 166 } 167 168 static if(hasSlicing!R) 169 { 170 Segment opSlice() 171 { 172 static if(isForwardRange!R) 173 return save; 174 else 175 return typeof(this)(_range); 176 } 177 178 179 auto opSlice(size_t i, size_t j) 180 { 181 return segment!1(_range[i .. j]); 182 } 183 } 184 185 186 @property Tuple!E front() 187 { 188 return tuple(_range.front); 189 } 190 191 static if(isBidirectionalRange!R) 192 @property Tuple!E back() 193 { 194 return tuple(_range.back); 195 } 196 197 static if(isRandomAccessRange!R) 198 Tuple!E opIndex(size_t i) 199 { 200 return tuple(_range[i]); 201 } 202 203 static if(hasAssignableElements!R || hasSwappableElements!R || hasLvalueElements!R) 204 { 205 @property void front(Tuple!E e) 206 { 207 _range.front = e[0]; 208 } 209 210 211 static if(isBidirectionalRange!R) 212 { 213 @property void back(Tuple!E e) 214 { 215 _range.back = e[0]; 216 } 217 } 218 219 static if(isRandomAccessRange!R) 220 { 221 void opIndexAssign(Tuple!E e, size_t i) 222 { 223 _range[i] = e[0]; 224 } 225 } 226 } 227 228 } 229 } 230 231 232 unittest 233 { 234 //debug scope(failure) writefln("unittest Failure :%s(%s)", __FILE__, __LINE__); 235 debug scope(success) {writefln("Unittest Success :%s(%s)", __FILE__, __LINE__); stdout.flush();} 236 237 auto a = [0, 1, 2, 3, 4]; 238 auto sg = segment!1(a); 239 240 assert(equal(sg, [tuple(0), tuple(1), tuple(2), tuple(3), tuple(4)])); 241 assert(equal(sg.retro, [tuple(0), tuple(1), tuple(2), tuple(3), tuple(4)].retro)); 242 243 sg.front = tuple(3); 244 assert(equal(sg, [tuple(3), tuple(1), tuple(2), tuple(3), tuple(4)])); 245 246 sg[3] = tuple(2); 247 assert(equal(sg, [tuple(3), tuple(1), tuple(2), tuple(2), tuple(4)])); 248 249 assert(sg.length == 5); 250 251 sg.back = tuple(8); 252 assert(equal(sg, [tuple(3), tuple(1), tuple(2), tuple(2), tuple(8)])); 253 assert(sg[$-1] == tuple(8)); 254 255 assert(equal(sg[2..4], [tuple(2), tuple(2)])); 256 257 auto sv = sg.save; 258 sv.popFront(); 259 assert(equal(sg, [tuple(3), tuple(1), tuple(2), tuple(2), tuple(8)])); 260 assert(equal(sv, [tuple(1), tuple(2), tuple(2), tuple(8)])); 261 262 auto sl = sv[]; 263 sv.popFront(); 264 assert(equal(sl, [tuple(1), tuple(2), tuple(2), tuple(8)])); 265 assert(equal(sv, [tuple(2), tuple(2), tuple(8)])); 266 } 267 268 269 ///ditto 270 template segment(size_t N, Range) 271 if (isInputRange!(Unqual!Range) 272 && (isForwardRange!(Unqual!Range) ? (!isBidirectionalRange!(Unqual!Range) 273 && !isRandomAccessRange!(Unqual!Range)) : true)) 274 { 275 Segment segment(Range range) 276 { 277 return Segment(range); 278 } 279 280 alias Unqual!Range R; 281 alias ElementType!R E; 282 283 enum assE = isForwardRange!R && (hasAssignableElements!R || hasLvalueElements!R || hasSwappableElements!R); 284 285 struct Segment{ 286 private: 287 R _range; 288 E[] _front; 289 290 static if(assE) 291 R _assignRange; 292 293 public: 294 this(R range) 295 { 296 _range = range; 297 298 static if(assE) 299 _assignRange = _range.save; 300 301 for(int i = 0; i < N && !_range.empty; ++i, _range.popFront()) 302 _front ~= _range.front; 303 } 304 305 306 void popFront() 307 { 308 if(_range.empty) 309 _front = _front[1..$]; 310 else{ 311 _front = _front[1..$]; 312 _front ~= _range.front; 313 _range.popFront(); 314 static if(assE) 315 _assignRange.popFront(); 316 } 317 } 318 319 @property 320 Tuple!(TypeNuple!(E, N)) front() 321 { 322 return (cast(typeof(return)[])(cast(ubyte[])_front))[0]; 323 } 324 325 326 static if(assE) 327 @property void front(Tuple!(TypeNuple!(E, N)) e) 328 { 329 R _tmpRange = _assignRange.save; 330 331 _front = [e.field]; 332 333 for(int i = 0; i < N; ++i, _tmpRange.popFront) 334 _tmpRange.front = _front[i]; 335 } 336 337 338 static if(isForwardRange!R) { 339 @property Segment save() 340 { 341 Segment dst = this; 342 dst._range = dst._range.save; 343 344 static if(assE) 345 dst._assignRange = dst._assignRange.save; 346 347 return dst; 348 } 349 } 350 351 static if(isInfinite!R) 352 enum bool empty = false; 353 else 354 @property 355 bool empty() 356 { 357 return _front.length != N; 358 } 359 360 361 static if(hasLength!R){ 362 @property 363 size_t length() 364 { 365 return _range.length + !this.empty; 366 } 367 368 alias length opDollar; 369 } 370 371 static if(hasSlicing!R) 372 { 373 Segment opSlice() 374 { 375 static if(isInputRange!R) 376 return this; 377 else 378 return save; 379 } 380 381 auto opSlice(size_t i, size_t j) 382 { 383 return segment!N(_assignRange[i..j + (N-1)]); 384 } 385 } 386 } 387 } 388 389 390 unittest 391 { 392 //debug scope(failure) writefln("unittest Failure :%s(%s)", __FILE__, __LINE__); 393 debug scope(success) {writefln("Unittest Success :%s(%s)", __FILE__, __LINE__); stdout.flush();} 394 395 struct TRange 396 { 397 int _front, _end; 398 @property int front(){return _front;} 399 void popFront(){_front += 1;} 400 @property bool empty(){return _front == _end;} 401 @property TRange save(){return this;} 402 @property size_t length(){return _end - _front;} 403 alias length opDollar; 404 } 405 406 auto tr = TRange(0, 5); 407 auto sg2 = segment!2(tr); 408 assert(equal(sg2, [tuple(0, 1), tuple(1, 2), tuple(2, 3), tuple(3, 4)])); 409 410 auto sg2sv = sg2.save; 411 sg2sv.popFront(); 412 assert(equal(sg2, [tuple(0, 1), tuple(1, 2), tuple(2, 3), tuple(3, 4)])); 413 assert(equal(sg2sv, [tuple(1, 2), tuple(2, 3), tuple(3, 4)])); 414 415 assert(sg2.length == 4); 416 417 auto sg3 = segment!3(tr); 418 assert(equal(sg3, [tuple(0, 1, 2), tuple(1, 2, 3), tuple(2, 3, 4)])); 419 assert(sg3.length == 3); 420 421 auto sg4 = segment!4(tr); 422 assert(equal(sg4, [tuple(0, 1, 2, 3), tuple(1, 2, 3, 4)])); 423 assert(sg4.length == 2); 424 425 auto sg5 = segment!5(tr); 426 assert(equal(sg5, [tuple(0, 1, 2, 3, 4)])); 427 assert(sg5.length == 1); 428 429 auto sg6 = segment!6(tr); 430 assert(sg6.empty); 431 assert(sg6.length == 0); 432 433 auto tremp = TRange(0, 0); 434 assert(tremp.empty); 435 assert(segment!2(tremp).empty); 436 } 437 unittest 438 { 439 //debug scope(failure) writefln("unittest Failure :%s(%s)", __FILE__, __LINE__); 440 debug scope(success) {writefln("Unittest Success :%s(%s)", __FILE__, __LINE__); stdout.flush();} 441 442 struct TRange 443 { 444 int _front, _end; 445 @property int front(){return _front;} 446 void popFront(){_front += 1;} 447 @property bool empty(){return _front == _end;} 448 @property TRange save(){return this;} 449 @property size_t length(){return _end - _front;} 450 alias length opDollar; 451 } 452 453 auto tr = TRange(0, 5); 454 auto sg2 = segment!2(tr); 455 assert(equal(sg2, [tuple(0, 1), tuple(1, 2), tuple(2, 3), tuple(3, 4)])); 456 457 assert(sg2.length == 4); 458 459 auto sg3 = segment!3(tr); 460 assert(equal(sg3, [tuple(0, 1, 2), tuple(1, 2, 3), tuple(2, 3, 4)])); 461 assert(sg3.length == 3); 462 463 auto sg4 = segment!4(tr); 464 assert(equal(sg4, [tuple(0, 1, 2, 3), tuple(1, 2, 3, 4)])); 465 assert(sg4.length == 2); 466 467 auto sg5 = segment!5(tr); 468 assert(equal(sg5, [tuple(0, 1, 2, 3, 4)])); 469 assert(sg5.length == 1); 470 471 auto sg6 = segment!6(tr); 472 assert(sg6.empty); 473 assert(sg6.length == 0); 474 475 auto tremp = TRange(0, 0); 476 assert(tremp.empty); 477 assert(segment!2(tremp).empty); 478 } 479 unittest 480 { 481 //debug scope(failure) writefln("unittest Failure :%s(%s)", __FILE__, __LINE__); 482 debug scope(success) {writefln("Unittest Success :%s(%s)", __FILE__, __LINE__); stdout.flush();} 483 484 struct TRange 485 { 486 int[] a; 487 @property ref int front(){return a.front;} 488 @property bool empty(){return a.empty;} 489 void popFront(){a.popFront;} 490 @property TRange save(){return TRange(a.save);} 491 @property size_t length(){return a.length;} 492 alias length opDollar; 493 TRange opSlice(size_t i, size_t j){return TRange(a[i..j]);} 494 } 495 496 497 int[] a = [0, 1, 2, 3, 4]; 498 auto r = TRange(a); 499 auto sg = segment!2(r); 500 assert(equal(sg, [tuple(0, 1), tuple(1, 2), tuple(2, 3), tuple(3, 4)])); 501 assert(equal(sg[2..4], [tuple(2, 3), tuple(3, 4)])); 502 503 sg.front = tuple(3, 2); 504 assert(equal(sg, [tuple(3, 2), tuple(2, 2), tuple(2, 3), tuple(3, 4)])); 505 506 assert(sg.length == 4); 507 sg.popFront(); 508 assert(sg.length == 3); 509 sg.popFront(); 510 assert(sg.length == 2); 511 sg.popFront(); 512 assert(sg.length == 1); 513 sg.popFront(); 514 assert(sg.length == 0); 515 assert(sg.empty); 516 517 a = [0, 1, 2, 3, 4]; 518 r = TRange(a); 519 auto sg3 = segment!3(r); 520 assert(equal(sg3, [tuple(0, 1, 2), tuple(1, 2, 3), tuple(2, 3, 4)])); 521 sg3.front = tuple(2, 3, 1); 522 assert(equal(sg3, [tuple(2, 3, 1), tuple(3, 1, 3), tuple(1, 3, 4)])); 523 524 auto sl3 = sg3[]; 525 sl3.popFront(); 526 assert(equal(sg3, [tuple(2, 3, 1), tuple(3, 1, 3), tuple(1, 3, 4)])); 527 assert(equal(sl3, [tuple(3, 1, 3), tuple(1, 3, 4)])); 528 529 auto sv3 = sg3.save; 530 sv3.popFront(); 531 assert(equal(sg3, [tuple(2, 3, 1), tuple(3, 1, 3), tuple(1, 3, 4)])); 532 assert(equal(sv3, [tuple(3, 1, 3), tuple(1, 3, 4)])); 533 534 assert(sg3.length == 3); 535 sg3.popFront(); 536 assert(sg3.length == 2); 537 sg3.popFront(); 538 assert(sg3.length == 1); 539 sg3.popFront(); 540 assert(sg3.length == 0); 541 assert(sg3.empty); 542 } 543 544 545 ///ditto 546 template segment(size_t N, Range) 547 if(isRandomAccessRange!(Unqual!Range) 548 && isBidirectionalRange!(Unqual!Range) 549 && hasLength!(Unqual!Range)) 550 { 551 Segment segment(Range range) 552 { 553 return Segment(range); 554 } 555 556 557 alias Unqual!Range R; 558 alias ElementType!R E; 559 560 struct Segment{ 561 private: 562 R _range; 563 size_t _fidx; 564 size_t _bidx; 565 E[] _front; 566 E[] _back; 567 568 void reConstruct() 569 { 570 if(!empty){ 571 _front.length = 0; 572 _back.length = 0; 573 foreach(i; 0..N) 574 { 575 _front ~= _range[_fidx + i]; 576 _back ~= _range[_bidx + i]; 577 } 578 } 579 } 580 581 582 public: 583 this(R range) 584 { 585 _range = range; 586 _fidx = 0; 587 _bidx = _range.length - N; 588 589 reConstruct(); 590 } 591 592 593 @property bool empty() const 594 { 595 return (cast(int)_bidx - cast(int)_fidx) < 0; 596 } 597 598 599 void popFront() 600 { 601 ++_fidx; 602 if(!empty){ 603 _front = _front[1..$]; 604 _front ~= _range[_fidx + (N - 1)]; 605 } 606 } 607 608 609 void popBack() 610 { 611 --_bidx; 612 if(!empty){ 613 _back = _back[0..$-1]; 614 _back = [_range[_bidx]] ~ _back; 615 } 616 } 617 618 619 @property Segment save() 620 { 621 Segment dst = cast(Segment)this; 622 dst._range = dst._range.save; 623 dst._front = dst._front.dup; 624 dst._back = dst._back.dup; 625 return dst; 626 } 627 628 629 @property size_t length() const 630 { 631 return _bidx - _fidx + 1; 632 } 633 634 635 alias length opDollar; 636 637 638 auto opSlice() 639 { 640 return save; 641 } 642 643 644 Segment opSlice(size_t i, size_t j) 645 { 646 Segment dst = this.save; 647 dst._fidx += i; 648 dst._bidx -= this.length - j; 649 650 dst.reConstruct(); 651 return dst; 652 } 653 654 655 @property Tuple!(TypeNuple!(E, N)) front() 656 { 657 return (cast(typeof(return)[])cast(ubyte[])_front)[0]; 658 } 659 660 661 @property Tuple!(TypeNuple!(E, N)) back() 662 { 663 return (cast(typeof(return)[])cast(ubyte[])_back)[0]; 664 } 665 666 667 Tuple!(TypeNuple!(E, N)) opIndex(size_t i) 668 { 669 if(i == 0) 670 return this.front; 671 else if(i == this.length - 1) 672 return this.back; 673 else 674 { 675 E[N] dst; 676 foreach(j; 0 .. N) 677 dst[j] = _range[_fidx + i + j]; 678 return (cast(typeof(return)[])(cast(ubyte[])(dst[])))[0]; 679 } 680 } 681 682 683 static if(hasSwappableElements!R || hasLvalueElements!R || hasAssignableElements!R) 684 { 685 @property void front(Tuple!(TypeNuple!(E, N)) e) 686 { 687 E[] eSlice = [e.field]; 688 689 foreach(i; 0 .. N) 690 _range[i + _fidx] = eSlice[i]; 691 692 reConstruct(); 693 } 694 695 696 @property void back(Tuple!(TypeNuple!(E, N)) e) 697 { 698 E[] eSlice = [e.field]; 699 700 foreach(i; 0..N) 701 _range[i + _bidx] = eSlice[i]; 702 703 reConstruct(); 704 } 705 706 707 void opIndexAssign(Tuple!(TypeNuple!(E, N)) e, size_t i) 708 { 709 E[] eSlice = [e.field]; 710 711 foreach(j; 0..N) 712 _range[_fidx + i + j] = eSlice[j]; 713 714 reConstruct(); 715 } 716 } 717 } 718 } 719 720 721 unittest 722 { 723 //debug scope(failure) writefln("unittest Failure :%s(%s)", __FILE__, __LINE__); 724 debug scope(success) {writefln("Unittest Success :%s(%s)", __FILE__, __LINE__); stdout.flush();} 725 726 auto r1 = [0,1,2,3,4,5]; 727 auto s = segment!2(r1); 728 assert(equal(s, [tuple(0,1), tuple(1,2), tuple(2,3), tuple(3,4), tuple(4,5)][])); 729 assert(s.length == 5); // .length 730 // back/popBack: 731 assert(equal(retro(s), retro([tuple(0,1), tuple(1,2), tuple(2,3), tuple(3,4), tuple(4,5)][]))); 732 assert(s[3] == tuple(3,4)); // opIndex 733 s[3] = tuple(0,0); // opIndexAssign 734 assert(s[2] == tuple(2,0)); // it affects its neighbors. 735 assert(s[4] == tuple(0,5)); 736 assert(r1 == [0,1,2,0,0,5][]); // affects r1 back (no .dup internally) 737 738 s = segment!2(r1); 739 s.front = tuple(2, 0); 740 assert(s[0] == tuple(2, 0)); 741 742 s.back = tuple(100, 500); 743 assert(s[s.length - 1] == tuple(100, 500)); 744 745 auto sl = s[]; 746 assert(equal(sl, s)); 747 sl.popFront(); 748 sl.popBack(); 749 assert(equal(sl, s[1 .. s.length - 1])); 750 } 751 unittest 752 { 753 //debug scope(failure) writefln("unittest Failure :%s(%s)", __FILE__, __LINE__); 754 debug scope(success) {writefln("Unittest Success :%s(%s)", __FILE__, __LINE__); stdout.flush();} 755 756 auto st = ["a","b","c","d","e","f"]; 757 auto s2 = segment!3(st); 758 assert(s2.front == tuple("a","b","c")); 759 } 760 unittest 761 { 762 //debug scope(failure) writefln("unittest Failure :%s(%s)", __FILE__, __LINE__); 763 debug scope(success) {writefln("Unittest Success :%s(%s)", __FILE__, __LINE__); stdout.flush();} 764 765 auto r1 = [0,1,2,3,4,5]; // regenerates r1 766 auto s3 = segment!1(r1); 767 assert(equal(s3, [tuple(0), tuple(1), tuple(2), tuple(3), tuple(4), tuple(5)][])); 768 assert(equal(s3.retro, [tuple(0), tuple(1), tuple(2), tuple(3), tuple(4), tuple(5)].retro)); 769 auto r2 = map!"a*a"(r1); 770 auto s4 = segment!2(r2); // On a forward range 771 auto s4_2 = segment!2(r2); 772 assert(equal(s4_2, [tuple(0,1), tuple(1,4), tuple(4,9), tuple(9,16), tuple(16,25)][])); 773 } 774 unittest 775 { 776 //debug scope(failure) writefln("unittest Failure :%s(%s)", __FILE__, __LINE__); 777 debug scope(success) {writefln("Unittest Success :%s(%s)", __FILE__, __LINE__); stdout.flush();} 778 779 int[] e; 780 auto s5 = segment!2(e); 781 assert(s5.empty); 782 } 783 unittest 784 { 785 //debug scope(failure) writefln("unittest Failure :%s(%s)", __FILE__, __LINE__); 786 debug scope(success) {writefln("Unittest Success :%s(%s)", __FILE__, __LINE__); stdout.flush();} 787 788 auto ri = iota(0, 5); 789 auto sg = segment!2(ri); 790 assert(equal(sg, [tuple(0, 1), tuple(1, 2), tuple(2, 3), tuple(3, 4)])); 791 assert(equal(sg.retro, [tuple(0, 1), tuple(1, 2), tuple(2, 3), tuple(3, 4)].retro)); 792 assert(sg[0] == tuple(0, 1)); 793 assert(sg[1] == tuple(1, 2)); 794 assert(sg[2] == tuple(2, 3)); 795 assert(sg[3] == tuple(3, 4)); 796 assert(sg.length == 4); 797 } 798 799 ///ditto 800 template segment(size_t N, Range) 801 if(isRandomAccessRange!(Unqual!Range) 802 && !isBidirectionalRange!(Unqual!Range) 803 && isInfinite!(Unqual!Range)) 804 { 805 Segment segment(Range range) 806 { 807 return Segment(range); 808 } 809 810 811 alias Unqual!Range R; 812 alias ElementType!R E; 813 814 struct Segment{ 815 private: 816 R _range; 817 size_t _fidx; 818 E[] _front; 819 820 void reConstruct() 821 { 822 if(!empty){ 823 _front.length = 0; 824 foreach(i; 0..N) 825 _front ~= _range[_fidx + i]; 826 } 827 } 828 829 public: 830 this(R range) 831 { 832 _range = range; 833 _fidx = 0; 834 835 reConstruct(); 836 } 837 838 839 enum bool empty = false; 840 841 842 void popFront() 843 { 844 ++_fidx; 845 if(!empty){ 846 _front = _front[1..$]; 847 _front ~= _range[_fidx + (N - 1)]; 848 } 849 } 850 851 852 @property Segment save() 853 { 854 Segment dst = this; 855 dst._range = dst._range.save; 856 return dst; 857 } 858 859 860 @property Tuple!(TypeNuple!(E, N)) front() 861 { 862 return (cast(typeof(return)[])(cast(ubyte[])_front))[0]; 863 } 864 865 866 Tuple!(TypeNuple!(E, N)) opIndex(size_t i) 867 { 868 if(i == 0) 869 return this.front; 870 else 871 { 872 E[] dst; 873 foreach(j; 0 .. N) 874 dst ~= _range[_fidx + i + j]; 875 return (cast(typeof(return)[])(cast(ubyte[])dst))[0]; 876 } 877 } 878 879 880 static if(hasSwappableElements!R || hasLvalueElements!R || hasAssignableElements!R) 881 { 882 @property void front(Tuple!(TypeNuple!(E, N)) e) 883 { 884 E[] eSlice = [e.field]; 885 886 foreach(i; 0 .. N) 887 _range[i + _fidx] = eSlice[i]; 888 889 reConstruct(); 890 } 891 892 893 void opIndexAssign(Tuple!(TypeNuple!(E, N)) e, size_t i) 894 { 895 E[] eSlice = [e.field]; 896 897 foreach(j; 0..N) 898 _range[_fidx + i + j] = eSlice[j]; 899 900 reConstruct(); 901 } 902 } 903 } 904 } 905 906 907 unittest 908 { 909 //debug scope(failure) writefln("unittest Failure :%s(%s)", __FILE__, __LINE__); 910 debug scope(success) {writefln("Unittest Success :%s(%s)", __FILE__, __LINE__); stdout.flush();} 911 912 struct TRange 913 { 914 int[] a, s; 915 916 this(int[] r){ 917 a = r.save; 918 s = r.save; 919 } 920 921 @property ref int front(){return a.front;} 922 enum bool empty = false; 923 void popFront(){a.popFront; if(a.empty)a = s;} 924 @property typeof(this) save(){return this;} 925 ref int opIndex(size_t i){return a[i%s.length];} 926 } 927 928 929 auto r = segment!2(TRange([0, 1, 2, 3, 4])); 930 assert(equal(r.take(4), [tuple(0, 1), tuple(1, 2), tuple(2, 3), tuple(3, 4)])); 931 932 auto sv = r.save; 933 sv.popFront(); 934 assert(equal(r.take(4), [tuple(0, 1), tuple(1, 2), tuple(2, 3), tuple(3, 4)])); 935 assert(equal(sv.take(3), [tuple(1, 2), tuple(2, 3), tuple(3, 4)])); 936 937 assert(r[2] == tuple(2, 3)); 938 assert(r[0] == tuple(0, 1)); 939 940 r.front = tuple(100, 50); 941 assert(equal(r.take(4), [tuple(100, 50), tuple(50, 2), tuple(2, 3), tuple(3, 4)])); 942 943 r[1] = tuple(10, 20); 944 assert(equal(r.take(4), [tuple(100, 10), tuple(10, 20), tuple(20, 3), tuple(3, 4)])); 945 } 946 947 948 ///ditto 949 template segment(size_t N, Range) 950 if(isBidirectionalRange!(Unqual!Range) 951 && (isRandomAccessRange!(Unqual!Range) ? (!hasLength!(Unqual!Range) && isInfinite!(Unqual!Range)) : true)) 952 { 953 Segment segment(Range range) 954 { 955 return Segment(range); 956 } 957 958 959 alias Unqual!Range R; 960 alias ElementType!R E; 961 enum assE = hasAssignableElements!R && hasLvalueElements!R && hasSwappableElements!R; 962 963 964 struct Segment{ 965 private: 966 R _fRange; 967 R _bRange; 968 E[] _front; 969 E[] _back; 970 971 static if(assE || isRandomAccessRange!R) 972 R _assignRange; 973 974 static if(assE || isRandomAccessRange!R) 975 void reConstruct(){ 976 _front.length = 0; 977 _back.length = 0; 978 979 _fRange = _assignRange.save; 980 _bRange = _assignRange.save; 981 982 for(int i = 0; i < N && !_fRange.empty; ++i, _fRange.popFront()) 983 _front ~= _fRange.front(); 984 985 for(int i = 0; i < N && !_bRange.empty; ++i, _bRange.popBack()) 986 _back ~= _bRange.back(); 987 988 _back.reverse(); 989 } 990 991 992 993 public: 994 this(R range) 995 { 996 _fRange = range.save; 997 _bRange = range.save; 998 999 static if(assE || isRandomAccessRange!R) 1000 _assignRange = range.save; 1001 1002 for(int i = 0; i < N && !_fRange.empty; ++i, _fRange.popFront()) 1003 _front ~= _fRange.front(); 1004 1005 for(int i = 0; i < N && !_bRange.empty; ++i, _bRange.popBack()) 1006 _back ~= _bRange.back(); 1007 1008 _back.reverse(); 1009 } 1010 1011 1012 static if(isInfinite!R) 1013 enum bool empty = false; 1014 else 1015 @property bool empty() 1016 { 1017 return (_front.length < N) || (_back.length < N); 1018 } 1019 1020 1021 void popFront() 1022 { 1023 _front = _front[1..$]; 1024 1025 if(!_fRange.empty){ 1026 _front ~= _fRange.front; 1027 1028 _fRange.popFront(); 1029 _bRange.popFront(); 1030 } 1031 1032 static if(assE || isRandomAccessRange!R) 1033 _assignRange.popFront(); 1034 } 1035 1036 1037 void popBack() 1038 { 1039 _back = _back[0..$-1]; 1040 1041 if(!_bRange.empty){ 1042 _back = [_bRange.back] ~ _back; 1043 1044 _fRange.popBack(); 1045 _bRange.popBack(); 1046 } 1047 1048 static if(assE || isRandomAccessRange!R) 1049 _assignRange.popBack(); 1050 } 1051 1052 1053 @property Segment save() 1054 { 1055 Segment dst = this; 1056 dst._fRange = dst._fRange.save; 1057 dst._bRange = dst._bRange.save; 1058 1059 static if(assE) 1060 dst._assignRange = dst._assignRange.save; 1061 1062 return dst; 1063 } 1064 1065 1066 static if(hasLength!R) 1067 { 1068 @property size_t length() 1069 { 1070 return _fRange.length + ((_front.length == N && _back.length == N) ? 1 : 0); 1071 } 1072 1073 1074 alias length opDollar; 1075 } 1076 1077 1078 static if(hasSlicing!R) 1079 { 1080 Segment opSlice() 1081 { 1082 return save; 1083 } 1084 1085 1086 static if(assE || isRandomAccessRange!R) 1087 auto opSlice(size_t i, size_t j) 1088 { 1089 return segment!N(_assignRange[i..j + (N-1)]); 1090 } 1091 //else 1092 } 1093 1094 1095 @property Tuple!(TypeNuple!(E, N)) front() 1096 { 1097 return (cast(typeof(return)[])(cast(ubyte[])_front))[0]; 1098 } 1099 1100 1101 @property Tuple!(TypeNuple!(E, N)) back() 1102 { 1103 return (cast(typeof(return)[])(cast(ubyte[])_back))[0]; 1104 } 1105 1106 1107 static if(isRandomAccessRange!R) 1108 Tuple!(TypeNuple!(E, N)) opIndex(size_t i) 1109 { 1110 E[] dst; 1111 1112 foreach(j; 0..N) 1113 dst ~= _assignRange[i + j]; 1114 1115 return (cast(typeof(return)[])(cast(ubyte[])dst))[0]; 1116 } 1117 1118 1119 1120 static if(assE) 1121 { 1122 @property void front(Tuple!(TypeNuple!(E, N)) e) 1123 { 1124 R _tmp = _assignRange.save; 1125 _front = [e.field]; 1126 1127 for(int i = 0; i < N; ++i, _tmp.popFront()) 1128 _tmp.front = _front[i]; 1129 1130 reConstruct(); 1131 } 1132 1133 1134 @property void back(Tuple!(TypeNuple!(E, N)) e) 1135 { 1136 R _tmp = _assignRange.save; 1137 _back = [e.field]; 1138 1139 for(int i = N-1; i >= 0; --i, _tmp.popBack()) 1140 _tmp.back = _back[i]; 1141 1142 reConstruct(); 1143 } 1144 1145 static if(isRandomAccessRange!R) 1146 void opIndexAssign(Tuple!(TypeNuple!(E, N)) e, size_t i) 1147 { 1148 foreach(j; 0..N) 1149 _assignRange[i + j] = [e.field][j]; 1150 1151 reConstruct(); 1152 } 1153 } 1154 } 1155 } 1156 1157 unittest 1158 { 1159 //debug scope(failure) writefln("unittest Failure :%s(%s)", __FILE__, __LINE__); 1160 debug scope(success) {writefln("Unittest Success :%s(%s)", __FILE__, __LINE__); stdout.flush();} 1161 1162 struct TRange{ 1163 int[] a; 1164 @property int front(){return a.front;} 1165 @property bool empty(){return a.empty;} 1166 void popFront(){a.popFront();} 1167 void popBack(){a.popBack();} 1168 @property int back(){return a.back();} 1169 @property TRange save(){return TRange(a.save);} 1170 @property size_t length(){return a.length;} 1171 alias length opDollar; 1172 } 1173 1174 1175 auto r = TRange([0, 1, 2, 3, 4]); 1176 auto sg = segment!2(r); 1177 assert(equal(sg, [tuple(0, 1), tuple(1, 2), tuple(2, 3), tuple(3, 4)])); 1178 assert(equal(sg.retro, [tuple(0, 1), tuple(1, 2), tuple(2, 3), tuple(3, 4)].retro)); 1179 assert(sg.length == 4); 1180 1181 sg.popFront(); 1182 assert(equal(sg, [tuple(1, 2), tuple(2, 3), tuple(3, 4)])); 1183 assert(sg.length == 3); 1184 assert(!sg.empty); 1185 1186 auto sv = sg.save; 1187 sv.popFront(); 1188 assert(equal(sg, [tuple(1, 2), tuple(2, 3), tuple(3, 4)])); 1189 assert(equal(sv, [tuple(2, 3), tuple(3, 4)])); 1190 assert(sg.length == 3); 1191 assert(sv.length == 2); 1192 assert(!sg.empty); 1193 assert(!sv.empty); 1194 1195 sg.popFront(); 1196 assert(equal(sg, [tuple(2, 3), tuple(3, 4)])); 1197 assert(sg.length == 2); 1198 assert(!sg.empty); 1199 1200 sg.popFront(); 1201 assert(equal(sg, [tuple(3, 4)])); 1202 assert(sg.length == 1); 1203 assert(!sg.empty); 1204 1205 sg.popFront(); 1206 assert(sg.length == 0); 1207 assert(sg.empty); 1208 } 1209 unittest 1210 { 1211 //debug scope(failure) writefln("unittest Failure :%s(%s)", __FILE__, __LINE__); 1212 debug scope(success) {writefln("Unittest Success :%s(%s)", __FILE__, __LINE__); stdout.flush();} 1213 1214 struct TRange{ 1215 int[] a; 1216 @property ref int front(){return a.front;} 1217 @property bool empty(){return a.empty;} 1218 void popFront(){a.popFront();} 1219 void popBack(){a.popBack();} 1220 @property ref int back(){return a.back();} 1221 @property TRange save(){return TRange(a.save);} 1222 @property size_t length(){return a.length;} 1223 TRange opSlice(size_t i, size_t j){return TRange(a[i..j]);} 1224 alias length opDollar; 1225 } 1226 1227 1228 auto r = TRange([0, 1, 2, 3, 4]); 1229 auto sg = segment!2(r); 1230 assert(equal(sg, [tuple(0, 1), tuple(1, 2), tuple(2, 3), tuple(3, 4)])); 1231 assert(equal(retro(sg), [tuple(3, 4), tuple(2, 3), tuple(1, 2), tuple(0, 1)])); 1232 assert(sg.length == 4); 1233 assert(equal(sg[2..4], [tuple(2, 3), tuple(3, 4)])); 1234 1235 auto sgsv = sg.save; 1236 sgsv.popFront(); 1237 assert(equal(sg, [tuple(0, 1), tuple(1, 2), tuple(2, 3), tuple(3, 4)])); 1238 assert(equal(sgsv, [tuple(1, 2), tuple(2, 3), tuple(3, 4)])); 1239 1240 auto sgsv2 = sg[]; 1241 sgsv2.popFront(); 1242 assert(equal(sg, [tuple(0, 1), tuple(1, 2), tuple(2, 3), tuple(3, 4)])); 1243 assert(equal(sgsv2, [tuple(1, 2), tuple(2, 3), tuple(3, 4)])); 1244 1245 1246 sg.front = tuple(2, 2); 1247 assert(equal(sg, [tuple(2, 2), tuple(2, 2), tuple(2, 3), tuple(3, 4)])); 1248 assert(equal(retro(sg), [tuple(3, 4), tuple(2, 3), tuple(2, 2), tuple(2, 2)])); 1249 1250 sg.popFront(); 1251 assert(equal(sg, [tuple(2, 2), tuple(2, 3), tuple(3, 4)])); 1252 assert(equal(retro(sg), [tuple(3, 4), tuple(2, 3), tuple(2, 2)])); 1253 assert(sg.length == 3); 1254 assert(!sg.empty); 1255 1256 sg.popFront(); 1257 assert(equal(sg, [tuple(2, 3), tuple(3, 4)])); 1258 assert(equal(retro(sg), [tuple(3, 4), tuple(2, 3)])); 1259 assert(sg.length == 2); 1260 assert(!sg.empty); 1261 1262 sg.popFront(); 1263 assert(equal(sg, [tuple(3, 4)])); 1264 assert(equal(retro(sg), [tuple(3, 4)])); 1265 assert(sg.length == 1); 1266 assert(!sg.empty); 1267 1268 sg.front = tuple(2, 5); 1269 assert(equal(sg, [tuple(2, 5)])); 1270 assert(equal(retro(sg), [tuple(2, 5)])); 1271 assert(sg.length == 1); 1272 assert(!sg.empty); 1273 1274 sg.front = tuple(2, 1); 1275 assert(equal(sg, [tuple(2, 1)])); 1276 assert(sg.length == 1); 1277 assert(!sg.empty); 1278 1279 sg.popFront(); 1280 assert(sg.length == 0); 1281 assert(sg.empty); 1282 } 1283 unittest 1284 { 1285 //debug scope(failure) writefln("unittest Failure :%s(%s)", __FILE__, __LINE__); 1286 debug scope(success) {writefln("Unittest Success :%s(%s)", __FILE__, __LINE__); stdout.flush();} 1287 1288 struct TRange{ 1289 int[] a; 1290 @property ref int front(){return a.front;} 1291 @property bool empty(){return a.empty;} 1292 void popFront(){a.popFront();} 1293 void popBack(){a.popBack();} 1294 @property ref int back(){return a.back();} 1295 @property TRange save(){return TRange(a.save);} 1296 @property size_t length(){return a.length;} 1297 TRange opSlice(size_t i, size_t j){return TRange(a[i..j]);} 1298 alias length opDollar; 1299 } 1300 1301 1302 auto r = TRange([0, 1, 2, 3, 4]); 1303 auto sg = segment!3(r); 1304 assert(equal(sg, [tuple(0, 1, 2), tuple(1, 2, 3), tuple(2, 3, 4)])); 1305 assert(equal(retro(sg), [tuple(0, 1, 2), tuple(1, 2, 3), tuple(2, 3, 4)].retro)); 1306 assert(sg.length == 3); 1307 assert(equal(sg[2..3], [tuple(2, 3, 4)])); 1308 1309 sg.front = tuple(2, 2, 2); 1310 assert(equal(sg, [tuple(2, 2, 2), tuple(2, 2, 3), tuple(2, 3, 4)])); 1311 assert(equal(sg.retro, [tuple(2, 2, 2), tuple(2, 2, 3), tuple(2, 3, 4)].retro)); 1312 1313 sg.popFront(); 1314 assert(equal(sg, [tuple(2, 2, 3), tuple(2, 3, 4)])); 1315 assert(equal(sg.retro, [tuple(2, 2, 3), tuple(2, 3, 4)].retro)); 1316 assert(sg.length == 2); 1317 assert(!sg.empty); 1318 1319 sg.back = tuple(4, 4, 4); 1320 assert(equal(sg, [tuple(2, 4, 4), tuple(4, 4, 4)])); 1321 assert(equal(sg.retro, [tuple(2, 4, 4), tuple(4, 4, 4)].retro)); 1322 assert(sg.length == 2); 1323 assert(!sg.empty); 1324 1325 sg.popFront(); 1326 assert(equal(sg, [tuple(4, 4, 4)])); 1327 assert(equal(sg.retro, [tuple(4, 4, 4)].retro)); 1328 assert(sg.length == 1); 1329 assert(!sg.empty); 1330 1331 sg.popFront(); 1332 assert(sg.length == 0); 1333 assert(sg.empty); 1334 } 1335 unittest 1336 { 1337 //debug scope(failure) writefln("unittest Failure :%s(%s)", __FILE__, __LINE__); 1338 debug scope(success) {writefln("Unittest Success :%s(%s)", __FILE__, __LINE__); stdout.flush();} 1339 1340 struct TRange{ 1341 size_t f, b; 1342 int[] s; 1343 1344 this(int[] r){ 1345 f = 0; 1346 s = r; 1347 b = s.length - 1; 1348 } 1349 1350 @property ref int front(){return s[f];} 1351 enum bool empty = false; 1352 void popFront(){++f; if(f == s.length)f = 0;} 1353 void popBack(){b = (b == 0 ? s.length - 1 : b-1);} 1354 @property ref int back(){return s[b];} 1355 @property typeof(this) save(){return this;} 1356 auto opSlice(size_t i, size_t j){auto dst = this; dst.popFrontN(i); return dst.take(j - i);} 1357 ref int opIndex(size_t i){return s[(i+f)%s.length];} 1358 } 1359 1360 alias TRange Range; 1361 static assert(isInputRange!TRange); 1362 1363 auto r = TRange([0, 1, 2, 3, 4]); 1364 auto sg = segment!3(r); 1365 assert(equal(sg.take(3), [tuple(0, 1, 2), tuple(1, 2, 3), tuple(2, 3, 4)])); 1366 assert(equal(retro(sg).take(3), [tuple(2, 3, 4), tuple(1, 2, 3), tuple(0, 1, 2)])); 1367 assert(sg[2] == tuple(2, 3, 4)); 1368 //assert(equal(sg[2..3], [tuple(2, 3, 4)])); 1369 1370 sg.front = tuple(2, 2, 2); //[2, 2, 2, 3, 4] 1371 assert(equal(sg.take(3), [tuple(2, 2, 2), tuple(2, 2, 3), tuple(2, 3, 4)])); 1372 assert(equal(retro(sg).take(3), [tuple(2, 3, 4), tuple(2, 2, 3), tuple(2, 2, 2)])); 1373 1374 sg.popFront(); 1375 assert(equal(sg.take(3), [tuple(2, 2, 3), tuple(2, 3, 4), tuple(3, 4, 2)])); 1376 assert(equal(retro(sg).take(3), [tuple(2, 3, 4), tuple(2, 2, 3), tuple(2, 2, 2)])); 1377 assert(!sg.empty); 1378 1379 sg[1] = tuple(3, 3, 3); //[2, 2, 3, 3, 3] 1380 assert(equal(sg.take(3), [tuple(2, 3, 3), tuple(3, 3, 3), tuple(3, 3, 2)])); 1381 assert(equal(sg.retro.take(3), [tuple(3, 3, 3), tuple(2, 3, 3), tuple(2, 2, 3)])); 1382 assert(!sg.empty); 1383 1384 sg.back = tuple(2, 3, 4);//[2, 2, 2, 3, 4] 1385 assert(equal(sg.take(3), [tuple(2, 2, 3), tuple(2, 3, 4), tuple(3, 4, 2)])); 1386 assert(equal(sg.retro.take(3), [tuple(2, 3, 4), tuple(2, 2, 3), tuple(2, 2, 2)])); 1387 assert(!sg.empty); 1388 1389 sg.popBack(); 1390 assert(equal(sg.take(3), [tuple(2, 2, 3), tuple(2, 3, 4), tuple(3, 4, 2)])); 1391 assert(equal(sg.retro.take(3), [tuple(2, 2, 3), tuple(2, 2, 2), tuple(4, 2, 2)])); 1392 assert(!sg.empty); 1393 } 1394 1395 1396 /** 1397 concats elements 1398 */ 1399 auto concat(R)(R range) if (isRangeOfRanges!R) 1400 { 1401 static struct Concat 1402 { 1403 private: 1404 R _range; 1405 alias ElementType!R ET0; 1406 alias ElementType!ET0 ET1; 1407 ET0 _subrange; 1408 1409 static if(isRangeOfRanges!(R, isBidirectionalRange)) 1410 { 1411 ET0 _backSubrange; 1412 } 1413 1414 public: 1415 static if(isInfinite!R) 1416 enum bool empty = false; 1417 else 1418 { 1419 @property 1420 bool empty() 1421 { 1422 return _range.empty; 1423 } 1424 } 1425 1426 1427 @property 1428 auto ref front() 1429 { 1430 return _subrange.front; 1431 } 1432 1433 1434 static if(hasAssignableElements!ET0) 1435 { 1436 @property 1437 void front(ET1 v) 1438 { 1439 _subrange.front = v; 1440 } 1441 } 1442 1443 1444 /* 1445 static if(isRangeOfRange!(R, isForwardRange)) 1446 { 1447 @property 1448 Concat save() 1449 { 1450 return this; 1451 } 1452 } 1453 */ 1454 1455 1456 void popFront() 1457 { 1458 if (!_subrange.empty) _subrange.popFront; 1459 1460 while(_subrange.empty && !_range.empty){ 1461 _range.popFront; 1462 1463 if (!_range.empty) 1464 _subrange = _range.front; 1465 } 1466 } 1467 1468 1469 static if (isRangeOfRanges!(R, isBidirectionalRange)) 1470 { 1471 @property 1472 auto ref back() 1473 { 1474 return _backSubrange.back; 1475 } 1476 1477 1478 static if(hasAssignableElements!ET0) 1479 { 1480 @property 1481 void back(ET1 v) 1482 { 1483 _backSubrange.back = v; 1484 } 1485 } 1486 1487 1488 void popBack() 1489 { 1490 if (!_backSubrange.empty) _backSubrange.popBack; 1491 1492 while (_backSubrange.empty && !_range.empty) { 1493 _range.popBack; 1494 if (!_range.empty) _backSubrange = _range.back; 1495 } 1496 } 1497 1498 1499 auto retro() @property 1500 { 1501 static struct RetroConcat 1502 { 1503 auto ref front() @property 1504 { 1505 return _r.back; 1506 } 1507 1508 1509 auto ref back() @property 1510 { 1511 return _r.front; 1512 } 1513 1514 1515 static if(hasAssignableElements!ET0) 1516 { 1517 void front(ET1 v) @property 1518 { 1519 _r.back = v; 1520 } 1521 1522 1523 void back(ET1 v) @property 1524 { 1525 _r.front = v; 1526 } 1527 } 1528 1529 1530 void popFront() 1531 { 1532 _r.popBack(); 1533 } 1534 1535 1536 void popBack() 1537 { 1538 _r.popFront(); 1539 } 1540 1541 1542 static if(isInfinite!R) 1543 enum bool empty = false; 1544 else 1545 bool empty() @property 1546 { 1547 return _r.empty; 1548 } 1549 1550 1551 // save.. 1552 1553 1554 auto retro() @property 1555 { 1556 return _r; 1557 } 1558 1559 1560 private: 1561 Concat _r; 1562 } 1563 1564 1565 return RetroConcat(this); 1566 } 1567 } 1568 } 1569 1570 1571 Concat dst = {_range : range}; 1572 1573 enum initMethod = 1574 q{ 1575 if (!dst._range.empty){ 1576 %1$s = dst._range.%2$s; 1577 while (%1$s.empty && !dst._range.empty){ 1578 dst._range.%3$s; 1579 1580 if (!dst._range.empty) 1581 %1$s = dst._range.%2$s; 1582 } 1583 } 1584 }; 1585 1586 mixin(format(initMethod, "dst._subrange", "front", "popFront")); 1587 1588 static if (isRangeOfRanges!(R, isBidirectionalRange)) 1589 { 1590 mixin(format(initMethod, "dst._backSubrange", "back", "popBack")); 1591 } 1592 1593 return dst; 1594 } 1595 1596 /// ditto 1597 R concat(R)(R range) 1598 if(isSimpleRange!R) 1599 { 1600 return range; 1601 } 1602 1603 /// 1604 unittest 1605 { 1606 debug scope(failure) writefln("unittest Failure :%s(%s)", __FILE__, __LINE__); 1607 debug scope(success) {writefln("Unittest Success :%s(%s)", __FILE__, __LINE__); stdout.flush();} 1608 1609 int[][] r1 = [[0, 1, 2, 3], [4, 5, 6], [7, 8], [9], []]; 1610 auto c = concat(r1); 1611 assert(equal(c, [0, 1, 2, 3, 4, 5, 6, 7, 8, 9])); 1612 assert(equal(c.retro(), retro([0, 1, 2, 3, 4, 5, 6, 7, 8, 9]))); // bidir range 1613 assert(equal(c.retro.retro, c)); 1614 1615 assert(equal(concat(c), c)); 1616 1617 auto r2 = [0, 1, 2, 3, 4, 5]; 1618 assert(equal(r2.map!"[a, 2]".concat, [0, 2, 1, 2, 2, 2, 3, 2, 4, 2, 5, 2])); 1619 assert(equal(r2[0 .. 4].map!(a => repeat(a, a)).concat, [1, 2, 2, 3, 3, 3])); 1620 assert(equal(r2[0 .. 3].repeat(2).map!(map!"a + 1").concat, [1, 2, 3, 1, 2, 3])); 1621 1622 int[] emp; 1623 assert(emp.repeat(15).concat.empty); 1624 assert(emp.concat.empty); 1625 } 1626 1627 1628 /// 1629 auto flatten(size_t N = size_t.max, R)(R r) 1630 if(isInputRange!R) 1631 { 1632 static if(N > 0 && isRangeOfRanges!R) 1633 return r.concat.flatten!(N-1); 1634 else 1635 return r; 1636 } 1637 1638 /// 1639 unittest 1640 { 1641 auto d1 = [0, 1, 2, 3, 4, 5, 6, 7, 8]; 1642 assert(equal(d1.flatten, d1)); 1643 assert(equal(d1.flatten!0, d1)); 1644 1645 auto d2 = [[0, 1], [], [2, 3], [4, 5, 6, 7], [8]]; 1646 assert(equal(d2.flatten, d1)); 1647 assert(equal(d2.flatten!1, d1)); 1648 assert(equal(d2.flatten!0, d2)); 1649 1650 auto d3 = [[[0, 1], [], [2, 3]], [[4, 5, 6, 7], [8]]]; 1651 assert(equal(d3.flatten, d1)); 1652 assert(equal(d3.flatten!0, d3)); 1653 assert(equal(d3.flatten!1, d2)); 1654 assert(equal(d3.flatten!2, d1)); 1655 } 1656 1657 1658 /** 1659 Haskell等の言語での$(D takeWhile)の実装です。 1660 この実装では、predは任意個数の引数を取ることができます。 1661 たとえば、2引数関数の場合、第一引数にはレンジの先頭の値が、第二引数にはレンジの次の値が格納されます。 1662 */ 1663 auto takeWhile(alias pred, R, T...)(R range, T args) 1664 if(isInputRange!R) 1665 { 1666 template Parameter(U...) 1667 { 1668 enum bool empty = false; 1669 alias front = U; 1670 alias tail() = Parameter!(ElementType!R, U); 1671 } 1672 1673 alias _pred = naryFun!pred; 1674 enum arityN = argumentInfo!(_pred, Parameter!T).arity - T.length; 1675 1676 static if(arityN <= 1) 1677 return TakeWhileResult!(_pred, arityN, R, T)(range, args); 1678 else 1679 return TakeWhileResult!(_pred, arityN, typeof(segment!arityN(range)), T)(segment!arityN(range), args); 1680 } 1681 1682 1683 1684 private struct TakeWhileResult(alias _pred, size_t arityN, SegR, T...) 1685 { 1686 @property 1687 bool empty() 1688 { 1689 if(_r.empty) 1690 return true; 1691 1692 static if(arityN == 0) 1693 return !_pred(_subArgs); 1694 else static if(arityN == 1) 1695 return !_pred(_r.front, _subArgs); 1696 else 1697 return !_pred(_r.front.field, _subArgs); 1698 } 1699 1700 1701 @property 1702 auto front() 1703 { 1704 static if(arityN <= 1) 1705 return _r.front; 1706 else 1707 return _r.front.field[0]; 1708 } 1709 1710 1711 void popFront() 1712 { 1713 _r.popFront(); 1714 } 1715 1716 1717 static if(isForwardRange!(typeof(_r))) 1718 { 1719 @property 1720 auto save() 1721 { 1722 return TakeWhileResult!(_pred, arityN, typeof(_r.save), T)(_r.save, _subArgs); 1723 } 1724 } 1725 1726 private: 1727 SegR _r; 1728 T _subArgs; 1729 } 1730 1731 1732 /// ditto 1733 unittest 1734 { 1735 debug scope(failure) writefln("unittest Failure :%s(%s)", __FILE__, __LINE__); 1736 debug scope(success) {writefln("Unittest Success :%s(%s)", __FILE__, __LINE__); stdout.flush();} 1737 1738 int[] em; 1739 assert(takeWhile!"true"(em).empty); 1740 1741 auto r1 = [1, 2, 3, 4, 3, 2, 1]; 1742 auto tw1 = takeWhile!"a < b"(r1); 1743 assert(equal(tw1, [1, 2, 3])); 1744 1745 auto tw2 = takeWhile!"a < b && b < c"(r1); 1746 assert(equal(tw2, [1, 2])); 1747 1748 auto tw3 = takeWhile!"a == (b - c)"(r1, 1); 1749 assert(equal(tw3, [1, 2, 3])); 1750 1751 auto tw4 = takeWhile!"true"(r1); 1752 assert(equal(tw4, r1)); 1753 1754 auto tw5 = takeWhile!"false"(r1); 1755 assert(tw5.empty); 1756 }