For Gauche 0.9.5


Next: , Previous: , Up: Library modules - Gauche extensions   [Contents][Index]

9.8 gauche.dictionary - Dictionary framework

Module: gauche.dictionary

A dictionary is an abstract class for objects that can map a key to a value. This module provides some useful generic functions for dictionaries, plus generic dictionary classes built on top of other dictionary classes.


Next: , Previous: , Up: Dictionary framework   [Contents][Index]

9.8.1 Generic functions for dictionaries

These generic functions are useful to implement algorithms common to any dictionary-like objects, a data structure that maps discrete, finite set of keys to values. (Theoretically we can think of continuous and/or infinite set of keys, but implementation-wise it is cleaner to limit the dictionary

Among built-in classes, <hash-table> and <tree-map> implement the dictionary interface. All the <dbm> classes provided by dbm module also implement it.

To make your own class implement the dictionary interface, you have to provide at least dict-get, dict-put!, dict-delete!, dict-fold and dict-comparator. (You can omit dict-delete! if the datatype doesn’t allow deleting entries.) Other generic functions have default behavior built on top of these. You can implement other methods as well, potentially to gain better performance.

(Note: Dictionaries are also collections, so you can use collection methods as well; for example, to get the number of entries, just use size-of).

Generic function: dict-get (dict <dictionary>) key :optional default

Returns the value corresponding to the key. If the dictionary doesn’t have an entry with key, returns default when it is provided, or raises an error if not.

Generic function: dict-put! (dict <dictionary>) key value

Puts the mapping from key to value into the dictionary.

Generic function: (setter dict-get) (dict <dictionary>) key value

This works the same as dict-put!.

Generic function: dict-exists? (dict <dictionary>) key

Returns #t if the dictionary has an entry with key, #f if not.

Generic function: dict-delete! (dict <dictionary>) key

Removes an entry with key form the dictionary. If the dictionary doesn’t have such an entry, this function is noop.

Generic function: dict-clear! (dict <dictionary>)

Empties the dictionary. Usually this is much faster than looping over keys to delete them one by one.

Generic function: dict-comparator (dict <dictionary>)

Should return a comparator used to compare keys.

Generic function: dict-fold (dict <dictionary>) proc seed

Calls a procedure proc over each entry in a dictionary dict, passing a seed value. Three arguments are given to proc; an entry’s key, an entry’s value, and a seed value. Initial seed value is seed. The value returned from proc is used for the seed value of the next call of proc. The result of the last call of proc is returned from dict-fold.

If dict is <ordered-dictionary>, proc is called in the way to keep the following associative order, where the key is ordered from K0 (minimum) to Kn (maximum), and the corresponding values is from V0 to Vn:

(proc Kn Vn (proc Kn-1 Vn-1 ... (proc K0 V0 seed)))
Generic function: dict-fold-right (dict <ordered-dictionary>) proc seed

Like dict-fold, but the associative order of applying proc is reversed as follows:

(proc K0 V0 (proc K1 V1 ... (proc Kn Vn seed)))

This generic function is only defined on <ordered-dictionary>.

Generic function: dict-for-each (dict <dictionary>) proc

Calls proc with a key and a value of every entry in the dictionary dict. For ordered dictionaries, proc is guaranteed to be called in the increasing order of keys.

Generic function: dict-map (dict <dictionary>) proc

Calls proc with a key and a value of every entry in the dictionary dict, and gathers the result into a list and returns it. For ordered dictionaries, the result is in the increasing order of keys (it doesn’t necessarily mean proc is called in that order).

Generic function: dict-keys (dict <dictionary>)
Generic function: dict-values (dict <dictionary>)

Returns a list of all keys or values of a dictionary dict, respectively. For ordered dictionaries, the returned list is in the increasing order of keys.

Generic function: dict->alist (dict <dictionary>)

Returns a list of pairs of key and value in the dictionary. The order of pairs is undefined.

Generic function: dict-push! (dict <dictionary>) key value

A shorthand way to say (dict-put! dict key (cons value (dict-get dict key '()))). A concrete implementation may be more efficient (e.g. it may not search key twice.)

Generic function: dict-pop! (dict <dictionary>) key :optional fallback

If (dict-get dict key) is a pair p, the entry value is replaced with (cdr p) and the procedure returns (car p). If no entry for key is in the table, or the entry isn’t a a pair, the table isn’t modified, and fallback is returned if given, or an error is raised.

Generic function: dict-update! (dict <dictionary>) key proc :optional fallback

Works like the following code, except that the concrete implementation may be more efficient by looking up key only once.

(rlet1 x (proc (dict-get dict key fallback))
  (dict-put! dict key x))
Macro: define-dict-interface dict-class method proc method2 proc2 …

Many dictionary-like datatypes already has their own procedures that directly corresponds to the generic dictionary API, and adding dictionary interface tends to become a simple repetition of define-methods, like this:

(define-method dict-put! ((dict <my-dict>) key value)
  (my-dict-put! key value))

The define-dict-interface macro is a convenient way to define those methods in a batch. Each method argument is a keyword that corresponds to dict-method, and proc is the name of the datatype-specific procedure. Here’s the definition of dict interface for <tree-map> and you’ll get the idea. You don’t need to provide every dictionary interface.

(define-dict-interface <tree-map>
  :get        tree-map-get
  :put!       tree-map-put!
  :delete!    tree-map-delete!
  :clear!     tree-map-clear!
  :comparator tree-map-comparator
  :exists?    tree-map-exists?
  :fold       tree-map-fold
  :fold-right tree-map-fold-right
  :for-each   tree-map-for-each
  :map        tree-map-map
  :keys       tree-map-keys
  :values     tree-map-values
  :pop!       tree-map-pop!
  :push!      tree-map-push!
  :update!    tree-map-update!
  :->alist    tree-map->alist)

Previous: , Up: Dictionary framework   [Contents][Index]

9.8.2 Generic dictionaries

Class: <bimap>

Provides a bidirectional map (bimap), a relation between two set of values, of which you can lookup both ways.

Internally, a bimap consists of two dictionaries, left map and right map. Think a bimap as a relation between xs and ys. The left map takes an x as a key and returns corresponding y as its value. The right map takes an y as a key and returns corresponding x as its value.

Currently, <bimap> only supports strict one-to-one mapping. Mutating interface (bimap-*-put!, bimap-*-delete! etc) modifies both left and right maps to maintain this one-to-one mapping. (In future, we may provide an option to make many-to-one and many-to-many mappings).

A bimap can be used as a dictionary, with the generic dictionary functions such as dict-get. In such cases, the left map takes precedence; that is, the key given to dict-get etc. is regarded as the key to the left map.

Function: make-bimap left-map right-map :key on-conflict

Creates a new bimap consists of two dictionaries, left-map and right-map. It is the caller’s responsibility to choose appropriate type of dictionaries; for example, if you want to create a relation between a string and a number, you man want to create it like this:

(make-bimap (make-hash-table 'string=?)  ; string -> number
            (make-hash-table 'eqv?))     ; number -> string

The keyword argument on-conflict specifies what will happen when the added entry would conflict the existing entries. The following values are allowed:

:supersede

This is the default behavior. Duplicate relations are silently removed in order to maintain one-to-one mapping. For example, suppose a bimap between strings and numbers has had ("foo", 1) and ("bar", 2). When you try to put ("bar", 2) with this option, the first two entries are removed. Returns #t.

:error

Raises an error when duplicate relations are found.

#f

When duplicate relations are found, does nothing and returns #f.

Note: At this moment, an attempt to add a relation exactly same as the existing one is regareded as a conflict. This limitation may be lifted in future.

Function: bimap-left bimap
Function: bimap-right bimap

Returns the left or right map of bimap, respectively. Do not mutate the returned map, or you’ll break the consistency of the bimap.

Function: bimap-left-get bimap key :optional default
Function: bimap-right-get bimap key :optional default

Lookup the value corresponding to the key in the left or right map of bimap. If no entry is found for key, default is returned if provided, otherwise an error is raised.

Function: bimap-left-exists? bimap key
Function: bimap-right-exists? bimap key

Returns #f if the left or right map of bimap has an entry of the key, #t otherwise.

Function: bimap-put! bimap x y :key on-conflict

Put a relation (x, y) into the bimap. After this, (bimap-left-get x) will return y, and (bimap-left-get y) will return x.

If the bimap already have relations with x and/or y, the conflict is handled according to the value of on-conflict; see make-bimap for the possible values and their meanings. The on-conflict keyword argument can override the bimap’s default setting specified at its creation time.

Function: bimap-left-delete! bimap key
Function: bimap-right-delete! bimap key

Deletes an relation with the given left key or right key from bimap. Both left and right maps are modified so that the consistency is maintained. If there’s no relations with given key, these are noop.


Previous: , Up: Dictionary framework   [Contents][Index]