#pragma once

#include <vector>

using namespace std;

namespace graph
{
	// 边模板类
	template <class TVertex, class TWeight>
	class Edge
	{
	public:
		TVertex starting_vertex;	// 起点
		TVertex ending_vertex;		// 终点
		TWeight weight;				// 边权重
		
		Edge() :starting_vertex(TVertex()), ending_vertex(TVertex()), weight(TWeight()) {}

		Edge(const TVertex& starting_vertex, const TVertex& ending_vertex, const TWeight& weight)
			:weight(weight), starting_vertex(starting_vertex), ending_vertex(ending_vertex) {}

		// 边的比较是边权值之间的比较

		// 重载<=
		bool operator<=(const Edge<TVertex, TWeight>& edge) { return this->weight <= edge.weight; }

		// 重载>=
		bool operator>=(const Edge<TVertex, TWeight>& edge) { return this->weight >= edge.weight; }

		// 重载>
		bool operator>(const Edge<TVertex, TWeight>& edge) { return this->weight > edge.weight; }

		// 重载<
		bool operator<(const Edge<TVertex, TWeight>& edge) { return this->weight < edge.weight; }

		// 重载==
		bool operator==(const Edge<TVertex, TWeight>& edge) { return (this->starting_vertex == edge.starting_vertex && this->ending_vertex == edge.ending_vertex); }
	};

	// 路径模板类
	template <class TVertex, class TWeight>
	class Path :public Edge<TVertex, TWeight>
	{
		TWeight weight;				// 路径权值
		TVertex starting_vertex;	// 起点
		TVertex ending_vertex;		// 终点

		Path() :starting_vertex(TVertex()), ending_vertex(TVertex()), weight(TWeight()) {}
	
		Path(TVertex starting_vertex, TVertex ending_vertex, TWeight weight)
			:starting_vertex(starting_vertex), ending_vertex(ending_vertex), weight(weight) {}
	};

	template <class TVertex, class TWeight>
	class Graph
	{
	protected:
		int max_vertex_count_;					// 图节点数量上限
		TWeight max_weight_;					// 边权值上限
		int edge_count_;						// 边数量
		int vertex_count_;						// 结点数量
		int type_;								// 类型（1：有向，2：无向）

		vector<TVertex> vertices_;				// 结点vector
		vector<int> degrees_;					// 度vector（无向图使用）
		vector<int> in_degrees_;				// 入度vector（有向图使用）
		vector<int> out_degrees_;				// 出度vector（有向图使用）
	
		vector<Edge<TVertex, TWeight>> edges_;	// 边vector

	public:
		static const int DIRECTED = 1;		// 有向
		static const int UNDIRECTED = 2;	// 无向

		// 获取图类型
		int type() const { return this->type_; }

		// 获取结点数量
		unsigned int vertexCount() const { return this->vertex_count_; }

		// 获取边数量
		unsigned int edgeCount() const { return this->edge_count_; }

		// 获取边权值上限
		// virtual关键字用于声明虚函数，这意味着这个函数可以在派生类中被重写（override）
		virtual TWeight maxWeight() const { return this->max_weight_; }

		// 获取点权值上限
		virtual int maxVertexCount() const { return this->max_vertex_count_; }

		// 获取边vector
		virtual const vector<Edge<TVertex, TWeight>>& edges() const { return this->edges_; }

		// 获取结点vector
		virtual const vector<TVertex>& vertices() const { return this->vertices_; }

		// 通过索引获取边，因为vector容器重载的“[]”
		virtual const Edge<TVertex, TWeight>& getEdge(int index) const { return this->edges_[index]; }

		// 通过索引获取结点，纯虚函数
		virtual bool getVertexByIndex(int vertex_index, TVertex& vertex) const = 0;
		// 通过结点获取边权值，纯虚函数
		virtual bool getWeight(const TVertex& starting_vertex, const TVertex& ending_vertex, TWeight& weight) const = 0;
		// 通过始末边的索引获取边权值,纯虚函数
		virtual bool getWeightByVertexIndex(int starting_vertex_index, int ending_vertex_index, TWeight& weight) const = 0;
		// 获取结点的第一个相邻结点,纯虚函数
		virtual bool getFirstNeighborVertex(const TVertex& vertex, TVertex& first_neighbor) const = 0;
		// 获取结点的下一个相邻结点,纯虚函数
		virtual bool getNextNeighborVertex(const TVertex& vertex, const TVertex& neighbor_vertex,TVertex& next_neighbor) const = 0;

		// 获取结点的度
		int getVertexDegree(TVertex vertex)
		{
			// 有向图没有度的概念，度被分为出度和入度
			if (this->type_ == DIRECTED)
				return -1;

			int vertex_index = this->getVertexIndex(vertex);

			return this->degrees_[vertex_index];
		}

		// 获取结点的入度
		int getVertexInDegree(const TVertex& vertex) const
		{
			// 无向图没有入度的概念
			if (this->type_ == UNDIRECTED)
				return -1;

			int vertex_index = this->getVertexIndex(vertex);

			return this->in_degrees_[vertex_index];
		}

		// 获取结点的出度
		int getVertexOutDegree(const TVertex& vertex) const
		{
			// 无向图没有入度的概念
			if (this->type_ == UNDIRECTED)
				return -1;

			int vertex_index = this->getVertexIndex(vertex);

			return this->out_degrees_[vertex_index];
		}

		// 插入结点，纯虚函数
		virtual bool insertVertex(const TVertex& vertex) = 0;
		// 插入边，纯虚函数
		virtual bool insertEdge(const TVertex& starting_vertex, const TVertex& ending_vertex, const TWeight& weight) = 0;
		// 删除结点，纯虚函数
		virtual bool removeVertex(const TVertex& vertex) = 0;
		// 删除边，纯虚函数
		virtual bool removeEdge(const TVertex& starting_vertex, const TVertex& ending_vertex) = 0;
		// 获取结点索引，纯虚函数
		virtual int getVertexIndex(const TVertex& vertex) const = 0;
	};
}