Unofficial Dub Package Documentation 
1 module nxt.unique_range;
2 
3 import std.range.primitives : hasLength;
4 
5 /** Unique range (slice) owning its source of `Source`.
6 
7     Copy construction is disabled, explicit copying is instead done through
8     member `.dup`.
9  */
10 struct UniqueRange(Source)
11 if (hasLength!Source)       // TODO: use traits `isArrayContainer` checking fo
12 {
13 @safe pure nothrow @nogc:
14     import std.range.primitives : ElementType, isBidirectionalRange;
15     import std.traits : isArray;
16     alias SourceRange = typeof(Source.init[]);
17     alias E = ElementType!SourceRange;
18 
19     @disable this(this);        // not intended to be copied
20 
21     /// Construct from `source`.
22     this(Source source)
23     {
24         import std.algorithm.mutation : move;
25 		() @trusted { move(source, _source); } (); // TODO: remove `move` when compiler does it for us
26         _sourceRange = _source[];
27     }
28 
29     /// Construct from reference to `source`, used by `intoUniqueRange`.
30     private this(ref Source source)
31     {
32         import std.algorithm.mutation : move;
33 		() @trusted { move(source, _source); } (); // TODO: remove `move` when compiler does it for us
34         _sourceRange = _source[];
35     }
36 
37     /// Is `true` if range is empty.
38     bool empty() const @property @trusted
39     {
40         static if (!__traits(hasMember, SourceRange, "empty"))
41             import std.range.primitives : empty;
42         return (cast(Unqual!SourceRange)_sourceRange).empty; // TODO: remove cast and @trusted when SortedRange.empty is const
43     }
44 
45     /// Returns: length of `this`.
46     static if (hasLength!(typeof(Source.init[])))
47         size_t length() const @property @trusted => (cast(Unqual!SourceRange)_sourceRange).length; // TODO: remove cast and @trusted when SortedRange.empty is const
48 
49     /// Front element.
50     @property scope auto ref inout(E) front() inout return @trusted in(!empty)
51     {
52         static if (!__traits(hasMember, SourceRange, "front"))
53             import std.range.primitives : front;
54         return cast(inout(E))(cast(SourceRange)_sourceRange).front;
55     }
56 
57     /// Pop front element.
58     void popFront() in(!empty)
59     {
60         static if (!__traits(hasMember, SourceRange, "popFront"))
61             import std.range.primitives : popFront;
62         _sourceRange.popFront(); // should include check for emptyness
63     }
64 
65     /// Pop front element and return it.
66     E takeFront()() in(!empty)
67     {
68 		scope(exit) popFront();
69 		static if (__traits(isPOD, E))
70 			return front;
71 		else
72 		{
73 			import std.algorithm.mutation : move;
74 			return move(front);
75 		}
76     }
77 
78     static if (isBidirectionalRange!(typeof(Source.init[])))
79     {
80         /// Back element.
81         @property scope auto ref inout(E) back() inout return @trusted in(!empty)
82         {
83             static if (!__traits(hasMember, SourceRange, "back"))
84                 import std.range.primitives : back;
85             return cast(inout(E))(cast(SourceRange)_sourceRange).back;
86         }
87 
88         /// Pop back element.
89         void popBack() in(!empty)
90         {
91             static if (!__traits(hasMember, SourceRange, "popBack"))
92                 import std.range.primitives : popBack;
93             _sourceRange.popBack(); // should include check for emptyness
94         }
95 
96         /// Pop back element and return it.
97         E takeBack()() in(!empty)
98         {
99             import core.internal.traits : hasElaborateDestructor;
100             static if (__traits(isCopyable, E) &&
101                        !hasElaborateDestructor!E)
102             {
103                 typeof(return) value = back;
104                 popBack();
105                 return value;
106             }
107             else
108             {
109                 static assert(0, "TODO: if back is an l-value move it out and return it");
110                 // import std.algorithm.mutation : move;
111                 // import core.internal.traits : Unqual;
112                 // TODO: reinterpret as typeof(*(cast(Unqual!E*)(&_source[_backIx]))) iff `E` doesn't contain any immutable indirections
113                 // typeof(return) value = move(_sourceRange.back);
114                 // popBack();
115                 // return value;
116             }
117         }
118         alias stealBack = takeBack;
119     }
120 
121     /// Returns: shallow duplicate of `this`.
122     static if (__traits(hasMember, Source, "dup"))
123         @property typeof(this) dup()() const => typeof(return)(_source.dup);
124 
125 private:
126     Source _source; // typically a non-reference counted container type with disable copy construction
127     SourceRange _sourceRange;
128 }
129 
130 /** Returns: A range of `Source` that owns its `source` (data container).
131     Similar to Rust's `into_iter`.
132  */
133 UniqueRange!Source intoUniqueRange(Source)(Source source)
134 	=> typeof(return)(source); // construct from reference
135 
136 /// A generator is a range which owns its state (typically a non-reference counted container).
137 alias intoGenerator = intoUniqueRange;
138 
139 /// basics
140 @safe pure nothrow @nogc unittest
141 {
142     import nxt.container.dynamic_array : SA = DynamicArray;
143     import std.traits : isIterable;
144     import std.range.primitives : isInputRange;
145     alias C = SA!int;
146 
147     auto cs = C([11, 13, 15, 17].s).intoUniqueRange;
148     auto cs2 = cs.dup;
149 
150     assert(cs !is cs2);
151 
152     assert(cs == cs2);
153     cs2.popFront();
154     assert(cs2.length == 3);
155     assert(cs != cs2);
156 
157     static assert(isInputRange!(typeof(cs)));
158     static assert(isIterable!(typeof(cs)));
159 
160     assert(!cs.empty);
161     assert(cs.length == 4);
162     assert(cs.front == 11);
163     assert(cs.back == 17);
164 
165     cs.popFront();
166     assert(cs.length == 3);
167     assert(cs.front == 13);
168     assert(cs.back == 17);
169 
170     cs.popBack();
171     assert(cs.length == 2);
172     assert(cs.front == 13);
173     assert(cs.back == 15);
174 
175     assert(cs.takeFront() == 13);
176     assert(cs.length == 1);
177     assert(cs.front == 15);
178     assert(cs.back == 15);
179 
180     assert(cs.takeBack() == 15);
181     assert(cs.length == 0);
182     assert(cs.empty);
183 }
184 
185 /// combined with Phobos ranges
186 @safe pure nothrow unittest
187 {
188     import nxt.container.dynamic_array : SA = DynamicArray;
189     alias C = SA!int;
190     assert(C([11, 13, 15, 17].s)
191            .intoUniqueRange()
192            .filterUnique!(_ => _ != 11)
193            .mapUnique!(_ => 2*_)
194            .equal([2*13, 2*15, 2*17]));
195 }
196 
197 import std.functional : unaryFun;
198 
199 template mapUnique(fun...)
200 if (fun.length >= 1)
201 {
202     import std.algorithm.mutation : move;
203     import std.range.primitives : isInputRange, ElementType;
204     import core.internal.traits : Unqual;
205 
206     auto mapUnique(Range)(Range r)
207     if (isInputRange!(Unqual!Range))
208     {
209         import std.meta : AliasSeq, staticMap;
210 
211         alias RE = ElementType!(Range);
212         static if (fun.length > 1)
213         {
214             import std.functional : adjoin;
215             import std.meta : staticIndexOf;
216 
217             alias _funs = staticMap!(unaryFun, fun);
218             alias _fun = adjoin!_funs;
219 
220             // Once DMD issue #5710 is fixed, this validation loop can be moved into a template.
221             foreach (f; _funs)
222                 static assert(!is(typeof(f(RE.init)) == void),
223                     "Mapping function(s) must not return void: " ~ _funs.stringof);
224         }
225         else
226         {
227             alias _fun = unaryFun!fun;
228             alias _funs = AliasSeq!(_fun);
229 
230             // Do the validation separately for single parameters due to DMD issue #15777.
231             static assert(!is(typeof(_fun(RE.init)) == void),
232                 "Mapping function(s) must not return void: " ~ _funs.stringof);
233         }
234 
235         return MapUniqueResult!(_fun, Range)(move(r));
236     }
237 }
238 
239 private struct MapUniqueResult(alias fun, Range)
240 {
241     import core.internal.traits : Unqual;
242     import std.range.primitives : isInputRange, isForwardRange, isBidirectionalRange, isRandomAccessRange, isInfinite, hasSlicing;
243     import std.algorithm.mutation : move;
244 
245     alias R = Unqual!Range;
246     R _input;
247 
248     this(R input)
249     {
250         _input = move(input); // TODO: remove `move` when compiler does it for us
251     }
252 
253     static if (isInfinite!R)
254         enum bool empty = false; ///< Propagate infinite-ness.
255     else
256         @property bool empty() => _input.empty;
257 
258     auto ref front() @property in(!empty) => fun(_input.front);
259     void popFront() in(!empty) => _input.popFront();
260 
261     static if (isBidirectionalRange!R)
262     {
263         auto ref back()() @property in(!empty) => fun(_input.back);
264         void popBack()() in(!empty) => _input.popBack();
265     }
266 
267     static if (isRandomAccessRange!R)
268     {
269         static if (is(typeof(_input[ulong.max])))
270             private alias opIndex_t = ulong;
271         else
272             private alias opIndex_t = uint;
273         auto ref opIndex(opIndex_t index) => fun(_input[index]);
274     }
275 
276     static if (hasLength!R)
277     {
278         @property auto length() => _input.length;
279         alias opDollar = length;
280     }
281 
282     static if (hasSlicing!R &&
283                __traits(isCopyable, R))
284     {
285         static if (is(typeof(_input[ulong.max .. ulong.max])))
286             private alias opSlice_t = ulong;
287         else
288             private alias opSlice_t = uint;
289         static if (hasLength!R)
290             auto opSlice(opSlice_t low, opSlice_t high) => typeof(this)(_input[low .. high]);
291         else static if (is(typeof(_input[opSlice_t.max .. $])))
292         {
293             struct DollarToken{}
294             enum opDollar = DollarToken.init;
295             auto opSlice(opSlice_t low, DollarToken) => typeof(this)(_input[low .. $]);
296 			import std.range : takeExactly;
297             auto opSlice(opSlice_t low, opSlice_t high) => this[low .. $].takeExactly(high - low);
298         }
299     }
300 
301     static if (isForwardRange!R &&
302                __traits(isCopyable, R))    // TODO: should save be allowed for non-copyable?
303         @property auto save() => typeof(this)(_input.save);
304 }
305 
306 // TODO: Add duck-typed interface that shows that result is still sorted according to `predicate`
307 template filterUnique(alias predicate)
308 if (is(typeof(unaryFun!predicate)))
309 {
310     import std.algorithm.mutation : move;
311     import std.range.primitives : isInputRange;
312     import core.internal.traits : Unqual;
313     auto filterUnique(Range)(Range range)
314     if (isInputRange!(Unqual!Range))
315 		=> FilterUniqueResult!(unaryFun!predicate, Range)(move(range));
316 }
317 
318 // TODO: Add duck-typed interface that shows that result is still sorted according to `predicate`
319 private struct FilterUniqueResult(alias pred, Range)
320 {
321     import std.algorithm.mutation : move;
322     import std.range.primitives : isForwardRange, isInfinite;
323     import core.internal.traits : Unqual;
324     alias R = Unqual!Range;
325     R _input;
326 
327     this(R r)
328     {
329         _input = move(r);       // TODO: remove `move` when compiler does it for us
330         while (!_input.empty && !pred(_input.front))
331             _input.popFront();
332     }
333 
334     static if (__traits(isCopyable, Range))
335         auto opSlice() => this;
336 
337     static if (isInfinite!Range)
338         enum bool empty = false;
339     else
340         bool empty() @property => _input.empty;
341 
342     void popFront()
343     {
344         do
345             _input.popFront();
346         while (!_input.empty && !pred(_input.front));
347     }
348 
349     auto ref front() @property in(!empty) => _input.front;
350 
351     static if (isForwardRange!R &&
352                __traits(isCopyable, R)) // TODO: should save be allowed for non-copyable?
353         auto save() @property => typeof(this)(_input.save);
354 }
355 
356 // TODO: move these hidden behind template defs of takeUnique
357 import core.internal.traits : Unqual;
358 import std.range.primitives : isInputRange, isInfinite, hasSlicing;
359 
360 /// Unique take.
361 UniqueTake!R takeUnique(R)(R input, size_t n)
362     if (is(R T == UniqueTake!T))
363 {
364     import std.algorithm.mutation : move;
365     import std.algorithm.comparison : min;
366     return R(move(input.source), // TODO: remove `move` when compiler does it for us
367              min(n, input._maxAvailable));
368 }
369 
370 /// ditto
371 UniqueTake!(R) takeUnique(R)(R input, size_t n)
372 if (isInputRange!(Unqual!R) &&
373     (isInfinite!(Unqual!R) ||
374      !hasSlicing!(Unqual!R) &&
375      !is(R T == UniqueTake!T)))
376 {
377     import std.algorithm.mutation : move;
378     return UniqueTake!R(move(input), n); // TODO: remove `move` when compiler does it for us
379 }
380 
381 struct UniqueTake(Range)
382 if (isInputRange!(Unqual!Range) &&
383     //take _cannot_ test hasSlicing on infinite ranges, because hasSlicing uses
384     //take for slicing infinite ranges.
385     !((!isInfinite!(Unqual!Range) && hasSlicing!(Unqual!Range)) || is(Range T == UniqueTake!T)))
386 {
387     import std.range.primitives : isForwardRange, hasAssignableElements, ElementType, hasMobileElements, isRandomAccessRange, moveFront;
388 
389     private alias R = Unqual!Range;
390 
391     /// User accessible in read and write
392     public R source;
393 
394     private size_t _maxAvailable;
395 
396     alias Source = R;
397 
398     this(R source, size_t _maxAvailable)
399     {
400         import std.algorithm.mutation : move;
401         this.source = move(source);
402         this._maxAvailable = _maxAvailable;
403     }
404 
405     /// Range primitives
406     bool empty() @property => _maxAvailable == 0 || source.empty;
407 
408     /// ditto
409 	auto ref front() @property in(!empty) => source.front;
410 
411     /// ditto
412     void popFront() in(!empty)
413     {
414         source.popFront();
415         --_maxAvailable;
416     }
417 
418     static if (isForwardRange!R)
419         /// ditto
420 		UniqueTake save() @property => UniqueTake(source.save, _maxAvailable);
421 
422     static if (hasAssignableElements!R)
423         /// ditto
424         @property auto front(ElementType!R v)
425 		in(!empty, "Attempting to assign to the front of an empty " ~ UniqueTake.stringof)
426         {
427             // This has to return auto instead of void because of Bug 4706.
428             source.front = v;
429         }
430 
431     // static if (hasMobileElements!R)
432     // {
433     //     /// ditto
434     //     auto moveFront()
435     //     {
436     //         assert(!empty,
437     //             "Attempting to move the front of an empty "
438     //             ~ UniqueTake.stringof);
439     //         return source.moveFront();
440     //     }
441     // }
442 
443     static if (isInfinite!R)
444     {
445         /// ditto
446         @property size_t length() const => _maxAvailable;
447         /// ditto
448         alias opDollar = length;
449 
450         //Note: Due to UniqueTake/hasSlicing circular dependency,
451         //This needs to be a restrained template.
452         /// ditto
453         auto opSlice()(size_t i, size_t j)
454         if (hasSlicing!R)
455         in(i <= j, "Invalid slice bounds")
456         in(j <= length, "Attempting to slice past the end of a " ~ UniqueTake.stringof)
457 			=> source[i .. j];
458     }
459     else static if (hasLength!R)
460     {
461         /// ditto
462         @property size_t length()
463         {
464             import std.algorithm.comparison : min;
465             return min(_maxAvailable, source.length);
466         }
467         alias opDollar = length;
468     }
469 
470     static if (isRandomAccessRange!R)
471     {
472         /// ditto
473         void popBack()
474 		in(!empty, "Attempting to popBack() past the beginning of a " ~ UniqueTake.stringof)
475         {
476             --_maxAvailable;
477         }
478 
479         /// ditto
480         @property auto ref back()
481 		in(!empty, "Attempting to fetch the back of an empty " ~ UniqueTake.stringof)
482 			=> source[this.length - 1];
483 
484         /// ditto
485         auto ref opIndex(size_t index)
486 		in(index < length, "Attempting to index out of the bounds of a " ~ UniqueTake.stringof)
487 			=> source[index];
488 
489         static if (hasAssignableElements!R)
490         {
491             /// ditto
492             @property auto back(ElementType!R v)
493 			in(!empty, "Attempting to assign to the back of an empty " ~ UniqueTake.stringof)
494             {
495                 // This has to return auto instead of void because of Bug 4706.
496                 source[this.length - 1] = v;
497             }
498 
499             /// ditto
500             void opIndexAssign(ElementType!R v, size_t index)
501 			in(index < length, "Attempting to index out of the bounds of a " ~ UniqueTake.stringof)
502             {
503                 source[index] = v;
504             }
505         }
506 
507         static if (hasMobileElements!R)
508         {
509             /// ditto
510             auto moveBack()
511 			in(!empty, "Attempting to move the back of an empty " ~ UniqueTake.stringof)
512 				=> source.moveAt(this.length - 1);
513 
514             /// ditto
515             auto moveAt(size_t index)
516 			in(index < length, "Attempting to index out of the bounds of a " ~ UniqueTake.stringof)
517 				=> source.moveAt(index);
518         }
519     }
520 
521     /**
522     Access to maximal length of the range.
523     Note: the actual length of the range depends on the underlying range.
524     If it has fewer elements, it will stop before maxLength is reached.
525     */
526     @property size_t maxLength() const => _maxAvailable;
527 }
528 
529 /// array range
530 @safe pure nothrow @nogc unittest
531 {
532     import nxt.container.dynamic_array : SA = DynamicArray;
533     import std.traits : isIterable;
534     import std.range.primitives : isInputRange;
535     alias C = SA!int;
536 
537     auto cs = C([11, 13].s).intoUniqueRange;
538 
539     alias CS = typeof(cs);
540     static assert(isInputRange!(typeof(cs)));
541     static assert(isIterable!(typeof(cs)));
542 
543     assert(cs.front == 11);
544     cs.popFront();
545 
546     assert(cs.front == 13);
547     cs.popFront();
548 
549     assert(cs.empty);
550 }
551 
552 import std.functional : binaryFun;
553 
554 InputRange findUnique(alias pred = "a == b", InputRange, Element)(InputRange haystack, scope Element needle)
555 if (isInputRange!InputRange &&
556     is (typeof(binaryFun!pred(haystack.front, needle)) : bool))
557 {
558     for (; !haystack.empty; haystack.popFront())
559         if (binaryFun!pred(haystack.front, needle))
560             break;
561     import std.algorithm.mutation : move;
562     return move(haystack);
563 }
564 
565 version(unittest)
566 {
567     import nxt.array_help : s;
568     import nxt.dbgio : dbg;
569 	import nxt.array_algorithm : equal;
570 }

Page generated by adrdox