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

/**This contains the proof of 3 statements:

1. The strip Signa=[-20,20] times [-2,2] is covered by the union of the pinwheel
   tiles and the 3 place-holder tiles of Sigma-Sigma_+-Sigma_-.  That is,
   Sigma_+ and Sigma_- are covered by the pinwheel tiles. 

2. The outer billiards map is defined on
   the interior of each pinwheel tile, at least until the square outer billiards
   map first returns to the relevant strip.  We are talking about either
   the positive strip Sigma_plus or the negative strip Sigma_minus.

3. The outer billiards map is not defined on any essential edge of a pinwheel 
   tile. By essential, we mean an edge that is not contained in the
   boundary of the main strip.

In the paper, Statements 2 and 3 correspond to the result that the pinwheel tiles 
are Psi-perfect.**/

    


public class ProofPinwheel1 implements Runnable {
    int halt;
    Manager M;


public ProofPinwheel1(Manager MM) {
    this.M=MM;
}


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


    public void run() {

	int mode=M.C.CON_X.PINWHEEL.mode;
	if(mode==0) coverTest();
	if(mode>0) definednessTest();
    }

    /**This routine checks statement 1 above. We also plot
       the tiles as a sanity check.*/

    public void coverTest() {
        GoldenPolyWedge[] ALL=polyList();
        int total=ALL.length;
	PolyCover.coverTest(ALL,total,basicStrip());
	for(int i=0;i<total;++i) M.T.addPoly(ALL[i].toPolyWedge());
	M.T.repaint();
    }


    public void definednessTest() {
        GoldenPolyWedge[] ALL=polyList();
        int total=ALL.length;
	System.out.print("start defined test 1  --  ");
	for(int i=0;i<total;++i) {
	   boolean test=testDefined(i);
	   if(test==false) failMessage();
	} 
        System.out.println("end");

	System.out.print("start undefined test 1  --  ");
	for(int i=0;i<total;++i) {
	   boolean test=testUndefined(i);
	   if(test==false) failMessage();
	}
	System.out.println("end");
    }



    /**Here is the rectangle [-20,20] times [-2,2]**/

    public static GoldenPolyWedge basicStrip() {
	GoldenPolyWedge GP=new GoldenPolyWedge();
	GP.count=4;
	GP.z[0]=new GoldenComplex(-20,0,-2,0);
	GP.z[1]=new GoldenComplex(+20,0,-2,0);
	GP.z[2]=new GoldenComplex(+20,0,+2,0);
	GP.z[3]=new GoldenComplex(-20,0,+2,0);
	return(GP);
    }


    /**This gets the list of all the pinwheel polyhedra**/


    public static GoldenPolyWedge[] polyList() {
	int total=DataPinwheel.COUNT();
	int count=0;
	GoldenPolyWedge[] LIST=new GoldenPolyWedge[total];
	for(int i=0;i<total;++i) {
	    GoldenPolyWedge P=DataPinwheel.returnPoly(i);
	    if(outOfRange(P)==false) {
		LIST[count]=P;
		++count;
	    }
	}
	LIST=Lists.clean(LIST,count);
	System.out.println("total number "+LIST.length);
	return(LIST);
    }

	/**This returns true of the polygon is
           completely outside the strip**/

	public static boolean outOfRange(GoldenPolyWedge P) {
	    if(tooNegative(P)==true) return(true);
	    if(tooPositive(P)==true) return(true);
	    return(false);
	}


	public static boolean tooNegative(GoldenPolyWedge P) {
	    GoldenReal r=new GoldenReal(-20,0);
	    for(int i=0;i<P.count;++i) {
		if(GoldenReal.isLess(P.z[i].x,r)==false) return(false);
	    }
	    return(true);
	}

	public static boolean tooPositive(GoldenPolyWedge P) {
	    GoldenReal r=new GoldenReal(20,0);
	    for(int i=0;i<P.count;++i) {
		if(GoldenReal.isLess(r,P.z[i].x)==false) return(false);
	    }
	    return(true);
	}







    /**This performs the check for the ith tile.  The
       idea is to first nonrigorously compute the 
       vertex sequence for the center of the tile.
       Once we have the vertex sequence, we rigorously
       check that each vertex of the given pinwheel
       tile weakly follows this itinerary.  This means
       that there is an arbitrarily small perturbation
       which does follow the itinerary in the strict sense.
       If all the vertices weakly follow the itinerary,
       then every point in the interior of the tile
       files in the actual sense.  This follows from
       convexity.*/


    public boolean testDefined(int i) {
         Complex z=center(i);  
         int[] list=vertexSequence(z);	
	 if(list==null) return(true);
         GoldenPolyWedge P=DataPinwheel.returnPoly(i);
	 for(int j=0;j<P.count;++j) {
	     boolean test=testDefined(i,j);
	     if(test==false) return(false);
	 }
	 return(true);
    }


    /**This performs the check that the jth vertex
       of the ith tile weakly follows the itinerary computed for
       the centroid of the tile.**/

    public boolean testDefined(int i,int j) {
         Complex z=center(i);  
         int[] list=vertexSequence(z);
	 GoldenPolyWedge P=DataPinwheel.returnPoly(i);
	 GoldenComplex zz=new GoldenComplex(P.z[j]);
	 boolean test=testOrbit(zz,list);
	 return(test);
    }



    /**This checks that a given point weakly follows
       the itinerary specified by the given list of vertices*/

    public boolean testOrbit(GoldenComplex z,int[] list) {
	GoldenComplex w=new GoldenComplex(z);
	for(int i=0;i<list.length;++i) {
	    boolean test=testPoint(w,list[i]);
	    w=outerBilliards(list[i],w);
	    if(test==false) return(false);
	}
	return(true);
    }



    /**This checks that a given point z is weakly contained in
       the region of the plane on which the outer billiards map
       selects the kth vertex.*/

    public boolean testPoint(GoldenComplex z,int k) {
	GoldenComplex[] X=penroseKite();
	int k1=(k+3)%4;
	int k2=(k+0)%4;;
	int k3=(k+1)%4;

	boolean test1=GoldenComplex.weakPositivelyOriented(X[k1],X[k2],z);
	boolean test2=GoldenComplex.weakPositivelyOriented(X[k3],X[k2],z);
	if(test1==false) return(false);
	if(test2==false) return(false);
	return(true);
    }




    /**This performs the check that the first return map
       is nowhere defined on the boundary of the ith tile.**/

    public boolean testUndefined(int i) {
         GoldenPolyWedge P=DataPinwheel.returnPoly(i);
	 for(int j=0;j<P.count;++j) {	 
	     boolean test=testUndefined(i,j);
	     if(test==false) return(false);
	 }
	 return(true);
    }



    /**Checks if the point lies on one of the 3 horizontal lines
       y=-2,0,2.  We ignore horizontal edges on these lines**/

    public static boolean onBdy(GoldenComplex z) {
	if((z.y.a[0]==+2)&&(z.y.a[1]==0)) return(true);
	if((z.y.a[0]== 0)&&(z.y.a[1]==0)) return(true);
	if((z.y.a[0]==-2)&&(z.y.a[1]==0)) return(true);
	return(false);
    }



    /**This performs the check that some pre-first-return
       iterate of the the outer billiards map
       is nowhere defined on the jth edge of the ith tile**/


    public boolean testUndefined(int i,int j) {
         Complex z=center(i);  
         int[] list=vertexSequence(z);
	 if(list==null) return(true);
	 GoldenPolyWedge P=DataPinwheel.returnPoly(i);
	 int j1=j;
	 int j2=(j+1)%P.count;
	 GoldenComplex zz1=new GoldenComplex(P.z[j1]);
	 GoldenComplex zz2=new GoldenComplex(P.z[j2]);
	 boolean test1=onBdy(zz1);
	 boolean test2=onBdy(zz2);
	 if((test1==true)&&(test2==true)) return(true);  //ignore edges on boundary of strip
	 boolean test=testOrbitRay(zz1,zz2,list);
	 if(test==false) {
	     Complex aa1=zz1.toComplex();
	     Complex aa2=zz2.toComplex();
	     aa1.print();
	     aa2.print();
	 }

	 return(test);
    }



    /**This checks that a given pair of points eventually lands
       in one of the boundary rays of the sectors*/

    public boolean testOrbitRay(GoldenComplex z1,GoldenComplex z2,int[] list) {
	GoldenComplex w1=new GoldenComplex(z1);
	GoldenComplex w2=new GoldenComplex(z2);
	for(int i=0;i<list.length;++i) {
	    boolean test=testRay(w1,w2,list[i]);
	    w1=outerBilliards(list[i],w1);
	    w2=outerBilliards(list[i],w2);
	    if(test==true) return(true);
	}
        boolean test=excludedEdge(w1,w2);
	if(test==true) return(true);
	return(false);
    }



    /**This tests if the two points lie in a common boundary ray
       of the planar region associated to the kth vertex.  This region
       is a cone.**/


    public boolean testRay(GoldenComplex z,GoldenComplex w,int k) {
	GoldenComplex[] X=penroseKite();
	int k1=(k+3)%4;
	int k2=(k+0)%4;;
	int k3=(k+1)%4;
	boolean test1=GoldenComplex.collinear(X[k1],X[k2],z,w);
	boolean test2=GoldenComplex.collinear(X[k3],X[k2],z,w);
	if(test1==true) return(true);
	if(test2==true) return(true);
	if(excludedEdge(z,w)==true) return(true);
	return(false);
    }

    /**This tests if the edge is one of the 4 special excluded edges**/

    public boolean excludedEdge(GoldenComplex z,GoldenComplex w) {
	if(excludedEdge1(z,w)==true) return(true);
	if(excludedEdge1(z.conjugate(),w.conjugate())==true) return(true);
	return(false);
    }


    public boolean excludedEdge1(GoldenComplex z,GoldenComplex w) {
	GoldenComplex[] X=excludedVertices();
	boolean test1=GoldenComplex.weakBetween(z,X[0],X[1]);
	boolean test2=GoldenComplex.weakBetween(w,X[0],X[1]);
	boolean test3=GoldenComplex.weakBetween(z,X[0],X[2]);
	boolean test4=GoldenComplex.weakBetween(w,X[0],X[2]);
	if((test1==true)&&(test2==true)) return(true);
	if((test3==true)&&(test4==true)) return(true);
	return(false);

    }



    /**Computes the centroid of the ith dynamical tile.  This is a
       floating point computation, but we don't need to do any
       rigorous computations with this point.*/


    public static Complex center(int i) {
           GoldenPolyWedge IP=DataPinwheel.returnPoly(i);
	   PolyWedge P=IP.toPolyWedge();
	   return(P.getCenter());
    }

    /**tests if the given point is inside the Penrose kite.*/

    public static boolean insideKite(Complex z) {
	PolyWedge P=PolyWedge.penroseKite();
	if(P.inside(z)==true) return(true);
	return(false);
    }



/**This routine computes the sequence of vertices
hit by a point z, as it does one iteration of
the first return map to the positive strip. This is not a rigorous
computation, but it doesn't matter.  We simply use this
computation to generate a candidate sequence, relative to
the centroid of each tile, and then we rigorously verify
that the sequence works for all the tile vertices.**/

    public static int[] vertexSequence(Complex w) {
	int a1=OuterBilliards.positiveTest(w);
	int a2=OuterBilliards.negativeTest(w);
	if(insideKite(w)==true) return(null);
	if((a1==0)&&(a2==0)) return(null);
	Complex z=new Complex(w);
	int[] LIST0=new int[1000];
	int count=0;
	int test=0;
	while(test==0) {
	    int b1=0;
	    int b2=0;

	    if(test==0) {
	      z=OuterBilliards.nextComplex(z);
	      LIST0[count]=z.history;++count;
	      z=OuterBilliards.nextComplex(z);
	      LIST0[count]=z.history;++count;
 	      b1=OuterBilliards.positiveTest(z);
	      b2=OuterBilliards.negativeTest(z);
	    }
	    if((a1==b1)&&(a2==b2)) test=1;
	}
	int[] LIST=new int[count];
	for(int i=0;i<count;++i) LIST[i]=LIST0[i];
	return(LIST);
    }


    /**lists the vertices of the Penrose kite, as GoldenComplex objects*/

    public static GoldenComplex[] penroseKite() {
	GoldenComplex[] X=new GoldenComplex[4];
	X[0]=new GoldenComplex(0,0,1,0);
	X[1]=new GoldenComplex(-1,0,0,0);
	X[2]=new GoldenComplex(0,0,-1,0);
	X[3]=new GoldenComplex(-3,2,0,0);
	return(X);
    }

    /**lists the vertices of the upper excluded edges**/

    public static GoldenComplex[] excludedVertices() {
	GoldenComplex[] X=new GoldenComplex[4];
	X[0]=new GoldenComplex(0,0,1,0);
	X[1]=new GoldenComplex(3,-2,2,0);
	X[2]=new GoldenComplex(1,0,2,0);
	return(X);
    }

    /**Does one step of the outer billiards map on the point z. In
       all cases the point z is weakly contained in the region associated to
       the kth vertex.*/


    public static GoldenComplex outerBilliards(int k,GoldenComplex z) {
	GoldenComplex[] X=penroseKite();
	GoldenComplex  v=X[k];
	v=GoldenComplex.plus(v,v);
	v=GoldenComplex.minus(v,z);
	return(v);
    }

}