protected type N: TreeNode[K, E]
# The `root` node of the tree (null if tree is empty)
- protected var root: nullable N protected writable = null
+ protected var root: nullable N = null is protected writable
# Display the tree in a gaphical windows
# Graphviz with a working -Txlib is expected
fun show_dot is abstract
end
-# Node used in Tree implementation
-# nodes are used to store values
-# * `E`: type of value
-class TreeNode[K: Comparable, E]
+# Abstract node structure used in `Tree` implementation
+#
+# Nodes are defined recursively each node (except the root one) pointing to a parent.
+# Nodes can be used to store data with the `TreeNode::value` attribute.
+#
+# Formal parameters:
+# * `K`: key type (a `Comparable` one so nodes can be sorted by their keys)
+# * `E`: value type (to store your data)
+abstract class TreeNode[K: Comparable, E]
+ super Comparable
# TreeNode type
- type SELF: TreeNode[K, E]
+ type N: TreeNode[K, E]
# `key` for this node
var key: K
# `value` stored in the node
var value: E
- # Direct parent of this node (null if the node is root)
- var parent: nullable SELF writable = null
+ # Direct parent of this node (`null` if the node is root)
+ #
+ # See `Tree::root`.
+ var parent: nullable N = null is writable
+
+ # Depth in tree (length of the path from `self` to `root`)
+ fun depth: Int do
+ var node = parent
+ var i = 0
+ while node != null do
+ node = node.parent
+ i += 1
+ end
+ return i
+ end
redef fun to_s do return "\{{value or else ""}\}"
# Return dot representation of this node
- # Used for debugging by `AbstractTree::show_dot`
+ #
+ # See `Tree::show_dot`.
fun to_dot: String do
var res = new FlatBuffer
res.append "\"{self}\";\n"
if parent != null then res.append "\"{parent.as(not null)}\" -> \"{self}\"[dir=back];\n"
return res.to_s
end
-end
+ redef type OTHER: N
+
+ # Nodes equality is done on `value` equality
+ #
+ # Redefine this method to change the default behavior.
+ redef fun ==(o) do
+ if not o isa N then return false
+ return self.value == o.value
+ end
+
+ # Nodes ordering is based on the `key`
+ redef fun <(o) do return self.key < o.key
+end