For Gauche 0.9.5


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

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

Module: data.imap

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

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

Class: <imap-meta>

<imap>のメタクラスです。

Class: <imap>

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

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

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

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

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

Creates a new empty immutable map, populates it with key-value association list alist, and returns it. This may be a bit more efficient than creating an empty map with make-imap and populates it with imap-put one by one.

The comparator argument specifies how to compare the keys. It must have comparison procedure. If omitted, default-comparator is used. See 基本的な比較器, for the details.

The third form creates a key comparator from a equality predicate key=? and less-than predicate key<=?, both must accept two keys.

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

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

Returns a new immutable map with the same content (and the same comparator) as tree-map.

Function: imap? obj

Returns #t if obj is an immutable map, #f otherwise.

Function: imap-empty? immap

Returns #t if an immutable map immap is empty, #f otherwise.

Function: imap-exists? immap key

Returns #t if key exists in an immutable map immap.

Function: imap-get immap key :optional default

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

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

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

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]