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

Unlike the structures you implemented in Part 1, your SortedMap implementation will be tested directly as well as through your XML. That is, we're going to link your DodekaTrie 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() method works correctly. Furthermore, it is equally important that the TreeMap equals() method will work with your DodekaTrie. Look at TreeMap's source code, see what it extends, and make sure it will be able to check your DodekaTrie 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.

In addition, your SortedMap implementation must have properly working hashCode() and toString() methods that agree with TreeMap. All returned objects must also have hashCode() and toString() methods that agree with TreeMap. For example, your EntrySet and SubMap must have hashCode() and toString() methods agreeing with TreeMap.

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.