/*
 * LoopWord.java
 *
 * Created on October 27, 2005, 2:43 PM
 */

package Current.plot.BilliardLike;

import java.util.*;
import java.awt.Color;
import java.awt.geom.GeneralPath;

import Current.basic.*;

/**
 *
 * @author  pat
 */
public class LoopWord {
    public class Edge {
        int i; // index
        boolean dir; // true-> forward direction
        
        public Edge(int I, boolean DIR){
            i=I;
            dir=DIR;
        }
        
        public Edge(Edge e){
            i=e.i;
            dir=e.dir;
        }
        
        public boolean equals(Edge e){
            return ((i==e.i)&&(dir==e.dir));
        }
        
        public boolean equals(Object e){
            return equals((Edge) e);
        }
        
        public int eval(){
            return x[i];
        }
        
        public int evalNext(){
            if (dir)
                return x[(i+1)%x.length];
            else
                return x[(i+x.length-1)%x.length];
        }
        
        public int evalPrev(){
            if (dir)
                return x[(i+x.length-1)%x.length];
            else
                return x[(i+1)%x.length];
        }
        
        public void inc(){
            if (dir){
                i=(i+1)%x.length;
            } else {
                i=(i+x.length-1)%x.length;
            }
        }
        
        public void dec(){
            if (dir){
                i=(i+x.length-1)%x.length;
            } else {
                i=(i+1)%x.length;
            }
        }
        
        public Edge incCopy(){
            if (dir)
                return new Edge((i+1)%x.length,dir);
            return new Edge((i+x.length-1)%x.length,dir);
        }
        
        public Edge decCopy(){
            if (dir)
                return new Edge((i+x.length-1)%x.length,dir);
            return new Edge((i+1)%x.length,dir);
        }
        
        public boolean leftOf(Edge E){
            if (dir^(i%2==1)) {  // xor
                return (eval()==(E.eval()+2)%3);
            } else {
                return (eval()==(E.eval()+1)%3);
            }
        }
        
        public boolean rightOf(Edge E){
            if (dir^(i%2==1)) {  // xor
                return (eval()==(E.eval()+1)%3);
            } else {
                return (eval()==(E.eval()+2)%3);
            }
        }
        
        public void print(){
            System.out.print(""+i+(dir?"T":"F"));
        }
        
        public String toString(){
            return ""+i+(dir?"T":"F");
        }
    }
    
    public class LeftOfOrder implements Comparator {
        
        /** Return -1 if E is to the left of E1.
         * Return 1 if E1 is to the left of E. Return 0 if they are equal
         */
        public int compare(Edge E, Edge E1) {
            if (E.equals(E1))
                return 0;
            Edge e=new Edge(E);
            Edge e1=new Edge(E1);
            while (e.eval()==e1.eval()){
                e.inc();
                e1.inc();
            }
            if (e.leftOf(e1))
                return -1;
            else
                return 1;
        }
        
        
        public int compare(Object obj, Object obj1) {
            return compare((Edge)obj,(Edge)obj1);
        }
        
    }
    
    protected class VertexNames{
        int[] rs, ls;
        int lmax,rmax;
        
        public int get(int a, int b) {
            if (a==0)
                return ls[b];
            else
                return rs[b];
        }
        
        public VertexNames(){
            rs=new int[x.length];
            ls=new int[x.length];
            
            rs[0]=1;
            ls[0]=1;
            for (int i=1; i<x.length; i++){
                if (i%2==0){
                    if (x[i]==(x[i-1]+1)%3) {
                        // edge added on left, vertex appears on right side
                        rs[i]=rs[i-1]+1;
                        ls[i]=ls[i-1];
                    } else {
                        // edge added on right, vertex appears on left side
                        ls[i]=ls[i-1]+1;
                        rs[i]=rs[i-1];
                    }
                } else {
                    if (x[i]==(x[i-1]+1)%3) {
                        // edge added on right, vertex appears on left side
                        ls[i]=ls[i-1]+1;
                        rs[i]=rs[i-1];
                    } else {
                        // edge added on left, vertex appears on right side
                        rs[i]=rs[i-1]+1;
                        ls[i]=ls[i-1];
                    }
                }
            }
            lmax=ls[x.length-1];
            rmax=rs[x.length-1];
            
            if (x[0]==(x[x.length-1]+1)%3) {
                // copy of first edge added on left
                int i=x.length-1;
                while (ls[i]==lmax){
                    ls[i]=1;
                    i--;
                }
                lmax--;
            } else {
                // copy of first edge added on right
                int i=x.length-1;
                while (rs[i]==rmax){
                    rs[i]=1;
                    i--;
                }
                rmax--;
            }
            //            for (int i=0; i<ls.length;i++)
            //                System.out.print(""+ls[i]+" ");
            //            System.out.println("--lmax="+lmax);
            //            for (int i=0; i<rs.length;i++)
            //                System.out.print(""+rs[i]+" ");
            //            System.out.println("--rmax="+rmax);
        }
    }
    
    final private int[] x;
    
    /** Creates a new instance of LoopWord */
    public LoopWord(String str) {
        x=new int[str.length()];
        for (int i=0; i<x.length; i++){
            x[i]=(int)(str.charAt(i)-'1');
        }
    }
    
    public int get(int index){
        return x[index%x.length];
    }
    
    public int length(){
        return x.length;
    }
    
    public HolonomyPosition[] createHolonomy(){
        HolonomyPosition[] hol=new HolonomyPosition[x.length];
        hol[0]=new HolonomyPosition(x[0]);
        for (int i=1; i<hol.length; i++){
            hol[i]=new HolonomyPosition(hol[i-1]);
            hol[i].shift(x[i]);
        }
        return hol;
    }
    
    protected TreeSet[][] createLeftOf(){
        TreeSet[][] leftOf=new TreeSet[2][3];
        LeftOfOrder order=new LeftOfOrder();
        for (int a=0; a<2; a++){
            for (int b=0; b<3; b++){
                leftOf[a][b]=new TreeSet(order);
            }
        }
        for (int i=0; i<x.length; i++){
            leftOf[i%2][x[i]].add(new Edge(i, true));
            leftOf[(i+1)%2][x[i]].add(new Edge(i, false));
        }
        return leftOf;
    }
    
    protected static void printLeftOf(TreeSet[][] leftOf){
        for (int a=0; a<2; a++){
            for (int b=0; b<3; b++){
                System.out.println("ordering for leftOf["+a+"]["+b+"]:");
                for (Iterator it=leftOf[a][b].iterator();
                it.hasNext();){
                    ((Edge)it.next()).print();
                    System.out.print(" ");
                }
                System.out.println();
            }
        }
    }
    
    public static Complex[] BlikeVertices(String word) {
        relevantVertices(word);
        LoopWord w=new LoopWord(word);
        HolonomyPosition[] hol=w.createHolonomy();
        TreeSet[][] leftOf=w.createLeftOf();
        PatConvexHull pch=w.computeTile(hol,leftOf);
        if (pch==null) 
            return null;
        return w.computeTile(hol,leftOf).toComplex();
    }
    
//    /** This is the (Conjectural) Billiard Like tile for the word W */
//    public static SpaceTile BlikeTile(String word, Color c) {
//        LoopWord w=new LoopWord(word);
//        HolonomyPosition[] hol=w.createHolonomy();
//        TreeSet[][] leftOf=w.createLeftOf();
//        PatConvexHull ch=w.computeTile(hol,leftOf);
//        
//        //SubwordProfile sp=new SubwordProfile(word);
//        //sp.printDebug(20);
//        
//        if (ch!=null)
//            return new SpaceTile(word,ch.toGeneralPath(),c);
//        else
//            return null;
//    }
    
    /** Return a linked list of bounds */
    protected LinkedList computeBoundryLines(HolonomyPosition[] hol, TreeSet[][] leftOf){
        LinkedList L=new LinkedList();
        Edge e1,e2;
        HolonomyPosition hp1,hp2;
        Iterator it1,it2;
        for (int a=0; a<2; a++){
            for (int b=0; b<3; b++){
                for (it1=leftOf[a][b].iterator();it1.hasNext();){
                    e2=(Edge)it1.next();
                    e1=null;
                    for (it2=leftOf[a][b].iterator();(e1=(Edge)it2.next())!=e2;){
                        hp1=hol[e1.i];
                        hp2=hol[e2.i];
                        
                        if (e1.decCopy().rightOf(e2.decCopy())) {
                            // we have an essential intersection
                            
                            // angle difference>0
                            L.add(new RationalLine(
                                hp2.p[0]-hp1.p[0],
                                hp2.p[1]-hp1.p[1],
                                hp2.p[2]-hp1.p[2]));
                           
                            // angle difference<pi
                            L.add(new RationalLine(
                                1-(hp2.p[0]-hp1.p[0]),
                                1-(hp2.p[1]-hp1.p[1]),
                                1-(hp2.p[2]-hp1.p[2])));
                        }
                    }
                }
            }
        }
        return L;
    }

        /** Return a linked list of bounds */
    protected LinkedList computeAllLines(HolonomyPosition[] hol, TreeSet[][] leftOf){
        LinkedList L=new LinkedList();
        Edge e1,e2;
        HolonomyPosition hp1,hp2;
        Iterator it1,it2;
        int x,y,z;
        for (int a=0; a<2; a++){
            for (int b=0; b<3; b++){
                for (it1=leftOf[a][b].iterator();it1.hasNext();){
                    e2=(Edge)it1.next();
                    e1=null;
                    for (it2=leftOf[a][b].iterator();(e1=(Edge)it2.next())!=e2;){
                        hp1=hol[e1.i];
                        hp2=hol[e2.i];
                        
                        if (e1.decCopy().rightOf(e2.decCopy())) {
                            // we have an essential intersection
                            x=hp2.p[0]-hp1.p[0];
                            y=hp2.p[1]-hp1.p[1];
                            z=hp2.p[2]-hp1.p[2];
                            
                            L.add(new RationalLine(x,y,z));
                            L.add(new RationalLine(x-1,y-1,z-1));
                            int k=-2;
                            RationalLine l=new RationalLine(x+k,y+k,z+k);
                            while (l.isBoundaryValid()) {
                                L.add(l);
                                k--;
                                l=new RationalLine(x+k,y+k,z+k);
                            } 
                            k=1;
                            l=new RationalLine(x+k,y+k,z+k);
                            while (l.isBoundaryValid()) {
                                L.add(l);
                                k++;
                                l=new RationalLine(x+k,y+k,z+k);
                            } 
                        }
                    }
                }
            }
        }
        return L;
    }
    
    public static LinkedList boundaryLines (String word) {
        relevantVertices(word);
        LoopWord w=new LoopWord(word);
        HolonomyPosition[] hol=w.createHolonomy();
        TreeSet[][] leftOf=w.createLeftOf();
        return w.computeBoundryLines(hol,leftOf);
        //w.computeTile(hol,leftOf).toComplex();
    }
    
    public static LinkedList allLines (String word) {
        relevantVertices(word);
        LoopWord w=new LoopWord(word);
        HolonomyPosition[] hol=w.createHolonomy();
        TreeSet[][] leftOf=w.createLeftOf();
        return w.computeAllLines(hol,leftOf);
        //w.computeTile(hol,leftOf).toComplex();
    }
    
    protected PatConvexHull computeTile(HolonomyPosition[] hol, TreeSet[][] leftOf){
        PatConvexHull ch=new PatConvexHull();
        Edge e1,e2;
        HolonomyPosition hp1,hp2;
        Iterator it1,it2;
        for (int a=0; a<2; a++){
            for (int b=0; b<3; b++){
                for (it1=leftOf[a][b].iterator();it1.hasNext();){
                    e2=(Edge)it1.next();
                    e1=null;
                    for (it2=leftOf[a][b].iterator();(e1=(Edge)it2.next())!=e2;){
                        hp1=hol[e1.i];
                        hp2=hol[e2.i];
                        
                        if (e1.decCopy().rightOf(e2.decCopy())) {
                            // we have an essential intersection
                            
                            // angle difference>0
                            if (!ch.add(
                            hp2.p[0]-hp1.p[0],
                            hp2.p[1]-hp1.p[1],
                            hp2.p[2]-hp1.p[2]))
                                return null;
                            
                            // angle difference<pi
                            if (! ch.add(
                            1-(hp2.p[0]-hp1.p[0]),
                            1-(hp2.p[1]-hp1.p[1]),
                            1-(hp2.p[2]-hp1.p[2])))
                                return null;
                        }
                        //                         else {
                        //                        //System.out.println("Comparing: "+hp1+" and "+hp2);
                        //                        //if ((hp1.hexEquals(hp2))) {
                        //                        //if ((hp1.hexEquals(hp2))&&(e1.dir!=e2.dir)) {
                        //                            //System.out.println("Comparing: "+hp1+" and "+hp2);
                        //                            // angle difference>-pi
                        //                            ch.add(
                        //                            1+(hp2.p[0]-hp1.p[0]),
                        //                            1+(hp2.p[1]-hp1.p[1]),
                        //                            1+(hp2.p[2]-hp1.p[2]));
                        //
                        //                            // angle difference<pi
                        //                            ch.add(
                        //                            1-(hp2.p[0]-hp1.p[0]),
                        //                            1-(hp2.p[1]-hp1.p[1]),
                        //                            1-(hp2.p[2]-hp1.p[2]));
                        //
                        //                        }
                    }
                }
            }
        }
        //eliminateIrrelevant(leftOf);
        return ch;
    }
    
    protected boolean[][] eliminateIrrelevant(TreeSet[][] leftOf){
        VertexNames v=new VertexNames();
        boolean[][] relevant=new boolean[2][];
        relevant[0]=new boolean[v.lmax+1];
        relevant[1]=new boolean[v.rmax+1];
        for (int a=0; a<2; a++)
            for (int b=1; b<relevant[a].length; b++)
                relevant[a][b]=true;
        
        Edge e1,e2;
        Iterator it1,it2;
        for (int a=0; a<2; a++){
            for (int b=0; b<3; b++){
                for (it1=leftOf[a][b].iterator();it1.hasNext();){
                    e2=(Edge)it1.next();
                    e1=null;
                    for (it2=leftOf[a][b].iterator();(e1=(Edge)it2.next())!=e2;){
                        //hp1=hol[e1.i];
                        //hp2=hol[e2.i];
                        
                        if (e1.decCopy().leftOf(e2.decCopy())) {
                            // the two arcs never intersect and
                            // avoid a topological saddle connection
                            Edge a1=new Edge(e1),a2=new Edge(e2);
                            // a1 is the leftmost arc and a2 is the right
                            while (a1.eval()==a2.eval()) {
                                if (a1.dir)
                                    relevant[1][v.rs[a1.i]]=false;
                                else
                                    relevant[0][v.ls[a1.i]]=false;
                                if (a2.dir)
                                    relevant[0][v.ls[a2.i]]=false;
                                else
                                    relevant[1][v.rs[a2.i]]=false;
                                a1.inc();
                                a2.inc();
                            }
                        }
                    }
                }
            }
        }
//        // print debugging info
//        int count=0;
//        for (int a=0; a<2; a++)
//            for (int b=1; b<relevant[a].length; b++)
//                if (relevant[a][b]){
//                    count++;
//                    System.out.print("("+a+", "+b+") ");
//                }
//        System.out.println();
//        System.out.println(""+count+" out of "+x.length+" vertices remain relevant.");
       return relevant;
    }
    
    public static int[][] relevantVertices(String word){
        LoopWord w=new LoopWord(word);
        HolonomyPosition[] hol=w.createHolonomy();
        TreeSet[][] leftOf=w.createLeftOf();
        boolean[][] relevant=w.eliminateIrrelevant(leftOf);
        int[] count=new int[2];
        for (int a=0; a<2; a++){
            for (int b=1; b<relevant[a].length; b++)
                if (relevant[a][b]){
                    count[a]++;
                }
        }
        int[][] ret=new int[2][];
        ret[0]=new int[count[0]];
        ret[1]=new int[count[1]];
        count[0]=count[1]=0;
        for (int a=0; a<2; a++){
            for (int b=1; b<relevant[a].length; b++)
                if (relevant[a][b]){
                    ret[a][count[a]]=b;
                    count[a]++;
                }
        }
//        for (int a=0; a<2; a++){
//            if (a==0)
//                System.out.print("bottom:");
//            else
//                System.out.print("top:");
//            for (int b=0; b<ret[a].length; b++)
//                System.out.print(" "+ret[a][b]);
//            System.out.println();
//        }        
        return ret;
    }
}