#include "MinMaxNodes.h"
#include <stdio.h>
#include "patterns.h"
#include <time.h>
#include <stdlib.h>


#define XTURN 1
#define OTURN 0

#define XWINS 1
#define OWINS -1
#define TIE   0
#define NOWINS 7

unsigned long iterations = 0;

int GenerateChildren(Node * _parent, int _turn);
int CheckForWinner(unsigned long _xLocation, unsigned long _oLocation);
void PropagateScore(Node * _node, int _winner);
int PlayGame(Node * _node, int _turn);
void DumpBoard(unsigned long _x, unsigned long _o);
void Stop();

int main()
{
  srand(time(0));
  Node * root = new Node(0);
  root->xLocation = 0;
  root->oLocation = 0;
  printf("Generation MinMaxTree...\n");
  int rootChildren = GenerateChildren(root, XTURN); 
  printf ("MinMaxTree Complete: %ld\n", iterations);
  printf("Playing Game...\n");
  int winner = PlayGame(root, XTURN);

}
int GenerateChildren(Node * _parent, int _turn)
{
  unsigned long xLocation = _parent->xLocation;
  unsigned long oLocation = _parent->oLocation;
  int totalChildren = 0;
  int tokenPlaced = 0;
  int winner = NOWINS;
  for (int x = 0; x<9; x++)
  {
    //printf("checking %d: \n", x);
    if (!(xLocation & 1<<x) && !(oLocation & 1<<x))
    {
      //printf("VALID\n");
      tokenPlaced = 1;
      iterations++;
      //place token
      _parent->children[totalChildren] = new Node (_parent);       
      if (_turn == XTURN)
      {
        //printf("Placing X token @ %d \n", x);
        _parent->children[totalChildren]->oLocation = oLocation;
        _parent->children[totalChildren]->xLocation = xLocation | 1<<x;
//        printf("%ld:\n", _parent->children[totalChildren]->xLocation);
      }
      else
      {
//        printf("Placing O token @ %d \n", x);
        _parent->children[totalChildren]->xLocation = xLocation;
        _parent->children[totalChildren]->oLocation = oLocation | 1<<x;
      }
      winner = CheckForWinner(_parent->children[totalChildren]->xLocation,
                             _parent->children[totalChildren]->oLocation);
      if (winner != NOWINS)
      {
//        printf("WINNER: %d\n\n\n", winner);
//        if (winner == TIE)
//         printf("TIE\n");
        //Do Something - propagate score to parents...

        _parent->children[totalChildren]->minScore = winner;
        _parent->children[totalChildren]->maxScore = winner;
        _parent->children[totalChildren]->complete = 1;
        PropagateScore(_parent, winner);
      }
      else
      {
        int nextTurn = 0;
        if (_turn == XTURN)
          nextTurn = OTURN;
        else 
          nextTurn = XTURN; 
        GenerateChildren(_parent->children[totalChildren], nextTurn);
      }
      totalChildren ++;
    }
  }
  if (tokenPlaced == 0)
  {
    printf("Error no place to go\n");
    DumpBoard(_parent->xLocation, _parent->oLocation);
    Stop();
  }
  return totalChildren;
}

int CheckForWinner(unsigned long _xLocation, unsigned long _oLocation)
{
//  printf("__CheckForWinner__\n");
//  DumpBoard(_xLocation, _oLocation);
  
  for (int x = 0; x< TOTAL_WIN_PATTERNS; x++)
  {
    if ((_xLocation & WINPATTERNS[x]) == WINPATTERNS[x])
    {
      //printf("XWINS\n");
      return XWINS;
    }
    if ((_oLocation & WINPATTERNS[x]) == WINPATTERNS[x])
    {
      //printf("OWINS\n");
      return OWINS;
    }
  }
  if ((_xLocation | _oLocation) == FULL_CARD)
  {
    //printf("TIE\n");
    return TIE;
  }
  //printf("Nobody wins\n");
  return NOWINS;
}
void PropagateScore(Node * _node, int _winner)
{
  if (_winner > _node->maxScore)
    _node->maxScore = _winner;
  if (_winner < _node->minScore)
    _node->minScore = _winner;
  if (_node->parent)
    PropagateScore(_node->parent, _winner);

}
int PlayGame(Node * _node, int _turn)
{
  int xWinCount = 0; 
  int oWinCount = 0;
  int tieCount = 0;

  int xWins[9];
  int oWins[9];
  int ties[9];

  int nextTurn;
  if (_turn == XTURN) 
    nextTurn = OTURN;
  else
    nextTurn = XTURN;

  for (int x = 0; x<9; x++)
  {
    xWins[x] = -1;
    oWins[x] = -1;
    ties[x] =  -1;

  }

  for (int x = 0; x<9; x++)
  {
    if (_node->children[x])
    {
      if (_node->children[x]->maxScore == XWINS)
      {
//        printf("XWINS: %d: %d\n", xWinCount, x);
        xWins[xWinCount] = x;
        xWinCount++;
      }

      if (_node->children[x]->minScore == OWINS)
      {
//        printf("OWINS\n");
        oWins[oWinCount] = x;
        oWinCount++;
      }
    
      if (_node->children[x]->maxScore == TIE)
      {
//        printf("TIE\n");
        ties[tieCount] = x;
        tieCount++;
      }
      else if (_node->children[x]->minScore == TIE)
      {
//        printf("TIE2\n");
       ties[tieCount] = x;
        tieCount++;
      }
    }
  }

  int nextPosition;
  if (_turn == XTURN) //minimize
  {
    if (oWinCount > 0)
    {
//      nextPosition = oWins[getrandom(0,oWinCount-1)];
      nextPosition = oWins[0];
      if (_node->children[nextPosition]->complete)
      {
        printf("Game Over\n");
        DumpBoard(_node->children[nextPosition]->xLocation, 
                  _node->children[nextPosition]->oLocation);
      }
      else
        PlayGame(_node->children[nextPosition], nextTurn); 
    }
    else if (tieCount > 0)
    {
//      nextPosition = ties[getrandom(0,tieCount-1)];
      nextPosition = ties[0];
      if (_node->children[nextPosition]->complete)
      {
        printf("Game Over\n");
        DumpBoard(_node->children[nextPosition]->xLocation, 
                  _node->children[nextPosition]->oLocation);
      }
      else
        PlayGame(_node->children[nextPosition], nextTurn); 
    }
    else if (xWinCount > 0)
    {
//      nextPosition = xWins[getrandom(0,xWinCount-1)];
      nextPosition = xWins[0];
      if (_node->children[nextPosition]->complete)
      {
        printf("Game Over\n");
        DumpBoard(_node->children[nextPosition]->xLocation, 
                  _node->children[nextPosition]->oLocation);
     }
      else
        PlayGame(_node->children[nextPosition], nextTurn); 
    }
    else
    {
      DumpBoard(_node->xLocation, _node->oLocation);
      printf("MAJOR ISSUE, NO WHERE TO GO\n");
    }
  }
  else  //maximize
  {
    DumpBoard(_node->xLocation, _node->oLocation);
    printf("Place a token\n");
    int move;
    scanf("%d", &move);
    unsigned long tempLocation = _node->oLocation;
    tempLocation |= 1<<move;
    
    for (int x = 0; x<9; x++)
    {
      if (_node->children[x])
      {
        if (_node->children[x]->oLocation == tempLocation)
        {
          PlayGame(_node->children[x], nextTurn); 
        }


      }
    }
#if 0
    if (xWinCount > 0)
    {
//      nextPosition = xWins[getrandom(0,xWinCount-1)];
      nextPosition = xWins[0];
      if (_node->children[nextPosition]->complete)
      {
        printf("Game Over\n");
        DumpBoard(_node->children[nextPosition]->xLocation, 
                  _node->children[nextPosition]->oLocation);
      }
      else
        PlayGame(_node->children[nextPosition], nextTurn); 
    }
    else if (tieCount > 0)
    {
//      nextPosition = ties[getrandom(0,tieCount-1)];
      nextPosition = ties[0];
      if (_node->children[nextPosition]->complete)
      {
        printf("Game Over\n");
        DumpBoard(_node->children[nextPosition]->xLocation, 
                  _node->children[nextPosition]->oLocation);
      }
      else
        PlayGame(_node->children[nextPosition], nextTurn); 
    }
    else if (oWinCount > 0)
    {
//      nextPosition = oWins[getrandom(0,oWinCount-1)];
      nextPosition = oWins[0];
      if (_node->children[nextPosition]->complete)
      {
        printf("Game Over\n");
        DumpBoard(_node->children[nextPosition]->xLocation, 
                  _node->children[nextPosition]->oLocation);
      }
      else
        PlayGame(_node->children[nextPosition], nextTurn); 
    }
    else
    {
      printf("MAJOR ISSUE, NO WHERE TO GO\n");
      DumpBoard(_node->xLocation, _node->oLocation);
    }

#endif
  }
  return 1;
}
void DumpBoard(unsigned long _x, unsigned long _o)
{
  for (int x = 0; x<9; x++)
  {
    if (_x & 1<<x)
      printf("X");
    else if (_o & 1<<x)
      printf("O");
    else
      printf(" ");
    if (x==2 || x==5 || x==8)
      printf("\n");
  }
  printf("\n");
  fflush(stdout);
}
void Stop()
{
  exit(0);
}