## bsearch-g.pkg
# Compiled by:
# src/lib/std/standard.lib# Binary searching on sorted typelocked arrays.
generic package binary_search_g (a: Typelocked_Rw_Vector ) # Typelocked_Rw_Vector is from src/lib/std/src/typelocked-rw-vector.api: (weak)
api {
package a: Typelocked_Rw_Vector; # Typelocked_Rw_Vector is from src/lib/std/src/typelocked-rw-vector.api bsearch
:
(((X, a::Element)) -> Order)
->
((X, a::Rw_Vector))
->
Null_Or( (Int, a::Element) );
#
# binary search on ordered typelocked arrays. The comparison function
# compare embeds a projection function from the element type to the key
# type.
}
{
package a = a;
# binary search on ordered typelocked arrays. The comparison function
# compare embeds a projection function from the element type to the key
# type.
fun bsearch compare (key, arr)
=
get (0, a::length arr - 1)
where
fun get (lo, hi)
=
if (hi >= lo)
m = lo + (hi - lo) / 2;
x = a::get (arr, m);
case (compare (key, x))
LESS => get (lo, m - 1);
EQUAL => (THE (m, x));
GREATER => get (m+1, hi);
esac;
else
NULL;
fi;
end;
}; # BSearch
## COPYRIGHT (c) 1994 by AT&T Bell Laboratories. See SMLNJ-COPYRIGHT file for details.
## Subsequent changes by Jeff Prothero Copyright (c) 2010-2015,
## released per terms of SMLNJ-COPYRIGHT.