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} 変更不可なマップimmap中のキーkeyに対応する値を返します。 immapがkeyを持っていない場合、default引数が与えられていれば その値を返し、なければエラーが投げられます。

Function: imap-put immap key val ¶

{data.imap} 変更不可なマップimmapに、キーkeyと値valの対応を付け加えた (あるいは、既に対応があった場合は置き換えた)新たな変更不可なマップを作って返します。 この操作は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} 変更不可なマップimmapから、キーkeyに対応するエントリを 取り除いた新たな変更不可なマップを作って返します。 immapにkeyが含まれていなかった場合、返されるマップは 元のマップと同じ内容を持ちます。

(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} 変更不可なマップimmap中で、最小または最大のキーと、それに対応する値を ペアにして返します。immapが空の場合は#fを返します。