Algorithms-I : 1-Percolation: add PercolationJZU.java

1 files changed, 103 insertions, 0 deletions

diff --git a/Algorithms/Part-I/1-Percolation/PercolationJZU.java b/Algorithms/Part-I/1-Percolation/PercolationJZU.java
new file mode 100644
index 0000000..8112b9f
--- /dev/null
+++ b/Algorithms/Part-I/1-Percolation/PercolationJZU.java
@@ -0,0 +1,103 @@
+/* vim: set expandtab tabstop=4 shiftwidth=4 : */
+
+public class PercolationJZU
+{
+    private static final int closed = -1;
+    private int N;
+    // faste using struct { id, weight } ?
+    private int[] sites;
+    private int[] weights;
+
+    public PercolationJZU(int N)
+    {
+        this.N = N;
+        int n = (N*N)+2;
+        sites = new int[n];
+        weights = new int[n];
+        sites[0] = 0;
+        weights[0] = N+1;
+        sites[n-1] = n-1;
+        weights[n-1] = N+1;
+        for(int x=1; x<=n-1; x++)
+        {
+            sites[x] = x;
+            weights[x] = closed;
+        }
+    }
+
+    private int ijToX(int i, int j)
+    {
+        if(i<1 || j<1 || i>N || j>N)
+            throw new java.lang.IndexOutOfBoundsException("check your indexes");
+        return ((j-1)*N)+i;
+    }
+
+    private boolean isOpen(int x)
+    {
+        return (weights[x]!=closed);
+    }
+
+    private int root(int x)
+    {
+        while (x != sites[x])
+        {
+            sites[x] = sites[sites[x]];
+            x = sites[x];
+        }
+        return x;
+    }
+
+    private void connect(int i, int j)
+    {
+        int ri = root(i);
+        int rj = root(j);
+        if (ri==rj) return;
+        if (weights[ri] < weights[rj])
+        {
+            sites[ri] = rj;
+            weights[rj] += weights[ri];
+        }
+        else
+        {
+            sites[rj] = ri;
+            weights[ri] += weights[rj];
+        }
+
+    }
+
+    public void open(int i, int j)
+    {
+        int x = ijToX(i,j);
+        if (isOpen(x)) return;
+        weights[x] = 1;
+        if (i>1 && isOpen(x-1)) connect(x,x-1);
+        if (i<N && isOpen(x+1)) connect(x,x+1);
+        if(j==1) {
+            connect(x,0);
+            if (isOpen(x+N)) connect(x,x+N);
+        }
+        else if(j==N) {
+            connect(x,N*N+1);
+            if (isOpen(x-N)) connect(x,x-N);
+        } else {
+            if (isOpen(x-N)) connect(x,x-N);
+            if (isOpen(x+N)) connect(x,x+N);
+        }
+    }
+
+    public boolean isOpen(int i, int j)
+    {
+        return isOpen(ijToX(i,j));
+    }
+
+    public boolean isFull(int i, int j)
+    {
+        int x = ijToX(i,j);
+        return ((isOpen(x)) && (root(x)==0));
+    }
+
+    public boolean percolates()
+    {
+        return (root(0)==root(N*N+1));
+    }
+}