Overview: The Disjoint Set data structure will be used in the creation of a maze.

Details: Write a program to generate and display a maze The program may either be a command-line program that generates a character-based maze, or it may be a GUI program that draws the maze in a window. The user should be able to specify the number of rows and columns in the maze, at least up to 20x20. You must use the DisjSet class to implement the algorithm. The DisjSet class must be used as given without making modifications to it.

// DisjSets class // // CONSTRUCTION: with int representing initial number of sets // // ******************PUBLIC OPERATIONS********************* // void union( root1, root2 ) --> Merge two sets // int find( x ) --> Return set containing x // ******************ERRORS******************************** // No error checking is performed

/** * Disjoint set class, using union by rank and path compression. * Elements in the set are numbered starting at 0. * @author Mark Allen Weiss */ public class DisjSets { /** * Construct the disjoint sets object. * @param numElements the initial number of disjoint sets. */ public DisjSets( int numElements ) { s = new int [ numElements ]; for( int i = 0; i < s.length; i++ ) s[ i ] = -1; }

/** * Union two disjoint sets using the height heuristic. * For simplicity, we assume root1 and root2 are distinct * and represent set names. * @param root1 the root of set 1. * @param root2 the root of set 2. */ public void union( int root1, int root2 ) { if( s[ root2 ] < s[ root1 ] ) // root2 is deeper s[ root1 ] = root2; // Make root2 new root else { if( s[ root1 ] == s[ root2 ] ) s[ root1 ]--; // Update height if same s[ root2 ] = root1; // Make root1 new root } }

/** * Perform a find with path compression. * Error checks omitted again for simplicity. * @param x the element being searched for. * @return the set containing x. */ public int find( int x ) { if( s[ x ] < 0 ) return x; else return s[ x ] = find( s[ x ] ); }

private int [ ] s;

// Test main; all finds on same output line should be identical public static void main( String [ ] args ) { int NumElements = 128; int NumInSameSet = 16;

DisjSets ds = new DisjSets( NumElements ); int set1, set2;

for( int k = 1; k < NumInSameSet; k *= 2 ) { for( int j = 0; j + k < NumElements; j += 2 * k ) { set1 = ds.find( j ); set2 = ds.find( j + k ); ds.union( set1, set2 ); } }

for( int i = 0; i < NumElements; i++ ) { System.out.print( ds.find( i )+ "*" ); if( i % NumInSameSet == NumInSameSet - 1 ) System.out.println( ); } System.out.println( ); } }