chickadee » integer-map

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:

objAny Scheme object.
booleanA boolean.
imapAn integer map (imapping).
kAn exact integer.
listA proper list.
alistAn association list.
procA procedure.
mprocA procedure returning a Maybe object.
predA predicate.
compA 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

proc arg₁ arg₂ procedure

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 list-ref procedure would be written

list-ref list kprocedure

since the type of the return value depends on list.

Constructors

imapping k₁ obj₁ k₂ procedure

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.

imapping-unfold stop? mapper successor seedprocedure

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.

imapping-unfold-maybe mproc seedprocedure

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)
alist->imapping alistprocedure

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

imapping? objprocedure

Returns #t iff obj is an imapping.

imapping-contains? imap kprocedure

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

imapping-empty? imapprocedure

Returns #t iff imap contains no associations.

imapping-disjoint? imap₁ imap₂procedure

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

Accessors

imapping-lookup imap kprocedure

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

imapping-lookup-default imap k objprocedure

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

imapping-min imapprocedure

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

imapping-max imapprocedure

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

imapping-adjoin imap k₁ obj₁ k₂ procedure

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.

imapping-adjoin/combine imap proc k₁ obj₁ k₂ procedure

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.

imapping-adjust imap k procprocedure
imapping-adjust/key imap k procprocedure

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.

imapping-delete imap k₁ k₂ procedure

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.

imapping-delete-all imap listprocedure

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

imapping-update imap k mprocprocedure
imapping-update/key imap k mprocprocedure

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)))
imapping-alter imap k procprocedure

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)))))
imapping-delete-min imapprocedure
imapping-delete-max imapprocedure

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.

imapping-update-min imap mprocprocedure
imapping-update-max imap mprocprocedure
imapping-update-min/key imap mprocprocedure
imapping-update-max/key imap mprocprocedure

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

imapping-size imapprocedure

Returns the number of associations in imap.

Traversal

imapping-count pred imapprocedure
imapping-count/key pred imapprocedure

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.

imapping-any? pred imapprocedure

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

imapping-every? pred imapprocedure

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.

imapping-map proc imapprocedure
imapping-map/key proc imapprocedure

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.

imapping-for-each proc imapprocedure
imapping-for-each/key proc imapprocedure

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.

imapping-fold-left kons knil imapprocedure
imapping-fold-right kons knil imapprocedure
imapping-fold-left/key kons knil imapprocedure
imapping-fold-right/key kons knil imapprocedure

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.

imapping-map->list proc imapprocedure
imapping-map/key->list proc imapprocedure

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

imapping-filter pred imapprocedure
imapping-filter/key pred imapprocedure

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.

imapping-remove pred imapprocedure
imapping-remove/key pred imapprocedure

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.

imapping-partition pred imapprocedure
imapping-partition/key pred imapprocedure

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

imapping->alist imapprocedure

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))
imapping-keys imapprocedure

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

imapping-values imapprocedure

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

Comparison

imapping=? comp imap₁ imap₂ imap₃ procedure

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

imapping<? comp imap₁ imap₂ imap₃ procedure
imapping<=? comp imap₁ imap₂ imap₃ procedure
imapping>? comp imap₁ imap₂ imap₃ procedure
imapping>=? comp imap₁ imap₂ imap₃ procedure

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

imapping-union imap₁ imap₂ imap₃ procedure
imapping-intersection imap₁ imap₂ imap₃ procedure
imapping-difference imap₁ imap₂ imap₃ procedure
imapping-xor imap₁ imap₂procedure

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

imapping-open-interval imap low highprocedure
imapping-closed-interval imap low highprocedure
imapping-open-closed-interval imap low highprocedure
imapping-closed-open-interval imap low highprocedure

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.

isubmapping= imap kprocedure
isubmapping< imap kprocedure
isubmapping<= imap kprocedure
isubmapping> imap kprocedure
isubmapping>= imap kprocedure

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

Copyright (C) Wolfgang Corcoran-Mathe (2020). 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
Initial release.
0.1.1
Fix relative path errors when running tests.
0.1.2
Fix egg file/release-info book-keeping errors.

Contents »