// psearch with relation given by 3 integers.
// rel=(a, b, -a-b) would mean that the 
// word (13)^a(23)^b is a translation 
word_link psearchwRel(T,DEPTH, rel)
     ptriangle T;
     int DEPTH;
     int rel[3];
{
  word_link SUCCEED;
  pword_list TRY;
  pword *w;
  int last;
  int pl1,pl2; // for future lexi test
  int bal; // for balance test
  reflection r;
  word new;
  triangle T2;

  T2=triangle_from_ptriangle(T);
  SUCCEED=NULL;
  pword_list_initialize(&TRY,DEPTH);

  reflect_from_ptriangle(T,&r); // stores the matrices of reflections


  TRY.l=1;

  // this initializes our pword and phull.
  pword_empty(&(TRY.w[0]));
  phull_setup(&(TRY.w[0].h));
  addLetter(&(TRY.w[0]), 0);
  addLetter(&(TRY.w[0]), 1);
  TRY.w[0].h.last_left->z=T.z3;
  TRY.w[0].h.last_right->z=T.z2;
  //phull_insert(&(TRY.w[0].h), T.z3, -1);
  timesEquals(&(TRY.w[0].m), &(r.m[0]));
  phull_insert(&(TRY.w[0].h), eucTimes(&(TRY.w[0].m),T.z1), 1);
  timesEquals(&(TRY.w[0].m), &(r.m[1]));
  // This certainly passes the balance and lexi test
  TRY.w[0].lexi=TRY.w[0].w.first;
  TRY.w[0].lexi_count=0;
  TRY.w[0].h.current=NULL;

  setArea(&(TRY.w[0].h));



  while (TRY.l>0){
    w=&(TRY.w[TRY.l-1]);
    if ((bal=pbalance_wRel(w,rel))+w->w.l>DEPTH){
      pword_destroy(w);
      TRY.l--;
    } else {
      if (pweak_test(w)==1){ // if fails weak test 
	pword_destroy(w);
	TRY.l--;
      } else { // passes weak test
	if (bal==0) // balanced word
	  if (pstrong_test(w)==0){ //if passes strong test
	    if (power_test(&(w->w))){ // if not a power of an even word
	      if (general_strong_test_tol(w->w,T2,.000000001)){
		word_copy(&(w->w),&new);
		word_simplify(&new);
		SUCCEED=word_insert(SUCCEED,&new);
	      }
	    }
	  }
	// now we consider adding letters to our word
	last=w->w.last->l;
	
	if ((pl1=future_plexi_test(w, (last+1)%3))!=-1){ //if first one passes
	  if ((pl2=future_plexi_test(w, (last+2)%3))!=-1){ //and second one passes
	    if (TRY.l<TRY.MAX_DEPTH){ // This should always be true
	      pword_copy(w,&(TRY.w[TRY.l]));
	      addLetter_r(&(TRY.w[TRY.l]),(last+2)%3,&r,&T);
	      if (pl2==0){
		TRY.w[TRY.l].lexi=TRY.w[TRY.l].w.first;
		TRY.w[TRY.l].lexi_count=0;
	      } else {
		TRY.w[TRY.l].lexi=TRY.w[TRY.l].lexi->next;
		TRY.w[TRY.l].lexi_count++;
	      }
	      TRY.l++;	  
	    }
	    
	    addLetter_r(w,(last+1)%3,&r,&T);
	    
	    //lexi test upkeep
	    if (pl1==0){
	      w->lexi=w->w.first;
	      w->lexi_count=0;
	    } else {
	      w->lexi=w->lexi->next;
	      w->lexi_count++;
	    }	 
	  } else { // only first passes;
	    addLetter_r(w,(last+1)%3,&r,&T);
	    // some lexi upkeep
	    if (pl1==0){
	      w->lexi=w->w.first;
	      w->lexi_count=0;
	    } else {
	      w->lexi=w->lexi->next;
	      w->lexi_count++;
	    }
	  }
	} else if ((pl2=future_plexi_test(w, (last+2)%3))!=-1){ //first failed, if second one passes
	  addLetter_r(w,(last+2)%3,&r,&T);
	  // lexi upkeep
	  if (pl2==0){
	    w->lexi=w->w.first;
	    w->lexi_count=0;
	  } else {
	    w->lexi=w->lexi->next;
	    w->lexi_count++;
	  }
	} else { // we are at a dead end.
	  pword_destroy(w);
	  TRY.l--;
	}
      }
    }
  }

  pwordlist_destroy(&TRY);

  // We also need to search for words of the form 1313...232323...
  pword_list_initialize(&TRY,DEPTH);
  TRY.l=1;

  // this initializes our pword and phull.
  pword_empty(&(TRY.w[0]));
  phull_setup(&(TRY.w[0].h));
  addLetter(&(TRY.w[0]), 0);
  addLetter(&(TRY.w[0]), 2);
  TRY.w[0].h.last_left->z=T.z3;
  TRY.w[0].h.last_right->z=T.z2;
  //phull_insert(&(TRY.w[0].h), T.z3, -1);
  timesEquals(&(TRY.w[0].m), &(r.m[0]));
  phull_insert(&(TRY.w[0].h), eucTimes(&(TRY.w[0].m),T.z1), -1);
  timesEquals(&(TRY.w[0].m), &(r.m[2]));
  // This certainly passes the balance and lexi test
  TRY.w[0].lexi=TRY.w[0].w.first;
  TRY.w[0].lexi_count=0;
  TRY.w[0].h.current=NULL;

  setArea(&(TRY.w[0].h));

  while (TRY.l>0){
    w=&(TRY.w[TRY.l-1]);
    if ((bal=pbalance_wRel(w,rel))+w->w.l>DEPTH){
      pword_destroy(w);
      TRY.l--;
    } else {
      if (pweak_test(w)==1){ // if fails weak test 
	pword_destroy(w);
	TRY.l--;
      } else { // passes weak test
	if (bal==0) // balanced word
	  if (pstrong_test(w)==0){ //if passes strong test
	    if (power_test(&(w->w))){ // if not a power of an even word
	      if (general_strong_test_tol(w->w,T2,.000000001)){
		word_copy(&(w->w),&new);
		word_simplify(&new);
		SUCCEED=word_insert(SUCCEED,&new);
	      }
	    }
	  }
	// now we consider adding letters to our word
	last=w->w.last->l;
	
	if ((pl1=future_plexi_test(w, (last+1)%3))!=-1){ //if first one passes
	  if ((pl2=future_plexi_test(w, (last+2)%3))!=-1){ //and second one passes
	    if (TRY.l<TRY.MAX_DEPTH){ // This should always be true
	      pword_copy(w,&(TRY.w[TRY.l]));
	      addLetter_r(&(TRY.w[TRY.l]),(last+2)%3,&r,&T);
	      if (pl2==0){
		TRY.w[TRY.l].lexi=TRY.w[TRY.l].w.first;
		TRY.w[TRY.l].lexi_count=0;
	      } else {
		TRY.w[TRY.l].lexi=TRY.w[TRY.l].lexi->next;
		TRY.w[TRY.l].lexi_count++;
	      }
	      TRY.l++;	  
	    }
	    
	    addLetter_r(w,(last+1)%3,&r,&T);
	    
	    //lexi test upkeep
	    if (pl1==0){
	      w->lexi=w->w.first;
	      w->lexi_count=0;
	    } else {
	      w->lexi=w->lexi->next;
	      w->lexi_count++;
	    }	 
	  } else { // only first passes;
	    addLetter_r(w,(last+1)%3,&r,&T);
	    // some lexi upkeep
	    if (pl1==0){
	      w->lexi=w->w.first;
	      w->lexi_count=0;
	    } else {
	      w->lexi=w->lexi->next;
	      w->lexi_count++;
	    }
	  }
	} else if ((pl2=future_plexi_test(w, (last+2)%3))!=-1){ //first failed, if second one passes
	  addLetter_r(w,(last+2)%3,&r,&T);
	  // lexi upkeep
	  if (pl2==0){
	    w->lexi=w->w.first;
	    w->lexi_count=0;
	  } else {
	    w->lexi=w->lexi->next;
	    w->lexi_count++;
	  }
	} else { // we are at a dead end.
	  pword_destroy(w);
	  TRY.l--;
	}
      }
    }
  }

  pwordlist_destroy(&TRY);

  return SUCCEED;  

}


// psearch with relation given by 3 integers.
// rel=(a, b, -a-b) would mean that the 
// word (13)^a(23)^b is a translation 
// this version returns the word of shortest length
word rat_fill_psearchwRel(T,DEPTH, rel)
     ptriangle T;
     int DEPTH;
     int rel[3];
{
  word SUCCEED;
  pword_list TRY;
  pword *w;
  int last;
  int pl1,pl2; // for future lexi test
  int bal; // for balance test
  reflection r;
  triangle T2;

  T2=triangle_from_ptriangle(T);
  
  word_empty(&SUCCEED);
  pword_list_initialize(&TRY,DEPTH);


  reflect_from_ptriangle(T,&r); // stores the matrices of reflections

  TRY.l=1;

  // this initializes our pword and phull.
  pword_empty(&(TRY.w[0]));
  phull_setup(&(TRY.w[0].h));
  addLetter(&(TRY.w[0]), 0);
  addLetter(&(TRY.w[0]), 1);
  TRY.w[0].h.last_left->z=T.z3;
  TRY.w[0].h.last_right->z=T.z2;
  //phull_insert(&(TRY.w[0].h), T.z3, -1);
  timesEquals(&(TRY.w[0].m), &(r.m[0]));
  phull_insert(&(TRY.w[0].h), eucTimes(&(TRY.w[0].m),T.z1), 1);
  timesEquals(&(TRY.w[0].m), &(r.m[1]));
  // This certainly passes the balance and lexi test
  TRY.w[0].lexi=TRY.w[0].w.first;
  TRY.w[0].lexi_count=0;
  TRY.w[0].h.current=NULL;

  setArea(&(TRY.w[0].h));



  while (TRY.l>0){
    w=&(TRY.w[TRY.l-1]);
    if ((bal=pbalance_wRel(w,rel))+w->w.l>DEPTH){
      pword_destroy(w);
      TRY.l--;
    } else {
      if (pweak_test(w)==1){ // if fails weak test 
	pword_destroy(w);
	TRY.l--;
      } else { // passes weak test
	if (bal==0) // balanced word
	  if (pstrong_test(w)==0){ //if passes strong test
	    if (power_test(&(w->w))){ // if not a power of an even word
	      if (general_strong_test_tol(w->w,T2,.000000001)){

		if ((SUCCEED.l==0)||(SUCCEED.l>w->w.l)){
		  if (SUCCEED.l!=0)
		    word_destroy(&SUCCEED);
		  word_copy(&(w->w),&SUCCEED);
		  word_simplify(&SUCCEED);
		  DEPTH=w->w.l-2;
		}

	      }
	    }
	  }
	// now we consider adding letters to our word
	last=w->w.last->l;
	
	if ((pl1=future_plexi_test(w, (last+1)%3))!=-1){ //if first one passes
	  if ((pl2=future_plexi_test(w, (last+2)%3))!=-1){ //and second one passes
	    if (TRY.l<TRY.MAX_DEPTH){ // This should always be true
	      pword_copy(w,&(TRY.w[TRY.l]));
	      addLetter_r(&(TRY.w[TRY.l]),(last+2)%3,&r,&T);
	      if (pl2==0){
		TRY.w[TRY.l].lexi=TRY.w[TRY.l].w.first;
		TRY.w[TRY.l].lexi_count=0;
	      } else {
		TRY.w[TRY.l].lexi=TRY.w[TRY.l].lexi->next;
		TRY.w[TRY.l].lexi_count++;
	      }
	      TRY.l++;	  
	    }
	    
	    addLetter_r(w,(last+1)%3,&r,&T);
	    
	    //lexi test upkeep
	    if (pl1==0){
	      w->lexi=w->w.first;
	      w->lexi_count=0;
	    } else {
	      w->lexi=w->lexi->next;
	      w->lexi_count++;
	    }	 
	  } else { // only first passes;
	    addLetter_r(w,(last+1)%3,&r,&T);
	    // some lexi upkeep
	    if (pl1==0){
	      w->lexi=w->w.first;
	      w->lexi_count=0;
	    } else {
	      w->lexi=w->lexi->next;
	      w->lexi_count++;
	    }
	  }
	} else if ((pl2=future_plexi_test(w, (last+2)%3))!=-1){ //first failed, if second one passes
	  addLetter_r(w,(last+2)%3,&r,&T);
	  // lexi upkeep
	  if (pl2==0){
	    w->lexi=w->w.first;
	    w->lexi_count=0;
	  } else {
	    w->lexi=w->lexi->next;
	    w->lexi_count++;
	  }
	} else { // we are at a dead end.
	  pword_destroy(w);
	  TRY.l--;
	}
      }
    }
  }

  pwordlist_destroy(&TRY);
  return SUCCEED;  

}

void rat_line_get_endpoints(line, end)
     int line[3];
     pcomplex *end;
{
  int i;
  double d;
  // Determine the end points of the line
  if (line[0]==0){
    end[0].x=0;
    end[0].y=((double)line[2])/line[1];
    end[0].x=.5;
    end[0].y=((double)line[2])/line[1];
  } else if (line[0]==0){
    end[0].y=0;
    end[0].x=((double)line[2])/line[0];
    end[0].y=.5;
    end[0].x=((double)line[2])/line[0];
  } else {
    i=0;
    // alpha=0 beta=
    d=((double)line[2])/line[1];
    if ((d>=0)&&(d<.5)){
      end[i].x=0;
      end[i].y=d;
      i++;
    }    
    // beta=0 alpha=
    d=((double)line[2])/line[0];
    if ((d>=0)&&(d<.5)){
      end[i].x=d;
      end[i].y=0;
      i++;
    }    
    // alpha=.5 beta=
    d=(((double)line[2])-((double)line[0])/2)/line[1];
    if ((d>=0)&&(d<.5)){
      end[i].x=.5;
      end[i].y=d;
      i++;
    }
    // beta=.5 alpha=
    d=(((double)line[2])-((double)line[1])/2)/line[0];
    if ((d>=0)&&(d<.5)){
      end[i].x=d;
      end[i].y=.5;
      i++;
    }
    if (i!=2){
      printf("Error rat_line_get_endpoints: unable to determine endpoints of line");
      exit(0);
    }
  }
  // End determining end points
}

//returns complex numbers for the end points of the tile
void rat_plot(z,line,w, mesh, ret)
     pcomplex z; 
     int line[3];
     word w;
     int mesh;
     pcomplex *ret;
{
  triangle T;
  pcomplex end[2], temp;
  int i,j;

  T=triangle_make2(z);
  if (!general_strong_test(w,T)){
    printf("rat_plot: Bad call... the point does not lie within the tile.\n");
    exit(0);
  }

  rat_line_get_endpoints(line,&end);

  ret[0]=ret[1]=z;
  for (i=0; i<2; i++)
    for (j=1; j<mesh; j++){
      temp.x=(ret[i].x+end[i].x)/2;
      temp.y=(ret[i].y+end[i].y)/2;
      T=triangle_make2(temp);
      if (general_strong_test(w,T)) // if passes strong test
	ret[i]=temp;
      else
	end[i]=temp;
    }
}