/***************************************************************************
*                                                                          *
*  Copyright (C) Golaem S.A.  All Rights Reserved.                         *
*                                                                          *
***************************************************************************/

#pragma once

#include <glmCoreAPI.h>
#include "glmDelaunay.h"
#include "glmDelaunayQuery2.h"
#include "glmVector2.h"
#include "glmSet.h"

namespace glm
{
	/**
	* \brief This class defines 2D Delaunay Triangulation
	* 
	* \ingroup delaunay
	*
	* \author Golaem <dev@golaem.com>
	*
	* \param float Manipulated scalar type (\ref Expression, double, float...)
	*/

	class GLM_CORE_API Delaunay2 : public Delaunay
	{
	protected:

		struct Information ;

	public:

		GLM_CLASS_STAT_ID( glm::MemoryStatIds::GolaemShared)

		/**
		* \brief Constructor
		* \param verticesCount Number of vertices 
		* \param vertices Array of vertices whose Delaunay triangulation is required
		* \param epsilon  Tolerance used for determining the intrinsic dimension of the input set of vertices
		* \param queryType Wanted precision (see DelaunayQuery::Type doxygen for more information)
		* \warning The input array of vertices is acquired by the class and will be deleted by it
		*/
		Delaunay2(const unsigned int verticesCount, Vector2* vertices, const float epsilon, const DelaunayQuery::Type::Values queryType) ;

		/**
		* \brief destructor
		*/
		virtual ~Delaunay2() ;

		/// \name Member accessors
		/// @{
		/**
		* \brief returns the input vertex array
		* \return  the input vertex array
		*/
		inline const Vector2* getVertices() const ;

		/**
		* \brief Returns the number of unique vertices processed
		* \return the number of unique vertices processed
		*/
		inline unsigned int getUniqueVerticesCount() const ;
		/// @}

		/// \name Other Dimension accessors
		/// @{
		/**
		* \brief the 1d Delaunay as a line if getDimension() returns 1
		* \return the 1d Delaunay as a line if getDimension() returns 1
		*/
		inline const Vector2& getLineOrigin() const ;

		/**
		* \brief Returns the line direction of getLineOrigin()
		* \return the line direction of getLineOrigin()
		*/
		inline const Vector2& getLineDirection() const ;
		/// @}

		/// \name Triangulation manipulation
		/// @{
		/**
		* \brief get information about a triangulation
		* \param verticesCount verticesCount Number of vertices 
		* \param vertices[] vertices Array of vertices whose Delaunay triangulation is required
		* \param epsilon epsilon Tolerance used for determining the intrinsic dimension of the input set of vertices
		* \param[out] info info Computed information
		*/
		static void getInformation(const unsigned int verticesCount, const Vector2 vertices[], const float epsilon, Information& info);

		/**
		* \brief Returns the hull edges of the triangulation
		* \param[out] edgesCount edgesCount Number of returned edges
		* \param[out] indices indices Array of 2*edgesCount indices, each pair representing an edge
		* \return true if the dimension of the triangulation is 2
		* \note Returned edges are not ordered 
		* \warning Do not forget to delete the indices array when no longer used
		*/
		bool getHull (unsigned int& edgesCount, int*& indices) ;

		/**
		* \brief Get the Hull closest edge to a point
		* \param p the 2d point
		* \param[out] indexEdgeP0 index of first vertex of the edge
		* \param[out] indexEdgeP1 index of second vertex of the edge
		* \return true if it found a valid Hull edge
		*/
		bool getHullClosestEdge (const Vector2& p, int& indexEdgeP0, int& indexEdgeP1) const ;

		/**
		* \brief Returns a triangle that contains a point
		* \param point Wanted point
		* \return the triangle index i with 0 <= i < getSimplicesCount() (-1 if there is no containing triangle)
		*/
		int getContainingTriangle (const Vector2& point) const;

		/**
		* \brief returns an array with the path of triangles visited in a getContainingTriangle function call
		* \return an array with the path of triangles visited in a getContainingTriangle function call
		*/
		inline const int* getPath() const ;

		/**
		* \brief returns the last index of the array returned by getPath()
		* \return 
		*/
		inline int getPathLast() const ;

		/**
		* \brief Returns the vertex indices of the edge of the last triangle of the path obtained by getContainingTriangle
		* \param[out] v0 First vertex index of the edge
		* \param[out] v1 Second vertex index of the edge
		* \param v2 Vertex index of the point to the opposite of the edge 
		* \return the index of the triple of vertex indices: the value is 0, 1, or 2.
		* \note the returned indices are listed in counterclockwise order relative to the convex hull of the data points
		* \note if getContainingTriangle has returned -1, the input point is outside a edge of the last triangle in the path. This edge is returned by this function.
		*/
		inline int getLastEdge (int& v0, int& v1, int& v2) const ;
		/// @}

		/// \name Triangulation accessors
		/// @{
		/**
		* \return get the vertices of a triangle 
		* \param i Index of the wanted triangle
		* \param[out] vertices Array of vertices of the triangle
		* \return true if i is a valid triangle index, in which case vertices are valid
		*/
		bool getVertexSet (const int i, Vector2 vertices[3]) const ;

		/**
		* \brief Get the closest vertex to a point
		* \param p the 2d point
		* \return the index of the closest vertex
		*/
		int getClosestVertex (const Vector2& p) const ;

		/**
		* \brief Get the vertices indices of a triangle 
		* \param i Index of the wanted triangle
		* \param[out] indices Array of vertices indices of the triangle
		* \return true if i is a valid triangle index, in which case indices are valid
		*/
		bool getIndexSet (const int i, int indices[3]) const ;

		/**
		* \brief Get the indices of triangles adjacent to a triangle 
		* \param i Index of the wanted triangle
		* \param[out] adjacencies Array of indices of triangles adjacent to the triangle 
		* \return true if i is a valid triangle index, in which case adjacencies are valid
		*/
		bool getAdjacentSet (const int i, int adjacencies[3]) const ;

		/**
		* \brief Compute the barycentric coordinates of a given point with respect to a given triangle
		* \param i Index of the given triangle
		* \param p Wanted point
		* \param[out] bary Computed barycentric coordinates
		* \return true if i is a valid triangle index, in which case barycentric coordinates are valid
		*/
		bool getBarycentricSet (const int i, const Vector2& p, float bary[3]) const ;


		/// @}

	protected:		

		/// \name Internal Types & Structures
		/// @{
		/**
		* \brief Triangulation Triangle
		*/
		struct Triangle
		{
		public:
			GLM_CLASS_STAT_ID( glm::MemoryStatIds::GolaemShared)


			Triangle();

			/**
			* \brief Constructor
			* \param v0 Index of the first vertice
			* \param v1 Index of the second vertice
			* \param v2 Index of the third vertice
			*/
			Triangle( const int v0, const int v1, const int v2 ) ;

			/**
			* \brief Todo
			* \param i 
			* \param adj 
			* \param query 
			* \param supervertices 
			* \return 
			*/
			bool isInsertionComponent (int i, Triangle* adj, const DelaunayQuery2* query, const int* supervertices) ;

			/**
			* \brief update adjacencies 
			* \param adjIndex 
			* \param adj 
			* \return 
			*/
			int detachFrom (const int adjIndex, Triangle* adj) ;

			/// Adjacent triangles
			Triangle* _adj[3];		

			/// Indices of the triangle vertices
			int _vertices[3];

			int	_time;
			bool _isComponent;
			bool _onStack;
			bool _inUse; // replaces former GlmSet of Triangle*
		};

		struct Vertex
		{
		public:
			GLM_CLASS_STAT_ID( glm::MemoryStatIds::GolaemShared)

				Vertex();

			int _edgesIndicesInCacheArray[2];
			int _vertexValue;				
		};

		struct Edge
		{
		public:
			GLM_CLASS_STAT_ID( glm::MemoryStatIds::GolaemShared)

				Edge();

			/// Owner triangle
			Triangle* _ownerTriangle; // can store pointer as triangle is never reallocated

			/// Adjacent edges: _triangles[0] points to edge sharing _vertices[0], _triangles[1] points to edge sharing _vertices[1]
			int _adjacentEdgesIndicesInCacheArray[2];
			int	_verticesValues[2]; // order for align
			int	_nullIndex;
		};

		/**
		* \brief 2D Triangulation Information
		*/
		struct Information
		{
			/// Intrinsic dimension of the input set
			int	_dimension;											

			/// Axis-aligned bounding box of the input set
			float _min[2], _max[2];

			/// Larger of max.x-min.x and max.y-min.y
			float _maxRange;

			/// Coordinate system.  The origin is valid for any dimension d.
			Vector2 _origin;				

			// Is valid only for 0 <= i < d. If d = 0, all points are the same.  If d = 1, all points lie on a line segment. If d = 2, the points are not collinear.
			Vector2 _direction[2];	

			/// Indices that define the maximum dimensional extents. _extreme[0] and _extreme[1] are the indices for the points that define the largest extent in one of the coordinate axis directions
			int _extreme[3];								

			/// Triangle formed by the points _vertices[extreme0], _vertices[extreme1], and _vertices[extreme2] is clockwise or counterclockwise, the condition stored in _extremeCCW.
			bool _extremeCCW;		
		};
		/// @}

		Triangle* obtainTriangle();
		void recycleTriangle(Triangle*);

		Edge* polygonInsertEdge(int v0, int v1);
		bool polygonIsClosed();

		void update(const int i) ;
		Triangle* getContainingTriangle(const int i);
		void removeTriangles();
		bool isSupervertex(const int i) const ;

		/// Input vertices
		Vector2* _vertices;

		/// Current triangulation
		// manage a triangle pool to avoid allocating one by one. 
		glm::Array<Triangle>	_trianglePool; // avoid calling an allocation for each triangle, as we have a upper bound for expected triangles we allocate the whole pool at once.
		glm::PODArray<int>		_trianglePoolRecycledIndices;	// should stay on low size, as we create more triangles than we delete at each step. maybe even one index could be sufficient
		uint32_t				_trianglePoolFirstAvailableIndex; // first available index, when updating is set to a recycled reference, as we create more triangles than we delete at each step. 

		/// Number of unique vertices processed
		unsigned int _uniqueVerticesCount;		

		/// Indices of the three supertriangle vertices
		int	_supervertices[3];		

		/// Line of containment if the dimension is 1
		Vector2	_lineOrigin;					

		/// Line of containment if the dimension is 1
		Vector2	_lineDirection;				

		/// Path of triangles visited in a getContainingTriangle function call
		mutable int* _path;							

		/// Last index contained in the array _path
		mutable int _pathLast;						

		// The scaled input vertices with additional storage for the three supertriangle vertices.  
		// This array and supporting data structures are for robust calculations.
		Vector2* _sVertices;
		DelaunayQuery2*	_query;
		Vector2	_min;
		float	_scale;

		// for VertexEdgeManifoldMesh replacement (too much allocations with its 2 maps)
		glm::Array<Vertex> _polygonVerticesCache;
		glm::Array<Edge> _polygonEdgesCache;
		glm::PODArray<Triangle*> _triStackCache;

		// If a query point is not in the convex hull of the input points, the point is outside an edge of the last triangle in the search path.
		// These are the vertex indices for that edge.
		mutable int _lastEdgeV0, _lastEdgeV1;
		mutable int _lastEdgeOpposite, _lastEdgeOppositeIndex;
		//@}
		
		// for gcc
		using Delaunay::_queryType;
		using Delaunay::_verticesCount;
		using Delaunay::_dimension;
		using Delaunay::_simplicesCount;
		using Delaunay::_indices;
		using Delaunay::_adjacencies;
		using Delaunay::_epsilon;
	};

	//-----------------------------------------------------------------------------
	// getVertices
	//-----------------------------------------------------------------------------

	inline const Vector2* 
		Delaunay2::getVertices() const
	{
		return _vertices;
	}

	//-----------------------------------------------------------------------------
	// getUniqueVerticesCount
	//-----------------------------------------------------------------------------

	inline unsigned int 
		Delaunay2::getUniqueVerticesCount() const
	{
		return _uniqueVerticesCount;
	}

	//-----------------------------------------------------------------------------
	// getLineOrigin
	//-----------------------------------------------------------------------------

	inline const Vector2& 
		Delaunay2::getLineOrigin() const
	{
		return _lineOrigin;
	}

	//-----------------------------------------------------------------------------
	// getLineDirection
	//-----------------------------------------------------------------------------

	inline const Vector2& 
		Delaunay2::getLineDirection() const
	{
		return _lineDirection;
	}

	//-----------------------------------------------------------------------------
	// getPath
	//-----------------------------------------------------------------------------

	inline const int* 
		Delaunay2::getPath() const
	{
		return _path;
	}

	//-----------------------------------------------------------------------------
	// getPathLast
	//-----------------------------------------------------------------------------

	inline int 
		Delaunay2::getPathLast() const
	{
		return _pathLast;
	}

	//-----------------------------------------------------------------------------
	// getLastEdge
	//-----------------------------------------------------------------------------

	inline int 
		Delaunay2::getLastEdge (int& v0, int& v1, int& v2) const
	{
		v0 = _lastEdgeV0;
		v1 = _lastEdgeV1;
		v2 = _lastEdgeOpposite;

		return _lastEdgeOppositeIndex;
	}
}

