void gotoxy(int x, int y); //函數原型，使用光標的xy坐標；
// 枚舉搜索的類型；
enum TYPE {BREADTH_FIRST, DEPTH_FIRST };
//#include<iostream.h> // for console i/o

// 類舉可能的A* 啟發式方法，第二種啟發式使用深度；
enum HEURISTIC {NOT_USED, MANHATTAN_DISTANCE, WRONG_TILES}; 
// include the header files we are going to need

#include<iostream.h>

#include<windows.h> // for sleep() and gotoxy()
#include"State.h" // for game state class
#include"Llist.h" // for a linked list class


CLList PrevStates;/* 用于跟蹤以前的狀態，程序結束時要及時刪除，以免內存泄露*/
CLList MainQue; // 等待主隊列； 
SIDE PushSide;
SIDE PopSide;
// 膨脹函數；
CState* GeneralExpand(int DepthLimit, HEURISTIC heuristic);
// 膨脹的步數；
double Expanded = 0;

// 當發現解決方法后，該函數將結果顯示在屏幕上；
void ShowSolution(CState* Solution) {
// 結果是回退得到的，所以實際結果應該是與之反向的，這時候可以使用后入先出的方法； 
CLList Reverse;
bool EndLoop=false;
while(!EndLoop) {
  Reverse.Push(LEFT, Solution);
  if(Solution->GetPrevState() != 0) {
    Solution = Solution->GetPrevState();
  }
  else {
    EndLoop = true;
  }
}
int NewLine = 0;
CState *Temp;
cout << "\n";
while(!Reverse.IsListEmpty()) {
  Temp = Reverse.Pop(LEFT);
  NewLine++;
  if(NewLine > 10) { cout << "\n"; NewLine=0;}
  switch(Temp->GetLastOperator()) {
    case NORTH:
      cout << "North, ";
      break;
    case EAST:
      cout << "East, ";
      break;
    case SOUTH:
      cout << "South, ";
      break;
    case WEST:
      cout << "West, ";
      break;
  }
}
cout << "\n\n" << "Expanded: " << Expanded << endl;
}


// 設置控制臺i/o x,y坐標
void gotoxy(int x, int y) {
  // SET CONSOLE CURSOR POSITION.
  COORD coord = {x,y};
  HANDLE handle = GetStdHandle(STD_OUTPUT_HANDLE);
  SetConsoleCursorPosition(handle,coord);
}

// 為主循環做準備；
void GeneralSearch(TYPE Type, HEURISTIC heuristic) {
  CState *Solution;
  int DepthLimit=0;
  switch(heuristic) {
    case NOT_USED:
      // Breadth First Queing Type
      if(Type == BREADTH_FIRST) {
        PushSide = RIGHT;
        PopSide = LEFT;
      }
      else {
        // Depth First Search
        cout << "Enter a Depth Limit :";
        cin >> DepthLimit;
        PushSide = RIGHT;
        PopSide = RIGHT;
      }
      break;
    case MANHATTAN_DISTANCE:
      PushSide = RIGHT;
      PopSide = RIGHT;
      break;
    case WRONG_TILES:
      PushSide = RIGHT;
      PopSide = RIGHT;
  }

  //將最初的狀態放入鏈表中；
  MainQue.Push(PushSide, new CState());
  //調用主循環
  Solution = GeneralExpand(DepthLimit, heuristic);
  // returns pointer to soution.
  // or null pointer (failure)
  if(Solution != 0) {
    cout << "FOUND SOLUTION!" << endl;
    ShowSolution(Solution);
    cout << "DONE" << endl;
  }
  else {
    //Fail
    cout << "FAIL" << endl;
  }
}

// 主循環函數(YEP, it BITES !)
CState* GeneralExpand(int DepthLimit, HEURISTIC heuristic) {
  CState *CurrentState = 0;
  CState *TempState = 0;
  int LastDepth=-1;
  if(PushSide == PopSide) {cout << "THINKING...please wait." << endl;}
    // Main loop
    while(!MainQue.IsListEmpty()) {
      if(heuristic == NOT_USED) {
        CurrentState = MainQue.Pop(PopSide);
      }
      else {
        CurrentState = MainQue.PopBestByHeuristics(heuristic);
      }
      PrevStates.Push(RIGHT, CurrentState); 
      //對取出的狀態保持跟蹤(需要防止內存)
      /*可以讓用戶規定結束游戲所需要移動的最大步數，這僅限于"breadth first only"方法*/
      if(LastDepth < CurrentState->GetDepth() && PushSide != PopSide) {
          LastDepth = CurrentState->GetDepth();
          cout << "EXPANDING LEVEL " << LastDepth << endl;
      }

      // 如果當前節點沒有超出depth限制
      if((CurrentState->GetDepth() < DepthLimit) || (DepthLimit == 0 )) {
        if((CurrentState->CanBlankMove(NORTH)) && (CurrentState->GetLastOperator() != SOUTH)) {
          TempState = new CState(CurrentState, NORTH);
          MainQue.Push(PushSide, TempState);
          Expanded++;
          if(TempState->Solution()) { 
            return TempState; 
          }
        }

        if((CurrentState->CanBlankMove(EAST)) && (CurrentState->GetLastOperator() != WEST)) {
          TempState = new CState(CurrentState, EAST);
          MainQue.Push(PushSide, TempState);
          Expanded++;
          if(TempState->Solution()) { 
            return TempState; 
          }
        }

      if((CurrentState->CanBlankMove(SOUTH)) && (CurrentState->GetLastOperator() != NORTH)) {
        TempState = new CState(CurrentState, SOUTH);
        MainQue.Push(PushSide, TempState);
        Expanded++;
        if(TempState->Solution()) { 
          return TempState; 
        }
      }

      if((CurrentState->CanBlankMove(WEST)) && (CurrentState->GetLastOperator() != EAST)) {
        TempState = new CState(CurrentState, WEST);
        MainQue.Push(PushSide, TempState);
        Expanded++;
        if(TempState->Solution()) { 
          return TempState; 
        }
      }
    }
  }
  return 0;
}