Algorithms-I : 1-Percolation: use WeightedQuickUnionUF from algs4.jar

1 files changed, 55 insertions, 62 deletions

diff --git a/Algorithms/Part-I/1-Percolation/Percolation.java b/Algorithms/Part-I/1-Percolation/Percolation.java
index a866013..efe79e8 100644
--- a/Algorithms/Part-I/1-Percolation/Percolation.java
+++ b/Algorithms/Part-I/1-Percolation/Percolation.java
@@ -1,72 +1,65 @@
 /* vim: set expandtab tabstop=4 shiftwidth=4 : */
 
-// package pkgname;
+public class Percolation
+{
+    private int N;
+    private byte[] opened;
+    private WeightedQuickUnionUF uf;
 
-import java.io.File;
-import java.util.Date;
-import jargs.gnu.CmdLineParser;
-
-public class Percolation {
-     public Percolation(int N)              // create N-by-N grid, with all sites blocked
-        public void open(int i, int j)         // open site (row i, column j) if it is not already
-        public boolean isOpen(int i, int j)    // is site (row i, column j) open?
-        public boolean isFull(int i, int j)    // is site (row i, column j) full?
-        public boolean percolates()            // does the system percolate?
-}
-/**
- * Class Percolation
- *
- * @author  <john.doe@nope.com>
- * @date 02/03/13
- */
- public class Percolation {
-
-	/*
-	 * print usage and exit with status 1
-	 */
-	private static void printUsage () {
-		System.err.println("Usage : Percolation [{-d, --debug} a_float] [ --input file_name]");
-		System.err.println("            debug   : debug verbosity");
-		System.err.println("            input   : path to input file");
-	}
-
-	/**
-	 * application entry point
-	 */
-	public static void main (String [] args ) {
-
-        CmdLineParser parser = new CmdLineParser();
-        CmdLineParser.Option debug = parser.addIntegerOption('d',"debug");
-        CmdLineParser.Option input = parser.addStringOption("input");
-
-        try {
-            parser.parse(args);
-        } catch(CmdLineParser.OptionException e) {
-            System.err.println("\n"+e.getMessage());
-            printUsage();
-		    System.exit(2);
-        }
-
-        int debugLevel = ((Integer)parser.getOptionValue(debug,new Integer(0))).intValue();
-        String inputFile = (String)parser.getOptionValue(input);
+    // 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);
+        opened = new byte[n];
+        opened[0] = 1;
+        opened[n-1] = 1;
+    }
 
-        if(debugLevel>0){
-            System.out.println("Debug Trace :");
-            System.out.println("\t"+new Date( ) );
-            System.out.println("\tdebug level : "+debugLevel);
-            System.out.println("\texcel file  : "+inputFile);
+    // open site (row i, column j) if it is not already
+    public void open(int i, int j)
+    {
+        if (i < 1 || j < 1 || i > N || j > N)
+            throw new java.lang.IndexOutOfBoundsException("check your indexes");
+        int x = (j-1)*N+i;
+        if (opened[x] == 1) return;
+        opened[x] = 1;
+        if (i > 1 && opened[x-1] == 1) uf.union(x, x-1);
+        if (i < N && opened[x+1] == 1) uf.union(x, x+1);
+        if (j == 1) {
+            uf.union(x, 0);
+            if (opened[x+N] == 1) uf.union(x, x+N);
         }
-
-        if(inputFile!=null && !inputFile.equals("")){
-            File f = new File(inputFile);
-            if(!f.canRead()){
-                System.err.println("Fatal Error : Unable to read "+inputFile);
-                System.exit(1);
-            }
+        else if (j == N) {
+            uf.union(x, N*N+1);
+            if (opened[x-N] == 1) uf.union(x, x-N);
+        } else {
+            if (opened[x-N] == 1) uf.union(x, x-N);
+            if (opened[x+N] == 1) uf.union(x, x+N);
         }
+    }
 
-        System.exit(0);
+    // is site (row i, column j) open?
+    public boolean isOpen(int i, int j)
+    {
+        if (i < 1 || j < 1 || i > N || j > N)
+            throw new java.lang.IndexOutOfBoundsException("check your indexes");
+        return (opened[(j-1)*N+i] == 1);
     }
-}
 
+    // is site (row i, column j) full?
+    public boolean isFull(int i, int j)
+    {
+        if (i < 1 || j < 1 || i > N || j > N)
+            throw new java.lang.IndexOutOfBoundsException("check your indexes");
+        int x = (j-1)*N+i;
+        return ((opened[x] == 1) && (uf.find(x) == 0));
+    }
 
+    // does the system percolate?
+    public boolean percolates()
+    {
+        return (uf.find(0) == uf.find(N*N+1));
+    }
+}