Commit | Line | Data |
---|---|---|
7f918cf1 CE |
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 |