M.Hiroi's Home Page

Functional Programming

お気楽 Scheme プログラミング入門

オブジェクト指向編

[ PrevPage | Scheme | NextPage ]

二分木

今回も簡単な例題として「二分木」というデータ構造を作ってみましょう。拙作の Scheme 入門講座 二分木 ではリストとクロージャを使って二分木を実装しましたが、オブジェクト指向を使っても簡単にプログラムを作ることができます。

なお、Gauche には平衡木の一種である赤黒木を使った「ツリーマップ (tree-map) 」という組み込みライブラリが用意されています。自分で二分木を作る必要はまったくありませんが、オブジェクト指向の勉強ということで、プログラムを作ってみましょう。

●二分木の仕様

Gauche の <tree-map> はキーと値を格納しますが、今回作成する二分木はキーだけを格納することとし、重複した要素は含まないものとします。クラス名は <tree-set> としました。キーを比較する関数は <tree-set> のインスタンスを生成するときに指定します。キーワード :obj=? には 2 つの引数が等しいときに真を返す述語を、:obj<? には第 1 引数が第 2 引数より小さい場合に真を返す述語を渡します。デフォルトでは obj=? が eqv? で、obj<? が < とします。

これだけでは面白くないので、要素からキーを取り出す関数をキーワード :key で指定できるようにします。たとえば、コンスセル (a . b) を要素とする場合、:key に car を指定すると、コンスセルの CAR 部をキーとして二分木を構成します。cdr を指定すると、CDR 部をキーとして二分木が構成されます。:key を指定することで、<tree-map> と同じような動作を行わせることも可能です。:key のデフォルトは (lambda (x) x) とします。

次は、クラス <tree-set> で公開するメソッドを表 1 に示します。

表 1 : 二分木の操作メソッド
メソッド機能
tree-member? tree keytree に key が存在すれば #t を返す
tree-get tree keytree から key を持つ要素を求める
tree-put! tree valuetree に要素 value を追加する
tree-delete! tree keytree から key を持つ要素を削除する
tree-get-min treetree から最小値を求める
tree-get-max treetree から最大値を求める
tree-delete-min! treetree から最小値を削除する
tree-delete-max! treetree から最大値を削除する
tree-fold tree func inittree の要素に畳み込みを行う
tree-for-each tree functree の要素に関数 func を適用する
tree-copy treetree をコピーする
tree-empty? treetree が空の場合は #t を返す
tree-num-entries treetree の要素数を求める

:key を指定しない場合、引数 key と引数 value に違いはありませんが、:key を指定する場合、二分木に格納する要素と key は異なるデータになります。たとえば、コンスセル (a . b) を格納する場合、tree-put! の引数 value はコンスセルになり、他のメソッドの引数 key は CAR 部のデータになります。また、tree-get の返り値はキーではなくコンスセルになります。

●クラスの定義

それではプログラムを作りましょう。最初に、節 (ノード) と二分木を表すクラスを定義します。次のリストを見てください。

リスト 1 : クラスの定義

; 節の定義
(define-class <node> ()
  ((item  :accessor node-item  :init-keyword :item)
   (left  :accessor node-left  :init-keyword :left)
   (right :accessor node-right :init-keyword :right)))

; メタクラス
(define-class <tree-set-meta> (<class>)
  ((term :accessor get-term :initform (make <node>))))

; 二分木
(define-class <tree-set> (<collection>)
  ((root :accessor     tree-root
         :init-form    (get-term <tree-set>)
         :init-keyword :root)
   (obj=?  :accessor get-obj=? :init-value eqv? :init-keyword :obj=?)
   (obj<?  :accessor get-obj<? :init-value <    :init-keyword :obj<?)
   (key    :accessor get-key   :init-value (lambda (x) x) :init-keyword :key))
  :metaclass <tree-set-meta>)

節はクラス <node> で表します。スロット item にデータを、left に左の子を、right に右の子を格納します。二分木はクラス <tree-set> で表します。スロット root に二分木のルートを格納します。拙作の Scheme 講座 では、二分木の終端を空リストで表しましたが、今回は終端を表す節を用意することにします。

終端はクラスにただ一つだけあればよく、複数あってはいけません。そこで、クラス <tree-set> のスロット term に終端を格納することにします。これはメタクラス <tree-set-meta> でスロット item を定義することで簡単に実現できます。<tree-set-meta> からクラスオブジェクト <tree-set> が生成されるとき、スロット term に <node> のインスタンスがセットされます。

<tree-set> は <collection> を Mix-in します。<tree-set> のスロット obj=? と obj<? には要素を比較する述語をセットします。obj=? には要素が等しいときに #t を返す述語を、obj<? には第 1 引数が第 2 引数よりも小さい場合に #t を返す述語をセットします。デフォルトの値は eqv? と < です。

スロット key には要素からキーを取り出す関数をセットします。デフォルトは引数をそのまま返す関数 (lambda (x) x) です。それから、終端を判定する関数を用意しておくと便利です。

リスト 2 : 終端の判定

(define (tree-end? node)
  (eq? (get-term <tree-set>) node))

終端は (get-term <tree-set>) で求めることができます。あとは eq? で引数 node と比較するだけです。同様に、節を生成する関数 make-node も用意しておきます。

リスト 3 : 節の生成

(define (make-node value)
  (make <node>
        :item  value
        :left  (get-term <tree-set>)
        :right (get-term <tree-set>)))

この関数でスロット left と right の値を終端で初期化します。

●データの探索

次は、二分木の中から key を探索するメソッド tree-member? と tree-get を作ります。

リスト 4 : データの探索

(define (node-get node key key-of obj=? obj<?)
  (let loop ((node node))
    (cond ((tree-end? node) #f)
          ((obj=? key (key-of (node-item node)))
           (node-item node))
          ((obj<? key (key-of (node-item node)))
           (loop (node-left node)))
          (else
           (loop (node-right node))))))

; データの探索 (要素を返す)
(define-method tree-get ((tree <tree-set>) key)
  (node-get (tree-root tree)
            key
            (get-key tree)
            (get-obj=? tree)
            (get-obj<? tree)))

; データの探索 (boolean を返す)
(define-method tree-member? ((tree <tree-set>) key)
  (if (tree-get tree key) #t #f))

tree-get は関数 node-get を呼び出します。このとき、スロット key, obj=?, obj<? から関数を取り出して node-get に渡します。データを比較するとき、節 node からキーを求めるため、node に関数 key-of を適用することを忘れないでください。あとは、とくに難しいところないでしょう。

●データの挿入

次は二分木にデータを挿入するメソッド tree-put! です。

リスト 5 : データの挿入

(define (node-put! node key value key-of obj=? obj<?)
  (define (node-put-sub! node)
    (cond ((tree-end? node) (make-node value))
          ((obj=? key (key-of (node-item node)))
           (set! (node-item node) value)
           node)
          ((obj<? key (key-of (node-item node)))
           (set! (node-left node)
                 (node-put-sub! (node-left node)))
           node)
          (else
           (set! (node-right node)
                 (node-put-sub! (node-right node)))
           node)))
  (node-put-sub! node))

; データの挿入
(define-method tree-put! ((tree <tree-set>) value)
  (set! (tree-root tree)
        (node-put! (tree-root tree)
                   ((get-key tree) value)
                   value
                   (get-key tree)
                   (get-obj=? tree)
                   (get-obj<? tree))))

実際の処理は関数 node-insert! で行います。このとき、引数 value からキーを取り出して渡すことに注意してください。キーの比較は tree-get と同じです。node が終端であれば、新しい節を make-node で作成して返します。同じキーが見つかった場合、節の item を value に書き換えます。こうするとキー以外の値を更新することができるので便利です。

●データの削除

次はデータを削除するメソッド tree-delete! を作ります。

リスト 6 : データの削除

(define (node-delete! node key fail key-of obj=? obj<?)
  (define (node-delete-sub! node)
    (cond ((tree-end? node) (fail #f))
          ((obj=? key (key-of (node-item node)))
           (cond ((tree-end? (node-left node))
                  (node-right node))
                 ((tree-end? (node-right node))
                  (node-left node))
                 (else
                  (set! (node-item node)
                        (node-search-min (node-right node)))
                  (set! (node-right node)
                        (node-delete-min! (node-right node)))
                  node)))
          ((obj<? key (key-of (node-item node)))
           (set! (node-left node)
                 (node-delete-sub! (node-left node)))
           node)
          (else
           (set! (node-right node)
                 (node-delete-sub! (node-right node)))
           node)))
  (node-delete-sub! node))

; データの削除
(define-method tree-delete! ((tree <tree-set>) key)
  (call/cc
    (lambda (fail)
      (set! (tree-root tree)
            (node-delete! (tree-root tree)
                          key
                          fail
                          (get-key tree)
                          (get-obj=? tree)
                          (get-obj<? tree))))))

実際の処理は関数 node-delete! で行います。キーの比較は tree-get, tree-put! と同じです。木の途中にある節を削除する場合は、節の値を右部分木の最小値に置き換えてから、最小値を格納していた節を削除します。最小値を探す関数が node-search-min で、最小値を削除する関数が node-delete-min! です。データの削除処理はちょっと複雑です。詳しい説明は拙作のページ 二分木 をお読みください。

●巡回

次は二分木を巡回する高階関数 tree-for-each を作ります。次のリストを見てください。

リスト 7 : 二分木の巡回

; 二分木を巡回する
(define (tree-for-each-sub func node before after)
  (cond ((not (tree-end? node))
         (tree-for-each-sub func (before node) before after)
         (func (node-item node))
         (tree-for-each-sub func (after node) before after))))

; 巡回
(define-method tree-for-each ((tree <tree-set>) func . opts)
  (if (get-keyword :from-end opts #f) 
      (tree-for-each-sub func (tree-root tree) node-right node-left)
    (tree-for-each-sub func (tree-root tree) node-left node-right)))

実際の処理は関数 tree-for-each-sub で行います。この関数はイテレータを作成するときにも使います。処理は簡単で、通りがけ順で二分木を巡回して、要素 (note-item node) に関数 func を適用します。:from-end の真偽値で、木を巡回する順序を変更します。真の場合、最初が右部分木で、次に節の要素、最後に左部分木を巡回します。偽の場合は最初に左部分木を巡回します。この処理は引数 after, before にメソッド node-left, node-right を渡すことで簡単に実現できます。

●イテレータと畳み込み

次はイテレータ call-with-iterator と畳み込みを行う tree-fold を作ります。なお。call-with-builder は実装しないので、他のコレクションから <tree-set> に変換することはできません。二分木のイテレータは「継続」を使うと簡単にプログラムできます。拙作のページ 継続と継続渡しスタイル より、イテレータを生成する関数を再掲します。

リスト 8 : イテレータを生成する関数

(define (make-iter proc . args)
  (letrec ((iter
            (lambda (return)
              (apply 
                proc
                (lambda (x)             ; 高階関数に渡す関数の本体
                  (set! return          ; 脱出先継続の書き換え
                   (call/cc
                    (lambda (cont)
                      (set! iter cont)  ; 継続の書き換え
                      (return x)))))
                args)
                ; 終了後は継続 return で脱出
                (return #f))))
    (lambda ()
      (call/cc
        (lambda (cont) (iter cont))))))

make-iter に tree-for-each を渡すと、二分木の要素をひとつずつ順番に取り出すイテレータを生成することができます。プログラムは次のようになります。

リスト 9 : イテレータと畳み込み

; 木のイテレータを作る
(define (make-iter-tree node from-end)
  (if from-end
      (make-iter tree-for-each-sub node node-right node-left)
    (make-iter tree-for-each-sub node node-left node-right)))

; <collection> 用イテレータ
(define-method call-with-iterator ((tree <tree-set>) proc . opts)
  (let* ((iter (make-iter-tree (tree-root tree)
                               (get-keyword :from-end opts #f)))
         (item (iter)))
    (proc (lambda () (eq? item #f))
          (lambda () (begin0 item (set! item (iter)))))))

; 畳み込み
(define-method tree-fold ((tree <tree-set>) func init . opts)
  (let ((from-end (get-keyword :from-end opts #f)))
    (call-with-iterator
      tree
      (lambda (end? next)
        (let loop ((a init))
          (if (end?)
              a
            (loop (if from-end (func (next) a) (func a (next)))))))
      :from-end from-end)))

make-iter-tree は引数 from-end の値により、二分木を巡回する順番を変更します。これは node-left と node-right を渡す順番を変えるだけです。call-with-iterator は make-iter-tree を呼び出し、その返り値 (イテレータ) を変数 iter にセットします。そして、iter を呼び出して二分木から取り出した要素を変数 item にセットします。要素がなくなった場合、イテレータは #f を返すので、item の値が #f ならば終了と判断することができます。要素を返す関数は、begin0 で item の値を返してから (iter) で更新します。

畳み込みを行うメソッド tree-fold は call-with-iterator を使って実装します。named-let で二分木から要素を取り出して、関数 func に適用するだけです。from-end の値によって、func に渡す引数の順番が逆になることに注意してください。最後に累積変数 a の値を返します。

あとのメソッドは簡単なので説明は割愛いたします。詳細は プログラムリスト1 をお読みください。

●実行例

それでは簡単な実行例を示しましょう。

gosh> (use srfi-1)
#<undef>
gosh> (use srfi-27)
#<undef>
gosh> (use tree_set)
#<undef>
gosh> (define xs (list-tabulate 16 (lambda (x) (random-integer 1000))))
xs
gosh> xs
(992 546 188 278 547 97 308 632 221 913 968 126 835 905 135 814)
gosh> (define a (make <tree-set>))
a
gosh> (dolist (x xs) (tree-put! a x))
()
gosh> (tree-for-each a (lambda (x) (format #t "~D " x)))
97 126 135 188 221 278 308 546 547 632 814 835 905 913 968 992 #<undef>
gosh> (tree-for-each a (lambda (x) (format #t "~D " x)) :from-end #t)
992 968 913 905 835 814 632 547 546 308 278 221 188 135 126 97 #<undef>
gosh> (dolist (x xs) (tree-delete! a x)
(tree-for-each a (lambda (x) (format #t "~D " x))) (newline))
97 126 135 188 221 278 308 546 547 632 814 835 905 913 968
97 126 135 188 221 278 308 547 632 814 835 905 913 968
97 126 135 221 278 308 547 632 814 835 905 913 968
97 126 135 221 308 547 632 814 835 905 913 968
97 126 135 221 308 632 814 835 905 913 968
126 135 221 308 632 814 835 905 913 968
126 135 221 632 814 835 905 913 968
126 135 221 814 835 905 913 968
126 135 814 835 905 913 968
126 135 814 835 905 968
126 135 814 835 905
135 814 835 905
135 814 905
135 814
814

()
gosh> (tree-empty? a)
#t

srfi-1 は list-tabulate を使うために、srfi-27 は random-integer を使うためにロードします。正常に動作していますね。次は :key を指定した例を示します。

gosh> (define b (make <tree-set> :key car :obj=? string=? :obj<? string<?))
b
gosh> (dolist (x xs) (tree-put! b (cons (number->string x) x)))
()
gosh> (tree-for-each a (lambda (x) (format #t "~S~%" x)))
#<undef>
gosh> (tree-for-each b (lambda (x) (format #t "~S~%" x)))
("126" . 126)
("135" . 135)
("188" . 188)
("221" . 221)
("278" . 278)
("308" . 308)
("546" . 546)
("547" . 547)
("632" . 632)
("814" . 814)
("835" . 835)
("905" . 905)
("913" . 913)
("968" . 968)
("97" . 97)
("992" . 992)
#<undef>
gosh> (dolist (x (map number->string xs)) (format "~S: ~S~%" x (tree-get b x)))
()
gosh> (dolist (x (map number->string xs)) (format #t "~S: ~S~%" x (tree-get b x)))
"992": ("992" . 992)
"546": ("546" . 546)
"188": ("188" . 188)
"278": ("278" . 278)
"547": ("547" . 547)
"97": ("97" . 97)
"308": ("308" . 308)
"632": ("632" . 632)
"221": ("221" . 221)
"913": ("913" . 913)
"968": ("968" . 968)
"126": ("126" . 126)
"835": ("835" . 835)
"905": ("905" . 905)
"135": ("135" . 135)
"814": ("814" . 814)
()
gosh> (dolist (x (map number->string xs))
(tree-put! b (cons x (* (cdr (tree-get b x)) 10))))
()
gosh> (tree-for-each b (lambda (x) (format #t "~S~%" x)))
("126" . 1260)
("135" . 1350)
("188" . 1880)
("221" . 2210)
("278" . 2780)
("308" . 3080)
("546" . 5460)
("547" . 5470)
("632" . 6320)
("814" . 8140)
("835" . 8350)
("905" . 9050)
("913" . 9130)
("968" . 9680)
("97" . 970)
("992" . 9920)
#<undef>

このように、:key を指定することで <tree-map> と同じような動作を行わせることもできます。ただし、今回のプログラムは単純な二分木なので、バランスが崩れると性能は大きく劣化してしまいます。もしも、実用的に使うのであれば、<tree-map> のように平衡木をプログラムしたほうがよいでしょう。平衡木のアルゴリズムは拙作のページ Algorithms with Python で詳しく説明しています。興味のある方は下記ページをお読みくださいませ。


●プログラムリスト1

;
; tree_set.scm : 二分木
;
;              Copyright (C) 2010 Makoto Hiroi
;
(define-module tree_set
  (use gauche.collection)
  (export <tree-set>
          tree-member? tree-get tree-put! tree-delete!
            tree-get-min tree-get-max
          tree-delete-min! tree-delete-max!
          tree-fold tree-for-each tree-copy
          tree-empty? tree-num-entries
        ))

(select-module tree_set)

;;; クラス定義

; 節の定義
(define-class <node> ()
  ((item  :accessor node-item  :init-keyword :item)
   (left  :accessor node-left  :init-keyword :left)
   (right :accessor node-right :init-keyword :right)))

; メタクラス
(define-class <tree-set-meta> (<class>)
  ((term :accessor get-term :initform (make <node>))))

; 二分木
(define-class <tree-set> (<collection>)
  ((root :accessor     tree-root
         :init-form    (get-term <tree-set>)
         :init-keyword :root)
   (obj=? :accessor get-obj=? :init-value eqv? :init-keyword :obj=?)
   (obj<? :accessor get-obj<? :init-value <    :init-keyword :obj<?)
   (key   :accessor get-key   :init-value (lambda (x) x) :init-keyword :key)
   (tools :accessor get-tools))
  :metaclass <tree-set-meta>)

;;; 作業用関数

; 終端の判定
(define (tree-end? node)
  (eq? (get-term <tree-set>) node))

; 節の生成
(define (make-node value)
  (make <node>
        :item  value
        :left  (get-term <tree-set>)
        :right (get-term <tree-set>)))

; 部分木 node の最小値を探す
(define (node-search-min node)
  (if (tree-end? (node-left node))
      (node-item node)
    (node-search-min (node-left node))))

; 部分木 node の最大値を探す
(define (node-search-max node)
  (if (tree-end? (node-right node))
      (node-item node)
    (node-search-max (node-right node))))

; 部分木 node から最小値を削除する
(define (node-delete-min! node)
  (cond ((tree-end? (node-left node))
         (node-right node))
        (else
         (set! (node-left node)
               (node-delete-min! (node-left node)))
         node)))

; 部分木 node から最大値を削除する
(define (node-delete-max! node)
  (cond ((tree-end? (node-right node))
         (node-left node))
        (else
         (set! (node-right node)
               (node-delete-max! (node-right node)))
         node)))

; データの探索
(define (node-get node key key-of obj=? obj<?)
  (let loop ((node node))
    (cond ((tree-end? node) #f)
          ((obj=? key (key-of (node-item node)))
           (node-item node))
          ((obj<? key (key-of (node-item node)))
           (loop (node-left node)))
          (else
           (loop (node-right node))))))

; データの挿入
(define (node-put! node key value key-of obj=? obj<?)
  (define (node-put-sub! node)
    (cond ((tree-end? node) (make-node value))
          ((obj=? key (key-of (node-item node)))
           (set! (node-item node) value)
           node)
          ((obj<? key (key-of (node-item node)))
           (set! (node-left node)
                 (node-put-sub! (node-left node)))
           node)
          (else
           (set! (node-right node)
                 (node-put-sub! (node-right node)))
           node)))
  (node-put-sub! node))

; データの削除
(define (node-delete! node key fail key-of obj=? obj<?)
  (define (node-delete-sub! node)
    (cond ((tree-end? node) (fail #f))
          ((obj=? key (key-of (node-item node)))
           (cond ((tree-end? (node-left node))
                  (node-right node))
                 ((tree-end? (node-right node))
                  (node-left node))
                 (else
                  (set! (node-item node)
                        (node-search-min (node-right node)))
                  (set! (node-right node)
                        (node-delete-min! (node-right node)))
                  node)))
          ((obj<? key (key-of (node-item node)))
           (set! (node-left node)
                 (node-delete-sub! (node-left node)))
           node)
          (else
           (set! (node-right node)
                 (node-delete-sub! (node-right node)))
           node)))
  (node-delete-sub! node))

; 二分木を巡回する
(define (tree-for-each-sub func node before after)
  (cond ((not (tree-end? node))
         (tree-for-each-sub func (before node) before after)
         (func (node-item node))
         (tree-for-each-sub func (after node) before after))))

; イテレータを生成する関数
(define (make-iter proc . args)
  (letrec ((iter
            (lambda (return)
              (apply 
                proc
                (lambda (x)             ; 高階関数に渡す関数の本体
                  (set! return          ; 脱出先継続の書き換え
                   (call/cc
                    (lambda (cont)
                      (set! iter cont)  ; 継続の書き換え
                      (return x)))))
                args)
                ; 終了後は継続 return で脱出
                (return #f))))
    (lambda ()
      (call/cc
        (lambda (cont) (iter cont))))))

; 木のイテレータを作る
(define (make-iter-tree node from-end)
  (if from-end
      (make-iter tree-for-each-sub node node-right node-left)
    (make-iter tree-for-each-sub node node-left node-right)))


;;; メソッドの定義

; データの挿入
(define-method tree-put! ((tree <tree-set>) value)
  (set! (tree-root tree)
        (node-put! (tree-root tree)
                   ((get-key tree) value)
                   value
                   (get-key tree)
                   (get-obj=? tree)
                   (get-obj<? tree))))

; データの探索 (要素を返す)
(define-method tree-get ((tree <tree-set>) key)
  (node-get (tree-root tree)
            key
            (get-key tree)
            (get-obj=? tree)
            (get-obj<? tree)))

; データの探索 (boolean を返す)
(define-method tree-member? ((tree <tree-set>) key)
  (if (tree-get tree key) #t #f))

; データの削除
(define-method tree-delete! ((tree <tree-set>) key)
  (call/cc
    (lambda (fail)
      (set! (tree-root tree)
            (node-delete! (tree-root tree)
                          key
                          fail
                          (get-key tree)
                          (get-obj=? tree)
                          (get-obj<? tree))))))

; 最大値を求める
(define-method tree-get-max ((tree <tree-set>))
  (if (tree-end? (tree-root tree))
      #f
    (node-search-max (tree-root tree))))

; 最小値を求める
(define-method tree-get-min ((tree <tree-set>))
  (if (tree-end? (tree-root tree))
      #f
    (node-search-min (tree-root tree))))

; 最大値を削除
(define-method tree-delete-max! ((tree <tree-set>))
  (if (tree-end? (tree-root tree))
      #f
    (begin0
      (node-search-max (tree-root tree))
      (set! (tree-root tree)
            (node-delete-max! (tree-root tree))))))

; 最小値を削除
(define-method tree-delete-min! ((tree <tree-set>))
  (if (tree-end? (tree-root tree))
      #f
    (begin0
      (node-search-min (tree-root tree))
      (set! (tree-root tree)
            (node-delete-min! (tree-root tree))))))

; 巡回
(define-method tree-for-each ((tree <tree-set>) func . opts)
  (if (get-keyword :from-end opts #f) 
      (tree-for-each-sub func (tree-root tree) node-right node-left)
    (tree-for-each-sub func (tree-root tree) node-left node-right)))

; <collection> 用イテレータ
(define-method call-with-iterator ((tree <tree-set>) proc . opts)
  (let* ((iter (make-iter-tree (tree-root tree)
                               (get-keyword :from-end opts #f)))
         (item (iter)))
    (proc (lambda () (eq? item #f))
          (lambda () (begin0 item (set! item (iter)))))))

; 畳み込み
(define-method tree-fold ((tree <tree-set>) func init . opts)
  (let ((from-end (get-keyword :from-end opts #f)))
    (call-with-iterator
      tree
      (lambda (end? next)
        (let loop ((a init))
          (if (end?)
              a
            (loop (if from-end (func (next) a) (func a (next)))))))
      :from-end from-end)))

; コピー
(define-method tree-copy ((tree <tree-set>))
  (define (node-copy node)
    (if (tree-end? node)
        node
      (make <node>
            :item  (node-item node)
            :left  (node-copy (node-left node))
            :right (node-copy (node-right node)))))
  ;
  (make <tree-set> :root  (node-copy (tree-root tree))
                   :obj=? (get-obj=? tree)
                   :obj<? (get-obj<? tree)))

; 空か?
(define-method tree-empty? ((tree <tree-set>))
  (tree-end? (tree-root tree)))

; 要素数
(define-method tree-num-entries ((tree <tree-set>))
  (tree-fold tree (lambda (a x) (+ a 1)) 0))

; 空にする
(define-method tree-clear! ((tree <tree-set>))
  (set! (tree-root tree) (get-term <tree-set>)))

(provide "tree_set")

Copyright (C) 2010 Makoto Hiroi
All rights reserved.

[ PrevPage | Scheme | NextPage ]