For Gauche 0.9.9

Next: , Previous: , Up: Core library   [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 :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 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

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: , Previous: , Up: Core library   [Contents][Index]