Problem: A Set Backed by a Map

Let’s build a set out of a map, using the map as storage instead of writing a new array or linked list.

The keys of a map are distinct and have no order. That is exactly what the elements of a set are. So each element of the set can be stored as a key of the map.

Here is the Set interface from the end of the iterator chapter. It extends Iterable<T>, so a set works in an enhanced for loop:

public interface Set<T> extends Iterable<T> {
  boolean add(T item);       // true if added, false if it was already present
  boolean remove(T item);    // true if removed, false if it was not present
  boolean contains(T item);
  int size();
}

Here is the skeleton of the class:

public class MapSet<T> implements Set<T> {
  // a private Map field whose keys are the elements of this set

  // ... add, remove, contains, size, and iterator() go here
}

The code for this problem includes ArrayMap from this chapter, so you have a working map to store the elements in.

Here is a short sequence of calls, with what each returns and the keys the map holds afterward:

call          returns   keys in the map
──────────    ───────   ───────────────
add(4)        true      4
add(9)        true      4, 9
add(4)        false     4, 9
contains(9)   true      4, 9
remove(7)     false     4, 9
remove(4)     true      9
size()        1         9

A MapSet is a Set, so every operation must follow the Set contract:

add, remove, and contains throw an IllegalArgumentException when the item is null.
Adding an item that is already present returns false and leaves the set unchanged. Removing an item that is not present returns false and leaves the set unchanged.
The iterator visits every element once, in no particular order, and its next() throws NoSuchElementException after the last element.

size should run in $O (1)$ time. add, remove, and contains should each cost no more than one lookup in the map, which is $O (n)$ with ArrayMap.

The test class MapSetTest runs the iterator chapter’s SetTest suite against your class. It also checks that the elements are stored as the keys of a Map field.