package net.sunzhenyu.miscellaneous.dsa.other.percolation;
import edu.princeton.cs.algs4.WeightedQuickUnionUF;
/**
* Percolation Model
*
* @author <a href='mailto:sunzhenyucn@gmail.com'>SunZhenyu</a>
* @version 0.0.1
* @date 2018/4/19
* @since 1.8
*/
public class Percolation {
/**
* Initial number
*/
private final int n;
/**
* Open & Blocked status array
*/
private final boolean[] open;
/**
* The n * n grid
*/
private final WeightedQuickUnionUF uf, uf2;
/**
* Open site count cache
*/
private int count;
/**
* Constructor
*
* @param n create n * n grid
* @throws IllegalArgumentException if the initial num not between 1 and n
*/
public Percolation(int n) {
if (n <= 0) {
throw new IllegalArgumentException('The initial num must between 1 and ' + n);
}
this.n = n;
open = new boolean[n * n + 2];
// Because we add 2 sites, so we need plus 2
uf = new WeightedQuickUnionUF(n * n + 2);
// Why use this?
uf2 = new WeightedQuickUnionUF(n * n + 1);
for (int i = 0; i < this.n; i++) {
// The initial status is blocked
open[i] = false;
}
}
/**
* Verify coordinate for avoid {@link IllegalArgumentException}
*
* @param row coordinate
* @param col coordinate
* @throws IllegalArgumentException if coordinate not between one and {@code n}
*/
private void outBoundsCheck(int row, int col) {
if (row <= 0 || row > n || col <= 0 || col > n) {
throw new IllegalArgumentException(
'The coordinate must be [1, n], please check your coordinate');
}
}
/**
* Transfer coordinate to array index
*
* @param row coordinate
* @param col coordinate
* @return array index of coordinate
*/
private int index(int row, int col) {
outBoundsCheck(row, col);
return (row - 1) * n + col;
}
/**
* Check specified coordinate's site is open
*
* @param row coordinate
* @param col coordinate
* @return if open return true
*/
public boolean isOpen(int row, int col) {
outBoundsCheck(row, col);
return open[index(row, col)];
}
/**
* Check specified coordinate's site is full
*
* @param row coordinate
* @param col coordinate
* @return if full return true
*/
public boolean isFull(int row, int col) {
outBoundsCheck(row, col);
if (!isOpen(row, col)) {
return false;
}
return uf2.connected(index(row, col), 0);
}
/**
* Return this percolate model's open site count
*
* @return this percolate model's open site count
*/
public int numberOfOpenSites() {
return count;
}
/**
* Return this percolate model's percolates status
*
* @return this percolate model's percolates status
*/
public boolean percolates() {
return uf.connected(0, n * n + 1);
}
/**
* Open specified coordinate's site and neighborhood's site if they are not open already
*
* @param row coordinate
* @param col coordinate
*/
public void open(int row, int col) {
outBoundsCheck(row, col);
if (isOpen(row, col)) {
return;
}
//Open this site
open[index(row, col)] = true;
// Top
if (row == 1) {
open[0] = true;
uf.union(index(row, col), 0);
uf2.union(index(row, col), 0);
}
// Bottom
if (row == n) {
open[n * n + 1] = true;
uf.union(index(row, col), n * n + 1);
}
// Up
if (row > 1 && isOpen(row - 1, col)) {
uf.union(index(row, col), index(row - 1, col));
uf2.union(index(row, col), index(row - 1, col));
}
// Down
if (row < n && isOpen(row + 1, col)) {
uf.union(index(row, col), index(row + 1, col));
uf2.union(index(row, col), index(row + 1, col));
}
// Left
if (col > 1 && isOpen(row, col - 1)) {
uf.union(index(row, col), index(row, col - 1));
uf2.union(index(row, col), index(row, col - 1));
}
// Right
if (col < n && isOpen(row, col + 1)) {
uf.union(index(row, col), index(row, col + 1));
uf2.union(index(row, col), index(row, col + 1));
}
// Increment open count
count++;
}
public static void main(String[] args) {
int n = 3;
Percolation p = new Percolation(n);
// while (!p.percolates()) {
// int i = StdRandom.uniform(1, n + 1);
// int j = StdRandom.uniform(1, n + 1);
// if (!p.isOpen(i, j)) {
// p.open(i, j);
// System.out.println('open (' + i + ',' + j + '), isFull::' + p.isFull(i, j));
// }
// }
p.open(2, 1);
System.out.println(p.isOpen(1, 1));
System.out.println(p.isOpen(1, 1));
System.out.println(p.isFull(1, 1));
}
}