Changeset 40217 in project


Ignore:
Timestamp:
06/26/21 02:57:05 (5 weeks ago)
Author:
Zipheir
Message:

Update page for 1.0.1 release.

File:
1 edited

Legend:

Unmodified
Added
Removed
  • wiki/eggref/5/integer-map

    r39662 r40217  
    11== Integer Mappings
    22
    3 This library defines integer mappings (imappings), which are immutable
    4 structures that define a set of associations between exact integers
    5 and arbitrary Scheme objects.  The interface is inspired by
    6 [[srfi-146]] and by Haskell's
    7 [[https://hackage.haskell.org/package/containers-0.6.4.1/docs/Data-IntMap-Strict.html|IntMap]]
    8 library.
     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]].
    97
    108Integer maps are implemented as immutable radix trees, as described by
     
    1311These provide fast lookup and set-theoretical operations.
    1412
    15 Many functions make use of Maybe values.  See [[srfi-189]] for details
    16 on this type.
    17 
    18 This is a new library, and the interface is subject to change.  Please
    19 send any feedback to the author.
    20 
    2113[[toc:]]
    2214
    23 == Specification
     15== Library
    2416
    2517=== Notation
    26 
    27 The naming conventions of this document are consistent with those used
    28 in the R7RS Scheme standard.
    2918
    3019The following names are used for the parameters of procedures:
    3120<table>
    32 <tr><td>''obj''</td><td>Any Scheme object.</td></tr>
    33 <tr><td>''boolean''</td><td>A boolean.</td></tr>
    34 <tr><td>''imap''</td><td>An integer map (imapping).</td></tr>
    35 <tr><td>''k''</td><td>An exact integer.</td></tr>
    36 <tr><td>''list''</td><td>A proper list.</td></tr>
    37 <tr><td>''alist''</td><td>An association list.</td></tr>
    38 <tr><td>''proc''</td><td>A procedure.</td></tr>
    39 <tr><td>''mproc''</td><td>A procedure returning a Maybe object.</td></tr>
    40 <tr><td>''pred''</td><td>A predicate.</td></tr>
    41 <tr><td>''comp''</td><td>A [[srfi-128]] comparator object.</td></tr>
     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>
    4230</table>
    4331It is an error (unless otherwise noted) if the procedures are passed arguments
    4432that do not have the type implied by the argument names.
    4533
    46 Each procedure is written in the form
    47 
    48 <procedure>(proc arg₁ arg₂ 
) → type₁ type₂ 
</procedure>
    49 
    50 where ''proc'' is the name of the procedure, the ''args'' are its
    51 parameters, and the ''types'' are the types of the objects it returns.
    52 The latter refer (informally) to Scheme types, e.g. boolean, integer,
    53 etc.  An exception is the notation '*', which indicates that the type
    54 of the value depends on the context of the procedure call.
    55 For example, Scheme's {{list-ref}} procedure would be written
    56 
    57 <procedure>(list-ref list k) → *</procedure>
    58 
    59 since the type of the return value depends on ''list''.
     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.
    6041
    6142=== Constructors
    6243
    63 <procedure>(imapping k₁ obj₁ k₂ 
) → imapping</procedure>
    64 
    65 Returns a new imapping.  The arguments alternate between keys (which
    66 must be exact integers) and values (which may be anything); the
    67 resulting imapping contains these (''k'', ''obj'') associations.
    68 The number of arguments must be even.  If duplicate keys occur in
    69 the arguments, earlier associations take priority.
    70 
    71 <procedure>(imapping-unfold stop? mapper successor seed) → imapping</procedure>
    72 
    73 Unfold a new imapping from the initial seed value ''seed''.
    74 ''mapper'' is applied to each seed and returns two values, a key
    75 (which must be an exact integer) and an associated value (which may be
    76 anything); ''successor'' maps each seed to a new seed;
    77 unfolding terminates when the predicate ''stop?'' returns a true
    78 value when applied to the current seed.
    79 
    80 <procedure>(imapping-unfold-maybe mproc seed) → imapping</procedure>
    81 
    82 Unfold a new imapping.  ''mproc'' is applied to ''seed'' and returns
    83 a Maybe value.  If this value is Nothing, then unfolding terminates.
    84 If it is a Just of three values ''k, v, seed′'', then a new association
    85 ''(k, v)'' is added to the resulting imapping and unfolding continues
    86 with ''seed′''.
    87 
    88 The following equivalence between the two imapping-unfold procedures
    89 may clarify things:
    90 
    91     (imapping-unfold p f g x)
    92       ≡
    93     (imapping-unfold-maybe (lambda (s)
    94                              (if (p s)
    95                                  (nothing)
    96                                  (let-values (((k v) (f s)))
    97                                    (just k v (g s)))))
    98                            x)
    99 
    100 <procedure>(alist->imapping alist) → imapping</procedure>
    101 
    102 Returns a new imapping containing the associations of ''alist''.
    103 It is an error if the car of any pair in ''alist'' is not an
    104 exact integer.
     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>
    105138
    106139=== Predicates
    107140
    108 <procedure>(imapping? obj) → boolean</procedure>
    109 
    110 Returns {{#t}} iff ''obj'' is an imapping.
    111 
    112 <procedure>(imapping-contains? imap k) → boolean</procedure>
    113 
    114 Returns {{#t}} iff ''imap'' contains an association for key ''k''.
    115 
    116 <procedure>(imapping-empty? imap) → boolean</procedure>
    117 
    118 Returns {{#t}} iff ''imap'' contains no associations.
    119 
    120 <procedure>(imapping-disjoint? imap₁ imap₂) → boolean</procedure>
    121 
    122 Returns {{#t}} iff ''imap₁'' and ''imap₂'' have no keys in common.
     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>
    123177
    124178=== Accessors
    125179
    126 <procedure>(imapping-lookup imap k) → *-or-false</procedure>
    127 
    128 If an association ''(k, v)'' occurs in ''imap'', returns ''v''.
    129 Otherwise, returns {{#f}}.
    130 
    131 <procedure>(imapping-lookup-default imap k obj) → *</procedure>
    132 
    133 If an association ''(k, v)'' occurs in ''imap'', returns ''v''.
    134 Otherwise, returns ''obj''.
    135 
    136 <procedure>(imapping-min imap) → maybe[exact-integer, *]</procedure>
    137 
    138 Returns Just ''k'' ''v'', where ''k'' is the least key of ''imap''.
    139 If ''imap'' is empty in the sense of {{imapping-empty?}}, returns
    140 Nothing.
    141 
    142 <procedure>(imapping-max imap) → maybe[exact-integer, *]</procedure>
    143 
    144 Returns Just ''k'' ''v'', where ''k'' is the greatest key of ''imap''.
    145 If ''imap'' is empty in the sense of {{imapping-empty?}}, returns
    146 Nothing.
     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>
    147233
    148234=== Updaters
    149235
    150 <procedure>(imapping-adjoin imap k₁ obj₁ k₂ 
) → imapping</procedure>
    151 
    152 Returns a new imapping containing all of the associations of
    153 ''imap'' as well as the associations (''k''₁, ''v''₁), (''k''₂, ''k''₂), 

     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''₂), 

    154240The number of key/value arguments must be even.
    155241
    156 If any of the keys already have associations in ''imap'', the old
    157 associations are replaced.
    158 
    159 <procedure>(imapping-adjoin/combine imap proc k₁ obj₁ k₂ 
)</procedure>
    160 
    161 Similar to {{imapping-adjoin}}, except that duplicate associations
     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
    162253are combined with ''proc'', which is a procedure of type {{* * → *}}.
    163254''proc'' is called on the new and old values (in that order) associated
    164255with a duplicated key and is expected to return a value for the key.
    165 
    166 <procedure>(imapping-adjust imap k proc) → imapping</procedure>
    167 <procedure>(imapping-adjust/key imap k proc) → imapping</procedure>
    168 
    169 Returns a new imapping in which the association ''(n, v)'' in ''imap''
    170 is replaced by ''(n, (proc v))'', or by ''(n, (proc n v))'' in the
    171 case of `imapping-adjust/key`.  If ''n'' has no association in ''imap'',
    172 then (a copy of) ''imap'' is returned.
    173 
    174 <procedure>(imapping-delete imap k₁ k₂ 
) → imapping</procedure>
    175 
    176 Returns a new imapping with the same associations as ''imap'', except
    177 those for keys equal to ''k₁, k₂, 
''.  If a key does not have an
    178 association in ''imap'', it is ignored.
    179 
    180 <procedure>(imapping-delete-all imap list) → imapping</procedure>
    181 
    182 Returns a new imapping with the same associations as ''imap'', except
     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
    183317those for keys equal to an element of ''list''.
    184318
    185 <procedure>(imapping-update imap k mproc) → imapping</procedure>
    186 <procedure>(imapping-update/key imap k mproc) → imapping</procedure>
    187 
    188 Returns a new imapping with the same associations as ''imap'', except
    189 that the association for ''k'' is updated as follows.  ''mproc'' is
    190 applied to the value associated with ''k''.
    191 If it returns Nothing, the association is deleted;
    192 if it returns Just ''v'', then ''(k, v)'' is added to the new imapping.
    193 
    194 {{imapping-update/key}} is the same as {{imapping-update}}, except that
    195 ''mproc'' is called on ''n'' and its associated value, in that order.
    196 
    197 Simple versions of several other update operations may be defined
    198 in terms of {{imapping-update}}, e.g.:
    199 
    200     (imapping-delete imap k)
    201   ≡
    202     (imapping-update imap k (lambda (_) (nothing)))
    203 
    204     (imapping-adjoin imap k v)
    205   ≡
    206     (imapping-update imap k (lambda (_) (just v)))
    207 
    208 <procedure>(imapping-alter imap k proc) → imapping</procedure>
    209 
    210 ''proc'' is a procedure of type {{maybe[*] → maybe[*]}}.
    211 
    212 Returns a new imapping with the same associations as ''imap'', except
    213 that the association, or lack thereof, for ''k'' is updated as follows.
    214 If the association ''(k, v)'' exists in ''imap'', then ''proc'' is called on
    215 Just ''v''; if no such association exists, then ''proc'' is called on
    216 Nothing.  If the result of this application is Nothing, the
    217 association is deleted (or no new association is added); if the result
    218 is Just ''v′'', a new association ''(k, v′)'' is added to the new
    219 imapping, replacing any old association for ''k''.
    220 
    221 {{imapping-alter}} is a very general operator on imappings, and most
    222 of the other update operations may be defined in terms of it.  For
    223 example:
    224 
    225       (imapping-update imap k f)
    226     ≡
    227       (imapping-alter imap k (lambda (m)
    228                                (maybe-ref m
    229                                           nothing
    230                                           (lambda (v) (f v)))))
    231 
    232 <procedure>(imapping-delete-min imap) → imapping</procedure>
    233 <procedure>(imapping-delete-max imap) → imapping</procedure>
    234 
    235 Returns a new imapping with the same associations as ''imap'', except
    236 for the association with the least/greatest key.  If ''imap'' is empty,
    237 returns an empty imapping.
    238 
    239 <procedure>(imapping-update-min imap mproc) → imapping</procedure>
    240 <procedure>(imapping-update-max imap mproc) → imapping</procedure>
    241 <procedure>(imapping-update-min/key imap mproc) → imapping</procedure>
    242 <procedure>(imapping-update-max/key imap mproc) → imapping</procedure>
    243 
    244 The ''mproc'' argument of {{imapping-update-min}} and {{-max}} is of
    245 type {{* → maybe[*]}}; that of {{imapping-update-min/key}} and of
    246 {{-max/key}} is of type {{exact-integer * → maybe[*]}}.
    247 
    248 Returns a new imapping with the same associations as ''imap'', except
    249 that the association for the least/greatest key ''k'' is updated as
    250 follows.  ''mproc'' is applied to the value associated with ''k'' and is
    251 expected to return a Maybe value.  If it returns Nothing, the
    252 association is deleted; if it returns Just ''v'', then ''(k, v)'' is added
    253 to the new imapping.
    254 
    255 {{imapping-update-min/key}} and {{imapping-update-max/key}} are the same
    256 as {{imapping-update-min}} and {{imapping-update-max}}, respectively,
    257 except that ''mproc'' is called on ''k'' and its associated value, in that
    258 order.
    259 
    260 === Size
    261 
    262 <procedure>(imapping-size imap) → exact-integer</procedure>
    263 
    264 Returns the number of associations in ''imap''.
     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>
    265615
    266616=== Traversal
    267617
    268 <procedure>(imapping-count pred imap) → exact-integer</procedure>
    269 <procedure>(imapping-count/key pred imap) → exact-integer</procedure>
    270 
    271 Returns the number of associations in ''imap'' whose values satisfy
    272 ''pred''.
    273 
    274 {{imapping-count/key}} is the same, except that ''pred'' is called on
    275 the key and value of each association.
    276 
    277 <procedure>(imapping-any? pred imap) → boolean</procedure>
    278 
    279 Returns {{#t}} iff there exists an association in ''imap'' whose value
    280 satisfies ''pred''.  ''imap'' is traversed in ascending numerical order
    281 of keys.
    282 
    283 <procedure>(imapping-every? pred imap) → boolean</procedure>
    284 
    285 Returns {{#t}} iff the value of every association in ''imap'' satisfies
    286 ''pred'', or if ''imap'' is empty.  ''imap'' is traversed in ascending
    287 numerical order of keys.
    288 
    289 <procedure>(imapping-map proc imap) → imapping</procedure>
    290 <procedure>(imapping-map/key proc imap) → imapping</procedure>
    291 
    292 The ''proc'' argument of {{imapping-map}} is of type {{* → *}};
    293 that of {{imapping-map/key}} is of type {{exact-integer * → *}}.
    294 
    295 Returns a new imapping.  For each association ''(n, v)'' in ''imap'',
    296 the association ''(n, (proc v))'' is added to the new imapping.
    297 Associations are traversed in an arbitrary order.
    298 
    299 {{imapping-map/key}} is the same, except that ''proc'' is called on
    300 the key and value of each association.
    301 
    302 Note that, in contrast to SRFI 146's map procedures, these procedures
    303 transform the values of ''imap'' only; that is, the set of keys of the
    304 resulting imapping is the same as that of ''imap''.
    305 
    306 <procedure>(imapping-for-each proc imap) → unspecified</procedure>
    307 <procedure>(imapping-for-each/key proc imap) → unspecified</procedure>
    308 
    309 Calls ''proc'' on the value of each association in ''imap'' and returns
    310 an unspecified value.  ''imap'' in traversed in ascending numerical
     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
    311649order of keys.
    312650
    313 {{imapping-for-each/key}} is the same, except that ''proc'' is called on
    314 the key and value of each association.
    315 
    316 <procedure>(imapping-fold-left kons knil imap) → *</procedure>
    317 <procedure>(imapping-fold-right kons knil imap) → *</procedure>
    318 <procedure>(imapping-fold-left/key kons knil imap) → *</procedure>
    319 <procedure>(imapping-fold-right/key kons knil imap) → *</procedure>
    320 
    321 The ''kons'' argument of {{imapping-fold-left}} and {{-right}} is a
    322 procedure of type {{* * → *}}; that of {{imapping-fold-left/key}}
    323 and of {{-right/key}} is of type {{exact-integer * * → *}}.
    324 ''knil'' can be any object.
    325 
    326 Folds ''kons'' over ''imap'', using ''knil'' as the base value.  At
    327 each step, ''kons'' is applied to the value of an association and to
    328 the result of the last application.
    329 {{imapping-fold-left}} folds in ascending numerical order of keys;
    330 {{imapping-fold-right}} folds in descending order.
    331 
    332 {{imapping-fold-left/key}} and {{imapping-fold-right/key}} are the same
    333 as {{imapping-fold-left}} and {{imapping-fold-right}}, respectively,
    334 except that ''kons'' is also passed the key of each association.
    335 
    336 <procedure>(imapping-map->list proc imap) → list</procedure>
    337 <procedure>(imapping-map/key->list proc imap) → list</procedure>
    338 
    339 Fusion of {{(imapping-values (imapping-map proc imap))}}.
    340 
    341 {{imapping-map/key->list}} is the same, except that ''proc'' is called on
    342 the key and value of each association.
     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.
    343716
    344717=== Filter
    345718
    346 <procedure>(imapping-filter pred imap) → imapping</procedure>
    347 <procedure>(imapping-filter/key pred imap) → imapping</procedure>
    348 
    349 Returns a new imapping containing all of the associations of ''imap''
    350 whose values satisfy ''pred''.
    351 
    352 {{imapping-filter/key}} is the same, except that ''pred'' is applied to
    353 the key and value of each association.
    354 
    355 <procedure>(imapping-remove pred imap) → imapping</procedure>
    356 <procedure>(imapping-remove/key pred imap) → imapping</procedure>
    357 
    358 Returns a new imapping containing all of the associations of ''imap''
    359 whose values do not satisfy ''pred''.
    360 
    361 {{imapping-remove/key}} is the same, except that ''pred'' is applied to
    362 the key and value of each association.
    363 
    364 <procedure>(imapping-partition pred imap) → imapping imapping</procedure>
    365 <procedure>(imapping-partition/key pred imap) → imapping imapping</procedure>
    366 
    367 Returns two new imappings: the first contains all associations of
    368 ''imap'' whose values satisfy ''pred'', and the second contains those
    369 whose values do not.
    370 
    371 {{imapping-partition/key}} is the same, except that ''pred'' is applied to
    372 the key and value of each association.
     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>
    373762
    374763=== Conversion
    375764
    376 <procedure>(imapping->alist imap) → alist[exact-integer, *]</procedure>
    377 
    378 Returns a car/cdr alist containing the associations of ''imap'' in
    379 ascending numerical order of keys.  Example:
    380 
    381     (imapping->alist (imapping 1 'a 2 'b)) ⇒ ((1 . a) (2 . b))
    382 
    383 <procedure>(imapping-keys imap) → list[exact-integer]</procedure>
    384 
    385 Returns the keys of ''imap'' as a list in ascending numerical order.
    386 
    387 <procedure>(imapping-values imap) → list[*]</procedure>
    388 
    389 Returns the elements of ''imap'' as a list in ascending numerical
     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
    390798order of key.
    391799
     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
    392828=== Comparison
    393829
    394 <procedure>(imapping=? comp imap₁ imap₂ imap₃ 
) → boolean</procedure>
    395 
    396 Returns {{#t}} iff all of the ''imaps'' contain equal associations.  Two
     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
    397837associations are equal exactly when their keys are equal (in the sense
    398838of {{=}}) and if their values are equal in the sense of the equality
    399 predicate of ''comp'' (see [[srfi-128]]).
    400 
    401 <procedure>(imapping<? comp imap₁ imap₂ imap₃ 
) → boolean</procedure>
    402 <procedure>(imapping<=? comp imap₁ imap₂ imap₃ 
) → boolean</procedure>
    403 <procedure>(imapping>? comp imap₁ imap₂ imap₃ 
) → boolean</procedure>
    404 <procedure>(imapping>=? comp imap₁ imap₂ imap₃ 
) → boolean</procedure>
    405 
    406 Returns {{#t}} iff each ''imap'' other than the last is a proper
    407 subset/subset/proper superset/superset of the last.  Values are
    408 compared using the equality predicate of ''comp''.
     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>
    409882
    410883=== Set theory operations
    411884
    412 <procedure>(imapping-union imap₁ imap₂ imap₃ 
) → imapping</procedure>
    413 <procedure>(imapping-intersection imap₁ imap₂ imap₃ 
) → imapping</procedure>
    414 <procedure>(imapping-difference imap₁ imap₂ imap₃ 
) → imapping</procedure>
    415 <procedure>(imapping-xor imap₁ imap₂) → imapping</procedure>
    416 
    417 Return a newly allocated imapping whose set of associations is the
    418 union, intersection, asymmetric difference, or symmetric difference of
    419 the sets of associations of the ''imaps''.  Asymmetric difference is
    420 extended to more than two imappings by taking the difference between
    421 the first imapping and the union of the others.  Symmetric difference
    422 is not extended beyond two imappings.  When comparing associations,
    423 only the keys are compared.  In case of duplicate keys, associations
    424 in the result imapping are drawn from the first imapping in which they
    425 appear.
     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>
    426948
    427949=== Submappings
    428950
    429 <procedure>(imapping-open-interval imap low high) → imapping</procedure>
    430 <procedure>(imapping-closed-interval imap low high) → imapping</procedure>
    431 <procedure>(imapping-open-closed-interval imap low high) → imapping</procedure>
    432 <procedure>(imapping-closed-open-interval imap low high) → imapping</procedure>
     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>
    433955
    434956''low'' and ''high'' are both exact integers.
    435957
    436 Procedures that return a subset of ''imap'' containing the associations
     958Procedures that return a subset of ''fxmap'' containing the associations
    437959whose keys are contained in the interval from ''low'' to ''high''.  The
    438960interval may be open, closed, open below and closed above, or open
    439961above and closed below.
    440962
    441 <procedure>(isubmapping= imap k) → imapping</procedure>
    442 <procedure>(isubmapping< imap k) → imapping</procedure>
    443 <procedure>(isubmapping<= imap k) → imapping</procedure>
    444 <procedure>(isubmapping> imap k) → imapping</procedure>
    445 <procedure>(isubmapping>= imap k) → imapping</procedure>
    446 
    447 Procedures that return an imapping containing the associations of
    448 ''imap'' whose keys are equal to, less than/less than or equal
     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
    449986to/greater than/greater than or equal to ''k''.  Note that the result of
    450 {{isubmapping=}} contains at most one element.
     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>
    4511026
    4521027== About This Egg
     
    4601035* [[srfi-143]]
    4611036* [[srfi-145]]
    462 * [[srfi-189]]
    463 * [[matchable]]
    4641037
    4651038=== Author
     
    4791052=== License
    4801053
    481 Copyright (C) Wolfgang Corcoran-Mathe (2020). All rights reserved.
     1054Copyright (C) Wolfgang Corcoran-Mathe (2021). All rights reserved.
    4821055
    4831056Permission is hereby granted, free of charge, to any person obtaining
     
    5021075=== Version history
    5031076
    504 ; 0.1 : Initial release.
    505 ; 0.1.1 : Fix relative path errors when running tests.
    506 ; 0.1.2 : Fix egg file/release-info book-keeping errors.
     1077; 0.1 (2021-03-06) : Initial release.
     1078; 0.1.1 (2021-03-06) : Tests bugfix.
     1079; 0.1.2 (2021-03-06) : Bookkeeping bugfix.
     1080; 1.0.1 (2021-06-26) : Update to current SRFI 224, overhaul interface.
Note: See TracChangeset for help on using the changeset viewer.