import java.util.Arrays;

public class SquareGrid {

    /*
     * This method check if a given node in the node array can be reached from
     * the top Node and the left node within the node array.
     */
    public static boolean validConnection(int row, int col, Node[][] nodeArray) {
        Node currentNode = nodeArray[row][col];

        if(currentNode == null) { return false; } //Handles NullPointExceptions by inductive reasoning

        if (row == 0 && col == 0) { //Top left corner - always valid by exercise description
            return true;
        } else if (row == 0) { //Only check top connection
            return nodeArray[row][col - 1].getRight() == currentNode;
        } else if (col == 0) { //Only check left connection
            return nodeArray[row - 1][col].getDown() == currentNode;
        } else { //Check both connections
            return nodeArray[row - 1][col].getDown() == currentNode &&
                   nodeArray[row][col - 1].getRight() == currentNode;
        }
    }

    /*
     * This method determines the number of times we can go right from
     * a given node, i.e. determine the length
     */
    public static int getLength(Node node) {
        int length = 0;
        while(node != null) {
            length = length + 1;
            node = node.getRight();
        }
        return length;
    }

    /*
     * This method determines the maximum length of the grid
     * Maximum Length = The maximum number of times we can go right <- L
     */
    public static int getMaxLength(Node origin) {
        Node currentNode = origin;

        int maxLength = 0;

        while(currentNode != null) { //Go through all nodes and determine its length
            maxLength = Math.max(maxLength, getLength(currentNode));
            currentNode = currentNode.getDown();
        }
        return maxLength;
    }

    /*
     * This method determines the number of times we can go down from
     * a given node, i.e. determine the depth
     */
    public static int getDepth(Node node) {
        int depth = 0;
        while(node != null) {
            depth = depth + 1;
            node = node.getDown();
        }
        return depth;
    }

    /*
     * This method determines the maximum depth of the grid
     * Maximum Depth = The maximum number of times we can go down <- D
     */
    public static int getMaxDepth(Node origin) {
        Node currentNode = origin;

        int maxDepth = 0;

        while(currentNode != null) { //Go through all nodes and determine its length
            maxDepth = Math.max(maxDepth, getDepth(currentNode));
            currentNode = currentNode.getRight();
        }
        return maxDepth;
    }

    /*
     * This method transforms the node representation of the
     * grid into an array transformation. This transformation
     * is not one-by-one which will help us in determining if
     * a part of the grid is square.
     */
    public static Node[][] getNodeArray(Node origin) {
        int L = getMaxLength(origin);
        int D = getMaxDepth(origin); System.out.println(D + " " + L);

        Node[][] nodeArray = new Node[D][L];

        Node currentRow = origin;

        for(int row = 0; row < D && currentRow != null; ++row) {
            Node currentNode = currentRow;
            for(int col = 0; col < L && currentNode != null; ++col) {
                nodeArray[row][col] = currentNode;
                currentNode = currentNode.getRight();
            }
            currentRow = currentRow.getDown();
        }

        return nodeArray;
    }

    /*
     * This method checks for some i if there is a square grid of size i
     * PRE: nodeArray dimensions > i
     */
    public static boolean kGridExists(Node[][] nodeArray, int i) {
        for(int row = 0; row < i; ++row) {
            for(int col = 0; col < i; ++col) {
                if(!validConnection(row, col, nodeArray)) {
                    return false;
                }
            }
        }
        return true;
    }

    /*
     * Determines largest square grid inside a grid given
     * its origin.
     * PRE: origin != null
     */
    public static int analyzeSquareGrid(Node origin) {
        Node[][] nodeArray = getNodeArray(origin); System.out.println(Arrays.deepToString(nodeArray));

        int D = nodeArray.length; //We only must check squares
        int maxSize = 0;

        for(int row = 1; row <= D; ++row) {
            if(kGridExists(nodeArray, row)) {
                maxSize = maxSize + 1;
            }
        }
        return maxSize;
    }
}