Cashew updated, Sep 2007

[Bill Baxter]

Chris Nicholson-Sauls wrote:
> Yet some more updates to Cashew.  Woooo.

> cashew.utils.Array : 0.12.0
>  -- Added .collect() pseudo-member
>  -- Changed pseudo-members returning 'void' to return 'T[]' instead, for 
> chaining.
>     This means you can do silly things like this:
>         array.unique.remove(foo).rotl(4);
>     :)

I sent you some binary search routines for array a while back.  Since 
you didn't put 'em in  I'll just post 'em here for anyone who needs to 
do binary searching:


/** Check that the array A is sorted in non-decreasing order */
bool is_sorted(T)(T[] A)
{
     size_t N = A.length;
     for(size_t i=1; i<N; i++) {
         if (A[i]<A[i-1]) return false;
     }
     return true;
}
unittest{
     int[] foo = [1,2,3,5,6];
     assert(foo.is_sorted());
     foo = [1,2,4,3,6];
     assert(!foo.is_sorted());
     foo = [];
     assert(foo.is_sorted());
     foo = [42];
     assert(foo.is_sorted());
}

/** Use binary search to look for x in A, which must be sorted.
     If there are multiple values that match, returns the value with
     the lowest index.  This method uses bisect_left() for the dirty work.

     Optional args lo (default 0) and hi (default A.length) bound the
     slice of A to be searched.
*/
size_t bsearch(T)(T[] A, T x, size_t lo=0, size_t hi=size_t.max)
in { assert(is_sorted(A)); }
body
{
     size_t ret = A.bisect_left(x,lo,hi);
     if (ret<hi && ret<A.length && A[ret]==x) {
         return ret;
     }
     return NOT_FOUND;
}
unittest{
     int[] foo = [1,3,4,6,8];
     assert(foo.bsearch(0) == NOT_FOUND);
     assert(foo.bsearch(1) == 0);
     assert(foo.bsearch(2) == NOT_FOUND);
     assert(foo.bsearch(3) == 1);
     assert(foo.bsearch(4) == 2);
     assert(foo.bsearch(5) == NOT_FOUND);
     assert(foo.bsearch(6) == 3);
     assert(foo.bsearch(7) == NOT_FOUND);
     assert(foo.bsearch(8) == 4);
     assert(foo.bsearch(9) == NOT_FOUND);
     int[] bar = [1,1,3,3,3,8,8];
     assert(bar.bsearch(0) == NOT_FOUND);
     assert(bar.bsearch(1) == 0);
     assert(bar.bsearch(2) == NOT_FOUND);
     assert(bar.bsearch(3) == 2);
     assert(bar.bsearch(4) == NOT_FOUND);
     assert(bar.bsearch(8) == 5);
     assert(bar.bsearch(9) == NOT_FOUND);
}


/** Use binary search to look for x in A, which must be sorted.
     If there are multiple values that match, returns the value with
     the highest index.

     Optional args lo (default 0) and hi (default A.length) bound the
     slice of A to be searched.
*/
size_t bsearch_right(T)(T[] A, T x, size_t lo=0, size_t hi=size_t.max)
in { assert(is_sorted(A)); }
body
{
     size_t ret = A.bisect(x,lo,hi);
     if (ret>lo) ret--;
     if (A[ret]==x) {
         return ret;
     }
     return NOT_FOUND;
}
unittest{
     int[] foo = [1,3,4,6,8];
     assert(foo.bsearch_right(0) == NOT_FOUND);
     assert(foo.bsearch_right(1) == 0);
     assert(foo.bsearch_right(2) == NOT_FOUND);
     assert(foo.bsearch_right(3) == 1);
     assert(foo.bsearch_right(4) == 2);
     assert(foo.bsearch_right(5) == NOT_FOUND);
     assert(foo.bsearch_right(6) == 3);
     assert(foo.bsearch_right(7) == NOT_FOUND);
     assert(foo.bsearch_right(8) == 4);
     assert(foo.bsearch_right(9) == NOT_FOUND);
     int[] bar = [1,1,3,3,3,8,8];
     assert(bar.bsearch_right(0) == NOT_FOUND);
     assert(bar.bsearch_right(1) == 1);
     assert(bar.bsearch_right(2) == NOT_FOUND);
     assert(bar.bsearch_right(3) == 4);
     assert(bar.bsearch_right(4) == NOT_FOUND);
     assert(bar.bsearch_right(8) == 6);
     assert(bar.bsearch_right(9) == NOT_FOUND);
}

/** Return the index where to insert item x in list A, assuming A sorted.

     The return value i is such that all e in A[0..i] have e <= x, and all
     e in A[i..$] have e > x.  So if x already appears in the list, i
     points just beyond the rightmost x already there

     Optional args lo (default 0) and hi (default A.length) bound the
     slice of A to be searched.
*/
size_t bisect(T)(T[] A, T x, size_t lo=0, size_t hi=size_t.max)
in { assert(is_sorted(A)); }
body
{
     if (hi == size_t.max) hi = A.length;
     size_t mid;
     while (lo < hi)
     {
         mid = (lo+hi)/2;
         if (x < A[mid]) { hi = mid; }
         else { lo = mid+1; }
     }
     return lo;
}
unittest{
     int[] foo = [1,3,4,6,8];
     assert(foo.bisect(0) == 0);
     assert(foo.bisect(1) == 1);
     assert(foo.bisect(2) == 1);
     assert(foo.bisect(3) == 2);
     assert(foo.bisect(4) == 3);
     assert(foo.bisect(5) == 3);
     assert(foo.bisect(10) == 5);
     int[] bar = [1,1,3,4,4,6,8,8];
     assert(bar.bisect(0) == 0);
     assert(bar.bisect(1) == 2);
     assert(bar.bisect(2) == 2);
     assert(bar.bisect(3) == 3);
     assert(bar.bisect(4) == 5);
     assert(bar.bisect(5) == 5);
     assert(bar.bisect(6) == 6);
     assert(bar.bisect(7) == 6);
     assert(bar.bisect(8) == 8);
     assert(bar.bisect(9) == 8);
}

/** Return the index where to insert item x in list A, assuming A sorted.

     The return value i is such that all e in A[0..i] have e < x, and
     all e in A[i..$] have e >= x.  So if x already appears in the
     list, i points at the leftmost x already there.

     Optional args lo (default 0) and hi (default len(a)) bound the
     slice of a to be searched.
*/
size_t bisect_left(T)(T[] A, T x, size_t lo=0, size_t hi=size_t.max)
in { assert(is_sorted(A)); }
body
{
     if (hi==size_t.max) hi = A.length;
     size_t mid;
     while (lo < hi)
     {
         mid = (lo+hi)/2;
         if (A[mid] < x) { lo = mid+1; }
         else { hi = mid; }
     }
     return lo;
}
unittest{
     int[] foo = [1,3,4,6,8];
     assert(foo.bisect_left(0) == 0);
     assert(foo.bisect_left(1) == 0);
     assert(foo.bisect_left(2) == 1);
     assert(foo.bisect_left(3) == 1);
     assert(foo.bisect_left(4) == 2);
     assert(foo.bisect_left(5) == 3);
     assert(foo.bisect_left(10) == 5);
     int[] bar = [1,1,3,4,4,6,8,8];
     assert(bar.bisect_left(0) == 0);
     assert(bar.bisect_left(1) == 0);
     assert(bar.bisect_left(2) == 2);
     assert(bar.bisect_left(3) == 2);
     assert(bar.bisect_left(4) == 3);
     assert(bar.bisect_left(5) == 5);
     assert(bar.bisect_left(6) == 5);
     assert(bar.bisect_left(7) == 6);
     assert(bar.bisect_left(8) == 6);
     assert(bar.bisect_left(9) == 8);
}