/* gpsubpres.c   16/1/96. 
 * 13/10/98 large scale reorganisation to omit globals, etc.
 * 16/3/96 - changed command-line syntax to
 * gpmimult [options] groupname [subfilename]
 * where subfilename defaults to "sub".
 * Find relations of a subgroup of a coset automatic group, using the
 * Schreier generators that are the initial states of the generalised
 * multiplier automaton.
 * It is based on gpaxioms. We form the coset mi-multipliers for the group
 * relators, and then their initial states are the relators of the subgroup.
 *
 * This program assumes that makecosfile, kbprogcos, gpmakefsa -cos,
 * gpaxios -cos, have already been run on groupname.
 *
 * Input is from groupname (for group relators) and groupname.cosfile.gm
 * where cosfile is derived from subfilename as in makecosfile.
 * Output is to groupname.subfilename.pres, in GAP format.
 *
 * SYNOPSIS:
 * gpsubpres [-ip d/s[dr]] [-op d/s] [-silent] [-v] [-l] [-s] [-pref prefix] 
 *           groupname [subfilename]
 *
 * OPTIONS:
 * -ip d/s[dr]  input in dense or sparse format - dense is default
 * -op d/s      output in dense or sparse format - sparse is default
 * -v           verbose
 * -silent      no diagnostics
 * -l/-h        large/huge hash-tables (for big examples)
 * -s		Throw away files immediately after use whenever possible, to
 *              save disk-space. This will slow things down considerably.
 * -pref prefix Use the string 'prefix' as prefix for subgroup generators
 *              Their names are 'prefix'1. 'prefix'2, etc.
 *              Default is "_x".
 *              It will also be used as the name of the group in the GAP file.
 */

#include <stdio.h>

#include "defs.h"
#include "fsa.h"
#include "rws.h"
#include "definitions.h"

#define MAXEQNS		1024
#define MAXREDUCELEN	4096

static rewriting_system  rws, *rwsptr;

static char gpname[100], subname[100], cosgpname[100], inf[100], outf[100],
            outfp[100], fsaname[100],
       prefix[16], tablefilename[100];
static fsa migm, migm2, *migm2ptr;
static int ngens, neqns, *inv, numstoredmult, nsubgens;
static reduction_equation *eqn;
static char **storedmult;
static storage_type ip_store = DENSE;
static int dr = 0;
static storage_type op_store = SPARSE;
static boolean readback = TRUE;
static boolean keepfiles = TRUE;
static boolean first_relator;
static FILE *rfile, *wfile, *wfilep;

/* Functions defined in this file */
char *file_suffix();
int  find_subrels();
int  long_word_multiplier();
void badusage_gpsubpres();

/* Functions used in this file defined in other files: */
void read_kbinput_simple();
void printbuffer();
void add_to_buffer();
int add_word_to_buffer();
int int_len();
void fsa_table_dptr_init();
fsa  *fsa_migm2();
int   fsa_mimakemult();
int   fsa_mimakemult2();
fsa  *fsa_micomposite();
int  midfa_labeled_minimize();
int  mimult_minimize();
void fsa_clear();
void rws_clear();
int stringlen();
int genstrlen();
int genstrcmp();
void genstrcpy();

main(argc, argv)
        int             argc;
        char           *argv[];
{ int arg, i, j, l, ct;
  char *suffl, *suffr;
  gen *relator, *ptr, *ptr2;
  boolean gotl, gotr;
  boolean seengpname, seensubname;

  setbuf(stdout,(char*)0);
  setbuf(stderr,(char*)0);

  rwsptr= &rws;
  rwsptr->maxeqns = MAXEQNS;
  rwsptr->maxreducelen = MAXREDUCELEN;
  rwsptr->maxreducelenset = FALSE;
  rwsptr->cosets = FALSE;
   /* even in the cosets case we read relations from original group file */
  rwsptr->inv_of=0;
  rwsptr->weight=0;rwsptr->level=0;rwsptr->history=0;
  rwsptr->slowhistory=0;rwsptr->slowhistorysp=0;
  rwsptr->preflen=0;rwsptr->prefno=0;

  strcpy(prefix,"_x");
  arg = 1;
  seengpname=seensubname=FALSE;
  while (argc > arg) {
    if (strcmp(argv[arg],"-ip")==0) {
      arg++;
      if (arg >= argc)
        badusage_gpsubpres();
      if (strcmp(argv[arg],"d")==0)
        ip_store = DENSE;
      else if (argv[arg][0] == 's') {
        ip_store = SPARSE;
        if (stringlen(argv[arg]) > 1)
          dr = atoi(argv[arg]+1);
      }
      else
        badusage_gpsubpres();
    }
    else if (strcmp(argv[arg],"-op")==0) {
      arg++;
      if (arg >= argc)
        badusage_gpsubpres();
      if (strcmp(argv[arg],"d")==0)
        op_store = DENSE;
      else if (strcmp(argv[arg],"s")==0)
        op_store = SPARSE;
      else
        badusage_gpsubpres();
    }
    else if (strcmp(argv[arg],"-silent")==0)
      kbm_print_level = 0;
    else if (strcmp(argv[arg],"-v")==0)
      kbm_print_level = 2;
    else if (strcmp(argv[arg],"-vv")==0)
      kbm_print_level = 3;
    else if (strcmp(argv[arg],"-l")==0)
      kbm_large = TRUE;
    else if (strcmp(argv[arg],"-h")==0)
      kbm_huge = TRUE;
    else if (strcmp(argv[arg],"-s")==0)
      keepfiles = FALSE;
    else if (strcmp(argv[arg],"-pref")==0) {
      arg++;
      if (arg >= argc)
        badusage_gpsubpres();
      strcpy(prefix,argv[arg]);
    }
    else if (argv[arg][0] == '-')
      badusage_gpsubpres();
    else if (!seengpname) {
      seengpname=TRUE;
      strcpy(gpname,argv[arg]);
    }
    else if (!seensubname) {
      seensubname=TRUE;
      strcpy(subname,argv[arg]);
    }
    else
      badusage_gpsubpres();
    arg++;
  }
  if (!seengpname)
    badusage_gpsubpres();
  if (!seensubname)
    strcpy(subname,"sub");
  if (strncmp(subname,"sub",3)==0) {
    strcpy(cosgpname,gpname);
    strcat(cosgpname,".cos");
    strcat(cosgpname,subname+3);
  }
  else {
    strcpy(cosgpname,gpname);
    strcat(cosgpname,".");
    strcat(cosgpname,subname);
    strcat(cosgpname,"_cos");
  }
  
  strcpy(tablefilename,cosgpname);
  strcat(tablefilename,"temp_axXXX");

/* First read in the defining relations for the group. */
  strcpy(inf,gpname);
  if ((rfile = fopen(inf,"r")) == 0) {
    fprintf(stderr,"Cannot open file %s.\n",inf);
      exit(1);
  }
  read_kbinput_simple(rfile,FALSE,rwsptr);
  fclose(rfile);
  ngens = rws.num_gens;
  neqns = rws.num_eqns;
  inv = rws.inv_of;
  eqn = rws.eqns;

/* Now read in the general multiplier, and see how many subgroup generators
 * there are (which is just the number of initial states - 1).
 */
  strcpy(inf,cosgpname);
  strcat(inf,".migm");
  if ((rfile = fopen(inf,"r")) == 0) {
    fprintf(stderr,"Cannot open file %s.\n",inf);
      exit(1);
  }
  fsa_read(rfile,&migm,ip_store,dr,0,TRUE,fsaname);
  fclose(rfile);

  nsubgens = migm.num_initial - 1;
  /* The first initial state always corresponds to the identity.
   * Now we can open the output file and commence the output in GAP format.
   */
  sprintf(outfp,"%s.%s.pres",gpname,subname);
  wfilep = fopen(outfp,"w");
  fprintf(wfilep,"%sg := FreeGroup(%d);\n",prefix,nsubgens);
  for (i=1;i<=nsubgens;i++)
    fprintf(wfilep,"%s%d := %sg.%d;\n",prefix,i,prefix,i);
  fprintf(wfilep,"%s_relators:=[\n",prefix);

 /* Now calculate the general multiplier for words of length 2 */
  if (kbm_print_level>1)
    printf(
           "  #Calculating general word-length 2 multiplier.\n");
  migm2ptr = fsa_migm2(&migm,op_store,TRUE,tablefilename,readback,prefix);
  if (migm2ptr==0) exit(1);
  if (kbm_print_level>1)
    printf(
         "  #Number of states of migm2 = %d.\n",migm2ptr->states->size);
  
  if (readback) { /* always true */
    if (midfa_labeled_minimize(migm2ptr)==-1) exit(1);
  }
/*
  else
    fsa_ip_labeled_minimize(migm2ptr);
*/
  if (kbm_print_level>1)
    printf("  #Number of states of migm2 after minimization = %d.\n",
             migm2ptr->states->size);
  strcpy(fsaname,rws.name);
  strcat(fsaname,".migm2");
  strcpy(outf,cosgpname);
  strcat(outf,".migm2");
  wfile = fopen(outf,"w");
  fsa_print(wfile,migm2ptr,fsaname);
  if (kbm_print_level>0)
    printf("#General length-2 multiplier with %d states computed.\n",
          migm2ptr->states->size);
  fclose(wfile);
  fsa_clear(migm2ptr);
  tfree(migm2ptr);


/* If keepfiles is false, then we will throw away every multiplier immediately
 * after it has been used. Otherwise, we will keep them, in case they are
 * needed again.
 * We store a list of words for which we have got the multipliers in
 * storedmult. We first form a rough upper bound on how long this list
 * could get - ngens + total relator length - 1.
 */
  strcpy(fsaname,rws.name);
  strcat(fsaname,".mimult"); /* this is unimportant, since file is temporary */
  if (keepfiles) {
    ct = ngens;
    for (i=1;i<=neqns;i++)
      ct += (genstrlen(eqn[i].lhs) + genstrlen(eqn[i].rhs));
    tmalloc(storedmult,char *,ct);
    numstoredmult = 0;
  }

/* Now we are ready to start building the multipliers for the group relators,
 * which will give rise to the subgroup relators.
 * We use rws.testword1 to store the relators of G as they arise.
 * We start with the inverse relators.
 */
  first_relator=TRUE;
  relator = rws.testword1;
  for (i=1;i<=ngens;i++) {
    relator[0]=i; relator[1]=inv[i]; relator[2]='\0';
    if (kbm_print_level > 0) {
      kbm_buffer[0] = '\0';
      add_to_buffer(0,"#Processing relator:  ");
      add_word_to_buffer(stdout,relator,rws.gen_name);
      printbuffer(stdout,kbm_buffer);
    }
    if (find_subrels(relator)==-1) exit(1);
  }

/* Now the other relators.
 * We first need to get them from equation to relator form.
 */
  for (i=1;i<=neqns;i++) {
    if (genstrlen(eqn[i].lhs)==0 &&  genstrlen(eqn[i].rhs)==0)
      continue;
    genstrcpy(relator,eqn[i].lhs);
    ptr = relator+genstrlen(relator);
    ptr2 = eqn[i].rhs;
    for (j=genstrlen(ptr2)-1;j>=0;j--)
      *(ptr++) = inv[ptr2[j]];
    *ptr='\0';
    if (genstrlen(relator)==2 && relator[1]==inv[relator[0]])
      continue; /* since we have already done this one */
    if (kbm_print_level > 0) {
      kbm_buffer[0] = '\0';
      add_to_buffer(0,"#Processing relator:  ");
      add_word_to_buffer(stdout,relator,rws.gen_name);
      printbuffer(stdout,kbm_buffer);
    }
    if (find_subrels(relator)==-1) exit(1);
  }

  fprintf(wfilep,"\n];\n");
  fclose(wfilep);

  if (keepfiles) {
    for (i=1;i<=numstoredmult;i++) {
      sprintf(outf,"%s.mim%s",cosgpname,storedmult[i]);
      unlink(outf);
      tfree(storedmult[i]);
    }
    tfree(storedmult);
  }
  strcpy(outf,cosgpname);
  strcat(outf,".migm2");
  unlink(outf);
  rws_clear(&rws);
  exit(0);
}

char *
file_suffix(w)
	gen *w;
/* For a word w in the generators, this function returns a corresponding
 * string with the terms of w replaced by integers separated by '_'.
 * This is used as a suffix in the filenames used for storing the
 * corresponding multiplier fsa's.
 */
{ char *s;
  gen *p;
  boolean first;
  int len;
/* First work out the length of the required string. */
  len = genstrlen(w);
  p = w-1;
  while (*(++p) != 0)
    len += int_len((int)(*p));
  tmalloc(s,char,len);
  s[0] = '\0';
  first = TRUE;
  p = w-1;
  while (*(++p) != 0) {
    if (first)
      first = FALSE;
    else
      sprintf(s+stringlen(s),"_");
    sprintf(s+stringlen(s),"%d",*p);
  }
  return s;
}

int
find_subrels(r)
  gen *r;
  /* Find and output the subgroup relators arising from the group relator */
{ char *suff;
  gen ***labnames, *rel, *relend;
  char **alph;
  boolean got, *laboccurs;
  fsa mult;
  int i, j, nlabs;
  
  suff = file_suffix(r);
  /* First see if we have formed the multiplier for  r  already - if
   * not, build and store it using long_word_multiplier().
   */
  got=FALSE;
  if (keepfiles) {
    for (i=1;i<=numstoredmult;i++) {
      if (strcmp(suff,storedmult[i])==0) {
        got = TRUE;
        break;
      }
    }
  }
  if (!got) {
    if (long_word_multiplier(r,suff)==-1) return -1;
  }
  /* Now we read the composite multiplier in */
  sprintf(inf,"%s.mim%s",cosgpname,suff);
  if ((rfile = fopen(inf,"r")) == 0) {
    fprintf(stderr,"Cannot open file %s.\n",inf);
      exit(1);
  }
  fsa_read(rfile,&mult,ip_store,dr,0,TRUE,fsaname);
  fclose(rfile);
  /* Now we write the words for its initial states into the GAP file.
   * They occur among the names of the labels of the state-set.
   */
  nlabs=mult.states->labels->size;
  tmalloc(laboccurs,boolean,nlabs+1);
  for (i=1;i<=nlabs;i++)
    laboccurs[i]=FALSE;
  for (i=1;i<=mult.states->size;i++)
    laboccurs[mult.states->setToLabels[i]] = TRUE;
  labnames = mult.states->labels->wordslist;
  alph = mult.states->labels->alphabet;
  for (i=1;i<=nlabs;i++) if (laboccurs[i]) {
    j=0;
    while (labnames[i][j]) {
      rel = labnames[i][j];
      if (*rel != '\0') {
        /* We have a subgroup relator */
        if (first_relator) {
          first_relator=FALSE;
          fprintf(wfilep,"  ");
        }
        else
          fprintf(wfilep,",\n  ");
        relend = rel+genstrlen(rel)-1;
        while (rel<=relend) {
          fprintf(wfilep,"%s",alph[*rel]);
          if (rel!=relend)
            fprintf(wfilep,"*");
          rel++;
        }
      }
      j++;
    }
  }
  fsa_clear(&mult);
  unlink(inf);
  tfree(suff);
  tfree(laboccurs);
  return 0;
}

int
long_word_multiplier(w,s)
	gen *w;
       char *s;
/* Calculate the multiplier associated with the word w.
 * s is the suffix of the file in which it will be stored.
 * (s has been derived from w by a call of file_suffix.)
 */
{ int i, l;
  gen *wl, *wlt, *wr, *wrt;
  char *suffl, *sufflt, *suffr, *suffrt;
  boolean gotl, gotr, gotlt, gotrt;
  fsa mult1, mult2, *compmult;
  if (kbm_print_level >= 3) {
    kbm_buffer[0] = '\0';
    add_to_buffer(0,"  #Calculating multiplier for word:  ");
    add_word_to_buffer(stdout,w,rws.gen_name);
    printbuffer(stdout,kbm_buffer);
  }
  l = genstrlen(w);

  if (l==1) { /* Length 1 - use fsa_mimakemult */
    strcpy(inf,cosgpname);
    strcat(inf,".migm");
    if ((rfile = fopen(inf,"r")) == 0) {
      fprintf(stderr,"Cannot open file %s.\n",inf);
        exit(1);
    }
    fsa_read(rfile,&migm,op_store,0,0,TRUE,fsaname);
    fclose(rfile);
    if (fsa_mimakemult(&migm,w[0],prefix)==-1) return -1;
    if (mimult_minimize(&migm)==-1) return -1;
    sprintf(outf,"%s.mim%s",cosgpname,s);
    wfile = fopen(outf,"w");
    fsa_print(wfile,&migm,fsaname);
    fclose(wfile);
    fsa_clear(&migm);
  }
  else if (l==2) { /* Length 2 - use fsa_mimakemult2 */
    strcpy(inf,cosgpname);
    strcat(inf,".migm2");
    if ((rfile = fopen(inf,"r")) == 0) {
      fprintf(stderr,"Cannot open file %s.\n",inf);
        exit(1);
    }
    fsa_read(rfile,&migm2,op_store,0,0,TRUE,fsaname);
    fclose(rfile);
    if (fsa_mimakemult2(&migm2,w[0],w[1],prefix)==-1) return -1;
    mimult_minimize(&migm2);
    sprintf(outf,"%s.mim%s",cosgpname,s);
    wfile = fopen(outf,"w");
    fsa_print(wfile,&migm2,fsaname);
    fclose(wfile);
    fsa_clear(&migm2);
  }
  else { /* general case - we have to split w up */
    if (l%2 == 0) {
      tmalloc(wl,gen,l/2 + 1); tmalloc(wr,gen,l/2 + 1);
      for (i=0;i<l/2;i++) wl[i]=w[i];
      wl[l/2]='\0';
      genstrcpy(wr,w+l/2);
      suffl = file_suffix(wl); suffr = file_suffix(wr);
    }
    else  {
      tmalloc(wl,gen,l/2 + 2); tmalloc(wr,gen,l/2 + 1);
      for (i=0;i<=l/2;i++) wl[i]=w[i];
      wl[l/2 + 1]='\0';
      genstrcpy(wr,w+l/2+1);
      suffl = file_suffix(wl); suffr = file_suffix(wr);
    }
/* See whether we have either of them already */
    gotl = gotr = FALSE;
    if (keepfiles) {
      for (i=1;i<=numstoredmult;i++) {
        if (strcmp(suffl,storedmult[i])==0)
          gotl = TRUE;
        if (strcmp(suffr,storedmult[i])==0)
          gotr = TRUE;
      }
    }

    if (keepfiles && l%2==1 && (!gotl || !gotr)) {
/* In this case, there are two possible ways to split w up -
 * we see if the other way has more multipliers already stored.
 */
      tmalloc(wlt,gen,l/2 + 1); tmalloc(wrt,gen,l/2 + 2);
      for (i=0;i<l/2;i++) wlt[i]=w[i];
      wlt[l/2]='\0';
      genstrcpy(wrt,w+l/2);
      sufflt = file_suffix(wlt); suffrt = file_suffix(wrt);
      gotlt = gotrt = FALSE;
      for (i=1;i<=numstoredmult;i++) {
        if (strcmp(sufflt,storedmult[i])==0)
          gotlt = TRUE;
        if (strcmp(suffrt,storedmult[i])==0)
          gotrt = TRUE;
      }
      if ((gotlt && gotrt) || ((gotlt || gotrt) && !gotl && !gotr)) {
        tfree(wl); tfree(wr); tfree(suffl); tfree(suffr);
        wl=wlt; wr=wrt; suffl=sufflt; suffr=suffrt; gotl=gotlt; gotr=gotrt;
      }
      else {
        tfree(wlt); tfree(wrt); tfree(sufflt); tfree(suffrt);
      }
    }
    if (!gotl) {
      if (long_word_multiplier(wl,suffl)==-1) return -1;
    }
    if (!gotr && genstrcmp(wl,wr)!=0) {
      if (long_word_multiplier(wr,suffr)==-1) return -1;
    }
/* Read back in the two multipliers and form their composite */
    sprintf(inf,"%s.mim%s",cosgpname,suffl);
    if ((rfile = fopen(inf,"r")) == 0) {
      fprintf(stderr,"Cannot open file %s.\n",inf);
        exit(1);
    }
    fsa_read(rfile,&mult1,ip_store,dr,0,TRUE,fsaname);
    fclose(rfile);
    sprintf(inf,"%s.mim%s",cosgpname,suffr);
    if ((rfile = fopen(inf,"r")) == 0) {
      fprintf(stderr,"Cannot open file %s.\n",inf);
        exit(1);
    }
    fsa_read(rfile,&mult2,ip_store,dr,0,TRUE,fsaname);
    fclose(rfile);

    compmult =
        fsa_micomposite(&mult1,&mult2,op_store,TRUE,tablefilename,readback);
    fsa_clear(&mult1); fsa_clear(&mult2);
    if (readback) /* always true */
      mimult_minimize(compmult);
/*
    else
      fsa_ip_minimize(compmult);
*/
    sprintf(outf,"%s.mim%s",cosgpname,s);
    wfile = fopen(outf,"w");
    fsa_print(wfile,compmult,fsaname);
    fclose(wfile);
    fsa_clear(compmult);
    tfree(compmult);

    if (keepfiles) {
      if (gotl) tfree(suffl)
      else storedmult[++numstoredmult] = suffl;
      if (gotr) tfree(suffr)
      else storedmult[++numstoredmult] = suffr;
    }
    else {
      sprintf(inf,"%s.mim%s",cosgpname,suffl); unlink(inf);
      sprintf(inf,"%s.mim%s",cosgpname,suffr); unlink(inf);
      tfree(suffl); tfree(suffr);
    }
    tfree(wl); tfree(wr);
  }

  return;
}

void
badusage_gpsubpres()
{
   fprintf(stderr,
"Usage: gpsubpres [-ip d/s[dr]] [-op d/s] [-silent] [-v] [-l] [-f]\n");
 fprintf(stderr,"\t\t  groupname [subname].\n");
	exit(1);
}
