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

*[procedure]*

`(list-ref list k) → *`

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

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