end
protected fun search_down(from: N, key: K): nullable N do
- if key == from.key then return from
- if from.left != null and key < from.key then
+ 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)
# Push down the `node` in tree from a specified `from` index
protected fun shift_down(from, node: N) do
- if node.key < from.key then
+ 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 node.key > from.key then
+ else if cmp > 0 then
if from.right == null then
from.right = node
node.parent = from
# 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
# 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
private var prev: nullable BinTreeNode[K, E]
private var next: nullable BinTreeNode[K, E]
- redef type SELF: BinTreeNode[K, E]
+ redef type N: BinTreeNode[K, E]
init(key: K, item: E) do
super(key, item)
end
- private var left_node: nullable SELF = null
+ private var left_node: nullable N = null
# `left` tree node child (null if node has no left child)
- fun left: nullable SELF do return left_node
+ fun left: nullable N do return left_node
# set `left` child for this node (or null if left no child)
# ENSURE: node.key < key (only if node != null)
- fun left=(node: nullable SELF) do
- assert node != null implies node.key < key
+ fun left=(node: nullable N) do
+ #assert node != null implies node.key < key
left_node = node
end
- private var right_node: nullable SELF = null
+ private var right_node: nullable N = null
# `right` tree node child (null if node has no right child)
- fun right: nullable SELF do return right_node
+ fun right: nullable N do return right_node
# set `right` child for this node (or null if right no child)
# ENSURE: node.key < key (only if node != null)
- fun right=(node: nullable SELF) do
- if node != null then
- assert node.key > key
- end
+ fun right=(node: nullable N) do
+ #assert node != null implies node.key > key
right_node = node
end
# `parent` of the `parent` of this node (null if root)
- fun grandparent: nullable SELF do
+ fun grandparent: nullable N do
if parent == null then
return null
else
# Other child of the `grandparent`
# `left` or `right` depends on the position of the current node against its parent
- fun uncle: nullable SELF do
+ fun uncle: nullable N do
var g = grandparent
if g == null then
return null
# Other child of the parent
# `left` or `right` depends on the position of the current node against its parent
- fun sibling: nullable SELF do
+ fun sibling: nullable N do
if parent == null then
return null
else if self == parent.left then
end
end
- redef fun to_s do return "\{{key}: {value}\}"
+ redef fun to_s do return "\{{key}: {value or else ""}\}"
end
private class BinTreeMapIterator[K: Comparable, E]