package Current.search;

import java.lang.Thread;

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

public class BasicSearch 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 {
        SlalomUnfolding.DataBackup db;
        int lexi, next;
        
        public SearchData(SlalomUnfolding SU, int LEXI, int NEXT) {
            db=SU.backup();
            lexi=LEXI;
            next=NEXT;
        }
    }
    
    /** The BasicSearcher is the class that handles the responses */
    public BasicSearch(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 BasicSearch(Complex tri, int depth, Searcher BS){
        bs=BS;
        this.tri=new Complex(tri);
        //depth+=2;
        this.depth=depth;
        start();
    }
        
    /** Return true if the word w (from 0 up to l-1) is less or equal
     * lexigraphically than the word obtained by starting with next and
     * adding letters of w in reverse order (from l-1 down to 0)
     **/
    public static boolean reverseLexiTest(int w[], int l, int next) {
        if (w[0]<next)
            return true;
        if (w[0]>next)
            return false;
        for (int i=1; i<(l+1)/2; i++){
            if (w[i]<w[l-i])
                return true;
            if (w[i]>w[l-i])
                return false;
        }
        return true;
    }
    
    public void interrupt() {
        interrupt=true;
    }
    
    /** Start the search! */
    public void run(){
        interrupt=false;
        //int languish=0;
        // for storing the results:
        StringWordOrganizer results=new StringWordOrganizer();
        
        // backup the depth (it may change otherwise)
        int d=depth;
        
        /** Information used when searching */
        int w[]=new int[d];     // array of letters in the word
        w[0]=0;
        w[1]=1;
        
        int l=2;                  // current word length
        int lexi=0;               // lexi-test data
        HexPosition hp=new HexPosition();           // current position in hex grid
        hp.shift(0);
        hp.shift(1);
        
        SlalomUnfolding su=new SlalomUnfolding(tri,0);
        if (!su.addEdge(1)) {
            l=5/0;
        }
        
        SearchData sd[]=new SearchData[d+1];
        
        int next,next2,dist,dist2,dist3;
        
        while (l>1){
            if (interrupt)
                return;
            
            //           System.out.println("Statistics: length="+l+" size="+su.size());
            //            if (l==151)
            //                System.out.println("help");
            if ( ((dist=hp.dist())==0) &&
            (su.strongTest()) &&
            (lexi<=l/2) &&
            ((lexi<l/2)||(lexi%2==1))) {
                StringBuffer temp=new StringBuffer(l);
                for (int i=0; i<l; i++){
                    temp.append((char)('1'+w[i]));
                }
                results.add(temp.toString());
            }
            next=(w[l-1]+1)%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 ((next>=w[lexi])&&           // lexi-test
            //            (!(dist2+l<d))&&               // distance test
            //            (su.survivesAdd(next)) &&       // slalom test
            //            (reverseLexiTest(w,l,next))) {   //reverse lexi test
            //                languish++;
            //            }
            
            
            if ((next>=w[lexi])&&           // lexi-test
            (dist2+l<d)&&               // distance test
            (su.survivesAdd(next)) &&       // slalom test
            (reverseLexiTest(w,l,next))) {   //reverse lexi test
                next2=(w[l-1]+2)%3;
                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 ((next2>=w[lexi])&&           // lexi-test
                //                (!(dist3+l<d))&&               // distance test
                //                (su.survivesAdd(next2)) &&       // slalom test
                //                (reverseLexiTest(w,l,next2))) {   //reverse lexi test
                //                    languish++;
                //                }
                
                
                if ((next2>=w[lexi])&&           // lexi-test
                (dist3+l<d)&&               // distance test
                (su.survivesAdd(next2)) &&       // slalom test
                (reverseLexiTest(w,l,next2))) {   //reverse lexi test
                    // we need to add both
                    // copy to backup
                    sd[l-1]=new SearchData(su,lexi,next2);
                    
                    // add next
                    if (w[lexi]<next)
                        lexi=0;
                    else
                        lexi++;
                    if (!su.addEdge(next)) {
                        l=5/0;
                    }
                    hp.shift(next);
                    w[l++]=next;
                } else {
                    // we only need to add next
                    if (w[lexi]<next)
                        lexi=0;
                    else
                        lexi++;
                    if (!su.addEdge(next)) {
                        l=5/0;
                    }
                    hp.shift(next);
                    w[l++]=next;
                }
            } else {
                next2=(w[l-1]+2)%3;
                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 ((next2>=w[lexi])&&           // lexi-test
                //                (!(dist3+l<d))&&               // distance test
                //                (su.survivesAdd(next2)) &&       // slalom test
                //                (reverseLexiTest(w,l,next2))) {   //reverse lexi test
                //                    languish++;
                //                }
                
                if ((next2>=w[lexi])&&           // lexi-test
                (dist3+l<d)&&               // distance test
                (su.survivesAdd(next2)) &&       // slalom test
                (reverseLexiTest(w,l,next2))) {   //reverse lexi test
                    // we only need to add next2
                    if (w[lexi]<next2)
                        lexi=0;
                    else
                        lexi++;
                    if (!su.addEdge(next2)) {
                        l=5/0;
                    }
                    hp.shift(next2);
                    w[l++]=next2;
                } else {
                    l=l-1;
                    hp.shift(w[l]);
                    while ((l>1)&&(sd[l-1]==null)){
                        l=l-1;
                        hp.shift(w[l]);
                    }
                    if (l>1) {
                        next=sd[l-1].next;
                        lexi=sd[l-1].lexi;
                        su.recover(sd[l-1].db);
                        sd[l-1]=null;
                        
                        if (w[lexi]<next)
                            lexi=0;
                        else
                            lexi++;
                        if (!su.addEdge(next)) {
                            l=5/0;
                        }
                        hp.shift(next);
                        w[l++]=next;
                    }
                }
            }
        }
        //System.out.println("Languishing words="+languish);
        bs.doneBasicSearch(new Results(results.toArray(),tri));
    }
}