#include <iostream>
#include <queue>
#include <fstream>
#include <string.h>
#include <sstream>
#include <cassert>
#include "gph_io.h"

bool includes(int* list, int n, int v) {
	for (int i = 0; i < n; i++) {
		if (list[i] == v) {
			return (true);
		}
	}
	return (false);
}

std::string* file_to_line_array(string filename, int length) {
	std::string line;
	std::string* lines = new std::string[length + 1];
	for (int i = 0; i < length; i++) {
		lines[i] = "";
	}
	ifstream myfile(filename);
	assert(myfile);
	int i = 0;
	while (getline(myfile, line)) {
		lines[i] = line;
		i++;
	};
	lines[i] = "_end";
	return (lines);
}

int find(std::string* lines, std::string line) {
	for (int i = 0; lines[i] != "_end"; i++) {
		if  (lines[i] == line) {
			return (i);
		}
	}
	return (-1);
}



//main functions

int find_distance(struct graph* g, int v1, int v2) {
	int* visited = new int[g->node_count];
	int* previous = new int[g->node_count];
	int length = 0;
	int distance = 1;
	bool abort = false;
	bool success = false;
	std::queue<int> queue;
	queue.push(v1);
	queue.push(-1);

	if (v1 == v2) {
		return (0);
	}
	if (g->nodes[index(queue.front())] == nullptr) {
		success = false;
		abort = true;
	}
	while (!queue.empty() && !abort) {
		if (queue.front() == -1) {
			queue.pop();
			if (queue.front() == -1 || queue.empty()) {
				distance--;
				abort = true;
			}
			distance++;
			queue.push(-1);
		}
		else {
			for (edge *t = g->nodes[index(queue.front())]; t != nullptr; t = t->next) {
				if (!includes(visited, length, t->target)) {
					queue.push(t->target);
					visited[length] = t->target;
					previous[index(t->target)] = queue.front();
					length++;
				}
				if (t->target == v2) {
					success = true;
					abort = true;
					cout << "found " << distance << endl;
				}
			}
			queue.pop();
		}
	}
	if (success == false) {
		cout << "there is no path" << endl;
		distance = -1;
	}
	else if (success == true) {
		cout << v2;
		for (int x = previous[index(v2)]; x != v1; x = previous[index(x)]) {
			cout << " < " << x;
		}
		cout << " < " << v1;
		cout << endl;
	}
	return (distance);
}

int find_maximum_distance(struct graph* g, int v1) {
	int* visited = new int[g->node_count];
	int length = 0;
	int distance = 0;
	bool abort = false;
	std::queue<int> queue;
	queue.push(v1);
	queue.push(-1);

	if (g->nodes[index(queue.front())] == nullptr) {
		abort = true;
	}
	while (!queue.empty() && !abort) {
		if (queue.front() == -1) {
			queue.pop();
			if (queue.front() == -1 || queue.empty()) {
				distance--;
				abort = true;
			}
			distance++;
			queue.push(-1);
		}
		else {
			for (edge *t = g->nodes[index(queue.front())]; t != nullptr; t = t->next) {
				if (!includes(visited, length, t->target)) {
					queue.push(t->target);
					visited[length] = t->target;
					length++;
				}

			}
			queue.pop();
		}
	}
	return (distance);
}

int get_connected_size(struct graph* g, int v1) {
	int* visited = new int[g->node_count];
	visited[0] = v1;
	int length = 1;
	std::queue<int> queue;
	queue.push(v1);
	while (!queue.empty()) {
		for (edge *t = g->nodes[index(queue.front())]; t != nullptr; t = t->next) {
			if (!includes(visited, length, t->target)) {
				queue.push(t->target);
				visited[length] = t->target;
				length++;
			}
		}
		queue.pop();
	}
	return (length);
}
int* get_connected_component(struct graph* g, int v1) {
	int* visited = new int[g->node_count];
	visited[0] = v1;
	int length = 1;
	std::queue<int> queue;
	queue.push(v1);
	while (!queue.empty()) {
		for (edge *t = g->nodes[index(queue.front())]; t != nullptr; t = t->next) {
			if (!includes(visited, length, t->target)) {
				queue.push(t->target);
				visited[length] = t->target;
				length++;
			}
		}
		queue.pop();
	}
	return (visited);
}


void task_find_distance(struct graph* g) {
	std::string name1, name2;
	int v1, v2;
	std::string* legende = file_to_line_array("legende", g->node_count);
	cout << "enter the names: " << endl;
	std::getline(std::cin, name1);
	std::getline(std::cin, name2);
	v1 = find(legende, name1) + 1;
	v2 = find(legende, name2) + 1;
	cout << v1 << endl;
	if (v1 != -1 && v2 != -1) {
		cout << "the distance is: " << find_distance(g, v1, v2) << endl;
	}
	else {
		cout << "name not found" << endl;
	}
}
void task_check_connected(struct graph *g) {
	if (g->node_count == get_connected_size(g, 1)) {
		cout << "this graph is connected" << endl;
	}
	else {
		cout << "this graph is not connected" << endl;
	}
}

void task_find_diametre(struct graph* g) {
	int v;
	cout << "enter a vertex to specify the connected component: " << endl;
	cin >> v;
	int distance = 0;
	int maximum = 0;
	int size = get_connected_size(g, v);
	int* component = get_connected_component(g, v);

	for (int i = 0; i < size; i++)  {
		distance = find_maximum_distance(g, component[i]);
		if (distance > maximum) {
			maximum = distance;
		}
	}
	cout << "this connected component has diametre: " << distance << endl;
}
int main() {
	struct graph* erdos = read_edges_file("erdosgraph");

	task_find_distance(erdos);
	task_check_connected(erdos);
	task_find_diametre(erdos);
	return (0);
}