//---------------------------------------------------
//Pletter and pword definitions:

// word structs using a linked list

typedef struct pletter
{ struct pletter *next;
  struct pletter *prev;
  int l;}
*Pletter;

typedef struct
{ Pletter first, last; // first and last letters
  int l;  // length of the word
}
word;

// a word_link is a pointer to the following structure
typedef struct word_link_struct
{ word w;
  struct word_link_struct *next;
}  
*word_link;

typedef struct
{ word w;            // Stores the word
  Pletter lexi;      // Pointer for the lexitest
  int count[3];      // signed sum of occurances of each letter
  int mod2;          //
  int lexi_count;
  matrix m; 
  phull h;
}
pword;

typedef struct
{ 
  //pword w[MAX_DEPTH]; This array has been replaced by a pointer
  pword *w;
  int MAX_DEPTH; // stores the length of w

  int l; // stores the number of elements actually stored in w
}
pword_list;

// -----------------------------------------------
// word functions:

// initializes a pword
void word_empty(w)
     word *w;
{
  w->first=w->last=NULL;
  w->l=0;
}

// returns true if the word is empty
// returns false if the word is not empty
int word_is_empty(w)
       word *w;
{
  return (w->l==0);
}   

void word_addLetter(w,i)
     word *w;
     int i;
{
  if (w->last!=NULL){   // theres is at least one letter
    w->last->next=(Pletter) malloc (sizeof(struct pletter));
    //word_alloc++;
    w->last->next->l=i;
    w->last->next->next=NULL;
    w->last->next->prev=w->last;
    w->last=w->last->next;
  } else { // the first letter
    w->last=(Pletter) malloc (sizeof(struct pletter));
    //word_alloc++;
    w->last->l=i;
    w->first=w->last;
    w->last->next=w->last->prev=NULL;
  }
  w->l++;
}

//this copys a pword
void word_copy(w,new)
     word *w, *new;
{
  Pletter lw;
  
  word_empty(new);

  lw=w->first;
  while (lw!=NULL){
    word_addLetter(new,lw->l);
    lw=lw->next;
  }
  new->l=w->l;
}

void word_destroy(p)
     word *p;
{
  Pletter l,m;

  if (p->first==NULL) return;
  l=p->first;
  while (l!=NULL){
    m=(l->next);
    free(l);
    //word_free++;
    l=m;
  }
}

// returns 1 if w1 "comes before" w2
// returns -1 if w2 "comes before" w1
// returns 0 if w1 equals w2
// By w1 "comes before" w2 I mean either
// 1) w1 is shorter than w2 OR
// 2) If they have equal length w1 comes before w2 lexigraphically 
int word_compare(w1,w2)
     word *w1, *w2;
{
  Pletter l1,l2;
  if (w1->l < w2->l)
    return 1;
  if (w1->l > w2->l)
    return -1;
  
  // Now we know the length of w1 equals the length of w2
  l1=w1->first;
  l2=w2->first;
  while (l1!=NULL){
    if (l1->l < l2->l)
      return 1;
    if (l1->l > l2->l)
      return -1;
    l1=l1->next;
    l2=l2->next;
  }
  return 0;
}

// return the distance from being balanced
int word_balance(w)
     word *w;
{
  Pletter l;
  int b[3], mod2, i;

  b[0]=b[1]=b[2]=0;
  mod2=1;
  l=w->first;
  while (l!=NULL){
    b[l->l]+=mod2;
    mod2=-mod2;
    l=l->next;
  }
  mod2=0;
  for (i=0; i<3; i++) {
    if (b[i]<0)
      mod2-=b[i];
    else 
      mod2+=b[i];
  }
  //fprintf(stderr,"word is ");
  //word_print_file(stderr,w);
  //fprintf(stderr,"word_balance computes balance at %d\n",mod2);  
  return mod2;
}


// -----------------------------------------------
// word_link functions:

/*
void word_link_create(wl) 
     word_link wl;
{
  wl=(word_link) malloc (sizeof(struct word_link_struct));
  wl->next=NULL;
  word_empty(&(wl->w));
}
*/

//Destroys the word link and all next word_links as well
void word_link_destroy(wl)
      word_link wl;
{
  word_link i,j;
  i=wl;
  while (i!=NULL){
    j=i->next;
    word_destroy(&(i->w));
    free(i);
    i=j;
  }
}    


// inserts a word into the word_link
// word is inserted in word length order
// then by lexigraphical order
// The original word will be destroyed
// No word will be inserted if there is a duplicate already in the list
word_link word_insert(wl,w)
     word_link wl;
     word *w;
{
  word_link i,j;
  int temp;

  if (wl==NULL){
    // This is the first word

    // create a word_link
    wl=(word_link) malloc (sizeof(struct word_link_struct));
    wl->next=NULL;
    word_empty(&(wl->w));

    //word_link_create(wl);
    wl->w.first=w->first;
    wl->w.last=w->last;
    wl->w.l=w->l;

    w->first=w->last=NULL;
    w->l=0;
    return wl;
  }
  //if (word_is_empty(wl->w)){
  //  wl->w.first=w->first;
  //  wl->w.last=w->last;
  //  wl->w.l=w->l;
  //  return wl;
  //}
  if ((temp=word_compare(w,&(wl->w)))==0){
    // w equals the first word
    // destroy w and return
    word_destroy(w);
    return wl;
  }
  if (temp==1){
    // w should be the first word
    i=wl;
    
    // create a word_link   
    wl=(word_link) malloc (sizeof(struct word_link_struct));
    //wl->next=NULL;
    word_empty(&(wl->w));
    
    //wl=word_link_create();
    wl->w.first=w->first;
    wl->w.last=w->last;
    wl->w.l=w->l;
    wl->next=i;
    
    w->first=w->last=NULL;
    w->l=0;
    return wl;
  }
  i=wl;
  j=i->next;
  while ((j!=NULL)&&((temp=word_compare(w,&(j->w)))==-1)){
    i=j;
    j=i->next;
  }
  if (temp==0) {
    // words w and j->w are equal
    word_destroy(w);
    return wl;
  }

  // create a word_link
  i->next=(word_link) malloc (sizeof(struct word_link_struct));
  //i->next->next=NULL;
  word_empty(&(i->next->w));
  
  //i->next=word_link_create();

  i->next->w.first=w->first;
  i->next->w.last=w->last;
  i->next->w.l=w->l;
  i->next->next=j;

  w->first=w->last=NULL;
  w->l=0;
  return wl;
}




// -----------------------------------------------
// SOME USEFUL FUNCTIONS: PWORD

//int pword_free=0, pword_alloc=0;
// this initializes a pword
// the phull must be initialized seperately
void pword_empty(w)
     pword *w;
{
  w->count[0]=w->count[1]=w->count[2]=0;
  w->w.first=w->w.last=w->lexi=NULL;
  w->lexi_count=0;
  w->w.l=0;
  w->mod2=1;
  w->m.m[0][0]=1; w->m.m[0][1]=0; w->m.m[0][2]=0;
  w->m.m[1][0]=0; w->m.m[1][1]=1; w->m.m[1][2]=0;
}

void addLetter(w,i)
     pword *w;
     int i;
{
  if (w->w.last!=NULL){   // theres is at least one letter
    w->w.last->next=(Pletter) malloc (sizeof(struct pletter));
    //pword_alloc++;
    w->w.last->next->l=i;
    w->w.last->next->next=NULL;
    w->w.last->next->prev=w->w.last;
    w->w.last=w->w.last->next;
  } else { // the first letter
    w->w.last=(Pletter) malloc (sizeof(struct pletter));
    //pword_alloc++;
    w->w.last->l=i;
    w->w.first=w->w.last;
    w->w.last->next=NULL;
    w->lexi=NULL;
    w->w.last->prev=NULL;
  }
  w->count[i]+=w->mod2;
  w->mod2*=-1;
  w->w.l++;
}

//add letter and record the reflections effect on on m, our euclidean transform
// at least two letters should already be present.
// i is the current side being reflected in
void addLetter_r(w,i,r,T)
     pword *w; 
     int i;
     reflection *r;
     ptriangle *T;
{
  if (w->mod2==1) // even number of letters- the usual orientation
    if (w->w.last->l==0) // last reflected was the first side
      if (i==2) // add the point to the right side;
	phull_insert(&(w->h), eucTimes(&(w->m),T->z1), 1);
      else // (i==1); -- left side
	phull_insert(&(w->h), eucTimes(&(w->m),T->z1), -1);
    else if (w->w.last->l==1) // last reflected was the second side
      if (i==0) // add the point to the right side;
	phull_insert(&(w->h), eucTimes(&(w->m),T->z2), 1);
      else // (i==2); -- left side
	phull_insert(&(w->h), eucTimes(&(w->m),T->z2), -1);
    else // w->w.last->l==2 last reflected third side
        if (i==1) // add the point to the right side;
	phull_insert(&(w->h), eucTimes(&(w->m),T->z3), 1);
      else // (i==0); -- left side
	phull_insert(&(w->h), eucTimes(&(w->m),T->z3), -1);
  else // (w->mod2==-1) // odd number of letters- the opposite orientation
    if (w->w.last->l==0) // last reflected was the first side
      if (i==2) // add the point to the left side;
	phull_insert(&(w->h), eucTimes(&(w->m),T->z1), -1);
      else // (i==1); -- right side
	phull_insert(&(w->h), eucTimes(&(w->m),T->z1), 1);
    else if (w->w.last->l==1) // last reflected was the second side
      if (i==0) // add the point to the left side;
	phull_insert(&(w->h), eucTimes(&(w->m),T->z2), -1);
      else // (i==2); -- right side
	phull_insert(&(w->h), eucTimes(&(w->m),T->z2), 1);
    else // w->w.last->l==2 last reflected third side
        if (i==1) // add the point to the left side;
	phull_insert(&(w->h), eucTimes(&(w->m),T->z3), -1);
      else // (i==0); -- right side
	phull_insert(&(w->h), eucTimes(&(w->m),T->z3), 1);
  timesEquals(&(w->m), &(r->m[i])); 
  addLetter(w,i);
}

// this adds the letter and performs the requested change 
// after a future_plexi_test
void addLetter_lexi(w,i,lex)
  pword *w; 
  int i; 
  int lex;
{
  addLetter(w,i);
  if (lex==1){
    w->lexi=w->lexi->next;
    w->lexi_count++;
  } else {  //otherwise assume lex=0;
    w->lexi_count=0;
    w->lexi=w->w.first; 
  }
}

//this copys a pword
void pword_copy(w,new)
     pword *w, *new;
{
  int i;
  Pletter lw;
  
  pword_empty(new);
  new->lexi_count=w->lexi_count;
  new->m.m[0][0]=w->m.m[0][0];
  new->m.m[0][1]=w->m.m[0][1];
  new->m.m[0][2]=w->m.m[0][2];
  new->m.m[1][0]=w->m.m[1][0];
  new->m.m[1][1]=w->m.m[1][1];
  new->m.m[1][2]=w->m.m[1][2];

  new->lexi=NULL;

  i=0;
  lw=w->w.first;
  while (lw!=NULL){
    addLetter(new,lw->l);
    if (lw==w->lexi)
      new->lexi=new->w.last;
    lw=lw->next;
  }
  if (lw==w->lexi)
    new->lexi=new->w.last;
  //if (new->lexi==NULL){
  //  pword_print_file(stdout,w);
  //  fprintf(stdout,"we have an error");
  //  fflush(stdout);
  //}

  phull_copy(&(w->h),&(new->h));  
}

// this frees the memory used by a pword
void pword_destroy(p)
     pword *p;
{
  phull_destroy(&(p->h));
  word_destroy(&(p->w));
}

// -----------------------------------------------
// SOME USEFUL FUNCTIONS: PWORD_LIST

void pword_list_initialize(wl, MAX_DEPTH)
     pword_list *wl;
     int MAX_DEPTH;
{
  wl->w=(pword *)malloc(MAX_DEPTH * sizeof(pword));
  wl->MAX_DEPTH=MAX_DEPTH;
  wl->l=0;
}


void pwordlist_destroy(wl)
     pword_list *wl;
{
  int i;
  for (i=0; i< wl->l; i++)
    pword_destroy(&(wl->w[i]));
  free(wl->w);
}

//--------------------------------------------
// INPUT AND OUTPUT MEATHODS

// print out the pword
void word_print_file(file,w)
     FILE *file;
     word *w;
{

  Pletter l=w->first;
  while (l!=NULL){
    fprintf(file,"%d",l->l+1);
    l=l->next;
  }
  fprintf(file,"\n");
}

// print out the pword and some data
void pword_print_file2(file,w)
     FILE *file;
     pword *w;
{
  Pletter l=w->w.first;
  while (l!=NULL){
    fprintf(file,"%d",l->l+1);
    l=l->next;
  }
  fprintf(file,"\n");
  fprintf(file,"a=%d, b=%d, c=%d\n",w->count[0],w->count[1],w->count[2]);
  fprintf(file,"length=%d\n",w->w.l);
}

void pword_list_print_file(file, pwl)
     FILE *file; 
     pword_list *pwl;
{
  int i;
  for (i=0; i<pwl->l; i++){
    word_print_file(file,&(pwl->w[i].w));    
  }
}

void word_link_print_file(file, wl)
    FILE *file; 
    word_link wl;
{
  word_link i;
  i=wl;
  while (i!=NULL){
    word_print_file(file,&(i->w));
    i=i->next;
  }
}

pword pword_read_file(file)
     FILE *file;
{
  char c;
  pword w;
  pword_empty(&w);
  c = fgetc(file);
  while ((!feof(file))&&((c<'1')||(c>'3'))) //read whitespace
    c = fgetc(file);
  while ((!feof(file))&&(c>='1')&&(c<='3')){
    addLetter(&w,c-'1');
    c = fgetc(file);
  }
  return w;
}