#include <stdio.h>
#include <stdlib.h>
#include "queens.h"
#include <assert.h>

BOARDPTR InitBoard () {
  int i;
  BOARDPTR board = CreateBoard();

  assert (board);
  for ( i=0 ; i < ROWS ; i++ ) {
    board->board[i] = EMPTY;
  }
  board->nextRow = 0;
  return (board);
}

BOARDPTR CopyBoard (BOARDPTR old) {
  BOARDPTR new = CreateBoard ();
  int i;

  assert (old); assert (new);
  for ( i=0 ; i < ROWS ; i++ ) {
    new->board[i] = old->board[i];
  }
  new->nextRow = old->nextRow;
  return (new);
}

void AddMoves (BOARDPTR board, NODEPTR *open, NODEPTR *tail, int search) {
  int i;
  BOARDPTR new;

  assert (board); assert (open); assert (tail); 
  /* Nothing to add! */
  if ( board->nextRow == ROWS ) {
    /* printf ("Nothing to add in AddMoves...\n"); */
    return;
  }
  /* Push each new move on the stack or queue */
  for ( i=0 ; i < ROWS ; i++ ) {
    if ( IsLegal (board->nextRow, i, board->board) ) {
      /* printf ("Adding %d,%d\n", board->nextRow, i); */
      new = CopyBoard (board);
      assert (new);
      new->board[new->nextRow] = i;
      (new->nextRow)++;
      Add (new, open, tail, search);
    }
  }
}

BOARDPTR CreateBoard () {
  BOARDPTR board;
  if ( ! ( board = (BOARDPTR) malloc (sizeof (BOARD)) ) ) {
    fprintf (stderr, "Error: No more memory in CreateBoard!\n");
    exit(-1);
  }
  assert (board);
  return (board);
}

BOARDPTR Search (NODEPTR *open, NODEPTR *tail, int *moves, int search) {
  BOARDPTR next;

  assert (open);
  if ( IsEmpty (*open) ) {
    /* printf ("Reached end of search -- fail!\n"); */
    return (NULL);
  }
  assert (*open); assert (*tail); assert (moves);
  (*moves)++;
  next = Remove (open, tail, search);
  if ( IsGoal (next) ) {
    /* printf ("Reached goal!\n"); */
    return (next);
  }
  /* printf ("Adding moves and recursing...\n"); */
  AddMoves (next, open, tail, search);
  free (next);
  assert (open); assert (tail); assert (*open); assert (*tail);
  /* PrintQueue (*open); */
  return (Search (open, tail, moves, search));
}

void PrintBoard (BOARDPTR board) {
  int i, j;

  assert (board);
  for ( i=0 ; i < ROWS ; i++ ) {
    for ( j=0 ; j < ROWS ; j++ ) {
      if ( board->board[i] == j ) {
	printf ("Q");
      } else {
	printf ("-");
      }
    }
    printf ("\n");
  }
}

void Add (BOARDPTR board, NODEPTR *open, NODEPTR *tail, int search) {
  /* printf ("Search type is %d\n", search); */
  assert (board); assert (open); assert (tail);
  if ( search == BFS ) {
    Enqueue (open, tail, CreateNode (board));
  } else if ( search == DFS ) {
    Push (open, CreateNode (board));
  } else {
    fprintf (stderr, "Unknown search method %d!\n", search);
  }
}

BOARDPTR Remove (NODEPTR *open, NODEPTR *tail, int search) {
  assert (open); assert (tail);
  if ( search == BFS ) {
    return (Dequeue(open, tail));
  } else if ( search == DFS ) {
    return (Pop(open));
  } else {
    fprintf (stderr, "Unknown search method %d!\n", search);
    exit (-1);
  }
}

int IsGoal (BOARDPTR board) {
  assert (board);
  /* printf ("Testing board:\n"); */
  /* PrintBoard (board); */
  /* printf ("nextRow is %d, so IsGoal is %d\n",
     board->nextRow, (board->nextRow==ROWS)); */
  return ( board->nextRow == ROWS );
}

int IsLegal (int row, int col, int board[ROWS]) {
  int i;

  /* only need to check rows that have already been assigned */
  for ( i=0 ; i < row ; i++ ) {
    if ( i != row ) {
      /* check for same column */
      if ( board[i] == col ) {
	/* printf ("   ...same column!\n"); */
	return (0);
      }
      /* check for same diagonal */
      if ( abs(board[i] - col) == abs(i-row) ) {
	/* printf ("   ...same diagonal!\n"); */
	return (0);
      }
    }
  }
  return (1);
}