Merge: lib/std/union_find: make DisjointSet Cloneable

Just because I need it.

I'm still not sure about what is the best way to deal with the various copy-constructors and clone methods. I think the following make sense:

A copy constructor named `from` that takes, if possible a general classifier (like an interface). This named constructor may use `nosuper` to avoid the automatic invocation of the standard init method if this cause a useless complex initialization that will be throw away by the copy.
A direct copy `clone` than can just return `new SELFTYPE.from(self)`

The advantage is that for simple clone, the `clone` method do the job.
If one want to change the class but keep the data, then the `from` constructor can be used. Like `new HashSet.from([1,2,3])`

Pull-Request: #1226
Reviewed-by: Alexis Laferrière <alexis.laf@xymus.net>
Reviewed-by: Romain Chanoir <chanoir.romain@courrier.uqam.ca>
Reviewed-by: Alexandre Terrasa <alexandre@moz-code.org>

diff --git a/lib/standard/collection/union_find.nit b/lib/standard/collection/union_find.nit
index 4df80b5..12c9c86 100644 (file)
--- a/lib/standard/collection/union_find.nit
+++ b/lib/standard/collection/union_find.nit
@@ -33,10 +33,46 @@ import hash_collection
 # The methods `in_same_subset`, `to_partitions`, and their variations are offered instead.
 class DisjointSet[E]
        super SimpleCollection[E]
+       super Cloneable
 
        # The node in the hiearchical structure for each element
        private var nodes = new HashMap[E, DisjointSetNode]
 
+       # Copy constructor
+       init from(other: DisjointSet[E])
+       do
+               # Associate a root node in other to the associated root node in self
+               var map = new HashMap[DisjointSetNode, DisjointSetNode]
+               for e, v in other.nodes do
+                       # Create the associated node
+                       var n2 = new DisjointSetNode
+                       nodes[e] = n2
+
+                       # Get the root node in other and the associated one in self
+                       var p = other.find(e)
+                       var p2 = map.get_or_null(p)
+                       if p2 == null then
+                               # if no associated root node, then a new subset is created
+                               map[p] = n2.parent
+                               number_of_subsets += 1
+                       else
+                               # else attach the new node to the subset of the root node
+                               n2.parent = p2
+                       end
+               end
+       end
+
+       # Shallow copy
+       #
+       #     var s = new DisjointSet[Int]
+       #     s.add_all([1,2,3,4,5])
+       #     s.union_all([1,4,5])
+       #     var s2 = s.clone
+       #     assert s2.number_of_subsets == 3
+       #     assert s2.all_in_same_subset([1,4,5]) == true
+       #     assert s2.in_same_subset(1,2) == false
+       redef fun clone do return new DisjointSet[E].from(self)
+
        # The number of subsets in the partition
        #
        #     var s = new DisjointSet[Int]