#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <ctype.h>
#include <unistd.h>
#include <sys/types.h>
#include <sys/socket.h>
#include <sys/wait.h>
#include <signal.h>
#include <arpa/inet.h>

#include "trie.h"

#define NETBOGGLE_PORT  12345
#define BUFSIZE         128
#define MAX_BOX_SIZE	6

#define MIN_WORD_LEN    4

#define NOT_SEEN	0
#define SEEN		1

#define FOUND_SIZE      1000


extern TRIE_NODE trie_root;

void try_print(char *found[FOUND_SIZE], char *choices, int depth,
               int *num_found)
{
  int i;

  choices[depth] = '\0';

  if (*num_found >= FOUND_SIZE) {
    printf("too many words found\n");
    return;
  }

  for (i = 0; i < *num_found; i++)
    if (!strcmp(choices, found[i]))
      return;

  found[(*num_found)++] = strdup(choices);
  printf("bog %s\n", choices);
}



void dfs(int graph[MAX_BOX_SIZE][MAX_BOX_SIZE], int board_size,
         int letters[MAX_BOX_SIZE][MAX_BOX_SIZE],
         char *choices, char *found[FOUND_SIZE], int *num_found,
         int x, int y, int depth, TRIE_NODE *trie_node)
{
  int i, j;

  /* stop if we've gone off the edge of the matrix */
  if (x < 0 || y < 0 || x >= board_size || y >= board_size)
    return;

  /* stop if we're going in circles */
  if (graph[x][y] == SEEN)
    return;

  /* the following line is the core of the algorithm: check and see if
   * there exists a trie node that corresponds to the letter in this
   * matrix position.  If so, "move down" in the trie by setting
   * trie_node to be the child corresponding to the current letter.
   * If not, it means no words in the dictionary start with the
   * currently found letter sequence. */
  if ((trie_node = trie_node->next[letters[x][y]]) == NULL)
    return;

  /* okay -- at this point, we know that the letter sequence we've
   * found so far is either a prefix of a word in the dictionary, or a
   * word in the dictionary, or both. */

  /* update the sequence of letters that we've found so far */
  choices[depth++] = letters[x][y] + 'a';

  /* print the current word if it exists in the dictionary and it's
   * long enough */
  if (trie_node->mark && depth >= board_size-1)
    try_print(found, choices, depth, num_found);

  /* now continue our search downward */

  /* record that we've been here before so that we don't go in circles */
  graph[x][y] = SEEN;

  for (j = -1; j <= 1; j++)
    for(i = -1; i <= 1; i++)
      if (i || j)
	dfs(graph, board_size, letters, choices, found, num_found,
            x+i, y+j, depth, trie_node);

  /* as we back out of the matrix, mark the node as not seen again so
   * we can use this space for other words */
  graph[x][y] = NOT_SEEN;
}



/* Read the board from input.  Return the dimension of the board. */
int read_board(int *raw_input, int fd)
{
  int num_read = 0;
  int let_number, retval, i;
  char buf[BUFSIZE];

  for (;;) {

    /* Keep reading until we read a letter, or "%", or reach end of input */
    do {
      if ((retval = read(fd, buf, sizeof(char))) != sizeof(char))
        break;
    } while (!isalpha(*buf) && *buf != '%');

    /* if this is the stop character, assume end of input */
    if (*buf == '%')
      break;

    /* make sure this letter is legal */
    let_number = tolower(*buf) - 'a';
    if (let_number < 0 || let_number >= NUM_LETTERS) {
      printf("illegal character '%c' in board\n", *buf);
      exit(1);
    }

    /* store this letter */
    raw_input[num_read++] = let_number;

    /* make sure we don't exceed our bounds... */
    if (num_read >= MAX_BOX_SIZE*MAX_BOX_SIZE)
      break;
  }

  for (i = 2; i <= MAX_BOX_SIZE; i++)
    if (num_read == i*i)
      return i;

  printf("Illegal board size -- the board must be square.  You only entered\n"
         "%d letters.  Max allowed box size is %d x %d.\n", num_read,
         MAX_BOX_SIZE, MAX_BOX_SIZE);
  exit(1);
}



int solve(int fd)
{
  char *found[FOUND_SIZE];
  int num_found = 0;
  int letters[MAX_BOX_SIZE][MAX_BOX_SIZE];
  int graph[MAX_BOX_SIZE][MAX_BOX_SIZE];
  char choices[MAX_BOX_SIZE*MAX_BOX_SIZE];
  int raw_input[MAX_BOX_SIZE*MAX_BOX_SIZE];
  int board_size;

  int i, j, num;

  board_size = read_board(raw_input, fd);

  num = 0;
  for (j = 0; j < board_size; j++) {
    for (i = 0; i < board_size; i++) {

      /* put it in our matrix */
      letters[i][j] = raw_input[num++];
      graph[i][j] = NOT_SEEN;
    }
  }

  printf("You entered the following box: \n\n");
  for (j = 0; j < board_size; j++) {
    for (i = 0; i < board_size; i++)
      printf("%c ", letters[i][j] + 'a');
    putchar('\n');
  }

  printf("\nThe following is a list of words that can be found in the matrix\n"
         "(Search limited to words with a minimum length of %d letters)\n\n",
         board_size-1);

  /* walk the matrix */
  for (j = 0; j < board_size; j++)
    for (i = 0; i < board_size; i++)
      dfs(graph, board_size, letters, choices, found, &num_found, i, j, 0,
          &trie_root);

  return 0;
}

/*
 * init_socket sets up the mother descriptor - creates the socket, sets
 * its options up, binds it, and listens.
 */
int init_socket(int port)
{
  int s, opt;
  struct sockaddr_in sa;

  /*
   * Should the first argument to socket() be AF_INET or PF_INET?  I don't
   * know, take your pick.  PF_INET seems to be more widely adopted, and
   * Comer (_Internetworking with TCP/IP_) even makes a point to say that
   * people erroneously use AF_INET with socket() when they should be using
   * PF_INET.  However, the man pages of some systems indicate that AF_INET
   * is correct; some such as ConvexOS even say that you can use either one.
   * All implementations I've seen define AF_INET and PF_INET to be the same
   * number anyway, so ths point is (hopefully) moot.
   */

  if ((s = socket(PF_INET, SOCK_STREAM, 0)) < 0) {
    perror("Create socket");
    exit(1);
  }
#if defined(SO_REUSEADDR)
  opt = 1;
  if (setsockopt(s, SOL_SOCKET, SO_REUSEADDR, (char *) &opt, sizeof(opt)) < 0) {
    perror("setsockopt REUSEADDR");
    exit(1);
  }
#endif

#if defined(SO_LINGER)
  {
    struct linger ld;

    ld.l_onoff = 0;
    ld.l_linger = 0;
    if (setsockopt(s, SOL_SOCKET, SO_LINGER, (char *) &ld, sizeof(ld)) < 0) {
      perror("setsockopt LINGER");
      exit(1);
    }
  }
#endif

  sa.sin_family = AF_INET;
  sa.sin_port = htons(port);
  sa.sin_addr.s_addr = htonl(INADDR_ANY);

  if (bind(s, (struct sockaddr *) &sa, sizeof(sa)) < 0) {
    perror("bind");
    close(s);
    exit(1);
  }
  listen(s, 5);
  return (s);
}


void load_dictionary()
{
  FILE *f;
  char buf[BUFSIZE];
  int i;

  if (!(f = fopen("./bigdict", "r"))) {
    perror("error opening dictionary");
    exit(0);
  }

  trie_init();

  while (fgets(buf, BUFSIZE, f)) {
    buf[strlen(buf)-1] = '\0';
    for (i = 0; i < strlen(buf); i++)
      buf[i] = tolower(buf[i]);
    trie_add_word(buf);
  }

#if 0
  trie_walk();
#endif
}


/* clean up our zombie kids to avoid defunct processes */
void reap(int sig)
{
  while (waitpid(-1, NULL, WNOHANG) > 0);

  signal(SIGCHLD, reap);
}



int main(int argc, char *argv[])
{
  int s, child, port, desc;

  port = NETBOGGLE_PORT;


  fprintf(stderr, "attaching to network\n");
  s = init_socket(port);

  fprintf(stderr, "loading dictionary...\n");
  load_dictionary();


  if ((child = fork()) > 0) {
    fprintf(stderr, "Netboggle ready to answer queries on port %d (pid %d).\n",
            port, child);
    exit(0);
  }
  signal(SIGCHLD, reap);

  for (;;) {
    if ((desc = accept(s, (struct sockaddr *) NULL, 0)) < 0)
      continue;

    if (fork() == 0) {
      int retval;

      close(STDIN_FILENO);
      dup2(desc, STDIN_FILENO);
      close(STDOUT_FILENO);
      dup2(desc, STDOUT_FILENO);
      retval = solve(desc);
      close(desc);
      exit(retval);
    }
    close(desc);
  }
}