[m-rev.] For review: add array.binary_search

[Ralph Becket]

Interdiff in response to verbal feedback in the office:

diff -u NEWS NEWS
--- NEWS	17 Jun 2009 04:18:22 -0000
+++ NEWS	17 Jun 2009 04:43:56 -0000
@@ -96,9 +96,12 @@
     set.filter_map/3
 
 * The following predicates have been added to the array modules:
+    array.binary_search/3
+    array.binary_search/4
+    array.approx_binary_search/3
+    array.approx_binary_search/4
     array.fold/4
     array.foldl2/6
-    array.binary_search/3
     version_array.foldl/4
 
 * The following predicates have been added to the list module:
diff -u library/array.m library/array.m
--- library/array.m	17 Jun 2009 04:17:23 -0000
+++ library/array.m	17 Jun 2009 04:43:36 -0000
@@ -328,6 +328,9 @@
 %:- mode array.fetch_items(array_ui, in, in) = out is det.
 :- mode array.fetch_items(in, in, in) = out is det.
 
+    % XXX We prefer users to call the new array.binary_search predicate
+    % instead of array.bsearch, which may be deprecated in later releases.
+    %
     % array.bsearch takes an array, an element to be matched and a comparison
     % predicate and returns the position of the first occurrence in the array
     % of an element which is equivalent to the given one in the ordering
@@ -342,6 +345,32 @@
 %:- mode array.bsearch(array_ui, in, in(comparison_func)) = out is det.
 :- mode array.bsearch(in, in, in(comparison_func)) = out is det.
 
+    % array.approx_binary_search(A, X, I) performs a binary search for an
+    % approximate match for X in array A, computing I as the result.  More
+    % specifically, if the call succeeds, then either A ^ elem(I) = X or
+    % A ^ elem(I) @< X and either X @< A ^ elem(I + 1) or I is the last index
+    % in A.
+    %
+    % array.binary_search(A, X, I) performs a binary search for an
+    % exact match for X in array A (i.e., it succeeds iff X = A ^ elem(I)).
+    %
+    % A must be sorted into ascending order, but may contain duplicates
+    % (the ordering must be with respect to the supplied comparison predicate
+    % if one is supplied, otherwise with respect to the Mercury standard
+    % ordering).
+    %
+:- pred array.approx_binary_search(array(T), T, int).
+:- mode array.approx_binary_search(array_ui, in, out) is semidet.
+
+:- pred array.approx_binary_search(comparison_func(T), array(T), T, int).
+:- mode array.approx_binary_search(in, array_ui, in, out) is semidet.
+
+:- pred array.binary_search(array(T), T, int).
+:- mode array.binary_search(array_ui, in, out) is semidet.
+
+:- pred array.binary_search(comparison_func(T), array(T), T, int).
+:- mode array.binary_search(in, array_ui, in, out) is semidet.
+
     % array.map(Closure, OldArray, NewArray) applies `Closure' to
     % each of the elements of `OldArray' to create `NewArray'.
     %
@@ -407,17 +436,6 @@
 %:- mode array.foldr(func(in, di) = uo is det, array_ui, di) = uo is det.
 :- mode array.foldr(func(in, di) = uo is det, in, di) = uo is det.
 
-    % array.binary_search(A, X, I) performs a binary search for X in array A,
-    % computing I as the result.  More specifically, if the call succeeds, then
-    % either A ^ elem(I) = X or I is the largest index of A such that
-    % A ^ elem(I) @< X and either X @< A ^ elem(I + 1) or I is the last index
-    % in A.
-    %
-    % A must be sorted into ascending order (but may contain duplicates).
-    %
-:- pred array.binary_search(array(T), T, int).
-:- mode array.binary_search(array_ui, in, out) is semidet.
-
     % array.random_permutation(A0, A, RS0, RS) permutes the elements in
     % A0 given random seed RS0 and returns the permuted array in A
     % and the next random seed in RS.
@@ -1488,20 +1506,30 @@
 %------------------------------------------------------------------------------%
 
 array.binary_search(A, X, I) :-
+    array.binary_search(ordering, A, X, I).
+
+array.binary_search(Cmp, A, X, I) :-
+    array.approx_binary_search(Cmp, A, X, I),
+    A ^ elem(I) = X.
+
+array.approx_binary_search(A, X, I) :-
+    array.approx_binary_search(ordering, A, X, I).
+
+array.approx_binary_search(Cmp, A, X, I) :-
     Lo = 0,
     Hi = array.size(A) - 1,
-    binary_search_2(A, X, Lo, Hi, I).
+    approx_binary_search_2(Cmp, A, X, Lo, Hi, I).
 
-:- pred binary_search_2(array(T), T, int, int, int).
-:- mode binary_search_2(array_ui, in, in, in, out) is semidet.
+:- pred approx_binary_search_2(comparison_func(T), array(T), T, int, int, int).
+:- mode approx_binary_search_2(in, array_ui, in, in, in, out) is semidet.
 
-binary_search_2(A, X, Lo, Hi, I) :-
+approx_binary_search_2(Cmp, A, X, Lo, Hi, I) :-
     Lo =< Hi,
     Mid = (Lo + Hi) / 2,
-    O = ordering(A ^ elem(Mid), X),
+    O = Cmp(A ^ elem(Mid), X),
     (
         O = (>),
-        binary_search_2(A, X, Lo, Mid - 1, I)
+        approx_binary_search_2(Cmp, A, X, Lo, Mid - 1, I)
     ;
         O = (=),
         I = Mid
@@ -1510,7 +1538,7 @@
         ( if Mid < Hi, X @< A ^ elem(Mid + 1) then
             I = Mid
           else
-            binary_search_2(A, X, Mid + 1, Hi, I)
+            approx_binary_search_2(Cmp, A, X, Mid + 1, Hi, I)
         )
     ).
 
--------------------------------------------------------------------------
mercury-reviews mailing list
Post messages to:       mercury-reviews at csse.unimelb.edu.au
Administrative Queries: owner-mercury-reviews at csse.unimelb.edu.au
Subscriptions:          mercury-reviews-request at csse.unimelb.edu.au
--------------------------------------------------------------------------