Next: Weak pointers, Previous: Hashtables, Up: Core library [Contents][Index]

- Builtin Class:
**<tree-map>** -
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.

The

`<tree-map>`

class inherits`<sequence>`

and`<ordered-dictionary>`

.

- Function:
**make-tree-map***:optional comparator* - Function:
**make-tree-map***key=? key<?* Creates and returns an instance of

`<tree-map>`

. The keys are compared by`comparator`, whose default is`default-comparator`

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

`make-tree-map`

also accepts a procedure as a`comparator`; the procedure must take two keys and returns either`-1`

,`0`

, or`1`

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

- Function:
**tree-map-comparator***tree-map* Returns the comparator used in the tree map.

- Function:
**tree-map-copy***tree-map* Copies and returns

`tree-map`. Modification on the returned tree doesn’t affect the original tree.

- Function:
**tree-map-empty?***tree-map* Returns

`#t`

if`tree-map`doesn’t have any elements, or`#f`

otherwise.

- Function:
**tree-map-num-entries***tree-map* Returns the number of elements in

`tree-map`.

- Function:
**tree-map-exists?***tree-map key* Returns

`#t`

if`tree-map`has an entry with`key`, or`#f`

otherwise.

- Function:
**tree-map-get***tree-map key :optional fallback* 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.

- Function:
**tree-map-put!***tree-map key value* 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`.

- Function:
**tree-map-delete!***tree-map key* Deletes an entry with

`key`from`tree-map`if such an entry exists, and returns`#t`

. If`tree-map`doesn’t have such an entry,`#f`

is returned.

- Function:
**tree-map-clear!***tree-map* Removes all entries in

`tree-map`.

- Function:
**tree-map-update!***tree-map key proc :optional fallback* A generalized version of

`tree-map-push!`

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

- Function:
**tree-map-push!***tree-map key value* 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`and makes`(list`

its value.`value`)

- Function:
**tree-map-pop!***tree-map key :optional fallback* 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.

- Function:
**tree-map-min***tree-map* - Function:
**tree-map-max***tree-map* Returns a pair of a key and its value with the minimum or maximum key, respectively. If

`tree-map`is empty,`#f`

is returned.

- Function:
**tree-map-pop-min!***tree-map* - Function:
**tree-map-pop-max!***tree-map* 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.

- Function:
**tree-map-fold***tree-map proc seed* - Function:
**tree-map-fold-right***tree-map proc seed* Iterate over elements in

`tree-map`, applying`proc`which has a type`(key, value, seed) -> seed`

. The difference of`tree-map-fold`

and`tree-map-fold-right`

is the associative order of applying`proc`

, just like the difference between`fold`

and`fold-right`

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

Some examples:

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

- Function:
**tree-map-map***tree-map proc* 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. (Note: Like`map`

, the order that`proc`is actually called is unspecified;`proc`is better to be side-effect free.)

- Function:
**tree-map-for-each***tree-map proc* 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.

- Function:
**tree-map-floor***tree-map probe :optional fallback-key fallback-value* - Function:
**tree-map-ceiling***tree-map probe :optional fallback-key fallback-value* - Function:
**tree-map-predecessor***tree-map probe :optional fallback-key fallback-value* - Function:
**tree-map-successor***tree-map probe :optional fallback-key fallback-value* 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`#f`

.The criteria of “closest” differ slightly among these procedures;

`tree-map-floor`

finds the maximum key which is no greater than`probe`;`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`; and`tree-map-successor`

finds the minimum key which is strictly greater than`probe`.

- Function:
**tree-map-floor-key***tree-map probe*`optional`fallback-key - Function:
**tree-map-ceiling-key***tree-map probe*`optional`fallback-key - Function:
**tree-map-predecessor-key***tree-map probe*`optional`fallback-key - Function:
**tree-map-successor-key***tree-map probe*`optional`fallback-key Like

`tree-map-floor`

etc., but only returns the key of the found entry (or`fallback-key`if there’s no entry which satisfies the criteria).

- Function:
**tree-map-floor-value***tree-map probe*`optional`fallback-value - Function:
**tree-map-ceiling-value***tree-map probe*`optional`fallback-value - Function:
**tree-map-predecessor-value***tree-map probe*`optional`fallback-value - Function:
**tree-map-successor-value***tree-map probe*`optional`fallback-value Like

`tree-map-floor`

etc., but only returns the value of the found entry (or`fallback-value`if there’s no entry which satisfies the criteria).

- Function:
**tree-map-keys***tree-map* - Function:
**tree-map-values***tree-map* Returns a list of all keys and all values, respectively. The keys and values are in ascending order of the keys.

- Function:
**tree-map->alist***tree-map* Returns a list of pairs of keys and values for all entries. The pairs are in ascending order of the keys.

- Function:
**alist->tree-map***alist :optional comparator* - Function:
**alist->tree-map***alist key=? key<?* 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`make-tree-map`

.

The following two procedures compares two tree maps with slightly different views.

- Function:
**tree-map-compare-as-sets***tree-map1 tree-map2 :optional value=? fallback* Compares two tree maps as sets of entries. If we look at tree maps as sets of entries, we can define a partial order between two maps; they are equal to each other if they have exactly the same entries, and tree-map A is smaller than tree-map B if A us a strict subset of B.

If

`tree-map1`and`tree-map2`are the same, 0 is returned. If`tree-map1`is smaller than`tree-map2`, -1 is returned. If`tree-map1`is greater than`tree-map2`, 1 is returned.If one argument isn’t subset of the other, we can’t determine the order. In such a case, if

`fallback`is given, it is returned. Otherwise, an error is signalled.The comparators of

`tree-map1`and`tree-map2`must be the same (`equal?`

), otherwise an error is signalled. See Basic comparators, about the comparators.An entry is equal to another entry if their keys match in terms of the comparator of the tree-map, and also their values match with the provided

`value=?`predicate, which is defaulted to`equal?`

.(tree-map-compare-as-sets (alist->tree-map '((1 . a) (2 . b) (3 . c)) default-comparator) (alist->tree-map '((3 . c) (1 . a) (2 . b)) default-comparator)) ⇒ 0 (tree-map-compare-as-sets (alist->tree-map '((1 . a) (3 . c)) default-comparator) (alist->tree-map '((3 . c) (1 . a) (2 . b)) default-comparator)) ⇒ -1 (tree-map-compare-as-sets (alist->tree-map '((1 . a) (3 . c) (4 . d) (2 . b)) default-comparator) (alist->tree-map '((3 . c) (1 . a) (2 . b)) default-comparator)) ⇒ 1 (tree-map-compare-as-sets (alist->tree-map '((1 . a) (3 . c) (4 . d)) default-comparator) (alist->tree-map '((3 . c) (1 . a) (2 . b)) default-comparator)) ⇒ ERROR: tree-maps can't be ordered (tree-map-compare-as-sets (alist->tree-map '((1 . a) (3 . c) (4 . d)) default-comparator) (alist->tree-map '((3 . c) (1 . a) (2 . b)) default-comparator) eq? #f) ⇒ #f

- Function:
**tree-map-compare-as-sequences***tree-map1 tree-map2 :optional value-cmp* Compares two tree maps as sequence of entries, ordered by keys. If both maps have entries with the same key, we use a comparator

`value-cmp`to break the tie (naturally,`value-cmp`must have ordering predicate.) If`value-cmp`is omitted,`default-comparator`

is used.The comparators of

`tree-map1`and`tree-map2`must be the same (`equal?`

), otherwise an error is signalled. See Basic comparators, about the comparators.If

`tree-map1`and`tree-map2`are the same, 0 is returned. If`tree-map1`is smaller than`tree-map2`, -1 is returned. If`tree-map1`is greater than`tree-map2`, 1 is returned.Unlike

`tree-map-compare-as-sets`

, this procedure defines total order of tree maps which share the same comparator.(tree-map-compare-as-sequences (alist->tree-map '((1 . a) (3 . c)) default-comparator) (alist->tree-map '((3 . c) (2 . b)) default-comparator)) ⇒ -1 (tree-map-compare-as-sequences (alist->tree-map '((2 . b) (3 . d)) default-comparator) (alist->tree-map '((3 . c) (2 . b)) default-comparator)) ⇒ 1

Next: Weak pointers, Previous: Hashtables, Up: Core library [Contents][Index]