//////////////////////////////////////////////////////////////////////////////////////////////
// 
// Delaunay triangulation 
// 
//////////////////////////////////////////////////////////////////////////////////////////////
//#ifdef WIN32
#include <windows.h>
//#endif
#include <GL/freeglut.h>

#include <iterator>
#include <list>
#include <vector>
#include <algorithm>
#include <functional>
#include <string>
#include <iostream>
#include <fstream>
#include <set>


#define VMATH_NAMESPACE vam
#include "vmath.h"
#include "structs.h"
#include "utils.h"
#include "mytime.h"






using namespace std;

namespace vam
{




	/**
	 * Application class
	 */
	class Application
	{
		list<Triangle*> triangles;

		int level;
	public:
		Vector2f aabbMin, aabbMax;

		Application()
		{
			level = 0;
		}
		~Application()
		{
			for (list<Triangle*>::iterator it = triangles.begin(); it != triangles.end(); it++)
			{
				Triangle* t = *it;
				delete t;
			}
		}

		void reportTriangles(list<Triangle*>& tris) const
		{
			for (list<Triangle*>::iterator it = tris.begin(); it != tris.end(); it++)
			{
				cerr << *it << " ";
			}
			cerr << endl;
		}

		void initUniform(unsigned n)
		{
			points.clear();
			generate_n(back_insert_iterator< vector<Vector2f> >(points), n, UniformPointGenerator(100));
		}

		void initGaussian(unsigned n)
		{
			points.clear();

			Vector2f mean(0,0);

			generate_n(back_insert_iterator< vector<Vector2f> >(points), n, GausianPointGenerator(mean.x, mean.y, 25));

		}

		void handleEdge(set<Edge>& edges, int v1, int v2)
		{
			Edge e(v1,v2);
			set<Edge>::iterator it = edges.find(e);
			if (it == edges.end())
			{
				edges.insert(e);
			}
			else
			{
				edges.erase(it);
			}
		}

		void triangulate()
		{
			triangles.clear();

			unsigned n = points.size();
			
			aabbMin = aabbMax = points[0];

			for_each(points.begin(), points.end(), GetAABB(aabbMin, aabbMax));

			

			Vector2f v1 = aabbMin;
			float w = aabbMax.x - aabbMin.x;
			w *= 2;
			float h = aabbMax.y - aabbMin.y;
			h *= 2;
			Vector2f v2(aabbMin.x, h);
			Vector2f v3(w, aabbMin.y);
			/*Vector2f v1(-1000,-1000);
			Vector2f v2(1000,-1000);
			Vector2f v3(0,1000);*/
			points.push_back(v1);
			points.push_back(v2);
			points.push_back(v3);

			triangles.push_back(new Triangle(n, n+1,n+2));

			for (unsigned i = 0; i < n; i++)
			{
				Vector2f p = points[i];
				
				set<Edge> edges;

				list<Triangle*>::iterator it = triangles.begin();
				while (it != triangles.end())
				{
					list<Triangle*>::iterator tmpIt = it;
					tmpIt++;

					Triangle* t = *it;
					if (t->isInCircle(p))
					{
						handleEdge(edges, t->v[0], t->v[1]);
						handleEdge(edges, t->v[1], t->v[2]);
						handleEdge(edges, t->v[2], t->v[0]);
						
						triangles.erase(it);
						delete t;
					}

					it = tmpIt;
				}

				for (set<Edge>::iterator it = edges.begin(); it != edges.end(); it++)
				{
					const Edge& e = *it;
					triangles.push_back(new Triangle(e.v[0], e.v[1], i));
				}
				edges.clear();
			}

			// remove super triangle
			list<Triangle*>::iterator newEnd = remove_if(triangles.begin(), triangles.end(), ContainsSuperTriangle(n));
			triangles.erase(newEnd, triangles.end());
			points.erase(points.begin() + n, points.end());
			for_each(triangles.begin(), triangles.end(), ForceCCW());
		}

		void bTriangulate()
		{
			unsigned n = points.size();
			cout << n << endl;
			for (unsigned i = 0; i < n-2; i++)
			{
				for (unsigned j = i + 1; j < n - 1; j++)
				{
					for (unsigned k = j + 1; k < n; k++)
					{
						bool pointFree = true;
						Circle c = Circle::fromTriangle(points[i], points[j], points[k]);
						for (unsigned l = 0; l < n; l++)
						{
							if (l != i && l != j && l != k)
							{
								if (c.isPointInside(points[l]))
								{
									pointFree = false;
									break;
								}
							}
						}
						if (pointFree)
						{
							triangles.push_back(new Triangle(i,j,k));
						}

					}
				}
			}

		}

		void draw()
		{
			glColor3f(0.5, 0.5, 0.5);
			for (list<Triangle*>::iterator it = triangles.begin(); it != triangles.end(); it++)
			{
				const Triangle* t = *it;
				t->draw();
			}
			glColor3f(1,1,0);
			glPointSize(2);
			glBegin(GL_POINTS);
			for (unsigned i = 0; i < points.size(); i++)
			{
				glVertex2fv(points[i]);
			}
			glEnd();
		}

		void nextLevel()
		{
			level++;
			if ((unsigned)level < points.size())
			{
				triangulate();
			}
		}


		friend ostream& operator<<(ostream& ostr, Application& app)
		{
			ostr << points.size() << endl;
			copy(points.begin(), points.end(), ostream_iterator<Vector2f>(ostr, "\n"));
			ostr << app.triangles.size() << endl;
			copy(app.triangles.begin(), app.triangles.end(), ostream_iterator<Triangle*>(ostr, "\n"));

			return ostr;
		}

		friend istream& operator>>(istream& istr, Application& app)
		{
			unsigned n;
			istr >> n;
			for (unsigned i = 0; i < n; i++)
			{
				float x,y;
				istr >> x >> y;
				points.push_back(Vector2f(x,y));
			}

			return istr;
		}

	};

}

vam::Application app;

void render()
{
	//cerr << "Render" << endl << flush;
	glClear(GL_COLOR_BUFFER_BIT | GL_DEPTH_BUFFER_BIT);
	app.draw();
	glutSwapBuffers();
	//cerr << glGetError() << endl;
}

void reshape(int w, int h)
{
	glMatrixMode(GL_PROJECTION);
	glLoadIdentity();
	glViewport(0,0,w,h);
	//glOrtho(-100, 100, -100, 100, 0.01, 1000);
	glOrtho(app.aabbMin.x, app.aabbMax.x, app.aabbMin.y, app.aabbMax.y, 0.01, 1000);
	glMatrixMode(GL_MODELVIEW);
	glLoadIdentity();
	gluLookAt(0,0,250, 0,0,0, 0,1,0);
}

void keyPressed(unsigned char ch, int x, int y)
{
	if (ch == ' ')
	{
		app.nextLevel();
		render();
	}
}

int main(int argc, char** argv)
{
	//app.initUniform(5000);
	bool ok = false;
	if (argc > 1)
	{
		ifstream fp(argv[1], ios::in);
		if (fp.good())
		{
			fp >> app;
			ok = true;
		}
		fp.close();
	}

	if (!ok) app.initGaussian(5000);
	//app.bTriangulate();
	double startTime = vam::myTime();
	app.triangulate();
	double endTime = vam::myTime();

	cout << "Triangulation time: " << endTime - startTime << " seconds" << endl;


	ofstream fp("./out.dat", ios::out);
	fp << app;
	fp.close();
	//cout << app;

	glutInit(&argc,argv);
	glutInitDisplayMode(GLUT_DEPTH | GLUT_DOUBLE | GLUT_RGB);
	glutCreateWindow("VAM - Delaunay triangulation");
	glutDisplayFunc(render);
	glutReshapeFunc(reshape);
	glutKeyboardFunc(keyPressed);

	
	glutMainLoop();	return 0;
}

