1 # This file is part of NIT ( http://www.nitlanguage.org ).
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
7 # http://www.apache.org/licenses/LICENSE-2.0
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.
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.
21 # Abstract tree map structure
22 # * `K`: tree node key
23 # * `E`: tree node value
24 abstract class TreeMap[K
: Comparable, E
]
27 # Type of nodes used in this tree implementation
28 protected type N
: TreeNode[K
, E
]
30 # The `root` node of the tree (null if tree is empty)
31 protected var root
: nullable N
= null is protected writable
33 # Display the tree in a gaphical windows
34 # Graphviz with a working -Txlib is expected
36 fun show_dot
is abstract
39 # Node used in Tree implementation
40 # nodes are used to store values
41 # * `E`: type of value
42 class TreeNode[K
: Comparable, E
]
45 type N
: TreeNode[K
, E
]
50 # `value` stored in the node
53 # Direct parent of this node (null if the node is root)
54 var parent
: nullable N
= null is writable
56 redef fun to_s
do return "\{{value or else ""}\}"
58 # Return dot representation of this node
59 # Used for debugging by `AbstractTree::show_dot`
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"