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

SCM Repository

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

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

Parent Directory Parent Directory | Revision Log Revision Log


Revision 2144 - (download) (annotate)
Thu Nov 2 16:23:11 2006 UTC (12 years, 9 months ago) by blume
File size: 1087 byte(s)
moved smlnj-lib to toplevel
(* bsearch-fn.sml
 *
 * COPYRIGHT (c) 1994 by AT&T Bell Laboratories.  See COPYRIGHT file for details.
 *
 * Binary searching on sorted monomorphic arrays.
 *)

functor BSearchFn (A : MONO_ARRAY) : sig

    structure A : MONO_ARRAY

    val bsearch : (('a * A.elem) -> order)
	  -> ('a * A.array) -> (int * A.elem) option
	(* binary search on ordered monomorphic arrays. The comparison function
	 * cmp embeds a projection function from the element type to the key
	 * type.
	 *)

  end = struct

    structure A = A

  (* binary search on ordered monomorphic arrays. The comparison function
   * cmp embeds a projection function from the element type to the key
   * type.
   *)
    fun bsearch cmp (key, arr) = let
	  fun look (lo, hi) = 
                if hi >= lo then let
		  val m = lo + (hi - lo) div 2
		  val x = A.sub(arr, m)
		  in
	 	    case cmp(key, x)
		    of LESS => look(lo, m-1)
		     | EQUAL => (SOME(m, x))
		     | GREATER => look(m+1, hi)
		    (* end case *)
		  end
                else NONE
	  in
	    look (0, A.length arr - 1)
	  end

  end; (* BSearch *)


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