1 /* This Source Code Form is subject to the terms of the Mozilla Public
2 * License, v. 2.0. If a copy of the MPL was not distributed with this
3 * file, You can obtain one at http://mozilla.org/MPL/2.0/. */
4
5 /**
6 * Single-dimensioned array.
7 *
8 * Copyright: Eugene Wissner 2016-2021.
9 * License: $(LINK2 https://www.mozilla.org/en-US/MPL/2.0/,
10 * Mozilla Public License, v. 2.0).
11 * Authors: $(LINK2 mailto:info@caraus.de, Eugene Wissner)
12 * Source: $(LINK2 https://github.com/caraus-ecms/tanya/blob/master/source/tanya/container/array.d,
13 * tanya/container/array.d)
14 */
15 module tanya.container.array;
16
17 import core.checkedint;
18 import std.algorithm.comparison;
19 import std.algorithm.iteration;
20 import std.algorithm.mutation : bringToFront;
21 import tanya.algorithm.mutation;
22 import tanya.memory.allocator;
23 import tanya.memory.lifetime;
24 import tanya.meta.trait;
25 import tanya.meta.transform;
26 import tanya.range;
27
28 /**
29 * Random-access range for the $(D_PSYMBOL Array).
30 *
31 * Params:
32 * A = Array type.
33 */
34 struct Range(A)
35 {
36 private alias E = PointerTarget!(typeof(A.data));
37 private E* begin, end;
38 private A* container;
39
40 invariant
41 {
42 assert(this.begin <= this.end);
43 assert(this.container !is null);
44 assert(this.begin >= this.container.data);
45 assert(this.end <= this.container.data + this.container.length);
46 }
47
48 private this(return ref A container, return E* begin, return E* end)
49 @trusted
50 in
51 {
52 assert(begin <= end);
53 assert(begin >= container.data);
54 assert(end <= container.data + container.length);
55 }
56 do
57 {
58 this.container = &container;
59 this.begin = begin;
60 this.end = end;
61 }
62
63 @disable this();
64
65 @property Range save()
66 {
67 return this;
68 }
69
70 @property bool empty() const
71 {
72 return this.begin == this.end;
73 }
74
75 @property size_t length() const
76 {
77 return this.end - this.begin;
78 }
79
80 alias opDollar = length;
81
82 @property ref inout(E) front() inout
83 in
84 {
85 assert(!empty);
86 }
87 do
88 {
89 return *this.begin;
90 }
91
92 @property ref inout(E) back() inout @trusted
93 in
94 {
95 assert(!empty);
96 }
97 do
98 {
99 return *(this.end - 1);
100 }
101
102 void popFront() @trusted
103 in
104 {
105 assert(!empty);
106 }
107 do
108 {
109 ++this.begin;
110 }
111
112 void popBack() @trusted
113 in
114 {
115 assert(!empty);
116 }
117 do
118 {
119 --this.end;
120 }
121
122 ref inout(E) opIndex(size_t i) inout @trusted
123 in
124 {
125 assert(i < length);
126 }
127 do
128 {
129 return *(this.begin + i);
130 }
131
132 Range opIndex()
133 {
134 return typeof(return)(*this.container, this.begin, this.end);
135 }
136
137 A.ConstRange opIndex() const
138 {
139 return typeof(return)(*this.container, this.begin, this.end);
140 }
141
142 Range opSlice(size_t i, size_t j) @trusted
143 in
144 {
145 assert(i <= j);
146 assert(j <= length);
147 }
148 do
149 {
150 return typeof(return)(*this.container, this.begin + i, this.begin + j);
151 }
152
153 A.ConstRange opSlice(size_t i, size_t j) const @trusted
154 in
155 {
156 assert(i <= j);
157 assert(j <= length);
158 }
159 do
160 {
161 return typeof(return)(*this.container, this.begin + i, this.begin + j);
162 }
163
164 inout(E)[] get() inout
165 {
166 return this.begin[0 .. length];
167 }
168 }
169
170 /**
171 * One dimensional array.
172 *
173 * Params:
174 * T = Content type.
175 */
176 struct Array(T)
177 {
178 /// The range types for $(D_PSYMBOL Array).
179 alias Range = .Range!Array;
180
181 /// ditto
182 alias ConstRange = .Range!(const Array);
183
184 private size_t length_;
185 private T* data;
186 private size_t capacity_;
187
188 invariant
189 {
190 assert(this.length_ <= this.capacity_);
191 assert(this.capacity_ == 0 || this.data !is null);
192 }
193
194 /**
195 * Creates a new $(D_PSYMBOL Array) with the elements from a static array.
196 *
197 * Params:
198 * R = Static array size.
199 * init = Values to initialize the array with.
200 * allocator = Allocator.
201 */
202 this(size_t R)(T[R] init, shared Allocator allocator = defaultAllocator)
203 {
204 this(allocator);
205 insertBack!(T[])(init[]);
206 }
207
208 /**
209 * Creates a new $(D_PSYMBOL Array) with the elements from an input range.
210 *
211 * Params:
212 * R = Type of the initial range.
213 * init = Values to initialize the array with.
214 * allocator = Allocator.
215 */
216 this(R)(scope R init, shared Allocator allocator = defaultAllocator)
217 if (!isInfinite!R
218 && isInputRange!R
219 && isImplicitlyConvertible!(ElementType!R, T))
220 {
221 this(allocator);
222 insertBack(init);
223 }
224
225 /**
226 * Initializes this array from another one.
227 *
228 * If $(D_PARAM init) is passed by value, it won't be copied, but moved.
229 * If the allocator of ($D_PARAM init) matches $(D_PARAM allocator),
230 * $(D_KEYWORD this) will just take the ownership over $(D_PARAM init)'s
231 * storage, otherwise, the storage will be allocated with
232 * $(D_PARAM allocator) and all elements will be moved;
233 * $(D_PARAM init) will be destroyed at the end.
234 *
235 * If $(D_PARAM init) is passed by reference, it will be copied.
236 *
237 * Params:
238 * R = Source array type.
239 * init = Source array.
240 * allocator = Allocator.
241 */
242 this(R)(ref R init, shared Allocator allocator = defaultAllocator)
243 if (is(Unqual!R == Array))
244 {
245 this(allocator);
246 insertBack(init[]);
247 }
248
249 /// ditto
250 this(R)(R init, shared Allocator allocator = defaultAllocator) @trusted
251 if (is(R == Array))
252 {
253 this(allocator);
254 if (allocator is init.allocator)
255 {
256 // Just steal all references and the allocator.
257 this.data = init.data;
258 this.length_ = init.length_;
259 this.capacity_ = init.capacity_;
260
261 // Reset the source array, so it can't destroy the moved storage.
262 init.length_ = init.capacity_ = 0;
263 init.data = null;
264 }
265 else
266 {
267 // Move each element.
268 reserve(init.length_);
269 foreach (ref target; slice(init.length_))
270 {
271 moveEmplace(*init.data++, target);
272 }
273 this.length_ = init.length_;
274 // Destructor of init should destroy it here.
275 }
276 }
277
278 ///
279 @nogc nothrow pure @safe unittest
280 {
281 auto v1 = Array!int([1, 2, 3]);
282 auto v2 = Array!int(v1);
283 assert(v1 == v2);
284
285 auto v3 = Array!int(Array!int([1, 2, 3]));
286 assert(v1 == v3);
287 assert(v3.length == 3);
288 assert(v3.capacity == 3);
289 }
290
291 /**
292 * Creates a new $(D_PSYMBOL Array).
293 *
294 * Params:
295 * len = Initial length of the array.
296 * init = Initial value to fill the array with.
297 * allocator = Allocator.
298 */
299 this()(size_t len,
300 auto ref T init,
301 shared Allocator allocator = defaultAllocator)
302 {
303 this(allocator);
304 reserve(len);
305 uninitializedFill(slice(len), init);
306 length_ = len;
307 }
308
309 /// ditto
310 this(size_t len, shared Allocator allocator = defaultAllocator)
311 {
312 this(allocator);
313 length = len;
314 }
315
316 /// ditto
317 this(shared Allocator allocator)
318 in
319 {
320 assert(allocator !is null);
321 }
322 do
323 {
324 allocator_ = allocator;
325 }
326
327 ///
328 @nogc nothrow pure @safe unittest
329 {
330 auto v = Array!int([3, 8, 2]);
331
332 assert(v.capacity == 3);
333 assert(v.length == 3);
334 assert(v[0] == 3 && v[1] == 8 && v[2] == 2);
335 }
336
337 ///
338 @nogc nothrow pure @safe unittest
339 {
340 auto v = Array!int(3, 5);
341
342 assert(v.capacity == 3);
343 assert(v.length == 3);
344 assert(v[0] == 5 && v[1] == 5 && v[2] == 5);
345 }
346
347 /**
348 * Destroys this $(D_PSYMBOL Array).
349 */
350 ~this()
351 {
352 destroyAll(slice(this.length_));
353 deallocate();
354 }
355
356 private void deallocate() @trusted
357 {
358 allocator.deallocate(slice(capacity));
359 }
360
361 static if (isCopyable!T)
362 {
363 this(this)
364 {
365 auto buf = slice(this.length);
366 this.length_ = capacity_ = 0;
367 this.data = null;
368 insertBack(buf);
369 }
370 }
371 else
372 {
373 @disable this(this);
374 }
375
376 /**
377 * Removes all elements.
378 */
379 void clear()
380 {
381 length = 0;
382 }
383
384 ///
385 @nogc nothrow pure @safe unittest
386 {
387 auto v = Array!int([18, 20, 15]);
388 v.clear();
389 assert(v.length == 0);
390 assert(v.capacity == 3);
391 }
392
393 /**
394 * Returns: How many elements the array can contain without reallocating.
395 */
396 @property size_t capacity() const
397 {
398 return capacity_;
399 }
400
401 ///
402 @nogc nothrow pure @safe unittest
403 {
404 auto v = Array!int(4);
405 assert(v.capacity == 4);
406 }
407
408 /**
409 * Returns: Array length.
410 */
411 @property size_t length() const
412 {
413 return length_;
414 }
415
416 /// ditto
417 size_t opDollar() const
418 {
419 return length;
420 }
421
422 /**
423 * Expands/shrinks the array.
424 *
425 * Params:
426 * len = New length.
427 */
428 @property void length(size_t len) @trusted
429 {
430 if (len > length)
431 {
432 reserve(len);
433 initializeAll(this.data[length_ .. len]);
434 }
435 else
436 {
437 destroyAll(this.data[len .. this.length_]);
438 }
439 if (len != length)
440 {
441 length_ = len;
442 }
443 }
444
445 ///
446 @nogc nothrow pure @safe unittest
447 {
448 Array!int v;
449
450 v.length = 5;
451 assert(v.length == 5);
452 assert(v.capacity == 5);
453
454 v.length = 7;
455 assert(v.length == 7);
456 assert(v.capacity == 7);
457
458 assert(v[$ - 1] == 0);
459 v[$ - 1] = 3;
460 assert(v[$ - 1] == 3);
461
462 v.length = 0;
463 assert(v.length == 0);
464 assert(v.capacity == 7);
465 }
466
467 /**
468 * Reserves space for $(D_PARAM size) elements.
469 *
470 * If $(D_PARAM size) is less than or equal to the $(D_PSYMBOL capacity), the
471 * function call does not cause a reallocation and the array capacity is not
472 * affected.
473 *
474 * Params:
475 * size = Desired size.
476 */
477 void reserve(size_t size) @trusted
478 {
479 if (capacity_ >= size)
480 {
481 return;
482 }
483 bool overflow;
484 const byteSize = mulu(size, T.sizeof, overflow);
485 assert(!overflow);
486
487 void[] buf = this.data[0 .. this.capacity_];
488 if (!allocator.reallocateInPlace(buf, byteSize))
489 {
490 buf = allocator.allocate(byteSize);
491 if (buf is null)
492 {
493 onOutOfMemoryError();
494 }
495 scope (failure)
496 {
497 allocator.deallocate(buf);
498 }
499 for (T* src = this.data, dest = cast(T*) buf; src != end; ++src, ++dest)
500 {
501 moveEmplace(*src, *dest);
502 static if (hasElaborateDestructor!T)
503 {
504 destroy(*src);
505 }
506 }
507 deallocate();
508 this.data = cast(T*) buf;
509 }
510 this.capacity_ = size;
511 }
512
513 ///
514 @nogc nothrow pure @safe unittest
515 {
516 Array!int v;
517 assert(v.capacity == 0);
518 assert(v.length == 0);
519
520 v.reserve(3);
521 assert(v.capacity == 3);
522 assert(v.length == 0);
523 }
524
525 /**
526 * Requests the array to reduce its capacity to fit the $(D_PARAM size).
527 *
528 * The request is non-binding. The array won't become smaller than the
529 * $(D_PARAM length).
530 *
531 * Params:
532 * size = Desired size.
533 */
534 void shrink(size_t size) @trusted
535 {
536 if (capacity <= size)
537 {
538 return;
539 }
540 const n = max(length, size);
541 void[] buf = slice(this.capacity_);
542 if (allocator.reallocateInPlace(buf, n * T.sizeof))
543 {
544 this.capacity_ = n;
545 }
546 }
547
548 ///
549 @nogc nothrow pure @safe unittest
550 {
551 Array!int v;
552 assert(v.capacity == 0);
553 assert(v.length == 0);
554
555 v.reserve(5);
556 v.insertBack(1);
557 v.insertBack(3);
558 assert(v.capacity == 5);
559 assert(v.length == 2);
560 }
561
562 /**
563 * Returns: $(D_KEYWORD true) if the array is empty.
564 */
565 @property bool empty() const
566 {
567 return length == 0;
568 }
569
570 /**
571 * Removes the value at the back of the array.
572 *
573 * Returns: The number of elements removed
574 *
575 * Precondition: $(D_INLINECODE !empty).
576 */
577 void removeBack()
578 in
579 {
580 assert(!empty);
581 }
582 do
583 {
584 length = length - 1;
585 }
586
587 /**
588 * Removes $(D_PARAM howMany) elements from the array.
589 *
590 * This method doesn't fail if it could not remove $(D_PARAM howMany)
591 * elements. Instead, if $(D_PARAM howMany) is greater than the array
592 * length, all elements are removed.
593 *
594 * Params:
595 * howMany = How many elements should be removed.
596 *
597 * Returns: The number of elements removed
598 */
599 size_t removeBack(size_t howMany)
600 out (removed)
601 {
602 assert(removed <= howMany);
603 }
604 do
605 {
606 const toRemove = min(howMany, length);
607
608 length = length - toRemove;
609
610 return toRemove;
611 }
612
613 ///
614 @nogc nothrow pure @safe unittest
615 {
616 auto v = Array!int([5, 18, 17]);
617
618 assert(v.removeBack(0) == 0);
619 assert(v.removeBack(2) == 2);
620 assert(v.removeBack(3) == 1);
621 assert(v.removeBack(3) == 0);
622 }
623
624 private inout(T)[] slice(size_t length) inout @trusted
625 in
626 {
627 assert(length <= capacity);
628 }
629 do
630 {
631 return this.data[0 .. length];
632 }
633
634 private @property inout(T)* end() inout @trusted
635 {
636 return this.data + this.length_;
637 }
638
639 /**
640 * Remove all elements beloning to $(D_PARAM r).
641 *
642 * Params:
643 * r = Range originally obtained from this array.
644 *
645 * Returns: A range spanning the remaining elements in the array that
646 * initially were right after $(D_PARAM r).
647 *
648 * Precondition: $(D_PARAM r) refers to a region of $(D_KEYWORD this).
649 */
650 Range remove(scope Range r)
651 in
652 {
653 assert(r.container is &this);
654 assert(r.begin >= this.data);
655 assert(r.end <= end);
656 }
657 do
658 {
659 auto target = r.begin;
660 auto source = r.end;
661 while (source !is end)
662 {
663 move(*source, *target);
664 ((ref s, ref t) @trusted {++s; ++t;})(source, target);
665 }
666 length = length - r.length;
667 return Range(this, r.begin, end);
668 }
669
670 ///
671 @nogc nothrow pure @safe unittest
672 {
673 auto v = Array!int([5, 18, 17, 2, 4, 6, 1]);
674
675 assert(v.remove(v[1 .. 3]).length == 4);
676 assert(v[0] == 5 && v[1] == 2 && v[2] == 4 && v[3] == 6 && v[4] == 1);
677 assert(v.length == 5);
678
679 assert(v.remove(v[4 .. 4]).length == 1);
680 assert(v[0] == 5 && v[1] == 2 && v[2] == 4 && v[3] == 6 && v[4] == 1);
681 assert(v.length == 5);
682
683 assert(v.remove(v[4 .. 5]).length == 0);
684 assert(v[0] == 5 && v[1] == 2 && v[2] == 4 && v[3] == 6);
685 assert(v.length == 4);
686
687 assert(v.remove(v[]).length == 0);
688
689 }
690
691 private void moveBack(R)(ref R el) @trusted
692 if (isImplicitlyConvertible!(R, T))
693 {
694 reserve(this.length + 1);
695 moveEmplace(el, *end);
696 ++this.length_;
697 }
698
699 /**
700 * Inserts the $(D_PARAM el) into the array.
701 *
702 * Params:
703 * R = Type of the inserted value(s) (single value, range or static array).
704 * el = Value(s) should be inserted.
705 *
706 * Returns: The number of elements inserted.
707 */
708 size_t insertBack(R)(R el)
709 if (isImplicitlyConvertible!(R, T))
710 {
711 moveBack(el);
712 return 1;
713 }
714
715 /// ditto
716 size_t insertBack(R)(ref R el)
717 if (isImplicitlyConvertible!(R, T))
718 {
719 length = length + 1;
720 scope (failure)
721 {
722 length = length - 1;
723 }
724 opIndex(this.length - 1) = el;
725 return 1;
726 }
727
728 /// ditto
729 size_t insertBack(R)(scope R el)
730 if (!isInfinite!R
731 && isInputRange!R
732 && isImplicitlyConvertible!(ElementType!R, T))
733 {
734 static if (hasLength!R)
735 {
736 reserve(length + el.length);
737 }
738 return fold!((acc, e) => acc + insertBack(e))(el, size_t.init);
739 }
740
741 /// ditto
742 size_t insertBack(size_t R)(T[R] el)
743 {
744 return insertBack!(T[])(el[]);
745 }
746
747 /// ditto
748 alias insert = insertBack;
749
750 ///
751 @nogc nothrow pure @safe unittest
752 {
753 struct TestRange
754 {
755 int counter = 6;
756
757 int front()
758 {
759 return counter;
760 }
761
762 void popFront()
763 {
764 counter -= 2;
765 }
766
767 bool empty()
768 {
769 return counter == 0;
770 }
771 }
772
773 Array!int v1;
774
775 assert(v1.insertBack(5) == 1);
776 assert(v1.length == 1);
777 assert(v1.capacity == 1);
778 assert(v1.back == 5);
779
780 assert(v1.insertBack(TestRange()) == 3);
781 assert(v1.length == 4);
782 assert(v1.capacity == 4);
783 assert(v1[0] == 5 && v1[1] == 6 && v1[2] == 4 && v1[3] == 2);
784
785 assert(v1.insertBack([34, 234]) == 2);
786 assert(v1.length == 6);
787 assert(v1.capacity == 6);
788 assert(v1[4] == 34 && v1[5] == 234);
789 }
790
791 /**
792 * Inserts $(D_PARAM el) before or after $(D_PARAM r).
793 *
794 * Params:
795 * R = Type of the inserted value(s) (single value, range or static array).
796 * r = Range originally obtained from this array.
797 * el = Value(s) should be inserted.
798 *
799 * Returns: The number of elements inserted.
800 *
801 * Precondition: $(D_PARAM r) refers to a region of $(D_KEYWORD this).
802 */
803 size_t insertAfter(R)(Range r, scope R el)
804 if (!isInfinite!R
805 && isInputRange!R
806 && isImplicitlyConvertible!(ElementType!R, T))
807 in
808 {
809 assert(r.container is &this);
810 assert(r.begin >= this.data);
811 assert(r.end <= this.data + length);
812 }
813 do
814 {
815 const oldLength = length;
816 const after = r.end - this.data;
817 const inserted = insertBack(el);
818
819 bringToFront(this.data[after .. oldLength], this.data[oldLength .. length]);
820 return inserted;
821 }
822
823 /// ditto
824 size_t insertAfter(size_t R)(Range r, T[R] el)
825 in
826 {
827 assert(r.container is &this);
828 assert(r.begin >= this.data);
829 assert(r.end <= this.data + length);
830 }
831 do
832 {
833 return insertAfter!(T[])(r, el[]);
834 }
835
836 /// ditto
837 size_t insertAfter(R)(Range r, auto ref R el)
838 if (isImplicitlyConvertible!(R, T))
839 in
840 {
841 assert(r.container is &this);
842 assert(r.begin >= this.data);
843 assert(r.end <= this.data + length);
844 }
845 do
846 {
847 const oldLen = length;
848 const offset = r.end - this.data;
849
850 static if (__traits(isRef, el))
851 {
852 insertBack(el);
853 }
854 else
855 {
856 moveBack(el);
857 }
858 bringToFront(this.data[offset .. oldLen], this.data[oldLen .. length]);
859
860 return 1;
861 }
862
863 /// ditto
864 size_t insertBefore(R)(Range r, scope R el)
865 if (!isInfinite!R
866 && isInputRange!R
867 && isImplicitlyConvertible!(ElementType!R, T))
868 in
869 {
870 assert(r.container is &this);
871 assert(r.begin >= this.data);
872 assert(r.end <= this.data + length);
873 }
874 do
875 {
876 return insertAfter(Range(this, this.data, r.begin), el);
877 }
878
879 /// ditto
880 size_t insertBefore(size_t R)(Range r, T[R] el)
881 in
882 {
883 assert(r.container is &this);
884 assert(r.begin >= this.data);
885 assert(r.end <= this.data + length);
886 }
887 do
888 {
889 return insertBefore!(T[])(r, el[]);
890 }
891
892 /// ditto
893 size_t insertBefore(R)(Range r, auto ref R el)
894 if (isImplicitlyConvertible!(R, T))
895 in
896 {
897 assert(r.container is &this);
898 assert(r.begin >= this.data);
899 assert(r.end <= this.data + length);
900 }
901 do
902 {
903 const oldLen = length;
904 const offset = r.begin - this.data;
905
906 static if (__traits(isRef, el))
907 {
908 insertBack(el);
909 }
910 else
911 {
912 moveBack(el);
913 }
914 bringToFront(this.data[offset .. oldLen], this.data[oldLen .. length]);
915
916 return 1;
917 }
918
919 ///
920 @nogc nothrow pure unittest
921 {
922 Array!int v1;
923 v1.insertAfter(v1[], [2, 8]);
924 assert(v1[0] == 2);
925 assert(v1[1] == 8);
926 assert(v1.length == 2);
927
928 v1.insertAfter(v1[], [1, 2]);
929 assert(v1[0] == 2);
930 assert(v1[1] == 8);
931 assert(v1[2] == 1);
932 assert(v1[3] == 2);
933 assert(v1.length == 4);
934
935 v1.insertAfter(v1[0 .. 0], [1, 2]);
936 assert(v1[0] == 1);
937 assert(v1[1] == 2);
938 assert(v1[2] == 2);
939 assert(v1[3] == 8);
940 assert(v1[4] == 1);
941 assert(v1[5] == 2);
942 assert(v1.length == 6);
943
944 v1.insertAfter(v1[0 .. 4], 9);
945 assert(v1[0] == 1);
946 assert(v1[1] == 2);
947 assert(v1[2] == 2);
948 assert(v1[3] == 8);
949 assert(v1[4] == 9);
950 assert(v1[5] == 1);
951 assert(v1[6] == 2);
952 assert(v1.length == 7);
953 }
954
955 ///
956 @nogc nothrow pure unittest
957 {
958 Array!int v1;
959 v1.insertBefore(v1[], [2, 8]);
960 assert(v1[0] == 2);
961 assert(v1[1] == 8);
962 assert(v1.length == 2);
963
964 v1.insertBefore(v1[], [1, 2]);
965 assert(v1[0] == 1);
966 assert(v1[1] == 2);
967 assert(v1[2] == 2);
968 assert(v1[3] == 8);
969 assert(v1.length == 4);
970
971 v1.insertBefore(v1[0 .. 1], [1, 2]);
972 assert(v1[0] == 1);
973 assert(v1[1] == 2);
974 assert(v1[2] == 1);
975 assert(v1[3] == 2);
976 assert(v1[4] == 2);
977 assert(v1[5] == 8);
978 assert(v1.length == 6);
979
980 v1.insertBefore(v1[2 .. $], 9);
981 assert(v1[0] == 1);
982 assert(v1[1] == 2);
983 assert(v1[2] == 9);
984 assert(v1[3] == 1);
985 assert(v1[4] == 2);
986 assert(v1[5] == 2);
987 assert(v1[6] == 8);
988 assert(v1.length == 7);
989 }
990
991 /**
992 * Assigns a value to the element with the index $(D_PARAM pos).
993 *
994 * Params:
995 * E = Value type.
996 * value = Value.
997 * pos = Position.
998 *
999 * Returns: Assigned value.
1000 *
1001 * Precondition: $(D_INLINECODE length > pos).
1002 */
1003 ref T opIndexAssign(E : T)(auto ref E value, size_t pos)
1004 {
1005 return opIndex(pos) = forward!value;
1006 }
1007
1008 /// ditto
1009 Range opIndexAssign(E : T)(auto ref E value)
1010 {
1011 return opSliceAssign(value, 0, length);
1012 }
1013
1014 ///
1015 @nogc nothrow pure @safe unittest
1016 {
1017 Array!int a = Array!int(1);
1018 a[0] = 5;
1019 assert(a[0] == 5);
1020 }
1021
1022 /**
1023 * Assigns a range or a static array.
1024 *
1025 * Params:
1026 * R = Value type.
1027 * value = Value.
1028 *
1029 * Returns: Assigned value.
1030 *
1031 * Precondition: $(D_INLINECODE length == value.length).
1032 */
1033 Range opIndexAssign(size_t R)(T[R] value)
1034 {
1035 return opSliceAssign!R(value, 0, length);
1036 }
1037
1038 /// ditto
1039 Range opIndexAssign()(Range value)
1040 {
1041 return opSliceAssign(value, 0, length);
1042 }
1043
1044 ///
1045 @nogc nothrow pure @safe unittest
1046 {
1047 auto v1 = Array!int([12, 1, 7]);
1048
1049 v1[] = 3;
1050 assert(v1[0] == 3);
1051 assert(v1[1] == 3);
1052 assert(v1[2] == 3);
1053
1054 v1[] = [7, 1, 12];
1055 assert(v1[0] == 7);
1056 assert(v1[1] == 1);
1057 assert(v1[2] == 12);
1058 }
1059
1060 /**
1061 * Params:
1062 * pos = Index.
1063 *
1064 * Returns: The value at a specified index.
1065 *
1066 * Precondition: $(D_INLINECODE length > pos).
1067 */
1068 ref inout(T) opIndex(size_t pos) inout @trusted
1069 in
1070 {
1071 assert(length > pos);
1072 }
1073 do
1074 {
1075 return *(this.data + pos);
1076 }
1077
1078 /**
1079 * Returns: Random access range that iterates over elements of the array,
1080 * in forward order.
1081 */
1082 Range opIndex() @trusted
1083 {
1084 return typeof(return)(this, this.data, this.data + length);
1085 }
1086
1087 /// ditto
1088 ConstRange opIndex() const @trusted
1089 {
1090 return typeof(return)(this, this.data, this.data + length);
1091 }
1092
1093 ///
1094 @nogc nothrow pure @safe unittest
1095 {
1096 const v1 = Array!int([6, 123, 34, 5]);
1097
1098 assert(v1[0] == 6);
1099 assert(v1[1] == 123);
1100 assert(v1[2] == 34);
1101 assert(v1[3] == 5);
1102 static assert(is(typeof(v1[0]) == const(int)));
1103 static assert(is(typeof(v1[])));
1104 }
1105
1106 /**
1107 * Comparison for equality.
1108 *
1109 * Params:
1110 * that = The array to compare with.
1111 *
1112 * Returns: $(D_KEYWORD true) if the arrays are equal, $(D_KEYWORD false)
1113 * otherwise.
1114 */
1115 bool opEquals()(auto ref typeof(this) that) @trusted
1116 {
1117 return equal(this.data[0 .. length], that.data[0 .. that.length]);
1118 }
1119
1120 /// ditto
1121 bool opEquals()(auto ref const typeof(this) that) const @trusted
1122 {
1123 return equal(this.data[0 .. length], that.data[0 .. that.length]);
1124 }
1125
1126 /// ditto
1127 bool opEquals(R)(R that)
1128 if (is(R == Range))
1129 {
1130 return equal(opIndex(), that);
1131 }
1132
1133 /**
1134 * Comparison for equality.
1135 *
1136 * Params:
1137 * R = Right hand side type.
1138 * that = Right hand side array range.
1139 *
1140 * Returns: $(D_KEYWORD true) if the array and the range are equal,
1141 * $(D_KEYWORD false) otherwise.
1142 */
1143 bool opEquals(R)(R that) const
1144 if (is(R == Range) || is(R == ConstRange))
1145 {
1146 return equal(opIndex(), that);
1147 }
1148
1149 ///
1150 @nogc nothrow pure @safe unittest
1151 {
1152 Array!int v1, v2;
1153 assert(v1 == v2);
1154
1155 v1.length = 1;
1156 v2.length = 2;
1157 assert(v1 != v2);
1158
1159 v1.length = 2;
1160 v1[0] = v2[0] = 2;
1161 v1[1] = 3;
1162 v2[1] = 4;
1163 assert(v1 != v2);
1164
1165 v2[1] = 3;
1166 assert(v1 == v2);
1167 }
1168
1169 /**
1170 * Returns: The first element.
1171 *
1172 * Precondition: $(D_INLINECODE !empty).
1173 */
1174 @property ref inout(T) front() inout
1175 in
1176 {
1177 assert(!empty);
1178 }
1179 do
1180 {
1181 return *this.data;
1182 }
1183
1184 ///
1185 @nogc nothrow pure @safe unittest
1186 {
1187 auto v = Array!int([5]);
1188
1189 assert(v.front == 5);
1190
1191 v.length = 2;
1192 v[1] = 15;
1193 assert(v.front == 5);
1194 }
1195
1196 /**
1197 * Returns: The last element.
1198 *
1199 * Precondition: $(D_INLINECODE !empty).
1200 */
1201 @property ref inout(T) back() inout @trusted
1202 in
1203 {
1204 assert(!empty);
1205 }
1206 do
1207 {
1208 return *(this.data + length - 1);
1209 }
1210
1211 ///
1212 @nogc nothrow pure @safe unittest
1213 {
1214 auto v = Array!int([5]);
1215
1216 assert(v.back == 5);
1217
1218 v.length = 2;
1219 v[1] = 15;
1220 assert(v.back == 15);
1221 }
1222
1223 /**
1224 * Params:
1225 * i = Slice start.
1226 * j = Slice end.
1227 *
1228 * Returns: A range that iterates over elements of the container from
1229 * index $(D_PARAM i) up to (excluding) index $(D_PARAM j).
1230 *
1231 * Precondition: $(D_INLINECODE i <= j && j <= length).
1232 */
1233 Range opSlice(size_t i, size_t j) @trusted
1234 in
1235 {
1236 assert(i <= j);
1237 assert(j <= length);
1238 }
1239 do
1240 {
1241 return typeof(return)(this, this.data + i, this.data + j);
1242 }
1243
1244 /// ditto
1245 ConstRange opSlice(size_t i, size_t j) const @trusted
1246 in
1247 {
1248 assert(i <= j);
1249 assert(j <= length);
1250 }
1251 do
1252 {
1253 return typeof(return)(this, this.data + i, this.data + j);
1254 }
1255
1256 ///
1257 @nogc nothrow pure @safe unittest
1258 {
1259 auto v = Array!int([1, 2, 3]);
1260 auto r = v[];
1261
1262 assert(r.front == 1);
1263 assert(r.back == 3);
1264
1265 r.popFront();
1266 assert(r.front == 2);
1267
1268 r.popBack();
1269 assert(r.back == 2);
1270
1271 assert(r.length == 1);
1272 }
1273
1274 ///
1275 @nogc nothrow pure @safe unittest
1276 {
1277 auto v = Array!int([1, 2, 3, 4]);
1278 auto r = v[1 .. 4];
1279 assert(r.length == 3);
1280 assert(r[0] == 2);
1281 assert(r[1] == 3);
1282 assert(r[2] == 4);
1283
1284 r = v[0 .. 0];
1285 assert(r.length == 0);
1286
1287 r = v[4 .. 4];
1288 assert(r.length == 0);
1289 }
1290
1291 /**
1292 * Slicing assignment.
1293 *
1294 * Params:
1295 * R = Type of the assigned slice or length of the static array should
1296 * be assigned.
1297 * value = New value (single value, range or static array).
1298 * i = Slice start.
1299 * j = Slice end.
1300 *
1301 * Returns: Slice with the assigned part of the array.
1302 *
1303 * Precondition: $(D_INLINECODE i <= j && j <= length
1304 * && value.length == j - i)
1305 */
1306 Range opSliceAssign(size_t R)(T[R] value, size_t i, size_t j)
1307 @trusted
1308 in
1309 {
1310 assert(i <= j);
1311 assert(j <= length);
1312 }
1313 do
1314 {
1315 copy(value[], this.data[i .. j]);
1316 return opSlice(i, j);
1317 }
1318
1319 /// ditto
1320 Range opSliceAssign(R : T)(auto ref R value, size_t i, size_t j)
1321 @trusted
1322 in
1323 {
1324 assert(i <= j);
1325 assert(j <= length);
1326 }
1327 do
1328 {
1329 fill(this.data[i .. j], value);
1330 return opSlice(i, j);
1331 }
1332
1333 /// ditto
1334 Range opSliceAssign()(Range value, size_t i, size_t j) @trusted
1335 in
1336 {
1337 assert(i <= j);
1338 assert(j <= length);
1339 assert(j - i == value.length);
1340 }
1341 do
1342 {
1343 copy(value, this.data[i .. j]);
1344 return opSlice(i, j);
1345 }
1346
1347 ///
1348 @nogc nothrow pure @safe unittest
1349 {
1350 auto v1 = Array!int([3, 3, 3]);
1351 auto v2 = Array!int([1, 2]);
1352
1353 v1[0 .. 2] = 286;
1354 assert(v1[0] == 286);
1355 assert(v1[1] == 286);
1356 assert(v1[2] == 3);
1357
1358 v2[0 .. $] = v1[1 .. 3];
1359 assert(v2[0] == 286);
1360 assert(v2[1] == 3);
1361
1362 v1[0 .. 2] = [5, 8];
1363 assert(v1[0] == 5);
1364 assert(v1[1] == 8);
1365 assert(v1[2] == 3);
1366 }
1367
1368 /**
1369 * Returns an array used internally by the array to store its owned elements.
1370 * The length of the returned array may differ from the size of the allocated
1371 * memory for the array: the array contains only initialized elements, but
1372 * not the reserved memory.
1373 *
1374 * Returns: The array with elements of this array.
1375 */
1376 inout(T[]) get() inout
1377 {
1378 return this.data[0 .. length];
1379 }
1380
1381 ///
1382 @nogc nothrow pure @system unittest
1383 {
1384 auto v = Array!int([1, 2, 4]);
1385 auto data = v.get();
1386
1387 assert(data[0] == 1);
1388 assert(data[1] == 2);
1389 assert(data[2] == 4);
1390 assert(data.length == 3);
1391
1392 data = v[1 .. 2].get();
1393 assert(data[0] == 2);
1394 assert(data.length == 1);
1395 }
1396
1397 /**
1398 * Assigns another array.
1399 *
1400 * If $(D_PARAM that) is passed by value, it won't be copied, but moved.
1401 * This array will take the ownership over $(D_PARAM that)'s storage and
1402 * the allocator.
1403 *
1404 * If $(D_PARAM that) is passed by reference, it will be copied.
1405 *
1406 * Params:
1407 * R = Content type.
1408 * that = The value should be assigned.
1409 *
1410 * Returns: $(D_KEYWORD this).
1411 */
1412 ref typeof(this) opAssign(R)(ref R that)
1413 if (is(Unqual!R == Array))
1414 {
1415 return this = that[];
1416 }
1417
1418 /// ditto
1419 ref typeof(this) opAssign(R)(R that)
1420 if (is(R == Array))
1421 {
1422 swap(this.data, that.data);
1423 swap(this.length_, that.length_);
1424 swap(this.capacity_, that.capacity_);
1425 swap(this.allocator_, that.allocator_);
1426 return this;
1427 }
1428
1429 /**
1430 * Assigns a range to the array.
1431 *
1432 * Params:
1433 * R = Content type.
1434 * that = The value should be assigned.
1435 *
1436 * Returns: $(D_KEYWORD this).
1437 */
1438 ref typeof(this) opAssign(R)(scope R that)
1439 if (!isInfinite!R
1440 && isInputRange!R
1441 && isImplicitlyConvertible!(ElementType!R, T))
1442 {
1443 length = 0;
1444 insertBack(that);
1445 return this;
1446 }
1447
1448 ///
1449 @nogc nothrow pure @safe unittest
1450 {
1451 auto v1 = const Array!int([5, 15, 8]);
1452 Array!int v2;
1453 v2 = v1;
1454 assert(v1 == v2);
1455 }
1456
1457 /**
1458 * Assigns a static array.
1459 *
1460 * Params:
1461 * R = Static array size.
1462 * that = Values to initialize the array with.
1463 *
1464 * Returns: $(D_KEYWORD this).
1465 */
1466 ref typeof(this) opAssign(size_t R)(T[R] that)
1467 {
1468 return opAssign!(T[])(that[]);
1469 }
1470
1471 ///
1472 @nogc nothrow pure @safe unittest
1473 {
1474 auto v1 = Array!int([5, 15, 8]);
1475 Array!int v2;
1476
1477 v2 = [5, 15, 8];
1478 assert(v1 == v2);
1479 }
1480
1481 mixin DefaultAllocator;
1482 }
1483
1484 ///
1485 @nogc nothrow pure @safe unittest
1486 {
1487 auto v = Array!int([5, 15, 8]);
1488
1489 assert(v.front == 5);
1490 assert(v[1] == 15);
1491 assert(v.back == 8);
1492
1493 auto r = v[];
1494 r[0] = 7;
1495 assert(r.front == 7);
1496 assert(r.front == v.front);
1497 }