Caution: entrySet() is tricky

There is one method that deserves considerable attention and is the most difficult to implement. It's vastly important that you understand this concept since it is required for most of the other methods (which you don't have to implement until the next project). This method is entrySet().

As you can see from the prototype of the method, it returns a Set object. When students see this, they immediately assume that the method is supposed to create a new Set, add all of the Map's entries into it, and return that Set. That is completely wrong. Observe the API description of the entrySet() method:

Returns a set view of the mappings contained in this map. Each element in the returned set is a Map.Entry. The set is backed by the map, so changes to the map are reflected in the set, and vice-versa.

Note that changes in the Set are reflected in the Map and vice versa. Some students will read that and still think that they are supposed to create a new Set, copy all of the elements of the Map into it, return it, but include some way of managing that relationship (for instance, keep a pointer to the Map in the Set object, and store a list of all of the entry sets created and returned by that method in the map, updating all as necessary). This is also completely wrong (although it's closer to accurate).

How, then, does one implement this relationship in Java without making copies? The Set object that is returned from entrySet() does not itself contain any data. The Set that is returned is simply an object whose methods call the methods in the ``backing map'' (i.e., the map from which it was created). The simplest way to implement this behavior is by creating an inner class inside your SortedMap implementation that itself implements the Set interface. For example

    public class Treap<K, V> implements SortedMap<K, V> {
    public Object remove(Object key) { ... }
    public boolean containsKey(Object key) { ... }
    // We're leaving out generics here because otherwise
    // the code would be a mile long
    public Set entrySet() { return new EntrySet(); }
    protected class EntrySet implements Set {
        public boolean remove(Object o) {
            Map.Entry me = (Map.Entry)o;
                // throws a ClassCastException if this fails,
                // as per the API for Set

            boolean b = Treap.this.containsKey(me.getKey());
            Treap.this.remove(me.getKey());
            return b;
        }
        public boolean contains(Object o) {
            Map.Entry me = (Map.Entry)o;
            return Treap.this.containsKey(me.getKey()) &&
                (me.getValue() == null ?
                    Treap.this.get(me.getKey()) == null :
                    me.getValue().equals(Treap.this.get(me.getKey())));
        }
    }
}

Observe that the Set object returned by Treap's entrySet() method is of type EntrySet, an inner class of Treap, whose remove() method simply calls the Treap's remove() method, and containment in the returned set is checked by existence in the Treap. Thus, if the Treap changes after the Set is created, the contains() method of that Set will still return accurate results. You must implement entrySet() to this standard. We will easily discover whether or not your entrySet() is implemented correctly. It's very easy to grade:

    SortedMap<String, String> m = new Treap<String, String>();
m.put(``Auto'',''Fail'');
Set<Map.Entry<String, String> > s = m.entrySet();
m.put(``F'',''---'');
if (!s.contains(new Map.Entry<String, String>(``F'',''---'')))
System.out.println(``You fail!'');

Note that this wouldn't compile since Map.Entry is an interface, so you can't instantiate it. Substitute that with a concrete implementer of Map.Entry. ;)

All methods in Set must be implemented by the Set object you return via your entrySet() method. However, there are certain methods, as detailed in the description of the entrySet() method, which are explicitly not supported by the entry set. Those include add() and addAll(). A good exam question might be why the authors of the SortedMap interface (our friend Josh Bloch) made this decision. There's a good reason--think about it!