From: Jean Privat <jean@pryen.org>
Date: Wed, 23 Sep 2015 18:20:22 +0000 (-0400)
Subject: Merge: Beef up OrderedTree API
X-Git-Tag: v0.7.8~9
X-Git-Url: http://nitlanguage.org?hp=8d71597913a195ff5f9dce1d77182449f711c932

Merge: Beef up OrderedTree API

This add services to the class OrderedTree

Pull-Request: #1732
Reviewed-by: Lucas Bajolet <r4pass@hotmail.com>
Reviewed-by: Alexandre Terrasa <alexandre@moz-code.org>
---

diff --git a/lib/ordered_tree.nit b/lib/ordered_tree.nit
index 2a6a10c..0b1d383 100644
--- a/lib/ordered_tree.nit
+++ b/lib/ordered_tree.nit
@@ -61,6 +61,7 @@ module ordered_tree
 class OrderedTree[E: Object]
 	super Writable
 	super Collection[E]
+	super Cloneable
 
 	# The roots of the tree (in sequence)
 	var roots = new Array[E]
@@ -69,17 +70,67 @@ class OrderedTree[E: Object]
 	# For each element, the ordered array of its direct sub-elements.
 	var sub = new HashMap[E, Array[E]]
 
+	# The parent of each element.
+	#
+	# Roots have `null` as parent.
+	private var parents = new HashMap[E, nullable E]
+
+	redef fun length do return parents.length
+
+	redef fun has(e) do return parents.has_key(e)
+
+	# The parent of the element `e`
+	#
+	# Roots have `null` as parent.
+	#
+	# ~~~
+	# var tree = new OrderedTree[Int]
+	# tree.add(1, 2)
+	# assert tree.parent(2) == 1
+	# assert tree.parent(1) == null
+	# ~~~
+	fun parent(e: E): nullable E do return parents[e]
+
 	# Add a new element `e` in the tree.
+	#
 	# `p` is the parent of `e`.
-	# if `p` is null, then `e` is a root element.
+	# If `p` is null, then `e` is a root element.
+	#
+	# If `e` is already in the tree, it is detached from its old
+	# parent and attached to the new parent `p`.
 	fun add(p: nullable E, e: E)
 	do
+		detach(e)
+		parents[e] = p
 		if p == null then
 			roots.add(e)
-		else if sub.has_key(p) then
-			sub[p].add(e)
 		else
-			sub[p] = [e]
+			if not has(p) then add(null, p)
+			if sub.has_key(p) then
+				sub[p].add(e)
+			else
+				sub[p] = [e]
+			end
+		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
+
+	# Temporary remove `e`.
+	#
+	# Children of `e` are left untouched in the tree.
+	# This make the tree inconstant until `e` is added back.
+	private fun detach(e: E)
+	do
+		var old_parent = parents.get_or_null(e)
+		if old_parent != null then
+			sub[old_parent].remove(e)
+		else if roots.has(e) then
+			roots.remove(e)
 		end
 	end
 
@@ -130,16 +181,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]
@@ -165,21 +211,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