blakeman8192

/*
 * Copyright (C) 2010 Blake Beaupain
 *
 * This program is free software: you can redistribute it and/or modify
 * it under the terms of the GNU General Public License as published by
 * the Free Software Foundation, either version 3 of the License, or
 * (at your option) any later version.
 *
 * This program 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 General Public License for more details.
 *
 * You should have received a copy of the GNU General Public License
 * along with this program.  If not, see <http://www.gnu.org/licenses/>.
 */

package quadtree;

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

/**
 * A node for the Quadtree.
 *
 * @author blakeman8192
 *
 * @param <E>
 *            An Object that extends {@link Locatable}.
 */
public final class QuadtreeNode<E extends Locatable>
{

    private final int minX, minY, maxX, maxY;
    private final List<E> locatables = new ArrayList<E>();
    private QuadtreeNode<E> parent, northwest, northeast, southwest, southeast;

    /**
     * Creates a new <code>QuadtreeNode</code>.
     *
     * @param parent
     *            The parent node.
     * @param minX
     *            The minimum X coordinate.
     * @param minY
     *            The minimum Y coordinate.
     * @param maxX
     *            The maximum X coordinate.
     * @param maxY
     *            The maximum Y coordinate.
     */
    public QuadtreeNode(QuadtreeNode<E> parent, int minX, int minY, int maxX, int maxY)
    {
        this.parent = parent;
        this.minX = minX;
        this.minY = minY;
        this.maxX = maxX;
        this.maxY = maxY;
    }

    /**
     * Gets the subnode of this node that contains the argued {@link Locatable}.
     *
     * @param locatable
     *            The {@link Loctable} to search for.
     * @return The subnode of this node which contains the argued
     *         {@link Locatable}, or <code>null</code> if no subnode of this
     *         node contains the argued {@link Locatable}.
     */
    public QuadtreeNode<E> subnodeContaining(E locatable)
    {
        if (isLeaf())
            return null;

        if (northwest.isWithin(locatable))
            return northwest;
        else if (northeast.isWithin(locatable))
            return northeast;
        else if (southwest.isWithin(locatable))
            return southwest;
        else if (southeast.isWithin(locatable))
            return southeast;

        return null;
    }

    /**
     * Splits this node into four equal sub-nodes, and adds the
     * {@link Locatable} objects of this node into each appropriate sub-node.
     */
    public void split()
    {
        // Split this node into four equal smaller nodes.
        southwest = new QuadtreeNode<E>(this, minX, minY, maxX / 2, maxY / 2);
        southeast = new QuadtreeNode<E>(this, maxX / 2, maxY / 2, maxX, maxY);
        northwest = new QuadtreeNode<E>(this, minX, maxY / 2, maxX / 2, maxY);
        northeast = new QuadtreeNode<E>(this, maxX / 2, maxY / 2, maxX, maxY);

        // Add our locatables into the appropriate new nodes.
        for (E locatable : locatables)
        {
            if (southwest.isWithin(locatable))
                southwest.getLocatables().add(locatable);
            if (southeast.isWithin(locatable))
                southeast.getLocatables().add(locatable);
            if (northwest.isWithin(locatable))
                northwest.getLocatables().add(locatable);
            if (northeast.isWithin(locatable))
                northwest.getLocatables().add(locatable);
        }
    }

    /**
     * Merges each sub-node and every sub-node of each sub-node into this single
     * node, effectively turning this node into a leaf.
     */
    public void merge()
    {
        southwest = null;
        southeast = null;
        northwest = null;
        northeast = null;
    }

    /**
     * Checks if the argued {@link Locatable} is within this node.
     *
     * @param l
     *            The {@link Locatable} to check.
     * @return <code>true</code> if the argued {@link Locatable} is within this
     *         node, <code>false</code> otherwise.
     */
    public boolean isWithin(Locatable l)
    {
        return l.getX() > minX && l.getY() > minY && l.getX() <= maxX && l.getY() <= maxY;
    }

    /**
     * Checks if this node is a leaf node. A leaf node is a node that has not
     * been split.
     *
     * @return <code>true</code> if this node is a leaf node, <code>false</code>
     *         otherwise.
     */
    public boolean isLeaf()
    {
        // If northwest is null, all of them are and this node is a leaf.
        return northwest == null;
    }

    /**
     * Checks if this node is a root node.
     *
     * @return <code>true</code> if this node is a root node, <code>false</code>
     *         otherwise.
     */
    public boolean isRoot()
    {
        return parent == null;
    }

    /**
     * Gets a {@link List} containing the {@link Locatable} objects in this
     * node.
     */
    public List<E> getLocatables()
    {
        return locatables;
    }

    /**
     * Gets the minimum X coordinate of this node.
     */
    public int getMinX()
    {
        return minX;
    }

    /**
     * Gets the minimum Y coordinate of this node.
     */
    public int getMinY()
    {
        return minY;
    }

    /**
     * Gets the maximum X coordinate of this node.
     */
    public int getMaxX()
    {
        return maxX;
    }

    /**
     * Gets the maximum Y coordinate of this node.
     */
    public int getMaxY()
    {
        return maxY;
    }

    /**
     * Gets the width of this node.
     */
    public int getWidth()
    {
        return maxX - minX;
    }

    /**
     * Gets the height of this node.s
     */
    public int getHeight()
    {
        return maxY - minY;
    }

    /**
     * Gets the parent node.
     *
     * @return The parent <code>QuadtreeNode</code>, or <code>null</code> if
     *         this is a root node.
     */
    public QuadtreeNode<E> getParent()
    {
        return parent;
    }

    /**
     * Gets the Northwest node.
     */
    public QuadtreeNode<E> getNorthwest()
    {
        return northwest;
    }

    /**
     * Gets the Northeast node.
     */
    public QuadtreeNode<E> getNortheast()
    {
        return northeast;
    }

    /**
     * Gets the Southwest node.
     */
    public QuadtreeNode<E> getSouthwest()
    {
        return southwest;
    }

    /**
     * Gets the Southeast node.
     */
    public QuadtreeNode<E> getSoutheast()
    {
        return southeast;
    }

}