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.functional, 37 std.range, 38 std..string, 39 std.traits, 40 std.typecons; 41 42 debug import std.stdio; 43 44 import carbon.functional, 45 carbon.templates, 46 carbon.traits; 47 48 49 /** 50 true if isInputRange!R is true and isInputRange!R is false. 51 */ 52 enum isSimpleRange(R, alias I = isInputRange) = 53 I!(R) && !I!(ElementType!R); 54 55 56 /** 57 true if both isInputRange!R and isInputRange!R are true. 58 */ 59 enum isRangeOfRanges(R, alias I = isInputRange) = 60 I!(R) && I!(ElementType!R); 61 62 63 64 /** 65 あるレンジのN個の連続する要素のリストを返します。 66 67 Example: 68 ---- 69 auto r1 = [0, 1, 2, 3, 4, 5]; 70 auto s = segment!2(r1); 71 assert(equal(s, [tuple(0, 1), tuple(1, 2), tuple(2, 3), tuple(3, 4), tuple(4, 5)][])); 72 assert(s.length == 5); // .length 73 // back/popBack: 74 assert(equal(retro(s), retro([tuple(0, 1), tuple(1, 2), tuple(2, 3), tuple(3, 4), tuple(4, 5)][]))); 75 assert(s[3] == tuple(3, 4)); // opIndex 76 s[3] = tuple(0, 0); // opIndexAssign not ref opIndex 77 assert(s[2] == tuple(2, 0)); // it affects its neighbors. 78 assert(s[4] == tuple(0, 5)); 79 assert(r1 == [0, 1, 2, 0, 0, 5][]); // affects r1 back (no .dup internally) 80 81 82 auto st = ["a","b","c","d","e","f"]; 83 auto s2 = segment!3(st); 84 assert(s2.front == tuple("a","b","c")); 85 86 87 auto r1 = [0,1,2,3,4,5]; // regenerates r1 88 auto s3 = segment!1(r1); 89 assert(equal(s3, [tuple(0), tuple(1), tuple(2), tuple(3), tuple(4), tuple(5)][])); 90 auto r2 = map!"a*a"(r1); 91 auto s4 = segment!2(r2); // On a forward range 92 assert(equal(s4, [tuple(0,1), tuple(1,4), tuple(4,9), tuple(9,16), tuple(16,25)][])); 93 94 95 int[] e; 96 auto s5 = segment!2(e); 97 assert(s5.empty); 98 ---- 99 100 Authors: Komatsu Kazuki 101 */ 102 template SegmentType(size_t N, R) 103 if(isInputRange!(Unqual!R) && N > 0) 104 { 105 alias typeof(segment!N(R.init)) SegmentType; 106 } 107 108 109 ///ditto 110 template segment(size_t N : 1, Range) 111 if(isInputRange!(Unqual!Range)) 112 { 113 Segment segment(Range range) 114 { 115 return Segment(range); 116 } 117 118 alias Unqual!Range R; 119 alias ElementType!Range E; 120 121 struct Segment{ 122 private: 123 R _range; 124 125 public: 126 this(R range) 127 { 128 _range = range; 129 } 130 131 132 static if(isInfinite!R) 133 enum bool e = false; 134 else 135 @property bool empty() 136 { 137 return _range.empty; 138 } 139 140 141 void popFront() 142 { 143 _range.popFront(); 144 } 145 static if(isBidirectionalRange!R) 146 void popBack() 147 { 148 _range.popBack(); 149 } 150 151 152 static if(isForwardRange!R) 153 @property typeof(this) save() 154 { 155 typeof(this) dst = this; 156 dst._range = dst._range.save; 157 return dst; 158 } 159 160 static if(hasLength!R) 161 { 162 @property size_t length() 163 { 164 return _range.length; 165 } 166 167 alias length opDollar; 168 } 169 170 static if(hasSlicing!R) 171 { 172 Segment opSlice() 173 { 174 static if(isForwardRange!R) 175 return save; 176 else 177 return typeof(this)(_range); 178 } 179 180 181 auto opSlice(size_t i, size_t j) 182 { 183 return segment!1(_range[i .. j]); 184 } 185 } 186 187 188 @property Tuple!E front() 189 { 190 return tuple(_range.front); 191 } 192 193 static if(isBidirectionalRange!R) 194 @property Tuple!E back() 195 { 196 return tuple(_range.back); 197 } 198 199 static if(isRandomAccessRange!R) 200 Tuple!E opIndex(size_t i) 201 { 202 return tuple(_range[i]); 203 } 204 205 static if(hasAssignableElements!R || hasSwappableElements!R || hasLvalueElements!R) 206 { 207 @property void front(Tuple!E e) 208 { 209 _range.front = e[0]; 210 } 211 212 213 static if(isBidirectionalRange!R) 214 { 215 @property void back(Tuple!E e) 216 { 217 _range.back = e[0]; 218 } 219 } 220 221 static if(isRandomAccessRange!R) 222 { 223 void opIndexAssign(Tuple!E e, size_t i) 224 { 225 _range[i] = e[0]; 226 } 227 } 228 } 229 230 } 231 } 232 233 234 unittest 235 { 236 //debug scope(failure) writefln("unittest Failure :%s(%s)", __FILE__, __LINE__); 237 debug scope(success) {writefln("Unittest Success :%s(%s)", __FILE__, __LINE__); stdout.flush();} 238 239 auto a = [0, 1, 2, 3, 4]; 240 auto sg = segment!1(a); 241 242 assert(equal(sg, [tuple(0), tuple(1), tuple(2), tuple(3), tuple(4)])); 243 assert(equal(sg.retro, [tuple(0), tuple(1), tuple(2), tuple(3), tuple(4)].retro)); 244 245 sg.front = tuple(3); 246 assert(equal(sg, [tuple(3), tuple(1), tuple(2), tuple(3), tuple(4)])); 247 248 sg[3] = tuple(2); 249 assert(equal(sg, [tuple(3), tuple(1), tuple(2), tuple(2), tuple(4)])); 250 251 assert(sg.length == 5); 252 253 sg.back = tuple(8); 254 assert(equal(sg, [tuple(3), tuple(1), tuple(2), tuple(2), tuple(8)])); 255 assert(sg[$-1] == tuple(8)); 256 257 assert(equal(sg[2..4], [tuple(2), tuple(2)])); 258 259 auto sv = sg.save; 260 sv.popFront(); 261 assert(equal(sg, [tuple(3), tuple(1), tuple(2), tuple(2), tuple(8)])); 262 assert(equal(sv, [tuple(1), tuple(2), tuple(2), tuple(8)])); 263 264 auto sl = sv[]; 265 sv.popFront(); 266 assert(equal(sl, [tuple(1), tuple(2), tuple(2), tuple(8)])); 267 assert(equal(sv, [tuple(2), tuple(2), tuple(8)])); 268 } 269 270 271 ///ditto 272 template segment(size_t N, Range) 273 if (isInputRange!(Unqual!Range) 274 && (isForwardRange!(Unqual!Range) ? (!isBidirectionalRange!(Unqual!Range) 275 && !isRandomAccessRange!(Unqual!Range)) : true)) 276 { 277 Segment segment(Range range) 278 { 279 return Segment(range); 280 } 281 282 alias Unqual!Range R; 283 alias ElementType!R E; 284 285 enum assE = isForwardRange!R && (hasAssignableElements!R || hasLvalueElements!R || hasSwappableElements!R); 286 287 struct Segment{ 288 private: 289 R _range; 290 E[] _front; 291 292 static if(assE) 293 R _assignRange; 294 295 public: 296 this(R range) 297 { 298 _range = range; 299 300 static if(assE) 301 _assignRange = _range.save; 302 303 for(int i = 0; i < N && !_range.empty; ++i, _range.popFront()) 304 _front ~= _range.front; 305 } 306 307 308 void popFront() 309 { 310 if(_range.empty) 311 _front = _front[1..$]; 312 else{ 313 _front = _front[1..$]; 314 _front ~= _range.front; 315 _range.popFront(); 316 static if(assE) 317 _assignRange.popFront(); 318 } 319 } 320 321 @property 322 Tuple!(TypeNuple!(E, N)) front() 323 { 324 return (cast(typeof(return)[])(cast(ubyte[])_front))[0]; 325 } 326 327 328 static if(assE) 329 @property void front(Tuple!(TypeNuple!(E, N)) e) 330 { 331 R _tmpRange = _assignRange.save; 332 333 _front = [e.field]; 334 335 for(int i = 0; i < N; ++i, _tmpRange.popFront) 336 _tmpRange.front = _front[i]; 337 } 338 339 340 static if(isForwardRange!R) { 341 @property Segment save() 342 { 343 Segment dst = this; 344 dst._range = dst._range.save; 345 346 static if(assE) 347 dst._assignRange = dst._assignRange.save; 348 349 return dst; 350 } 351 } 352 353 static if(isInfinite!R) 354 enum bool empty = false; 355 else 356 @property 357 bool empty() 358 { 359 return _front.length != N; 360 } 361 362 363 static if(hasLength!R){ 364 @property 365 size_t length() 366 { 367 return _range.length + !this.empty; 368 } 369 370 alias length opDollar; 371 } 372 373 static if(hasSlicing!R) 374 { 375 Segment opSlice() 376 { 377 static if(isInputRange!R) 378 return this; 379 else 380 return save; 381 } 382 383 auto opSlice(size_t i, size_t j) 384 { 385 return segment!N(_assignRange[i..j + (N-1)]); 386 } 387 } 388 } 389 } 390 391 392 unittest 393 { 394 //debug scope(failure) writefln("unittest Failure :%s(%s)", __FILE__, __LINE__); 395 debug scope(success) {writefln("Unittest Success :%s(%s)", __FILE__, __LINE__); stdout.flush();} 396 397 struct TRange 398 { 399 int _front, _end; 400 @property int front(){return _front;} 401 void popFront(){_front += 1;} 402 @property bool empty(){return _front == _end;} 403 @property TRange save(){return this;} 404 @property size_t length(){return _end - _front;} 405 alias length opDollar; 406 } 407 408 auto tr = TRange(0, 5); 409 auto sg2 = segment!2(tr); 410 assert(equal(sg2, [tuple(0, 1), tuple(1, 2), tuple(2, 3), tuple(3, 4)])); 411 412 auto sg2sv = sg2.save; 413 sg2sv.popFront(); 414 assert(equal(sg2, [tuple(0, 1), tuple(1, 2), tuple(2, 3), tuple(3, 4)])); 415 assert(equal(sg2sv, [tuple(1, 2), tuple(2, 3), tuple(3, 4)])); 416 417 assert(sg2.length == 4); 418 419 auto sg3 = segment!3(tr); 420 assert(equal(sg3, [tuple(0, 1, 2), tuple(1, 2, 3), tuple(2, 3, 4)])); 421 assert(sg3.length == 3); 422 423 auto sg4 = segment!4(tr); 424 assert(equal(sg4, [tuple(0, 1, 2, 3), tuple(1, 2, 3, 4)])); 425 assert(sg4.length == 2); 426 427 auto sg5 = segment!5(tr); 428 assert(equal(sg5, [tuple(0, 1, 2, 3, 4)])); 429 assert(sg5.length == 1); 430 431 auto sg6 = segment!6(tr); 432 assert(sg6.empty); 433 assert(sg6.length == 0); 434 435 auto tremp = TRange(0, 0); 436 assert(tremp.empty); 437 assert(segment!2(tremp).empty); 438 } 439 unittest 440 { 441 //debug scope(failure) writefln("unittest Failure :%s(%s)", __FILE__, __LINE__); 442 debug scope(success) {writefln("Unittest Success :%s(%s)", __FILE__, __LINE__); stdout.flush();} 443 444 struct TRange 445 { 446 int _front, _end; 447 @property int front(){return _front;} 448 void popFront(){_front += 1;} 449 @property bool empty(){return _front == _end;} 450 @property TRange save(){return this;} 451 @property size_t length(){return _end - _front;} 452 alias length opDollar; 453 } 454 455 auto tr = TRange(0, 5); 456 auto sg2 = segment!2(tr); 457 assert(equal(sg2, [tuple(0, 1), tuple(1, 2), tuple(2, 3), tuple(3, 4)])); 458 459 assert(sg2.length == 4); 460 461 auto sg3 = segment!3(tr); 462 assert(equal(sg3, [tuple(0, 1, 2), tuple(1, 2, 3), tuple(2, 3, 4)])); 463 assert(sg3.length == 3); 464 465 auto sg4 = segment!4(tr); 466 assert(equal(sg4, [tuple(0, 1, 2, 3), tuple(1, 2, 3, 4)])); 467 assert(sg4.length == 2); 468 469 auto sg5 = segment!5(tr); 470 assert(equal(sg5, [tuple(0, 1, 2, 3, 4)])); 471 assert(sg5.length == 1); 472 473 auto sg6 = segment!6(tr); 474 assert(sg6.empty); 475 assert(sg6.length == 0); 476 477 auto tremp = TRange(0, 0); 478 assert(tremp.empty); 479 assert(segment!2(tremp).empty); 480 } 481 unittest 482 { 483 //debug scope(failure) writefln("unittest Failure :%s(%s)", __FILE__, __LINE__); 484 debug scope(success) {writefln("Unittest Success :%s(%s)", __FILE__, __LINE__); stdout.flush();} 485 486 struct TRange 487 { 488 int[] a; 489 @property ref int front(){return a.front;} 490 @property bool empty(){return a.empty;} 491 void popFront(){a.popFront;} 492 @property TRange save(){return TRange(a.save);} 493 @property size_t length(){return a.length;} 494 alias length opDollar; 495 TRange opSlice(size_t i, size_t j){return TRange(a[i..j]);} 496 } 497 498 499 int[] a = [0, 1, 2, 3, 4]; 500 auto r = TRange(a); 501 auto sg = segment!2(r); 502 assert(equal(sg, [tuple(0, 1), tuple(1, 2), tuple(2, 3), tuple(3, 4)])); 503 assert(equal(sg[2..4], [tuple(2, 3), tuple(3, 4)])); 504 505 sg.front = tuple(3, 2); 506 assert(equal(sg, [tuple(3, 2), tuple(2, 2), tuple(2, 3), tuple(3, 4)])); 507 508 assert(sg.length == 4); 509 sg.popFront(); 510 assert(sg.length == 3); 511 sg.popFront(); 512 assert(sg.length == 2); 513 sg.popFront(); 514 assert(sg.length == 1); 515 sg.popFront(); 516 assert(sg.length == 0); 517 assert(sg.empty); 518 519 a = [0, 1, 2, 3, 4]; 520 r = TRange(a); 521 auto sg3 = segment!3(r); 522 assert(equal(sg3, [tuple(0, 1, 2), tuple(1, 2, 3), tuple(2, 3, 4)])); 523 sg3.front = tuple(2, 3, 1); 524 assert(equal(sg3, [tuple(2, 3, 1), tuple(3, 1, 3), tuple(1, 3, 4)])); 525 526 auto sl3 = sg3[]; 527 sl3.popFront(); 528 assert(equal(sg3, [tuple(2, 3, 1), tuple(3, 1, 3), tuple(1, 3, 4)])); 529 assert(equal(sl3, [tuple(3, 1, 3), tuple(1, 3, 4)])); 530 531 auto sv3 = sg3.save; 532 sv3.popFront(); 533 assert(equal(sg3, [tuple(2, 3, 1), tuple(3, 1, 3), tuple(1, 3, 4)])); 534 assert(equal(sv3, [tuple(3, 1, 3), tuple(1, 3, 4)])); 535 536 assert(sg3.length == 3); 537 sg3.popFront(); 538 assert(sg3.length == 2); 539 sg3.popFront(); 540 assert(sg3.length == 1); 541 sg3.popFront(); 542 assert(sg3.length == 0); 543 assert(sg3.empty); 544 } 545 546 547 ///ditto 548 template segment(size_t N, Range) 549 if(isRandomAccessRange!(Unqual!Range) 550 && isBidirectionalRange!(Unqual!Range) 551 && hasLength!(Unqual!Range)) 552 { 553 Segment segment(Range range) 554 { 555 return Segment(range); 556 } 557 558 559 alias Unqual!Range R; 560 alias ElementType!R E; 561 562 struct Segment{ 563 private: 564 R _range; 565 size_t _fidx; 566 size_t _bidx; 567 E[] _front; 568 E[] _back; 569 570 void reConstruct() 571 { 572 if(!empty){ 573 _front.length = 0; 574 _back.length = 0; 575 foreach(i; 0..N) 576 { 577 _front ~= _range[_fidx + i]; 578 _back ~= _range[_bidx + i]; 579 } 580 } 581 } 582 583 584 public: 585 this(R range) 586 { 587 _range = range; 588 _fidx = 0; 589 _bidx = _range.length - N; 590 591 reConstruct(); 592 } 593 594 595 @property bool empty() const 596 { 597 return (cast(int)_bidx - cast(int)_fidx) < 0; 598 } 599 600 601 void popFront() 602 { 603 ++_fidx; 604 if(!empty){ 605 _front = _front[1..$]; 606 _front ~= _range[_fidx + (N - 1)]; 607 } 608 } 609 610 611 void popBack() 612 { 613 --_bidx; 614 if(!empty){ 615 _back = _back[0..$-1]; 616 _back = [_range[_bidx]] ~ _back; 617 } 618 } 619 620 621 @property Segment save() 622 { 623 Segment dst = cast(Segment)this; 624 dst._range = dst._range.save; 625 dst._front = dst._front.dup; 626 dst._back = dst._back.dup; 627 return dst; 628 } 629 630 631 @property size_t length() const 632 { 633 return _bidx - _fidx + 1; 634 } 635 636 637 alias length opDollar; 638 639 640 auto opSlice() 641 { 642 return save; 643 } 644 645 646 Segment opSlice(size_t i, size_t j) 647 { 648 Segment dst = this.save; 649 dst._fidx += i; 650 dst._bidx -= this.length - j; 651 652 dst.reConstruct(); 653 return dst; 654 } 655 656 657 @property Tuple!(TypeNuple!(E, N)) front() 658 { 659 return (cast(typeof(return)[])cast(ubyte[])_front)[0]; 660 } 661 662 663 @property Tuple!(TypeNuple!(E, N)) back() 664 { 665 return (cast(typeof(return)[])cast(ubyte[])_back)[0]; 666 } 667 668 669 Tuple!(TypeNuple!(E, N)) opIndex(size_t i) 670 { 671 if(i == 0) 672 return this.front; 673 else if(i == this.length - 1) 674 return this.back; 675 else 676 { 677 E[N] dst; 678 foreach(j; 0 .. N) 679 dst[j] = _range[_fidx + i + j]; 680 return (cast(typeof(return)[])(cast(ubyte[])(dst[])))[0]; 681 } 682 } 683 684 685 static if(hasSwappableElements!R || hasLvalueElements!R || hasAssignableElements!R) 686 { 687 @property void front(Tuple!(TypeNuple!(E, N)) e) 688 { 689 E[] eSlice = [e.field]; 690 691 foreach(i; 0 .. N) 692 _range[i + _fidx] = eSlice[i]; 693 694 reConstruct(); 695 } 696 697 698 @property void back(Tuple!(TypeNuple!(E, N)) e) 699 { 700 E[] eSlice = [e.field]; 701 702 foreach(i; 0..N) 703 _range[i + _bidx] = eSlice[i]; 704 705 reConstruct(); 706 } 707 708 709 void opIndexAssign(Tuple!(TypeNuple!(E, N)) e, size_t i) 710 { 711 E[] eSlice = [e.field]; 712 713 foreach(j; 0..N) 714 _range[_fidx + i + j] = eSlice[j]; 715 716 reConstruct(); 717 } 718 } 719 } 720 } 721 722 723 unittest 724 { 725 //debug scope(failure) writefln("unittest Failure :%s(%s)", __FILE__, __LINE__); 726 debug scope(success) {writefln("Unittest Success :%s(%s)", __FILE__, __LINE__); stdout.flush();} 727 728 auto r1 = [0,1,2,3,4,5]; 729 auto s = segment!2(r1); 730 assert(equal(s, [tuple(0,1), tuple(1,2), tuple(2,3), tuple(3,4), tuple(4,5)][])); 731 assert(s.length == 5); // .length 732 // back/popBack: 733 assert(equal(retro(s), retro([tuple(0,1), tuple(1,2), tuple(2,3), tuple(3,4), tuple(4,5)][]))); 734 assert(s[3] == tuple(3,4)); // opIndex 735 s[3] = tuple(0,0); // opIndexAssign 736 assert(s[2] == tuple(2,0)); // it affects its neighbors. 737 assert(s[4] == tuple(0,5)); 738 assert(r1 == [0,1,2,0,0,5][]); // affects r1 back (no .dup internally) 739 740 s = segment!2(r1); 741 s.front = tuple(2, 0); 742 assert(s[0] == tuple(2, 0)); 743 744 s.back = tuple(100, 500); 745 assert(s[s.length - 1] == tuple(100, 500)); 746 747 auto sl = s[]; 748 assert(equal(sl, s)); 749 sl.popFront(); 750 sl.popBack(); 751 assert(equal(sl, s[1 .. s.length - 1])); 752 } 753 unittest 754 { 755 //debug scope(failure) writefln("unittest Failure :%s(%s)", __FILE__, __LINE__); 756 debug scope(success) {writefln("Unittest Success :%s(%s)", __FILE__, __LINE__); stdout.flush();} 757 758 auto st = ["a","b","c","d","e","f"]; 759 auto s2 = segment!3(st); 760 assert(s2.front == tuple("a","b","c")); 761 } 762 unittest 763 { 764 //debug scope(failure) writefln("unittest Failure :%s(%s)", __FILE__, __LINE__); 765 debug scope(success) {writefln("Unittest Success :%s(%s)", __FILE__, __LINE__); stdout.flush();} 766 767 auto r1 = [0,1,2,3,4,5]; // regenerates r1 768 auto s3 = segment!1(r1); 769 assert(equal(s3, [tuple(0), tuple(1), tuple(2), tuple(3), tuple(4), tuple(5)][])); 770 assert(equal(s3.retro, [tuple(0), tuple(1), tuple(2), tuple(3), tuple(4), tuple(5)].retro)); 771 auto r2 = map!"a*a"(r1); 772 auto s4 = segment!2(r2); // On a forward range 773 auto s4_2 = segment!2(r2); 774 assert(equal(s4_2, [tuple(0,1), tuple(1,4), tuple(4,9), tuple(9,16), tuple(16,25)][])); 775 } 776 unittest 777 { 778 //debug scope(failure) writefln("unittest Failure :%s(%s)", __FILE__, __LINE__); 779 debug scope(success) {writefln("Unittest Success :%s(%s)", __FILE__, __LINE__); stdout.flush();} 780 781 int[] e; 782 auto s5 = segment!2(e); 783 assert(s5.empty); 784 } 785 unittest 786 { 787 //debug scope(failure) writefln("unittest Failure :%s(%s)", __FILE__, __LINE__); 788 debug scope(success) {writefln("Unittest Success :%s(%s)", __FILE__, __LINE__); stdout.flush();} 789 790 auto ri = iota(0, 5); 791 auto sg = segment!2(ri); 792 assert(equal(sg, [tuple(0, 1), tuple(1, 2), tuple(2, 3), tuple(3, 4)])); 793 assert(equal(sg.retro, [tuple(0, 1), tuple(1, 2), tuple(2, 3), tuple(3, 4)].retro)); 794 assert(sg[0] == tuple(0, 1)); 795 assert(sg[1] == tuple(1, 2)); 796 assert(sg[2] == tuple(2, 3)); 797 assert(sg[3] == tuple(3, 4)); 798 assert(sg.length == 4); 799 } 800 801 ///ditto 802 template segment(size_t N, Range) 803 if(isRandomAccessRange!(Unqual!Range) 804 && !isBidirectionalRange!(Unqual!Range) 805 && isInfinite!(Unqual!Range)) 806 { 807 Segment segment(Range range) 808 { 809 return Segment(range); 810 } 811 812 813 alias Unqual!Range R; 814 alias ElementType!R E; 815 816 struct Segment{ 817 private: 818 R _range; 819 size_t _fidx; 820 E[] _front; 821 822 void reConstruct() 823 { 824 if(!empty){ 825 _front.length = 0; 826 foreach(i; 0..N) 827 _front ~= _range[_fidx + i]; 828 } 829 } 830 831 public: 832 this(R range) 833 { 834 _range = range; 835 _fidx = 0; 836 837 reConstruct(); 838 } 839 840 841 enum bool empty = false; 842 843 844 void popFront() 845 { 846 ++_fidx; 847 if(!empty){ 848 _front = _front[1..$]; 849 _front ~= _range[_fidx + (N - 1)]; 850 } 851 } 852 853 854 @property Segment save() 855 { 856 Segment dst = this; 857 dst._range = dst._range.save; 858 return dst; 859 } 860 861 862 @property Tuple!(TypeNuple!(E, N)) front() 863 { 864 return (cast(typeof(return)[])(cast(ubyte[])_front))[0]; 865 } 866 867 868 Tuple!(TypeNuple!(E, N)) opIndex(size_t i) 869 { 870 if(i == 0) 871 return this.front; 872 else 873 { 874 E[] dst; 875 foreach(j; 0 .. N) 876 dst ~= _range[_fidx + i + j]; 877 return (cast(typeof(return)[])(cast(ubyte[])dst))[0]; 878 } 879 } 880 881 882 static if(hasSwappableElements!R || hasLvalueElements!R || hasAssignableElements!R) 883 { 884 @property void front(Tuple!(TypeNuple!(E, N)) e) 885 { 886 E[] eSlice = [e.field]; 887 888 foreach(i; 0 .. N) 889 _range[i + _fidx] = eSlice[i]; 890 891 reConstruct(); 892 } 893 894 895 void opIndexAssign(Tuple!(TypeNuple!(E, N)) e, size_t i) 896 { 897 E[] eSlice = [e.field]; 898 899 foreach(j; 0..N) 900 _range[_fidx + i + j] = eSlice[j]; 901 902 reConstruct(); 903 } 904 } 905 } 906 } 907 908 909 unittest 910 { 911 //debug scope(failure) writefln("unittest Failure :%s(%s)", __FILE__, __LINE__); 912 debug scope(success) {writefln("Unittest Success :%s(%s)", __FILE__, __LINE__); stdout.flush();} 913 914 struct TRange 915 { 916 int[] a, s; 917 918 this(int[] r){ 919 a = r.save; 920 s = r.save; 921 } 922 923 @property ref int front(){return a.front;} 924 enum bool empty = false; 925 void popFront(){a.popFront; if(a.empty)a = s;} 926 @property typeof(this) save(){return this;} 927 ref int opIndex(size_t i){return a[i%s.length];} 928 } 929 930 931 auto r = segment!2(TRange([0, 1, 2, 3, 4])); 932 assert(equal(r.take(4), [tuple(0, 1), tuple(1, 2), tuple(2, 3), tuple(3, 4)])); 933 934 auto sv = r.save; 935 sv.popFront(); 936 assert(equal(r.take(4), [tuple(0, 1), tuple(1, 2), tuple(2, 3), tuple(3, 4)])); 937 assert(equal(sv.take(3), [tuple(1, 2), tuple(2, 3), tuple(3, 4)])); 938 939 assert(r[2] == tuple(2, 3)); 940 assert(r[0] == tuple(0, 1)); 941 942 r.front = tuple(100, 50); 943 assert(equal(r.take(4), [tuple(100, 50), tuple(50, 2), tuple(2, 3), tuple(3, 4)])); 944 945 r[1] = tuple(10, 20); 946 assert(equal(r.take(4), [tuple(100, 10), tuple(10, 20), tuple(20, 3), tuple(3, 4)])); 947 } 948 949 950 ///ditto 951 template segment(size_t N, Range) 952 if(isBidirectionalRange!(Unqual!Range) 953 && (isRandomAccessRange!(Unqual!Range) ? (!hasLength!(Unqual!Range) && isInfinite!(Unqual!Range)) : true)) 954 { 955 Segment segment(Range range) 956 { 957 return Segment(range); 958 } 959 960 961 alias Unqual!Range R; 962 alias ElementType!R E; 963 enum assE = hasAssignableElements!R && hasLvalueElements!R && hasSwappableElements!R; 964 965 966 struct Segment{ 967 private: 968 R _fRange; 969 R _bRange; 970 E[] _front; 971 E[] _back; 972 973 static if(assE || isRandomAccessRange!R) 974 R _assignRange; 975 976 static if(assE || isRandomAccessRange!R) 977 void reConstruct(){ 978 _front.length = 0; 979 _back.length = 0; 980 981 _fRange = _assignRange.save; 982 _bRange = _assignRange.save; 983 984 for(int i = 0; i < N && !_fRange.empty; ++i, _fRange.popFront()) 985 _front ~= _fRange.front(); 986 987 for(int i = 0; i < N && !_bRange.empty; ++i, _bRange.popBack()) 988 _back ~= _bRange.back(); 989 990 _back.reverse(); 991 } 992 993 994 995 public: 996 this(R range) 997 { 998 _fRange = range.save; 999 _bRange = range.save; 1000 1001 static if(assE || isRandomAccessRange!R) 1002 _assignRange = range.save; 1003 1004 for(int i = 0; i < N && !_fRange.empty; ++i, _fRange.popFront()) 1005 _front ~= _fRange.front(); 1006 1007 for(int i = 0; i < N && !_bRange.empty; ++i, _bRange.popBack()) 1008 _back ~= _bRange.back(); 1009 1010 _back.reverse(); 1011 } 1012 1013 1014 static if(isInfinite!R) 1015 enum bool empty = false; 1016 else 1017 @property bool empty() 1018 { 1019 return (_front.length < N) || (_back.length < N); 1020 } 1021 1022 1023 void popFront() 1024 { 1025 _front = _front[1..$]; 1026 1027 if(!_fRange.empty){ 1028 _front ~= _fRange.front; 1029 1030 _fRange.popFront(); 1031 _bRange.popFront(); 1032 } 1033 1034 static if(assE || isRandomAccessRange!R) 1035 _assignRange.popFront(); 1036 } 1037 1038 1039 void popBack() 1040 { 1041 _back = _back[0..$-1]; 1042 1043 if(!_bRange.empty){ 1044 _back = [_bRange.back] ~ _back; 1045 1046 _fRange.popBack(); 1047 _bRange.popBack(); 1048 } 1049 1050 static if(assE || isRandomAccessRange!R) 1051 _assignRange.popBack(); 1052 } 1053 1054 1055 @property Segment save() 1056 { 1057 Segment dst = this; 1058 dst._fRange = dst._fRange.save; 1059 dst._bRange = dst._bRange.save; 1060 1061 static if(assE) 1062 dst._assignRange = dst._assignRange.save; 1063 1064 return dst; 1065 } 1066 1067 1068 static if(hasLength!R) 1069 { 1070 @property size_t length() 1071 { 1072 return _fRange.length + ((_front.length == N && _back.length == N) ? 1 : 0); 1073 } 1074 1075 1076 alias length opDollar; 1077 } 1078 1079 1080 static if(hasSlicing!R) 1081 { 1082 Segment opSlice() 1083 { 1084 return save; 1085 } 1086 1087 1088 static if(assE || isRandomAccessRange!R) 1089 auto opSlice(size_t i, size_t j) 1090 { 1091 return segment!N(_assignRange[i..j + (N-1)]); 1092 } 1093 //else 1094 } 1095 1096 1097 @property Tuple!(TypeNuple!(E, N)) front() 1098 { 1099 return (cast(typeof(return)[])(cast(ubyte[])_front))[0]; 1100 } 1101 1102 1103 @property Tuple!(TypeNuple!(E, N)) back() 1104 { 1105 return (cast(typeof(return)[])(cast(ubyte[])_back))[0]; 1106 } 1107 1108 1109 static if(isRandomAccessRange!R) 1110 Tuple!(TypeNuple!(E, N)) opIndex(size_t i) 1111 { 1112 E[] dst; 1113 1114 foreach(j; 0..N) 1115 dst ~= _assignRange[i + j]; 1116 1117 return (cast(typeof(return)[])(cast(ubyte[])dst))[0]; 1118 } 1119 1120 1121 1122 static if(assE) 1123 { 1124 @property void front(Tuple!(TypeNuple!(E, N)) e) 1125 { 1126 R _tmp = _assignRange.save; 1127 _front = [e.field]; 1128 1129 for(int i = 0; i < N; ++i, _tmp.popFront()) 1130 _tmp.front = _front[i]; 1131 1132 reConstruct(); 1133 } 1134 1135 1136 @property void back(Tuple!(TypeNuple!(E, N)) e) 1137 { 1138 R _tmp = _assignRange.save; 1139 _back = [e.field]; 1140 1141 for(int i = N-1; i >= 0; --i, _tmp.popBack()) 1142 _tmp.back = _back[i]; 1143 1144 reConstruct(); 1145 } 1146 1147 static if(isRandomAccessRange!R) 1148 void opIndexAssign(Tuple!(TypeNuple!(E, N)) e, size_t i) 1149 { 1150 foreach(j; 0..N) 1151 _assignRange[i + j] = [e.field][j]; 1152 1153 reConstruct(); 1154 } 1155 } 1156 } 1157 } 1158 1159 unittest 1160 { 1161 //debug scope(failure) writefln("unittest Failure :%s(%s)", __FILE__, __LINE__); 1162 debug scope(success) {writefln("Unittest Success :%s(%s)", __FILE__, __LINE__); stdout.flush();} 1163 1164 struct TRange{ 1165 int[] a; 1166 @property int front(){return a.front;} 1167 @property bool empty(){return a.empty;} 1168 void popFront(){a.popFront();} 1169 void popBack(){a.popBack();} 1170 @property int back(){return a.back();} 1171 @property TRange save(){return TRange(a.save);} 1172 @property size_t length(){return a.length;} 1173 alias length opDollar; 1174 } 1175 1176 1177 auto r = TRange([0, 1, 2, 3, 4]); 1178 auto sg = segment!2(r); 1179 assert(equal(sg, [tuple(0, 1), tuple(1, 2), tuple(2, 3), tuple(3, 4)])); 1180 assert(equal(sg.retro, [tuple(0, 1), tuple(1, 2), tuple(2, 3), tuple(3, 4)].retro)); 1181 assert(sg.length == 4); 1182 1183 sg.popFront(); 1184 assert(equal(sg, [tuple(1, 2), tuple(2, 3), tuple(3, 4)])); 1185 assert(sg.length == 3); 1186 assert(!sg.empty); 1187 1188 auto sv = sg.save; 1189 sv.popFront(); 1190 assert(equal(sg, [tuple(1, 2), tuple(2, 3), tuple(3, 4)])); 1191 assert(equal(sv, [tuple(2, 3), tuple(3, 4)])); 1192 assert(sg.length == 3); 1193 assert(sv.length == 2); 1194 assert(!sg.empty); 1195 assert(!sv.empty); 1196 1197 sg.popFront(); 1198 assert(equal(sg, [tuple(2, 3), tuple(3, 4)])); 1199 assert(sg.length == 2); 1200 assert(!sg.empty); 1201 1202 sg.popFront(); 1203 assert(equal(sg, [tuple(3, 4)])); 1204 assert(sg.length == 1); 1205 assert(!sg.empty); 1206 1207 sg.popFront(); 1208 assert(sg.length == 0); 1209 assert(sg.empty); 1210 } 1211 unittest 1212 { 1213 //debug scope(failure) writefln("unittest Failure :%s(%s)", __FILE__, __LINE__); 1214 debug scope(success) {writefln("Unittest Success :%s(%s)", __FILE__, __LINE__); stdout.flush();} 1215 1216 struct TRange{ 1217 int[] a; 1218 @property ref int front(){return a.front;} 1219 @property bool empty(){return a.empty;} 1220 void popFront(){a.popFront();} 1221 void popBack(){a.popBack();} 1222 @property ref int back(){return a.back();} 1223 @property TRange save(){return TRange(a.save);} 1224 @property size_t length(){return a.length;} 1225 TRange opSlice(size_t i, size_t j){return TRange(a[i..j]);} 1226 alias length opDollar; 1227 } 1228 1229 1230 auto r = TRange([0, 1, 2, 3, 4]); 1231 auto sg = segment!2(r); 1232 assert(equal(sg, [tuple(0, 1), tuple(1, 2), tuple(2, 3), tuple(3, 4)])); 1233 assert(equal(retro(sg), [tuple(3, 4), tuple(2, 3), tuple(1, 2), tuple(0, 1)])); 1234 assert(sg.length == 4); 1235 assert(equal(sg[2..4], [tuple(2, 3), tuple(3, 4)])); 1236 1237 auto sgsv = sg.save; 1238 sgsv.popFront(); 1239 assert(equal(sg, [tuple(0, 1), tuple(1, 2), tuple(2, 3), tuple(3, 4)])); 1240 assert(equal(sgsv, [tuple(1, 2), tuple(2, 3), tuple(3, 4)])); 1241 1242 auto sgsv2 = sg[]; 1243 sgsv2.popFront(); 1244 assert(equal(sg, [tuple(0, 1), tuple(1, 2), tuple(2, 3), tuple(3, 4)])); 1245 assert(equal(sgsv2, [tuple(1, 2), tuple(2, 3), tuple(3, 4)])); 1246 1247 1248 sg.front = tuple(2, 2); 1249 assert(equal(sg, [tuple(2, 2), tuple(2, 2), tuple(2, 3), tuple(3, 4)])); 1250 assert(equal(retro(sg), [tuple(3, 4), tuple(2, 3), tuple(2, 2), tuple(2, 2)])); 1251 1252 sg.popFront(); 1253 assert(equal(sg, [tuple(2, 2), tuple(2, 3), tuple(3, 4)])); 1254 assert(equal(retro(sg), [tuple(3, 4), tuple(2, 3), tuple(2, 2)])); 1255 assert(sg.length == 3); 1256 assert(!sg.empty); 1257 1258 sg.popFront(); 1259 assert(equal(sg, [tuple(2, 3), tuple(3, 4)])); 1260 assert(equal(retro(sg), [tuple(3, 4), tuple(2, 3)])); 1261 assert(sg.length == 2); 1262 assert(!sg.empty); 1263 1264 sg.popFront(); 1265 assert(equal(sg, [tuple(3, 4)])); 1266 assert(equal(retro(sg), [tuple(3, 4)])); 1267 assert(sg.length == 1); 1268 assert(!sg.empty); 1269 1270 sg.front = tuple(2, 5); 1271 assert(equal(sg, [tuple(2, 5)])); 1272 assert(equal(retro(sg), [tuple(2, 5)])); 1273 assert(sg.length == 1); 1274 assert(!sg.empty); 1275 1276 sg.front = tuple(2, 1); 1277 assert(equal(sg, [tuple(2, 1)])); 1278 assert(sg.length == 1); 1279 assert(!sg.empty); 1280 1281 sg.popFront(); 1282 assert(sg.length == 0); 1283 assert(sg.empty); 1284 } 1285 unittest 1286 { 1287 //debug scope(failure) writefln("unittest Failure :%s(%s)", __FILE__, __LINE__); 1288 debug scope(success) {writefln("Unittest Success :%s(%s)", __FILE__, __LINE__); stdout.flush();} 1289 1290 struct TRange{ 1291 int[] a; 1292 @property ref int front(){return a.front;} 1293 @property bool empty(){return a.empty;} 1294 void popFront(){a.popFront();} 1295 void popBack(){a.popBack();} 1296 @property ref int back(){return a.back();} 1297 @property TRange save(){return TRange(a.save);} 1298 @property size_t length(){return a.length;} 1299 TRange opSlice(size_t i, size_t j){return TRange(a[i..j]);} 1300 alias length opDollar; 1301 } 1302 1303 1304 auto r = TRange([0, 1, 2, 3, 4]); 1305 auto sg = segment!3(r); 1306 assert(equal(sg, [tuple(0, 1, 2), tuple(1, 2, 3), tuple(2, 3, 4)])); 1307 assert(equal(retro(sg), [tuple(0, 1, 2), tuple(1, 2, 3), tuple(2, 3, 4)].retro)); 1308 assert(sg.length == 3); 1309 assert(equal(sg[2..3], [tuple(2, 3, 4)])); 1310 1311 sg.front = tuple(2, 2, 2); 1312 assert(equal(sg, [tuple(2, 2, 2), tuple(2, 2, 3), tuple(2, 3, 4)])); 1313 assert(equal(sg.retro, [tuple(2, 2, 2), tuple(2, 2, 3), tuple(2, 3, 4)].retro)); 1314 1315 sg.popFront(); 1316 assert(equal(sg, [tuple(2, 2, 3), tuple(2, 3, 4)])); 1317 assert(equal(sg.retro, [tuple(2, 2, 3), tuple(2, 3, 4)].retro)); 1318 assert(sg.length == 2); 1319 assert(!sg.empty); 1320 1321 sg.back = tuple(4, 4, 4); 1322 assert(equal(sg, [tuple(2, 4, 4), tuple(4, 4, 4)])); 1323 assert(equal(sg.retro, [tuple(2, 4, 4), tuple(4, 4, 4)].retro)); 1324 assert(sg.length == 2); 1325 assert(!sg.empty); 1326 1327 sg.popFront(); 1328 assert(equal(sg, [tuple(4, 4, 4)])); 1329 assert(equal(sg.retro, [tuple(4, 4, 4)].retro)); 1330 assert(sg.length == 1); 1331 assert(!sg.empty); 1332 1333 sg.popFront(); 1334 assert(sg.length == 0); 1335 assert(sg.empty); 1336 } 1337 unittest 1338 { 1339 //debug scope(failure) writefln("unittest Failure :%s(%s)", __FILE__, __LINE__); 1340 debug scope(success) {writefln("Unittest Success :%s(%s)", __FILE__, __LINE__); stdout.flush();} 1341 1342 struct TRange{ 1343 size_t f, b; 1344 int[] s; 1345 1346 this(int[] r){ 1347 f = 0; 1348 s = r; 1349 b = s.length - 1; 1350 } 1351 1352 @property ref int front(){return s[f];} 1353 enum bool empty = false; 1354 void popFront(){++f; if(f == s.length)f = 0;} 1355 void popBack(){b = (b == 0 ? s.length - 1 : b-1);} 1356 @property ref int back(){return s[b];} 1357 @property typeof(this) save(){return this;} 1358 auto opSlice(size_t i, size_t j){auto dst = this; dst.popFrontN(i); return dst.take(j - i);} 1359 ref int opIndex(size_t i){return s[(i+f)%s.length];} 1360 } 1361 1362 alias TRange Range; 1363 static assert(isInputRange!TRange); 1364 1365 auto r = TRange([0, 1, 2, 3, 4]); 1366 auto sg = segment!3(r); 1367 assert(equal(sg.take(3), [tuple(0, 1, 2), tuple(1, 2, 3), tuple(2, 3, 4)])); 1368 assert(equal(retro(sg).take(3), [tuple(2, 3, 4), tuple(1, 2, 3), tuple(0, 1, 2)])); 1369 assert(sg[2] == tuple(2, 3, 4)); 1370 //assert(equal(sg[2..3], [tuple(2, 3, 4)])); 1371 1372 sg.front = tuple(2, 2, 2); //[2, 2, 2, 3, 4] 1373 assert(equal(sg.take(3), [tuple(2, 2, 2), tuple(2, 2, 3), tuple(2, 3, 4)])); 1374 assert(equal(retro(sg).take(3), [tuple(2, 3, 4), tuple(2, 2, 3), tuple(2, 2, 2)])); 1375 1376 sg.popFront(); 1377 assert(equal(sg.take(3), [tuple(2, 2, 3), tuple(2, 3, 4), tuple(3, 4, 2)])); 1378 assert(equal(retro(sg).take(3), [tuple(2, 3, 4), tuple(2, 2, 3), tuple(2, 2, 2)])); 1379 assert(!sg.empty); 1380 1381 sg[1] = tuple(3, 3, 3); //[2, 2, 3, 3, 3] 1382 assert(equal(sg.take(3), [tuple(2, 3, 3), tuple(3, 3, 3), tuple(3, 3, 2)])); 1383 assert(equal(sg.retro.take(3), [tuple(3, 3, 3), tuple(2, 3, 3), tuple(2, 2, 3)])); 1384 assert(!sg.empty); 1385 1386 sg.back = tuple(2, 3, 4);//[2, 2, 2, 3, 4] 1387 assert(equal(sg.take(3), [tuple(2, 2, 3), tuple(2, 3, 4), tuple(3, 4, 2)])); 1388 assert(equal(sg.retro.take(3), [tuple(2, 3, 4), tuple(2, 2, 3), tuple(2, 2, 2)])); 1389 assert(!sg.empty); 1390 1391 sg.popBack(); 1392 assert(equal(sg.take(3), [tuple(2, 2, 3), tuple(2, 3, 4), tuple(3, 4, 2)])); 1393 assert(equal(sg.retro.take(3), [tuple(2, 2, 3), tuple(2, 2, 2), tuple(4, 2, 2)])); 1394 assert(!sg.empty); 1395 } 1396 1397 1398 /** 1399 Dynamic Array Segment 1400 */ 1401 template dsegment(Range) 1402 if(isInputRange!Range) 1403 { 1404 alias E = Unqual!(ElementType!Range); 1405 1406 1407 Segment dsegment(Range r, size_t n) 1408 { 1409 Segment dst; 1410 1411 dst._r = r; 1412 dst._arr = new E[n]; 1413 dst._empty = false; 1414 1415 foreach(i; 0 .. n){ 1416 if(dst._r.empty){ 1417 dst._empty = true; 1418 break; 1419 } 1420 1421 dst._arr[i] = dst._r.front; 1422 dst._r.popFront(); 1423 } 1424 1425 return dst; 1426 } 1427 1428 1429 struct Segment 1430 { 1431 E[] front() @property { return _arr; } 1432 const(E)[] front() const @property { return _arr; } 1433 1434 1435 static if(isInfinite!Range) 1436 enum bool empty = false; 1437 else 1438 { 1439 bool empty() const @property { return _empty; } 1440 } 1441 1442 1443 void popFront() 1444 { 1445 if(_r.empty){ 1446 _empty = true; 1447 return; 1448 } 1449 1450 foreach(i; 1 .. _arr.length) 1451 _arr[i-1] = _arr[i]; 1452 1453 _arr[$-1] = _r.front; 1454 _r.popFront(); 1455 } 1456 1457 1458 static if(isForwardRange!Range) 1459 { 1460 typeof(this) save() @property 1461 { 1462 typeof(this) dst; 1463 1464 dst._r = this._r.save; 1465 dst._arr = this._arr.dup; 1466 dst._empty = this._empty; 1467 1468 return dst; 1469 } 1470 } 1471 1472 1473 private: 1474 Range _r; 1475 E[] _arr; 1476 bool _empty; 1477 } 1478 } 1479 1480 unittest 1481 { 1482 //debug scope(failure) writefln("unittest Failure :%s(%s)", __FILE__, __LINE__); 1483 debug scope(success) {writefln("Unittest Success :%s(%s)", __FILE__, __LINE__); stdout.flush();} 1484 1485 static struct TRange 1486 { 1487 int _front, _end; 1488 @property int front(){return _front;} 1489 void popFront(){_front += 1;} 1490 @property bool empty(){return _front == _end;} 1491 @property TRange save(){return this;} 1492 @property size_t length(){return _end - _front;} 1493 alias length opDollar; 1494 } 1495 1496 auto tr = TRange(0, 5); 1497 auto sg2 = dsegment(tr, 2); 1498 import std.stdio; 1499 assert(equal(sg2, [[0, 1], [1, 2], [2, 3], [3, 4]])); 1500 } 1501 1502 1503 /** 1504 concats elements 1505 */ 1506 auto concat(R)(R range) if (isRangeOfRanges!R) 1507 { 1508 static struct Concat 1509 { 1510 private: 1511 R _range; 1512 alias ElementType!R ET0; 1513 alias ElementType!ET0 ET1; 1514 ET0 _subrange; 1515 1516 static if(isRangeOfRanges!(R, isBidirectionalRange)) 1517 { 1518 ET0 _backSubrange; 1519 } 1520 1521 public: 1522 static if(isInfinite!R) 1523 enum bool empty = false; 1524 else 1525 { 1526 @property 1527 bool empty() 1528 { 1529 return _range.empty; 1530 } 1531 } 1532 1533 1534 @property 1535 auto ref front() 1536 { 1537 return _subrange.front; 1538 } 1539 1540 1541 static if(hasAssignableElements!ET0) 1542 { 1543 @property 1544 void front(ET1 v) 1545 { 1546 _subrange.front = v; 1547 } 1548 } 1549 1550 1551 /* 1552 static if(isRangeOfRange!(R, isForwardRange)) 1553 { 1554 @property 1555 Concat save() 1556 { 1557 return this; 1558 } 1559 } 1560 */ 1561 1562 1563 void popFront() 1564 { 1565 if (!_subrange.empty) _subrange.popFront; 1566 1567 while(_subrange.empty && !_range.empty){ 1568 _range.popFront; 1569 1570 if (!_range.empty) 1571 _subrange = _range.front; 1572 } 1573 } 1574 1575 1576 static if (isRangeOfRanges!(R, isBidirectionalRange)) 1577 { 1578 @property 1579 auto ref back() 1580 { 1581 return _backSubrange.back; 1582 } 1583 1584 1585 static if(hasAssignableElements!ET0) 1586 { 1587 @property 1588 void back(ET1 v) 1589 { 1590 _backSubrange.back = v; 1591 } 1592 } 1593 1594 1595 void popBack() 1596 { 1597 if (!_backSubrange.empty) _backSubrange.popBack; 1598 1599 while (_backSubrange.empty && !_range.empty) { 1600 _range.popBack; 1601 if (!_range.empty) _backSubrange = _range.back; 1602 } 1603 } 1604 1605 1606 auto retro() @property 1607 { 1608 static struct RetroConcat 1609 { 1610 auto ref front() @property 1611 { 1612 return _r.back; 1613 } 1614 1615 1616 auto ref back() @property 1617 { 1618 return _r.front; 1619 } 1620 1621 1622 static if(hasAssignableElements!ET0) 1623 { 1624 void front(ET1 v) @property 1625 { 1626 _r.back = v; 1627 } 1628 1629 1630 void back(ET1 v) @property 1631 { 1632 _r.front = v; 1633 } 1634 } 1635 1636 1637 void popFront() 1638 { 1639 _r.popBack(); 1640 } 1641 1642 1643 void popBack() 1644 { 1645 _r.popFront(); 1646 } 1647 1648 1649 static if(isInfinite!R) 1650 enum bool empty = false; 1651 else 1652 bool empty() @property 1653 { 1654 return _r.empty; 1655 } 1656 1657 1658 // save.. 1659 1660 1661 auto retro() @property 1662 { 1663 return _r; 1664 } 1665 1666 1667 private: 1668 Concat _r; 1669 } 1670 1671 1672 return RetroConcat(this); 1673 } 1674 } 1675 } 1676 1677 1678 Concat dst = {_range : range}; 1679 1680 enum initMethod = 1681 q{ 1682 if (!dst._range.empty){ 1683 %1$s = dst._range.%2$s; 1684 while (%1$s.empty && !dst._range.empty){ 1685 dst._range.%3$s; 1686 1687 if (!dst._range.empty) 1688 %1$s = dst._range.%2$s; 1689 } 1690 } 1691 }; 1692 1693 mixin(format(initMethod, "dst._subrange", "front", "popFront")); 1694 1695 static if (isRangeOfRanges!(R, isBidirectionalRange)) 1696 { 1697 mixin(format(initMethod, "dst._backSubrange", "back", "popBack")); 1698 } 1699 1700 return dst; 1701 } 1702 1703 /// ditto 1704 R concat(R)(R range) 1705 if(isSimpleRange!R) 1706 { 1707 return range; 1708 } 1709 1710 /// 1711 unittest 1712 { 1713 debug scope(failure) writefln("unittest Failure :%s(%s)", __FILE__, __LINE__); 1714 debug scope(success) {writefln("Unittest Success :%s(%s)", __FILE__, __LINE__); stdout.flush();} 1715 1716 int[][] r1 = [[0, 1, 2, 3], [4, 5, 6], [7, 8], [9], []]; 1717 auto c = concat(r1); 1718 assert(equal(c, [0, 1, 2, 3, 4, 5, 6, 7, 8, 9])); 1719 assert(equal(c.retro(), retro([0, 1, 2, 3, 4, 5, 6, 7, 8, 9]))); // bidir range 1720 assert(equal(c.retro.retro, c)); 1721 1722 assert(equal(concat(c), c)); 1723 1724 auto r2 = [0, 1, 2, 3, 4, 5]; 1725 assert(equal(r2.map!"[a, 2]".concat, [0, 2, 1, 2, 2, 2, 3, 2, 4, 2, 5, 2])); 1726 assert(equal(r2[0 .. 4].map!(a => repeat(a, a)).concat, [1, 2, 2, 3, 3, 3])); 1727 assert(equal(r2[0 .. 3].repeat(2).map!(map!"a + 1").concat, [1, 2, 3, 1, 2, 3])); 1728 1729 int[] emp; 1730 assert(emp.repeat(15).concat.empty); 1731 assert(emp.concat.empty); 1732 } 1733 1734 1735 /// 1736 auto flatten(size_t N = size_t.max, R)(R r) 1737 if(isInputRange!R) 1738 { 1739 static if(N > 0 && isRangeOfRanges!R) 1740 return r.concat.flatten!(N-1); 1741 else 1742 return r; 1743 } 1744 1745 /// 1746 unittest 1747 { 1748 auto d1 = [0, 1, 2, 3, 4, 5, 6, 7, 8]; 1749 assert(equal(d1.flatten, d1)); 1750 assert(equal(d1.flatten!0, d1)); 1751 1752 auto d2 = [[0, 1], [], [2, 3], [4, 5, 6, 7], [8]]; 1753 assert(equal(d2.flatten, d1)); 1754 assert(equal(d2.flatten!1, d1)); 1755 assert(equal(d2.flatten!0, d2)); 1756 1757 auto d3 = [[[0, 1], [], [2, 3]], [[4, 5, 6, 7], [8]]]; 1758 assert(equal(d3.flatten, d1)); 1759 assert(equal(d3.flatten!0, d3)); 1760 assert(equal(d3.flatten!1, d2)); 1761 assert(equal(d3.flatten!2, d1)); 1762 } 1763 1764 1765 /** 1766 Haskell等の言語での$(D takeWhile)の実装です。 1767 この実装では、predは任意個数の引数を取ることができます。 1768 たとえば、2引数関数の場合、第一引数にはレンジの先頭の値が、第二引数にはレンジの次の値が格納されます。 1769 */ 1770 auto takeWhile(alias pred, R, T...)(R range, T args) 1771 if(isInputRange!R) 1772 { 1773 template Parameter(U...) 1774 { 1775 enum bool empty = false; 1776 alias front = U; 1777 alias tail() = Parameter!(ElementType!R, U); 1778 } 1779 1780 alias _pred = naryFun!pred; 1781 enum arityN = argumentInfo!(_pred, Parameter!T).arity - T.length; 1782 1783 static if(arityN <= 1) 1784 return TakeWhileResult!(_pred, arityN, R, T)(range, args); 1785 else 1786 return TakeWhileResult!(_pred, arityN, typeof(segment!arityN(range)), T)(segment!arityN(range), args); 1787 } 1788 1789 private struct TakeWhileResult(alias _pred, size_t arityN, SegR, T...) 1790 { 1791 @property 1792 bool empty() 1793 { 1794 if(_r.empty) 1795 return true; 1796 1797 static if(arityN == 0) 1798 return !_pred(_subArgs); 1799 else static if(arityN == 1) 1800 return !_pred(_r.front, _subArgs); 1801 else 1802 return !_pred(_r.front.field, _subArgs); 1803 } 1804 1805 1806 @property 1807 auto front() 1808 { 1809 static if(arityN <= 1) 1810 return _r.front; 1811 else 1812 return _r.front.field[0]; 1813 } 1814 1815 1816 void popFront() 1817 { 1818 _r.popFront(); 1819 } 1820 1821 1822 static if(isForwardRange!(typeof(_r))) 1823 { 1824 @property 1825 auto save() 1826 { 1827 return TakeWhileResult!(_pred, arityN, typeof(_r.save), T)(_r.save, _subArgs); 1828 } 1829 } 1830 1831 private: 1832 SegR _r; 1833 T _subArgs; 1834 } 1835 1836 /// ditto 1837 unittest 1838 { 1839 debug scope(failure) writefln("unittest Failure :%s(%s)", __FILE__, __LINE__); 1840 debug scope(success) {writefln("Unittest Success :%s(%s)", __FILE__, __LINE__); stdout.flush();} 1841 1842 int[] em; 1843 assert(takeWhile!"true"(em).empty); 1844 1845 auto r1 = [1, 2, 3, 4, 3, 2, 1]; 1846 auto tw1 = takeWhile!"a < b"(r1); 1847 assert(equal(tw1, [1, 2, 3])); 1848 1849 auto tw2 = takeWhile!"a < b && b < c"(r1); 1850 assert(equal(tw2, [1, 2])); 1851 1852 auto tw3 = takeWhile!"a == (b - c)"(r1, 1); 1853 assert(equal(tw3, [1, 2, 3])); 1854 1855 auto tw4 = takeWhile!"true"(r1); 1856 assert(equal(tw4, r1)); 1857 1858 auto tw5 = takeWhile!"false"(r1); 1859 assert(tw5.empty); 1860 } 1861 1862 1863 1864 /** 1865 受け取ったレンジの要素をそれぞれ連続してn回繰り返すようなレンジを返します。 1866 */ 1867 auto resampling(R)(R range, size_t n) 1868 { 1869 alias E = ElementType!R; 1870 1871 static struct SamplerResult 1872 { 1873 E front() @property { return _f; } 1874 1875 1876 void popFront() 1877 { 1878 ++_cnt; 1879 if(_cnt == _n){ 1880 if(!_r.empty){ 1881 _f = _r.front; 1882 _r.popFront(); 1883 _cnt = 0; 1884 } 1885 } 1886 } 1887 1888 1889 bool empty() const 1890 { 1891 return (_n == 0) || (_cnt == _n && _r.empty); 1892 } 1893 1894 1895 private: 1896 size_t _cnt; 1897 size_t _n; 1898 R _r; 1899 E _f; 1900 } 1901 1902 if(range.empty) 1903 return SamplerResult.init; 1904 1905 auto f = range.front; 1906 range.popFront(); 1907 1908 return SamplerResult(0, n, range, f); 1909 } 1910 1911 /// 1912 unittest 1913 { 1914 debug scope(failure) writefln("unittest Failure :%s(%s)", __FILE__, __LINE__); 1915 debug scope(success) {writefln("Unittest Success :%s(%s)", __FILE__, __LINE__); stdout.flush();} 1916 1917 import std.stdio; 1918 uint[] arr = [0, 1, 2]; 1919 //writeln(arr.resampling(3)); 1920 assert(arr.resampling(3).equal([0,0,0,1,1,1,2,2,2,])); 1921 1922 assert(arr.resampling(0).empty); 1923 1924 uint[] emp = []; 1925 assert(emp.resampling(3).empty); 1926 } 1927 1928 1929 /** 1930 std.range.iotaを汎用的にしたものです． 1931 */ 1932 auto giota(alias add = "a + b", alias pred = "a == b", S, E, D)(S start, E end, D diff) 1933 if(is(typeof((S s, E e, D d){ s = binaryFun!add(s, d); if(binaryFun!pred(s, e)){} }))) 1934 { 1935 static struct Iota 1936 { 1937 inout(S) front() inout @property { return _value; } 1938 bool empty() @property { return !!binaryFun!pred(_value, _end); } 1939 void popFront() { _value = binaryFun!add(_value, _diff); } 1940 1941 private: 1942 S _value; 1943 E _end; 1944 D _diff; 1945 } 1946 1947 1948 return Iota(start, end, diff); 1949 } 1950 1951 1952 /// ditt 1953 auto giotaInf(alias add = "a + b", S, D)(S start, D diff) 1954 if(is(typeof((S s, D d){ s = binaryFun!add(s, d); }))) 1955 { 1956 static struct IotaInf 1957 { 1958 inout(S) front() inout @property { return _value; } 1959 enum bool empty = false; 1960 void popFront() { _value = binaryFun!add(_value, _diff); } 1961 1962 private: 1963 S _value; 1964 D _diff; 1965 } 1966 1967 1968 return IotaInf(start, diff); 1969 } 1970 1971 1972 /// 1973 unittest 1974 { 1975 import std.datetime; 1976 import core.time; 1977 1978 auto ds1 = giota(Date(2004, 1, 1), Date(2005, 1, 1), days(1)); 1979 assert(ds1.walkLength() == 366); 1980 1981 1982 auto ds2 = giotaInf(Date(2004, 1, 1), days(2)); 1983 assert(ds2.front == Date(2004, 1, 1)); ds2.popFront(); 1984 assert(ds2.front == Date(2004, 1, 3)); ds2.popFront(); 1985 assert(ds2.front == Date(2004, 1, 5)); 1986 } 1987 1988 1989 auto whenEmpty(alias func, R)(R range) 1990 if(isInputRange!R && isCallable!func) 1991 { 1992 static struct ResultRangeOfWhenEmpty 1993 { 1994 auto ref front() { return _r.front; } 1995 1996 static if(isInfinite!R) 1997 enum bool empty = false; 1998 else 1999 { 2000 bool empty() @property { return _r.empty; } 2001 } 2002 2003 2004 void popFront() 2005 { 2006 _r.popFront(); 2007 if(_r.empty){ 2008 func(); 2009 } 2010 } 2011 2012 private: 2013 R _r; 2014 } 2015 2016 2017 ResultRangeOfWhenEmpty res; 2018 res._r = range; 2019 return res; 2020 } 2021 2022 /// 2023 unittest 2024 { 2025 { 2026 static auto arrA = [1, 2, 3]; 2027 auto r = arrA.whenEmpty!((){ arrA = null; }); 2028 assert(equal(r, arrA)); 2029 assert(arrA is null); 2030 } 2031 { 2032 static auto arrB = [1, 2, 3]; 2033 auto r = arrB.whenEmpty!((){ arrB = null; }); 2034 //assert(equal(r, arr)); 2035 r.popFront(); r.popFront(); 2036 assert(arrB !is null); 2037 r.popFront(); 2038 assert(arrB is null); 2039 } 2040 } 2041 2042 2043 auto whenEmpty(R, Fn)(R range, Fn fn) 2044 if(isCallable!Fn) 2045 { 2046 static struct ResultRangeOfWhenEmpty 2047 { 2048 auto ref front() { return _r.front; } 2049 2050 static if(isInfinite!R) 2051 enum bool empty = false; 2052 else 2053 { 2054 bool empty() @property { return _r.empty; } 2055 } 2056 2057 2058 void popFront() 2059 { 2060 _r.popFront(); 2061 if(_r.empty){ 2062 _fn(); 2063 } 2064 } 2065 2066 private: 2067 R _r; 2068 Fn _fn; 2069 } 2070 2071 2072 ResultRangeOfWhenEmpty res; 2073 res._r = range; 2074 res._fn = fn; 2075 return res; 2076 } 2077 2078 /// 2079 unittest 2080 { 2081 { 2082 auto arr = [1, 2, 3]; 2083 auto r = arr.whenEmpty((){ arr = null; }); 2084 assert(equal(r, arr)); 2085 assert(arr is null); 2086 } 2087 { 2088 auto arr = [1, 2, 3]; 2089 auto r = arr.whenEmpty((){ arr = null; }); 2090 //assert(equal(r, arr)); 2091 r.popFront(); r.popFront(); 2092 assert(arr !is null); 2093 r.popFront(); 2094 assert(arr is null); 2095 } 2096 }