Debian Codegraph @

src/core/Map.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 code is translated from OCaml ExtLib PMap
25 Copyright (C) 1996-2003 Xavier Leroy, Nicolas Cannasse, Markus Mottl
26 */
27
28 type ('k, 'v) map {
29 Empty;
30 Node : (('k, 'v) map , 'k , 'v , ('k, 'v) map , int);
31 }
32
33 type ('k, 'v) t {
34 cmp : 'k -> 'k -> int;
35 map : ('k, 'v) map;
36 }
37
38 function height(m) {
39 match m {
40 | Node (_, _, _, _, h) -> h
41 | Empty -> 0
42 }
43 }
44
45 function make(l,k,v,r) {
46 Node(l, k, v, r, max (height l) (height r) + 1)
47 }
48
49 function bal(l,k,v,r) {
50 var hl = height l;
51 var hr = height r;
52 if hl > hr + 2 then
53 match l {
54 | Node (ll,lk,lv,lr,_) ->
55 if height ll >= height lr then make ll lk lv (make lr k v r)
56 else match lr {
57 | Node (lrl,lrk,lrv,lrr,_) ->
58 make (make ll lk lv lrl) lrk lrv (make lrr k v r)
59 | Empty -> assert()
60 }
61 | Empty -> assert()
62 }
63 else if hr > hl + 2 then
64 match r {
65 | Node (rl,rk,rv,rr,_) ->
66 if height rr >= height rl then make (make l k v rl) rk rv rr
67 else match rl {
68 | Node (rll, rlk, rlv, rlr, _) ->
69 make (make l k v rll) rlk rlv (make rlr rk rv rr)
70 | Empty -> assert()
71 }
72 | Empty -> assert()
73 }
74 else Node(l, k, v, r, max hl hr + 1)
75 }
76
77 function rec min_binding(m) {
78 match m {
79 | Node (Empty, k, v, _, _) -> (k, v)
80 | Node (l, _, _, _, _) -> min_binding l
81 | Empty -> throw Not_found
82 }
83 }
84
85 function rec remove_min_binding(m) {
86 match m {
87 | Node (Empty, _, _, r, _) -> r
88 | Node (l, k, v, r, _) -> bal (remove_min_binding l) k v r
89 | Empty -> invalid_arg()
90 }
91 }
92
93 function merge(t1,t2) {
94 match (t1, t2) {
95 | (Empty, _) -> t2
96 | (_, Empty) -> t1
97 | _ ->
98 var k, v = min_binding t2;
99 bal t1 k v (remove_min_binding t2)
100 }
101 }
102
103 function create(cmp) {
104 {
105 cmp = cmp;
106 map = Empty;
107 }
108 }
109
110 function empty() {
111 {
112 cmp = compare;
113 map = Empty;
114 }
115 }
116
117 function is_empty(m) {
118 m.map == Empty
119 }
120
121 function add(m,x,d) {
122 var cmp = m.cmp;
123 function rec loop(m) {
124 match m {
125 | Node (l, k, v, r, h) ->
126 var c = cmp x k;
127 if c == 0 then Node(l, x, d, r, h)
128 else if c < 0 then {
129 var nl = loop l;
130 bal nl k v r;
131 } else {
132 var nr = loop r;
133 bal l k v nr
134 }
135 | Empty ->
136 Node(Empty, x, d, Empty, 1)
137 }
138 };
139 {
140 cmp = cmp;
141 map = loop m.map;
142 }
143 }
144
145 function find(m,x) {
146 var cmp = m.cmp;
147 function rec loop(m) {
148 match m {
149 | Node (l, k, v, r, _) ->
150 var c = cmp x k;
151 if c < 0 then loop l
152 else if c > 0 then loop r
153 else v
154 | Empty ->
155 throw Not_found
156 }
157 };
158 loop m.map
159 }
160
161 function remove(m,x) {
162 var cmp = m.cmp;
163 function rec loop(m) {
164 match m {
165 | Node(l, k, v, r, _) ->
166 var c = cmp x k;
167 if c == 0 then merge l r else
168 if c < 0 then bal (loop l) k v r else bal l k v (loop r)
169 | Empty -> Empty
170 }
171 };
172 {
173 cmp = cmp;
174 map = loop m.map;
175 }
176 }
177
178 function exists(m,x) {
179 var cmp = m.cmp;
180 function rec loop(m) {
181 match m {
182 | Node (l, k, v, r, _) ->
183 var c = cmp x k;
184 c == 0 || loop (if c < 0 then l else r)
185 | Empty -> false
186 }
187 };
188 loop m.map
189 }
190
191 function iter(f,m) {
192 function rec loop(m) {
193 match m {
194 | Empty -> ()
195 | Node (l, k, v, r, _) ->
196 loop l;
197 f k v;
198 loop r
199 }
200 };
201 loop m.map
202 }
203
204 function map(f,m) {
205 function rec loop(m) {
206 match m {
207 | Empty -> Empty
208 | Node (l, k, v, r, h) ->
209 var l = loop l;
210 var r = loop r;
211 Node(l, k, f v, r, h)
212 }
213 };
214 {
215 cmp = m.cmp;
216 map = loop m.map;
217 }
218 }
219
220 function fold(f,m,acc) {
221 function rec loop(acc,m) {
222 match m {
223 | Empty -> acc
224 | Node (l, k, v, r, _) ->
225 loop (f (loop acc l) v) r
226 }
227 };
228 loop acc m.map
229 }
230