import java.awt.event.*;
import java.awt.*;
import java.awt.geom.*;
import java.util.Arrays;

/**This class starts with an already-built
polygon and extracts the graph (vertices + edges)
using the pairing and holonomy data*/


public class PolygonToGraph {


    /**This routine adds the total list of complex points
       and sorts them into equivalence classes*/

public static void getVertices(EnhancedPolygon E,int mode) {
	E.V=PolygonFiller.totalList(E,mode);
	int[][] list=pairListRaw(E);
	list=improveList(E,list);
	int cc=0;
	int[][] LIST=new int[E.V.length][1];

	for(int i=0;i<E.V.length;++i) {
	    if(E.V[i].a[0]==0) {
		LIST[cc][0]=i;
		++cc;
	    }
	}
	LIST=ListHelp.trim(LIST,cc);
	E.equiv=ListHelp.merge(LIST,list);
    }


    /**This produces the complex affine map which
       maps (e1,e2) to (f1,f2)*/

    public static Complex doPair(Complex e1,Complex e2,Complex f1,Complex f2,Complex z) {
	Complex e12=Complex.minus(e1,e2);
	Complex f12=Complex.minus(f1,f2);
	Complex u=Complex.divide(f12,e12);
	Complex z1=Complex.minus(z,e1);
	Complex z2=Complex.times(z1,u);
	Complex z3=Complex.plus(z2,f1);
	return z3;
    }

    /**This does the (k)th pairing map*/

    public static Complex doPair(EnhancedPolygon E,int k,Complex w) {
    	int a1=k;
	int a2=(a1+1)%E.count;
    	int b1=E.pair[k];
	int b2=(b1+1)%E.count;
	Complex e1=E.z[a1];
	Complex e2=E.z[a2];
	Complex f1=E.z[b2];
	Complex f2=E.z[b1];
	return doPair(e1,e2,f1,f2,w);
      }


    /**Checks if the relevant side pairing matches the two vertices*/
    
    public static boolean isPaired(EnhancedPolygon E,int k,Complex z1,Complex z2) {
	if(z1.a[0]==0) return false;
	if(z2.a[0]!=z1.a[0]) return false;
	if(z1.a[1]!=k) return false;
  	Complex w1=doPair(E,k,z1);
	double test=Complex.dist(w1,z2);
	if(test>.0000001) return false;
	return true;
    }


    public static int[][] improveList(EnhancedPolygon E,int[][] t) {
	int[][] u=improveList0(E,t);
	for(int i=0;i<6;++i) u=improveList0(E,u);
	u=ListHelp.irredundant(u);
	int[][] v=new int[u.length][0];
	int cc=0;
	for(int i=0;i<6;++i) {
	    for(int j=0;j<u.length;++j) {
		if(u[j].length==i) {
		    v[cc]=ListHelp.copy(u[j]);
		    ++cc;
		}
	    }
	}
	return v;
    }

    public static int[][] improveList0(EnhancedPolygon E,int[][] t) {
	int[][] u=new int[t.length][0];
	for(int i=0;i<t.length;++i) {
	    u[i]=ListHelp.copy(t[i]);
	    for(int j=0;j<t.length;++j) {
		if(ListHelp.isOverlap(u[i],t[j])==true) {
		    u[i]=ListHelp.merge(u[i],t[j]);
		    u[i]=ListHelp.irredundant(u[i]);
		    Arrays.sort(u[i]);
		}
	    }
	}
	return u;
    }


    /**creates the raw pairing list*/

    public static int[][] pairListRaw(EnhancedPolygon E) {
	//	Complex[] q=PolygonFiller.totalList(this);
	Complex[] q=ListHelp.trim(E.V,E.V.length);
	int max=q.length;
	int[][] list=new int[max][2];
	int cc=0;
	for(int i=0;i<q.length;++i) {
	    for(int j=0;j<q.length;++j) {
		Complex a=new Complex(q[i]);
		Complex b=new Complex(q[j]);
   		boolean test=isPaired(E,a.a[1],a,b);
		if(test==true) {
		    list[cc][0]=a.a[2];
		    list[cc][1]=b.a[2];
		    ++cc;
		}
	    }
	}
	int[][] list2=new int[cc][2];
	for(int i=0;i<cc;++i) list2[i]=list[i];
	return list2;
    }




    /** getting the edges*/
    
    public static void getEdges(EnhancedPolygon E) {
 	int n=E.equiv.length;
	E.graph=new int[n][0];
	for(int i=0;i<n;++i) {
	    int cc=0;
	    int[] list=new int[12];
	    for(int j=0;j<n;++j) {
		if(isNeighbor(E,i,j)==true) {
 		    list[cc]=j;
		    ++cc;
		}
	    }
   	    E.graph[i]=ListHelp.trim(list,cc);
	    Arrays.sort(E.graph[i]);
	}
    }

    public static boolean isNeighbor(EnhancedPolygon E,int i0,int i1) {
	if(i0==i1) return false;
	boolean test=false;
	test=isNeighbor0(E,i0,i1);
	if(test==true) return true;
	test=isNeighbor1(E,i0,i1);
	if(test==true) return true;
	return false;
    }

    public static boolean isNeighbor0(EnhancedPolygon E,int i0,int i1) {
	int[] t0=E.equiv[i0];
	int[] t1=E.equiv[i1];
	for(int j0=0;j0<t0.length;++j0) {
	   for(int j1=0;j1<t1.length;++j1) {
	       Complex z0=E.V[t0[j0]];
	       Complex z1=E.V[t1[j1]];
	       double d=Complex.dist(z0,z1);
	       if((d>.99)&&(d<1.01)) return true;
	   }
	}
	return false;
    }


    public static boolean isNeighbor1(EnhancedPolygon E,int i0,int i1) {
	int[] t0=E.equiv[i0];
	int[] t1=E.equiv[i1];
	for(int q0=0;q0<t0.length;++q0) {
	    for(int q1=0;q1<t1.length;++q1) {
	      Complex z0=E.V[t0[q0]];
	      Complex z1=E.V[t1[q1]];
	      int[] list0=E.crossingList(z0);
	      int[] list1=E.crossingList(z1);
	      if((list0!=null)&&(list1!=null)) {
	        for(int j0=0;j0<list0.length;++j0) {
	        for(int j1=0;j1<list1.length;++j1) {
	           int k0=list0[j0];
	           int k1=list1[j1];
	           if(k1==E.pair[k0]) {
		       Complex w1=doPair(E,k1,z1);
		      double d=Complex.dist(z0,w1);
		      if((d>.99)&&(d<1.01)) return true;
		   }
		}}
	      }
	    }
	}
	return false;
    }

}


