package cop3530;
import java.util.List;
public interface TwoDimensionSearcher
{
void makeEmpty( );
boolean isEmpty( );
boolean add( Pair x );
int size( );
List getItemsInInterval( Pair lowerLeft, Pair
upperRight );
boolean contains( Pair x );
Pair makePair( Object first, Object second );
public interface Pair
{
Object getFirst( );
Object getSecond( );
}
}
Here is the rough outline of the implementation:
package cop3530;
import java.util.Comparator;
import java.util.List;
import java.util.ArrayList;
public class TwoDList implements TwoDimensionSearcher
{
private static class LocalPair implements TwoDimensionSearcher.Pair
{ /* Implementation not shown */
}
public TwoDList( )
{ /* Implementation not shown */
}
public TwoDList( Comparator c1, Comparator c2
)
{ /* Implementation not shown */
}
public void makeEmpty( )
{ /* Implementation not shown */
}
public Pair makePair( Object first, Object second )
{ /* Implementation not shown */
}
public boolean isEmpty( )
{ /* Implementation not shown */
}
public int size( )
{ /* Implementation not shown */
}
public boolean contains( Pair
x )
{ return getItemsInInterval( x,
x ).size( ) == 1; }
public boolean add( Pair
x )
{ /* Implementation not shown */
}
public List getItemsInInterval( Pair lowerLeft, Pair
upperRight )
{ /* Implementation not shown */
}
private int size;
private Pair [ ] arr = new Pair[ 5 ];
private Comparator cmp1;
private Comparator cmp2;
}
In implementing this interface you must use an array of Pairs as the private data (shown as arr), along with a size field. You should not need to throw any runtime exceptions. The array arr initially starts with length 5, and is doubled in the add routine when capacity is reached. You may not replace this with any of the java.util.List implementations. Also, note that duplicates are not allowed, and add returns false if an attempt is made to insert a duplicate item. An item is a duplicate if the comparators say so (specifically, DO NOT use equals to make the determination.
Observe that signatures all refer to objects of type Pair, which in turn refers to two Objects. The interface defines a nested interface Pair, and the implementation class defines a private class called LocalPair that implements Pair. A TwoDList object is created by supplying two java.util.Comparator function objects (the first Comparator compares first components of the pair, and the second Comparator compares second components of the pair); if none is given, it is assumed that the items in the pairs all implement the java.lang.Comparable interface and can be compared by calling compareTo.
If you are careless, the test program will require significant amounts of time.