Move Myrddin libs to lib/ subdirectory.

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
+}
+		
+