trees :: BinTreeMap
Properties:
Operations:
Usage:
var tree = new BinTreeMap[Int, String]
tree[1] = "n1"
assert tree.min == "n1"
trees :: BinTreeMap :: defaultinit
trees :: BinTreeMap :: dot_down
Translate the tree in dot format starting fromnode
.
trees :: BinTreeMap :: print_tree
Print the tree starting fromnode
.
trees :: BinTreeMap :: rotate_right
Perform right rotation onnode
trees :: BinTreeMap :: search_down
Searchkey
in from
and its children nodes.
trees :: BinTreeMap :: shift_down
Push down thenode
in tree from a specified from
index
trees :: BinTreeMap :: transplant
Swap anode
with the other
in this Tree
trees $ BinTreeMap :: N
Type of nodes used in this tree implementationtrees $ BinTreeMap :: SELF
Type of this instance, automatically specialized in every classtrees $ BinTreeMap :: is_empty
O(n) in worst case, average is O(h) with h: tree heighttrees $ BinTreeMap :: iterator
Nodes are iterated in the same order in which they were added to the tree.serialization :: Serializable :: accept_json_serializer
Refinable service to customize the serialization of this class to JSONserialization :: Serializable :: accept_msgpack_attribute_counter
Hook to customize the behavior of theAttributeCounter
serialization :: Serializable :: accept_msgpack_serializer
Hook to customize the serialization of this class to MessagePackserialization :: Serializable :: add_to_bundle
Called by[]=
to dynamically choose the appropriate method according
core :: Object :: class_factory
Implementation used byget_class
to create the specific class.
serialization :: Serializable :: core_serialize_to
Actual serialization ofself
to serializer
trees :: BinTreeMap :: defaultinit
core :: Object :: defaultinit
trees :: TreeMap :: defaultinit
core :: MapRead :: defaultinit
core :: Map :: defaultinit
trees :: BinTreeMap :: dot_down
Translate the tree in dot format starting fromnode
.
core :: MapRead :: filter_keys
Return all elements ofkeys
that have a value.
serialization :: Serializable :: from_deserializer
Create an instance of this class from thedeserializer
core :: MapRead :: get_or_default
Get the item atkey
or return default
if not in map
core :: MapRead :: get_or_null
Get the item atkey
or null if key
is not in the map.
core :: Object :: is_same_instance
Return true ifself
and other
are the same instance (i.e. same identity).
core :: Object :: is_same_serialized
Isself
the same as other
in a serialization context?
core :: Object :: is_same_type
Return true ifself
and other
have the same dynamic type.
core :: MapRead :: keys_sorted_by_values
Return an array of all keys sorted with their values usingcomparator
.
core :: MapRead :: lookup_all_values
Search all the values inpe.greaters
.
core :: MapRead :: lookup_values
Combine the values inpe.greaters
from the most smaller elements that have a value.
serialization :: Serializable :: msgpack_extra_array_items
Hook to request a larger than usual metadata arraycore :: Object :: output_class_name
Display class name on stdout (debug only).trees :: BinTreeMap :: print_tree
Print the tree starting fromnode
.
core :: MapRead :: provide_default_value
Called by the underling implementation of[]
to provide a default value when a key
has no value
trees :: BinTreeMap :: rotate_right
Perform right rotation onnode
trees :: BinTreeMap :: search_down
Searchkey
in from
and its children nodes.
serialization :: Serializable :: serialize_msgpack
Serializeself
to MessagePack bytes
serialization :: Serializable :: serialize_to
Serializeself
to serializer
serialization :: Serializable :: serialize_to_json
Serializeself
to JSON
trees :: BinTreeMap :: shift_down
Push down thenode
in tree from a specified from
index
core :: MapRead :: to_map_comparator
A comparator that compares things with their values in self.serialization :: Serializable :: to_pretty_json
Serializeself
to plain pretty JSON
trees :: BinTreeMap :: transplant
Swap anode
with the other
in this Tree
core :: MapRead :: values_sorted_by_key
Return an array of all values sorted with their keys usingcomparator
.
# 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)
sorted.add(node.value)
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
# keys.add k
# end
# assert keys == [4, 2, 1, 5, 3]
redef fun iterator do return new BinTreeMapIterator[K, E](self)
end
lib/trees/bintree.nit:25,1--377,3