chickadee » integer-map

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 SRFI 224.

Integer maps are implemented as immutable radix trees, as described by Chris Okasaki and Andrew Gill in "Fast Mergeable Integer Maps". These provide fast lookup and set-theoretical operations.

Library

Notation

The following names are used for the parameters of procedures:

obj	Any Scheme object.
boolean	A boolean.
fxmap	A fxmapping with values of arbitrary type.
k	A fixnum, satisfying fixnum?.
list	A proper list.
alist	An association list.
proc	A procedure.
pred	A predicate, assumed to entail no side-effects.
comp	A SRFI 128 comparator object.

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

fxmapping k₁ obj₁ k₂ …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:

(fxmapping->alist (fxmapping 0 'a 1 'b 2 'c)) ⇒ ((0 . a) (1 . b) (2 . c))
(fxmapping->alist (fxmapping -10 "worf" -10 "yar")) ⇒ ((-10 . "worf"))

fxmapping-unfold stop? mapper successor seed₁ seed₂ …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

(call-with-values
 (lambda () (successor seed₁ seed₂ … ))
 mapper)

must result in a valid procedure application.

Unfold a fxmapping from the initial seeds. mapper is applied to the seeds and returns two values, a key and an associated value, which are adjoined to the new fxmapping. successor maps the seeds 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:

(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"))

fxmapping-accumulate proc seed₁ seed₂ …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 seeds. proc is applied to a procedure abort-with-result and the seeds, 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:

(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

Predicates

fxmapping? objprocedure

Returns #t if and only if obj is a fxmapping.

fxmapping-contains? fxmap kprocedure

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

Examples:

(fxmapping-contains? (fxmapping 1 'b) 1) ⇒ #t
(fxmapping-contains? (fxmapping 1 'b) 0) ⇒ #f

fxmapping-empty? fxmapprocedure

Returns #t if and only if fxmap contains no associations.

Examples:

(fxmapping-empty? (alist->fxmapping '())) ⇒ #t
(fxmapping-empty? (alist->fxmapping '((0 . a)))) ⇒ #f

fxmapping-disjoint? fxmap₁ fxmap₂procedure

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

Examples:

(fxmapping-disjoint? (fxmapping 0 'a) (fxmapping 1 'b)) ⇒ #t
(fxmapping-disjoint? (fxmapping 1 '(b)) (fxmapping 1 'b)) ⇒ #f

Accessors

fxmapping-ref fxmap k #!optional failure successprocedure

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:

(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

fxmapping-ref/default fxmap k objprocedure

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

Examples:

(fxmapping-ref/default (fxmapping 36864 'zap) 36864 #f) ⇒ zap
(fxmapping-ref/default (fxmapping 0 'a) 36864 #f) ⇒ #f

fxmapping-min fxmapprocedure

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

Example:

(fxmapping-min (fxmapping 0 'a 1 'b 2 'c)) ⇒ 0 a

fxmapping-max fxmapprocedure

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

Example:

(fxmapping-max (fxmapping 0 'a 1 'b 2 'c)) ⇒ 2 c

Updaters

fxmapping-adjoin fxmap k₁ obj₁ k₂ …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.

(fxmapping->alist (fxmapping-adjoin (fxmapping 1 'b) 0 'a))
 ⇒ ((0 . a) (1 . b))

fxmapping-adjoin/combinator fxmap proc k₁ obj₁ k₂ …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:

(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"))

fxmapping-set fxmap k₁ obj₁ k₂ …procedure

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

Example:

(fxmapping->alist
 (fxmapping-set (fxmapping 0 "geordi" 1 "reginald") 1 "tasha"))
 ⇒ ((0 . "geordi") (1 . "tasha"))

fxmapping-adjust fxmap k procprocedure

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:

(fxmapping->alist
 (fxmapping-adjust (fxmapping 64 "var")
                   64
                   (lambda (k s) (string-append s (number->string k)))))
 ⇒ ((64 . "var64"))

fxmapping-delete fxmap k₁ k₂ …procedure

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

Example:

(fxmapping->alist (fxmapping-delete (fxmapping 0 -200 1 -100) 0))
 ⇒ ((1 . -100))

fxmapping-delete-all fxmap listprocedure

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

(fxmapping->alist (fxmapping-delete-all (fxmapping 0 'a 1 'b 2 'c) '(1 2)))
 ⇒ ((0 . a))

fxmapping-update fxmap k proc #!optional failureprocedure

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:

(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))

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

(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)))

Examples:

;; 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))

fxmapping-alter fxmap k failure successprocedure

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:

;; 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

Examples:

;; 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))

fxmapping-delete-min fxmapprocedure

fxmapping-delete-max fxmapprocedure

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:

(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))

fxmapping-update-min fxmap procprocedure

fxmapping-update-max fxmap procprocedure

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:

(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))

Examples:

(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))

fxmapping-pop-min fxmapprocedure

fxmapping-pop-max fxmapprocedure

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:

(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)))

The whole fxmapping

fxmapping-size fxmapprocedure

Returns the number of associations in fxmap.

fxmapping-find pred fxmap failure #!optional successprocedure

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:

(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")

fxmapping-count pred fxmapprocedure

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:

(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

fxmapping-any? pred fxmapprocedure

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:

(fxmapping-any? (lambda (_ v) (odd? v))
                (fxmapping 0 1 1 2 2 4 3 8)) ⇒ #t

fxmapping-every? pred fxmapprocedure

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:

(fxmapping-every? (lambda (_ v) (integer? v))
                  (fxmapping 0 1 1 2 2 4 3 8)) ⇒ #t

Traversal

fxmapping-map proc fxmapprocedure

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:

(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"))

fxmapping-for-each proc fxmapprocedure

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:

(let ((sum 0))
  (fxmapping-for-each (lambda (_ v) (set! sum (+ sum v)))
                      (fxmapping 0 1 1 2 2 4 3 8))
  sum)
 ⇒ 15

fxmapping-fold kons knil fxmapprocedure

fxmapping-fold-right kons knil fxmapprocedure

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:

(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)

fxmapping-map->list proc fxmapprocedure

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

Example:

(fxmapping-map->list (lambda (_ v) (string-length v))
                     (fxmapping 0 "picard" 1 "riker" 2 "troi"))
 ⇒ (6 5 4)

fxmapping-relation-map proc fxmapprocedure

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

fxmapping-filter pred fxmapprocedure

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

Example:

(fxmapping->alist
 (fxmapping-filter (lambda (_ v) (positive? v))
                   (fxmapping 0 2 1 -4 2 8 3 -16)))
 ⇒ ((0 . 2) (2 . 8))

fxmapping-remove pred fxmapprocedure

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

Example:

(fxmapping->alist
 (fxmapping-remove (lambda (_ v) (positive? v))
                   (fxmapping 0 2 1 -4 2 8 3 -16)))
 ⇒ ((1 . -4) (3 . -16))

fxmapping-partition pred fxmapprocedure

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:

(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))

Conversion

fxmapping->alist fxmapprocedure

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

Example:

(fxmapping->alist (fxmapping 1 'a 2 'b)) ⇒ ((1 . a) (2 . b))

fxmapping->decreasing-alist fxmapprocedure

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

Example:

(fxmapping->alist (fxmapping 1 'a 2 'b)) ⇒ ((2 . b) (1 . a))

fxmapping-keys fxmapprocedure

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

Example:

(fxmapping-keys (fxmapping 137 'a -24 'b -5072 'c)) ⇒ (-5072 -24 137)

fxmapping-values fxmapprocedure

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

Example:

(fxmapping-values (fxmapping 0 "picard" 1 "riker" 2 "troi"))
 ⇒ ("picard" "riker" "troi")

fxmapping->generator fxmappingprocedure

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

Example:

(generator->list (fxmapping->generator (fxmapping 3 "yar" 2 "troi")))
 ⇒ ((2 . "troi") (3 . "yar"))

fxmapping->decreasing-generator fxmappingprocedure

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

Example:

(generator->list (fxmapping->decreasing-generator (fxmapping 3 "yar" 2 "troi")))
 ⇒ ((3 . "yar") (2 . "troi"))

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 =.)

fxmapping=? comp fxmap₁ fxmap₂ fxmap₃ …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:

(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

fxmapping<? comp fxmap₁ fxmap₂ fxmap₃ …procedure

fxmapping<=? comp fxmap₁ fxmap₂ fxmap₃ …procedure

fxmapping>? comp fxmap₁ fxmap₂ fxmap₃ …procedure

fxmapping>=? comp fxmap₁ fxmap₂ fxmap₃ …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:

(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

Set theory operations

fxmapping-union fxmap₁ fxmap₂ fxmap₃ …procedure

fxmapping-intersection fxmap₁ fxmap₂ fxmap₃ …procedure

fxmapping-difference fxmap₁ fxmap₂ fxmap₃ …procedure

fxmapping-xor fxmap₁ fxmap₂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:

(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))

fxmapping-union/combinator proc fxmap₁ fxmap₂ fxmap₃ …procedure

fxmapping-intersection/combinator proc fxmap₁ fxmap₂ fxmap₃ …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:

;; 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"))

Submappings

fxmapping-open-interval fxmap low highprocedure

fxmapping-closed-interval fxmap low highprocedure

fxmapping-open-closed-interval fxmap low highprocedure

fxmapping-closed-open-interval fxmap low highprocedure

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:

(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))

fxsubmapping= fxmap kprocedure

fxsubmapping< fxmap kprocedure

fxsubmapping<= fxmap kprocedure

fxsubmapping> fxmap kprocedure

fxsubmapping>= fxmap kprocedure

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:

(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))

fxmapping-split fxmap kprocedure

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

(values (fxsubmapping<= fxmap k) (fxsubmapping> fxmap k))

but is implemented more efficiently.

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

Example:

(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)))

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

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.