cashew.utils.array 0.1a.2
clayasaurus
clayasaurus at gmail.com
Wed Sep 13 06:48:31 PDT 2006
Chris Nicholson-Sauls wrote:
> Lionello Lunesu wrote:
>> Chris Nicholson-Sauls wrote:
>>
>>> I've been pushing for some array utilities to get into Phobos, yes,
>>> but in the meantime I updated the array module in my personal Cashew
>>> lib. Included in the updates are the rotl/rotr that I recall someone
>>> asking about. In the process I've discovered two bugs, as well: the
>>> behavior of 'is' versus '==' is incompatable if the operands are
>>> arrays, and DDoc for abbreviated function templates is borked. For
>>> an example of the latter, just look at Cashew's own docs.
>>
>>
>>
>> Nice.. I hope something like this will make it into Phobos at some
>> point, since everybody seems to have implemented these functions anyway..
>>
>> One remark though: your removeAll is pretty slow. It should be enough
>> to iterate the array only once. A indexOf that takes a starting_index
>> would be a simple fix.
>>
>> L.
>
> True... and fixed. :) Functions indexOf, rindexOf, indexOfSub, and
> rindexOfSub all take an optional 'start' parameter now. This effected
> the design of functions removeAll and unique.
>
> I did, however, have to do something weird with removeAll. It just
> didn't want to work right any other way... must play with it some more
> later.
>
> -- Chris Nicholson-Sauls
>
>
> ------------------------------------------------------------------------
>
> /*****************************************************************************************
> * 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");
> }
Phobos does need something like this.
More information about the Digitalmars-d-announce
mailing list