#ifndef TCG_MESH_HPP

#define TCG_MESH_HPP

// tcg includes

#include "../mesh.h"

namespace tcg

{

//************************************************************************

//    Polygon Mesh methods

//************************************************************************

template <typename e,="" f="" typename="" v,=""></typename>

int Mesh<v, e,="" f="">::edgeInciding(int vIdx1, int vIdx2, int n) const</v,>

{

	const V &v1 = vertex(vIdx1);

	const tcg::list<int> &incidingV1 = v1.edges();</int>

	tcg::list<int>::const_iterator it;</int>

	for (it = incidingV1.begin(); it != incidingV1.end(); ++it) {

		const E &e = edge(*it);

		if (e.otherVertex(vIdx1) == vIdx2 && n-- == 0)

			break;

	}

	return (it == incidingV1.end()) ? -1 : (*it);

}

//-------------------------------------------------------------------------

template <typename e,="" f="" typename="" v,=""></typename>

int Mesh<v, e,="" f="">::addEdge(const E &ed)</v,>

{

	int e = int(m_edges.push_back(ed));

	m_edges[e].setIndex(e);

	// Add the edge index to the edge's vertices

	typename edge_traits<e>::vertices_const_iterator it, end(ed.verticesEnd());</e>

	for (it = ed.verticesBegin(); it != end; ++it)

		m_vertices[*it].addEdge(e);

	return e;

}

//---------------------------------------------------------------------------------------------

template <typename e,="" f="" typename="" v,=""></typename>

int Mesh<v, e,="" f="">::addFace(const F &fc)</v,>

{

	int f = int(m_faces.push_back(fc));

	m_faces[f].setIndex(f);

	// Add the face index to the face's edges

	typename face_traits<f>::edges_const_iterator it, end = fc.edgesEnd();</f>

	for (it = fc.edgesBegin(); it != end; ++it)

		m_edges[*it].addFace(f);

	return f;

}

//---------------------------------------------------------------------------------------------

template <typename e,="" f="" typename="" v,=""></typename>

void Mesh<v, e,="" f="">::removeVertex(int v)</v,>

{

	V &vx = vertex(v);

	// As long as there are incident edges, remove them

	while (vx.edgesCount() > 0)

		removeEdge(vx.edges().front());

	m_vertices.erase(v);

}

//---------------------------------------------------------------------------------------------

template <typename e,="" f="" typename="" v,=""></typename>

void Mesh<v, e,="" f="">::removeEdge(int e)</v,>

{

	E &ed = edge(e);

	// Remove all the associated faces

	typename edge_traits<e>::faces_iterator ft;</e>

	while ((ft = ed.facesBegin()) != ed.facesEnd()) // current iterator could be erased here!

		removeFace(*ft);

	// Remove the edge from the associated vertices

	typename edge_traits<e>::vertices_iterator vt, vEnd = ed.verticesEnd();</e>

	for (vt = ed.verticesBegin(); vt != vEnd; ++vt) {

		V &vx = vertex(*vt);

		typename vertex_traits<v>::edges_iterator et = std::find(vx.edgesBegin(), vx.edgesEnd(), e);</v>

		assert(et != vx.edgesEnd());

		vx.eraseEdge(et);

	}

	m_edges.erase(e);

}

//---------------------------------------------------------------------------------------------

template <typename e,="" f="" typename="" v,=""></typename>

void Mesh<v, e,="" f="">::removeFace(int f)</v,>

{

	F &fc = face(f);

	// Remove the face from all adjacent edges

	typename face_traits<f>::edges_iterator et, eEnd = fc.edgesEnd();</f>

	for (et = fc.edgesBegin(); et != eEnd; ++et) {

		E &ed = edge(*et);

		typename edge_traits<e>::faces_iterator ft = std::find(ed.facesBegin(), ed.facesEnd(), f);</e>

		assert(ft != ed.facesEnd());

		ed.eraseFace(ft);

	}

	m_faces.erase(f);

}

//---------------------------------------------------------------------------------------------

/*!

  \brief    Remaps the mesh indices in a natural order, removing unused cells in the internal

            container model, for minimum memory consumption.

  \warning  This is a slow operation, compared to all the others in the Mesh class.

*/

template <typename e,="" f="" typename="" v,=""></typename>

void Mesh<v, e,="" f="">::squeeze()</v,>

{

	// Build new indices for remapping.

	typename tcg::list<f>::iterator it, endI(m_faces.end());</f>

	int i;

	for (i = 0, it = m_faces.begin(); it != endI; ++i, ++it)

		it->setIndex(i);

	typename tcg::list<e>::iterator jt, endJ(m_edges.end());</e>

	for (i = 0, jt = m_edges.begin(); jt != endJ; ++i, ++jt)

		jt->setIndex(i);

	typename tcg::list<v>::iterator kt, endK(m_vertices.end());</v>

	for (i = 0, kt = m_vertices.begin(); kt != endK; ++i, ++kt)

		kt->setIndex(i);

	// Update stored indices

	for (it = m_faces.begin(); it != endI; ++it) {

		F &face = *it;

		typename face_traits<f>::edges_iterator et, eEnd = face.edgesEnd();</f>

		for (et = face.edgesBegin(); et != eEnd; ++et)

			*et = edge(*et).getIndex();

	}

	for (jt = m_edges.begin(); jt != endJ; ++jt) {

		E &edge = *jt;

		typename edge_traits<e>::vertices_iterator vt, vEnd = edge.verticesEnd();</e>

		for (vt = edge.verticesBegin(); vt != vEnd; ++vt)

			*vt = vertex(*vt).getIndex();

		typename edge_traits<e>::faces_iterator ft, fEnd = edge.facesEnd();</e>

		for (ft = edge.facesBegin(); ft != fEnd; ++ft)

			*ft = face(*ft).getIndex();

	}

	tcg::list<int>::iterator lt;</int>

	for (kt = m_vertices.begin(); kt != endK; ++kt) {

		V &vertex = *kt;

		typename vertex_traits<v>::edges_iterator et, eEnd = vertex.edgesEnd();</v>

		for (et = vertex.edgesBegin(); et != eEnd; ++et)

			*et = edge(*et).getIndex();

	}

	// Finally, rebuild the actual containers

	if (!m_faces.empty()) {

		tcg::list<f> temp(m_faces.begin(), m_faces.end());</f>

		std::swap(m_faces, temp);

	}

	if (!m_edges.empty()) {

		tcg::list<e> temp(m_edges.begin(), m_edges.end());</e>

		std::swap(m_edges, temp);

	}

	if (!m_vertices.empty()) {

		tcg::list<v> temp(m_vertices.begin(), m_vertices.end());</v>

		std::swap(m_vertices, temp);

	}

}

//************************************************************************

//    Triangular Mesh methods

//************************************************************************

template <typename e,="" f="" typename="" v,=""></typename>

TriMesh<v, e,="" f="">::TriMesh(int verticesHint)</v,>

{

	int edgesHint = (3 * verticesHint) / 2;

	m_vertices.reserve(verticesHint);

	m_edges.reserve(edgesHint);

	m_faces.reserve(edgesHint + 1); // Since V - E + F = 1 for planar graphs (no outer face), and vMin == 0

}

//---------------------------------------------------------------------------------------------

template <typename e,="" f="" typename="" v,=""></typename>

int TriMesh<v, e,="" f="">::addFace(V &vx1, V &vx2, V &vx3)</v,>

{

	int v1 = vx1.getIndex(), v2 = vx2.getIndex(), v3 = vx3.getIndex();

	// Retrieve the edges having v1, v2, v3 in common

	int e1, e2, e3;

	e1 = this->edgeInciding(v1, v2);

	e2 = this->edgeInciding(v2, v3);

	e3 = this->edgeInciding(v3, v1);

	if (e1 < 0)

		e1 = this->addEdge(E(v1, v2));

	if (e2 < 0)

		e2 = this->addEdge(E(v2, v3));

	if (e3 < 0)

		e3 = this->addEdge(E(v3, v1));

	F fc;

	fc.addEdge(e1), fc.addEdge(e2), fc.addEdge(e3);

	int f = int(m_faces.push_back(fc));

	m_faces[f].setIndex(f);

	E &E1 = this->edge(e1);

	E1.addFace(f);

	E &E2 = this->edge(e2);

	E2.addFace(f);

	E &E3 = this->edge(e3);

	E3.addFace(f);

	return f;

}

//---------------------------------------------------------------------------------------------

template <typename e,="" f="" typename="" v,=""></typename>

int TriMesh<v, e,="" f="">::otherFaceVertex(int f, int e) const</v,>

{

	const F &face = Mesh<v, e,="" f="">::face(f);</v,>

	const E &otherEdge = face.edge(0) == e ? this->edge(face.edge(1)) : this->edge(face.edge(0));

	int v1 = this->edge(e).vertex(0), v2 = this->edge(e).vertex(1), v3 = otherEdge.otherVertex(v1);

	return (v3 == v2) ? otherEdge.otherVertex(v2) : v3;

}

//---------------------------------------------------------------------------------------------

template <typename e,="" f="" typename="" v,=""></typename>

int TriMesh<v, e,="" f="">::otherFaceEdge(int f, int v) const</v,>

{

	const F &face = Mesh<v, e,="" f="">::face(f);</v,>

	{

		const E &ed = this->edge(face.edge(0));

		if (ed.vertex(0) != v && ed.vertex(1) != v)

			return face.edge(0);

	}

	{

		const E &ed = this->edge(face.edge(1));

		if (ed.vertex(0) != v && ed.vertex(1) != v)

			return face.edge(1);

	}

	return face.edge(2);

}

//---------------------------------------------------------------------------------------------

template <typename e,="" f="" typename="" v,=""></typename>

int TriMesh<v, e,="" f="">::swapEdge(int e)</v,>

{

	E &ed = this->edge(e);

	if (ed.facesCount() < 2)

		return -1;

	int f1 = ed.face(0), f2 = ed.face(1);

	//Retrieve the 2 vertices not belonging to e in the adjacent faces

	int v1 = ed.vertex(0), v2 = ed.vertex(1);

	int v3 = otherFaceVertex(f1, e), v4 = otherFaceVertex(f2, e);

	assert(this->edgeInciding(v3, v4) < 0);

	//Remove e

	this->removeEdge(e);

	//Insert the new faces

	addFace(v1, v3, v4); // Inserts edge E(v3, v4)

	addFace(v2, v4, v3);

	return this->edgeInciding(v3, v4);

}

//---------------------------------------------------------------------------------------------

/*

    *---*---*     Common case          *          FORBIDDEN case:

   / \ / x / \                        /|\           note that the collapsed edge

  *---*-x-X---*                      /_*_\          have 3 (possibly more) other vertices

   \ / \ x \ /                      *--X--*         with edges inciding both the collapsed

    *---*---*                        \   /          edge's extremes.

                                      \ /

                                       *            This cannot be processed, since the

                                                    unexpected merged edge would either have

                                                    more than 2 adjacent faces, or a hole.

*/

template <typename e,="" f="" typename="" v,=""></typename>

int TriMesh<v, e,="" f="">::collapseEdge(int e)</v,>

{

	E &ed = this->edge(e);

	// First, retrieve ed's adjacent vertices

	int vKeep = ed.vertex(0), vDelete = ed.vertex(1);

	V &vxKeep = this->vertex(vKeep), &vxDelete = this->vertex(vDelete);

	// Then, retrieve the 2 vertices not belonging to e in the adjacent faces

	int f, fCount = ed.facesCount();

	int otherV[2];

	for (f = 0; f != fCount; ++f)

		otherV[f] = otherFaceVertex(ed.face(f), e);

	// Remove e

	this->removeEdge(e);

	// Merge edges inciding vDelete and otherV with the corresponding inciding vKeep and otherV

	for (f = 0; f != fCount; ++f) {

		int srcE = this->edgeInciding(vDelete, otherV[f]),

			dstE = this->edgeInciding(vKeep, otherV[f]);

		E &srcEd = this->edge(srcE),

		  &dstEd = this->edge(dstE);

		typename edge_traits<e>::faces_iterator ft = srcEd.facesBegin();</e>

		while (ft != srcEd.facesEnd()) // current iterator will be erased

		{

			F &fc = this->face(*ft);

			(fc.edge(0) == srcE) ? fc.setEdge(0, dstE) : (fc.edge(1) == srcE) ? fc.setEdge(1, dstE) : fc.setEdge(2, dstE);

			dstEd.addFace(*ft);

			ft = srcEd.eraseFace(ft); // here

		}

		this->removeEdge(srcE);

	}

	// Move further edges adjacent to vDelete to vKeep

	typename vertex_traits<v>::edges_iterator et = vxDelete.edgesBegin();</v>

	while (et != vxDelete.edgesEnd()) // current iterator will be erased

	{

		E &ed = this->edge(*et);

// Ensure that there is no remaining edge which would be duplicated

// after vDelete and vKeep merge

/* FIXME: edgeInciding がないと言われるのでとりあえず省略 */

#if 0

    assert("Detected vertex adjacent to collapsed edge's endpoints, but not to its faces." &&

           edgeInciding(ed.otherVertex(vDelete), vKeep) < 0);

#endif

		(ed.vertex(0) == vDelete) ? ed.setVertex(0, vKeep) : ed.setVertex(1, vKeep);

		vxKeep.addEdge(*et);

		et = vxDelete.eraseEdge(et); // here

	}

	// Finally, update vKeep's position and remove vDelete

	vxKeep.P() = 0.5 * (vxKeep.P() + vxDelete.P());

	m_vertices.erase(vDelete);

	return vKeep;

}

//---------------------------------------------------------------------------------------------

template <typename e,="" f="" typename="" v,=""></typename>

int TriMesh<v, e,="" f="">::splitEdge(int e)</v,>

{

	E &ed = this->edge(e);

	// Build a new vertex on the middle of e

	int v1 = ed.vertex(0), v2 = ed.vertex(1);

	V &vx1 = this->vertex(v1), &vx2 = this->vertex(v2);

	V v(0.5 * (vx1.P() + vx2.P()));

	int vIdx = this->addVertex(v);

	// Retrieve opposite vertices

	int otherV[2];					 // NOTE: If ever extended to support edges with

	int f, fCount = ed.facesCount(); //       MORE than 2 adjacent faces, the new faces

									 //       should be inserted BEFORE removing the split

	for (f = 0; f != fCount; ++f)	//       edge.

		otherV[f] = otherFaceVertex(ed.face(f), e);

	// Remove e

	this->removeEdge(e);

	// Add the new edges

	this->addEdge(E(v1, vIdx));

	this->addEdge(E(vIdx, v2));

	// Add the new faces

	for (f = 0; f != fCount; ++f)

		addFace(v1, vIdx, otherV[f]), addFace(vIdx, v2, otherV[f]);

	return vIdx;

}

} //namespace tcg

#endif //TCG_MESH_HPP