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

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

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

int	searchFlag;

int binSearch(register int low, register int high, register int length,
	register int cmpLength, register char *mask)
{
  register int	current, rc;

  searchFlag=0;
  while(low!=high)
  {
    current=(low+high)>>1;
    rc=strncmp(mask, WORD(length, current), cmpLength);
    if(rc>0)
      low=current+1;
    else
      high=current;
  }
  if(strncmp(mask, WORD(length, low), cmpLength))
    searchFlag=1;
  return low;
}

unsigned long getLettersAcross(register int x, register int y, int ID)
{
  register int	ret;
  register char	mask[20], maskHigh[20];
  register int	l=across[ID].length, current=0, high;

  x-=across[ID].x;
  strncpy(mask, &grid[y][across[ID].x], x);
  
  strncpy(maskHigh, mask, x);
  for(ret=x-1; ret>=0; ret--)
    if(maskHigh[ret]=='Z')
      maskHigh[ret]='A';
    else
      break;
  if(ret<0)
    high=numWords[l];
  else
  {
    maskHigh[ret]++;
    high=binSearch(0, numWords[l], l, x, maskHigh);
  }

  ret=0;
  for(mask[x]='A'; mask[x]<='Z'; mask[x]++)
  {
    current=binSearch(current, high, l, x+1, mask);
    if(!searchFlag)
      ret|=1<<(mask[x]-'A');
  }

  return ret;
}

unsigned long getLettersDown(register int x, register int y, int ID)
{
  register int	ret=0;
  register char	mask[20], maskHigh[20], *c1, *c2, *c3;
  register int	l=down[ID].length, current=0, high;

  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(ret=y-1; ret>=0; ret--)
    if(maskHigh[ret]=='Z')
      maskHigh[ret]='A';
    else
      break;
  if(ret<0)
    high=numWords[l];
  else
  {
    maskHigh[ret]++;
    high=binSearch(0, numWords[l], l, y, maskHigh);
  }

  ret=0;
  for(mask[y]='A'; mask[y]<='Z'; mask[y]++)
  {
    current=binSearch(current, high, l, y+1, mask);
    if(!searchFlag)
      ret|=1<<(mask[y]-'A');
  }

  return ret;
}

/* Moves position i to position 1 and shifts 2..(i-1) down. */
void roll(register char *s, register int i)
{
  register int	j;
  register 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(register int x, register 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(register int id)
{
  register unsigned long	letters;
  register char	letter;
  register int	rc, x, y, i;
  register char	*f;
  register int	BTdownMe, BTacrossMe;

  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;
  }

  f=stack[id].order;
  for(i=0; letters && i<26; i++)
  {
    letter=f[i];
    if(!(letters&(1<<(letter-'A'))))
      continue;
    letters^=1<<(letter-'A');
    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;
}