package Current.popups.Deg100;

import Current.*;
import Current.basic.*;
import Current.plot.Dyadic.*;
import Current.manage.*;

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

public class Deg100Verifier {
    Manager M;
    //the input data
    int type;          //either local or global
    int select;        //tile number
    Color C;           //color of plot
    Complex Z;         //parameter point - used with local plot
    Complex[] POLY;    //the polygon
    Deg100Polygon DPOLY; //the polygon
    String word;       //the word;
    int exact;         //tells whether or not to do rigorous computations;
    int palindrome;    //decides if the word is a palindrome;
    int EXCEPTION0=0;
    int EXCEPTION1=0;
    int debug;
    
    //some output data; stats on the algorithm
    int max;                             //number of boxes
    int[][] record=new int[2][500];      //record of the tournament
    
    //needed for computing the defining function
    int[][] numerator=new int[3][500];           //numerator
    int[][][] denominator=new int[3][3][500];    //denominators of defining functions
    CombinatorialTriangle[] CT;                  //all the combinatorial info is encoded here
    int[] top;                                   //list of top vertices
    int[] bot;                                   //list of bottom vertices
    int spine;                                   //spine number for defining function
    VertexPair V;                                //indexes current defining function
    
    //lists of dyadic squares
    DyadicSquare[] D=new DyadicSquare[500];
    DyadicSquare[] IN=new DyadicSquare[10000];
    int D_N,IN_N;
    
    //memory
    VertexPair[] VP=new VertexPair[10000];
    
    public Deg100Verifier(Manager M) {
        this.M=M;
        M.addListener(this);
    }
    
    
    public void communicate() {
        Deg100Interface DI=(Deg100Interface)(M.mcbGet(Deg100Interface.class));
        if (DI!=null) {
            this.DPOLY=DI.getDeg100Polygon();
            this.POLY=DI.getPOLY();
            int[] modes=DI.getModes();
            exact=modes[0];
            type=modes[1];
            select=modes[2];
        }
    }
    
    
    public DyadicTile basicPlot(String word) {
        communicate();
        this.word=word;
        this.C=M.getColor();
        this.Z=M.getZ();
        if(DPOLY==null) return(null);
        doReset();
        
        System.out.println("starting "+select);
        double time1=System.currentTimeMillis();
        max=0;
        
        while(D_N>0) processSquare();
        if(IN_N==0) return(null);
        
        //picture is created
        GeneralPath gp=new GeneralPath();
        if (IN_N==0) return(null);
        for(int i=0;i<IN_N;++i) {
            gp.append(IN[i].toGeneralPathSpecial(), false);
        }
        DyadicTile DT=new DyadicTile(word, gp, C);
        
        //algorithm stats are recorded
        DT.depth=max;
        DT.boxes=IN_N;
        double time2=System.currentTimeMillis();
        double time=time2-time1;
        DT.time=(int)(time);
        
        //if its a local plot, the tournament record is recorded
        if(type==2) {
            if(IN_N==0) return(null);
            DT.record=record;
            DT.record_active=1;
            DT.Z=Z;
            DT.Z=IN[0].getCenter();
            DT.dyadic_size=IN[0].k;
        }
        System.out.println("done "+select);
        
        if(type==0) {
            int[] stats=new int[3];
            stats[0]=DT.boxes;
            stats[1]=DT.depth;
            stats[2]=DT.time;
            M.mcbSend(stats);
        }
        return DT;
    }
    
    
    public int[] initPlayers(int q) {
        int[] play=new int[q+1];
        play[0]=q;
        for(int i=1;i<=q;++i) play[i]=i;
        return(play);
    }
    
    
    
    public void doReset() {
        
        /**All the defining have one of three types, and all defining
         * functions of the same type have the same second component,
         * which we call the denominator.  Technically, we take
         * im(PQ_bar) rather than im(P/Q), but the result is the same in terms
         * of the sign of the function.  These first 4 lines compute the
         * combinatorics of the word and then the defining functions.*/
        
        CT=CombinatorialTriangle.unfold(word);
        CT=CombinatorialTriangle.assignTails(CT);
        denominator[0]=Deg100Function.computeDenominator(0,CT);
        denominator[1]=Deg100Function.computeDenominator(1,CT);
        denominator[2]=Deg100Function.computeDenominator(2,CT);
        
        /**this is another bit of combinatorics. Our list of vertices
         * is 1,2,3,4... but on the unfolding these vertices are indexed
         * by the triangle on which they appear. For instance, vertex 7
         * might naturally be the vertex of the 11th triangle. These two
         * lists convert between the two ways of indexing the vertices*/
        
        top=completeList(1,CT);
        bot=completeList(2,CT);
        
        
        /**We initialize the first square on the test list to be the
         * whole parameter -i.e. the unit square.  We initialize the
         * lists of vertices to be everything.  In case the word is a
         * palindrome, it suffices by symmetry to consider the first
         * halves of the lists.  This saves time. */
        
        int[] x={1,1};
        int[] y={1,1};
        D[0]=new DyadicSquare(x,y,0);
        int qq=word.length()/2;
        palindrome=palindromeTest(CT);
        if(palindrome==1) qq=word.length()/4+1;
        D[0].top=initPlayers(qq);
        D[0].bot=initPlayers(qq);
        
        
        /**Here we set the memory for the elimination tournaments. This
         * is only used in the local mode but there is no harm in setting
         * up in general.*/
        
        for(int i=0;i<D[0].top.length;++i) record[0][i]=i;
        for(int i=0;i<D[0].bot.length;++i) record[1][i]=i;
        record[0][0]=D[0].top.length;
        
        /**V names the defining function currently considered. Here we initialize V.*/
        V=new VertexPair();
        
        /**Various quantities are stored during the computation, and VP is the
         * wrapper for the stored quantities.  Here we initialize it. */
        
        VP[0]=new VertexPair(0,0,0,0);
        VP[0].cert=0;
        
        /**set the test list length to 1 and covering list length to 0*/
        D_N=1;
        IN_N=0;
        
        
    }
    
    
    
    /*SOME COMBINATORIAL ROUTINES*/
    
    /**conversion between different indexing systems for vertices*/
    
    public static int[] completeList(int ii,CombinatorialTriangle[] CT) {
        int count,OLD,NEW;
        int[] n=new int[CT[0].c[0]];
        count=0;
        OLD=1;
        
        for(int i=1;i<=CT[0].c[0];++i) {
            NEW=CT[i].c[ii];
            if(NEW>OLD) {
                OLD=NEW;
                ++count;
                n[count]=i-1;
            }
        }
        
        if(2*count<CT[0].c[0]) {
            ++count;
            n[count]=CT[0].c[0];
        }
        
        n[0]=CT[0].c[0]/2;
        return(n);
    }
    
    
    public static int palindromeTest(CombinatorialTriangle[] T) {
        int N=T[0].c[0]+1;
        for(int i=1;i<N;++i) {
            for(int j=0;j<=2;++j) {
                if(T[i].b[j]+T[N-i].b[j]!=0) return(0);
            }
        }
        return(1);
    }
    
    
    public static int spineNumber(VertexPair V,CombinatorialTriangle[] T) {
        int n1=coordsToType(T[V.e1],V.o1);
        int n2=coordsToType(T[V.e2],V.o2);
        if(n1!=n2) return(3-n1-n2);
        if(n1==2) return(1);
        return(2);
    }
    
    public static int coordsToType(CombinatorialTriangle T,int m0) {
        return((3+T.c[0]+T.parity*(2*m0-3))%3);
    }
    
    
    
    public static int[] absSecond(VertexPair V,CombinatorialTriangle[] CT,int[][] d) {
        int[] a=new int[3];
        int[][] numerator=Deg100Function.computeNumerator(V,CT);
        int[][] f=Deg100Function.foil(numerator,d);
        a[0]=Deg100Function.absoluteSecondDerivative(f,2,0);
        a[1]=Deg100Function.absoluteSecondDerivative(f,1,1);
        a[2]=Deg100Function.absoluteSecondDerivative(f,0,2);
        return(a);
    }
    
    
    
    
    /**FUNCTION CREATION AND EVALUATION*/
    
    
    public void computeNumerator() {
        int[][]f=new int[0][0];
        spine=spineNumber(V,CT);
        numerator=Deg100Function.getSignedNumerator(denominator[spine],V,CT);
    }
    
    
    //this routine uses the function certificates computed below.
    public int signEvaluate(int cert) {
        DyadicSquare A=D[D_N-1];
        int test=0;
        if(exact==0) test=Deg100Compute.signEvaluate(numerator,denominator[spine],A,cert);    //NUMERICAL
        if(exact==1) test=Deg100Compute.signEvaluate2(numerator,denominator[spine],A,cert);   //RIGOROUS
        return(test);
    }
    
    
    /**FUNCTION CERTIFICATES:  These routines are designed to certify that
     * a given defining function is quadrantic in a given square.  A function
     * is quadrantic in a region if its gradient lies in a quadrant throughout
     * that region.  The first routine does the computations.  This routine
     * is somewhat costly to compute, and so we store any certificates
     * we do compute, for later use.  The second and third routines manage
     * this storing and looking up of certificates.*/
    
    
    public int certify() {
        DyadicSquare A=D[D_N-1];
        int[] a=lookup3();
        if(a[0]+a[1]+a[2]==0) {
            a=absSecond(V,CT,denominator[spine]);
            ++VP[0].cert;
            VP[VP[0].cert]=new VertexPair(V.o1,V.e1,V.o2,V.e2,a[0],a[1],a[2]); }
        int test=0;
        
        if(exact==0) test=Deg100Compute.certify(numerator,denominator[spine],A,a);           //NUMERICAL
        if(exact==1) test=Deg100Compute.certify2(numerator,denominator[spine],A,a);          //RIGOROUS
        return(test);
    }
    
    
    public int[] lookupCertify(int q) {
        DyadicSquare A=D[D_N-1];
        int[] cert=new int[2];
        cert[0]=0;
        cert[1]=0;
        if(q==1) cert[1]=lookup1();
        if(q==2) cert[1]=lookup2();
        if(cert[1]>0)  cert[0]=cert[1];
        if(cert[1]==0) cert[0]=certify();
        return(cert);
    }
    
    public void recordCertify(int q,int[] cert) {
        DyadicSquare A=D[D_N-1];
        if(q==1) {
            if((cert[1]==0)&&(cert[0]>0)) {      //record certificate for later use
                ++A.V1[0].cert;
                int L=A.V1[0].cert;
                A.V1[L]=new VertexPair(V.o1,V.e1,V.o2,V.e2);
                A.V1[L].cert=cert[0];
            }}
        
        if(q==2) {
            if((cert[1]==0)&&(cert[0]>0)) {      //record certificate for later use
                ++A.V2[0].cert;
                int L=A.V2[0].cert;
                A.V2[L]=new VertexPair(V.o1,V.e1,V.o2,V.e2);
                A.V2[L].cert=cert[0];
            }}
    }
    
    
    
    
    
    
    
    
    
    
    
    /**LOOKING UP STORED INFORMATION*/
    
    
    
    public int compare(VertexPair VV1,VertexPair VV2) {
        if(VV1.o1!=VV2.o1) return(0);
        if(VV1.e1!=VV2.e1) return(0);
        if(VV1.o2!=VV2.o2) return(0);
        if(VV1.e2!=VV2.e2) return(0);
        return(VV2.cert);
    }
    
    public int lookup1() {
        int N=D[D_N-1].V1[0].cert;
        int cert=0;
        for(int i=N;i>=1;--i) {
            cert=compare(V,D[D_N-1].V1[i]);
            if(cert!=0) return(cert);
        }
        return(0);
    }
    
    
    
    public int lookup2() {
        int N=D[D_N-1].V2[0].cert;
        int cert=0;
        for(int i=N;i>=1;--i) {
            cert=compare(V,D[D_N-1].V2[i]);
            if(cert!=0) return(cert);
        }
        return(0);
    }
    
    
    public int[] compare3(VertexPair VV1,VertexPair VV2) {
        int[] a=new int[3];
        a[0]=0;
        a[1]=0;
        a[2]=0;
        int test=1;
        if(VV1.o1!=VV2.o1) test=0;
        if(VV1.e1!=VV2.e1) test=0;
        if(VV1.o2!=VV2.o2) test=0;
        if(VV1.e2!=VV2.e2) test=0;
        if(test==1) {
            a[0]=VV2.a20;
            a[1]=VV2.a11;
            a[2]=VV2.a02;
        }
        return(a);
    }
    
    
    public int[] lookup3() {
        int N=VP[0].cert;
        int[] a=new int[3];
        a[0]=0;
        a[1]=0;
        a[2]=0;
        for(int i=N;i>=1;--i) {
            a=compare3(V,VP[i]);
            if(a[0]!=0) return(a);
        }
        return(a);
    }
    
    public int getMatchNumber() {
        return(D[D_N-1].top[0]*D[D_N-1].bot[0]);
    }
    
    
    
    
    
    
    
    
    
    
    /**HERE IS THE ALGORITHM*/
    
    public void processSquare() {
        DyadicSquare A=D[D_N-1];
        
        
        if(max<A.k) max=A.k;
        int action=determineAction();
        if(action==-1) --D_N;
        if(action==0) refineList();
        if(action==1) addToInsiders();
    }
    
    
    public void refineList() {
        DyadicSquare A=D[D_N-1];
        D[D_N-1]=DyadicSquare.subdivideAndRemember(0,0,A);
        D[D_N+0]=DyadicSquare.subdivideAndRemember(0,1,A);
        D[D_N+1]=DyadicSquare.subdivideAndRemember(1,1,A);
        D[D_N+2]=DyadicSquare.subdivideAndRemember(1,0,A);
        D_N=D_N+3;
    }
    
    
    public void addToInsiders() {
        DyadicSquare A=D[D_N-1];
        IN[IN_N]=new DyadicSquare(A.x,A.y,A.k);
        IN[IN_N].top=new int[300];
        IN[IN_N].bot=new int[300];
        IN[IN_N].top[0]=A.top[0];
        IN[IN_N].bot[0]=A.bot[0];
        
        for(int i=1;i<=A.top[0];++i) {
            IN[IN_N].top[i]=A.top[i];
        }
        
        for(int i=1;i<=A.bot[0];++i) {
            IN[IN_N].bot[i]=A.bot[i];
        }
        
        if(type>=2) {
            Z=A.getCenter(); // set Z
            D_N=0;
        }
        
        ++IN_N;
        --D_N;
    }
    
    
    
    /**When type=2 we have the local mode.  This mode discards any squares which
     * do not contain a specific point, and thereby lets the user trace what
     * the algorithm one box at a time.  The routine to ConvexIntersector is
     * not done with interval arithmetic, and doesn't have to be done with
     * interval arithmetic.  The idea
     * here is just to use the point Z to select a box.*/
    
    public int determineAction() {
        
        
        DyadicSquare A=D[D_N-1];
        if(A.x[0]>A.y[0]) return(-1);  //throws out boxes centered on acute side.
        
        if(type==2) {
            int touch=ConvexIntersector.checkTouch(Z,A.toPolygon());      //NUMERICAL
            if(touch==0) return(-1);
        }
        
        
        /**This is what we use for the vast majority of the calculations.
         * There are only 7 exceptions below. We can't use the rigorous
         * intersector on the 7 exceptions because they have rational but
         * non-dyadic rational vertices. */
        
        int test=0;
        if(select<=221) {
            if(exact==1)  test=Deg100IntegerPolygon.checkDisjoint(A,DPOLY);    //RIGOROUS
            if(exact==0)  test=ConvexIntersector.checkDisjoint(A,POLY);        //NUMERICAL
        }
        
        
        /**We only invoke this numerical method for the 7 exceptional tiles
         * P222,...,P228.  In each of these cases, the final output is a
         * just a few squares and we visually inspect that it covers
         * the tile.  In other words, we overcome any roundoff error just
         * by inspection */
        
        if(select>221) {
            test=ConvexIntersector.checkDisjoint(A,POLY);                     //NUMERICAL
        }
        
        if(test==3) return(-1); //does not intersect
        
        tournament();
        int p=playoffs();
        return(p);
    }
    
    
    
    
    public void tournament() {
        int STOP=1;
        while(STOP!=0) STOP=round(1);
        STOP=1;
        while(STOP!=0) STOP=round(2);
    }
    
    
    public int round(int q) {
        
        int match=0;
        int count=0;
        int previous=0;
        int elim=0;
        int BEFORE=0;
        DyadicSquare A=D[D_N-1];
        
        if(q==1) BEFORE=A.top[0];
        if(q==2) BEFORE=A.bot[0];
        
        for(int i=1;i<BEFORE;++i) {
            
            if(q==1) {
                V.o1=1;V.e1=top[A.top[i+0]];
                V.o2=1;V.e2=top[A.top[i+1]];
            }
            
            if(q==2) {
                V.o1=2;V.e1=bot[A.bot[i+0]];
                V.o2=2;V.e2=bot[A.bot[i+1]];
            }
            
            
            //the match
            elim=0;
            match=0;
            if(previous==2) elim=1;
            if(elim==0) match=ordinaryMatch();
            if(match==1) elim=1;
            //match is done
            
            if((q==1)&&(match==1)) record[0][A.top[i]]=A.top[i+1];
            if((q==2)&&(match==1)) record[1][A.bot[i]]=A.bot[i+1];
            
            if((q==1)&&(previous==2)) record[0][A.top[i]]=A.top[i-1];
            if((q==2)&&(previous==2)) record[1][A.bot[i]]=A.bot[i-1];
            
            if(elim==0) {
                ++count;
                if(q==1) A.top[count]=A.top[i];
                if(q==2) A.bot[count]=A.bot[i];
            }
            
            previous=match;
        }
        
        //*last element*/
        if((q==1)&&(match!=2)) {++count;A.top[count]=A.top[BEFORE];}
        if((q==2)&&(match!=2)) {++count;A.bot[count]=A.bot[BEFORE];}
        
        int tlen=A.top[0];        int blen=A.bot[0];
        if((q==1)&&(match==2)) record[0][A.top[tlen]]=A.top[tlen-1];
        if((q==2)&&(match==2)) record[1][A.bot[blen]]=A.bot[blen-1];
        
        //loop is done
        if(count==0) ++count;
        
        if(q==1) A.top[0]=count;
        if(q==2) A.bot[0]=count;
        return(BEFORE-count);
    }
    
    
    
    public int playoffs() {
        int match=0;
        int fail=0;
        DyadicSquare A=D[D_N-1];
        for(int i=1;i<=A.top[0];++i) {
            for(int j=1;j<=A.bot[0];++j) {
                int ii=A.top[i];
                int jj=A.bot[j];
                V.o1=1;V.e1=top[ii];
                V.o2=2;V.e2=bot[jj];
                computeNumerator();
                EXCEPTION0=ii;
                EXCEPTION1=jj;
                match=playoffMatch();
                if(match==0) return(0);
            }
        }
        return(1);
    }
    
    
    public int ordinaryMatch() {
        computeNumerator();
        int match=0;
        int[] cert=lookupCertify(1);
        recordCertify(1,cert);
        match=signEvaluate(cert[0]);
        if(V.o1*V.o2==1) match=3-match;
        if(match==1) return(1);
        if(match==2) return(2);
        return(0);
    }
    
    public int playoffMatch() {
        int match=0;
        int[] cert=new int[2];
        cert=lookupCertify(2);
        int isException=checkExceptions();              //check exceptions
        if((cert[0]>0)&&(isException==1)) return(3);
        if((select==222)&&(isException==1)) return(3);   //here is tile 222
        match=signEvaluate(cert[0]);
        if(getMatchNumber()<=25) recordCertify(2,cert);  //don't want to overload memory
        return(match);
    }
    
    
    /**Here we check the exceptions. We ignore the pair
     * provided it is on our list of exceptions AND the
     * function for this pair is certified.  There is one
     * special exception, and that is for tile 222.  This
     * tile contains the right angled isosceles point
     * as a vertex.  In a neighborhood of a vertex we cannot
     * certify the defining functions computationally. We
     * have to analyze it analytically. */
    
    
    public int checkExceptions() {
        int exc=0;
        for(int ii=1;ii<=DPOLY.exceptions[0][0];++ii) {
            if((EXCEPTION0==DPOLY.exceptions[ii][0])&&(EXCEPTION1==DPOLY.exceptions[ii][1])) exc=1;
        }
        return(exc);
    }
    
    
    
    
}