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