/*
 * PointRegionQuadTree  -- A QuadTree data structure for storing XYPoint objects.
 *
 * Copyright (C) 2018, by Joseph A. Huwaldt
 * All rights reserved.
 *
 * This library is free software; you can redistribute it and/or
 * modify it under the terms of the GNU Lesser General Public
 * License as published by the Free Software Foundation; either
 * version 2.1 of the License, or (at your option) any later version.
 *
 * This library is distributed in the hope that it will be useful,
 * but WITHOUT ANY WARRANTY; without even the implied warranty of
 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
 * Lesser General Public License for more details.
 *
 * You should have received a copy of the GNU Lesser General Public
 * License along with this library; if not, write to the Free Software
 * Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston,
 * MA 02110-1301  USA
 */
package jahuwaldt.util;

import java.util.Collections;
import java.util.LinkedList;
import java.util.List;

/**
 * A QuadTree data structure for storing 2D XYPoint objects.
 * 
 * <p> Modified by: Joseph A. Huwaldt </p>
 *
 * @author Joseph A. Huwaldt, Date: February 5, 2018
 * @version February 5, 2018
 * @param <P> The type of XYPoint stored in the QuadTree.
 */
public class PointRegionQuadTree<P extends XYPoint> {

    private QuadNode<P> root = null;

    //  A mutable AABB that is used as part of the queryRange() method.
    private final AxisAlignedBoundingBox RANGE = new AxisAlignedBoundingBox();

    /**
     * Create a QuadTree who's upper left coordinate is located at x,y and it's bounding
     * box is described by the height and width.
     *
     * @param xyPoint XYPoint representing the min-X, min-Y corner of the bounding box of
     *                all the 2D points.
     * @param width   Width of the bounding box containing all points
     * @param height  Height of the bounding box containing all points
     */
    public PointRegionQuadTree(P xyPoint, double width, double height) {
        AxisAlignedBoundingBox aabb = new AxisAlignedBoundingBox(xyPoint, width, height);
        root = new QuadNode(aabb);
    }

    /**
     * Range query of the QuadTree. Return all the points in the quad-tree that fall in
     * the specified bounding box.
     *
     * @param x      The minimum X-coordinate of the region to search for points in.
     * @param y      The minimum Y-coordinate of the region to search for points in.
     * @param width  The width of the region to search for points in.
     * @param height The height of the region to search for points in.
     * @return A collection of points that fall in the search region.
     */
    public List<P> queryRange(double x, double y, double width, double height) {
        if (root == null)
            return Collections.EMPTY_LIST;

        RANGE.set(x, y, width, height);

        List<P> pointsInRange = new LinkedList();
        root.queryRange(RANGE, pointsInRange);
        return pointsInRange;
    }

    /**
     * Insert point at X,Y into tree.
     *
     * @param xyPoint The 2D point to insert.
     * @return True if the point was successfully inserted.
     */
    public boolean insert(P xyPoint) {
        return root.insert(xyPoint);
    }

    /**
     * Remove point at X,Y from tree.
     *
     * @param xyPoint The 2D point to remove.
     * @return True of the point was successfully removed from the tree.
     */
    public boolean remove(P xyPoint) {
        return root.remove(xyPoint);
    }

    /**
     * A node for use in a PointRegionQuadTree.
     *
     * @param <P> The type of point stored in the node.
     */
    private static class QuadNode<P extends XYPoint> {

        private final AxisAlignedBoundingBox aabb;

        private QuadNode northWest = null;
        private QuadNode northEast = null;
        private QuadNode southWest = null;
        private QuadNode southEast = null;

        // max number of children before sub-dividing
        private static final int MAX_CAPACITY = 4;

        private List<P> points = new LinkedList();
        private int height = 1;

        public QuadNode(AxisAlignedBoundingBox aabb) {
            this.aabb = aabb;
        }

        /**
         * Insert object into tree.
         *
         * @param p The 2D point to insert into tree.
         * @return True if successfully inserted.
         */
        public boolean insert(P p) {
            // Ignore objects which do not belong in this quad tree
            if (!aabb.containsPoint(p) || (isLeaf() && points.contains(p)))
                return false; // object cannot be added

            // If there is space in this quad tree, add the object here
            if (isLeaf() && points.size() < MAX_CAPACITY) {
                points.add(p);
                return true;
            }

            // Otherwise, we need to subdivide then add the point to whichever node will accept it
            if (isLeaf())
                subdivide();

            return insertIntoChildren(p);
        }

        /**
         * Remove object from tree.
         *
         * @param p The 2D Point to remove from tree.
         * @return True if successfully removed.
         */
        public boolean remove(P p) {
            // If not in this AABB, don't do anything
            if (!aabb.containsPoint(p))
                return false;

            // If in this AABB and in this node
            if (points.remove(p))
                return true;

            // If this node has children
            if (!isLeaf()) {
                // If in this AABB but in a child branch
                boolean removed = removeFromChildren(p);
                if (!removed)
                    return false;

                // Try to merge children
                merge();

                return true;
            }

            return false;
        }

        /**
         * How many Point objects this node contains.
         *
         * @return Number of Point objects this node contains.
         */
        public int size() {
            return points.size();
        }

        private void subdivide() {
            double h = aabb.height * 0.5;
            double w = aabb.width * 0.5;

            double x = aabb.getMinX();
            double y = aabb.getMinY();
            AxisAlignedBoundingBox aabbNW = new AxisAlignedBoundingBox(x,y, w,h);
            northWest = new QuadNode(aabbNW);
            northWest.height = height + 1;

            x = aabb.getMinX() + w;
            y = aabb.getMinY();
            AxisAlignedBoundingBox aabbNE = new AxisAlignedBoundingBox(x,y, w,h);
            northEast = new QuadNode(aabbNE);
            northEast.height = height + 1;

            x = aabb.getMinX();
            y = aabb.getMinY() + h;
            AxisAlignedBoundingBox aabbSW = new AxisAlignedBoundingBox(x,y, w,h);
            southWest = new QuadNode(aabbSW);
            southWest.height = height + 1;

            x = aabb.getMinX() + w;
            y = aabb.getMinY() + h;
            AxisAlignedBoundingBox aabbSE = new AxisAlignedBoundingBox(x,y, w,h);
            southEast = new QuadNode(aabbSE);
            southEast.height = height + 1;

            // points live in leaf nodes, so distribute
            for (P p : points)
                insertIntoChildren(p);
            points.clear();
        }

        private void merge() {
            // If the children aren't leaves, you cannot merge
            if (!northWest.isLeaf() || !northEast.isLeaf() || !southWest.isLeaf() || !southEast.isLeaf())
                return;

            // Children and leaves, see if you can remove points and merge into this node
            int nw = northWest.size();
            int ne = northEast.size();
            int sw = southWest.size();
            int se = southEast.size();
            int total = nw + ne + sw + se;

            // If all the children's points can be merged into this node
            if ((size() + total) < MAX_CAPACITY) {
                this.points.addAll(northWest.points);
                this.points.addAll(northEast.points);
                this.points.addAll(southWest.points);
                this.points.addAll(southEast.points);

                this.northWest = null;
                this.northEast = null;
                this.southWest = null;
                this.southEast = null;
            }
        }

        private boolean insertIntoChildren(P p) {
            // A point can only live in one child.
            if (northWest.insert(p))
                return true;
            if (northEast.insert(p))
                return true;
            if (southWest.insert(p))
                return true;
            return southEast.insert(p);
        }

        private boolean removeFromChildren(P p) {
            // A point can only live in one child.
            if (northWest.remove(p))
                return true;
            if (northEast.remove(p))
                return true;
            if (southWest.remove(p))
                return true;
            return southEast.remove(p);
        }

        /**
         * Find all objects which appear within a range.
         *
         * @param range         Upper-left and width,height of a axis-aligned bounding
         *                      box.
         * @param pointsInRange The existing list that will be filled with the XYPoint
         *                      objects that are inside the bounding box.
         */
        public void queryRange(AxisAlignedBoundingBox range, List<P> pointsInRange) {
            // Automatically abort if the range does not collide with this quad
            if (!aabb.intersectsBox(range))
                return;

            // If leaf, check objects at this level
            if (isLeaf()) {
                for (P xyPoint : points) {
                    if (range.containsPoint(xyPoint))
                        pointsInRange.add(xyPoint);
                }
                return;
            }

            // Otherwise, add the points from the children
            northWest.queryRange(range, pointsInRange);
            northEast.queryRange(range, pointsInRange);
            southWest.queryRange(range, pointsInRange);
            southEast.queryRange(range, pointsInRange);
        }

        /**
         * Is current node a leaf node.
         *
         * @return True if node is a leaf node.
         */
        public boolean isLeaf() {
            return (northWest == null && northEast == null && southWest == null && southEast == null);
        }

    }

    /**
     * An axis-aligned bounding box for use in a quad-tree.
     */
    private static class AxisAlignedBoundingBox {

        private double height = 0;
        private double width = 0;

        private double minX = 0;
        private double minY = 0;
        private double maxX = 0;
        private double maxY = 0;

        public AxisAlignedBoundingBox() { }

        public AxisAlignedBoundingBox(double minX, double minY, double width, double height) {
            this.width = width;
            this.height = height;

            this.minX = minX;
            this.minY = minY;
            maxX = minX + width;
            maxY = minY + height;
        }

        public AxisAlignedBoundingBox(AxisAlignedBoundingBox aabb, double width, double height) {
            this.width = width;
            this.height = height;

            minX = aabb.minX;
            minY = aabb.minY;
            maxX = minX + width;
            maxY = minY + height;
        }

        public AxisAlignedBoundingBox(XYPoint upperLeft, double width, double height) {
            this.width = width;
            this.height = height;

            minX = upperLeft.getX();
            minY = upperLeft.getY();
            maxX = minX + width;
            maxY = minY + height;
        }

        public void set(double minX, double minY, double width, double height) {
            this.width = width;
            this.height = height;

            this.minX = minX;
            this.minY = minY;
            maxX = minX + width;
            maxY = minY + height;
        }

        public double getMinX() {
            return minX;
        }

        public double getMinY() {
            return minY;
        }

        public double getHeight() {
            return height;
        }

        public double getWidth() {
            return width;
        }

        public boolean containsPoint(XYPoint p) {
            double px = p.getX();
            double py = p.getY();
            if (px >= maxX)
                return false;
            if (px < minX)
                return false;
            if (py >= maxY)
                return false;
            return py >= minY;
        }

        /**
         * Is the inputted AxisAlignedBoundingBox completely inside this
         * AxisAlignedBoundingBox.
         *
         * @param b AxisAlignedBoundingBox to test.
         * @return True if the AxisAlignedBoundingBox is completely inside this
         *         AxisAlignedBoundingBox.
         */
        public boolean insideThis(AxisAlignedBoundingBox b) {
            return b.minX >= minX && b.maxX <= maxX && b.minY >= minY && b.maxY <= maxY;
        }

        /**
         * Is the inputted AxisAlignedBoundingBox intersecting this
         * AxisAlignedBoundingBox.
         *
         * @param b AxisAlignedBoundingBox to test.
         * @return True if the AxisAlignedBoundingBox is intersecting this
         *         AxisAlignedBoundingBox.
         */
        public boolean intersectsBox(AxisAlignedBoundingBox b) {
            if (insideThis(b) || b.insideThis(this)) {
                // INSIDE
                return true;
            }

            // OUTSIDE
            if (maxX < b.minX || minX > b.maxX)
                return false;
            return !(maxY < b.minY || minY > b.maxY);
        }

    }

}