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         super Streamable
  28
  29         # Sequence
  30         var roots = new Array[E]
  31         var sub = new HashMap[E, Array[E]]
  32
  33         # Add a new element `e` in the tree
  34         # `p` is the parent of `e`.
  35         # if `p` is null, then `e` is a root element.
  36         #
  37         # By defauld, the elements with a same parent
  38         # are displayed in the order they are added.
  39         #
  40         # The `sort_with` method can be used reorder elements
  41         fun add(p: nullable E, e: E)
  42         do
  43                 if p == null then
  44                         roots.add(e)
  45                 else if sub.has_key(p) then
  46                         sub[p].add(e)
  47                 else
  48                         sub[p] = [e]
  49                 end
  50         end
  51
  52         # print the full tree on `o`
  53         # Write a ASCII-style tree and use the `display` method to label elements
  54         redef fun write_to(stream: OStream)
  55         do
  56                 var last = roots.last
  57                 for r in roots do
  58                         stream.write display(r)
  59                         stream.write "\n"
  60                         sub_write_to(stream, r, "")
  61                 end
  62         end
  63
  64         private fun sub_write_to(o: OStream, e: E, prefix: String)
  65         do
  66                 if not sub.has_key(e) then return
  67                 var subs = sub[e]
  68                 var last = subs.last
  69                 for e2 in subs do
  70                         if e2 != last then
  71                                 o.write "{prefix}|--{display(e2)}\n"
  72                                 sub_write_to(o, e2, prefix+"|  ")
  73                         else
  74                                 o.write "{prefix}`--{display(e2)}\n"
  75                                 sub_write_to(o, e2, prefix+"   ")
  76                         end
  77                 end
  78         end
  79
  80         # Sort roots and other elements using a comparator method
  81         # This method basically sorts roots then each group of children
  82         fun sort_with(comparator: AbstractSorter[E])
  83         do
  84                 comparator.sort(roots)
  85                 for a in sub.values do
  86                         comparator.sort(a)
  87                 end
  88         end
  89
  90         # How to display a specific element of the tree
  91         # By defaut, uses `to_s`
  92         #
  93         # Subclasses should redefine this method to provide a specific output
  94         fun display(e: E): String do return e.to_s
  95 end