/*
 * Name - Anisaftab Saiyed
 * ID- 300259073
 * CSI PA2
 */


import java.util.List;
import java.util.ArrayList;


/*
 * NearestNeighboursKD makes the kdtree from a array list and then finds the 
 * nearby neighbors within eps of a given point.
 */
public class NearestNeighborsKD{
    /*
     * kdtree is our tree of kd tree data structure
     */
    KDtree kdTree;
    /*
     * neighbors of a given point stored in a list
     */
    List<Point3D> neighbors;
    /*
     * Constructor which accepts the list of all the points and 
     * makes a kdtree from all the points.
     */
    public NearestNeighborsKD(List<Point3D> list) {

      kdTree = new KDtree();
      for( Point3D p : list){
        kdTree.add(p);
      }  
      neighbors = new ArrayList<Point3D>();
      

    }

    
    /** getTree returns the kdtree containing all the points
     * @return KDtree
     */
    public KDtree getTree(){
      return this.kdTree;
    }

    
    /** This method acts as an intercept between outer classes and calls rangeQuery method.
     * @param p the point whose neighbor we have to find
     * @param eps euclidean min. distance within which we will finds neighboring points
     * @return List<Point3D> list of neighbors of p
     */
    public List<Point3D> getNeighbors(Point3D p, double eps){
      
      rangeQuery(p, eps, neighbors, getTree().getRoot());
      return neighbors;
    }
    
    /** This method finds the neighbors of a given point within eps using kd search.
     * @param p the point whose neighbor we have to find
     * @param eps euclidean min. distance within which we will finds neighboring points
     * @param neighbors neighbors list where we will store nearby points
     * @param node starting node of kdtree fro where we will start search
     */
    private void rangeQuery(Point3D p, double eps, List<Point3D> neighbors, KDtree.KDnode node ){

      
      if(node == null){
        return;
      }
      if( p.distance(node.point) < eps){
        neighbors.add(node.point);
      }
      if ( p.get(node.axis) - eps <= node.value){
        rangeQuery(p, eps, neighbors, node.left);
      }
      if( p.get(node.axis) + eps > node.value){
        rangeQuery(p, eps, neighbors, node.right);
      }
      return;
    }

    
}