/*
								+----------------------------------+
								|                                  |
								|  ***  Vertex pool template  ***  |
								|                                  |
								|   Copyright © -tHE SWINe- 2008   |
								|                                  |
								|           VertexPool.h           |
								|                                  |
								+----------------------------------+
*/

#pragma once
#ifndef __VERTEX_POOL_INCLUDED
#define __VERTEX_POOL_INCLUDED

/**
 *	@file dev/VertexPool.h
 *	@data 2008
 *	@author -tHE SWINe-
 *	@brief Vertex pool template
 *
 *	@date 2009-05-23
 *
 *	removed all instances of std::vector::reserve and replaced them by stl_ut::Reserve_*
 *
 *
 *	@date 2010-12-20
 *
 *	removed CVertexPool::b_Error() and added code to re-throw std::bad_alloc on failure instead.
 *	changed size types from int to size_t.
 *
 *	@todo debug this (especially size_t related issues)
 *	fixed indexing issue in the for_each loop (maybe only in one version)
 *
 *	@date 2012-06-19
 *
 *	Moved multiple inclusion guard before file documentation comment.
 *
 */

#include "../NewFix.h"

#include <vector>
#include <algorithm>

/*
 *								=== CVertexPool ===
 */

template <class CVertexStruct>
class CVertexPool {
protected:
	size_t m_n_page_size; // size of a single page
	size_t m_n_last_page_used; // index of first unused vertex in the last page
	std::vector<CVertexStruct*> m_vertex_pool; // list of pages

public:
	/*
	 *	CVertexPool::CVertexPool(int n_page_size = 1000)
	 *		- default constructor
	 *		- n_page_size is number of vertices in a single page
	 *		  (bigger pages are better, but may lead to memory trashing)
	 */
	CVertexPool(size_t n_page_size = 1000)
		:m_n_page_size(n_page_size), m_n_last_page_used(n_page_size)
	{
		__FuncGuard("CVertexPool::CVertexPool");

		_ASSERTE(n_page_size > 0); // won't work otherwise
	}

	/*
	 *	CVertexPool::~CVertexPool()
	 *		- destructor
	 */
	~CVertexPool()
	{
		__FuncGuard("CVertexPool::~CVertexPool");

		std::for_each(m_vertex_pool.begin(), m_vertex_pool.end(), _DeletePage);
	}

	/*
	 *	void CVertexPool::Clear()
	 *		- removes all vertices in the vertex pool and deallocates all memory
	 */
	void Clear()
	{
		std::for_each(m_vertex_pool.begin(), m_vertex_pool.end(), _DeletePage);
		m_vertex_pool.clear();
		m_n_last_page_used = m_n_page_size; // all used
	}

	/*
	 *	void Swap(CVertexPool<CVertexStruct> &r_other)
	 *		- swaps contents of this vertex pool and r_other
	 */
	void Swap(CVertexPool<CVertexStruct> &r_other)
	{
		size_t n_page_size = m_n_page_size;
		m_n_page_size = r_other.m_n_page_size;
		r_other.m_n_page_size = n_page_size;

		size_t n_last_page_used = m_n_last_page_used;
		m_n_last_page_used = r_other.m_n_last_page_used;
		r_other.m_n_last_page_used = n_last_page_used;

		m_vertex_pool.swap(r_other.m_vertex_pool);
	}

	/*
	 *	bool CVertexPool::Reserve(int n_vertex_num)
	 *		- makes sure there's at least n_vertex_num vertices in the pool
	 *		- returns true on success, false on failure
	 *		- note this works a bit differently from std::vector::reserve
	 *		  which creates space for vertices to allocate. this creates
	 *		  space and allocates vertices as well
	 *		- in case this fails, vertex pool might have some extra vertices
	 *		  allocated (but not enough to reach n_vertex_num)
	 */
	bool Reserve(int n_vertex_num) /*throw(std::bad_alloc)*/
	{
		size_t n_cur_vertex_num = n_Vertex_Num();
		if(n_cur_vertex_num >= n_vertex_num)
			return true;
		// calculate current vertex count and see if it suffices

		n_vertex_num -= n_cur_vertex_num;
		// calculate how many more vertices do we need

		if(!n_cur_vertex_num && m_vertex_pool.empty()) {
			_ASSERTE(m_n_last_page_used == m_n_page_size);
			m_n_last_page_used = m_n_page_size = max(1024, n_Make_Lower_POT(n_vertex_num));
		}
		// in case the mesh is empty and there is a lot of vertices, resize pages

		if(m_n_last_page_used != m_n_page_size) {
			if(n_vertex_num < m_n_page_size - m_n_last_page_used) {
				m_n_last_page_used += n_vertex_num;
				return true;
			}
			n_vertex_num -= m_n_page_size - m_n_last_page_used;
			m_n_last_page_used = m_n_page_size;
		}
		// use unused rest of the last page

		int n_page_num = (n_vertex_num + (m_n_page_size - 1)) / m_n_page_size;
		// calculate how many more pages do we need

		if(!stl_ut::Reserve_NMore(m_vertex_pool, n_page_num)) {
			throw std::bad_alloc();
			return false;
		}
		// make sure theres space for new pages in the pool

		for(size_t i = 0; i < n_page_num; ++ i) {
			CVertexStruct *p_page;
			if(!(p_page = new(std::nothrow) CVertexStruct[m_n_page_size])) {
				throw std::bad_alloc();
				return false;
			}
			// alloc new page

			m_vertex_pool.push_back(p_page);
			// put the new page into the list
		}
		// alloc all the pages

		m_n_last_page_used = n_vertex_num - (n_page_num - 1) * m_n_page_size;
		// calculate how many vertices will be used in the last page

		return true;
	}

	/*
	 *	CVertexStruct *CVertexPool::p_GetVertex()
	 *		- returns pointer to a new vertex
	 *		- returns 0 in case there was not enough memory
	 */
	CVertexStruct *p_GetVertex() /*throw(std::bad_alloc)*/
	{
		__FuncGuard("CVertexPool::p_GetVertex");

		if(m_n_last_page_used != m_n_page_size)
			return m_vertex_pool.back() + m_n_last_page_used ++;
		// just return next vertex

		if(!stl_ut::Reserve_1More(m_vertex_pool)) {
			throw std::bad_alloc();
			return 0;
		}
		// make sure theres space for another page in the pool

		CVertexStruct *p_page;
		if(!(p_page = new(std::nothrow) CVertexStruct[m_n_page_size])) {
			throw std::bad_alloc();
			return 0;
		}
		// alloc new page

		m_vertex_pool.push_back(p_page);
		// put the new page into the list

		m_n_last_page_used = 1;
		// we use first vertex right away

		return p_page;
	}

	/*
	 *	inline size_t CVertexPool::n_Vertex_Num() const
	 *		- returns number of currently allocated vertices
	 */
	inline size_t n_Vertex_Num() const
	{
		return (m_vertex_pool.size() - 1) * m_n_page_size + m_n_last_page_used;
	}

	/*
	 *	int CVertexPool::n_Index(const CVertexStruct *p_vertex) const
	 *		- returns index of vertex p_vertex or -1 in case p_vertex is not in the pool
	 */
	size_t n_Index(const CVertexStruct *p_vertex) const
	{
		__FuncGuard("CVertexPool::n_Index");

		std::vector<CVertexStruct*>::const_iterator p_page_it =
			std::find_if(m_vertex_pool.begin(), m_vertex_pool.end(),
			CFindPage(p_vertex, m_n_page_size));
		if(p_page_it == m_vertex_pool.end())
			return -1; // not found

		_ASSERTE(p_vertex >= *p_page_it);
		size_t n_page_index = p_vertex - *p_page_it;
		_ASSERTE(n_page_index >= 0 && n_page_index < m_n_page_size);
		// calculate index in the page

		return n_page_index + (p_page_it - m_vertex_pool.begin()) * m_n_page_size;
		// global index is page index + number of vertices in preceding pages
	}

	/*
	 *	CVertexStruct *CVertexPool::p_Vertex(size_t n_index)
	 *		- returns pointer of vertex with index n_index
	 */
	CVertexStruct *p_Vertex(size_t n_index)
	{
		__FuncGuard("CVertexPool::p_Vertex");

		return m_vertex_pool[n_index / m_n_page_size] + n_index % m_n_page_size;
	}

	/*
	 *	const CVertexStruct *CVertexPool::p_Vertex(size_t n_index) const
	 *		- returns const pointer of vertex with index n_index
	 */
	const CVertexStruct *p_Vertex(size_t n_index) const
	{
		__FuncGuard("CVertexPool::p_Vertex");

		return m_vertex_pool[n_index / m_n_page_size] + n_index % m_n_page_size;
	}

	/*
	 *	CVertexStruct *CVertexPool::operator [](size_t n_index)
	 *		- returns pointer of vertex with index n_index
	 */
	CVertexStruct *operator [](size_t n_index)
	{
		__FuncGuard("CVertexPool::operator []");

		return m_vertex_pool[n_index / m_n_page_size] + n_index % m_n_page_size;
	}

	/*
	 *	const CVertexStruct *CVertexPool::operator [](size_t n_index) const
	 *		- returns const pointer of vertex with index n_index
	 */
	const CVertexStruct *operator [](size_t n_index) const
	{
		__FuncGuard("CVertexPool::operator []");

		return m_vertex_pool[n_index / m_n_page_size] + n_index % m_n_page_size;
	}

	/*
	 *	template <class CFunctor>
	 *	CFunctor CVertexPool::ForEach(int n_begin = 0, int n_end = -1, CFunctor functor)
	 *		- for-each function for vertices
	 *		- n_begin and n_end are indices of the first
	 *		  and one after the last vertex respectively
	 *		- functor is function object vertex pointers are
	 *		  passed to and which is returned by the function
	 */
	template <class CFunctor>
	CFunctor ForEach(size_t n_begin, size_t n_end, CFunctor functor)
	{
		__FuncGuard("CVertexPool::ForEach");

		if(m_vertex_pool.empty())
			return functor;

		size_t n_first_page = n_begin / m_n_page_size;
		size_t n_first_index = n_begin % m_n_page_size;
		size_t n_last_page = (n_end == -1)? m_vertex_pool.size() - 1 : n_end / m_n_page_size;
		size_t n_last_index = (n_end == -1)? m_n_last_page_used : n_end % m_n_page_size;

		if(n_first_page == n_last_page) {
			CVertexStruct *p_page = m_vertex_pool[n_first_page];
			for(CVertexStruct *p_begin = p_page + n_first_index,
			   *p_end = p_page + n_last_index; p_begin != p_end; ++ p_begin)
				functor(p_begin);
			// cycle trough all vertices in the only page (n_first_index to n_last_index)
		} else if(n_begin < n_end || n_end == -1) {
			// the following branch is correct for non empty intervals only

			{
				CVertexStruct *p_page = m_vertex_pool[n_first_page];
				for(CVertexStruct *p_begin = p_page + n_first_index,
				   *p_end = p_page + m_n_page_size; p_begin != p_end; ++ p_begin)
					functor(p_begin);
			}
			// cycle trough all vertices in the first page (n_first_index to page end)

			for(int i = n_first_page + 1; i < n_last_page; ++ i) {
				CVertexStruct *p_page = m_vertex_pool[i];
				for(CVertexStruct *p_begin = p_page,
				   *p_end = p_page + m_n_page_size; p_begin != p_end; ++ p_begin)
					functor(p_begin);
			}
			// cycle trough all vertices in the other pages (0 to page end)

			{
				CVertexStruct *p_page = m_vertex_pool[n_last_page];
				for(CVertexStruct *p_begin = p_page,
				   *p_end = p_page + n_last_index; p_begin != p_end; ++ p_begin)
					functor(p_begin);
			}
			// cycle trough all vertices in the last page (0 to n_last_index)
		}

		return functor;
	}

	/*
	 *	template <class CFunctor>
	 *	CFunctor CVertexPool::ForEach(int n_begin = 0, int n_end = -1, CFunctor functor) const
	 *		- for-each const function for vertices
	 *		- n_begin and n_end are indices of the first
	 *		  and one after the last vertex respectively
	 *		- functor is function object vertex pointers are
	 *		  passed to and which is returned by the function
	 */
	template <class CFunctor>
	CFunctor ForEach(size_t n_begin, size_t n_end, CFunctor functor) const
	{
		__FuncGuard("CVertexPool::ForEach");

		size_t n_first_page = n_begin / m_n_page_size;
		size_t n_first_index = n_begin % m_n_page_size;
		size_t n_last_page = (n_end == -1)? m_vertex_pool.size() : n_end / m_n_page_size;
		size_t n_last_index = (n_end == -1)? 0 : n_end % m_n_page_size;

		if(n_first_page == n_last_page) {
			const CVertexStruct *p_page = m_vertex_pool[n_first_page];
			for(const CVertexStruct *p_begin = p_page + n_first_index,
			   *p_end = p_page + n_last_index; p_begin != p_end; ++ p_begin)
				functor(p_begin);
			// cycle trough all vertices in the only page (n_first_index to n_last_index)
		} else if(n_begin < n_end || n_end == -1) {
			// the following branch is correct for non empty intervals only

			{
				const CVertexStruct *p_page = m_vertex_pool[n_first_page];
				for(const CVertexStruct *p_begin = p_page + n_first_index,
				   *p_end = p_page + m_n_page_size; p_begin != p_end; ++ p_begin)
					functor(p_begin);
			}
			// cycle trough all vertices in the first page (n_first_index to page end)

			for(int i = n_first_page + 1; i < n_last_page; ++ i) {
				const CVertexStruct *p_page = m_vertex_pool[i];
				for(const CVertexStruct *p_begin = p_page,
				   *p_end = p_page + m_n_page_size; p_begin != p_end; ++ p_begin)
					functor(p_begin);
			}
			// cycle trough all vertices in the other pages (0 to page end)

			{
				const CVertexStruct *p_page = m_vertex_pool[n_last_page];
				for(const CVertexStruct *p_begin = p_page,
				   *p_end = p_page + n_last_index; p_begin != p_end; ++ p_begin)
					functor(p_begin);
			}
			// cycle trough all vertices in the last page (0 to n_last_index)
		}

		return functor;
	}

protected:
	static inline void _DeletePage(CVertexStruct *p_vertex_page)
	{
		__FuncGuard("CVertexPool::_DeletePage");

		_ASSERTE(p_vertex_page);
		delete[] p_vertex_page;
	}

	class CFindPage {
	protected:
		const CVertexStruct *m_p_begin, *m_p_end;

	public:
		CFindPage(const CVertexStruct *p_vertex, size_t n_page_size)
			:m_p_begin(p_vertex), m_p_end(p_vertex - n_page_size)
		{}

		inline bool operator ()(const CVertexStruct *p_page) const
		{
			return m_p_begin >= p_page && m_p_end < p_page;
		}
	};
};

/*
 *								=== ~CVertexPool ===
 */

/*
 *								=== TRefVertex2 ===
 */

/*
 *	template <class TBaseVertex>
 *	struct TRefVertex2
 *		- template for creating reference vertices for any arbitrary vertices
 */
template <class TBaseVertex>
struct TRefVertex2 {
	TBaseVertex *m_p_ref; // referenced vertex
	CVertexPool<TBaseVertex> *m_p_vertex_pool; // vertex pool (here we're going to add new vertices)

	typedef TBaseVertex TIntermediate;
	// intermediate type for calculations will be TBaseVertex

	/*
	 *	inline TRefVertex2(const TBaseVertex &r_t_vertex, CVertexPool<TBaseVertex> &r_vertex_pool)
	 *		- default constructor
	 */
	inline TRefVertex2(const TBaseVertex &r_t_vertex, CVertexPool<TBaseVertex> &r_vertex_pool)
		:m_p_ref(0), m_p_vertex_pool(r_vertex_pool) /*throw(std::bad_alloc)*/
	{
		m_p_ref = r_vertex_pool.p_GetVertex(); // insert it to the list
		*m_p_ref = r_t_vertex; // and copy the data
	}

	/*
	 *	inline TRefVertex2(TBaseVertex *p_vertex, CVertexPool<TBaseVertex> &r_vertex_pool)
	 *		- reference vertex that is already in the list
	 */
	inline TRefVertex2(TBaseVertex *p_vertex, CVertexPool<TBaseVertex> &r_vertex_pool)
		:m_p_ref(p_vertex), m_p_vertex_pool(&r_vertex_pool)
	{
		_ASSERTE(r_vertex_pool.n_Index(p_vertex) != -1); // make sure it's inside the vertex list
	}

	/*
	 *	inline TRefVertex2(int n_index, CVertexPool<TBaseVertex> &r_vertex_pool)
	 *		- reference vertex that is already in the list
	 */
	inline TRefVertex2(int n_index, CVertexPool<TBaseVertex> &r_vertex_pool)
		:m_p_ref(r_vertex_pool.p_Vertex(n_index)), m_p_vertex_pool(&r_vertex_pool)
	{
		_ASSERTE(m_p_ref);
	}

	/*
	 *	inline TRefVertex2(const TRefVertex2 &r_t_vertex)
	 *		- copy constructor
	 */
	inline TRefVertex2(const TRefVertex2 &r_t_vertex)
		:m_p_ref(r_t_vertex.m_p_ref), m_p_vertex_pool(r_t_vertex.m_p_vertex_pool)
	{}

	/*
	 *	inline TRefVertex2 operator =(const TRefVertex2 &r_t_vertex)
	 *		- copy operator = (need it to avoid unwanted conversions)
	 */
	inline TRefVertex2 operator =(const TRefVertex2 &r_t_vertex)
	{
		m_p_ref = r_t_vertex.m_p_ref;
		m_p_vertex_pool = r_t_vertex.m_p_vertex_pool;

		return *this;
	}

	/*
	 *	inline TRefVertex2 operator =(const TBaseVertex &r_t_vertex)
	 *		- conversion from TBaseVertex to TRefVertex2 (conversion
	 *		  is solved by adding vertex to the vertex list)
	 */
	inline TRefVertex2 operator =(const TBaseVertex &r_t_vertex) /*throw(std::bad_alloc)*/
	{
		m_p_ref = m_p_vertex_pool->p_GetVertex(); // insert it to the list
		*m_p_ref = r_t_vertex; // and copy the data

		return *this;
	}

	/*
	 *	inline operator TBaseVertex() const
	 *		- now we need means to convert vertex type to intermediate vertex type
	 */
	inline operator TBaseVertex() const
	{
		return *m_p_ref;
	}

	/*
	 *	inline operator Vector3f() const
	 *		- conversion to Vector3f should return vertex position
	 */
	inline operator Vector3f() const
	{
		return m_p_ref->v_position;
	}

	/*
	 *	inline TRefVertex2 operator =(const Vector3f &r_v_position)
	 *		- assigning Vector3f should write to vertex position
	 */
	inline TRefVertex2 operator =(const Vector3f &r_v_position)
	{
		m_p_ref->v_position = r_v_position;
		return *this;
	}

	/*
	 *	inline bool operator ==(const TBaseVertex &r_t_vertex)
	 *		- we might need means to compare two vertices
	 *		- constant f_epsilon is used as maximal coordinate distance tolerance
	 */
	inline bool operator ==(const TBaseVertex &r_t_vertex)
	{
		return *m_p_ref == r_t_vertex;
	}

	/*
	 *	TVertex operator *(float f_scalar) const
	 *		- return vertex, scaled by f_scalar
	 *		- returns a new TBaseVertex because new vertex originated
	 *		  (in case it will need to be converted to TRefVertex2, it will be added to the list)
	 */
	TBaseVertex operator *(float f_scalar) const
	{
		return *m_p_ref * f_scalar;
	}

	/*
	 *	TBaseVertex operator +(const TBaseVertex &r_vertex) const
	 *		- return vertex with sum of coordinates of both original vertices
	 *		- returns a new TBaseVertex because new vertex originated
	 *		  (in case it will need to be converted to TRefVertex2, it will be added to the list)
	 */
	TBaseVertex operator +(const TBaseVertex &r_vertex) const
	{
		return *m_p_ref + r_vertex;
	}

	/*
	 *	TRefVertex2 operator *=(float f_scalar) const
	 *		- return vertex, scaled by f_scalar
	 *		- returns this because no new vertex originated
	 *		  (coordinates of some existing vertex were scaled only)
	 */
	TRefVertex2 operator *=(float f_scalar)
	{
		*m_p_ref *= f_scalar;
		return *this;
	}

	/*
	 *	TRefVertex2 operator +=(const TBaseVertex &r_vertex) const
	 *		- return vertex with sum of coordinates of both original vertices
	 *		- returns this because no new vertex originated
	 *		  (coordinates of some existing vertex were scaled only)
	 */
	TRefVertex2 operator +=(const TBaseVertex &r_vertex)
	{
		*m_p_ref += r_vertex;
		return *this;
	}
};

/*
 *								=== ~TRefVertex2 ===
 */

#endif // __VERTEX_POOL_INCLUDED
