Testing SortedMap: equals(), hashCode(), and toString() must work

Unlike the structures you implemented in Part 1, we are going to independently test your implementation of SortedMap programmatically (i.e., we're going to link your Treap into our code and run a SortedMapTester program on it). Your SortedMap implementation should always agree with TreeMap. Thus, it is extremely important that your equals() methods works correctly. Furthermore, it is equally important that the TreeMap equals() method will work with your Treap. Look at TreeMap's source code, see what it does, and make sure it will be able to check your Treap for equality, since we will invoke the equals() method bidirectionally. And don't try to cheat and make your equals() method return true all the time, because we can (and will) test that-quite easily, in fact.. Your SortedMap will fail all of the tests if equals() does not work and that is not a valid excuse for a regrade. You have been warned.

Your SortedMap will not support null keys. TreeMap is actually bugged in this regard, in that it will not throw a NullPointerException when a null key is added to the map, although it will throw one later, unintentionally. If we attempt to pass null to your Treap's put() method, you should immediately throw a NullPointerException.

Also, RTFAPI. The API is very specific about what exceptions need to be thrown when, what needs to be returned when, etc. You are expected to throw exactly the exceptions the API defines. This applies both to the methods in the Map/SortedMap interface but also the methods in Set for the object returned by entrySet(). I am imposing another requirement that is commonly done in the Java Collections Framework but not clearly defined in the API, and that refers to the Iterator object returned by a call to entrySet().iterator(). In addition to the exceptions described by the API for Iterator (specifically NoSuchElementException if next() is invoked when hasNext() returns false), your iterator must throw a ConcurrentModificationException if the map changes after an Iterator has been created. There is a very easy way to do this--just keep a modCount variable that gets incremented whenever a structure-changing method (i.e., put() and remove()) is called. When you create an iterator, save the modCount according to the Map when the iterator was created, and each time next() is called, check the saved modCount against the modCount of the Map. If the two numbers are not the same, it means the map has changed since the Iterator was created, and at that moment the next() method of the iterator should throw a ConcurrentModificationException.