C++ assignmet Maze Stack
f.a.qx8t
lab06.rarlab06/Cell.cpp
#include "Cell.h" Cell::Cell(int r, int c) { dir = DOWN; //the first direction that will be tried after this location row = r; col = c; } Cell::~Cell() {} int Cell::getRow() { return row; } int Cell::getCol() { return col; } Direction Cell::getDir() { return dir; } Cell* Cell::nextCell() { Cell* cell = NULL; if (dir == DOWN) //down was a dead end, move right next { cell = new Cell(row + 1, col); dir = RIGHT; } else if (dir == RIGHT) //move up { cell = new Cell(row, col + 1); dir = UP; } else if (dir == UP) //move left { cell = new Cell(row - 1, col); dir = LEFT; } //all 4 directions have been tried //if we come back here for another direction, this cell is invalid and must be discarded else if (dir == LEFT) { cell = new Cell(row, col - 1); dir = DEAD_END; } return cell; //returns NULL if all options have been attempted }
lab06/Cell.h
#if !defined (NULL) #define NULL 0 #endif #if !defined (DIRECTION) #define DIRECTION enum Direction {DOWN = 1, RIGHT, UP, LEFT, DEAD_END}; #endif #if !defined (CELL_H) #define CELL_H class Cell { private: int row; int col; Direction dir; public: Cell(int row, int col); virtual ~Cell(); int getRow(); int getCol(); Direction getDir(); Cell* nextCell(); }; #endif
lab06/lab06.pdf
Laboratory 06: Maze Stack Download the following files:
Lab06Files.zip StackLinked.h Cell.h Cell.cpp Maze.h Maze.cpp MazeGUI.h MazeGUI.cpp
StackLinked
Complete StackLinked.h (push, pop, peek).
Cell
Take a look at Cell.cpp. A Cell object represents a location in the Maze. Therefore, a Cell needs to store the row and column in the Maze that it corresponds to. From a given Cell location, a move can be attempted in one of the four orthogonal Directions DOWN, RIGHT, UP, or LEFT, attempted in that order. A Cell then also needs to store the next Direction to try so that the same Direction is not attempted more than once. When a Cell is initially created, the next Direction to try is DOWN. If that Direction eventually leads to a dead end, RIGHT will be tried, and so forth.
The nextCell() method creates and returns the Cell neighboring the current Cell location in the specified Direction. That is, one will be added to the row or col as appropriate when creating the neighboring Cell. The starting direction for this new Cell is again DOWN. At the same time, the next Direction to try from the current Cell is updated. If all Directions from the current Cell have been attempted and have led to dead ends, NULL is returned.
Maze
The Maze is simply a Matrix with 0 (WALL), 1 (SPACE), 2 (TRIED), 3 (BACKTRACK), or 4 (PATH) as its possible values. The Maze is built using the text file maze.txt.
If the Direction of the Cell on top of the Stack (top_cell) is not DEAD_END, obtain the Cell corresponding to an as yet untried row and col by calling the nextCell() method on top_cell. If the newly generated Cell does not contain a valid row and col (the row and col is a WALL or has already been TRIED, i.e. the row and col is not SPACE), delete it and ask top_cell for the nextCell() to try. Otherwise, push the new Cell onto the Stack and start processing it in the same manner.
If all four Directions of the Cell on the top of the Stack have been tried (Direction == DEAD_END), the Cell represents a dead end, so pop that Cell and delete it.
You may need to pop several Cells from the top of the Stack when a DEAD_END has been reached. This is called backtracking and is a very powerful technique for solving complex problems. The Maze location needs to be updated with BACKTRACK for each location that you pass through while backtracking. Complete the following method to handle any necessary backtracking:
Cell* processBackTrack(StackLinked<Cell>* stack) //pops all DEAD_END cells from the stack
If there is a solution to the Maze, your Stack will eventually find it. Complete the following method to determine if the Maze has been solved:
bool isSolved(Cell* curr_cell, StackLinked<Cell>* stack) //determines if the bottom right has been reached
If there is a solution to the Maze, the successful traversal of the Maze is completely stored on the Stack in the form of Cells that retrace the steps from the end of the Maze back to the beginning. Any Cells corresponding to DEAD_ENDs have already been popped, so your Stack is the solution. A maze with no solution should have an empty Stack. Complete the following method to update the Maze, showing the solution PATH:
void processSolution(StackLinked<Cell>* stack) //pops solution off the Stack, updating the Maze with PATH
The below class interfaces are defined in the namespace CSC2110.
String methods String(const char* text) //constructor void displayString() int length() const char* getText() int a_to_i() float a_to_f String* i_to_a(int number) //static method String* f_to_a(float number) //static method int find(char delimiter, int start) //find the index of a particular character String* substr(int start, int end) int compare(String* other) char charAt(int index) //0-based
Tokens methods Tokens(String* str, char delimiter) //destructor does not delete the individual tokens String* getToken(int index)
int getNumTokens() void displayTokens()
ReadFile methods ReadFile(const char* file_name) String* readLine() bool eof() void close()
WriteFile methods WriteLine(String* file_name) void writeLine(String* line) void close()
Random methods (use getRandom first) static Random* getRandom() int getRandomInt(int lower, int upper) float getRandomFloat(float lower, float upper)
Keyboard methods (use getKeyboard first) static Keyboard* getKeyboard() //call this first int readInt(string prompt) int getValidatedInt(string prompt, int min, int max) double readDouble(string prompt) double getValidatedDouble(string prompt, double min, double max) String* readString(string prompt)
Integer/Double methods Integer(int val)/Double(double val) int getValue()/double getValue()
CD methods CD(String* artist, String* title, int year, int rating, int num_tracks) void displayCD() //display the current state of the CD String* getKey() void addSong(String* title, String* length) static int compare_items(CD* one, CD* two) //define how to compare CDs (in this case, by title) static int compare_keys(String* sk, CD* cd) static ListArray* readCDs(const char* file_name) //read in all of the CDs from a text file
Song methods Song(String* title, String* length) void displaySong()
lab06/Lab06Files.zip
build.bat
@echo off cls set DRIVE_LETTER=%1: set PATH=%DRIVE_LETTER%\MinGW\bin;%DRIVE_LETTER%\MinGW\msys\1.0\bin;%DRIVE_LETTER%\MinGW\gtkmm3\bin;%DRIVE_LETTER%\MinGW\gtk\bin;c:\Windows;c:\Windows\system32 set PROJECT_PATH=. make DRIVE_LETTER="%DRIVE_LETTER%" PROJECT_DIR="%PROJECT_PATH%"
maze.txt
21 31 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 1 1 1 1 1 1 1 1 1 0 1 0 1 0 1 1 1 0 1 0 1 1 1 0 1 1 1 0 1 0 0 0 0 1 0 1 0 1 0 0 0 1 0 1 0 0 0 1 0 1 0 1 0 0 0 1 0 1 0 1 0 0 1 1 1 0 1 0 1 1 1 1 1 0 1 1 1 0 1 1 1 1 1 0 1 1 1 0 1 1 1 0 0 1 0 0 0 0 0 0 0 1 0 0 0 1 0 0 0 1 0 0 0 0 0 1 0 0 0 0 0 0 0 0 1 1 1 0 1 1 1 1 1 0 1 1 1 1 1 0 1 1 1 1 1 1 1 1 1 1 1 1 1 0 0 1 0 0 0 0 0 0 0 1 0 1 0 0 0 1 0 1 0 1 0 0 0 0 0 1 0 0 0 0 0 0 1 0 1 1 1 1 1 1 1 0 1 0 1 0 1 1 1 0 1 0 1 1 1 1 1 1 1 1 1 0 0 0 0 1 0 1 0 0 0 1 0 1 0 1 0 0 0 0 0 0 0 0 0 0 0 1 0 1 0 0 0 0 1 1 1 0 1 0 1 1 1 1 1 1 1 1 1 0 1 1 1 0 1 0 1 1 1 0 1 1 1 0 0 0 0 1 0 0 0 0 0 1 0 0 0 1 0 1 0 0 0 1 0 1 0 0 0 1 0 0 0 0 0 0 1 1 1 1 1 0 1 1 1 0 1 1 1 0 1 1 1 0 1 1 1 0 1 0 1 1 1 1 1 0 0 1 0 0 0 0 0 0 0 1 0 0 0 1 0 1 0 1 0 0 0 1 0 1 0 0 0 1 0 1 0 0 1 0 1 1 1 1 1 1 1 1 1 0 1 0 1 0 1 1 1 1 1 0 1 0 1 1 1 0 1 0 0 0 0 0 0 1 0 1 0 0 0 1 0 0 0 1 0 0 0 0 0 1 0 1 0 0 0 1 0 0 0 0 1 1 1 0 1 0 1 0 1 1 1 1 1 0 1 0 1 1 1 1 1 0 1 0 1 1 1 1 1 0 0 1 0 0 0 1 0 0 0 0 0 1 0 1 0 0 0 1 0 0 0 0 0 1 0 1 0 0 0 0 0 0 1 1 1 1 1 0 1 0 1 1 1 0 1 0 1 1 1 1 1 1 1 0 1 1 1 1 1 1 1 0 0 1 0 0 0 1 0 1 0 0 0 1 0 1 0 0 0 1 0 0 0 0 0 0 0 1 0 0 0 0 0 0 1 1 1 0 1 1 1 0 1 1 1 0 1 0 1 1 1 1 1 1 1 1 1 0 1 1 1 1 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1
NextNode.h
#if !defined (NEXTNODE_H) #define NEXTNODE_H template < class T > class NextNode { private: NextNode<T>* next; T* item; public: NextNode(T* item); ~NextNode(); NextNode<T>* getNext(); void setNext(NextNode<T>* next); T* getItem(); }; template < class T > NextNode<T>::NextNode(T* itm) { item = itm; next = NULL; } template < class T > NextNode<T>::~NextNode() { item = NULL; next = NULL; } template < class T > NextNode<T>* NextNode<T>::getNext() { return next; } template < class T > void NextNode<T>::setNext(NextNode<T>* nxt) { next = nxt; } template < class T > T* NextNode<T>::getItem() { return item; } #endif
Update.h
#ifndef UPDATE_H #define UPDATE_H class Update { private: public: Update() {} virtual ~Update() {} virtual void update() = 0; }; #endif
Makefile
AutomatedMakefile = am CC = g++ FILES = EXECUTABLE = PROJECT_PATH = $(PROJECT_DIR) GTK_PATH = /$(DRIVE_LETTER)/MinGW/GTK GTKMM3_PATH = /$(DRIVE_LETTER)/MinGW/gtkmm3 INC_DIRS = -I$(PROJECT_PATH)/CSC2110 -I$(PROJECT_PATH)/GUI -I$(GTK_PATH)/include/gtk-3.0 -I$(GTK_PATH)/include/cairo -I$(GTK_PATH)/include/pango-1.0 -I$(GTK_PATH)/include/atk-1.0 -I$(GTK_PATH)/include/pixman-1 -I$(GTK_PATH)/include -I$(GTK_PATH)/include/freetype2 -I$(GTK_PATH)/include/libpng15 -I$(GTK_PATH)/include/gdk-pixbuf-2.0 -I$(GTK_PATH)/include/glib-2.0 -I$(GTK_PATH)/lib/glib-2.0/include -I$(GTKMM3_PATH)/include/gtkmm-3.0 -I$(GTKMM3_PATH)/lib/gtkmm-3.0/include -I$(GTKMM3_PATH)/include/atkmm-1.6 -I$(GTKMM3_PATH)/include/gdkmm-3.0 -I$(GTKMM3_PATH)/lib/gdkmm-3.0/include -I$(GTKMM3_PATH)/include/giomm-2.4 -I$(GTKMM3_PATH)/lib/giomm-2.4/include -I$(GTKMM3_PATH)/include/pangomm-1.4 -I$(GTKMM3_PATH)/lib/pangomm-1.4/include -I$(GTKMM3_PATH)/include/glibmm-2.4 -I$(GTKMM3_PATH)/lib/glibmm-2.4/include -I$(GTKMM3_PATH)/include/cairomm-1.0 -I$(GTKMM3_PATH)/lib/cairomm-1.0/include -I$(GTKMM3_PATH)/include/sigc++-2.0 -I$(GTKMM3_PATH)/lib/sigc++-2.0/include LIB_DIRS = -L$(PROJECT_PATH)/CSC2110 -L$(PROJECT_PATH)/GUI -L$(GTK_PATH)/lib -L$(GTKMM3_PATH)/lib LIBS = -lCSC2110 -lgui -lgtkmm-3.0 -latkmm-1.6 -lgdkmm-3.0 -lgiomm-2.4 -lpangomm-1.4 -lglibmm-2.4 -lgtk-3 -lgdk-3 -lgdi32 -limm32 -lshell32 -lole32 -Wl,-luuid -lpangocairo-1.0 -lpangoft2-1.0 -lfreetype -lfontconfig -lpangowin32-1.0 -lgdi32 -lpango-1.0 -lm -latk-1.0 -lcairo-gobject -lgio-2.0 -lcairomm-1.0 -lcairo -lsigc-2.0 -lgdk_pixbuf-2.0 -lgobject-2.0 -lglib-2.0 -lintl COMPILE = $(CC) $(INC_DIRS) -c LINK = $(CC) $(LIB_DIRS) -o all: Project Project: $(FILES) $(LINK) $(EXECUTABLE) $(FILES) $(LIBS) Cell.o: Cell.h Cell.cpp $(COMPILE) Cell.cpp
CSC2110/CD.h
#if !defined CD_H #define CD_H #include "Song.h" #include "Text.h" using CSC2110::String; #include "ListArray.h" using CSC2110::ListArray; namespace CSC2110 { class CD { private: String* artist; String* title; int year; int rating; int num_tracks; ListArray<Song>* songs; public: CD(String* artist, String* title, int year, int rating, int num_tracks); virtual ~CD(); String* getKey(); void addSong(String* title, String* length); void displayCD(); static ListArray<CD>* readCDs(const char* file_name); static int compare_items(CD* one, CD* two); static int compare_keys(String* sk, CD* cd); static char getRadixChar(CD* cd, int index); //1-based }; } #endif
CSC2110/Double.h
#if !defined (DOUBLE_H) #define DOUBLE_H namespace CSC2110 { class Double { private: double value; public: Double(double val); ~Double(); double getValue(); }; } #endif
CSC2110/HighPerformanceCounter.h
#if !defined (HIGHPERFORMANCECOUNTER_H) #define HIGHPERFORMANCECOUNTER_H namespace CSC2110 { class HighPerformanceCounter { private: double micro_spt; //micro_seconds per tick HighPerformanceCounter(); static HighPerformanceCounter* hpc; static int getTicksPerSecond(); public: virtual ~HighPerformanceCounter(); static HighPerformanceCounter* getHighPerformanceCounter(); int getCurrentTimeInTicks(); double getTimeDifferenceInMicroSeconds(int start_time, int end_time); }; } #endif
CSC2110/Integer.h
#if !defined (INTEGER_H) #define INTEGER_H namespace CSC2110 { class Integer { private: int value; public: Integer(int val); virtual ~Integer(); int getValue(); }; } #endif
CSC2110/Keyboard.h
#if !defined KEYBOARD_H #define KEYBOARD_H #include "Text.h" using CSC2110::String; #include <string> using namespace std; namespace CSC2110 { class Keyboard { private: Keyboard(); public: virtual ~Keyboard(); static Keyboard* getKeyboard(); //pre: the string (character literal) that will prompt the user for input //post: the input read from the keyboard interpreted as an int is returned int readInt(string prompt); int getValidatedInt(string prompt, int min, int max); //pre: the string that will prompt the user for input //post: the input read from the keyboard interpreted as a double is returned double readDouble(string prompt); double getValidatedDouble(string prompt, double min, double max); //pre: the string that will prompt the user for input // the string to store the user input and the length of the input storage string //post: the text read from the keyboard is copied into the storage string String* readString(string prompt); }; } #endif
CSC2110/libCSC2110.a
Keyboard.o
Matrix.o
Random.o
ReadFile.o
String.o
WriteFile.o
Tokens.o
Poly.o
CD.o
Song.o
Double.o
HighPerformanceCounter.o
Integer.o
Permutation.o
CSC2110/ListArray.h
#if !defined (LISTARRAY_H) #define LISTARRAY_H #include "ListArrayIterator.h" namespace CSC2110 { template < class T > class ListArray { private: int max_size; T** items; int sz; void arrayResize(int new_max_size); public: ListArray(); ~ListArray(); bool isEmpty(); int size(); void removeAll(); T* get(int index); void add(int index, T* item); void add(T* item); void remove(int index); void set(int index, T* item); ListArrayIterator<T>* iterator(); T** toArray(); }; template < class T > ListArray<T>::ListArray() { max_size = 10; items = new T*[max_size]; sz = 0; } template < class T > ListArray<T>::~ListArray() { delete[] items; //the items themselves are not deleted } template < class T > bool ListArray<T>::isEmpty() { return (sz == 0); } template < class T > int ListArray<T>::size() { return sz; } template < class T > //1-based T* ListArray<T>::get(int index) { T* item = NULL; if (index >= 1 && index <= sz) { item = items[index - 1]; } return item; } template < class T > void ListArray<T>::add(T* item) { add(sz + 1, item); //add the item to the end of the array list } template < class T > void ListArray<T>::add(int index, T* item) { if (index < 1 || index > sz + 1) { return; } //need more room in the array list if (sz == max_size) { arrayResize(2*max_size); } for (int i = sz; i >= index; i--) { items[i] = items[i - 1]; } items[index - 1] = item; sz++; } template < class T > void ListArray<T>::remove(int index) { if (index < 1 || index > sz) { return; } for (int i = index; i < sz; i++) { items[i - 1] = items[i]; } items[sz - 1] = NULL; sz--; /* if (sz < max_size/2 - 1) //halve the size of the array, smallest size of max_size should be 2 { arrayResize(max_size/2); } */ } template < class T > ListArrayIterator<T>* ListArray<T>::iterator() { ListArrayIterator<T>* iter = new ListArrayIterator<T>(items, sz); return iter; } template < class T > void ListArray<T>::set(int index, T* item) { //could use other methods already written, but this is more efficient if (index >= 1 && index <= sz) { items[index - 1] = item; //overwrite contents at that location } } template < class T > void ListArray<T>::arrayResize(int new_max_size) { max_size = new_max_size; T** temp = new T*[max_size]; for (int i = 0; i < sz; i++) { temp[i] = items[i]; } delete[] items; items = temp; } template < class T > void ListArray<T>::removeAll() { delete[] items; max_size = 10; items = new T*[max_size]; sz = 0; } template < class T > T** ListArray<T>::toArray() { int num_items = size(); T** to_array = new T*[num_items]; for (int i = 0; i < num_items; i++) { to_array[i] = items[i]; } return to_array; } } #endif
CSC2110/ListArrayIterator.h
#if !defined (NULL) #define NULL 0 #endif #if !defined (LISTARRAYITERATOR_H) #define LISTARRAYITERATOR_H namespace CSC2110 { template < class T > class ListArrayIterator { private: int index; int sz; T** items; public: ListArrayIterator(T** items, int size); ~ListArrayIterator(); bool hasNext(); T* next(); }; template < class T > ListArrayIterator<T>::ListArrayIterator(T** itms, int size) { items = new T*[size]; for (int i = 0; i < size; i++) { items[i] = itms[i]; //snapshot of the data } index = 1; sz = size; } template < class T > ListArrayIterator<T>::~ListArrayIterator() { delete[] items; } template < class T > bool ListArrayIterator<T>::hasNext() { return (index <= sz); } template < class T > T* ListArrayIterator<T>::next() { T* item = NULL; if (hasNext()) { item = items[index - 1]; index++; } return item; } } #endif
CSC2110/Matrix.h
#if !defined MATRIX_H #define MATRIX_H //the indices are 1-based!! namespace CSC2110 { class Matrix { private: int rows; int cols; double* mat; public: Matrix(int rows, int cols); //constructor ~Matrix(); //destructor void displayMatrix(); int getNumRows(); int getNumCols(); double getElement(int row, int col); void setElement(int row, int col, double val); Matrix* add(Matrix* other); Matrix* multiply(Matrix* other); static Matrix* readMatrix(const char* file_name); //discuss static void writeMatrix(const char* file_name); }; } #endif
CSC2110/Poly.h
#if !defined (POLY) #define POLY namespace CSC2110 { class Poly { private: int max_power; int degree; double* coeffs; public: Poly(int max_power); ~Poly(); int getDegree(); double getCoeff(int power); void setCoeff(int power, double coeff); double evaluate(double x); Poly* multiply(Poly* other); static Poly* multiply(Poly* one, Poly* two); void displayPoly(); static Poly* readPoly(const char* file_name); void writePoly(const char* file_name); }; } #endif
CSC2110/Random.h
#if !defined RANDOM_H #define RANDOM_H namespace CSC2110 { class Random { private: Random(); void randomInit(); public: virtual ~Random(); static Random* getRandom(); int getRandomInt(int lower, int upper); float getRandomFloat(float lower, float upper); }; } #endif
CSC2110/ReadFile.h
#if !defined READ_FILE_H #define READ_FILE_H #include "Text.h" #include <fstream> using namespace std; namespace CSC2110 { class ReadFile { private: ifstream* input_file; bool _eof; bool closed; public: ReadFile(const char* file_name); ~ReadFile(); CSC2110::String* readLine(); bool eof(); void close(); }; } #endif
CSC2110/Song.h
#if !defined SONG_H #define SONG_H #include "Text.h" using CSC2110::String; namespace CSC2110 { class Song { private: String* title; String* length; public: Song(String* title, String* length); virtual ~Song(); void displaySong(); }; } #endif
CSC2110/Text.h
#if !defined TEXT_H #define TEXT_H namespace CSC2110 { class String { private: const char* text; int sz; //length of string not including null terminator public: String(const char* char_array); virtual ~String(); void displayString(); int length(); const char* getText(); //add this member function char charAt(int index); int a_to_i(); float a_to_f(); static String* i_to_a(int number); static String* f_to_a(float number); //find the location of a particular character in a String and return the index if found //preconditions: // str is the String being examined for the character delimiter (str must point to a valid String) // delimiter is the character being searched for // start is the index to start the search at (the first index of the String is 0, start cannot exceed the length of the String) //postconditions: // if the preconditions are met, the index of the first delimiter encountered at or after the start index is returned // if the delimiter is not present in the String at index start or later, -1 is returned // if the preconditions are not met, no guarantees on output are made int find(char delimiter, int start); //creates a new String that is extracted from an existing String with characters specified by the start and end indices //preconditions: // str is the String from which the substring will be extracted (str must point to a valid String) // start and end are the indices used to create the substring // start must be less than or equal to end, start must be >= 0, end must be >= 0, end < the length of the String //postconditions: // if the preconditions are met, the String extracted from the parameter String // that starts at index start and ends at index end is created and returned // the original string is unaffected String* substr(int start, int end); //need to document that this compare only has three possible return values (-1, 0, 1) int compare(String* other); }; } #endif
CSC2110/Tokens.h
#if !defined TOKENS_H #define TOKENS_H #include "Text.h" using CSC2110::String; namespace CSC2110 { class Tokens { private: String** tokens; int max_tokens; int sz; void addToken(String* str); //requires a resizing check void resize(); public: Tokens(String* str, char delimiter); ~Tokens(); //Tokens is not responsible for deleting each token void displayTokens(); String* getToken(int index); //returns a specifically requested token int getNumTokens(); }; } #endif
CSC2110/WriteFile.h
#if !defined WRITE_FILE #define WRITE_FILE #include "Text.h" using CSC2110::String; #include <fstream> using namespace std; namespace CSC2110 { class WriteFile { private: ofstream* output_file; bool closed; public: WriteFile(const char* file_name); ~WriteFile(); void writeLine(String* line); void close(); }; } #endif
GUI/Circle.h
#ifndef CIRCLE_H #define CIRCLE_H #include "Color.h" #include "../CSC2110/Text.h" #include <gtkmm.h> class Circle { private: int radius; Color* color; CSC2110::String* text; static const float PI2 = 6.283854; public: Circle(Color* color, int radius, CSC2110::String* text); ~Circle(); void draw(Cairo::RefPtr<Cairo::Context> cr, int x, int y); }; #endif
GUI/Color.h
#ifndef COLOR_H #define COLOR_H class Color { private: double red; double green; double blue; double alpha; double clampColor(double c); void clamp(double r, double g, double b, double a); public: Color(double r, double g, double b, double a); Color(double r, double g, double b); ~Color(); double getRed(); double getGreen(); double getBlue(); double getAlpha(); void setRed(double r); void setGreen(double g); void setBlue(double b); void setAlpha(double a); }; #endif
GUI/Drawable.h
#ifndef DRAWABLE_H #define DRAWABLE_H #include <cairomm/context.h> #include <gtkmm/drawingarea.h> class Drawable { private: public: Drawable() {}; virtual ~Drawable() {}; virtual void draw(Cairo::RefPtr<Cairo::Context> cr, int width, int height) = 0; virtual void mouseClicked(int x, int y) = 0; }; #endif
GUI/DrawPanel.h
#ifndef DRAWPANEL_H #define DRAWPANEL_H #include "Drawable.h" #include <cairomm/context.h> #include <gtkmm/drawingarea.h> class DrawPanel : public Gtk::DrawingArea { private: int width; int height; Drawable* drawable; virtual void drawBackground(Cairo::RefPtr<Cairo::Context> cr); public: DrawPanel(int width, int height, Drawable* d); virtual ~DrawPanel(); virtual void render(); virtual void render(const Cairo::RefPtr<Cairo::Context>& cr); virtual bool on_button_press_event(GdkEventButton* event); virtual bool on_draw(const Cairo::RefPtr<Cairo::Context>& cr); //virtual bool on_key_press_event(GdkEventKey* event); protected: //override default signal handler }; #endif
GUI/ImageLoader.h
#ifndef IMAGELOADER_H #define IMAGELOADER_H #include <gtkmm/drawingarea.h> class ImageLoader { public: static Glib::RefPtr<Gdk::Pixbuf> loadImageRGB(const char* id); static Glib::RefPtr<Gdk::Pixbuf> loadImageRGBA(const char* id); }; #endif
GUI/libgui.a
Color.o
Drawable.o
DrawPanel.o
Line.o
Rect.o
Circle.o
ImageLoader.o
GUI/Line.h
#if !defined (LINE_H) #define LINE_H #include "Color.h" #include <gtkmm.h> class Line { private: Color* color; double line_width; public: Line(Color* color, double line_width); ~Line(); void draw(Cairo::RefPtr<Cairo::Context> cr, int x1, int y1, int x2, int y2); }; #endif
GUI/Rect.h
#ifndef RECT_H #define RECT_H #include "Color.h" #include <gtkmm.h> class Rect { private: int width; int height; Color* color; public: Rect(Color* color, int width, int height); virtual ~Rect(); void draw(Cairo::RefPtr<Cairo::Context> cr, int x, int y); }; #endif
CSC2110/Permutation.h
#if !defined (PERMUTATION_H) #define PERMUTATION_H #include "ListArray.h" using CSC2110::ListArray; #include "Integer.h" using CSC2110::Integer; #include "Random.h" using CSC2110::Random; namespace CSC2110 { class Permutation { private: int r; ListArray<Integer>* numbers; Random* random; public: Permutation(int r, int n); virtual ~Permutation(); int next(); }; } #endif
lab06/Maze.cpp
#include "Maze.h" #include "Color.h" #include "Rect.h" #include <windows.h> //for the sleep function #include <iostream> using namespace std; Maze::Maze(Matrix* mz) { maze = mz; height = maze->getNumRows(); width = maze->getNumCols(); WALL = 0; SPACE = 1; TRIED = 2; BACKTRACK = 3; PATH = 4; } Maze::~Maze() { delete maze; } void Maze::addListener(Update* g) { gui = g; } bool Maze::solve() { bool done = traverse(); return done; } //backing through the maze, setting the color to BACKTRACK Cell* Maze::processBackTrack(StackLinked<Cell>* stack) { //DO THIS //you may need to back through several cells Cell* top_cell = stack->peek(); //top_cell is NULL if the stack is empty //top_cell's direction is DEAD_END if you need to keep backtracking while ( ) //need to back track { //remove the cell and set the maze location to BACKTRACK (the maze is a Matrix) //look at the next cell Sleep(75); //slow down the maze traversal gui->update(); //update whenever the color of a cell has been changed } return top_cell; } bool Maze::isSolved(Cell* curr_cell, StackLinked<Cell>* stack) { //DO THIS //get row and col from curr_cell //have you solved the maze? (check that we are at the bottom right maze location and that it is a SPACE if ( ) { //set the maze location to TRIED //push curr_cell gui->update(); //return the appropriate boolean } //return the appropriate boolean } //backing through the maze, setting the solution color to PATH void Maze::processSolution(StackLinked<Cell>* stack) { //DO THIS //the stack has the solution path stored while( ) { //get the next cell from the stack //update the maze location to PATH gui->update(); } } bool Maze::traverse() { //DO THIS //complete several sections in this method bool done = false; //assume we are not done unless proven otherwise StackLinked<Cell> stack; maze->setElement(1, 1, TRIED); gui->update(); Cell* start_cell = new Cell(1, 1); stack.push(start_cell); //start from the top left corner while(!stack.isEmpty()) { Cell* top_cell = processBackTrack(&stack); if (top_cell == NULL) break; //no solution (back tracked all the way to the beginning) //call a method in the Cell class to give you a new Cell in a new direction relative to top_cell (initially, DOWN) //DO THIS Cell* curr_cell = //does this new Cell solve the maze? done = isSolved(curr_cell, &stack); if (done) break; //DO THIS //get the row and col from curr_cell int row = int col = //check that the current maze location corresponds to SPACE, otherwise delete it if ( ) { //update the maze location to TRIED //put the cell on the stack (move forward through the maze) Sleep(75); //slow down the maze traversal gui->update(); } else //look for a different route { //DO THIS //delete the cell } } //did we make it to the bottom right? if (done) { processSolution(&stack); } else { cout << "No solution." << endl; } return done; } void Maze::mouseClicked(int x, int y) {} void Maze::draw(Cairo::RefPtr<Cairo::Context> cr, int width, int height) { int rows = maze->getNumRows(); int cols = maze->getNumCols(); int cell_width = (int) (((double) width)/cols + 0.5); int cell_height = (int) (((double) height)/rows + 0.5); Color red(1.0, 0.0, 0.0); Rect redRect(&red, cell_width, cell_height); Color green(0.0, 1.0, 0.0); Rect greenRect(&green, cell_width, cell_height); Color blue(0.0, 0.0, 1.0); Rect blueRect(&blue, cell_width, cell_height); Color white(1.0, 1.0, 1.0); Rect whiteRect(&white, cell_width, cell_height); Color black(0.0, 0.0, 0.0); Rect blackRect(&black, cell_width, cell_height); for (int i = 1; i <= rows; i++) { for (int j = 1; j <= cols; j++) { int val = (int) maze->getElement(i, j); int x_pixel = (j - 1) * cell_width + cell_width/2; int y_pixel = (i - 1) * cell_height + cell_height/2; if (val == WALL) { blackRect.draw(cr, x_pixel, y_pixel); } else if (val == SPACE) { whiteRect.draw(cr, x_pixel, y_pixel); } else if (val == TRIED) { blueRect.draw(cr, x_pixel, y_pixel); } else if (val == BACKTRACK) { redRect.draw(cr, x_pixel, y_pixel); } else if (val == PATH) { greenRect.draw(cr, x_pixel, y_pixel); } } } }
lab06/Maze.h
#if !defined (MAZE_H) #define MAZE_H #include "Matrix.h" using CSC2110::Matrix; #include "Update.h" #include "Drawable.h" #include "StackLinked.h" #include "Cell.h" #include <gtkmm.h> class Maze : public Drawable { private: Matrix* maze; Update* gui; int width; int height; bool traverse(); Cell* processBackTrack(StackLinked<Cell>* stack); void processSolution(StackLinked<Cell>* stack); bool isSolved(Cell* curr_cell, StackLinked<Cell>* stack); int WALL; int SPACE; int TRIED; int BACKTRACK; int PATH; public: Maze(Matrix* maze); virtual ~Maze(); bool solve(); void addListener(Update* gui); virtual void draw(Cairo::RefPtr<Cairo::Context> cr, int width, int height); virtual void mouseClicked(int x, int y); }; #endif
lab06/MazeGUI.cpp
#include "MazeGUI.h" #include "Matrix.h" #include <gtkmm/main.h> #include <gtkmm/table.h> #include <gtkmm/window.h> #include <gtkmm/button.h> #include <iostream> using namespace std; #include <windows.h> DWORD WINAPI traverseMaze(LPVOID* parameters) { MazeGUI* maze_gui = (MazeGUI*) (parameters[0]); maze_gui->solve(); } void MazeGUI::startMazeThread() { //start a new thread to solve the maze LPVOID* params = new LPVOID[1]; params[0] = this; CreateThread(NULL, 0, (LPTHREAD_START_ROUTINE) traverseMaze, params, 0, NULL); } MazeGUI::MazeGUI(int w, int h, Maze* mz) : DrawPanel(w, h, mz) { maze = mz; maze->addListener(this); } MazeGUI::~MazeGUI() { //the maze is deleted in DrawPanel } void MazeGUI::update() { render(); } void MazeGUI::solve() { maze->solve(); } void MazeGUI::on_maze_button_click_event() { startMazeThread(); } int main(int argc, char** argv) { Matrix* mat = Matrix::readMatrix("maze.txt"); Gtk::Main kit(argc, argv); Gtk::Window win; win.set_title("Maze!"); win.set_position(Gtk::WIN_POS_CENTER); //the size of the window int width = 875; int height = 445; win.set_size_request(width, height); win.set_resizable(false); Gtk::Table tbl(10, 1, true); int rows = tbl.property_n_rows(); int button_height = (int) (((double) height)/rows + 0.5); Maze* maze = new Maze(mat); MazeGUI mg(width, height - button_height, maze); //needs to know its own dimensions Gdk::Color c("#FF0000"); Gtk::Button btnMaze("Solve!"); btnMaze.signal_clicked().connect(sigc::mem_fun(mg, &MazeGUI::on_maze_button_click_event)); tbl.attach(mg, 0, 1, 0, 9, Gtk::FILL | Gtk::EXPAND, Gtk::FILL | Gtk::EXPAND, 0, 0); tbl.attach(btnMaze, 0, 1, 9, 10, Gtk::FILL | Gtk::EXPAND, Gtk::FILL | Gtk::EXPAND, 0, 0); win.add(tbl); win.show_all_children(); Gtk::Main::run(win); return 0; }
lab06/MazeGUI.h
#ifndef MAZEGUI_H #define MAZEGUI_H #include "Maze.h" #include "DrawPanel.h" class MazeGUI : public DrawPanel, Update { private: Maze* maze; public: MazeGUI(int width, int height, Maze* maze); virtual ~MazeGUI(); virtual void update(); virtual void on_maze_button_click_event(); void startMazeThread(); void solve(); }; #endif
lab06/StackLinked.h
#if !defined (STACKLINKED_H) #define STACKLINKED_H #include "NextNode.h" template < class T > class StackLinked { private: NextNode<T>* top; int sze; // number of items in the stack public: StackLinked(); ~StackLinked(); bool isEmpty(); int size(); void popAll(); T* pop(); void push(T* item); T* peek(); }; template < class T > StackLinked<T>::StackLinked() { top = NULL; sze = 0; } template < class T > StackLinked<T>::~StackLinked() { popAll(); } template < class T > bool StackLinked<T>::isEmpty() { return sze == 0; } template < class T > int StackLinked<T>::size() { return sze; } template < class T > void StackLinked<T>::popAll() { //loop over the stack, deleting the nodes //the actual items are not deleted if (sze == 0) return; NextNode<T>* curr = top; NextNode<T>* prev = NULL; while (curr != NULL) { prev = curr; curr = curr->getNext(); prev->setNext(NULL); delete prev; } } template < class T > T* StackLinked<T>::peek() { T* item = NULL; //DO THIS } template < class T > void StackLinked<T>::push(T* item) { //DO THIS } template < class T > T* StackLinked<T>::pop() { if (sze == 0) return NULL; //DO THIS } #endif
