/*]  Copyright (c) 2009-2010, Charles McGarvey  [**************************
**]  All rights reserved.
*
* vi:ts=4 sw=4 tw=75
*
* Distributable under the terms and conditions of the 2-clause BSD license;
* see the file COPYING for a complete text of the license.
*
**************************************************************************/

#ifndef _MOOF_OCTREE_HH_
#define _MOOF_OCTREE_HH_

#include <algorithm>
#include <list>

#include <boost/shared_ptr.hpp>
#include <stlplus/ntree.hpp>

#include <Moof/Aabb.hh>
#include <Moof/Drawable.hh>
#include <Moof/Entity.hh>
#include <Moof/Frustum.hh>
#include <Moof/Log.hh>
#include <Moof/Math.hh>
#include <Moof/Sphere.hh>
	

namespace Mf {


struct OctreeInsertable
{
	virtual ~OctreeInsertable() {}

	virtual int getOctant(const Aabb<3>& aabb) const = 0;
};


template <class T>
class Octree : public Entity
{
	typedef boost::shared_ptr<T> InsertableP;

	struct Node : public Entity
	{
		std::list<InsertableP> objects;

		Node(const Aabb<3>& aabb)
		{
			mAabb = aabb;
			mSphere.point = mAabb.getCenter();
			mSphere.radius = (mAabb.min - mSphere.point).length();
		}

		void draw(Scalar alpha) const
		{
			mAabb.draw(alpha);
		}

		void printSize()
		{
			logInfo << "size of node " << objects.size() << std::endl;
		}

		void getAll(std::list<InsertableP>& insertables) const
		{
			insertables.insert(insertables.end(), objects.begin(),
					objects.end());
		}

		void getIfVisible(std::list<InsertableP>& insertables,
				const Frustum& frustum) const
		{
			typename std::list<InsertableP>::const_iterator it;

			for (it = objects.begin(); it != objects.end(); ++it)
			{
				if ((*it)->isVisible(frustum)) insertables.push_back(*it);
			}
		}
	};


public:

	typedef boost::shared_ptr<Octree> Ptr;
	typedef typename stlplus::ntree<Node>::iterator NodeP;
	
private:


	NodeP insert(InsertableP entity, NodeP node)
	{
		ASSERT(node.valid() && "invalid node passed");
		ASSERT(entity && "null entity passed");

		Aabb<3> entityAabb = entity->getAabb();
		Aabb<3> nodeAabb = node->getAabb();

		if (!(entityAabb.max[0] < nodeAabb.max[0] &&
			  entityAabb.min[0] > nodeAabb.min[0] &&
			  entityAabb.max[1] < nodeAabb.max[1] &&
			  entityAabb.min[1] > nodeAabb.min[1] &&
			  entityAabb.max[2] < nodeAabb.max[2] &&
			  entityAabb.min[2] > nodeAabb.min[2]))
		{
			node->objects.push_back(entity);
			return node;
		}
		else
		{
			return insert_recurse(entity, node);
		}
	}

	NodeP insert_recurse(InsertableP entity, NodeP node)
	{
		ASSERT(node.valid() && "invalid node passed");
		ASSERT(entity && "null entity passed");

		int octantNum = entity->getOctant(node->getAabb());
		if (octantNum == -1)
		{
			node->objects.push_back(entity);
			return node;
		}
		else
		{
			if ((int)mTree.children(node) <= octantNum)
			{
				addChild(node, octantNum);
			}

			NodeP child = mTree.child(node, octantNum);
			ASSERT(child.valid() && "expected valid child node");

			return insert_recurse(entity, child);
		}
	}

	void addChild(NodeP node, int index)
	{
		ASSERT(node.valid() && "invalid node passed");

		Aabb<3> octant;

		for (int i = mTree.children(node); i <= index; ++i)
		{
			node->getAabb().getOctant(octant, i);
			mTree.append(node, octant);
		}
	}


	void getNearbyObjects(std::list<InsertableP>& insertables,
			const OctreeInsertable& entity, NodeP node) const
	{
		ASSERT(node.valid() && "invalid node passed");

		node->printSize();

		int octantNum = entity.getOctant(node->getAabb());
		if (octantNum != -1)
		{
			node->getAll(insertables);

			if (octantNum < (int)mTree.children(node))
			{
				NodeP child = mTree.child(node, octantNum);
				ASSERT(child.valid() && "expected valid child node");

				getNearbyObjects(insertables, entity, child);
			}
		}
		else
		{
			logInfo("getting all the rest...");
			getAll(insertables, node);
		}
	}


	void getAll(std::list<InsertableP>& insertables, NodeP node) const
	{
		ASSERT(node.valid() && "invalid node passed");

		node->getAll(insertables);

		for (unsigned i = 0; i < mTree.children(node); ++i)
		{
			NodeP child = mTree.child(node, i);
			ASSERT(child.valid() && "expected valid child node");

			getAll(insertables, child);
		}
	}

	void getIfVisible(std::list<InsertableP>& insertables,
			const Frustum& frustum, NodeP node) const
	{
		ASSERT(node.valid() && "invalid node passed");

		// try to cull by sphere
		Frustum::Collision collision = frustum.contains(node->getSphere());
		if (collision == Frustum::OUTSIDE) return;

		// try to cull by aabb
		collision = frustum.contains(node->getAabb());
		if (collision == Frustum::OUTSIDE) return;


		if (collision == Frustum::INSIDE)
		{
			node->getAll(insertables);
		}
		else // collision == Frustum::INTERSECT
		{
			node->getIfVisible(insertables, frustum);
		}

		if (mTree.children(node) > 0)
		{
			if (collision == Frustum::INSIDE)
			{
				for (unsigned i = 0; i < mTree.children(node); ++i)
				{
					NodeP child = mTree.child(node, i);
					ASSERT(child.valid() && "expected valid child node");

					getAll(insertables, child);
				}
			}
			else // collision == Frustum::INTERSECT
			{
				for (unsigned i = 0; i < mTree.children(node); ++i)
				{
					NodeP child = mTree.child(node, i);
					ASSERT(child.valid() && "expected valid child node");

					getIfVisible(insertables, frustum, child);
				}
			}
		}
	}


	mutable stlplus::ntree<Node> mTree;


public:

	void print(NodeP node)
	{
		logInfo("-----");
		logInfo << "depth to node: " << mTree.depth(node) << std::endl;
		logInfo << "size of node: " << mTree.size(node) << std::endl;
	}

	static Ptr alloc(const Node& rootNode)
	{
		return Ptr(new Octree(rootNode));
	}

	explicit Octree(const Node& rootNode)
	{
		mTree.insert(rootNode);
	}


	NodeP insert(InsertableP entity)
	{
		return insert(entity, mTree.root());
	}

	void remove(InsertableP entity, NodeP node)
	{
		ASSERT(entity && "null entity passed");
		ASSERT(node.valid() && "invalid node passed");

		typename std::list<InsertableP>::iterator it;
		it = std::find(node->objects.begin(), node->objects.end(), entity);

		if (it != node->objects.end())
		{
			node->objects.erase(it);
		}
	}


	NodeP reinsert(InsertableP entity, NodeP node)
	{
		remove(entity, node);
		return insert(entity);
	}


	void draw(Scalar alpha) const
	{
		std::list<InsertableP> objects;
		getAll(objects);

		typename std::list<InsertableP>::const_iterator it;
		for (it = objects.begin(); it != objects.end(); ++it)
		{
			(*it)->draw(alpha);
		}
	}

	void drawIfVisible(Scalar alpha, const Frustum& frustum) const
	{
		std::list<InsertableP> objects;
		getIfVisible(objects, frustum);
		//getNearbyObjects(objects, *savedObj);

		typename std::list<InsertableP>::const_iterator it;
		for (it = objects.begin(); it != objects.end(); ++it)
		{
			(*it)->draw(alpha);
		}
	}


	void getAll(std::list<InsertableP>& insertables) const
	{
		getAll(insertables, mTree.root());
	}

	void getIfVisible(std::list<InsertableP>& insertables,
			const Frustum& frustum) const
	{
		getIfVisible(insertables, frustum, mTree.root());
	}

	mutable const OctreeInsertable* savedObj;


	void getNearbyObjects(std::list<InsertableP>& insertables,
			const OctreeInsertable& entity) const
	{
		logInfo("--- GETTING NEARBY");
		getNearbyObjects(insertables, entity, mTree.root());
		logInfo("---");
		savedObj = &entity;
	}
};


} // namespace Mf

#endif // _MOOF_OCTREE_HH_