Solution: Iterating Keys and Entries

The keys are already in ascending order in keys, so the key iterator works the same way as ArrayMap’s key iterator: a cursor moves through the array one index at a time. It visits the keys in ascending order without doing anything extra:

@Override
public Iterator<K> iterator() {
  return new KeyIterator();
}

private class KeyIterator implements Iterator<K> {
  private int cursor = 0;  // index of the key that comes next

  @Override
  public boolean hasNext() {
    return cursor < size;
  }

  @Override
  public K next() {
    if (!hasNext()) {
      throw new NoSuchElementException();
    }
    return keys[cursor++];
  }
}

ArrayMap’s entry iterator hands back the Entry objects stored in its array. This map stores no pair objects. The key is in one array and the value is in the other.

One option is to change the representation and store Entry objects after all. That would undo the representation this problem asked for. The other option is to build a pair object on each call to next(), from the key and the value at the cursor. We take the second option. In the chapter, ArrayMap and LinkedMap returned their stored objects so that they would not have to create a new object on each step, but this map has no stored pair to return. Each next() creates one small object, and the iterator itself still keeps only its cursor.

The pair object needs a class that implements the read-only Map.Entry:

private static class Pair<K, V> implements Map.Entry<K, V> {
  K key;
  V value;

  Pair(K key, V value) {
    this.key = key;
    this.value = value;
  }

  @Override
  public K key() {
    return key;
  }

  @Override
  public V value() {
    return value;
  }
}

Pair is a static nested class, because it needs nothing from the map. It only holds the key and the value it was given. The iterators are inner classes, because they read the map’s keys, values, and size.

@Override
public Iterable<Map.Entry<K, V>> entries() {
  return new Entries();
}

private class Entries implements Iterable<Map.Entry<K, V>> {
  @Override
  public Iterator<Map.Entry<K, V>> iterator() {
    return new EntryIterator();
  }
}

private class EntryIterator implements Iterator<Map.Entry<K, V>> {
  private int cursor = 0;  // index of the pair that comes next

  @Override
  public boolean hasNext() {
    return cursor < size;
  }

  @Override
  public Map.Entry<K, V> next() {
    if (!hasNext()) {
      throw new NoSuchElementException();
    }
    Pair<K, V> pair = new Pair<>(keys[cursor], values[cursor]);
    cursor++;
    return pair;
  }
}