/* wordsquare-finding code modified for Lonestar MPI system */
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <ctype.h>
#include <unistd.h>
#include <time.h>
#include <signal.h>


#ifdef MPI
#include <mpi.h>
#endif
#include "splib.h"

#ifndef TRUE
#define TRUE (0==0)
#define FALSE (!TRUE)
#endif

// 24 checkpoint entires per 6 hr run, not too onerous
//#define CHECKPOINT_INTERVAL (15*60)
// force possible error from checkpointing early, in case
// we still have a bug
#define CHECKPOINT_INTERVAL1 60
#define CHECKPOINT_INTERVAL (15*60)

/* The dictionary itself is global, as these variables are seldom
   referenced, and I don't want to pass them in as parameters to every
   procedure just so I can access them occassionaly */

NODE *rootdawg;
NODE *headwords;
INDEX nedges;
INDEX headnedges;

#define MAX 12 /* Biggest we're willing to tackle will eventually be 11 */

static int sq[MAX/* row */][MAX/* col */];		/* letters */

static NODE *fork_point[MAX+1/* row */][MAX/* col */];
             /* downward word branch choices from this row */

static char check[MAX+1/* row */][MAX/* col */][256+1/* alphabet */];
                  /* string of letters which
                     are valid in each position in the row below */

/* This one is *NOT* row, col */
static char vertical_word[MAX /* col */][MAX+1 /* row/wordlen */];

/* This is probably redundant - it's just a printable horizontal word 
   also used for communication.  Can probably use sq[][] instead. */
char word[MAX /* row */][MAX+1 /* len */];


/* Doubles as producing answers and debug routine */
void print_square(FILE *results, int row, int col, int max, char *s)
{
  int i, j;
  time_t now;
  int star = FALSE;

  fprintf(results, s);
  for (j = 0; j < row; j++) {
    for (i = 0; i < max; i++) {
      if (sq[j][i] == '*') star = TRUE;
      if (star) fputc('?', results); else fputc(sq[j][i], results);
    }
    fputc(' ', results);
  }
  for (j = row; j < max; j++) {
    for (i = 0; i < max; i++) fputc('.', results);
    fputc(' ', results);
  }
  now = time(NULL); fprintf(results, "%s", ctime(&now));
  // fputc('\n', results);
  fflush(results);
}

static char sresults[512] = { '\0' };
void safe_dump(int max, char *s)
{
  int row = max, col = max;
  int i, j;
  time_t now;
  int star = FALSE;
  char *sp;

  sp = sresults + sprintf(sresults, s);
  for (j = 0; j < row; j++) {
    for (i = 0; i < max; i++) {
      if (sq[j][i] == '*') star = TRUE;
      if (star) *sp++ = '?'; else *sp++ = sq[j][i];
    }
    *sp++ = ' ';
  }
  for (j = row; j < max; j++) {
    for (i = 0; i < max; i++) *sp++ = '.';
    *sp++ = ' ';
  }
  now = time(NULL); sprintf(sp, "%s", ctime(&now));
}

/* parameter col is the length is of the horizontal word and should
   always be invoked externally with len=0.  hnode should be dawg+1 for
   the start of every word in the full wordlist. */

/* Iterate a letter at a time across each row; recurse at the end of a
   row to go to the next row.  Backtrack when the square is blocked. */

void next_letter(FILE *results, NODE *hnode, int row, int max, int col)
{
  NODE *nextnode;
  int ch;
  NODE *savednode;
  char savedcheck[256];

  if (row == max || col == max) return;

  /* safety - I'd prefer this were done at the point of the recursive call  */
  /* It's because of things like that that some of the arrays have to be +1 */

  for (;;) { /* loop across horizontal letter placement */

    if (*sresults != '\0') { // This is so that we do not do I/O in the signal handlers 
      fprintf(results, "%s", sresults);
      *sresults = '\0'; // remove the message once printed
    }

    ch = (char)(((*hnode) >> V_LETTER) & M_LETTER);
    word[row][col] = ch;
    word[row][col+1] = '\0';
    sq[row][col] = ch;    sq[row][col+1] = '*';
    vertical_word[col][row] = ch;
    vertical_word[col][row+1] = '\0';

    nextnode = rootdawg+((*hnode) & M_NODE_POINTER);

    /* Test to see if this edge letter is allowed in the vertical
       crosscheck list */

    /* Here we can either search for 'traditional' squares (where the vertical
       words are the same as the horizontal words), or 'double' squares, where
       the words across differ from the words down.
     */
#ifdef DOUBLE
    if (strchr(check[row][col], ch) != NULL) {
#else
    if (
         (    (col < row)
           && (ch == sq[col][row])
           && (strchr(check[row][col], ch) != NULL)
         )
         ||
         (    (col >= row)
           && (strchr(check[row][col], ch) != NULL)
         )
        ) {
#endif

      int nextfree;
      int found;
      NODE *vnode;

      /* letter is placed.  Before we go any further, did this
         placement generate a solution? */

      /* letter is placed in the square, now see if it is valid.
         We place next horizontal letter recursively if this one was
           accepted OK.  It may be rejected due to vertical crosscheck
           and it may be rejected because it blocks off the vertical
           word from being expanded further downwards.  Of course
           we shouldn't care about the latter if this is the final row. */

      /* INLINE: 
         fork_point[row+1][col] = follow_edge(fork_point[row][col], ch); */

      vnode = fork_point[row][col];

      found = FALSE;
      for (;;) { /* placed a letter, look for next set of options */
        if (ch == (((*vnode) >> V_LETTER) & M_LETTER)) {
          vnode = rootdawg+(*vnode & M_NODE_POINTER);
          found = TRUE; break;
	}
        if ((*vnode & M_END_OF_NODE) != 0) break;
        vnode++;
      }
      if (found) {
        savednode = fork_point[row+1][col];
        strcpy(savedcheck, check[row+1][col]);
        fork_point[row+1][col] = vnode;
        nextfree = 0;
        for (;;) {
          if (vnode == NULL) {
            fprintf(stdout, "Don't know why vnode is NULL\n");
            exit(1);
          }
          check[row+1][col][nextfree++] = ((*vnode) >> V_LETTER) & M_LETTER;
          if ((*vnode & M_END_OF_NODE) != 0) break;
          vnode++;
        }
        check[row+1][col][nextfree++] = '\0';

        if (col+1 == max) {
          /* good placement on this row.
             recurse to next row.
             reset the dictionary to start of line */

          if (row+1 == max) {
            /* As the word would not have been placed unless it formed a
               vertical word also, we must have a solution.  Print it and return */
            print_square(results, max,max,max,"Solution: ");
          }

          /* good placement.  recurse to next row.  reset the dictionary */
          next_letter(results, rootdawg+1, row+1, max, 0);
        } else {
          /* place next letter horizontally */
          next_letter(results, 
            nextnode, row, max, col+1);
	}
        /* what I worry about here is when we backtrack, do all
           the things like check[] and fork_point[] work properly?
           They *should* do, because ones we backtrack over should
           never be looked at, but I have this niggling doubt, at
           least as long as the program isn't working...
         */

        fork_point[row+1][col] = savednode;
        strcpy(check[row+1][col], savedcheck);
      } else {
        char tmp[256];
        /* Cannot make this play because it blocks of progress for
           a vertical word.  Go back up a row. */;
        /* (or maybe backtrack a letter and try another word on this row?) */
      }
    }

    /* now see if there is another letter at this position. */

    if ((*hnode & M_END_OF_NODE) != 0) break; /* end of node */
    hnode++;
  } /* end loop across horizontal letter placement */
}

static void dawg_pr(NODE *dawg, INDEX node, int len, int *count)
{
  static char word[MAX_WORD_LEN];
  NODE *edge;

  for (edge = (NODE *)&dawg[node]; ; edge++) {
  long c;
    c = *edge;           /* Don't rewrite this - its avoiding a MSC bug */
    c = c >> V_LETTER;
    c = c & M_LETTER;
    word[len] = (char)c;
    if ((*edge & M_END_OF_WORD) != 0) {
      word[len+1] = '\0';
      (*count) += 1; // fprintf(stdout, "%s\n", word);
    }
    c = *edge & M_NODE_POINTER;
    if ((*edge & M_NODE_POINTER) != 0)
      dawg_pr (dawg, c, len + 1, count);
    if ((*edge & M_END_OF_NODE) != 0) break; /* End of node */
  }
}

int count(NODE *dawg)
{
  int i = 0; dawg_pr(dawg, ROOT_NODE, 0, &i);
  return i;
}

static char *dawg_w(NODE *dawg, INDEX node, int len, int *count, int target)
{
  static char word[MAX_WORD_LEN];
  NODE *edge;

  for (edge = (NODE *)&dawg[node]; ; edge++) {
    long c;
    c = *edge;           /* Don't rewrite this - its avoiding a MSC bug */
    c = c >> V_LETTER;
    c = c & M_LETTER;
    word[len] = (char)c;
    if ((*edge & M_END_OF_WORD) != 0) {
      word[len+1] = '\0';
      (*count) += 1; // fprintf(stdout, "%s\n", word);
      if (*count == target) return(word);
    }
    c = *edge & M_NODE_POINTER;
    if ((*edge & M_NODE_POINTER) != 0) {
      char *w = dawg_w (dawg, c, len + 1, count, target);
      if (w) return w;
    }
    if ((*edge & M_END_OF_NODE) != 0) break; /* End of node */
  }
  return NULL;
}

char *wordno(NODE *dawg, int no) // 1..count(dawg) inclusive
{
  int i = 0;
  return dawg_w(dawg, ROOT_NODE, 0, &i, no);
}

static int max;
static FILE *results;
void catch_alarm(int x)
{
  safe_dump(max,"Checkpoint: ");
  alarm(CHECKPOINT_INTERVAL); // Reset the alarm for the next one
}

void catch_shutdown(int x)
{
  signal(SIGALRM, SIG_DFL);
  safe_dump(max,"Early termination: ");
  signal(SIGUSR2, SIG_DFL);  // we're done.  reinstate the default handlers
//kill(getpid(), SIGUSR2);  // reraise the signal to cause termination
                            // (otherwise we continue to run past our time limit!)
  // don't kill - allow to return, so that dump message is printed by usercode
  // rather than signal handler
}

int main(int argc, char **argv) {
  char fname[256], rfname[256], *topline;
  char w1[MAX], w2[MAX];
  int rank = 0, size = 1;
  int row, col;
  int hi, lo;
  int word, words;
  int found;
  NODE *vnode;
  int ch;

  if (argc == 1) {
    max = 10;
  } else if (argc == 2) {
    max = *argv[1];
    if (isdigit(max)) max = max - '0'; else max = 4;
  } else {
    fprintf(stderr, "syntax: ws 7\n        (or any number 2-9)\n");
    exit(1);
  }

#ifdef MPI
  MPI_Init (&argc, &argv);     /* starts MPI */
  MPI_Comm_rank (MPI_COMM_WORLD, &rank);       /* get current process id */
  MPI_Comm_size (MPI_COMM_WORLD, &size);       /* get number of processes */
#endif

  sprintf(fname, "dawg.%0d", max);
  if (!dawg_init(fname, &rootdawg, &nedges)) {
    fprintf(stderr, "Cannot open %s\n", fname);
#ifdef MPI
    MPI_Finalize();
#endif
    exit(1);
  }

  if (!dawg_init("headwords10.dwg", &headwords, &headnedges)) {
    fprintf(stderr, "Cannot open %s\n", fname);
#ifdef MPI
    MPI_Finalize();
#endif
    exit(1);
  }

  // Find the rank/size-th word.  with 2 processes, rank = {0, 1}, size = 2

  words = count(headwords);

  fprintf(stdout, "Process %d of %d - ",
	  rank+1, size);

  fprintf(stdout, "loaded %d words (%ld edges).  ",
	  words, headnedges);

  fprintf(stdout, "This job: %d to %d ",
	  lo = (int)((words * rank) / size)+1, hi = (int)((words * (rank+1)) / size));
  strcpy(w1, wordno(headwords, lo));  strcpy(w2, wordno(headwords, hi));
  fprintf(stdout, "(%s to %s)\n", w1, w2);

  sprintf(rfname, "%s-%s:%05d.txt", w1, w2, rank+1);
  results = fopen(rfname, "w"); // in $WORK directory
  if (results == NULL) {
    fprintf(stderr, "Cannot open %s\n", rfname);
#ifdef MPI
    MPI_Finalize();
#endif
    exit(1);
  }

  {time_t now = time(NULL); fprintf(stdout, "PROGRAM BEGINS: %s", ctime(&now));fflush(stdout);}
  {time_t now = time(NULL); fprintf(results, "PROGRAM BEGINS: %s", ctime(&now));fflush(results);}


  /* Have to initialise first row specially.
     *all* words are valid at this point. */

  // TAKING OUT ALL SIGNALS IN CASE THIS IS WHY THE PROGRAM IS QUITTING
  //signal(SIGALRM, &catch_alarm);
  //signal(SIGUSR2, &catch_shutdown);
  //alarm(CHECKPOINT_INTERVAL1);

  for (word = lo; word <= hi; word++) { // range is inclusive
    time_t now;
    row = 0;
    topline = wordno(rootdawg, word); // this is not efficient but we'll live with it...

    now = time(NULL); fprintf(results, "Starting: %s %s", topline, ctime(&now));fflush(results);

    // Load initial word:
    for (col = 0; col < max; col++) {
      ch = topline[col];
      sq[row][col] = ch;
      // the only letter allowed in this position is the letter which exactly matches the first word!
      check[row][col][0] = ch; check[row][col][1] = '\0';
      vertical_word[col][0] = ch; vertical_word[col][1] = '\0';
      fork_point[row][col] = rootdawg+1;

      // if ((!found) && (*vnode & M_END_OF_NODE)) break; // THIS LETTER DOES NOT START ANY VERTICAL WORDS!!!
    }

    // if ((!found) && (*vnode & M_END_OF_NODE)) continue; // THIS LETTER DOES NOT START ANY VERTICAL WORDS!!!

    for (row = 1; row < max; row++) {
      /* wrong for all but 1st row, but we don't care as subsequent rows will be filled in
         by next_letter() before they are accessed */
      for (col = 0; col < max; col++) {
        sq[row][col] = '_';
        /* This could be done better by extracting the next letter info from the dawg
           Although not the most efficient, the 'strchr()' overhead is low */
        strcpy(check[row][col],
	         "ABCDEFGHIJKLMNOPQRSTUVWXYZaáâäæbcçdeéèêëfghiíìîïÏjklmnoóòôöøpqrstuúùûüÜvwxyýz"
	       );
	       /* previously "ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz"*/
        // BUG!!!  In multi-lingual searches, this didn't include all letters :-(  Stil problematical for upper case
        fork_point[row][col] = rootdawg+1;
        strcpy(vertical_word[col], "");
      }
    }
    next_letter(results, rootdawg+1, 0, max, 0/*len*/);
    now = time(NULL); fprintf(results, "Finished: %s %s", topline, ctime(&now));fflush(results);

  }

  print_square(results, max,max,max,"Final state (non solution): ");

  // DEBUGGING.  SIGNALS REMOVED
  //signal(SIGALRM, SIG_DFL); // we're done.  reinstate the default handlers
  //signal(SIGUSR2, SIG_DFL);

  fclose(results);
#ifdef MPI
  MPI_Finalize();
#endif
  exit(0);
  return(0);
}