lib/ordered_tree.nit

   1 # This file is part of NIT ( http://www.nitlanguage.org ).
   2 #
   3 # Copyright 2012 Jean Privat <jean@pryen.org>
   4 #
   5 # Licensed under the Apache License, Version 2.0 (the "License");
   6 # you may not use this file except in compliance with the License.
   7 # You may obtain a copy of the License at
   8 #
   9 #     http://www.apache.org/licenses/LICENSE-2.0
  10 #
  11 # Unless required by applicable law or agreed to in writing, software
  12 # distributed under the License is distributed on an "AS IS" BASIS,
  13 # WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
  14 # See the License for the specific language governing permissions and
  15 # limitations under the License.
  16
  17 # management and display of ordered trees
  18 module ordered_tree
  19
  20 # Generic structure to manage and display an ordered tree
  21 #
  22 # Ordered tree are tree where the elements of a same parent are in a specific order
  23 #
  24 # The class can be used as it to work with generic tree.
  25 # The class can also be specialized to provide more specific behavior.
  26 class OrderedTree[E: Object]
  27         # Sequence
  28         var roots = new Array[E]
  29         var sub = new HashMap[E, Array[E]]
  30
  31         # Add a new element `e` in the tree
  32         # `p` is the parent of `e`.
  33         # if `p` is null, then `e` is a root element.
  34         #
  35         # By defauld, the elements with a same parent
  36         # are displayed in the order they are added.
  37         #
  38         # The `sort_with` method can be used reorder elements
  39         fun add(p: nullable E, e: E)
  40         do
  41                 if p == null then
  42                         roots.add(e)
  43                 else if sub.has_key(p) then
  44                         sub[p].add(e)
  45                 else
  46                         sub[p] = [e]
  47                 end
  48         end
  49
  50         # print the full tree on `o`
  51         # Write a ASCII-style tree and use the `display` method to label elements
  52         fun pretty(o: OStream)
  53         do
  54                 var last = roots.last
  55                 for r in roots do
  56                         o.write display(r)
  57                         o.write "\n"
  58                         sub_pretty(o, r, "")
  59                 end
  60         end
  61
  62         private fun sub_pretty(o: OStream, e: E, prefix: String)
  63         do
  64                 if not sub.has_key(e) then return
  65                 var subs = sub[e]
  66                 var last = subs.last
  67                 for e2 in subs do
  68                         if e2 != last then
  69                                 o.write "{prefix}|--{display(e2)}\n"
  70                                 sub_pretty(o, e2, prefix+"|  ")
  71                         else
  72                                 o.write "{prefix}`--{display(e2)}\n"
  73                                 sub_pretty(o, e2, prefix+"   ")
  74                         end
  75                 end
  76         end
  77
  78         # Sort roots and other elements using a comparator method
  79         # This method basically sorts roots then each group of children
  80         fun sort_with(comparator: AbstractSorter[E])
  81         do
  82                 comparator.sort(roots)
  83                 for a in sub.values do
  84                         comparator.sort(a)
  85                 end
  86         end
  87
  88         # How to display a specific element of the tree
  89         # By defaut, uses `to_s`
  90         #
  91         # Subclasses should redefine this method to provide a specific output
  92         fun display(e: E): String do return e.to_s
  93 end