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