#include <stdio.h>
#include <iostream>
#include <string>
#include <sstream>
#include <fstream>
#include <cstring>
#include <climits>

#include <queue>
#include <list>
#include <map>

#include <thread>
#include <mutex>          // std::mutex

using namespace std;
using namespace std::chrono_literals;

#define INFINITY numeric_limits<int>::max()

struct struct_Node_ShortestPath {
	int shortestDistance;
	int prevPath;
	int prevPath_Weight;
	std::map<int, int> map_Edges;
};

std::mutex mutex_shortestPath;           // mutex for critical section

// A callable object 
class shortestPath {
private:
	int node_count = 0;

public:

	//std::mutex mutex_shortestPath;           // mutex for critical section

	std::map<int, struct_Node_ShortestPath> theMap;

	void readFile(string filename)
	{
		//Read graph's nodes connection from a file
		mutex_shortestPath.lock();

		std::ifstream inputfile(filename);
		node_count = 0;

		if (inputfile.is_open())
		{
			//Read from file,  save the nodes' edges record into 'Nodes_Edges_records'
			string sLine;
			while (getline(inputfile, sLine)) {
				vector<string> vectorStr;
				stringstream ss(sLine);
				string item;

				while (getline(ss, item, ' '))
				{
					vectorStr.push_back(item);
				}

				int tmpEdgesCount = 0;
				int tmp_Dest, tmp_Weight;
				struct_Node_ShortestPath tmp_struct_Node;
				for (auto i : vectorStr)
				{
					if (tmpEdgesCount % 2 == 0)
						tmp_Dest = stoi(i);
					else
					{
						tmp_Weight = stoi(i);
						tmp_struct_Node.map_Edges[tmp_Dest] = tmp_Weight;
					}

					tmpEdgesCount++;
				}

				theMap[node_count] = tmp_struct_Node;
				node_count++;
			}
			inputfile.close();
		}

		cout << "Read file completed." << endl;

		mutex_shortestPath.unlock();
	}

	void ShortestPathDerivation()
	{
		mutex_shortestPath.lock();

		//Graph initialize
		for (int i = 0; i < node_count; i++)
		{
			theMap[i].prevPath = -1;
			theMap[i].prevPath_Weight = -1;
			theMap[i].shortestDistance = INFINITY;
		}
		theMap[0].shortestDistance = 0;

		cout << "Graph initialize completed." << endl;

		//Shortest Path derivation
		std::list <int> list_Checklist;
		list_Checklist.push_back(0);

		int top = -1, sum = 0;
		while (!list_Checklist.empty()) {

			top = list_Checklist.front();
			list_Checklist.pop_front();

			for (std::pair<int, int> tmp_Edges : theMap[top].map_Edges) {
				sum = theMap[top].shortestDistance + tmp_Edges.second;
				if (theMap[tmp_Edges.first].shortestDistance > sum) {
					theMap[tmp_Edges.first].shortestDistance = sum;
					theMap[tmp_Edges.first].prevPath = top;
					theMap[tmp_Edges.first].prevPath_Weight = tmp_Edges.second;

					if (std::find(list_Checklist.begin(), list_Checklist.end(), tmp_Edges.first) == list_Checklist.end())
						list_Checklist.push_back(tmp_Edges.first);
				}
			}
		}
		cout << "Finish Shortest Path derivation" << endl;

		//Print shortest path to all nodes
		cout << endl;
		for (int i = 0; i < node_count; i++) {
			if (theMap[i].prevPath == -1)
				cout << "Shortest path from node \'0\' to node \'" << i << "\' is not yet being found\n";
			else {
				cout << "Shortest path from node \'0\' to node \'" << i << "\':\n"
					<< i << " --> ";
				int preRoute = theMap[i].prevPath;
				while (preRoute != -1) {
					cout << preRoute << " --> ";
					preRoute = theMap[preRoute].prevPath;
				}
				cout << "End\n";
			}

			cout << "Shortest distance is " << theMap[i].shortestDistance << "\n\n";
		}
		cout << endl;

		//Save Open Shortest Path First (OSPF) graph into file 'OSPF_info.txt'
		ofstream myfile;
		myfile.open("OSPF_info.txt");
		for (int i = 0; i < node_count; i++) {
			myfile << theMap[i].prevPath << " " << theMap[i].prevPath_Weight << "\n";
		}
		myfile.close();

		mutex_shortestPath.unlock();
	}
};

//Global class, mutex accesss by all.
shortestPath share_ShortestPath;

class myTimer2s
{
	std::thread::id this_id = std::this_thread::get_id();

public:
	void operator()(int x)
	{
		for (int i = 0; i < x; i++)
		{
			share_ShortestPath.ShortestPathDerivation();
			cout << "thread " << this_id << " sleeping...\n\n" << endl;
			std::this_thread::sleep_for(2s);
		}
	}
};

class myTimer1s
{
	std::thread::id this_id = std::this_thread::get_id();

public:
	void operator()(int x)
	{
		for (int i = 0; i < x; i++)
		{
			share_ShortestPath.readFile("graph3.txt");
			cout << "thread " << this_id << " sleeping...\n\n" << endl;
			std::this_thread::sleep_for(1s);
		}
	}
};

int main()
{
	// This thread is launched by using function object as callable 
	thread tm1s(myTimer1s(), 6);
	thread tm2s(myTimer2s(), 3);

	// Wait for thread tm1s to finish 
	tm1s.join();
	// Wait for thread tm2s to finish 
	tm2s.join();

	return 0;
}