| 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 | (* This code is not working -- it is not even in sources.cm *) |
| 10 | signature HASH_TABLE = |
| 11 | sig |
| 12 | type ('a, 'b) t |
| 13 | |
| 14 | val fold: ('a, 'b) t * 'c * ('b * 'c -> 'c) -> 'c |
| 15 | val foldi: ('a, 'b) t * 'c * ('a * 'b * 'c -> 'c) -> 'c |
| 16 | val forall: ('a, 'b) t * ('b -> bool) -> bool |
| 17 | val foralli: ('a, 'b) t * ('a * 'b -> bool) -> bool |
| 18 | val foreach: ('a, 'b) t * ('b -> unit) -> unit |
| 19 | val foreachi: ('a, 'b) t * ('a * 'b -> unit) -> unit |
| 20 | (* If it's already in the table, call the thunk, else insert it and |
| 21 | * return it. |
| 22 | *) |
| 23 | val insertIfNew: ('a, 'b) t * 'a * 'b * (unit -> 'b) -> 'b |
| 24 | val listItems: ('a, 'b) t -> 'b list |
| 25 | val listItemsi: ('a, 'b) t -> ('a * 'b) list |
| 26 | val layout: ('a * 'b -> Layout.t) -> ('a, 'b) t -> Layout.t |
| 27 | val lookupOrInsert: ('a, 'b) t * 'a * (unit -> 'b) -> 'b |
| 28 | val map: ('a, 'b) t * ('b -> 'c) -> ('a, 'c) t |
| 29 | val mapi: ('a, 'b) t * ('a * 'b -> 'c) -> ('a, 'c) t |
| 30 | val new: {equals: 'a * 'a -> bool, |
| 31 | hash: 'a -> word} -> ('a, 'b) t |
| 32 | val peek: ('a, 'b) t * 'a -> 'b option |
| 33 | val size: ('a, 'b) t -> int |
| 34 | val stats: unit -> Layout.t |
| 35 | val update: ('a, 'b) t * 'a * 'b -> unit |
| 36 | end |
| 37 | |
| 38 | functor TestHashTable (S: HASH_TABLE): sig end = |
| 39 | struct |
| 40 | |
| 41 | open S |
| 42 | |
| 43 | val _ = |
| 44 | Assert.assert |
| 45 | ("TestHashTable", fn () => |
| 46 | let val t = new Int.equals |
| 47 | val n = 10 |
| 48 | val hash = Word.fromInt |
| 49 | val _ = |
| 50 | Int.for(0, n, fn i => |
| 51 | (lookupOrInsert(t, hash i, i, fn () => i * 2) |
| 52 | ; ())) |
| 53 | val sum = Int.fold(0, n, 0, op +) |
| 54 | in |
| 55 | let val r = ref 0 |
| 56 | in foreach (t, fn j => r := !r + j) |
| 57 | ; 2 * sum = !r |
| 58 | end |
| 59 | andalso Int.forall(0, n, fn i => Option.isSome(peek(t, hash i, i))) |
| 60 | andalso foralli(t, fn (i, j) => j = 2 * i) |
| 61 | andalso n = List.length(listItems t) |
| 62 | andalso n = List.length(listItemsi t) |
| 63 | andalso let val t' = map(t, fn j => j div 2) |
| 64 | in n = size t' |
| 65 | andalso foralli(t', fn (i, j) => i = j) |
| 66 | end |
| 67 | andalso n = size t |
| 68 | end) |
| 69 | |
| 70 | end |