source: project/wiki/eggref/5/integer-map @ 40218

Last change on this file since 40218 was 40218, checked in by Zipheir, 3 months ago

We still need srfi-158.

File size: 37.5 KB
Line 
1== Integer Mappings
2
3This library defines fixnum mappings (fxmappings), which are immutable
4structures that define a set of associations between fixnums (exact
5integers) and arbitrary Scheme objects.  The interface is compliant with
6[[https://srfi.schemers.org/srfi-224/srfi-224.html|SRFI 224]].
7
8Integer maps are implemented as immutable radix trees, as described by
9Chris Okasaki and Andrew Gill in
10[[http://ittc.ku.edu/~andygill/papers/IntMap98.pdf|"Fast Mergeable Integer Maps"]].
11These provide fast lookup and set-theoretical operations.
12
13[[toc:]]
14
15== Library
16
17=== Notation
18
19The 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>
31It is an error (unless otherwise noted) if the procedures are passed arguments
32that do not have the type implied by the argument names.
33
34=== Non-local control flow
35
36The procedures in this library fully support exceptions, continuable
37exceptions, first-class continuations, and other forms of non-local control
38flow. In particular, if multiple returns occur from a higher-order procedure,
39such as {{fxmapping-unfold}}, then the values returned by earlier returns are
40not mutated.
41
42=== Constructors
43
44<procedure>(fxmapping k₁ obj₁ k₂ 
) → fxmapping</procedure>
45
46Constructs a fxmapping from the given arguments, which alternate between keys
47and values (which are arbitrary Scheme objects); the resulting fxmapping is
48newly allocated and contains these (''k'', ''obj'') associations. The number of
49arguments must be even. If duplicate keys occur in the arguments, earlier
50associations take priority.
51
52Examples:
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
61The arguments have the following types:
62
63* ''stop?'' : {{* * 
 → *-or-false}}
64* ''mapper'' : {{* * 
 → fixnum *}}
65* ''successor'' : {{* * 
 → * * 
}}
66* ''seed''₁, ''seed''₂, 
 : {{*}}
67
68The ''stop?'', ''mapper'', and ''successor'' procedures must accept as many
69arguments as there are ''seed'' parameters. In addition, the number of values
70returned by the ''successor'' procedure must agree with the number of arguments
71expected 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
79must result in a valid procedure application.
80
81Unfold 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
83adjoined to the new fxmapping. ''successor'' maps the ''seed''s to new seeds.
84Unfolding terminates when the predicate ''stop?'' returns a true value when
85applied to the current seeds. The resulting fxmapping is newly allocated.
86
87It is an error for the number of seeds to vary between steps of the unfolding
88process. If different steps of this process produce associations with the same
89key, then the first such association takes precedence.
90
91Example:
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
102The arguments have the following types:
103
104* ''proc'' : {{(* 
 → fxmapping * 
) * * 
 → fixnum * * * 
}}
105* ''seed''₁, ''seed''₂, 
 : {{*}}
106
107Similar to {{fxmapping-unfold}}, except that a single procedure
108controls the unfolding of a new fxmapping.  Let ''n'' be the number of
109''seed''s.  ''proc'' is applied to a procedure ''abort-with-result''
110and the ''seed''s, in that order, and is expected to return ''n'' + 2
111values: a key (fixnum), an associated value, and ''n'' new seed
112values.  The key/value association is added to the new fxmapping, and
113unfolding continues with the new seeds.  If, instead,
114''abort-with-result'' is invoked on any number of arbitrary values,
115then the current continuation is discarded and the new fxmapping along
116with the arguments passed to ''abort-with-result'' are delivered as
117multiple values to the continuation that was in effect when
118{{fxmapping-accumulate}} was called.
119
120It is an error for the number of seeds to vary between steps of the
121unfolding process.  If different steps of this process produce
122associations with the same key, then the first such association takes
123precedence.
124
125Example:
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
143Returns {{#t}} if and only if ''obj'' is a fxmapping.
144
145<procedure>(fxmapping-contains? fxmap k) → boolean</procedure>
146
147Returns {{#t}} if and only if ''fxmap'' contains an association for key ''k''.
148
149Examples:
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
158Returns {{#t}} if and only if ''fxmap'' contains no associations.
159
160Examples:
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
169Returns {{#t}} if and only if ''fxmap''₁ and ''fxmap''₂ have no keys in common.
170
171Examples:
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
182The optional ''failure'' parameter is a procedure of type {{[] → * 
}}. The
183optional ''success'' parameter is a procedure of type {{* → * 
}}. ''success''
184defaults to {{values}}.
185
186If an association (''k'', ''v'') occurs in ''fxmap'', then ''success'' is invoked
187in tail context on ''v'' and its values are returned. If ''k'' does not have an
188association in ''fxmap'' and ''failure'' is supplied, then it is invoked in tail
189context on no arguments and its values are returned. Otherwise, it is an
190error.
191
192Examples:
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
202If an association (''k'', ''v'') occurs in ''fxmap'', returns ''v''. Otherwise,
203returns ''obj''.
204
205Examples:
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
214Returns two values, the least key of ''fxmap'' and its associated value. It is
215an error if ''fxmap'' is empty.
216
217Example:
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
225Returns two values, the greatest key of ''fxmap'' and its associated value. It
226is an error if ''fxmap'' is empty.
227
228Example:
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
238Returns a new fxmapping containing all of the associations of
239''fxmap'' as well as the associations (''k''₁, ''v''₁), (''k''₂, ''k''₂), 

240The number of key/value arguments must be even.
241
242If any of the keys already have associations in ''fxmap'', the old
243associations 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
252Similar to {{fxmapping-adjoin}}, except that duplicate associations
253are combined with ''proc'', which is a procedure of type {{* * → *}}.
254''proc'' is called on the new and old values (in that order) associated
255with a duplicated key and is expected to return a value for the key.
256For example, if ''fxmap'' contains the association (''k'', ''v''₁), then
257the value of {{(fxmapping-adjoin/combinator}} ''fxmap f k v''₂{{)}} will
258be a fxmapping with the association (''k'', (''f k v''₁ ''v''₂)).
259
260Example:
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
275existing associations for ''k''₁, ''k''₂, 
 are replaced.
276
277Example:
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
287The ''proc'' parameter is a procedure of type {{fixnum * → *}}.
288
289Returns a new fxmapping in which the association (''k'', ''v'') in
290''fxmap'' is replaced by (''k'', (''proc k v'')).  If ''k'' has no
291association in ''fxmap'', then a fxmapping with the same associations
292as ''fxmap'' is returned.
293
294Example:
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
305Returns a new fxmapping with the same associations as ''fxmap'', except
306those for keys equal to ''k''₁, ''k''₂, 
.
307
308Example:
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
316Returns a new fxmapping with the same associations as ''fxmap'', except
317those 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) → * 
}}.
327If the optional ''failure'' parameter is provided, then it must be a
328procedure of type {{[] → * 
}}.
329
330Updates the association for ''k'' in ''fxmap'' as follows. If ''k'' has an
331association in ''fxmap'', then ''proc'' is invoked in tail context on ''k'', its
332associated value, and two procedure arguments, ''replace'' and ''delete'', and its
333values are returned. Invoking ''replace'' on a value ''v'' returns a fxmapping
334with the association (''k'', ''v'') and all of ''fxmap'''s other associations.
335Invoking ''delete'' returns a fxmapping with all of the associations of ''fxmap'',
336but 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
338arguments and its values are returned. Otherwise, it is an error.
339
340Note that, in contrast to similar Scheme forms, ''proc'' is not required to
341tail-call one of ''delete'' or ''replace'', and that {{fxmapping-update}} simply
342returns the results of invoking ''proc'' (assuming ''k'' is found). Thus, the
343following 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
355Simple versions of several other update operations may be defined in
356terms 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
368Examples:
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
396Updates the association, or lack thereof, for ''k'' in ''fxmap'' as
397follows.  If the association (''k'', ''v'') exists in ''fxmap'', then
398''success'' is invoked in tail context on ''k'', ''v'', and two
399procedure arguments, ''replace'' and ''delete'', and its values are
400returned.
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
405If no association for ''k'' exists in ''fxmap'', then ''failure'' is
406invoked 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
412Note that, in contrast to similar Scheme forms, ''failure'' and
413''success'' are not required to tail-call one of their procedure
414arguments, and that {{fxmapping-alter}} simply returns the results of
415invoking ''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
430Examples:
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
457Returns a new fxmapping with the same associations as ''fxmap'', except
458for the association with the least/greatest key.  It is an error if
459''fxmap'' is empty.
460
461Examples:
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
470The ''proc'' argument of {{fxmapping-update-min}} and {{-max}} is of
471type {{fixnum * (* → fxmapping) ([] → fxmapping) → * 
}}.
472
473Updates 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
475procedure arguments, ''replace'' and ''delete'', and its values are returned.
476Invoking ''replace'' on a value ''v'' returns a fxmapping with the association
477(''k'', ''v'') and all of ''fxmap'''s other associations. Invoking ''delete'' returns
478a fxmapping with all of the associations of ''fxmap'', but without an
479association for ''k''. It is an error if ''fxmap'' is empty.
480
481Note that, in contrast to similar Scheme forms, ''proc'' is not required to
482tail-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
484valid:
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
495Examples:
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
518Returns three values, ''k'', ''v'', and ''fxmap′'', where (''k'', ''v'') is the
519association of ''fxmap'' with the least/greatest key and ''fxmap′'' is a fxmapping
520containing all of the associations of ''fxmap'' except for (''k'', ''v''). It is an
521error if ''fxmap'' is empty.
522
523Example:
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
535Returns 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
540of type {{[] → * 
}}. If the optional ''success'' parameter is supplied, then
541it must be a procedure of type {{fixnum * → * 
}}. ''success'' defaults to
542{{values}}.
543
544Invokes ''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
548are returned.
549
550Examples:
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
574Returns the number of associations in ''fxmap'' that satisfy ''pred''
575(in the sense of {{fxmapping-find}}).
576
577Examples:
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
591Returns {{#t}} if and only if there exists an association in ''fxmap''
592that satisfies ''pred'' (in the sense of {{fxmapping-find}}). ''fxmap''
593is traversed in ascending numerical order of keys.
594
595Example:
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
605Returns {{#t}} if and only every association in ''fxmap'' satisfies
606''pred'' (in the sense of {{fxmapping-find}}), or if ''fxmap'' is
607empty.  ''fxmap'' is traversed in ascending numerical order of keys.
608
609Example:
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
620The ''proc'' argument of {{fxmapping-map}} is of type {{fixnum * → *}}.
621
622Returns a fxmapping with the same keys as ''fxmap'' whose values are the result
623of transforming the values of ''fxmap'' with ''proc''. For each association (''k,
624v'') in ''fxmap'', the association (''k'', (''proc k v'')) is added to the
625resulting fxmapping. The dynamic order of the applications of ''proc'' to the
626elements of ''fxmap'' is unspecified.
627
628Examples:
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
647Calls ''proc'' on the key and value of each association in ''fxmap'' and returns
648an unspecified value.  ''fxmap'' in traversed in ascending numerical
649order of keys.
650
651Example:
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
663The ''kons'' argument of {{fxmapping-fold}} and {{fxmapping-fold-right}} is a
664procedure of type {{fixnum * * → *}}. ''knil'' is an object of any type which can
665be passed to ''kons'' as its third argument.
666
667Folds ''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
669the result of the last application. {{fxmapping-fold}} folds in ascending
670numerical order of keys; {{fxmapping-fold-right}} folds in descending order.
671
672Examples:
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
687Efficient fusion of
688{{(fxmapping-values (fxmapping-map}} ''proc fxmap''{{))}}.
689
690Example:
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
702Returns a fxmapping whose associations are the results of transforming
703both the keys and the values of ''fxmap'' with ''proc''.  For each
704association (''k'', ''v'') in ''fxmap'', (''proc k v'') is evaluated
705to return a new key and a new value which are associated in the new
706fxmapping.  Duplicate keys are replaced, but the results in this case
707are unpredictable; if ''proc'' is not injective, that is, if it
708produces multiple associations with the same key, then it is
709unspecified which one of these associations will be present in the
710resulting 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}}
714from SRFI 146 and is provided primarily for compatibility with that
715SRFI.
716
717=== Filter
718
719<procedure>(fxmapping-filter pred fxmap) → fxmapping</procedure>
720
721Returns a fxmapping containing all of the associations of ''fxmap''
722that satisfy ''pred'' (in the sense of {{fxmapping-find}}).
723
724Example:
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
735Returns a fxmapping containing all of the associations of ''fxmap''
736that do not satisfy ''pred'' (in the sense of {{fxmapping-find}}).
737
738Example:
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
748Returns two fxmappings: the first contains all associations of ''fxmap''
749that satisfy ''pred'' (in the sense of {{fxmapping-find}}), and the second
750contains those that do not.
751
752Example:
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
767Returns an alist containing the associations of ''fxmap'' in increasing
768numerical order of key.
769
770Example:
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
777Identical to {{fxmapping->alist}}, except that the resulting alist
778contains the associations of ''fxmap'' in decreasing numerical order
779of key.
780
781Example:
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
788Returns the keys of ''fxmap'' as a list in ascending numerical order.
789
790Example:
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
797Returns the values of ''fxmap'' as a list in ascending numerical
798order of key.
799
800Example:
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
808Returns a [[srfi-158]] generator which produces the associations of
809''fxmapping'' as key/value pairs in increasing order of key.
810
811Example:
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
819This is the same as {{fxmapping->generator}}, except that the associations of
820''fxmapping'' are produced in decreasing order of key.
821
822Example:
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
830Each of the following predicates takes a {{srfi-128}} comparator
831argument which is used to compare the values of the associations of
832two fxmappings.  (Keys are always compared as if with {{=}}.)
833
834<procedure>(fxmapping=? comp fxmap₁ fxmap₂ fxmap₃ 
) → boolean</procedure>
835
836Returns {{#t}} iff all of the ''fxmaps'' contain equal associations.  Two
837associations are equal exactly when their keys are equal (in the sense
838of {{=}}) and if their values are equal in the sense of the equality
839predicate of ''comp''.
840
841Examples:
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
859Returns {{#t}} iff each ''fxmap'' other than the last is a proper
860subset/subset/proper superset/superset of the following ''fxmap''.
861Values are compared using the equality predicate of ''comp''.
862
863Examples:
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
890Return a fxmapping whose set of associations is the union, intersection,
891asymmetric difference, or symmetric difference of the sets of associations of
892the ''fxmaps''. Asymmetric difference is extended to more than two fxmappings by
893taking the difference between the first fxmapping and the union of the others.
894Symmetric difference is not extended beyond two fxmappings. When comparing
895associations, only the keys are compared. In case of duplicate keys,
896associations in the result fxmapping are drawn from the first fxmapping in
897which they appear.
898
899Examples:
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
922Return a fxmapping whose set of keys is the union/intersection of the sets of
923keys of the ''fxmaps''. The values associated with duplicate keys are combined
924left-associatively with ''proc'', which is also passed the duplicated key as its
925first argument; that is, if an integer ''k'' is associated with values ''v''₁,
926''v''₂, 
, ''v''ₙ in ''fxmap''₁, ''fxmap''₂, 
, ''fxmap''ₙ, respectively, then the
927resulting fxmapping will contain the association (''k'', (''proc k'' 
 (''proc k
928v''₁ ''v''₂) 
 ''v''ₙ)).
929
930Examples:
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
958Procedures that return a subset of ''fxmap'' containing the associations
959whose keys are contained in the interval from ''low'' to ''high''.  The
960interval may be open, closed, open below and closed above, or open
961above and closed below.
962
963Examples:
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
984Procedures that return a fxmapping containing the associations of
985''fxmap'' whose keys are equal to, less than/less than or equal
986to/greater than/greater than or equal to ''k''.  Note that the result of
987{{fxsubmapping=}} contains at most one element.
988
989Examples:
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
1006Returns two fxmappings.  The first contains all of the associations of
1007''fxmap'' whose keys are less than or equal to ''k'', and the second
1008contains the remaining associations.  This is equivalent to
1009
1010<enscript highlight="scheme">
1011(values (fxsubmapping<= fxmap k) (fxsubmapping> fxmap k))
1012</enscript>
1013
1014but is implemented more efficiently.
1015
1016If ''fxmap'' is empty, then both of the fxmappings returned by
1017{{fxmapping-split}} are empty.
1018
1019Example:
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
1031The following eggs are required:
1032
1033* [[srfi-1]]
1034* [[srfi-128]]
1035* [[srfi-143]]
1036* [[srfi-145]]
1037* [[srfi-158]]
1038
1039=== Author
1040
1041Wolfgang Corcoran-Mathe
1042
1043Contact: {{<wcm at sigwinch dot xyzzy minus the zy>}}
1044
1045=== Maintainer
1046
1047Wolfgang Corcoran-Mathe
1048
1049=== Repository
1050
1051[[https://github.com/Zipheir/integer-map|GitHub]]
1052
1053=== License
1054
1055Copyright (C) Wolfgang Corcoran-Mathe (2021). All rights reserved.
1056
1057Permission is hereby granted, free of charge, to any person obtaining
1058a copy of this software and associated documentation files (the
1059"Software"), to deal in the Software without restriction, including
1060without limitation the rights to use, copy, modify, merge, publish,
1061distribute, sublicense, and/or sell copies of the Software, and to
1062permit persons to whom the Software is furnished to do so, subject to
1063the following conditions:
1064
1065The above copyright notice and this permission notice shall be
1066included in all copies or substantial portions of the Software.
1067
1068THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,
1069EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF
1070MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT.
1071IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY
1072CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION OF CONTRACT,
1073TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION WITH THE
1074SOFTWARE 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.
Note: See TracBrowser for help on using the repository browser.