Important Notes about the SortedMap

In a development environment, it is prudent to isolate new code from tested code, especially after refactoring. Furthermore, you will often be required to modify a version of a well-studied data structure to suit your application. Finally, avoiding double jeopardy in grading is a meta-requirement for any course managed by Darth Hugue. Thus, we provide the following guidelines for the design, implementation, and use of the AVL-g tree in MeeshQuest.

• While you are free to implement this tree in whatever manner you choose, the explicit use of the TreeMap or TreeSet class is strictly prohibited!

  However, you are encouraged to look at the code used to implement them to see how you might proceed, as well as the SortedMapExample.jar, where the skiplist plays the role that the AVL-g tree will in your project.

• Warning. The Roadmap says that the AVL-g tree should be used for the data dictionary, and, indeed, is expected to be populated when a create_city command is processed However, you are encouraged and expected to maintain your treemap-based data dictionary as well to protect your other structures from failing tests because a faulty AVL-g tree corrupted your city database. Again, it is expected that tests of, say, the map_road command will use a data dictionary that is correct, irrespective of SortedMap implementation. The AVL-g will be evaluated by checking its compliance with the SortedMap Interface.