2 CMSC 341 Spring 2006 Project 2

CMSC 341 Spring 2006
Project 2

Assigned Wednesday March 1, 2006

Due 11:59pm Tuesday March 14, 2006

Updates

10 March
This has been discussed on blackboard and in some classes, but just to be sure everyone's gotten the message -- in a circular list like the one in this project, incrementing an iterator (iter++ or ++iter) that is currently positioned to the last data element should position the iterator to the first data element. Similarly, decrementing an iterator positioned at the first data element moves it to the last data element.

06 March
More regarding the Chunk Size -- so that we are doing things the same way, please create a new ChunkList constructor with an integer parameter for the chunk size
(e.g. ChunkList( int chunksize )). All other methods of the List should be unchanged when implementing the ChunkList.

02 March

Details about insertion and deletion in a ChunkList have been added for clarity
Because template parameters are evaluated at compile time, the requirement that the ChunkSize (a command line parameter) be a template parameter has been eliminated. You will have find some other means of using the ChunkSize in the list and list node.

Objectives

To gain experience

reading and modifying code written by someone else.
combining multiple data structures.
implementing and using iterators in an application.
designing C++ classes.
using exceptions.

Description

In a standard linked list, each node contains just one data element, so finding an element means traversing the list from node to node. In this project, you will implement a variation of the linked list which we will call a "chunk" list. In this implementation, each node of the linked list contains not just one data element, but an array/vector of data elements (the "chunk" of data). You will be given the author's linked list code discussed in class as a starting point. You will then modify that code to create the chunk list. A picture of a circular chunk list containing 11 integers with chunk size of 4 is shown below. Note that not all elements of each chunk contain data.

In addition to adding chunks, you will also modify the author's code to create a circular double linked list. In a circular list, the head's prev pointer is not NULL, but points to the tail. Similarly, the tail's next pointer points to the head.

Thirdly, you will improve the author's code by designing exception classes which will be thrown where appropriate in the linked list and/or iterator code.

Finally, you will implement a small application that will test your chunk list. That application is a simple version of "solitaire" -- a one-person card game. The solitaire game is described below.

Your Tasks

Copy List.h from Mr. Frey's public directory. This file contains the author's linked list code discussed in class. The code has been slightly modified already so that it compiles under g++.
Modify List.h to implement the circular double linked chunk list. Your chunk list must support all list and iterator functionality provided by the author. Implement the chunk list as described above and in the project requirements below.
Modify List.h by adding exception classes to be thrown by the linked list and/or iterator code where appropriate.
Write main( ) in Proj2.cpp which uses your chunk list to implement the solitaire card game described below. Your code should use try blocks and catch any exceptions thrown by the linked list and/or iterators.
Design and implement C++ classes related to the solitaire game that are appropriate from an OO design perspective. There is no one perfect design. More than one design is acceptable.
Copy the questions file (341-Spring06-p2_questions.txt) from Mr. Frey's directory. Edit this file to answer the questions within.
Create a makefile for the project.
Submit your files.

Basic Project Requirements

Your executable must be named Proj2. Proj2 will be invoked with two command line arguments. The first argument will be an integer which is to be used as the seed of the random number generator (RNG) used to shuffle the cards. See the shuffling algorithm below. Use the function random( ) to get random numbers and use the function srandom( ) to seed the RNG. Both functions require you to #include <cstdlib>. The second argument is an integer which is the "chunk" size.
Your chunk list class must be named ChunkList and must be defined and implemented in ChunkList.h. You should expect that your ChunkList class will be tested by a program which we will write.
ChunkList Operations
1. Insertion -- as with the author's code, insert( iterator p, Object x )inserts x before the position represented by p. This operation first attempts to insert x into the chunk in the node pointed to by p. Only if the chunk in p's node is full should a new node be created.
2. Deletion -- as with the author's code erase( iterator p ) deletes the data element at position p. When the last data element in p's chunk is deleted the node be deleted.
There are 52 different cards in the standard deck. Each card has two attributes - its suit and its rank. There are four possible suits (clubs, diamonds, hearts, and spades) and thirteen different ranks - (Ace, 2, 3, 4, ..., 10, Jack, Queen, King).
The Solitaire Game To play this simple version of solitaire, the player first shuffles a standard 52-card deck of cards. All cards are then laid face-up (rank and suit showing) side by side in a (very large) circle. Beginning with the first card placed face-up, The player scans the circle of cards in the direction they were laid. When two adjacent cards have the same rank (e.g. both are 9s) or have the same suit (e.g. both are spades), the pair of cards is removed. The player continues scanning the circle of cards, removing all possible adjacent pairs. The player continues to scan the circle until all cards have been removed (the player wins) or until no adjacent cards can be removed (the player loses). So that we can see the progress of the game, some output is required. Before starting a new turn around the circle of cards print the number of cards remaining and the rank and suit of the first 10 cards. If there are less than 10 cards remaining, print all remaining cards. Whenever two cards are removed the rank and suit of both cards must be displayed. If the player loses, the rank and suit of all remaining cards must be displayed. If the player wins, an appropriate message must be displayed.
Both the rank and suit of each card are represented by a single character. For ranks, use the uppercase characters 'A' for Ace, 'T' for ten, 'J' for jack, 'Q' for queen, 'K' for king, and the appropriate numeral for ranks 2 - 9. For suits, use the first letter of the suit in lowercase -- 'c' for clubs, 'd' for diamonds, 'h' for hearts, and 's' for spades. Cards should be displayed with rank and suit characters concatenated. For example, the "two of hearts" is displayed as 2h and the "Jack of clubs" as Jc.
Use the following algorithm to shuffle the cards where "in order" means first sorted by suit in alphabetical order (clubs, diamonds, hearts, spades) and then by rank within suit (i.e. in the order {2c, 3c, ...., Tc, Jc, Qc, Kc, Ac, 2d, ..., Ad, 2h, ..., Ah, 2s, ..., As}) initialize an array 'a' by placing the 52 cards "in order" as above seed the random number generator for (size = 52 down to 1) { select a random number 'i' between 0 and size-1, inclusive; swap a[i] and a[size-1]; }

Sample Output This partial sample output is provided as an example of an acceptable output format only, showing the minimum required data. It is not the result of executing any program. DO NOT expect to match this output with your program. Of course only one of the last two messages will be displayed. linux3[1]% Proj2 1234 10 Shuffling.... There are 52 cards remaining. The first 10 cards are 5h, Ts, As, 6c, 9c, 8h, 6d, Kc, Kh, 7h Playing.... Removing Ts, As Removing 6c, 9c Removing 7h, 7s There are 38 cards remaining. The first 10 cards are 5h, 9d, Kd, 2s, 3h, 3c, 4d, 2h, Ac, Qs .... etc ... You win! All cards have been removed. Sorry, you lose. The remaining cards are 4d, 6s, 5d, 6h Files To Be Submitted Submit any files which you have written or modified -- source code and makefile. Be sure to submit the answers to the project questions in plain text format. Submit the files using the procedure given to you for your section of the course. If your makefile is set up correctly, you should be able to execute the command make submit. Submission Tools There are a number of tools available to you to check on your submittal. It is your responsibility to ensure that the submittal is correct and will result in a successful compilation of your project. Do not wait till the last minute to submit your files. Give yourself enough time to check that your submittal is correct. If you don't submit a project correctly, you will not get credit for it. Why throw away all that hard work you did to write the project? Check your submittals. Make sure they work. Do this before the due date. Documentation for the submit program is on the web at http://www.gl.umbc.edu/submit/ . One of the tools provided by the submit program is submitls. It lists the names of the files you have submitted. Additionally, there are two programs for use only by CMSC-341 students (not part of the UCS submit program). They are in the directory /afs/umbc.edu/users/d/e/dennis/pub/CMSC341/ and are named submitmake and submitrun. You can use these programs to make or run your submitted projects. The syntax is similar to that for submit: submitmake <class> <project> Example: submitmake cs341 Proj2 <parameter list> This makes the project, and shows you the report from the make utility. It cleans up the directory after making the project (removes .o and ii_files), but leaves the executable in place. submitrun <class> <project> Example: submitrun cs341 Proj2 This runs the project, assuming there is an executable (i.e. submitmake was run successfully). Grading and Academic Integrity Project grading is described in the Project Policy handout. Cheating in any form will not be tolerated. Please re-read the Project Policy handout for further details on honesty in doing projects for this course. Remember, the due date is firm. Submittals made after midnight of the due date will not be accepted. Do not submit any files after that time.