1 /**
2     Some additional containers.
3 
4     Copyright: © 2019 Arne Ludwig <arne.ludwig@posteo.de>
5     License: Subject to the terms of the MIT license, as written in the
6              included LICENSE file.
7     Authors: Arne Ludwig <arne.ludwig@posteo.de>
8 */
9 module dalicious.container;
10 
11 import core.exception;
12 
13 
14 /// An array-based implementation of a ring buffer.
15 struct RingBuffer(T, size_t staticBufferSize = size_t.max)
16 {
17 private:
18 
19     static if (staticBufferSize < size_t.max)
20        T[staticBufferSize] _buffer;
21     else
22        T[] _buffer;
23     ptrdiff_t _frontPtr = -1;
24     ptrdiff_t _backPtr;
25 
26 public:
27 
28     static if (staticBufferSize == size_t.max)
29     {
30         @disable this();
31 
32         this(size_t bufferSize)
33         {
34             this._buffer = new T[bufferSize];
35         }
36     }
37 
38 
39     static if (staticBufferSize < size_t.max)
40         enum bufferSize = _buffer.length;
41     else
42         @property size_t bufferSize() const pure nothrow @safe
43         {
44             return _buffer.length;
45         }
46 
47 
48     @property RingBuffer!(T, staticBufferSize) save() const pure nothrow @trusted
49     {
50         return cast(typeof(return)) this;
51     }
52 
53 
54     @property bool empty() const pure nothrow @safe
55     {
56         return _frontPtr < _backPtr || bufferSize == 0;
57     }
58 
59 
60     @property size_t length() const pure nothrow @safe
61     {
62         return empty ? 0 : _frontPtr - _backPtr + 1;
63     }
64 
65 
66     @property auto ref T front()
67     {
68         assert(!empty, "Attempting to fetch the front of an empty RingBuffer");
69 
70         return _buffer[indexOf(_frontPtr)];
71     }
72 
73 
74     @property void front(T newFront)
75     {
76         assert(!empty, "Attempting to assign to the front of an empty RingBuffer");
77 
78         this.front() = newFront;
79     }
80 
81 
82     @property auto ref T back()
83     {
84         assert(!empty, "Attempting to fetch the back of an empty RingBuffer");
85 
86         return _buffer[indexOf(_backPtr)];
87     }
88 
89 
90     @property void back(T newBack)
91     {
92         assert(!empty, "Attempting to assign to the back of an empty RingBuffer");
93 
94         this.back() = newBack;
95     }
96 
97 
98     void popFront() pure nothrow @safe
99     {
100         assert(!empty, "Attempting to popFront an empty RingBuffer");
101 
102         --_frontPtr;
103     }
104 
105 
106     void popBack() pure nothrow @safe
107     {
108         assert(!empty, "Attempting to popBack an empty RingBuffer");
109 
110         ++_backPtr;
111     }
112 
113 
114     void pushFront(T value)
115     {
116         assert(bufferSize > 0, "Attempting to pushFront an zero-sized RingBuffer");
117 
118         auto wasEmpty = empty;
119 
120         ++_frontPtr;
121         if (!wasEmpty && indexOf(_backPtr) == indexOf(_frontPtr))
122             ++_backPtr;
123 
124         front = value;
125     }
126 
127     alias put = pushFront;
128 
129 
130     void pushBack(T value)
131     {
132         assert(bufferSize > 0, "Attempting to pushBack an zero-sized RingBuffer");
133 
134         --_backPtr;
135 
136         if (indexOf(_frontPtr) == indexOf(_backPtr))
137             --_frontPtr;
138 
139         back = value;
140     }
141 
142 
143     private size_t indexOf(ptrdiff_t ptr) const pure nothrow @safe
144     {
145         // make sure the index is positive
146         return cast(size_t) ((ptr % bufferSize) + bufferSize) % bufferSize;
147     }
148 }
149 
150 unittest
151 {
152     import std.meta;
153     import std.range.primitives;
154 
155     alias Element = int;
156     alias DyanmicRB = RingBuffer!Element;
157     alias StaticRB = RingBuffer!(Element, 10);
158 
159     enum isDefaultConstructible(T) = is(typeof(T()));
160 
161     static assert(!isDefaultConstructible!DyanmicRB);
162     static assert(isDefaultConstructible!StaticRB);
163 
164     static foreach (alias RB; AliasSeq!(DyanmicRB, StaticRB))
165     {
166         static assert(isInputRange!RB);
167         static assert(isOutputRange!(RB, Element));
168         static assert(isForwardRange!RB);
169         static assert(isBidirectionalRange!RB);
170         static assert(is(ElementType!RB == Element));
171         static assert(hasAssignableElements!RB);
172         static assert(hasLvalueElements!RB);
173         static assert(hasLength!RB);
174         static assert(!isInfinite!RB);
175     }
176 }
177 
178 /// Ring buffer stores the `bufferSize` most recent elements.
179 unittest
180 {
181     import std.algorithm;
182 
183     auto buffer = RingBuffer!int(5);
184 
185     buffer.pushFront(1);
186     buffer.pushFront(2);
187     buffer.pushFront(3);
188     buffer.pushFront(4);
189     buffer.pushFront(5);
190 
191     assert(buffer.front == 5);
192     assert(equal(buffer, [5, 4, 3, 2, 1]));
193 
194     buffer.pushFront(6);
195 
196     assert(buffer.front == 6);
197     assert(equal(buffer, [6, 5, 4, 3, 2]));
198 }
199 
200 /// Ring buffer may have a static size.
201 unittest
202 {
203     import std.algorithm;
204 
205     auto buffer = RingBuffer!(int, 5)();
206 
207     buffer.pushFront(1);
208     buffer.pushFront(2);
209     buffer.pushFront(3);
210     buffer.pushFront(4);
211     buffer.pushFront(5);
212 
213     assert(buffer.front == 5);
214     assert(equal(buffer, [5, 4, 3, 2, 1]));
215 
216     buffer.pushFront(6);
217 
218     assert(buffer.front == 6);
219     assert(equal(buffer, [6, 5, 4, 3, 2]));
220 }
221 
222 /// Elements can be removed.
223 unittest
224 {
225     import std.algorithm;
226 
227     auto buffer = RingBuffer!int(5);
228 
229     buffer.pushFront(1);
230     buffer.pushFront(2);
231     buffer.pushFront(3);
232     buffer.pushFront(4);
233     buffer.pushFront(5);
234 
235     assert(buffer.length == 5);
236     assert(equal(buffer, [5, 4, 3, 2, 1]));
237 
238     buffer.popFront();
239     buffer.popBack();
240 
241     assert(buffer.length == 3);
242     assert(equal(buffer, [4, 3, 2]));
243 }
244 
245 /// The buffer is double-ended.
246 unittest
247 {
248     import std.algorithm;
249 
250     auto buffer = RingBuffer!int(5);
251 
252     buffer.pushFront(1);
253     buffer.pushFront(2);
254     buffer.pushFront(3);
255     buffer.pushFront(4);
256     buffer.pushFront(5);
257     buffer.pushFront(6);
258 
259     assert(buffer.front == 6);
260     assert(buffer.back == 2);
261     assert(equal(buffer, [6, 5, 4, 3, 2]));
262 
263     buffer.pushBack(1);
264 
265     assert(buffer.front == 5);
266     assert(buffer.back == 1);
267     assert(equal(buffer, [5, 4, 3, 2, 1]));
268 }