diff options
author | Ori Bernstein <ori@eigenstate.org> | 2015-08-26 12:20:58 -0700 |
---|---|---|
committer | Ori Bernstein <ori@eigenstate.org> | 2015-08-26 12:20:58 -0700 |
commit | 2bc852bda98762d3bc01548bf972e3f1b137fbfb (patch) | |
tree | 74831deed3c9057c5fe0cbb8790d220e855bc792 /lib/std/search.myr | |
parent | 3de952510eb2a23350d24ed926f19c0cf72a12f2 (diff) | |
download | mc-2bc852bda98762d3bc01548bf972e3f1b137fbfb.tar.gz |
Move Myrddin libs to lib/ subdirectory.
Diffstat (limited to 'lib/std/search.myr')
-rw-r--r-- | lib/std/search.myr | 43 |
1 files changed, 43 insertions, 0 deletions
diff --git a/lib/std/search.myr b/lib/std/search.myr new file mode 100644 index 0000000..725e419 --- /dev/null +++ b/lib/std/search.myr @@ -0,0 +1,43 @@ +use "cmp.use" +use "option.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 + | _: + /* nothing */ + ;; + ;; + -> `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 +} + + |