/***************************************************************************************** * Utility template functions for arrays. Example: * * $(CASHEW_HEAD) *---------------------------------------------------------------------------------------- * import cashew .utils .array ; * // ... * int[] foo = ...; * foo.remove(4); * foo.eat(foo.indexOf(2)); *---------------------------------------------------------------------------------------- */ module cashew.utils.array ; /*********************************************************************************** * Unit tests support. */ version (Unittest) { import std .stdio ; } unittest { writefln("Unittest: cashew.utils.array: begin"); } /*********************************************************************************** * Create an array. */ T[] array (T) (T[] arr ...) body { return arr.dup; } unittest { writef("\t array(...) --------> "); auto foo = array!(int)(1, 2, 3); assert(foo.length == 3U); assert(typeid(typeof(foo[0])) == typeid(typeof(1))); writefln("Pass"); } /*********************************************************************************** * Verify that a given value is present in an array. */ bool contains (T) (inout T[] haystack, T needle) body { return haystack.indexOf(needle) != size_t.max; } unittest { writef("\t.contains(T) -------> "); auto foo = array!(int)(1, 2, 3); assert( foo.contains(2)); assert(! foo.contains(4)); writefln("Pass"); } /*********************************************************************************** * Compose a new array of the values in the first parameter not present in the second. */ T[] diff (T) (inout T[] alpha, inout T[] beta) body { T[] result = alpha.dup; foreach (x; alpha) { if (beta.contains(x)) { while (result.contains(x)) { result.remove(x); } } } return result; } unittest { writef("\t.diff(T[]) ---------> "); auto foo = array!(int)(1, 2, 3, 4, 5); auto bar = array!(int)(1, 3, 5); assert(foo.diff(bar) == array!(int)(2, 4)); writefln("Pass"); } /*********************************************************************************** * Remove some of the beginning of an array. */ void eat (T) (inout T[] haystack, size_t count) body { if (count > haystack.length) { haystack.length = 0; } else { haystack = haystack[count .. haystack.length]; } } unittest { writef("\t.eat(N) ------------> "); auto foo = array!(int)(1, 2, 3, 4, 5); foo.eat(3U); assert(foo == array!(int)(4, 5)); writefln("Pass"); } /*********************************************************************************** * Search an array for a given item, and return its index, or size_t.max if not found. */ size_t indexOf (T) (inout T[] haystack, T needle, size_t start = 0U) body { size_t result = size_t.max ; foreach (index, item; haystack[start .. haystack.length]) { if (item is needle) { result = index; break; } } if (result != size_t.max) { result += start; } return result; } unittest { writef("\t.indexOf(T) --------> "); auto foo = array!(int)(1, 2, 3); assert(foo.indexOf(2) == 1U); writefln("Pass"); } /*********************************************************************************** * Search an array for a given sub-array, and return its index, or size_t.max if not found. */ size_t indexOfSub (T) (inout T[] haystack, inout T[] bale, size_t start = 0U) body { size_t result = size_t.max , wall = haystack.length - bale.length ; for (size_t i = start; i < wall; i++) { if (haystack[i .. i + bale.length] == bale) { result = i; break; } } return result; } unittest { writef("\t.indexOfSub(T[]) ---> "); auto foo = array!(int)(1, 2, 3, 4, 5); auto sub = array!(int)( 3, 4 ); assert(foo.indexOfSub(sub) == 2U); writefln("Pass"); } /*********************************************************************************** * Same as indexOf but work backwards from the end. */ size_t rindexOf (T) (inout T[] haystack, T needle, size_t start = size_t.max) body { size_t result = size_t.max ; if (start == size_t.max) { start = haystack.length - 1U; } for (size_t i = start; i >= 0U; i--) { if (haystack[i] is needle) { result = i; break; } } return result; } unittest { writef("\t.rindexOf(T) -------> "); auto foo = array!(int)(1, 9, 2, 9, 3); assert(foo.rindexOf(9) == 3U); writefln("Pass"); } /*********************************************************************************** * Same as indexOf but work backwards from the end. */ size_t rindexOfSub (T) (inout T[] haystack, inout T[] bale, size_t start = size_t.max) body { size_t result = size_t.max ; if (start == size_t.max) { start = haystack.length; } for (size_t i = start - bale.length; i >= 0; i--) { if (haystack[i .. i + bale.length] == bale) { result = i; break; } } return result; } unittest { writef("\t.rindexOfSub(T[]) --> "); auto foo = array!(int)(1, 2, 9, 8, 1, 2, 9, 8); auto sub = array!(int)(1, 2 ); assert(foo.rindexOfSub(sub) == 4U); writefln("Pass"); } /*********************************************************************************** * Return an array composed of common elements of two arrays. */ T[] intersect (T) (inout T[] alpha, inout T[] beta) body { T[] result; foreach (x; alpha) { if (beta.contains(x)) { result ~= x; } } return result; } unittest { writef("\t.intersect(T[]) ----> "); auto foo = array!(int)(1, 2, 3, 4, 5 ); auto bar = array!(int)( 3, 4, 5, 6, 7); assert(foo.intersect(bar) == array!(int)(3, 4, 5)); writefln("Pass"); } /*********************************************************************************** * Remove an item from an array. */ void remove (T) (inout T[] haystack, T needle) body { size_t index = haystack.indexOf(needle) ; if (index != size_t.max) { haystack.removeIndex(index); } } unittest { writef("\t.remove(T) ---------> "); auto foo = array!(int)(1, 2, 3); foo.remove(2); assert(foo == array!(int)(1, 3)); writefln("Pass"); } /*********************************************************************************** * Remove all occurances of an item from an array. */ void removeAll (T) (inout T[] haystack, T needle) body { size_t index = 0U ; size_t[] indices ; while ((index = haystack.indexOf(needle, index)) != size_t.max) { indices ~= index; index++; } foreach (i, x; indices) { haystack.removeIndex(x - i); } } unittest { writef("\t.removeAll(T) ------> "); auto foo = array!(int)(1, 2, 1, 3, 1, 4, 1, 5); foo.removeAll(1); assert(foo == array!(int)(2, 3, 4, 5)); writefln("Pass"); } /*********************************************************************************** * Remove the item at a given index. */ void removeIndex (T) (inout T[] haystack, size_t index) body { haystack = haystack[0 .. index] ~ haystack[index + 1 .. haystack.length]; } unittest { writef("\t.removeIndex(N) ----> "); auto foo = array!(int)(1, 2, 3, 4); foo.removeIndex(2U); assert(foo == array!(int)(1, 2, 4)); writefln("Pass"); } /*********************************************************************************** * Build an array by repeating an item. */ void repeat (T) (inout T[] haystack, T needle, size_t len = size_t.max) body { if (len == size_t.max) { len = haystack.length; } haystack.length = len; haystack[] = needle; } unittest { writef("\t.repeat(T [, N]) ---> "); int[] foo ; foo.repeat(3, 3U); assert(foo == array!(int)(3, 3, 3)); auto bar = array!(int)(0, 0, 0, 0, 0, 0, 0); bar.repeat(7); assert(bar == array!(int)(7, 7, 7, 7, 7, 7, 7)); writefln("Pass"); } /*********************************************************************************** * Build an array by repeating a smaller array. */ void repeatSub (T) (inout T[] haystack, inout T[] bale, size_t count) body { haystack.length = 0; for (int i; i < count; i++) { haystack ~= bale; } } unittest { writef("\t.repeatSub(T[], N) -> "); int[] foo , sub = array!(int)(4, 2) ; foo.repeatSub(sub, 3U); assert(foo == array!(int)(4, 2, 4, 2, 4, 2)); writefln("Pass"); } /*********************************************************************************** * Fill an array with a given smaller array. */ void fill (T) (inout T[] haystack, inout T[] bale, size_t len = size_t.max) body { if (len == size_t.max) { len = haystack.length; } haystack.length = 0; while (haystack.length < len) { haystack ~= bale; } haystack.length = len; } unittest { writef("\t.fill (T[] [, N]) --> "); auto foo = array!(int)(1, 2, 3, 4, 5); auto sub = array!(int)(3, 2, 1 ); foo.fill(sub); assert(foo == array!(int)(3, 2, 1, 3, 2)); writefln("Pass"); } /*********************************************************************************** * Remove duplicate values from an array. */ void unique (T) (inout T[] haystack) body { size_t ridx ; for (int i = 0; i < haystack.length; i++) { ridx = size_t.max; while ((ridx = haystack.rindexOf(haystack[i], ridx)) != i) { haystack.removeIndex(ridx); } } } unittest { writef("\t.unique() ----------> "); auto foo = array!(int)(1, 1, 2, 1, 2, 3, 1, 2, 3, 4, 1, 2, 3, 4, 5); foo.unique(); assert(foo == array!(int)(1, 2, 3, 4, 5)); writefln("Pass"); } /*********************************************************************************** * Pull a number of items from one array into another. */ T[] pull (T) (inout T[] haystack, size_t idx) body { T[] result ; if (idx >= haystack.length) { idx = haystack.length; } result = haystack[0 .. idx ]; haystack = haystack[idx .. haystack.length]; return result; } unittest { writef("\t.pull(N) -----------> "); auto foo = array!(int)(1, 2, 3, 4, 5); auto bar = foo.pull(3U); assert(foo == array!(int)( 4, 5)); assert(bar == array!(int)(1, 2, 3 )); writefln("Pass"); } /*********************************************************************************** * Same as pull, but indexed from the end. */ T[] rpull (T) (inout T[] haystack, size_t idx) body { T[] result ; if (idx >= haystack.length) { result = haystack; haystack.length = 0; } else { idx--; result = haystack[idx .. haystack.length]; haystack = haystack[0 .. idx ]; } return result; } unittest { writef("\t.rpull(N) ----------> "); auto foo = array!(int)(1, 2, 3, 4, 5); auto bar = foo.rpull(3U); assert(foo == array!(int)(1, 2 )); assert(bar == array!(int)( 3, 4, 5)); auto alpha = array!(int)(1, 2, 3); auto beta = alpha.rpull(4U); assert(alpha == array!(int)( )); assert(beta == array!(int)(1, 2, 3)); writefln("Pass"); } /*********************************************************************************** * Rotate an array's contents toward the left. */ void rotl (T) (inout T[] haystack, size_t iter) body { iter %= haystack.length; haystack = haystack[iter .. haystack.length] ~ haystack[0 .. iter]; } unittest { writef("\t.rotl(N) -----------> "); auto foo = array!(int)(1, 2, 3, 4, 5, 6); foo.rotl(2U); assert(foo == array!(int)(3, 4, 5, 6 ,1, 2)); auto bar = array!(int)(1, 2, 3); bar.rotl(4U); assert(bar == array!(int)(2, 3, 1)); writefln("Pass"); } /*********************************************************************************** * Rotate an array's contents toward the right. */ void rotr (T) (inout T[] haystack, size_t iter) body { size_t idx ; iter %= haystack.length ; idx = haystack.length - iter ; haystack = haystack[idx .. haystack.length] ~ haystack[0 .. idx]; } unittest { writef("\t.rotr(N) -----------> "); auto foo = array!(int)(1, 2, 3, 4, 5, 6); foo.rotr(2U); assert(foo == array!(int)(5, 6, 1, 2, 3, 4)); auto bar = array!(int)(1, 2, 3); bar.rotr(4U); assert(bar == array!(int)(3, 1, 2)); writefln("Pass"); } /*********************************************************************************** * Append to an array. */ void push (T) (inout T[] haystack, T[] bale ...) body { haystack ~= bale; } unittest { writef("\t.push(...) ---------> "); auto foo = array!(int)(1, 2, 3); foo.push(4, 5); assert(foo == array!(int)(1, 2, 3, 4, 5)); writefln("Pass"); } /*********************************************************************************** * Retrieve and remove the last value of an array. */ T pop (T) (inout T[] haystack) body { T result = haystack[haystack.length - 1]; haystack.length = haystack.length - 1; return result; } unittest { writef("\t.pop() -------------> "); auto foo = array!(int)(1, 2, 3); auto elm = foo.pop(); assert(foo == array!(int)(1, 2)); assert(elm == 3); writefln("Pass"); } /*********************************************************************************** * Prepend to an array. */ void backpush (T) (inout T[] haystack, T[] bale ...) body { haystack ~= bale; haystack.rotr(bale.length); } unittest { writef("\t.backpush(...) -----> "); auto foo = array!(int)(3, 4); foo.backpush(1, 2); assert(foo == array!(int)(1, 2, 3, 4)); writefln("Pass"); } /*********************************************************************************** * Retrieve and remove the first value of an array. */ T backpop (T) (inout T[] haystack) body { T result = haystack[0]; haystack = haystack[1 .. haystack.length]; return result; } unittest { writef("\t.backpop() ---------> "); auto foo = array!(int)(1, 2, 3); auto elm = foo.backpop(); assert(foo == array!(int)(2, 3)); assert(elm == 1); writefln("Pass"); } /*********************************************************************************** * Drop values from the beginning of an array. */ T[] shift (T) (inout T[] haystack, size_t count) body { T[] result ; if (count >= haystack.length) { result = haystack; haystack.length = 0; } else { result = haystack[0 .. count]; haystack = haystack[count .. haystack.length]; } return result; } unittest { writef("\t.shift(N) ----------> "); auto foo = array!(int)(1, 2, 3, 4, 5); auto sub = foo.shift(3U); assert(foo == array!(int)( 4, 5)); assert(sub == array!(int)(1, 2, 3 )); writefln("Pass"); } /*********************************************************************************** * Drop values from the end of an array. */ T[] rshift (T) (inout T[] haystack, size_t count) body { T[] result ; if (count >= haystack.length) { result = haystack; haystack.length = 0; } else { result = haystack[haystack.length - count .. haystack.length]; haystack.length = haystack.length - count; } return result; } unittest { writef("\t.rshift(N) ---------> "); auto foo = array!(int)(1, 2, 3, 4, 5); auto sub = foo.rshift(3U); assert(foo == array!(int)(1, 2 )); assert(sub == array!(int)( 3, 4, 5)); writefln("Pass"); } /*********************************************************************************** * Unit tests support. */ unittest { writefln("Unittest: cashew.utils.array: end\n"); }