doc: Commands tests use `test_frontend`

[nit.git] / lib / trees / abstract_tree.nit

diff --git a/lib/trees/abstract_tree.nit b/lib/trees/abstract_tree.nit
index 0b79490..dccde3a 100644 (file)
--- a/lib/trees/abstract_tree.nit
+++ b/lib/trees/abstract_tree.nit
@@ -28,7 +28,7 @@ abstract class TreeMap[K: Comparable, E]
        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
@@ -36,13 +36,19 @@ abstract class TreeMap[K: Comparable, E]
        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
@@ -50,18 +56,44 @@ class TreeNode[K: Comparable, E]
        # `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