/* diffreduce.c  1/11/95
 * 6/8/98 large-scale re-organisation to elimiante externals.
 * 9/1/98 type of generator changed from char to `gen' 
 * Copied from old automata package and edited.
 * This file contains the procedure for reducing a word using a
 * word-difference machine *wd_fsa (defined externally).
 */
#include "defs.h"
#include "fsa.h"
#include "rws.h"
#include "externals.h"

#define MAXV 65536 /* The maximum number of vertices allowed. */

/* functions defined in this file */
int diff_reduce();

/* functions defined in other files used in this file */
int genstrlen();

int
diff_reduce(w,rs_wd)
        gen              *w;
        reduction_struct *rs_wd;
/* w is the word to be reduced using the word-difference machine  *wd_fsa.
 * It is assumed that wd_fsa->table->table_data_dptr is set up.
 * This function allocates its own space.
 * NOTE: No checks on the validity of the word are carried out.
 */
{ int ndiff, ngens, identity, padsymbol, wordlen, ***difftab,
      gct, *gpref, level, gen1, gen2, diff, diffct, newdiff,
      olen, nlen, i, j;
  boolean deqi, donesub, *cf;
  fsa *wd_fsa = rs_wd->wd_fsa;
  int maxv = MAXV;
  struct vertexd {
       gen genno;
       int diffno;
       int sublen;
       struct vertexd *backptr;
  }
       *gptr, *ngptr, *substruc;

/* vertexd is the structure used to store a vertex in the graph of strings
   for possible substitution. The components are as follows.
   backptr - points back to another vertexd, or to zero.
   genno  - the number of the generator at the end of the string.
   diffno - the word difference number of the string defined by following
            backptr back to zero (using genno), relative to the corresponding
            part of the word being reduced.
   sublen - plus or minus the length of this string. sublen is positive if and
            only if the string lexicographically precedes the
            corresponding part of the word being reduced.
   sublen is put in to save time.
    Another essential component of a vertexd is its level (i.e. the length of
    the string got by chasing back to the beginning of the word)
    but we always calculate this, using
    the integers defined by gpref. (See below))
*/

  if (wd_fsa->alphabet->type != PRODUCT || wd_fsa->alphabet->arity != 2) {
    fprintf(stderr,
        "Error: diff_reduce must be called with a word-difference machine.\n");
    return -1;
  }
  ndiff = wd_fsa->states->size;
  ngens = wd_fsa->alphabet->base->size;
  identity = wd_fsa->initial[1];
  padsymbol = ngens+1;
  wordlen= genstrlen(w);
  if (wordlen<=0)
    return 0;
  difftab = wd_fsa->table->table_data_dptr;
  w = w-1; /* since code below assumes word is from w[1] .. w[wordlen]. */

  tmalloc(cf,boolean,ndiff+1);
/* cf is used as a characteristic function, when constructing a subset of the
  set  D  of word differences.
*/

  tmalloc(gpref,int,wordlen+1);
  gct= -1;
  gpref[0]= -1;
/* gpref[n]+1 is the number of vertices that have been defined after reading the
  first n elements of the word. These vertices are gptr[0],...,gptr[gpref[n]].
  We start by allocating space for maxv vertices.
*/

  tmalloc(gptr,struct vertexd,maxv);

/* Now we start reading the word. */
  level=0;
  while (++level<=wordlen) {
    for (i=1;i<=ndiff;i++)
      cf[i]=FALSE;
/* Read the element of the word at position level. */
    gen1= w[level];

/* The next loop is over the identity and the subset of D defined at the
   previous level, level-1.
*/
    diff = identity;
    while (1) {
      deqi= diff==identity;
/* First look for a possible substitution of a shorter string */
      newdiff = dense_dtarget(difftab,gen1,padsymbol,diff);
      if (newdiff==identity) {
/* Make substitution and reduce length of word by 1. */
        i = level-1;
        if (!deqi) {
          substruc = gptr+diffct;
          do {
            w[i] = substruc->genno;
            substruc = substruc->backptr;
            i--;
          } while (substruc);
        }
        for (j=level;j<wordlen;j++)
          w[j] = w[j+1];
        w[wordlen] = 0;
        wordlen--;

/* Whenever we make a substitution, we have to go back one level more than
   expected, because of our policy of looking ahead for substitutions
   that reduce the length by 2.
*/
        level= i>0 ? i-1 : i;
        gct = gpref[level];
        break;
      }
      else if (newdiff && level<wordlen) {
        j = dense_dtarget(difftab,w[level+1],padsymbol,newdiff);
        if (j==identity)
/* Make substitution and reduce length of word by 2. */
        { i = level-1;
          if (!deqi) {
            substruc=gptr+diffct;
            do {
              w[i] = substruc->genno;
              substruc = substruc->backptr;
              i--;
            } while (substruc);
          }
          for (j=level;j<wordlen-1;j++)
            w[j] = w[j+2];
          w[wordlen-1] = 0;
          wordlen -= 2;
          level = i>0 ? i-1 : i;
          gct = gpref[level];
          break;
        }
      }

      donesub = FALSE;
/* Now we loop over the generator that is a candidate for substitution
   at this point.
*/
      for (gen2=1;gen2<=ngens;gen2++)
       if (newdiff = dense_dtarget(difftab,gen1,gen2,diff)) {
        if (newdiff==identity) {
          if (deqi) {
            if (gen2<gen1) {
              w[level] = gen2;
              level = level>1 ? level-2 : level-1;
              gct = gpref[level];
              donesub = TRUE;
              break;
            }
          }
          else if (gptr[diffct].sublen > 0) {
/* Make a substitution (by a string of equal length). */
            w[level] = gen2;
            i = level-1;
            substruc = gptr+diffct;
            do {
              w[i] = substruc->genno;
              substruc = substruc->backptr;
              i--;
            } while (substruc);
            level = i>0 ? i-1 : i;
            gct = gpref[level];
            donesub = TRUE;
            break;
          }
        }
        else {
          if (cf[newdiff])
/* We have this word difference stored already, but we will check to see if
   the current string precedes the existing one.
*/
            for (i=gpref[level-1]+1;;i++) {
              substruc=gptr+i;
              if (substruc->diffno == newdiff) {
                olen = substruc->sublen;
                nlen = deqi ? (gen2 < gen1 ? 1 : -1) : 
                       (j = (gptr[diffct].sublen))>0 ? j+1 : j-1;
                if (nlen > olen) {
/* The new string is better than the existing one */
                  substruc->genno = gen2;
                  substruc->sublen = nlen;
                  substruc->backptr = deqi ? 0 : gptr+diffct;
                }
                break;
              }
            }
          else
/* This is a new word difference at this level, so we define a new vertexd in
   graph.
*/
          { gct++;
            if (gct >= maxv) {
/* We need more space for vertices. Allocate twice the preceding space and
   copy existing data.
*/
              tmalloc(ngptr,struct vertexd,2*maxv);
              if (kbm_print_level>=3)
                printf("    #Allocating more space in diff_reduce.\n");
              for (i=0;i<maxv;i++) {
                ngptr[i].genno = gptr[i].genno;
                ngptr[i].diffno = gptr[i].diffno;
                ngptr[i].sublen = gptr[i].sublen;
                substruc = gptr[i].backptr;
                if (substruc==0)
                  ngptr[i].backptr = 0;
                else
                  for (j=i-1;;j--) if (substruc==gptr+j) {
                    ngptr[i].backptr = ngptr+j;
                    break;
                  }
              }
              tfree(gptr);
              gptr=ngptr;
              maxv *= 2;
            }
/* Define the new vertexd. */
            substruc = gptr+gct;
            nlen = deqi ? (gen2<gen1 ? 1 : -1) : 
                       (j = (gptr[diffct].sublen))>0 ? j+1 : j-1;
            substruc->genno = gen2;
            substruc->diffno = newdiff;
            substruc->sublen = nlen;
            substruc->backptr = deqi ? 0 : gptr+diffct;
            cf[newdiff] = TRUE;
          }
        }
      } /*End of loop over gen2 */

      if (donesub)
        break;

/* Go on to next word difference from previous level. */
      if (diff==identity) {
        if (level==1) break;
        diffct = gpref[level-2]+1;
      }
      else
        diffct++;
      if (diffct > gpref[level-1])
         break;
      diff = gptr[diffct].diffno;
    } /* end of loop over word differences at previous level */

    gpref[level] = gct;
  }

  tfree(gptr);
  tfree(cf);
  tfree(gpref);
  return 0;
}
