SortedMap interface in the java.util
package using the AVL-g tree.
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. 5
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. 6
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 an appropriate choice for implementation using the AVL-g, so that it can be used in place.
We also promise that when testing your SortedMap interface we will only try to insert homogeneously typed objects. That is, if we have inserted numerous Integer values into a tree, we won't try to insert a Double or Site into the same tree. Having values of different types in your leaves may or may not be a problem given your design, but the behavior for comparing a Site object to an Integer, for instance, is undefined so we won't be testing it.
Note that when discussing internal, or ``guide nodes'', the Map/SortedMap ``key'' refers to the guide values in those nodes and should not be confused with the real data (called keys, unfortunately) that resides in the leaf nodes.
Your AVL-G 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:
https://docs.oracle.com/javase/8/docs/api/java/util/SortedMap.html
One hint if anyone really likes a class name other than AvlGTree: you can just add an extra AvlGTree.java file with the following contents and you'll be set:
//file AvlGTree.java
package cmsc420.sortedmap
public class AvlGTree<K, V> extends YOURNAME {
public AvlGTree() {
super();
}
public AvlGTree(final Comparator<? super K> c) {
super(c);
}
public AvlGTree(final int g) {
super(g);
}
public AvlGTree(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 ``AvlGTree.entrySet()" then ``AvlGTree.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 AvlGTree class must be called AvlGTree, and it must exist in AvlGTree.java. The AvlGTree 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 AvlGTree(); public AvlGTree(final Comparator<? super K> c); public AvlGTree(final int g); public AvlGTree(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. The URLs are
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 AVL-g tree. 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).