DodekaTrie requirements

In Part 2, you will be asked to consider replacing the treemap of city names which is used as an index to the city objects with some other structure. A Twelve-ary Search Trie, or DodekaTrie, is an extended 12-ary tree, and 12-way search trie where the internal nodes contain guide values, and the keys are in the leaves. Furthermore, leaves in the DodekaTrie contain between $\lceil \frac{leafOrder}{2} \rceil$ and leafOrder keys. The values in the internal nodes are not otherwise specified--they just have to work. And, as always in our search structures, equality is associated with the right child of every node.

Since we're using Java and a fundamental feature of Java is its interfaces, your code will be required not only to properly implement the DodekaTrie specifications, but also to implement Java's SortedMap interface. This will allow you to fully replace the TreeMap with your SortedMap as you desire. Your DodekaTrie should be generic just like the TreeMap, and it should eventually implement every one of the SortedMap methods except headMap(), tailMap(), keySet() and values(). However, we will not test remove() until Part3. So, you can choose to delay it until after you've finished Part2.

But, since you don't implement remove in Part 2, this prevents you from properly implementing subMap().clear() and related functions. Therefore, your behavior for subMap().clear() won't be tested--but we advise that at this point you forward to DodekaTrie.this.clear(). If that sounded confusing to you, don't worry about it for now, but come back to it later. If you would like guidance on how to begin implementing SortedMap, there are two resources to which you can turn: we provide you with an example, SortedMapExample.jar, which shows a SkipList that has been used to implement SortedMap. You can find SortedMapExample.jar in the top level directory of the course files. Similarly, you can easily find the source code for Java's TreeMap online; Josh Bloch's implementation strategies may prove useful and relevant to your code. As always, if you take inspiration or structure from either of these sources please cite that in your README file.

Any portion of the TreeMap that uses the red-black tree explicitly (or the skiplist version) must be modified to use the DodekaTrie tree instead. Failure to do this will result in a deduction of the points that you tricked the submit server into giving you. It will not be treated as an honor code violation since the red-black tree is not the most intuitive creature that you will ever meet.

Although this probably won't be a problem for B+ as much as some of the structures in the past, we expressly forbid you from actually using a skiplist or other complex data type inside your DodekaTrie code. That is, although you may be inspired (or more) by the code you see in TreeMap or SkipList, you may not actually use a TreeMap or SkipList in your implementation. The same goes for TreeSet (which, interestingly, is just a wrapper around a TreeMap--cool trivia!), HashSet or HashMap; basically, if you're using a structure that you feel probably duplicates the functionality of your SortedMap, you should not be using it.

We now proceed into a formal definition of the DodekaTrie.