1(* ========================================================================= *)
2(* FINITE MAPS WITH A FIXED KEY TYPE                                         *)
3(* Copyright (c) 2004 Joe Hurd, distributed under the BSD License            *)
4(* ========================================================================= *)
5
6signature KeyMap =
7sig
8
9(* ------------------------------------------------------------------------- *)
10(* A type of map keys.                                                       *)
11(* ------------------------------------------------------------------------- *)
12
13type key
14
15val compareKey : key * key -> order
16
17val equalKey : key -> key -> bool
18
19(* ------------------------------------------------------------------------- *)
20(* A type of finite maps.                                                    *)
21(* ------------------------------------------------------------------------- *)
22
23type 'a map
24
25(* ------------------------------------------------------------------------- *)
26(* Constructors.                                                             *)
27(* ------------------------------------------------------------------------- *)
28
29val new : unit -> 'a map
30
31val singleton : key * 'a -> 'a map
32
33(* ------------------------------------------------------------------------- *)
34(* Map size.                                                                 *)
35(* ------------------------------------------------------------------------- *)
36
37val null : 'a map -> bool
38
39val size : 'a map -> int
40
41(* ------------------------------------------------------------------------- *)
42(* Querying.                                                                 *)
43(* ------------------------------------------------------------------------- *)
44
45val peekKey : 'a map -> key -> (key * 'a) option
46
47val peek : 'a map -> key -> 'a option
48
49val get : 'a map -> key -> 'a  (* raises Error *)
50
51val pick : 'a map -> key * 'a  (* an arbitrary key/value pair *)
52
53val nth : 'a map -> int -> key * 'a  (* in the range [0,size-1] *)
54
55val random : 'a map -> key * 'a
56
57(* ------------------------------------------------------------------------- *)
58(* Adding.                                                                   *)
59(* ------------------------------------------------------------------------- *)
60
61val insert : 'a map -> key * 'a -> 'a map
62
63val insertList : 'a map -> (key * 'a) list -> 'a map
64
65(* ------------------------------------------------------------------------- *)
66(* Removing.                                                                 *)
67(* ------------------------------------------------------------------------- *)
68
69val delete : 'a map -> key -> 'a map  (* must be present *)
70
71val remove : 'a map -> key -> 'a map
72
73val deletePick : 'a map -> (key * 'a) * 'a map
74
75val deleteNth : 'a map -> int -> (key * 'a) * 'a map
76
77val deleteRandom : 'a map -> (key * 'a) * 'a map
78
79(* ------------------------------------------------------------------------- *)
80(* Joining (all join operations prefer keys in the second map).              *)
81(* ------------------------------------------------------------------------- *)
82
83val merge :
84    {first : key * 'a -> 'c option,
85     second : key * 'b -> 'c option,
86     both : (key * 'a) * (key * 'b) -> 'c option} ->
87    'a map -> 'b map -> 'c map
88
89val union :
90    ((key * 'a) * (key * 'a) -> 'a option) ->
91    'a map -> 'a map -> 'a map
92
93val intersect :
94    ((key * 'a) * (key * 'b) -> 'c option) ->
95    'a map -> 'b map -> 'c map
96
97(* ------------------------------------------------------------------------- *)
98(* Set operations on the domain.                                             *)
99(* ------------------------------------------------------------------------- *)
100
101val inDomain : key -> 'a map -> bool
102
103val unionDomain : 'a map -> 'a map -> 'a map
104
105val unionListDomain : 'a map list -> 'a map
106
107val intersectDomain : 'a map -> 'a map -> 'a map
108
109val intersectListDomain : 'a map list -> 'a map
110
111val differenceDomain : 'a map -> 'a map -> 'a map
112
113val symmetricDifferenceDomain : 'a map -> 'a map -> 'a map
114
115val equalDomain : 'a map -> 'a map -> bool
116
117val subsetDomain : 'a map -> 'a map -> bool
118
119val disjointDomain : 'a map -> 'a map -> bool
120
121(* ------------------------------------------------------------------------- *)
122(* Mapping and folding.                                                      *)
123(* ------------------------------------------------------------------------- *)
124
125val mapPartial : (key * 'a -> 'b option) -> 'a map -> 'b map
126
127val map : (key * 'a -> 'b) -> 'a map -> 'b map
128
129val app : (key * 'a -> unit) -> 'a map -> unit
130
131val transform : ('a -> 'b) -> 'a map -> 'b map
132
133val filter : (key * 'a -> bool) -> 'a map -> 'a map
134
135val partition :
136    (key * 'a -> bool) -> 'a map -> 'a map * 'a map
137
138val foldl : (key * 'a * 's -> 's) -> 's -> 'a map -> 's
139
140val foldr : (key * 'a * 's -> 's) -> 's -> 'a map -> 's
141
142(* ------------------------------------------------------------------------- *)
143(* Searching.                                                                *)
144(* ------------------------------------------------------------------------- *)
145
146val findl : (key * 'a -> bool) -> 'a map -> (key * 'a) option
147
148val findr : (key * 'a -> bool) -> 'a map -> (key * 'a) option
149
150val firstl : (key * 'a -> 'b option) -> 'a map -> 'b option
151
152val firstr : (key * 'a -> 'b option) -> 'a map -> 'b option
153
154val exists : (key * 'a -> bool) -> 'a map -> bool
155
156val all : (key * 'a -> bool) -> 'a map -> bool
157
158val count : (key * 'a -> bool) -> 'a map -> int
159
160(* ------------------------------------------------------------------------- *)
161(* Comparing.                                                                *)
162(* ------------------------------------------------------------------------- *)
163
164val compare : ('a * 'a -> order) -> 'a map * 'a map -> order
165
166val equal : ('a -> 'a -> bool) -> 'a map -> 'a map -> bool
167
168(* ------------------------------------------------------------------------- *)
169(* Converting to and from lists.                                             *)
170(* ------------------------------------------------------------------------- *)
171
172val keys : 'a map -> key list
173
174val values : 'a map -> 'a list
175
176val toList : 'a map -> (key * 'a) list
177
178val fromList : (key * 'a) list -> 'a map
179
180(* ------------------------------------------------------------------------- *)
181(* Pretty-printing.                                                          *)
182(* ------------------------------------------------------------------------- *)
183
184val toString : 'a map -> string
185
186(* ------------------------------------------------------------------------- *)
187(* Iterators over maps.                                                      *)
188(* ------------------------------------------------------------------------- *)
189
190type 'a iterator
191
192val mkIterator : 'a map -> 'a iterator option
193
194val mkRevIterator : 'a map -> 'a iterator option
195
196val readIterator : 'a iterator -> key * 'a
197
198val advanceIterator : 'a iterator -> 'a iterator option
199
200end
201