import java.applet.Applet;
import java.awt.*;
import java.awt.event.*;
import java.applet.*;
import java.awt.geom.*;
import java.math.*;

/**This file contains the routines we use to show that a
   list of polygons partitions a given region.**/


class PolyCover {


    public static void failMessage() {
	throw new ProofException("PolyCover");
    }


    /**Main routine: checks that each vertex in the tiling has 
       the following property: If it lies in the polywedge HOME
       then its link is a circle. 
       This result, combined with the convexity test, shows that
       HOME is covered by the list of tiles.**/

    public static void coverTest(GoldenPolyWedge[] ALL0,int total,GoldenPolyWedge HOME) {
	System.out.print("start cover test --  ");
	GoldenPolyWedge[] ALL=clean(ALL0,HOME);	
        boolean cvx=positiveConvex(ALL,total);
	if(cvx==false) failMessage();
	for(int i=0;i<total;++i) {
	    GoldenPolyWedge P=ALL[i];
	    for(int j=0;j<P.count;++j) {
	       GoldenComplex z=new GoldenComplex(P.z[j%P.count]);
	       boolean test=PolyCover.inside(z,HOME);
	       if(test==true) {
		   GoldenComplex[] L1=PolyCover.neighbors(0,z,ALL,total);
		   GoldenComplex[] L2=PolyCover.neighbors(1,z,ALL,total);
	           boolean test2=PolyCover.matchFold(z,L1,L2);
	           if(test2==false) failMessage();
	       }
	    }
	}
	System.out.println("end");
    }



    /**Convexity test:  Checks that the tiles are
       convex and counterclockwise oriented.*/

    public static boolean positiveConvex(GoldenPolyWedge[] ALL,int total) {
	boolean cvx=true;
	for(int i=0;i<ALL.length;++i) {
	   GoldenPolyWedge P=ALL[i];
	   boolean test=P.isPositivelyConvex();
	   if(test==false) cvx=false;
	}
	return(cvx);
    }

    /**gets all the neighboring vertices. The parity
       should be 0 for the backward vertices and 1 for the forward.*/


    /**Here we know the length of the list.**/
    public static GoldenComplex[] neighbors(int parity,GoldenComplex z,GoldenPolyWedge[] ALL) {
	int total=ALL.length;
	return(neighbors(parity,z,ALL,total));
    }



    /**Here the length is specified explicitly.**/
    public static GoldenComplex[] neighbors(int parity,GoldenComplex z,GoldenPolyWedge[] ALL,int total) {
	GoldenComplex[] LIST0=new GoldenComplex[20];
	int count=0;
	for(int i=0;i<total;++i) {
	    GoldenPolyWedge P=ALL[i];
	    if(inside(z,P)==true) {
		z.print2();
		System.out.println("--");
		P.print1();
                failMessage();
	    }


	    int v=vertexMatch(z,P);
	    int e=edgeMatch(z,P);
	    if(e!=-1) {
		LIST0[count]=new GoldenComplex(P.z[(e+parity)%P.count]);
		++count;
	    }
	    if(v!=-1) {
		int v1=(v+1)%P.count;
		if(parity==0) v1=(P.count+v-1)%P.count;
		LIST0[count]=new GoldenComplex(P.z[v1]);
		++count;
	    }
	}
	GoldenComplex[] LIST=new GoldenComplex[count];
	for(int i=0;i<count;++i) LIST[i]=new GoldenComplex(LIST0[i]);
	return(LIST);
    }


    /**Checks if the given vertex lies on an edge of the polygon.**/


    public static int edgeMatch(GoldenComplex z1,GoldenPolyWedge P) {
       for(int k=0;k<P.count;++k) {
	  int k1=k;
	  int k2=(k+1)%P.count;
	  GoldenComplex z2=new GoldenComplex(P.z[k1]);
	  GoldenComplex z3=new GoldenComplex(P.z[k2]);
	  if(GoldenComplex.isBetween(z1,z2,z3)==true) return(k);
       }
       return(-1);
    }


    /**Checks if the vector z2-z1 is a positive multiple of exactly one
       vector in the translated L-x.        
       Here x and y and the elements of L are interpreted as GoldenComplex objects.*/

    public static boolean matchFold(GoldenComplex z1,GoldenComplex z2,GoldenComplex[] L) {
	int count=0;
	for(int i=0;i<L.length;++i) {
	    GoldenComplex z3=new GoldenComplex(L[i]);
	    if(GoldenComplex.isFolded(z1,z2,z3)==true) ++count;
	}
	if(count==1) return(true);
	return(false);

    }


    /**This is the main routine, it checks that each vector (x,L1[i])
       points in the same direction as some vector (x,L2[j]).**/

    public static boolean matchFold(GoldenComplex z,GoldenComplex[] L1,GoldenComplex[] L2) {
	for(int i=0;i<L1.length;++i) {
	    if(matchFold(z,L1[i],L2)==false) return(false);
	}
	return(true);
    }

    /**Checks if the first point is a vertex of the polygon**/

    public static int vertexMatch(GoldenComplex z,GoldenPolyWedge P) {
	for(int i=0;i<P.count;++i) {
	    if(GoldenComplex.equals(z,P.z[i])==true) return(i);
	}
	return(-1);
    }


    /**ELIMINATE SPANNING EDGES:  A spanning edge is an edge of the
       small polygon that has both vertices in the boundary of the
       big polygon.  Our covering test only works when there are no
       spanning edges.**/

    /**This routine pre-processes the list of all polygons
       adding extra vertices to those polygons which have spanning
       edges.*/

    public static GoldenPolyWedge[] clean(GoldenPolyWedge[] LIST,GoldenPolyWedge HOME) {
	GoldenPolyWedge[] LIST2=new GoldenPolyWedge[LIST.length];
	for(int i=0;i<LIST.length;++i) {
	    boolean test=spanningEdge(LIST[i],HOME);
	    if(test==false) LIST2[i]=LIST[i];
	    if(test==true) LIST2[i]=addVertices(LIST[i]);
	}
	return(LIST2);
    }


    public static GoldenPolyWedge addVertices(GoldenPolyWedge P) {
	GoldenPolyWedge Q=new GoldenPolyWedge();
	Q.count=2*P.count;
	for(int i=0;i<P.count;++i) {
	    int i0=i;
	    int i1=(i+1)%P.count;
            GoldenComplex z0=P.z[i0];
	    GoldenComplex z1=P.z[i1];
	    GoldenComplex z2=GoldenComplex.interpolate(z0,z1);
	    Q.z[2*i+0]=new GoldenComplex(z0);
	    Q.z[2*i+1]=new GoldenComplex(z2);
	}
	return(Q);
    }


    /**This routine checks if a polygon has 
       an edge that intersects the interior of the big polygon but 
       has both vertices in the boundary**/


    public static boolean spanningEdge(GoldenPolyWedge Q,GoldenPolyWedge HOME) {
	for(int i=0;i<Q.count;++i) {
	    int i0=i;
	    int i1=(i+1)%Q.count;
	    GoldenComplex z0=Q.z[i0];
	    GoldenComplex z1=Q.z[i1];
	    GoldenComplex z2=GoldenComplex.interpolate(z0,z1);
	    boolean test0=inside(z0,HOME);
	    boolean test1=inside(z1,HOME);
	    boolean test2=inside(z2,HOME);
	    if((test0==false)&&(test1==false)&&(test2==true)) return(true);
	}
	return(false);
    }




    /**returns true if and only if the vertex lies in the interior of the polygon.
       All our polygons are counterclockwise oriented.**/

    public static boolean inside(GoldenComplex z,GoldenPolyWedge P) {
	for(int i=0;i<P.count;++i) {
	    int i0=i;
	    int i1=(i+1)%P.count;
   	    boolean test=GoldenComplex.isPositivelyOriented(z,P.z[i0],P.z[i1]);
	    if(test==false) return(false);
	}
	return(true);
    }

}