Tree map class. Tree maps are a data structure that maps key objects to value objects. It’s like hash tables except tree maps uses balanced tree internally. Insertion and lookup is O(log n).
Unlike hashtables, a tree map keeps the order of the keys, so it is easy to traverse entries in the order of keys, to find minimum/maximum keys, or to find a key closest to the given value.
<tree-map> class inherits
Creates and returns an instance of
The keys are compared by comparator,
whose default is
The comparator must have a comparison procedure, for
we need a total order in the keys.
See Basic comparators, for the details.
For the backward compatibility,
accepts a procedure as a comparator; the procedure must
take two keys and returns either
depending on whether the first key is less than, equal to, or
greater than the second key, respectively. In other words, it
is a comparison procedure of a comparator.
The second form of
make-tree-map is also for the
backward compatibility; it takes two procedures, each must
be a procedure that takes two keys; the first one returns
#t iff two keys are equal, and the second one returns
#t iff the first key is strictly smaller than the second.
Returns the comparator used in the tree map.
Copies and returns tree-map. Modification on the returned tree doesn’t affect the original tree.
#t if tree-map doesn’t have any elements,
Returns the number of elements in tree-map.
#t if tree-map has an entry with key,
Looks for key in tree-map. If the entry is found, returns a value corresponding to the key. Otherwise, returns fallback if it is provided, or signals an error.
Inserts an entry with a key and corresponding value into tree-map. If there already exists an entry with a key which is equivalent (under key=?), the entry is modified to have value.
Deletes an entry with key from tree-map if such an entry
exists, and returns
If tree-map doesn’t have such an entry,
#f is returned.
Removes all entries in tree-map.
A generalized version of
It works like the following code, except that searching
for the key is done only once.
(let ((tmp (proc (tree-map-get tree-map key fallback)))) (tree-map-put! tree-map key tmp) tmp)
Looks for an entry with key in tree-map. If it exists,
the procedure conses value to the original value and makes
it as a new value.
Otherwise, the procedure creates a new entry for the key
(list value) its value.
Looks for an entry with key in tree-map. If it exists
and its value is a pair, then the procedure updates
its value with
cdr of the original value, and returns
car of the original entry. If such an entry does not
exist, or has a non-pair value, the procedure doesn’t
modify tree-map and returns fallback if it is given,
otherwise reports an error.
Returns a pair of a key and its value with the minimum
or maximum key, respectively. If tree-map is empty,
#f is returned.
Looks for an entry with minimum or maximum key, respectively,
then deletes the entry from tree-map and returns
a pair of the key and its value of the original entry.
If tree-map is empty,
#f is returned.
Iterate over elements in tree-map, applying
proc which has a type
(key, value, seed) -> seed.
The difference of
is the associative order of applying
just like the difference between
tree-map-fold: (proc Kn Vn (proc Kn-1 Vn-1 ... (proc K0 V0 seed))) tree-map-fold-right (proc K0 V0 (proc K1 V1 ... (proc Kn Vn seed)))
(define tree (alist->tree-map '((3 . a) (7 . b) (5 . c)) = <)) (tree-map-fold tree list* '()) ⇒ (7 b 5 c 3 a) (tree-map-fold-right tree list* '()) ⇒ (3 a 5 c 7 b)
Calls proc, which must take two arguments,
with each key/value pair in tree-map,
and collect the results into a list and returns it. The order
of results corresponds to the order of keys—that is, the first element
of the result list is what proc returns with minimum key and its value,
and the last element of the result list is what proc returns
with the maximum key and its value.
map, the order that proc is actually called
is unspecified; proc is better to be side-effect free.)
Calls proc, which must take two arguments, with each key/value pair in tree-map, in the increasing order of the keys. proc is called purely for side effects; the returned values are discarded.
These procedures search the entry which has the closest key
to the given probe. If such an entry is found, returns
two values, its key and its value. Otherwise, returns two values,
fallback-key and fallback-value, both defaulted to
The criteria of “closest” differ slightly among these procedures;
tree-map-floor finds the maximum key which is no greater than
tree-map-ceiling finds the minimum key which is
no less than probe;
tree-map-predecessor finds the
maximum key which is strictly less than probe;
tree-map-successor finds the minimum key which
is strictly greater than probe.
tree-map-floor etc., but only returns the key of
the found entry (or fallback-key if there’s no entry which satisfies
tree-map-floor etc., but only returns the value of
the found entry (or fallback-value if there’s no entry which satisfies
Returns a list of all keys and all values, respectively. The keys and values are in ascending order of the keys.
Returns a list of pairs of keys and values for all entries. The pairs are in ascending order of the keys.
Creates a new tree map with the comparator or
key=?/key<? procedures, then
populates it with alist, each pair in which are
interpreted as a cons of a key and its value.
The meaning of comparator, key=? and key<? are
the same as