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 # Node used in Tree implementation
  40 # nodes are used to store values
  41 # * `E`: type of value
  42 class TreeNode[K: Comparable, E]
  43
  44         # TreeNode type
  45         type SELF: TreeNode[K, E]
  46
  47         # `key` for this node
  48         var key: K
  49
  50         # `value` stored in the node
  51         var value: E
  52
  53         # Direct parent of this node (null if the node is root)
  54         var parent: nullable SELF = null is writable
  55
  56         redef fun to_s do return "\{{value or else ""}\}"
  57
  58         # Return dot representation of this node
  59         # Used for debugging by `AbstractTree::show_dot`
  60         fun to_dot: String do
  61                 var res = new FlatBuffer
  62                 res.append "\"{self}\";\n"
  63                 if parent != null then res.append "\"{parent.as(not null)}\" -> \"{self}\"[dir=back];\n"
  64                 return res.to_s
  65         end
  66 end
  67