For Gauche 0.9.5


Next: , Previous: , Up: 組み込みライブラリ   [Contents][Index]

6.16 ツリーマップ

Builtin Class: <tree-map>

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

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

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

Function: make-tree-map :optional comparator
Function: make-tree-map key=? key<?

<tree-map>オブジェクトを作成して返します。 キーは比較器comparatorを使って比較されます。comparatorの デフォルト値はdefault-comparatorです。キーには全順序関係が必要なので、 比較器は比較手続きを持っていなければなりません。 詳しくは基本的な比較器を参照してください。

互換性のため、make-tree-mapcomparator引数に 単なる手続きを取ることもできます。渡される手続きは2引数を取り、 最初の引数が2番目の引数より小さいか、等しいか、大きいかに応じて -101をそれぞれ返します。つまり この手続きは比較器の比較手続きそのものです。

make-tree-mapの2番目の呼び出し形式も互換性のためのものです。 それぞれ2引数の2つの手続きを取り、 最初の手続きkey=?は、2つのキーが等しい場合にのみ真を返し、 2番目の手続きkey<?は、最初のキーが2番目のキーより前にある(小さい)場合にのみ 真を返すようにします。

Function: tree-map-comparator tree-map

tree-mapで使われている比較器を返します。

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

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

Function: tree-map-put! tree-map key value

キーkeyと対応する値valuetree-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-foldtree-map-fold-rightの違いは foldfold-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-map tree-map proc

2引数を取る手続きprocを、tree-mapの各キーおよび値のペアに 対して呼び出し、結果をリストにして返します。 結果のリストは、キーの昇順に並んでいます。つまり、最小のキーとその値で呼び出した procの結果が最初の要素に、最大のキーとその値で呼び出したprocの 結果が最後の要素になります。 (mapと同様、実際にprocが呼ばれる順序は保証されていません。 したがってprocは副作用の無いものにすべきです)。

Function: tree-map-for-each tree-map proc

2引数を取る手続きprocを、tree-mapの各キーおよび値のペアに対して、 キーの昇順に呼び出します。procは副作用のためだけに呼ばれ、結果は捨てられます。

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

これらの手続きは、probeに最も近いキーを持つエントリをtree-mapから 探します。そのようなエントリが見つかれば、該当するキーと値が2つの戻り値となります。 見つからない場合は、fallback-keyfallback-valueが 2つの戻り値として返されます。それぞれの省略時の値は#fです。

それぞれの手続きは異なった「最も近い」の基準を持っています。 tree-map-floorprobe以下で最大のキーを、 tree-map-ceilingprobe以上で最小のキーを、 tree-map-precedessorprobe未満で最大のキーを、 tree-map-successorprobeを越える最小のキーを探します。

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

tree-map-floor等と同様ですが、見つかったエントリのキーのみを返します。 該当エントリが見つからない場合はfallback-keyの値(デフォルトは#f)が 返されます。

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

tree-map-floor等と同様ですが、見つかったエントリの値のみを返します。 該当エントリが見つからない場合はfallback-valueの値(デフォルトは#f)が 返されます。

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 :optional comparator
Function: alist->tree-map alist key=? key<?

comparatorまたはkey=?, key<? によって新たなtreemapを作成し、 連想リストalistに含まれる要素を追加した上で返します。 alistの各ペアのcarがキーに、cdrが値に使われます。 comparator, key=?, key<?引数の意味は make-tree-mapと同じです。


Next: , Previous: , Up: 組み込みライブラリ   [Contents][Index]