/*
 * Name - Anisaftab Saiyed
 * ID- 300259073
 * CSI PA2
 */
/*
 * KDtree implements kd tree data structure which compares entering
 * point with different axis'.
 */

public class KDtree{
    /*
     * KDnode is a node in a kdtree which will hold our point.
     */
    public class KDnode{
        /*
         * point is the 3d point which will be stored inside the node.
         */
        public Point3D point;
        /*
         * axis is axis value on whose basis we will insert the kd in the tree
         */
        public int axis;
        /*
         * value is on whose basis we will judge where we will enter the node from the parent node
         */
        public double value;
        /*
         * left is where the left child of the kdnode will go
         */
        public KDnode left;
        /*
         * right is where the right child of the kdnode will go
         */
        public KDnode right;
        /*
         * Constructor of KDnode which will make the node
         * @param pt, a : pt is the point which will be stored inside the node and a is the axis value based on which it was judged
         * 
         */
        KDnode( Point3D pt, int a){
            this.point = pt;
            this.axis = a;
            this.value = pt.get(a);
            left = right = null;
        }

        
    }
    
    /*
     * root is the root node of our kdtree
     */
    private KDnode root;

    /*
     * DIMENSIONS is how many dimensions our points have
     */
    private final int DIMENSIONS = 3;
    /*
     * Constructor of KDtree which will set the root to null
     */
    KDtree(){
        root = null;
    }

    
    /** getRoot provides us the root of the kdtree
     * @return KDnode the root
     */
    public KDnode getRoot(){
        return root;
    }

    
    /** add is the public method which will intercept between outer classes and insert the point given in the tree.
     * @param pt the point which will be added.
     */
    public void add(Point3D pt){
        insert(pt, root, 0);
    }

    
    /** insert actually insert a point into the tree by creating a node
     * @param pt point to be added in the tree
     * @param node the root from which comparison will begin
     * @param axis axis value from which comparison will be done
     * @return KDnode the node which was added in the tree
     */
    private KDnode insert(Point3D pt, KDnode node, int axis){

        if ( this.root == null){
            this.root = new KDnode(pt, axis);
        }
        if( node == null){
            node = new KDnode(pt, axis);
        }
        else if( pt.get(axis) <= node.value){
            node.left = insert(pt, node.left, (axis + 1 )% DIMENSIONS);
        }
        else{
            node.right = insert(pt, node.right, (axis +1) % DIMENSIONS);
        }

        return node; 
    }
    
}