/*#define GTDEBUG*/
/*
 * 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)
{
long ret;
int ch;
  ret = 0;
  fprintf(stderr, "+{"); 
  for (;;) {
    ch = (int)(((dawg[edge] >> V_LETTER) & M_LETTER));
    if ('A' <= ch && ch <= 'Z') {
      ret |= (1UL << (unsigned long)((long)ch - (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 w[128];
int i, c;
int final;
  final = TRUE;
  if (l == 0) return(0==0);
  for (i = 0; i < l; i++) {
    c = word[i];
    if (c < 32 || c >= 127) c = '?';
    w[i] = c;
  }
  for (i = l; i < m; i++) {
    final = FALSE;
    w[i] = '?';
  }
  w[m] = '\0';
  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;
  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 < 1 || l > 15) {fprintf(stderr, "len = %d\n", l); exit(1);}
  ret = 0;
  if (check("Across ", dawg[l], mask, x, l, &root)) {
/*
    for(mask[x]='A'; mask[x]<='Z'; mask[x]++)
    {
      if (check("Across ", dawg[l], mask, x+1, l))
        ret|=1<<(mask[x]-'A');
    }
 */
    ret = get_branches(dawg[l], root);
  }

  return ret;
}

unsigned long getLettersDown(int x, int y, int ID)
{
  unsigned long ret=0U;
  int r;
  char     mask[20], maskHigh[20]; /* Taking address again... */
  char  *c1, *c2, *c3;
  int  l=down[ID].length, current=0, high;
  INDEX root;


  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;
  
  strncpy(maskHigh, mask, y);
  for(r=y-1; r>=0; r--)
    if(maskHigh[r]=='Z')
      maskHigh[r]='A';
    else
      break;

  /* check root length y, then see which letters can be added (y+1) */

  if (mask[0] == '.') return(ALLCHARS);
  ret = 0U;
  if (check("Down ", dawg[l], mask, y, l, &root)) {
/*
    for(mask[y]='A'; mask[y]<='Z'; mask[y]++)
    {
      if (check("Down ", dawg[l], mask, y+1, l, &root))
        ret|=1<<(mask[y]-'A');
    }
 */
    ret = get_branches(dawg[l], root);
  }

  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;
  for(i=0; letters && i<26; i++)
  {
    /*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))
        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);
          goto Return;
        }
      }
    }
    else
      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
  return 0;
}