Problem: A Sorted Array Map

When we designed ArrayMap, I said we could keep the array sorted by key and find a key with binary search, the same way SortedArraySet did for a set, and that I would not build it. Let’s build it here.

The Comparable bound is the same one SortedArraySet needed. To keep the keys in order, the keys must be comparable to one another.

Representation

ArrayMap stores each pair as one Entry object in a single array. For this problem, store the pairs in two parallel arrays instead:

public class SortedArrayMap<K extends Comparable<K>, V> implements Map<K, V> {
  private K[] keys;    // kept in ascending order
  private V[] values;  // values[i] is the value for keys[i]
  private int size;    // how many pairs the map holds

  // ... the Map operations and the iterators go here
}

Parallel arrays are a valid choice. The class keeps the two arrays aligned, so a caller never sees them, just as a caller never sees size. The cost stays inside the class. values[i] is the value stored under keys[i], so every change to one array has to make the same change to the other: each shift happens twice, and growing means growing both arrays.

Here is what the two arrays hold after put("pear", 3), put("apple", 5), and put("fig", 2):

          0         1        2
keys    ┌─────────┬───────┬────────┬───┬───┐
        │ "apple" │ "fig" │ "pear" │   │ … │
        └─────────┴───────┴────────┴───┴───┘
values  ┌─────────┬───────┬────────┬───┬───┐
        │    5    │   2   │   3    │   │ … │
        └─────────┴───────┴────────┴───┴───┘
size 3

"fig" was added last, but it sits in the middle, because that is where it belongs in sorted order.

Requirements

Every operation must follow the Map contract, and the tests for the chapter’s maps apply unchanged. In addition:

get and containsKey must run in $O (lo g n)$ time.
size must run in $O (1)$ time.
put and remove may run in $O (n)$ time.
When the arrays are full, grow both of them by doubling, as ArrayMap does.
The map is Iterable<K>, and its iterator must visit the keys in ascending order. entries() must visit the pairs in ascending order of their keys.