Important Notes about the Treap

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 Treap in MeeshQuest.

• Since we have not yet studied that structure formally, the above Treap definition was provided and is sufficient for MeeshQuest.

• While you are free to implement the Treap 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 Treap will in your project.

• Warning. The Roadmap says that the Treap should be used for the data dictionary, and, indeed, is expected to be populated when a createCity 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 Treap corrupted your city database. Again, it is expected that tests of, say, the mapRoad command will use a data dictionary that is independent of your Treap. The Treap will be evaluated by checking its compliance with the SortedMap Interface.