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