dkh.container.deque source code

1 module dkh.container.deque;
2 
3 struct DequePayload(T) {
4     import core.exception : RangeError;
5 
6     private T* _data;
7     private uint start, len, cap;
8 
9     @property bool empty() const { return len == 0; }
10     @property size_t length() const { return len; }
11     alias opDollar = length;
12 
13     ref inout(T) opIndex(size_t i) inout {
14         version(assert) if (len <= i) throw new RangeError();
15         if (start + i < cap) return _data[start + i];
16         else return _data[start + i - cap];
17     }
18     ref inout(T) front() inout { return this[0]; }
19     ref inout(T) back() inout { return this[$-1]; }
20 
21     void reserve(size_t newCap) {
22         import core.memory : GC;
23         import std.algorithm : max;
24         import std.conv : to;
25         if (newCap <= cap) return;
26         T* newData = cast(T*)GC.malloc(newCap * T.sizeof);
27         foreach (i; 0..length) {
28             newData[i] = this[i];
29         }
30         _data = newData; start = 0; cap = newCap.to!uint;
31     }
32     void clear() {
33         start = len = 0;
34     }
35     import std.algorithm : max;
36     void insertFront(T item) {
37         if (len == cap) reserve(max(cap * 2, 4));
38         if (start == 0) start += cap;
39         start--; len++;
40         this[0] = item;
41     }
42     void insertBack(T item) {
43         if (len == cap) reserve(max(cap * 2, 4));
44         len++;
45         this[len-1] = item;
46     }
47     void removeFront() {
48         assert(!empty, "Deque.removeFront: Deque is empty");
49         start++; len--;
50         if (start == cap) start = 0;
51     }
52     void removeBack() {
53         assert(!empty, "Deque.removeBack: Deque is empty");        
54         len--;
55     }
56 }
57 
58 /**
59 Deque on ring buffer
60  */
61 struct Deque(T, bool mayNull = true) {
62     import core.exception : RangeError;
63     import std.range : ElementType, isInputRange;
64     import std.traits : isImplicitlyConvertible;
65 
66     alias Payload = DequePayload!T;
67     Payload* _p;
68     
69     static if (!mayNull) @disable this();
70 
71     /// Deque(1, 2, 3)
72     this(U)(U[] values...) if (isImplicitlyConvertible!(U, T)) {
73         _p = new Payload();
74         foreach (v; values) {
75             insertBack(v);
76         }
77     }
78     /// Deque(iota(3))
79     this(Range)(Range r)
80     if (isInputRange!Range &&
81     isImplicitlyConvertible!(ElementType!Range, T) &&
82     !is(Range == T[])) {
83         _p = new Payload();
84         foreach (v; r) {
85             insertBack(v);
86         }
87     }
88     private this(Payload* p) { _p = p; }
89     static Deque make() { return Deque(new Payload()); }
90     
91     private bool havePayload() const { return (!mayNull || _p); }    
92     @property bool empty() const { return (!havePayload || _p.empty); } ///
93     @property size_t length() const { return (havePayload ? _p.length : 0); } ///
94     alias opDollar = length; /// ditto
95 
96     ref inout(T) opIndex(size_t i) inout {
97         assert(!empty, "Deque.opIndex: Deque is empty");
98         return (*_p)[i];
99     } ///
100     ref inout(T) front() inout { return this[0]; } ///
101     ref inout(T) back() inout { return this[$-1]; } ///
102 
103     void clear() { if (_p) _p.clear(); } ///
104 
105     /// Warning: break range
106     void insertFront(T item) {
107         if (mayNull && !_p) _p = new Payload();
108         _p.insertFront(item);
109     }
110     void insertBack(T item) {
111         if (mayNull && !_p) _p = new Payload();
112         _p.insertBack(item);
113     } ///
114     alias opOpAssign(string op : "~") = insertBack; /// ditto
115     alias stableInsertBack = insertBack; /// ditto
116 
117     /// Warning: break range
118     void removeFront() {
119         assert(!mayNull || _p, "Deque.removeFront: Deque is empty");
120         _p.removeFront();
121     }
122     void removeBack() {
123         assert(!mayNull || _p, "Deque.removeBack: Deque is empty");
124         _p.removeBack();
125     } ///
126     alias stableRemoveBack = removeBack; /// ditto
127 
128     /// Random-access range    
129     alias Range = RangeT!(DequePayload!T);
130     alias ConstRange = RangeT!(const DequePayload!T); /// ditto
131     alias ImmutableRange = RangeT!(immutable DequePayload!T); /// ditto
132 
133     size_t[2] opSlice(size_t dim : 0)(size_t start, size_t end) const {
134         assert(start <= end && end <= length);
135         return [start, end];
136     } ///
137     Range opIndex(size_t[2] rng) { return Range(_p, rng[0], rng[1]); } /// Get slice
138     ConstRange opIndex(size_t[2] rng) const { return ConstRange(_p, rng[0], rng[1]); } /// ditto
139     ImmutableRange opIndex(size_t[2] rng) immutable { return ImmutableRange(_p, rng[0], rng[1]); } /// ditto
140     auto opIndex() inout { return this[0..$]; } /// ditto
141 
142     static struct RangeT(QualifiedPayload) {
143         alias A = QualifiedPayload;
144         import std.traits : CopyTypeQualifiers;
145         alias E = CopyTypeQualifiers!(A, T);
146         A *p;
147         size_t l, r;
148 
149         @property bool empty() const { return r <= l; }
150         @property size_t length() const { return r - l; }
151         alias opDollar = length;
152 
153         @property auto save() { return this; }
154         
155         ref inout(E) opIndex(size_t i) inout {
156             version(assert) if (empty) throw new RangeError();
157             return (*p)[l+i];
158         }
159         @property ref inout(E) front() inout { return this[0]; }
160         @property ref inout(E) back() inout { return this[$-1]; }
161 
162         void popFront() {
163             version(assert) if (empty) throw new RangeError();
164             l++;
165         }
166         void popBack() {
167             version(assert) if (empty) throw new RangeError();
168             r--;
169         }
170         
171         size_t[2] opSlice(size_t dim : 0)(size_t start, size_t end) const {
172             assert(start <= end && end <= length);
173             return [start, end];
174         }
175         auto opIndex(size_t[2] rng) { return RangeT(p, l+rng[0], l+rng[1]); }
176         auto opIndex(size_t[2] rng) const { return RangeT!(const A)(p, l+rng[0], l+rng[1]); }
177         auto opIndex(size_t[2] rng) immutable { return RangeT!(immutable A)(p, l+rng[0], l+rng[1]); }
178         auto opIndex() inout { return this[0..$]; }
179     } 
180 }
181 
182 ///
183 unittest {
184     import std.algorithm : equal;
185     auto q = Deque!int();
186 
187     assert(equal(q[], new int[0]));
188     q.insertBack(1);
189     assert(equal(q[], [1]));
190     q.insertBack(2);
191     assert(equal(q[], [1, 2]));
192     q.insertFront(3);
193     assert(equal(q[], [3, 1, 2]));
194     q.removeFront;
195     assert(equal(q[], [1, 2]));
196     q.insertBack(4);
197     assert(equal(q[], [1, 2, 4]));
198     q.insertFront(5);
199     assert(equal(q[], [5, 1, 2, 4]));
200     q.removeBack();
201     assert(equal(q[], [5, 1, 2]));
202 }
203 
204 unittest {
205     import std.algorithm : equal;
206     import std.range.primitives : isRandomAccessRange;
207     import std.container.util : make;
208     auto q = Deque!int();
209     assert(isRandomAccessRange!(typeof(q[])));
210 
211     //insert,remove
212     assert(equal(q[], new int[](0)));
213     q.insertBack(1);
214     assert(equal(q[], [1]));
215     q.insertBack(2);
216     assert(equal(q[], [1, 2]));
217     q.insertFront(3);
218     assert(equal(q[], [3, 1, 2]) && q.front == 3);
219     q.removeFront;
220     assert(equal(q[], [1, 2]) && q.length == 2);
221     q.insertBack(4);
222     assert(equal(q[], [1, 2, 4]) && q.front == 1 && q.back == 4 && q[$-1] == 4);
223     q.insertFront(5);
224     assert(equal(q[], [5, 1, 2, 4]));
225 
226     //range
227     assert(equal(q[][1..3], [1, 2]));
228     assert(equal(q[][][][], q[]));
229     //const range
230     const auto rng = q[];
231     assert(rng.front == 5 && rng.back == 4);
232     
233     //reference type
234     auto q2 = q;
235     q2.insertBack(6);
236     q2.insertFront(7);
237     assert(equal(q[], q2[]) && q.length == q2.length);
238 
239     //construct with make
240     auto a = make!(Deque!int)(1, 2, 3);
241     auto b = make!(Deque!int)([1, 2, 3]);
242     assert(equal(a[], b[]));
243 }
244 
245 unittest {
246     static assert( is(typeof(Deque!(int, true)())));
247     static assert(!is(typeof(Deque!(int, false)())));
248 }
249 
250 unittest {
251     import std.algorithm : equal;
252     import std.range.primitives : isRandomAccessRange;
253     import std.container.util : make;
254     auto q = make!(Deque!int);
255     q.clear();
256     assert(equal(q[], new int[0]));
257     foreach (i; 0..100) {
258         q.insertBack(1);
259         q.insertBack(2);
260         q.insertBack(3);
261         q.insertBack(4);
262         q.insertBack(5);    
263         assert(equal(q[], [1,2,3,4,5]));
264         q.clear();
265         assert(equal(q[], new int[0]));
266     }
267 }
268 
269 unittest {
270     Deque!(int, false) q1 = Deque!(int, false).make();
271     q1.insertBack(3);
272     assert(q1[0] == 3);
273     Deque!(int, false) q2 = Deque!(int, false)(4, 2);
274     assert(q2[0] == 4);
275     Deque!(int, false) q3 = Deque!(int, false)([6, 9]);
276     assert(q3[1] == 9);
277 }
278 
279 unittest {
280     Deque!int a;
281     Deque!int b;
282     a.insertFront(2);
283     assert(b.length == 0);
284 }
285 
286 unittest {
287     import std.algorithm : equal;
288     import std.range : iota;
289     Deque!int a;
290     foreach (i; 0..100) {
291         a.insertBack(i);
292     }
293     assert(equal(a[], iota(100)));
294 }