You can edit this page using wiki syntax for markup.

Article contents:== 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]] === 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. Description of your changes:

I would like to authenticate

Spam control

What do you get when you multiply 0 by 3?