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



public class GoldenPolyCombinatorics {

    /**MAIN ROUTINES**/

    /** given a convex GoldenPolyhedron, return the list of faces. 
        The faces are given as lists of vertices, with each face
        being listed according to the following right hand rule: If you
        curl your right hand around the vertices, as they are listed,
        your thumb points along the OUTWARD normal*/


     public static int[][] faceList(GoldenPolyhedron P) {
	 int[] LIST=faceListRaw(P);
	 int[][] LIST2=new int[LIST.length][0];

	 for(int i=0;i<LIST2.length;++i) LIST2[i]=fixFace(P,LIST[i]);
	 return(LIST2);
     }

    /**returns the list of edges of a polyhedron**/

     public static int[][] edgeList(GoldenPolyhedron P) {
	 int[][] LIST=new int[100][2];
	 int total=0;
	 for(int i=0;i<P.count;++i) {
	     for(int j=i+1;j<P.count;++j) {
		 boolean test=edge(P,i,j);
		 if(test==true) {
		     LIST[total][0]=i;
		     LIST[total][1]=j;
		     ++total;
		 }
	     }
	 }
	 int[][] LIST2=new int[total][2];
	 for(int i=0;i<total;++i) LIST2[i]=LIST[i];
	 return(LIST2);
     }

    /**returns the list of edges of a polyhedron that cross a
       horizontal plane of a given Z[phi] height. The ordering
       is such that consecutive pairs of edges are co-facial.**/


    public static int[][] edgeList(GoldenPolyhedron P,GoldenReal r) {
	int[][] LIST=edgeList(P);
	if(LIST==null) return(null);
	int total=0;

	for(int k=0;k<LIST.length;++k) {
	    int i=LIST[k][0];
	    int j=LIST[k][1];
	    boolean test=testCross(P,i,j,r);
	    if(test==true) {
                 LIST[total][0]=i;
		 LIST[total][1]=j;
		 ++total;
	    }
	}
	if(total==0) return(null);
	int[][] LIST2=new int[total][2];
	for(int i=0;i<total;++i) LIST2[i]=LIST[i];

        for(int i=0;i<LIST2.length-1;++i) {
             LIST2=nextInEdgeCircuit(P,LIST2,i);
	}
	return(LIST2);
    }


    /**Gets the index list of the anchors/normals to the polyhedron.
       anchor points listed first; normals listed second.*/

    public static int[][] normalList(GoldenPolyhedron P) {
	int[][] A=faceList(P);
	int[][] LIST=new int[A.length][2];
	for(int i=0;i<A.length;++i) {
	    LIST[i][0]=A[i][0];
	    GoldenVector V=GoldenVector.normal(P.V[A[i][0]],P.V[A[i][1]],P.V[A[i][2]]);
	    for(int j=0;j<18;++j) {
		if(GoldenVector.isPositiveMultiple(V,DataPartition.getNormal(j))==true) {
		   LIST[i][1]=j;
		}
	    }
	}
	return(LIST);
    }

    /**tests whether a point is inside the polyhedron**/

    public static boolean inside(GoldenPolyhedron P,GoldenVector V) {
	int[][] LIST=normalList(P);
	return(inside(P,V,LIST));
    }

    public static boolean inside(GoldenPolyhedron P,GoldenVector V,int[][]LIST) {
	for(int i=0;i<LIST.length;++i) {
           GoldenVector p=P.V[LIST[i][0]];
	   GoldenVector n=DataPartition.getNormal(LIST[i][1]);
	   GoldenReal test1=GoldenVector.dot(n,p);
	   GoldenReal test2=GoldenVector.dot(n,V);
	   GoldenReal test3=GoldenReal.minus(test1,test2);
	   if(test3.isPositiveOrZero()==false) return(false);
	}
	return(true);
    }


    /**computes the polygon intersection of P with the plane of height r*/

    public static GoldenPolyWedge intersect(GoldenPolyhedron P,GoldenReal r) {
	GoldenPolyWedge Q=new GoldenPolyWedge();
	int total=0;
	int[][] LIST=edgeList(P,r);

	if(LIST==null) return(null);
	Q.count=LIST.length;
	for(int a=0;a<LIST.length;++a) {
	    int i=LIST[a][0];
	    int j=LIST[a][1];
	    GoldenVector[] V={P.V[i],P.V[j]};
	    Q.z[a]=interpolate(r,V);
	}
	boolean test=GoldenComplex.isPositivelyOriented(Q.z[0],Q.z[1],Q.z[2]);
	if(test==true) return(Q);
	/**reverse the polygon **/
	GoldenPolyWedge QQ=new GoldenPolyWedge();
	QQ.count=Q.count;
	int n=Q.count-1;
	for(int i=0;i<Q.count;++i) {
	    QQ.z[i]=new GoldenComplex(Q.z[n-i]);
	}
	return(QQ);
    }





    /**SUPPORTING ROUTINES**/

    /**This routine tells which vertex comes next in the circuit.**/

     public static int[][] nextInEdgeCircuit(GoldenPolyhedron P,int[][] u,int k) {
	     int[] u2={-1,-1};
	     int L=u.length;
	     for(int i=k+1;i<L;++i) {
		 int[] uu={u[k][0],u[k][1],u[i][0],u[i][1]};
		 uu=mergeIndices(uu);
		 if(face(P,uu)==true) u2=u[i];
	     }
	     int[][] v=new int[L][2];
	     for(int i=0;i<=k;++i) v[i]=u[i];
	     v[k+1]=u2;
	     int total=k+2;
	     for(int i=k+1;i<L;++i) {
		 if(u[i]!=u2) {
		     v[total]=u[i];
		     ++total;
		 }
	     }
	     return(v);
     }


    public static int[] mergeIndices(int[] u) {
	if((u[2]!=u[0])&&(u[2]!=u[1])&&(u[3]!=u[0])&&(u[3]!=u[1])) return(u);
	if((u[2]!=u[0])&&(u[2]!=u[1])) {
	       int[] v={u[0],u[1],u[2]};
	       return(v);
	}
        int[] v={u[0],u[1],u[3]};
	return(v);
    }



     /**This gives the list of subsets of vertices that have faces.
        However, these subsets are not cyclically ordered.**/

     public static int[] faceListRaw(GoldenPolyhedron P) {
	int[] LIST=new int[2048];
	int N=P.count;
	int total=0;
	for(int i=0;i<Math.pow(2,N);++i) {
	    int[] u=binaryList(N,i);
	    boolean test=face(P,u);
	    if((u.length>=3)&&(test==true)) {
                LIST[total]=i;
		++total;
	    }
	}
	int[] LIST2=new int[total];
	for(int i=0;i<total;++i) LIST2[i]=LIST[i];
	LIST2=trim(N,LIST2);
	return(LIST2);
    }


     /**This routine converts the raw data into the list of
        vertices, and then orders the list into a circuit.*/

     public static int[] fixFace(GoldenPolyhedron P,int n) {
	 int N=P.count;
	 int[] u=binaryList(N,n);
	 if(u.length>3) {
	   for(int i=0;i<u.length-1;++i) u=nextInFaceCircuit(P,u,i);
	 }
	 boolean test=faceOriented(P,u);
	 if(test==true) return(u);
	 /*reverse orientation*/
	 int[] v=new int[u.length];
	 for(int i=1;i<u.length;++i) v[i]=u[u.length-i];
	 v[0]=u[0];
	 return(v);
     }


    /**This routine tells which vertex comes next in the circuit.**/

     public static int[] nextInFaceCircuit(GoldenPolyhedron P,int[] u,int k) {

	     int u2=-1;
	     int L=u.length;
	     for(int i=k+1;i<L;++i) {
		 if(edge(P,u[k],u[i])==true) {
                     u2=u[i];
		 }
	     }
	     int[] v=new int[L];
	     for(int i=0;i<=k;++i) v[i]=u[i];
	     v[k+1]=u2;
	     int total=k+2;
	     for(int i=k+1;i<L;++i) {
		 if(u[i]!=u2) {
		     v[total]=u[i];
		     ++total;
		 }
	     }
	     return(v);
     }



     /**This routine answers true if the point X is an extreme point for the linear
        functional "dot with DIR".  
        When choice=0, we insist that the point is a strict extreme point.
        This is the vertex test.
        When choice=1, we do not insist this.  This is the test we use for faces.*/

    public static boolean extreme(GoldenPolyhedron P,int choice,GoldenVector X,GoldenVector DIR) {
	for(int j=0;j<P.count;++j) {
	    GoldenVector Y=GoldenVector.minus(X,P.V[j]);
	    GoldenReal d=GoldenVector.dot(Y,DIR);

	    double dd=Vector.dot(Y.toVector(),DIR.toVector());
	    double ee=d.toDouble();
	    if(Math.abs(dd-ee)>.0001) {
		System.out.println("ERROR");
		DIR.print();
	    }

	    boolean test0=d.isZero();
	    boolean test1=d.isPositive();
	    boolean test2=GoldenVector.equals(X,P.V[j]);
	    if((choice==0)&&(test1==false)&&(test2==false)) return(false);
	    if((choice==1)&&(test0==false)&&(test1==false)&&(test2==false)) return(false);
	}
	return(true);
    }








/**tells if the list of vertices is the subset of a face.  Computes the centroid
   of the list of vectors and decides if it is on the boundary or not.*/

     public static boolean face(GoldenPolyhedron P,int[] u) {
	if(u.length<3) return(false);
	boolean test0=coplanar(P,u);
	if(test0==false) return(false);
	GoldenPolyhedron Q=P.scale(u.length);
	GoldenVector W=GoldenVector.zero();
	GoldenVector DIR=normal(Q.V[u[0]],Q.V[u[1]],Q.V[u[2]]);
	if(DIR==null) return(false);
	for(int i=0;i<u.length;++i) W=GoldenVector.plus(W,P.V[u[i]]);
        boolean test1=extreme(Q,1,W,DIR);
	DIR=DIR.negate();
        boolean test2=extreme(Q,1,W,DIR);
	if(test1==true) return(true);
	if(test2==true) return(true);
	return(false);
    }


    /**This routine relies on our advance knowledge that the normals are only
       in one of 18 directions.**/

    public static GoldenVector normal(GoldenVector V1,GoldenVector V2,GoldenVector V3) {
	GoldenVector W=GoldenVector.normal(V1,V2,V3);
	for(int i=0;i<18;++i) {
	    GoldenVector X=DataPartition.getNormal(i);
	    if(GoldenVector.isPositiveMultiple(W,X)==true) return(X);
	}
	return(null);
    }




    /**tells if a list of vectors is coplanar**/

   public static boolean coplanar(GoldenPolyhedron P,int[] u) {
       int n=u.length;
       if(n==3) return(true);
       for(int i=0;i<n-3;++i) {
	  GoldenVector DIR1=GoldenVector.normal(P.V[u[i+0]],P.V[u[i+1]],P.V[u[i+2]]);
	  GoldenVector DIR2=GoldenVector.normal(P.V[u[i+1]],P.V[u[i+2]],P.V[u[i+3]]);
	  GoldenVector V=GoldenVector.cross(DIR1,DIR2);
	  if(V.isZero()==false) return(false);
       }
       return(true);
   }





     /**This only will return true if the first 3 vertices of the face
        are counter-clockwise oriented.*/

     public static boolean faceOriented(GoldenPolyhedron P,int[] u) {
	if(u.length<3) return(false);
	GoldenPolyhedron Q=P.scale(u.length);
	GoldenVector W=GoldenVector.zero();
	GoldenVector DIR=normal(Q.V[u[0]],Q.V[u[1]],Q.V[u[2]]);
	for(int i=0;i<u.length;++i) W=GoldenVector.plus(W,P.V[u[i]]);
        boolean test1=extreme(Q,1,W,DIR);
	if(test1==true) return(true);
	return(false);
    }


     /**answers true if the edge lies in 2 distinct faces*/

     public static boolean edge(GoldenPolyhedron P,int i,int j) {
	 for(int k1=0;k1<P.count;++k1) {
	     for(int k2=k1+1;k2<P.count;++k2) {
		 if((i!=k1)&&(i!=k2)&&(j!=k1)&&(j!=k2)) {
		     int[] u1={i,j,k1};
		     int[] u2={i,j,k2};
		     boolean test1=face(P,u1);
		     boolean test2=face(P,u2);
		     if((test1==true)&&(test2==true)) {
			 GoldenVector V1=GoldenVector.normal(P.V[i],P.V[j],P.V[k1]);
			 GoldenVector V2=GoldenVector.normal(P.V[i],P.V[j],P.V[k2]);
			 GoldenVector W=GoldenVector.cross(V1,V2);
			 if(W.isZero()==false) return(true);
		     }
		 }
	     }
	 }
	 return(false);
    }


    /**checks if an edge of a polyhedron crosses a given plane**/

    public static boolean testCross(GoldenPolyhedron P,int i,int j,GoldenReal t) {
	GoldenReal r1=P.V[i].x[2];
	GoldenReal r2=P.V[j].x[2];
	boolean test1=GoldenReal.isLess(r1,t);
	boolean test2=GoldenReal.isLess(t,r2);
	if((test1==true)&&(test2==true)) return(true);
        test1=GoldenReal.isLess(r2,t);
	test2=GoldenReal.isLess(t,r1);
	if((test1==true)&&(test2==true)) return(true);
	return(false);
    }


    public static GoldenComplex interpolate(GoldenReal t,GoldenVector[] V) {
 	GoldenVector W=new GoldenVector();
	GoldenReal x0=new GoldenReal(V[0].x[0]);
	GoldenReal x1=new GoldenReal(V[1].x[0]);
	GoldenReal y0=new GoldenReal(V[0].x[1]);
	GoldenReal y1=new GoldenReal(V[1].x[1]);
	GoldenReal z0=new GoldenReal(V[0].x[2]);
	GoldenReal z1=new GoldenReal(V[1].x[2]);
	GoldenReal s0=GoldenReal.minus(t,z0);
	GoldenReal s1=GoldenReal.minus(z1,z0);
	W.x[0]=GoldenReal.plus(GoldenReal.times(s1,x0),GoldenReal.times(s0,GoldenReal.minus(x1,x0)));
	W.x[1]=GoldenReal.plus(GoldenReal.times(s1,y0),GoldenReal.times(s0,GoldenReal.minus(y1,y0)));
	W.x[2]=GoldenReal.times(s1,t);
	GoldenReal xx=GoldenReal.specialDivide(W.x[0],s1);
	GoldenReal yy=GoldenReal.specialDivide(W.x[1],s1);
	GoldenComplex z=new GoldenComplex(xx,yy);
	return(z);
    }

    /**computes a normal vector to a face.  This is only applied when the list of
       indices lies on a face.**/

    public static GoldenVector normal(GoldenPolyhedron P,int[] A) {
	return(GoldenVector.normal(P.V[A[0]],P.V[A[1]],P.V[A[2]]));
    }


     /**These are combinatorial routines.*/

    /**The pairs (a,N) and (b,N) both determine subsets of the set {0,...,N-1}.
       This routine tests if the former is a subset of the latter.  The purpose
       of this routine is to help in picking out the maximal faces.**/


    public static boolean isSubset(int N,int a,int b) {
	int[] u=binaryList(N,a);
	int[] v=binaryList(N,b);
	return(isSubset(u,v));
    }

     /**straight up routine to tell if one integer list is a subset of another.*/

    public static  boolean isSubset(int[] u,int[] v) {
	for(int i=0;i<u.length;++i) {
	    boolean test=false;
	    for(int j=0;j<v.length;++j) {
		if(u[i]==v[j]) test=true;
	    }
	    if(test==false) return(false);
	}
	return(true);
    }

    public static boolean isSubset(int N,int a,int[] LIST) {
	for(int i=0;i<LIST.length;++i) {
	    if((a!=LIST[i])&&(isSubset(N,a,LIST[i])==true)) return(true);
	}
	return(false);
    }

     /**removes all but the maximal subsets.*/

    public static int[] trim(int N,int[] LIST) {
	int total=0;
	int[] LIST1=new int[LIST.length];
	for(int i=0;i<LIST.length;++i) {
	    if(isSubset(N,LIST[i],LIST)==false) {
		LIST1[total]=LIST[i];
		++total;
	    }
	}
	int[] LIST2=new int[total];
	for(int i=0;i<total;++i) LIST2[i]=LIST1[i];
	return(LIST2);
    }


     /**Produces a subset of {0,...,N-1} from the pair (N,n)**/

    public static int[] binaryList(int N,int n) {
	int[] x=new int[N];
	int m=n;
	for(int count=0;count<N;++count) {
	    x[N-1-count]=m%2;
	    m=(m-x[N-1-count])/2;
	}
	int[] y=new int[N];
	int total=0;
	for(int i=0;i<N;++i) {
	    if(x[i]==1) {
                y[total]=i;
		++total;
	    }
	}
	int[] z=new int[total];
	for(int i=0;i<total;++i) z[i]=y[i];
	return(z);
    }






}