9.5 gauche.dictionary - ディクショナリフレームワーク

Module: gauche.dictionary

ディクショナリはキーから値への写像ができるオブジェクトを表わす抽象クラ スです。このモジュールではディクショナリに対してよく使うジェネリック関数、 および他のディクショナリクラスの上に構築される汎用的なディクショナリクラスを 提供します。

9.5.1 ディクショナリのためのジェネリック関数

These generic functions are useful to implement algorithms common to any dictionary-like objects. 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-exists?, dict-delete! and dict-fold. Other generic functions have default behavior built on top of these. Of course your can implement other methods as well, potentially to gain better performance.

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-fold (dict <dictionary>) proc seed

dictの各要素に対してprocを呼びシード値を次に渡します。 procは引数を3つとります。エントリーのキー、エントリーの値、それ にシード値です。最初のシード値はseedです。procからの返り値 は次のprocの呼び出しでシード値として使われます。最後のproc の呼び出しの結果がdict-foldの返り値として返されます。

dictが<ordered-dictionary>であれば、procは以下のよ うな結合で呼ばれます。ここで、キーはK0(最小)からKn(最大)ま でで、それに対応する値がV0からVnまでであるとします。

(proc Kn Vn (proc Kn-1 Vn-1 ... (proc K0 V0 seed)))

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

dict-foldと同じですが、procを適用する結合の順が以下のよう に逆になります。

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

このジェネリック関数は<ordered-dictionary>上にのみ定義されてい ます。

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

ディクショナリdictの各エントリーのキーと値に対してprocを呼 びます。順序付きディクショナリに対してはprocがキーの昇順に呼ばれ ることが保証されています。

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

ディクショナリdictの各エントリーのキーと値に対してprocを呼 び、結果をリストにまとめて返します。順序付きディクショナリに対しては結 果が最初のキーの順にならびます(が、procがキーの昇順に呼ばれるこ とを保証するものではありません)。

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

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

それぞれdict内にあるすべてのキーのリスト、すべての値のリストを返 します。順序付きディクショナリについてはリストの要素はキーの昇順になら んでいます。

9.5.2 汎用ディクショナリ

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

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

Function: bimap-left bimap

Function: bimap-right bimap

Returns the left or right map of bimap, respectively.

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 :supersede)

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 there's already a relation (x, _) and/or (_, y), the behavior depends on the value of the keyword argument on-conflit.

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

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.

This document was generated by Shiro Kawai on November, 22 2009 using texi2html 1.78.