TREE_SET¶

Provides an `ordered_set` implementation which stores all the elements in a balanced binary tree.

Tree set is a safe default choice, because it guarantees logarithmic worst-case computational complexity for operations like .push and .have?.

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

`new` returns a new empty tree `ordered_set`.

Config method

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

Comparison of elements

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

• 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_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"

Example: reversed order

: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` makes a new tree `ordered_set` which contains the values of `Elems`. The elements of are ordered by `<=` operator, or `op_le` method.

Precondition

The elements of `Elems` must be in the domain of the elements of the set.

Example

: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` makes a new empty tree `ordered_set` containing the elements of `Eacher`. The elements are ordered by `<=` operator, or `op_le` method.

Precondition

`Eacher` must implement each($consume) method, which calls $consume for each element of `Eacher`.

The elements of `Eacher` must be in the domain of the elements of the set.

Example

: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"