Algorithms-I : 1-Percolation: fix isFull()

 - need 2 WeightedQuickUnionUF
 - 1 to implement percolates, uses top and bottom virtual sites
 - 1 to implement isFull, uses only top virtual site

1 files changed, 49 insertions, 14 deletions

diff --git a/Algorithms/Part-I/1-Percolation/Percolation.java b/Algorithms/Part-I/1-Percolation/Percolation.java
index 8364585..e41d265 100644
--- a/Algorithms/Part-I/1-Percolation/Percolation.java
+++ b/Algorithms/Part-I/1-Percolation/Percolation.java
@@ -4,14 +4,18 @@ public class Percolation
 {
     private int N;
     private boolean[] opened;
-    private WeightedQuickUnionUF uf;
+    // to implement percolates, uses top and bottom virtual sites
+    private WeightedQuickUnionUF p;
+    // to implement isFull, uses only top virtual site
+    private WeightedQuickUnionUF f;
 
     // create N-by-N grid, with all sites blocked
     public Percolation(int N)
     {
         this.N = N;
         int n = (N*N)+2;
-        uf = new WeightedQuickUnionUF(n);
+        p = new WeightedQuickUnionUF(n);
+        f = new WeightedQuickUnionUF(n);
         opened = new boolean[n];
         opened[0] = true;
         opened[n-1] = true;
@@ -25,18 +29,49 @@ public class Percolation
         int x = (i-1)*N+j;
         if (opened[x]) return;
         opened[x] = true;
-        if (j > 1 && opened[x-1]) uf.union(x, x-1);
-        if (j < N && opened[x+1]) uf.union(x, x+1);
-        if (i == 1) {
-            uf.union(0, x);
-            if (opened[x+N]) uf.union(x, x+N);
+        // left
+        if (j > 1 && opened[x-1])
+        {
+            p.union(x, x-1);
+            f.union(x, x-1);
+        }
+        // right
+        if (j < N && opened[x+1])
+        {
+            p.union(x, x+1);
+            f.union(x, x+1);
         }
-        else if (i == N) {
-            uf.union(N*N+1, x);
-            if (opened[x-N]) uf.union(x, x-N);
+        // virtual top
+        if (i == 1) {
+            f.union(0, x);
+            p.union(0, x);
+            if (opened[x+N])
+            {
+                p.union(x, x+N);
+                f.union(x, x+N);
+            }
+        } else if (i == N) {
+            // virtual bottom
+            // only connect percolation
+            p.union(N*N+1, x);
+            if (opened[x-N])
+            {
+                p.union(x, x-N);
+                f.union(x, x-N);
+            }
         } else {
-            if (opened[x-N]) uf.union(x, x-N);
-            if (opened[x+N]) uf.union(x, x+N);
+            // up
+            if (opened[x-N])
+            {
+                p.union(x, x-N);
+                f.union(x, x-N);
+            }
+            // down
+            if (opened[x+N])
+            {
+                p.union(x, x+N);
+                f.union(x, x+N);
+            }
         }
     }
 
@@ -54,12 +89,12 @@ public class Percolation
         if (i < 1 || j < 1 || i > N || j > N)
             throw new java.lang.IndexOutOfBoundsException("check your indexes");
         int x = (i-1)*N+j;
-        return ((opened[x]) && (uf.find(x) == 0));
+        return (opened[x] && (f.find(x) == f.find(0)));
     }
 
     // does the system percolate?
     public boolean percolates()
     {
-        return (uf.find(0) == uf.find(N*N+1));
+        return (p.find(0) == p.find(N*N+1));
     }
 }