6.36. kink/container/TREE_MAP

キーを平衡二分木に格納するordered_mapの実装を提供する。

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

6.36.1. TREE_MAP.new(...[$config={}])

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

コンフィグメソッド

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_MAP.require_from('kink/container/')

:Map <- TREE_MAP.new
Map.set('one' 1)
Map.set('two' 2)
Map.set('three' 3)
Map.set('four' 4)
stdout.print_line(Map.get_opt('one').repr)  # => [1]
stdout.print_line(Map.get_opt('two').repr)  # => [2]
stdout.print_line(Map.get_opt('TWO').repr)  # => []

例: 自前の順序

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

:Map <- TREE_MAP.new{(:C)
  C.order{(:X :Y)
    X.ascii_downcase <= Y.ascii_downcase
  }
}
Map.set('one' 1)
Map.set('two' 2)
Map.set('three' 3)
Map.set('four' 4)
stdout.print_line(Map.get_opt('one').repr)  # => [1]
stdout.print_line(Map.get_opt('two').repr)  # => [2]
stdout.print_line(Map.get_opt('TWO').repr)  # => [2]

6.36.2. TREE_MAP.of(...[K0 V0 K1 V1 ,,,])

ofは、与えられたキーと値を含む平衡二分木ordered_mapを新しく作って戻す。キーは <= 演算子、またはop_leメソッドで順序付けられる。

結果のmapは、(K0, V1), (K1, V1), (K2, V2) ,,, のキー/値ペアを持つ。

事前条件

K0, K1, K2 ,,, はキーの定義域に含まれなければならない。

例

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

:Map <- TREE_MAP.of('one' 1 'two' 2 'three' 3 'four' 4)
Map.pair_iter.each{([:K :V])
  stdout.print_line('{} => {}'.format(K.repr V.repr))
}
# Output:
#   "four" => 4
#   "one" => 1
#   "three" => 3
#   "two" => 2