import java.awt.event.*;
import java.awt.*;

/**This class transfers the coloring solution to the planar
   picture of the enhanced polygon*/

public class TriangleFiller {
    Complex[][] TRI=new Complex[1000][6];
    int[] TAG=new int[1000]; //index of triangle in the enhanced polygon listing
    int[] SOL=new int[1000]; //the solution
    int count;
    

    public TriangleFiller() {
	count=0;
    }


    /**This is the main routine.  It takes a solution and imparts it to
       the polygon which describes the triangulation.  The basic idea is to
       get the core of the solution, consisting of triangles in the interior
       of the polygon, and then to augment it by building around it.*/
    
    public static TriangleFiller getFiller(EnhancedPolygon E) {
	TriangleFiller X=TriangleFiller.coreSolution(E);
	boolean test=true;
	while(test==true) {
	    int before=X.count;
	    try{
	      TriangleFiller.augment(X,E);
	      TriangleFiller.augmentPairing(X,E);
	    }
	    catch(Exception e) {
	    }
	    int after=X.count;
	    if(before==after) test=false;
	}
	return X;
    }



    /**This is the core solution, consisting of triangles with all
       three vertices in the polygon*/

    public static TriangleFiller coreSolution(EnhancedPolygon E) {
	TriangleFiller X=new TriangleFiller();
        int count=0;
	for(int i=0;i<E.solution.length;++i) {
	    int t=E.solution[i];
	    int[] T=E.triangles[i];//the ith triangle
	    int[] T0=E.equiv[T[0]];
	    int[] T1=E.equiv[T[1]];
	    int[] T2=E.equiv[T[2]];
	    for(int i0=0;i0<T0.length;++i0) {
	    for(int i1=0;i1<T1.length;++i1) {
	    for(int i2=0;i2<T2.length;++i2) {
		Complex z0=E.V[T0[i0]];
		Complex z1=E.V[T1[i1]];
		Complex z2=E.V[T2[i2]];
		Complex[] Z={z0,z1,z2};
		boolean test=isUnitTriangle(Z);
		if((t!=-1)&&(test==true)) {
		    X.TAG[count]=i;
		    X.SOL[count]=t;
		    X.TRI[count]=Z;
		    ++count;
		}
	    }}}
	}
	X.count=count;
	return X;
    }


    /**This routine augments the filler by using the edge pairing maps
       to transport triangles around.*/

    public static void augmentPairing(TriangleFiller X,EnhancedPolygon E) {
	int c=X.count;
	for(int i=0;i<c;++i) {
	    int k=X.crossingIndex(E,i);
	    if(k!=-1) {
                Complex[] W=new Complex[3];
		for(int j=0;j<3;++j) {
		    W[j]=PolygonToGraph.doPair(E,k,X.TRI[i][j]);
		}
		if(X.newTriangle(W)==true) {
		  X.TRI[X.count]=W;
		  X.TAG[X.count]=X.TAG[i];
	   	  X.SOL[X.count]=X.SOL[i];
	          ++X.count;
		}
	    }
	}
    }

    public int crossingIndex(EnhancedPolygon E,int k) {
	for(int i=0;i<E.count;++i) {
	    if(crosses(E,k,i)==true) return i;
 	}
	return -1;
    }

    public boolean crosses(EnhancedPolygon E,int k,int e) {
	Complex[] Z=this.TRI[k];
	int f=(e+1)%E.count;
	for(int i=0;i<3;++i) {
	    int j=(i+1)%3;
	    boolean test=Complex.doTheyCrossStrict(Z[i],Z[j],E.z[e],E.z[f]);
	
	    if(test==true) return true;
	}
	return false;
    }


    public boolean newTriangle(Complex[] Z) {
	for(int i=0;i<count;++i) {
	    boolean test=match(Z,TRI[i]);
	    if(test==true) return false;
	}
	return true;
    }


    /**checks if 2 eisenstein triangles match*/
    
    public static boolean match(Complex[] Z,Complex[] W) {
	Complex z=center(Z);
	Complex w=center(W);
	double d=Complex.dist(z,w);
	if(d<.1) return true;
	return false;
    }
    

    
    public static Complex center(Complex[] Z) {
	Complex w=new Complex(0,0);
	for(int i=0;i<Z.length;++i) w=Complex.plus(w,Z[i]);
	w=w.scale(1.0/Z.length);
	return w;
    }

    /**end pairing routines*/


    /**This is the augmenting routine that extends flower-by-flower.*/

    
    public static void augment(TriangleFiller X,EnhancedPolygon E) {
	int[] k=X.firstExtendingIndex(E);//kth flower. also kth vertex
   	if(k==null) return;
	
	int[] M=X.getNeighbors(E,k[0],k[1]);
	int k1=X.orientation(E,k,M);
	int k2=X.startingPosition(E,M);
   	Complex[] Z0=X.TRI[M[k2]]; //gets the triangle

	int vtx=E.equiv[k[0]][k[1]];
	Complex cen=E.V[vtx];
	int[] s=TreeSearch.solution(E.local[k[0]]);//local solution - parallels the flowers
	
	for(int i=0;i<6;++i) {
	    if(M[i]==-1) {
		int u=i-k2;
		if(k1==1) u=-u;
	        X.TRI[X.count]=rotateTriangle(Z0,cen,u);
		X.TAG[X.count]=E.flower[k[0]][i];
  		try{X.SOL[X.count]=s[i];}
		catch(Exception e) {X.SOL[X.count]=-1;}
		++X.count;
	    }
	}
    }
    
      public static Complex[] rotateTriangle(Complex[] Z0,Complex cen,int u) {
	Complex[] Z1=new Complex[3];
	Complex a=Complex.alpha(u);
	for(int j=0;j<3;++j) {
	      Complex b=Complex.minus(Z0[j],cen);
	      b=Complex.times(a,b);
	      Z1[j]=Complex.plus(b,cen);
	}
	return Z1;
    }

    /**this analyzes the orientation (0 or 1) of a partially overlapping index set*/
    public int orientation(EnhancedPolygon E,int[] q,int[] M) { //qth flower
	if(M==null) return -1;
	for(int j=0;j<6;++j) {
	    int k=(j+1)%6;
	    if((M[j]!=-1)&&(M[k]!=-1)) {
   		int vtx=E.equiv[q[0]][q[1]];
		Complex z0=E.V[vtx];
		Complex z1=triangleCenter(M[j]);
		Complex z2=triangleCenter(M[k]);
		Complex w01=Complex.minus(z0,z1);
		Complex w02=Complex.minus(z0,z2);
		Complex w=Complex.divide(w02,w01);
		if(w.y>0) return 0;
		return 1;
	    }
	}
	return -1;
    }

    
    /**this gets the value of the first nonzero index*/
    public int startingPosition(EnhancedPolygon E,int[] M) {
	if(M==null) return -1;
	for(int j=0;j<6;++j) {
	    if(M[j]!=-1) return j;
	}
	return -1;
    }


    

    /**This examines a flower and computes the overlap with the
       triangle filler.  We want a vertex that has a nontrivial
       but incomplete overlap.  Returns the index of the desired flower*/
    

    public int[] firstExtendingIndex(EnhancedPolygon E) {
	int n=E.flower.length;
	for(int i=0;i<n;++i) {
	    int k=E.equiv[i].length;
	    for(int j=0;j<k;++j) {
		int[] M=getNeighbors(E,i,j);
		if(M!=null) {
		    int[] a={i,j};
		    return a;
		}
	    }
	}
	return null;
    }

    
      public Complex triangleCenter(int j) {
	Complex[] Z=this.TRI[j];
	Complex w=new Complex(0,0);
	for(int i=0;i<3;++i) w=Complex.plus(w,Z[i]);
	w=w.scale(1.0/3);
	return w;
    }



    /**This examines the filler and finds the triangles in the (kth) flower that are incident
       to the vertices. What we want is a vertex with 2 consecutive triangles contained in
       the filler, but not all 6 triangles in the filler*/
    
    public int[] getNeighbors(EnhancedPolygon E,int k,int l) {
  	int vtx=E.equiv[k][l];
	Complex cen=E.V[vtx];
	int[] list={-1,-1,-1,-1,-1,-1};
	int[] T=E.flower[k];
	if(T.length<6) return null;
	
	for(int i0=0;i0<6;++i0) {
	    for(int i1=0;i1<this.count;++i1) {
		if(TAG[i1]==T[i0]) {
  	            boolean test=isIncident(TRI[i1],cen);
		    if(test==true) list[i0]=i1;
		}
	    }
	}
	if(ListHelp.onList(-1,list)==false) return null;
	if(consecutivePositive(list)==true) return list;
	return null;
    }


    /**this version allows for all triangles to be present*/
    
    public int[] getNeighbors2(EnhancedPolygon E,int k,int l) {
  	int vtx=E.equiv[k][l];
	Complex cen=E.V[vtx];
	int[] list={-1,-1,-1,-1,-1,-1};
	int[] T=E.flower[k];
	if(T.length<6) return null;
	
	for(int i0=0;i0<6;++i0) {
	    for(int i1=0;i1<this.count;++i1) {
		if(TAG[i1]==T[i0]) {
  	            boolean test=isIncident(TRI[i1],cen);
		    if(test==true) list[i0]=i1;
		}
	    }
	}
	if(consecutivePositive(list)==true) return list;
	return null;
    }

    public static boolean consecutivePositive(int[] T) {
	for(int i=0;i<6;++i) {
	    int j=(i+1)%6;
	    if((T[i]!=-1)&&(T[j]!=-1)) return true;
	}
	return false;
    }




    
    /**end augment routine*/



    /**triangle routines*/

    /**checks if the vertex cen is a vertex of the triangle*/
    
    public static boolean isIncident(Complex[] Z,Complex cen) {
	for(int i=0;i<3;++i) {
	    if(Complex.dist(Z[i],cen)<.1) return true;
	}
	return false;
    }
    
    /**checks if this is a unit triangle*/
    
    public static boolean isUnitTriangle(Complex[] Z) {
	if(Z==null) return false;
	Complex z0=Z[0];
	Complex z1=Z[1];
	Complex z2=Z[2];
	if(isUnitEdge(z0,z1)==false) return false;
	if(isUnitEdge(z1,z2)==false) return false;
	if(isUnitEdge(z0,z2)==false) return false;
	return true;
    }

    /**Checks if these points make an Eisenstein edge*/
    
    public static boolean isUnitEdge(Complex z0,Complex z1) {
	double d01=Complex.dist(z0,z1);
	if(d01<.9) return false;
	if(d01>1.1) return false;
	return true;
    }	




}


