/*
								+----------------------------------+
								|                                  |
								|     ***  Vertex hashing  ***     |
								|                                  |
								|   Copyright © -tHE SWINe- 2013   |
								|                                  |
								|           VertexHash.h           |
								|                                  |
								+----------------------------------+
*/

#pragma once
#ifndef __POLYMESH_VERTEX_HASHING_INCLUDED
#define __POLYMESH_VERTEX_HASHING_INCLUDED

/**
 *	@file lml/VertexHash.h
 *	@date 2007
 *	@author -tHE SWINe-
 *	@brief vertex hashing for CPolyMesh
 */

#include "PolyMesh.h"
#include <map>

/**
 *	@brief the vertex hash wrapper class
 */
class CVertexHash {
public:
	typedef CPolyMesh::_TyPolygon _TyPolygon; /**< @brief polygon type */
	typedef CPolyMesh::_TyVertex _TyVertex; /**< @brief vertex type */

	/**
	 *	@brief a simple helper that wraps vertex list of a mesh with a subset of interface of std::vector
	 */
	class CMeshVertexListHelper {
	public:
		typedef CPolyMesh::_TyVertex value_type; /**< @brief type of the element */

	protected:
		CPolyMesh &m_r_mesh; /**< @brief reference to the mesh */

	public:
		/**
		 *	@brief default constructor
		 *	@param[in] r_mesh is reference to the mesh
		 */
		CMeshVertexListHelper(CPolyMesh &r_mesh)
			:m_r_mesh(r_mesh)
		{}

		/**
		 *	@brief gets number of vertices
		 *	@return Returns number of vertices.
		 */
		size_t size() const
		{
			return m_r_mesh.n_Vertex_Num();
		}

		/**
		 *	@brief gets a vertex
		 *	@param[in] n_index is zero-based vertex index
		 *	@return Returns reference the selected vertex.
		 */
		CPolyMesh::_TyVertex &operator [](size_t n_index)
		{
			return m_r_mesh.r_Vertex(n_index);
		}

		/**
		 *	@brief gets a vertex
		 *	@param[in] n_index is zero-based vertex index
		 *	@return Returns const reference the selected vertex.
		 */
		const CPolyMesh::_TyVertex &operator [](size_t n_index) const
		{
			return m_r_mesh.r_Vertex(n_index);
		}
	};

	/**
	 *	@brief vertex hash-table; associates position to a list of nearby vertices
	 */
	template <class CVertex = _TyVertex>
	class CUniformGrid { // todo - this design is dumb, there are bad cases when memory blows up exponentially and the maximum epsilon is plain stupid; redo this to the classical insert to one bin, look up many bins approach, should be seamless using the same interface; benchmark; allow non-square cells? use indices instead of pointers (and use combined iterators to get poisitions easily)
	protected:
		float m_f_cell_side; /**< @brief length of one cell side */
		float m_f_inv_cell_side; /**< @brief inverse length of one cell side */
		Vector3<size_t> m_v_table_size; /**< @brief number of cells along each respective axis */
#ifdef __VERTEX_HASH_DENSE_TABLE
		std::vector<CVertex*> *m_p_vertex_hash; /**< @brief list of lists of vertices (one vector per cell) */
#else // __VERTEX_HASH_DENSE_TABLE
		std::map<size_t, std::vector<CVertex*> > m_vertex_hash; /**< @brief a "sparse" list of lists of vertices (one vector per cell) */
		std::vector<CVertex*> &m_empty; /**< @brief empty list of vertices shared by all empty cells */

		static std::vector<CVertex*> &r_GetEmpty()
		{
			static std::vector<CVertex*> empty;
			return empty;
		}
#endif // __VERTEX_HASH_DENSE_TABLE

		/**
		 *	@brief a simple predicate filter for for-each loops
		 *
		 *	@tparam CPredicate is predicate type
		 *	@tparam CFunctor is functor type
		 */
		template <class CPredicate, class CFunctor>
		class CForEachVertexAdaptor {
		protected:
			CPredicate m_pred; /**< @brief predicate instance */
			CFunctor m_functor; /**< @brief function object */

		public:
			/**
			 *	@brief default constructor
			 *
			 *	@param[in] pred is predicate instance
			 *	@param[in] functor is function object
			 */
			inline CForEachVertexAdaptor(CPredicate pred, CFunctor functor)
				:m_pred(pred), m_functor(functor)
			{}

			/**
			 *	@brief calls functor on a vertex, but only if the predicate passed
			 *	@param[in] p_vertex is a pointer to vertex in the hash table
			 */
			inline void operator ()(CVertex *p_vertex)
			{
				if(m_pred(p_vertex))
					m_functor(p_vertex);
			}

			/**
			 *	@brief gets the value of the functor
			 *	@return Returns the value of the functor after passing all the vertices to it.
			 */
			inline CFunctor GetFunctor() const
			{
				return m_functor;
			}
		};

	public:
		/**
		 *	@brief constructor
		 *
		 *	@param[in] r_mesh is the mesh to be hashed
		 *	@param[in] n_vertices_per_node is desired number of vertices per node
		 *		(to determine uniform grid size)
		 *	@param[in] f_max_epsilon is maximum epsilon for vertex searches
		 *		on the grid (affects minimal cell size)
		 *
		 *	@note Use b_Status() to determine wheter constructor was successful.
		 */
		CUniformGrid(CPolyMesh &r_mesh, size_t n_vertices_per_node, float f_max_epsilon);

		/**
		 *	@brief constructor
		 *
		 *	@param[in] r_vertex_list is list of vertices to be hashed (note that the
		 *		addresses of the vertices need to remain constant)
		 *	@param[in] n_vertices_per_node is desired number of vertices per node
		 *		(to determine uniform grid size)
		 *	@param[in] f_max_epsilon is maximum epsilon for vertex searches
		 *		on the grid (affects minimal cell size)
		 *
		 *	@note Use b_Status() to determine wheter constructor was successful.
		 */
		CUniformGrid(std::vector<CVertex> &r_vertex_list, size_t n_vertices_per_node, float f_max_epsilon);

#ifdef __VERTEX_HASH_DENSE_TABLE
		/**
		 *	@brief destructor
		 *	@note This is only needed if __VERTEX_HASH_DENSE_TABLE is defined.
		 */
		~CUniformGrid();
#endif // __VERTEX_HASH_DENSE_TABLE

		/**
		 *	@brief gets status of the vertex map object
		 *	@return Returns true in case constructor succeeded and vertex hash
		 *		is ready to be used, otherwise returns false.
		 */
		inline bool b_Status() const
		{
#ifdef __VERTEX_HASH_DENSE_TABLE
			return m_p_vertex_hash != 0;
#else // __VERTEX_HASH_DENSE_TABLE
			return m_v_table_size.x != 0; // cleared on ctor failure
#endif // __VERTEX_HASH_DENSE_TABLE
		}

		/**
		 *	@brief gets uniform grid cell side
		 *	@return Returns uniform grid cell side.
		 */
		inline float f_Cell_Side() const
		{
			return m_f_cell_side;
		}

		/**
		 *	@brief gets maximum epsilon for uniform grid lookups
		 *	@return Returns maximum epsilon for uniform grid lookups.
		 */
		inline float f_Max_Epsilon() const
		{
			return m_f_cell_side * .5f;
		}

		/**
		 *	@brief gets grid resolution along the x axis
		 *	@return Returns grid resolution along the x axis.
		 */
		inline size_t n_Cell_X_Num() const
		{
			return m_v_table_size.x;
		}

		/**
		 *	@brief gets grid resolution along the y axis
		 *	@return Returns grid resolution along the y axis.
		 */
		inline size_t n_Cell_Y_Num() const
		{
			return m_v_table_size.y;
		}

		/**
		 *	@brief gets grid resolution along the z axis
		 *	@return Returns grid resolution along the z axis.
		 */
		inline size_t n_Cell_Z_Num() const
		{
			return m_v_table_size.z;
		}

		/**
		 *	@brief gets average cell occupation
		 *	@return Returns average cell occupation.
		 */
		float f_Avg_CellOccupation() const;

		/**
		 *	@brief calculates a discrete position in the uniform grid
		 *	@param[in] v_pos is the reference point
		 *	@return Returns position of a cell in the uniform grid the given point falls in
		 */
		Vector3<size_t> v_UniformGrid_Pos(Vector3f v_pos) const;

		/**
		 *	@brief calculates hash value for a point
		 *	@param[in] v_pos is the reference point
		 *	@return Returns hash value for the given point
		 */
		inline size_t n_Hash_Value(Vector3f v_pos) const
		{
			Vector3<size_t> v_index = v_UniformGrid_Pos(v_pos); 
			return v_index.x + m_v_table_size.x * (v_index.y + m_v_table_size.y * v_index.z);
		}

		inline CVertex *p_Nearest(Vector3f v_pos, float f_max_dist) const
		{
			_ASSERTE(f_max_dist <= m_f_cell_side); // if greater, will not work // todo - support greater lookups gracefully
			const std::vector<CVertex*> &r_cell = r_Hash(v_pos);
			if(r_cell.empty())
				return 0;
			CVertex *p_nearest = r_cell.front();
			float f_dist2 = (v_pos - (Vector3f)*p_nearest).f_Length2();
			for(size_t i = 1, n = r_cell.size(); i < n; ++ i) {
				CVertex *p_vert = r_cell[i];
				float f_cur_dist2 = (v_pos - (Vector3f)*p_vert).f_Length2();
				if(f_dist2 > f_cur_dist2) {
					f_dist2 = f_cur_dist2;
					p_nearest = p_vert;
				}
			}
			return (f_dist2 <= f_max_dist)? p_nearest : 0;
		}

protected: // this needs to be hidden in order to allow different implementations
		/**
		 *	@brief gets a list of vertices in cell corresponding to a given position
		 *	@param[in] v_pos is the reference point
		 *	@return Returns a list of vertices in cell corresponding the given point falls in.
		 */
		inline const std::vector<CVertex*> &r_Hash(Vector3f v_pos) const
		{
#ifdef __VERTEX_HASH_DENSE_TABLE
			return m_p_vertex_hash[n_Hash_Value(v_pos)];
#else // __VERTEX_HASH_DENSE_TABLE
			std::map<size_t, std::vector<CVertex*> >::const_iterator p_map_it =
				m_vertex_hash.find(n_Hash_Value(v_pos));
			if(p_map_it != m_vertex_hash.end())
				return (*p_map_it).second;
			return m_empty; // no vertices in this bucket
#endif // __VERTEX_HASH_DENSE_TABLE
		}

public:
		/**
		 *	@brief close position predicate for ForEachVertex template function
		 */
		class CVertexPosPredicate {
		protected:
			float m_f_epsilon_ex2; /**< @brief close position threshold */
			const Vector3f m_v_ref; /**< @brief the reference position */

		public:
			/**
			 *	@brief default constructor
			 *
			 *	@param[in] r_ref_vertex is reference vertex
			 *	@param[in] f_epsilon_ex is maximal allowed distance
			 *		(note the grid cell size is a limit to this distance)
			 */
			CVertexPosPredicate(const CVertex &r_ref_vertex, float f_epsilon_ex = f_epsilon)
				:m_v_ref(r_ref_vertex), m_f_epsilon_ex2(f_epsilon_ex * f_epsilon_ex)
			{}

			/**
			 *	@brief decides whether a vertex is a close vertex
			 *	@param[in] p_vertex is pointer to a vertex from the vertex hash
			 *	@return Returns true if the given vertex is close enough
			 *		to the reference, otherwise returns false.
			 */
			inline bool operator ()(const CVertex *p_vertex) const
			{
				return (m_v_ref - (Vector3f)*p_vertex).f_Length2() <= m_f_epsilon_ex2;
			}
		};

		/**
		 *	@brief close vertex predicate for ForEachVertex template function
		 */
		class CVertexGenPredicate {
		protected:
			bool m_b_compare_normal;
			bool m_b_compare_color;
			size_t m_n_compare_texcoord_num;
			float m_f_epsilon_ex2;
			float m_f_normal_epsilon2;
			float m_f_color_epsilon2;
			float m_f_texcoord_epsilon2;
			const CVertex &m_r_ref_vertex;

		public:
			/**
			 *	@brief default constructor
			 *
			 *	@param[in] r_ref_vertex is a reference vertex
			 *	@param[in] b_compare_normal is normal comparison flag
			 *	@param[in] b_compare_color is color comparison flag
			 *	@param[in] n_compare_texcoord_num is a nomber of texture coordinates to compate
			 *	@param[in] f_epsilon_ex is maximal allowed distance (note the grid cell overlap of
			 *		  vertex hash is limit to this distance)
			 *	@param[in] f_normal_epsilon is maximal allowed normal distance
			 *	@param[in] f_color_epsilon is maximal allowed color distance (euclidean)
			 *	@param[in] f_texcoord_epsilon is maximal allowed texcoord distance
			 */
			CVertexGenPredicate(const CVertex &r_ref_vertex,
				bool b_compare_normal, bool b_compare_color, size_t n_compare_texcoord_num,
				float f_epsilon_ex, float f_normal_epsilon, float f_color_epsilon,
				float f_texcoord_epsilon)
				:m_r_ref_vertex(r_ref_vertex), m_b_compare_normal(b_compare_normal),
				m_b_compare_color(b_compare_color), m_n_compare_texcoord_num(n_compare_texcoord_num),
				m_f_epsilon_ex2(f_epsilon_ex * f_epsilon_ex),
				m_f_normal_epsilon2(f_normal_epsilon * f_normal_epsilon),
				m_f_color_epsilon2(f_color_epsilon * f_color_epsilon),
				m_f_texcoord_epsilon2(f_texcoord_epsilon * f_texcoord_epsilon)
			{
				_ASSERTE(m_n_compare_texcoord_num <= CVertex::n_Texcoord_Num);
			}

			/**
			 *	@brief decides whether a vertex is a close vertex
			 *	@param[in] p_vertex is pointer to a vertex from the vertex hash
			 *	@return Returns true if the given vertex is close enough
			 *		to the reference, otherwise returns false.
			 */
			inline bool operator ()(const CVertex *p_vertex) const
			{
				if((m_r_ref_vertex.v_position -
				   p_vertex->v_position).f_Length2() > m_f_epsilon_ex2)
					return false;
				if(m_b_compare_normal && (m_r_ref_vertex.v_normal -
				   p_vertex->v_normal).f_Length2() > m_f_normal_epsilon2)
					return false;
				if(m_b_compare_color && (m_r_ref_vertex.v_color -
				   p_vertex->v_color).f_Length2() > m_f_color_epsilon2)
					return false;
				const Vector4f *p_ref_texcoord = m_r_ref_vertex.p_texture_coord;
				const Vector4f *p_texcoord = p_vertex->p_texture_coord;
				for(size_t i = 0; i < m_n_compare_texcoord_num; ++ i) {
					if((p_ref_texcoord[i] - p_texcoord[i]).f_Length2() > m_f_texcoord_epsilon2)
						return false;
				}
				return true;
			}
		};

		/**
		 *	@brief for-each loop that iterates vertices near a given position
		 *
		 *	@tparam CFunctor is functor type
		 *
		 *	@param[in] v_pos is reference position
		 *	@param[in] functor is instance of the functor
		 *
		 *	@return Returns value of the function object after passing
		 *		all the (relevant) vertices to it.
		 */
		template <class CFunctor>
		CFunctor ForEachVertexNear(Vector3f v_pos, CFunctor functor)
		{
			const std::vector<CVertex*> &r_vertex_list = r_Hash(v_pos);
			return std::for_each(r_vertex_list.begin(), r_vertex_list.end(), functor);
		}

		/**
		 *	@brief for-each loop that iterates vertices near a given position,
		 *		conditioned by a vertex predicate
		 *
		 *	@tparam CPredicate is vertex predicate type (to enable filtering of the results)
		 *	@tparam CFunctor is functor type
		 *
		 *	@param[in] v_pos is reference position
		 *	@param[in] pred is instance of the predicate
		 *	@param[in] functor is instance of the functor
		 *
		 *	@return Returns value of the function object after passing
		 *		all the (relevant) vertices to it.
		 */
		template <class CPredicate, class CFunctor>
		CFunctor ForEachVertexNear(Vector3f v_pos, CPredicate pred, CFunctor functor)
		{
			const std::vector<CVertex*> &r_vertex_list = r_Hash(v_pos);
			return std::for_each(r_vertex_list.begin(), r_vertex_list.end(),
				CForEachVertexAdaptor<CPredicate, CFunctor>(pred, functor)).GetFunctor();
		}

		/**
		 *	@brief for-each loop that iterates vertices near a given position
		 *
		 *	@tparam CFunctor is functor type
		 *
		 *	@param[in] v_pos is reference position
		 *	@param[in] functor is instance of the functor
		 *
		 *	@return Returns value of the function object after passing
		 *		all the (relevant) vertices to it.
		 */
		template <class CFunctor>
		CFunctor ForEachVertexNear(Vector3f v_pos, CFunctor functor) const
		{
			const std::vector<CVertex*> &r_vertex_list = r_Hash(v_pos);
			return std::for_each(r_vertex_list.begin(), r_vertex_list.end(), functor);
		}

		/**
		 *	@brief for-each loop that iterates vertices near a given position,
		 *		conditioned by a vertex predicate
		 *
		 *	@tparam CPredicate is vertex predicate type (to enable filtering of the results)
		 *	@tparam CFunctor is functor type
		 *
		 *	@param[in] v_pos is reference position
		 *	@param[in] pred is instance of the predicate
		 *	@param[in] functor is instance of the functor
		 *
		 *	@return Returns value of the function object after passing
		 *		all the (relevant) vertices to it.
		 */
		template <class CPredicate, class CFunctor>
		CFunctor ForEachVertexNear(Vector3f v_pos, CPredicate pred, CFunctor functor) const
		{
			const std::vector<CVertex*> &r_vertex_list = r_Hash(v_pos);
			return std::for_each(r_vertex_list.begin(), r_vertex_list.end(),
				CForEachVertexAdaptor<CPredicate, CFunctor>(pred, functor)).GetFunctor();
		}

	protected:
		template <class CVertexList>
		void Fill(CVertexList &r_list, Vector3f v_min, Vector3f v_max,
			size_t n_vertices_per_node, float f_max_epsilon)
		{
			size_t n_node_num = max(size_t(1), (r_list.size() + n_vertices_per_node - 1) / n_vertices_per_node);
			Vector3f v_cell_size = v_max - v_min;
			m_f_cell_side = std::max((float)pow(v_cell_size.x * v_cell_size.y * v_cell_size.z /
				n_node_num, 1.0f / 3), std::max(f_max_epsilon * 2, .01f));
			m_f_inv_cell_side = 1 / m_f_cell_side;
			m_v_table_size.x = max(size_t(1), size_t(v_cell_size.x * m_f_inv_cell_side + .5f));
			m_v_table_size.y = max(size_t(1), size_t(v_cell_size.y * m_f_inv_cell_side + .5f));
			m_v_table_size.z = max(size_t(1), size_t(v_cell_size.z * m_f_inv_cell_side + .5f));
			// calculate grid dimensions

		#ifdef __VERTEX_HASH_DENSE_TABLE
			if(!(m_p_vertex_hash = new(std::nothrow)
			   std::vector<CVertex*>[m_v_table_size.x * m_v_table_size.y * m_v_table_size.z]))
				return;
		#endif // __VERTEX_HASH_DENSE_TABLE
			// create new hash

			try {
				for(size_t i = 0, m = r_list.size(); i < m; ++ i) {
					typename CVertexList::value_type &r_vertex = r_list[i];

					Vector3<size_t> v_index[2] = {
						v_UniformGrid_Pos((Vector3f)r_vertex),
						v_UniformGrid_Pos(((Vector3f)r_vertex) + (m_f_cell_side * .5f))
					};
					// calc indices

					for(int x = 0; x < 2; x ++) {
						for(int y = 0; y < 2; y ++) {
							for(int z = 0; z < 2; z ++) {
								size_t n_cell =
									v_index[x].x + m_v_table_size.x * (v_index[y].y + m_v_table_size.y * v_index[z].z);
								// calc cell index

		#ifdef __VERTEX_HASH_DENSE_TABLE
								if(!stl_ut::Reserve_1More(m_p_vertex_hash[n_cell])) {
									delete[] m_p_vertex_hash;
									m_p_vertex_hash = 0;
									return;
								}
								m_p_vertex_hash[n_cell].push_back((CVertex*)&r_vertex));
		#else // __VERTEX_HASH_DENSE_TABLE
								m_vertex_hash[n_cell].push_back((CVertex*)&r_vertex);
		#endif // __VERTEX_HASH_DENSE_TABLE
								// add reference into a cell

								if(v_index[0].z == v_index[1].z)
									break;
							}
							if(v_index[0].y == v_index[1].y)
								break;
						}
						if(v_index[0].x == v_index[1].x)
							break;
					}
					// add references to a vertex to all cells it hit
				}
			} catch(std::bad_alloc&) {
				m_v_table_size = Vector3<size_t>(0, 0, 0); // mark failure
			}
		}
	};

	/**
	 *	@brief lookup tables of vertices at close positions
	 */
	class CVertexGroupTable {
	public:
		typedef std::vector<std::vector<_TyVertex*> > _TyGroupTable; /**< @brief type of table of vertex groups */

		/**
		 *	@brief a helper implementation of vertex reference table
		 *
		 *	@tparam CInitializer is initializer class that converts from the
		 *		(polygon, polygon index, vertex index, group index) quadruple to CStoreType
		 *	@tparam CStoreType is type of vertex reference information to be stored in the table
		 */
		template <class CInitializer, class CStoreType = typename CInitializer::_TyStoreType>
		class CVertexReferenceTableFactory {
		public:
			typedef CInitializer _TyInitializer; /**< @brief conversion to CStoreType */
			typedef CStoreType _TyStoreType; /**< @brief type of vertex reference information */
			typedef std::vector<std::vector<_TyStoreType> > _TyReferenceTable; /**< @brief vertex reference table type */

		public:
			/**
			 *	@brief builds the vertex reference table (list of references per each vertex group)
			 *
			 *	@param[out] r_vertex_ref_list is reference to the vector where the
			 *		vertex references should be stored (gets overwritten)
			 *	@param[in] r_mesh is a mesh to construct the vertex reference table for
			 *	@param[in] r_merge_table is vertex group table for the same mesh
			 *
			 *	@return Returns true on success, false on failure.
			 *
			 *	@note This runs in linear time in the number of mesh vertices.
			 */
			static bool Build_VertexReference_Table(_TyReferenceTable &r_vertex_ref_list,
				const CPolyMesh &r_mesh, const CVertexGroupTable &r_merge_table)
			{
				if(!r_merge_table.b_Status())
					return false;
				// see if merge CVertexGroupTable is ready

				try {
					if(!r_vertex_ref_list.empty() && r_vertex_ref_list.capacity() < r_merge_table.n_Group_Num())
						r_vertex_ref_list.clear();
					// avoid copying non-empty vectors, but do reuse the allocated storage // dubious

					r_vertex_ref_list.resize(r_merge_table.n_Group_Num());
					// allocate the reference table

					const std::vector<size_t> &r_group_index_table = r_merge_table.r_GroupIndexTable();
					const CPolyMesh::_TyVertexPool &r_vertex_list = r_mesh.r_Vertex_Pool();
					for(size_t i = 0, m = r_mesh.n_Polygon_Num(); i < m; ++ i) {
						const _TyPolygon &r_poly = r_mesh.r_Polygon(i);
						for(size_t j = 0, n = r_poly.n_Vertex_Num(); j < n; ++ j) {
							size_t n_index_n = r_vertex_list.n_IndexOf(r_poly.t_Vertex(j).m_p_ref);
							_ASSERTE(n_index_n != size_t(-1));
							size_t n_group = r_group_index_table[n_index_n];
							// determine vertex group (vertex position id)

							r_vertex_ref_list[n_group].push_back(_TyInitializer(r_poly, i, j, n_group));
							// add the polygon index to the given group
						}
					}
					// create CVertexGroupTable of polygon references
				} catch(std::bad_alloc&) {
					return false;
				}

				return true;
			}
		};

		/**
		 *	@brief conversion of vertex reference to polygon pointer
		 */
		class CVertexRef_to_PolygonPtr {
		public:
			typedef _TyPolygon *_TyStoreType; /**< @brief type of vertex reference information */

		protected:
			_TyPolygon *m_p_poly; /**< @brief value of vertex reference information */

		public:
			/**
			 *	@brief default constructor; initializes the vertex reference information
			 *
			 *	@param[in] r_poly is reference to the polygon that references the referenced vertex
			 *	@param[in] n_polygon is index of the polygon that references the referenced vertex
			 *	@param[in] n_vertex is index of the referenced vertex, within the polygon vertices
			 *	@param[in] n_vertex_group is vertex group the referenced vertex belongs to
			 */
			inline CVertexRef_to_PolygonPtr(const _TyPolygon &r_poly, size_t UNUSED(n_polygon),
				size_t UNUSED(n_vertex), size_t UNUSED(n_vertex_group))
				:m_p_poly(const_cast<_TyPolygon*>(&r_poly))
			{}

			/**
			 *	@brief gets the vertex reference information
			 *	@return Returns value of the vertex reference information.
			 */
			inline operator _TyStoreType()
			{
				return m_p_poly;
			}
		};

		/**
		 *	@brief conversion of vertex reference to pair of polygon index and local vertex index
		 */
		class CVertexRef_to_IndexPair {
		public:
			typedef std::pair<size_t, size_t> _TyStoreType; /**< @brief type of vertex reference information */

		protected:
			std::pair<size_t, size_t> m_index_pair; /**< @brief value of vertex reference information */

		public:
			/**
			 *	@brief default constructor; initializes the vertex reference information
			 *
			 *	@param[in] r_poly is reference to the polygon that references the referenced vertex
			 *	@param[in] n_polygon is index of the polygon that references the referenced vertex
			 *	@param[in] n_vertex is index of the referenced vertex, within the polygon vertices
			 *	@param[in] n_vertex_group is vertex group the referenced vertex belongs to
			 */
			inline CVertexRef_to_IndexPair(const _TyPolygon &UNUSED(r_poly),
				size_t n_polygon, size_t n_vertex, size_t UNUSED(n_vertex_group))
				:m_index_pair(n_polygon, n_vertex)
			{}

			/**
			 *	@brief gets the vertex reference information
			 *	@return Returns value of the vertex reference information.
			 */
			inline operator _TyStoreType() const
			{
				return m_index_pair;
			}
		};

		typedef std::vector<std::vector<_TyPolygon*> > _TySimpleVRefTable; /**< @brief vertex reference table storing simple referencing polygon pointers */
		typedef std::vector<std::vector<std::pair<size_t, size_t> > > _TyIndexedVRefTable; /**< @brief vertex reference table storing polygon index and local vertex index pairs */

	protected:
		_TyGroupTable m_table; /**< @brief table of vertex groups */
		std::vector<size_t> m_vertex_group_id_list; /**< @brief table of vertex affiliations to the groups */
		bool m_b_status; /**< @brief table status flag */

		class CGroupVertices; /**< @brief helper functor that fills vertex groups */
		class CCreateIndexTable; /**< @brief helper functor that fills group id list */

	public:
		/**
		 *	@brief default constructor; fills the tables
		 *
		 *	The table of vertex groups takes group num at high level and vertex num of the
		 *	mesh at low level. The table of vertex affiliations to the groups contains entry
		 *	for each mesh vertex. The space complexity therefore equals
		 *	<tt>O(sizeof(std::vector) * g + (sizeof(void*) + sizeof(size_t)) * v)</tt>, where
		 *	<tt>g</tt> is number of vertex groups and <tt>v</tt> is number of mesh vertices.
		 *
		 *	@param[in] r_mesh is the mesh for which the group table is constructed
		 *	@param[in] r_vertex_hash is up-to-date vertex hash for the same object
		 *	@param[in] b_compare_normal is normal comparison flag
		 *	@param[in] b_compare_color is color comparison flag
		 *	@param[in] n_compare_texcoord_num is number of texture coordinates to be compared
		 *	@param[in] f_epsilon_ex is maximal allowed distance (note the grid cell overlap of
		 *		vertex hash is limit to this distance)
		 *	@param[in] f_normal_epsilon is maximal allowed normal distance
		 *	@param[in] f_color_epsilon is maximal allowed color distance (euclidean)
		 *	@param[in] f_texcoord_epsilon is maximal allowed texcoord distance
		 *
		 *	@note Call b_Status() to see wheter the constructor succeeded.
		 *	@note This runs in best case linear time in number of mesh vertices in case
		 *		each uniform grid cell contains a single vertex, or in quadratic time
		 *		in case a single uniform grid cell contains all the vertices.
		 */
		CVertexGroupTable(const CPolyMesh &r_mesh, const CUniformGrid<> &r_vertex_hash,
			bool b_compare_normal = false, bool b_compare_color = false,
			size_t n_compare_texcoord_num = _TyVertex::n_Texcoord_Num,
			float f_epsilon_ex = f_epsilon, float f_normal_epsilon = f_epsilon,
			float f_color_epsilon = f_epsilon, float f_texcoord_epsilon = f_epsilon);

		/**
		 *	@return Returns true in case constructor succeeded and
		 *		the table is ready to use, otherwise returns false.
		 */
		bool b_Status() const;

		/**
		 *	@brief gets the number of groups of colocated vertices
		 *	@return Returns the number of groups of colocated vertices.
		 */
		inline size_t n_Group_Num() const
		{
			return m_table.size();
		}

		/**
		 *	@brief gets group table contents
		 *	@return Returns const reference to the group table contents.
		 */
		inline const _TyGroupTable &r_GroupTable() const
		{
			return m_table;
		}

		/**
		 *	@brief gets the group affiliation table
		 *	@return Returns const reference to group affiliation table.
		 */
		inline const std::vector<size_t> &r_GroupIndexTable() const
		{
			return m_vertex_group_id_list;
		}

		/**
		 *	@brief gets a representative vertex for a given group
		 *	@param[in] n_group is zero-based index of the colocated vertex group
		 *	@return Returns a pointer to the first vertex of the selected group.
		 */
		inline _TyVertex *p_FirstVertex(size_t n_group) const
		{
			return m_table[n_group].front();
		}

		/**
		 *	@brief builds the vertex reference table
		 *		(list of referencing polygons per each vertex group)
		 *
		 *	@param[out] r_vertex_ref_list is reference to the vector where the
		 *		vertex references should be stored (gets overwritten)
		 *	@param[in] r_mesh is a mesh to construct the vertex reference table for
		 *	@param[in] r_merge_table is vertex group table for the same mesh
		 *
		 *	@return Returns true on success, false on failure.
		 *
		 *	@note This runs in linear time in the number of mesh vertices.
		 */
		inline bool Build_VertexReference_Table(_TySimpleVRefTable &r_vertex_ref_list,
			const CPolyMesh &r_mesh)
		{
			return CVertexReferenceTableFactory<CVertexRef_to_PolygonPtr,
				_TyPolygon*>::Build_VertexReference_Table(r_vertex_ref_list, r_mesh, *this);
		}

		/**
		 *	@brief builds the vertex reference table (list of references per each vertex group)
		 *
		 *	@param[out] r_vertex_ref_list is reference to the vector where the
		 *		vertex references should be stored (gets overwritten)
		 *	@param[in] r_mesh is a mesh to construct the vertex reference table for
		 *	@param[in] r_merge_table is vertex group table for the same mesh
		 *
		 *	@return Returns true on success, false on failure.
		 *
		 *	@note This runs in linear time in the number of mesh vertices.
		 */
		inline bool Build_VertexReference_Table(_TyIndexedVRefTable &r_vertex_ref_list,
			const CPolyMesh &r_mesh)
		{
			return CVertexReferenceTableFactory<CVertexRef_to_IndexPair,
				CVertexRef_to_IndexPair::_TyStoreType>::Build_VertexReference_Table(
				r_vertex_ref_list, r_mesh, *this);
		}

	protected:
		bool Create(const CPolyMesh &r_mesh, const CUniformGrid<> &r_vertex_hash, bool b_compare_normal,
			bool b_compare_color, size_t n_compare_texcoord_num, float f_epsilon_ex,
			float f_normal_epsilon, float f_color_epsilon, float f_texcoord_epsilon);
		static inline void DeleteVector(std::vector<_TyVertex*> *p_vector);
	};
};

// todo - put the below code to an .inl

/*
 *								=== CVertexHash::CUniformGrid ===
 */

/*#ifndef __VERTEX_HASH_DENSE_TABLE
std::vector<CVertexHash::_TyVertex*> CVertexHash::CUniformGrid::m_empty; // not practical anymore, as CUniformGrid is a template
#endif // !__VERTEX_HASH_DENSE_TABLE*/

/*template <class CVertex, class CVertexList>
void CVertexHash::CUniformGrid<CVertex>::Fill(CVertexList &r_list,
	Vector3f v_min, Vector3f v_max, size_t n_vertices_per_node, float f_max_epsilon)
{
	size_t n_node_num = max(size_t(1), (r_list.size() + n_vertices_per_node - 1) / n_vertices_per_node);
	Vector3f v_cell_size = v_max - v_min;
	m_f_cell_side = std::max((float)pow(v_cell_size.x * v_cell_size.y * v_cell_size.z /
		n_node_num, 1.0f / 3), std::max(f_max_epsilon * 2, .01f));
	m_f_inv_cell_side = 1 / m_f_cell_side;
	m_v_table_size.x = max(size_t(1), size_t(v_cell_size.x * m_f_inv_cell_side + .5f));
	m_v_table_size.y = max(size_t(1), size_t(v_cell_size.y * m_f_inv_cell_side + .5f));
	m_v_table_size.z = max(size_t(1), size_t(v_cell_size.z * m_f_inv_cell_side + .5f));
	// calculate grid dimensions

#ifdef __VERTEX_HASH_DENSE_TABLE
	if(!(m_p_vertex_hash = new(std::nothrow)
	   std::vector<CVertex*>[m_v_table_size.x * m_v_table_size.y * m_v_table_size.z]))
		return;
#endif // __VERTEX_HASH_DENSE_TABLE
	// create new hash

	try {
		for(size_t i = 0, m = r_list.size(); i < m; ++ i) {
			typename CVertexList::value_type &r_vertex = r_list[i];

			Vector3<size_t> v_index[2] = {
				v_UniformGrid_Pos((Vector3f)r_vertex),
				v_UniformGrid_Pos(((Vector3f)r_vertex) + (m_f_cell_side * .5f))
			};
			// calc indices

			for(int x = 0; x < 2; x ++) {
				for(int y = 0; y < 2; y ++) {
					for(int z = 0; z < 2; z ++) {
						size_t n_cell =
							v_index[x].x + m_v_table_size.x * (v_index[y].y + m_v_table_size.y * v_index[z].z);
						// calc cell index

#ifdef __VERTEX_HASH_DENSE_TABLE
						if(!stl_ut::Reserve_1More(m_p_vertex_hash[n_cell])) {
							delete[] m_p_vertex_hash;
							m_p_vertex_hash = 0;
							return;
						}
						m_p_vertex_hash[n_cell].push_back((CVertex*)&r_vertex));
#else // __VERTEX_HASH_DENSE_TABLE
						m_vertex_hash[n_cell].push_back((CVertex*)&r_vertex);
#endif // __VERTEX_HASH_DENSE_TABLE
						// add reference into a cell

						if(v_index[0].z == v_index[1].z)
							break;
					}
					if(v_index[0].y == v_index[1].y)
						break;
				}
				if(v_index[0].x == v_index[1].x)
					break;
			}
			// add references to a vertex to all cells it hit
		}
	} catch(std::bad_alloc&) {
		m_v_table_size = Vector3<size_t>(0, 0, 0); // mark failure
	}
}*/

template <class CVertex>
CVertexHash::CUniformGrid<CVertex>::CUniformGrid(CPolyMesh &r_mesh,
	size_t n_vertices_per_node, float f_max_epsilon) // t_odo - template a Fill() function, make a helper for wrapping CPolyMesh with a std::vector lookalike interface, see how a constructor can call other constructors (and whether msvc 60 is ok with that)
#ifndef __VERTEX_HASH_DENSE_TABLE
	:m_empty(r_GetEmpty())
#endif // !__VERTEX_HASH_DENSE_TABLE
{
	Vector3f v_min, v_max;
	r_mesh.BoundingBox(v_min, v_max);
	// calculate bounding box

	Fill(CVertexHash::CMeshVertexListHelper(r_mesh), v_min, v_max, n_vertices_per_node, f_max_epsilon);
}

template <class CVertex>
CVertexHash::CUniformGrid<CVertex>::CUniformGrid(std::vector<CVertex> &r_vertex_list,
	size_t n_vertices_per_node, float f_max_epsilon)
#ifndef __VERTEX_HASH_DENSE_TABLE
	:m_empty(r_GetEmpty())
#endif // !__VERTEX_HASH_DENSE_TABLE
{
	Vector3f v_min, v_max;
	if(!r_vertex_list.empty()) {
		v_min = (Vector3f)r_vertex_list.front();
		v_max = v_min;
	}
	for(size_t i = 1, n = r_vertex_list.size(); i < n; ++ i) {
		Vector3f v_pos = r_vertex_list[i];
		for(int j = 0; j < 3; ++ j) {
			if(v_min[j] > v_pos[j])
				v_min[j] = v_pos[j];
			if(v_max[j] < v_pos[j])
				v_max[j] = v_pos[j];
		}
	}
	// calculate the bounding box

	Fill(r_vertex_list, v_min, v_max, n_vertices_per_node, f_max_epsilon);
}

#ifdef __VERTEX_HASH_DENSE_TABLE
template <class CVertex>
CVertexHash::CUniformGrid<CVertex>::~CUniformGrid()
{
	if(m_p_vertex_hash)
		delete[] m_p_vertex_hash;
}
#endif // __VERTEX_HASH_DENSE_TABLE

/*const std::vector<CVertexHash::CUniformGrid::_TyVertex*>
	&CVertexHash::CUniformGrid::r_Hash(Vector3f v_pos) const
{
	size_t p_table_size[3] = {m_v_table_size.x, m_v_table_size.y, m_v_table_size.z};
	ptrdiff_t p_index[3];
	for(int n = 0; n < 3; n ++) {
		p_index[n] = ptrdiff_t(v_pos[n] * m_f_inv_cell_side) % p_table_size[n];
		while(p_index[n] < 0)
			p_index[n] += p_table_size[n];
	}
	size_t n_cell = p_index[0] + (p_index[1] + p_index[2] * m_v_table_size.y) * m_v_table_size.x;
	return m_p_vertex_hash[n_cell];
}*/

template <class CVertex>
Vector3<size_t> CVertexHash::CUniformGrid<CVertex>::v_UniformGrid_Pos(Vector3f v_pos) const
{
	_ASSERTE(m_v_table_size.x > 0 && m_v_table_size.y > 0 && m_v_table_size.z > 0);
	Vector3<size_t> v_index;
	for(int n = 0; n < 3; n ++) { // unroll?
		size_t n_pos = size_t(fmod(fabs(v_pos[n] * m_f_inv_cell_side), float(m_v_table_size[n])));
		if(v_pos[n] < 0)
			n_pos = m_v_table_size[n] - 1 - n_pos; // modulo rounds in the opposite direction then
		_ASSERTE(n_pos < m_v_table_size[n]);
		v_index[n] = n_pos;
	}
	return v_index;
}

template <class CVertex>
float CVertexHash::CUniformGrid<CVertex>::f_Avg_CellOccupation() const
{
#ifdef __VERTEX_HASH_DENSE_TABLE
	size_t n_vertex_num = 0;
	std::vector<_TyVertex*> *p_cell = m_p_vertex_hash;
	for(size_t i = 0, n = m_v_table_size.x * m_v_table_size.y * m_v_table_size.z; i < n; ++ i, ++ p_cell) {
		_ASSERTE(n_vertex_num <= SIZE_MAX - p_cell->size());
		n_vertex_num += p_cell->size();
	}
	return float(n_vertex_num) / (m_v_table_size.x * m_v_table_size.y * m_v_table_size.z);
#else // __VERTEX_HASH_DENSE_TABLE
	size_t n_vertex_num = 0;
	for(std::map<size_t, std::vector<_TyVertex*> >::const_iterator p_map_it =
	   m_vertex_hash.begin(), p_end_it = m_vertex_hash.end(); p_map_it != p_end_it; ++ p_map_it)
		n_vertex_num += (*p_map_it).second.size();
	return float(n_vertex_num) / (m_v_table_size.x * m_v_table_size.y * m_v_table_size.z);
#endif // __VERTEX_HASH_DENSE_TABLE
}

/*
 *								=== ~CVertexHash::CUniformGrid ===
 */

#endif // !__POLYMESH_VERTEX_HASHING_INCLUDED
