#include "Graph.h"
#include <qfile.h>
#include <qtextstream.h>
#include <qstringlist.h>
#include <string>
#include <stdlib.h>
#include <queue>
#include <qdebug.h>
#define UNVISITED 0
#define VISITED 1

using namespace std;

Graph::Graph()
{   numStation = 0;
    numEdge = 0;

	QFile stationL(":/files/files/All.txt");   
    stationL.open(QIODevice::ReadOnly);

    while (!stationL.atEnd()) {                    //将全部站点存入stationList
        QByteArray array = stationL.readLine();
        QString str(array);
        str = str.trimmed();
        Station s(numStation,str.toStdString());
        stationList.push_back(s);
        numStation++;
    }
    stationL.close();


    QFile distance(":/files/files/distance.txt");  //打开存储站点间距信息的文件
    distance.open(QIODevice::ReadOnly);
    QTextStream in(&distance);
    while (true) {
        QString line = in.readLine();
        line = line.trimmed();
        if (line.isNull()) {
            break;
        }
        QStringList parts = line.split(",");          //添加边和站点间距信息


        //qDebug() << parts.at(0) << "  " << parts.at(1) << "  " << parts.at(2) << "  ";
        for (int i = 0; i < stationList.size(); i++) {
            if (stationList.at(i).getName() == parts.at(1).toStdString()) {
                for (int j = 0; j < stationList.size(); j++) {
                    if (stationList.at(j).getName() == parts.at(2).toStdString()) {
                        stationList.at(i).setEdge(parts.at(0).toInt(), stationList.at(j).getNO(), parts.at(3).toInt());
                        stationList.at(j).setEdge(parts.at(0).toInt(), stationList.at(i).getNO(), parts.at(3).toInt());
                        numEdge++; //边的数目加一，实际上存了两遍
                        //qDebug() << parts.at(2).toInt() <<" ";
                    }
                }
            }
        }
    }

    //给Mark分配空间，并全部设为UNVISITED
    Mark = new int[numStation];
    for (int i = 0; i < numStation; i++) {
        Mark[i] = UNVISITED;
    }
}

Edge Graph::FirstEdge(int station) {
    return stationList.at(station).FirstEdge();
}

Edge Graph::NextEdge(Edge preEdge) {  //返回与preEdge有相同顶点的下一条边,若下一条边不存在，则返回一条to和weight都为-1的边
    return stationList.at(preEdge.from).NextEdge(preEdge.to);
}

int Graph::getStationNO(string name) {
    for (int i = 0; i < stationList.size(); i++) {
        if (stationList.at(i).getName() == name) {
            return stationList.at(i).getNO();
        }
    }
    return -1;   //不存在该名称的站点返回-1
}

string Graph::getStationName(int NO) {
    for (int i = 0; i < stationList.size(); i++) {
        if (stationList.at(i).getNO() == NO) {
            return stationList.at(i).getName();
        }
    }
    return "";  //不存在该编号的站点返回空
}

bool Graph::isEdge(Edge e) {
    if (e.from >= 0 && e.from <= numStation && e.to >= 0 && e.to <= numStation) {
        return stationList.at(e.from).isDistance(e.to, e.weight);
    }
    else {
        return false;
    }
}

bool Graph::isTrans(int front, int middle, int behind) {
    return stationList.at(front).getEdge(middle).line != stationList.at(middle).getEdge(behind).line;
}

void Graph::Dijkstra(int s, Dist*& D) {
    D = new Dist[numStation];
    for (int i = 0; i < numStation; i++) {
        Mark[i] = UNVISITED;
        D[i].index = i;
        D[i].length = 2147483647;   //设置length为最大值
        D[i].pre = s;
    }
    D[s].length = 0;
    priority_queue<Dist, vector<Dist>, greater<Dist>>  H;  //堆(heap)等同于优先队列，或者准确地说，优先队列是通过堆实现的。
    H.push(D[s]);
    for (int i = 0; i < numStation; i++) {
        bool FOUND = false;
        Dist d;
        while (!H.empty()) {
            d = H.top();    //获得到s路径长度最小的顶点
            H.pop();
            if (Mark[d.index] == UNVISITED) {   //未访问过就跳出循环
                FOUND = true;
                break;
            }
        }
        if (!FOUND) {  //没有符合条件的最短路径
            break;
        }
        int v = d.index;
        Mark[v] = VISITED;  //该顶点处的标记设为VISITED
        //加入v后需要刷新D中v的邻接点的最短路径长度
        for (Edge e = FirstEdge(v); isEdge(e); e = NextEdge(e)) {
            if (Mark[e.to] == VISITED) {
                continue;
            }
            if (D[e.to].length > (D[v].length + e.weight)) {
                D[e.to].length = D[v].length + e.weight;
                D[e.to].pre = v;
                H.push(D[e.to]);
            }
        }
    }
}

void Graph::Dijk_minTrans(int s, Dist*& D) {
    D = new Dist[numStation];
    for (int i = 0; i < numStation; i++) {
        Mark[i] = UNVISITED;
        D[i].index = i;
        D[i].length = 2147483647;   //设置length为最大值
        D[i].pre = s;
    }
    D[s].length = 0;
    int v = s;
    priority_queue<Dist, vector<Dist>, greater<Dist>>  H;  //堆(heap)等同于优先队列，或者准确地说，优先队列是通过堆实现的。
    H.push(D[s]);
    for (int i = 0; i < numStation; i++) {
        bool FOUND = false;
        Dist d;
        while (!H.empty()) {
            d = H.top();    //获得到s路径长度最小的顶点
            H.pop();
            if (Mark[d.index] == UNVISITED) {   //未访问过就跳出循环
                FOUND = true;
                break;
            }
        }
        if (!FOUND) {  //没有符合条件的最短路径
            break;
        }
        v = d.index;
        Mark[v] = VISITED;  //该顶点处的标记设为VISITED
        //加入v后需要刷新D中v的邻接点的最短路径长度
        for (Edge e = FirstEdge(v); isEdge(e); e = NextEdge(e)) {
            if (Mark[e.to] == VISITED) {
                continue;
            }
            if (D[e.to].length > (D[v].length + isTrans(D[v].pre, v, e.to))){
                D[e.to].length = D[v].length + isTrans(D[v].pre, v, e.to);
                D[e.to].pre = v;
                H.push(D[e.to]);
            }
        }
    }
}

string Graph::minRoute(int source, int target) {
    Dist* d;
    Dijkstra(source, d);
    if (source == target) {
        delete[]d;
        return stationList.at(source).getName();
    }
    else {
        vector<int> l;
        string route="";
        for (int temp = target; temp != source; temp = d[temp].pre) {
            l.push_back(temp);
        }
        l.push_back(source);
        for (int i = l.size() - 1; i > 0; i--) {
            route += stationList.at(l.at(i)).getName();
            route += " -> ";
        }
        route += stationList.at(l.at(0)).getName();
        delete[]d;
        return route;
    }
}

string Graph::minTranRoute(int source, int target) {
    Dist* d;
    Dijk_minTrans(source, d);
    if (source == target) {
        delete[]d;
        return stationList.at(source).getName();
    }
    else {
        vector<int> l;
        string route = "";
        for (int temp = target; temp != source; temp = d[temp].pre) {
            l.push_back(temp);
        }
        l.push_back(source);
        for (int i = l.size() - 1; i > 0; i--) {
            route += stationList.at(l.at(i)).getName();
            route += " -> ";
        }
        route += stationList.at(l.at(0)).getName();
        delete[]d;
        return route;
    }
}

int Graph::minLength(int source, int target) {
    Dist* d;
    Dijkstra(source, d);

    if (source == target) {
        delete[]d;
        return 0;
    }
    else {
        int min=0;
        min = d[target].length;
        delete[]d;
        return min;
    }
}

int Graph::minTranNum(int source, int target) {
    Dist* d;
    Dijk_minTrans(source, d);

    if (source == target) {
        delete[]d;
        return 0;
    }
    else {
        int min = 0;
        min = d[target].length;
        delete[]d;
        return min-1; //开始时就被判定为换乘，所以比实际值大一，减一
    }
}

int Graph::TranNum(int source, int target, Dist*& D) {
    int num = 0;
    int temp1, temp2 = 0;  //temp2总是更靠近source
    if (D[target].pre == source) {
        return 0;                 //只经过两站，无换乘
    }
    else {
        for (temp1 = target,temp2=D[target].pre; temp2 != source; temp1 = D[temp1].pre,temp2=D[temp2].pre) {
            num += isTrans(temp1, temp2, D[temp2].pre);
        }
    }
    return num;
}

int Graph::Length(int source, int target, Dist*& D) {
    int length = 0;
    int temp = 0;
    for (temp = target; temp != source; temp = D[temp].pre) {
        length += stationList.at(temp).getEdge(D[temp].pre).weight;
    }
    return length;
}
/*
string Graph::Route(int source, int target, Dist*& D) {
    string route = "";
    int temp = 0;
    for (temp = target; temp != source; temp = D[temp].pre) {
        route.insert(0, stationList.at(temp).getName());
        route.insert(0, "->");
    }
    route.insert(0, stationList.at(source).getName());
    return route;
}*/

Edge* Graph::Route(int source, int target, Dist*& D) {
    int num = getEdgeNum(source, target, D);
    Edge* s = new Edge[num];
    int temp1,temp2 = 0;
    int i = num-1;
    for (temp1 = target, temp2 = D[target].pre; temp1 != source && i >= 0; temp1 = D[temp1].pre, temp2 = D[temp2].pre, i--) {
        s[i]=stationList.at(temp2).getEdge(temp1);
    }
    return s;
}

int Graph::getEdgeNum(int source, int target, Dist*& D) {
    int temp = 0;
    int num = 0;
    for (temp = target; temp != source; temp = D[temp].pre) {
        num++;
    }
    return num;
}

void Graph::resetMark() {
    for (int i = 0; i < numStation; i++) {
        Mark[i] = UNVISITED;
    }
}

Graph::~Graph() {
    delete[] Mark;
}