Added weighted union

nars · nars · commit eac1c0dbc90c · 2015-03-10T16:34:19.000+05:30
diff --git a/UnionFindAlgo/src/UnionFindRunner.java b/UnionFindAlgo/src/UnionFindRunner.java
@@ -1,10 +1,11 @@
-import implemenation.QuickUnionImpl;
+import implemenation.WeightedUnionImpl;
 
 /**
  * Created by nars on 2/24/15.
  */
 public class UnionFindRunner {
-    public static QuickUnionImpl unionUnionImpl = new QuickUnionImpl();
+//    public static QuickUnionImpl unionUnionImpl = new QuickUnionImpl();
+    public static WeightedUnionImpl unionUnionImpl = new WeightedUnionImpl();
     public static void main(String[] args) {
         unionUnionImpl.process("/Users/nars/Dev/DragonRepo/JavaDevelopment/UnionFindAlgo/src/input.txt");
     }
diff --git a/UnionFindAlgo/src/implemenation/QuickUnionImpl.java b/UnionFindAlgo/src/implemenation/QuickUnionImpl.java
@@ -24,7 +24,7 @@ public boolean find(int p, int q) {
     public void union(int p, int q) {
         if (! find(p, q))
         {
-            setRootOf(p, getRootOf(q));
+            this.setRootOf(p, getRootOf(q));
         }
     }
 
diff --git a/UnionFindAlgo/src/implemenation/WeightedUnionImpl.java b/UnionFindAlgo/src/implemenation/WeightedUnionImpl.java
@@ -0,0 +1,51 @@
+package implemenation;
+
+/**
+ * Created by nars on 3/10/15.
+ */
+public class WeightedUnionImpl extends QuickUnionImpl{
+
+    int[] weightArray = null;
+
+    public void initializeInput() {
+        this.initInputArraySize();
+        weightArray = new int[this.getInputSize()];
+        for (int i = 0; i < this.getInputSize(); i++) {
+            this.setElementAt(i,i);
+            this.setWeightAt(i,1);
+        }
+    }
+
+    public void setWeightAt(int index, int value)
+    {
+        this.weightArray[index] = value;
+    }
+    public int getWeightAt(int index)
+    {
+        return this.weightArray[index];
+    }
+
+    public void union(int p, int q) {
+        if (! find(p, q))
+        {
+            int rootWeightOfP= this.getWeightAt(this.getRootOf(p));
+            int rootWeightOfQ= this.getWeightAt(this.getRootOf(q));
+            if (rootWeightOfP < rootWeightOfQ)
+            {
+                this.setRootOf(p, getRootOf(q));
+            }
+            else
+            {
+                this.setRootOf(q, getRootOf(p));
+            }
+        }
+    }
+
+    public void setRootOf(int nodeP, int newRoot) {
+        int currentWeight = this.getWeightAt(getRootOf(nodeP));
+        int newRootWeight = this.getWeightAt(newRoot);
+        this.setElementAt(getRootOf(nodeP), newRoot);
+        this.setWeightAt(newRoot, currentWeight+newRootWeight);
+    }
+
+}
diff --git a/UnionFindAlgo/src/input.txt b/UnionFindAlgo/src/input.txt
@@ -1,4 +1,10 @@
-4
-F 1 2
-U 1 2
-F 1 2
+10
+U 3 4
+U 4 9
+U 8 0
+U 2 3
+U 5 6
+U 5 9
+U 7 3
+U 4 8
+U 6 1

Original file line number	Diff line number	Diff line change
`@@ -24,7 +24,7 @@ public boolean find(int p, int q) {`
`24`	`24`	`public void union(int p, int q) {`
`25`	`25`	`if (! find(p, q))`
`26`	`26`	`{`
`27`		`- setRootOf(p, getRootOf(q));`
	`27`	`+ this.setRootOf(p, getRootOf(q));`
`28`	`28`	`}`
`29`	`29`	`}`
`30`	`30`
-Original file line number
+Diff line change
@@ @@ -1,4 +1,10 @@ @@
 -4
 -F 1 2
 -U 1 2
 -F 1 2
 +10
 +U 3 4
 +U 4 9
 +U 8 0
 +U 2 3
 +U 5 6
 +U 5 9
 +U 7 3
 +U 4 8
 +U 6 1