ref: 61766f9822581c7f7ed44c66ff975517b350987a
parent: df187615868a82da67b31b921334449f7db5a868
author: Ori Bernstein <[email protected]>
date: Thu May 8 10:09:48 EDT 2014
Add 'search' functions:
bsearch: does a binary search on a sorted array
lsearch: does a linear search on any array
--- a/libstd/Makefile
+++ b/libstd/Makefile
@@ -27,6 +27,7 @@
optparse.myr \
rand.myr \
resolve.myr \
+ search.myr \
slcp.myr \
sldup.myr \
sleq.myr \
--- /dev/null
+++ b/libstd/search.myr
@@ -1,0 +1,42 @@
+use "cmp.use"
+use "option.use"
+use "fmt.use"
+
+pkg std =
+ generic lsearch : (sl : @t[:], val : @t, cmp : (a : @t, b : @t -> order) -> option(@idx::(integral,numeric)))
+ generic bsearch : (sl : @t[:], val : @t, cmp : (a : @t, b : @t -> order) -> option(@idx::(integral,numeric)))
+;;
+
+/* linear search over a list of values */
+generic lsearch = {sl, val, cmp+ var i
+
+ for i = 0; i < sl.len; i++
+ match cmp(sl[i], val)
+ | `Equal:
+ -> `Some i
+ ;;
+ ;;
+ -> `None
+}
+
+/* binary search over a sorted list of values. */
+generic bsearch = {sl, val, cmp+ var hi, lo, mid
+
+ lo = 0
+ hi = sl.len - 1
+
+ while lo <= hi
+ mid = (hi + lo) / 2
+ match cmp(val, sl[mid])
+ | `Before: hi = mid - 1
+ | `After: lo = mid + 1
+ | `Equal:
+ -> `Some mid
+ ;;
+ ;;
+ -> `None
+}
+
+
--- /dev/null
+++ b/test/stdsearch.myr
@@ -1,0 +1,33 @@
+use std
+
+const sl = [1, 3, 5, 8, 9, 33]
+
+const main = {+
+ expect(std.lsearch(sl[:], 1, std.numcmp), `std.Some 0)
+ expect(std.lsearch(sl[:], 33, std.numcmp), `std.Some sl.len - 1)
+ expect(std.lsearch(sl[:], 5, std.numcmp), `std.Some 2)
+ expect(std.lsearch(sl[:], 6, std.numcmp), `std.None)
+
+ expect(std.bsearch(sl[:], 1, std.numcmp), `std.Some 0)
+ expect(std.bsearch(sl[:], 33, std.numcmp), `std.Some sl.len - 1)
+ expect(std.bsearch(sl[:], 5, std.numcmp), `std.Some 2)
+ expect(std.bsearch(sl[:], 6, std.numcmp), `std.None)
+}
+
+const expect = {a, b+ match a
+ | `std.None:
+ match b
+ | `std.Some x: std.fatal(1, "Expected `std.None, `std.None, got `std.None, `std.Some %i\n", x)
+ ;;
+ | `std.Some x:
+ match b
+ | `std.None: std.fatal(1, "Expected `std.Some %i, `std.Some %i, got `std.Some %i, `std.None\n", x, x, x)
+ | `std.Some y:
+ if x != y
+ std.fatal(1, "Expected `std.Some %i, `std.Some %i, got `std.Some %i, `std.Some %i\n", x, x, x, y)
+ ;;
+ ;;
+ ;;
+}
--- a/test/tests
+++ b/test/tests
@@ -115,6 +115,7 @@
B strtab C
B catfile C
B stdsort C
+B stdsearch E 0
B strstrip C
B strsplit C
B strfind C