Lab #1: Snake

The first data structure to implement is the queue. You will be implementing the Java interface Queue. The queue is used to represent the points in the snake. The snake grows at the head and shrinks at the tail, a FIFO access method. The Queue class uses a feature of Java called generics. You may want to get familiar with the Java implementation of generics.

Some notes about this implementation:

• Your implementation of the queue must be in ArrayQueue.java
• You must implement the queue as a circular buffer (as an array)
• Your iterator does not need to implement the remove method. It also does not need to implement fail fast behavior. This means that we won't test modifications concurrent with iteration, and any behavior that occurs during such modifications are perfectly fine (even if your code fails immediately or throws strange exceptions, so don't worry about it at all).

Java has a useful class called HashSet, a Set that implements constant time add, remove and contains operations. The data structure is a hashtable. You will be implementing your own version of HashSet in MyHashSet.java. In snake, the hashset is used to represent a set of points. We will want to test if a given point is in that set. For example, we need to know if the snake's head is at a food item to see if it should eat the item. Since many such calls need to be made, a constant time data structure is important.

• You must use a hashtable implementation.
• Like the iterators in the queue, the MyHashSet iterator does not need to be fail-fast or implement the remove method.
• You may not use any collection classes from java.util except for AbstractSet (used as the base class). Specifically, lists, sets, maps, and other such classes are off limits. If you do separate chaining to handle collisions, you'll have to create your own linked list (a simple Node class will do).
• Feel free to use any collision handling method you like. You must obey the loadFactor given in this process, if possible (if you use open addressing, you can assume that all loadFactors > 1 are equal to 1). Note that in the past, most people who have tried open addressing have struggled with it. This is a perfectly valid form of collision handling, but see a TA for some pointers if you're planning on this.
• Your set must handle resizing.
• Your hashtable must tolerate hash functions that return integers with a common divisor, for example, by using a prime table size.
• You must use the hash and equality functions from java.lang.Object.

• For MyHashSet, an easy way to find a prime number to use is just with a static array of values. Just look for one at least 2 times the size of your current one: private static final int [] PRIME_TABLE = {11, 19, 37, 73, 109, 163, 251, 367, 557, 823, 1237, 1861, 2777, 4177, 6247, 9371, 14057, 21089, 31627, 47431, 71143, 106721, 160073, 240101, 360163, 540217, 810343, 1215497, 1823231, 2734867, 4102283, 6153409, 9230113, 13845163};
• MyHashSet can contain one and only one null element. There are different ways to handle this. Talk to a TA for some good ideas.
• Be careful with hashCode. This method can return any integer value.
• This assignment makes use of generics in order to keep code clean. A good place to check for questions is: Java Generics FAQ.
• We cannot reiterate enough times the importance of writing JUnit tests and thinking about what tests you want to write. We've even created a separate document to help on testing.

To play the game of Snake you just need to run the main method in Gui: java Gui. You can press space to begin a game. the red circles are the snake and the blue squares food. To change the direction the snake moves, use the arrow keys.

It should go without saying that your submission must have good style. This is needed so that the TAs can understand your code and give you partial credit. It's also a good habit.

As you know, we test your labs very thoroughly using a set of unit tests via JUnit. You'll certainly want to do the same -- or you might be very surprised.

Just to make sure you get off to a good start with the first lab, we're going to grade your test suite's thoroughness, utility and correctness.