Assignment #4: 2-d Trees

Implement a data structure that supports two dimensional range queries using a 2-d tree. A 2-d trees stores pairs of items.A 2-d tree is like a binary search tree, except that at even levels branching is done with respect to the first item in the pair, and at odd levels, branching is done with respect to the second item in the pair.

Testing the Class

I will provide a program to test your implementation. Compile the program, and give me the output. Warning: you should probably write another program to make sure everything works.

Requirements

Here is the class interface for cop3530.TwoDimensionSearcher. You will implement your class as cop3530.TwoDTree. You may not change the interface in any way whatsoever. You should not add any new public methods to your implementation, but you can add private member functions as needed to avoid replication of code.

package cop3530;

import java.util.List;

public interface TwoDimensionSearcher<Type1,Type2>
{
    void makeEmpty( );
    boolean isEmpty( );
    boolean add( Pair<Type1,Type2> x );
    int size( );
    List<Pair<Type1,Type2>> getItemsInInterval( Pair<Type1,Type2> lowerLeft, Pair<Type1,Type2> upperRight );
    boolean contains( Pair<Type1,Type2> x );
    Pair<Type1,Type2> makePair( Type1 first, Type2 second );

    public interface Pair<Type1,Type2>
    {
        Type1 getFirst( );
        Type2 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 TwoDTree<Type1,Type2> implements TwoDimensionSearcher<Type1,Type2>
{
private static class LocalPair<Type1,Type2> implements TwoDimensionSearcher.Pair<Type1,Type2>
{ /* Implementation not shown */ }

private static class Node<Type1,Type2>
{ /* Implementation not shown */ }

public TwoDTree( )
{ /* Implementation not shown */ }

public TwoDTree( Comparator<? super Type1> c1, Comparator<? super Type2> c2 )
{ /* Implementation not shown */ }

public void makeEmpty( )
{ /* Implementation not shown */ }

public Pair<Type1,Type2> makePair( Type1 first, Type2 second )
{ /* Implementation not shown */ }

public boolean isEmpty( )
{ /* Implementation not shown */ }

public int size( )
{ /* Implementation not shown */ }

public boolean contains( Pair<Type1,Type2> x )
{ return getItemsInInterval( x, x ).size( ) == 1; }

    public boolean add( Pair<Type1,Type2> x )
    {
        int oldSize = size( );
        root = add( x, root, true ); // call private recursive routine
        return size( ) != oldSize;
    }

private Node<Type1,Type2> add( Pair<Type1,Type2> x, Node<Type1,Type2> t, boolean isEven )
{ /* Implementation not shown */ }

    public List<Pair<Type1,Type2>> getItemsInInterval( Pair<Type1,Type2> lowerLeft, Pair<Type1,Type2> upperRight )
      { /* Implementation not shown;
           may involve use of private recursive routine */ }

    private int size;
    private Node<Type1,Type2> root;
    private Comparator<? super Type1> cmp1;
    private Comparator<? super Type2> cmp2;
}

In implementing this interface you must use a tree of Pairs as the private data (shown as root), along with a size field. You should not need to throw any runtime exceptions.

Observe that signatures all refer to objects of generic type Pair, which is a generic nested interface, and the implementation class defines a private class called LocalPair that implements Pair. A TwoDTree object is created by supplying two java.util.Comparator function objects; 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.

It is very important that you optimize your getItemsInInterval method to avoid going down branches of the tree that cannot possibly produce any items. If you are careful, your algorithm will run in average time that is O( K + log N ) rather than O( N ), where K is the number of items that are found. In particular, this will make your contains method (in which K is 1) logarithmic, on average. If you are careless, the test program will require significant amounts of time.