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 /sml/trunk/src/MLRISC/library/hashSet.sml
ViewVC logotype

Annotation of /sml/trunk/src/MLRISC/library/hashSet.sml

Parent Directory Parent Directory | Revision Log Revision Log


Revision 412 - (view) (download)

1 : monnier 411 (*
2 :     * A set datatype that uses hashing
3 :     *
4 :     * -- Allen
5 :     *)
6 :    
7 : monnier 245 structure HashSet :> HASH_SET =
8 :     struct
9 :    
10 :     structure A = Array
11 :    
12 :     datatype 'a set =
13 :     SET of
14 :     { table : 'a list Array.array ref,
15 :     size : int ref,
16 :     order : 'a * 'a -> order,
17 :     hash : 'a -> int
18 :     }
19 :    
20 :     fun create { order, hash } N =
21 :     let val N = if N <= 10 then 10 else N
22 :     in
23 :     SET { table = ref(Array.array(N,[])),
24 :     size = ref 0,
25 :     order = order,
26 :     hash = hash
27 :     }
28 :     end
29 :    
30 :     fun size (SET { size, ... }) = !size
31 :    
32 :     fun bucketSize (SET { table, ... }) = Array.length (!table)
33 :    
34 :     fun isEmpty (SET { size, ... }) = !size = 0
35 :    
36 :     fun clear (SET { size, table, ... }) =
37 :     (table := A.array(A.length(!table),[]); size := 0)
38 :    
39 :     and insert (m as SET { size, table = ref T, order, hash,...}) x =
40 :     let val pos = hash x mod A.length T
41 :     val list = A.sub(T,pos)
42 :     fun ins [] = (size := !size + 1;
43 :     A.update(T,pos,x::list);
44 :     if !size > 6 * A.length T then grow m else ())
45 :     | ins (x'::rest) =
46 :     case order(x,x') of
47 :     EQUAL => ()
48 :     | _ => ins rest
49 :     in
50 :     ins list
51 :     end
52 :    
53 :     and grow (SET { size, table = table as ref T, order, hash, ... }) =
54 :     let val m2 as
55 :     SET{table = ref T',...} = create{ order=order, hash=hash }
56 :     (!size * 2 + 10)
57 :     in A.app (app (insert m2)) T; table := T'
58 :     end
59 :    
60 :     fun remove (SET { size, table = ref T, order, hash,...}) x =
61 :     let val pos = hash x mod A.length T
62 :     val list = A.sub(T,pos)
63 :     fun del ([],list) = ()
64 :     | del (x'::rest,list) =
65 :     case order(x,x') of
66 :     EQUAL => (size := !size - 1;
67 :     A.update(T,pos,rest@list)
68 :     )
69 :     | _ => del (rest,x'::list)
70 :    
71 :     in del(list,[])
72 :     end
73 :    
74 :     fun contains (SET { table = ref T, order, hash, ... }) x =
75 :     let val pos = hash x mod A.length T
76 :     fun find [] = false
77 :     | find (x'::rest) =
78 :     case order(x,x') of
79 :     EQUAL => true
80 :     | _ => find rest
81 :     in find(A.sub(T,pos))
82 :     end
83 :    
84 :     fun fold f x =
85 :     fn (SET { table = ref T, ... }) =>
86 :     A.foldl (fn (t,l) => List.foldl f l t) x T
87 :    
88 :     fun app f =
89 :     fn (SET { table = ref T, ... }) =>
90 :     A.app (List.app f) T
91 :    
92 :     fun toList set = fold (op::) [] set
93 :    
94 :     fun toString f set =
95 :     "{" ^ fold (fn (x,"") => f x
96 :     | (x,l) => f x ^ ", " ^ l
97 :     ) "" set ^ "}"
98 :    
99 :     end
100 :    

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