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

#include "../NewFix.h"
#include "../CallStack.h"
#include "VertexHash.h"
#include "../BitArray.h"

/*
 *								=== CVertexHash::CVertexGroupTable ===
 */

class CVertexHash::CVertexGroupTable::CGroupVertices {
protected:
	std::vector<_TyVertex*> &m_r_group;
	const CForwardAllocatedPool<_TyVertex> &m_vertex_pool;
	CBitArray &m_r_vertex_flags;

public:
	CGroupVertices(std::vector<_TyVertex*> &r_group,
		const CForwardAllocatedPool<_TyVertex> &r_vertex_pool, CBitArray &r_vertex_flags)
		:m_r_group(r_group), m_vertex_pool(r_vertex_pool),
		m_r_vertex_flags(r_vertex_flags)
	{}

	inline void operator ()(_TyVertex *p_vertex) // throw(std::bad_alloc)
	{
		size_t n_index = m_vertex_pool.n_IndexOf(p_vertex);
		_ASSERTE(n_index != size_t(-1));
		//_ASSERTE(!m_r_vertex_flags[n_index]);
		if(m_r_vertex_flags[n_index])
			return; // one vertex can be close to two others
		m_r_vertex_flags.Raise(n_index);
		m_r_group.push_back(p_vertex);
	}
};

class CVertexHash::CVertexGroupTable::CCreateIndexTable {
protected:
	std::vector<size_t> &m_r_vertex_group_id_list;
	const CForwardAllocatedPool<CVertexHash::_TyVertex> &m_vertex_pool;
	size_t m_n_index;

	class CFillIndices {
	protected:
		std::vector<size_t> &m_r_vertex_group_id_list;
		const CForwardAllocatedPool<CVertexHash::_TyVertex> &m_vertex_pool;
		size_t m_n_index;

	public:
		CFillIndices(std::vector<size_t> &r_vertex_group_id_list,
			const CForwardAllocatedPool<_TyVertex> &r_vertex_pool, size_t n_index)
			:m_r_vertex_group_id_list(r_vertex_group_id_list),
			m_vertex_pool(r_vertex_pool), m_n_index(n_index)
		{}

		inline void operator ()(const CVertexHash::_TyVertex *p_vertex)
		{
			m_r_vertex_group_id_list[m_vertex_pool.n_IndexOf(p_vertex)] = m_n_index;
		}
	};

public:
	CCreateIndexTable(std::vector<size_t> &r_vertex_group_id_list,
		const CForwardAllocatedPool<_TyVertex> &r_vertex_pool)
		:m_r_vertex_group_id_list(r_vertex_group_id_list),
		m_vertex_pool(r_vertex_pool), m_n_index(0)
	{}

	inline void operator ()(const std::vector<_TyVertex*> &r_equal_vertex_list)
	{
		std::for_each(r_equal_vertex_list.begin(), r_equal_vertex_list.end(),
			CFillIndices(m_r_vertex_group_id_list, m_vertex_pool, m_n_index));
		++ m_n_index;
	}
};

CVertexHash::CVertexGroupTable::CVertexGroupTable(const CPolyMesh &r_mesh,
	const CVertexHash::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)
{
	m_b_status = Create(r_mesh, r_vertex_hash, b_compare_normal,
		b_compare_color, n_compare_texcoord_num, f_epsilon_ex,
		f_normal_epsilon, f_color_epsilon, f_texcoord_epsilon);
}

bool CVertexHash::CVertexGroupTable::b_Status() const
{
	return m_b_status;
}

bool CVertexHash::CVertexGroupTable::Create(const CPolyMesh &r_mesh,
	const CVertexHash::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)
{
	if(!r_vertex_hash.b_Status())
		return false;

	if(f_epsilon_ex > r_vertex_hash.f_Max_Epsilon() ||
	   (b_compare_normal && f_normal_epsilon > r_vertex_hash.f_Max_Epsilon()) ||
	   (b_compare_color && f_color_epsilon > r_vertex_hash.f_Max_Epsilon()) ||
	   (n_compare_texcoord_num > 0 && f_texcoord_epsilon > r_vertex_hash.f_Max_Epsilon()))
		return false;
	// makes sure that the grid is fine enough to search with the given epsilon

	const size_t n_vertex_num = r_mesh.n_Vertex_Num();
	CBitArray vertex_flags(n_vertex_num);
	if(vertex_flags.n_Length() < n_vertex_num)
		return false;
	vertex_flags = false;
	// alloc and clear vertex flags

	_ASSERTE(m_table.empty());
	std::vector<std::vector<_TyVertex*>*> temp_table; // note that we could do away with a list (would entirely eliminate the need to dynamically alloc stuff)
	stl_ut::Reserve_N(temp_table, n_vertex_num / 2); // keep it here, ignore bad_alloc, might not need so many entries
	// roughly estimate to avoid resizing later

	try {
		for(size_t i = 0, n = n_vertex_num; i < n; ++ i) {
			if(vertex_flags[i])
				continue;
			// we've already added this one

			std::vector<_TyVertex*> *p_group = new std::vector<_TyVertex*>();
			temp_table.push_back(p_group);
			// create a new vertex group & add it to group CVertexGroupTable

			{
				CUniformGrid<>::CVertexGenPredicate pred(r_mesh.r_Vertex(i), b_compare_normal,
					b_compare_color, n_compare_texcoord_num, f_epsilon_ex, f_normal_epsilon,
					f_color_epsilon, f_texcoord_epsilon);
				// a predicate for comparing vertices

				r_vertex_hash.ForEachVertexNear((Vector3f)r_mesh.r_Vertex(i),
					pred, CGroupVertices(*p_group, r_mesh.r_Vertex_Pool(), vertex_flags)); // O(n) where n is number of vertices in the uniform grid cell near the given vertex
				// add all the vertices 
			}
			// other vertices include current vertex as well so we don't need to explicitly add it

			if(!p_group->size()) {
				temp_table.erase(temp_table.end() - 1);
				delete p_group;
			} else {
				_ASSERTE(vertex_flags[i]);
				// otherwise it should mark itself as well
			}
			// when there's vertex with NAN coordinate, it can't be compared with the other
			// ones, neither with itself so it's not included in CVertexGroupTable
		}
		// group all the vertices, roughly O(n log n) depending on fill of the uniform grid

		m_table.resize(temp_table.size());
		for(size_t i = 0, n = temp_table.size(); i < n; ++ i)
			m_table[i].swap(*temp_table[i]); // just swap the lists, no copying involved
		std::for_each(temp_table.begin(), temp_table.end(), DeleteVector); // !!
		// throw the dynamically allocated CVertexGroupTable away, avoid expensive data copying on resizing
	} catch(std::bad_alloc&) {
		std::for_each(temp_table.begin(), temp_table.end(), DeleteVector);
		return false;
	}
	// create vertex group CVertexGroupTable

	{
		if(!stl_ut::Resize_To_N(m_vertex_group_id_list, n_vertex_num))
			return false;
		// alloc index CVertexGroupTable (note this is written on separate lines because
		// it's causing internal compiler error in MSVC 6.0 otherwise)

		std::for_each(m_table.begin(), m_table.end(),
			CCreateIndexTable(m_vertex_group_id_list, r_mesh.r_Vertex_Pool())); // O(n)
		// fill vertex indices (this will cause problems if called with a different/changed mesh)
	}
	// create vertex index CVertexGroupTable right away, the storage is not so bad

	return true;
}

inline void CVertexHash::CVertexGroupTable::DeleteVector(std::vector<_TyVertex*> *p_vector)
{
	delete p_vector;
}

/*
 *								=== ~CVertexHash::CVertexGroupTable ===
 */

/*
 *								=== CVertexHash ===
 */

#if 0 // templated away

bool CVertexHash::Build_VertexReference_Table(
	std::vector<std::vector<_TyPolygon*> > &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 CPolyMesh::_TyPolygon &r_poly = r_mesh.r_Polygon(i);
			for(size_t n = 0, nn = r_poly.n_Vertex_Num(); n < nn; ++ n) {
				size_t n_index_n = r_vertex_list.n_IndexOf(r_poly.t_Vertex(n).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(const_cast<CPolyMesh::_TyPolygon*>(&r_poly));
				// add the polygon index to the given group
			}
		}
		// create CVertexGroupTable of polygon references
	} catch(std::bad_alloc&) {
		return false;
	}

	return true;
}

bool CVertexHash::Build_VertexReference_Table(
	std::vector<std::vector<std::pair<size_t, size_t> > > &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 CPolyMesh::_TyPolygon &r_poly = r_mesh.r_Polygon(i);
			for(size_t n = 0, nn = r_poly.n_Vertex_Num(); n < nn; ++ n) {
				size_t n_index_n = r_vertex_list.n_IndexOf(r_poly.t_Vertex(n).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(std::make_pair(i, n));
				// add the polygon index to the given group
			}
		}
		// create CVertexGroupTable of polygon references
	} catch(std::bad_alloc&) {
		return false;
	}

	return true;
}

#endif // 0

/*
 *								=== ~CVertexHash ===
 */
