#include <iostream>
#include <string>
#include <fstream>
#include<sstream>
#include "Cities.h"
#include "Neighbours.h"
#include "DjikstraResult.h"
#include "Visited.h"
using namespace std;

bool contain(Cities* head, string name) {
    while (head) {
        if (head->name == name) {
            return true;
        }
        head = head->next;
    }
    return false;
}
bool containNeighbours(Neighbours* head, string name) {
    while (head) {
        if (head->name == name) {
            return true;
        }
        head = head->next;
    }
    return false;
}
void addVert(DjikstraResult*& head, string name) {
    if (head == nullptr) {
        head = new DjikstraResult{ name,"", INT_MAX, nullptr };
        return;
    }
    else {
        DjikstraResult* tmp = head;
        while (tmp->next) {
            tmp = tmp->next;
        }
        tmp->next = new DjikstraResult{ name,"",INT_MAX, nullptr };
    }
}
void set0forcapital(DjikstraResult* head, string name) {
    while (head) {
        if (name == head->vertname) {
            head->waga = 0;
            break;
        }
        head = head->next;
    }
}
void add(Cities*& head, string name) {
    if (head == nullptr) {
        head = new Cities{ name, nullptr, nullptr };
    }
    else {
        Cities* tmp = head;
        while (tmp->next) {
            tmp = tmp->next;
        }
        tmp->next = new Cities{ name, nullptr, nullptr };
    }
}
void addToNeighbours(Neighbours*& head, string name, int dis) {
    if (head == nullptr) {
        head = new Neighbours{ name, dis, nullptr };
        return;
    }
    else {
        Neighbours* tmp = head;
        while (tmp->next) {
            tmp = tmp->next;
        }

        tmp->next = new Neighbours{ name, dis, nullptr };
    }
}
Cities* getByName(Cities* head, const string& name) {
    while (head) {
        if (head->name == name) {
            return head;
        }
        head = head->next;
    }
}
void read(const string& n, Cities*& head) {
    fstream file;
    file.open(n, ios::in);
    if (file.good()) {
        while (!file.eof()) {
            string city1, city2;
            int distance;
            string line;
            getline(file, line);
            stringstream linestream;
            linestream << line;
            if (linestream >> city1 >> city2 >> distance) {
                if (!contain(head, city1)) {
                    add(head, city1);
                    Cities* city1cell = getByName(head, city1);
                    addToNeighbours(city1cell->distances, city2, distance);
                }
                else {
                    Cities* city1cell = getByName(head, city1);
                    if (!containNeighbours(city1cell->distances, city2)) {
                        addToNeighbours(city1cell->distances, city2, distance);
                    }
                }
                if (!contain(head, city2)) {
                    add(head, city2);
                    Cities* city2cell = getByName(head, city2);
                    addToNeighbours(city2cell->distances, city1, distance);
                }
                else {
                    Cities* city2cell = getByName(head, city2);
                    if (!containNeighbours(city2cell->distances, city1)) {
                        addToNeighbours(city2cell->distances, city1, distance);
                    }
                }
            }
        }
    }
    file.close();
}
Neighbours* getNeighbours(Cities* head, string name) {
    while (head) {
        if (head->name == name) {
            return head->distances;
        }
        head = head->next;
    }
}
bool checkInVisited(Visited* head, string name) {
    while (head) {
        if (head->name == name) {
            return true;
        }
        head = head->next;
    }
    return false;
}
bool isVisited(Visited* head, string name) {
    while (head) {
        if (head->name == name) {
            return true;
        }
        head = head->next;
    }
    return false;
}
void addAtEnd(Visited*& head, string name) {
    if (!head) {
        head = new Visited{ name, nullptr };
    }
    else {
        Visited* nowy = head;
        while (nowy->next) {
            nowy = nowy->next;
        }
        nowy->next = new Visited{ name, nullptr };
    }
}
DjikstraResult* fillTab(Cities* head, string city) {
    Cities* temp = head;
    DjikstraResult* pathvert = nullptr;
    while (temp) {
        addVert(pathvert, temp->name);
        temp = temp->next;
    }
    set0forcapital(pathvert, city);
    return pathvert;
}
DjikstraResult* findCityWithShortestPath(DjikstraResult* pathLengths, Visited* visitedCities) {
    DjikstraResult* shortest = new DjikstraResult{ "","",INT_MAX,nullptr };
    while (pathLengths) {
        if (!isVisited(visitedCities, pathLengths->vertname) && pathLengths->waga < shortest->waga) {
            shortest = pathLengths;
        }
        pathLengths = pathLengths->next;
    }
    return shortest;
}
int getWeightByName(DjikstraResult* head, string name) {
    while (head) {
        if (head->vertname == name) {
            return head->waga;
        }
        head = head->next;
    }
}
void setNewWeight(DjikstraResult* head, string name, string currentName, int weight) {
    while (head) {
        if (head->vertname == name) {
            head->waga = weight;
            head->previous = currentName;
            break;
        }
        head = head->next;
    }

}
void deleteNeighbours(Neighbours* head) {
    if (head) {
        deleteNeighbours(head->next);
        delete head;
        head = nullptr;
    }
}
void deleteMap(Cities* Map) {
    if (Map) {
        deleteMap(Map->next);
        deleteNeighbours(Map->distances);
        delete Map;
        Map = nullptr;
    }
}
void deleteResults(DjikstraResult* Tab) {
    if (Tab) {
        deleteResults(Tab->next);
        delete Tab;
        Tab = nullptr;
    }
}
void djikstra(Cities*& Map, DjikstraResult*& Tab, string capital) {
    Cities* cities = Map;
    DjikstraResult* pathLengths = Tab;
    int citiesLength = 0;
    while (cities) {
        addVert(pathLengths, cities->name);
        cities = cities->next;
        citiesLength++;
    }
    set0forcapital(pathLengths, capital);
    Visited* visitedCities = nullptr;
    cities = Map;
    for (int i = 0; i < citiesLength; i++) {
        DjikstraResult* currentCity = findCityWithShortestPath(pathLengths, visitedCities);
        Neighbours* neighbours = getNeighbours(cities, currentCity->vertname);

        while (neighbours) {
            int newWeight = currentCity->waga + neighbours->dist;
            if (newWeight < getWeightByName(pathLengths, neighbours->name)) {
                setNewWeight(pathLengths, neighbours->name, currentCity->vertname, newWeight);
            }
            neighbours = neighbours->next;
        }
        addAtEnd(visitedCities, currentCity->vertname);
    }
    Tab = pathLengths;

}
DjikstraResult* findByName(DjikstraResult* head, string n) {
    DjikstraResult* tmp = head;

    while (tmp) {
        if (tmp->vertname == n) {
            return tmp;
        }
        else {
            tmp = tmp->next;
        }
    }

    return nullptr;
}
string xd(DjikstraResult* Tab, string name) {
    if (Tab) {
        DjikstraResult* current = findByName(Tab, name);

        if (current->previous != "") {
            return xd(Tab, current->previous) + "->" + current->vertname;
        }
        return current->vertname;
    }
    return "";
}
void saveToTXT(DjikstraResult* Tab, const string& n, string capital) {
    fstream file;
    file.open(n, fstream::out);
    if (file.good()) {
        DjikstraResult* tmp = Tab;
        while (tmp) {
            if (tmp->vertname != capital) {
                string x = xd(Tab, tmp->vertname);
                file << x << ": " << tmp->waga << endl;
                tmp = tmp->next;
            }
            else {
                tmp = tmp->next;
            }

        }
        file.close();
    }
}