X-Git-Url: http://nitlanguage.org

diff --git a/lib/ordered_tree.nit b/lib/ordered_tree.nit
index 91f8e63..7216474 100644
--- a/lib/ordered_tree.nit
+++ b/lib/ordered_tree.nit
@@ -14,31 +14,65 @@
 # See the License for the specific language governing permissions and
 # limitations under the License.
 
-# management and display of ordered trees
+# Manipulation and presentation of ordered trees.
 module ordered_tree
 
 # Generic structure to manage and display an ordered tree
 #
 # Ordered tree are tree where the elements of a same parent are in a specific order
 #
-# The class can be used as it to work with generic tree.
-# The class can also be specialized to provide more specific behavior.
+# Elements of the trees are added with the `add` method that takes a parent and
+# a sub-element.
+# If the parent is `null`, then the element is considered a root.
+#
+# ~~~~
+# var t = new OrderedTree[String]
+# t.add(null, "root")
+# t.add("root", "child1")
+# t.add("root", "child2")
+# t.add("child1", "grand-child")
+# assert t.length == 4
+# ~~~~
+#
+# By default, the elements with a same parent
+# are visited in the order they are added.
+#
+# ~~~
+# assert t.to_a == ["root", "child1", "grand-child", "child2"]
+# assert t.write_to_string == """
+# root
+# |--child1
+# |  `--grand-child
+# `--child2
+# """
+# ~~~
+#
+# The `sort_with` method can be used reorder elements
+#
+# ~~~
+# t.add("root", "aaa")
+# assert t.to_a == ["root", "child1", "grand-child", "child2", "aaa"]
+# t.sort_with(alpha_comparator)
+# assert t.to_a == ["root", "aaa", "child1", "grand-child", "child2"]
+# ~~~
+#
+# This class can be used as it to work with generic trees but can also be specialized to provide more specific
+# behavior or display. It is why the internal attributes are mutable.
 class OrderedTree[E: Object]
-	super Streamable
+	super Writable
 	super Collection[E]
+	super Cloneable
 
-	# Sequence
+	# The roots of the tree (in sequence)
 	var roots = new Array[E]
+
+	# The branches of the trees.
+	# For each element, the ordered array of its direct sub-elements.
 	var sub = new HashMap[E, Array[E]]
 
-	# Add a new element `e` in the tree
+	# Add a new element `e` in the tree.
 	# `p` is the parent of `e`.
 	# if `p` is null, then `e` is a root element.
-	#
-	# By defauld, the elements with a same parent 
-	# are displayed in the order they are added.
-	#
-	# The `sort_with` method can be used reorder elements
 	fun add(p: nullable E, e: E)
 	do
 		if p == null then
@@ -50,11 +84,16 @@ class OrderedTree[E: Object]
 		end
 	end
 
+	# Append all nodes `es` as children of `p`.
+	fun add_all(p: nullable E, es: Collection[E])
+	do
+		for e in es do add(p, e)
+	end
+
 	# print the full tree on `o`
 	# Write a ASCII-style tree and use the `display` method to label elements
-	redef fun write_to(stream: OStream)
+	redef fun write_to(stream: Writer)
 	do
-		var last = roots.last
 		for r in roots do
 			stream.write display(r)
 			stream.write "\n"
@@ -62,7 +101,7 @@ class OrderedTree[E: Object]
 		end
 	end
 
-	private fun sub_write_to(o: OStream, e: E, prefix: String)
+	private fun sub_write_to(o: Writer, e: E, prefix: String)
 	do
 		if not sub.has_key(e) then return
 		var subs = sub[e]
@@ -98,16 +137,11 @@ class OrderedTree[E: Object]
 	# Order is preserved
 	#
 	#     var tree = new OrderedTree[Int]
-	#     tree.add(null, 1)
-	#     tree.add(1, 11)
-	#     tree.add(11, 111)
-	#     tree.add(11, 112)
-	#     tree.add(1, 12)
-	#     tree.add(12, 121)
-	#     tree.add(12, 122)
-	#     tree.add(null, 2)
-	#     tree.add(2, 21)
-	#     tree.add(2, 22)
+	#     tree.add_all(null, [1, 2])
+	#     tree.add_all(1, [11, 12])
+	#     tree.add_all(11, [111, 112])
+	#     tree.add_all(12, [121, 122])
+	#     tree.add_all(2, [21, 22])
 	#     assert tree.to_a == [1, 11, 111, 112, 12, 121, 122, 2, 21, 22]
 	redef fun to_a: Array[E] do
 		var res = new Array[E]
@@ -133,21 +167,60 @@ class OrderedTree[E: Object]
 	redef fun first do return roots.first
 
 	#     var tree = new OrderedTree[Int]
-	#     tree.add(null, 1)
-	#     tree.add(1, 11)
-	#     tree.add(11, 111)
-	#     tree.add(11, 112)
-	#     tree.add(1, 12)
-	#     tree.add(12, 121)
-	#     tree.add(12, 122)
-	#     tree.add(null, 2)
-	#     tree.add(2, 21)
-	#     tree.add(2, 22)
+	#     tree.add_all(null, [1, 2])
+	#     tree.add_all(1, [11, 12])
+	#     tree.add_all(11, [111, 112])
+	#     tree.add_all(12, [121, 122])
+	#     tree.add_all(2, [21, 22])
 	#     var order = [1, 11, 111, 112, 12, 121, 122, 2, 21, 22]
-	#     var res = new Array[Int]
-	#     for i in tree do res.add(i)
-	#     assert res == order
+	#     assert tree.iterator.to_a == order
 	redef fun iterator do return new OrderedTreeIterator[E](self)
+
+	# Two trees are equal if they have the same nodes in the same order
+	#
+	# ~~~
+	# var t1 = new OrderedTree[Int]
+	# t1.add_all(null, [1, 2])
+	# t1.add_all(1, [11, 12])
+	#
+	# var t2 = new OrderedTree[Int]
+	# t2.add_all(null, [1, 2])
+	#
+	# assert t1 != t2
+	#
+	# t2.add_all(1, [11, 12])
+	#
+	# assert t1 == t2
+	# ~~~
+	redef fun ==(other)
+	do
+		if not other isa OrderedTree[Object] then return false
+		return roots == other.roots and sub == other.sub
+	end
+
+	redef fun hash
+	do
+		return roots.hash + sub.hash
+	end
+
+	# Shallow clone of the tree.
+	#
+	# ~~~
+	# var t = new OrderedTree[Int]
+	# t.add_all(null, [1, 2])
+	# t.add_all(1, [11, 12])
+	#
+	# assert t.clone == t
+	# ~~~
+	redef fun clone
+	do
+		var res = new OrderedTree[E]
+		res.add_all(null, roots)
+		for p, es in sub do
+			res.add_all(p, es)
+		end
+		return res
+	end
 end
 
 # An Iterator over an OrderedTree
@@ -158,9 +231,7 @@ private class OrderedTreeIterator[E: Object]
 
 	var iterators = new Array[Iterator[E]]
 
-	init(tree: OrderedTree[E]) do
-		self.tree = tree
-
+	init do
 		if not tree.is_empty then
 			iterators.add tree.roots.iterator
 		end