Gauche ユーザリファレンス: 6.14 ツリーマップ

6.14 ツリーマップ

Builtin Class: <tree-map>

ツリーマップクラス。ツリーマップはキーオブジェクトから値オブジェクトへの写像をあらわすデータ構造です。ツリーマップでは平衡木を使うということ以外はハッシュテーブルと同じです。ツリーマップでは挿入と検索の手間は O(log n)です。

ハッシュテーブルとはちがい、キーの順序は保存されます。したがってキーの順序どおりにトラバースするのは簡単で、キーの最小値/最大値を見つけたり、指定したキーにもっとも近いキーを探すのも簡単です。

<tree-map>クラスは<sequence>および <ordered-dictionary>を継承しています。

Function: make-tree-map key=? key<?: <tree-map>オブジェクトを作成して返します。 key=?、key<?はそれぞれ引数を2つ受け取り真偽値を返す手続きであり、要素のキーが渡されます。 key=?は、2つの引数a, b が同値の場合に真を、それ以外の場合に#fを返す手続きです。key<?は、a < bが成り立つ場合に真を、それ以外の場合に#fを返す手続きです。

Function: tree-map-copy tree-map: tree-mapのコピーを作り、それを返します。返された木に対する破壊的操作は、元の木に影響を与えません。

Function: tree-map-empty? tree-map: tree-mapが要素を持たないなら#tを、そうでなければ#fを返します。

Function: tree-map-num-entries tree-map: tree-map内の要素の個数を返します。

Function: tree-map-exists? tree-map key: tree-mapにキーkeyを持つエントリがあれば#tを、そうでなければ#fを返します。

Function: tree-map-get tree-map key &optional fallback: キーkeyをtree-mapから探します。見つかればkeyに対応する値を返します。キーが見つからなかった場合、fallbackが与えられていればそれを返し、そうでなければエラーを報告します。

Function: tree-map-put! tree-map key value: キーkeyと対応する値valueをtree-mapに挿入します。もし、keyと、 key=?における意味で同じキーがすでに存在する場合、キーに対応する値は新たな値に置き換えられます。

Function: tree-map-delete! tree-map key: tree-mapからキーkeyを持つエントリを削除します。keyを持つエントリが実際に存在して削除された場合は#tを、エントリが存在しなかった場合は#fを返します。

Function: tree-map-clear! tree-map: tree-map内の全てのエントリを削除します。

Function: tree-map-update! tree-map key proc &optional fallback

tree-map-push!等のより一般的なバージョンです。木の探索が一度しか行われないことを除いては、基本的に次のように動作します。

(let ((tmp (proc (tree-map-get tree-map key fallback))))
  (tree-map-put! tree-map key tmp)
  tmp)

Function: tree-map-push! tree-map key value: tree-map中の、キーkeyに対応する値にvalueをコンスし、それをkey に対する新たな値とします。もしkeyに対応する値がまだ無ければ、新たなエントリが作成され、(list value)がその値となります。

Function: tree-map-pop! tree-map key &optional fallback: tree-map中のキーkeyに対応する値が存在し、かつペアであった場合に、そのエントリの値を元の値のcdrで置き換え、元の値のcarを返します。 keyに対応する値が存在しないかペアではなかった場合、tree-mapは変更されず、fallbackが与えられていればそれが返され、与えられていなければエラーが報告されます。

Function: tree-map-min tree-map
Function: tree-map-max tree-map: それぞれ、tree-mapに含まれる最小および最大のキーを探索し、そのキーと値のペアを返します。tree-mapが空だった場合は#fが返されます。

Function: tree-map-pop-min! tree-map
Function: tree-map-pop-max! tree-map: それぞれ、tree-mapに含まれる最小および最大のキーを探索し、そのエントリをtree-mapから削除したうえで、そのキーと値のペアを返します。tree-mapが空だった場合は#fが返されます。

Function: tree-map-fold tree-map proc seed

Function: tree-map-fold-right tree-map proc seed

tree-mapの各要素に対し、(key, value, seed) -> seed の型を持つ procを適用してゆきます。 tree-map-foldとtree-map-fold-rightの違いは foldのfold-right違いと同じ、すなわち結合の方向にあります。

tree-map-fold:
  (proc Kn Vn (proc Kn-1 Vn-1 ... (proc K0 V0 seed)))

tree-map-fold-right
  (proc K0 V0 (proc K1 V1 ... (proc Kn Vn seed)))

例:

(define tree (alist->tree-map '((3 . a) (7 . b) (5 . c)) = <))

(tree-map-fold tree list* '()) 
   ⇒ (7 b 5 c 3 a)
(tree-map-fold-right tree list* '()) 
   ⇒ (3 a 5 c 7 b)

Function: tree-map-floor tree-map probe &optional fallback-key fallback-value

Function: tree-map-ceiling tree-map probe &optional fallback-key fallback-value

Function: tree-map-predecessor tree-map probe &optional fallback-key fallback-value

Function: tree-map-successor tree-map probe &optional fallback-key fallback-value

These procedures search the entry which has the closest key to the given probe. If such an entry is found, returns two values, its key and its value. Otherwise, returns two values, fallback-key and fallback-value, both defaulted to #f.

The criteria of “closest” differ slightly among these procedures; tree-map-floor finds the maximum key which is no greater than probe; tree-map-ceiling finds the minimum key which is no less than probe; tree-map-predecessor finds the maximum key which is strictly less than probe; and tree-map-successor finds the minimum key which is strictly greater than probe.

Function: tree-map-floor-key tree-map probe optional fallback-key
Function: tree-map-ceiling-key tree-map probe optional fallback-key
Function: tree-map-predecessor-key tree-map probe optional fallback-key
Function: tree-map-successor-key tree-map probe optional fallback-key: Like tree-map-floor etc., but only returns the key of the found entry (or fallback-key if there's no entry which satisfies the criteria).

Function: tree-map-floor-value tree-map probe optional fallback-value
Function: tree-map-ceiling-value tree-map probe optional fallback-value
Function: tree-map-predecessor-value tree-map probe optional fallback-value
Function: tree-map-successor-value tree-map probe optional fallback-value: Like tree-map-floor etc., but only returns the value of the found entry (or fallback-value if there's no entry which satisfies the criteria).

Function: tree-map-keys tree-map
Function: tree-map-values tree-map: それぞれ、tree-map内の全てのキーまたは値をリストにして返します。返されるリストの要素はキーの昇順に並んでいます。

Function: tree-map->alist tree-map: tree-map含まれる要素を連想リストにして返します。返される連想リストのキーは昇順に並んでいます。

Function: alist->tree-map alist key=? key<?: key=?, key<? によって新たなtreemapを作成し、連想リストalistに含まれる要素を追加した上で返します。

[ < ]

[ > ]

[ << ]

[ Up ]

[ >> ]

This document was generated by Shiro Kawai on November, 22 2009 using texi2html 1.78.