Integer Mappings (historical revision 39646)

You are looking at historical revision 39646 of this page. It may differ significantly from its current revision.

Integer Mappings

This library defines integer mappings (imappings), which are immutable structures that define a set of associations between exact integers and arbitrary Scheme objects. The interface is inspired by srfi-146 and by Haskell's IntMap library.

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.

Many functions make use of Maybe values. See srfi-189 for details on this type.

This is a new library, and the interface is subject to change. Please send any feedback to the author.

Specification

Notation

The naming conventions of this document are consistent with those used in the R7RS Scheme standard.

The following names are used for the parameters of procedures:

obj	Any Scheme object.
boolean	A boolean.
imap	An integer map (imapping).
k	An exact integer.
list	A proper list.
alist	An association list.
proc	A procedure.
mproc	A procedure returning a Maybe object.
pred	A predicate.
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.

Each procedure is written in the form

[procedure] (proc arg₁ arg₂ …) → type₁ type₂ …

where proc is the name of the procedure, the args are its parameters, and the types are the types of the objects it returns. The latter refer (informally) to Scheme types, e.g. boolean, integer, etc. An exception is the notation '*', which indicates that the type of the value depends on the context of the procedure call. For example, Scheme's car procedure would be written

[procedure] (car list) → *

since the type of the return value depends on list.

Constructors

[procedure] (imapping k₁ obj₁ k₂ …) → imapping

Returns a new imapping. The arguments alternate between keys (which must be exact integers) and values (which may be anything); the resulting imapping contains these (k, obj) associations. The number of arguments must be even. If duplicate keys occur in the arguments, earlier associations take priority.

[procedure] (imapping-unfold stop? mapper successor seed) → imapping

Unfold a new imapping from the initial seed value seed. mapper is applied to each seed and returns two values, a key (which must be an exact integer) and an associated value (which may be anything); successor maps each seed to a new seed; unfolding terminates when the predicate stop? returns a true value when applied to the current seed.

[procedure] (imapping-unfold-maybe mproc seed) → imapping

Unfold a new imapping. mproc is applied to seed and returns a Maybe value. If this value is Nothing, then unfolding terminates. If it is a Just of three values k, v, seed′, then a new association (k, v) is added to the resulting imapping and unfolding continues with seed′.

The following equivalence between the two imapping-unfold procedures may clarify things:

   (imapping-unfold p f g x)
     ≡
   (imapping-unfold-maybe (lambda (s)
                            (if (p s)
                                (nothing)
                                (let-values (((k v) (f s)))
                                  (just k v (g s)))))
                          x)

[procedure] (alist->imapping alist) → imapping

Returns a new imapping containing the associations of alist. It is an error if the car of any pair in alist is not an exact integer.

Predicates

[procedure] (imapping? obj) → boolean

Returns #t iff obj is an imapping.

[procedure] (imapping-contains? imap k) → boolean

Returns #t iff imap contains an association for key k.

[procedure] (imapping-empty? imap) → boolean

Returns #t iff imap contains no associations.

[procedure] (imapping-disjoint? imap₁ imap₂) → boolean

Returns #t iff imap₁ and imap₂ have no keys in common.

Accessors

[procedure] (imapping-lookup imap k) → *-or-false

If an association (k, v) occurs in imap, returns v. Otherwise, returns #f.

[procedure] (imapping-lookup-default imap k obj) → *

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

[procedure] (imapping-min imap) → maybe[exact-integer, *]

Returns Just k v, where k is the least key of imap. If imap is empty in the sense of imapping-empty?, returns Nothing.

[procedure] (imapping-max imap) → maybe[exact-integer, *]

Returns Just k v, where k is the greatest key of imap. If imap is empty in the sense of imapping-empty?, returns Nothing.

Updaters

[procedure] (imapping-adjoin imap k₁ obj₁ k₂ …) → imapping

Returns a new imapping containing all of the associations of imap 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 imap, the old associations are replaced.

[procedure] (imapping-adjoin/combine imap proc k₁ obj₁ k₂ …)

Similar to imapping-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.

[procedure] (imapping-adjust imap k proc) → imapping
[procedure] (imapping-adjust/key imap k proc) → imapping

Returns a new imapping in which the association (n, v) in imap is replaced by (n, (proc v)), or by (n, (proc n v)) in the case of `imapping-adjust/key`. If n has no association in imap, then (a copy of) imap is returned.

[procedure] (imapping-delete imap k₁ k₂ …) → imapping

Returns a new imapping with the same associations as imap, except those for keys equal to k₁, k₂, …. If a key does not have an association in imap, it is ignored.

[procedure] (imapping-delete-all imap list) → imapping

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

[procedure] (imapping-update imap k mproc) → imapping
[procedure] (imapping-update/key imap k mproc) → imapping

Returns a new imapping with the same associations as imap, except that the association for k is updated as follows. mproc is applied to the value associated with k. If it returns Nothing, the association is deleted; if it returns Just v, then (k, v) is added to the new imapping.

imapping-update/key is the same as imapping-update, except that mproc is called on n and its associated value, in that order.

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

   (imapping-delete imap k)
 ≡
   (imapping-update imap k (lambda (_) (nothing)))

   (imapping-adjoin imap k v)
 ≡
   (imapping-update imap k (lambda (_) (just v)))

[procedure] (imapping-alter imap k proc) → imapping

proc is a procedure of type maybe[*] → maybe[*].

Returns a new imapping with the same associations as imap, except that the association, or lack thereof, for k is updated as follows. If the association (k, v) exists in imap, then proc is called on Just v; if no such association exists, then proc is called on Nothing. If the result of this application is Nothing, the association is deleted (or no new association is added); if the result is Just v′, a new association (k, v′) is added to the new imapping, replacing any old association for k.

imapping-alter is a very general operator on imappings, and most of the other update operations may be defined in terms of it. For example:

     (imapping-update imap k f)
   ≡
     (imapping-alter imap k (lambda (m)
                              (maybe-ref m
                                         nothing
                                         (lambda (v) (f v)))))

[procedure] (imapping-delete-min imap) → imapping
[procedure] (imapping-delete-max imap) → imapping

Returns a new imapping with the same associations as imap, except for the association with the least/greatest key. If imap is empty, returns an empty imapping.

[procedure] (imapping-update-min imap mproc) → imapping
[procedure] (imapping-update-max imap mproc) → imapping
[procedure] (imapping-update-min/key imap mproc) → imapping
[procedure] (imapping-update-max/key imap mproc) → imapping

The mproc argument of imapping-update-min and -max is of type * → maybe[*]; that of imapping-update-min/key and of -max/key is of type exact-integer * → maybe[*].

Returns a new imapping with the same associations as imap, except that the association for the least/greatest key k is updated as follows. mproc is applied to the value associated with k and is expected to return a Maybe value. If it returns Nothing, the association is deleted; if it returns Just v, then (k, v) is added to the new imapping.

imapping-update-min/key and imapping-update-max/key are the same as imapping-update-min and imapping-update-max, respectively, except that mproc is called on k and its associated value, in that order.

Size

[procedure] (imapping-size imap) → exact-integer

Returns the number of associations in imap.

Traversal

[procedure] (imapping-count pred imap) → exact-integer
[procedure] (imapping-count/key pred imap) → exact-integer

Returns the number of associations in imap whose values satisfy pred.

imapping-count/key is the same, except that pred is called on the key and value of each association.

[procedure] (imapping-any? pred imap) → boolean

Returns #t iff there exists an association in imap whose value satisfies pred. imap is traversed in ascending numerical order of keys.

[procedure] (imapping-every? pred imap) → boolean

Returns #t iff the value of every association in imap satisfies pred, or if imap is empty. imap is traversed in ascending numerical order of keys.

[procedure] (imapping-map proc imap) → imapping
[procedure] (imapping-map/key proc imap) → imapping

The proc argument of imapping-map is of type * → *; that of imapping-map/key is of type exact-integer * → *.

Returns a new imapping. For each association (n, v) in imap, the association (n, (proc v)) is added to the new imapping. Associations are traversed in an arbitrary order.

imapping-map/key is the same, except that proc is called on the key and value of each association.

Note that, in contrast to SRFI 146's map procedures, these procedures transform the values of imap only; that is, the set of keys of the resulting imapping is the same as that of imap.

[procedure] (imapping-for-each proc imap) → unspecified
[procedure] (imapping-for-each/key proc imap) → unspecified

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

imapping-for-each/key is the same, except that proc is called on the key and value of each association.

[procedure] (imapping-fold-left kons knil imap) → *
[procedure] (imapping-fold-right kons knil imap) → *
[procedure] (imapping-fold-left/key kons knil imap) → *
[procedure] (imapping-fold-right/key kons knil imap) → *

The kons argument of imapping-fold-left and -right is a procedure of type * * → *; that of imapping-fold-left/key and of -right/key is of type exact-integer * * → *. knil can be any object.

Folds kons over imap, using knil as the base value. At each step, kons is applied to the value of an association and to the result of the last application. imapping-fold-left folds in ascending numerical order of keys; imapping-fold-right folds in descending order.

imapping-fold-left/key and imapping-fold-right/key are the same as imapping-fold-left and imapping-fold-right, respectively, except that kons is also passed the key of each association.

[procedure] (imapping-map->list proc imap) → list
[procedure] (imapping-map/key->list proc imap) → list

Fusion of (imapping-values (imapping-map proc imap)).

imapping-map/key->list is the same, except that proc is called on the key and value of each association.

Filter

[procedure] (imapping-filter pred imap) → imapping
[procedure] (imapping-filter/key pred imap) → imapping

Returns a new imapping containing all of the associations of imap whose values satisfy pred.

imapping-filter/key is the same, except that pred is applied to the key and value of each association.

[procedure] (imapping-remove pred imap) → imapping
[procedure] (imapping-remove/key pred imap) → imapping

Returns a new imapping containing all of the associations of imap whose values do not satisfy pred.

imapping-remove/key is the same, except that pred is applied to the key and value of each association.

[procedure] (imapping-partition pred imap) → imapping imapping
[procedure] (imapping-partition/key pred imap) → imapping imapping

Returns two new imappings: the first contains all associations of imap whose values satisfy pred, and the second contains those whose values do not.

imapping-partition/key is the same, except that pred is applied to the key and value of each association.

Conversion

[procedure] (imapping->alist imap) → alist[exact-integer, *]

Returns a car/cdr alist containing the associations of imap in ascending numerical order of keys. Example:

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

[procedure] (imapping-keys imap) → list[exact-integer]

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

[procedure] (imapping-values imap) → list[*]

Returns the elements of imap as a list in ascending numerical order of key.

Comparison

[procedure] (imapping=? comp imap₁ imap₂ imap₃ …) → boolean

Returns #t iff all of the imaps 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 (see srfi-128).

[procedure] (imapping<? comp imap₁ imap₂ imap₃ …) → boolean
[procedure] (imapping<=? comp imap₁ imap₂ imap₃ …) → boolean
[procedure] (imapping>? comp imap₁ imap₂ imap₃ …) → boolean
[procedure] (imapping>=? comp imap₁ imap₂ imap₃ …) → boolean

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

Set theory operations

[procedure] (imapping-union imap₁ imap₂ imap₃ …) → imapping
[procedure] (imapping-intersection imap₁ imap₂ imap₃ …) → imapping
[procedure] (imapping-difference imap₁ imap₂ imap₃ …) → imapping
[procedure] (imapping-xor imap₁ imap₂) → imapping

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

Submappings

[procedure] (imapping-open-interval imap low high) → imapping
[procedure] (imapping-closed-interval imap low high) → imapping
[procedure] (imapping-open-closed-interval imap low high) → imapping
[procedure] (imapping-closed-open-interval imap low high) → imapping

low and high are both exact integers.

Procedures that return a subset of imap 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.

[procedure] (isubmapping= imap k) → imapping
[procedure] (isubmapping< imap k) → imapping
[procedure] (isubmapping<= imap k) → imapping
[procedure] (isubmapping> imap k) → imapping
[procedure] (isubmapping>= imap k) → imapping

Procedures that return an imapping containing the associations of imap 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 isubmapping= contains at most one element.

About This Egg

Dependencies

The following eggs are required:

Author

Wolfgang Corcoran-Mathe

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

Maintainer

Wolfgang Corcoran-Mathe

Repository

GitHub

License

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

[Release pending.]