1.(30 marks) A string in C++ is simply an array of characters with the null character(\0) used to mark the end of the string. C++ provides a set of string handling function in as well as I/O functions in . With the addition of the STL (Standard Template Library), C++ now provides a string class. But for this assignment, you are to develop your own string class. This will give you a chance to develop and work with a C++ class, define constructors and destructors, define member functions outside of the class body, develop a copy constructor and assignment operator (and understand why!), work with C-Style strings and pointers, dynamically allocate memory and free it when done. Of course, you must also do suitable testing which implies writing a main function that uses your new string class. The following is the skeleton of the Mystring class declaration. Mystring.h file is provided. You must produce the Mystring.cpp and main.cpp files. class Mystring { private: char *pData; //pointer to simple C-style representation of the string //(i.e., sequence of characters terminated by null) //pData is only a pointer. You must allocate space for //the actual character data int length; //length of the string // //possibly other private data public: MyString(); //constructor --- create empty string MyString(char *cString); //constructor --- create a string whose data is a copy of //cString ~MyString(); //destructor -- don't forget to free space allocated by the constructor //i.e., the space allocated for the character data MyString(MyString const& s); //override the default copy constructor --- why? //important -- think about it -- possible test question MyString operator = (MyString const& s); //override default assignment operator void Put(); //output string void Reverse(); //reverse the string 2 MyString operator + (MyString const& s); //concatenation operator // //other useful member functions //as you wish }; In addition, prepare a graphical explanation of each of your member functions. (You can use Pseudo code or flowchart or some diagram to show your design.) 2. (70 marks) In this assignment, you will implement a simple Tic-Tac-Toe game. It will be possible to play human-vs-human, human-vs-computer, or computer-vs-computer. Tic-Tac-Toe, also called X's and O's, Noughts and Crosses, and X and 0 is a simple game played on a 3x3 grid, referred to as the board. The grid starts empty, and the two players take turns placing their respective symbols, X and O, on an empty grid cell, referred to as making a move. The first player to get a straight line of three symbols wins. If all the cells on the board are filled and neither player has a line of 3 symbols, the game is a tie. Lines may be horizontal, vertical, or diagonal. You will implement a Board class to represent the 3x3 grid. This class will have functions to determine which symbol, if any, is in a cell, to place a symbol in a cell, to determine the winner, if any so far, and to print the board to standard output. The board should appear as below: +---+---+---+ | X | | | +---+---+---+ | | O | X | +---+---+---+ | | | | +---+---+---+ You will implement an abstract Player class to determine the player's moves. The Player class should store which symbol it will place and contain a pure virtual function to determine the Player's next move. This function will be overridden by the subclasses of Player. You will implement PlayerHuman as a subclass of Player. When this subclass is to choose a move, it should print out the current board and ask the user for the row and column to place a symbol. This class should detect if the user enters an invalid location, either because it is not in the grid or it already has a symbol, and if the location is invalid, ask the user again. You will implement PlayerRandom as a subclass of Player. When this subclass is to choose a move, it should return a random position in the grid that does not yet have a symbol. 3 You will implement a program to play the Tic Tac Toe game. The program should begin by asking the user if each team should be controlled by a human or by the computer. The program should then use dynamic memory allocation to create instances of the appropriate subclasses of Player. These must be stored with pointers of type Player*. The first team should place X symbols, while the second team should place O symbols. The program should then alternate asking the players for moves until one player wins, or the board is full and the game is a tie. After the game is over, the program should print the winner and the board and exit. The purpose of this assignment is to ensure that you understand how to use inheritance and dynamic memory allocation to implement polymorphism in programs, and how to structure your program into classes with a clear distinction between interface and implementation. For Part A, you will develop a Board class. For Part B, you will program an abstract Player class. For Parts C and D, you will implement the PlayerHuman and PlayerRandom classes. For Part E, you will write a program to use these classes to simulate a game of Tic Tac Toe. For Part F, you will devise an extra feature above and beyond those described below. The required steps towards programming for this assignment are as follows: Part A [15%]: Implement a Board class with the following functionality: Default constructor, copy constructor, destructor, assignment operator. Determine the symbol at the specified grid position. Change the symbol at the specified grid position. Determine the winner of the game, if any. You must distinguish between the case where there is no winner because the game is not over yet, and the case where there is no winner because the game ended in a tie. o Hint: Create four constants for the four game states and return one of them. Hint: Find a way to pass the position in the grid as a single value. This can be done by creating a record (struct) to store the row and column, or by representing both values using a single integer. This will make Parts B, C, and D easier and your program easier to read. Print the board to standard output. Part B [5%]: Implement an abstract Player class with the following functionality: Default constructor, copy constructor, destructor, assignment operator. o Remember: This class will be inherited, so the destructor must be declared with the virtual keyword. A way to set the symbol placed by this Player. o This can be done as either a function or as an additional constructor with a parameter. Determine the symbol placed by this Player. Determine the next move for this Player. This function should take a const reference to a Board as a parameter and must be a pure virtual function. Hint: Add a class invariant that ensures that a Player always has a valid symbol. Part C [15%]: Implement a PlayerHuman class the following functionality: Default constructor, copy constructor, destructor, assignment operator. 4 Determine the next move. This must be a virtual function and override the corresponding function in Player. Detect and reject invalid user input. Part D [5%]: Implement a PlayerRandom class with the following functionality: Default constructor, copy constructor, destructor, assignment operator. Determine the next move. This must be a virtual function and override the corresponding function in Player. Part E [20%]: Implement a program to simulate the Tic Tac Toe game. This program should behave as follows: Ask the user whether each player is human or computer o Detect and reject invalid input Dynamically create appropriate Player subclass instances for each team. Repeatedly ask the players for moves in alternating order. When the game is over, print who won, print the board, and exit the program. Part F [10%]: Extra Feature 1. Before modifying your program to include an extra feature, you MUST make a copy of your program in a separate folder called extra. 2. Devise an extra feature, or several extra features, above and beyond those described above or required for subsequent assignments. 3. Write a paragraph (or more) describing: What is your feature? What parts of the program were changed? How can your feature be tested? Other Points to Note: [-10% if not done] Neatly indent and format your program. Use a consistent indentation scheme and make sure to put spaces around your arithmetic operators. [-10% if not done] Deallocate all dynamically allocated memory. [-10% if not done each] The Board, Player, PlayerHuman, and PlayerRandom classes should be fully encapsulated. The rest of the program should only interact with these classes using their defined interfaces. The data in the Player class should not be accessed directly by its subclasses.