#include <string>
#include <iostream>
#include <sstream>
#include <math.h>
#include <list>
#include "Space.h"
#include "Piece.h"
#include "Board.h"
using namespace std;



bool SucceedInserting(Piece* piece,Board* board,int icol,int irow){
  while (board->InsertPiece(piece,icol,irow)!=0){     // doesnt fit in this configuration.  Try rotating
    if (piece->RotateCounterClockwise()!=0){      // we have tried all rotations at this centerpoint.  Try recentering
      if (piece->RecenterAtNextBlackSquare()!=0){  // that's it.  We have tried everything.  It does not fit at all
	return false;                              // means doesn't fit
      }
    }
  }
  return true;  // that means there was no problem.  The Piece was inserted at the next available Space on the Board
}

// in this following function, we increment the configuration once first, then go to the SucceedInserting()
bool ReconfigureThenTryInserting(Piece* piece,Board* board,int icol, int irow){
  // cout << "--6\n";
  if (piece->RotateCounterClockwise()!=0){      // we have tried all rotations at this centerpoint.  Try recentering
    // cout << "--6.1\n";
    if (piece->RecenterAtNextBlackSquare()!=0){  // that's it.  We have tried everything.  It does not fit at all
      // cout << "--6.2\n";
      return false;                              // means doesn't fit
    }
  }
  // cout << "--7\n";
  return SucceedInserting(piece,board,icol,irow);
}

bool IncrementConfiguration(Piece* p){
  if (p->RotateCounterClockwise()!=0){
    if (p->RecenterAtNextBlackSquare()!=0){
      return false;
    }
  }
  return true;
}




int main(){
  Board TheBoard;
  cout << "\n Empty Board\n";
  TheBoard.Draw();

  vector<Piece*> AllPieces;


  Space* sp;
  Piece* thePiece;

  // define Piece#1
  thePiece = new Piece();
  thePiece->SetId(1);
  sp = new Space(black,0,0);  // first Square should always be at 0,0 then others are relative to it
  sp->SetOccupied();  sp->SetBorder(0);  sp->SetBorder(1);  sp->SetBorder(2);
  thePiece->AddSquare(sp);
  sp = new Space(red,-1,0);
  sp->SetOccupied();  sp->SetBorder(0);  sp->SetBorder(3);
  thePiece->AddSquare(sp);
  sp = new Space(black,-1,-1);
  sp->SetOccupied();  sp->SetBorder(1);  sp->SetBorder(3);
  thePiece->AddSquare(sp);
  sp = new Space(red,-1,-2);
  sp->SetOccupied();  sp->SetBorder(1);  sp->SetBorder(2);  sp->SetBorder(3);
  thePiece->AddSquare(sp);
  AllPieces.push_back(thePiece);
  

  // define Piece#2
  thePiece = new Piece();
  thePiece->SetId(2);
  sp = new Space(black,0,0);  // first Square should always be at 0,0 then others are relative to it
  sp->SetOccupied();  sp->SetBorder(0);  sp->SetBorder(1);  sp->SetBorder(3);
  thePiece->AddSquare(sp);
  sp = new Space(red,0,-1);
  sp->SetOccupied();  sp->SetBorder(3);
  thePiece->AddSquare(sp);
  sp = new Space(black,1,-1);
  sp->SetOccupied();  sp->SetBorder(0);  sp->SetBorder(1); sp->SetBorder(2);
  thePiece->AddSquare(sp);
  sp = new Space(black,0,-2);
  sp->SetOccupied();  sp->SetBorder(1); sp->SetBorder(3);
  thePiece->AddSquare(sp);
  sp = new Space(red,0,-3);
  sp->SetOccupied();  sp->SetBorder(1);  sp->SetBorder(2);  sp->SetBorder(3);
  thePiece->AddSquare(sp);
  AllPieces.push_back(thePiece);
  

  // define Piece#3
  thePiece = new Piece();
  thePiece->SetId(3);
  sp = new Space(black,0,0);  // first Square should always be at 0,0 then others are relative to it
  sp->SetOccupied();  sp->SetBorder(2);  sp->SetBorder(3);
  thePiece->AddSquare(sp);
  sp = new Space(red,0,1);
  sp->SetOccupied();  sp->SetBorder(0); sp->SetBorder(1); sp->SetBorder(3);
  thePiece->AddSquare(sp);
  sp = new Space(red,1,0);
  sp->SetOccupied();  sp->SetBorder(0); sp->SetBorder(1);
  thePiece->AddSquare(sp);
  sp = new Space(black,1,-1);
  sp->SetOccupied();   sp->SetBorder(1); sp->SetBorder(3);
  thePiece->AddSquare(sp);
  sp = new Space(red,1,-2);
  sp->SetOccupied();  sp->SetBorder(1);  sp->SetBorder(2);  sp->SetBorder(3);
  thePiece->AddSquare(sp);
  AllPieces.push_back(thePiece);
  

  // define Piece#4  (note #4 and #12 are identical pieces)
  thePiece = new Piece();
  thePiece->SetId(4);
  sp = new Space(black,0,0);  // first Square should always be at 0,0 then others are relative to it
  sp->SetOccupied();  sp->SetBorder(0); sp->SetBorder(2);  sp->SetBorder(3);
  thePiece->AddSquare(sp);
  sp = new Space(red,1,0);
  sp->SetOccupied();  sp->SetBorder(0); sp->SetBorder(1);
  thePiece->AddSquare(sp);
  sp = new Space(black,1,-1);
  sp->SetOccupied();   sp->SetBorder(1); sp->SetBorder(3);
  thePiece->AddSquare(sp);
  sp = new Space(red,1,-2);
  sp->SetOccupied(); sp->SetBorder(2);  sp->SetBorder(3);
  thePiece->AddSquare(sp);
  sp = new Space(black,2,-2);
  sp->SetOccupied();  sp->SetBorder(0);  sp->SetBorder(1); sp->SetBorder(2);
  thePiece->AddSquare(sp);
  AllPieces.push_back(thePiece);
  

  // define Piece#5
  thePiece = new Piece();
  thePiece->SetId(5);
  sp = new Space(black,0,0);  // first Square should always be at 0,0 then others are relative to it
  sp->SetOccupied();  sp->SetBorder(3);
  thePiece->AddSquare(sp);
  sp = new Space(red,0,1);
  sp->SetOccupied();  sp->SetBorder(0); sp->SetBorder(1); sp->SetBorder(3);
  thePiece->AddSquare(sp);
  sp = new Space(red,1,0);
  sp->SetOccupied();  sp->SetBorder(0); sp->SetBorder(1);
  thePiece->AddSquare(sp);
  sp = new Space(red,0,-1);
  sp->SetOccupied();  sp->SetBorder(2); sp->SetBorder(3);
  thePiece->AddSquare(sp);
  sp = new Space(black,1,-1);
  sp->SetOccupied();  sp->SetBorder(2);
  thePiece->AddSquare(sp);
  sp = new Space(red,2,-1);
  sp->SetOccupied();  sp->SetBorder(0); sp->SetBorder(1); sp->SetBorder(2);
  thePiece->AddSquare(sp);
  AllPieces.push_back(thePiece);
  

  // define Piece#6
  thePiece = new Piece();
  thePiece->SetId(6);
  sp = new Space(black,0,0);  // first Square should always be at 0,0 then others are relative to it
  sp->SetOccupied();  sp->SetBorder(0);  sp->SetBorder(1);  sp->SetBorder(3);
  thePiece->AddSquare(sp);
  sp = new Space(red,0,-1);
  sp->SetOccupied();  sp->SetBorder(1); sp->SetBorder(3);
  thePiece->AddSquare(sp);
  sp = new Space(black,0,-2);
  sp->SetOccupied(); sp->SetBorder(3);
  thePiece->AddSquare(sp);
  sp = new Space(red,0,-3);
  sp->SetOccupied();  sp->SetBorder(1);  sp->SetBorder(2);  sp->SetBorder(3);
  thePiece->AddSquare(sp);
  sp = new Space(red,1,-2);
  sp->SetOccupied();  sp->SetBorder(0);  sp->SetBorder(1); sp->SetBorder(2);
  thePiece->AddSquare(sp);
  AllPieces.push_back(thePiece);
  

  // define Piece#7
  thePiece = new Piece();
  thePiece->SetId(7);
  sp = new Space(black,0,0);  // first Square should always be at 0,0 then others are relative to it
  sp->SetOccupied();  sp->SetBorder(0);  sp->SetBorder(1);
  thePiece->AddSquare(sp);
  sp = new Space(red,0,-1);
  sp->SetOccupied();  sp->SetBorder(1); sp->SetBorder(3);
  thePiece->AddSquare(sp);
  sp = new Space(black,0,-2);
  sp->SetOccupied();  sp->SetBorder(1); sp->SetBorder(3);
  thePiece->AddSquare(sp);
  sp = new Space(red,0,-3);
  sp->SetOccupied();  sp->SetBorder(1);  sp->SetBorder(2);  sp->SetBorder(3);
  thePiece->AddSquare(sp);
  sp = new Space(red,-1,0);
  sp->SetOccupied();  sp->SetBorder(0);  sp->SetBorder(2); sp->SetBorder(3);
  thePiece->AddSquare(sp);
  AllPieces.push_back(thePiece);
  

  // define Piece#8
  thePiece = new Piece();
  thePiece->SetId(8);
  sp = new Space(black,0,0);  // first Square should always be at 0,0 then others are relative to it
  sp->SetOccupied();  sp->SetBorder(0);  sp->SetBorder(1);  sp->SetBorder(3);
  thePiece->AddSquare(sp);
  sp = new Space(red,0,-1);
  sp->SetOccupied();  sp->SetBorder(1); sp->SetBorder(2);
  thePiece->AddSquare(sp);
  sp = new Space(black,-1,-1);
  sp->SetOccupied();  sp->SetBorder(0); sp->SetBorder(3);
  thePiece->AddSquare(sp);
  sp = new Space(red,-1,-2);
  sp->SetOccupied();  sp->SetBorder(1);  sp->SetBorder(3);
  thePiece->AddSquare(sp);
  sp = new Space(black,-1,-3);
  sp->SetOccupied();  sp->SetBorder(1);  sp->SetBorder(2); sp->SetBorder(3);
  thePiece->AddSquare(sp);
  AllPieces.push_back(thePiece);
  

  // define Piece#9
  thePiece = new Piece();
  thePiece->SetId(9);
  sp = new Space(black,0,0);  // first Square should always be at 0,0 then others are relative to it
  sp->SetOccupied();  sp->SetBorder(1);
  thePiece->AddSquare(sp);
  sp = new Space(red,0,1);
  sp->SetOccupied();  sp->SetBorder(0); sp->SetBorder(1); sp->SetBorder(3);
  thePiece->AddSquare(sp);
  sp = new Space(red,0,-1);
  sp->SetOccupied();  sp->SetBorder(1);
  thePiece->AddSquare(sp);
  sp = new Space(black,0,-2);
  sp->SetOccupied();  sp->SetBorder(1); sp->SetBorder(2); sp->SetBorder(3);
  thePiece->AddSquare(sp);
  sp = new Space(red,-1,0);
  sp->SetOccupied();  sp->SetBorder(0);  sp->SetBorder(3);
  thePiece->AddSquare(sp);
  sp = new Space(black,-1,-1);
  sp->SetOccupied();  sp->SetBorder(2); sp->SetBorder(3);
  thePiece->AddSquare(sp);
  AllPieces.push_back(thePiece);
  

  // define Piece#10
  thePiece = new Piece();
  thePiece->SetId(10);
  sp = new Space(black,0,0);  // first Square should always be at 0,0 then others are relative to it
  sp->SetOccupied();  sp->SetBorder(0);  sp->SetBorder(2);  sp->SetBorder(3);
  thePiece->AddSquare(sp);
  sp = new Space(red,1,0);
  sp->SetOccupied();  sp->SetBorder(0); sp->SetBorder(1);
  thePiece->AddSquare(sp);
  sp = new Space(black,1,-1);
  sp->SetOccupied();  sp->SetBorder(1); sp->SetBorder(3);
  thePiece->AddSquare(sp);
  sp = new Space(red,1,-2);
  sp->SetOccupied();  sp->SetBorder(1); sp->SetBorder(3);
  thePiece->AddSquare(sp);
  sp = new Space(black,1,-3);
  sp->SetOccupied();  sp->SetBorder(1); sp->SetBorder(2); sp->SetBorder(3);
  thePiece->AddSquare(sp);
  AllPieces.push_back(thePiece);
  

  // define Piece#11
  thePiece = new Piece();
  thePiece->SetId(11);
  sp = new Space(black,0,0);  // first Square should always be at 0,0 then others are relative to it
  sp->SetOccupied();  sp->SetBorder(0);  sp->SetBorder(1);  sp->SetBorder(3);
  thePiece->AddSquare(sp);
  sp = new Space(red,0,-1);
  sp->SetOccupied();
  thePiece->AddSquare(sp);
  sp = new Space(black,0,-2);
  sp->SetOccupied();
  thePiece->AddSquare(sp);
  sp = new Space(red,0,-3);
  sp->SetOccupied();  sp->SetBorder(1);  sp->SetBorder(2);  sp->SetBorder(3);
  thePiece->AddSquare(sp);
  sp = new Space(black,-1,-1);
  sp->SetOccupied(); sp->SetBorder(0);  sp->SetBorder(3);
  thePiece->AddSquare(sp);
  sp = new Space(red,-1,-2);
  sp->SetOccupied();  sp->SetBorder(2);  sp->SetBorder(3);
  thePiece->AddSquare(sp);
  sp = new Space(black,1,-1);
  sp->SetOccupied(); sp->SetBorder(0);  sp->SetBorder(1);
  thePiece->AddSquare(sp);
  sp = new Space(red,1,-2);
  sp->SetOccupied();  sp->SetBorder(1);  sp->SetBorder(2);
  thePiece->AddSquare(sp);
  AllPieces.push_back(thePiece);
  

  // define Piece#12  (note #4 and #12 are identical pieces)
  thePiece = new Piece();
  thePiece->SetId(12);
  sp = new Space(black,0,0);  // first Square should always be at 0,0 then others are relative to it
  sp->SetOccupied();  sp->SetBorder(0); sp->SetBorder(2);  sp->SetBorder(3);
  thePiece->AddSquare(sp);
  sp = new Space(red,1,0);
  sp->SetOccupied();  sp->SetBorder(0); sp->SetBorder(1);
  thePiece->AddSquare(sp);
  sp = new Space(black,1,-1);
  sp->SetOccupied();   sp->SetBorder(1); sp->SetBorder(3);
  thePiece->AddSquare(sp);
  sp = new Space(red,1,-2);
  sp->SetOccupied(); sp->SetBorder(2);  sp->SetBorder(3);
  thePiece->AddSquare(sp);
  sp = new Space(black,2,-2);
  sp->SetOccupied();  sp->SetBorder(0);  sp->SetBorder(1); sp->SetBorder(2);
  thePiece->AddSquare(sp);
  AllPieces.push_back(thePiece);

  


  list<Piece*> PiecesOnBoard;
  list<Piece*> PiecesOffBoard;
  // none of the Pieces, as yet, are on the Board
  for(vector<Piece*>::iterator iter = AllPieces.begin(); iter < AllPieces.end(); iter++){
    PiecesOffBoard.push_back(*iter);
  }
  //  for (int ipp=0; ipp<AllPieces.size(); ipp++){
  //    PiecesOffBoard.push_back(AllPieces[ipp]);
  //  }
  cout << "Number of Pieces sitting to the side is " << PiecesOffBoard.size() << endl;
  cout << "Number of Pieces sitting on the Board is " << PiecesOnBoard.size() << endl;

  
  //---------------- Here comes just some demonstration for human visualaztion/debugging -------------------------
  cout << "\n Empty Board\n";
  TheBoard.Draw();
  for (int ip=0; ip<AllPieces.size(); ip++){
    cout << "\n Piece Number " << AllPieces[ip]->GetId() << endl;
    TheBoard.InsertPiece(AllPieces[ip],3,3);
    TheBoard.Draw();
    AllPieces[ip]->RemoveFromBoard(&TheBoard);
  }
  cout << "\n Empty Board\n";
  TheBoard.Draw();


  int look;
  unsigned int nRot;
  /*
    cout << "Enter which piece you want to see [negative to quit] and # times rotated CCW: ";
    cin >> look >> nRot;
    look--;  // because id = index+1
    while (look >= 0){
    cout << "\n Piece Number " << AllPieces[look]->GetId() << endl;
    AllPieces[look]->RotateCounterClockwise(nRot);
    if (TheBoard.InsertPiece(AllPieces[look],3,3) != 0){  // if it returns non-zero, then piece didn't fit
    cout << "Piece did not fit on the Board!\n";
    }
    TheBoard.Draw();
    AllPieces[look]->RemoveFromBoard(&TheBoard);
    cout << "Enter which piece you want to see [negative to quit] and # times rotated CCW: ";
    cin >> look >> nRot;
    look--;  // because id = index+1
    }
  */
  

  //-----

  cout << "\n Now we are gonna watch a piece rotate all the way around\n";
  cout << "and then recenter and rotate all the way around, etc\n";
  cout << "until it has recentered around all of the black ones\n";
  //  cout << "\n Choose a Piece [1..12]";
  //  cin >> look;
  look = 1;
  look--;
  cout << "Here we go....\n\n";

  int junk;

  int triedAllBlacks=0;
  while (triedAllBlacks == 0){
    int rotDone=0;
    while (rotDone == 0){
      if (TheBoard.InsertPiece(AllPieces[look],3,3) != 0){  // if it returns non-zero, then piece didn't fit
	cout << "Piece did not fit on the Board!\n";
      }
      cout << "Piece " << AllPieces[look]->GetId() << "\n";
      TheBoard.Draw();
      //      cout << "Enter any number to continue: ";
      //      cin >> junk;
      AllPieces[look]->RemoveFromBoard(&TheBoard);
      
      rotDone = AllPieces[look]->RotateCounterClockwise();  cout << " ...rotating... ";
    }
    cout << "\n All orientations finished\n";
    triedAllBlacks = AllPieces[look]->RecenterAtNextBlackSquare();  cout << " ...recentering (translating)... ";
  }
  cout << "\n All orientations and recenterings finished\n";

  cout << "\n ===================================== \n";
  cout << "OK lets do this.  We will now show all the ways in which a Piece can fit on Board touching\n"
       << "  lower left (black) square [icol=irow=0]\n";
  cout << "You choose which Piece to look at : ";
  cin >> look;
  look--;

  triedAllBlacks=0;
  while (triedAllBlacks == 0){
    int rotDone=0;
    while (rotDone == 0){
      if (TheBoard.InsertPiece(AllPieces[look],0,0)==0){     // it fit and didn't overlap with anything
	cout << "\n Here is one which works (Piece " << AllPieces[look]->GetId() << ")" << endl;
	TheBoard.Draw();
	AllPieces[look]->RemoveFromBoard(&TheBoard);
      }
      rotDone = AllPieces[look]->RotateCounterClockwise(); cout << "...rotating...";
    }
    triedAllBlacks = AllPieces[look]->RecenterAtNextBlackSquare();  cout << " ...recentering (translating)... ";
  }

  cout << endl;

  //-------------------------- end of visualization/debugging section -----------------------------

  //---- Get real.  Solve the puzzle

  //  These are the lists defined above:
  //  list<Piece*> PiecesOnBoard;
  //  list<Piece*> PiecesOffBoard;
  //

  cout << "\n\n ========================================================= \n";
  cout << " ==================== Here we go ========================= \n";
  cout << " ========================================================= \n\n";

  int junky;


  list<Piece*>::iterator pPieceBeingConsidered;  // points to list PiecesOffBoard;

  pPieceBeingConsidered = PiecesOffBoard.begin();
  while (PiecesOffBoard.size() !=0){
    int icol,irow;
    //    pPieceBeingConsidered = PiecesOffBoard.begin();
    while (pPieceBeingConsidered != PiecesOffBoard.end()){
      icol = TheBoard.NextAvailableBlackSpace().Column();
      irow = TheBoard.NextAvailableBlackSpace().Row();
      cout << "Piece under consideration is " << (*pPieceBeingConsidered)->GetId() << " at (" << icol << "," << irow << ")\n";
      //-----      cout << "Enter a number to continue: ";  cin >> junky;

      // SucceedInserting tries all possible ways to Insert the Piece which weren't already tried
      if (SucceedInserting(*pPieceBeingConsidered,&TheBoard,icol,irow)){   // then this piece fits here
	if (TheBoard.AnyRedOrphans()){                                     // check it made any orphans.
	  cout << " \n Orphan below ! \n Orphan below ! \n Orphan below ! \n Orphan below ! \n";
	  TheBoard.Draw();  //------- cout << "Enter a number to continue: ";  cin >> junky;

	  (*pPieceBeingConsidered)->RemoveFromBoard(&TheBoard);              // remove it
	  if (IncrementConfiguration(*pPieceBeingConsidered)){             // jiggle configuration
	    /* no-op */                                                    // if it has more configurations, do nothing.  loop will look at them
	  }
	  else{
	    pPieceBeingConsidered++;                                       // but if it's done, then move to the next Piece
	  }
	}
	else{                                                              // no orphans were created
	  PiecesOnBoard.push_back(*pPieceBeingConsidered);
	  PiecesOffBoard.erase(pPieceBeingConsidered);
	  cout << "Succeeded in placing Piece " << (*pPieceBeingConsidered)->GetId() << ". It is the " <<
	    PiecesOnBoard.size() << "th Piece on the Board.  " << PiecesOffBoard.size() << " still on the side\n";
	  TheBoard.Draw();  //------ cout << "Enter a number to continue: ";  cin >> junky;
	  pPieceBeingConsidered = PiecesOffBoard.begin();    // start at beginning again.
	}
      }
      else{                                                               // this is if the Piece didn't fit at all
	pPieceBeingConsidered++;
	cout << "Nope just didn't fit at all\n";
	TheBoard.Draw();  //------ cout << "Enter a number to continue: ";  cin >> junky;
      }
    }

    cout << " Dead end \n";
    TheBoard.Draw();  //------- cout << "Enter a number to continue: ";  cin >> junky;

    // OK if we make it here then we've hit a dead end, need to start undoing what we've done

    PiecesOnBoard.back()->RemoveFromBoard(&TheBoard);
    PiecesOffBoard.push_front(PiecesOnBoard.back());
    pPieceBeingConsidered = PiecesOffBoard.begin();
    if (!(IncrementConfiguration(PiecesOnBoard.back()))) //this was last try for this guy.  Put pointer past him
      pPieceBeingConsidered++;
    /*
      if (IncrementConfiguration(PiecesOnBoard.back())){      // this last piece was not in its last configuration.  try it again
      PiecesOffBoard.push_front(PiecesOnBoard.back());
      }
      else{
      PiecesOffBoard.push_back(PiecesOnBoard.back());      // no, it was done.  put it at the end
      }
    */

    PiecesOnBoard.pop_back();
  
  }

  
  return 0;

}