/*
 * fill.c
 *
 * Copyright (C) 1990 Rob Mayoff.
 */

#ifdef DEBUG
#include <curses.h>
#endif
#include <stdio.h>
#include <string.h>
#include "grid.h"
#include "word.h"
#include "misc.h"

#define ALLCHARS ((1<<26)-1)

#include "splib.h"

INDEX dawg_locate_prefix(NODE *dawg, char *word, INDEX edge)
{
  for (;;) {
    if (*word == (((dawg[edge] >> V_LETTER) & M_LETTER))) {
      if (*++word == '?') {
        return(dawg[edge]&M_NODE_POINTER);
      } else {
        if ((edge = (dawg[edge] & M_NODE_POINTER)) == ROOT_NODE) break;
        continue;
      }
    }
    if (((dawg[edge++]) & M_END_OF_NODE) != 0) break;
  }
  return(0);
}

unsigned long get_branches(NODE *dawg, INDEX edge, char *start, char *how)
{
unsigned long ret;
int ch;
  ret = 0L;
  /*fprintf(stderr, "get branches %s%p[%ld] %s+{", how, dawg, edge, start);*/
  for (;;) {
    ch = (int)(((dawg[edge] >> V_LETTER) & M_LETTER));
    if ('A' <= ch && ch <= 'Z') {
      ret |= (unsigned long)(1UL << ((unsigned long)ch - (unsigned long)'A'));
      /*fprintf(stderr, "%c", ch);*/
    }
    if (((dawg[edge++]) & M_END_OF_NODE) != 0) break;
  }
  /*fprintf(stderr, "} %8lx\n", ret);*/
  return(ret);
}

NODE *dawg[16] = { NULL };

int check(char *pref, NODE *dawg, char *word, int l, int m, INDEX *idx, char *ww) {
int i, c;
int final;
char w[128];
  final = TRUE;
  ww[0] = '\0';
  if (l == 0) return(0==0);
  for (i = 0; i < l; i++) {
    c = word[i];
    if (c == '.') return(0==0);
    if (c < 32 || c >= 127) {
      fprintf(stderr, "data error %d\n", c); exit(3);
    }
    w[i] = c;
  }
  for (i = l; i < m; i++) {
    final = FALSE;
    w[i] = '?';
  }
  w[m] = '\0';
  strcpy(ww, w);
  if (final) {
    i = dawg_check(dawg, w);
    /*fprintf(stderr, "%sword%d: %s -> %d\n", pref, m, w, i);*/
    *idx = 0;
    return(i);
  }
  *idx = dawg_locate_prefix(dawg, w, ROOT_NODE);
  /*fprintf(stderr, "%sprefix%d: %s -> %ld\n", pref, m, w, *idx);*/
  return(*idx != 0);
}


unsigned long getLettersAcross(int x, int y, int ID)
{
  unsigned long ret;
  char     mask[20];
  INDEX    root = 0;
  char w[128];
  int l;

  x-=across[ID].x;
  strncpy(mask, &grid[y][across[ID].x], x);
  mask[x] = '\0';
  
  /* First, do a check of the root (length x), then see which letters
     can be added. */
  l = across[ID].length;
  if (l == 0) return(ALLCHARS);
  if (l < 1 || l > 15) {fprintf(stderr, "len = %d\n", l); exit(1);}
  ret = 0;
  if (check("Across ", dawg[l], mask, x, l, &root, w)) {
    ret = get_branches(dawg[l], root, mask, "across ");
  }

  return ret;
}

unsigned long getLettersDown(int x, int y, int ID)
{
  unsigned long  ret;
  char     mask[20];
  char w[128] = { '\0' };
  char  *c1, *c2, *c3;
  int  l;
  INDEX root;

  ret = 0;
  l = down[ID].length;

  mask[0] = '\0';
  w[0] = '\0';
  c1 = NULL; c2 = NULL; c3 = NULL;
  root = 0L;

  y-=down[ID].y;
  for(c1=&grid[down[ID].y][x], c2=&grid[down[ID].y+y][x], c3=mask;
      c1<c2; c1+=G_REAL_WIDTH, c3++)
    *c3=*c1;
  
  /* check root length y, then see which letters can be added (y+1) */

  if (mask[0] == '.') return(ALLCHARS);

  if (check("Down ", dawg[l], mask, y, l, &root, w)) {
    ret = get_branches(dawg[l], root, mask, "down ");
  }

  return ret;
}

/* Moves position i to position 1 and shifts 2..(i-1) down. */
void roll(char *s, int i)
{
  int  j;
  char c;

  c=s[i];
  for(j=i-1; j>=0; j--)
    s[j+1]=s[j];
  s[0]=c;
}

#define BT_ACROSS       0x1
#define BT_DOWN         0x2

int     backTrack;
int     BTacrossID, BTdownID;

void    setBackTrack(int x, int y)
{
  if(grid[y-1][x]!=BLOCK)
    backTrack=BT_DOWN;
  else
    backTrack=0;
  if(grid[y][x-1]!=BLOCK)
    backTrack|=BT_ACROSS;
  BTacrossID=acrossID[y][x];
  BTdownID=downID[y][x];
}

int fill(int id)
{
  unsigned long        letters;
  char letter;
  int  /*rc,*/ x, y, i; /* rc not used */
  char *f;
  /* int       BTdownMe, BTacrossMe; */  /* Not used */

  x=stack[id].x;
  y=stack[id].y;
  letters=getLettersAcross(x, y, stack[id].acrossID);
  letters&=getLettersDown(x, y, stack[id].downID);
  if(!letters)
  {
    setBackTrack(x, y);
    return 0;
  }
  /*fprintf(stderr, "valid letters: %8lx\n", letters);*/
  f=stack[id].order;
  intr(1);
  for(i=0; letters && i<26; i++)
  {
    /******** Compiler bug - remov this & it breaks!!! ********/
    /*********   fprintf(stderr, "try %c\n", i+'A');  *********/
    /*fprintf(stderr, "try %c\n", i+'A');*/
    letter=f[i];
    if(!(letters&(1L<<(long)((long)letter-'A')))) /* Loss of precision */
      continue;
    letters^=1L<<(long)((long)letter-'A'); /* ditto */
    grid[y][x]=letter;
#ifdef DEBUG
    mvaddch(y, x, letter);
    refresh();
#endif
    if(id+1<stackTop)
    {
      if(fill(id+1)) {
        /*fprintf(stderr, "<fill 1\n");*/
        return 1;
      }
      el(backTrack)
      {
        if(acrossID[y][x]==BTacrossID)
          backTrack&=~BT_ACROSS;
        el(downID[y][x]==BTdownID)
          backTrack&=~BT_DOWN;
        else
        {
          if(i>0)
            roll(f, i);
          /*fprintf(stderr, "<fill 2+\n");*/
          goto Return;
        }
      }
    }
    else {
      /*fprintf(stderr, "<fill 3\n");*/
      return 1;
    }
  }

  if(!letters && !backTrack)
    setBackTrack(x, y);
Return:
  grid[stack[id].y][stack[id].x]=SPACE;
#ifdef DEBUG
  mvaddch(y, x, SPACE);
  refresh();
#endif
  /*fprintf(stderr, "<fill 4\n");*/
  return 0;
}