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 methods as needed to avoid replication of code.

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 TwoDTree implements TwoDimensionSearcher
{
    private static class LocalPair implements TwoDimensionSearcher.Pair
      { /* Implementation not shown */ }

    private static class Node
      { /* Implementation not shown */ }

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

    public TwoDTree( 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 )
    {
        int oldSize = size( );
        root = add( x, root, true ); // call private recursive routine
        return size( ) != oldSize;
    }

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

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

    private int size;
    private Node root;
    private Comparator cmp1;
    private Comparator 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 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 TwoDTree object is created by supplying two java.util.Comparator function objects (one for even levels, one for odd levels); 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.

Submission Procedure

Submit all your source code, and the results of running the program on the data I will specify. Your source code should include a signed disclaimer that states the work is your own. Your submission must be stapled or otherwise bound together. Failure to follow these instructions will adversely affect your grade for the assignment.

Due Date

This assignment is due on Thursday, October 25.