1 # This file is part of NIT ( http://www.nitlanguage.org ).
3 # Copyright 2012 Jean Privat <jean@pryen.org>
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
9 # http://www.apache.org/licenses/LICENSE-2.0
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.
17 # management and display of ordered trees
20 # Generic structure to manage and display an ordered tree
22 # Ordered tree are tree where the elements of a same parent are in a specific order
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]
31 var roots
= new Array[E
]
32 var sub
= new HashMap[E
, Array[E
]]
34 # Add a new element `e` in the tree
35 # `p` is the parent of `e`.
36 # if `p` is null, then `e` is a root element.
38 # By defauld, the elements with a same parent
39 # are displayed in the order they are added.
41 # The `sort_with` method can be used reorder elements
42 fun add
(p
: nullable E
, e
: E
)
46 else if sub
.has_key
(p
) then
53 # print the full tree on `o`
54 # Write a ASCII-style tree and use the `display` method to label elements
55 redef fun write_to
(stream
: OStream)
59 stream
.write display
(r
)
61 sub_write_to
(stream
, r
, "")
65 private fun sub_write_to
(o
: OStream, e
: E
, prefix
: String)
67 if not sub
.has_key
(e
) then return
72 o
.write
"{prefix}|--{display(e2)}\n"
73 sub_write_to
(o
, e2
, prefix
+"| ")
75 o
.write
"{prefix}`--{display(e2)}\n"
76 sub_write_to
(o
, e2
, prefix
+" ")
81 # Sort roots and other elements using a comparator method
82 # This method basically sorts roots then each group of children
83 fun sort_with
(comparator
: Comparator[E
])
85 comparator
.sort
(roots
)
86 for a
in sub
.values
do
91 # How to display a specific element of the tree
92 # By defaut, uses `to_s`
94 # Subclasses should redefine this method to provide a specific output
95 fun display
(e
: E
): String do return e
.to_s
97 # Get an array of the contained elements
100 # var tree = new OrderedTree[Int]
111 # assert tree.to_a == [1, 11, 111, 112, 12, 121, 122, 2, 21, 22]
112 redef fun to_a
: Array[E
] do
113 var res
= new Array[E
]
114 for r
in roots
do sub_to_a
(r
, res
)
118 private fun sub_to_a
(e
: E
, res
: Array[E
]) do
120 if sub
.has_key
(e
) then for e2
in sub
[e
] do sub_to_a
(e2
, res
)
123 # var tree = new OrderedTree[Int]
124 # assert tree.is_empty
126 # assert not tree.is_empty
127 redef fun is_empty
: Bool do return roots
.is_empty
129 # var tree = new OrderedTree[Int]
132 # assert tree.first == 1
133 redef fun first
do return roots
.first
135 # var tree = new OrderedTree[Int]
146 # var order = [1, 11, 111, 112, 12, 121, 122, 2, 21, 22]
147 # var res = new Array[Int]
148 # for i in tree do res.add(i)
149 # assert res == order
150 redef fun iterator
do return new OrderedTreeIterator[E
](self)
153 # An Iterator over an OrderedTree
154 private class OrderedTreeIterator[E
: Object]
157 var tree
: OrderedTree[E
]
159 var iterators
= new Array[Iterator[E
]]
161 init(tree
: OrderedTree[E
]) do
164 if not tree
.is_empty
then
165 iterators
.add tree
.roots
.iterator
169 redef fun is_ok
do return not iterators
.is_empty
173 return iterators
.last
.item
178 if tree
.sub
.has_key
(item
) then
179 iterators
.add tree
.sub
[item
].iterator
182 while is_ok
and not iterators
.last
.is_ok
do
184 if is_ok
and iterators
.last
.is_ok
then
191 redef fun iterator
do return new OrderedTreeIterator[E
](tree
)