package Minor3.DS;
import java.io.FileWriter;
import java.io.IOException;
import java.util.Vector;

//  A note on the meaning of "matching"...
//
//  When comparing two objects of type T, you could use either the
//  equals() method or the compare2D() method.  For this assignment,
//  those two methods are guaranteed to be consistent.  That is, 
//  A.equals(B) will return true iff A.compare2D(B) returns NONE.
//  
//  We fuss about that because the Java language specification does,
//  in fact, explicitly allow equals() and compareTo() to disagree.

public class prQuadtree< T extends TwoDComparable<? super T> > {
	
    // You must use a hierarchy of node types with an abstract base
    // class.  You may use different names for the node types if
    // you like (change displayHelper() accordingly).
	public class prQuadNode {
		// abstract class
	}
	public class prQuadLeaf extends prQuadNode {
		// members and public interface are up to you
	}
    public class prQuadInternal extends prQuadNode {
		// members and public interface are up to you
    }
    
    prQuadNode root;                // pointer to root node, if any
    long xMin, xMax, yMin, yMax;    // world boundaries
    
    public prQuadtree(long xMin, long xMax, long yMin, long yMax) {
        // details are up to you
    }
    
    //  If Elem does not match an element already in the tree insert Elem 
    //  into the tree.  Return true unless the insertion is not performed.
    public boolean insert(T Elem) {
        // details are up to you
        return false;
    }
    
    //  If Elem matches an element in the tree delete that matching 
    //  element from the tree.
    //  Return true unless the deletion is not performed.
    public boolean delete(T Elem) {
        // details are up to you
        return false;
    }
    
    //  Search for an element that matches Elem; return a reference to the
    //  matching element.
    public T find(T Elem) {
        // details are up to you
        return null;                     // if no matching element is found
    }
    
    //  Search efficiently for elements that lie within the rectangle specified
    //  by the parameters.  You should avoid descending into branches of the 
    //  tree if it's possible to logically determine that the subtree root node
    //  corresponds to a square that does not have any intersection with the
    //  given search region.
    //
    //  The search should include elements that lie on the boundary of the
    //  search region.
    //
    //  The returned Vector object should contain references to all the elements
    //  that fell within the search region, if any.
    public Vector<T> find(long xLeft, long xRight, long yLow, long YHigh) {
        // details are up to you
        return null;                     // if no matching elements are found
    }
    
    // Do not modify the given display code in any way that would alter
    // the formatting of the display.  Other modifications, such as the
    // node class names should be transparent to the caller, so those
    // should be OK.
    public void display(FileWriter Out) {
    	try {
           if ( root == null ) {
              Out.write( " Empty tree.\n" );
           }
           else
              displayHelper(Out,  root, "");
    	}
    	catch ( IOException e ) {
    		return;
    	}
     }

	public void displayHelper(FileWriter Out, prQuadNode sRoot, String Padding) {

		try {
			String pExtend = "---";
			// Check for empty leaf
			if ( sRoot == null ) {
				Out.write(Padding + "*\n");
				return;
			}
			// Check for and process SW and SE subtrees
			if ( sRoot.getClass().getName().equals("Minor3.DS.prQuadtree$prQuadInternal") ) {
				prQuadInternal p = (prQuadInternal) sRoot;
				displayHelper(Out, p.SW, Padding + pExtend);
				displayHelper(Out, p.SE, Padding + pExtend);
			}

			// Determine if at leaf or internal and display accordingly
            Out.write(Padding);
			if ( sRoot.getClass().getName().equals("Minor3.DS.prQuadtree$prQuadLeaf") ) {
				prQuadLeaf p = (prQuadLeaf) sRoot;
				for (int pos = 0; pos < p.Elements.size(); pos++) {
					Out.write(p.Elements.get(pos) + "  " );   // uses data object's toString() method
				}
				Out.write("\n");
			}
			else if ( sRoot.getClass().getName().equals("Minor3.DS.prQuadtree$prQuadInternal") )
				Out.write("@\n" );
			else
				Out.write(sRoot.getClass().getName() + "#\n");

			// Check for and process NE and NW subtrees
			if ( sRoot.getClass().getName().equals("Minor3.DS.prQuadtree$prQuadInternal") ) {
				prQuadInternal p = (prQuadInternal) sRoot;
				displayHelper(Out, p.NE, Padding + pExtend);
				displayHelper(Out, p.NW, Padding + pExtend);
			}
		}
		catch ( IOException e ) {
			return;
		}
	}

}