Maps/SortedArrayMap

Notes

Procedure

Following the Maps/UnsortedArrayMap implementation mainly, here.

While we could have a general parent class, ArrayMap, what we do instead is to repeat our implementation of the ItemIterator utility class. A little bit of copy-pasta, but that's okay.

Next, we define the class itself, which still uses an ArrayList object to store data, but stores it in a sorted order. This makes insertions O(N) or O(log N), depending on the algorithm used.

Code

Git link

The sorted array implementation of a map is at git.charlesreid1.com: https://git.charlesreid1.com/cs/java/src/master/hash/SortedArrayMap.java

This implements the Map ADT - see Maps/ADT.