lib/mlton/basic/binary-search.sig

   1 (* Copyright (C) 2009 Matthew Fluet.
   2  * Copyright (C) 1999-2006 Henry Cejtin, Matthew Fluet, Suresh
   3  *    Jagannathan, and Stephen Weeks.
   4  *
   5  * MLton is released under a BSD-style license.
   6  * See the file MLton-LICENSE for details.
   7  *)
   8
   9 signature BINARY_SEARCH =
  10    sig
  11       (* largest(a, f)
  12        * Pre: if 0 <= i < j < Array.size a
  13        *         andalso f (Array.sub (a, j))
  14        *      then f (Array.sub (a, i))
  15        * Returns the largest i such that f (Array.sub (a, i))
  16        *)
  17       val largest: 'a array * ('a -> bool) -> int option
  18       val search: 'a array * ('a -> order) -> int option
  19       (* smallest(a, f)
  20        * Pre: if 0 <= i < j < Array.size a
  21        *         and f(Array.sub(a, i))
  22        *      then f(Array.sub(a, j)
  23        * Returns the smallest i such that f(Array.sub(a, i))
  24        *)
  25       val smallest: 'a array * ('a -> bool) -> int option
  26    end
  27
  28 functor TestBinarySearch (S: BINARY_SEARCH): sig end =
  29 struct
  30
  31 open S
  32
  33 val _ =
  34    Assert.assert
  35    ("TestBinarySearch", fn () =>
  36     let
  37        val n = 17
  38        val a = Array.fromList (Pervasive.List.tabulate (n, fn i => i))
  39     in Int.forall (0, n, fn i =>
  40                    SOME i = search (a, fn x => Int.compare (i, x)))
  41     end)
  42
  43 end