From ed999c6141a39712177763d1df4134c36ce6117e Mon Sep 17 00:00:00 2001 From: Jean Privat Date: Sun, 29 Mar 2015 21:39:02 +0700 Subject: [PATCH] lib/std/union_find: make DisjointSet Cloneable Signed-off-by: Jean Privat --- lib/standard/collection/union_find.nit | 36 ++++++++++++++++++++++++++++++++ 1 file changed, 36 insertions(+) diff --git a/lib/standard/collection/union_find.nit b/lib/standard/collection/union_find.nit index 4df80b5..12c9c86 100644 --- 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] -- 1.7.9.5