6.14.1 ハッシュテーブル ¶

R7RS-largeにはハッシュテーブルが定義されています (scheme.hash-tableモジュール、scheme.hash-table - R7RSハッシュテーブル参照)。 しかし、そのAPIはGaucheにもともとあったハッシュテーブルや他のネイティブAPIと一貫性を 欠いている部分があります。

APIをごちゃまぜにするよりは、GaucheのネイティブなAPIの一貫性を保つことを重視し、 R7RSの手続きのうちGaucheにそぐわないものは、組み込み関数では別名 (サフィックス-r7がついたもの)をつけて提供しています。 ポータブルなコードを書く場合は、scheme.hash-tableをインポートすれば R7RSの名前が使えます。

Builtin Class: <hash-table> ¶

ハッシュテーブルのクラスです。<collection>と<dictionary>を 継承します。

Gaucheは今のところ、変更不可なハッシュテーブルは提供しません。 (変更不可なマップが必要な場合は、data.imap - 変更不可なマップを参照してください。)

ハッシュテーブルのプロパティ ¶

Function: hash-table? obj ¶

[R7RS hash-table] objがハッシュテーブルであれば#tを返します。

Function: hash-table-mutable? ht ¶

[R7RS hash-table] ハッシュテーブルhtが変更可能なら#tを返します。 Gaucheは変更不可なハッシュテーブルを持たないので、 どんなハッシュテーブルに関しても手続きは#tを返します。

Function: hash-table-comparator ht ¶

ハッシュテーブルhtで使われている比較器を返します。

Function: hash-table-num-entries ht ¶

Function: hash-table-size ht ¶

[R7RS hash-table] ハッシュテーブルht中の要素の個数を返します。 R7RSの名前はhash-table-size.

Function: hash-table-type ht ¶

Deprecated. これは古いAPIで、hash-table-comparatorによって置き換えられました。

ハッシュテーブルhtのタイプに応じて、シンボル eq?、eqv?、equal?、string=?、 generalのいずれかを返します。

ハッシュテーブルのコンストラクタとコンバータ ¶

Function: make-hash-table :optional comparator ¶

[R7RS+ hash-table] ハッシュテーブルを作成します。comparator引数には、 キーの等価判定とハッシュに使う比較器(基本的な比較器参照)を渡します。 省略された場合はeq-comparatorが使われます。 (R7RSではcomparatorは省略できません。)

Gauche独自拡張として、comparatorにシンボル eq?、eqv?、equal?、string=?のいずれかを 指定することもできます。 eq-comparator、 eqv-comparator、equal-comparator、 string-comparatorが使われます。

比較器はハッシュ関数を持っていなければなりません。組み込みのハッシュ関数については ハッシュを参照してください。比較器を組み合わせて作られた比較器については、 元の比較器がハッシュ関数を持っていれば、通常は適切なハッシュ関数が設定されます。

Function: hash-table-from-pairs comparator key&value … ¶

与えられたキーと値の列からハッシュテーブルを構築して 返します。comparator引数の意味はmake-hash-tableと同じです。 各key&valueはペアでなければならず、そのcarがキー、cdrが値として使われます。

註：これは0.9.5までhash-tableと呼ばれていた手続きです。 R7RSは同名で異なるインタフェースを持つインタフェースを定義しました。 そちらの方が使いやすいので、長期的にはR7RSインタフェースへとスイッチする予定ですが、 それはかなり将来のことになります。 R7RSインタフェースはhash-table-r7という名前で利用可能なので、 新たなコードはそちらを使うことを強くお勧めします。 また、既存のコードでhash-tableを使っていたら、 hash-table-from-pairsに直してください。

(hash-table-from-pairs 'eq? '(a . 1) '(b . 2))
  ≡
  (rlet1 h (make-hash-table 'eq?)
     (hash-table-put! h 'a 1)
     (hash-table-put! h 'b 2))

Function: hash-table comparator key&value … ¶

hash-table-from-pairsの別名です。 R7RSが同名で別インタフェースの手続き(下のhash-table-r7参照)を導入し、 将来的にはGaucheもそちらに移行する予定です。なので今のところ、 hash-table-from-pairsかhash-table-r7を使うか、 scheme.hash-tableをインポートしてR7RSとして書いてください。

Function: hash-table-r7 comparator args … ¶

comparatorを比較器に使うハッシュテーブルを作って返します。 args …はキーと値を交互に並べたもので、ハッシュテーブルの内容を指定します。

これはR7RS scheme.hash-tableでhash-tableと定義されている手続きです (scheme.hash-table - R7RSハッシュテーブル参照)。

(hash-table-r7 'eq? 'a 1 'b 2)
  ≡
  (rlet1 h (make-hash-table 'eq?)
     (hash-table-put! h 'a 1)
     (hash-table-put! h 'b 2))

註: R7RS準拠の実装には、hash-tableが変更不可なハッシュテーブルを 返すものがあります。Gaucheは変更不可なハッシュテールを持っていないので (変更不可なマップならあります: data.imap - 変更不可なマップ参照)、 変更可能なハッシュテーブルが返されます。 ただ、ポータブルなプログラムを書いている場合は、この手続きが返したハッシュテーブルを 変更しないように注意してください。

Function: hash-table-unfold p f g seed comparator :rest args ¶

[R7RS hash-table] 次の手順で新たなハッシュテーブルを作り返します。 各繰り返しは「現在のシード値」を参照しますが、その初期値はseedです。

1. 停止述語pを現在のシード値に適用します。それが真の値を返したら、そこで終了です。
2. 生産手続きfを現在のシード値に適用します。fは二つの値を返さねばなりません。 最初の値がキー、二番目がキーに対応する値として、作られているハッシュテーブルに挿入されます。
3. 手続きgが現在のシード値に適用され、その戻り値が次の繰り返しでのシード値となります。

Function: hash-table-copy ht :optional mutable? ¶

[R7RS hash-table] ハッシュテーブルhtのコピーを作って返します。

R7RSは、実装が変更不可なハッシュテーブルをサポートする場合、 mutable?引数に真の値が与えられない限りは、 この手続きは変更不可なハッシュテーブルを返すと規定しています。 Gaucheは変更不可なハッシュテーブルを持たないので、mutable?引数は無視され、 常に変更可能なハッシュテーブルが返されますが、 ポータブルなコードを書いている場合は気をつけてください。

Function: hash-table-empty-copy ht ¶

[R7RS hash-table] ハッシュテーブルhtと同じ性質を持つ空の変更可能なハッシュテーブルを作成して 返します。

Function: alist->hash-table alist :optional comparator ¶

[R7RS+ hash-table] alistに含まれるそれぞれの要素をエントリとして持つハッシュテーブルを 作成して返します。その時、要素のcarがキーとして、要素のcdrが値として 使われます。comparator引数の意味はmake-hash-tableと同じです。 comparatorのデフォルト値はeq-comparatorです。

R7RSではcomparatorは省略不可です。

Function: hash-table->alist hash-table ¶

[R7RS hash-table]

  (hash-table-map h cons)

ハッシュテーブルのルックアップと変更 ¶

Function: hash-table-get ht key :optional default ¶

キーkeyをハッシュテーブルhtから探します。見つかればキーに対応する 値を返します。キーが見つからなかった場合、defaultが与えられていればそれを 返し、そうでなければエラーを報告します。

Function: hash-table-put! ht key value ¶

キーkeyと対応する値valueをハッシュテーブルhtに挿入します。

Method: ref (ht <hash-table>) key :optional default ¶

Method: (setter ref) (ht <hash-table>) key value ¶

hash-table-getとhash-table-put!のメソッド版です。

Function: hash-table-ref ht key :optional failure success ¶

[R7RS hash-table] これがR7RS方式のハッシュテーブルルックアップです。

ハッシュテーブルht中の、keyに結びつけられた値を探し、 それを手続きsuccessに渡して、その結果を返します。 successが省略された場合は単に値そのものが返されます。

keyに対応する値がhtに無い場合は、引数を取らない手続きfailureが 呼ばれ、その結果が返されます。failureが省略されていた場合はエラーが報告されます。

これはGaucheのhash-table-getよりも汎用的ですが、 キーが見つからなかった場合に単純に既定値を返したいといった場合に、 それをいちいちクロージャで包むのは面倒です。R7RSではそのために 下に説明するhash-table-ref/defaultがあります。

Function: hash-table-ref/default ht key default ¶

[R7RS hash-table] ハッシュテーブルhtからkeyを探し、対応する値を返します。 keyが見つからない場合はdefaultを返します。

これは、defaultが省略できないことを除いては、Gaucheの hash-table-getと同じです。hash-table-getの方が短くて便利なので 両方提供しています。

Function: hash-table-set! ht args … ¶

[R7RS hash-table] これが、ハッシュテーブルに新たなエントリを追加するR7RS式のインタフェースです。 args …にはキーと値を交互に並べたリストを指定します。 Gaucheのhash-table-put!と違い、いくつものエントリを一度に追加することができます。 args …が偶数要素でなければエラーです。

(hash-table-set! ht 'a 1 'b 2)
  ≡
  (begin (hash-table-put! ht 'a 1)
         (hash-table-put! ht 'b 2))

Function: hash-table-intern!-r7 ht key failure ¶

これはR7RSでhash-table-intern!として定義されています。 Gaucheの慣習と異なり、R7RSの方式でfailureにサンクを取ることを強調するために -r7サフィックスをつけました。

htからkeyを探します。もし既にエントリがあれば、その値を返します。 エントリが無ければ、サンクfailureを呼び、その戻り値をkeyに対応する 値としてhtに挿入して、failureの戻り値を返します。

Function: hash-table-exists? ht key ¶

Function: hash-table-contains? ht key ¶

[R7RS hash-table] ハッシュテーブルhtにキーkeyを持つエントリがあれば#tを返します。

R7RSでの名前はhash-table-contains?です。

Function: hash-table-delete! ht key ¶

ハッシュテーブルhtからキーkeyを持つエントリを削除します。 keyを持つエントリが実際に存在して削除された場合は#tを、 エントリが存在しなかった場合は#fを返します。 この手続きはSTkでhash-table-remove!と呼ばれているものです (STkのは戻り値が定義されていませんが)。GaucheではSRFI-1, SRFI-13やその他の ライブラリとの一貫性のために ‘delete’ を採用しました。

註: これはR7RSのhash-table-delete!と異なります。 R7RSインタフェースはhash-table-delete!-r7という別名で提供されます。

Function: hash-table-delete!-r7 ht key … ¶

key …を持つエントリをハッシュテーブルhtから削除します。 htに含まれなかったキーは単に無視されます。実際に削除されたエントリの数が返されます。

これはR7RSでhash-table-delete!と呼ばれており、 scheme.hash-tableでもその名前で提供されます。 Gaucheのhash-table-delete!は真偽値を返すので、 組み込みとしては別名で提供することにしました。

Function: hash-table-clear! ht ¶

[R7RS hash-table] ハッシュテーブルhtの全てのエントリを削除します。

Function: hash-table-push! ht key value ¶

ハッシュテーブルht中の、キーkeyに対応する値にvalueをコンスし、 それをkeyに対する新たな値とします。もしkeyに対応する値がまだ無ければ、 新たなエントリが作成され、(list value)がその値となります。

この手続きは次のコードと同じ動作をしますが、キーの探索が一度しか行われないためより高速です。

(hash-table-put! ht key
    (cons value (hash-table-get ht key '())))

Function: hash-table-pop! ht key :optional default ¶

ハッシュテーブルht中のキーkeyに対応する値が存在し、かつペアで あった場合に、そのエントリーを元の値のcdrで置き換え、元の値のcarを返します。 keyに対応する値が存在しないかペアではなかった場合、テーブルは変更されず、 defaultが与えられていればそれが返され、与えられていなければエラーが報告されます。

値が置き換えられる場合でもキーの探索は一度しか行われないため効率が良いです。

註：R7RSもhash-table-pop!を定義していますが、全く違う操作です。 そこで、R7RSバージョンはhash-table-pop!-r7として提供しています。

Function: hash-table-pop!-r7 ht ¶

ハッシュテーブルht中の任意のエントリをひとつ削除し、 そのエントリのキーと値を二つの戻り値として返します。 htが空ならエラーが報告されます。

R7RSではこれがhash-table-pop!と呼ばれていて、 scheme.hash-tableでもその名前で提供されます。

Function: hash-table-update! ht key proc :optional default ¶

hash-table-push!等のより一般的なバージョンです。 ハッシュテーブルの探索が一度しか行われないことを除いては、 基本的に次のように動作します。

(let ((tmp (proc (hash-table-get ht key default))))
  (hash-table-put! ht key tmp)
  tmp)

例えば、ハッシュテーブルを使ってオブジェクトの個数を数えているとしましょう。 次の1行で、オブジェクトitemが既に出現したかどうかを気にせずに その個数をインクリメントできます。

(hash-table-update! ht item (cut + 1 <>) 0))

R7RSもhash-table-update!を定義していますが、インタフェースが異なるので、 GaucheではR7RS版を別名hash-table-update!-r7として提供します。

Function: hash-table-update!-r7 ht key updater :optional failure success ¶

これがR7RS版のhash-table-update!です。 省略可能引数を全て省略した場合はGaucheのhash-table-update!と同じになりますが、 実際にはkeyがhtに無かった場合の振る舞いを指定する必要があることが多く、 その場合R7RSのインタフェースはGaucheと異なってきます。

R7RS版は、効率を除けば次のとおり動作します。

(hash-table-put! ht key (updater (hash-table-ref ht key failure success)))

Function: hash-table-update!/default ht key updater default ¶

[R7RS hash-table] これはdefaultが省略できないことを除けば、 Gaucheのhash-table-update!と同じです。

ハッシュテーブルの走査 ¶

Function: hash-table-for-each ht proc ¶

Function: hash-table-map ht proc ¶

ハッシュテーブルht内の全てのエントリについて、各エントリのキーと値を 2つの引数として手続きprocを呼びます。

Function: hash-table-fold ht kons knil ¶

ハッシュテーブルht内の全てのエントリについてkonsを呼びます。 konsには3つの引数が渡されます。 各エントリのキーと値、および一つ前のkonsの返り値です。 最初のkonsの呼び出しの時には、第3引数にknilが渡されます。 最後のkonsの返り値がhash-table-foldの返り値となります。

Function: hash-table-find ht pred :optional failure ¶

predをハッシュテーブルhtの各エントリのキーと値を引数にして 呼び出し、それが真の値を返したら直ちにそれを戻り値とします。 predを満たすキーと値が無ければ、無引数の手続きfailureが呼び出され、 その値が戻り値となります。failureが省略された場合は (lambda () #f)が使われます。

註: SRFI-1から始まった慣習では、*-findというAPIは 述語を満たすようなコレクション内の要素を返し、*-anyというAPIが 述語が偽でない値を返した時にその値をそのまま返り値とします。 SRFI-125が慣習を破った理由は、 “any”のセマンティクスで従来の “find” の動作もエミュレートできるので “find”が “any” の動作も兼ねてしまえばよいというものです。 しかし、現在までのところ、この慣習を破っているのはSRFI-125のみです。

;; ハッシュテーブルhaとhbに共通のキーがあるかどうか調べる
(hash-table-find ha (^[k v] (hash-table-exists? hb k)))

Function: hash-table-keys ht ¶

Function: hash-table-values ht ¶

それぞれ、ハッシュテーブルht内の全てのキーまたは値をリストにして返します。

集合としてのハッシュテーブル ¶

Function: hash-table-compare-as-sets ht1 ht2 :optional value=? fallback ¶

ハッシュテーブルは、キーと値の組を要素とする集合とみなすことができます。 この手続きは二つのハッシュテーブルht1とht2を集合として比較します。

二つのハッシュテーブルのキー比較器は同じ (equal?の意味で) でなければなりません。そうでない場合はエラーが投げられます。

二つの要素は、キー同士がキー比較器によって等価と判断され、かつ 値同士がvalue=?手続きによって等価と判断された場合に等しいとみなされます。 value=?が省略された場合はequal?が使われます。

4通りの結果が有り得ます。

• ht1がht2の純粋部分集合である場合は-1が返されます (ht1 ＜ ht2)。
• ht2がht1の純粋部分集合である場合は1が返されます (ht1 ＞ ht2)。
• ht1とht2がまったく同じだけの要素を含んでいる場合は0が返されます (ht1 ＝ ht2)。
• ht1とht2がお互いに相手の部分集合でない場合は、 fallbackが与えられていればそれが返され、 省略された場合はエラーが投げられます。

Function: hash-table=? value-cmpr ht1 ht2 ¶

[R7RS hash-table] この手続きもht1とht2を集合として比較し、 二つのテーブルが等しい集合である場合、つまりht1の要素がすべてht2の要素でもあり、 またその逆も真である場合に#tを、そうでなければ#fを返します。

二つの要素は、キー同士がキー比較器によって等価と判定され、かつ また値同士が比較器value-cmprによって等価と判定された場合に 等しいとみなされます。

ht1とht2のキー比較器が異なっていた場合はエラーが投げられます。 上のhash-table-compare-as-setsも参照してください。

Function: hash-table-union! ht1 ht2 ¶

Function: hash-table-intersection! ht1 ht2 ¶

Function: hash-table-difference! ht1 ht2 ¶

Function: hash-table-xor! ht1 ht2 ¶

[R7RS hash-table] 二つのハッシュテーブル間で集合演算を行い、結果をht1に格納します。 これらの手続きでは、集合の要素としてキーだけを見ます。 もし同じキーを持つ要素の値がht1とht2で異なっていた場合、 ht1の値が優先されます。

• unionは、ht1かht2の少なくとも一方に入っている要素を集めます。
• intersectionは、ht1とht2の両方に含まれる要素のみを集めます。
• differenceは、ht1に含まれるがht2には含まれない要素のみを集めます。
• xorは、ht1かht2の一方のみに含まれる要素のみを集めます。

---

6.14.2 ツリーマップ ¶

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-mapはcomparator引数に 単なる手続きを取ることもできます。渡される手続きは2引数を取り、 最初の引数が2番目の引数より小さいか、等しいか、大きいかに応じて -1、0、1をそれぞれ返します。つまり この手続きは比較器の比較手続きそのものです。

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 ¶

キー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-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-keyとfallback-valueが 2つの戻り値として返されます。それぞれの省略時の値は#fです。

それぞれの手続きは異なった「最も近い」の基準を持っています。 tree-map-floorはprobe以下で最大のキーを、 tree-map-ceilingはprobe以上で最小のキーを、 tree-map-predecessorはprobe未満で最大のキーを、 tree-map-successorは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 ¶

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->generator/key-range tree-map :key > >= < <= descending ¶

キーが指定された範囲に入っているようなキーと値のペアを生成するジェネレータを作って 返します (gauche.generator - ジェネレータ参照)。 もしdescendingキーワード引数が#f(デフォルト値)なら、ペアは キーの昇順に生成されます。それが真の値なら、ペアはキーの降順に生成されます。

キーワード引数>と>=はキーの下限を指定します。前者は指定値を含み、 後者は含みません。両方指定された場合はどちらかひとつだけが有効です。

キーワード引数<と<=はキーの下限を指定します。前者は指定値を含み、 後者は含みません。両方指定された場合はどちらかひとつだけが有効です。

(define tm (alist->tree-map '((0 . a) (1 . b) (2 . c) (3 . d) (4 . e))
                            default-comparator))


(use gauche.generator)

(generator->list
  (tree-map->generator/key-range tm :>= 1 :< 4))
  ⇒ ((1 . b) (2 . c) (3 . d))

(generator->list
  (tree-map->generator/key-range tm :>= 1 :< 4 :descending #t))
  ⇒ ((3 . d) (2 . c) (1 . b))

(generator->list
  (tree-map->generator/key-range tm :<= 2))
  ⇒ ((0 . a) (1 . b) (2 . c))

(generator->list
  (tree-map->generator/key-range tm :> 2))
  ⇒ ((3 . d) (4 . e))

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と同じです。

以下の二つの手続きは二つのツリーマップを比較しますが、見方が異なります。

Function: tree-map-compare-as-sets tree-map1 tree-map2 :optional value=? fallback ¶

二つのツリーマップを、エントリの集合として比較します。エントリの集合として見れば、 ツリーマップ間に半順序関係を定義できます。すなわち、全てのエントリが等しければ ツリーマップ同士も等しく、ツリーマップAがツリーマップBの真部分集合であれば AはBより小さい、とします。

tree-map1とtree-map2が等しければ0が、 tree-map1の方がtree-map2より小さければ-1が、 tree-map1の方がtree-map2より大きければ1が返されます。

どちらのツリーマップも相手の部分集合になっていない場合は、順序が決められません。 その場合、fallback引数が与えられていればその値が返され、 与えられていなければエラーが報告されます。

tree-map1とtree-map2の比較器はequal?の意味で 等しくなければなりません。比較器については基本的な比較器を参照してください。

エントリは、それぞれのキーがツリーマップの比較器による比較で等しく、 かつ対応する値がvalue=?手続きによる比較で等しい場合にのみ等しいとみなされます。 value=?が省略された場合はequal?が使われます。

(tree-map-compare-as-sets
 (alist->tree-map '((1 . a) (2 . b) (3 . c)) default-comparator)
 (alist->tree-map '((3 . c) (1 . a) (2 . b)) default-comparator))
 ⇒ 0

(tree-map-compare-as-sets
 (alist->tree-map '((1 . a) (3 . c)) default-comparator)
 (alist->tree-map '((3 . c) (1 . a) (2 . b)) default-comparator))
 ⇒ -1

(tree-map-compare-as-sets
 (alist->tree-map '((1 . a) (3 . c) (4 . d) (2 . b)) default-comparator)
 (alist->tree-map '((3 . c) (1 . a) (2 . b)) default-comparator))
 ⇒ 1

(tree-map-compare-as-sets
 (alist->tree-map '((1 . a) (3 . c) (4 . d)) default-comparator)
 (alist->tree-map '((3 . c) (1 . a) (2 . b)) default-comparator))
 ⇒ ERROR: tree-maps can't be ordered

(tree-map-compare-as-sets
 (alist->tree-map '((1 . a) (3 . c) (4 . d)) default-comparator)
 (alist->tree-map '((3 . c) (1 . a) (2 . b)) default-comparator)
 eq?
 #f)
 ⇒ #f

Function: tree-map-compare-as-sequences tree-map1 tree-map2 :optional value-cmp ¶

二つのツリーマップを、キーの順序で並べられたエントリのシーケンスとして比較します。 両マップにキーが同じであるエントリがあった場合は、 対応する値同士をvalue-cmp比較器で比べます (従って、value-cmpは比較述語を持っていなければなりません。) value-cmpが省略された場合はdefault-comparatorが使われます。

tree-map1とtree-map2の比較器はequal?の意味で 等しくなければなりません。比較器については基本的な比較器を参照してください。

tree-map1とtree-map2が等しければ0が、 tree-map1の方がtree-map2より小さければ-1が、 tree-map1の方がtree-map2より大きければ1が返されます。

tree-map-compare-as-setsと異なり、 この手続きは比較器が同じであるようなツリーマップについて全順序関係を定義します。

(tree-map-compare-as-sequences
 (alist->tree-map '((1 . a) (3 . c)) default-comparator)
 (alist->tree-map '((3 . c) (2 . b)) default-comparator))
 ⇒ -1

(tree-map-compare-as-sequences
 (alist->tree-map '((2 . b) (3 . d)) default-comparator)
 (alist->tree-map '((3 . c) (2 . b)) default-comparator))
 ⇒ 1