#pragma once
#include "spatialpartitioningtree.h"

#include <hash_map>

using namespace stdext;

class DynOctTree;
class DynOctTreeNode;

class DynOctTree : public SpatialPartitioningTree
{
	float m_CellSize; //length of a cell edge
	float m_Epsilon; //tollerance for loose tree

	//maximum and minimum index of last level cells
	//int m_MinX, m_MinY, m_MinZ; 
	//int m_MaxX, m_MaxY, m_MaxZ; 
	//int m_Levels;

	//stdext::hash_map<LONGLONG, DynOctTreeNode*> m_NodeIndex;
	LList<hash_map<LONGLONG, DynOctTreeNode*>> m_NodeIndex;

protected:
	friend DynOctTreeNode;

	static LONGLONG BuildNodeKey(const int cx, const int cy, const int cz)
	{
		return cx & 0x1ffff | ((__int64)(cy & 0x1ffff) << 21) | ((__int64)(cz & 0x1ffff) << 42);
	}

	AABB CalcCellBound(const int cx, const int cy, const int cz, const int level)
	{
		DXVector3 e = DXVector3(m_Epsilon, m_Epsilon, m_Epsilon);
		return AABB((DXVector3(cx, cy, cz) - e) * m_CellSize * (1 << level), (DXVector3(cx + 1, cy + 1, cz + 1) + e) * m_CellSize * (1 << level));
	}

	void AddLevel(void);

	void FindSuitableCell(SceneObject* const obj, int& cx, int& cy, int& cz, int& l);

	void ReleaseNode(DynOctTreeNode* const pNode);

public:
	DynOctTree(const float CellSize, const float Epsilon);
	~DynOctTree(void);

	float GetCellSize(void) const { return m_CellSize; }
	float GetEpsilon(void) const { return m_Epsilon; }

	DynOctTreeNode* AcquireCellNode(const int cx, const int cy, const int cz, const int l);

	virtual void AddObject(SceneObject* const obj);
	virtual void ObjectMoved(SceneObject* const obj);
	virtual void RemoveObject(SceneObject* const obj);
};

class DynOctTreeNode : public SpatialPartitioningTreeNode
{
protected:
	friend DynOctTree;

	DynOctTree* pTree;
	//indices of cell
	int CellX;
	int CellY;
	int CellZ; 
	int Level;
	//unique key of cell: signed 21 bit for CellX/CellY/CellZ -> 1 mega cells ^ 3
	LONGLONG Key;
	DynOctTreeNode* pFather;
	
	AABB MaxBound;

public:
	DynOctTreeNode(DynOctTree* const tree, DynOctTreeNode* const father, const int x, const int y, const int z, const int level) : SpatialPartitioningTreeNode(8)
	{
		pTree = tree;
		pFather = father;
		CellX = x;
		CellY = y;
		CellZ = z;
		Level = level;
		Key = DynOctTree::BuildNodeKey(x, y, z);
		
		m_Bound = pTree->CalcCellBound(x, y, z, level);
		m_FastBound.Center = m_Bound.GetCenter();
		m_FastBound.Radius = m_Bound.GetE().Length();

		//insert 8 emtpy childs
		for (int i = 0; i < 8; i++)
			m_Childs.Push(NULL);
	}

	int GetChildCount(void) const
	{
		int n = 0;
		for (int i = 0; i < 8; i++)
		{
			if (m_Childs[i])
				n++;
		}
		return n;
	}

	/*void RemoveChild(DynOctTreeNode* const child)
	{
		int sx = child->CellX - (child->CellX / 2 * 2);
		int sy = child->CellY - (child->CellY / 2 * 2);
		int sz = child->CellZ - (child->CellZ / 2 * 2);
		m_Childs.SetN(NULL, sx + sy * 2 + sz * 4);

		int cc = GetChildCount();
		if (m_Objects.GetElementCount() == 0 && (cc == 0 || cc == 1 && this == pTree->m_pRoot))
		{
			if (pFather)
				pFather->RemoveChild(this);
			pTree->ReleaseNode(this);
			delete this;
		}
	}*/
};

