//---------------------------------------------------------------------------
#ifndef GRAPH_BAS_H_
#define GRAPH_BAS_H_
//---------------------------------------------------------------------------
#include <iostream>
#include <list>
#include <vector>
#include "Graph_Input.h"
using namespace std;

template <class T>
class graph_bas
{
    private:
       typedef vector<list<T> > AdjacencyLists;
       // 頂點數
       int vertexNum;
       // 邊數
       int edgeNum;
    protected:
       // 保存頂點數據的鏈表
       list<T> vertexList;
       // 鄰接鏈表
       AdjacencyLists AdjLists;
    public:
       // 圖類型信息
       bool gType;
       // 返回頂點位置
       int GetVertexPos(const T& vertext);
       // 重載下標運算符
       list<size_t>& operator[](size_t i) { return AdjLists[i]; }
       // 圖構造器: 創建空圖對象
       graph_bas() { }
       // 圖構造器: 創建基于鄰接鏈表的圖對象（不帶權值）
       graph_bas(graphInfo<T> ginfor);
       // 返回保存頂點數據的鏈表
       list<T> GetvertexList() { return vertexList; }
       // 返回圖頂點數
       int GetnumVertices(void) const { return vertexNum; }
       // 返回圖邊數
       int GetnumEdges(void) const { return edgeNum; }
       // 輸出鏈表
       void print_List(char *c,list<T> L);
       // 輸出鄰接鏈表
       void print_AdjLists(char *c);
};

// 不帶權值的無向圖/有向圖構造器
template <class T>
graph_bas<T>::graph_bas(graphInfo<T> ginfor):
  vertexNum(ginfor.numV),edgeNum(ginfor.numE),
  AdjLists(ginfor.numV),gType(ginfor.directedGraph)
{
   T vertex;
   T vertex1,vertex2;
   for(int i=0; i<vertexNum; i++) {     // 建立供查找的頂點鏈表
      vertex=ginfor.vexs[i];
      vertexList.push_back(vertex);     // 插入頂點到一個頂點鏈表尾部
   }
   for(i=0; i<edgeNum; i++) {
     vertex1 = ginfor.edges[i].v1;
     vertex2 = ginfor.edges[i].v2;
     // 無向圖建鄰接鏈表時，頂點1和2是互相鄰接的，插入到鄰接鏈表首部
     AdjLists[GetVertexPos(vertex1)].push_front(vertex2);
     // 對于有向圖，頂點1和2鄰接是單向的，不執行下面插入語句
     if(!gType)
        AdjLists[GetVertexPos(vertex2)].push_front(vertex1);
   }
   for(i=0; i<vertexNum; i++)
      AdjLists[i].push_front(ginfor.vexs[i]); // 插入頂點到頂點鏈表首部
}

template <class T>
int graph_bas<T>::GetVertexPos(const T& vertex)
{
   list<T>::iterator itr;         // 聲明鏈表迭代器
   itr = vertexList.begin();      // 迭代器指向頂點鏈表首元素
   int pos = 0;
   // 查找指定頂點的位置
   while(itr!=vertexList.end() && (*itr) != vertex) {
      ++pos;
      ++itr;
   }
   return pos;
}
// 鏈表存儲數據的公用顯示函數
template <class T>
void graph_bas<T>::print_List(char *c,list<T> L)
{
   list<T>::iterator it;
   cout << c;
   for (it=L.begin(); it!=L.end(); it++)
      cout << *it << "   ";
   cout << endl;
  
}

template <class T>
void graph_bas<T>::print_AdjLists(char *c)
{ 
   cout << c << endl;
   list<VertexNode<T,T1> >::const_iterator it;
   for (int k=0; k<GetnumVertices(); k++) {
      for (it=AdjLists[k].begin(); it!=AdjLists[k].end(); it++)
         if (it==AdjLists[k].begin())
            cout << "《" << it->flag << "，id: " << it->id << "》";
         else
            cout << "→《" << it->flag << "，dut: " << it->dut << "》";
      cout << endl;
   }
}

#endif