TREE_SET¶

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

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

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

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

コンフィグメソッド

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

要素の比較

要素は$in_order?で比較される。$in_order?は全順序関係であり、要素のドメイン内のすべてのX, Y, Zについて、次の条件を満たさなければならない。

• 反射律: in_order?(X X)

• 推移律: if in_order?(X Y) && in_order?(Y Z) then in_order?(X Z)

• 反対称律: if in_order?(X Y) && in_order?(Y X) then X is equivalent to Y

• 狭義の連結律: in_order?(X Y) || in_order?(Y X)

事前条件

$in_order?は、ふたつの引数を取って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の要素を含む平衡二分木ordered_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の要素を含む平衡二分木ordered_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"