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/hashMultimap.sml
ViewVC logotype

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

Parent Directory Parent Directory | Revision Log Revision Log


Revision 245 - (view) (download)
Original Path: sml/branches/SMLNJ/src/MLRISC/library/hashMultimap.sml

1 : monnier 245 structure HashMultimap :> HASH_MULTIMAP =
2 :     struct
3 :    
4 :     structure S = HashMap
5 :    
6 :     type ('a,'b) multimap = ('a,'b list) S.map * int ref
7 :    
8 :    
9 :     fun create x n = (S.create x n, ref 0)
10 :    
11 :     fun size (_,c) = !c
12 :     fun bucketSize (m,_) = S.bucketSize m
13 :     fun isEmpty (_,c) = !c = 0
14 :    
15 :     fun insert (m,c) (e as (x,y)) =
16 :     (S.update m ((x,[y]),fn ys => y::ys); c := !c + 1)
17 :    
18 :     fun removeAll (m,c) i =
19 :     let val stuff = S.lookup m i
20 :     in S.remove m i; c := !c - length stuff
21 :     end handle _ => ()
22 :    
23 :     fun update (m,c) (e as (x,ys)) =
24 :     let val stuff = S.lookupOrElse m [] x
25 :     in S.insert m e; c := !c - length stuff + length ys
26 :     end
27 :    
28 :     fun lookup (m,_) i = S.lookup m i
29 :    
30 :     fun contains (m,_) i = S.contains m i
31 :    
32 :     fun count (m,_) i = length(S.lookupOrElse m [] i)
33 :    
34 :     fun toList (m,_) = S.toList m
35 :    
36 :     fun toDupList (m,_) =
37 :     let fun collect (x,[],l) = l
38 :     | collect (x,h::t,l) = (x,h)::collect(x,t,l)
39 :     in
40 :     S.fold (fn ((x,ys),l) => collect (x,ys,l)) [] m
41 :     end
42 :    
43 :     fun clear (m,c) = (S.clear m; c := 0)
44 :    
45 :     fun dupApp f (m,_) =
46 :     let fun call (x,[]) = ()
47 :     | call (x,h::t) = (f(x,h); call(x,t))
48 :     in
49 :     S.app call m
50 :     end
51 :    
52 :     fun app f (m,_) = S.app f m
53 :    
54 :     fun dupFold f x (m,_) =
55 :     let fun collect((x,[]),l) = l
56 :     | collect((x,h::t),l) = collect((x,t),f((x,h),l))
57 :     in
58 :     S.fold collect x m
59 :     end
60 :    
61 :     fun fold f x (m,_) = S.fold f x m
62 :    
63 :     fun toString (f,g) m =
64 :     "{" ^
65 :     dupFold (fn ((x,y),"") => "(" ^ f x ^ ", " ^ g y ^ ")"
66 :     | ((x,y),l) => "(" ^ f x ^ ", " ^ g y ^ "), " ^ l)
67 :     "" m ^ "}"
68 :    
69 :     end
70 :    
71 :     (*
72 :     * $Log$
73 :     *)

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