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