TREE_MAP¶

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

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

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

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

コンフィグメソッド

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_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は、与えられたキーと値を含む平衡二分木order_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