#ifndef GRAPH_H
#define GRAPH_H

#include <iostream>
#include <string>
#include <vector>
#include <stdlib.h>

using namespace std;

// 定義頂點
typedef struct EdgeNode {
	int adjvex;	// 頂點下標
	struct  EdgeNode *next;	// 下一條邊的指針
	double cost;	// 當前邊的代價

	EdgeNode();
	~EdgeNode();
} EdgeNode;


// 定義頂點表
typedef struct VexList
{
	string Vexs;  //用來存儲頂點信息
	EdgeNode *firstedge;  //用來存儲當前頂點的下一個頂點

	VexList();
	~VexList();
} VertexList;



// 定義圖
typedef class GraphList {
public:
	GraphList();
	~GraphList();

	void PrintGraph();	// 打印圖
	void CreateGraph();	// 構建圖

	vector<VexList> VexList;
	int Vertexs, Edges;

} GraphList;

typedef GraphList* GraphListPtr;


#endif

#include <graph.h>

EdgeNode::EdgeNode() {
	cost = 0;
	next = nullptr;
}
EdgeNode::~EdgeNode() {
	//cout << "delete Node" << endl;
}

VexList::VexList() {
	firstedge = nullptr;
}
VexList::~VexList() {
	//cout << "delete VexList" << endl;
}

GraphList::GraphList() {
	VexList.clear();
}

GraphList::~GraphList() {
	//cout << "delete GraphList" << endl;
}

void GraphList::PrintGraph() {
	cout << "所建立的地圖如以下所示：" << endl;
	for (int i = 0; i< Vertexs; i++) {
		cout << VexList[i].Vexs;             //先輸出頂點信息
		EdgeNode * e = VexList[i].firstedge;
		while (e) {                           //然后就開始遍歷輸出每個邊表所存儲的鄰接點的下標
			if (e->cost == -1) {
				cout << "---->" << e->adjvex;
			}
			else {
				cout << "-- " << e->cost << " -->" << e->adjvex;
			}
			e = e->next;
		}
		cout << endl;
	}
}

void GraphList::CreateGraph() {
	EdgeNode *e = new EdgeNode();
	cout << "請輸入頂點數和邊數：" << endl;
	cin >> Vertexs >> Edges;
	cout << "請輸入頂點的信息：" << endl;

	for (int i = 0; i <Vertexs; ++i) {
		VertexList tmp;
		cin >> tmp.Vexs;
		tmp.firstedge = NULL;
		VexList.push_back(tmp);
	}

	for (int k = 0; k < Edges; ++k) {
		int i, j;	//(Vi，Vj)
		double cost;
		cout << "請輸入邊（Vi,Vj）與 cost：" << endl;
		cin >> i >> j >> cost;
		if (VexList[i].firstedge == NULL) {//當前頂點i后面沒有頂點
			e = new EdgeNode;
			e->adjvex = j;
			e->cost = cost;
			e->next = NULL;
			VexList[i].firstedge = e;
		}
		else {  //當前i后面有頂點
			EdgeNode *p = VexList[i].firstedge;
			while (p->next) {
				p = p->next;
			}
			e = new EdgeNode;
			e->adjvex = j;
			e->cost = cost;
			e->next = NULL;
			p->next = e;
		}
	}
}

#ifndef PATH_FINDER_H
#define PATH_FINDER_H

#include <iostream>
#include <graph.h>
#include <queue>

enum State{OPEN = 0, CLOSED, UNFIND};
// 定義dijkstra求解器
class DijNode {

public:
	DijNode();
	DijNode(double _val);
	~DijNode() {};
	double getCost() { return m_cost; }
	State getState() { return m_state; }
	void setCost(double _val) { m_cost = _val; }
	void setState(State _state) { m_state = _state; }
	int getIndex() { return m_index; }
	void setIndex(int _idx) { m_index = _idx; }
	void setPred(DijNode* _ptr) { preNode = _ptr; }
	DijNode* getPred() { return preNode; }

	VertexList Vertex;
private:
	int m_index;
	double m_cost;	// 起點到當前點的代價
	State m_state;
	DijNode* preNode;	// 保存父節點
};

typedef DijNode* DijNodePtr;

// 構造優先隊列用的
struct cmp {
	bool operator() (DijNodePtr &a, DijNodePtr &b) {
		return a->getCost() > b->getCost();
	}
};

class PathFinder {
public:
	priority_queue<DijNodePtr, vector<DijNodePtr>, cmp > openList;//用優先隊列做openList，隊首元素為最小值
	vector<DijNodePtr> m_path;	// 存放最終路徑
	PathFinder() {
		openList.empty();
		m_path.clear();
	}
	~PathFinder() {};

	void StoreGraph(GraphListPtr _graph);
	void Search(int start, int end);
	void retrievePath(DijNodePtr _ptr);

	vector<DijNodePtr> NodeList;

private:
	GraphListPtr m_graph;
	/*vector<DijNodePtr> NodeList;*/
};

typedef PathFinder* PathFinderPtr;
#endif

#include <PathFinder.h>

DijNode::DijNode() {
	m_cost = -1;	// -1表示未被探索過，距離為無窮，非負數表示已經被探索過
	m_index = -1;
	m_state = UNFIND;	// OPEN表示openlist， CLOSED表示在closeList中，UNFIND表示未探索過
	preNode = nullptr;
}

DijNode::DijNode(double _val) {
	m_cost = _val;	// -1表示未被探索過，非負數表示已經被探索過
	m_index = -1;
	m_state = UNFIND;	// OPEN表示openlist， CLOSED表示在closeList中，UNFIND表示未探索過
	preNode = nullptr;
}

void PathFinder::StoreGraph(GraphListPtr _graph) {
	for (int i = 0; i < _graph->VexList.size(); ++i) {
		DijNodePtr node = new DijNode();
		node->Vertex = _graph->VexList[i];
		node->setIndex(i);
		NodeList.push_back(node);
	}
}

void PathFinder::Search(int start, int end) {
	// 搜索起點
	DijNodePtr m_start = NodeList[start];
	m_start->setCost(0);
	m_start->setIndex(start);
	m_start->setState(OPEN);
	openList.push(m_start);

	int count = 0;
	while (!openList.empty()) {

		
		// 彈出openList中的隊首元素
		DijNodePtr cur = openList.top();
		cur->setState(CLOSED);	// 加入closelist中
		openList.pop();

		// 遍歷隊首元素所有的邊
		EdgeNode *e = cur->Vertex.firstedge;
		while (e != nullptr) {
			int _index = e->adjvex;
			double _cost = e->cost;
			
			//cout << "_cost = " << _cost << endl;
			// 如果節點在close list中，直接跳過
			if (NodeList[_index]->getState() == CLOSED) {
				continue;
			}

			if (NodeList[_index]->getCost() == -1) {
				NodeList[_index]->setCost(cur->getCost() + _cost);	// 更新代價
				NodeList[_index]->setPred(cur);		// 更新父節點
				NodeList[_index]->setState(OPEN);	// 加入open list中
				openList.push(NodeList[_index]);
			}
			else if (cur->getCost() + _cost < NodeList[_index]->getCost()) {
				// 如果從當前節點到第_index個節點的距離更短，更新距離和父節點
				NodeList[_index]->setCost(cur->getCost() + _cost);	// 更新代價
				NodeList[_index]->setPred(cur);		// 更新父節點
				NodeList[_index]->setState(OPEN);	// 加入open list中
			}

			e = e->next;
		}
	}

	cout << "最短距離為：" << NodeList[end]->getCost() << endl;
	retrievePath(NodeList[end]);

}

void PathFinder::retrievePath(DijNodePtr ptr) {
	while (ptr != nullptr) {
		m_path.push_back(ptr);
		ptr = ptr->getPred();
	}
	reverse(m_path.begin(),m_path.end());
}

#include <graph.h>
#include <PathFinder.h>


int main() {
	cout << "構建地圖" << endl;
	GraphListPtr graph = new GraphList();
	graph->CreateGraph();

	cout << "\n \n";
	graph->PrintGraph();

	PathFinderPtr _solver = new PathFinder();
	_solver->StoreGraph(graph);

	cout << "\n \n";

	int start, end;
	cout << "輸入起點" << endl;
	cin >> start;

	cout << "輸入終點" << endl;
	cin >> end;

	cout << "\n \n";

	_solver->Search(start, end);
	cout << "最短路徑為：";
	 
	for (int i = 0; i < _solver->m_path.size(); ++i) {
		 cout << _solver->m_path[i]->Vertex.Vexs ;
		 if (i < _solver->m_path.size() - 1)
			 cout << "-->";
	}
	cout << endl;

	system("pause");
	return 0;
}