digitalmars.D.announce - Cashew updated, Sep 2007
- Chris Nicholson-Sauls (21/21) Sep 04 2007 Yet some more updates to Cashew. Woooo.
- Bill Baxter (182/190) Sep 04 2007 I sent you some binary search routines for array a while back. Since
- Chris Nicholson-Sauls (4/9) Sep 04 2007 I do still have those, just hadn't merged them in yet. (Didn't work on ...
- Chris Nicholson-Sauls (8/20) Sep 04 2007 And now they are there.
- Bill Baxter (10/37) Sep 04 2007 Great! Now next time I need them I won't have to go digging through my
Yet some more updates to Cashew. Woooo.
cashew.cgi.UrlEncode : 0.2.0
-- Cleanup
-- DDoc'd
cashew.sys.Environment : 0.3.1
-- Cleanup
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);
:)
cashew.utils.UTest : 0.2.4
-- DDoc'd
CashewXML (cashew.xml.*) : 0.1.0a
-- Almost usable, but not quite yet.
(This is a minimalistic/simplistic XML library without PI's or SGML except
CDATA.
For complete XML support, Mango is your friend.)
CashewJSON (cashew.json.*) : 0.3.0
-- Fully re-implemented JSON library.
-- Chris Nicholson-Sauls
Sep 04 2007
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); }
Sep 04 2007
Bill Baxter wrote: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:I do still have those, just hadn't merged them in yet. (Didn't work on Cashew at all for a good long while.) They'll be in their own module (cashew.utils.Binary) in the next update. -- Chris Nicholson-Sauls
Sep 04 2007
Chris Nicholson-Sauls wrote:Bill Baxter wrote:And now they are there. cashew.utils.Binary : 0.1.0 -- Care of Bill Baxter Sorry about that. :) I did make small modifications, but only to add a public import of cashew.utils.Array:NOT_FOUND since you use it, and to add cashew.utils.UTest wrappers to your unittests. (Which, of course, all passed flawlessly.) -- Chris Nicholson-SaulsI 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:I do still have those, just hadn't merged them in yet. (Didn't work on Cashew at all for a good long while.) They'll be in their own module (cashew.utils.Binary) in the next update. -- Chris Nicholson-Sauls
Sep 04 2007
Bill Baxter <dnewsgroup billbaxter.com> Chris Nicholson-Sauls wrote:Chris Nicholson-Sauls wrote:Great! Now next time I need them I won't have to go digging through my source code trying to remember where I put them. :-). I just remembered one thing I changed in a different copy of this stuff I have in another folder somewhere: the preconditions should be changed to only check that the specified lo..hi range is sorted. So something like in { assert(is_sorted(A[lo..(hi==size_t.max)?$:hi])); } I've attached a patch that does that plus adds a few more unittests that would have failed under the old code. --bbBill Baxter wrote:And now they are there. cashew.utils.Binary : 0.1.0 -- Care of Bill Baxter Sorry about that. :) I did make small modifications, but only to add a public import of cashew.utils.Array:NOT_FOUND since you use it, and to add cashew.utils.UTest wrappers to your unittests. (Which, of course, all passed flawlessly.) -- Chris Nicholson-SaulsI 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:I do still have those, just hadn't merged them in yet. (Didn't work on Cashew at all for a good long while.) They'll be in their own module (cashew.utils.Binary) in the next update. -- Chris Nicholson-Sauls
Sep 04 2007