package Current.search;

import java.lang.Thread;
import java.util.*;

import Current.basic.*;
import Current.search.basic.*;

public class LeaderSearch extends Thread {
    /** interface with this to interact with the BasicSearch class */
    
    private Complex tri; // coordinates for triangle
    private int depth;
    private Searcher bs;
    private boolean interrupt;
    
    private class SearchData {
        MarkedSlalomUnfolding.DataBackup db;
        //boolean last; // if true then the next edge gets added last.
        int next;
        
        public SearchData(MarkedSlalomUnfolding SU, int NEXT) {
            db=SU.backup();
            //this.last=last;
            next=NEXT;
        }
    }
    
    /** The BasicSearcher is the class that handles the responses */
    public LeaderSearch(double x, double y, int depth, Searcher BS){
        bs=BS;
        this.tri=new Complex(x,y);
        //depth+=2;
        this.depth=depth;
        start();
    }
    
    /** The BasicSearcher is the class that handles the responses */
    public LeaderSearch(Complex tri, int depth, Searcher BS){
        bs=BS;
        this.tri=new Complex(tri);
        //depth+=2;
        this.depth=depth;
        start();
    }
    
    public void interrupt() {
        interrupt=true;
    }
    
    StringWordOrganizer results;
    int d;
    LinkedList w;
    int minlength;
    MarkedSlalomUnfolding su;
    boolean last;
    HexPosition hp;
    LinkedList sd; //search data
    int next,next2,dist,dist2,dist3;
    boolean killed;
        
    protected final int getLast() {
        return ((Integer)(w.getLast())).intValue();
    }
    
    protected final int getFirst() {
        return ((Integer)(w.getFirst())).intValue();
    }
    
    protected void addLastBoth() {
        //System.out.println("adding last both");
        //su.printDebug();
        
        // we need to add both
        // copy to backup
        sd.addLast(new SearchData(su,next2));
        
        if (!su.addLastEdge(next)) {
            //System.out.println("Marked vertex removed");
            su.recover(((SearchData)(sd.removeLast())).db);
            addLast2();
            return;
        }
        hp.shift(next);
        w.addLast(new Integer(next));
        last=!last;
    }
    
    protected void addLast1() {
        //System.out.println("adding last 1, letter="+next+" hull size: "+su.size());
        //su.printDebug();
        
        // we only need to add next
        sd.addLast(null);
        
        if (!su.addLastEdge(next)) {
            //System.out.println("Marked vertex removed");
            sd.removeLast();
            recoil();
            return;
        }
        hp.shift(next);
        w.addLast(new Integer(next));
        last=!last;
    }
    
    protected void addLast2() {
        //System.out.println("adding last 2 letter="+next2+"");
        //su.printDebug();
        // we only need to add next2
        sd.addLast(null);
        if (!su.addLastEdge(next2)) {
            //System.out.println("Marked vertex removed");
            
            sd.removeLast();
            recoil();
            return;
        }
        hp.shift(next2);
        w.addLast(new Integer(next2));
        last=!last;
    }
    
    protected void addFirstBoth() {
        //System.out.println("adding first both");
        //su.printDebug();
        // we need to add both
        // copy to backup
        sd.addFirst(new SearchData(su,next2));
        
        if (!su.addFirstEdge(next)) {
            //System.out.println("Marked vertex removed");
            
            su.recover(((SearchData)(sd.removeFirst())).db);
            addFirst2();
            return;
        }
        hp.shiftback(next);
        w.addFirst(new Integer(next));
        last=!last;
    }
    
    protected void addFirst1() {
        //System.out.println("adding first 1 letter="+next+"");
        //su.printDebug();
        // we only need to add next
        sd.addFirst(null);
        
        if (!su.addFirstEdge(next)) {
            //System.out.println("Marked vertex removed");
            
            sd.removeFirst();
            recoil();
            return;
        }
        hp.shiftback(next);
        w.addFirst(new Integer(next));
        last=!last;
    }
    
    protected void addFirst2() {
        //System.out.println("adding first 2 letter="+next+"");
        // we only need to add next2
        sd.addFirst(null);
        if (!su.addFirstEdge(next2)) {
            //System.out.println("Marked vertex removed");
            
            sd.removeFirst();
            recoil();
            return;
        }
        hp.shiftback(next2);
        w.addFirst(new Integer(next2));
        last=!last;
    }
    
    
    public void recoil() {
        //System.out.println("recoil");
        while (sd.size()>0) {
            last=!last;
            if (last) {
                hp.shift(getLast());
                w.removeLast();
            } else {
                hp.shiftback(getFirst());
                w.removeFirst();
            }
            if (last) {
                SearchData d=(SearchData)(sd.removeLast());
                if (d!=null) {
                    //System.out.print("recoiled to ");
                    //printword();
                    //System.out.println("adding "+d.next+" to last");
                    su.recover(d.db);
                    next=d.next;
                    addLast1();
                    return;
                }
            } else {
                SearchData d=(SearchData)(sd.removeFirst());
                if (d!=null) {
                    //System.out.print("recoiled to ");
                    //printword();
                    //System.out.println("adding "+d.next+" to first");
                    su.recover(d.db);
                    next=d.next;
                    addFirst1();
                    return;
                }
            }
        }
        killed=true;
    }
    
    public void printword() {
        for (ListIterator it=w.listIterator();it.hasNext();) {
            System.out.print(it.next());
        }
        System.out.println();
    }
    
    /** Start the search! */
    public void run(){
        interrupt=false;
        //int languish=0;
        // for storing the results:
        results=new StringWordOrganizer();
        
        // backup the depth (it may change otherwise)
        d=depth;
        
        
        for (int i=0; i<3; i++) {
            boolean left=true;
            for (int k=0; k<2; k++) {
                /** Information used when searching */
                w=new LinkedList();     // array of letters in the word
                
                w.addLast(new Integer(i));
                
                left=!left;
                if (left)
                    w.addLast(new Integer((i+2)%3));
                else
                    w.addLast(new Integer((i+1)%3));
                minlength=2;
                
                hp=new HexPosition(); // current position in hex grid
                if (left) {
                    double ang=Math.IEEEremainder(Math.PI/2,
                    TriangleGeometry.angle(tri, (i+2)%3));
                    if (ang<0) {
                        ang+=TriangleGeometry.angle(tri, (i+2)%3);
                    }
                    
                    
                    su=new MarkedSlalomUnfolding(tri,getFirst(),true,false);
                    su.sh.addToLeftLast(
                    Complex.intersect(su.t1.z[(i+1)%3], su.t1.z[i],
                    su.t1.z[(i+2)%3],
                    su.t1.z[(i+1)%3].minus(su.t1.z[(i+2)%3]).times(Complex.unitGivenArg(ang)).plus(su.t1.z[(i+2)%3])
                    ));
                } else {
                    double ang=Math.IEEEremainder(Math.PI/2,
                    TriangleGeometry.angle(tri, (i+1)%3));
                    if (ang<0) {
                        ang+=TriangleGeometry.angle(tri, (i+1)%3);
                    }
                    ang=-ang;
                    
                    su=new MarkedSlalomUnfolding(tri,getFirst(),false,true);
                    su.sh.addToLeftLast(
                    Complex.intersect(su.t1.z[(i+2)%3], su.t1.z[i],
                    su.t1.z[(i+1)%3],
                    su.t1.z[(i+2)%3].minus(su.t1.z[(i+1)%3]).times(Complex.unitGivenArg(ang)).plus(su.t1.z[(i+1)%3])
                    ));
                }
                { int temp, j=0;
                  for (ListIterator it=w.listIterator();it.hasNext();) {
                      temp=((Integer)(it.next())).intValue();
                      hp.shift(temp);
                      if (j>0) {
                          if (!su.addLastEdge(temp)) {
                              i=5/0;
                          }
                      }
                      j++;
                  }
                }
                
                last=true;
                
                sd=new LinkedList();
                
                killed=false;
                
                //System.out.print("Starting search with word ");
                //printword();
                
                while (!killed){
                    //System.out.print("now: hp="+hp+" and word=");
                    //printword();
                    if (interrupt)
                        return;
                    
                    //           //System.out.println("Statistics: length="+l+" size="+su.size());
                    //            if (l==151)
                    //                //System.out.println("help");
                    if ( ((dist=hp.dist())==0) )
                        if (su.strongTest()) {
                            //System.out.println("passed strong test");
                            StringBuffer temp=new StringBuffer(w.size());
                            for (ListIterator it=w.listIterator();it.hasNext();) {
                                temp.append((char)('1'+((Integer)(it.next())).intValue()));
                            }
                            results.add(temp.toString());
                        } else {
                            //System.out.println("failed strong test");
                        }
                    if (last) {
                        //System.out.println("trying to add last");
                        next=(getLast()+1)%3;
                        next2=(getLast()+2)%3;
                        
                        if (hp.even())
                            if (hp.p[next]>=0)
                                dist2=dist+1;
                            else
                                dist2=dist-1;
                        else
                            if (hp.p[next]<=0)
                                dist2=dist+1;
                            else
                                dist2=dist-1;
                        
                        if (hp.even())
                            if (hp.p[next2]>=0)
                                dist3=dist+1;
                            else
                                dist3=dist-1;
                        else
                            if (hp.p[next2]<=0)
                                dist3=dist+1;
                            else
                                dist3=dist-1;
                        
                        //            if ((next>=w[lexi])&&           // lexi-test
                        //            (!(dist2+l<d))&&               // distance test
                        //            (su.survivesAdd(next)) &&       // slalom test
                        //            (reverseLexiTest(w,l,next))) {   //reverse lexi test
                        //                languish++;
                        //            }
                        if ((dist2+w.size()>=d)) {
                            //System.out.println("failed distance test adding "+next);
                        }
                        if ((!su.survivesAddLast(next))) {
                            //System.out.println("failed slalom test adding "+next);
                        }
                        
                        
                        if ((dist2+w.size()<d)&&               // distance test
                        (su.survivesAddLast(next)) ) {       // slalom test
                            
                            if ((dist3+w.size()>=d)) {
                                //System.out.println("failed distance test adding "+next2);
                            }
                            if ((!su.survivesAddLast(next2))) {
                                //System.out.println("failed slalom test adding "+next2);
                            }
                            
                            if ( (dist3+w.size()<d)&&               // distance test
                            (su.survivesAddLast(next2)) ) {     // slalom test
                                
                                addLastBoth();
                                
                            } else {
                                
                                addLast1();
                            }
                        } else {
                            
                            if ((dist3+w.size()>=d)) {
                                //System.out.println("failed distance test adding "+next2);
                            }
                            if ((!su.survivesAddLast(next2))) {
                                //System.out.println("failed slalom test adding "+next2);
                            }
                            
                            if ( (dist3+w.size()<d)&&            // distance test
                            (su.survivesAddLast(next2)) ) {      // slalom test
                                addLast2();
                            } else {
                                recoil();
                            }
                        }
                    } else {
                        
                        //System.out.println("trying to add first");
                        
                        next=(getFirst()+1)%3;
                        if (hp.p[next]>=1)
                            dist2=dist-1;
                        else
                            dist2=dist+1;
                        
                        if ((dist2+w.size()>=d)) {
                            //System.out.println("failed distance test adding "+next);
                        }
                        if ((!su.survivesAddFirst(next))) {
                            //System.out.println("failed slalom test adding "+next);
                        }
                        
                        if ((dist2+w.size()<d)&&              // distance test
                        (su.survivesAddFirst(next)) ) {       // slalom test
                            
                            next2=(getFirst()+2)%3;
                            if (hp.p[next2]>=1)
                                dist3=dist-1;
                            else
                                dist3=dist+1;
                            
                            if ((dist3+w.size()>=d)) {
                                //System.out.println("failed distance test adding "+next2);
                            }
                            if ((!su.survivesAddFirst(next2))) {
                                //System.out.println("failed slalom test adding "+next2);
                            }
                            
                            if ( (dist3+w.size()<d)&&           // distance test
                            (su.survivesAddFirst(next2)) ) {     // slalom test
                                
                                addFirstBoth();
                                
                            } else {
                                
                                addFirst1();
                            }
                        } else {
                            next2=(getFirst()+2)%3;
                            if (hp.p[next2]>=1)
                                dist3=dist-1;
                            else
                                dist3=dist+1;
                            
                            if ((dist3+w.size()>=d)) {
                                //System.out.println("failed distance test adding "+next2);
                            }
                            if ((!su.survivesAddFirst(next2))) {
                                //System.out.println("failed slalom test adding "+next2);
                            }
                            
                            if ( (dist3+w.size()<d)&&             // distance test
                            (su.survivesAddFirst(next2)) ) {      // slalom test
                                addFirst2();
                            } else {
                                recoil();
                            }
                        }
                    }
                    
                    
                }
            }
        }
        ////System.out.println("Languishing words="+languish);
        bs.doneBasicSearch(new Results(results.toArray(),tri));
    }
}