tests: update sav/test_parser* because AST changes

[nit.git] / lib / ordered_tree.nit

diff --git a/lib/ordered_tree.nit b/lib/ordered_tree.nit
index 2b1e6ea..d1dde15 100644 (file)
--- 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,47 @@ 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
 
@@ -89,6 +120,28 @@ class OrderedTree[E: Object]
                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
+                       var subs = sub[old_parent]
+                       subs.remove(e)
+                       if subs.is_empty then
+                               # remove the sub when all children are detached
+                               # so that `==` and `hash` are sane
+                               # Otherwise an empty array will be considered
+                               # differently than no array.
+                               sub.keys.remove(old_parent)
+                       end
+               else if roots.has(e) then
+                       roots.remove(e)
+               end
+       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: Writer)
@@ -104,6 +157,7 @@ class OrderedTree[E: Object]
        do
                if not sub.has_key(e) then return
                var subs = sub[e]
+               if subs.is_empty then return
                var last = subs.last
                for e2 in subs do
                        if e2 != last then
@@ -174,6 +228,52 @@ class OrderedTree[E: Object]
        #     var order = [1, 11, 111, 112, 12, 121, 122, 2, 21, 22]
        #     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