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 }