unionfind

Class Percolation

java.lang.Object

unionfind.Percolation

public class Percolation
extends java.lang.Object

Written: 7/20/2017 Last updated: 7/20/2017

Requirement: Class must be in unionfind package and exercises.* and java.lang.* must be imported.

Javadoc: javadoc -author -version -private -classpath .;algs4_exercises.jar; -d .\javadoc Percolation.java

Compilation: javac -cp .;algs4_exercises.jar; Percolation.java

Execution 1: java -cp ../;.;algs4_exercises.jar; unionfind.Percolation <input5.txt

Execution 2: java -cp ../;.;algs4_exercises.jar; unionfind.Percolation <input10.txt

Execution 3: java -cp ../;.;algs4_exercises.jar; unionfind.Percolation <jerry47.txt

Execution 4: java -cp ../;.;algs4_exercises.jar; unionfind.Percolation <sedgewick60.txt

Execution 5: java -cp ../;.;algs4_exercises.jar; unionfind.Percolation <wayne98.txt

Summary: The Percolation Program reads a data file, into a 2D array. The first number in the file is the dimensions of the 2D array. The dimension is passed into the percolation constructor. In order to workaround accepting input with a col and row starting at (1,1), a 1 is added to the dimension, to produce an extra row and column, with nothing in the 0 row or 0 column. The printBlockedGrid() method is called to set the 2-D coordinates to BLOCKED and draw them. The open() method then reads the row, col combination from the input file. For each set of coordinates read, they must be assigned to instance members this.col and this.row and the this.status variable (grid[col][row] must be assigned the value BLOCKED before calling the nodeChangerRowTracker() method. The open() method (should use Weighted API) flips the row coordinates to map them to the StdDraw coordinates. For example, to map the top left coords. of StdDraw to (1,1) file coords, the input row has to be flipped, to map the StdDraw coord map (0, 0) to the bottom left corner, instead of the top. Since the 0 column is not used, the column values must be shifted to the right. This requires an extra column at the end of the grid to shift the last column over one.

Methods:

1. createNode() is a mirror of searchForOpenedNodeByRow(), accept instead of reading in input, it creates random coordinates and converts them to a WeightedQuickUnionUF object, so they can be flipped from BLOCKED to OPENED.
2. The nodeChangerRowTracker() method opens all the BLOCKED squares that are read from the file. Once done, the searchForOpenedNodeByRow() method is called by checkPerculation(), to search for touching OPENED squares, and partially isolated OPENED squares in each row (starting from top)and sets them to FILLED, then draws them. The color cascades down to all touching or partially touching OPENED squares.

Files: The first element in the file is the dimension, the other numbers are rows and cols in sequence.

Version:

1.7

Author:

Tony Lockhart

Field Summary

Fields

Modifier and Type	Field and Description
private int	BLOCKED The lowest status that can be entered into an array index (Blocked - this.squaredDimensionHigh).
private int	col
private int	count Tracks the number of inputs read from the external file, it is incremented by 2 because the coordinates come in pairs (col, row).
private int	dimensionHigh The dimension of the N by N grid, +1 to get rid of 0 offset
private static int	dimensionLow The lowest index of the N by N grid, starts at 0
private double	doubleThreshold
private boolean	endOfRowReached Flag that is set to true when the end of a row has been reached.
private int	FILLED The highest status that can be entered into an array index (Filled - this.squaredDimensionHigh+2).
private int	filledRowCounter Keeps track of the total number of Filled squares.
private int	fillRow Keeps track of the number of squares Filled in the row (starting at 1).
private int[][]	grid The N by N grid array.
private static int[]	inputArray The linear input array.
private int	OPENED The middle status that can be entered into an array index (Opened - this.squaredDimensionHigh+1).
private int	openedSquareCounter The total number of Opened squares
private int	openNodeSearchCol The starting value (1) used to search for other opened squares in the same row, when an opened square is found.
private boolean	percolates Boolean value that returns true if the grid perculates (Filled value reaches the bottom of the grid).
private exercises.WeightedQuickUnionUF	qf
private int	row
private int	squaredDimensionHigh The total number of squares in the grid.
private int	status The array index value of the grid, where squaredDimensionHigh = Blocked, squaredDimensionHigh+1= Opened, squaredDimensionHigh+2 = Filled.
private static int	statusHigh The highest status that can be entered into an array index (Filled - this.squaredDimensionHigh+2).
private static int	statusLow The highest status that can be entered into an array index (Blocked - this.squaredDimensionHigh).
private int	totalFilledSquares The total number of Filled squares.

Constructor Summary

Constructors

Constructor and Description
Percolation(int dimensionHigh) Percolation constructor intializes all the grid values based on the dimensions.

Method Summary

Methods

Modifier and Type	Method and Description
private void	checkBound(int n)
private void	checkBounds(int row, int col)
private void	checkPerculation() Checks the entire grid, starting at col 1(opentNodeSearchCtr), to determine if the grid perculates (filled square has reached the bottom of the grid).
private int	convertGridCoordToLinearNode(int col, int row) Method maps the random coordinates from the createNode method to the Linear Array in UF
private void	convertLinearArrayNodeToGridCoord(int index) Converts a linear array index to an N by N grid coordinate and stores the row and col instance.
private void	createNode() Creates random linear index from the dimensionLow and the squaredDimensionHigh instance variables.
private void	drawSquare(int col, int row, int status) Draws the background color of the squares, based on its status
private void	drawText(java.lang.String text)
private void	flipBlockedNodeToOpened(int col, int row) Method Flips Blocked Nodes to Opened, if surrounding squares are Filled.
private void	flipOpenNodeToFilled(int col, int row) Method changes the value in the square associated with the (col, row) coordinate in the N by N grid, from Opened to Filled.
private void	flipSurroundingOpenSquaresToFilled(int col, int row) Method checks surrounding squares and changes colors as necessary Method is recursively called to flip squares from Opened (White) to Filled (Green) as necessary.
private int	getRandomNum(int low, int high) Returns a random integer uniformly in [a, b).
private boolean	isBlockedNodeReadyToBeOpened(int col, int row) Method checks if target square is Blocked, and instance var status is set to Opened.
boolean	isFilled(int row, int col)
boolean	isOpen(int row, int col)
private boolean	isOpenNodeReadyToBeFilled(int col, int row) Method checks if target node is Opened and instance var status is set to Filled.
private boolean	isSurroundingSquareFilled(int col, int row) Method checks to the Left, Above, Right, and Below the current sqaure, for filled squares.
static void	main(java.lang.String[] args)
private void	nodeChangerRowTracker() Method changes the colors from Blocked to Opened, and from Opened to Filled.
int	numberOfOpenSites()
void	open(int row, int col) Sets the square at (col, row) to Opened, and flips the row , so coordinates (0,0) is at the top of the coordinate system, instead of at lower left.
private void	openSquare(int row, int col) Method changes the N by N square coordinates(row, col) from blocked to opened
boolean	percolates() Determines if the grid percolates (Filled square reaches the bottom grid).
private void	printBlockedGrid(int source) Prints the grid with initial Blocked values
private void	searchForOpenedNodeByRow(int col, int row) When an opened node is found in the grid, the method searches the row of the Opened square of other Opened squares, to be Filled (starting at col 1, to take care of the 1 col offset).
private java.lang.String	threshold()

Methods inherited from class java.lang.Object

clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait

Field Detail

dimensionHigh

private final int dimensionHigh

The dimension of the N by N grid, +1 to get rid of 0 offset

dimensionLow

private static final int dimensionLow

The lowest index of the N by N grid, starts at 0

See Also:

Constant Field Values

qf

private exercises.WeightedQuickUnionUF qf

squaredDimensionHigh

private int squaredDimensionHigh

The total number of squares in the grid.

statusHigh

private static int statusHigh

The highest status that can be entered into an array index (Filled - this.squaredDimensionHigh+2).

statusLow

private static int statusLow

The highest status that can be entered into an array index (Blocked - this.squaredDimensionHigh).

status

private int status

The array index value of the grid, where squaredDimensionHigh = Blocked, squaredDimensionHigh+1= Opened, squaredDimensionHigh+2 = Filled.

grid

private int[][] grid

The N by N grid array.

row

private int row

col

private int col

count

private int count

Tracks the number of inputs read from the external file, it is incremented by 2 because the coordinates come in pairs (col, row). It is initially set at 1 because the 1rst integer read is the array dimension.

inputArray

private static int[] inputArray

The linear input array.

fillRow

private int fillRow

Keeps track of the number of squares Filled in the row (starting at 1). Once the row is completely Filled, it will be incremented to the next row.

filledRowCounter

private int filledRowCounter

Keeps track of the total number of Filled squares.

openedSquareCounter

private int openedSquareCounter

The total number of Opened squares

totalFilledSquares

private int totalFilledSquares

The total number of Filled squares.

openNodeSearchCol

private int openNodeSearchCol

The starting value (1) used to search for other opened squares in the same row, when an opened square is found. The value is used to flip Opened squares to Filled.

doubleThreshold

private double doubleThreshold

percolates

private boolean percolates

Boolean value that returns true if the grid perculates (Filled value reaches the bottom of the grid).

endOfRowReached

private boolean endOfRowReached

Flag that is set to true when the end of a row has been reached. This value allows the fillRow to be incremented.

BLOCKED

private int BLOCKED

The lowest status that can be entered into an array index (Blocked - this.squaredDimensionHigh).

OPENED

private int OPENED

The middle status that can be entered into an array index (Opened - this.squaredDimensionHigh+1).

FILLED

private int FILLED

The highest status that can be entered into an array index (Filled - this.squaredDimensionHigh+2).

Constructor Detail

Percolation

public Percolation(int dimensionHigh)

Percolation constructor intializes all the grid values based on the dimensions.

Parameters:

dimensionHigh - the integer used to establish the dimensions of the N by N grid.

Method Detail

createNode

private void createNode()

Creates random linear index from the dimensionLow and the squaredDimensionHigh instance variables. Method converts the linear array index to the row, col for the N by N grid.

searchForOpenedNodeByRow

private void searchForOpenedNodeByRow(int col,
                            int row)

When an opened node is found in the grid, the method searches the row of the Opened square of other Opened squares, to be Filled (starting at col 1, to take care of the 1 col offset).

convertGridCoordToLinearNode

private int convertGridCoordToLinearNode(int col,
                               int row)

Method maps the random coordinates from the createNode method to the Linear Array in UF

convertLinearArrayNodeToGridCoord

private void convertLinearArrayNodeToGridCoord(int index)

Converts a linear array index to an N by N grid coordinate and stores the row and col instance.

Parameters:

index - The linear array index to be created to an N by N grid coordinate.

openSquare

private void openSquare(int row,
              int col)

Method changes the N by N square coordinates(row, col) from blocked to opened

open

public void open(int row,
        int col)

Sets the square at (col, row) to Opened, and flips the row , so coordinates (0,0) is at the top of the coordinate system, instead of at lower left.

Parameters:

row - the row coordinate in the N by N grid.

col - the col coordinate in the N by N grid.

getRandomNum

private int getRandomNum(int low,
               int high)

Returns a random integer uniformly in [a, b). NOTE: [excluded, included)

Parameters:

low - excluded integer value at the low end of the range.

high - included integer value at the high end of the range.

Returns:

value A randomly generated value between the arguments low and high.

printBlockedGrid

private void printBlockedGrid(int source)

Prints the grid with initial Blocked values

drawSquare

private void drawSquare(int col,
              int row,
              int status)

Draws the background color of the squares, based on its status

Parameters:

col - the col of the N by N grid.

row - the row of the N by N grid.

status - The grid coordinate value, which indicates the status of the grid[Blocked , Opened , and Filled squares]

flipOpenNodeToFilled

private void flipOpenNodeToFilled(int col,
                        int row)

Method changes the value in the square associated with the (col, row) coordinate in the N by N grid, from Opened to Filled.

Parameters:

col - the col of the N by N grid.

row - the row of the N by N grid.

isSurroundingSquareFilled

private boolean isSurroundingSquareFilled(int col,
                                int row)

Method checks to the Left, Above, Right, and Below the current sqaure, for filled squares.

Returns:

value Returns boolean value.

checkBounds

private void checkBounds(int row,
               int col)

checkBound

private void checkBound(int n)

isOpen

public boolean isOpen(int row,
             int col)

isFilled

public boolean isFilled(int row,
               int col)

percolates

public boolean percolates()

Determines if the grid percolates (Filled square reaches the bottom grid).

nodeChangerRowTracker

private void nodeChangerRowTracker()

Method changes the colors from Blocked to Opened, and from Opened to Filled.

isOpenNodeReadyToBeFilled

private boolean isOpenNodeReadyToBeFilled(int col,
                                int row)

Method checks if target node is Opened and instance var status is set to Filled.

Returns:

value Returns boolean value.

isBlockedNodeReadyToBeOpened

private boolean isBlockedNodeReadyToBeOpened(int col,
                                   int row)

Method checks if target square is Blocked, and instance var status is set to Opened.

Returns:

value Returns boolean value.

flipBlockedNodeToOpened

private void flipBlockedNodeToOpened(int col,
                           int row)

Method Flips Blocked Nodes to Opened, if surrounding squares are Filled.

numberOfOpenSites

public int numberOfOpenSites()

flipSurroundingOpenSquaresToFilled

private void flipSurroundingOpenSquaresToFilled(int col,
                                      int row)

Method checks surrounding squares and changes colors as necessary Method is recursively called to flip squares from Opened (White) to Filled (Green) as necessary.

threshold

private java.lang.String threshold()

drawText

private void drawText(java.lang.String text)

checkPerculation

private void checkPerculation()

Checks the entire grid, starting at col 1(opentNodeSearchCtr), to determine if the grid perculates (filled square has reached the bottom of the grid).

main

public static void main(java.lang.String[] args)