1 /** Extensions to std.range.
2     License: $(WEB boost.org/LICENSE_1_0.txt, Boost License 1.0).
3 */
4 
5 module nxt.range_ex;
6 
7 import core.internal.traits: hasElaborateDestructor;
8 import std.traits : isSomeString, isNarrowString;
9 import std.range: hasSlicing, hasLength, isInfinite, isInputRange, isBidirectionalRange, ElementType, isRandomAccessRange;
10 import std.traits: hasUnsharedAliasing, isScalarType;
11 
12 public import nxt.slicing;
13 
14 enum hasPureCopy(T) = (isScalarType!T || // TODO remove?
15                        (!hasUnsharedAliasing!T &&
16                         !hasElaborateDestructor!T));
17 
18 enum hasStealableElements(R) = (hasPureCopy!(ElementType!R)); // TODO recurse
19 
20 /* template hasStealableElements(T...) */
21 /* { */
22 /*     import std.range: ElementType; */
23 /*     import std.typecons : Rebindable; */
24 
25 /*     static if (is(ElementType!T)) */
26 /*     { */
27 /*         enum hasStealableElements = true; */
28 /*     } */
29 /*     else static if (is(T[0] R: Rebindable!R)) */
30 /*     { */
31 /*         enum hasStealableElements = hasStealableElements!R; */
32 /*     } */
33 /*     else */
34 /*     { */
35 /*         template unsharedDelegate(T) */
36 /*         { */
37 /*             enum bool unsharedDelegate = isDelegate!T */
38 /*             && !is(T == shared) */
39 /*             && !is(T == shared) */
40 /*             && !is(T == immutable) */
41 /*             && !is(FunctionTypeOf!T == shared) */
42 /*             && !is(FunctionTypeOf!T == immutable); */
43 /*         } */
44 
45 /*         enum hasStealableElements = */
46 /*         hasRawUnsharedAliasing!(T[0]) || */
47 /*         anySatisfy!(unsharedDelegate, RepresentationTypeTuple!(T[0])) || */
48 /*         hasUnsharedObjects!(T[0]) || */
49 /*         hasStealableElements!(T[1..$]); */
50 /*     } */
51 /* } */
52 
53 /** Steal front from $(D r) destructively and return it.
54    See_Also: http://forum.dlang.org/thread/jkbhlezbcrufowxtthmy@forum.dlang.org#post-konhvblwbmpdrbeqhyuv:40forum.dlang.org
55    See_Also: http://forum.dlang.org/thread/onibkzepudfisxtrigsi@forum.dlang.org#post-dafmzroxvaeejyxrkbon:40forum.dlang.org
56 */
57 ElementType!R frontPop(R)(ref R r)
58 if (isInputRange!R &&
59     hasStealableElements!R)
60 {
61     import std.range: moveFront, popFront;
62     /* scope(success) r.popFront(); */
63     /* return r.moveFront(); */
64     auto e = r.moveFront();
65 
66     r.popFront();
67 
68     import std.traits : hasIndirections;
69     static if (hasIndirections!(typeof(return))) // TODO better trait?
70     {
71         import core.lifetime : move;
72         return move(e);
73     }
74     else
75     {
76         return e;
77     }
78 }
79 alias stealFront = frontPop;
80 alias pullFront = frontPop;
81 alias takeFront = frontPop;
82 
83 version(unittest)
84 {
85     import nxt.array_help : s;
86 }
87 
88 @safe pure nothrow unittest
89 {
90     auto x = [11, 22];
91     assert(x.frontPop() == 11); assert(x == [22]);
92     assert(x.frontPop() == 22); assert(x == []);
93 }
94 
95 @safe pure nothrow unittest
96 {
97     auto x = ["a", "b"];
98     assert(x.frontPop() == "a"); assert(x == ["b"]);
99 }
100 
101 @safe pure nothrow unittest
102 {
103     struct V { int x, y; }
104     auto x = [V(11, 12),
105               V(21, 22)];
106     assert(x.frontPop() == V(11, 12)); assert(x == [V(21, 22)]);
107     assert(x.frontPop() == V(21, 22)); assert(x == []);
108 }
109 
110 /** Steal back from $(D r) destructively and return it.
111     See_Also: http://forum.dlang.org/thread/jkbhlezbcrufowxtthmy@forum.dlang.org#post-konhvblwbmpdrbeqhyuv:40forum.dlang.org
112     See_Also: http://forum.dlang.org/thread/onibkzepudfisxtrigsi@forum.dlang.org#post-dafmzroxvaeejyxrkbon:40forum.dlang.org
113 */
114 ElementType!R backPop(R)(ref R r)
115 if (isInputRange!R &&
116     hasStealableElements!R)
117 {
118     import std.range: moveBack, popBack;
119     /* scope(success) r.popBack(); */
120     /* return r.moveBack(); */
121     auto e = r.moveBack();
122 
123     r.popBack();
124 
125     import std.traits : hasIndirections;
126     static if (hasIndirections!(typeof(return))) // TODO better trait?
127     {
128         import core.lifetime : move;
129         return move(e);
130     }
131     else
132     {
133         return e;
134     }
135 }
136 alias stealBack = backPop;
137 alias pullBack = backPop;
138 alias takeBack = backPop;
139 
140 @safe pure nothrow unittest
141 {
142     auto x = [11, 22];
143     assert(x.backPop() == 22); assert(x == [11]);
144     assert(x.backPop() == 11); assert(x == []);
145 }
146 
147 @safe pure nothrow unittest
148 {
149     auto x = ["a", "b"];
150     assert(x.backPop() == "b"); assert(x == ["a"]);
151 }
152 
153 @safe pure nothrow unittest
154 {
155     struct V { int x, y; }
156     auto x = [V(11, 12),
157               V(21, 22)];
158     assert(x.backPop() == V(21, 22)); assert(x == [V(11, 12)]);
159     assert(x.backPop() == V(11, 12)); assert(x == []);
160 }
161 
162 /** Sliding Splitter.
163  *
164  * See_Also: http://forum.dlang.org/thread/dndicafxfubzmndehzux@forum.dlang.org
165  * See_Also: http://forum.dlang.org/thread/uzrbmjonrkixojzflbig@forum.dlang.org#epost-viwkavbmwouiquoqwntm:40forum.dlang.org
166  *
167  * TODO Use size_t for _lower and _upper instead and reserve _upper = size_t.max
168  * for emptyness?
169  *
170  * TODO Should lower and upper operate on code units instead of code point if
171  * isNarrowString!Range. ?
172  *
173  * TODO generalize with stride
174  */
175 struct SlidingSplitter(Range)
176 if (isSomeString!Range ||
177     (hasSlicing!Range &&
178      !isInfinite!Range))
179 {
180     import std.range: isForwardRange;
181     import core.internal.traits : Unqual;
182     import std.typecons : Tuple, tuple;
183     alias R = Unqual!Range;
184 
185     this(R)(R data, size_t lower = 0)
186     in { assert(lower <= data.length); }
187     do
188     {
189         _data = data;
190         static if (hasSlicing!Range) // TODO should we use isSomeString here instead?
191         {
192             _lower = lower;
193             _upper = data.length;
194         }
195         else
196         {
197             while (lower)
198             {
199                 popFront;
200                 --lower;
201             }
202         }
203         _upper = data.length;
204     }
205 
206     this(R)(R data, size_t lower, size_t upper)
207     in { assert(lower <= upper + 1 || // the extra + 1 makes empty initialization (lower + 1 == upper) possible in for example opSlice below
208                 ((lower <= data.length) &&
209                  (upper <= data.length))); }
210     do
211     {
212         _data = data;
213         _lower = lower;
214         _upper = upper;
215     }
216 
217     @property Tuple!(R, R) front()
218     {
219         return typeof(return)(_data[0 .. _lower],
220                               _data[_lower .. $]);
221     }
222 
223     void popFront()
224     {
225         static if (isNarrowString!R)
226         {
227             if (_lower < _upper)
228             {
229                 import std.utf: stride;
230                 _lower += stride(_data, _lower);
231             }
232             else                // when we can't decode beyond
233             {
234                 ++_lower; // so just indicate we're beyond back
235             }
236         }
237         else
238         {
239             ++_lower;
240         }
241     }
242 
243     static if (!isInfinite!R)
244     {
245         @property Tuple!(R, R) back()
246         {
247             return typeof(return)(_data[0 .. _upper],
248                                   _data[_upper .. $]);
249         }
250         void popBack()
251         {
252             static if (isNarrowString!R)
253             {
254                 if (_lower < _upper)
255                 {
256                     import std.utf: strideBack;
257                     _upper -= strideBack(_data, _upper);
258                 }
259                 else                // when we can't decode beyond
260                 {
261                     --_upper; // so just indicate we're beyond front
262                 }
263             }
264             else
265             {
266                 --_upper;
267             }
268         }
269     }
270 
271     static if (isForwardRange!R)
272     {
273         @property auto save()
274         {
275             import std.range: save;
276             return typeof(this)(_data.save, _lower, _upper);
277         }
278     }
279 
280     static if (isInfinite!R)
281     {
282         enum bool empty = false;  // propagate infiniteness
283     }
284     else
285     {
286         @property bool empty() const
287         {
288             return _upper < _lower;
289         }
290     }
291 
292     static if (hasSlicing!R)
293     {
294         Tuple!(R, R) opIndex(size_t i)
295         in { assert(i < length); }
296         do
297         {
298             return typeof(return)(_data[0 .. _lower + i],
299                                   _data[_lower + i .. _upper]);
300         }
301 
302         typeof(this) opSlice(size_t lower, size_t upper)
303         {
304             if (lower == upper)
305             {
306                 return slidingSplitter(_data,
307                                        _upper + 1, // defines empty intialization
308                                        _upper);
309             }
310             else
311             {
312                 return slidingSplitter(_data,
313                                        _lower + lower,
314                                        _lower + (upper - 1));
315             }
316         }
317 
318         // TODO Should length be provided if isNarrowString!Range?
319         @property size_t length() const
320         {
321             return _upper - _lower + 1;
322         }
323     }
324 
325     private R _data;
326     private ptrdiff_t _lower;
327     private ptrdiff_t _upper;
328 }
329 
330 auto slidingSplitter(R)(R data, size_t lower = 0)
331 {
332     return SlidingSplitter!R(data, lower, data.length);
333 }
334 
335 auto slidingSplitter(R)(R data, size_t lower, size_t upper)
336 {
337     return SlidingSplitter!R(data, lower, upper);
338 }
339 
340 @safe pure nothrow unittest
341 {
342     import std.typecons : tuple;
343     import std.conv: to;
344 
345     auto x = [1, 2, 3];
346 
347     import std.range: isInputRange, isForwardRange, isBidirectionalRange, isRandomAccessRange;
348 
349     static assert(isInputRange!(SlidingSplitter!(typeof(x))));
350     static assert(isForwardRange!(SlidingSplitter!(typeof(x))));
351     // static assert(isBidirectionalRange!(SlidingSplitter!(typeof(x))));
352     static assert(isRandomAccessRange!(SlidingSplitter!(typeof(x))));
353     static assert(!isRandomAccessRange!(SlidingSplitter!string));
354     static assert(!isRandomAccessRange!(SlidingSplitter!wstring));
355     static assert(isRandomAccessRange!(SlidingSplitter!dstring));
356 
357     auto y = SlidingSplitter!(typeof(x))(x);
358 
359     for (size_t i; i < y.length; ++i)
360     {
361         assert(y[i] == tuple(x[0 .. i],
362                              x[i .. 3]));
363     }
364 
365     assert(y.front == tuple([], x));
366     assert(!y.empty);
367     assert(x.length + 1 == y.length);
368 
369     assert(!y.empty); assert(y.front == tuple(x[0 .. 0], x[0 .. 3])); y.popFront();
370     assert(!y.empty); assert(y.front == tuple(x[0 .. 1], x[1 .. 3])); y.popFront();
371     assert(!y.empty); assert(y.front == tuple(x[0 .. 2], x[2 .. 3])); y.popFront();
372     assert(!y.empty); assert(y.front == tuple(x[0 .. 3], x[3 .. 3])); y.popFront();
373     y.popFront(); assert(y.empty);
374 }
375 
376 @safe pure unittest                        // forwards
377 {
378     import std.conv: to;
379 
380     size_t lower = 2;
381 
382     const name = "Nordlöw";
383     auto name8  = name.to! string.slidingSplitter(lower);
384     auto name16 = name.to!wstring.slidingSplitter(lower);
385     auto name32 = name.to!dstring.slidingSplitter(lower);
386 
387     static assert(!__traits(compiles, { name8.length >= 0; } ));
388     static assert(!__traits(compiles, { name16.length >= 0; } ));
389     assert(name32.length);
390 
391     foreach (ch; name8)
392     {
393         static foreach (ix; 0 .. ch.length) // for each part in split
394         {
395             import std.algorithm: equal;
396             assert(ch[ix].equal(name16.front[ix]));
397             assert(ch[ix].equal(name32.front[ix]));
398 
399         }
400         name16.popFront();
401         name32.popFront();
402     }
403 }
404 
405 @safe pure unittest                        // backwards
406 {
407     import std.conv: to;
408     import std.range: retro;
409 
410     size_t lower = 2;
411 
412     auto name = "Nordlöw";
413     auto name8  = name.to! string.slidingSplitter(lower).retro;
414     auto name16 = name.to!wstring.slidingSplitter(lower).retro;
415     auto name32 = name.to!dstring.slidingSplitter(lower).retro;
416 
417     foreach (ch; name8)
418     {
419         import std.algorithm: equal;
420         static foreach (ix; 0 .. ch.length) // for each part in split
421         {
422             assert(ch[ix].equal(name16.front[ix]));
423             assert(ch[ix].equal(name32.front[ix]));
424         }
425         name16.popFront();
426         name32.popFront();
427     }
428 }
429 
430 @safe pure nothrow unittest                        // radial
431 {
432     auto x = [1, 2, 3];
433     import std.range: radial;
434     import std.typecons : tuple;
435     auto s = x.slidingSplitter;
436     auto r = s.radial;
437     assert(!r.empty); assert(r.front == tuple(x[0 .. 1], x[1 .. 3])); r.popFront();
438     assert(!r.empty); assert(r.front == tuple(x[0 .. 2], x[2 .. 3])); r.popFront();
439     assert(!r.empty); assert(r.front == tuple(x[0 .. 0], x[0 .. 3])); r.popFront();
440     assert(!r.empty); assert(r.front == tuple(x[0 .. 3], x[3 .. 3])); r.popFront();
441     assert(r.empty);
442 }
443 
444 /** Ring Buffer.
445  *
446  * See_Also: http://forum.dlang.org/thread/ltpaqk$2dav$1@digitalmars.com
447  * TODO inout
448  */
449 struct RingBuffer(T)
450 {
451     this(T[] data, size_t length = 0)
452     {
453         enforce(data.length, "empty ring buffer is prohibited");
454         enforce(length <= data.length, "buffer length shall not be more
455 than buffer capacity");
456         _data = data;
457         _beginIndex = 0;
458         _length = length;
459     }
460 
461     auto opSlice() const
462     {
463 	return cycle(_data[0 .. _length]).take(_length);
464     }
465 
466     @property auto length() { return _length; }
467 
468 private:
469     T[] _data;
470     size_t _beginIndex;
471     size_t _length;
472 }
473 
474 /** Same as $(D iota) but with explicit conversion to type $(D T).
475     See_Also: http://forum.dlang.org/thread/mailman.955.1444358510.22025.digitalmars-d@puremagic.com?page=1
476 */
477 auto iotaOf(T, B, E, S)(B begin = T.min,
478                         E end = T.max,
479                         S step = 1)
480 {
481     import std.range : iota;
482     import std.algorithm.iteration : map;
483     import std.conv : to;
484     return iota(begin, end, step).map!(a => cast(T)a);
485 }
486 
487 // @safe pure unittest
488 // {
489 //     import std.array : array;
490 //     import std.exception : assertThrown;
491 //     import std.meta : AliasSeq;
492 //     foreach (T; AliasSeq!(ubyte, ushort, uint, ulong))
493 //     {
494 //         auto x = iotaOf!T(0, T.max + 1);
495 //         import nxt.traits_ex : ElementTypeOf;
496 //         static assert(is(ElementTypeOf!(x) == T));
497 //     }
498 // }
499 
500 auto iotaOfExceptional(T, B, E, S)(B begin = T.min, E end = T.max, S step = 1)
501 {
502     import std.range : iota;
503     import std.algorithm.iteration : map;
504     import std.conv : to;
505     return iota(begin, end, step).map!(a => a.to!T);
506 }
507 
508 // @safe pure unittest
509 // {
510 //     import std.array : array;
511 //     import std.exception : assertThrown;
512 //     import std.conv;
513 //     alias T = ubyte;
514 //     auto x = iotaOfExceptional!T(0, T.max + 1);
515 //     import nxt.traits_ex : ElementTypeOf;
516 //     static assert(is(ElementTypeOf!() == T));
517 //     assertThrown!ConvOverflowException(iotaOfExceptional!T(0, T.max + 1 + 1).array);
518 // }
519 
520 /** Return Array of Key-Value Pairs of Associative Array $(D aa).
521  *
522  * See_Also: https://github.com/D-Programming-Language/druntime/pull/574
523  * See_Also: http://forum.dlang.org/thread/dxotcrutrlmszlidufcr@forum.dlang.org?page=2#post-fhkgitmifgnompkqiscd:40forum.dlang.org
524 */
525 auto pairs(Key, Value)(Value[Key] aa)
526 {
527     import std.typecons: Tuple, tuple;
528     Tuple!(Key,Value)[] arr;
529     arr.reserve(aa.length);
530     foreach (key; aa.byKey)
531     {
532         arr ~= tuple(key, aa[key]);
533     }
534     return arr;
535 }
536 alias items = pairs; // TODO Is this Python-style naming better?
537 
538 unittest
539 {
540     string[int] x;
541     x[0] = "a";
542     import std.typecons : tuple;
543     assert(x.pairs == [tuple(0, "a")]);
544 }
545 
546 import std.traits: isInstanceOf, Unqual;
547 import std.range: SortedRange;
548 import std.meta: allSatisfy, staticMap;
549 
550 /// Is the `CommonType` of the `ElementType`s of the ranges `Rs`.
551 template CommonElementType(Rs...)
552 {
553     import std.traits: CommonType;
554     import std.range: ElementType;
555     alias CommonElementType = CommonType!(staticMap!(ElementType, Rs));
556 }
557 
558 ///
559 @safe pure nothrow @nogc unittest
560 {
561     static assert(is(CommonElementType!(int[], double[]) == double));
562 }
563 
564 enum bool haveCommonElementType(Types...) = !is(CommonElementType!Types == void);
565 
566 /// Is `true` iff the ranges `Rs` have a common element type.
567 @safe pure nothrow @nogc unittest
568 {
569     static assert(haveCommonElementType!(bool[], int[]));
570     static assert(!haveCommonElementType!(bool[], int[], string[]));
571 }
572 
573 alias isSortedRange(R) = isInstanceOf!(SortedRange, R); // TODO Or use: __traits(isSame, TemplateOf!R, SortedRange)
574 
575 /** True if R is a `SortedRange`
576  *
577  * SeeAlso:
578  * `std.range.SortedRange`
579  */
580 template isSortedRange_alt(R)
581 {
582     import std.range.primitives : SortedRange;
583     enum isSortedRange = is(R : SortedRange!U, U...);
584 }
585 
586 ///
587 unittest
588 {
589     import std.algorithm : sort;
590     import std.range : assumeSorted;
591     static assert(isSortedRange!(typeof([0, 1, 2])) == false);
592     static assert(isSortedRange!(typeof([0, 1, 2].sort)) == true);
593     static assert(isSortedRange!(typeof([0, 1, 2].assumeSorted)) == true);
594     static assert(isSortedRange!int == false);
595 }
596 
597 /// See_Also: http://forum.dlang.org/post/gkdqakdogqevwzntpgtu@forum.dlang.org
598 template genTypeList(T, size_t n)
599 {
600     import std.meta : AliasSeq;
601     static if (n <= 1)
602         alias genTypeList = T;
603     else
604         alias genTypeList = AliasSeq!(T, genTypeList!(T, n - 1));
605 }
606 
607 /** Return Static Array $(D arr) as a $(D Tuple).
608  *
609  * See_Also: http://forum.dlang.org/post/gkdqakdogqevwzntpgtu@forum.dlang.org
610  * Check if std.conv.to() support conversion from T[n] to std.typecons.Tuple(T, ...).
611  */
612 auto asTuple(T, size_t n)(ref T[n] arr)
613 {
614     import std.typecons : Tuple;
615     return Tuple!(genTypeList!(T, n))(arr);
616 }
617 
618 /** Return: Adjacent $(D N)-Tuples of $(D r).
619  *
620  * TODO: Support ref return via $(D zip) for non-const case.
621  * TODO Use a ring buffer instead of copy?
622  * TODO Add a variant of adjacentTuples that return a static array instead?
623  * See_Also: http://forum.dlang.org/post/gkdqakdogqevwzntpgtu@forum.dlang.org
624  */
625 auto adjacentTuples(size_t N, R)(R r)
626     if (N >= 2 &&
627         isInputRange!R)
628 {
629     struct Range(R)
630     {
631         import core.internal.traits : Unqual;
632         import std.typecons : Tuple;
633         alias E = Unqual!(ElementType!R);
634         enum M = N - 1;  // temporary order
635         alias P = E[M];
636         alias T = Tuple!(genTypeList!(E, N)); // TODO functionize
637 
638         this(R r)
639         {
640             this._source = r;
641             foreach (i; 0 .. M)
642             {
643                 if (!empty)
644                     popFront;
645             }
646         }
647 
648         static if (isInfinite!R)
649         {
650             enum bool empty = false;  // propagate infiniteness
651         }
652         else
653         {
654             bool empty() @property // TODO can't empty be const when R is a MapResult?
655             {
656                 import std.range.primitives : empty;
657                 return _source.empty;
658             }
659         }
660 
661         auto ref front() @property
662         {
663             import std.range.primitives : front;
664             T t;
665             t[0 .. M] = _prevs.asTuple;
666             t[M] = _source.front;
667             return t;
668         }
669 
670         void popFront()
671         {
672             static if (N >= 3)
673             {
674                 // TODO use static foreach to do left-shifting
675 
676                 // Need $(D copy) because $(D source) and $(D dest) may overlap.
677                 // See_Also: http://dlang.org/arrays.html#overlapping-copying
678                 import std.algorithm.mutation : copy;
679                 copy(_prevs[1 .. M], _prevs[0 .. M - 1]);
680             }
681 
682             import std.range.primitives : front, popFront;
683             _prevs[M - 1] = _source.front;
684             _source.popFront();
685         }
686 
687         private:
688         P _prevs;
689         R _source;
690     }
691     return Range!R(r);
692 }
693 
694 auto adjacentPairs(R)(R r)
695 if (isInputRange!R)
696 {
697     return adjacentTuples!(2, R)(r);
698 }
699 
700 auto adjacentTriples(R)(R r)
701 if (isInputRange!R)
702 {
703     return adjacentTuples!(3, R)(r);
704 }
705 
706 ///
707 @safe pure nothrow @nogc unittest
708 {
709     import std.typecons : t = tuple;
710     import std.algorithm : equal, map;
711     auto x = [1, 2, 3, 4, 5, 6, 7].s[].map!(a => a); // test with ForwardRange
712     auto y = x.adjacentTuples!4;
713     assert(y.equal([t(1, 2, 3, 4),
714                     t(2, 3, 4, 5),
715                     t(3, 4, 5, 6),
716                     t(4, 5, 6, 7)].s[]));
717 }
718 
719 ///
720 @safe pure nothrow @nogc unittest
721 {
722     import std.typecons : t = tuple;
723     import std.algorithm : equal;
724     immutable x = [1, 2, 3, 4].s;
725     auto y = x[].adjacentPairs;
726     assert(y.equal([t(1, 2), t(2, 3), t(3, 4)].s[]));
727 }
728 
729 ///
730 @safe pure nothrow @nogc unittest
731 {
732     import std.typecons : t = tuple;
733     import std.algorithm : equal;
734     auto x = ["1", "2", "3", "4"].s;
735     auto y = x[].adjacentPairs;
736     assert(y.equal([t("1", "2"), t("2", "3"), t("3", "4")].s[]));
737 }
738 
739 ///
740 @safe pure nothrow @nogc unittest
741 {
742     import std.typecons : t = tuple;
743     import std.algorithm : equal;
744     immutable x = ["1", "2", "3", "4"].s;
745     auto y = x[].adjacentPairs;
746     assert(y.equal([t("1", "2"), t("2", "3"), t("3", "4")].s[]));
747 }
748 
749 auto rangify(T)(T range)
750     if (__traits(hasMember, T, "length") &&
751         __traits(hasMember, T, "opIndex"))
752 {
753     struct Range
754     {
755         bool empty() { return _counter == range.length; }
756         auto front() { return range[_counter]; }
757         auto popFront() { _counter++; }
758         T range;
759         ulong _counter;
760     }
761     return Range(range);
762 }
763 
764 struct S
765 {
766     int[] arr;
767     auto length() { return arr.length; }
768     int opIndex(size_t i) { return arr[i]; }
769 }
770 
771 unittest
772 {
773     import std.algorithm : equal;
774     auto s = S();
775     s.arr = [1, 2, 3];
776     assert(s.rangify.equal([1, 2, 3].s[]));
777 }
778 
779 /** Overload has questionable memory safety.  Would be quite cool if DIP-1000
780  * could support this use case
781  *
782  * See_Also: http://forum.dlang.org/post/qgrbmkqxffgeiqaigdic@forum.dlang.org
783  */
784 auto staticLengthRange(T, size_t n)(ref T[n] arr)
785 {
786     return .staticLengthRange!(n, T[])(arr[]); // TODO DIP-1000 scope
787 }
788 
789 import std.range.primitives : hasLength, isInputRange;
790 
791 auto staticLengthRange(size_t n, R)(R range)
792 if (isInputRange!R && hasLength!R)
793 {
794     static struct Result
795     {
796         enum size_t length = n;
797         R _range;
798         alias _range this;
799     }
800     assert (range.length == n);
801     return Result(range);
802 }
803 
804 
805 @safe pure nothrow @nogc unittest
806 {
807     import std.algorithm.iteration : map;
808 
809     int[3] sarr = [1, 2, 3];
810     auto r1 = sarr.staticLengthRange;
811     static assert (isInputRange!(typeof(r1)));
812     static assert (r1.length == 3);
813 
814     auto arr = [1, 2, 3, 4].s;
815     auto r2 = arr[].map!(a => a * 2).staticLengthRange!4;
816     static assert (r2.length == 4);
817 }
818 
819 /** Given a `SortedRange` R, `sortingPredicate!R(a, b)` will call in to the
820  * predicate that was used to create the `SortedRange`.
821  *
822  * Params:
823  *   Range = the range to extract the predicate from
824  *   fallbackPred = the sorting predicate to fallback to if `Range` is not a `SortedRange`
825 */
826 template sortingPredicate(Range, alias fallbackPred = "a < b")
827 if (isInputRange!Range)
828 {
829     import std.range : SortedRange;
830     import std.functional : binaryFun;
831     static if (is(Range : SortedRange!P, P...))
832     {
833         alias sortingPredicate = binaryFun!(P[1]);
834     }
835     else
836     {
837         alias sortingPredicate = binaryFun!fallbackPred;
838     }
839 }
840 
841 ///
842 unittest
843 {
844     import std.algorithm : sort;
845     assert(sortingPredicate!(typeof([1].sort!"a < b"))(1, 2) == true);
846     assert(sortingPredicate!(typeof([1].sort!"a > b"))(1, 2) == false);
847     assert(sortingPredicate!(typeof([1].sort!((a, b) => a < b)))(1, 2) == true);
848     assert(sortingPredicate!(typeof([1].sort!((a, b) => a > b)))(1, 2) == false);
849     assert(sortingPredicate!(int[])(1, 2) == true);
850 }
851 
852 /** Faster than std.range.zip on DMD.
853  *
854  * See_Also: https://forum.dlang.org/post/khvwfwvjiblobfybsurd@forum.dlang.org
855  */
856 auto zip(R1, R2)(R1 r1, R2 r2)
857 if (isRandomAccessRange!R1 &&
858     isRandomAccessRange!R2)
859 {
860     static struct Result(R1, R2)
861     {
862         size_t _length;
863 
864         this(R1 r1, R2 r2)
865         {
866             _r1 = r1;
867             _r2 = r2;
868             import std.algorithm.comparison : min;
869             _length = min(r1.length, r2.length);
870         }
871 
872         @property auto front()
873         {
874             import std.typecons : tuple;
875             return tuple(_r1[_index],
876                          _r2[_index]);
877         }
878 
879         @property bool empty() const @safe pure nothrow @nogc
880         {
881             return _index == _length;
882         }
883 
884         @property size_t length() const @safe pure nothrow @nogc
885         {
886             return _length;
887         }
888 
889         void popFront() @safe pure nothrow @nogc
890         {
891             assert(!empty);
892             _index += 1;
893         }
894 
895     private:
896         size_t _index = 0;
897         R1 _r1;
898         R2 _r2;
899     }
900     return Result!(R1,R2)(r1,r2);
901 }
902 
903 @safe pure nothrow @nogc unittest
904 {
905     import nxt.array_help : s;
906     import std.algorithm.comparison : equal;
907     import std.typecons : tuple;
908     const r1 = [1, 2, 3].s;
909     const r2 = [4, 5, 6, 7].s;
910     auto r12 = zip(r1[], r2[]);
911     assert(r12.equal([tuple(1, 4),
912                       tuple(2, 5),
913                       tuple(3, 6)].s[]));
914 }