1 module darray;
2 
3 import std.array : back;
4 
5 import exceptionhandling;
6 
7 struct Payload {
8 	align(8) void* store;
9 	size_t capacity;
10 	long base;
11 	long length;
12 	long refCnt;
13 }
14 
15 struct PayloadHandler {
16 	import core.memory : GC;
17 	static Payload* make() @trusted {
18 		Payload* pl;
19 		pl = cast(Payload*)GC.realloc(pl, typeof(*pl).sizeof);
20 		pl.store = null;
21 		pl.base = 0;
22 		pl.length = 0;
23 		pl.capacity = 0;
24 		pl.refCnt = 1;
25 
26 		return pl;
27 	}
28 
29 	static void allocate(Payload* pl, in size_t s) @trusted {
30 		assert(s != 0);
31 		if(s >= pl.length) {
32 			pl.store = GC.realloc(pl.store, s);
33 			pl.capacity = s;
34 		}
35 	}
36 
37 	static void deallocate(Payload* pl) @trusted {
38 		GC.realloc(pl.store, 0);
39 		pl.capacity = 0;
40 		GC.realloc(pl, 0);
41 	}
42 
43 	static void incrementRefCnt(Payload* pl) {
44 		if(pl !is null) {
45 			++(pl.refCnt);
46 		}
47 	}
48 
49 	static void decrementRefCnt(Payload* pl) {
50 		if(pl !is null) {
51 			--(pl.refCnt);
52 			if(pl.refCnt == 0) {
53 				deallocate(pl);
54 			}
55 		}
56 	}
57 
58 	static Payload* duplicate(Payload* pl) {
59 		Payload* ret = make();	
60 		ret.base = pl.base;
61 		ret.length = pl.length;
62 		allocate(ret, pl.capacity);
63 		size_t len = (*pl).capacity;
64 		ret.store[0 .. len] = pl.store[0 .. len];
65 		decrementRefCnt(pl);
66 		return ret;
67 	}
68 }
69 
70 unittest {
71 	auto pl = PayloadHandler.make();
72 	PayloadHandler.allocate(pl, int.sizeof);
73 	*(cast(int*)(pl.store)) = 1337;
74 	assertEqual(*(cast(int*)(pl.store)), 1337);
75 	PayloadHandler.incrementRefCnt(pl);
76 	auto pl2 = PayloadHandler.duplicate(pl);
77 	assertEqual(*(cast(int*)(pl2.store)), 1337);
78 	PayloadHandler.decrementRefCnt(pl);
79 	PayloadHandler.decrementRefCnt(pl);
80 	PayloadHandler.decrementRefCnt(pl2);
81 }
82 
83 struct DArraySlice(FSA,T) {
84 	FSA* fsa;
85 	short low;
86 	short high;
87 
88 	pragma(inline, true)
89 	this(FSA* fsa, short low, short high) {
90 		this.fsa = fsa;
91 		this.low = low;
92 		this.high = high;
93 	}
94 
95 	pragma(inline, true)
96 	@property bool empty() const pure @safe nothrow @nogc {
97 		return this.low >= this.high;
98 	}
99 
100 	pragma(inline, true)
101 	@property size_t length() pure @safe nothrow @nogc {
102 		return cast(size_t)(this.high - this.low);
103 	}
104 
105 	pragma(inline, true)
106 	@property ref T front() {
107 		return (*this.fsa)[cast(size_t)this.low];
108 	}
109 
110 	pragma(inline, true)
111 	@property ref const(T) front() const {
112 		return (*this.fsa)[cast(size_t)this.low];
113 	}
114 
115 	pragma(inline, true)
116 	@property ref T back() {
117 		return (*this.fsa)[cast(size_t)(this.high - 1)];
118 	}
119 
120 	pragma(inline, true)
121 	@property ref const(T) back() const {
122 		return (*this.fsa)[cast(size_t)(this.high - 1)];
123 	}
124 
125 	pragma(inline, true)
126 	void insertBack(S)(auto ref S s) {
127 		(*this.fsa).insertBack(s);
128 	}
129 
130 	/// Ditto
131 	alias put = insertBack;
132 
133 	pragma(inline, true)
134 	ref T opIndex(const size_t idx) {
135 		return (*this.fsa)[this.low + idx];
136 	}
137 
138 	pragma(inline, true)
139 	void popFront() pure @safe nothrow @nogc {
140 		++this.low;
141 	}
142 
143 	pragma(inline, true)
144 	void popBack() pure @safe nothrow @nogc {
145 		--this.high;
146 	}
147 
148 	pragma(inline, true)
149 	@property typeof(this) save() pure @safe nothrow @nogc {
150 		return this;
151 	}
152 
153 	pragma(inline, true)
154 	@property const(typeof(this)) save() const pure @safe nothrow @nogc {
155 		return this;
156 	}
157 
158 	pragma(inline, true)
159 	typeof(this) opIndex() pure @safe nothrow @nogc {
160 		return this;
161 	}
162 
163 	pragma(inline, true)
164 	typeof(this) opIndex(size_t l, size_t h) pure @safe nothrow @nogc {
165 		return this.opSlice(l, h);
166 	}
167 
168 	pragma(inline, true)
169 	typeof(this) opSlice(size_t l, size_t h) pure @safe nothrow @nogc {
170 		assert(l <= h);
171 		return typeof(this)(this.fsa, 
172 				cast(short)(this.low + l),
173 				cast(short)(this.low + h)
174 			);
175 	}
176 }
177 
178 struct DArray(T) {
179 	import std.traits;
180 
181 	Payload* payload;
182 
183 	/** If `true` no destructor of any element stored in the DArray
184 	  will be called.
185 	*/
186 	bool disableDtor;
187 
188 	enum TSize = SizeToAlloc!T;
189 
190 	this(this) {
191 		if(this.payload !is null) {
192 			PayloadHandler.incrementRefCnt(this.payload);
193 		}
194 	}
195 
196 	template SizeToAlloc(S) {
197 		static if(is(S == class)) {
198 			enum SizeToAlloc = __traits(classInstanceSize, S);
199 		} else {
200 			enum SizeToAlloc = S.sizeof;
201 		}
202 	}
203 
204 	private void checkPayload() {
205 		if(this.payload is null) {
206 			this.payload = PayloadHandler.make();
207 			PayloadHandler.allocate(this.payload, TSize * 16);
208 		} else if(this.payload.refCnt > 1) {
209 			this.payload = PayloadHandler.duplicate(this.payload);
210 		}
211 	}
212 
213 	private void buildCapacity() {
214 		this.checkPayload();
215 		if(this.payload.length + TSize >= this.payload.capacity) {
216 			PayloadHandler.allocate(this.payload, this.payload.capacity * 2);
217 		}
218 	}
219 
220 	pragma(inline, true)
221 	this(Args...)(Args args) {
222 		foreach(it; args) {
223 			static if(isAssignable!(T,typeof(it))) {
224 				this.insertBack(it);
225 			}
226 		}
227 	}
228 
229 	pragma(inline, true)
230 	~this() @trusted {
231 		if(this.payload !is null) { 
232 			if(this.payload.refCnt == 1) {
233 				static if(hasElaborateDestructor!T && !is(T == class)) {
234 					if(!this.disableDtor) {
235 						this.removeAll();
236 					}
237 				}
238 			}
239 			PayloadHandler.decrementRefCnt(this.payload);
240 		}
241 	}
242 
243 	pragma(inline, true)
244 	size_t capacity() const @nogc @safe pure nothrow {
245 		if(this.payload is null) {
246 			return cast(size_t)0;
247 		}
248 		return this.payload.capacity;
249 	}
250 
251 	/** This function inserts an `S` element at the back if there is space.
252 	Otherwise the behaviour is undefined.
253 	*/
254 	pragma(inline, true)
255 	void insertBack(S)(auto ref S t) @trusted if(is(Unqual!(S) == T)) {
256 		this.buildCapacity();
257 
258 		*(cast(T*)(&this.payload.store[
259 			cast(size_t)((this.payload.base + this.payload.length) %
260 				this.payload.capacity)
261 		])) = t;
262 		this.payload.length += TSize;
263 	}
264 
265 	/// Ditto
266 	pragma(inline, true)
267 	void insertBack(S)(auto ref S s) @trusted if(!is(Unqual!(S) == T)) {
268 		import std.traits;
269 		import std.conv;
270 
271 		static if((isIntegral!T || isFloatingPoint!T) 
272 				|| (isSomeChar!T && isSomeChar!S && T.sizeof >= S.sizeof)) 
273 		{
274 			this.insertBack!T(cast(T)(s));
275 		} else static if (isSomeChar!T && isSomeChar!S && T.sizeof < S.sizeof) {
276             /* may throwable operation:
277              * - std.utf.encode
278              */
279             // must do some transcoding around here
280             import std.utf : encode;
281             Unqual!T[T.sizeof == 1 ? 4 : 2] encoded;
282             auto len = encode(encoded, s);
283 			foreach(T it; encoded[0 .. len]) {
284 				 this.insertBack!T(it);
285 			}
286         } else static if(isAssignable!(T,S)) {
287 			this.buildCapacity();
288 			*(cast(T*)(&this.payload.store[
289 				cast(size_t)((this.payload.base + this.payload.length) %
290 					this.payload.capacity)
291 			])) = s;
292 			this.payload.length += TSize;
293 		} else {
294 			static assert(false);
295 		}
296 	}
297 
298 	/// Ditto
299 	pragma(inline, true)
300 	void insertBack(S)(auto ref S defaultValue, size_t num) {
301 		for(size_t i = 0; i < num; ++i) {
302 			this.insertBack(defaultValue);
303 		}
304 	}
305 
306 	///
307 	@safe unittest {
308 		DArray!(int) fsa;
309 		fsa.insertBack(1337);
310 		assert(fsa.length == 1);
311 		assert(fsa[0] == 1337);
312 
313 		fsa.insertBack(99, 5);
314 
315 		foreach(it; fsa[1 .. fsa.length]) {
316 			assert(it == 99);
317 		}
318 	}
319 
320 	/** This function inserts an `S` element at the front if there is space.
321 	Otherwise the behaviour is undefined.
322 	*/
323 	pragma(inline, true)
324 	void insertFront(S)(auto ref S t) @trusted if(is(Unqual!(S) == T)) {
325 		this.buildCapacity();
326 		this.payload.base -= TSize;
327 		if(this.payload.base < 0) {
328 			this.payload.base =
329 				cast(typeof(this.payload.base))((this.payload.capacity) - TSize);
330 		}
331 
332 		*(cast(T*)(&this.payload.store[cast(size_t)this.payload.base])) = t;
333 		this.payload.length += TSize;
334 	}
335 
336 	@safe unittest {
337 		DArray!(int) fsa;
338 		fsa.insertFront(1337);
339 		assert(fsa.length == 1);
340 		assert(fsa[0] == 1337);
341 		assert(fsa.front == 1337);
342 		assert(fsa.back == 1337);
343 
344 		fsa.removeBack();
345 		assert(fsa.length == 0);
346 		assert(fsa.empty);
347 		fsa.insertFront(1336);
348 
349 		assert(fsa.length == 1);
350 		assert(fsa[0] == 1336);
351 		assert(fsa.front == 1336);
352 		assert(fsa.back == 1336);
353 	}
354 
355 	@safe unittest {
356 		DArray!(int) fsa;
357 		for(int i = 0; i < 32; ++i) {
358 			fsa.insertFront(i);
359 			assert(fsa.length == 1);
360 			assert(!fsa.empty);
361 			assert(fsa.front == i);
362 			assert(fsa.back == i);
363 			fsa.removeFront();
364 			assert(fsa.length == 0);
365 			assert(fsa.empty);
366 		}
367 	}
368 
369 	@safe unittest {
370 		DArray!(int) fsa;
371 		for(int i = 0; i < 32; ++i) {
372 			fsa.insertFront(i);
373 			assert(fsa.length == 1);
374 			assert(!fsa.empty);
375 			assert(fsa.front == i);
376 			assert(fsa.back == i);
377 			fsa.removeBack();
378 			assert(fsa.length == 0);
379 			assert(fsa.empty);
380 		}
381 	}
382 
383 	@safe unittest {
384 		DArray!(int) fsa;
385 		for(int i = 0; i < 32; ++i) {
386 			fsa.insertBack(i);
387 			assert(fsa.length == 1);
388 			assert(!fsa.empty);
389 			assert(fsa.front == i);
390 			assert(fsa.back == i);
391 			fsa.removeFront();
392 			assert(fsa.length == 0);
393 			assert(fsa.empty);
394 		}
395 	}
396 
397 	/** This function removes an element form the back of the array.
398 	*/
399 	pragma(inline, true)
400 	void removeBack() {
401 		assert(!this.empty);
402 
403 		static if(hasElaborateDestructor!T) {
404 			if(!this.disableDtor) {
405 				static if(hasMember!(T, "__dtor")) {
406 					this.back().__dtor();
407 				} else static if(hasMember!(T, "__xdtor")) {
408 					this.back().__xdtor();
409 				} else {
410 					static assert(false);
411 				}
412 			}
413 		}
414 
415 		this.payload.length -= TSize;
416 	}
417 
418 	/** This function removes an element form the front of the array.
419 	*/
420 	pragma(inline, true)
421 	void removeFront() {
422 		assert(!this.empty);
423 
424 		static if(hasElaborateDestructor!T) {
425 			if(!this.disableDtor) {
426 				static if(hasMember!(T, "__dtor")) {
427 					this.back().__dtor();
428 				} else static if(hasMember!(T, "__xdtor")) {
429 					this.back().__xdtor();
430 				} else {
431 					static assert(false);
432 				}
433 			}
434 		}
435 
436 		//this.begin = (this.begin + T.sizeof) % (Size * T.sizeof);
437 		this.payload.base += TSize;
438 		if(this.payload.base >= this.payload.capacity) {
439 			this.payload.base = 0;
440 		}
441 		this.payload.length -= TSize;
442 	}
443 
444 	@safe unittest {
445 		DArray!(int) fsa;
446 		fsa.insertBack(1337);
447 		assert(fsa.length == 1);
448 		assert(fsa[0] == 1337);
449 		
450 		fsa.removeBack();
451 		assert(fsa.length == 0);
452 		assert(fsa.empty);
453 	}
454 
455 	/** This function removes all elements from the array.
456 	*/
457 	pragma(inline, true)
458 	void removeAll() {
459 		while(!this.empty) {
460 			this.removeBack();
461 		}
462 	}
463 
464 	@safe unittest {
465 		DArray!(int) fsa;
466 		fsa.insertBack(1337);
467 		fsa.insertBack(1338);
468 		assert(fsa.length == 2);
469 		assert(fsa[0] == 1337);
470 		assert(fsa[1] == 1338);
471 		
472 		fsa.removeAll();
473 		assert(fsa.length == 0);
474 		assert(fsa.empty);
475 	}
476 
477 	pragma(inline, true)
478 	void remove(ulong idx) {
479 		import std.stdio;
480 		if(idx == 0) {
481 			this.removeFront();
482 		} else if(idx == this.length - 1) {
483 			this.removeBack();
484 		} else {
485 			for(long i = idx + 1; i < this.length; ++i) {
486 				this[cast(size_t)(i - 1)] = this[cast(size_t)i];
487 			}
488 			this.removeBack();
489 		}
490 	}
491 
492 	unittest {
493 		DArray!(int) fsa;
494 		foreach(i; 0..10) {
495 			fsa.insertBack(i);
496 		}
497 		fsa.remove(1);
498 		foreach(idx, i; [0,2,3,4,5,6,7,8,9]) {
499 			assert(fsa[idx] == i);
500 		}
501 		fsa.remove(0);
502 		foreach(idx, i; [2,3,4,5,6,7,8,9]) {
503 			assert(fsa[idx] == i);
504 		}
505 		fsa.remove(7);
506 		foreach(idx, i; [2,3,4,5,6,7,8]) {
507 			assert(fsa[idx] == i);
508 		}
509 		fsa.remove(5);
510 		foreach(idx, i; [2,3,4,5,6,8]) {
511 			assert(fsa[idx] == i);
512 		}
513 		fsa.remove(1);
514 		foreach(idx, i; [2,4,5,6,8]) {
515 			assert(fsa[idx] == i);
516 		}
517 		fsa.remove(0);
518 		foreach(idx, i; [4,5,6,8]) {
519 			assert(fsa[idx] == i);
520 		}
521 		fsa.remove(0);
522 		foreach(idx, i; [5,6,8]) {
523 			assert(fsa[idx] == i);
524 		}
525 	}
526 
527 	/** Access the last or the first element of the array.
528 	*/
529 	pragma(inline, true)
530 	@property ref T back() @trusted {
531 		ensure(this.payload !is null);
532 		return *(cast(T*)(&this.payload.store[
533 			cast(size_t)(this.payload.base + this.payload.length - TSize) 
534 				% this.payload.capacity
535 		]));
536 	}
537 
538 	pragma(inline, true)
539 	@property ref const(T) back() const @trusted {
540 		ensure(this.payload !is null);
541 		return *(cast(T*)(&this.payload.store[
542 			cast(size_t)(this.payload.base + this.payload.length - TSize) 
543 				% this.payload.capacity
544 		]));
545 	}
546 
547 	/// Ditto
548 	pragma(inline, true)
549 	@property ref T front() @trusted {
550 		ensure(this.payload !is null);
551 		return *(cast(T*)(&this.payload.store[cast(size_t)this.payload.base]));
552 	}
553 
554 	pragma(inline, true)
555 	@property ref const(T) front() const @trusted {
556 		ensure(this.payload !is null);
557 		return *(cast(T*)(&this.payload.store[cast(size_t)this.payload.base]));
558 	}
559 
560 	///
561 	@safe unittest {
562 		DArray!(int) fsa;
563 		assertEqual(fsa.capacity, 0);
564 		fsa.insertBack(1337);
565 		fsa.insertBack(1338);
566 		assert(fsa.capacity > 0);
567 		assert(fsa.length == 2);
568 
569 		assert(fsa.front == 1337);
570 		assert(fsa.back == 1338);
571 
572 		void f(ref const(DArray!int) d) {
573 			assert(d.front == 1337);
574 			assert(d.back == 1338);
575 		}
576 
577 		f(fsa);
578 	}
579 
580 	/** Use an index to access the array.
581 	*/
582 	pragma(inline, true)
583 	ref T opIndex(const size_t idx) @trusted {
584 		ensure(idx <= this.length);
585 		return *(cast(T*)(&this.payload.store[
586 				cast(size_t)((this.payload.base + idx * TSize) %
587 					this.payload.capacity)
588 		]));
589 	}
590 
591 	/// Ditto
592 	pragma(inline, true)
593 	ref const(T) opIndex(const size_t idx) @trusted const {
594 		ensure(idx <= this.length);
595 		return *(cast(T*)(&this.payload.store[
596 				cast(size_t)((this.payload.base + idx * TSize) %
597 					this.payload.capacity)
598 		]));
599 	}
600 
601 	///
602 	@safe unittest {
603 		DArray!(int) fsa;
604 		fsa.insertBack(1337);
605 		fsa.insertBack(1338);
606 		assert(fsa.length == 2);
607 
608 		assert(fsa[0] == 1337);
609 		assert(fsa[1] == 1338);
610 
611 		void f(ref const(DArray!int) d) {
612 			assert(d[0] == 1337);
613 			assert(d[1] == 1338);
614 		}
615 
616 		f(fsa);
617 	}
618 
619 	/// Gives the length of the array.
620 	pragma(inline, true)
621 	@property size_t length() const pure @nogc nothrow {
622 		if(this.payload is null) {
623 			return cast(size_t)0;
624 		}
625 		return cast(size_t)(this.payload.length / SizeToAlloc!T);
626 	}
627 
628 	/// Ditto
629 	pragma(inline, true)
630 	@property bool empty() const pure @nogc nothrow {
631 		return this.length == 0;
632 	}
633 
634 	///
635 	@safe unittest {
636 		DArray!(int) fsa;
637 		assert(fsa.empty);
638 		assert(fsa.length == 0);
639 
640 		fsa.insertBack(1337);
641 		fsa.insertBack(1338);
642 
643 		assert(fsa.length == 2);
644 		assert(!fsa.empty);
645 	}
646 
647 	pragma(inline, true)
648 	DArraySlice!(typeof(this),T) opSlice() pure @nogc @safe nothrow {
649 		return DArraySlice!(typeof(this),T)(&this, cast(short)0, 
650 				cast(short)this.length
651 		);
652 	}
653 	
654 	pragma(inline, true)
655 	DArraySlice!(typeof(this),T) opSlice(const size_t low, 
656 			const size_t high) 
657 			pure @nogc @safe nothrow 
658 	{
659 		return DArraySlice!(typeof(this),T)(&this, cast(short)low, 
660 				cast(short)high
661 		);
662 	}
663 
664 	pragma(inline, true)
665 	auto opSlice() pure @nogc @safe nothrow const {
666 		return DArraySlice!(typeof(this),const(T))
667 			(&this, cast(short)0, cast(short)this.length);
668 	}
669 	
670 	pragma(inline, true)
671 	auto opSlice(const size_t low, const size_t high) pure @nogc @safe nothrow const 
672 	{
673 		return DArraySlice!(typeof(this),const(T))
674 			(&this, cast(short)low, cast(short)high);
675 	}
676 }
677 
678 unittest {
679 	DArray!int d;
680 	assertEqual(d.length, 0);
681 	assert(d.empty);
682 
683 	for(int i = 0; i < 20; ++i) {
684 		d.insertBack(i);
685 		assertEqual(d.length, i+1);
686 	}
687 	assertEqual(d.length, 20);
688 
689 	DArray!int d2 = d;
690 	assertEqual(d.length, 20);
691 	assertEqual(d2.length, 20);
692 
693 	d2.insertBack(21);
694 	assertEqual(d.length, 20);
695 	assertEqual(d2.length, 21);
696 }
697 
698 unittest {
699 	import exceptionhandling;
700 	import std.stdio;
701 
702 	DArray!(int) fsa;
703 	assert(fsa.empty);
704 	cast(void)assertEqual(fsa.length, 0);
705 
706 	fsa.insertBack(1);
707 	assert(!fsa.empty);
708 	cast(void)assertEqual(fsa.length, 1);
709 	cast(void)assertEqual(fsa.front, 1);
710 	cast(void)assertEqual(fsa.back, 1);
711 
712 	fsa.insertBack(2);
713 	assert(!fsa.empty);
714 	cast(void)assertEqual(fsa.length, 2);
715 	cast(void)assertEqual(fsa.front, 1);
716 	cast(void)assertEqual(fsa.back, 2);
717 
718 	fsa.removeFront();
719 	assert(!fsa.empty);
720 	cast(void)assertEqual(fsa.length, 1);
721 	cast(void)assertEqual(fsa.front, 2);
722 	cast(void)assertEqual(fsa.back, 2);
723 
724 	fsa.removeBack();
725 	//writefln("%s %s", fsa.begin, fsa.end);
726 	assert(fsa.empty);
727 	cast(void)assertEqual(fsa.length, 0);
728 }
729 
730 unittest {
731 	import std.format;
732 
733 	DArray!(char) fsa;
734 	formattedWrite(fsa[], "%s %s %s", "Hello", "World", 42);
735 	//assert(cast(string)fsa == "Hello World 42", cast(string)fsa);
736 }
737 
738 unittest {
739 	import exceptionhandling;
740 
741 	DArray!(int) fsa;
742 	auto a = [0,1,2,4,32,64,1024,2048,65000];
743 	foreach(idx, it; a) {
744 		fsa.insertBack(it);
745 		assertEqual(fsa.length, idx + 1);
746 		assertEqual(fsa.back, it);
747 		for(int i = 0; i < idx; ++i) {
748 			assertEqual(fsa[i], a[i]);
749 		}
750 	}
751 }
752 
753 unittest {
754 	import exceptionhandling;
755 	import std.traits;
756 	import std.meta;
757 	import std.range;
758 	import std.stdio;
759 	foreach(Type; AliasSeq!(byte,int,long)) {
760 		DArray!(Type) fsa2;
761 		static assert(isInputRange!(typeof(fsa2[])));
762 		static assert(isForwardRange!(typeof(fsa2[])));
763 		static assert(isBidirectionalRange!(typeof(fsa2[])));
764 		foreach(idx, it; [[0], [0,1,2,3,4], [2,3,6,5,6,21,9,36,61,62]]) {
765 			DArray!(Type) fsa;
766 			foreach(jdx, jt; it) {
767 				fsa.insertBack(jt);
768 				//writefln("%s idx %d jdx %d length %d", Type.stringof, idx, jdx, fsa.length);
769 				cast(void)assertEqual(fsa.length, jdx + 1);
770 				foreach(kdx, kt; it[0 .. jdx]) {
771 					assertEqual(fsa[kdx], kt);
772 				}
773 
774 				{
775 					auto forward = fsa[];
776 					auto forward2 = forward;
777 					cast(void)assertEqual(forward.length, jdx + 1);
778 					for(size_t i = 0; i < forward.length; ++i) {
779 						cast(void)assertEqual(forward[i], it[i]);
780 						cast(void)assertEqual(forward2.front, it[i]);
781 						forward2.popFront();
782 					}
783 					assert(forward2.empty);
784 
785 					auto backward = fsa[];
786 					auto backward2 = backward.save;
787 					cast(void)assertEqual(backward.length, jdx + 1);
788 					for(size_t i = 0; i < backward.length; ++i) {
789 						cast(void)assertEqual(backward[backward.length - i - 1],
790 								it[jdx - i]
791 						);
792 
793 						cast(void)assertEqual(backward2.back, 
794 								it[0 .. jdx + 1 - i].back
795 						);
796 						backward2.popBack();
797 					}
798 					assert(backward2.empty);
799 					auto forward3 = fsa[].save;
800 					auto forward4 = fsa[0 .. jdx + 1];
801 
802 					while(!forward3.empty && !forward4.empty) {
803 						cast(void)assertEqual(forward3.front, forward4.front);
804 						cast(void)assertEqual(forward3.back, forward4.back);
805 						forward3.popFront();
806 						forward4.popFront();
807 					}
808 					assert(forward3.empty);
809 					assert(forward4.empty);
810 				}
811 
812 				{
813 					const(DArray!(Type))* constFsa;
814 					constFsa = &fsa;
815 					auto forward = (*constFsa)[];
816 					auto forward2 = forward.save;
817 					cast(void)assertEqual(forward.length, jdx + 1);
818 					for(size_t i = 0; i < forward.length; ++i) {
819 						cast(void)assertEqual(cast(int)forward[i], it[i]);
820 						cast(void)assertEqual(cast(int)forward2.front, it[i]);
821 						forward2.popFront();
822 					}
823 					assert(forward2.empty);
824 
825 					auto backward = (*constFsa)[];
826 					auto backward2 = backward.save;
827 					cast(void)assertEqual(backward.length, jdx + 1);
828 					for(size_t i = 0; i < backward.length; ++i) {
829 						cast(void)assertEqual(backward[backward.length - i - 1],
830 								it[jdx - i]
831 						);
832 
833 						cast(void)assertEqual(backward2.back, 
834 								it[0 .. jdx + 1 - i].back
835 						);
836 						backward2.popBack();
837 					}
838 					assert(backward2.empty);
839 					auto forward3 = (*constFsa)[];
840 					auto forward4 = (*constFsa)[0 .. jdx + 1];
841 
842 					while(!forward3.empty && !forward4.empty) {
843 						cast(void)assertEqual(forward3.front, forward4.front);
844 						cast(void)assertEqual(forward3.back, forward4.back);
845 						forward3.popFront();
846 						forward4.popFront();
847 					}
848 					assert(forward3.empty);
849 					assert(forward4.empty);
850 				}
851 			}
852 		}
853 	}
854 }
855 
856 unittest {
857 	import exceptionhandling;
858 
859 	int cnt;
860 
861 	struct Foo {
862 		int* cnt;
863 		this(int* cnt) { this.cnt = cnt; }
864 		~this() { if(cnt) { 
865 			++(*cnt); 
866 		} }
867 	}
868 
869 	int i = 0;
870 	for(; i < 1000; ++i) {
871 		{
872 			DArray!(Foo) fsa;
873 			fsa.insertBack(Foo(&cnt));
874 			fsa.insertBack(Foo(&cnt));
875 			fsa.insertBack(Foo(&cnt));
876 			fsa.insertBack(Foo(&cnt));
877 		}
878 
879 		assert(cnt > i * 4);
880 	}
881 }
882 
883 // Test case Issue #2
884 unittest {
885 	import exceptionhandling;
886 
887 	DArray!(int) fsa;
888 	fsa.insertBack(0);
889 	fsa.insertBack(1);
890 
891 	assertEqual(fsa[0], 0);	
892 	assertEqual(fsa[1], 1);	
893 	assertEqual(fsa.front, 0);
894 	assertEqual(fsa.back, 1);
895 }
896 
897 unittest {
898 	import exceptionhandling;
899 	import std.stdio;
900 	string s = "Hellö Wärlß";
901 	{
902 		DArray!(char) fsa;
903 		foreach(dchar c; s) {
904 			fsa.insertBack(c);
905 		}
906 		for(int i = 0; i < s.length; ++i) {
907 			assert(fsa[i] == s[i]);
908 		}
909 	}
910 	{
911 		import std.format;
912 		DArray!(char) fsa;
913 		formattedWrite(fsa[], s);
914 		for(int i = 0; i < s.length; ++i) {
915 			assert(fsa[i] == s[i]);
916 		}
917 	}
918 }
919 
920 unittest {
921 	import std.stdio;
922 	import core.memory;
923 	enum size = 128;
924 	//auto arrays = new DArray!(int)[size];
925 	DArray!(int)[size] arrays;
926 	//GC.removeRoot(arrays.ptr);
927 	//DArray!(int, size)[size] arrays;
928 	foreach (i; 0..size) {
929 	    foreach (j; 0..size) {
930 			assert(arrays[i].length == j);
931 	        arrays[i].insertBack(i * 1000 + j);
932 	    }
933 	}
934 	/*foreach(ref it; arrays) {
935 		writef("%d ", it.length);
936 	}
937 	writeln();*/
938 	bool[int] o;
939 	foreach (i; 0..size) {
940 	    foreach (j; 0..size) {
941 			assert(arrays[i][j] !in o);
942 	        o[arrays[i][j]] = true;
943 	    }
944 	}
945 	assert(size * size == o.length);
946 }
947 
948 // issue #1 won't fix not sure why
949 unittest {
950 	import std.stdio;
951 	import core.memory;
952 	enum size = 256;
953 	DArray!(Object) arrays;
954 	foreach (i; 0..size) {
955 		auto o = new Object();
956 		assert(arrays.length == i);
957 		foreach(it; arrays[]) {
958 			assert(it !is null);
959 			assert(it.toHash());
960 		}
961 	    arrays.insertBack(o);
962 		assert(arrays.back is o);
963 		assert(!arrays.empty);
964 		assert(arrays.length == i + 1);
965 	}
966 
967 	assert(arrays.length == size);
968 	for(int i = 0; i < size; ++i) {
969 		assert(arrays[i] !is null);
970 		assert(arrays[i].toHash());
971 	}
972 	bool[Object] o;
973 	foreach (i; 0..size) {
974 		assert(arrays[i] !is null);
975 		assert(arrays[i] !in o);
976 	    o[arrays[i]] = true;
977 	    
978 	}
979 	assert(size == o.length);
980 }
981 
982 unittest {
983 	import exceptionhandling;
984 	DArray!(int) fsa;
985 	fsa.insertFront(1337);
986 	assert(!fsa.empty);
987 	assertEqual(fsa.length, 1);
988 	assertEqual(fsa.back, 1337);
989 	assertEqual(fsa.front, 1337);
990 	assertEqual(fsa.payload.base, 15 * int.sizeof);
991 }
992 
993 // Test case Issue #2
994 unittest {
995 	enum size = 256;
996 	//auto arrays = new DArray!(Object)[size];
997 	DArray!(Object)[size] arrays;
998 	foreach (i; 0..size) {
999 	    foreach (j; 0..size) {
1000 	        arrays[i].insertBack(new Object);
1001 	    }
1002 	}
1003 	bool[Object] o;
1004 	foreach (i; 0..size) {
1005 	    foreach (j; 0..size) {
1006 	        o[arrays[i][j]] = true;
1007 	    }
1008 	}
1009 	assert(o.length == size * size);
1010 }
1011 
1012 unittest {
1013 	import exceptionhandling;
1014 	struct Foo {
1015 		int* a;
1016 		this(int* a) {
1017 			this.a = a;
1018 		}
1019 		~this() {
1020 			if(this.a !is null) {
1021 				++(*a);
1022 			}
1023 		}
1024 	}
1025 
1026 	{
1027 		int a = 0;
1028 		{
1029 			DArray!(Foo) fsa;
1030 			for(int i = 0; i < 10; ++i) {
1031 				fsa.insertBack(Foo(&a));
1032 			}
1033 		}
1034 		assertEqual(a, 20);
1035 	}
1036 	{
1037 		int a = 0;
1038 		{
1039 			DArray!(Foo) fsa;
1040 			fsa.disableDtor = true;
1041 			for(int i = 0; i < 10; ++i) {
1042 				fsa.insertBack(Foo(&a));
1043 			}
1044 		}
1045 		assertEqual(a, 10);
1046 	}
1047 }
1048 
1049 unittest {
1050 	import std.range.primitives : hasAssignableElements, hasSlicing, isRandomAccessRange;
1051 	DArray!(int) fsa;
1052 	auto s = fsa[];
1053 	static assert(hasSlicing!(typeof(s)));
1054 	static assert(isRandomAccessRange!(typeof(s)));
1055 	static assert(hasAssignableElements!(typeof(s)));
1056 }
1057 
1058 unittest {
1059 	import exceptionhandling;
1060 
1061 	DArray!(int) fsa;
1062 	for(int i = 0; i < 32; ++i) {
1063 		fsa.insertBack(i);	
1064 	}
1065 
1066 	auto s = fsa[];
1067 	for(int i = 0; i < 32; ++i) {
1068 		assert(s[i] == i);
1069 	}
1070 	s = s[0 .. 33];
1071 	for(int i = 0; i < 32; ++i) {
1072 		assert(s[i] == i);
1073 	}
1074 
1075 	auto t = s.save;
1076 	s.popFront();
1077 	for(int i = 0; i < 32; ++i) {
1078 		assert(t[i] == i);
1079 	}
1080 
1081 	auto r = t[10, 20];
1082 	for(int i = 10; i < 20; ++i) {
1083 		assertEqual(r[i-10], fsa[i]);
1084 	}
1085 
1086 	foreach(ref it; r) {
1087 		it = 0;
1088 	}
1089 
1090 	for(int i = 10; i < 20; ++i) {
1091 		assertEqual(r[i-10], 0);
1092 	}
1093 }
1094 
1095 unittest {
1096 	DArray!(int) fsaM;
1097 	for(int i = 0; i < 32; ++i) {
1098 		fsaM.insertBack(i);	
1099 	}
1100 
1101 	const(DArray!(int)) fsa = fsaM;
1102 
1103 	auto s = fsa[];
1104 	for(int i = 0; i < 32; ++i) {
1105 		assert(s[i] == i);
1106 	}
1107 	s = s[0 .. 33];
1108 	for(int i = 0; i < 32; ++i) {
1109 		assert(s[i] == i);
1110 	}
1111 
1112 	auto t = s.save;
1113 	s.popFront();
1114 	for(int i = 0; i < 32; ++i) {
1115 		assert(t[i] == i);
1116 	}
1117 }
1118 
1119 unittest {
1120 	import std.random : Random, uniform;
1121 	import std.format : format;
1122 	struct Data {
1123 		ulong a, b, c, d, e;
1124 	}
1125 
1126 	auto rnd = Random(1337);
1127 	DArray!(Data) a;
1128 	for(size_t i = 0; i < 4096; ++i) {
1129 		Data d;
1130 		d.a = i;
1131 		d.b = i;
1132 		d.c = i;
1133 		d.d = i;
1134 		d.e = i;
1135 
1136 		a.insertBack(d);
1137 
1138 		int c = uniform(4,10, rnd);
1139 		while(a.length > c) {
1140 			a.removeFront();
1141 		}
1142 		assert(!a.empty);
1143 		assert(a.length <= c, format("%d < %d", a.length, c));
1144 
1145 		auto r = a[];
1146 		assert(r.back.a == i);
1147 		assert(r.front.a <= i);
1148 
1149 		foreach(it; r[]) {
1150 			assert(it.a <= i);
1151 		}
1152 
1153 		auto cr = (*(cast(const(typeof(a))*)(&a)));
1154 		assert(cr.back.a == i);
1155 		assert(cr.front.a <= i);
1156 
1157 		auto crr = cr[];
1158 		assert(crr.front.a <= i);
1159 		assert(crr.back.a <= i);
1160 		foreach(it; crr.save) {
1161 			assert(it.a <= i);
1162 		}
1163 	}
1164 }