6.37. kink/container/TREE_SET

平衡二分木に要素を格納するorder_setの実装を提供する。

平衡二分木setは安全なデフォルトの選択肢である。これは、pushやhave?などの操作について、最悪ケースで対数オーダーの計算複雑性を保証するからである。

6.37.1. TREE_SET.new(...[$config={}])

newは空の平衡二分木order_setを新しく作って戻す。

コンフィグメソッド

C.order($up_to?): default = {(:X :Y) X <= Y }

全順序関係

$up_to?は、ふたつの値X, Yを取る関数でなければならない。 `up_to?(X Y)` は `X up-to Y` のbool値を返さなければならない。ここで、 `up-to` は要素の全順序関係である。

事前条件

$up_to?は、ふたつの引数を取ってboolを戻す関数でなければならない。

例: デフォルトの順序

:TREE_SET.require_from('kink/container/')

:Map <- TREE_SET.new
Map.push('foo')
Map.push('bar')
Map.push('baz')
stdout.print_line(Map.have?('foo').repr) # => true
stdout.print_line(Map.have?('FOO').repr) # => false
Map.each{(:Elem)
  stdout.print_line(Elem.repr)
}
# Output:
#   "bar"
#   "baz"
#   "foo"

例: 逆順

:TREE_SET.require_from('kink/container/')

:Map <- TREE_SET.new{(:C)
  C.order{(:X :Y) X >= Y }
}
Map.push('foo')
Map.push('bar')
Map.push('baz')
Map.each{(:Elem)
  stdout.print_line(Elem.repr)
}
# Output:
#   "foo"
#   "baz"
#   "bar"

6.37.2. TREE_SET.of(...Elems)

ofは、Elemsの要素を含む平衡二分木order_setを新しく作って戻す。要素は <= 演算子、つまりop_leメソッドで順序付けられる。

事前条件

Elemsの要素は、setの要素の定義域に含まれなければならない。

例

:TREE_SET.require_from('kink/container/')

:Map <- TREE_SET.of('foo' 'bar' 'baz')
stdout.print_line(Map.have?('foo').repr) # => true
stdout.print_line(Map.have?('FOO').repr) # => false
Map.each{(:Elem)
  stdout.print_line(Elem.repr)
}
# Output:
#   "bar"
#   "baz"
#   "foo"

6.37.3. TREE_SET.from_each(Eacher)

from_eachは、Eacherの要素を含む平衡二分木order_setを新しく作って戻す。要素は <= 演算子、つまりop_leメソッドで順序付けられる。

事前条件

Eacherはeach($consume)メソッドを実装しなければならない。eachメソッドは、Eacherのそれぞれの要素について$consumeを呼び出すものでなければならない。

Eacherの要素はsetの要素の定義域に含まれなければならない。

例

:TREE_SET.require_from('kink/container/')

:Iter <- ['foo' 'bar' 'baz'].iter
:Map <- TREE_SET.from_each(Iter)
stdout.print_line(Map.have?('foo').repr) # => true
stdout.print_line(Map.have?('FOO').repr) # => false
Map.each{(:Elem)
  stdout.print_line(Elem.repr)
}
# Output:
#   "bar"
#   "baz"
#   "foo"