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.
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.|
|imap||An integer map (imapping).|
|k||An exact integer.|
|list||A proper list.|
|alist||An association list.|
|mproc||A procedure returning a Maybe object.|
|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
- 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.
- 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.
- 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.
- 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.
- 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.
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
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.
- imapping-size imapprocedure
Returns the number of associations in imap.
- 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
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
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-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.
- 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.
- 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.
- 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.
- 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.
- 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.
The following eggs are required:
Contact: <wcm at sigwinch dot xyzzy minus the zy>
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.
- Initial release.
- Fix relative path errors when running tests.
- Fix egg file/release-info book-keeping errors.