//列舉鏈表的兩個(gè)末端；
//enum TYPE {BREADTH_FIRST, DEPTH_FIRST };

// 類(lèi)舉可能的A* 啟發(fā)式方法，第二種啟發(fā)式使用深度；
//enum HEURISTIC {NOT_USED, MANHATTAN_DISTANCE, WRONG_TILES}; 
enum SIDE { LEFT, RIGHT }; 
// 鏈表由下面的Link結(jié)構(gòu)對(duì)象組成； 
struct Link { 
  Link *LeftLink; // 指向鏈表中左端LINK對(duì)象的指針； 
  Link *RightLink; //指向鏈表中右端LINK對(duì)象的指針；
  CState *Data; // 指向狀態(tài)數(shù)據(jù)的指針；
}; 

// 鏈表類(lèi)； 
class CLList { 
private: 
  Link* LeftPointer; // 指向一個(gè)永遠(yuǎn)是空的，并且是末端的link對(duì)象；
  Link* RightPointer; //與上面的指針一樣，但方向相反；
  double ListLen; // 鏈表的長(zhǎng)度； 
  // 清空內(nèi)存；
  void EmptyUsedMemory() { 
    CState *temp; 
    while(!IsListEmpty()) { 
      temp = Pop(LEFT); 
      delete temp; 
    } 
  } 

public: 
  class ERROR_CANT_POP_EMPTY_LIST{}; // Error Exception 

  CLList() { 
  // initialise all private variables 
    LeftPointer = new Link; 
    RightPointer = new Link; 
    ListLen = 0; 
    LeftPointer->LeftLink = 0; 
    LeftPointer->RightLink = RightPointer; 
    RightPointer->RightLink = 0; 
    RightPointer->LeftLink = LeftPointer; 
  } 
  ~CLList() { 
    EmptyUsedMemory(); 
  } 

  inline double GetListLen() { 
    return ListLen; 
  } 

  inline bool IsListEmpty() { 
    return (LeftPointer->RightLink == RightPointer); 
  } 

  //從鏈表中彈出數(shù)據(jù)；
  CState* Pop(SIDE Side) { 
    Link ForReturn; 
    Link* ForDelete; 
    if (!IsListEmpty()) { 
      ListLen--; 
      if (Side == LEFT) { 
        ForReturn = *(LeftPointer->RightLink); 
        ForDelete = LeftPointer->RightLink; 
        LeftPointer->RightLink = ForReturn.RightLink; 
        ForReturn.RightLink->LeftLink = LeftPointer; 
      } 
      else { 
        ForReturn = *(RightPointer->LeftLink); 
        ForDelete = RightPointer->LeftLink; 
        RightPointer->LeftLink = ForReturn.LeftLink; 
        ForReturn.LeftLink->RightLink = RightPointer; 
      } 
      delete ForDelete; 
      return ForReturn.Data; 
    } 
    return 0; 
  } 

  //向鏈表中壓入數(shù)據(jù) 
  void Push(SIDE Side, CState* What) { 
    Link* NewLink = new Link; 
    NewLink->Data = What; 
    ListLen++; 
    if (Side == LEFT) { 
      NewLink->RightLink = LeftPointer->RightLink; 
      NewLink->LeftLink = LeftPointer; 
      LeftPointer->RightLink = NewLink; 
      NewLink->RightLink->LeftLink = NewLink; 
    } 
    else { 
      NewLink->RightLink = RightPointer; 
      NewLink->LeftLink = RightPointer->LeftLink; 
      RightPointer->LeftLink = NewLink; 
      NewLink->LeftLink->RightLink = NewLink; 
    } 
  } 

  //啟發(fā)式搜索過(guò)程中，從鏈表中搜尋最佳狀態(tài)；
  CState* PopBestByHeuristics(HEURISTIC heuristic) { 
    int BestValue=9999; 
    int Temp=0; 
    Link* BestState = 0; 
    Link* Current = LeftPointer; 
    CState* ForReturn = 0; 
    if(!IsListEmpty()) { 
      //啟發(fā)式搜索可以使用MANHATTAN_DISTANCE或WrongTile方式來(lái)搜尋最佳狀態(tài)
      while(Current->RightLink != RightPointer) { 
        Current = Current->RightLink; 
        if(heuristic == MANHATTAN_DISTANCE) { 
          Temp = Current->Data->GetManhattanDistance(); 
        } 
        else { 
          Temp = Current->Data->GetWrongTiles(); 
        } 
        if(Temp < BestValue) { 
          BestValue = Temp; 
          BestState = Current; 
        } 
      } 
      //從鏈表中刪除最佳狀態(tài)；
      BestState->RightLink->LeftLink = BestState->LeftLink; 
      BestState->LeftLink->RightLink = BestState->RightLink; 
      ForReturn = BestState->Data; 
      delete BestState; 
      return ForReturn; 
    } 
    return 0; 
  } 

  CState* PeekByBestHueristics(HEURISTIC heuristic) { 
    int BestValue=9999; 
    int Temp=0; 
    Link* BestState = 0; 
    Link* Current = LeftPointer; 
    CState* ForReturn = 0; 
    if(!IsListEmpty()) { 
      // Find BEST State By Wrong tile number heuristic 
      while(Current->RightLink != RightPointer) { 
        Current = Current->RightLink; 
        if(heuristic == MANHATTAN_DISTANCE) { 
          Temp = Current->Data->GetManhattanDistance(); 
        } 
        else { 
          Temp = Current->Data->GetWrongTiles(); 
        } 
        if(Temp < BestValue) { 
          BestValue = Temp; 
          BestState = Current; 
        } 
      } 
      ForReturn = BestState->Data; 
      return ForReturn; 
    } 
    return 0; 
  }
};