Next: Caution: entrySet() is tricky Up: Part 2: Sorted Map Previous: Important Notes about the
SortedMap interface in the java.util
package using the Treap.
(In earlier versions of JAVA, we would have had you extend the Dictionary class
but it has become deprecated and replaced by the Map and SortedMap interfaces.)
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 a Treap structure guarantees that the actual data values, in this case what we've called ``search keys'', can be retrieved in sorted order using an in-order traversal ( go left, process the root, go right) the Treap is a reasonable choice of underlying structure to implement the SortedMap interface . Then, the Treap-based SortedMap interface , can be used in place of any other data structure that implements the SortedMap interface. Just make sure that you maintain parent pointers to help you navigate the Treap eficiently.
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 Treap 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 Treap: you can just add an extra Treap.java file with the following contents and you'll be set:
//file Treap.java
.....
public class Treap extends YOURNAME
{
public Treap(Comparator c){super(c);}
}
As the Java specifications for entrySet, keySet, and values, note, your Treap should return a Set or Collection that is backed by the Treap. 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 ``Treap.entrySet'' then ``Treap.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 adopt the code from TreeMap for entrySet, keySet, and values as you see fit. As always, document your source.
Be sure that your Treap.entrySet().iterator(), Treap.subMap().entrySet().iterator() calls return correctly working Iterators!
The SortedMap you will (partially) implement for this project
Your Treap class must be called Treap, and it must exist in Treap.java. The Treap class must be placed in the package cmsc420.sortedmap. Your class must implement the following constructors:
public Treap();
public Treap(Comparator comp);
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 a Treap. The details of your class are mentioned in the Treap portion of the spec (e.g., the name of the class and its required constructors).