The objectives for this lab are to:

• Understand how data structures store generic data types (i.e., templates in C++).
• Work with CircularArrayList, our third implementation of the List interface
• Gain experience with memory management by expanding the capacity of a CircularArrayList
• Understand the interface and implementations for the Stack and Queue data structures
• Implementing DFS and BFS search algorithms using stacks and queues
• Gain experience with dynamically allocating two dimensional arrays
• Utilize gdb to enhance your debugging skills
• Utilizing modular testing to evaluate your programs

To accomplish these goals, your lab consists of three parts:

1. Implement the expandCapacity function for the CircularArrayList from lecture.
   1. Test your CircularArrayList thoroughly.
2. Implement a templated stack and a templated queue.
   1. Thorougly test your stack and queue implementations.
3. Create a program to search for a way to navigate through a maze. You will first implement Maze and Position classes that we have declared, and then use your stack and queue to implement depth-first search and breadth-first search for the Maze.

The first two parts of this lab are substantially shorter than the last. The first part requires you to implement just one function for the CircularArrayList class. Although you are implementing both a stack and a queue for the second part, both of those implementations are short because each stack and queue function is a one-line call to a function of an existing list. You should work with a partner on this lab. If you want to work alone on this lab, you must email me by Wednesday 11:59PM. Note: students who want partners take priority, so if I need to, I might pair you with such a student.

Note: despite my warnings about the work involved, this is a one week lab. This lab is not more work than usual if you proceed incrementally, test each component thoroughly, and spend time thinking about how to design the third part before jumping right in. I am extending the deadline because of fall break, and because of midterms the week after. You shouldn't need to work on this over break, although you are welcome to do so. To prevent students from not starting this lab until October 25, the first two parts of this lab are due Friday before you go on break.

As usual, run update35 to obtain the cs35/labs/05 directory and the starting files for this lab.

Relevant Files (those in blue require modification):

• list.h - templated List interface
• circularArrayList.h - declaration of CircularArrayList which implements the List interface
• circularArrayList-inl.h - inline implementation of CircularArrayList. You must implement expandCapacity()
• testList.cpp - thoroughly test your CircularArrayList implementation using modular testing and assert commands

The CircularArrayList class can currently hold only a fixed number (10) of items. You should implement the private expandCapacity() function to expand the array when the array is full. The basic outline for doing this is:

1. Allocate memory on the heap for a new, bigger array.
2. Copy items from the old array to the new array.
3. Update the CircularArrayList class data (such as size, headPos, capacity) as needed.
4. Free the memory for the old array.
5. Point the array pointer to the new array.

Please test your expandCapacity function before starting the next portion of the lab. A good way to test this function is to add a moderately large (100s) number of items to the list, then remove some (~half) of those items, and then add a large number of new items to the list. (This should not be the only test you perform. The goal here is to make sure that your expandCapacity function works correctly for any list state, not just when items have been added -- but not removed -- from the list). In past semesters, this was the most common source of points lost on this lab.

Relevant Files (those in blue require modification):

• stack.h - templated Stack interface
• queue.h - templated Queue interface
• arrayStack.h (-inl.h) OR linkedStack.h (-inl.h) - inline implementation of Stack ADT using either CircularArrayList or LinkedList
• arrayQueue.h (-inl.h) OR linkedQueue.h (-inl.h) - inline implementation of Queue ADT using either CircularArrayList or LinkedList
• testStackQueue.cpp - thoroughly test your implementations using modular testing and assert commands
• Makefile - be sure to add your new implementations to the list of header files

Complete a stack and queue implementation, based on an existing list implementation, that inherits from and implements our Stack and Queue interfaces. We've declared an ArrayStack class for you to implement; if you want, though, you may ignore our definition and instead implement a LinkedStack class. You must declare and implement either an ArrayQueue or LinkedQueue class that inherits from the Queue interface. You will be not given a starting point for the Queue implementation, so be sure to create your own solution in an appropriately named file e.g. linkedQueue.h or arrayQueue.h.

Since the list data structure performs error checking for you (e.g., throw runtime_error), you do not need to worry about handling errors in your stack or queue implementations. For example, if a user attempts to dequeue an empty list, the underlying list will throw an error for attempting to remove on an empty list.

Please thoroughly test your stack and queue implementations before proceeding to the third part of this lab. We assure you that you do not want to debug your stack and queue implementations using your depth-first and breadth-first search programs.

Image taken from Trienen Farms in Lodi, Wisconsin. Each year, they design a maze based on some mathematical principles such as the golden ratio.

Relevant Files (those in blue require modification):

• position.h,position.cpp - Position class, describing one location in the maze
• maze.h,maze.cpp - Maze class, describing the entire maze and important operations
• solveMaze.cpp - main program where you will read in data and perform both dept-first and breadth-first search
• input/ - directory of test mazes

In this part of the lab you will implement two search algorithms -- depth-first search and breadth-first search -- for finding a path through a maze.

Each maze is a rectangular space with an entrance at the upper left-hand corner, an exit at the lower right-hand corner, and some internal walls. Your algorithm must find a path through a given maze starting from the entrance and finishing at the exit, without passing through any walls. The path may move through the maze by going up, down, left, or right -- but not diagonally.

For example, here is one depiction of a 5x5 maze:

  start --> * * * O O
            1 1 * 1 1
            O * * O O
            O * 1 1 1
            O * * * * <-- finish

  Path:  (0,0)  (0,1)  (0,2)  (1,2)  (2,2)  (2,1)  (3,1)
         (4,1)  (4,2)  (4,3)  (4,4)

The 0s represent open spaces in the maze and the 1s represent walls. The asterisks represent a path from the entrance to the exit of the maze. Locations in the maze are indexed by row and column, with (0,0) always being the entrance in the upper-left corner, and the exit always being (rows-1,columns-1) in the lower-right corner. (In this case, the 5x5 maze, the exit is at (4,4).)

Here are two example program executions, one with a successful search and one for which the maze had no solution:

  $ ./solveMaze
  How many rows are in the maze?  5
  How many columns are in the maze?  5
  How many walls does the maze have?  7

  Please enter the row and column position for each of the 7 walls:
  1 1
  2 1
  3 1
  1 3
  2 3
  3 3
  4 3
  
  start --> 0 0 0 0 0 
            0 1 0 1 0 
            0 1 0 1 0 
            0 1 0 1 0 
            0 0 0 1 0 <-- finish

  Searching with stack... found a path.
  The path has length 17.
  Path:  (0,0)  (1,0)  (2,0)  (3,0)  (4,0)  (4,1)  (4,2)
         (3,2)  (2,2)  (1,2)  (0,2)  (0,3)  (0,4)  (1,4)
         (2,4)  (3,4)  (4,4)
  
   start --> * O * * * 
             * 1 * 1 * 
             * 1 * 1 * 
             * 1 * 1 * 
             * * * 1 * <-- finish

  Searching with queue... found a path.
  The path has length 9.
  Path:  (0,0)  (0,1)  (0,2)  (0,3)  (0,4)  (1,4)  (2,4)
         (3,4)  (4,4)

   start --> * * * * * 
             O 1 O 1 * 
             O 1 O 1 * 
             O 1 O 1 * 
             O O O 1 * <-- finish

  $ ./solveMaze
  How many rows are in the maze?  5
  How many columns are in the maze?  5
  How many walls does the maze have?  4

  Please enter the row and column position for each of the 4 walls:
  3 0
  2 1
  1 2
  0 3

   start --> O O O 1 O 
             O O 1 O O 
             O 1 O O O 
             1 O O O O 
             O O O O O <-- finish

  Searching with stack... no path was found.
  Searching with queue... no path was found.

Note: Below is a guide on how to proceed with implementation. You are expected to employ modular testing. While I haven't provided a simple test file this week, you should be creating test programs to make sure each of your implementations are working in isolation. The ninjas cannot and will not be able to help you if you are using the main solveMaze program as your testing method.

We have declared Maze and Position classes to help represent a maze. You should start by implementing these classes:

1. The Position class represents one position in the maze; i.e., an x and y position in the maze. It stores relevant information for that position including x and y, whether it is a wall, whether is is on the found path, and the previous Position on the path.

   It has two constructors: a primary constructor that accepts an x and y value as arguments and constructs a Position for that position. All other class variables should be given default values for a Position (e.g., it is not a wall, not on the path, has not previous location). The second constructor is a default constructor that should set x and y to some invalid maze position, such as (-1,-1).

   Using position.h as a guide, you should implement all the methods for the Position class one-by-one in the position.cpp file. Most of these are very simple, one or two line methods.

   Stop and test: Can you construct a single Position? Can you access the x and y value? Can you create a list of Positions? Are you correctly storing information about the wall? the path?

   
   
2. The Maze class represents the rectangular grid and walls of a maze. It stores the number of rows and columns in the maze, and a 2-dimensional Position array marking the positions of walls in the maze. You should complete the Maze by implementing the constructor as well as access and update functions that we've declared. Be sure to look closely at your class examples and notes for allocating a two-dimensional array on the heap.

   Most of the Maze functions are simple one- or two-line functions. The getNeighbors(p) function is slightly more complicated: it returns a list of all valid non-wall neighbors for a given position p. A position is a valid non-wall neighbor of p if (1) it is up, down, left, or right of p, (2) it is within the bounds of the maze, and (3) it is not a wall.

   Stop and test: Can you create a simple Maze? Try printing out the values at each grid location. What do you get if you call getNeighbors? Does it return the correct number and values of the numbers of a grid point?

3. After you have thoroughly tested your Position and Maze implementations, implement breadth-first and depth-first search in solveMaze.cpp. For each search algorithm you'll need to keep track of a data structure (a queue or stack) containing the Positions left to explore as well as a Maze object containing the necessary information to navigate the maze
You will need to carefully think about how to use the Maze and associated Position objects to keep track of what points in the maze have been visited and where they have been visited from.

With this data, the following pseudocode describes both breadth-first and depth-first search:

  Mark start position as visited.
  Add start position to data structure.
  while (data structure is not empty): 
     current = Remove position from data structure.
     if (current is exit):
         break
     for (each valid neighbor of current):
         if (neighbor has not been visited):
             Mark neighbor as visited.
             Record neighbor as visited from current.
             Add neighbor to the data structure.

After this algorithm is complete current will be the maze's exit position if the search found a path, but will be some other position if the search failed. If the search succeeded you can reconstruct the path by checking from which position the exit was visited, and then checking from which position that position was visited, and so on, until you reach the maze entrance. You should print the maze and the path positions as in the examples above using the print method of the Maze class.

Testing your main program: I have provided three test files. You can use cin to obtain input for your program and then type in the values in the test file. This can get tedious, so a better strategy is to pipe in your input:

$ ./solveMaze < inputs/test0.in 

The direction of the bracket is important - this tells unix to use the file test0.in as the standard input. cin will read the values as if they were typed in by a user. Alternatively, feel free to use file i/o as demonstrated in previous labs. You'll have to take the file name as input to the program:

$ ./solveMaze inputs/test0.in 

See me if you are interested in pursuing this.

Working executable For an example working maze solver, see the following program:

$ ~brody/public/cs35/maze/solveMaze

Once you are satisfied with your program, hand it in by typing handin35 at the unix prompt.

You may run handin35 as many times as you like, and only the most recent submission will be recorded. This is useful if you realize after handing in some programs that you'd like to make a few more changes to them.