[ < ] [ > ]   [ << ] [ Up ] [ >> ]         [Top] [Contents] [Index] [ ? ]

6.16 Treemaps

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