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 # Abstract node structure used in `Tree` implementation
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.
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
]
51 type N
: TreeNode[K
, E
]
56 # `value` stored in the node
59 # Direct parent of this node (`null` if the node is root)
62 var parent
: nullable N
= null is writable
64 # Depth in tree (length of the path from `self` to `root`)
75 redef fun to_s
do return "\{{value or else ""}\}"
77 # Return dot representation of this node
79 # See `Tree::show_dot`.
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"
89 # Nodes equality is done on `value` equality
91 # Redefine this method to change the default behavior.
93 if not o
isa N
then return false
94 return self.value
== o
.value
97 # Nodes ordering is based on the `key`
98 redef fun <(o
) do return self.key
< o
.key