#include <iostream>
#include <fstream>
#include <iterator>
#include <fstream>
#include <unordered_map>
#include <vector>
#include <list>
#include <string>
#include <sstream>
#include <queue>






std::vector<std::string> splitroute(char* arg){ //bör ha throw exception om första
    std::string argstr;
    int counter = 0;
    std::string route[2];
    std::vector<std::string> routevec;
    //std::cout << arg << " char*" << std::endl; //temp
    argstr = arg;
    //std::cout << argstr << " string" << std::endl; //temp
    for (int i=0; i<argstr.length(); i++){
        if (isalnum(argstr[i]) || isblank(argstr[i])){
            route[counter]+=argstr[i];
        }
        else if(argstr[i]=='>'){
            //std::cout << "Hit '>' in argstr" << std::endl;
            counter++;
        }
        else{
            //std::cout << "Hit '-' in argstr" << std::endl; //temp
        }
        }
        routevec.push_back(route[0]);
        routevec.push_back(route[1]);
        //std::cout << routevec[0] << " : " << routevec[1] << std::endl;

    return routevec;
}

bool is_undirected(std::string value){
    if(value == "UNDIRECTED"){
        return true;
    }
    else{
        return false;
    }

}

std::vector<std::string> get_townslist(std::vector<std::string> filecontent){
    std::vector<std::string> townslist;
    for(int i = 1; i < filecontent.size(); i++){
        if(filecontent[i] == ""){
            break;
        }
        else
        {
            townslist.push_back(filecontent[i]);
        }
    }
    return townslist;
}

bool is_route_in_townslist(std::vector<std::string>townslist, std::vector<std::string> route){ //THROW EXCEPTION???????
    int counter = 0;
    for(int j = 0; j < 2; j++){
        for(int i = 0; i < townslist.size();i++){
            if(route[j] == townslist[i])
                counter++;
    }
    }
    if(counter != 2){
        return false;
    }
    else if (counter == 2){
        return true;
    }
    return false;
}

std::vector<std::vector<std::string>> split_data(std::vector<std::string>datavector){
    std::vector<std::vector<std::string>> towndata;
    /*std::string currentdata;
    int count = 0;
    for(int i = 0; i < datavector.size(); i++){
        for(int j = 0; j < datavector[i].length(); j++){
            if(isalnum(datavector[i][j]) || isspace(datavector[i][j])){
                currentdata += datavector[i][j];
            }
            else if(datavector[i][j]=='\t'){
                lesstowndata.push_back(currentdata);
                currentdata="";
            }
            else{
                lesstowndata.empty();
                currentdata="";
            }
        }
        towndata.push_back(lesstowndata);
        lesstowndata.empty();
    }*/

    for(int i = 0; i < datavector.size(); i++){
    std::string input = datavector[i];
	std::istringstream ss(input);
	std::string currentdata;

    std::vector<std::string> lesstowndata;
	while(std::getline(ss, currentdata, '\t')) {
		lesstowndata.push_back(currentdata);
		//std::cout << currentdata << '\n';
	}
    towndata.push_back(lesstowndata);

	}

    return towndata;

}

std::vector<std::string> datacontent(std::vector<std::string>filecontent){
    std::vector<std::string> content;
    int count = 0;
    for(int i=0; i < filecontent.size(); i++){
        if(!isalnum(filecontent[i][0])){
            count++;
        }
        else if(count==1){
            content.push_back(filecontent[i]);
        }
    }
    return content;
}

std::vector<std::string> readfile(char* arg){
    std::vector<std::string> filecontent;
    std::string line;
    std::ifstream myfile;
    myfile.open(arg);
    if(myfile.is_open() & myfile.good()){
        while(std::getline(myfile, line)){
            filecontent.push_back(line);
            //std::cout << line << std::endl;
        }
    }
    else{
        std::cout << "Unable to open file" << std::endl;
    }
    myfile.close();

    return filecontent;
}

std::vector<std::vector<std::pair<int, int> > > FormAdjList(std::vector<std::string> townslist, std::vector<std::vector<std::string>>towndata)
    {
    // Our adjacency list.
    std::vector<std::vector<std::pair<int, int> > > adjList;

    // We have townslist.size vertices, so initialize townslist.size rows.
    const int n = townslist.size();

    for(int i = 0; i < n; i++)
        {
        // Create a vector to represent a row, and add it to the adjList.
        std::vector<std::pair<int, int> > row;
        adjList.push_back(row);
        }


    // Now let's add our actual edges into the adjacency list.
    // See the picture here: https://www.srcmake.com/uploads/5/3/9/0/5390645/spadjlist_orig.jpg

    //adjList[0].push_back(std::make_pair(1, 2));
    int currenttowndata = 0;
    for(int i = 0; i++; i<townslist.size()){
        for(int k = 0; k++; k<towndata.size()){
            if(townslist[i]==towndata[k][0]){
                for(int m = 0; m++; m<townslist.size()){
                    if(towndata[k][1]==townslist[m]){
                        adjList[i].push_back(std::make_pair(m, stoi(towndata[k][2])));
                    }
                }
            }
        }
    }

    // Our graph is now represented as an adjacency list. Return it.
    return adjList;
    }


    //0_2_4_3_1
    //TOWNSLIST[0]_TOWNSLIST[2]......TOWNSLIST[1]

    std::vector< std::pair<int, int> > DijkstraSP(std::vector< std::vector<std::pair<int, int> > > &adjList, int &start)
    {
    std::cout << "\nGetting the shortest path from " << start << " to all other nodes.\n";
    std::vector<std::pair<int, int> > dist; // First int is dist, second is the previous node.

    // Initialize all source->vertex as infinite.
    int n = adjList.size();
    for(int i = 0; i < n; i++)
        {
        dist.push_back(std::make_pair(1000000007, i)); // Define "infinity" as necessary by constraints.
        }

    // Create a PQ.
    std::priority_queue<std::pair<int, int>, std::vector< std::pair<int, int> >, std::greater<std::pair<int, int> > > pq;

    // Add source to pq, where distance is 0.
    pq.push(std::make_pair(start, 0));
    dist[start] = std::make_pair(0, start);;

    // While pq isn't empty...
    while(pq.empty() == false)
        {
        // Get min distance vertex from pq. (Call it u.)
        int u = pq.top().first;
        pq.pop();

        // Visit all of u's friends. For each one (called v)....
        for(int i = 0; i < adjList[u].size(); i++)
            {
            int v = adjList[u][i].first;
            int weight = adjList[u][i].second;

            // If the distance to v is shorter by going through u...
            if(dist[v].first > dist[u].first + weight)
                {
                // Update the distance of v.
                dist[v].first = dist[u].first + weight;
                // Update the previous node of v.
                dist[v].second = u;
                // Insert v into the pq.
                pq.push(std::make_pair(v, dist[v].first));
                }
            }
        }

    return dist;
    }

    void PrintShortestPath(std::vector<std::pair<int, int> > &dist, int &start){
    std::ofstream out_put("./Answer.txt");
    if(out_put.is_open())
        {

        out_put << "\nPrinting the shortest paths for node " << start << ".\n";
        for(int i = 0; i < dist.size(); i++)
            {
                out_put << "0" << std::endl;
                out_put << "The distance from node " << start << " to node " << i << " is: " << dist[i].first << std::endl;

                int currnode = i;
                out_put << "The path is: " << currnode;
                while(currnode != start)
                    {
                    currnode = dist[currnode].second;
                    out_put << " -> " << currnode;
                    }
                out_put << std::endl << std::endl;
            }
        }
    }


int main(int argc, char* argv[]) {
    std::vector<std::string> filecontent;
    bool bidir;
    std::vector<std::string> townslist;
    std::vector<std::string> townsdatavector;
    std::vector<std::string> route;
    std::vector<std::vector<std::string>> towndata;
    if(argc != 3) {
        std::cerr << "Usage: " << argv[0]
                << " <FILEPATH> <ROUTE(X->Y)>" << std::endl;
        return 1;
    }
    filecontent = readfile(argv[1]);


    //std::cout << "argv[1]="<<argv[1]<<std::endl;
    //std::cout << "argv[2]="<<argv[2]<<std::endl;

    route = splitroute(argv[2]);
    bidir = is_undirected(filecontent[0]);
    townslist = get_townslist(filecontent);
    /*std::cout << townslist.size() << "townslist size " << std::endl;
    std::cout << route[0] << ";" << route[1] << std::endl;*/
    is_route_in_townslist(townslist, route);

    //print townslist
    std::cout << "List of all towns";
    for(int i = 0; i < townslist.size(); i++)
        std::cout  << ":" << townslist[i];
    std::cout << std::endl;
    std::cout<< "Town size: " << townslist.size() << std::endl;

    //print route

    std::cout << "Route";
    for(int i = 0; i < route.size(); i++){
        std::cout  << ":" << route[i];
    }
    std::cout << std::endl;
    std::cout << "The route contains " << route.size() << " elements" << std::endl;

    //print routeintownslist

    if(is_route_in_townslist(townslist, route)){
        std::cout << "Route is in townslist!"<< std::endl;
    }
    else{
        std::cout << "Route is not in townslist!" << std::endl;
    }


    townsdatavector = datacontent(filecontent);

    /*for(int i = 0; i < townsdatavector.size(); i++){
        std::cout << townsdatavector[i]<< std::endl;
    }*/

    towndata=split_data(townsdatavector);

    //print towndata size
    std::cout << "Size of towndata(2d vector): "<< towndata.size() << std::endl;
    /*for(int i=0; i< towndata.size(); i++){
        std::cout << "Towndata:" << towndata[i][0] << ":" << towndata[i][1] << ":"<<towndata[i][2]<<std::endl;
    }*/
    int startingnode;
    for(int i = 0; i<townslist.size(); i++){
        if(route[0] == townslist[i])
            startingnode=i;
    }


    std::cout << "Test" << std::endl;
    std::cout << townslist[5] << std::endl;
    std::cout << towndata[6][0] << std::endl;
    std::cout << towndata[6][1] << std::endl;
    std::cout << towndata[6][2] << std::endl;

    /*
    for(int i=0; i < towndata.size(); i++){
        traingraph.addEdge(towndata[i][0],towndata[i][1],stoi(towndata[i][2]),bidir);
    }*/
    std::cout << "Program started.\n";

    // Construct the adjacency list that represents our graph.
    std::vector< std::vector<std::pair<int, int> > > adjList = FormAdjList(townslist, towndata);

    // Get a list of shortest path distances for node 0.
    int node = 0;
    std::vector< std::pair<int, int> > dist = DijkstraSP(adjList, node);

    // Print the list.
    PrintShortestPath(dist, startingnode);

    std::cout << "Program ended.\n";


    return 0;


}