cs61b backwash code example

Example: cs61b backwash

//use two WQUUF
//One way to fix this is two use two different WQUF.
//One for checking if the system percolates(include virtual top and bottom ), 
//and the other to check if a given cell is full(only include virtual top).

import edu.princeton.cs.algs4.WeightedQuickUnionUF;

public class Percolation {  
    private boolean[] openSite; //if open is true , block false
    private int N; //create N-by-N grid
    private WeightedQuickUnionUF uf; 
    private WeightedQuickUnionUF ufNoBottom; 
    private int top;
    private int bottom;
   
    public Percolation(int N)  {             // create N-by-N grid, with all sites blocked
        if (N <= 0) {
            throw new IllegalArgumentException("N must be bigger than 0");
        } 
         this.N = N;
         uf = new WeightedQuickUnionUF(N*N + 2);
         ufNoBottom = new WeightedQuickUnionUF(N*N + 1);
         openSite = new boolean[N*N+2];   // 0 top_visual N*N+1 bottom_visual
         top = 0;
         bottom = N*N +1;
         for (int i = 1; i <= N*N; i++) {
             openSite[i] = false;   //initial all sites block
         }        
    }
     
    public void open(int i, int j)  {        // open site (row i, column j) if it is not open already
        validateIJ(i, j); 
        int index = xyTo1D(i, j);
        openSite[index] = true; 
  
        if (i == 1) {
            uf.union(index, top);
            ufNoBottom.union(index, top);
        }
        if (!percolates()) {
            if (i == N) {
                uf.union(index, bottom);
            }
        }
        if (i < N && openSite[index+N]) {
             uf.union(index, index+N);
             ufNoBottom.union(index, index+N);
        }
        if (i > 1 && openSite[index-N]) {
             uf.union(index, index-N);
             ufNoBottom.union(index, index-N);
        }
        if (j < N && openSite[index+1]) {
             uf.union(index, index+1);
             ufNoBottom.union(index, index+1);
        }
        if (j > 1 && openSite[index-1]) {
             uf.union(index, index-1);
             ufNoBottom.union(index, index-1);
        }
    }
    
    private int xyTo1D(int i, int j) {
        validateIJ(i, j);
        return j + (i-1) * N;
    }
    
    private void validateIJ(int i, int j) {
        if (!(i >= 1 && i <= N && j >= 1 && j <= N)) {
            throw new IndexOutOfBoundsException("Index is not betwwen 1 and N");
        }
    }
    
    public boolean isOpen(int i, int j) {     // is site (row i, column j) open?
        validateIJ(i, j);
        return openSite[xyTo1D(i, j)];
    }
    
    /*A full site is an open site that can be connected to an open site in the top row 
     * via a chain of neighboring (left, right, up, down) open sites. 
    */
    public boolean isFull(int i, int j) {    // is site (row i, column j) full?
        validateIJ(i, j);
        return ufNoBottom.connected(top, xyTo1D(i, j));
    }
    
    /* Introduce 2 virtual sites (and connections to top and bottom). 
     * Percolates iff virtual top site is connected to virtual bottom site.
     */
    public boolean percolates()  {           // does the system percolate? 
        return uf.connected(top, bottom);
    }
    
    public static void main(String[] args) { // test client (optional)
    }
}