Debian Codegraph @

src/core/Set.nml

raw
1 /*
2 * Copyright (C)2005-2022 Haxe Foundation
3 *
4 * Permission is hereby granted, free of charge, to any person obtaining a
5 * copy of this software and associated documentation files (the "Software"),
6 * to deal in the Software without restriction, including without limitation
7 * the rights to use, copy, modify, merge, publish, distribute, sublicense,
8 * and/or sell copies of the Software, and to permit persons to whom the
9 * Software is furnished to do so, subject to the following conditions:
10 *
11 * The above copyright notice and this permission notice shall be included in
12 * all copies or substantial portions of the Software.
13 *
14 * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
15 * IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
16 * FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE
17 * AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
18 * LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING
19 * FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER
20 * DEALINGS IN THE SOFTWARE.
21 */
22
23 /*
24 This is very similar to PMap except that it does only store one value
25 */
26
27 type 'a set {
28 Empty;
29 Node : ('a set, 'a ,'a set, int);
30 }
31
32 type 'a t {
33 cmp : 'a -> 'a -> int;
34 set : 'a set;
35 }
36
37 /* -------- tools ----------- */
38
39 function height(s) {
40 match s {
41 | Empty -> 0
42 | Node(_, _, _, h) -> h
43 }
44 }
45
46 function make(l,v,r) {
47 Node(l, v, r, max (height l) (height r) + 1)
48 }
49
50 function bal(l,v,r) {
51 var hl = height l;
52 var hr = height r;
53 if hl > hr + 2 then
54 match l {
55 | Node (ll,lv,lr,_) ->
56 if height ll >= height lr then
57 make ll lv (make lr v r)
58 else match lr {
59 | Node (lrl,lrv,lrr,_) ->
60 make (make ll lv lrl) lrv (make lrr v r)
61 | Empty -> assert()
62 }
63 | Empty -> assert()
64 }
65 else if hr > hl + 2 then
66 match r {
67 | Node (rl,rv,rr,_) ->
68 if height rr >= height rl then
69 make (make l v rl) rv rr
70 else match rl {
71 | Node (rll, rlv, rlr, _) ->
72 make (make l v rll) rlv (make rlr rv rr)
73 | Empty -> assert()
74 }
75 | Empty -> assert()
76 }
77 else
78 Node l v r (max hl hr + 1)
79 }
80
81
82 function rec remove_min_elt(s) {
83 match s {
84 | Empty -> assert()
85 | Node(Empty, v, r, _) -> r
86 | Node(l, v, r, _) -> bal (remove_min_elt l) v r
87 }
88 }
89
90 function rec min_elt(s) {
91 match s {
92 | Empty -> throw Not_found
93 | Node(Empty, v, r, _) -> v
94 | Node(l, v, r, _) -> min_elt l
95 }
96 }
97
98 function merge(t1,t2) {
99 match (t1, t2) {
100 | (Empty, t) -> t
101 | (t, Empty) -> t
102 | _ -> bal t1 (min_elt t2) (remove_min_elt t2)
103 }
104 }
105
106 function rec add_loop(cmp,x,s) {
107 match s {
108 | Empty ->
109 Node(Empty,x,Empty,1)
110 | Node(l, v, r, _) ->
111 var c = cmp x v;
112 if c == 0 then
113 s
114 else if c < 0 then
115 bal (add_loop cmp x l) v r
116 else
117 bal l v (add_loop cmp x r)
118 }
119 }
120
121 function rec join(cmp,l,v,r) {
122 match (l, r) {
123 | (Empty, _) -> add_loop cmp v r
124 | (_, Empty) -> add_loop cmp v l
125 | (Node(ll, lv, lr, lh), Node(rl, rv, rr, rh)) ->
126 if lh > rh + 2 then bal ll lv (join cmp lr v r) else
127 if rh > lh + 2 then bal (join cmp l v rl) rv rr else
128 make l v r
129 | _ -> assert()
130 }
131 }
132
133 function concat(cmp,t1,t2) {
134 match (t1, t2) {
135 | (Empty, t) -> t
136 | (t, Empty) -> t
137 | _ ->
138 join cmp t1 (min_elt t2) (remove_min_elt t2)
139 }
140 }
141
142 function rec split(cmp,x,s) {
143 match s {
144 | Empty ->
145 (Empty, false, Empty)
146 | Node(l, v, r, _) ->
147 var c = cmp x v;
148 if c == 0 then
149 (l, true, r)
150 else if c < 0 then {
151 var ll, pres, rl = split cmp x l;
152 (ll, pres, join cmp rl v r)
153 } else {
154 var lr, pres, rr = split cmp x r;
155 (join cmp l v lr, pres, rr)
156 }
157 }
158 }
159
160
161 /* ---------- api ----------- */
162
163 function rec add(set : 'a t, x : 'a) {
164 {
165 cmp = set.cmp;
166 set = add_loop set.cmp x set.set;
167 }
168 }
169
170 function create(cmp) {
171 {
172 cmp = cmp;
173 set = Empty;
174 }
175 }
176
177 function empty() {
178 {
179 cmp = compare;
180 set = Empty;
181 }
182 }
183
184 function is_empty(s) {
185 match s.set {
186 | Empty -> true
187 | _ -> false
188 }
189 }
190
191 function exists(set,x) {
192 function rec loop(s) {
193 match s {
194 | Empty -> false
195 | Node(l, v, r, _) ->
196 var c = set.cmp x v;
197 c == 0 || loop (if c < 0 then l else r)
198 }
199 }
200 loop set.set
201 }
202
203 function remove(set,x) {
204 function rec loop(s) {
205 match s {
206 | Empty -> Empty
207 | Node(l, v, r, _) ->
208 var c = set.cmp x v;
209 if c == 0 then merge l r else
210 if c < 0 then bal (loop l) v r else bal l v (loop r)
211 }
212 }
213 {
214 cmp = set.cmp;
215 set = loop set.set;
216 }
217 }
218
219 function union(set1,set2) {
220 var cmp = set1.cmp;
221 function rec loop(s1,s2) {
222 match (s1, s2) {
223 | (Empty, t2) -> t2
224 | (t1, Empty) -> t1
225 | (Node(l1, v1, r1, h1), Node(l2, v2, r2, h2)) ->
226 if h1 >= h2 then
227 if h2 == 1 then
228 add_loop cmp v2 s1
229 else {
230 var l2, _, r2 = split cmp v1 s2;
231 join cmp (loop l1 l2) v1 (loop r1 r2)
232 }
233 else
234 if h1 == 1 then
235 add_loop cmp v1 s2
236 else {
237 var l1, _, r1 = split cmp v2 s1;
238 join cmp (loop l1 l2) v2 (loop r1 r2)
239 }
240 | _ ->
241 assert()
242 }
243 }
244 {
245 cmp = cmp;
246 set = loop set1.set set2.set;
247 }
248 }
249
250 function inter(set1,set2) {
251 var cmp = set1.cmp;
252 function rec loop(s1,s2) {
253 match (s1, s2) {
254 | (Empty, t2) -> Empty
255 | (t1, Empty) -> Empty
256 | (Node(l1, v1, r1, _), t2) ->
257 match split cmp v1 t2 {
258 | (l2, false, r2) ->
259 concat cmp (loop l1 l2) (loop r1 r2)
260 | (l2, true, r2) ->
261 join cmp (loop l1 l2) v1 (loop r1 r2)
262 | _ ->
263 assert()
264 }
265 | _ ->
266 assert()
267 }
268 }
269 {
270 cmp = cmp;
271 set = loop set1.set set2.set;
272 }
273 }
274
275 function diff(set1,set2) {
276 var cmp = set1.cmp;
277 function rec loop(s1,s2) {
278 match (s1, s2) {
279 | (Empty, t2) -> Empty
280 | (t1, Empty) -> t1
281 | (Node(l1, v1, r1, _), t2) ->
282 match split cmp v1 t2 {
283 | (l2, false, r2) ->
284 join cmp (loop l1 l2) v1 (loop r1 r2)
285 | (l2, true, r2) ->
286 concat cmp (loop l1 l2) (loop r1 r2)
287 | _ ->
288 assert()
289 }
290 | _ ->
291 assert()
292 }
293 }
294 {
295 cmp = cmp;
296 set = loop set1.set set2.set;
297 }
298 }
299
300 function iter(f,set) {
301 function rec loop(s) {
302 match s {
303 | Empty -> ()
304 | Node(l, v, r, _) ->
305 loop l;
306 f v;
307 loop r
308 }
309 }
310 loop set.set
311 }