From: Alexandre Blondin Massé <alexandre.blondin.masse@gmail.com>
Date: Sun, 16 Nov 2014 03:40:56 +0000 (-0500)
Subject: lib: Enhanced DisjointSet data structure
X-Git-Tag: v0.6.11~33^2
X-Git-Url: http://nitlanguage.org

lib: Enhanced DisjointSet data structure

It is now possible to retrieve the number of subsets in the partition by
using the 'number_of_subsets' property. It is useful for instance when
one wants to know if the partition is a singleton, or if it is trivial
(every element is alone in its subset).

Signed-off-by: Alexandre Blondin Massé <alexandre.blondin.masse@gmail.com>
---

diff --git a/lib/standard/collection/union_find.nit b/lib/standard/collection/union_find.nit
index e865703..f9ac76f 100644
--- a/lib/standard/collection/union_find.nit
+++ b/lib/standard/collection/union_find.nit
@@ -37,6 +37,17 @@ class DisjointSet[E: Object]
 	# The node in the hiearchical structure for each element
 	private var nodes = new HashMap[E, DisjointSetNode]
 
+	# The number of subsets in the partition
+	#
+	#     var s = new DisjointSet[Int]
+	#     s.add_all([1,2,3,4,5])
+	#     assert s.number_of_subsets == 5
+	#     s.union_all([1,4,5])
+	#     assert s.number_of_subsets == 3
+	#     s.union(4,5)
+	#     assert s.number_of_subsets == 3
+	var number_of_subsets: Int = 0
+
 	# Get the root node of an element
 	# require: `has(e)`
 	private fun find(e:E): DisjointSetNode
@@ -84,6 +95,7 @@ class DisjointSet[E: Object]
 		if nodes.has_key(e) then return
 		var ne = new DisjointSetNode
 		nodes[e] = ne
+		number_of_subsets += 1
 	end
 
 	# Are two elements in the same subset?
@@ -171,6 +183,7 @@ class DisjointSet[E: Object]
 				ne.rank = er+1
 			end
 		end
+		number_of_subsets -= 1
 	end
 
 	# Combine the subsets of all elements of `es`