Please read the remarks about programming problems for this course.

Maze construction is an application of the disjoint-set data structure. In this assignment you will develop the disjoint-set abstract data type (ADT), and then use your disjoint-set ADT to assist in building a graphical maze. This assignment has three parts:

1. Your maze building program will need to draw lines within a graphics window. First you must obtain the libraries needed to do the graphics. See Step #2 in this CPTR 124 Lab assignment. Ensure that you place the files in their proper places. If you are using a Mac or Linux, the task is much simpler, as you have only one file to manage, and it can go in your build directory. (If you are running Windows and wish to consider options other than Visual Studio, I can provide a turn-key MinGW distribution that "just works.") You can check to see if everything is installed correctly and your build system successfully builds a graphical program by testing it with the program drawgrid.cpp. You will know everything works if the program displays the following image:
   

   If you are using a Mac, the command line to build your graphical program is

   clang++ -Wall -std=c++14 -framework OpenGL -framework GLUT drawgrid.cpp
   If you are a Mac user and using an IDE like Xcode or Qt Creator and you do not wish to compile in a Terminal window, you will need to configure your project properties to include the OpenGL and GLUT libraries in your build environment.

   Visual Studio users need do nothing special if all the files are in the appropriate locations.

2. Implement a disjoint-set ADT. Name your new class DisjointSet. Your DisjointSet class must support the following operations:
   • a constructor that accepts the number of elements in the set and initializes all the elements to be in their own individual equivalence classes of size one,
   • a Find method that returns the equivalence class (representative element) of an element,
   • a Union method that accepts two set elements and merges their equivalence classes,
   • a Split method that partitions the set into blocks of size one (all elements in their own equivalence class, unrelated to any other elements in the set), and
   • a Cardinality method that returns the number of equivalence classes in the set.

3. Use your DisjointSet ADT to construct a graphical puzzle. You program should display a 25x40 maze as follows:
   

   Use the algorithm we considered in class. First begin with a proto-puzzle in which no room is connected to any other room. This corresponds to a disjoint-set in which the size of all the equivalence classes is one. (If drawn at this point, the unsolvable maze would look like the output of drawgrid.cpp.) Then enter a loop that continues until only one equivalence class remains, the one that contains all the elements in the set. Each time through the loop your algorithm should select a room at random and also select a neighboring room (north, south, east, or west) at random. If these two rooms are not part of the same equivalence class, union them; otherwise, do not union them. Eventually all the rooms will be in the same equivalence class which means there will exist exactly one path from the entrance to the exit.

   Even though the grid is two dimensional, you probably will find it easier to represent it as a linear sequence. Be sure to take note in class for more information about how to map a room to an index within the sequence (and vice-versa) and how to compute the indices of its neighbors.

When you are satisfied that your code is complete and correct, consolidate all your code into one source file named with your last name; for example, halterman.cpp. It should be possible to compile this single source file to produce the executable. Submit this source file to eclass.