TREE_MAP¶

Provides an `ordered_map` implementation which stores keys in a balanced binary tree.

Tree map is a safe default choice, because it guarantees logarithmic worst-case computational complexity for operations like `get` and `set`.

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

`new` returns a new empty tree `ordered_map`.

Config method

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

Comparison of keys

$in_order? is used to compare keys. $in_order? must be a toal order which satisfies the following for all X, Y, and Z in the domain of keys.

• reflexive: in_order?(X X)

• transitive: if in_order?(X Y) && in_order?(Y Z) then in_order?(X Z)

• antisymmetric: if in_order?(X Y) && in_order?(Y X) then X is equivalent to Y

• strongly connected: in_order?(X Y) || in_order?(Y X)

Precondition

$in_order? must be a fun which takes two values and returns a `bool`.

Example: default order

: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)  # => []

Example: custom order

: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` makes a new tree `ordered_map` which contains the given keys and values. Keys are ordered by `<=` operator, or `op_le` method.

The result map has key-value pairs (K0, V0), (K1, V1), (K2, V2) ,,,.

Precondition

`K0`, `K1`, `K2` ,,, must be in the domain of keys.

Example

: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