== Integer Mappings

This library defines fixnum mappings (fxmappings), which are immutable
structures that define a set of associations between fixnums (exact
integers) and arbitrary Scheme objects.  The interface is compliant with
[[https://srfi.schemers.org/srfi-224/srfi-224.html|SRFI 224]].

Integer maps are implemented as immutable radix trees, as described by
Chris Okasaki and Andrew Gill in
[[http://ittc.ku.edu/~andygill/papers/IntMap98.pdf|"Fast Mergeable Integer Maps"]].
These provide fast lookup and set-theoretical operations.

[[toc:]]

== Library

=== Notation

The following names are used for the parameters of procedures:
<table>
<tr><td><em>obj</em></td><td>Any Scheme object.</td></tr>
<tr><td><em>boolean</em></td><td>A boolean.</td></tr>
<tr><td><em>fxmap</em></td><td>A fxmapping with values of arbitrary type.</td></tr>
<tr><td><em>k</em></td><td>A fixnum, satisfying {{fixnum?}}.</td></tr>
<tr><td><em>list</em></td><td>A proper list.</td></tr>
<tr><td><em>alist</em></td><td>An association list.</td></tr>
<tr><td><em>proc</em></td><td>A procedure.</td></tr>
<tr><td><em>pred</em></td><td>A predicate, assumed to entail no side-effects.</td></tr>
<tr><td><em>comp</em></td><td>A SRFI 128 comparator object.</td></tr>
</table>
It is an error (unless otherwise noted) if the procedures are passed arguments
that do not have the type implied by the argument names.

=== Non-local control flow

The procedures in this library fully support exceptions, continuable
exceptions, first-class continuations, and other forms of non-local control
flow. In particular, if multiple returns occur from a higher-order procedure,
such as {{fxmapping-unfold}}, then the values returned by earlier returns are
not mutated.

=== Constructors

<procedure>(fxmapping k₁ obj₁ k₂ …) → fxmapping</procedure>

Constructs a fxmapping from the given arguments, which alternate between keys
and values (which are arbitrary Scheme objects); the resulting fxmapping is
newly allocated and contains these (''k'', ''obj'') associations. The number of
arguments must be even. If duplicate keys occur in the arguments, earlier
associations take priority.

Examples:

<enscript highlight="scheme">
(fxmapping->alist (fxmapping 0 'a 1 'b 2 'c)) ⇒ ((0 . a) (1 . b) (2 . c))
(fxmapping->alist (fxmapping -10 "worf" -10 "yar")) ⇒ ((-10 . "worf"))
</enscript>

<procedure>(fxmapping-unfold stop? mapper successor seed₁ seed₂ …) → fxmapping</procedure>

The arguments have the following types:

* ''stop?'' : {{* * … → *-or-false}}
* ''mapper'' : {{* * … → fixnum *}}
* ''successor'' : {{* * … → * * …}}
* ''seed''₁, ''seed''₂, … : {{*}}

The ''stop?'', ''mapper'', and ''successor'' procedures must accept as many
arguments as there are ''seed'' parameters. In addition, the number of values
returned by the ''successor'' procedure must agree with the number of arguments
expected by ''mapper''; that is, the expression

<enscript highlight="scheme">
(call-with-values
 (lambda () (successor seed₁ seed₂ … ))
 mapper)
</enscript>

must result in a valid procedure application.

Unfold a fxmapping from the initial ''seed''s. ''mapper'' is applied to the
''seed''s and returns two values, a key and an associated value, which are
adjoined to the new fxmapping. ''successor'' maps the ''seed''s to new seeds.
Unfolding terminates when the predicate ''stop?'' returns a true value when
applied to the current seeds. The resulting fxmapping is newly allocated.

It is an error for the number of seeds to vary between steps of the unfolding
process. If different steps of this process produce associations with the same
key, then the first such association takes precedence.

Example:
<enscript highlight="scheme">
(fxmapping->alist
 (fxmapping-unfold (lambda (i) (= i 4))
                   (lambda (i) (values i (make-string i #\a)))
                   (lambda (i) (+ i 1))
                   0))
 ⇒ ((0 . "") (1 . "a") (2 . "aa") (3 . "aaa"))
</enscript>
<procedure>(fxmapping-accumulate proc seed₁ seed₂ …) → fxmapping</procedure>

The arguments have the following types:

* ''proc'' : {{(* … → fxmapping * …) * * … → fixnum * * * …}}
* ''seed''₁, ''seed''₂, … : {{*}}

Similar to {{fxmapping-unfold}}, except that a single procedure
controls the unfolding of a new fxmapping.  Let ''n'' be the number of
''seed''s.  ''proc'' is applied to a procedure ''abort-with-result''
and the ''seed''s, in that order, and is expected to return ''n'' + 2
values: a key (fixnum), an associated value, and ''n'' new seed
values.  The key/value association is added to the new fxmapping, and
unfolding continues with the new seeds.  If, instead,
''abort-with-result'' is invoked on any number of arbitrary values,
then the current continuation is discarded and the new fxmapping along
with the arguments passed to ''abort-with-result'' are delivered as
multiple values to the continuation that was in effect when
{{fxmapping-accumulate}} was called.

It is an error for the number of seeds to vary between steps of the
unfolding process.  If different steps of this process produce
associations with the same key, then the first such association takes
precedence.

Example:
<enscript highlight="scheme">
(let-values (((fxmap s)
              (fxmapping-accumulate
               (lambda (abort-with-result i)
                 (if (< i -3)
                     (abort-with-result 'finished)
                     (values i (square i) (- i 1))))
               -1)))
  (values (fxmapping->alist fxmap) s))
 ⇒ ((-3 . 9) (-2 . 4) (-1 . 1))
   finished
</enscript>

=== Predicates

<procedure>(fxmapping? obj) → boolean</procedure>

Returns {{#t}} if and only if ''obj'' is a fxmapping.

<procedure>(fxmapping-contains? fxmap k) → boolean</procedure>

Returns {{#t}} if and only if ''fxmap'' contains an association for key ''k''.

Examples:

<enscript highlight="scheme">
(fxmapping-contains? (fxmapping 1 'b) 1) ⇒ #t
(fxmapping-contains? (fxmapping 1 'b) 0) ⇒ #f
</enscript>

<procedure>(fxmapping-empty? fxmap) → boolean</procedure>

Returns {{#t}} if and only if ''fxmap'' contains no associations.

Examples:

<enscript highlight="scheme">
(fxmapping-empty? (alist->fxmapping '())) ⇒ #t
(fxmapping-empty? (alist->fxmapping '((0 . a)))) ⇒ #f
</enscript>

<procedure>(fxmapping-disjoint? fxmap₁ fxmap₂) → boolean</procedure>

Returns {{#t}} if and only if ''fxmap''₁ and ''fxmap''₂ have no keys in common.

Examples:

<enscript highlight="scheme">
(fxmapping-disjoint? (fxmapping 0 'a) (fxmapping 1 'b)) ⇒ #t
(fxmapping-disjoint? (fxmapping 1 '(b)) (fxmapping 1 'b)) ⇒ #f
</enscript>

=== Accessors

<procedure>(fxmapping-ref fxmap k [ failure [ success ] ]) → * …</procedure>

The optional ''failure'' parameter is a procedure of type {{[] → * …}}. The
optional ''success'' parameter is a procedure of type {{* → * …}}. ''success''
defaults to {{values}}.

If an association (''k'', ''v'') occurs in ''fxmap'', then ''success'' is invoked
in tail context on ''v'' and its values are returned. If ''k'' does not have an
association in ''fxmap'' and ''failure'' is supplied, then it is invoked in tail
context on no arguments and its values are returned. Otherwise, it is an
error.

Examples:

<enscript highlight="scheme">
(fxmapping-ref (fxmapping 36864 'zap) 36864) ⇒ zap
(fxmapping-ref (fxmapping 0 'a) 36864) ⇒ ; error
(fxmapping-ref (fxmapping 0 "worf") 0 (lambda () #f) string-length) ⇒ 4
</enscript>

<procedure>(fxmapping-ref/default fxmap k obj) → *</procedure>

If an association (''k'', ''v'') occurs in ''fxmap'', returns ''v''. Otherwise,
returns ''obj''.

Examples:

<enscript highlight="scheme">
(fxmapping-ref/default (fxmapping 36864 'zap) 36864 #f) ⇒ zap
(fxmapping-ref/default (fxmapping 0 'a) 36864 #f) ⇒ #f
</enscript>

<procedure>(fxmapping-min fxmap) → fixnum *</procedure>

Returns two values, the least key of ''fxmap'' and its associated value. It is
an error if ''fxmap'' is empty.

Example:

<enscript highlight="scheme">
(fxmapping-min (fxmapping 0 'a 1 'b 2 'c)) ⇒ 0 a
</enscript>

<procedure>(fxmapping-max fxmap) → fixnum *</procedure>

Returns two values, the greatest key of ''fxmap'' and its associated value. It
is an error if ''fxmap'' is empty.

Example:

<enscript highlight="scheme">
(fxmapping-max (fxmapping 0 'a 1 'b 2 'c)) ⇒ 2 c
</enscript>

=== Updaters

<procedure>(fxmapping-adjoin fxmap k₁ obj₁ k₂ …) → fxmapping</procedure>

Returns a new fxmapping containing all of the associations of
''fxmap'' as well as the associations (''k''₁, ''v''₁), (''k''₂, ''k''₂), …
The number of key/value arguments must be even.

If any of the keys already have associations in ''fxmap'', the old
associations are preserved.

<enscript highlight="scheme">
(fxmapping->alist (fxmapping-adjoin (fxmapping 1 'b) 0 'a))
 ⇒ ((0 . a) (1 . b))
</enscript>

<procedure>(fxmapping-adjoin/combinator fxmap proc k₁ obj₁ k₂ …) → fxmapping</procedure>

Similar to {{fxmapping-adjoin}}, except that duplicate associations
are combined with ''proc'', which is a procedure of type {{* * → *}}.
''proc'' is called on the new and old values (in that order) associated
with a duplicated key and is expected to return a value for the key.
For example, if ''fxmap'' contains the association (''k'', ''v''₁), then
the value of {{(fxmapping-adjoin/combinator}} ''fxmap f k v''₂{{)}} will
be a fxmapping with the association (''k'', (''f k v''₁ ''v''₂)).

Example:

<enscript highlight="scheme">
(fxmapping->alist
 (fxmapping-adjoin/combinator (fxmapping 0 "geordi" 1 "reginald")
                              (lambda (_ last first)
                                (string-append first " " last))
                              0 "laforge"
                              1 "barclay"))
 ⇒ ((0 . "geordi laforge") (1 . "reginald barclay"))
</enscript>

<procedure>(fxmapping-set fxmap k₁ obj₁ k₂ …) → fxmapping</procedure>

{{fxmapping-set}} is the same as {{fxmapping-adjoin}}, except that any
existing associations for ''k''₁, ''k''₂, … are replaced.

Example:

<enscript highlight="scheme">
(fxmapping->alist
 (fxmapping-set (fxmapping 0 "geordi" 1 "reginald") 1 "tasha"))
 ⇒ ((0 . "geordi") (1 . "tasha"))
</enscript>

<procedure>(fxmapping-adjust fxmap k proc) → fxmapping</procedure>

The ''proc'' parameter is a procedure of type {{fixnum * → *}}.

Returns a new fxmapping in which the association (''k'', ''v'') in
''fxmap'' is replaced by (''k'', (''proc k v'')).  If ''k'' has no
association in ''fxmap'', then a fxmapping with the same associations
as ''fxmap'' is returned.

Example:
<enscript highlight="scheme">
(fxmapping->alist
 (fxmapping-adjust (fxmapping 64 "var")
                   64
                   (lambda (k s) (string-append s (number->string k)))))
 ⇒ ((64 . "var64"))
</enscript>

<procedure>(fxmapping-delete fxmap k₁ k₂ …) → fxmapping</procedure>

Returns a new fxmapping with the same associations as ''fxmap'', except
those for keys equal to ''k''₁, ''k''₂, ….

Example:
<enscript highlight="scheme">
(fxmapping->alist (fxmapping-delete (fxmapping 0 -200 1 -100) 0))
 ⇒ ((1 . -100))
</enscript>

<procedure>(fxmapping-delete-all fxmap list) → fxmapping</procedure>

Returns a new fxmapping with the same associations as ''fxmap'', except
those for keys equal to an element of ''list''.

<enscript highlight="scheme">
(fxmapping->alist (fxmapping-delete-all (fxmapping 0 'a 1 'b 2 'c) '(1 2)))
 ⇒ ((0 . a))
</enscript>

<procedure>(fxmapping-update fxmap k proc [ failure ]) → * …</procedure>

''proc'' is a procedure of type {{fixnum * (* → fxmapping) ([] → fxmapping) → * …}}.
If the optional ''failure'' parameter is provided, then it must be a
procedure of type {{[] → * …}}.

Updates the association for ''k'' in ''fxmap'' as follows. If ''k'' has an
association in ''fxmap'', then ''proc'' is invoked in tail context on ''k'', its
associated value, and two procedure arguments, ''replace'' and ''delete'', and its
values are returned. Invoking ''replace'' on a value ''v'' returns a fxmapping
with the association (''k'', ''v'') and all of ''fxmap'''s other associations.
Invoking ''delete'' returns a fxmapping with all of the associations of ''fxmap'',
but without an association for ''k''. If ''k'' has no association in ''fxmap'' and
''failure'' is provided, then ''failure'' is invoked in tail context on no
arguments and its values are returned. Otherwise, it is an error.

Note that, in contrast to similar Scheme forms, ''proc'' is not required to
tail-call one of ''delete'' or ''replace'', and that {{fxmapping-update}} simply
returns the results of invoking ''proc'' (assuming ''k'' is found). Thus, the
following is valid:

<enscript highlight="scheme">
(fxmapping-update (fxmapping 0 'a 1 'b 2 'c)
                  1
                  (lambda (k v replace _del)
                    (values k v (fxmapping->alist (replace 'z)))))
 ⇒ 1
   b
   ((0 . a) (1 . z) (2 . c))
</enscript>

Simple versions of several other update operations may be defined in
terms of {{fxmapping-update}}, e.g.:

<enscript highlight="scheme">
(fxmapping-delete fxmap k)
 ≡
(fxmapping-update fxmap k (lambda (_k _v _r delete) (delete)))

(fxmapping-set fxmap k v)
 ≡
(fxmapping-update fxmap k (lambda (_k _u replace _d) (replace v)))
</enscript>

Examples:

<enscript highlight="scheme">
;; Delete the association for 1 if its value is a symbol.
(fxmapping->alist
 (fxmapping-update (fxmapping 0 'a 1 'b 2 'c)
                   1
                   (lambda (_k v replace delete)
                     (if (symbol? v)
                         (delete)
                         (replace v)))))
 ⇒ ((0 . a) (2 . c))

(fxmapping->alist
 (fxmapping-update (fxmapping 0 'a 1 'b 2 'c)
                   1
                   (lambda (k _v replace _d)
                     (replace k)))))
 ⇒ ((0 . a) (1 . 1) (2 . c))
</enscript>

<procedure>(fxmapping-alter fxmap k failure success) → * …</procedure>

''failure'' is a procedure of type
{{(* → fxmapping) ([] → fxmapping) → * …}}.
''success'' is a procedure of type
{{fixnum * (* → fxmapping) ([] → fxmapping) → * …}}.

Updates the association, or lack thereof, for ''k'' in ''fxmap'' as
follows.  If the association (''k'', ''v'') exists in ''fxmap'', then
''success'' is invoked in tail context on ''k'', ''v'', and two
procedure arguments, ''replace'' and ''delete'', and its values are
returned.

* Invoking (''replace v′'') returns a fxmapping with the association (''k'', ''v′'') as well as all of ''fxmap'''s other associations.
* Invoking (''delete'') returns a fxmapping with all of ''fxmap'''s associations except for (''k'', ''v'').

If no association for ''k'' exists in ''fxmap'', then ''failure'' is
invoked in tail context on two procedure arguments, ''insert'' and
''ignore'', and its values are returned.

* Invoking (''insert u'') returns a fxmapping with all of the associations of ''fxmap'' as well as (''k'', ''u'').
* Invoking (''ignore'') returns a fxmapping with the same associations as ''fxmap''.

Note that, in contrast to similar Scheme forms, ''failure'' and
''success'' are not required to tail-call one of their procedure
arguments, and that {{fxmapping-alter}} simply returns the results of
invoking ''failure'' or ''success''.  Thus, the following is valid:

<enscript highlight="scheme">
;; Returns an additional boolean value indicating
;; whether the fxmapping was updated.
(fxmapping-alter (fxmapping 0 'a 1 'b 2 'c)
                 1
                 (lambda (_ins ignore)
                   (values (ignore) #f))
                 (lambda (_k _v replace _del)
                   (values (replace 'z) #t)))
 ⇒ <fxmapping>
   #t
</enscript>

Examples:
<enscript highlight="scheme">
;; Insert an association for 4 if it's not present.
(fxmapping->alist
 (fxmapping-alter (fxmapping 0 'a 1 'b)
                  4
                  (lambda (insert _ig) (insert 'e))
                  (lambda (_k v replace _del)
                    (replace v))))  ; keep original value
 ⇒ ((0 . a) (1 . b) (4 . e))
   #t

;; Delete an association for 1 if its value is a symbol.
(fxmapping->alist
 (fxmapping-alter (fxmapping 0 'a 1 'b)
                  1
                  (lambda (_ins ignore) (ignore))
                  (lambda (_k v replace delete)
                    (if (symbol? v)
                        (delete)
                        (replace v)))))
 ⇒ ((0 . a))
</enscript>

<procedure>(fxmapping-delete-min fxmap) → fxmapping</procedure>
<procedure>(fxmapping-delete-max fxmap) → fxmapping</procedure>

Returns a new fxmapping with the same associations as ''fxmap'', except
for the association with the least/greatest key.  It is an error if
''fxmap'' is empty.

Examples:
<enscript highlight="scheme">
(fxmapping-delete-min (fxmapping 0 'a 1 'b 2 'c)) ⇒ ((1 . b) (2 . c))
(fxmapping-delete-max (fxmapping 0 'a 1 'b 2 'c)) ⇒ ((0 . a) (1 . b))
</enscript>

<procedure>(fxmapping-update-min fxmap proc) → * …</procedure>
<procedure>(fxmapping-update-max fxmap proc) → * …</procedure>

The ''proc'' argument of {{fxmapping-update-min}} and {{-max}} is of
type {{fixnum * (* → fxmapping) ([] → fxmapping) → * …}}.

Updates the association of ''fxmap'' with the least/greatest key ''k'' as follows.
''proc'' is invoked in tail context on ''k'', its associated value, and two
procedure arguments, ''replace'' and ''delete'', and its values are returned.
Invoking ''replace'' on a value ''v'' returns a fxmapping with the association
(''k'', ''v'') and all of ''fxmap'''s other associations. Invoking ''delete'' returns
a fxmapping with all of the associations of ''fxmap'', but without an
association for ''k''. It is an error if ''fxmap'' is empty.

Note that, in contrast to similar Scheme forms, ''proc'' is not required to
tail-call one of ''delete'' or ''replace'', and that {{fxmapping-update-min}} and
{{-max}} simply return the results of invoking ''proc''. Thus, the following is
valid:

<enscript highlight="scheme">
(fxmapping-update-min (fxmapping 0 'a 1 'b 2 'c)
                      (lambda (k v _r delete)
                        (values k v (fxmapping->alist (delete)))))
 ⇒ 0
   a
   ((1 . b) (2 . c))
</enscript>

Examples:

<enscript highlight="scheme">
(fxmapping->alist
 (fxmapping-update-min (fxmapping -5 "phaser" -1 "tricorder")
                       (lambda (_ v replace delete)
                         (if (symbol? v)
                             (replace v)
                             (delete)))))
 ⇒ ((-1 . "tricorder"))

(fxmapping->alist
 (fxmapping-update-max (fxmapping -5 "phaser" -1 "tricorder")
                       (lambda (k v replace delete)
                         (if (and (negative? k) (string? v))
                             (replace (string-length v))
                             (delete)))))
 ⇒ ((-5 . "phaser") (-1 . 9))
</enscript>

<procedure>(fxmapping-pop-min fxmap) → fixnum * fxmapping</procedure>
<procedure>(fxmapping-pop-max fxmap) → fixnum * fxmapping</procedure>

Returns three values, ''k'', ''v'', and ''fxmap′'', where (''k'', ''v'') is the
association of ''fxmap'' with the least/greatest key and ''fxmap′'' is a fxmapping
containing all of the associations of ''fxmap'' except for (''k'', ''v''). It is an
error if ''fxmap'' is empty.

Example:
<enscript highlight="scheme">
(let-values (((k v fxmap)
              (fxmapping-pop-min (fxmapping 0 'a 1 'b 2 'c))))
  (values k v (fxmapping->alist fxmap)))
 ⇒ (0 a ((1 . b) (2 . c)))
</enscript>

=== The whole fxmapping

<procedure>(fxmapping-size fxmap) → fixnum</procedure>

Returns the number of associations in ''fxmap''.

<procedure>(fxmapping-find pred fxmap failure [ success ]) → * …</procedure>

''pred'' is a predicate of type {{fixnum * → boolean}}. ''failure'' is a procedure
of type {{[] → * …}}. If the optional ''success'' parameter is supplied, then
it must be a procedure of type {{fixnum * → * …}}. ''success'' defaults to
{{values}}.

Invokes ''success'' in tail context on ''k'' and ''v'' and returns it results, where
(''k'', ''v'') is the association of ''fxmap'' with the least key such that
(''pred k v'') is true. If there is no such association, then
''failure'' is tail-called with no arguments and its results
are returned.

Examples:

<enscript highlight="scheme">
(fxmapping-find (lambda (_ v) (even? v))
                (fxmapping 0 1 1 2 2 4 3 8)
                (lambda () (values #f #f)))
 ⇒ 1 2

(fxmapping-find (lambda (_ v) (negative? v))
                (fxmapping 0 1 1 2 2 4 3 8)
                (lambda () (values 'nope 'nada)))
 ⇒ nope nada

(fxmapping-find (lambda (k s) (= k (string-length s)))
                (fxmapping 2 "worf" 3 "data" 4 "troi")
                (lambda () (error "not found"))
                list)
 ⇒ (4 "troi")
</enscript>

<procedure>(fxmapping-count pred fxmap) → fixnum</procedure>

''pred'' is a predicate of type {{fixnum * → boolean}}.

Returns the number of associations in ''fxmap'' that satisfy ''pred''
(in the sense of {{fxmapping-find}}).

Examples:

<enscript highlight="scheme">
(fxmapping-count (lambda (_ v) (even? v))
                 (fxmapping 0 1 1 2 2 4 3 8)) ⇒ 3
(fxmapping-count (lambda (k s) (= k (string-length s)))
                 (fxmapping 0 "x" 1 "y" 2 "z"))
 ⇒ 1
</enscript>

<procedure>(fxmapping-any? pred fxmap) → boolean</procedure>

''pred'' is a predicate of type {{fixnum * → boolean}}.

Returns {{#t}} if and only if there exists an association in ''fxmap''
that satisfies ''pred'' (in the sense of {{fxmapping-find}}). ''fxmap''
is traversed in ascending numerical order of keys.

Example:
<enscript highlight="scheme">
(fxmapping-any? (lambda (_ v) (odd? v))
                (fxmapping 0 1 1 2 2 4 3 8)) ⇒ #t
</enscript>

<procedure>(fxmapping-every? pred fxmap) → boolean</procedure>

''pred'' is a predicate of type {{fixnum * → boolean}}.

Returns {{#t}} if and only every association in ''fxmap'' satisfies
''pred'' (in the sense of {{fxmapping-find}}), or if ''fxmap'' is
empty.  ''fxmap'' is traversed in ascending numerical order of keys.

Example:

<enscript highlight="scheme">
(fxmapping-every? (lambda (_ v) (integer? v))
                  (fxmapping 0 1 1 2 2 4 3 8)) ⇒ #t
</enscript>

=== Traversal

<procedure>(fxmapping-map proc fxmap) → fxmapping</procedure>

The ''proc'' argument of {{fxmapping-map}} is of type {{fixnum * → *}}.

Returns a fxmapping with the same keys as ''fxmap'' whose values are the result
of transforming the values of ''fxmap'' with ''proc''. For each association (''k,
v'') in ''fxmap'', the association (''k'', (''proc k v'')) is added to the
resulting fxmapping. The dynamic order of the applications of ''proc'' to the
elements of ''fxmap'' is unspecified.

Examples:

<enscript highlight="scheme">
(fxmapping->alist
 (fxmapping-map (lambda (_ s) (string-length s))
                (fxmapping 0 "picard" 1 "riker" 2 "troi")))
 ⇒ ((0 . 6) (1 . 5) (2 . 4))

(fxmapping->alist
 (fxmapping-map (lambda (k s)
                  (string-append s (number->string k)))
                (fxmapping 256 "x" 512 "y" 1024 "z")))
 ⇒ ((256 . "x256") (512 . "y512") (1024 . "z1024"))
</enscript>

<procedure>(fxmapping-for-each proc fxmap) → unspecified</procedure>

''proc'' is a procedure of type {{fixnum * → *}}.

Calls ''proc'' on the key and value of each association in ''fxmap'' and returns
an unspecified value.  ''fxmap'' in traversed in ascending numerical
order of keys.

Example:
<enscript highlight="scheme">
(let ((sum 0))
  (fxmapping-for-each (lambda (_ v) (set! sum (+ sum v)))
                      (fxmapping 0 1 1 2 2 4 3 8))
  sum)
 ⇒ 15
</enscript>

<procedure>(fxmapping-fold kons knil fxmap) → *</procedure>
<procedure>(fxmapping-fold-right kons knil fxmap) → *</procedure>

The ''kons'' argument of {{fxmapping-fold}} and {{fxmapping-fold-right}} is a
procedure of type {{fixnum * * → *}}. ''knil'' is an object of any type which can
be passed to ''kons'' as its third argument.

Folds ''kons'' over ''fxmap'', using ''knil'' as the base value. At each step,
''kons'' is applied to the key of an association, its associated value, and to
the result of the last application. {{fxmapping-fold}} folds in ascending
numerical order of keys; {{fxmapping-fold-right}} folds in descending order.

Examples:
<enscript highlight="scheme">
(fxmapping-fold-right (lambda (_ v vs) (cons v vs))
                      '()
                      (fxmapping 0 "worf" 1 "data" 2 "crusher"))
 ⇒ ("worf" "data" "crusher")

(fxmapping-fold (lambda (k _ ks) (cons k ks))
                '()
                (fxmapping 0 "worf" 1 "data" 2 "crusher"))
 ⇒ (2 1 0)
</enscript>

<procedure>(fxmapping-map->list proc fxmap) → list</procedure>

Efficient fusion of
{{(fxmapping-values (fxmapping-map}} ''proc fxmap''{{))}}.

Example:

<enscript highlight="scheme">
(fxmapping-map->list (lambda (_ v) (string-length v))
                     (fxmapping 0 "picard" 1 "riker" 2 "troi"))
 ⇒ (6 5 4)
</enscript>

<procedure>(fxmapping-relation-map proc fxmap) → fxmapping</procedure>

''proc'' must be a procedure of type {{fixnum * → fixnum *}}.

Returns a fxmapping whose associations are the results of transforming
both the keys and the values of ''fxmap'' with ''proc''.  For each
association (''k'', ''v'') in ''fxmap'', (''proc k v'') is evaluated
to return a new key and a new value which are associated in the new
fxmapping.  Duplicate keys are replaced, but the results in this case
are unpredictable; if ''proc'' is not injective, that is, if it
produces multiple associations with the same key, then it is
unspecified which one of these associations will be present in the
resulting fxmapping.  The dynamic order of the applications of
''proc'' to the elements of ''fxmap'' is unspecified.

'''Rationale:''' {{fxmapping-relation-map}} corresponds to {{mapping-map}}
from SRFI 146 and is provided primarily for compatibility with that
SRFI.

=== Filter

<procedure>(fxmapping-filter pred fxmap) → fxmapping</procedure>

Returns a fxmapping containing all of the associations of ''fxmap''
that satisfy ''pred'' (in the sense of {{fxmapping-find}}).

Example:

<enscript highlight="scheme">
(fxmapping->alist
 (fxmapping-filter (lambda (_ v) (positive? v))
                   (fxmapping 0 2 1 -4 2 8 3 -16)))
 ⇒ ((0 . 2) (2 . 8))
</enscript>

<procedure>(fxmapping-remove pred fxmap) → fxmapping</procedure>

Returns a fxmapping containing all of the associations of ''fxmap''
that do not satisfy ''pred'' (in the sense of {{fxmapping-find}}).

Example:
<enscript highlight="scheme">
(fxmapping->alist
 (fxmapping-remove (lambda (_ v) (positive? v))
                   (fxmapping 0 2 1 -4 2 8 3 -16)))
 ⇒ ((1 . -4) (3 . -16))
</enscript>

<procedure>(fxmapping-partition pred fxmap) → fxmapping fxmapping</procedure>

Returns two fxmappings: the first contains all associations of ''fxmap''
that satisfy ''pred'' (in the sense of {{fxmapping-find}}), and the second
contains those that do not.

Example:
<enscript highlight="scheme">
(let-values (((pos ~pos)
              (fxmapping-partition (lambda (_ v) (positive? v))
                                   (fxmapping 0 2 1 -4 2 8 3 -16))))
  (values (fxmapping->alist pos)
          (fxmapping->alist ~pos)))
 ⇒ ((0 . 2) (2 . 8))
   ((1 . -4) (3 . -16))
</enscript>

=== Conversion

<procedure>(fxmapping->alist fxmap) → alist[fixnum, *]</procedure>

Returns an alist containing the associations of ''fxmap'' in increasing
numerical order of key.

Example:
<enscript highlight="scheme">
(fxmapping->alist (fxmapping 1 'a 2 'b)) ⇒ ((1 . a) (2 . b))
</enscript>

<procedure>(fxmapping->decreasing-alist fxmap) → alist[fixnum, *]</procedure>

Identical to {{fxmapping->alist}}, except that the resulting alist
contains the associations of ''fxmap'' in decreasing numerical order
of key.

Example:
<enscript highlight="scheme">
(fxmapping->alist (fxmapping 1 'a 2 'b)) ⇒ ((2 . b) (1 . a))
</enscript>

<procedure>(fxmapping-keys fxmap) → list[fixnum]</procedure>

Returns the keys of ''fxmap'' as a list in ascending numerical order.

Example:
<enscript highlight="scheme">
(fxmapping-keys (fxmapping 137 'a -24 'b -5072 'c)) ⇒ (-5072 -24 137)
</enscript>

<procedure>(fxmapping-values fxmap) → list[*]</procedure>

Returns the values of ''fxmap'' as a list in ascending numerical
order of key.

Example:
<enscript highlight="scheme">
(fxmapping-values (fxmapping 0 "picard" 1 "riker" 2 "troi"))
 ⇒ ("picard" "riker" "troi")
</enscript>

<procedure>(fxmapping->generator fxmapping) → generator[pair(fixnum, *)]</procedure>

Returns a [[srfi-158]] generator which produces the associations of
''fxmapping'' as key/value pairs in increasing order of key.

Example:
<enscript highlight="scheme">
(generator->list (fxmapping->generator (fxmapping 3 "yar" 2 "troi")))
 ⇒ ((2 . "troi") (3 . "yar"))
</enscript>

<procedure>(fxmapping->decreasing-generator fxmapping) → generator[pair(fixnum, *)]</procedure>

This is the same as {{fxmapping->generator}}, except that the associations of
''fxmapping'' are produced in decreasing order of key.

Example:
<enscript highlight="scheme">
(generator->list (fxmapping->decreasing-generator (fxmapping 3 "yar" 2 "troi")))
 ⇒ ((3 . "yar") (2 . "troi"))
</enscript>

=== Comparison

Each of the following predicates takes a {{srfi-128}} comparator
argument which is used to compare the values of the associations of
two fxmappings.  (Keys are always compared as if with {{=}}.)

<procedure>(fxmapping=? comp fxmap₁ fxmap₂ fxmap₃ …) → boolean</procedure>

Returns {{#t}} iff all of the ''fxmaps'' contain equal associations.  Two
associations are equal exactly when their keys are equal (in the sense
of {{=}}) and if their values are equal in the sense of the equality
predicate of ''comp''.

Examples:
<enscript highlight="scheme">
(fxmapping=? (make-default-comparator)
             (fxmapping 1 'a 2 'b)
             (fxmapping 2 'b 1 'a))
 ⇒ #t

(fxmapping=? (make-default-comparator)
             (fxmapping 1 'a 2 'b 3 'c)
             (fxmapping 2 'b 1 'a))
 ⇒ #f
</enscript>

<procedure>(fxmapping<? comp fxmap₁ fxmap₂ fxmap₃ …) → boolean</procedure>
<procedure>(fxmapping<=? comp fxmap₁ fxmap₂ fxmap₃ …) → boolean</procedure>
<procedure>(fxmapping>? comp fxmap₁ fxmap₂ fxmap₃ …) → boolean</procedure>
<procedure>(fxmapping>=? comp fxmap₁ fxmap₂ fxmap₃ …) → boolean</procedure>

Returns {{#t}} iff each ''fxmap'' other than the last is a proper
subset/subset/proper superset/superset of the following ''fxmap''.
Values are compared using the equality predicate of ''comp''.

Examples:
<enscript highlight="scheme">
(fxmapping<? (make-default-comparator)
             (fxmapping 1 'a 2 'b)
             (fxmapping 2 'b 1 'a 3 'c))
 ⇒ #t

(fxmapping>? (make-default-comparator)
             (fxmapping 2 'b 1 "worf" 3 'c)
             (fxmapping 1 'a 2 'b))
 ⇒ #f

(fxmapping>=? (make-default-comparator)
              (fxmapping 2 'b 1 'a 3 'c)
              (fxmapping 1 'a 2 'b)
              (fxmapping 2 'b 1 'a)
              (fxmapping 1 'a))
 ⇒ #t
</enscript>

=== Set theory operations

<procedure>(fxmapping-union fxmap₁ fxmap₂ fxmap₃ …) → fxmapping</procedure>
<procedure>(fxmapping-intersection fxmap₁ fxmap₂ fxmap₃ …) → fxmapping</procedure>
<procedure>(fxmapping-difference fxmap₁ fxmap₂ fxmap₃ …) → fxmapping</procedure>
<procedure>(fxmapping-xor fxmap₁ fxmap₂) → fxmapping</procedure>

Return a fxmapping whose set of associations is the union, intersection,
asymmetric difference, or symmetric difference of the sets of associations of
the ''fxmaps''. Asymmetric difference is extended to more than two fxmappings by
taking the difference between the first fxmapping and the union of the others.
Symmetric difference is not extended beyond two fxmappings. When comparing
associations, only the keys are compared. In case of duplicate keys,
associations in the result fxmapping are drawn from the first fxmapping in
which they appear.

Examples:
<enscript highlight="scheme">
(fxmapping->alist (fxmapping-union (fxmapping 0 'a 2 'c)
                                   (fxmapping 1 'b 3 'd)))
 ⇒ ((0 . a) (1 . b) (2 . c) (3 . d))

(fxmapping->alist
 (fxmapping-intersection (fxmapping 0 'a 2 'c)
                         (fxmapping 1 'b 2 'c 3 'd)
                         (fxmapping 2 'c 4 'e)))
 ⇒ ((2 . c))

(fxmapping->alist (fxmapping-difference (fxmapping 0 'a 1 'b 2 'c)
                                        (fxmapping 2 "worf")
                                        (fxmapping 1 "data")))
 ⇒ ((0 . a))
</enscript>

<procedure>(fxmapping-union/combinator proc fxmap₁ fxmap₂ fxmap₃ …) → fxmapping </procedure>
<procedure>(fxmapping-intersection/combinator proc fxmap₁ fxmap₂ fxmap₃ …) → fxmapping</procedure>

''proc'' is a procedure of type {{fixnum * * → *}}.

Return a fxmapping whose set of keys is the union/intersection of the sets of
keys of the ''fxmaps''. The values associated with duplicate keys are combined
left-associatively with ''proc'', which is also passed the duplicated key as its
first argument; that is, if an integer ''k'' is associated with values ''v''₁,
''v''₂, …, ''v''ₙ in ''fxmap''₁, ''fxmap''₂, …, ''fxmap''ₙ, respectively, then the
resulting fxmapping will contain the association (''k'', (''proc k'' … (''proc k
v''₁ ''v''₂) … ''v''ₙ)).

Examples:
<enscript highlight="scheme">
;; Right-biased union.
(fxmapping->alist
 (fxmapping-union/combinator (lambda (_k _l r) r)
                             (fxmapping 1 'b 2 'c)
                             (fxmapping 2 "data" 3 "picard")))

 ⇒ ((1 . b) (2 . "data") (3 . "picard"))

(fxmapping->alist
 (fxmapping-intersection/combinator
  (lambda (_ l r) (string-append l " " r))
  (fxmapping 1 "q" 3 "jean-luc" 5 "miles" 7 "quark")
  (fxmapping 3 "picard" 5 "o'brien")))

 ⇒ ((3 . "jean-luc picard") (5 . "miles o'brien"))
</enscript>

=== Submappings

<procedure>(fxmapping-open-interval fxmap low high) → fxmapping</procedure>
<procedure>(fxmapping-closed-interval fxmap low high) → fxmapping</procedure>
<procedure>(fxmapping-open-closed-interval fxmap low high) → fxmapping</procedure>
<procedure>(fxmapping-closed-open-interval fxmap low high) → fxmapping</procedure>

''low'' and ''high'' are both exact integers.

Procedures that return a subset of ''fxmap'' containing the associations
whose keys are contained in the interval from ''low'' to ''high''.  The
interval may be open, closed, open below and closed above, or open
above and closed below.

Examples:
<enscript highlight="scheme">
(fxmapping->alist
 (fxmapping-open-interval (fxmapping 0 'a 1 'b 2 'c 3 'd) 1 3))
 ⇒ ((2 . c))

(fxmapping->alist
 (fxmapping-closed-interval (fxmapping 0 'a 1 'b 2 'c 3 'd) 1 3))
 ⇒ ((1 . b) (2 . c) (3 . d))

(fxmapping->alist
 (fxmapping-closed-open-interval (fxmapping 0 'a 1 'b 2 'c 3 'd) 1 3))
 ⇒ ((1 . b) (2 . c))
</enscript>

<procedure>(fxsubmapping= fxmap k) → fxmapping</procedure>
<procedure>(fxsubmapping< fxmap k) → fxmapping</procedure>
<procedure>(fxsubmapping<= fxmap k) → fxmapping</procedure>
<procedure>(fxsubmapping> fxmap k) → fxmapping</procedure>
<procedure>(fxsubmapping>= fxmap k) → fxmapping</procedure>

Procedures that return a fxmapping containing the associations of
''fxmap'' whose keys are equal to, less than/less than or equal
to/greater than/greater than or equal to ''k''.  Note that the result of
{{fxsubmapping=}} contains at most one element.

Examples:
<enscript highlight="scheme">
(fxmapping->alist
 (fxsubmapping= (fxmapping 0 'a 1 'b 2 'c 3 'd) 2))
 ⇒ ((2 . c))

(fxmapping->alist
 (fxsubmapping< (fxmapping 0 'a 1 'b 2 'c 3 'd) 2))
 ⇒ ((0 . a) (1 . b))

(fxmapping->alist
 (fxsubmapping>= (fxmapping 0 'a 1 'b 2 'c 3 'd) 2))
 ⇒ ((2 . c) (3 . d))
</enscript>

<procedure>(fxmapping-split fxmap k) → fxmapping fxmapping</procedure>

Returns two fxmappings.  The first contains all of the associations of
''fxmap'' whose keys are less than or equal to ''k'', and the second
contains the remaining associations.  This is equivalent to

<enscript highlight="scheme">
(values (fxsubmapping<= fxmap k) (fxsubmapping> fxmap k))
</enscript>

but is implemented more efficiently.

If ''fxmap'' is empty, then both of the fxmappings returned by
{{fxmapping-split}} are empty.

Example:
<enscript highlight="scheme">
(let-values ((fxmaps (fxmapping-split (fxmapping 0 'a 1 'b 2 'c 3 'd) 2)))
  (map fxmapping->alist fxmaps))
 ⇒ (((0 . a) (1 . b) (2 . c))
((3 . d)))
</enscript>

=== Exceptions

Following CHICKEN's libraries, procedures from this egg abort with
{{(exn type assertion)}} and {{(exn arity assertion)}} conditions
when type- and arity-checking assertions fail, respectively.
When {{fxmapping-ref}} and similar procedures fail, or when an empty
fxmapping is passed to a procedure that expects a non-empty mapping,
an {{(exn access)}} condition is raised. See the
[[Module (chicken condition)]] page for more details.

== About This Egg

=== Dependencies

The following eggs are required:

* [[srfi-1]]
* [[srfi-128]]
* [[srfi-143]]
* [[srfi-158]]

The [[test]] egg is required to run the included tests.

=== Author

Wolfgang Corcoran-Mathe

Contact: {{<wcm at sigwinch dot xyzzy minus the zy>}}

=== Maintainer

Wolfgang Corcoran-Mathe

=== Repository

[[https://github.com/Zipheir/integer-map|GitHub]]

=== License

Copyright (C) Wolfgang Corcoran-Mathe (2021). All rights reserved.

Permission is hereby granted, free of charge, to any person obtaining
a copy of this software and associated documentation files (the
"Software"), to deal in the Software without restriction, including
without limitation the rights to use, copy, modify, merge, publish,
distribute, sublicense, and/or sell copies of the Software, and to
permit persons to whom the Software is furnished to do so, subject to
the following conditions:

The above copyright notice and this permission notice shall be
included in all copies or substantial portions of the Software.

THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,
EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF
MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT.
IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY
CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION OF CONTRACT,
TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION WITH THE
SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.

=== Version history

; 0.1 (2021-03-06) : Initial release.
; 0.1.1 (2021-03-06) : Tests bugfix.
; 0.1.2 (2021-03-06) : Bookkeeping bugfix.
; 1.0.1 (2021-06-26) : Update to current SRFI 224, overhaul interface.
; 1.0.2 (2021-06-26) : Remove types, which were difficult to understand and mostly useless.
; 1.0.3 (2022-08-13) : Add types (again) and improve runtime checks.
; 1.1.0 (2026-08-16) : Add CHICKEN 6 support.