diff options
Diffstat (limited to 'Algorithms')
| -rw-r--r-- | Algorithms/Part-I/1-Percolation/Percolation.java | 117 |
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)); + } +} |