# Binary Tree Map

Properties:

• unique root
• node.left.key < node.key
• node.right.key > node.key
• no duplicates allowed

Operations:

• search average O(lg n) worst O(n)
• insert average O(lg n) worst O(n)
• delete average O(lg n) worst O(n)

Usage:

``````var tree = new BinTreeMap[Int, String]
tree[1] = "n1"
assert tree.min == "n1"``````

### Introduced properties

##### init defaultinit

trees :: BinTreeMap :: defaultinit

##### fun delete(key: K): nullable E

trees :: BinTreeMap :: delete

Delete node at `key` (also return the deleted node value)
##### protected fun dot_down(node: N, f: ProcessWriter)

trees :: BinTreeMap :: dot_down

Translate the tree in dot format starting from `node`.
##### protected fun insert_node(node: N)

trees :: BinTreeMap :: insert_node

Add `node` in the tree.
##### fun max: E

trees :: BinTreeMap :: max

Get the node with the maximum key
##### protected fun max_from(node: N): N

trees :: BinTreeMap :: max_from

Get the right-most child from `node`.
##### fun min: E

trees :: BinTreeMap :: min

Get the node with the minimum key
##### protected fun min_from(node: N): N

trees :: BinTreeMap :: min_from

Get the left-most child from `node`.
##### protected fun print_tree(node: N): String

trees :: BinTreeMap :: print_tree

Print the tree starting from `node`.
##### protected fun rotate_left(node: N)

trees :: BinTreeMap :: rotate_left

Perform left rotation on `node`
##### protected fun rotate_right(node: N)

trees :: BinTreeMap :: rotate_right

Perform right rotation on `node`
##### protected fun search_down(from: N, key: nullable Object): nullable N

trees :: BinTreeMap :: search_down

Search `key` in `from` and its children nodes.
##### protected fun shift_down(from: N, node: N)

trees :: BinTreeMap :: shift_down

Push down the `node` in tree from a specified `from` index
##### fun sort: Array[E]

trees :: BinTreeMap :: sort

Sort the tree into an array
##### protected fun sort_down(node: N, sorted: Array[E])

trees :: BinTreeMap :: sort_down

Sort the tree from `node` and place results in `sorted`.
##### protected fun transplant(node: nullable N, other: nullable N)

trees :: BinTreeMap :: transplant

Swap a `node` with the `other` in this Tree

### Redefined properties

##### redef type N: BinTreeNode[K, E]

trees \$ BinTreeMap :: N

Type of nodes used in this tree implementation
##### redef type SELF: BinTreeMap[K, E]

trees \$ BinTreeMap :: SELF

Type of this instance, automatically specialized in every class
##### redef fun [](key: nullable Object): E

trees \$ BinTreeMap :: []

Get the node value associated to `key`
##### redef fun []=(key: K, item: E)

trees \$ BinTreeMap :: []=

Insert a new node in tree using `key` and `item`
##### redef fun has_key(key: nullable Object): Bool

trees \$ BinTreeMap :: has_key

O(n) in worst case, average is O(h) with h: tree height
##### redef fun is_empty: Bool

trees \$ BinTreeMap :: is_empty

O(n) in worst case, average is O(h) with h: tree height
##### redef fun iterator: MapIterator[K, E]

trees \$ BinTreeMap :: iterator

Nodes are iterated in the same order in which they were added to the tree.
##### redef fun length: Int

trees \$ BinTreeMap :: length

O(n)
##### redef fun show_dot

trees \$ BinTreeMap :: show_dot

Display the tree in a gaphical windows
##### redef fun to_s: String

trees \$ BinTreeMap :: to_s

User readable representation of `self`.

## All properties

##### fun !=(other: nullable Object): Bool

core :: Object :: !=

Have `self` and `other` different values?
##### fun ==(other: nullable Object): Bool

core :: Object :: ==

Have `self` and `other` the same value?
##### type CLASS: Class[SELF]

core :: Object :: CLASS

The type of the class of self.
##### protected type N: TreeNode[K, E]

trees :: TreeMap :: N

Type of nodes used in this tree implementation
##### type SELF: Object

core :: Object :: SELF

Type of this instance, automatically specialized in every class
##### abstract fun [](key: nullable Object): V

Get the item at `key`
##### abstract fun []=(key: K, value: V)

core :: Map :: []=

Set the `value` at `key`.
##### protected fun accept_json_serializer(v: JsonSerializer)

serialization :: Serializable :: accept_json_serializer

Refinable service to customize the serialization of this class to JSON
##### protected fun accept_msgpack_attribute_counter(v: AttributeCounter)

serialization :: Serializable :: accept_msgpack_attribute_counter

Hook to customize the behavior of the `AttributeCounter`
##### protected fun accept_msgpack_serializer(v: MsgPackSerializer)

serialization :: Serializable :: accept_msgpack_serializer

Hook to customize the serialization of this class to MessagePack

Add each (key,value) of `map` into `self`.
##### protected fun add_to_bundle(bundle: NativeBundle, key: JavaString)

Called by `[]=` to dynamically choose the appropriate method according
##### protected fun class_factory(name: String): CLASS

core :: Object :: class_factory

Implementation used by `get_class` to create the specific class.
##### fun class_name: String

core :: Object :: class_name

The class name of the object.
##### abstract fun clear

core :: Map :: clear

Remove all items
##### fun core_serialize_to(serializer: Serializer)

serialization :: Serializable :: core_serialize_to

Actual serialization of `self` to `serializer`
##### init defaultinit

trees :: BinTreeMap :: defaultinit

##### init defaultinit

serialization :: Serializable :: defaultinit

##### init defaultinit

core :: Object :: defaultinit

##### init defaultinit

trees :: TreeMap :: defaultinit

##### init defaultinit

core :: Map :: defaultinit

##### fun delete(key: K): nullable E

trees :: BinTreeMap :: delete

Delete node at `key` (also return the deleted node value)
##### protected fun dot_down(node: N, f: ProcessWriter)

trees :: BinTreeMap :: dot_down

Translate the tree in dot format starting from `node`.
##### fun filter_keys(keys: Collection[nullable Object]): Array[K]

Return all elements of `keys` that have a value.
##### init from_deserializer(deserializer: Deserializer)

serialization :: Serializable :: from_deserializer

Create an instance of this class from the `deserializer`
##### fun get_class: CLASS

core :: Object :: get_class

The meta-object representing the dynamic type of `self`.
##### fun get_or_default(key: nullable Object, default: V): V

Get the item at `key` or return `default` if not in map
##### fun get_or_null(key: nullable Object): nullable V

Get the item at `key` or null if `key` is not in the map.
##### fun has_key(key: nullable Object): Bool

Is there an item associated with `key`?
##### fun hash: Int

core :: Object :: hash

The hash code of the object.
##### init init

core :: Object :: init

##### protected fun insert_node(node: N)

trees :: BinTreeMap :: insert_node

Add `node` in the tree.
##### fun inspect: String

core :: Object :: inspect

Developer readable representation of `self`.

Return "CLASSNAME:#OBJECTID".
##### abstract fun is_empty: Bool

Is there no item in the collection?
##### intern fun is_same_instance(other: nullable Object): Bool

core :: Object :: is_same_instance

Return true if `self` and `other` are the same instance (i.e. same identity).
##### fun is_same_serialized(other: nullable Object): Bool

core :: Object :: is_same_serialized

Is `self` the same as `other` in a serialization context?
##### intern fun is_same_type(other: Object): Bool

core :: Object :: is_same_type

Return true if `self` and `other` have the same dynamic type.
##### abstract fun iterator: MapIterator[K, V]

Get a new iterator on the map.
##### abstract fun join(sep: String, couple_sep: String): String

core :: Map :: join

Concatenate couples of key value.
##### abstract fun keys: Collection[K]

Return the point of view of self on the keys only.
##### fun keys_sorted_by_values(comparator: Comparator): Array[K]

Return an array of all keys sorted with their values using `comparator`.
##### abstract fun length: Int

Number of items in the collection.
##### fun lookup_all_values(pe: POSetElement[K]): Set[V]

Search all the values in `pe.greaters`.
##### fun lookup_values(pe: POSetElement[K]): Set[V]

Combine the values in `pe.greaters` from the most smaller elements that have a value.
##### fun max: E

trees :: BinTreeMap :: max

Get the node with the maximum key
##### protected fun max_from(node: N): N

trees :: BinTreeMap :: max_from

Get the right-most child from `node`.
##### fun min: E

trees :: BinTreeMap :: min

Get the node with the minimum key
##### protected fun min_from(node: N): N

trees :: BinTreeMap :: min_from

Get the left-most child from `node`.
##### protected fun msgpack_extra_array_items: Int

serialization :: Serializable :: msgpack_extra_array_items

Hook to request a larger than usual metadata array
##### init new: Map[K, V]

core :: Map :: new

Get a `HashMap[K, V]` as default implementation
##### fun not_empty: Bool

Alias for `not is_empty`.
##### intern fun object_id: Int

core :: Object :: object_id

An internal hash code for the object based on its identity.
##### fun output

core :: Object :: output

Display self on stdout (debug only).
##### intern fun output_class_name

core :: Object :: output_class_name

Display class name on stdout (debug only).
##### protected fun print_tree(node: N): String

trees :: BinTreeMap :: print_tree

Print the tree starting from `node`.
##### protected fun provide_default_value(key: nullable Object): V

Called by the underling implementation of `[]` to provide a default value when a `key` has no value

core :: Map :: recover_with

Alias for `add_all`
##### protected fun root: nullable N

trees :: TreeMap :: root

The `root` node of the tree (null if tree is empty)
##### protected fun root=(root: nullable N)

trees :: TreeMap :: root=

The `root` node of the tree (null if tree is empty)
##### protected fun rotate_left(node: N)

trees :: BinTreeMap :: rotate_left

Perform left rotation on `node`
##### protected fun rotate_right(node: N)

trees :: BinTreeMap :: rotate_right

Perform right rotation on `node`
##### protected fun search_down(from: N, key: nullable Object): nullable N

trees :: BinTreeMap :: search_down

Search `key` in `from` and its children nodes.
##### fun serialization_hash: Int

core :: Object :: serialization_hash

Hash value use for serialization
##### fun serialize_msgpack(plain: nullable Bool): Bytes

serialization :: Serializable :: serialize_msgpack

Serialize `self` to MessagePack bytes
##### fun serialize_to(serializer: Serializer)

serialization :: Serializable :: serialize_to

Serialize `self` to `serializer`
##### fun serialize_to_json(plain: nullable Bool, pretty: nullable Bool): String

serialization :: Serializable :: serialize_to_json

Serialize `self` to JSON
##### protected fun shift_down(from: N, node: N)

trees :: BinTreeMap :: shift_down

Push down the `node` in tree from a specified `from` index
##### abstract fun show_dot

trees :: TreeMap :: show_dot

Display the tree in a gaphical windows
##### fun sort: Array[E]

trees :: BinTreeMap :: sort

Sort the tree into an array
##### protected fun sort_down(node: N, sorted: Array[E])

trees :: BinTreeMap :: sort_down

Sort the tree from `node` and place results in `sorted`.
##### intern fun sys: Sys

core :: Object :: sys

Return the global sys object, the only instance of the `Sys` class.
##### fun to_json: String

serialization :: Serializable :: to_json

Serialize `self` to plain JSON
##### abstract fun to_jvalue(env: JniEnv): JValue

core :: Object :: to_jvalue

##### fun to_map_comparator(comparator: Comparator): MapComparator[K, V]

A comparator that compares things with their values in self.
##### fun to_pretty_json: String

serialization :: Serializable :: to_pretty_json

Serialize `self` to plain pretty JSON
##### fun to_s: String

core :: Object :: to_s

User readable representation of `self`.
##### protected fun transplant(node: nullable N, other: nullable N)

trees :: BinTreeMap :: transplant

Swap a `node` with the `other` in this Tree
##### abstract fun values: Collection[V]

Return the point of view of self on the values only.
##### fun values_sorted_by_key(comparator: Comparator): Array[V]

Return an array of all values sorted with their keys using `comparator`.

### Ancestors

##### interface Map[K: nullable Object, V: nullable Object]

core :: Map

Maps are associative collections: `key` -> `item`.
##### interface MapRead[K: nullable Object, V: nullable Object]

MapRead are abstract associative collections: `key` -> `item`.
##### interface Object

core :: Object

The root of the class hierarchy.
##### interface Serializable

serialization :: Serializable

Instances of this class can be passed to `Serializer::serialize`

### Parents

##### abstract class TreeMap[K: Comparable, E: nullable Object]

trees :: TreeMap

Abstract tree map structure

### Children

##### class RBTreeMap[K: Comparable, E: nullable Object]

trees :: RBTreeMap

Red-Black Tree Map

## Class definitions

##### trees \$ BinTreeMap
```# Binary Tree Map
#
# Properties:
#  * unique root
#  * node.left.key < node.key
#  * node.right.key > node.key
#  * no duplicates allowed
#
# Operations:
#  * search average O(lg n) worst O(n)
#  * insert average O(lg n) worst O(n)
#  * delete average O(lg n) worst O(n)
#
# Usage:
#
#     var tree = new BinTreeMap[Int, String]
#     tree[1] = "n1"
#     assert tree.min == "n1"
class BinTreeMap[K: Comparable, E]
super TreeMap[K, E]

redef type N: BinTreeNode[K, E]

private var len = 0
private var first_node: nullable BinTreeNode[K, E] = null
private var last_node: nullable BinTreeNode[K, E] = null

# O(n) in worst case, average is O(h) with h: tree height
#
#     var tree = new BinTreeMap[Int, String]
#     assert tree.is_empty
#     tree[1] = "n1"
#     assert not tree.is_empty
redef fun is_empty do return root == null

# O(n) in worst case, average is O(h) with h: tree height
#
#     var tree = new BinTreeMap[Int, String]
#     assert not tree.has_key(1)
#     for i in [4, 2, 1, 5, 3] do tree[i] = "n{i}"
#     assert not tree.has_key(0)
#     assert tree.has_key(2)
#     assert not tree.has_key(6)
redef fun has_key(key) do
if is_empty then return false
var res = search_down(root.as(not null), key)
if res != null then
cache_node = res
return true
end
return false
end

private var cache_node: nullable N = null

# Get the node value associated to `key`
# O(n) in worst case, average is O(h) with h: tree height
#
#     var tree = new BinTreeMap[Int, String]
#     for i in [4, 2, 1, 5, 3] do tree[i] = "n{i}"
#     assert tree.has_key(1)
#     assert tree[1] == "n1"
#     assert tree.has_key(1)
#     assert tree[2] == "n2"
redef fun [](key) do
assert not_empty: not is_empty
if cache_node != null and cache_node.key == key then return cache_node.value
var res = search_down(root.as(not null), key)
assert has_key: res != null
return res.value
end

# Search `key` in `from` and its children nodes.
protected fun search_down(from: N, key: nullable Object): nullable N do
if not key isa Comparable then return null
var cmp = key <=> from.key
if cmp == 0 then return from
if from.left != null and cmp < 0 then
return search_down(from.left.as(not null), key)
else if from.right != null then
return search_down(from.right.as(not null), key)
end
return null
end

# Get the node with the minimum key
# O(n) in worst case, average is O(h) with h: tree height
#
#     var tree = new BinTreeMap[Int, String]
#     for i in [4, 2, 1, 5, 3] do tree[i] = "n{i}"
#     assert tree.min == "n1"
fun min: E do
assert not_empty: root != null
return min_from(root.as(not null)).value
end

# Get the left-most child from `node`.
protected fun min_from(node: N): N do
if node.left == null then return node
return min_from(node.left.as(not null))
end

# Get the node with the maximum key
# O(n) in worst case, average is O(h) with h: tree height
#
#     var tree = new BinTreeMap[Int, String]
#     for i in [4, 2, 1, 5, 3, 6, 7, 8] do tree[i] = "n{i}"
#     assert tree.max == "n8"
fun max: E do
assert not_empty: root != null
return max_from(root.as(not null)).value
end

# Get the right-most child from `node`.
protected fun max_from(node: N): N do
if node.right == null then return node
return max_from(node.right.as(not null))
end

# Insert a new node in tree using `key` and `item`
# O(n) in worst case, average is O(h) with h: tree height
#
#     var tree = new BinTreeMap[Int, String]
#     tree[1] = "n1"
#     assert tree.max == "n1"
#     tree[3] = "n3"
#     assert tree.max == "n3"
redef fun []=(key, item) do
insert_node(new BinTreeNode[K, E](key, item))
end

# Add `node` in the tree.
protected fun insert_node(node: N) do
len += 1
if root == null then
root = node
else
shift_down(root.as(not null), node)
end
if first_node == null then
first_node = node
end
if last_node != null then
last_node.next = node
node.prev = last_node
end
last_node = node
end

# Push down the `node` in tree from a specified `from` index
protected fun shift_down(from, node: N) do
var cmp = node.key <=> from.key
if cmp < 0 then
if from.left == null then
from.left = node
node.parent = from
else
shift_down(from.left.as(not null), node)
end
else if cmp > 0 then
if from.right == null then
from.right = node
node.parent = from
else
shift_down(from.right.as(not null), node)
end
end
end

# Delete node at `key` (also return the deleted node value)
# O(n) in worst case, average is O(h) with h: tree height
#
#     var tree = new BinTreeMap[Int, String]
#     tree[1] = "n1"
#     assert tree.max == "n1"
#     tree[3] = "n3"
#     assert tree.max == "n3"
#     tree.delete(3)
#     assert tree.max == "n1"
fun delete(key: K): nullable E do
assert is_empty: root != null
len -= 1
var node = search_down(root.as(not null), key)
if node == null then return null
if node.left == null then
transplant(node, node.right)
else if node.right == null then
transplant(node, node.left)
else
var min = min_from(node.right.as(not null))
if min.parent != node then
transplant(min, min.right)
min.right = node.right
min.right.parent = min
end
transplant(node, min)
min.left = node.left
min.left.parent = min
end
if first_node == node then
first_node = null
end
if last_node == node then
last_node = node.prev
last_node.next = null
else
node.prev.next = node.next
node.next.prev = node.prev
end
return node.value
end

# Swap a `node` with the `other` in this Tree
# note: Nodes parents are updated, children still untouched
protected fun transplant(node, other: nullable N) do
if node == null then return
if node.parent == null then
root = other
else if node == node.parent.left then
node.parent.left = other
else
node.parent.right = other
end
if other != null then other.parent = node.parent
end

# Perform left rotation on `node`
#
# ~~~raw
#     N             Y
#    / \     >     / \
#   a   Y         N   c
#      / \   <   / \
#     b   c     a   b
# ~~~
#
protected fun rotate_left(node: N) do
var y = node.right
node.right = y.left
if y.left != null then
y.left.parent = node
end
y.parent = node.parent
if node.parent == null then
root = y
else if node == node.parent.left then
node.parent.left = y
else
node.parent.right = y
end
y.left = node
node.parent = y
end

# Perform right rotation on `node`
#
# ~~~raw
#     N             Y
#    / \     >     / \
#   a   Y         N   c
#      / \   <   / \
#     b   c     a   b
# ~~~
#
protected fun rotate_right(node: N) do
var y = node.left
node.left = y.right
if y.right != null then
y.right.parent = node
end
y.parent = node.parent
if node.parent == null then
root = y
else if node == node.parent.right then
node.parent.right = y
else
node.parent.left = y
end
y.right = node
node.parent = y
end

# Sort the tree into an array
# O(n)
#
#     var tree = new BinTreeMap[Int, String]
#     for i in [4, 2, 1, 5, 3] do tree[i] = "n{i}"
#     assert tree.sort == ["n1", "n2", "n3", "n4", "n5"]
fun sort: Array[E] do
var sorted = new Array[E]
if root == null then return sorted
sort_down(root.as(not null), sorted)
return sorted
end

# Sort the tree from `node` and place results in `sorted`.
protected fun sort_down(node: N, sorted: Array[E]) do
if node.left != null then sort_down(node.left.as(not null), sorted)
if node.right != null then sort_down(node.right.as(not null), sorted)
end

redef fun to_s do
var root = self.root
if root == null then return "[]"
return "[{print_tree(root)}]"
end

# Print the tree starting from `node`.
protected fun print_tree(node: N): String do
var s = new FlatBuffer
s.append(node.to_s)
if node.left != null then s.append(print_tree(node.left.as(not null)))
if node.right != null then s.append(print_tree(node.right.as(not null)))
return s.to_s
end

redef fun show_dot do
assert not_empty: root != null
var f = new ProcessWriter("dot", "-Txlib")
f.write "digraph \{\n"
dot_down(root.as(not null), f)
f.write "\}\n"
f.close
end

# Translate the tree in dot format starting from `node`.
protected fun dot_down(node: N, f: ProcessWriter) do
if node.left != null then dot_down(node.left.as(not null), f)
f.write node.to_dot
if node.right != null then dot_down(node.right.as(not null), f)
end

# O(n)
#
#     var tree = new BinTreeMap[Int, String]
#     assert tree.length == 0
#     for i in [4, 2, 1, 5, 3] do tree[i] = "n{i}"
#     assert tree.length == 5
redef fun length do return len

# Nodes are iterated in the same order in which they were added to the tree.
# O(n)
#
#     var tree = new BinTreeMap[Int, String]
#     for i in [4, 2, 1, 5, 3] do tree[i] = "n{i}"
#     var keys = new Array[Int]
#     for k, v in tree do