Home My Page Projects Code Snippets Project Openings SML/NJ
Summary Activity Forums Tracker Lists Tasks Docs Surveys News SCM Files

SCM Repository

[smlnj] Annotation of /smlnj-lib/trunk/Util/bsearch-fn.sml
ViewVC logotype

Annotation of /smlnj-lib/trunk/Util/bsearch-fn.sml

Parent Directory Parent Directory | Revision Log Revision Log


Revision 651 - (view) (download)
Original Path: sml/trunk/src/smlnj-lib/Util/bsearch-fn.sml

1 : monnier 2 (* bsearch-fn.sml
2 :     *
3 :     * COPYRIGHT (c) 1994 by AT&T Bell Laboratories. See COPYRIGHT file for details.
4 :     *
5 :     * Binary searching on sorted monomorphic arrays.
6 :     *)
7 :    
8 :     functor BSearchFn (A : MONO_ARRAY) : sig
9 :    
10 :     structure A : MONO_ARRAY
11 :    
12 :     val bsearch : (('a * A.elem) -> order)
13 :     -> ('a * A.array) -> (int * A.elem) option
14 :     (* binary search on ordered monomorphic arrays. The comparison function
15 :     * cmp embeds a projection function from the element type to the key
16 :     * type.
17 :     *)
18 :    
19 :     end = struct
20 :    
21 :     structure A = A
22 :    
23 :     (* binary search on ordered monomorphic arrays. The comparison function
24 :     * cmp embeds a projection function from the element type to the key
25 :     * type.
26 :     *)
27 :     fun bsearch cmp (key, arr) = let
28 :     fun look (lo, hi) =
29 :     if hi >= lo then let
30 :     val m = lo + (hi - lo) div 2
31 :     val x = A.sub(arr, m)
32 :     in
33 :     case cmp(key, x)
34 :     of LESS => look(lo, m-1)
35 :     | EQUAL => (SOME(m, x))
36 :     | GREATER => look(m+1, hi)
37 :     (* end case *)
38 :     end
39 :     else NONE
40 :     in
41 :     look (0, A.length arr - 1)
42 :     end
43 :    
44 :     end; (* BSearch *)
45 :    

root@smlnj-gforge.cs.uchicago.edu
ViewVC Help
Powered by ViewVC 1.0.0