CSE 131 Module 9: ADT Representations

Bridges


ArrayMap

In the file ArrayMap.java complete the implementation of the class ArrayMap to implement the Map interface. For your internal representation, create an array of references to Pair objects, where each pair contains a domain element (a String) and a range element (a double). Create the array to allow enough space for 100 pairs. One of your representation invariants should be that the array is kept in sorted order according to the values of the String in each pair.

To find the right location in the array for the put, get, contains, and remove methods, use binary search on the array. This will be much more efficient than searching linearly through the array. Note that when you insert an item that belongs somewhere in the middle of the array, you'll have to bump all the items after it down by one to make room for it in the array.

Create a JUnit test case ArrayMapTest.java similar to the others. Again, notice that the test procedure only cares that the object's type implements the map interface. Verify that the output is correct. Look at the printed values of the map to be sure that your array is being kept in sorted order.