Next: gauche.fcntl
- 低レベルファイル操作, Previous: gauche.connection
- コネクションフレームワーク, Up: ライブラリモジュール - Gauche拡張モジュール [Contents][Index]
gauche.dictionary
- ディクショナリフレームワークディクショナリはキーから値への写像ができるオブジェクトを表わす抽象クラ スです。このモジュールではディクショナリに対してよく使うジェネリック関数、 および他のディクショナリクラスの上に構築される汎用的なディクショナリクラスを 提供します。
• ディクショナリのためのジェネリック関数: | ||
• 汎用ディクショナリ: |
Next: 汎用ディクショナリ, Previous: gauche.dictionary
- ディクショナリフレームワーク, Up: gauche.dictionary
- ディクショナリフレームワーク [Contents][Index]
これらのジェネリック関数は、ディクショナリ(離散的で有限なキーの集合から値の集合への 写像を表現するデータ構造)に対して共通するアルゴリズムを書くのに便利です。 (理論的には連続した、また無限なキーの集合を考えることもできますが、 実装上は有限集合に限る方がずっと簡潔になります。)
組み込みクラスでは、<hash-table>
と<tree-map>
が
ディクショナリのインタフェースを実装しています。dbm
モジュール群の
提供する<dbm>
クラスもそうです。
自分の定義したクラスにディクショナリのインタフェースを実装するには、
最低限、dict-get
、dict-put!
、
dict-delete!
、dict-fold
、dict-comparator
の
メソッドを実装してください
(データ型がエントリの削除を許さない場合は、dict-delete!
の実装を
省略することができます。)
他のジェネリック関数には、これらの基本的なメソッドを使ったデフォルト実装が
提供されます。ただ、他のジェネリック関数についても
自分のクラスに最適化した実装を書くと性能上有利になるでしょう。
註:ディクショナリはコレクションを継承しているので、コレクションを
扱うジェネリック関数はディクショナリに対しても使えます。
例えばエントリの数を得るにはsize-of
ジェネリック関数が使えます。
<dictionary>
) key :optional default ¶{gauche.dictionary} keyに関連付けられた値を返します。もしkeyを持つエントリが ディクショナリに無い場合、defaultが与えられていればそれを返し、 そうでなければエラーが通知されます。
<dictionary>
) key value ¶{gauche.dictionary} keyからvalueへの関連づけをディクショナリに追加します。
<dictionary>
) key value ¶{gauche.dictionary}
dict-put!
と同じ動作です。
<dictionary>
) key ¶{gauche.dictionary}
ディクショナリがkeyをキーに持つエントリを保持していれば#t
を、
そうでなければ#f
を返します。
<dictionary>
) key ¶{gauche.dictionary} ディクショナリからkeyをキーに持つエントリを除去します。 keyを持つエントリが無ければ何もしません。
<dictionary>
) ¶{gauche.dictionary} ディクショナリを空にします。通常、全キーをループしてひとつづつ消していくよりも ずっと高速です。
<dictionary>
) ¶{gauche.dictionary} キーを比較するのに使われるcomparatorを返します。
<dictionary>
) proc seed ¶{gauche.dictionary} 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)))
<ordered-dictionary>
) proc seed ¶{gauche.dictionary}
dict-fold
と同じですが、procを適用する結合の順が以下のよう
に逆になります。
(proc K0 V0 (proc K1 V1 ... (proc Kn Vn seed)))
このジェネリック関数は<ordered-dictionary>
上にのみ定義されてい
ます。
<dictionary>
) proc ¶{gauche.dictionary} ディクショナリdictの各エントリーのキーと値に対してprocを呼 びます。順序付きディクショナリに対してはprocがキーの昇順に呼ばれ ることが保証されています。
<dictionary>
) proc ¶{gauche.dictionary} ディクショナリdictの各エントリーのキーと値に対してprocを呼 び、結果をリストにまとめて返します。順序付きディクショナリに対しては結 果が最初のキーの順にならびます(が、procがキーの昇順に呼ばれるこ とを保証するものではありません)。
<dictionary>
) ¶<dictionary>
) ¶{gauche.dictionary} それぞれdict内にあるすべてのキーのリスト、すべての値のリストを返 します。順序付きディクショナリについてはリストの要素はキーの昇順になら んでいます。
<dictionary>
) ¶{gauche.dictionary} ディクショナリ中の各キーと値の対のリストを返します。対の順番は未定義です。
<dictionary>
) key value ¶{gauche.dictionary}
(dict-put! dict key (cons value (dict-get dict key '())))
と同じ動作をするメソッドです。具体的な実装によってはもっと効率が良いかもしれません
(keyを2度検索しなくても良い、など)。
<dictionary>
) key :optional fallback ¶{gauche.dictionary}
(dict-get dict key)
がペアpであれば、
そのエントリの値が(cdr p)
で置き換えられ、(car p)
の値が
戻り値となります。keyに該当するエントリが無かったり、ペアで無かった場合は
ディクショナリは変更されず、fallbackがあればそれが戻り値となり、
無ければエラーが報告されます。
<dictionary>
) key proc :optional fallback ¶{gauche.dictionary} 次のコードのような動作をしますが、具体的な実装はkeyを一度しかルックアップ しないなどより効率良くなっている場合があります。
(rlet1 x (proc (dict-get dict key fallback)) (dict-put! dict key x))
{gauche.dictionary}
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-method
s, 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: gauche.dictionary
- ディクショナリフレームワーク [Contents][Index]
{gauche.dictionary} 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.
{gauche.dictionary} 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 regarded as a conflict. This limitation may be lifted in future.
{gauche.dictionary} Returns the left or right map of bimap, respectively. Do not mutate the returned map, or you’ll break the consistency of the bimap.
{gauche.dictionary} 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.
{gauche.dictionary}
Returns #f
if the left or right map of bimap has an entry of
the key, #t
otherwise.
{gauche.dictionary}
Put a relation (x, y) into the bimap.
After this, (bimap-left-get x)
will return y,
and (bimap-right-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.
{gauche.dictionary} 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.
{gauche.dictionary} Stacked map allows you to stack (layer) multiple maps (dictionaries) and treat as if they are a single map. The upper map "shadows" the lower maps. Think of nested scopes, for example.
As a dictionary, it behaves as follows:
dict-get
operation searches the given key from the top
dictionary to the bottom dictionary, returns the first found entry.
dict-put!
operation always put the entry to the topmost
dictionary. If there’s an entry with the same key exists in a
lower dictionary, it will be shadowed.
If you want to alter the existing entry of non-top dictionary,
use stacked-map-entry-update!
.
dict-delete!
operations deletes all the entries with the
given key from all the dictionaries. This is for consistency as
a dictionary—you don’t want an entry pop up after deleting it.
If you want to delete only from the first entry in the stack,
use stacked-map-entry-delete!
.
dict-fold
operation traverse all the dictionaries
from top to bottom. When there are duplicate keys, the second and after
will be skipped.
Creates a new stacked map with the given dictionaries
dic dic2 …, where dic is the topmost dictionary.
You can give a comparator
key-comparator to be used to compare keys during
traversal with dict-fold
. If key-comparator is
omitted, the comparator from dic is used.
The key comparator is returned from dict-comparator
on the stacked map.
Creates a new stacked map, adding dic on top of the existing stacked map smap. The key comparator is inherited from smap.
Adds dic on top of the dictionaries smap holds.
Remove the topmost dictionary smap holds. An error is signaled if you attempt to pop from an smap that has no dictionaries.
Returns a number of dictionaries smap has.
Run (dict-update! d key proc fallback)
on the
first dictionary d
that has the given key.
This differs from running dict-update!
on smap; if the topmost
dictionary doesn’t have an entry with key but some lower dictionary has,
dict-update!
takes the existing value and applies proc to it,
then insert the result to the topmost dictionary, while the original entry
remains intact.
Deletes the first entry with key. If there’s another entry with key in a lower dictionary, it will become visible.
This differs from running dict-delete!
on smap; it
deletes all entries with key, so that dict-exists?
after dict-delete!
is guaranteed to return #f
.
Next: gauche.fcntl
- 低レベルファイル操作, Previous: gauche.connection
- コネクションフレームワーク, Up: ライブラリモジュール - Gauche拡張モジュール [Contents][Index]