赤黒木

gauche

タイマリストが rbtree になっている模様。どうもこれ、わしはあまりきちんとチェック入れていないデータ構造らしいことが段々分かってきた。Gauche 方面でも最近モジュールにしたらしく、とりあえずそれを足がかりにしてみることに。
ちなみに以下から取得してます。

ただ、ファイルを落としてすぐに云々とはいかなくて、落としたソレで試験にパスさせるために微妙にもごもごしてます。

  • rbtree-test.scm の (use util.rbtree) の前に (add-load-patn ".") を追加
  • rbtree-test.scm があるディレクトリに util ディレクトリを掘る
  • rbtree.scm を util の中に投入

これで Gauche な rbtree ではなくて download した rbtree が試験対象になるはず。

$ gosh ./rbtree-test.scm
Testing util.rbtree ...                                          
testing bindings in #<module util.rbtree> ... ok
<basic procedures>-------------------------------------------------------------
test make-rbtree, expects #t ==> ok
test rbtree-get, expects #<error> ==> ok
test rbtree-get, expects not-found ==> ok
test rbtree-get, expects #<error> ==> ok
test rbtree-put!, expects #<error> ==> ok
test rbtree-put!, expects "0" ==> ok
test rbtree-put!, expects ("0" "1") ==> ok
test rbtree-put!, expects bar ==> ok
test rbtree-check, expects #t ==> ok
test rbtree-delete! (exiting key), expects (#t not-found) ==> ok
test rbtree-delete! (non-existing key), expects #f ==> ok
test rbtree-delete!, expects no-error ==> ok
test rbtree->alist, expects () ==> ok
test rbtree->alist, expects ((0 . "0") (1 . "1") (2 . "2")) ==> ok
test alist->rbtree, expects ((0 . "0") (1 . "1") (2 . "2")) ==> ok
test rbtree-empty?, expects #f ==> ok
test rbtree-empty?, expects #t ==> ok
test rbtree-empty?, expects #<error> ==> ok
test rbtree-exists?, expects (#t #f) ==> ok
test rbtree-num-entries, expects (0 1 0) ==> ok
test rbtree-push!, expects (bar foo) ==> ok
test rbtree-pop!, expects (foo bar) ==> ok
test rbtree-update!, expects 2 ==> ok
test rbtree-min, expects (0 . "0") ==> ok
test rbtree-max, expects (2 . "2") ==> ok
test rbtree-min, expects #<error> ==> ok
test rbtree-min, expects #<error> ==> ok
test rbtree-min, expects default ==> ok
test rbtree-max, expects default ==> ok
test rbtree-keys, expects (0 1 2) ==> ok
test rbtree-values, expects ("0" "1" "2") ==> ok
test rbtree-copy, expects #t ==> ok
test rbtree-extract-min!, expects ((0 . "0") (1 . "1")) ==> ok
test rbtree-extract-max!, expects ((2 . "2") (1 . "1")) ==> ok
<iterators>--------------------------------------------------------------------
test for-each, expects ((1 . "1")) ==> ok
test rbtree-map, expects ((1 . "1")) ==> ok
test fold, expects ((1 . "1")) ==> ok
test fold-right, expects ((1 . "1")) ==> ok
<collection interfaces>--------------------------------------------------------
test map, expects (("0" . 0) ("1" . 1) ("2" . 1)) ==> ok
test call-with-builder, expects (("0" . 0) ("1" . 1) ("2" . 1)) ==> ok
<random insertion/deletion>----------------------------------------------------
test random insertion/deletion, expects done ==> ok
passed.
$

今から試験を確認しつつ中身を読みます。もしかするとメモの類を追記するかも。