// GlutExamples.cpp: определяет точку входа для консольного приложения.
//

#include  <stdlib.h>
#define _USE_MATH_DEFINES
#include  <math.h>
#include  <time.h>
#include  <string.h>
#include "gl/freeglut.h"

#pragma comment(lib, "freeglut.lib")
#include <vector>
#include <queue>
#include <iostream>
#include <fstream>
#include <string>
#include <iomanip>
using namespace std;
const int NV = 5;
struct edge {
	int start;
	int finish;
	int weight;
};

class Graph {
	int V; // Кількість вершин
	std::vector<std::vector<int>> adj; // Вектор списків суміжності
	std::vector<pair<int, int>> coords;
	std::vector<edge> edges;
	double** weights; //pointer to create weight matrix
	double* smallestWeight; //pointer to create the array to
	//store the smallest weight from
	//source to vertices
public:
	Graph(int V) : V(V), adj(V) {
		weights = new double* [V];
		for (int i = 0; i < V; i++)
			weights[i] = new double[V];
		smallestWeight = new double[V];
	}
	~Graph() {
		delete[] smallestWeight;
		for (int i = 0; i < V; i++)
			delete[] weights[i];
		delete[] weights;
	}

	// Додавання ребра (для неорієнтованого графу)
	void addEdge(int u, int v, int w) {
		adj[u].push_back(v);
		//adj[v].push_back(u);
		edge e;
		e.start = u; e.finish = v; e.weight=w;
		edges.push_back(e);
		//e.start = v; e.finish = u; e.weight=w;
		//edges.push_back(e);
	}
	void Load(const char* fn);

	void print() {
		for (int i = 0; i < V; ++i) {
			std::cout << i << ": ";
			for (int neighbor : adj[i]) std::cout << neighbor << " ";
			std::cout << "\n";
		}
	}
	void display();
	void dft(int v, bool visited[]);
	void bft();
	void shortestPath(int vertex);
	void printShortestDistance(int vertex);
};
void Graph::Load(const char* fn) {
	string s;	
	adj.clear();
	ifstream f(fn);
	int nv, ne, w;
	int i1, i2, i0;
	int x, y;
	f >> nv >> ne;
	getline(f, s);
	for (int i = 0; i < nv; i++) {
		f >> x >> y;
		getline(f, s);
		vector<int> v;
		adj.push_back(v);
		coords.push_back(pair<int,int>(x,y));
	}
	for (int i = 0; i < V; i++) {
		for (int j = 0; j < V; j++) {
			weights[i][j] = DBL_MAX;
		}
		weights[i][i] = 0;
	}
	for (int i = 0; i < ne; i++) {
		f >> i1 >> i2 >> w;
		getline(f, s);
		addEdge(i1, i2, w);
		weights[i1][i2] = w;
	}
	f.close();
}
void circle(double x0, double y0, double R);
void displayText(float x, float y, char* s);
void Graph::display()
{
	char buf[10];
	double R = 20;
	glColor3ub(255, 255, 255);
	/*
	for (int i = 0; i < adj.size(); i++) {
		for (int j = 0; j < adj[i].size(); j++) {
			//draw edge (i,j)
			glBegin(GL_LINES);
			glVertex2d(coords[i].first, coords[i].second);
			glVertex2d(coords[adj[i][j]].first, coords[adj[i][j]].second);
			glEnd();
		}
	}*/
	for (auto &e : edges) {
		glBegin(GL_LINES);
		glVertex2d(coords[e.start].first, coords[e.start].second);
		glVertex2d(coords[e.finish].first, coords[e.finish].second);
		glEnd();
		_itoa_s(e.weight, buf, 9, 10);
		displayText((coords[e.start].first+ coords[e.finish].first)/2, 
			(coords[e.start].second + coords[e.finish].second) / 2, buf);
	}
	for (int i = 0; i < coords.size(); i++) {
		glColor3ub(255, 255, 255);
		circle(coords[i].first, coords[i].second, R);
		glColor3ub(255, 0, 0);
		_itoa_s(i, buf, 9, 10);
		displayText(coords[i].first-8, coords[i].second-10, buf);
	}

}


void Graph::dft(int v, bool visited[])
{
	visited[v] = true;
	cout << " " << v << " "; //visit the vertex
	vector<int>::iterator it;
	//for each vertex adjacent to v
	for (it = adj[v].begin(); it != adj[v].end(); ++it)
	{
		int w = *it;
		if (!visited[w])
			dft(w, visited);
	} //end while
} //end

void Graph::bft()
{
	queue<int> queue;
	bool* visited;
	visited = new bool[V];
	for (int ind = 0; ind < V; ind++)
		visited[ind] = false; //initialize the array
	//visited to false
	//queue<int>::iterator *graphIt;
	vector<int>::iterator it;
	for (int index = 0; index < V; index++)
		if (!visited[index])
		{
			queue.push(index);
			visited[index] = true;
			cout << " " << index << " ";
			while (!queue.empty())
			{
				int u = queue.front();
				queue.pop();
				for (it = adj[u].begin();
					it != adj[u].end(); ++it)
				{
					int w = *it;
					if (!visited[w])
					{
						queue.push(w);
						visited[w] = true;
						cout << " " << w << " ";
					}
				}
			} //end while
		}
	delete[] visited;
} //end breadthFirstTraversal

void Graph::shortestPath(int vertex)
{
	for (int j = 0; j < V; j++)
		smallestWeight[j] = weights[vertex][j];
	bool* weightFound;
	weightFound = new bool[V];
	for (int j = 0; j < V; j++)
		weightFound[j] = false;
	weightFound[vertex] = true;
	smallestWeight[vertex] = 0;
	for (int i = 0; i < V - 1; i++)
	{
		double minWeight = DBL_MAX;
		int v;
		for (int j = 0; j < V; j++)
			if (!weightFound[j])
				if (smallestWeight[j] < minWeight)
				{
					v = j;
					minWeight = smallestWeight[v];
				}
		weightFound[v] = true;
		for (int j = 0; j < V; j++)
			if (!weightFound[j])
				if (minWeight + weights[v][j] < smallestWeight[j])
					smallestWeight[j] = minWeight + weights[v][j];
	} //end for
	for (int i = 0; i < V; i++)
		cout << smallestWeight[i]<<' ';
	cout << endl;
}
void Graph::printShortestDistance(int vertex)
{
	cout << "Source Vertex: " << vertex << endl;
	cout << "Shortest Distance from Source to each Vertex."
		<< endl;
	cout << "Vertex Shortest_Distance" << endl;
	for (int j = 0; j < V; j++)
		cout << setw(4) << j << setw(12) << smallestWeight[j]
		<< endl;
	cout << endl;
} //end printShortestDistance

int xx, yy, cc;
int ButtonStatus = 0;
//double* sizes;  // Масив діапазону розмірів точок
//double* step;     // Масив кроків зростання розмірів

double* a;
int N = 0;
int Ncur = -1;//зхвачена точка

Graph g(NV);
bool visited[NV];

void init()
{
	glViewport(0, 0, 500, 500);//встановлює розміри області відображення
	glClearColor(0.0f, 0.0f, 0.0f, 0.0f);
	glMatrixMode(GL_PROJECTION);//Задає режим проектування - ортографічна проекція
	glLoadIdentity();//Ініціалізація матриць проектування одиничними матрицями
	glOrtho(-20.0, 480.0, -20.0, 480.0, -250.0, 250.0);  //Задає параметри проектування (систему координат)
	glMatrixMode(GL_MODELVIEW);
}
void displayText(float x, float y, char* s) {
	int j = strlen(s);
	glRasterPos2f(x, y);
	for (int i = 0; i < j; i++) {
		glutBitmapCharacter(GLUT_BITMAP_TIMES_ROMAN_24, s[i]);
	}
}
void circle(double R);
void display()
{
	char buf[80];

	glClear(GL_COLOR_BUFFER_BIT);
	glLoadIdentity();
	glEnable(GL_POINT_SMOOTH);//точки згладженні. (якщо Disable - то квадратні)

	// Отримання діапазону розмірів точок та кроків зростання
	//glGetDoublev(GL_POINT_SIZE_RANGE, sizes);
	//glGetDoublev(GL_POINT_SIZE_GRANULARITY, step);

	//Формування графічної інформації
	/*
	for (int i = 1; i <= N; i++)
	{
		xx = (int)a[3 * i];
		yy = (int)a[3 * i + 1];
		cc = (int)a[3 * i + 2];
		glPointSize(cc);

		//Малювання примітивів
		glBegin(GL_POINTS);//Інші режими: GL_LINES, GL_LINE_STRIP, GL_LINE_LOOP, GL_TRIANGLES, GL_TRIANGLE_STRIP, GL_TRIANGLE_FAN, GL_QUADS, GL_QUAD_STRIP, GL_POLYGON 
		glVertex3f(xx, yy,0);// Вершина примітиву. В данному разі - точка.
		glEnd();
		_itoa_s(i, buf, 80, 10);
		displayText(xx + 16, yy + 20, buf);
	}

	//Задання кольору, розміру точки та формування точки
	glColor3ub(128, 0, 255);
	glPointSize(10);
	glBegin(GL_POINTS);
	glVertex2d(a[0], a[1]);
	glEnd();
	glColor3ub(255, 255, 255);
	
	circle(150);
	
	GLfloat BlueColor[3] = { 0,0,1 };
	glBegin(GL_TRIANGLES); 
	glColor3f(1.0, 0.0, 0.0);//червоний
	glVertex3f(0.0, 0.0, 0.0); 
	glColor3ub(0, 255, 0);  // зелений 
	glVertex3f(100.0, 0.0, 0.0); 
	glColor3fv(BlueColor); //синій 
	glVertex3f(100.0, 100.0, 0.0);
	glEnd();
	
	glRotated(30, 1, 0, 0);
	glRotated(15, 0, 1, 0);
	glScaled(10, 10, 10);
	glTranslated(10, 0, 0);
	glPushMatrix();
	glLoadIdentity();
	glPopMatrix();
	glBegin(GL_LINES);
	glColor3ub(255, 0, 0);//червоний
	glVertex3f(0.0, 0.0, 0.0);
	glVertex3f(100.0, 0.0, 0.0);
	glColor3ub(0, 255, 0);
	glVertex3f(0.0, 0.0, 0.0);
	glVertex3f(0.0, 100.0, 0.0);
	glColor3ub(0, 0, 255);
	glVertex3f(0.0, 0.0, 0.0);
	glVertex3f(0.0, 0.0, 100.0);
	glEnd();
	*/
	g.display();
	glFlush();
	//glutSwapBuffers();//Зміна графічних сторінок (корисно при анімації - проти "миготіння")
}

bool isin(int x, int y, int& n)
{
	n = -1;
	double eps = 10.0;
	for (int i = 0; i < N; i++)
		if (sqrt(((double)x - a[3 * i]) * (x - a[3 * i]) + (y - a[3 * i + 1]) * (y - a[3 * i + 1])) < eps)
		{
			n = i;
			return true;
		}
	return false;
}
void mouse(int button, int state, int x, int y)
{
	int n = -1;//індекс точки
	//Random r = new Random();
	srand(time(0));
	switch (button)
	{
	case GLUT_RIGHT_BUTTON:
		if (state == GLUT_DOWN)
		{
			//glutIdleFunc(spinDisplay); 
		}
		break;
	case GLUT_MIDDLE_BUTTON:
		if (state == GLUT_DOWN)
		{
			//glutIdleFunc(NULL); 
		}
		break;
	case GLUT_LEFT_BUTTON:
		if (state == GLUT_DOWN)
		{
			xx = x - 250;//Зв'язок координат миші та координат Opengl
			yy = 500 - y - 250;
			if (!isin(xx, yy, n))
			{
				//Нова точка
				cc = 1;// rand() % (int)sizes[1] + 1;
				N++;
				a[3 * N] = (double)xx;
				a[3 * N + 1] = (double)yy;
				a[3 * N + 2] = cc;
				glutPostRedisplay();
			}
			else
			{
				//Зхвачено вже існуючу точку
				ButtonStatus = 1;
				Ncur = n;
				//Поновлюємо координати
				a[3 * n] = (double)xx;
				a[3 * n + 1] = (double)yy;

			}
		}
		else
			if (state == GLUT_UP)
			{
				//Перетаскування завершено
				ButtonStatus = -1;
			}
		break;
	default:
		break;
	}
}
void MouseMotion(int x, int y)
{
	if (ButtonStatus == 1)
	{
		int xx, yy;
		xx = x - 250;//Зв'язок координат миші та координат Opengl
		yy = 500 - y - 250;
		a[3 * Ncur] = (double)xx;
		a[3 * Ncur + 1] = (double)yy;
		glutPostRedisplay();
	}
}
void keyb(unsigned char key, int x, int y)
{
	const unsigned char esc = 27;
	if (key == esc)
		exit(0);
	if (key == '1') {
		for (int i = 0; i < NV; i++)
			visited[i] = false;
		g.dft(0, visited);
	}
	if (key == '2') {
		g.bft();
	}
	if (key == '6') {
		g.shortestPath(0);
		g.printShortestDistance(0);
	}
}

void reshape(int w, int h)
{
	glViewport(0, 0, w, h);
	glMatrixMode(GL_PROJECTION);
	glLoadIdentity();
	glOrtho(-20.0, 480.0, -20.0, 480.0, -250.0, 250.0);
	glMatrixMode(GL_MODELVIEW);
	glLoadIdentity();
}
void circle(double x0, double y0, double R) {
	glBegin(GL_POLYGON);
	for (int i = 0; i < 360; i++) {
		double x =x0+ R * cos((double)i / 180.0 * M_PI);
		double y =y0+ R * sin((double)i / 180.0 * M_PI);
		glVertex2d(x,y);
	}
	glEnd();
}

int main(int argc, char* argv[])
{

	//Graph g({{0,1},{1,2},{2,3},{3,4},{4,0}});
	//Graph g(5);
	g.Load("graph4.txt");

	//sizes = new double[2];  // Масив діапазону розмірів точок
	//step = new double[2];     // Масив кроків зростання розмірів
	a = new double[900];

	xx = 0; yy = 0; cc = 10;
	a[0] = 0; a[1] = 0; a[2] = 0;

	glutInit(&argc, argv);//ініціалізує бібліотеку GLUT

	glutInitDisplayMode(GLUT_SINGLE | GLUT_RGB);
	/* визначає, яку колірну модель слід використовувати: режим RGBA або режим індексації кольору.
	* Можна також визначити, чи прагнете ви працювати з буфером кадру вікна з одинарної або з подвійний буферизацією.
	* (Якщо ви працюєте в режимі індексації кольору, то ви, можливо, захочете завантажити деякі кольори в
	* таблицю компонентів кольору; для того щоб зробити це, скористайтеся командою glutSetColor().)
	* Нарешті, можна використовувати цю функцію для того, щоб вказати, що ви прагнете зв'язати з даним вікном
	* буфери глибини, трафарету й/або буфер-накопичувач. Наприклад, якщо ви бажаєте використовувати вікно з
	* подвійною буферизацією, колірною моделлю RGBA і буфером глибини, то для цього можна викликати розглянуту
	* функцію з наступними параметрами:
	* glutInitDisplayMode(GLUT_DOUBLE | GLUT_RGB | GLUT_DEPTH).*/


	glutInitWindowSize(500, 500);//визначає розмір створюваного вікна в пікселях.
	glutInitWindowPosition(100, 100);//визначає місце розташування лівого верхнього кута створюваного вікна на екрані монітора.

	glutCreateWindow("hello");
	/* створює вікно з контекстом open Ця підпрограма повертає унікальний ідентифікатор для нового вікна.
	* Майте на увазі: доти, поки викликається підпрограма glutMainLoop(), це вікно ще не відображається на екрані.*/

	init();

	glutDisplayFunc(display);
	/* являє собою першу й найбільш важливу функцію зворотного виклику за подією.
	* Щоразу, коли бібліотека GLUT визначає, що вміст даного вікна має бути поновлений,
	* виконується функція зворотного виклику, зареєстрована підпрограмою glutDisplayFunc().
	* Тому ви повинні помістити всі підпрограми, які необхідні для перемальовування сцени,
	* у дану функцію зворотного виклику відображення.
	* Якщо ваша програма змінює вміст вікна, то іноді ви маєте викликати підпрограму glutPostRedisplay(void),
	* яка змушує підпрограму glutMainLoop() викликати зареєстровану функцію зворотного виклику відображення
	* при наступному зручному випадку
	*/

	glutReshapeFunc(reshape);//вказує на те, яке саме дія повинна бути виконана при зміні розміру вікна

	glutMouseFunc(mouse);//реєструє функцію, яка буде реагувати на події, що пов'язані з мишкою
	glutMotionFunc(MouseMotion);
	glutKeyboardFunc(keyb);//реєструє функцію, яка буде реагувати на події, що пов'язані з клавіатурою

	//glutIdleFunc(display);//реєструє функцію, що буде виконуватися постійно (у фоні)

	glutMainLoop();
	/* При цьому відображаються всі вікна, які були створені, і в цих вікнах тепер працює візуалізація.
	* Починається обробка подій, і викликається зареєстрована функція зворотного виклику відображення.
	* Увійшовши одного разу в цей цикл, з нього не виходять ніколи!*/

	return 0;
}