For Gauche 0.9.5


Next: , Previous: , Up: ライブラリモジュール - Gauche拡張モジュール   [Contents][Index]

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

Module: gauche.dictionary

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


Next: , Previous: , Up: ディクショナリフレームワーク   [Contents][Index]

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

これらのジェネリック関数は、ディクショナリ(離散的で有限なキーの集合から値の集合への 写像を表現するデータ構造)に対して共通するアルゴリズムを書くのに便利です。 (理論的には連続した、また無限なキーの集合を考えることもできますが、 実装上は有限集合に限る方がずっと簡潔になります。)

組み込みクラスでは、<hash-table><tree-map>が ディクショナリのインタフェースを実装しています。dbmモジュール群の 提供する<dbm>クラスもそうです。

自分の定義したクラスにディクショナリのインタフェースを実装するには、 最低限、dict-getdict-put!dict-delete!dict-folddict-comparatorの メソッドを実装してください (データ型がエントリの削除を許さない場合は、dict-delete!の実装を 省略することができます。) 他のジェネリック関数には、これらの基本的なメソッドを使ったデフォルト実装が 提供されます。ただ、他のジェネリック関数についても 自分のクラスに最適化した実装を書くと性能上有利になるでしょう。

註:ディクショナリはコレクションを継承しているので、コレクションを 扱うジェネリック関数はディクショナリに対しても使えます。 例えばエントリの数を得るにはsize-ofジェネリック関数が使えます。

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

keyに関連付けられた値を返します。もしkeyを持つエントリが ディクショナリに無い場合、defaultが与えられていればそれを返し、 そうでなければエラーが通知されます。

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

keyからvalueへの関連づけをディクショナリに追加します。

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

dict-put!と同じ動作です。

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

ディクショナリがkeyをキーに持つエントリを保持していれば#tを、 そうでなければ#fを返します。

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

ディクショナリからkeyをキーに持つエントリを除去します。 keyを持つエントリが無ければ何もしません。

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

ディクショナリを空にします。通常、全キーをループしてひとつづつ消していくよりも ずっと高速です。

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

キーを比較するのに使われるcomparatorを返します。

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内にあるすべてのキーのリスト、すべての値のリストを返 します。順序付きディクショナリについてはリストの要素はキーの昇順になら んでいます。

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

ディクショナリ中の各キーと値の対のリストを返します。対の順番は未定義です。

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

(dict-put! dict key (cons value (dict-get dict key '()))) と同じ動作をするメソッドです。具体的な実装によってはもっと効率が良いかもしれません (keyを2度検索しなくても良い、など)。

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

(dict-get dict key)がペアpであれば、 そのエントリの値が(cdr p)で置き換えられ、(car p)の値が 戻り値となります。keyに該当するエントリが無かったり、ペアで無かった場合は ディクショナリは変更されず、fallbackがあればそれが戻り値となり、 無ければエラーが報告されます。

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

次のコードのような動作をしますが、具体的な実装はkeyを一度しかルックアップ しないなどより効率良くなっている場合があります。

(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: ディクショナリフレームワーク   [Contents][Index]

9.8.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 :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: ディクショナリフレームワーク   [Contents][Index]