import edu.princeton.cs.algs4.UF;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
import java.util.Random;

public class MazeGenerator {
    Pair[] points;
    int x = 0;
    int rows;
    int columns;
    UF map;
    Random rand = new Random();

    MazeGenerator(int m, int n) {
        if (m < 1 || n < 1)
            throw new ArithmeticException();

        points = new Pair[m * n];
        rows = m;
        columns = n;

        //Note: each index in UF is to be mapped to its Pair index counterpart.
        //Example: points[1] == find[1]
        map = new UF (m*n);

        //Populate points array with Pair objects
        for (int j = 0; j < m; j++) {
            for (int i = 0; i < n; i++) {
                points[x++] = new Pair(i, j);
            }
        }
    }

    public void findPath() {
        int current;
        int neighbor;
        List<Pair> unusedPairs = new ArrayList(Arrays.asList(points));

        while(map.count() > 1) {
            current = rand.nextInt(unusedPairs.size());
            neighbor = findAdjacent(unusedPairs.get(current));

            if (map.find(encode(unusedPairs.get(current))) == map.find(neighbor)) {
                System.out.println(map.find(encode(unusedPairs.get(current))));
                System.out.println(map.find(neighbor));
                System.out.println("Connected in same component already!");
            }
            else {
                map.union(encode(unusedPairs.get(current)), neighbor);
                System.out.println(unusedPairs.get(current) + ", " + points[neighbor]);
                unusedPairs.remove(unusedPairs.get(current));
            }
        }
        System.out.println("Maze is complete");
    }

    public class Pair {
        Pair(int x, int y) {
            this.x = x;
            this.y = y;
        }
        //For testing purposes only
        @Override
        public String toString() {
            return ("(" + x + ", " + y + ")");
        }

        final int x;
        final int y;
    }

   /**
    //Theory used: Manhattan distance
    //Note: I don't have a use for this method yet, it was a suggestion.
    public boolean isAdjacent(Pair p, Pair q) {
        int distance = Math.abs(p.x - q.x) + Math.abs(q.y - q.y);

        if (distance == 1) {
            return true;
        }
        return false;
    }*/

    //An adjacent cell must be orthogonal.
    //Test for case: if edge, if side, else
    public int findAdjacent(Pair p) {
        final Pair n = new Pair(0,1);
        final Pair w = new Pair(1,0);
        final Pair s = new Pair(0,-1);
        final Pair e = new Pair(-1,0);
        final Pair[] nwse = {n, w, s, e};
        ArrayList<Pair> neighbors = new ArrayList<>();

        //For every possible 4 directions of the cell, determine which directions are valid and store in arraylist.
        for(Pair direction : nwse) {
            if((0 <= p.x+direction.x) && (p.x+direction.x < columns) && (0 <= p.y+direction.y) && (p.y+direction.y < rows)) {
                neighbors.add(direction);
            }
        }
        //Generate random index based on size of arraylist
        int nbr = (int)(Math.random()* (neighbors.size()));
        Pair direction = neighbors.get(nbr);
        Pair neighbor = new Pair (direction.x + p.x, direction.y + p.y);

        return encode(neighbor);
    }

    //Change Pair to int representation for Union Find struct
    public int encode(Pair a) {
        return Math.abs(a.x) + Math.abs(a.y) + Math.abs((columns-1)  * a.y);
    }

    public static void main(String[] args) {
        MazeGenerator test = new MazeGenerator(4, 5);
        test.findPath();


        //Expected output: print out a line for each union connected.
        //Optional/EC: output a visual representation of maze
    }
}