For Gauche 0.9.14Search (procedure/syntax/module):

Next: , Previous: , Up: ライブラリモジュール - ユーティリティ   [Contents][Index]

12.17 data.imap - 変更不可なマップ

Module: data.imap

このモジュールは、O(log n)でアクセスと更新が可能な、変更不可のデータ構造を 提供します(ここでの「更新」とは、要求された変更を取り込んだ新たな構造を 作って返すことです)。 現在の実装は関数的な赤黒木に基づいています。

リストや連想リストは、スタック風の変更不可なデータ構造として使えます。 つまり既存のデータ構造自体に変更を加えることなく、その先頭に要素を追加したり、 先頭から要素を取り除いたりできるということです。一方で、リストや連想リストは 任意の要素にアクセスするにはO(n)の時間を必要としますが、もっと速いアクセスが必要な 場合もあります。<imap>オブジェクトはO(log n)のアクセスを可能にします。 そのかわり、要素の追加や削除にもO(log n)を必要とします。

Class: <imap-meta>

{data.imap} <imap>のメタクラスです。

Class: <imap>

{data.imap} 変更不可なマップのクラスです。<imap-meta>をメタクラスとします。

<ordered-dictionary>を継承し、変更操作を除くディクショナリプロトコル を実装します(gauche.dictionary - ディクショナリフレームワーク参照)。 シーケンスとしてアクセスした場合は、キーと値のペアをキーの昇順に取り出すことができます。

Function: make-imap
Function: make-imap comparator
Function: make-imap key=? key<?

{data.imap} 空の変更不可なマップを新たに作って返します。 引数無しの場合は、キーの比較にはdefault-comparatorが使われます。 キーの比較方法を指定したい場合は、比較手続きを持つ比較器comparatorを 引数に渡してください。比較器については基本的な比較器を参照。 3番目の呼び出し形式は、キーの等価性を調べる述語key=?と 大小比較の述語key<?から比較器を作ります。どちらの述語も ふたつの引数をとらなければなりません。このインタフェースは tree-mapとの一貫性のためにサポートされています (ツリーマップ参照)。

Function: alist->imap alist
Function: alist->imap alist comparator
Function: alist->imap alist key=? key<?

{data.imap} 連想リストalistで指定されるキーと値の組み合わせを持つ変更不可なマップを新たに作って返します。 これはmake-imapで空のimapを作ってからimap-putで一要素づつ値を追加するよりも効率的です。

comparator引数はキーの比較に使うので比較手続きを持っていなければなりません。 省略された場合はdefault-comparatorが使われます。 比較器について詳しくは基本的な比較器を参照してください。

三つ目の形式は、等価判定述語key=?と比較述語key<?の組み合わせで キーの比較方法を指定するものです。どちらの述語も二つのキーを取ります。

(define m (alist->imap '((a . 1) (b . 2))))

(imap-get m 'a) ⇒ 1
(imap-get m 'b) ⇒ 2
Function: tree-map->imap tree-map

{data.imap} tree-mapと同じ内容、同じ比較器を持つ変更不可なマップを返します。

Function: imap? obj

{data.imap} objが変更不可なマップなら#tを、そうでなければ#fを返します。

Function: imap-empty? immap

{data.imap} 変更不可なマップimmapが空なら#tを、そうでなければ#fを返します。

Function: imap-exists? immap key

{data.imap} 変更不可なマップimmapがキーkeyを持っていれば#tを、 そうでなければ#fを返します。

Function: imap-get immap key :optional default

{data.imap} Returns the value associated with key in an immutable map immap. If immap doesn’t have key, default is returned when provided, otherwise an error is signalled.

Function: imap-put immap key val

{data.imap} Returns a new immutable map where association of key to val is added to (or replaced in) an immutable map immap. This operation is O(log n).

(define m1 (alist->imap '((a . 1) (b . 2))))

(define m2 (imap-put m1 'a 3))

(imap-get m2 'a)  ⇒ 3
(imap-get m1 'a)  ⇒ 1  ; not affected
Function: imap-delete immap key

{data.imap} Returns a new immutable map where key is removed from immap. If immap doesn’t have key, returned map has the same content as immap.

(define m1 (alist->imap '((a . 1) (b . 2))))

(define m2 (imap-delete m1 'a))

(imap-get m2 'a #f)  ⇒ #f
(imap-get m1 'a)     ⇒ 1  ; not affected
Function: imap-min immap
Function: imap-max immap

{data.imap} Returns a pair of key and value with the minimum or maximum key in immap, respectively. If immap is empty, #f is returned.


Next: , Previous: , Up: ライブラリモジュール - ユーティリティ   [Contents][Index]


For Gauche 0.9.14Search (procedure/syntax/module):