lib: introduce abstract_tree

Signed-off-by: Alexandre Terrasa <alexandre@moz-code.org>

diff --git a/lib/trees/abstract_tree.nit b/lib/trees/abstract_tree.nit
new file mode 100644 (file)
index 0000000..63ac67a
--- /dev/null
+++ b/lib/trees/abstract_tree.nit
@@ -0,0 +1,67 @@
+# This file is part of NIT ( http://www.nitlanguage.org ).
+#
+# Licensed under the Apache License, Version 2.0 (the "License");
+# you may not use this file except in compliance with the License.
+# You may obtain a copy of the License at
+#
+#     http://www.apache.org/licenses/LICENSE-2.0
+#
+# Unless required by applicable law or agreed to in writing, software
+# distributed under the License is distributed on an "AS IS" BASIS,
+# WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+# See the License for the specific language governing permissions and
+# limitations under the License.
+
+# Introduce tree structures abstraction
+# Trees are a widely used abstract data type (ADT) or data structure
+# implementing this ADT that simulates a hierarchical tree structure,
+# with a root value and subtrees of children, represented as a set of linked nodes.
+module abstract_tree
+
+# Abstract tree map structure
+# * `K`: tree node key
+# * `E`: tree node value
+abstract class TreeMap[K: Comparable, E]
+       super Map[K, E]
+
+       # Type of nodes used in this tree implementation
+       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
+
+       # Display the tree in a gaphical windows
+       # Graphviz with a working -Txlib is expected
+       # Used for debugging
+       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]
+
+       # TreeNode type
+       type SELF: 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
+
+       redef fun to_s do return "\{{value}\}"
+
+       # Return dot representation of this node
+       # Used for debugging by `AbstractTree::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
+