CSE 326 Project 1, Autumn 2000

DUE OCTOBER 9, 2000 at 2:30PM

In this project, you will implement a data structure called a "grabbag." A grabbag is similar to a stack or a queue, but instead of the first or last element being removed on a pop or dequeue, a random element is removed on a grab.

Background

This assignment should be done on the instructional unix machines, fiji, ceylon, sumatra, and tahiti. The code you turn in will be graded on those machines using their compiler, so while you are welcome to use any tools available to you, be sure that your final code works correctly and robustly on those machines.

The labs for this class are Sieg 232 and Sieg 329. Each of these labs contain about 30 Windows workstations that you can use to connect to the instructional unix machines. To connect, follow this procedure.

Log in to Windows in the CSEPCLAB domain.
Load Start -> Programs -> Reflection -> Reflection X
The "X Client Manager" program should open.
In the left window pane, select "linux.rxc (Generic Linux xterm)" by single-clicking it.
In the right window pane, change the method to "KERBERIZED TELNET." You maybe have to scroll down a bit to get to it.
Enter the host name (ceylon, fiji, sumatra, tahiti).
Click connect. An xterm window should open on the host that you specified. You may be asked for your username or password.

Once logged in to a unix machine, do the following sequence of commands at the % prompt:

"mkdir 326" - The mkdir command creates a new directory. Remember that what Windows calls folders are called directories in unix.
"chmod go-rwx 326" - The chmod command changes the security settings for files. This command will remove permissions for everyone but you on the 326 directory.
"cd 326" - The cd command changes the current directory to the one specified.
"mkdir project1"
"cd project1"
"cp /cse/courses/cse326/00au/project1/* ." - The cp command is copy. The first argument uses a * to specify every file in that directory. The second argument, a period, means the current directory.
"make" - This should compile everything. You'll get some warnings in the stub functions until you replace them with your implementation.

Now that you have all of the starting files in your directory, you have what you need to work on the project. If you need more help with unix, I recommend reading the tutorials at http://www.cs.washington.edu/education/courses/cse326/CurrentQtr/lab.htm.

Vector Template

The vector template will be used for this assignment instead of native C++ arrays. The vector template has a constructor that takes the size of the array. For example, to make a vector of 10 numbers, do:

vector<int> numbers(10);

You can then access individual elements by assigning them, just like a normal array:

numbers[0] = 3;
numbers[9] = 7; (Okay)
numbers[10] = 7; (ERROR)

Note that the vector template includes bounds checking. If you find that you need more space in your vector object, call its resize function:

numbers.resize(20);
numbers[10] = 7; (Now okay);

I've provided sample code that uses the vector template in example.cpp.

Grabbag Template

For this project, you must implement a grabbag template. Some of the code has already been written, and an interface has been provided for you. Here is the public specification of a grabbag. Note that you may not change the public part of grabbag.h.

  // A standard zero-argument constructor.  This constructor must
  // ensure all data members have appropriate values and do anything
  // else necessary to allow the class to be used.
  grabbag( );

  // This copy constructor takes another grabbag as an argument.  The
  // current object must be initialized to exactly the same characteristics
  // as the other grabbag.  However, note that any later actions to one copy
  // must not affect the other.
  grabbag( const grabbag & rhs );

  // The copy assignment operator is called when the current object has
  // already been initialized.  It must make make an exact copy, just
  // as in the copy constructor above.
  const grabbag & operator = ( const grabbag & rhs );
  
  // The destructor.
  ~grabbag( );


  // Size should return the number of items currently in the grabbag.
  // Must be O(1).
  int size( ) const;

  // Is_empty must return true if the grabbag is empty or false if it
  // contains at least one item.  Must be O(1).
  bool is_empty( ) const;
  

  // The insert function must store the item in the grabbag in O(1) time.
  void insert( const Object & item );

  // The grab function must return a random item from the grabbag in O(1) time.
  const Object & grab( );

The file grabbag.cpp has stubs for all of these member functions. For this assignment, you can ignore the cost of resizing a vector and treat it as an O(1) operation. We want to focus on the data structure, not memory allocation.

We've included an example test case in test1.cpp. Make sure it works with your data structure. Make at least one more test case program to turn in.

Note: To get a random number, call the rand() function. It will return a random number between 0 and RAND_MAX. Read man rand for more info.

Deckwars

Once you have implemented the grabbag data structure, we'd like you to implement a small game called "Deckwars." Deckwars has a simple set of rules. Each player (call them left and right) starts with a set of cards numbered 1 to N. N is a number that can be entered by the user. Each of these cards is placed in a grab bag and the game begins.

Each player picks one random card from their bag.

If the cards have the same number, both cards are discarded.
Otherwise, the player with the higher card adds both cards to his grab bag.

This process repeats until one player has all of the (non-discarded) cards or neither player has any cards left.

There is an included program called "sample1" in the directory that you copied. It's a sample of what your deckwars program might look like when done.

Turnin Items

You must use the turnin program to turn in your entire project1 directory. Here's the list of things you need to do:

Implement the grabbag data structure in grabbag.h and grabbag.cpp.
Write code to test your data structure (preferably test2.cpp).
Implement the "Deckwars" game in deckwars.cpp.
Write up your project in the README file.
Answer the two discussion questions in the README file.

That's it! If you have any questions, either email me (amohr@cs) or send mail to the class mailing list (cse326@cs).