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 # Manipulation and presentation 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 # Elements of the trees are added with the `add` method that takes a parent and
26 # If the parent is `null`, then the element is considered a root.
29 # var t = new OrderedTree[String]
31 # t.add("root", "child1")
32 # t.add("root", "child2")
33 # t.add("child1", "grand-child")
34 # assert t.length == 4
37 # By default, the elements with a same parent
38 # are visited in the order they are added.
41 # assert t.to_a == ["root", "child1", "grand-child", "child2"]
42 # assert t.write_to_string == """
50 # The `sort_with` method can be used reorder elements
53 # t.add("root", "aaa")
54 # assert t.to_a == ["root", "child1", "grand-child", "child2", "aaa"]
55 # t.sort_with(alpha_comparator)
56 # assert t.to_a == ["root", "aaa", "child1", "grand-child", "child2"]
59 # This class can be used as it to work with generic trees but can also be specialized to provide more specific
60 # behavior or display. It is why the internal attributes are mutable.
61 class OrderedTree[E
: Object]
66 # The roots of the tree (in sequence)
67 var roots
= new Array[E
]
69 # The branches of the trees.
70 # For each element, the ordered array of its direct sub-elements.
71 var sub
= new HashMap[E
, Array[E
]]
73 # The parent of each element.
75 # Roots have `null` as parent.
76 private var parents
= new HashMap[E
, nullable E
]
78 redef fun length
do return parents
.length
80 redef fun has
(e
) do return parents
.has_key
(e
)
82 # The parent of the element `e`
84 # Roots have `null` as parent.
87 # var tree = new OrderedTree[Int]
89 # assert tree.parent(2) == 1
90 # assert tree.parent(1) == null
92 fun parent
(e
: E
): nullable E
do return parents
[e
]
94 # Add a new element `e` in the tree.
96 # `p` is the parent of `e`.
97 # If `p` is null, then `e` is a root element.
99 # If `e` is already in the tree, it is detached from its old
100 # parent and attached to the new parent `p`.
101 fun add
(p
: nullable E
, e
: E
)
108 if not has
(p
) then add
(null, p
)
109 if sub
.has_key
(p
) then
117 # Append all nodes `es` as children of `p`.
118 fun add_all
(p
: nullable E
, es
: Collection[E
])
120 for e
in es
do add
(p
, e
)
123 # Temporary remove `e`.
125 # Children of `e` are left untouched in the tree.
126 # This make the tree inconstant until `e` is added back.
127 private fun detach
(e
: E
)
129 var old_parent
= parents
.get_or_null
(e
)
130 if old_parent
!= null then
131 var subs
= sub
[old_parent
]
133 if subs
.is_empty
then
134 # remove the sub when all children are detached
135 # so that `==` and `hash` are sane
136 # Otherwise an empty array will be considered
137 # differently than no array.
138 sub
.keys
.remove
(old_parent
)
140 else if roots
.has
(e
) then
145 # print the full tree on `o`
146 # Write a ASCII-style tree and use the `display` method to label elements
147 redef fun write_to
(stream
: Writer)
150 write_line
(stream
, r
, "")
151 sub_write_to
(stream
, r
, "")
155 private fun sub_write_to
(o
: Writer, e
: E
, prefix
: String)
157 if not sub
.has_key
(e
) then return
159 if subs
.is_empty
then return
163 write_line
(o
, e2
, prefix
+"|--")
164 sub_write_to
(o
, e2
, prefix
+"| ")
166 write_line
(o
, e2
, prefix
+"`--")
167 sub_write_to
(o
, e2
, prefix
+" ")
172 # Write the full line for the element `e` in `o`.
177 # o.write "{prefix}{display(e)}\n"
180 # Usually, you should redefine `display` to change the display of an element.
181 protected fun write_line
(o
: Writer, e
: E
, prefix
: String)
183 o
.write
"{prefix}{display(e)}\n"
186 # Sort roots and other elements using a comparator method
187 # This method basically sorts roots then each group of children
188 fun sort_with
(comparator
: Comparator)
190 comparator
.sort
(roots
)
191 for a
in sub
.values
do
196 # How to display a specific element of the tree
197 # By defaut, uses `to_s`
199 # Subclasses should redefine this method to provide a specific output
200 fun display
(e
: E
): String do return e
.to_s
202 # Get an array of the contained elements
205 # var tree = new OrderedTree[Int]
206 # tree.add_all(null, [1, 2])
207 # tree.add_all(1, [11, 12])
208 # tree.add_all(11, [111, 112])
209 # tree.add_all(12, [121, 122])
210 # tree.add_all(2, [21, 22])
211 # assert tree.to_a == [1, 11, 111, 112, 12, 121, 122, 2, 21, 22]
212 redef fun to_a
: Array[E
] do
213 var res
= new Array[E
]
214 for r
in roots
do sub_to_a
(r
, res
)
218 private fun sub_to_a
(e
: E
, res
: Array[E
]) do
220 if sub
.has_key
(e
) then for e2
in sub
[e
] do sub_to_a
(e2
, res
)
223 # var tree = new OrderedTree[Int]
224 # assert tree.is_empty
226 # assert not tree.is_empty
227 redef fun is_empty
: Bool do return roots
.is_empty
229 # var tree = new OrderedTree[Int]
232 # assert tree.first == 1
233 redef fun first
do return roots
.first
235 # var tree = new OrderedTree[Int]
236 # tree.add_all(null, [1, 2])
237 # tree.add_all(1, [11, 12])
238 # tree.add_all(11, [111, 112])
239 # tree.add_all(12, [121, 122])
240 # tree.add_all(2, [21, 22])
241 # var order = [1, 11, 111, 112, 12, 121, 122, 2, 21, 22]
242 # assert tree.iterator.to_a == order
243 redef fun iterator
do return new OrderedTreeIterator[E
](self)
245 # Two trees are equal if they have the same nodes in the same order
248 # var t1 = new OrderedTree[Int]
249 # t1.add_all(null, [1, 2])
250 # t1.add_all(1, [11, 12])
252 # var t2 = new OrderedTree[Int]
253 # t2.add_all(null, [1, 2])
257 # t2.add_all(1, [11, 12])
263 if not other
isa OrderedTree[Object] then return false
264 return roots
== other
.roots
and sub
== other
.sub
269 return roots
.hash
+ sub
.hash
272 # Shallow clone of the tree.
275 # var t = new OrderedTree[Int]
276 # t.add_all(null, [1, 2])
277 # t.add_all(1, [11, 12])
279 # assert t.clone == t
283 var res
= new OrderedTree[E
]
284 res
.add_all
(null, roots
)
292 # An Iterator over an OrderedTree
293 private class OrderedTreeIterator[E
: Object]
296 var tree
: OrderedTree[E
]
298 var iterators
= new Array[Iterator[E
]]
301 if not tree
.is_empty
then
302 iterators
.add tree
.roots
.iterator
306 redef fun is_ok
do return not iterators
.is_empty
310 return iterators
.last
.item
315 if tree
.sub
.has_key
(item
) then
316 iterators
.add tree
.sub
[item
].iterator
319 while is_ok
and not iterators
.last
.is_ok
do
321 if is_ok
and iterators
.last
.is_ok
then
328 redef fun iterator
do return new OrderedTreeIterator[E
](tree
)