Refactor exception throwing code
Add size function
readme: Don't use question mark in header, so anchor works
Efficient, purely functional integer-keyed maps for R7RS scheme.
To use, import the library file:
(import (int-map))
This library implements a purely functional finite map structure of integer-value pairs. It supports fast retrieval and modification, as well as efficient merging of multiple maps.
The implementation is based on radix trees (AKA patricia trees), as described in:
Chris Okasaki and Andy Gill, "Fast Mergeable Integer Maps", Workshop on ML, September 1998, pages 77-86
Radix trees are fast because they use bit masking, which requires us to have low-level access to the integer keys. R7RS leaves the implementation of integers unspecified, so we use fixnums as defined by SRFI-143, or an equivalent library such as Guile's R6RS fixnums.
This means there is a limit on the size of keys:
all keys should be less than int-map-key-size
,
an implementation-dependent value exported by this library.
This condition is not checked at run time.
Maps must preserve the invariant that keys are unique. Inserting a value at an existing key is called a collision. By default, collisions are resolved by overwriting the old value. In cases where this is not desirable, a resolution function can optionally be passed as the last argument to any function which modifies a mapping.
The complexity of each function is given in big-O notation. These were mostly taken from the Haskell IntMap documentation.
(int-map-empty) -> int-map
O(1). Construct an empty int-map.
(int-map-single key val) -> int-map
O(1). Construct a singleton int-map from an initial key-value binding.
(alist->int-map alist [resolve]) -> int-map
O(n*min(n,W)).
Construct an int-map from alist
, a list of key-value pairs.
By default, elements on the left are replaced
by elements on the right at the same key.
If resolve
is given, instead combine the old and new values
by calling (resolve old val)
, where old
is the old value.
(int-map (key val) ...) -> int-map
O(n*min(n,W)).
Like alist->int-map
but as syntax,
to potentially avoid creating an intermediate list.
(int-map-empty? int-map) -> bool
O(1).
Test whether int-map
is empty.
Use this before passing an int-map to a function
which expects at least one binding, such as int-map-min
.
Otherwise an unspecified error is signaled.
(int-map-size int-map) -> integer
O(n).
Return the size of int-map
.
This currently requires traversing the entire map.
(int-map-min int-map) -> (values key val)
(int-map-max int-map) -> (values key val)
O(min(n,W)).
Return the binding of the minimum or maximum key in int-map
.
The key and associated value are returned as two values.
Raise an unspecified error if int-map
is empty.
Call int-map-empty?
first to check for this condition.
(int-map-lookup key int-map [default]) -> val
O(min(n,W)).
Return the value bound to key
in int-map
.
If key
is not bound in int-map
,
either return default
if it is provided
or raise an exception satisfying int-map-unbound-error?
.
(int-map-insert key val int-map [resolve]) -> int-map
O(min(n,W)).
Bind key
to val
in int-map
.
By default, old values are replaced by new values at the same key.
If resolve
is given, instead combine the old and new values
by calling (resolve old val)
, where old
is the old value.
(int-map-delete key int-map) -> int-map
O(min(n,W)).
Delete the binding for key
in int-map
, if it exists.
(int-map-adjust proc key int-map) -> int-map
O(log n).
Adjust the value bound to key
in int-map
by calling proc
on it.
Modifies the value bound to key
only, if it exists,
without changing the structure of int-map
.
If key
is not bound in int-map
,
raise a continuable exception satisfying int-map-unbound-error?
.
If this exception is continued using with-exception-handler
,
the resulting value is bound in place to the missing key.
You can use this to insert a binding
without traversing the tree a second time:
(define (increment-or-zero key int-map)
(with-exception-handler
(lambda (e)
(cond ((int-map-unbound-error? e)
0)))
(lambda ()
(int-map-adjust (lambda (x) (+ x 1)) key int-map))))
(int-map->asc-alist (increment-or-zero 3 (int-map (3 10))))
;; => ((3 . 11))
(int-map->asc-alist (increment-or-zero 2 (int-map (3 10))))
;; => ((2 . 0) (3 . 10))
(int-map-merge . int-maps) -> int-map
(int-map-merge-with resolve . int-maps) -> int-map
(int-map-merge-list int-maps [resolve]) -> int-map
O(n+int-map).
Combine int-maps
into one containing the union of their bindings.
By default, elements on the left are replaced
by elements on the right at the same key.
If resolve
is provided, instead combine the old and new values
by calling (resolve old val)
, where old
is the old value.
Multiple versions are provided to support different calling conventions.
(int-map-map proc int-map) -> int-map
O(n).
Apply proc
to each value bound in int-map
.
The keys of int-map
are not changed, only the bound values.
(int-map-for-each-asc proc int-map) -> unspecified
(int-map-for-each-desc proc int-map) -> unspecified
O(n).
Iterate over values in int-map
, in ascending or descending order,
applying proc
to each of them for side effects.
(int-map-fold-asc insert accum int-map) -> accum
(int-map-fold-desc insert accum int-map) -> accum
O(n).
Fold over values in int-map
, in ascending or descending order.
With accum
as the base value,
replace calls to int-map-insert
with insert
.
For example, below is a possible definition of int-map-filter
:
(define (int-map-filter pred int-map)
(int-map-fold-asc (lambda (i v int-map)
(if (pred v)
(int-map-insert i v alist)
int-map))
(int-map-empty)
int-map))
(int-map->asc-alist int-map) -> alist
(int-map->desc-alist int-map) -> alist
O(n).
Convert int-map
to an alist, in ascending or descending order.