
#include "globals.h"

#define PRINT_DOES_X_WIN_INFO

// If defined we just immediately return from each function with
//   a value of -1. (In other words no winner yet.)
//#define NOTHING

// If defined don't pack any protected moves onto the board.
//#define NO_PROT

// If defined pretend all (unpacked) squares are available to opponent.
//#define NO_UNUSED

// If defined pretend we didn't find any vulnerable moves with a prot square.
//#define NO_VULN_W_PROT

// If defined pretend we didn't find any vulnerable moves with a prot square.
//#define NO_VULN_TYPE_1

// If defined pretend there were no vulnerable moves (note this also
//    means NO_VULN_W_PROT).
//#define NO_VULN

// If defined don't look for safe options.
//#define NO_SAFE_OPT

//#################################################################
// This function tries to pack as many 'protective' areas onto
//  the board as it can. (no guarantee of optimality).
//#################################################################
static inline void
pack_prot(u32bit tmp_board[32], s32bit player, s32bit *prot)
{
  s32bit r = 0, p = 0; //row, and number of prot. areas we have placed.
  
  u32bit tmp, inter, walls;
  
  for(r = 0; r < g_board_size[player]; r++){
    // set bit at each position where there is interference.
    inter = (tmp_board[r] | tmp_board[r+1] | tmp_board[r+2] | tmp_board[r+3]
             | g_board[player][r+1] | g_board[player][r+2]);
    inter = (inter >> 1) | inter; 
    
    // set bit at each position which there is a wall.
    walls = ( ((g_board[player][r] >> 1) & g_board[player][r])
              | ((g_board[player][r+3] >> 1) & g_board[player][r+3]) );
    
    // combine (bit set at each position which we can place a prot. area).
    inter = walls & ~inter;
    
    // process the positions.
    while(inter){
      tmp = (inter & -inter);        // least sig bit of m
      inter &= ~(tmp | (tmp << 1));  // remove bit and next bit.

      tmp_board[r+1] |= tmp | (tmp << 1); //record where we put
      tmp_board[r+2] |= tmp | (tmp << 1); // the protective square.

      p++; // count it.
    }
  }
  
  *prot = p;
}


//#################################################################
// This function tries to pack as many 'vuln. type 1 and 2' areas
//  onto the board as it can. (no guarantee of optimality).
// It also counts the number of unused squares.
//#################################################################
static void
pack_vuln(u32bit tmp_board[32], s32bit player,
          s32bit *vuln2, s32bit *vuln2_w_prot,
          s32bit *vuln1, s32bit *vuln1_w_prot,
          s32bit *unused) //, s32bit print)
{
  u32bit curr_row, adj_rows, next_prev_row;
  u32bit tmp = 0, tmp_;

  s32bit v2 = 0, v2_p = 0, v1 = 0, v1_p = 0, u = 0;
  
  s32bit r, state;
  u32bit s_v = 0; //start of vulnerable
  
  for(r = 0; r < g_board_size[player]; r++){
    next_prev_row  = tmp_board[r];
    next_prev_row |= ~(g_board[player][r+2] | (g_board[player][r+2] << 1));
    next_prev_row |= ~(g_board[player][r+2] | (g_board[player][r+2] >> 1));

    curr_row = ~(g_board[player][r+1] | tmp_board[r+1]);
    adj_rows = g_board[player][r] & g_board[player][r+2];
    state = 0;
    
    //========================================================
    // Three types of squares, prot, empty, occ.
    //
    // state = 0
    // if(prot)  -> state = 1
    // if(empty) -> state = 2, c_t = c,
    // if(occ)   -> state = 0
    //
    // state = 1
    // if(prot)  -> state = 0, safe++
    // if(empty) -> state = 0, v_p++, mark(c-1)
    // if(occ)   -> state = 0, unu++
    //
    // state = 2
    // if(prot)  -> state = 3,
    // if(empty) -> state = 0, vuln++, mark(c_t)
    // if(occ)   -> state = 0,
    //
    // state = 3
    // if(prot)  -> state = 4, safe++
    // if(empty) -> state = 2, v_p++, mark(c_t), c_t = c
    // if(occ)   -> state = 0, v_p++, mark(c_t)
    //
    // state = 4
    // if(prot)  -> state = 3
    // if(empty) -> state = 2, c_t = c
    // if(occ)   -> state = 0
    //========================================================

    while(curr_row){
      tmp_ = (curr_row & -curr_row);  //get least sig bit of curr_row
      curr_row ^= tmp_;               //remove least sig bit of curr_row.

      // if true then this iteration and last iteration are not contiguous.
      // Which means there was an occupied square.
      if ( ((tmp_ >> 1) & tmp) == 0 ) {
        if(state == 1) {
          u++;
          tmp_board[r+1] |= tmp;
        } else if(state == 3) {
          tmp_board[r+1] |= (s_v | (s_v << 1));
          if((s_v & next_prev_row) || ((s_v << 1) & next_prev_row))
            v2_p++;
          else
            v1_p++;
        }
        state = 0;
      }
      tmp = tmp_;
      
      // empty and protected
      if( tmp & adj_rows ){
        if(state == 0) {
          state = 1;
        } else if(state == 1) {
          state = 0;
          //safe
        } else if(state == 2) {
          state = 3;
        } else if(state == 3) {
          state = 4;
          //safe
        } else if(state == 4) {
          state = 3;
        }
      }
      
      // unprotected
      else {
        if(state == 0) {
          state = 2;
          s_v = tmp;
        } else if(state == 1){
          state = 0;

          // Check tmp >> 1

          tmp_board[r+1] |= (tmp | (tmp >> 1));
          if((tmp & next_prev_row) || ((tmp >> 1) & next_prev_row))
            v2_p++;
          else
            v1_p++;
        } else if(state == 2){
          state = 0;
          tmp_board[r+1] |= (s_v | (s_v << 1));
          if((s_v & next_prev_row) || ((s_v << 1) & next_prev_row))
            v2++;
          else
            v1++;
        } else if(state == 3){
          state = 2;
          tmp_board[r+1] |= (s_v | (s_v << 1));
          if((s_v & next_prev_row) || ((s_v << 1) & next_prev_row))
            v2_p++;
          else
            v1_p++;
          s_v = tmp;
        } else if(state == 4){
          state = 2;
          s_v = tmp;
        }
      }
    }

    if(state == 1) {
      u++;
      tmp_board[r+1] |= tmp;
    } else if(state == 3) {
      tmp_board[r+1] |= (s_v | (s_v << 1));
      if((s_v & next_prev_row) || ((s_v << 1) & next_prev_row))
        v2_p++;
      else
        v1_p++;
    }

    //    if(print)
    //  printf("%d %d %d %d %d - %X\n", v2, v2_p, v1, v1_p, u,
    //        tmp_board[r+1]);
    
  }
  //  if(print) printf("\n");

  *vuln2 = v2 + v2_p;
  *vuln2_w_prot = v2_p;
  *vuln1 = v1 + v1_p;
  *vuln1_w_prot = v1_p;
  *unused = u;
}


//#################################################################
// This function tries to pack as many 'option of vulnerability' areas
//  onto the board as it can. (no guarantee of optimality).
//#################################################################
static inline void
pack_safe(u32bit tmp_board[32], s32bit player,
          s32bit *safe_op2, s32bit *safe_op1, s32bit *safe_op0)
{
  u32bit guard, mask, curr, tmp;

  s32bit r;                       //row
  s32bit s2 = 0, s1 = 0, s0 = 0;
  
  for(r = 0; r < g_board_size[player]; r++){
    guard = g_board[player][r] & g_board[player][r+2];
    curr  = g_board[player][r+1] | tmp_board[r+1];
    
    // mask contains a bit for each safe move.
    mask  = ( (~(curr | (curr >> 1))) & (guard & (guard >> 1)) );

    while(mask){
      tmp   =  (mask & -mask);          // least sig bit of m
      mask &= ~(tmp | (tmp << 1));      // remove bit and next bit.

      // add these bits to current.
      curr |= (tmp | (tmp << 1));

      if( ! ( (curr | tmp_board[r] | tmp_board[r+2]) & (tmp >> 1) ) ){
        // we have an option to move vulnerably. (which option is it).
        curr           |= (tmp >> 1);
        tmp_board[r+1] |= (tmp >> 1);
        
        // check up.
        if(  (!(g_board[player][r] & (tmp >> 1)))
             && (g_board[player][r-1] & (tmp >> 1)) ){
          // up is good now check down.
          if(  (!(g_board[player][r+2] & (tmp >> 1)))
               && (g_board[player][r+3] & (tmp >> 1)) ){
            s2++;
          } else {
            s1++;
          }
        } else if(  (!(g_board[player][r+2] & (tmp >> 1)))
                    && (g_board[player][r+3] & (tmp >> 1)) ){
          s1++;
        } else {
          s0++;
        }
      } else 
      if( ! ( (mask | curr | tmp_board[r] | tmp_board[r+2]) & (tmp << 2) ) ){
        // we have an option to move vulnerably. (which option is it).
        curr           |= (tmp << 2);
        tmp_board[r+1] |= (tmp << 2);
        
        // check up.
        if(  (!(g_board[player][r] & (tmp << 2)))
             && (g_board[player][r-1] & (tmp << 2)) ){
          // up is good now check down.
          if(  (!(g_board[player][r+2] & (tmp << 2)))
               && (g_board[player][r+3] & (tmp << 2)) ){
            s2++;
          } else {
            s1++;
          }
        } else if(  (!(g_board[player][r+2] & (tmp << 2)))
                    && (g_board[player][r+3] & (tmp << 2)) ){
          s1++;
        } else {
          s0++;
        }
      }
    }
    //    if(debug) printf("(%d,%d) ", s0, s1);
  }
  //  if(debug) printf("\n");

  *safe_op2 = s2;
  *safe_op1 = s1;
  *safe_op0 = s0;
}

//#################################################################
// 
//#################################################################
extern s32bit
#ifdef PRINT_DOES_X_WIN_INFO
does_next_player_win(s32bit next_player, s32bit print)
#else
does_next_player_win(s32bit next_player)
#endif
{
  // info we directly get from the board.
  s32bit prot;   // This is the number of protective regions.

  s32bit vuln2;   // Total number of vulnerable moves (includes vuln_w_prot).
  // Num of vuln moves which contain a square unavailable to the opponent.
  s32bit vuln2_w_prot;
  s32bit vuln1;   // Total number of vulnerable moves (includes vuln_w_prot).
  // Num of vuln moves which contain a square unavailable to the opponent.
  s32bit vuln1_w_prot;

  s32bit safe;   // Number of safe moves horizontal has.
  // Number of squares unused in our packing and unavailable for opponent.
  s32bit unused;
  s32bit empty;  // Number of empty squares on board.
  s32bit safe_op2, safe_op1, safe_op0; //safe moves with options.

  // value we return and other variables.
  s32bit r_value = 0, i;

  // temporary board to store which positions have already been packed.
  u32bit tmp_board[32];

#ifdef NOTHING
  return -1;
#endif
  
  //========================================================  
  // Initialize all of the values.
  //========================================================  
  for(i = 0; i < 32; i++) tmp_board[i] = 0;
  safe  = g_info_totals[next_player].safe;
  empty = g_empty_squares;
  
  // Determine the number of protective regions that we have.
#ifdef NO_PROT
  prot = 0;
#else
  pack_prot(tmp_board, next_player, &prot);
#endif

  // Determine the number of vuln, vuln_w_prot, and unused.
  pack_vuln(tmp_board, next_player, &vuln2, &vuln2_w_prot,
            &vuln1, &vuln1_w_prot, &unused); //, print);

#ifdef NO_VULN_W_PROT
  vuln1_w_prot = vuln2_w_prot = 0;
#endif

#ifdef NO_VULN_TYPE_1
  vuln2 += vuln1;
  vuln2_w_prot += vuln1_w_prot;
  vuln1 = vuln1_w_prot = 0;
#endif

#ifdef NO_UNUSED
  unused = 0;
#endif

#ifdef NO_VULN
  vuln2 = vuln1 = vuln2_w_prot = vuln1_w_prot = 0;
#endif

  // Determine the number of safe moves with options we have.
#ifdef NO_SAFE_OPT
  safe_op2 = safe_op1 = safe_op0 = 0;
#else
  pack_safe(tmp_board, next_player, &safe_op2, &safe_op1, &safe_op0);
#endif

#ifdef PRINT_DOES_X_WIN_INFO
  if(print){
    fprintf(stderr, "%d moves next, do they win?\n", next_player);
    fprintf(stderr, "prot %d, vuln2 %d(%d), vuln1 %d(%d), "
            "safe %d, unused %d, empty %d.\n",
            prot, vuln2, vuln2_w_prot, vuln1, vuln1_w_prot,
            safe, unused, empty);
    fprintf(stderr, "safe_op2 %d, safe_op1 %d, safe_op0 %d.\n",
            safe_op2, safe_op1, safe_op0);
  }
#endif
  
  {
    s32bit moves, opp_moves, x = 0;

    if(prot % 2 == 1){
      prot--;
      safe += 2;
    } else if(vuln2 % 3 != 0){
      vuln2--;
      safe++;
      if(vuln2_w_prot > vuln2) vuln2_w_prot--;
    } else if(vuln1 % 2 != 0){
      vuln1--;
      safe++;
      if(vuln1_w_prot > vuln1) vuln1_w_prot--;
    } else if(safe_op2 % 2 != 0){
      safe_op2--;
      unused+=3;
    } else if(safe_op1 % 2 != 0){
      safe_op1--;
      unused+=2;
    } else if(safe_op0 % 2 != 0){
      safe_op0--;
      unused+=1;
    } else if(vuln2 > 0){
      vuln2--;
      safe++;
      if(vuln2_w_prot > vuln2) vuln2_w_prot--;
    } else if(vuln1 > 0){
      vuln1--;
      safe++;
      if(vuln1_w_prot > vuln1) vuln1_w_prot--;
    } else if(prot > 0){
      prot--;
      safe += 2;
    } else {
      return -1;
    }

    if(prot % 2 == 1){
      prot--;
      vuln2 += 2;
    }

    moves = (prot) + (vuln2/3) + (vuln1/2) + safe;
    
    if(vuln2 % 3 != 0 && vuln1 % 2 != 0){
      moves++, unused--, x=1;
      //      if(vuln2 > 0 || vuln1 > 0) unused--;
    } else if(vuln2 % 3 == 0 && vuln1 % 2 == 0) x=1;

    if(x == 1){
      if(safe_op2%2 == 1) safe_op2--, safe_op1++;
      if(safe_op1%2 == 1) safe_op1--, safe_op0++;
    } else {
      if(safe_op2%2 == 1){
        unused += 3;
        if(safe_op1%2==1) safe_op1--, safe_op0++;
      } else if(safe_op1%2 == 1) { unused += 2; }
      else if(safe_op0%2 == 1)   { unused += 1; }
    }
    
    unused += vuln2_w_prot - ( (vuln2)/3 - (vuln2-vuln2_w_prot)/3 );
    unused += vuln1_w_prot - ( (vuln1)/2 - (vuln1-vuln1_w_prot)/2 );

    unused += (safe_op2/2) * 3;
    unused += (safe_op1/2) * 2;
    unused += (safe_op0/2) * 1;

    opp_moves = (empty - (moves*2) - unused)/2;

    //========================================================
    // If r_value > 0 then next_player wins.
    //========================================================
    r_value = moves - opp_moves;

#ifdef PRINT_DOES_X_WIN_INFO
    if(print){
      printf("moves:%d, opp:%d.\n", moves, opp_moves);
      if(moves - opp_moves >= 0) printf("H WINS\n");
    }
#endif
  }

  return r_value;
}


//#################################################################
// 
//#################################################################
extern s32bit
#ifdef PRINT_DOES_X_WIN_INFO
does_who_just_moved_win(s32bit who_just_moved, s32bit print)
#else
does_who_just_moved_win(s32bit who_just_moved)
#endif
{
  // info we directly get from the board.
  s32bit prot;   // This is the number of protective regions.

  s32bit vuln2;   // Total number of vulnerable moves (includes vuln_w_prot).
  // Num of vuln moves which contain a square unavailable to the opponent.
  s32bit vuln2_w_prot;
  s32bit vuln1;   // Total number of vulnerable moves (includes vuln_w_prot).
  // Num of vuln moves which contain a square unavailable to the opponent.
  s32bit vuln1_w_prot;

  s32bit safe;   // Number of safe moves horizontal has.
  // Number of squares unused in our packing and unavailable for opponent.
  s32bit unused;
  s32bit empty;  // Number of empty squares on board.
  s32bit safe_op2, safe_op1, safe_op0; //safe moves with options.

  // value we return and other variables.
  s32bit r_value = 0, i;

  // temporary board to store which positions have already been packed.
  u32bit tmp_board[32];
  
#ifdef NOTHING
  return -1;
#endif
  
  //========================================================  
  // Initialize all of the values.
  //========================================================  
  for(i = 0; i < 32; i++) tmp_board[i] = 0;
  safe  = g_info_totals[who_just_moved].safe;
  empty = g_empty_squares;
  
  // Determine the number of protective regions that we have.
#ifdef NO_PROT
  prot = 0;
#else
  pack_prot(tmp_board, who_just_moved, &prot);
#endif

  // Determine the number of vuln, vuln_w_prot, and unused.
  pack_vuln(tmp_board, who_just_moved, &vuln2, &vuln2_w_prot,
            &vuln1, &vuln1_w_prot, &unused);

#ifdef NO_VULN_W_PROT
  vuln1_w_prot = vuln2_w_prot = 0;
#endif

#ifdef NO_VULN_TYPE_1
  vuln2 += vuln1;
  vuln2_w_prot += vuln1_w_prot;
  vuln1 = vuln1_w_prot = 0;
#endif

#ifdef NO_UNUSED
  unused = 0;
#endif

#ifdef NO_VULN
  vuln2 = vuln1 = vuln2_w_prot = vuln1_w_prot = 0;
#endif

  // Determine the number of safe moves with options we have.
#ifdef NO_SAFE_OPT
  safe_op2 = safe_op1 = safe_op0 = 0;
#else
  pack_safe(tmp_board, who_just_moved, &safe_op2, &safe_op1, &safe_op0);
#endif
  
  /*
  if(prot % 2 == 1){
    prot--;
    vuln2 += 2;
  }

  if(print == 1 && unused > 0
     && prot >= 2 // && (vuln2%3 != 0 || vuln1%2 != 0)
     && vuln2 >= 3 && vuln1 >= 2
     && safe_op1 + safe_op0 >= 2){
    print_board(who_just_moved);
  } else {
    print = 0;
  }
  */
#ifdef PRINT_DOES_X_WIN_INFO
  if(print){
    fprintf(stderr, "%d just moved, do they win?\n", who_just_moved);
    fprintf(stderr, "prot %d, vuln2 %d(%d), vuln1 %d(%d), "
            "safe %d, unused %d, empty %d.\n",
            prot, vuln2, vuln2_w_prot, vuln1, vuln1_w_prot,
            safe, unused, empty);
    fprintf(stderr, "safe_op2 %d, safe_op1 %d, safe_op0 %d.\n",
            safe_op2, safe_op1, safe_op0);
  }
#endif
  
  {
    s32bit moves, opp_moves, x = 0;

    if(prot % 2 == 1){
      prot--;
      vuln2 += 2;
    }
    
    moves = (prot) + (vuln2/3) + (vuln1/2) + safe;
    
    if(vuln2 % 3 != 0 && vuln1 % 2 != 0){
      moves++, unused--, x=1;
      //      if(vuln2 > 0 || vuln1 > 0) unused--;
    } else if(vuln2 % 3 == 0 && vuln1 % 2 == 0) x=1;

    if(x == 1){
      if(safe_op2%2 == 1) safe_op2--, safe_op1++;
      if(safe_op1%2 == 1) safe_op1--, safe_op0++;
    } else {
      if(safe_op2%2 == 1){
        unused += 3;
        if(safe_op1%2==1) safe_op1--, safe_op0++;
      } else if(safe_op1%2 == 1) { unused += 2; }
      else if(safe_op0%2 == 1)   { unused += 1; }
    }
    
    unused += vuln2_w_prot - ( (vuln2)/3 - (vuln2-vuln2_w_prot)/3 );
    unused += vuln1_w_prot - ( (vuln1)/2 - (vuln1-vuln1_w_prot)/2 );

    unused += (safe_op2/2) * 3;
    unused += (safe_op1/2) * 2;
    unused += (safe_op0/2) * 1;

    opp_moves = (empty - (moves*2) - unused)/2;

    //========================================================
    // If r_value >= 0 then who_just_moved wins.
    //========================================================
    r_value = moves - opp_moves;

#ifdef PRINT_DOES_X_WIN_INFO
    if(print){
      printf("moves:%d, opp:%d.\n", moves, opp_moves);
      if(moves - opp_moves >= 0) printf("H WINS\n");
    }
#endif
  }

  return r_value;
}