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


public class GraphDiamondImprover {

    /**We know that in the end we should have a triangulation.
       This class uses the knowledge to improve the graph.
       A diamond is a 4-cycle in the graph in which both diagonals
       are missing.  We look for a diamond in a graph and see if we
       can determine which diagonal should be filled in. If we can 
       determine this, we fill the diagonal in and continue.*/
    
    public static void improve(EnhancedPolygon E) {
	int count=0;
	boolean test=false;
	while(test==false) {
	    int[] B=deficit(E);
	    if(B==null) test=true;
	    if(count==30) test=true;
	    improveDiamond(E);
	    ++count;
	}
    }

    /**This routine looks for rhombs (i.e. DIAMONDS) in the graph such that
       the short diagonal is missing.  The short diagonal almost
       certainly should be there, so we improve the graph by adding it.*/

    
    public static void improveDiamond(EnhancedPolygon E) {
	int[] B=deficit(E);
	if(B==null) return;
	int[] A=firstDiamond(E);
	addEdge(E,A);
    }

    
    /**This routine finds the first diamond, assuming there is one*/

    public static int[] firstDiamond(EnhancedPolygon E) {
	int[] B=deficit(E);
	if(B==null) return null;
	int n=B.length;
	for(int i0=0;i0<n;++i0) {
	for(int i1=i0+1;i1<n;++i1) {
	    int[] l0=E.graph[B[i0]];
	    int[] l1=E.graph[B[i1]];
	    int[] l2=ListHelp.intersection(l0,l1);
	    if(l2.length==2) {
		int[] l3=E.graph[l2[0]];
  		boolean test1=GraphAnalyzer.neighbors(E,l2[0],l2[1]);
		boolean test2=GraphAnalyzer.neighbors(E,B[i0],i1);
		if((test1==false)&&(test2==false)) {
		    int[] A={B[i0],B[i1],l2[0],l2[1]};
		    return A;
		}
	    }
	}
	}
	return null;
    }
    

    /**This detects missing incidence relations, based
       on the expected degree sequence*/

    public static int[] deficit(EnhancedPolygon E) {
	int[] list=new int[E.graph.length];
	int count=0;
	for(int i=0;i<E.graph.length;++i) {
	    boolean test=deficit(E,i);
	    if(test==true) {
		list[count]=i;
		++count;
	    }
	}
	if(count==0) return null;
	return ListHelp.trim(list,count);
    }

    
    public static boolean deficit(EnhancedPolygon E,int k) {
	int[] l=E.graph[k];
	int t=E.equiv[k][0];
	int d1=0;
	if(t>=E.count) d1=6;
  	else d1=E.degrees[t];
	int d2=l.length;
	if(d2<d1) return true;
	return false;
    }

    /**This adds an edge to a graph.  This routine also appears in GraphFlowerImprover*/
    
    public static void addEdge(EnhancedPolygon E,int[] A) {
	if(A==null) return;
	int i0=A[0];
	int i1=A[1];
	E.graph[i0]=ListHelp.append(E.graph[i0],i1);
	E.graph[i1]=ListHelp.append(E.graph[i1],i0);
	Arrays.sort(E.graph[i0]);
	Arrays.sort(E.graph[i1]);
    }


}

