While the game of snake does make use of the hash and queue, it does not serve as a exhaustive test of your data structure implementations. For example, it takes a long time of playing to create a resize event that is often the hardest to get correct for both the ArrayQueue and MyHashSet. Instead, write JUnit tests to check the correctness of your program.

We have provided you a starter test for the ArrayQueue class in ArrayQueueTest.java. It is our hope that you will take this test case and make it more complete, as well as making one for your hash set. It will be hard to get a good grade without good tests.

You need to be able to debug failures (Eclipse Debugging may be a useful resource) As the assignments get harder and harder, testing will only become more essential. We hope you will start with good habits now!

Probably the hardest part of testing is figuring out a strategy to make good tests. Your end goal is to make sure you cover every possible code path and check that it is correct. You can do this by creating three types of tests.

Sanity Tests

Sanity tests are tests that check basic operations. The goal is to make sure you got a good start on the code. A sanity test might add an item to a queue and then remove it, and check that the same item was returned.

Edge Case Tests

What happens if you construct a hashtable with a load factor of -1.1? Check to make sure your code acts correctly, for example, by thowing an exception. What happens when the ArrayQueue wraps around or resizes? Check cases like this as well with separate tests.

Stress Tests

Stress tests will attempt to run through all code paths by doing long, random sequences of operations. For example, our stress test for hashset does the following operations

• Generates a bool. If the bool is true, it adds an item to the hash set, and then make sure the hash set returns true for contains on that object. Otherwise, it removes a random item.
• It checks equality of your set and a java.util.HashSet that has had the same operations done on it.
• It tests that your iterator gives the same number of items as the java.util.HashSet's. Also, for each item, it makes sure contains returns true.

This gives you a good idea of the effort required for a stress test.

An important question to ask is Who watches the watchmen?, or How do I know my test cases are correct?. In this assignment, there is an easy answer. For MyHashSet, HashSet is the gold standard for correctness. An implementation of MyHashSet that just called HashSet would pass all of the tests. Thus, a test for your test cases is if a HashSet with the same operations done on it acts in the same way. Likewise for ArrayQueue Java's LinkedList (it implements Queue) is a gold standard. These are especially useful for the stress tests.

Here are some assorted thoughts on what might need testing in ArrayQueue and MyHashSet

• Iterators are extremely hard to get right, especially in ArrayQueue due to the wrap-around nature of it. A good place to test iteration is in your stress tests (perhaps in addition to a separate test just for the iterator). Make sure that iteration works after each stress operation. Remember that the iterator for the Set is unordered, you can't expect the iterator from Java to give elements in the same order as yours.
• Every time you see % or / operators, you should think Could there be a zero on the right hand side of this operation?.
• Writing the wraparound and resize behavior of your ArrayQueue is tricky.
• Hashtable resizing is tricky. Make sure to test that the hashtable is correct after it is resized. Almost no one gets this right the first time.
• You should also check your hashset with null items and other edge cases (like negative hashCodes).
• You should test your hash set with many different load factors and initial sizes this will help you find bugs in the resizing logic.
• You should test the collision resolution of your hash set. A good way to do this is to insert alot of items into the hashtable with the same hash code which may or may not actually be equal (make your own class to do this)
• You should test for exceptions, such as IllegalArgumentException and NoSuchElementException.