1 /**
2  * Array utility functions
3  *
4  * License:
5  *   This Source Code Form is subject to the terms of
6  *   the Mozilla Public License, v. 2.0. If a copy of
7  *   the MPL was not distributed with this file, You
8  *   can obtain one at http://mozilla.org/MPL/2.0/.
9  *
10  * Authors:
11  *   Vladimir Panteleev <ae@cy.md>
12  */
13 
14 module ae.utils.array;
15 
16 import std.algorithm.iteration;
17 import std.algorithm.mutation;
18 import std.algorithm.searching;
19 import std.algorithm.sorting;
20 import std.array;
21 import std.exception;
22 import std.format;
23 import std.functional;
24 import std.range.primitives;
25 import std.traits;
26 
27 import ae.utils.meta;
28 
29 public import ae.utils.aa;
30 public import ae.utils.appender;
31 
32 /// Slice a variable.
33 @property T[] asSlice(T)(ref T v)
34 {
35 	return (&v)[0..1];
36 }
37 
38 // deprecated alias toArray = asSlice;
39 // https://issues.dlang.org/show_bug.cgi?id=23968
40 deprecated T[] toArray(T)(ref T v) { return v.asSlice; }
41 
42 /// Wrap `v` into a static array of length 1.
43 @property T[1] asUnitStaticArray(T)(T v)
44 {
45 	return (&v)[0..1];
46 }
47 
48 /// ditto
49 @property ref T[1] asUnitStaticArray(T)(ref T v)
50 {
51 	return (&v)[0..1];
52 }
53 
54 unittest
55 {
56 	int[1] arr = 1.asUnitStaticArray;
57 	int i;
58 	assert(i.asUnitStaticArray.ptr == &i);
59 }
60 
61 /// std.array.staticArray polyfill
62 static if (__traits(hasMember, std.array, "staticArray"))
63 	public import std.array : staticArray;
64 else
65 	pragma(inline, true) T[n] staticArray(T, size_t n)(auto ref T[n] a) { return a; }
66 
67 /// Convert a dynamic array to a static array
68 template toStaticArray(size_t n)
69 {
70 	ref T[n] toStaticArray(T)(return T[] a)
71 	{
72 		assert(a.length == n, "Size mismatch");
73 		return a[0 .. n];
74 	}
75 }
76 
77 unittest
78 {
79 	auto a = [1, 2, 3];
80 	assert(a.toStaticArray!3 == [1, 2, 3]);
81 
82 	import std.range : chunks;
83 	auto b = [1, 2, 3, 4];
84 	assert(b.chunks(2).map!(toStaticArray!2).array == [[1, 2], [3, 4]]);
85 }
86 
87 /// Return the value represented as an array of bytes.
88 @property inout(ubyte)[] asBytes(T)(ref inout(T) value)
89 	if (!hasIndirections!T)
90 {
91 	return value.asSlice.asBytes;
92 }
93 
94 /// ditto
95 @property inout(ubyte)[] asBytes(T)(inout(T) value)
96 	if (is(T U : U[]) && !hasIndirections!U)
97 {
98 	return cast(inout(ubyte)[])value;
99 }
100 
101 // deprecated alias bytes = asBytes;
102 // https://issues.dlang.org/show_bug.cgi?id=23968
103 deprecated @property inout(ubyte)[] bytes(T)(ref inout(T) value) if (!hasIndirections!T) { return value.asBytes; }
104 deprecated @property inout(ubyte)[] bytes(T)(inout(T) value) if (is(T U : U[]) && !hasIndirections!U) { return value.asBytes; }
105 
106 unittest
107 {
108 	ubyte b = 5;
109 	assert(b.asBytes == [5]);
110 
111 	struct S { ubyte b = 5; }
112 	S s;
113 	assert(s.asBytes == [5]);
114 
115 	ubyte[1] sa = [5];
116 	assert(sa.asBytes == [5]);
117 
118 	void[] va = sa[];
119 	assert(va.asBytes == [5]);
120 }
121 
122 /// Reverse of .asBytes
123 ref inout(T) as(T)(inout(ubyte)[] bytes)
124 	if (!hasIndirections!T)
125 {
126 	assert(bytes.length == T.sizeof, "Data length mismatch for %s".format(T.stringof));
127 	return *cast(inout(T)*)bytes.ptr;
128 }
129 
130 /// ditto
131 inout(T) as(T)(inout(ubyte)[] bytes)
132 	if (is(T U == U[]) && !hasIndirections!U)
133 {
134 	return cast(inout(T))bytes;
135 }
136 
137 // deprecated alias fromBytes = as;
138 // https://issues.dlang.org/show_bug.cgi?id=23968
139 deprecated ref inout(T) fromBytes(T)(inout(ubyte)[] bytes) if (!hasIndirections!T) { return bytes.as!T; }
140 deprecated inout(T) fromBytes(T)(inout(ubyte)[] bytes) if (is(T U == U[]) && !hasIndirections!U) { return bytes.as!T; }
141 
142 unittest
143 {
144 	{       ubyte b = 5; assert(b.asBytes.as!ubyte == 5); }
145 	{ const ubyte b = 5; assert(b.asBytes.as!ubyte == 5); }
146 	struct S { ubyte b; }
147 	{       ubyte b = 5; assert(b.asBytes.as!S == S(5)); }
148 }
149 
150 unittest
151 {
152 	struct S { ubyte a, b; }
153 	ubyte[] arr = [1, 2];
154 	assert(arr.as!S == S(1, 2));
155 	assert(arr.as!(S[]) == [S(1, 2)]);
156 	assert(arr.as!(S[1]) == [S(1, 2)]);
157 }
158 
159 /// Return the value represented as a static array of bytes.
160 @property ref inout(ubyte)[T.sizeof] asStaticBytes(T)(ref inout(T) value)
161 	if (!hasIndirections!T)
162 {
163 	return *cast(inout(ubyte)[T.sizeof]*)&value;
164 }
165 
166 /// ditto
167 @property inout(ubyte)[T.sizeof] asStaticBytes(T)(inout(T) value)
168 	if (!hasIndirections!T)
169 {
170 	return *cast(inout(ubyte)[T.sizeof]*)&value;
171 }
172 
173 unittest
174 {
175 	ubyte[4] arr = 1.asStaticBytes;
176 
177 	int i;
178 	void* a = i.asStaticBytes.ptr;
179 	void* b = &i;
180 	assert(a is b);
181 }
182 
183 /// Returns an empty, but non-null slice of T.
184 auto emptySlice(T)() pure @trusted
185 {
186 	static if (false)  // https://github.com/ldc-developers/ldc/issues/831
187 	{
188 		T[0] arr;
189 		auto p = arr.ptr;
190 	}
191 	else
192 		auto p = cast(T*)1;
193 	return p[0..0];
194 }
195 
196 unittest
197 {
198 	int[] arr = emptySlice!int;
199 	assert(arr.ptr);
200 	immutable int[] iarr = emptySlice!int;
201 	assert(iarr.ptr);
202 }
203 
204 // ************************************************************************
205 
206 /// A more generic alternative to the "is" operator,
207 /// which doesn't have corner cases with static arrays / floats.
208 bool isIdentical(T)(auto ref T a, auto ref T b)
209 {
210 	static if (hasIndirections!T)
211 		return a is b;
212 	else
213 		return a.asStaticBytes == b.asStaticBytes;
214 }
215 
216 unittest
217 {
218 	float nan;
219 	assert(isIdentical(nan, nan));
220 	float[4] nans;
221 	assert(isIdentical(nans, nans));
222 }
223 
224 /// C `memcmp` wrapper.
225 int memcmp(in ubyte[] a, in ubyte[] b)
226 {
227 	assert(a.length == b.length);
228 	import core.stdc.string : memcmp;
229 	return memcmp(a.ptr, b.ptr, a.length);
230 }
231 
232 /// Like std.algorithm.copy, but without the auto-decode bullshit.
233 /// https://issues.dlang.org/show_bug.cgi?id=13650
234 void memmove(T)(T[] dst, in T[] src)
235 {
236 	assert(src.length == dst.length);
237 	import core.stdc.string : memmove;
238 	memmove(dst.ptr, src.ptr, dst.length * T.sizeof);
239 }
240 
241 /// Performs binary operation `op` on every element of `a` and `b`.
242 T[] vector(string op, T)(T[] a, T[] b)
243 {
244 	assert(a.length == b.length);
245 	T[] result = new T[a.length];
246 	foreach (i, ref r; result)
247 		r = mixin("a[i]" ~ op ~ "b[i]");
248 	return result;
249 }
250 
251 /// Performs in-place binary operation `op` on every element of `a` and `b`.
252 T[] vectorAssign(string op, T)(T[] a, T[] b)
253 {
254 	assert(a.length == b.length);
255 	foreach (i, ref r; a)
256 		mixin("r " ~ op ~ "= b[i];");
257 	return a;
258 }
259 
260 /// Return `s` expanded to at least `l` elements, filling them with `c`.
261 T[] padRight(T)(T[] s, size_t l, T c)
262 {
263 	auto ol = s.length;
264 	if (ol < l)
265 	{
266 		s.length = l;
267 		s[ol..$] = c;
268 	}
269 	return s;
270 }
271 
272 /// Return a new `T[]` of length `l`, filled with `c`.
273 T[] repeatOne(T)(T c, size_t l)
274 {
275 	T[] result = new T[l];
276 	result[] = c;
277 	return result;
278 }
279 
280 static import std.string;
281 /// Pull in overload set
282 private alias indexOf = std..string.indexOf;
283 
284 /// Complement to std.string.indexOf which works with arrays
285 /// of non-character types.
286 /// Unlike std.algorithm.countUntil, it does not auto-decode,
287 /// and returns an index usable for array indexing/slicing.
288 ptrdiff_t indexOf(T, D)(in T[] arr, in D val)
289 //	if (!isSomeChar!T)
290 	if (!isSomeChar!T && is(typeof(arr.countUntil(val))) && is(typeof(arr[0]==val)))
291 {
292 	//assert(arr[0]==val);
293 	return arr.countUntil(val);
294 }
295 
296 ptrdiff_t indexOf(T)(in T[] arr, in T[] val) /// ditto
297 	if (!isSomeChar!T && is(typeof(arr.countUntil(val))))
298 {
299 	return arr.countUntil(val);
300 } /// ditto
301 
302 unittest
303 {
304 	assert("abc".indexOf('b') == 1);
305 	assert("abc".indexOf("b") == 1);
306 	assert([1, 2, 3].indexOf( 2 ) == 1);
307 	assert([1, 2, 3].indexOf([2]) == 1);
308 }
309 
310 deprecated ptrdiff_t indexOfElement(T, D)(in T[] arr, auto ref const D val)
311 	if (is(typeof(arr[0]==val)))
312 {
313 	foreach (i, ref v; arr)
314 		if (v == val)
315 			return i;
316 	return -1;
317 }
318 
319 /// Whether array contains value, no BS.
320 bool contains(T, V)(in T[] arr, auto ref const V val)
321 	if (is(typeof(arr[0]==val)))
322 {
323 	return arr.indexOf(val) >= 0;
324 }
325 
326 /// Ditto, for substrings
327 bool contains(T, U)(T[] str, U[] what)
328 if (is(Unqual!T == Unqual!U))
329 {
330 	return str._indexOf(what) >= 0;
331 }
332 
333 unittest
334 {
335 	assert( "abc".contains('b'));
336 	assert(!"abc".contains('x'));
337 	assert( "abc".contains("b"));
338 	assert(!"abc".contains("x"));
339 }
340 
341 /// Like startsWith, but with an offset.
342 bool containsAt(T)(in T[] haystack, in T[] needle, size_t offset)
343 {
344 	return haystack.length >= offset + needle.length
345 		&& haystack[offset..offset+needle.length] == needle;
346 }
347 
348 unittest
349 {
350 	assert( "abracadabra".containsAt("ada", 5));
351 	assert(!"abracadabra".containsAt("ada", 6));
352 	assert(!"abracadabra".containsAt("ada", 99));
353 }
354 
355 /// Returns `true` if one of the elements of `arr` contains `val`.
356 bool isIn(T)(T val, in T[] arr)
357 {
358 	return arr.contains(val);
359 }
360 
361 /// Returns `true` if one of the elements of `arr` contains `val`.
362 bool isOneOf(T)(T val, T[] arr...)
363 {
364 	return arr.contains(val);
365 }
366 
367 /// Like AA.get - soft indexing, throws an
368 /// Exception (not an Error) on out-of-bounds,
369 /// even in release builds.
370 ref T get(T)(T[] arr, size_t index)
371 {
372 	enforce(index < arr.length, "Out-of-bounds array access");
373 	return arr[index];
374 }
375 
376 /// Like AA.get - soft indexing, returns
377 /// default value on out-of-bounds.
378 auto get(T)(T[] arr, size_t index, auto ref T defaultValue)
379 {
380 	if (index >= arr.length)
381 		return defaultValue;
382 	return arr[index];
383 }
384 
385 /// Expand the array if index is out-of-bounds.
386 ref T getExpand(T)(ref T[] arr, size_t index)
387 {
388 	if (index >= arr.length)
389 		arr.length = index + 1;
390 	return arr[index];
391 }
392 
393 /// ditto
394 ref T putExpand(T)(ref T[] arr, size_t index, auto ref T value)
395 {
396 	if (index >= arr.length)
397 		arr.length = index + 1;
398 	return arr[index] = value;
399 }
400 
401 /// Slices an array. Throws an Exception (not an Error)
402 /// on out-of-bounds, even in release builds.
403 T[] slice(T)(T[] arr, size_t p0, size_t p1)
404 {
405 	enforce(p0 < p1 && p1 < arr.length, "Out-of-bounds array slice");
406 	return arr[p0..p1];
407 }
408 
409 /// Given an array and a reference to an element,
410 /// return whether the array slices over the element reference.
411 bool slicesOver(T)(const(T)[] arr, ref const T element)
412 {
413 	auto start = arr.ptr;
414 	auto end = start + arr.length;
415 	auto p = &element;
416 	return start <= p && p < end;
417 }
418 
419 /// Given an array and a reference to an element inside it, returns its index.
420 /// The reverse operation of indexing an array.
421 size_t elementIndex(T)(const(T)[] arr, ref const T element) @trusted
422 {
423 	auto start = arr.ptr;
424 	auto end = start + arr.length;
425 	auto p = &element;
426 	assert(start <= p && p < end, "Element is not in array");
427 	return p - start;
428 }
429 
430 @safe unittest
431 {
432 	auto arr = [1, 2, 3];
433 	assert(arr.elementIndex(arr[1]) == 1);
434 }
435 
436 /// Given an array and its slice, returns the
437 /// start index of the slice inside the array.
438 /// The reverse operation of slicing an array.
439 size_t sliceIndex(T)(in T[] arr, in T[] slice) @trusted
440 {
441 	auto a = arr.ptr;
442 	auto b = a + arr.length;
443 	auto p = slice.ptr;
444 	assert(a <= p && p <= b, "Out-of-bounds array slice");
445 	return p - a;
446 }
447 
448 /// Like std.array.split, but returns null if val was empty.
449 auto splitEmpty(T, S)(T value, S separator)
450 {
451 	return value.length ? split(value, separator) : null;
452 }
453 
454 /// Like std.array.split, but always returns a non-empty array.
455 auto split1(T, S)(T value, S separator)
456 {
457 	auto result = split(value, separator);
458 	return result.length ? result : [value];
459 }
460 
461 /// Include delimiter in result chunks as suffix
462 H[] splitWithSuffix(H, S)(H haystack, S separator)
463 {
464 	H[] result;
465 	while (haystack.length)
466 	{
467 		auto pos = haystack._indexOf(separator);
468 		if (pos < 0)
469 			pos = haystack.length;
470 		else
471 		{
472 			static if (is(typeof(haystack[0] == separator)))
473 				pos += 1;
474 			else
475 			static if (is(typeof(haystack[0..1] == separator)))
476 				pos += separator.length;
477 			else
478 				static assert(false, "Don't know how to split " ~ H.stringof ~ " by " ~ S.stringof);
479 		}
480 		result ~= haystack[0..pos];
481 		haystack = haystack[pos..$];
482 	}
483 	return result;
484 }
485 
486 unittest
487 {
488 	assert("a\nb".splitWithSuffix('\n') == ["a\n", "b"]);
489 	assert([1, 0, 2].splitWithSuffix(0) == [[1, 0], [2]]);
490 
491 	assert("a\r\nb".splitWithSuffix("\r\n") == ["a\r\n", "b"]);
492 	assert([1, 0, 0, 2].splitWithSuffix([0, 0]) == [[1, 0, 0], [2]]);
493 }
494 
495 /// Include delimiter in result chunks as prefix
496 H[] splitWithPrefix(H, S)(H haystack, S separator)
497 {
498 	H[] result;
499 	while (haystack.length)
500 	{
501 		auto pos = haystack[1..$]._indexOf(separator);
502 		if (pos < 0)
503 			pos = haystack.length;
504 		else
505 			pos++;
506 		result ~= haystack[0..pos];
507 		haystack = haystack[pos..$];
508 	}
509 	return result;
510 }
511 
512 unittest
513 {
514 	assert("a\nb".splitWithPrefix('\n') == ["a", "\nb"]);
515 	assert([1, 0, 2].splitWithPrefix(0) == [[1], [0, 2]]);
516 
517 	assert("a\r\nb".splitWithPrefix("\r\n") == ["a", "\r\nb"]);
518 	assert([1, 0, 0, 2].splitWithPrefix([0, 0]) == [[1], [0, 0, 2]]);
519 }
520 
521 /// Include delimiters in result chunks as prefix/suffix
522 S[] splitWithPrefixAndSuffix(S)(S haystack, S prefix, S suffix)
523 {
524 	S[] result;
525 	auto separator = suffix ~ prefix;
526 	while (haystack.length)
527 	{
528 		auto pos = haystack._indexOf(separator);
529 		if (pos < 0)
530 			pos = haystack.length;
531 		else
532 			pos += suffix.length;
533 		result ~= haystack[0..pos];
534 		haystack = haystack[pos..$];
535 	}
536 	return result;
537 }
538 
539 ///
540 unittest
541 {
542 	auto s = q"EOF
543 Section 1:
544 10
545 11
546 12
547 Section 2:
548 21
549 22
550 23
551 Section 3:
552 31
553 32
554 33
555 EOF";
556 	auto parts = s.splitWithPrefixAndSuffix("Section ", "\n");
557 	assert(parts.length == 3 && parts.join == s);
558 	foreach (part; parts)
559 		assert(part.startsWith("Section ") && part.endsWith("\n"));
560 }
561 
562 /// Ensure that arr is non-null if empty.
563 T[] nonNull(T)(T[] arr)
564 {
565 	if (arr !is null)
566 		return arr;
567 	return emptySlice!(typeof(arr[0]));
568 }
569 
570 /// If arr is null, return null. Otherwise, return a non-null
571 /// transformation dg over arr.
572 template mapNull(alias dg)
573 {
574 	auto mapNull(T)(T arr)
575 	{
576 		if (arr is null)
577 			return null;
578 		return dg(arr).nonNull;
579 	}
580 }
581 
582 unittest
583 {
584 	assert(string.init.mapNull!(s => s          )  is null);
585 	assert(string.init.mapNull!(s => ""         )  is null);
586 	assert(""         .mapNull!(s => s          ) !is null);
587 	assert(""         .mapNull!(s => string.init) !is null);
588 }
589 
590 /// Select and return a random element from the array.
591 auto ref sample(T)(T[] arr)
592 {
593 	import std.random;
594 	return arr[uniform(0, $)];
595 }
596 
597 unittest
598 {
599 	assert([7, 7, 7].sample == 7);
600 	auto s = ["foo", "bar"].sample(); // Issue 13807
601 	const(int)[] a2 = [5]; sample(a2);
602 }
603 
604 /// Select and return a random element from the array,
605 /// and remove it from the array.
606 T pluck(T)(ref T[] arr)
607 {
608 	import std.random;
609 	auto pos = uniform(0, arr.length);
610 	auto result = arr[pos];
611 	arr = arr.remove(pos);
612 	return result;
613 }
614 
615 unittest
616 {
617 	auto arr = [1, 2, 3];
618 	auto res = [arr.pluck, arr.pluck, arr.pluck];
619 	res.sort();
620 	assert(res == [1, 2, 3]);
621 }
622 
623 import std.functional;
624 
625 /// Remove first matching element in an array, mutating the array.
626 /// Returns true if the array has been modified.
627 /// Cf. `K[V].remove(K)`
628 bool removeFirst(T, alias eq = binaryFun!"a == b", SwapStrategy swapStrategy = SwapStrategy.stable)(ref T[] arr, T elem)
629 {
630 	foreach (i, ref e; arr)
631 		if (eq(e, elem))
632 		{
633 			arr = arr.remove!swapStrategy(i);
634 			return true;
635 		}
636 	return false;
637 }
638 
639 unittest
640 {
641 	int[] arr = [1, 2, 3, 2];
642 	arr.removeFirst(2);
643 	assert(arr == [1, 3, 2]);
644 }
645 
646 /// Remove all matching elements in an array, mutating the array.
647 /// Returns the number of removed elements.
648 size_t removeAll(T, alias eq = binaryFun!"a == b", SwapStrategy swapStrategy = SwapStrategy.stable)(ref T[] arr, T elem)
649 {
650 	auto oldLength = arr.length;
651 	arr = arr.remove!((ref e) => eq(e, elem));
652 	return oldLength - arr.length;
653 }
654 
655 unittest
656 {
657 	int[] arr = [1, 2, 3, 2];
658 	arr.removeAll(2);
659 	assert(arr == [1, 3]);
660 }
661 
662 /// Sorts `arr` in-place using counting sort.
663 /// The difference between the lowest and highest
664 /// return value of `orderPred(arr[i])` shouldn't be too big.
665 void countSort(alias orderPred = "a", T)(T[] arr, ref T[] valuesBuf, ref size_t[] countsBuf)
666 {
667 	alias getIndex = unaryFun!orderPred;
668 	alias Index = typeof(getIndex(arr[0]));
669 	if (arr.length == 0)
670 		return;
671 	Index min = getIndex(arr[0]);
672 	Index max = min;
673 	foreach (ref el; arr[1..$])
674 	{
675 		Index i = getIndex(el);
676 		if (min > i)
677 			min = i;
678 		if (max < i)
679 			max = i;
680 	}
681 
682 	auto n = max - min + 1;
683 	if (valuesBuf.length < n)
684 		valuesBuf.length = n;
685 	auto values = valuesBuf[0 .. n];
686 	if (countsBuf.length < n)
687 		countsBuf.length = n;
688 	auto counts = countsBuf[0 .. n];
689 
690 	foreach (el; arr)
691 	{
692 		auto i = getIndex(el) - min;
693 		values[i] = el;
694 		counts[i]++;
695 	}
696 
697 	size_t p = 0;
698 	foreach (i; 0 .. n)
699 	{
700 		auto count = counts[i];
701 		arr[p .. p + count] = values[i];
702 		p += count;
703 	}
704 	assert(p == arr.length);
705 }
706 
707 void countSort(alias orderPred = "a", T)(T[] arr)
708 {
709 	static size_t[] countsBuf;
710 	static T[] valuesBuf;
711 	countSort!orderPred(arr, valuesBuf, countsBuf);
712 } /// ditto
713 
714 unittest
715 {
716 	auto arr = [3, 2, 5, 2, 1];
717 	arr.countSort();
718 	assert(arr == [1, 2, 2, 3, 5]);
719 }
720 
721 // ***************************************************************************
722 
723 /// Push `val` into `arr`, treating it like a stack.
724 void stackPush(T)(ref T[] arr, auto ref T val)
725 {
726 	arr ~= val;
727 }
728 
729 /// Push `val` into `arr`, treating it like a queue.
730 alias stackPush queuePush;
731 
732 /// Peek at the front of `arr`, treating it like a stack.
733 ref T stackPeek(T)(T[] arr) { return arr[$-1]; }
734 
735 /// Pop a value off the front of `arr`, treating it like a stack.
736 ref T stackPop(T)(ref T[] arr)
737 {
738 	auto ret = &arr[$-1];
739 	arr = arr[0..$-1];
740 	return *ret;
741 }
742 
743 /// Peek at the front of `arr`, treating it like a queue.
744 ref T queuePeek(T)(T[] arr) { return arr[0]; }
745 
746 /// Peek at the back of `arr`, treating it like a queue.
747 ref T queuePeekLast(T)(T[] arr) { return arr[$-1]; }
748 
749 /// Pop a value off the front of `arr`, treating it like a queue.
750 ref T queuePop(T)(ref T[] arr)
751 {
752 	auto ret = &arr[0];
753 	arr = arr[1..$];
754 	if (!arr.length) arr = null;
755 	return *ret;
756 }
757 
758 /// Remove the first element of `arr` and return it.
759 ref T shift(T)(ref T[] arr) { auto oldArr = arr; arr = arr[1..$]; return oldArr[0]; }
760 
761 /// Remove the `n` first elements of `arr` and return them.
762 T[] shift(T)(ref T[] arr, size_t n) { T[] result = arr[0..n]; arr = arr[n..$]; return result; }
763 T[N] shift(size_t N, T)(ref T[] arr) { T[N] result = cast(T[N])(arr[0..N]); arr = arr[N..$]; return result; } /// ditto
764 
765 /// Insert elements in the front of `arr`.
766 void unshift(T)(ref T[] arr, T value) { arr.insertInPlace(0, value); }
767 void unshift(T)(ref T[] arr, T[] value) { arr.insertInPlace(0, value); } /// ditto
768 
769 unittest
770 {
771 	int[] arr = [1, 2, 3];
772 	assert(arr.shift == 1);
773 	assert(arr == [2, 3]);
774 	assert(arr.shift(2) == [2, 3]);
775 	assert(arr == []);
776 
777 	arr = [3];
778 	arr.unshift([1, 2]);
779 	assert(arr == [1, 2, 3]);
780 	arr.unshift(0);
781 	assert(arr == [0, 1, 2, 3]);
782 
783 	assert(arr.shift!2 == [0, 1]);
784 	assert(arr == [2, 3]);
785 }
786 
787 /// If arr starts with prefix, slice it off and return true.
788 /// Otherwise leave arr unchaned and return false.
789 deprecated("Use std.algorithm.skipOver instead")
790 bool eat(T)(ref T[] arr, T[] prefix)
791 {
792 	if (arr.startsWith(prefix))
793 	{
794 		arr = arr[prefix.length..$];
795 		return true;
796 	}
797 	return false;
798 }
799 
800 // Overload disambiguator
801 private sizediff_t _indexOf(H, N)(H haystack, N needle)
802 {
803 	static import std.string;
804 
805 	static if (is(typeof(ae.utils.array.indexOf(haystack, needle))))
806 		alias indexOf = ae.utils.array.indexOf;
807 	else
808 	static if (is(typeof(std..string.indexOf(haystack, needle))))
809 		alias indexOf = std..string.indexOf;
810 	else
811 		static assert(false, "No suitable indexOf overload found");
812 	return indexOf(haystack, needle);
813 }
814 
815 /// Returns the slice of source up to the first occurrence of delim,
816 /// and fast-forwards source to the point after delim.
817 /// If delim is not found, the behavior depends on orUntilEnd:
818 /// - If orUntilEnd is false (default), it returns null
819 ///   and leaves source unchanged.
820 /// - If orUntilEnd is true, it returns source,
821 ///   and then sets source to null.
822 T[] skipUntil(T, D)(ref T[] source, D delim, bool orUntilEnd = false)
823 {
824 	enum bool isSlice = is(typeof(source[0..1]==delim));
825 	enum bool isElem  = is(typeof(source[0]   ==delim));
826 	static assert(isSlice || isElem, "Can't skip " ~ T.stringof ~ " until " ~ D.stringof);
827 	static assert(isSlice != isElem, "Ambiguous types for skipUntil: " ~ T.stringof ~ " and " ~ D.stringof);
828 	static if (isSlice)
829 		auto delimLength = delim.length;
830 	else
831 		enum delimLength = 1;
832 
833 	auto i = _indexOf(source, delim);
834 	if (i < 0)
835 	{
836 		if (orUntilEnd)
837 		{
838 			auto result = source;
839 			source = null;
840 			return result;
841 		}
842 		else
843 			return null;
844 	}
845 	auto result = source[0..i];
846 	source = source[i+delimLength..$];
847 	return result;
848 }
849 
850 /// Like `std.algorithm.skipOver`, but stops when
851 /// `pred(suffix)` or `pred(suffix[0])` returns false.
852 template skipWhile(alias pred)
853 {
854 	T[] skipWhile(T)(ref T[] source, bool orUntilEnd = false)
855 	{
856 		enum bool isSlice = is(typeof(pred(source[0..1])));
857 		enum bool isElem  = is(typeof(pred(source[0]   )));
858 		static assert(isSlice || isElem, "Can't skip " ~ T.stringof ~ " until " ~ pred.stringof);
859 		static assert(isSlice != isElem, "Ambiguous types for skipWhile: " ~ T.stringof ~ " and " ~ pred.stringof);
860 
861 		foreach (i; 0 .. source.length)
862 		{
863 			bool match;
864 			static if (isSlice)
865 				match = pred(source[i .. $]);
866 			else
867 				match = pred(source[i]);
868 			if (!match)
869 			{
870 				auto result = source[0..i];
871 				source = source[i .. $];
872 				return result;
873 			}
874 		}
875 
876 		if (orUntilEnd)
877 		{
878 			auto result = source;
879 			source = null;
880 			return result;
881 		}
882 		else
883 			return null;
884 	}
885 }
886 
887 unittest
888 {
889 	import std.ascii : isDigit;
890 
891 	string s = "01234abcde";
892 	auto p = s.skipWhile!isDigit;
893 	assert(p == "01234" && s == "abcde", p ~ "|" ~ s);
894 }
895 
896 deprecated("Use skipUntil instead")
897 enum OnEof { returnNull, returnRemainder, throwException }
898 
899 deprecated("Use skipUntil instead")
900 template eatUntil(OnEof onEof = OnEof.throwException)
901 {
902 	T[] eatUntil(T, D)(ref T[] source, D delim)
903 	{
904 		static if (onEof == OnEof.returnNull)
905 			return skipUntil(source, delim, false);
906 		else
907 		static if (onEof == OnEof.returnRemainder)
908 			return skipUntil(source, delim, true);
909 		else
910 			return skipUntil(source, delim, false).enforce("Delimiter not found in source");
911 	}
912 }
913 
914 deprecated unittest
915 {
916 	string s;
917 
918 	s = "Mary had a little lamb";
919 	assert(s.eatUntil(" ") == "Mary");
920 	assert(s.eatUntil(" ") == "had");
921 	assert(s.eatUntil(' ') == "a");
922 
923 	assertThrown!Exception(s.eatUntil("#"));
924 	assert(s.eatUntil!(OnEof.returnNull)("#") is null);
925 	assert(s.eatUntil!(OnEof.returnRemainder)("#") == "little lamb");
926 
927 	ubyte[] bytes = [1, 2, 0, 3, 4, 0, 0];
928 	assert(bytes.eatUntil(0) == [1, 2]);
929 	assert(bytes.eatUntil([ubyte(0), ubyte(0)]) == [3, 4]);
930 }
931 
932 // ***************************************************************************
933 
934 /// Equivalents of `array(xxx(...))`.
935 template amap(alias pred)
936 {
937 	auto amap(R)(R range)
938 	if (isInputRange!R && hasLength!R)
939 	{
940 		import core.memory : GC;
941 		import core.lifetime : emplace;
942 		alias T = typeof(unaryFun!pred(range.front));
943 		auto result = uninitializedArray!(Unqual!T[])(range.length);
944 		foreach (i; 0 .. range.length)
945 		{
946 			auto value = cast()unaryFun!pred(range.front);
947 			moveEmplace(value, result[i]);
948 			range.popFront();
949 		}
950 		assert(range.empty);
951 		return cast(T[])result;
952 	}
953 
954 	/// Like `amap` but with a static array.
955 	auto amap(T, size_t n)(T[n] arr)
956 	{
957 		alias R = typeof(unaryFun!pred(arr[0]));
958 		R[n] result;
959 		foreach (i, ref r; result)
960 			r = unaryFun!pred(arr[i]);
961 		return result;
962 	}
963 }
964 template afilter(alias pred) { auto afilter(T)(T[] arr) { return array(filter!pred(arr)); } } /// ditto
965 auto auniq(T)(T[] arr) { return array(uniq(arr)); } /// ditto
966 auto asort(alias pred, T)(T[] arr) { sort!pred(arr); return arr; } /// ditto
967 
968 unittest
969 {
970 	assert([1, 2, 3].amap!`a*2`() == [2, 4, 6]);
971 	assert([1, 2, 3].amap!(n => n*n)() == [1, 4, 9]);
972 	assert([1, 2, 3].staticArray.amap!(n => n*n)() == [1, 4, 9].staticArray);
973 }
974 
975 unittest
976 {
977 	struct NC
978 	{
979 		int i;
980 		@disable this();
981 		this(int i) { this.i = i; }
982 		@disable this(this);
983 	}
984 
985 	import std.range : iota;
986 	assert(3.iota.amap!(i => NC(i))[1].i == 1);
987 }
988 
989 unittest
990 {
991 	import std.range : iota;
992 	immutable(int)[] arr;
993 	arr = 3.iota.amap!(i => cast(immutable)i);
994 	assert(arr[1] == 1);
995 }
996 
997 // ***************************************************************************
998 
999 /// Array with normalized comparison and hashing.
1000 /// Params:
1001 ///   T = array element type to wrap.
1002 ///   normalize = function which should return a range of normalized elements.
1003 struct NormalizedArray(T, alias normalize)
1004 {
1005 	T[] arr; /// Underlying array.
1006 
1007 	this(T[] arr) { this.arr = arr; } ///
1008 
1009 	int opCmp    (in T[]                 other) const { return std.algorithm.cmp(normalize(arr), normalize(other    ))   ; } ///
1010 	int opCmp    (    const typeof(this) other) const { return std.algorithm.cmp(normalize(arr), normalize(other.arr))   ; } ///
1011 	int opCmp    (ref const typeof(this) other) const { return std.algorithm.cmp(normalize(arr), normalize(other.arr))   ; } ///
1012 	bool opEquals(in T[]                 other) const { return std.algorithm.cmp(normalize(arr), normalize(other    ))==0; } ///
1013 	bool opEquals(    const typeof(this) other) const { return std.algorithm.cmp(normalize(arr), normalize(other.arr))==0; } ///
1014 	bool opEquals(ref const typeof(this) other) const { return std.algorithm.cmp(normalize(arr), normalize(other.arr))==0; } ///
1015 
1016 	private hash_t toHashReal() const
1017 	{
1018 		import std.digest.crc;
1019 		CRC32 crc;
1020 		foreach (c; normalize(arr))
1021 			crc.put(cast(ubyte[])((&c)[0..1]));
1022 		static union Result { ubyte[4] crcResult; hash_t hash; }
1023 		return Result(crc.finish()).hash;
1024 	}
1025 
1026 	hash_t toHash() const nothrow @trusted
1027 	{
1028 		return (cast(hash_t delegate() nothrow @safe)&toHashReal)();
1029 	} ///
1030 }
1031 
1032 // ***************************************************************************
1033 
1034 /// Equivalent of PHP's `list` language construct:
1035 /// http://php.net/manual/en/function.list.php
1036 /// Works with arrays and tuples.
1037 /// Specify `null` as an argument to ignore that index
1038 /// (equivalent of `list(x, , y)` in PHP).
1039 auto list(Args...)(auto ref Args args)
1040 {
1041 	struct List
1042 	{
1043 		auto dummy() { return args[0]; } // https://issues.dlang.org/show_bug.cgi?id=11886
1044 		void opAssign(T)(auto ref T t)
1045 		{
1046 			assert(t.length == args.length,
1047 				"Assigning %d elements to list with %d elements"
1048 				.format(t.length, args.length));
1049 			foreach (i; rangeTuple!(Args.length))
1050 				static if (!is(Args[i] == typeof(null)))
1051 					args[i] = t[i];
1052 		}
1053 	}
1054 	return List();
1055 }
1056 
1057 ///
1058 unittest
1059 {
1060 	string name, value;
1061 	list(name, null, value) = "NAME=VALUE".findSplit("=");
1062 	assert(name == "NAME" && value == "VALUE");
1063 }
1064 
1065 version(LittleEndian)
1066 unittest
1067 {
1068 	uint onlyValue;
1069 	ubyte[] data = [ubyte(42), 0, 0, 0];
1070 	list(onlyValue) = cast(uint[])data;
1071 	assert(onlyValue == 42);
1072 }