#ifndef QUADTREE_HPP
#define QUADTREE_HPP


#include <list>
#include <boost/array.hpp>
#include <boost/unordered_map.hpp>
#include <gmtl/gmtl.h>
#include "spatial_storage_base.hpp"


namespace zserver
{

namespace game
{

namespace storage
{

/******************************************************************************
* quadtree_node
*
* Helper class for quadtree which represents a single node within the tree.
******************************************************************************/
template<class Item, class Locator = locator<Item> >
class quadtree_node
{
    Locator                                         locator_;

    std::list<Item>                                 items_;
    boost::array<quadtree_node<Item, Locator>*, 4>  childs_;
    int                                             depth_;
    gmtl::AABoxf                                    box_;

public:
    /**************************************************************************
    * Parameterized constructor.
    **************************************************************************/
    quadtree_node<Item, Locator>(int depth, gmtl::AABoxf const& box)
        : items_(), childs_(), depth_(depth), box_(box)
    {
        if(depth <= 0)
            return;

        gmtl::Vec3f half_width = gmtl::Vec3f(
                                    (box.getMax()[0] - box.getMin()[0]) / 2.0f,
                                    0.0f,
                                    0.0f);
        gmtl::Vec3f half_height = gmtl::Vec3f(
                                    0.0f,
                                    (box.getMax()[1] - box.getMin()[1]) / 2.0f,
                                    0.0f);

        childs_[0] = new quadtree_node<Item>(
                depth - 1,
                gmtl::AABoxf(
                        box.getMin(),
                        box.getMin() + half_width + half_height));
        childs_[1] = new quadtree_node<Item>(
                depth - 1,
                gmtl::AABoxf(
                        box.getMin() + half_width,
                        box.getMin() + 2.0f * half_width + half_height));
        childs_[2] = new quadtree_node<Item>(
                depth - 1,
                gmtl::AABoxf(
                        box.getMin() + half_height,
                        box.getMin() + half_width + 2.0f * half_height));
        childs_[3] = new quadtree_node<Item>(
                depth - 1,
                gmtl::AABoxf(
                        box.getMin() + half_width + half_height,
                        box.getMin() + 2.0f * half_height + 2.0f * half_width));
    }

    /**************************************************************************
    * Virtual destructor.
    **************************************************************************/
    ~quadtree_node<Item, Locator>()
    {
        for(int i = 0; i < 4; ++i)
        {
            if(childs_[i])
                delete childs_[i];

            childs_[i] = 0;
        }
    }

    /**************************************************************************
    * Insert an item.
    **************************************************************************/
    quadtree_node<Item, Locator>* const insert(Item const& item)
    {
        if(depth_ > 0)
            for(int i = 0; i < 4; ++i)
            {
            std::cout << "isInVolume(" << childs_[i]->box_ << ", " << locator_(item) << ")=" << gmtl::isInVolume(childs_[i]->box_, locator_(item)) << std::endl;
                if(gmtl::isInVolume(childs_[i]->box_, locator_(item)))
                    return childs_[i]->insert(item);
            }

        items_.push_back(item);
        return this;
    }

    /**************************************************************************
    * Remove an item.
    **************************************************************************/
    void remove(Item const& item)
    {
        items_.remove(item);
    }

    /**************************************************************************
    * Find items contained or overlapped by a given box.
    **************************************************************************/
    void find(gmtl::AABoxf const& box, std::list<Item>& collected)
    {
        if(depth_ > 0)
            for(int i = 0; i < 4; ++i)
                if(gmtl::intersect(box, childs_[i]->box_))
                    childs_[i]->find(box, collected);

        collected.insert(collected.end(), items_.begin(), items_.end());
    }
};

/******************************************************************************
* quadtree
*
* Utilizes a quadtree to store items in a spatial manner.
******************************************************************************/
template<class Item, class Locator = locator<Item> >
class quadtree : public spatial_storage_base<Item>
{
    boost::unordered_map<Item,
                         quadtree_node<Item, Locator>*>   item_node_lookup_;
    quadtree_node<Item, Locator>                          root_;

public:
    /**************************************************************************
    * Parameterless constructor.
    **************************************************************************/
    quadtree<Item, Locator>(int depth, gmtl::AABoxf const& box)
        : root_(depth, box)
    {
    }

    /**************************************************************************
    * Virtual destructor.
    **************************************************************************/
    virtual ~quadtree<Item, Locator>()
    {
    }

    /**************************************************************************
    * Insert an item.
    **************************************************************************/
    void insert(Item const& item)
    {
        item_node_lookup_[item] = root_.insert(item);
    }

    /**************************************************************************
    * Remove an item.
    **************************************************************************/
    void remove(Item const& item)
    {
        item_node_lookup_[item]->remove(item);
        item_node_lookup_.erase(item);
    }

    /**************************************************************************
    * Find items contained or overlapped by a given box.
    **************************************************************************/
    std::list<Item> find(gmtl::AABoxf const& box)
    {
        std::list<Item> items;

        root_.find(box, items);

        return items;
    }
};

} // namespace storage

} // namespace game

} // namespace zserver


#endif // QUADTREE_HPP