/* file migmdet.c  23.10.95.
 * 6/8/98 large scale reorganisation to omit globals, etc.
 * 13/1/98 changes for the `gen' type replacing char for generators.
 *
 * This file contains the function migm_determinize, which makes the
 * multiple initial state generalised multiplier associated with
 * a coset automatic group deterministic.
 * That is, it computes the ordinary deterministic generalised multiplier.
 */

#define LABHTSIZE 8192

#include <stdio.h>
#include "defs.h"
#include "fsa.h"
#include "hash.h"
#include "externals.h"

/* Functions defined in this file: */
fsa *migm_determinize();
fsa *migm_determinize_short();
fsa *migm_determinize_int();

/* Functions used in this file and defined elsewhere */
int sparse_target();
void fsa_init();
void fsa_table_init();
void fsa_set_is_initial();
void srec_copy();
void fsa_copy();
void fsa_clear();
void compressed_transitions_read();
void hash_init();
void short_hash_init();
int  hash_locate();
int  short_hash_locate();
void hash_clear();
void short_hash_clear();
int* hash_rec();
unsigned short* short_hash_rec();
int hash_rec_len();
int short_hash_rec_len();
int genstrlen();
int stringlen();

fsa *
migm_determinize(migmptr,op_table_type,destroy,tempfilename)
	fsa *migmptr;
	storage_type op_table_type;
	boolean destroy;
	char *tempfilename;
/* The fsa *migmptr must be a migm.
 * The returned fsa accepts a accepts the same language but is deterministic.
 */
{
  if (kbm_print_level>=3)
    printf("    #Calling migm_determinize.\n");
  if (migmptr->states->size < MAXUSHORT)
    return migm_determinize_short(migmptr,op_table_type,destroy,tempfilename);
  else
    return migm_determinize_int(migmptr,op_table_type,destroy,tempfilename);
}

fsa *
migm_determinize_short(migmptr,op_table_type,destroy,tempfilename)
	fsa *migmptr;
	storage_type op_table_type;
	boolean destroy;
	char *tempfilename;
{
  int **table, ne, ngens, nssi, ns, dr, *fsarow,
      nt, cstate, csi, im, i, j, k, g1, len, nlab, ct;
  unsigned short *ht_ptr, *ht_chptr, *ht_ptrb, *ht_ptre,
                 *cs_ptr, *cs_ptre, *ptr;
  gen **w;
  boolean geninlab[MAXGEN+1];
  boolean dense_ip, dense_op;
  short_hash_table ht, labelht;
  setToLabelsType *newlabel;
  fsa *det;
  srec *labelset;
  FILE *tempfile, *fopen();

  if (kbm_print_level>=3)
    printf("    #Calling migm_determinize_short.\n");
  if (!migmptr->flags[MIDFA]){
    fprintf(stderr,"Error: migm_determinize only applies to MIDFA's.\n");
    return 0;
  }
  if (migmptr->alphabet->type!=PRODUCT || migmptr->alphabet->arity!=2) {
    fprintf(stderr, "Error in migm_determinize: fsa must be 2-variable.\n");
    return 0;
  }
  if (migmptr->states->type!=LABELED ||
      migmptr->states->labels->type!=LISTOFWORDS) {
    fprintf(stderr,
"Error in migm_determinize: states of fsa must be labels to lists of words.\n");
    return 0;
  }

  ne = migmptr->alphabet->size;
  ngens = migmptr->alphabet->base->size;

  tmalloc(det,fsa,1);
  fsa_init(det);
  srec_copy(det->alphabet,migmptr->alphabet);
  det->flags[DFA] = TRUE;
  det->flags[ACCESSIBLE] = TRUE;
  det->flags[BFS] = TRUE;

  det->table->table_type = op_table_type;
  det->table->denserows = 0;
  det->table->printing_format = op_table_type;

  dense_ip = migmptr->table->table_type==DENSE;
  dr = migmptr->table->denserows;
  dense_op = op_table_type==DENSE;
  table = migmptr->table->table_data_ptr;

  det->num_initial = 1;
  tmalloc(det->initial,int,2);
  det->initial[1] = 1;
  
  short_hash_init(&ht,FALSE,0,0,0);
  ht_ptr = ht.current_ptr;
  nssi = migmptr->num_initial;
  for (i=0;i<nssi;i++)
    ht_ptr[i] = migmptr->initial[i+1];
  im = short_hash_locate(&ht,nssi);
/* Each state in 'det' will be represented as a subset of the set of states
 * of *migmptr. The initial state contains the initial states
 * of *migmptr.
 * The subsets will be stored as variable-length records in the hash-table,
 * always in increasing order.
 */
  if (im!=1) {
    fprintf(stderr,"Hash-initialisation problem in migm_determinize.\n");
    return 0;
  }
  if ((tempfile=fopen(tempfilename,"w"))==0){
    fprintf(stderr,"Error: cannot open file %s\n",tempfilename);
    return 0;
  }
  if (dense_op)
    tmalloc(fsarow,int,ne)
  else
    tmalloc(fsarow,int,2*ne+1)
 
  cstate = 0;
  if (dense_op)
    len = ne; /* The length of the fsarow output. */
  nt = 0; /* Number of transitions in det */

  while (++cstate <= ht.num_recs) {
    if (kbm_print_level>=3) {
      if ((cstate<=1000 && cstate%100==0)||(cstate<=10000 && cstate%1000==0)||
          (cstate<=100000 && cstate%5000==0) || cstate%50000==0)
       printf("    #cstate = %d;  number of states = %d.\n",cstate,ht.num_recs);
    }
    cs_ptr = short_hash_rec(&ht,cstate);
    cs_ptre = short_hash_rec(&ht,cstate) + short_hash_rec_len(&ht,cstate) - 1;
    if (!dense_op)
      len = 0;

    for (g1=1;g1<=ne;g1++) {
/* Calculate action of generator g1 on state cstate  - to get the image, we
 * simply apply it to each state in the subset of states representing cstate.
 */
      ht_ptrb = ht.current_ptr;
      ht_ptre = ht_ptrb-1;
      ptr = cs_ptr-1;
      while (++ptr <= cs_ptre) {
        csi = target(dense_ip,table,g1,*ptr,dr);
        if (csi==0)
          continue;
        if (ht_ptrb>ht_ptre || csi> *ht_ptre) {
/* We have a new state for the image subset to be added to the end */
          *(++ht_ptre) = csi;
        }
        else {
          ht_chptr = ht_ptrb;
          while (*ht_chptr < csi)
            ht_chptr++;
          if (csi < *ht_chptr) {
/* we have a new state for the image subset to be added in the middle */
            ht_ptr = ++ht_ptre;
            while (ht_ptr > ht_chptr) {
              *ht_ptr = *(ht_ptr-1);
              ht_ptr--;
            }
            *ht_ptr = csi;
          }
        }
      }
      im = short_hash_locate(&ht,ht_ptre-ht_ptrb+1);
      if (im== -1) return 0;
      if (dense_op)
         fsarow[g1-1] = im;
      else if (im>0) {
         fsarow[++len] = g1;
         fsarow[++len] = im;
      }
      if (im>0)
        nt++;
    }
    if (!dense_op)
      fsarow[0] = len++;
    fwrite((void *)fsarow,sizeof(int),(size_t)len,tempfile);
  }
  fclose(tempfile);

  ns = det->states->size = ht.num_recs;
  det->table->numTransitions = nt;

/* Now we need to work out the labels of the states. These are lists of words
 * of length <= 1, arising from the lists in the states of *migmptr that
 * make up the relevant subset of states that is a state of *det.
 * We need another hash-table for this.
 */
  det->states->type = LABELED;
  tmalloc(det->states->labels,srec,1);
  labelset = det->states->labels;
  labelset->type = LISTOFWORDS;
  labelset->alphabet_size = migmptr->alphabet->base->size;
  for (i=1;i<=ngens;i++) {
    tmalloc(labelset->alphabet[i],char,
                     stringlen(migmptr->alphabet->base->names[i])+1);
    strcpy(labelset->alphabet[i],migmptr->alphabet->base->names[i]);
  }
  tmalloc(det->states->setToLabels,setToLabelsType,ns+1);
  newlabel = det->states->setToLabels;

  short_hash_init(&labelht,FALSE,0,LABHTSIZE,2*LABHTSIZE);

  tmalloc(det->is_accepting,boolean,ns+1);
  for (i=1;i<=ns;i++)
    det->is_accepting[i]=FALSE;
  for (cstate=1;cstate<=ns;cstate++) {
    ht_ptrb = labelht.current_ptr;
    ht_ptre = ht_ptrb-1;

    cs_ptr = short_hash_rec(&ht,cstate);
    cs_ptre = short_hash_rec(&ht,cstate) + short_hash_rec_len(&ht,cstate) - 1;
    for (i=0;i<=ngens;i++)
      geninlab[i]=FALSE; /* geninlab records which generators occur in label*/
    ptr = cs_ptr-1;
    while (++ptr <= cs_ptre) {
      if (j=migmptr->states->setToLabels[*ptr]) {
        w = migmptr->states->labels->wordslist[j];
        i=0;
        while (w[i]!=0) {
          if (genstrlen(w[i])<=1) {
            det->is_accepting[cstate]=TRUE;
            geninlab[w[i][0]]=TRUE;
          }
	  i++;
        }
      }
    }
    for (k=0;k<=ngens;k++) if (geninlab[k])
      *(++ht_ptre) = k==0 ? ngens+1 : k;
    /* that completes calculation of label for cstate */
    newlabel[cstate] = short_hash_locate(&labelht,ht_ptre-ht_ptrb+1);
    if (newlabel[cstate]== -1) return 0;
  }

  short_hash_clear(&ht);
  tfree(fsarow);

/* Finally copy the records from the label hash-table into the set of labels */
  nlab =
  labelset->size = labelht.num_recs;
  if (kbm_print_level>=3)
    printf("    #There are %d distinct labels.\n",nlab);
  tmalloc(labelset->wordslist,gen **,nlab+1);
  for (i=1;i<=nlab;i++) {
    len = short_hash_rec_len(&labelht,i);
    tmalloc(labelset->wordslist[i],gen *,len+1);
    ht_ptr = short_hash_rec(&labelht,i);
    for (j=0;j<len;j++) {
      if (ht_ptr[j]==ngens+1) {
        tmalloc(labelset->wordslist[i][j],gen,1);
        labelset->wordslist[i][j][0] = 0;
      }
      else {
        tmalloc(labelset->wordslist[i][j],gen,2);
        labelset->wordslist[i][j][0] = ht_ptr[j];
        labelset->wordslist[i][j][1] = 0;
      }
    }
    labelset->wordslist[i][len] = 0;
  }

  short_hash_clear(&labelht);
  ct=0;
  for (i=1;i<=ns;i++) if (det->is_accepting[i])
    ct++;
  det->num_accepting=ct;
  tmalloc(det->accepting,int,ct+1);
  ct=0;
  for (i=1;i<=ns;i++) if (det->is_accepting[i])
    det->accepting[++ct]=i;
  tfree(det->is_accepting);

  if (destroy)
    fsa_clear(migmptr);

/* Now read the transition table back in */
  tempfile = fopen(tempfilename,"r");
  compressed_transitions_read(det,tempfile);
  fclose(tempfile);

  unlink(tempfilename);

  return det;
}

fsa *
migm_determinize_int(migmptr,op_table_type,destroy,tempfilename)
	fsa *migmptr;
	table_struc op_table_type;
	boolean destroy;
	char *tempfilename;
{
  fprintf(stderr,
	"Sorry - migm_determinize is not yet implemented for machines.\n");
  fprintf(stderr,"with more than 65536 states.\n");
  return 0;
}
