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


/**This routine looks at the solution to a 4-coloring problem
and gets the monochrome pieces.  As usual, a solution is given
in terms of a black/white face coloring with local conditions
around the vertices*/


public class ShapeRecognizer {

    
    /**This is the biggest routine.  It gets all the monochrome pieces of a solution
       and also computes their boundaries*/

    public static int[][][] monochromePieceList(EnhancedPolygon E) {
	int[] used={};
	int count=0;
	int[][][] list=new int[E.flower.length][0][0];
	
	for(int i=0;i<E.triangles.length;++i) {
	    if(ListHelp.onList(i,used)==false) {
		int[][] t=monochromePiece(E,i);
		list[count]=t;
		++count;
		used=ListHelp.merge(used,completeMonochrome(E,i));
	    }
	}
	list=ListHelp.trim(list,count);
	return list;
    }
    
    /**This gets the number of edges (E) and the number of faces (F) and the
       degrees of freedom (E-2F) for the monochrome cell division*/

    public static int[] statsMonochrome(EnhancedPolygon E) {
	int[][][] list=monochromePieceList(E);
	int face=list.length;
	int edge=0;
	for(int i=0;i<list.length;++i) {
	    edge=edge+edgeNumber(E,list[i]);
	}
	edge=edge/2;
	int free=edge-2*face+2;//we add 2 because we don't need to compute the last piece. It is free.
	int[] A={edge,face,free};
	return A;
    }
    
    /**This gets the boundary vertices of the monochrome domain surrounding the (t)th triangle*/
    
    public static int[][] monochromePiece(EnhancedPolygon E,int t) {
	int[] n=completeMonochrome(E,t);
	int[] b=boundaryVerticesOrdered(E,n);
	int[][] T0={n,b};
	int[] g=boundaryGeometry(E,T0);
	int[] c=coneVertices(E,n);
	int[] s={E.solution[t]};
	int[][] T={n,b,g,c,s};
	return T;
    }




    /**This is one of the big routines.  It gets all the triangles in the
       connected region having the same color as the given triangle.*/
    
    public static int[] completeMonochrome(EnhancedPolygon E,int t) {
	int[] list={t};
	boolean test=false;
	while(test==false) {
	    int before=list.length;
	    int[] list2=adjacentMonochrome(E,list);
	    list=ListHelp.merge(list,list2);
	    list=ListHelp.irredundant(list);
	    int after=list.length;
	    if(before==after) test=true;
	}
	return list;
    }

    /**This gets all the triangles having the color sol in {0,1} */
    
    public static int[] getFlower(EnhancedPolygon E,int f,int sol) {
	int[] m=E.flower[f];
	int[] n=new int[m.length];
	int count=0;
	
	for(int i=0;i<m.length;++i) {
	    if(E.solution[m[i]]==sol) {
		n[count]=m[i];
		++count;
	    }
	}
	return ListHelp.trim(n,count);
    }



    /**This gets the triangles that are adjacent and have the same color in the solution*/
    
    public static boolean isAdjacentMonochrome(EnhancedPolygon E,int t1,int t2) {
	boolean test=GraphAnalyzer.isAdjacent(E,t1,t2);
	if(test==false) return false;
	int c1=E.solution[t1];
	int c2=E.solution[t2];
	if(c1==c2) return true;
	return false;
    }

    /**This gets all the same-colored adjacent triangles*/
    
    public static int[] adjacentMonochrome(EnhancedPolygon E,int t) {
	int[] list=new int[3];
	int count=0;
	for(int i=0;i<E.triangles.length;++i) {
	    if(isAdjacentMonochrome(E,t,i)==true) {
		list[count]=i;
		++count;
	    }
	}
	return ListHelp.trim(list,count);
    }

    /**This gets all the same-colored triangles adjacent to everything on the list.*/

    public static int[] adjacentMonochrome(EnhancedPolygon E,int[] t) {
	int[] list={};
	for(int i=0;i<t.length;++i) {
	    int[] y=adjacentMonochrome(E,t[i]);
	    list=ListHelp.merge(list,y);
	}
	list=ListHelp.irredundant(list);
	return list;
    }

    
    /**These routines extract the boundary vertices from a monchrome component*/

    public static int[] boundaryVertices(EnhancedPolygon E,int[] n) {
	int[] list=allVertices(E,n);
	int count=0;
	int[] list2=new int[list.length];
	for(int i=0;i<list.length;++i) {
	    int[] f=E.flower[list[i]];
	    int[] g=ListHelp.intersection(f,n);
	    if(g.length<6) {
		list2[count]=list[i];
		++count;
	    }
	}
	list2=ListHelp.trim(list2,count);
	return list2;
    }

    /**This gets all the boundary vertices which are cone points*/

    public static int[] coneVertices(EnhancedPolygon E,int[] n) {
	int[] b=boundaryVertices(E,n);
	int[] list=new int[b.length];
	int count=0;
	for(int i=0;i<b.length;++i) {
	    if(E.flower[b[i]].length<6) {
		list[count]=b[i];
		++count;
	    }
	}
	return ListHelp.trim(list,count);
    }

    /**This gets all vertices of a monochrome componet*/
    
    public static int[] allVertices(EnhancedPolygon E,int[] n) {
	int[] list={};
	for(int i=0;i<n.length;++i) {
	    int[] J=E.triangles2[n[i]];
	    list=ListHelp.merge(list,J);
	}
	list=ListHelp.irredundant(list);
	return list;
    }

    /**This tells if two vertices are adjacent on the boundary of the union of triangles
       listed in the tri array*/
    
    public static boolean boundaryAdjacent(EnhancedPolygon E,int[] tri,int a1,int a2) {
	if(a1==a2) return false;
	if(a1==-1) return false;
	if(a2==-1) return false;
  	int[] f1=E.flower[a1];
	int[] f2=E.flower[a2];
	int[] g=ListHelp.intersection(f1,f2);
	g=ListHelp.intersection(g,tri);
	if(g.length==1) return true;
	return false;
    }


    /**This gives the cyclically ordered list of boundary vertices*/
    public static int[] boundaryVerticesOrdered(EnhancedPolygon E,int[] n) {
	int[] list=boundaryVertices(E,n);
	int[] partial={list[0]};
	boolean test=true;
	while(test==true) {
	    if(partial.length<list.length) partial=augment(E,list,n,partial);
	    else test=false;
	}
	return partial;
    }
    

    /**These routines get the correct order on the boundary vertices*/


    public static int[] augment(EnhancedPolygon E,int[] vtx,int[] tri,int[] partial) {
	if(partial.length==1) {
	    int k=getNext(E,vtx,tri,partial[0]);
	    int[] extend=ListHelp.append(partial,k);
	    return extend;
	}
	else {
	    int l=partial.length;
	    int k=getNext(E,vtx,tri,partial[l-2],partial[l-1]);
	    int[] extend=ListHelp.append(partial,k);
	    return extend;
	}
    }

    /**starts with the FIRST vertex and gets the next (adjacent) one*/
    
    public static int getNext(EnhancedPolygon E,int[] vtx,int[] tri,int a) {
	for(int i=0;i<vtx.length;++i) {
	    if(boundaryAdjacent(E,tri,a,vtx[i])==true) return vtx[i];
	}
	return -1;
    }

    /**Given some finite linearly ordered set of boundary vertices, this gets the next one*/
    
    public static int getNext(EnhancedPolygon E,int[] vtx,int[] tri,int a,int b) {
		for(int i=0;i<vtx.length;++i) {
		    if(boundaryAdjacent(E,tri,b,vtx[i])==true) {
			if(vtx[i]!=a) return vtx[i];
		    }
		}
	return -1;
    }



    /**This gets the actual geometric piece.  Makes sure that the path is
       positively oriented*/
    
    public static PolygonWrapper boundaryRealization(int[][] piece) {
	int[] k=piece[2];
	if(k==null) return null;
	if(k.length<3) return null;
	Complex[] Z=new Complex[k.length];

	Z[0]=new Complex(0,0);
  	Z[1]=new Complex(1,0);
	for(int i=2;i<k.length;++i) {
	    Complex w1=Complex.minus(Z[i-1],Z[i-2]);
	    Complex w2=Complex.alpha(k[i]-3);
	    Complex w3=Complex.times(w1,w2);
	    Z[i]=Complex.plus(Z[i-1],w3);
	}

	Complex[] H=new Complex[Z.length];
	for(int i=0;i<H.length;++i) {
	    int j=(i-1+H.length)%H.length;
	    H[i]=new Complex(Z[j]);
	}

	PolygonWrapper X=new PolygonWrapper(H.length,H);
	boolean test=X.isPositivelyOriented();
	if(test==false) {
	    for(int i=0;i<X.count;++i) X.z[i]=X.z[i].conjugate();
	}
	return X;
    }




    
    

    /**This routine gets the curvatures of the vertices of the boundary of the piece*/

    public static int[] boundaryGeometry(EnhancedPolygon E,int[][] piece) {
	int[] tri=piece[0];
	int[] vtx=piece[1];
	int[] list=new int[vtx.length];
	for(int i=0;i<vtx.length;++i) {
	    if(vtx[i]==-1) return null;
      	    int[] f=E.flower[vtx[i]];
	    int[] g=ListHelp.intersection(f,tri);
	    list[i]=g.length;
	}
	return list;
    }

    /**This gets the number of edges of the piece*/
    public static int edgeNumber(EnhancedPolygon E,int[][] piece) {
	int count=0;
	int[] t=boundaryGeometry(E,piece);
	if(t==null) return 0;
 	for(int i=0;i<t.length;++i) {
	    if(t[i]!=3) ++count;
	}
	return count;
    }


    /**this routine gets the triangles in the piece adjecent to a vertex*/

    public static int[] incidentTriangles(EnhancedPolygon E,int[][] piece,int index) {
	int vtx=piece[1][index];
	int[] f=E.flower[vtx];
	f=ListHelp.intersection(f,piece[0]);
	return f;
    }

}

