/**
 * 
 * @author nickgrifasi
 * @version 10/15/21
 * Internal node of PRQuadTree. Recursively continue 
 * through internal nodes until leaf.
 */
public class InternalNode implements BaseNode {
    
    
    /**
     * private fields of BaseNode type. 
     */
    private BaseNode nEast;
    private BaseNode nWest;
    private BaseNode sEast;
    private BaseNode sWest;
    
    /**
     * default constructor for the internalNodes
     */
    public InternalNode()
    {
        this.setUp();
    }
    
    /**
     * sets up constructor by loading each
     * quadrant with flyWeight
     */
    public void setUp()
    {
        nEast = PRQuadtree.FLY_WEIGHT;
        nWest = PRQuadtree.FLY_WEIGHT;
        sEast = PRQuadtree.FLY_WEIGHT;
        sWest = PRQuadtree.FLY_WEIGHT;
    }
    
    /**
     * insertion method for internal node. Recurses
     * until function reaches a leaf or point inserted
     * is internal. 
     * Quadrant rules:
     * 
     * NW: x, y, w/2
     * NE: x + w/2, y, w/2
     * SW: x, y + w/2, w/2
     * SE: x+w/2, y+w/2, w/2
     * @param x x coordinate
     * @param y y coordinate
     * @param width width
     * @param point point inserted
     * @return BaseNode after insertion
     */
    @Override
    public BaseNode insert(int x, int y, int width, Point point)
    {
        
        int quad = width / 2;
        
        
        if ((point.getXCord() < x + (quad)))
        {
            if (point.getYCord() < (y + quad))
            {
                nWest = nWest.insert(x,  y, quad, point);
            }
                
            else 
            {
                sWest = sWest.insert(x,  y + quad, (quad), point);
            }
        }
        
        else if (point.getYCord() < y + (quad))
        {
            nEast = nEast.insert(x + quad, y, quad, point);
        }
        
        else
        {
            sEast = sEast.insert(x + quad, y + quad, quad, point);
        }
        
        return this;
    }
    
    /**
     * method merges the tree after successful removal
     */
    @Override
    public BaseNode mergeTree(int x, int y, int width)
    {
        int quad = width / 2;
        
        nWest.mergeTree(x, y, quad);
        sWest.mergeTree(x, y + quad, quad);
        nEast.mergeTree(x + quad, y, quad);
        sEast.mergeTree(x + quad, y + quad, quad);
        
        int duplicates = 0;
        duplicates = nWest.getNonDupe() + nEast.getNonDupe() +
                sWest.getNonDupe() + sEast.getNonDupe();
        
        if (duplicates == 0)
        {
            return PRQuadtree.FLY_WEIGHT;
        }
        
        if (duplicates <= 3)
        {
            LeafNode leaf = new LeafNode();
            
            while (nWest.getPoint() != null &&
                    nWest.getPoint().getHeadNode() != null)
            {
                leaf.insert(x, y, width, 
                        nWest.getPoint().removeFirst());
            }
            
            while (nEast.getPoint() != null &&
                    nEast.getPoint().getHeadNode() != null)
            {
                leaf.insert(x, y, width, 
                        nEast.getPoint().removeFirst());
            }
            
            while (sWest.getPoint() != null &&
                    sWest.getPoint().getHeadNode() != null)
            {
                leaf.insert(x, y, width, 
                        sWest.getPoint().removeFirst());
            }
            
            while (sEast.getPoint() != null &&
                    sEast.getPoint().getHeadNode() != null)
            {
                leaf.insert(x, y, width, 
                        sEast.getPoint().removeFirst());
            }
            
            return leaf.mergeTree(x, y, width);
            
        }
            
        else
        {
            return this;
        }
    }
    
    /**
     * @param x x coordinate
     * @param y y coordinate
     * @param width width
     * @param point point
     * @param flag flag for SkipList name logic
     * @return point removed from the tree
     */
    public Point remove(int x, int y, int width, Point point,
            boolean flag)
    {
        Point temp = null;
        int quad = width / 2;
        
        if ((point.getXCord() < x + (quad)) &&
                (point.getYCord() < (y + quad)))
        {
            temp = nWest.remove(x, y, quad, point, flag);
            nWest = nWest.mergeTree(x, y, quad);
        }
        
        else if ((point.getXCord() < x + (quad)) && 
                (point.getYCord() >= (y + quad)))
        {
            temp = sWest.remove(x, y + quad, quad, point, flag);
            sWest = sWest.mergeTree(x, y + quad, quad);
        }
        
        else if ((point.getXCord() >= x + (quad)) &&
                point.getYCord() < y + (quad))
        {
            temp = nEast.remove(x + quad, y, quad, point, flag);
            nEast = nEast.mergeTree(x + quad, y, quad);
        }
        
        else if ((point.getXCord() >= x + (quad)) &&
                (point.getYCord() >= y + (quad)))
        {
            temp = sEast.remove(x + quad, y + quad, quad, point, flag);
            sEast = sEast.mergeTree(x + quad, y + quad, quad);
        }
        
        return temp;
        
    }
    
    /**
     * Prints the nodes of PRQuadtree in preorder traversal
     * order. Indents two spaces for each level in the tree.
     * @param x x coordinate
     * @param y y coordinate
     * @param width width
     * @param level visited on the tree
     */
    @Override
    public int dump(int x, int y, int width, int level)
    {
        int quad = width / 2;
        String temp = "";
        int i = 0;
        //each level of the tree is 2 space indent
        while (i < level)
        {
            temp = temp + "  ";
            i++;
        }
        
        temp = temp + "Node at " + x + ", " + y + ", "
                + width + ": Internal";
        System.out.println(temp);
        
        //recursive signature increases level of tree 
        //parameter for each pass
        return 1 + nWest.dump(x, y, quad, level + 1) +
                nEast.dump(x + quad,  y,  quad, level + 1) +
                sWest.dump(x, y + quad, quad, level + 1) +
                sEast.dump(x + quad, y + quad, quad, level + 1);
    }
    
    /**
     * returns number of nonDupe, for internal nodes this will
     * always be 4
     * @return 4 child  nodes
     */
    public int getNonDupe()
    {
        return 4;
    }
    
    /**
     * returns point stored in node. Internal nodes
     * only point to children so always returns null.
     * @return null
     */
    public LinkedList getPoint()
    {
        return null;
    }
    
    /**
     * Returns the duplicates of each leaf quadrant
     */
    @Override
    public void findDuplicates()
    {
        nWest.findDuplicates();
        nEast.findDuplicates();
        sWest.findDuplicates();
        sEast.findDuplicates();
    }
}