I need a diagram to explain how this maze.java is working. So I can get a better understanding of how it works overall.

import java.util.*;

class DisjointSets {

private int[] array;

/**

* Construct a disjoint sets object.

*

* @param numElements the initial number of elements--also the initial

* number of disjoint sets, since every element is initially in its own set.

* so, this array will store the immediate parent of current element.

**/

public DisjointSets(int numElements) {

array = new int [numElements];

for (int i = 0; i < array.length; i++) {

array[i] = -1;

}

}

/**

* union() unites two disjoint sets into a single set. A union-by-size

* heuristic is used to choose the new root. This method will corrupt

* the data structure if root1 and root2 are not roots of their respective

* sets, or if they're identical.

*

* @param root1 the root of the first set.

* @param root2 the root of the other set.

* root is the parent of any particular set. You can imagine a set as a tree

* whose root is the parent and all the other nodes are different elements of the set.

* When doing union, we will check the larger set and we will add the smaller one to the larger

* one for optimal complexity while doing find()

* Also we'll update the root(parent) of the set.

**/

public void union(int root1, int root2) {

if (array[root2] < array[root1]) { // root2 has larger tree

array[root2] += array[root1]; // update # of items in root2's tree

array[root1] = root2; // make root2 new root

} else { // root1 has equal or larger tree

array[root1] += array[root2]; // update # of items in root1's tree

array[root2] = root1; // make root1 new root

}

}

/**

* find() finds the (int) name of the set containing a given element.

* Performs path compression along the way.

*

* @param x the element sought.

* @return the set containing x.

*

**/

public int find(int x) {

if (array[x] < 0) {

return x; // x is the root of the tree; return it

} else {

// Find out who the root is; compress path by making the root x's parent.

array[x] = find(array[x]);

return array[x]; // Return the root

}

}

}

/**

* The Maze class represents a maze in a rectangular grid. There is exactly

* one path between any two points.

**/

public class Maze {

// Horizontal and vertical dimensions of the maze.

protected int horiz;

protected int vert;

// Horizontal and vertical interior walls; each is true if the wall exists.

protected boolean[][] hWalls;

protected boolean[][] vWalls;

// Object for generating random numbers.

private static Random random;

// Constants used in depth-first search (which checks for cycles in the

// maze).

private static final int STARTHERE = 0;

private static final int FROMLEFT = 1;

private static final int FROMRIGHT = 2;

private static final int FROMABOVE = 3;

private static final int FROMBELOW = 4;

/**

* Maze() creates a rectangular maze having "horizontalSize" cells in the

* horizontal direction, and "verticalSize" cells in the vertical direction.

* There is a path between any two cells of the maze. A disjoint set data

* structure is used to ensure that there is only one path between any two

* cells.

**/

/**

*

* @param horizontalSize horizontal size of the maze

* @param verticalSize vertical size of the maze

* this is the constructor for the maze. It will take the size of the maze

* for using it in other functions of this class.

*/

public Maze(int horizontalSize, int verticalSize) {

int i, j;

horiz = horizontalSize;

vert = verticalSize;

if ((horiz < 1) || (vert < 1) || ((horiz == 1) && (vert == 1))) {

return; // There are no interior walls

//this is to check if the maze contains only a single cell or no cell at all

// if we have only one vertical length and one horizontal length then it will be only containing

// one single cell

// +-+

// | |

// +-+

//there will be no scope of finding a maze in it

}

// Create all of the horizontal interior walls. Initially, every

// horizontal wall exists; they will be removed later by the maze

// generation algorithm.

/**

* We are going to save the state (true or false) in this two dimensional array

* why two dimensional ...you can think it as coordinates of any horizontal wall

* inside the maze. First index of 2D array will give position of wall in horizontal direction

* and second index of that array will give position in vertical space.

* currently setting every wall to true because right now every horizontal wall is present in the maze

* why vert-1 as second index. Because we don't care about exterior walls because they will be there forever

* only interior wall matters, so, we are only saving the states of interior horizontal walls i.e. vertical

* length of the maze subtracted by 1. (you can try drawing it)

*/

if (vert > 1) {

hWalls = new boolean[horiz][vert - 1];

for (j = 0; j < vert - 1; j++) {

for (i = 0; i < horiz; i++) {

hWalls[i][j] = true;

}

}

}

// Create all of the vertical interior walls.

//Same thing with the vertical walls states. In this case the x-ais in the array will be horiz-1

// because we only care about the interior vertical walls. setting every wall to true because they are all present in the

// maze currently

if (horiz > 1) {

vWalls = new boolean[horiz - 1][vert];

for (i = 0; i < horiz - 1; i++) {

for (j = 0; j < vert; j++) {

vWalls[i][j] = true;

}

}

}

// this will calculate the number of walls in the maze. which is equal to

// total horizontal walls + total vertical walls

// you can derive this by drawing some examples.

int walls=(vWalls.length*(horizontalSize))+(hWalls.length*(verticalSize-1));

// now we will store three information of all the walls in below 2D array.

// (arr[k][0],arr[k][1]) will tell the position of the wall at kth index in the array

// arr[k][2] will tell is the wall is horizontal or vertical. We will store 0 if the wall is

// horizontal and 1 if the wall is vertical

int array[][]=new int[walls][3];

int k=0;

if (vert > 1) {

for (j = 0; j < vert - 1; j++) {

for (i = 0; i < horiz; i++) {

array[k][0]=i;

array[k][1]=j;

array[k][2]=0; //0 is horizontal

k++;

}

}

}

// these for loops will run for evrey wall in the maze and store its position and horizontal or vertical status

// of that wall

if (horiz > 1) {

for (i = 0; i < horiz - 1; i++) {

for (j = 0; j < vert; j++) {

array[k][0]=i;

array[k][1]=j;

array[k][2]=1; //1 is vertical

k++;

}

}

}

for (int a=walls; a>0; a--) {

int randInt=randInt(a);

int holder[]=new int[3];

holder[0]=array[randInt][0];

holder[1]=array[randInt][1];

holder[2]=array[randInt][2];

array[randInt][0]=array[a-1][0];

array[randInt][1]=array[a-1][1];

array[randInt][2]=array[a-1][2];

array[a-1][0]=holder[0];

array[a-1][1]=holder[1];

array[a-1][2]=holder[2];

}

//create an instance of a disjoint set with a size euqal to the number of walls

// present in the maze

DisjointSets set=new DisjointSets(horiz*vert);

for (int a=0; a

//iterate over all the walls now.

// store the position of the current wall in (x,y)

//check if the current wall is horizontal or vertical

//find the position of the cell in the maze. Calculate the position of left cell

// and right cell to that vertical wall and call union function on both of the cells

//set that particular wall to false because you've already joined the two cells

//adjacent to that vertical wall.

//Now, do the same with the horizontal wall. Just, pick up the cells above it and below it

//and set the value false to that horizontal wall in the maze.

//You don't have to worry about creating a cycle inside a maze during the deletion

// of the walls because we are using disjoint sets. There won't be more than one path

//between two nodes in the disjoint sets.

int x=array[a][0];

int y=array[a][1];

if (array[a][2]==1) { //0 is horizontal

int l_map=x+(y*horiz);

int r_map=l_map+1;

int left=set.find(l_map);

int right=set.find(r_map);

if (left!=right) {

set.union(left,right);

vWalls[x][y]=false;

}

} else if (array[a][2]==0) { //1 is vertical

int t_map=x+(y*horiz);

int top=set.find(t_map);

int b_map=t_map+horiz;

int bot=set.find(b_map);

if (top!=bot) {

set.union(top,bot);

hWalls[x][y]=false;

}

}

}

}

/**

* You should go through all the walls of

* the maze in random order, and remove any wall whose removal will not

* create a cycle. Use the implementation of disjoint sets provided in the

* set package to avoid creating any cycles.

*

* Note the method randInt() further below, which generates a random

* integer. randInt() generates different numbers every time the program

* is run, so that you can make lots of different mazes.

**/

/**

* toString() returns a string representation of the maze.

**/

public String toString() {

int i, j;

String s = "";

// Print the top exterior wall.

for (i = 0; i < horiz; i++) {

s = s + "--";

}

s = s + "- |";

// Print the maze interior.

for (j = 0; j < vert; j++) {

// Print a row of cells and vertical walls.

for (i = 0; i < horiz - 1; i++) {

if (vWalls[i][j]) {

s = s + " |";

} else {

s = s + " ";

}

}

s = s + " | +";

if (j < vert - 1) {

// Print a row of horizontal walls and wall corners.

for (i = 0; i < horiz; i++) {

if (hWalls[i][j]) {

s = s + "-+";

} else {

s = s + " +";

}

}

s = s + " |";

}

}

// Print the bottom exterior wall. (Note that the first corner has

// already been printed.)

for (i = 0; i < horiz; i++) {

s = s + "--";

}

return s + " ";

}

/**

* horizontalWall() determines whether the horizontal wall on the bottom

* edge of cell (x, y) exists. If the coordinates (x, y) do not correspond

* to an interior wall, true is returned.

**/

public boolean horizontalWall(int x, int y) {

// if the coordinates given in this function is outside of the maze

//checking conditions for outsidemaze points in case of horizontal walls

if ((x < 0) || (y < 0) || (x > horiz - 1) || (y > vert - 2)) {

return true;

}

//return the presence of the wall if it is still present or not in the maze

return hWalls[x][y];

}

/**

* verticalWall() determines whether the vertical wall on the right edge of

* cell (x, y) exists. If the coordinates (x, y) do not correspond to an

* interior wall, true is returned.

**/

public boolean verticalWall(int x, int y) {

// if the coordinates given in this function is outside of the maze

//checking conditions for outsidemaze points in case of vertical walls

if ((x < 0) || (y < 0) || (x > horiz - 2) || (y > vert - 1)) {

return true;

}

return vWalls[x][y];

}

/**

* randInt() returns a random integer from 0 to choices - 1.

**/

private static int randInt(int choices) {

if (random == null) { // Only executed first time randInt() is called

random = new Random(); // Create a "Random" object with random seed

}

int r = random.nextInt() % choices; // From 1 - choices to choices - 1

if (r < 0) {

r = -r; // From 0 to choices - 1

}

return r;

}

/**

* diagnose() checks the maze and prints a warning if not every cell can be

* reached from the upper left corner cell, or if there is a cycle reachable

* from the upper left cell.

**/

protected void diagnose() {

if ((horiz < 1) || (vert < 1) || ((horiz == 1) && (vert == 1))) {

return; // There are no interior walls

}

boolean mazeFine = true;

// Create an array that indicates whether each cell has been visited during

// a depth-first traversal.

boolean[][] cellVisited = new boolean[horiz][vert];

// Do a depth-first traversal.

if (depthFirstSearch(0, 0, STARTHERE, cellVisited)) {

System.out.println("Your maze has a cycle.");

mazeFine = false;

}

// Check to be sure that every cell of the maze was visited.

outerLoop:

for (int j = 0; j < vert; j++) {

for (int i = 0; i < horiz; i++) {

if (!cellVisited[i][j]) {

System.out.println("Not every cell in your maze is reachable from " +

"every other cell.");

mazeFine = false;

break outerLoop;

}

}

}

if(mazeFine) {

System.out.println("Congrats! you've got the required maze");

}

}

/**

* depthFirstSearch() does a depth-first traversal of the maze, marking each

* visited cell. Returns true if a cycle is found.

*/

protected boolean depthFirstSearch(int x, int y, int fromWhere,

boolean[][] cellVisited) {

boolean cycleDetected = false;

cellVisited[x][y] = true;

// Visit the cell to the right?

if ((fromWhere != FROMRIGHT) && !verticalWall(x, y)) {

if (cellVisited[x + 1][y]) {

cycleDetected = true;

} else {

cycleDetected = depthFirstSearch(x + 1, y, FROMLEFT, cellVisited) ||

cycleDetected;

}

}

// Visit the cell below?

if ((fromWhere != FROMBELOW) && !horizontalWall(x, y)) {

if (cellVisited[x][y + 1]) {

cycleDetected = true;

} else {

cycleDetected = depthFirstSearch(x, y + 1, FROMABOVE, cellVisited) ||

cycleDetected;

}

}

// Visit the cell to the left?

if ((fromWhere != FROMLEFT) && !verticalWall(x - 1, y)) {

if (cellVisited[x - 1][y]) {

cycleDetected = true;

} else {

cycleDetected = depthFirstSearch(x - 1, y, FROMRIGHT, cellVisited) ||

cycleDetected;

}

}

// Visit the cell above?

if ((fromWhere != FROMABOVE) && !horizontalWall(x, y - 1)) {

if (cellVisited[x][y - 1]) {

cycleDetected = true;

} else {

cycleDetected = depthFirstSearch(x, y - 1, FROMBELOW, cellVisited) ||

cycleDetected;

}

}

return cycleDetected;

}

/**

* main() creates a maze of dimensions specified in the x,y , prints

* the maze, and runs the diagnostic method to see if the maze is good.

*/

public static void main(String[] args) {

int x = 10;

int y = 10;

Maze maze = new Maze(x, y);

System.out.print(maze);

maze.diagnose();

}

}