[ < ] | [ > ] | [ << ] | [ Up ] | [ >> ] | [Top] | [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***key=? key<?*Creates and returns an instance of

`<tree-map>`

. The arguments`key=?`and`key<?`are both procedures that take two arguments, which are the keys. The`key=?`

procedure should return`#t`

if two arguments are equivalent, or`#f`

otherwise. The`key<?`

procedure should return`#t`

if the first argument is strictly less than the second argument, or`#f`

otherwise.

__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*Applies

`proc`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*Applies

`proc`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-keyLike

`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-valueLike

`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 key=? key<?*Creates a new tree map with

`key=?`and`key<?`, then populates it with`alist`, each pair in which are interpreted as a cons of a key and its value. Returns the created tree map.

[ < ] | [ > ] | [ << ] | [ Up ] | [ >> ] |

This document was generated by *Shiro Kawai* on *May 28, 2012* using *texi2html 1.82*.