summaryrefslogtreecommitdiff
path: root/lib/std/search.myr
diff options
context:
space:
mode:
authorandrewc <andrewchamberss@gmail.com>2016-03-07 11:35:17 +1300
committerOri Bernstein <ori@eigenstate.org>2016-03-06 15:21:10 -0800
commit7232ece6a83f28173aff8be16b201151ad7d3751 (patch)
tree6abce4527effc1c2ee4381347c0da3940fa427c3 /lib/std/search.myr
parent89b3d0c393d0fc58ce185fad5e841edf077b810b (diff)
downloadmc-7232ece6a83f28173aff8be16b201151ad7d3751.tar.gz
decouple search key type from value type
Diffstat (limited to 'lib/std/search.myr')
-rw-r--r--lib/std/search.myr16
1 files changed, 8 insertions, 8 deletions
diff --git a/lib/std/search.myr b/lib/std/search.myr
index 3bf93fc..98ba862 100644
--- a/lib/std/search.myr
+++ b/lib/std/search.myr
@@ -2,14 +2,14 @@ use "cmp"
use "option"
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)))
+ generic lsearch : (sl : @t[:], key : @k, cmp : (v : @t, k : @k -> order) -> option(@idx::(integral,numeric)))
+ generic bsearch : (sl : @t[:], key : @k, cmp : (v : @t, k : @k -> order) -> option(@idx::(integral,numeric)))
;;
/* linear search over a list of values */
-generic lsearch = {sl, val, cmp
+generic lsearch = {sl, key, cmp
for var i = 0; i < sl.len; i++
- match cmp(sl[i], val)
+ match cmp(sl[i], key)
| `Equal:
-> `Some i
| _:
@@ -20,7 +20,7 @@ generic lsearch = {sl, val, cmp
}
/* binary search over a sorted list of values. */
-generic bsearch = {sl, val, cmp
+generic bsearch = {sl, key, cmp
var hi, lo, mid
lo = 0
@@ -28,9 +28,9 @@ generic bsearch = {sl, val, cmp
while lo <= hi
mid = (hi + lo) / 2
- match cmp(val, sl[mid])
- | `Before: hi = mid - 1
- | `After: lo = mid + 1
+ match cmp(sl[mid], key)
+ | `After: hi = mid - 1
+ | `Before: lo = mid + 1
| `Equal:
-> `Some mid
;;