// Path: src/main/java/algs/model/IPoint.java
// public interface IPoint extends Comparable<IPoint> {
// 	
// 	/**
// 	 * Globally useful sorter, that first sorts by x, and then by y coordinate.
// 	 * 
// 	 * Useful for determining full ordering of IPoint objects over a Cartesian Plane.
// 	 */
// 	public static Comparator<IPoint> xy_sorter =
// 		new Comparator<IPoint>() {
// 
// 			/**
// 			 * Compares two 2-dimensional points in the Cartesian plane.
// 			 * 
// 			 * Handles null values as follows. 
// 			 * <ol>
// 			 * <ul>If one is null && two is null, then 0 is returned (an exact null match).
// 			 * <ul>Else if one is null, then return -1
// 			 * <ul>Else if two is null, then return +1
// 			 * </ol> 
// 			 * 
// 			 * @param one
// 			 * @param two
// 			 */
// 			public int compare(IPoint one, IPoint two) {
// 				if (one == null) {
// 					if (two == null) { 
// 						return 0; 
// 					}
// 					return -1;
// 				} else if (two == null) { 
// 					return +1; 
// 				}
// 				
// 				double fp = FloatingPoint.value(one.getX() - two.getX());
// 				if (fp < 0) { return -1; }
// 				if (fp > 0) { return +1; }
// 				
// 				fp = FloatingPoint.value(one.getY() - two.getY());
// 				if (fp < 0) { return -1; }
// 				if (fp > 0) { return +1; }
// 				
// 				// same exact (x,y) points
// 				return 0;
// 			}
// 
// 	};	
// 	
// 	/** 
// 	 * Return the x-coordinate value for the given point.
// 	 * @return x-coordinate for point. 
// 	 */
// 	double getX();
// 	
// 	/**
// 	 * Return the y-coordinate value for the given point. 
//  	 * @return y-coordinate for point. 
// 	 */
// 	double getY();
// }


import java.util.ArrayList;
import java.util.ConcurrentModificationException;
import java.util.Iterator;
import algs.model.IPoint;

package algs.model.kdtree;



/**
 * Enables quick intersection detection by KD Tree and places burden
 * of extraction onto the client retrieving the points using an iterator.
 *
 * Single points can be added, as well as entire subtrees. The order of the
 * points being returned doesn't matter, so this iterator maintains two
 * separate lists over which to be iterated.
 * 
 * Once {@link #hasNext()} is invoked, no more points can be added.
 * @since 2.0
 * @author George Heineman
 * @version 2.0, 4/25/15
 */
public class TwoDSearchResults implements Iterator<IPoint> {
	/** Storage of nodes. */
	ArrayList<TwoDNode> nodes = new ArrayList<TwoDNode>();
	
	/** Storage of points. */
	ArrayList<IPoint> points = new ArrayList<IPoint>();
	
	/** Once begun, start with points iterator. */
	Iterator<IPoint> pointsIterator = null;
	
	
	/** Once true, iteration has begun and no more points or nodes can be added. */
	boolean inProgress = false;
	
	public TwoDSearchResults () {
		
	}
	
	/**
	 * Add point to the result set.
	 * 
	 * @exception ConcurrentModificationException    if iterator already begun
	 * @param pt   point being added
	 */
	public void add(IPoint pt) {
		if (inProgress) { 
			throw new ConcurrentModificationException ("Can't add point while iterator in progress");
		}
		points.add(pt);
	}
	
	/**
	 * Add subtree rooted at given node to the result set.
	 * 
	 * @exception ConcurrentModificationException    if iterator already begun
	 * @param dn    node that is root of tree containing all points to be added.
	 */
	public void add(TwoDNode dn) {

// Path: src/main/java/algs/model/IPoint.java
// public interface IPoint extends Comparable<IPoint> {
// 	
// 	/**
// 	 * Globally useful sorter, that first sorts by x, and then by y coordinate.
// 	 * 
// 	 * Useful for determining full ordering of IPoint objects over a Cartesian Plane.
// 	 */
// 	public static Comparator<IPoint> xy_sorter =
// 		new Comparator<IPoint>() {
// 
// 			/**
// 			 * Compares two 2-dimensional points in the Cartesian plane.
// 			 * 
// 			 * Handles null values as follows. 
// 			 * <ol>
// 			 * <ul>If one is null && two is null, then 0 is returned (an exact null match).
// 			 * <ul>Else if one is null, then return -1
// 			 * <ul>Else if two is null, then return +1
// 			 * </ol> 
// 			 * 
// 			 * @param one
// 			 * @param two
// 			 */
// 			public int compare(IPoint one, IPoint two) {
// 				if (one == null) {
// 					if (two == null) { 
// 						return 0; 
// 					}
// 					return -1;
// 				} else if (two == null) { 
// 					return +1; 
// 				}
// 				
// 				double fp = FloatingPoint.value(one.getX() - two.getX());
// 				if (fp < 0) { return -1; }
// 				if (fp > 0) { return +1; }
// 				
// 				fp = FloatingPoint.value(one.getY() - two.getY());
// 				if (fp < 0) { return -1; }
// 				if (fp > 0) { return +1; }
// 				
// 				// same exact (x,y) points
// 				return 0;
// 			}
// 
// 	};	
// 	
// 	/** 
// 	 * Return the x-coordinate value for the given point.
// 	 * @return x-coordinate for point. 
// 	 */
// 	double getX();
// 	
// 	/**
// 	 * Return the y-coordinate value for the given point. 
//  	 * @return y-coordinate for point. 
// 	 */
// 	double getY();
// }


// Path: src/main/java/algs/model/kdtree/TwoDSearchResults.java
import java.util.ArrayList;
import java.util.ConcurrentModificationException;
import java.util.Iterator;
import algs.model.IPoint;

package algs.model.kdtree;



/**
 * Enables quick intersection detection by KD Tree and places burden
 * of extraction onto the client retrieving the points using an iterator.
 *
 * Single points can be added, as well as entire subtrees. The order of the
 * points being returned doesn't matter, so this iterator maintains two
 * separate lists over which to be iterated.
 * 
 * Once {@link #hasNext()} is invoked, no more points can be added.
 * @since 2.0
 * @author George Heineman
 * @version 2.0, 4/25/15
 */
public class TwoDSearchResults implements Iterator<IPoint> {
	/** Storage of nodes. */
	ArrayList<TwoDNode> nodes = new ArrayList<TwoDNode>();
	
	/** Storage of points. */
	ArrayList<IPoint> points = new ArrayList<IPoint>();
	
	/** Once begun, start with points iterator. */
	Iterator<IPoint> pointsIterator = null;
	
	
	/** Once true, iteration has begun and no more points or nodes can be added. */
	boolean inProgress = false;
	
	public TwoDSearchResults () {
		
	}
	
	/**
	 * Add point to the result set.
	 * 
	 * @exception ConcurrentModificationException    if iterator already begun
	 * @param pt   point being added
	 */
	public void add(IPoint pt) {
		if (inProgress) { 
			throw new ConcurrentModificationException ("Can't add point while iterator in progress");
		}
		points.add(pt);
	}
	
	/**
	 * Add subtree rooted at given node to the result set.
	 * 
	 * @exception ConcurrentModificationException    if iterator already begun
	 * @param dn    node that is root of tree containing all points to be added.
	 */
	public void add(TwoDNode dn) {

		if (inProgress) { 
