1 | == Integer Mappings |
---|
2 | |
---|
3 | This library defines fixnum mappings (fxmappings), which are immutable |
---|
4 | structures that define a set of associations between fixnums (exact |
---|
5 | integers) and arbitrary Scheme objects. The interface is compliant with |
---|
6 | [[https://srfi.schemers.org/srfi-224/srfi-224.html|SRFI 224]]. |
---|
7 | |
---|
8 | Integer maps are implemented as immutable radix trees, as described by |
---|
9 | Chris Okasaki and Andrew Gill in |
---|
10 | [[http://ittc.ku.edu/~andygill/papers/IntMap98.pdf|"Fast Mergeable Integer Maps"]]. |
---|
11 | These provide fast lookup and set-theoretical operations. |
---|
12 | |
---|
13 | [[toc:]] |
---|
14 | |
---|
15 | == Library |
---|
16 | |
---|
17 | === Notation |
---|
18 | |
---|
19 | The following names are used for the parameters of procedures: |
---|
20 | <table> |
---|
21 | <tr><td><em>obj</em></td><td>Any Scheme object.</td></tr> |
---|
22 | <tr><td><em>boolean</em></td><td>A boolean.</td></tr> |
---|
23 | <tr><td><em>fxmap</em></td><td>A fxmapping with values of arbitrary type.</td></tr> |
---|
24 | <tr><td><em>k</em></td><td>A fixnum, satisfying {{fixnum?}}.</td></tr> |
---|
25 | <tr><td><em>list</em></td><td>A proper list.</td></tr> |
---|
26 | <tr><td><em>alist</em></td><td>An association list.</td></tr> |
---|
27 | <tr><td><em>proc</em></td><td>A procedure.</td></tr> |
---|
28 | <tr><td><em>pred</em></td><td>A predicate, assumed to entail no side-effects.</td></tr> |
---|
29 | <tr><td><em>comp</em></td><td>A SRFI 128 comparator object.</td></tr> |
---|
30 | </table> |
---|
31 | It is an error (unless otherwise noted) if the procedures are passed arguments |
---|
32 | that do not have the type implied by the argument names. |
---|
33 | |
---|
34 | === Non-local control flow |
---|
35 | |
---|
36 | The procedures in this library fully support exceptions, continuable |
---|
37 | exceptions, first-class continuations, and other forms of non-local control |
---|
38 | flow. In particular, if multiple returns occur from a higher-order procedure, |
---|
39 | such as {{fxmapping-unfold}}, then the values returned by earlier returns are |
---|
40 | not mutated. |
---|
41 | |
---|
42 | === Constructors |
---|
43 | |
---|
44 | <procedure>(fxmapping kâ objâ kâ âŠ) â fxmapping</procedure> |
---|
45 | |
---|
46 | Constructs a fxmapping from the given arguments, which alternate between keys |
---|
47 | and values (which are arbitrary Scheme objects); the resulting fxmapping is |
---|
48 | newly allocated and contains these (''k'', ''obj'') associations. The number of |
---|
49 | arguments must be even. If duplicate keys occur in the arguments, earlier |
---|
50 | associations take priority. |
---|
51 | |
---|
52 | Examples: |
---|
53 | |
---|
54 | <enscript highlight="scheme"> |
---|
55 | (fxmapping->alist (fxmapping 0 'a 1 'b 2 'c)) â ((0 . a) (1 . b) (2 . c)) |
---|
56 | (fxmapping->alist (fxmapping -10 "worf" -10 "yar")) â ((-10 . "worf")) |
---|
57 | </enscript> |
---|
58 | |
---|
59 | <procedure>(fxmapping-unfold stop? mapper successor seedâ seedâ âŠ) â fxmapping</procedure> |
---|
60 | |
---|
61 | The arguments have the following types: |
---|
62 | |
---|
63 | * ''stop?'' : {{* * âŠ â *-or-false}} |
---|
64 | * ''mapper'' : {{* * âŠ â fixnum *}} |
---|
65 | * ''successor'' : {{* * âŠ â * * âŠ}} |
---|
66 | * ''seed''â, ''seed''â, âŠ : {{*}} |
---|
67 | |
---|
68 | The ''stop?'', ''mapper'', and ''successor'' procedures must accept as many |
---|
69 | arguments as there are ''seed'' parameters. In addition, the number of values |
---|
70 | returned by the ''successor'' procedure must agree with the number of arguments |
---|
71 | expected by ''mapper''; that is, the expression |
---|
72 | |
---|
73 | <enscript highlight="scheme"> |
---|
74 | (call-with-values |
---|
75 | (lambda () (successor seedâ seedâ âŠ )) |
---|
76 | mapper) |
---|
77 | </enscript> |
---|
78 | |
---|
79 | must result in a valid procedure application. |
---|
80 | |
---|
81 | Unfold a fxmapping from the initial ''seed''s. ''mapper'' is applied to the |
---|
82 | ''seed''s and returns two values, a key and an associated value, which are |
---|
83 | adjoined to the new fxmapping. ''successor'' maps the ''seed''s to new seeds. |
---|
84 | Unfolding terminates when the predicate ''stop?'' returns a true value when |
---|
85 | applied to the current seeds. The resulting fxmapping is newly allocated. |
---|
86 | |
---|
87 | It is an error for the number of seeds to vary between steps of the unfolding |
---|
88 | process. If different steps of this process produce associations with the same |
---|
89 | key, then the first such association takes precedence. |
---|
90 | |
---|
91 | Example: |
---|
92 | <enscript highlight="scheme"> |
---|
93 | (fxmapping->alist |
---|
94 | (fxmapping-unfold (lambda (i) (= i 4)) |
---|
95 | (lambda (i) (values i (make-string i #\a))) |
---|
96 | (lambda (i) (+ i 1)) |
---|
97 | 0)) |
---|
98 | â ((0 . "") (1 . "a") (2 . "aa") (3 . "aaa")) |
---|
99 | </enscript> |
---|
100 | <procedure>(fxmapping-accumulate proc seedâ seedâ âŠ) â fxmapping</procedure> |
---|
101 | |
---|
102 | The arguments have the following types: |
---|
103 | |
---|
104 | * ''proc'' : {{(* âŠ â fxmapping * âŠ) * * âŠ â fixnum * * * âŠ}} |
---|
105 | * ''seed''â, ''seed''â, âŠ : {{*}} |
---|
106 | |
---|
107 | Similar to {{fxmapping-unfold}}, except that a single procedure |
---|
108 | controls the unfolding of a new fxmapping. Let ''n'' be the number of |
---|
109 | ''seed''s. ''proc'' is applied to a procedure ''abort-with-result'' |
---|
110 | and the ''seed''s, in that order, and is expected to return ''n'' + 2 |
---|
111 | values: a key (fixnum), an associated value, and ''n'' new seed |
---|
112 | values. The key/value association is added to the new fxmapping, and |
---|
113 | unfolding continues with the new seeds. If, instead, |
---|
114 | ''abort-with-result'' is invoked on any number of arbitrary values, |
---|
115 | then the current continuation is discarded and the new fxmapping along |
---|
116 | with the arguments passed to ''abort-with-result'' are delivered as |
---|
117 | multiple values to the continuation that was in effect when |
---|
118 | {{fxmapping-accumulate}} was called. |
---|
119 | |
---|
120 | It is an error for the number of seeds to vary between steps of the |
---|
121 | unfolding process. If different steps of this process produce |
---|
122 | associations with the same key, then the first such association takes |
---|
123 | precedence. |
---|
124 | |
---|
125 | Example: |
---|
126 | <enscript highlight="scheme"> |
---|
127 | (let-values (((fxmap s) |
---|
128 | (fxmapping-accumulate |
---|
129 | (lambda (abort-with-result i) |
---|
130 | (if (< i -3) |
---|
131 | (abort-with-result 'finished) |
---|
132 | (values i (square i) (- i 1)))) |
---|
133 | -1))) |
---|
134 | (values (fxmapping->alist fxmap) s)) |
---|
135 | â ((-3 . 9) (-2 . 4) (-1 . 1)) |
---|
136 | finished |
---|
137 | </enscript> |
---|
138 | |
---|
139 | === Predicates |
---|
140 | |
---|
141 | <procedure>(fxmapping? obj) â boolean</procedure> |
---|
142 | |
---|
143 | Returns {{#t}} if and only if ''obj'' is a fxmapping. |
---|
144 | |
---|
145 | <procedure>(fxmapping-contains? fxmap k) â boolean</procedure> |
---|
146 | |
---|
147 | Returns {{#t}} if and only if ''fxmap'' contains an association for key ''k''. |
---|
148 | |
---|
149 | Examples: |
---|
150 | |
---|
151 | <enscript highlight="scheme"> |
---|
152 | (fxmapping-contains? (fxmapping 1 'b) 1) â #t |
---|
153 | (fxmapping-contains? (fxmapping 1 'b) 0) â #f |
---|
154 | </enscript> |
---|
155 | |
---|
156 | <procedure>(fxmapping-empty? fxmap) â boolean</procedure> |
---|
157 | |
---|
158 | Returns {{#t}} if and only if ''fxmap'' contains no associations. |
---|
159 | |
---|
160 | Examples: |
---|
161 | |
---|
162 | <enscript highlight="scheme"> |
---|
163 | (fxmapping-empty? (alist->fxmapping '())) â #t |
---|
164 | (fxmapping-empty? (alist->fxmapping '((0 . a)))) â #f |
---|
165 | </enscript> |
---|
166 | |
---|
167 | <procedure>(fxmapping-disjoint? fxmapâ fxmapâ) â boolean</procedure> |
---|
168 | |
---|
169 | Returns {{#t}} if and only if ''fxmap''â and ''fxmap''â have no keys in common. |
---|
170 | |
---|
171 | Examples: |
---|
172 | |
---|
173 | <enscript highlight="scheme"> |
---|
174 | (fxmapping-disjoint? (fxmapping 0 'a) (fxmapping 1 'b)) â #t |
---|
175 | (fxmapping-disjoint? (fxmapping 1 '(b)) (fxmapping 1 'b)) â #f |
---|
176 | </enscript> |
---|
177 | |
---|
178 | === Accessors |
---|
179 | |
---|
180 | <procedure>(fxmapping-ref fxmap k [ failure [ success ] ]) â * âŠ</procedure> |
---|
181 | |
---|
182 | The optional ''failure'' parameter is a procedure of type {{[] â * âŠ}}. The |
---|
183 | optional ''success'' parameter is a procedure of type {{* â * âŠ}}. ''success'' |
---|
184 | defaults to {{values}}. |
---|
185 | |
---|
186 | If an association (''k'', ''v'') occurs in ''fxmap'', then ''success'' is invoked |
---|
187 | in tail context on ''v'' and its values are returned. If ''k'' does not have an |
---|
188 | association in ''fxmap'' and ''failure'' is supplied, then it is invoked in tail |
---|
189 | context on no arguments and its values are returned. Otherwise, it is an |
---|
190 | error. |
---|
191 | |
---|
192 | Examples: |
---|
193 | |
---|
194 | <enscript highlight="scheme"> |
---|
195 | (fxmapping-ref (fxmapping 36864 'zap) 36864) â zap |
---|
196 | (fxmapping-ref (fxmapping 0 'a) 36864) â ; error |
---|
197 | (fxmapping-ref (fxmapping 0 "worf") 0 (lambda () #f) string-length) â 4 |
---|
198 | </enscript> |
---|
199 | |
---|
200 | <procedure>(fxmapping-ref/default fxmap k obj) â *</procedure> |
---|
201 | |
---|
202 | If an association (''k'', ''v'') occurs in ''fxmap'', returns ''v''. Otherwise, |
---|
203 | returns ''obj''. |
---|
204 | |
---|
205 | Examples: |
---|
206 | |
---|
207 | <enscript highlight="scheme"> |
---|
208 | (fxmapping-ref/default (fxmapping 36864 'zap) 36864 #f) â zap |
---|
209 | (fxmapping-ref/default (fxmapping 0 'a) 36864 #f) â #f |
---|
210 | </enscript> |
---|
211 | |
---|
212 | <procedure>(fxmapping-min fxmap) â fixnum *</procedure> |
---|
213 | |
---|
214 | Returns two values, the least key of ''fxmap'' and its associated value. It is |
---|
215 | an error if ''fxmap'' is empty. |
---|
216 | |
---|
217 | Example: |
---|
218 | |
---|
219 | <enscript highlight="scheme"> |
---|
220 | (fxmapping-min (fxmapping 0 'a 1 'b 2 'c)) â 0 a |
---|
221 | </enscript> |
---|
222 | |
---|
223 | <procedure>(fxmapping-max fxmap) â fixnum *</procedure> |
---|
224 | |
---|
225 | Returns two values, the greatest key of ''fxmap'' and its associated value. It |
---|
226 | is an error if ''fxmap'' is empty. |
---|
227 | |
---|
228 | Example: |
---|
229 | |
---|
230 | <enscript highlight="scheme"> |
---|
231 | (fxmapping-max (fxmapping 0 'a 1 'b 2 'c)) â 2 c |
---|
232 | </enscript> |
---|
233 | |
---|
234 | === Updaters |
---|
235 | |
---|
236 | <procedure>(fxmapping-adjoin fxmap kâ objâ kâ âŠ) â fxmapping</procedure> |
---|
237 | |
---|
238 | Returns a new fxmapping containing all of the associations of |
---|
239 | ''fxmap'' as well as the associations (''k''â, ''v''â), (''k''â, ''k''â), âŠ |
---|
240 | The number of key/value arguments must be even. |
---|
241 | |
---|
242 | If any of the keys already have associations in ''fxmap'', the old |
---|
243 | associations are preserved. |
---|
244 | |
---|
245 | <enscript highlight="scheme"> |
---|
246 | (fxmapping->alist (fxmapping-adjoin (fxmapping 1 'b) 0 'a)) |
---|
247 | â ((0 . a) (1 . b)) |
---|
248 | </enscript> |
---|
249 | |
---|
250 | <procedure>(fxmapping-adjoin/combinator fxmap proc kâ objâ kâ âŠ) â fxmapping</procedure> |
---|
251 | |
---|
252 | Similar to {{fxmapping-adjoin}}, except that duplicate associations |
---|
253 | are combined with ''proc'', which is a procedure of type {{* * â *}}. |
---|
254 | ''proc'' is called on the new and old values (in that order) associated |
---|
255 | with a duplicated key and is expected to return a value for the key. |
---|
256 | For example, if ''fxmap'' contains the association (''k'', ''v''â), then |
---|
257 | the value of {{(fxmapping-adjoin/combinator}} ''fxmap f k v''â{{)}} will |
---|
258 | be a fxmapping with the association (''k'', (''f k v''â ''v''â)). |
---|
259 | |
---|
260 | Example: |
---|
261 | |
---|
262 | <enscript highlight="scheme"> |
---|
263 | (fxmapping->alist |
---|
264 | (fxmapping-adjoin/combinator (fxmapping 0 "geordi" 1 "reginald") |
---|
265 | (lambda (_ last first) |
---|
266 | (string-append first " " last)) |
---|
267 | 0 "laforge" |
---|
268 | 1 "barclay")) |
---|
269 | â ((0 . "geordi laforge") (1 . "reginald barclay")) |
---|
270 | </enscript> |
---|
271 | |
---|
272 | <procedure>(fxmapping-set fxmap kâ objâ kâ âŠ) â fxmapping</procedure> |
---|
273 | |
---|
274 | {{fxmapping-set}} is the same as {{fxmapping-adjoin}}, except that any |
---|
275 | existing associations for ''k''â, ''k''â, âŠ are replaced. |
---|
276 | |
---|
277 | Example: |
---|
278 | |
---|
279 | <enscript highlight="scheme"> |
---|
280 | (fxmapping->alist |
---|
281 | (fxmapping-set (fxmapping 0 "geordi" 1 "reginald") 1 "tasha")) |
---|
282 | â ((0 . "geordi") (1 . "tasha")) |
---|
283 | </enscript> |
---|
284 | |
---|
285 | <procedure>(fxmapping-adjust fxmap k proc) â fxmapping</procedure> |
---|
286 | |
---|
287 | The ''proc'' parameter is a procedure of type {{fixnum * â *}}. |
---|
288 | |
---|
289 | Returns a new fxmapping in which the association (''k'', ''v'') in |
---|
290 | ''fxmap'' is replaced by (''k'', (''proc k v'')). If ''k'' has no |
---|
291 | association in ''fxmap'', then a fxmapping with the same associations |
---|
292 | as ''fxmap'' is returned. |
---|
293 | |
---|
294 | Example: |
---|
295 | <enscript highlight="scheme"> |
---|
296 | (fxmapping->alist |
---|
297 | (fxmapping-adjust (fxmapping 64 "var") |
---|
298 | 64 |
---|
299 | (lambda (k s) (string-append s (number->string k))))) |
---|
300 | â ((64 . "var64")) |
---|
301 | </enscript> |
---|
302 | |
---|
303 | <procedure>(fxmapping-delete fxmap kâ kâ âŠ) â fxmapping</procedure> |
---|
304 | |
---|
305 | Returns a new fxmapping with the same associations as ''fxmap'', except |
---|
306 | those for keys equal to ''k''â, ''k''â, âŠ. |
---|
307 | |
---|
308 | Example: |
---|
309 | <enscript highlight="scheme"> |
---|
310 | (fxmapping->alist (fxmapping-delete (fxmapping 0 -200 1 -100) 0)) |
---|
311 | â ((1 . -100)) |
---|
312 | </enscript> |
---|
313 | |
---|
314 | <procedure>(fxmapping-delete-all fxmap list) â fxmapping</procedure> |
---|
315 | |
---|
316 | Returns a new fxmapping with the same associations as ''fxmap'', except |
---|
317 | those for keys equal to an element of ''list''. |
---|
318 | |
---|
319 | <enscript highlight="scheme"> |
---|
320 | (fxmapping->alist (fxmapping-delete-all (fxmapping 0 'a 1 'b 2 'c) '(1 2))) |
---|
321 | â ((0 . a)) |
---|
322 | </enscript> |
---|
323 | |
---|
324 | <procedure>(fxmapping-update fxmap k proc [ failure ]) â * âŠ</procedure> |
---|
325 | |
---|
326 | ''proc'' is a procedure of type {{fixnum * (* â fxmapping) ([] â fxmapping) â * âŠ}}. |
---|
327 | If the optional ''failure'' parameter is provided, then it must be a |
---|
328 | procedure of type {{[] â * âŠ}}. |
---|
329 | |
---|
330 | Updates the association for ''k'' in ''fxmap'' as follows. If ''k'' has an |
---|
331 | association in ''fxmap'', then ''proc'' is invoked in tail context on ''k'', its |
---|
332 | associated value, and two procedure arguments, ''replace'' and ''delete'', and its |
---|
333 | values are returned. Invoking ''replace'' on a value ''v'' returns a fxmapping |
---|
334 | with the association (''k'', ''v'') and all of ''fxmap'''s other associations. |
---|
335 | Invoking ''delete'' returns a fxmapping with all of the associations of ''fxmap'', |
---|
336 | but without an association for ''k''. If ''k'' has no association in ''fxmap'' and |
---|
337 | ''failure'' is provided, then ''failure'' is invoked in tail context on no |
---|
338 | arguments and its values are returned. Otherwise, it is an error. |
---|
339 | |
---|
340 | Note that, in contrast to similar Scheme forms, ''proc'' is not required to |
---|
341 | tail-call one of ''delete'' or ''replace'', and that {{fxmapping-update}} simply |
---|
342 | returns the results of invoking ''proc'' (assuming ''k'' is found). Thus, the |
---|
343 | following is valid: |
---|
344 | |
---|
345 | <enscript highlight="scheme"> |
---|
346 | (fxmapping-update (fxmapping 0 'a 1 'b 2 'c) |
---|
347 | 1 |
---|
348 | (lambda (k v replace _del) |
---|
349 | (values k v (fxmapping->alist (replace 'z))))) |
---|
350 | â 1 |
---|
351 | b |
---|
352 | ((0 . a) (1 . z) (2 . c)) |
---|
353 | </enscript> |
---|
354 | |
---|
355 | Simple versions of several other update operations may be defined in |
---|
356 | terms of {{fxmapping-update}}, e.g.: |
---|
357 | |
---|
358 | <enscript highlight="scheme"> |
---|
359 | (fxmapping-delete fxmap k) |
---|
360 | â¡ |
---|
361 | (fxmapping-update fxmap k (lambda (_k _v _r delete) (delete))) |
---|
362 | |
---|
363 | (fxmapping-set fxmap k v) |
---|
364 | â¡ |
---|
365 | (fxmapping-update fxmap k (lambda (_k _u replace _d) (replace v))) |
---|
366 | </enscript> |
---|
367 | |
---|
368 | Examples: |
---|
369 | |
---|
370 | <enscript highlight="scheme"> |
---|
371 | ;; Delete the association for 1 if its value is a symbol. |
---|
372 | (fxmapping->alist |
---|
373 | (fxmapping-update (fxmapping 0 'a 1 'b 2 'c) |
---|
374 | 1 |
---|
375 | (lambda (_k v replace delete) |
---|
376 | (if (symbol? v) |
---|
377 | (delete) |
---|
378 | (replace v))))) |
---|
379 | â ((0 . a) (2 . c)) |
---|
380 | |
---|
381 | (fxmapping->alist |
---|
382 | (fxmapping-update (fxmapping 0 'a 1 'b 2 'c) |
---|
383 | 1 |
---|
384 | (lambda (k _v replace _d) |
---|
385 | (replace k))))) |
---|
386 | â ((0 . a) (1 . 1) (2 . c)) |
---|
387 | </enscript> |
---|
388 | |
---|
389 | <procedure>(fxmapping-alter fxmap k failure success) â * âŠ</procedure> |
---|
390 | |
---|
391 | ''failure'' is a procedure of type |
---|
392 | {{(* â fxmapping) ([] â fxmapping) â * âŠ}}. |
---|
393 | ''success'' is a procedure of type |
---|
394 | {{fixnum * (* â fxmapping) ([] â fxmapping) â * âŠ}}. |
---|
395 | |
---|
396 | Updates the association, or lack thereof, for ''k'' in ''fxmap'' as |
---|
397 | follows. If the association (''k'', ''v'') exists in ''fxmap'', then |
---|
398 | ''success'' is invoked in tail context on ''k'', ''v'', and two |
---|
399 | procedure arguments, ''replace'' and ''delete'', and its values are |
---|
400 | returned. |
---|
401 | |
---|
402 | * Invoking (''replace vâ²'') returns a fxmapping with the association (''k'', ''vâ²'') as well as all of ''fxmap'''s other associations. |
---|
403 | * Invoking (''delete'') returns a fxmapping with all of ''fxmap'''s associations except for (''k'', ''v''). |
---|
404 | |
---|
405 | If no association for ''k'' exists in ''fxmap'', then ''failure'' is |
---|
406 | invoked in tail context on two procedure arguments, ''insert'' and |
---|
407 | ''ignore'', and its values are returned. |
---|
408 | |
---|
409 | * Invoking (''insert u'') returns a fxmapping with all of the associations of ''fxmap'' as well as (''k'', ''u''). |
---|
410 | * Invoking (''ignore'') returns a fxmapping with the same associations as ''fxmap''. |
---|
411 | |
---|
412 | Note that, in contrast to similar Scheme forms, ''failure'' and |
---|
413 | ''success'' are not required to tail-call one of their procedure |
---|
414 | arguments, and that {{fxmapping-alter}} simply returns the results of |
---|
415 | invoking ''failure'' or ''success''. Thus, the following is valid: |
---|
416 | |
---|
417 | <enscript highlight="scheme"> |
---|
418 | ;; Returns an additional boolean value indicating |
---|
419 | ;; whether the fxmapping was updated. |
---|
420 | (fxmapping-alter (fxmapping 0 'a 1 'b 2 'c) |
---|
421 | 1 |
---|
422 | (lambda (_ins ignore) |
---|
423 | (values (ignore) #f)) |
---|
424 | (lambda (_k _v replace _del) |
---|
425 | (values (replace 'z) #t))) |
---|
426 | â <fxmapping> |
---|
427 | #t |
---|
428 | </enscript> |
---|
429 | |
---|
430 | Examples: |
---|
431 | <enscript highlight="scheme"> |
---|
432 | ;; Insert an association for 4 if it's not present. |
---|
433 | (fxmapping->alist |
---|
434 | (fxmapping-alter (fxmapping 0 'a 1 'b) |
---|
435 | 4 |
---|
436 | (lambda (insert _ig) (insert 'e)) |
---|
437 | (lambda (_k v replace _del) |
---|
438 | (replace v)))) ; keep original value |
---|
439 | â ((0 . a) (1 . b) (4 . e)) |
---|
440 | #t |
---|
441 | |
---|
442 | ;; Delete an association for 1 if its value is a symbol. |
---|
443 | (fxmapping->alist |
---|
444 | (fxmapping-alter (fxmapping 0 'a 1 'b) |
---|
445 | 1 |
---|
446 | (lambda (_ins ignore) (ignore)) |
---|
447 | (lambda (_k v replace delete) |
---|
448 | (if (symbol? v) |
---|
449 | (delete) |
---|
450 | (replace v))))) |
---|
451 | â ((0 . a)) |
---|
452 | </enscript> |
---|
453 | |
---|
454 | <procedure>(fxmapping-delete-min fxmap) â fxmapping</procedure> |
---|
455 | <procedure>(fxmapping-delete-max fxmap) â fxmapping</procedure> |
---|
456 | |
---|
457 | Returns a new fxmapping with the same associations as ''fxmap'', except |
---|
458 | for the association with the least/greatest key. It is an error if |
---|
459 | ''fxmap'' is empty. |
---|
460 | |
---|
461 | Examples: |
---|
462 | <enscript highlight="scheme"> |
---|
463 | (fxmapping-delete-min (fxmapping 0 'a 1 'b 2 'c)) â ((1 . b) (2 . c)) |
---|
464 | (fxmapping-delete-max (fxmapping 0 'a 1 'b 2 'c)) â ((0 . a) (1 . b)) |
---|
465 | </enscript> |
---|
466 | |
---|
467 | <procedure>(fxmapping-update-min fxmap proc) â * âŠ</procedure> |
---|
468 | <procedure>(fxmapping-update-max fxmap proc) â * âŠ</procedure> |
---|
469 | |
---|
470 | The ''proc'' argument of {{fxmapping-update-min}} and {{-max}} is of |
---|
471 | type {{fixnum * (* â fxmapping) ([] â fxmapping) â * âŠ}}. |
---|
472 | |
---|
473 | Updates the association of ''fxmap'' with the least/greatest key ''k'' as follows. |
---|
474 | ''proc'' is invoked in tail context on ''k'', its associated value, and two |
---|
475 | procedure arguments, ''replace'' and ''delete'', and its values are returned. |
---|
476 | Invoking ''replace'' on a value ''v'' returns a fxmapping with the association |
---|
477 | (''k'', ''v'') and all of ''fxmap'''s other associations. Invoking ''delete'' returns |
---|
478 | a fxmapping with all of the associations of ''fxmap'', but without an |
---|
479 | association for ''k''. It is an error if ''fxmap'' is empty. |
---|
480 | |
---|
481 | Note that, in contrast to similar Scheme forms, ''proc'' is not required to |
---|
482 | tail-call one of ''delete'' or ''replace'', and that {{fxmapping-update-min}} and |
---|
483 | {{-max}} simply return the results of invoking ''proc''. Thus, the following is |
---|
484 | valid: |
---|
485 | |
---|
486 | <enscript highlight="scheme"> |
---|
487 | (fxmapping-update-min (fxmapping 0 'a 1 'b 2 'c) |
---|
488 | (lambda (k v _r delete) |
---|
489 | (values k v (fxmapping->alist (delete))))) |
---|
490 | â 0 |
---|
491 | a |
---|
492 | ((1 . b) (2 . c)) |
---|
493 | </enscript> |
---|
494 | |
---|
495 | Examples: |
---|
496 | |
---|
497 | <enscript highlight="scheme"> |
---|
498 | (fxmapping->alist |
---|
499 | (fxmapping-update-min (fxmapping -5 "phaser" -1 "tricorder") |
---|
500 | (lambda (_ v replace delete) |
---|
501 | (if (symbol? v) |
---|
502 | (replace v) |
---|
503 | (delete))))) |
---|
504 | â ((-1 . "tricorder")) |
---|
505 | |
---|
506 | (fxmapping->alist |
---|
507 | (fxmapping-update-max (fxmapping -5 "phaser" -1 "tricorder") |
---|
508 | (lambda (k v replace delete) |
---|
509 | (if (and (negative? k) (string? v)) |
---|
510 | (replace (string-length v)) |
---|
511 | (delete))))) |
---|
512 | â ((-5 . "phaser") (-1 . 9)) |
---|
513 | </enscript> |
---|
514 | |
---|
515 | <procedure>(fxmapping-pop-min fxmap) â fixnum * fxmapping</procedure> |
---|
516 | <procedure>(fxmapping-pop-max fxmap) â fixnum * fxmapping</procedure> |
---|
517 | |
---|
518 | Returns three values, ''k'', ''v'', and ''fxmapâ²'', where (''k'', ''v'') is the |
---|
519 | association of ''fxmap'' with the least/greatest key and ''fxmapâ²'' is a fxmapping |
---|
520 | containing all of the associations of ''fxmap'' except for (''k'', ''v''). It is an |
---|
521 | error if ''fxmap'' is empty. |
---|
522 | |
---|
523 | Example: |
---|
524 | <enscript highlight="scheme"> |
---|
525 | (let-values (((k v fxmap) |
---|
526 | (fxmapping-pop-min (fxmapping 0 'a 1 'b 2 'c)))) |
---|
527 | (values k v (fxmapping->alist fxmap))) |
---|
528 | â (0 a ((1 . b) (2 . c))) |
---|
529 | </enscript> |
---|
530 | |
---|
531 | === The whole fxmapping |
---|
532 | |
---|
533 | <procedure>(fxmapping-size fxmap) â fixnum</procedure> |
---|
534 | |
---|
535 | Returns the number of associations in ''fxmap''. |
---|
536 | |
---|
537 | <procedure>(fxmapping-find pred fxmap failure [ success ]) â * âŠ</procedure> |
---|
538 | |
---|
539 | ''pred'' is a predicate of type {{fixnum * â boolean}}. ''failure'' is a procedure |
---|
540 | of type {{[] â * âŠ}}. If the optional ''success'' parameter is supplied, then |
---|
541 | it must be a procedure of type {{fixnum * â * âŠ}}. ''success'' defaults to |
---|
542 | {{values}}. |
---|
543 | |
---|
544 | Invokes ''success'' in tail context on ''k'' and ''v'' and returns it results, where |
---|
545 | (''k'', ''v'') is the association of ''fxmap'' with the least key such that |
---|
546 | (''pred k v'') is true. If there is no such association, then |
---|
547 | ''failure'' is tail-called with no arguments and its results |
---|
548 | are returned. |
---|
549 | |
---|
550 | Examples: |
---|
551 | |
---|
552 | <enscript highlight="scheme"> |
---|
553 | (fxmapping-find (lambda (_ v) (even? v)) |
---|
554 | (fxmapping 0 1 1 2 2 4 3 8) |
---|
555 | (lambda () (values #f #f))) |
---|
556 | â 1 2 |
---|
557 | |
---|
558 | (fxmapping-find (lambda (_ v) (negative? v)) |
---|
559 | (fxmapping 0 1 1 2 2 4 3 8) |
---|
560 | (lambda () (values 'nope 'nada))) |
---|
561 | â nope nada |
---|
562 | |
---|
563 | (fxmapping-find (lambda (k s) (= k (string-length s))) |
---|
564 | (fxmapping 2 "worf" 3 "data" 4 "troi") |
---|
565 | (lambda () (error "not found")) |
---|
566 | list) |
---|
567 | â (4 "troi") |
---|
568 | </enscript> |
---|
569 | |
---|
570 | <procedure>(fxmapping-count pred fxmap) â fixnum</procedure> |
---|
571 | |
---|
572 | ''pred'' is a predicate of type {{fixnum * â boolean}}. |
---|
573 | |
---|
574 | Returns the number of associations in ''fxmap'' that satisfy ''pred'' |
---|
575 | (in the sense of {{fxmapping-find}}). |
---|
576 | |
---|
577 | Examples: |
---|
578 | |
---|
579 | <enscript highlight="scheme"> |
---|
580 | (fxmapping-count (lambda (_ v) (even? v)) |
---|
581 | (fxmapping 0 1 1 2 2 4 3 8)) â 3 |
---|
582 | (fxmapping-count (lambda (k s) (= k (string-length s))) |
---|
583 | (fxmapping 0 "x" 1 "y" 2 "z")) |
---|
584 | â 1 |
---|
585 | </enscript> |
---|
586 | |
---|
587 | <procedure>(fxmapping-any? pred fxmap) â boolean</procedure> |
---|
588 | |
---|
589 | ''pred'' is a predicate of type {{fixnum * â boolean}}. |
---|
590 | |
---|
591 | Returns {{#t}} if and only if there exists an association in ''fxmap'' |
---|
592 | that satisfies ''pred'' (in the sense of {{fxmapping-find}}). ''fxmap'' |
---|
593 | is traversed in ascending numerical order of keys. |
---|
594 | |
---|
595 | Example: |
---|
596 | <enscript highlight="scheme"> |
---|
597 | (fxmapping-any? (lambda (_ v) (odd? v)) |
---|
598 | (fxmapping 0 1 1 2 2 4 3 8)) â #t |
---|
599 | </enscript> |
---|
600 | |
---|
601 | <procedure>(fxmapping-every? pred fxmap) â boolean</procedure> |
---|
602 | |
---|
603 | ''pred'' is a predicate of type {{fixnum * â boolean}}. |
---|
604 | |
---|
605 | Returns {{#t}} if and only every association in ''fxmap'' satisfies |
---|
606 | ''pred'' (in the sense of {{fxmapping-find}}), or if ''fxmap'' is |
---|
607 | empty. ''fxmap'' is traversed in ascending numerical order of keys. |
---|
608 | |
---|
609 | Example: |
---|
610 | |
---|
611 | <enscript highlight="scheme"> |
---|
612 | (fxmapping-every? (lambda (_ v) (integer? v)) |
---|
613 | (fxmapping 0 1 1 2 2 4 3 8)) â #t |
---|
614 | </enscript> |
---|
615 | |
---|
616 | === Traversal |
---|
617 | |
---|
618 | <procedure>(fxmapping-map proc fxmap) â fxmapping</procedure> |
---|
619 | |
---|
620 | The ''proc'' argument of {{fxmapping-map}} is of type {{fixnum * â *}}. |
---|
621 | |
---|
622 | Returns a fxmapping with the same keys as ''fxmap'' whose values are the result |
---|
623 | of transforming the values of ''fxmap'' with ''proc''. For each association (''k, |
---|
624 | v'') in ''fxmap'', the association (''k'', (''proc k v'')) is added to the |
---|
625 | resulting fxmapping. The dynamic order of the applications of ''proc'' to the |
---|
626 | elements of ''fxmap'' is unspecified. |
---|
627 | |
---|
628 | Examples: |
---|
629 | |
---|
630 | <enscript highlight="scheme"> |
---|
631 | (fxmapping->alist |
---|
632 | (fxmapping-map (lambda (_ s) (string-length s)) |
---|
633 | (fxmapping 0 "picard" 1 "riker" 2 "troi"))) |
---|
634 | â ((0 . 6) (1 . 5) (2 . 4)) |
---|
635 | |
---|
636 | (fxmapping->alist |
---|
637 | (fxmapping-map (lambda (k s) |
---|
638 | (string-append s (number->string k))) |
---|
639 | (fxmapping 256 "x" 512 "y" 1024 "z"))) |
---|
640 | â ((256 . "x256") (512 . "y512") (1024 . "z1024")) |
---|
641 | </enscript> |
---|
642 | |
---|
643 | <procedure>(fxmapping-for-each proc fxmap) â unspecified</procedure> |
---|
644 | |
---|
645 | ''proc'' is a procedure of type {{fixnum * â *}}. |
---|
646 | |
---|
647 | Calls ''proc'' on the key and value of each association in ''fxmap'' and returns |
---|
648 | an unspecified value. ''fxmap'' in traversed in ascending numerical |
---|
649 | order of keys. |
---|
650 | |
---|
651 | Example: |
---|
652 | <enscript highlight="scheme"> |
---|
653 | (let ((sum 0)) |
---|
654 | (fxmapping-for-each (lambda (_ v) (set! sum (+ sum v))) |
---|
655 | (fxmapping 0 1 1 2 2 4 3 8)) |
---|
656 | sum) |
---|
657 | â 15 |
---|
658 | </enscript> |
---|
659 | |
---|
660 | <procedure>(fxmapping-fold kons knil fxmap) â *</procedure> |
---|
661 | <procedure>(fxmapping-fold-right kons knil fxmap) â *</procedure> |
---|
662 | |
---|
663 | The ''kons'' argument of {{fxmapping-fold}} and {{fxmapping-fold-right}} is a |
---|
664 | procedure of type {{fixnum * * â *}}. ''knil'' is an object of any type which can |
---|
665 | be passed to ''kons'' as its third argument. |
---|
666 | |
---|
667 | Folds ''kons'' over ''fxmap'', using ''knil'' as the base value. At each step, |
---|
668 | ''kons'' is applied to the key of an association, its associated value, and to |
---|
669 | the result of the last application. {{fxmapping-fold}} folds in ascending |
---|
670 | numerical order of keys; {{fxmapping-fold-right}} folds in descending order. |
---|
671 | |
---|
672 | Examples: |
---|
673 | <enscript highlight="scheme"> |
---|
674 | (fxmapping-fold-right (lambda (_ v vs) (cons v vs)) |
---|
675 | '() |
---|
676 | (fxmapping 0 "worf" 1 "data" 2 "crusher")) |
---|
677 | â ("worf" "data" "crusher") |
---|
678 | |
---|
679 | (fxmapping-fold (lambda (k _ ks) (cons k ks)) |
---|
680 | '() |
---|
681 | (fxmapping 0 "worf" 1 "data" 2 "crusher")) |
---|
682 | â (2 1 0) |
---|
683 | </enscript> |
---|
684 | |
---|
685 | <procedure>(fxmapping-map->list proc fxmap) â list</procedure> |
---|
686 | |
---|
687 | Efficient fusion of |
---|
688 | {{(fxmapping-values (fxmapping-map}} ''proc fxmap''{{))}}. |
---|
689 | |
---|
690 | Example: |
---|
691 | |
---|
692 | <enscript highlight="scheme"> |
---|
693 | (fxmapping-map->list (lambda (_ v) (string-length v)) |
---|
694 | (fxmapping 0 "picard" 1 "riker" 2 "troi")) |
---|
695 | â (6 5 4) |
---|
696 | </enscript> |
---|
697 | |
---|
698 | <procedure>(fxmapping-relation-map proc fxmap) â fxmapping</procedure> |
---|
699 | |
---|
700 | ''proc'' must be a procedure of type {{fixnum * â fixnum *}}. |
---|
701 | |
---|
702 | Returns a fxmapping whose associations are the results of transforming |
---|
703 | both the keys and the values of ''fxmap'' with ''proc''. For each |
---|
704 | association (''k'', ''v'') in ''fxmap'', (''proc k v'') is evaluated |
---|
705 | to return a new key and a new value which are associated in the new |
---|
706 | fxmapping. Duplicate keys are replaced, but the results in this case |
---|
707 | are unpredictable; if ''proc'' is not injective, that is, if it |
---|
708 | produces multiple associations with the same key, then it is |
---|
709 | unspecified which one of these associations will be present in the |
---|
710 | resulting fxmapping. The dynamic order of the applications of |
---|
711 | ''proc'' to the elements of ''fxmap'' is unspecified. |
---|
712 | |
---|
713 | '''Rationale:''' {{fxmapping-relation-map}} corresponds to {{mapping-map}} |
---|
714 | from SRFI 146 and is provided primarily for compatibility with that |
---|
715 | SRFI. |
---|
716 | |
---|
717 | === Filter |
---|
718 | |
---|
719 | <procedure>(fxmapping-filter pred fxmap) â fxmapping</procedure> |
---|
720 | |
---|
721 | Returns a fxmapping containing all of the associations of ''fxmap'' |
---|
722 | that satisfy ''pred'' (in the sense of {{fxmapping-find}}). |
---|
723 | |
---|
724 | Example: |
---|
725 | |
---|
726 | <enscript highlight="scheme"> |
---|
727 | (fxmapping->alist |
---|
728 | (fxmapping-filter (lambda (_ v) (positive? v)) |
---|
729 | (fxmapping 0 2 1 -4 2 8 3 -16))) |
---|
730 | â ((0 . 2) (2 . 8)) |
---|
731 | </enscript> |
---|
732 | |
---|
733 | <procedure>(fxmapping-remove pred fxmap) â fxmapping</procedure> |
---|
734 | |
---|
735 | Returns a fxmapping containing all of the associations of ''fxmap'' |
---|
736 | that do not satisfy ''pred'' (in the sense of {{fxmapping-find}}). |
---|
737 | |
---|
738 | Example: |
---|
739 | <enscript highlight="scheme"> |
---|
740 | (fxmapping->alist |
---|
741 | (fxmapping-remove (lambda (_ v) (positive? v)) |
---|
742 | (fxmapping 0 2 1 -4 2 8 3 -16))) |
---|
743 | â ((1 . -4) (3 . -16)) |
---|
744 | </enscript> |
---|
745 | |
---|
746 | <procedure>(fxmapping-partition pred fxmap) â fxmapping fxmapping</procedure> |
---|
747 | |
---|
748 | Returns two fxmappings: the first contains all associations of ''fxmap'' |
---|
749 | that satisfy ''pred'' (in the sense of {{fxmapping-find}}), and the second |
---|
750 | contains those that do not. |
---|
751 | |
---|
752 | Example: |
---|
753 | <enscript highlight="scheme"> |
---|
754 | (let-values (((pos ~pos) |
---|
755 | (fxmapping-partition (lambda (_ v) (positive? v)) |
---|
756 | (fxmapping 0 2 1 -4 2 8 3 -16)))) |
---|
757 | (values (fxmapping->alist pos) |
---|
758 | (fxmapping->alist ~pos))) |
---|
759 | â ((0 . 2) (2 . 8)) |
---|
760 | ((1 . -4) (3 . -16)) |
---|
761 | </enscript> |
---|
762 | |
---|
763 | === Conversion |
---|
764 | |
---|
765 | <procedure>(fxmapping->alist fxmap) â alist[fixnum, *]</procedure> |
---|
766 | |
---|
767 | Returns an alist containing the associations of ''fxmap'' in increasing |
---|
768 | numerical order of key. |
---|
769 | |
---|
770 | Example: |
---|
771 | <enscript highlight="scheme"> |
---|
772 | (fxmapping->alist (fxmapping 1 'a 2 'b)) â ((1 . a) (2 . b)) |
---|
773 | </enscript> |
---|
774 | |
---|
775 | <procedure>(fxmapping->decreasing-alist fxmap) â alist[fixnum, *]</procedure> |
---|
776 | |
---|
777 | Identical to {{fxmapping->alist}}, except that the resulting alist |
---|
778 | contains the associations of ''fxmap'' in decreasing numerical order |
---|
779 | of key. |
---|
780 | |
---|
781 | Example: |
---|
782 | <enscript highlight="scheme"> |
---|
783 | (fxmapping->alist (fxmapping 1 'a 2 'b)) â ((2 . b) (1 . a)) |
---|
784 | </enscript> |
---|
785 | |
---|
786 | <procedure>(fxmapping-keys fxmap) â list[fixnum]</procedure> |
---|
787 | |
---|
788 | Returns the keys of ''fxmap'' as a list in ascending numerical order. |
---|
789 | |
---|
790 | Example: |
---|
791 | <enscript highlight="scheme"> |
---|
792 | (fxmapping-keys (fxmapping 137 'a -24 'b -5072 'c)) â (-5072 -24 137) |
---|
793 | </enscript> |
---|
794 | |
---|
795 | <procedure>(fxmapping-values fxmap) â list[*]</procedure> |
---|
796 | |
---|
797 | Returns the values of ''fxmap'' as a list in ascending numerical |
---|
798 | order of key. |
---|
799 | |
---|
800 | Example: |
---|
801 | <enscript highlight="scheme"> |
---|
802 | (fxmapping-values (fxmapping 0 "picard" 1 "riker" 2 "troi")) |
---|
803 | â ("picard" "riker" "troi") |
---|
804 | </enscript> |
---|
805 | |
---|
806 | <procedure>(fxmapping->generator fxmapping) â generator[pair(fixnum, *)]</procedure> |
---|
807 | |
---|
808 | Returns a [[srfi-158]] generator which produces the associations of |
---|
809 | ''fxmapping'' as key/value pairs in increasing order of key. |
---|
810 | |
---|
811 | Example: |
---|
812 | <enscript highlight="scheme"> |
---|
813 | (generator->list (fxmapping->generator (fxmapping 3 "yar" 2 "troi"))) |
---|
814 | â ((2 . "troi") (3 . "yar")) |
---|
815 | </enscript> |
---|
816 | |
---|
817 | <procedure>(fxmapping->decreasing-generator fxmapping) â generator[pair(fixnum, *)]</procedure> |
---|
818 | |
---|
819 | This is the same as {{fxmapping->generator}}, except that the associations of |
---|
820 | ''fxmapping'' are produced in decreasing order of key. |
---|
821 | |
---|
822 | Example: |
---|
823 | <enscript highlight="scheme"> |
---|
824 | (generator->list (fxmapping->decreasing-generator (fxmapping 3 "yar" 2 "troi"))) |
---|
825 | â ((3 . "yar") (2 . "troi")) |
---|
826 | </enscript> |
---|
827 | |
---|
828 | === Comparison |
---|
829 | |
---|
830 | Each of the following predicates takes a {{srfi-128}} comparator |
---|
831 | argument which is used to compare the values of the associations of |
---|
832 | two fxmappings. (Keys are always compared as if with {{=}}.) |
---|
833 | |
---|
834 | <procedure>(fxmapping=? comp fxmapâ fxmapâ fxmapâ âŠ) â boolean</procedure> |
---|
835 | |
---|
836 | Returns {{#t}} iff all of the ''fxmaps'' contain equal associations. Two |
---|
837 | associations are equal exactly when their keys are equal (in the sense |
---|
838 | of {{=}}) and if their values are equal in the sense of the equality |
---|
839 | predicate of ''comp''. |
---|
840 | |
---|
841 | Examples: |
---|
842 | <enscript highlight="scheme"> |
---|
843 | (fxmapping=? (make-default-comparator) |
---|
844 | (fxmapping 1 'a 2 'b) |
---|
845 | (fxmapping 2 'b 1 'a)) |
---|
846 | â #t |
---|
847 | |
---|
848 | (fxmapping=? (make-default-comparator) |
---|
849 | (fxmapping 1 'a 2 'b 3 'c) |
---|
850 | (fxmapping 2 'b 1 'a)) |
---|
851 | â #f |
---|
852 | </enscript> |
---|
853 | |
---|
854 | <procedure>(fxmapping<? comp fxmapâ fxmapâ fxmapâ âŠ) â boolean</procedure> |
---|
855 | <procedure>(fxmapping<=? comp fxmapâ fxmapâ fxmapâ âŠ) â boolean</procedure> |
---|
856 | <procedure>(fxmapping>? comp fxmapâ fxmapâ fxmapâ âŠ) â boolean</procedure> |
---|
857 | <procedure>(fxmapping>=? comp fxmapâ fxmapâ fxmapâ âŠ) â boolean</procedure> |
---|
858 | |
---|
859 | Returns {{#t}} iff each ''fxmap'' other than the last is a proper |
---|
860 | subset/subset/proper superset/superset of the following ''fxmap''. |
---|
861 | Values are compared using the equality predicate of ''comp''. |
---|
862 | |
---|
863 | Examples: |
---|
864 | <enscript highlight="scheme"> |
---|
865 | (fxmapping<? (make-default-comparator) |
---|
866 | (fxmapping 1 'a 2 'b) |
---|
867 | (fxmapping 2 'b 1 'a 3 'c)) |
---|
868 | â #t |
---|
869 | |
---|
870 | (fxmapping>? (make-default-comparator) |
---|
871 | (fxmapping 2 'b 1 "worf" 3 'c) |
---|
872 | (fxmapping 1 'a 2 'b)) |
---|
873 | â #f |
---|
874 | |
---|
875 | (fxmapping>=? (make-default-comparator) |
---|
876 | (fxmapping 2 'b 1 'a 3 'c) |
---|
877 | (fxmapping 1 'a 2 'b) |
---|
878 | (fxmapping 2 'b 1 'a) |
---|
879 | (fxmapping 1 'a)) |
---|
880 | â #t |
---|
881 | </enscript> |
---|
882 | |
---|
883 | === Set theory operations |
---|
884 | |
---|
885 | <procedure>(fxmapping-union fxmapâ fxmapâ fxmapâ âŠ) â fxmapping</procedure> |
---|
886 | <procedure>(fxmapping-intersection fxmapâ fxmapâ fxmapâ âŠ) â fxmapping</procedure> |
---|
887 | <procedure>(fxmapping-difference fxmapâ fxmapâ fxmapâ âŠ) â fxmapping</procedure> |
---|
888 | <procedure>(fxmapping-xor fxmapâ fxmapâ) â fxmapping</procedure> |
---|
889 | |
---|
890 | Return a fxmapping whose set of associations is the union, intersection, |
---|
891 | asymmetric difference, or symmetric difference of the sets of associations of |
---|
892 | the ''fxmaps''. Asymmetric difference is extended to more than two fxmappings by |
---|
893 | taking the difference between the first fxmapping and the union of the others. |
---|
894 | Symmetric difference is not extended beyond two fxmappings. When comparing |
---|
895 | associations, only the keys are compared. In case of duplicate keys, |
---|
896 | associations in the result fxmapping are drawn from the first fxmapping in |
---|
897 | which they appear. |
---|
898 | |
---|
899 | Examples: |
---|
900 | <enscript highlight="scheme"> |
---|
901 | (fxmapping->alist (fxmapping-union (fxmapping 0 'a 2 'c) |
---|
902 | (fxmapping 1 'b 3 'd))) |
---|
903 | â ((0 . a) (1 . b) (2 . c) (3 . d)) |
---|
904 | |
---|
905 | (fxmapping->alist |
---|
906 | (fxmapping-intersection (fxmapping 0 'a 2 'c) |
---|
907 | (fxmapping 1 'b 2 'c 3 'd) |
---|
908 | (fxmapping 2 'c 4 'e))) |
---|
909 | â ((2 . c)) |
---|
910 | |
---|
911 | (fxmapping->alist (fxmapping-difference (fxmapping 0 'a 1 'b 2 'c) |
---|
912 | (fxmapping 2 "worf") |
---|
913 | (fxmapping 1 "data"))) |
---|
914 | â ((0 . a)) |
---|
915 | </enscript> |
---|
916 | |
---|
917 | <procedure>(fxmapping-union/combinator proc fxmapâ fxmapâ fxmapâ âŠ) â fxmapping </procedure> |
---|
918 | <procedure>(fxmapping-intersection/combinator proc fxmapâ fxmapâ fxmapâ âŠ) â fxmapping</procedure> |
---|
919 | |
---|
920 | ''proc'' is a procedure of type {{fixnum * * â *}}. |
---|
921 | |
---|
922 | Return a fxmapping whose set of keys is the union/intersection of the sets of |
---|
923 | keys of the ''fxmaps''. The values associated with duplicate keys are combined |
---|
924 | left-associatively with ''proc'', which is also passed the duplicated key as its |
---|
925 | first argument; that is, if an integer ''k'' is associated with values ''v''â, |
---|
926 | ''v''â, âŠ, ''v''â in ''fxmap''â, ''fxmap''â, âŠ, ''fxmap''â, respectively, then the |
---|
927 | resulting fxmapping will contain the association (''k'', (''proc k'' âŠ (''proc k |
---|
928 | v''â ''v''â) âŠ ''v''â)). |
---|
929 | |
---|
930 | Examples: |
---|
931 | <enscript highlight="scheme"> |
---|
932 | ;; Right-biased union. |
---|
933 | (fxmapping->alist |
---|
934 | (fxmapping-union/combinator (lambda (_k _l r) r) |
---|
935 | (fxmapping 1 'b 2 'c) |
---|
936 | (fxmapping 2 "data" 3 "picard"))) |
---|
937 | |
---|
938 | â ((1 . b) (2 . "data") (3 . "picard")) |
---|
939 | |
---|
940 | (fxmapping->alist |
---|
941 | (fxmapping-intersection/combinator |
---|
942 | (lambda (_ l r) (string-append l " " r)) |
---|
943 | (fxmapping 1 "q" 3 "jean-luc" 5 "miles" 7 "quark") |
---|
944 | (fxmapping 3 "picard" 5 "o'brien"))) |
---|
945 | |
---|
946 | â ((3 . "jean-luc picard") (5 . "miles o'brien")) |
---|
947 | </enscript> |
---|
948 | |
---|
949 | === Submappings |
---|
950 | |
---|
951 | <procedure>(fxmapping-open-interval fxmap low high) â fxmapping</procedure> |
---|
952 | <procedure>(fxmapping-closed-interval fxmap low high) â fxmapping</procedure> |
---|
953 | <procedure>(fxmapping-open-closed-interval fxmap low high) â fxmapping</procedure> |
---|
954 | <procedure>(fxmapping-closed-open-interval fxmap low high) â fxmapping</procedure> |
---|
955 | |
---|
956 | ''low'' and ''high'' are both exact integers. |
---|
957 | |
---|
958 | Procedures that return a subset of ''fxmap'' containing the associations |
---|
959 | whose keys are contained in the interval from ''low'' to ''high''. The |
---|
960 | interval may be open, closed, open below and closed above, or open |
---|
961 | above and closed below. |
---|
962 | |
---|
963 | Examples: |
---|
964 | <enscript highlight="scheme"> |
---|
965 | (fxmapping->alist |
---|
966 | (fxmapping-open-interval (fxmapping 0 'a 1 'b 2 'c 3 'd) 1 3)) |
---|
967 | â ((2 . c)) |
---|
968 | |
---|
969 | (fxmapping->alist |
---|
970 | (fxmapping-closed-interval (fxmapping 0 'a 1 'b 2 'c 3 'd) 1 3)) |
---|
971 | â ((1 . b) (2 . c) (3 . d)) |
---|
972 | |
---|
973 | (fxmapping->alist |
---|
974 | (fxmapping-closed-open-interval (fxmapping 0 'a 1 'b 2 'c 3 'd) 1 3)) |
---|
975 | â ((1 . b) (2 . c)) |
---|
976 | </enscript> |
---|
977 | |
---|
978 | <procedure>(fxsubmapping= fxmap k) â fxmapping</procedure> |
---|
979 | <procedure>(fxsubmapping< fxmap k) â fxmapping</procedure> |
---|
980 | <procedure>(fxsubmapping<= fxmap k) â fxmapping</procedure> |
---|
981 | <procedure>(fxsubmapping> fxmap k) â fxmapping</procedure> |
---|
982 | <procedure>(fxsubmapping>= fxmap k) â fxmapping</procedure> |
---|
983 | |
---|
984 | Procedures that return a fxmapping containing the associations of |
---|
985 | ''fxmap'' whose keys are equal to, less than/less than or equal |
---|
986 | to/greater than/greater than or equal to ''k''. Note that the result of |
---|
987 | {{fxsubmapping=}} contains at most one element. |
---|
988 | |
---|
989 | Examples: |
---|
990 | <enscript highlight="scheme"> |
---|
991 | (fxmapping->alist |
---|
992 | (fxsubmapping= (fxmapping 0 'a 1 'b 2 'c 3 'd) 2)) |
---|
993 | â ((2 . c)) |
---|
994 | |
---|
995 | (fxmapping->alist |
---|
996 | (fxsubmapping< (fxmapping 0 'a 1 'b 2 'c 3 'd) 2)) |
---|
997 | â ((0 . a) (1 . b)) |
---|
998 | |
---|
999 | (fxmapping->alist |
---|
1000 | (fxsubmapping>= (fxmapping 0 'a 1 'b 2 'c 3 'd) 2)) |
---|
1001 | â ((2 . c) (3 . d)) |
---|
1002 | </enscript> |
---|
1003 | |
---|
1004 | <procedure>(fxmapping-split fxmap k) â fxmapping fxmapping</procedure> |
---|
1005 | |
---|
1006 | Returns two fxmappings. The first contains all of the associations of |
---|
1007 | ''fxmap'' whose keys are less than or equal to ''k'', and the second |
---|
1008 | contains the remaining associations. This is equivalent to |
---|
1009 | |
---|
1010 | <enscript highlight="scheme"> |
---|
1011 | (values (fxsubmapping<= fxmap k) (fxsubmapping> fxmap k)) |
---|
1012 | </enscript> |
---|
1013 | |
---|
1014 | but is implemented more efficiently. |
---|
1015 | |
---|
1016 | If ''fxmap'' is empty, then both of the fxmappings returned by |
---|
1017 | {{fxmapping-split}} are empty. |
---|
1018 | |
---|
1019 | Example: |
---|
1020 | <enscript highlight="scheme"> |
---|
1021 | (let-values ((fxmaps (fxmapping-split (fxmapping 0 'a 1 'b 2 'c 3 'd) 2))) |
---|
1022 | (map fxmapping->alist fxmaps)) |
---|
1023 | â (((0 . a) (1 . b) (2 . c)) |
---|
1024 | ((3 . d))) |
---|
1025 | </enscript> |
---|
1026 | |
---|
1027 | == About This Egg |
---|
1028 | |
---|
1029 | === Dependencies |
---|
1030 | |
---|
1031 | The following eggs are required: |
---|
1032 | |
---|
1033 | * [[srfi-1]] |
---|
1034 | * [[srfi-128]] |
---|
1035 | * [[srfi-143]] |
---|
1036 | * [[srfi-145]] |
---|
1037 | * [[srfi-158]] |
---|
1038 | |
---|
1039 | === Author |
---|
1040 | |
---|
1041 | Wolfgang Corcoran-Mathe |
---|
1042 | |
---|
1043 | Contact: {{<wcm at sigwinch dot xyzzy minus the zy>}} |
---|
1044 | |
---|
1045 | === Maintainer |
---|
1046 | |
---|
1047 | Wolfgang Corcoran-Mathe |
---|
1048 | |
---|
1049 | === Repository |
---|
1050 | |
---|
1051 | [[https://github.com/Zipheir/integer-map|GitHub]] |
---|
1052 | |
---|
1053 | === License |
---|
1054 | |
---|
1055 | Copyright (C) Wolfgang Corcoran-Mathe (2021). All rights reserved. |
---|
1056 | |
---|
1057 | Permission is hereby granted, free of charge, to any person obtaining |
---|
1058 | a copy of this software and associated documentation files (the |
---|
1059 | "Software"), to deal in the Software without restriction, including |
---|
1060 | without limitation the rights to use, copy, modify, merge, publish, |
---|
1061 | distribute, sublicense, and/or sell copies of the Software, and to |
---|
1062 | permit persons to whom the Software is furnished to do so, subject to |
---|
1063 | the following conditions: |
---|
1064 | |
---|
1065 | The above copyright notice and this permission notice shall be |
---|
1066 | included in all copies or substantial portions of the Software. |
---|
1067 | |
---|
1068 | THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, |
---|
1069 | EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF |
---|
1070 | MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. |
---|
1071 | IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY |
---|
1072 | CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION OF CONTRACT, |
---|
1073 | TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION WITH THE |
---|
1074 | SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE. |
---|
1075 | |
---|
1076 | === Version history |
---|
1077 | |
---|
1078 | ; 0.1 (2021-03-06) : Initial release. |
---|
1079 | ; 0.1.1 (2021-03-06) : Tests bugfix. |
---|
1080 | ; 0.1.2 (2021-03-06) : Bookkeeping bugfix. |
---|
1081 | ; 1.0.1 (2021-06-26) : Update to current SRFI 224, overhaul interface. |
---|
1082 | ; 1.0.2 (2021-06-26) : Remove types, which were difficult to understand and mostly useless. |
---|