#pragma once
#include "../../stdafx.h"

namespace glLib {

namespace Ext { namespace Alg {

template <typename type_value, typename type_float> class glLibInternal_node {
	private:
		glLibInternal_node* _children[8];
		map<unsigned long,type_value*> _values_index;
		map<string,type_value*> _values_key;

		unsigned short _max_depth, _depth;
		type_float _bounds[6];
		type_float _bifurcation[3];

		char _values_type;
	public:
		glLibInternal_node(
			type_float new_bound_x_neg, type_float new_bound_x_pos,
			type_float new_bound_y_neg, type_float new_bound_y_pos,
			type_float new_bound_z_neg, type_float new_bound_z_pos,
			unsigned short max_depth, unsigned short depth)
		{
			_depth = depth;
			_max_depth = max_depth;

			_bounds[0] = new_bound_x_neg;
			_bounds[1] = new_bound_x_pos;
			_bounds[2] = new_bound_y_neg;
			_bounds[3] = new_bound_y_pos;
			_bounds[4] = new_bound_z_neg;
			_bounds[5] = new_bound_z_pos;
			_bifurcation[0] = (_bounds[1]+_bounds[0]) / 2.0;
			_bifurcation[1] = (_bounds[3]+_bounds[2]) / 2.0;
			_bifurcation[2] = (_bounds[5]+_bounds[4]) / 2.0;

			_values_type = -1;
			if (_depth!=_max_depth) {
				type_float xb=_bounds[0], xt=_bounds[1];
				type_float yb=_bounds[2], yt=_bounds[3];
				type_float zb=_bounds[4], zt=_bounds[5];
				type_float xm=_bifurcation[0], ym=_bifurcation[1], zm=_bifurcation[2];
				_children[0] = new glLibInternal_node(xb,xm,yb,ym,zb,zm, _max_depth,_depth+1);
				_children[1] = new glLibInternal_node(xb,xm,yb,ym,zm,zt, _max_depth,_depth+1);
				_children[2] = new glLibInternal_node(xb,xm,ym,yt,zb,zm, _max_depth,_depth+1);
				_children[3] = new glLibInternal_node(xb,xm,ym,yt,zm,zt, _max_depth,_depth+1);
				_children[4] = new glLibInternal_node(xm,xt,yb,ym,zb,zm, _max_depth,_depth+1);
				_children[5] = new glLibInternal_node(xm,xt,yb,ym,zm,zt, _max_depth,_depth+1);
				_children[6] = new glLibInternal_node(xm,xt,ym,yt,zb,zm, _max_depth,_depth+1);
				_children[7] = new glLibInternal_node(xm,xt,ym,yt,zm,zt, _max_depth,_depth+1);
			}
		}
		~glLibInternal_node(void) {
			if (_depth!=_max_depth) {
				for (char i=0;i<8;++i) {
					delete (_children[i]);
				}
			}
		}

		void add_value(type_float x, type_float y, type_float z, const string* key, const type_value* value) {
			#ifdef GLLIB_ERROR_MODE_REPORT_ERRORS
			if (_values_type==2) throw GLLIB_ERROR_TYPE_ERROR("Cannot use both keys and indices to access tree!");
			#endif
			_values_type = 1;

			if (_depth==_max_depth) {
				//for (char i=0;i<_depth;++i) { printf("  "); }
				//printf("(%f,%f,%f added to tree!)\n",x,y,z);
				_values_key[*key] = value;
			}
			else {
				glLibInternal_recurse_add(x,y,z,key,value);
			}
		}
		void add_value(type_float x, type_float y, type_float z, unsigned long index, const type_value* value) {
			#ifdef GLLIB_ERROR_MODE_REPORT_ERRORS
			if (_values_type==1) throw GLLIB_ERROR_TYPE_ERROR("Cannot use both keys and indices to access tree!");
			#endif
			_values_type = 2;

			if (_depth==_max_depth) _values_key[index] = value;
			else glLibInternal_recurse_add(x,y,z,index,value);
		}
		type_value* get_value(type_float x, type_float y, type_float z, const string* key) const {
			#ifdef GLLIB_ERROR_MODE_REPORT_ERRORS
			if (_values_type==2) throw GLLIB_ERROR_TYPE_ERROR("Cannot use both keys and indices to access tree!");
			#endif
			if (_depth==_max_depth) return _values_key[*key];
			else return get_value(x,y,z,key);
		}
		type_value* get_value(type_float x, type_float y, type_float z, unsigned long index) const {
			#ifdef GLLIB_ERROR_MODE_REPORT_ERRORS
			if (_values_type==1) throw GLLIB_ERROR_TYPE_ERROR("Cannot use both keys and indices to access tree!");
			#endif
			if (_depth==_max_depth) return _values_index[index];
			else return get_value(x,y,z,index);
		}
		template <typename type_map> const type_map* get_values(type_float x, type_float y, type_float z) const {
			if (_values_type==1) return _values_key;
			else return _values_index;
		}

		template <typename type_map> bool trace_ray(const type_float origin[3], const type_float direction[3], const type_map* out) {
			type_float minimum[3] = {_bounds[0],_bounds[2],_bounds[4]};
			type_float maximum[3] = {_bounds[1],_bounds[3],_bounds[5]};
			type_float distance;
			if (::glLib::Math::Intersect::ray_AABB(origin,direction,minimum,maximum,&distance)>=0.0) {
				if (_depth==_max_depth) {
					if (!_values_key.empty()) {
						out->insert(_values_key.begin(),_values_key.end());
						return true;
					}
					if (!_values_index.empty()) {
						out->insert(_values_index.begin(),_values_index.end());
						return true;
					}
				}
				else {
					for (char i=0;i<8;++i) {
						if (_children[i]->trace_ray(origin,direction,out)) {
							return true;
						}
					}
				}
			}
			return false;
		}

		bool contains_data(void) {
			if (_depth==_max_depth) {
				if (!_values_key.empty()) return true;
				if (!_values_index.empty()) return true;
			}
			else {
				for (char i=0;i<8;++i) {
					if (_children[i]->contains_data()) return true;
				}
			}
			return false;
		}
	private:
		template <typename type_accessor> void glLibInternal_recurse_add(type_float x, type_float y, type_float z, const type_accessor access, const type_value* value) {
			//TODO: improve
			/*char loc = 0;
			loc |= 4 * (char)(x<_bifurcation[0]);
			loc |= 2 * (char)(y<_bifurcation[1]);
			loc |=     (char)(z<_bifurcation[2]);*/
			//for (char i=0;i<_depth;++i) { printf("  "); }
			//printf("(Recursing to index %d!)\n",loc);
			//_children[loc]->add_value(x,y,z,access,value);
			if (x<_bifurcation[0]) { //in _children 0-3
				if (y<_bifurcation[1]) { //in _children 0-1
					if (z<_bifurcation[2]) _children[0]->add_value(x,y,z,access,value);
					else                   _children[1]->add_value(x,y,z,access,value);
				}
				else { //in _children 2-3
					if (z<_bifurcation[2]) _children[2]->add_value(x,y,z,access,value);
					else                   _children[3]->add_value(x,y,z,access,value);
				}
			}
			else { //in _children 4-7
				if (y<_bifurcation[1]) { //in _children 4-5
					if (z<_bifurcation[2]) _children[4]->add_value(x,y,z,access,value);
					else                   _children[5]->add_value(x,y,z,access,value);
				}
				else { //in _children 6-7
					if (z<_bifurcation[2]) _children[6]->add_value(x,y,z,access,value);
					else                   _children[7]->add_value(x,y,z,access,value);
				}
			}
		}
};

template <typename type_value, typename type_float> class glLibExtAlgOctree {
	public:
		unsigned short max_depth;
	private:
		type_float bound_x_neg, bound_x_pos;
		type_float bound_y_neg, bound_y_pos;
		type_float bound_z_neg, bound_z_pos;
		glLibInternal_node<type_value,type_float>* _tree;

	public:
		glLibExtAlgOctree(
			type_float new_bound_x_neg, type_float new_bound_x_pos,
			type_float new_bound_y_neg, type_float new_bound_y_pos,
			type_float new_bound_z_neg, type_float new_bound_z_pos,
			unsigned short new_max_depth)
		{
			bound_x_neg = new_bound_x_neg; bound_x_pos = new_bound_x_pos;
			bound_y_neg = new_bound_y_neg; bound_y_pos = new_bound_y_pos;
			bound_z_neg = new_bound_z_neg; bound_z_pos = new_bound_z_pos;
			max_depth = new_max_depth;
			glLibInternal_init();
		}
		~glLibExtAlgOctree(void) {
			delete _tree;
		}
	private:
		glLibExtAlgOctree(const glLibExtAlgOctree& arg) {}
		glLibExtAlgOctree& operator=(const glLibExtAlgOctree &arg) {}

		void glLibInternal_init(void) {
			_tree = new glLibInternal_node<type_value,type_float>(
				bound_x_neg,bound_x_pos,
				bound_y_neg,bound_y_pos,
				bound_z_neg,bound_z_pos,
				max_depth,0);
		}
		#ifdef GLLIB_ERROR_MODE_REPORT_ERRORS
		void glLibInternal_check_bounds(type_float x, type_float y, type_float z) {
			if ((x<bound_x_neg)||(x>bound_x_pos)||
				(y<bound_y_neg)||(y>bound_y_pos)||
				(z<bound_z_neg)||(z>bound_z_pos)) {
				throw GLLIB_ERROR_TYPE_ERROR("The specified coordinates were outside the range of the octree!");
			}
		}
		#endif

	public:
		void add_value(type_float x, type_float y, type_float z, const string key, const type_value* value) {
			#ifdef GLLIB_ERROR_MODE_REPORT_ERRORS
			glLibInternal_check_bounds(x,y,z);
			#endif
			_tree->add_value(x,y,z,key,value);
		}
		void add_value(type_float x, type_float y, type_float z, unsigned long index, const type_value* value) {
			#ifdef GLLIB_ERROR_MODE_REPORT_ERRORS
			glLibInternal_check_bounds(x,y,z);
			#endif
			_tree->add_value(x,y,z,index,value);
		}
		void add_value(type_float position[3], const string key, const type_value* value) {
			#ifdef GLLIB_ERROR_MODE_REPORT_ERRORS
			glLibInternal_check_bounds(position[0],position[1],position[2]);
			#endif
			_tree->add_value(position[0],position[1],position[2],key,value);
		}
		void add_value(type_float position[3], unsigned long index, const type_value* value) {
			#ifdef GLLIB_ERROR_MODE_REPORT_ERRORS
			glLibInternal_check_bounds(position[0],position[1],position[2]);
			#endif
			_tree->add_value(position[0],position[1],position[2],index,value);
		}
		//TODO: remove()
		void clear(void) {
			delete _tree;
			glLibInternal_init();
		}
		const type_value get_value(type_float x, type_float y, type_float z, const string key) {
			#ifdef GLLIB_ERROR_MODE_REPORT_ERRORS
			glLibInternal_check_bounds(x,y,z);
			#endif
			return *(_tree->get_value(x,y,z, &key));
		}
		const type_value get_value(type_float x, type_float y, type_float z, unsigned long index) {
			#ifdef GLLIB_ERROR_MODE_REPORT_ERRORS
			glLibInternal_check_bounds(x,y,z);
			#endif
			return *(_tree->get_value(x,y,z, index));
		}
		template <typename type_map> const type_map* get_values(type_float x, type_float y, type_float z) {
			#ifdef GLLIB_ERROR_MODE_REPORT_ERRORS
			glLibInternal_check_bounds(x,y,z);
			#endif
			return _tree->get_values(x,y,z);
		}
		unsigned long get_numof_elements(type_float x, type_float y, type_float z) {
			#ifdef GLLIB_ERROR_MODE_REPORT_ERRORS
			glLibInternal_check_bounds(x,y,z);
			#endif
			return _tree->get_numof_elements(x,y,z);
		}

		template <typename type_map> bool trace_ray(type_float origin[3], type_float direction[3], type_map* out) {
			return _tree->trace_ray(origin,direction,out);
		}

		inline bool contains_data(void) {
			return _tree->contains_data();
		}
};

};};};