TREE_SET¶

Provides an `order_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 `order_set`.

Config method

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

Total order relation

$up_to? must be a function which takes two args X and Y. `up_to?(X Y)` must return the bool value of `X up-to Y`, where `up-to` is the total order relation of elements.

Precondition

$up_to? must be a function 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 `order_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 `order_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"