1 /**
2 License: public domain
3 Authors: Simon Bürger
4 */
5 
6 module jive.queue;
7 
8 import core.exception : RangeError;
9 import core.stdc.string : memmove, memcpy, memset;
10 import std.algorithm;
11 import std.conv : emplace;
12 import std.range;
13 import std.traits;
14 import jive.internal;
15 
16 
17 /**
18  *  Array structure that allows addition/deletion at both ends.
19  *
20  *  Intended to be used as a FIFO-queue or as a stack by combining
21  *  `pushFront`/`pushBack` and `popFront`/`popBack` appropriately. Implemented
22  *  as a circular buffer inside a continuous block of memory that is
23  *  automatically expanded as necessary, similar to jive.Array.
24  */
25 struct Queue(V)
26 {
27 	private V* _ptr = null;			// unused elements are undefined
28 	private size_t _capacity = 0;	// size of buf
29 	private size_t _length = 0;		// used size
30 	private size_t _left = 0;		// offset into buffer
31 
32 	/** constructor that gets content from arbitrary range */
33 	this(Stuff)(Stuff stuff)
34 		if(isInputRange!Stuff && is(ElementType!Stuff:V))
35 	{
36 		static if(hasLength!Stuff)
37 			reserve(_length + stuff.length);
38 
39 		foreach(ref x; stuff)
40 			pushBack(x);
41 	}
42 
43 	/** post-blit that does a full copy */
44 	this(this)
45 	{
46 		auto newPtr = jiveMalloc!V(_length);
47 
48 		static if(hasElaborateCopyConstructor!V)
49 		{
50 			for(size_t i = 0; i < _length; ++i)
51 				emplace(newPtr + i, this[i]);
52 		}
53 		else
54 		{
55 			if(_left + _length <=  _capacity)
56 			{
57 				memcpy(newPtr, _ptr + _left, V.sizeof * _length);
58 			}
59 			else
60 			{
61 				memcpy(newPtr, _ptr + _left, V.sizeof * (_capacity - _left));
62 				memcpy(newPtr + _capacity - _left, _ptr, V.sizeof * (_length - _capacity + _left));
63 			}
64 		}
65 		_ptr = newPtr;
66 		_capacity = _length;
67 		_left = 0;
68 	}
69 
70 	/** destructor */
71 	~this()
72 	{
73 		static if (hasElaborateDestructor!V)
74 			foreach (ref x; this[])
75 				destroy(x);
76 
77 		jiveFree(_ptr);
78 		_ptr = null; // probably not necessary, just a precaution
79 	}
80 
81 	/** check for emptiness */
82 	bool empty() const pure nothrow @property @safe
83 	{
84 		return _length == 0;
85 	}
86 
87 	/** number of elements */
88 	size_t length() const pure nothrow @property @safe
89 	{
90 		return _length;
91 	}
92 
93 	/** ditto */
94 	size_t opDollar() const pure nothrow @property @safe
95 	{
96 		return _length;
97 	}
98 
99 	/** number of elements this structure can hold without further allocations */
100 	size_t capacity() const pure nothrow @property @safe
101 	{
102 		return _capacity;
103 	}
104 
105 	/** make sure this structure can contain given number of elements without further allocs */
106 	void reserve(size_t newCap, bool overEstimate = false) nothrow @trusted
107 	{
108 		if(newCap <= _capacity)
109 			return;
110 
111 		if(overEstimate)
112 			newCap = max(newCap, 2*_capacity);
113 
114 		auto newPtr = jiveMalloc!V(newCap);
115 		if(_left + _length <=  _capacity)
116 		{
117 			memcpy(newPtr, _ptr + _left, V.sizeof * _length);
118 		}
119 		else
120 		{
121 			memcpy(newPtr, _ptr + _left, V.sizeof * (_capacity - _left));
122 			memcpy(newPtr + _capacity - _left, _ptr, V.sizeof * (_length - _capacity + _left));
123 		}
124 
125 		static if(hasIndirections!V)
126 			memset(newPtr + _length, 0, V.sizeof * (newCap - _length)); // prevent false pointers
127 
128 		jiveFree(_ptr);
129 		_ptr = newPtr;
130 		_capacity = newCap;
131 		_left = 0;
132 	}
133 
134 	/** default range */
135 	auto opSlice() nothrow pure @trusted
136 	{
137 		if(_left + _length <= _capacity)
138 			return chain(
139 					_ptr[_left .. _left + _length],
140 					_ptr[0 .. 0]
141 					);
142 		else
143 			return chain(
144 					_ptr[_left .. _capacity],
145 					_ptr[0 .. _left + _length - _capacity]
146 					);
147 	}
148 
149 	/** ditto */
150 	auto opSlice() const nothrow pure @trusted
151 	{
152 		if(_left + _length <= _capacity)
153 			return chain(
154 					_ptr[_left .. _left + _length],
155 					_ptr[0 .. 0]
156 					);
157 		else
158 			return chain(
159 					_ptr[_left .. _capacity],
160 					_ptr[0 .. _left + _length - _capacity]
161 					);
162 	}
163 
164 	/** ditto */
165 	auto opSlice() immutable nothrow pure @trusted
166 	{
167 		if(_left + _length <= _capacity)
168 			return chain(
169 					_ptr[_left .. _left + _length],
170 					_ptr[0 .. 0]
171 					);
172 		else
173 			return chain(
174 					_ptr[_left .. _capacity],
175 					_ptr[0 .. _left + _length - _capacity]
176 					);
177 	}
178 
179 	/** indexing */
180 	ref inout(V) opIndex(string file = __FILE__, int line = __LINE__)(size_t i) inout pure nothrow @trusted
181 	{
182 		if(boundsChecks && i >= _length)
183 			assert(false, boundsCheckMsg!(file, line));
184 		return _ptr[(_left + i) % _capacity];
185 	}
186 
187 	/** first element, same as this[0] */
188 	ref inout(V) front(string file = __FILE__, int line = __LINE__)() inout pure nothrow @property
189 	{
190 		if(boundsChecks && empty)
191 			assert(false, boundsCheckMsg!(file, line));
192 		return _ptr[_left];
193 	}
194 
195 	/** last element, same as this[$-1] */
196 	ref inout(V) back(string file = __FILE__, int line = __LINE__)() inout pure nothrow @property
197 	{
198 		if(boundsChecks && empty)
199 			assert(false, boundsCheckMsg!(file, line));
200 		return _ptr[(_left + _length - 1) % _capacity];
201 	}
202 
203 	/** add an element to the front of the queue */
204 	void pushFront(V val) @trusted
205 	{
206 		reserve(_length + 1, true);
207 		++_length;
208 		if(_left == 0)
209 			_left = _capacity-1;
210 		else
211 			--_left;
212 		moveEmplace(val, front);
213 	}
214 
215 	/** add multiple elements to the front of the queue */
216 	void pushFront(Stuff)(Stuff stuff)
217 		if(isInputRange!Stuff && is(ElementType!Stuff:V))
218 	{
219 		static if(hasLength!Stuff)
220 			reserve(_length + stuff.length, true);
221 
222 		foreach(ref x; stuff)
223 			pushFront(x);
224 	}
225 
226 	/** add an element to the back of the queue */
227 	void pushBack(V val) @trusted
228 	{
229 		reserve(_length + 1, true);
230 		++_length;
231 		moveEmplace(val, back);
232 	}
233 
234 	/** add multiple elements to the back of the queue */
235 	void pushBack(Stuff)(Stuff stuff)
236 		if(!is(Stuff:V) && isInputRange!Stuff && is(ElementType!Stuff:V))
237 	{
238 		static if(hasLength!Stuff)
239 			reserve(_length + stuff.length, true);
240 
241 		foreach(ref x; stuff)
242 			pushBack(x);
243 	}
244 
245 	/** removes first element of the queue and returns it */
246 	V popFront(string file = __FILE__, int line = __LINE__)() @trusted
247 	{
248 		if(boundsChecks && empty)
249 			assert(false, boundsCheckMsg!(file, line));
250 
251 		V r = void;
252 		memcpy(&r, &front(), V.sizeof);
253 		static if(hasIndirections!V)
254 			memset(&front(), 0, V.sizeof);
255 		_left = (_left + 1) % _capacity;
256 		--_length;
257 		return r;
258 	}
259 
260 	/** removes last element of the queue and returns it */
261 	V popBack(string file = __FILE__, int line = __LINE__)() @trusted
262 	{
263 		if(boundsChecks && empty)
264 			assert(false, boundsCheckMsg!(file, line));
265 
266 		V r = void;
267 		memcpy(&r, &back(), V.sizeof);
268 		static if(hasIndirections!V)
269 			memset(&back(), 0, V.sizeof);
270 		--_length;
271 		return r;
272 	}
273 
274 	/** remove all content but keep allocated memory */
275 	void clear() @trusted
276 	{
277 		// TODO: remove @trusted in case V's destructor is @system
278 		static if(hasElaborateDestructor!V)
279 			for(size_t i = 0; i < _length; ++i)
280 				destroy(this[i]);
281 		static if(hasIndirections!V)
282 			memset(_ptr, 0, V.sizeof * _capacity);
283 		_length = 0;
284 	}
285 }
286 
287 ///
288 /*@nogc*/ nothrow pure @safe unittest
289 {
290 	Queue!int a;
291 	a.pushBack([1,2,3]);
292 	a.pushFront([4,5,6]);
293 
294 	assert(equal(a[], [6,5,4,1,2,3]));
295 
296 	assert(a.popFront == 6);
297 	assert(a.popBack == 3);
298 
299 	assert(a.length == 4);
300 }
301 
302 // check actual 'circular' buffer
303 @nogc nothrow pure @safe unittest
304 {
305 	Queue!int q;
306 	q.reserve(3);
307 	assert(q.capacity == 3);
308 	assert(q.empty);
309 
310 	// forward
311 	q.pushBack(1);
312 	q.pushBack(2);
313 	q.pushBack(3);
314 	assert(q.popFront == 1); q.pushBack(4);
315 	assert(q.popFront == 2); q.pushBack(5);
316 	assert(q.popFront == 3); q.pushBack(6);
317 	assert(q.popFront == 4); q.pushBack(7);
318 	assert(q[0] == 5);
319 	assert(q[1] == 6);
320 	assert(q[2] == 7);
321 
322 	q.clear();
323 	assert(q.empty);
324 	assert(q.capacity == 3);
325 
326 	// backward
327 	q.pushFront(1);
328 	q.pushFront(2);
329 	q.pushFront(3);
330 	assert(q.popBack == 1); q.pushFront(4);
331 	assert(q.popBack == 2); q.pushFront(5);
332 	assert(q.popBack == 3); q.pushFront(6);
333 	assert(q.popBack == 4); q.pushFront(7);
334 	assert(q[$-1] == 5);
335 	assert(q[$-2] == 6);
336 	assert(q[$-3] == 7);
337 }
338 
339 // check correct invocation of postblit/destructor
340 unittest
341 {
342 	int counter = 0;
343 
344 	struct S
345 	{
346 		bool active;
347 		this(bool active) { this.active = active; if(active) ++counter; }
348 		this(this) { if(active) ++counter; }
349 		~this() { if(active) --counter; }
350 	}
351 
352 	{
353 		Queue!S a;
354 		assert(counter == 0);
355 		a.pushBack(S(true));
356 		assert(counter == 1);
357 		a.pushFront(a[0]);
358 		assert(counter == 2);
359 		a.reserve(5);
360 		a.pushBack(a[]);
361 
362 		Queue!S b = a;
363 		assert(equal(a[], b[]));
364 		assert(counter == 8);
365 	}
366 	assert(counter == 0);
367 }
368 
369 // check move-semantics
370 unittest
371 {
372 	struct S3
373 	{
374 		int x;
375 		alias x this;
376 		this(this) { assert(x == 0); }
377 	}
378 
379 	Queue!S3 a;
380 	a.pushBack(S3(1));
381 	a.pushBack(S3(2));
382 	a.pushFront(S3(3));
383 	a.reserve(5);
384 	a.popBack();
385 	a.popFront();
386 	a[0] = S3(4);
387 	a.clear();
388 }
389 
390 // type with no @safe/pure/etc-attributes
391 unittest
392 {
393 	struct S
394 	{
395 		int* x;
396 		this(this){ }
397 		~this(){ }
398 	}
399 
400 	static assert(hasIndirections!S);
401 	static assert(hasElaborateDestructor!S);
402 
403 	S s;
404 	Queue!S a;
405 	a.pushBack(s);
406 	a.pushBack([s,s]);
407 	a.pushFront(s);
408 	a.pushFront([s,s]);
409 	a.popBack();
410 	a.popFront();
411 	Queue!S b = a;
412 	a.clear();
413 	assert(equal(b[], [s,s,s,s]));
414 }