Percolation

/******************************************************************************
 *  Author:       Jules Martel (julesmartel@gmail.com)
 *  Date:         Nov. 2017
 *  Task: http://coursera.cs.princeton.edu/algs4/assignments/percolation.html
 *  This program estimates the percolation threshold of a size N grid.
 *  ---------NO BACKWASH SOLUTION HERE ! -------------------
 * Correctness:  27/30 tests passed (backwash sites)
 * Memory:       8/8 tests passed
 * Timing:       20/20 tests passed
 * Aggregate score: 94.00%
 * Estimated student memory = 9.00 n^2 + 0.00 n + 192.00   (R^2 = 1.000)
 ******************************************************************************/

import edu.princeton.cs.algs4.WeightedQuickUnionUF;

public class Percolation {
    private final int n;
    private final int gridSize;
    private final int bottom;
    private final int top;
    private final WeightedQuickUnionUF wquf;
    private boolean[] isOpen;
    private int openSites;

    public Percolation(int n) {
        this.n = n;
        if (n <= 0) {
            throw new IllegalArgumentException("N must be > 0");
        }
        gridSize = n * n;
        isOpen = new boolean[gridSize + 2];
        /* we add two sites to the grind top=0
         the grid will percolate when the top and bottom sites are connected*/
        wquf = new WeightedQuickUnionUF(gridSize + 2);
        /* we open top and bottom site which are always open because we cannot randomly
         open them as they stand outside the bounds i and j in connectAdjacentSites */
        openSites = 0;
        bottom = gridSize + 1;
        top = 0;
        isOpen[bottom] = true;
        isOpen[top] = true;
    }

    // this maps the grid coordinates to a site number
    private int xyTo1D(int i, int j) {
        validate(i, j);
        return (j + n * (i - 1));
    }


    private void validate(int i, int j) {
        if (i <= 0 || i > n || j <= 0 || j > n) {
            throw new java.lang.IllegalArgumentException("indices (" + i + ","
                    + j + ") are not between 1 and " + (n));
        }
    }

    public void open(int i, int j) {
        validate(i, j);
        int site = xyTo1D(i, j);
        if (!isOpen[site]) {
            isOpen[site] = true;
            openSites++;
            connectAdjacentSites(i, j);
        }
    }

    private void connectAdjacentSites(int i, int j) {
        int site = xyTo1D(i, j);
        int adjacent;

        // connect to top sites on the first row
        if (i == 1) wquf.union(site, top);

        // above site exits only if i>1
        if (i > 1) {
            adjacent = xyTo1D(i - 1, j);
            if (isOpen[adjacent]) {
                wquf.union(site, adjacent);
            }
        }

        // left site
        if (j > 1 && j <= n) {
            adjacent = xyTo1D(i, j - 1);
            if (isOpen[adjacent]) {
                wquf.union(site, adjacent);
            }
        }

        // right site
        if (j >= 1 && j < n) {
            adjacent = xyTo1D(i, j + 1);
            if (isOpen[adjacent]) {
                wquf.union(site, adjacent);
            }
        }

        // below site exists only if i<n
        if (i != n) {
            adjacent = xyTo1D(i + 1, j);
            if (isOpen[adjacent]) {
                wquf.union(site, adjacent);
            }
        }

        // all bottom sites are connected to bottom !
        if (i == n) {
            wquf.union(site, bottom);
        }
    }


    public boolean isOpen(int i, int j) {
        validate(i, j);
        int site = xyTo1D(i, j);
        return isOpen[site];
    }

    public boolean isFull(int i, int j) {
        validate(i, j);
        int site = xyTo1D(i, j);
        return wquf.connected(site, 0);
    }

    public int numberOfOpenSites() {
        return openSites;
    }

    public boolean percolates() {
        return wquf.connected(top, bottom);
    }

}