lib/trees/abstract_tree.nit

   1 # This file is part of NIT ( http://www.nitlanguage.org ).
   2 #
   3 # Licensed under the Apache License, Version 2.0 (the "License");
   4 # you may not use this file except in compliance with the License.
   5 # You may obtain a copy of the License at
   6 #
   7 #     http://www.apache.org/licenses/LICENSE-2.0
   8 #
   9 # Unless required by applicable law or agreed to in writing, software
  10 # distributed under the License is distributed on an "AS IS" BASIS,
  11 # WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
  12 # See the License for the specific language governing permissions and
  13 # limitations under the License.
  14
  15 # Introduce tree structures abstraction
  16 # Trees are a widely used abstract data type (ADT) or data structure
  17 # implementing this ADT that simulates a hierarchical tree structure,
  18 # with a root value and subtrees of children, represented as a set of linked nodes.
  19 module abstract_tree
  20
  21 # Abstract tree map structure
  22 # * `K`: tree node key
  23 # * `E`: tree node value
  24 abstract class TreeMap[K: Comparable, E]
  25         super Map[K, E]
  26
  27         # Type of nodes used in this tree implementation
  28         protected type N: TreeNode[K, E]
  29
  30         # The `root` node of the tree (null if tree is empty)
  31         protected var root: nullable N = null is protected writable
  32
  33         # Display the tree in a gaphical windows
  34         # Graphviz with a working -Txlib is expected
  35         # Used for debugging
  36         fun show_dot is abstract
  37 end
  38
  39 # Abstract node structure used in `Tree` implementation
  40 #
  41 # Nodes are defined recursively each node (except the root one) pointing to a parent.
  42 # Nodes can be used to store data with the `TreeNode::value` attribute.
  43 #
  44 # Formal parameters:
  45 # * `K`: key type (a `Comparable` one so nodes can be sorted by their keys)
  46 # * `E`: value type (to store your data)
  47 abstract class TreeNode[K: Comparable, E]
  48         super Comparable
  49
  50         # TreeNode type
  51         type N: TreeNode[K, E]
  52
  53         # `key` for this node
  54         var key: K
  55
  56         # `value` stored in the node
  57         var value: E
  58
  59         # Direct parent of this node (`null` if the node is root)
  60         #
  61         # See `Tree::root`.
  62         var parent: nullable N = null is writable
  63
  64         # Depth in tree (length of the path from `self` to `root`)
  65         fun depth: Int do
  66                 var node = parent
  67                 var i = 0
  68                 while node != null do
  69                         node = node.parent
  70                         i += 1
  71                 end
  72                 return i
  73         end
  74
  75         redef fun to_s do return "\{{value or else ""}\}"
  76
  77         # Return dot representation of this node
  78         #
  79         # See `Tree::show_dot`.
  80         fun to_dot: String do
  81                 var res = new FlatBuffer
  82                 res.append "\"{self}\";\n"
  83                 if parent != null then res.append "\"{parent.as(not null)}\" -> \"{self}\"[dir=back];\n"
  84                 return res.to_s
  85         end
  86
  87         redef type OTHER: N
  88
  89         # Nodes equality is done on `value` equality
  90         #
  91         # Redefine this method to change the default behavior.
  92         redef fun ==(o) do
  93                 if not o isa N then return false
  94                 return self.value == o.value
  95         end
  96
  97         # Nodes ordering is based on the `key`
  98         redef fun <(o) do return self.key < o.key
  99 end