DodekaTrie Implements Sorted Map Requirements

You are required to implement the SortedMap interface in the java.util package using the DodekaTrie. A Map, in short, is:

An object that maps keys to values. A map cannot contain duplicate keys; each key can map to at most one value. ⁵

The SortedMap extends the Map interface to further specify:

A map that further guarantees that it will be in ascending key order, sorted according to the natural ordering of its keys (see the Comparable interface), or by a comparator provided at sorted map creation time. ⁶

Since any Binary Search Trie structure guarantees that the actual data values, in this case what we've called "search keys", will be stored in sorted order as recovered through in-order traversal, the SortedMap interface is the most appropriate choice for implementation using the AVL-g, so that it can be used in place.

Your tree is not required to support null keys or values, however you may choose to do so. If a null values are ever passed in for a "key" or "value" parameter you are permitted to throw a NullPointerException if your implementation does not support null values.

You can find the exact specifications for the SortedMap interface in the JAVA API at:

http://docs.oracle.com/javase/6/docs/api/java/util/SortedMap.html

One hint if anyone really likes a class name other than DodekaTrie: you can just add an extra DodekaTrie.java file with the following contents and you'll be set:

//file DodekaTrie.java
package cmsc420.sortedmap

public class DodekaTrie<K, V> extends YOURNAME {
  public DodekaTrie() {
    super();
  }
  public DodekaTrie(final Comparator<? super K> c) {
    super(c);
  } 
  public DodekaTrie(final int g) {
    super(g);
  }
  public DodekaTrie(final Comparator<? super K> c, final int g) {
    super(c,g);
  }
}

As per the Java specifications for entrySet, keySet, and values, note, your structure should return a Set or Collection that is backed by the tree. When a Set/Collection is ``backed" by another data structure the set/collection always reflects the state of the backed data structure. That means that if someone called ``DodekaTrie.entrySet()" then ``DodekaTrie.put()", the Set obtained from entrySet would allow you to access the element added from the put operation even though the entrySet was returned prior to the call to put.

This is not as hard as you might think it is. There are many approaches to this problem but may we suggest that you take a peek at the source code for TreeMap. You are allowed to adapt the code from TreeMap for entrySet as you see fit as long as no red-black tree based TreeMap code is used.

A hint: if you implement AbstractSet, the problem of writing a Set for entries, keys, and values becomes reduced to the problem of writing their iterators. With a little careful thought, you could even reduce that problem to one rather than three! For more, look at how TreeMap implements its entrySet and keySet.

Your DodekaTrie class must be called DodekaTrie, and it must exist in DodekaTrie.java. The DodekaTrie class must be placed in the package cmsc420.sortedmap. Your class must implement the following constructors:

// If this generic wildcard confuses you, reread the end of the
// part 1 spec for the introduction to generics.
public DodekaTrie();
public DodekaTrie(final Comparator<? super K> c);
public DodekaTrie(final int g);
public DodekaTrie(final Comparator<? super K> comp, final int g);

You're already quite familiar with the SortedMap interface--you've been using it every time you use a TreeMap, which is Java's stock implementation of SortedMap. SortedMap is a sub-interface of the Map interface, defined in the java.util package as part of the Java Collections Framework. In this project, you are going to get some exposure to implementing a Sun-provided Java interface. This will give you some practical experience coding to a standard and will also teach you leaps and bounds about how to solidly implement an object.

The first thing you'll need to do is have a look at the API documentation for the Map and SortedMap interfaces. Bookmark these pages now, since you'll be referring to them again and again throughout this project. You might even find it useful to print out copies. The URLs are

• docs.oracle.com/javase/6/docs/api/java/util/Map.html

• docs.oracle.com/javase/6/docs/api/java/util/SortedMap.html

Note that you are responsible for implementing every method from the SortedMap interface except for remove(), headMap(), keySet(), tailMap(), and values(). In Eclipse, you will be given the option to auto-fill these methods when you implement the interface, so you only have to remember not to implement the methods listed above. A wise implementation would throw an UnsupportedOperationException in case the user is unaware that we don't require remove or any of the other methods--that's an example of what's known as ``fail-fast programming.'' The opposite camp of programmers would, of course, say that the tree should gracefully just return null and do nothing for unimplemented operations; however, we think that fail-fast programming is important and we will be testing your tree to see that you throw the desired exception. Many of these methods are one line, and most of the others are very short also. The majority of the work will be in implementing the put() method, which amounts to writing the algorithms for building an DodekaTrie. The details of your class are mentioned in the Avl-g portion of the spec (e.g., the name of the class and its required constructors).