package cop3530;
public interface Map
{
boolean isEmpty( );
void makeEmpty( );
int size( );
Object put( Object key, Object value );
Object get( Object key );
void remove( Object key );
java.util.Iterator getIterator( ); //non standard
public interface Entry
{
Object getKey( );
Object getValue( );
void setValue( Object value );
}
}
In interface Map, observe the following:
Here is the rough outline of the implementation:
package cop3530;
import java.util.Comparator;
import java.util.NoSuchElementException;
public class SortedArrayMap implements Map
{
public SortedArrayMap( )
{ /* Implementation not shown */ }
public SortedArrayMap( Comparator c )
{ /* Implementation not shown */ }
public boolean isEmpty( )
{ /* Implementation not shown */ }
public void makeEmpty( )
{ /* Implementation not shown */ }
public int size( )
{ /* Implementation not shown */ }
public Object put( Object key, Object value )
{ /* Implementation not shown */ }
public Object get( Object key )
{ /* Implementation not shown */ }
public void remove( Object key )
{ /* Implementation not shown */ }
public java.util.Iterator getIterator( )
{ return new LocalIterator( ); }
private class LocalIterator implements java.util.Iterator
{
/* next and hasNext not shown */
public void remove( )
{
if( !okToRemove )
throw new IllegalStateException( );
okToRemove = false; // two removes in a row not allowed
SortedArrayMap.this.remove( entries[ --current ].getKey( ) );
}
private int current = 0;
private boolean okToRemove = false; // set to true in next
}
private static class Pair implements Map.Entry
{ /* Implementation not shown */ }
private Pair [] entries;
private int theSize;
private Comparator cmp;
}
A SortedArrayMap object is created by supplying a java.util.Comparator function object that determines the sorted order; if none is given, it is assumed that the keys all implement the java.lang.Comparable interface and can be compared by calling compareTo. The cmp private data member should be initialized by the constructor(s). For the zero parameter constructor, initialize cmp to an instance of a default Comparator, as discussed in class.
In implementing the SortedArrayMap you must use a sorted array of Pairs as the private data (shown as entries), along with a theSize field. You should not need to throw any runtime exceptions. The array entries initially starts with length 5, and is doubled in the put routine when capacity is reached. You may not replace this with any of the java.util.List implementations. Also, note that duplicate keys are not allowed, and put overrides the existing value for a key with the new value if an attempt is made to put an already seen key. A key is already seen if the comparator says so (specifically, DO NOT use equals to make the determination.
Your implementation will almost certainly want to add some private methods to perform some of the repetitive tedious work.
The Map interface defines a nested interface Entry, and the implementation class defines a private class called Pair that implements Map.Entry. This implementation should be relatively trivial: it stores a key and value (both as Object), implements the three Map.Entry public methods in one line each, and provides a public two parameter constructor.
Finally, the implementation of SortedArrayMap requires that you implement the LocalIterator class, which itself implements the Iterator interface. This one is fairly tricky to code. You are not required to detect ConcurrentModificationExceptions (i.e. changes to the Map made by others outside of the iterator). But you should throw a NoSuchElementException if the call to next is out-of-bounds. I have provided an implementation of the trickiest part of LocalIterator; you have to fill in the rest. The implementation shows that it is ok to call remove only if the last call to next has not already had a call to remove made.
For this assignment only, it is important that you provide Javadoc comments for both the Map interface and the SortedArrayMap class.