var origDict = new Array(); //original dictionary
var orderedDict = new TAFFY([{word:"a",
                            ordWord:"a",
                            wLen:1}]);

var dictLengthIndexes = new Array();

//Search globals.
var findStack = new Array();
var longest=3;
var isDebugOn=false;

function UpdateDiv(div,msg){
    var collect = document.getElementsByName(div.valueOf());
    var cell = collect.item(0);
    if(cell)cell.innerHTML = msg;
}

function LogDiv(div,msg){
    collect = document.getElementsByName(div.valueOf());
    cell = collect.item(0);
    if(cell)cell.innerHTML = cell.innerHTML+msg;
}

function UpdateStatus(msg){
    UpdateDiv("status",msg);
}

function LogStatus(msg){
    LogDiv("status",msg);
}


function UpdateTime(msg){
    UpdateDiv("time_info",Date()+" - "+msg);
}

function LogTime(msg){
    LogDiv("time_info",Date()+" - "+msg);
}


function AlertDictStats(dict){
    LogStatus('There are '+dict.length+' words in this dictionary, and the 150th word is '+dict[149]+"<br>");
}

function LogDictStats(wordLength){
    var foundIndexes = orderedDict.find({wLen:{equal:wordLength}});
    
    if(dictLengthIndexes.length < wordLength){
        //make the raw dictLengthIndexes
        dictLengthIndexes = new Array();
        for (i=0;i<=wordLength;i++){
            dictLengthIndexes.unshift(new Array());    
        }
    }

    //doing extra work here: caching these results since they take so long to produce...
    dictLengthIndexes[wordLength] = foundIndexes; 
    
    foundIndexes.length>0
        ?LogStatus("Ordered Dictionary: Words of Len("+wordLength+") = "+foundIndexes.length+", and the 1st word is "+orderedDict.raw[dictLengthIndexes[wordLength][0]].word+"<br>")
        :LogStatus("Ordered Dictionary: Words of Len("+wordLength+") = "+foundIndexes.length+"<br>");
    if(wordLength>3){
        //async recurse
        next = wordLength-1;
        timeoutId = window.setTimeout("LogDictStats("+next+")",1);
    }else{
        LogTime("Searching for longest add-a-gram<br>");
        timeoutId = window.setTimeout("FindLongest()",750);    
    }
}

function CreateOriginalDictionary(fileContents){
    origDict = fileContents.split("\n");
    AlertDictStats(origDict);
    LogTime("Creating word hashes<br>");
    timeoutId = window.setTimeout("CreateOrderedDictionaries()",1);
}

function WordSort(word){
    //arranges all letter in alphabetical order:  cat -> act  apple -> aelpp
    var letters = new Array();
    var outWord = "";
    
    for(i=0;i<word.length;i++){
        letters.unshift(word.charAt(i));
    }
    letters.sort();
    for(i=0;i<word.length;i++){
        outWord = outWord + letters.shift();
    }
    return outWord.valueOf();
}


function SortOrderedDict(len){
        LogStatus("Sorting by word length...<br>");
//Takes too long... TAFFY DB can't handle it...       orderedDict.orderBy(["wLen"]);
        LogTime("Creating same length dictionaries<br>");
        timeoutId = window.setTimeout("LogDictStats("+len+")",1);
}

function PopulateNextItemInOrderedDictionary(idx,len){
    var newWord;
    var end;
    var lengthIndex;
    var maximum=5000;//max before re-sleeping

    end = Math.min(origDict.length,(idx+maximum));
    
    for(;idx<end;idx++){
        //create new sorted words
        oldWord = origDict[idx];
        orderedWord = WordSort(origDict[idx]);
        orderedDict.insert({word:oldWord,
                            ordWord:orderedWord,
                            wLen:orderedWord.length});
    }
    
    if(idx<origDict.length){
        //recurse Asyncronously
        //Update Status
        var percent = (idx/origDict.length)*100;
        UpdateDiv("pniiod","Working... "+percent+"%"+" ("+len+")");
        //set timer to do the next one
        if(isDebugOn){
            //debug on=true or off=false
            LogStatus("Debug mode, only using 5000 word in the dictionary<br>");
            timeoutId = window.setTimeout("SortOrderedDict("+len+")",1);
        }else{
            timeoutId = window.setTimeout("PopulateNextItemInOrderedDictionary("+idx+","+len+")",10);
        }
    }else{
        UpdateDiv("pniiod","Done<br>");
        
        //Done now sort each ordered array.
        timeoutId = window.setTimeout("SortOrderedDict("+len+")",1);
    }
}


function IsRoot(){
    return (findStack.length==1);
}

function HashMatch(){
    //returns true if this removed letter colides into a hash, or if this is a root node    
    var rtn = false;
    
    if(!IsRoot()){
        //Are there any words at this level
        if(findStack.length<2&&dictLengthIndexes[findStack[0].len].length<1){
            //Nothing Here... return false.
        }else{
            //Not a Root and has word this long, so get the parent word.
            var pWordIdx;
            var pOrdWord; 
        
            pWordIdx = dictLengthIndexes[findStack[1].len][findStack[1].word];
            pOrdWord = orderedDict.raw[pWordIdx].ordWord;
            
            //construct the target Hash from the parent Hash, by removing the current character
            pOrdWord = pOrdWord.replace(findStack[0].character,"");
            
            if(pOrdWord.length==findStack[0].len){
                //Only do it if we replaced a letter... otherwise there's no point.   
                for(i=0; i<dictLengthIndexes[findStack[0].len].length; i++){
                    //check each word at this level
                    var cWordIdx; 
                    var cOrdWord;
                    
                    cWordIdx = dictLengthIndexes[findStack[0].len][i];
                    cOrdWord = orderedDict.raw[cWordIdx].ordWord;
                    
                    if(cOrdWord==pOrdWord){
                        var cWord;
                        var pWord; 
                        
                        cWord = orderedDict.raw[cWordIdx].word;
                        pWord = orderedDict.raw[pWordIdx].word;
                                
                        //Let's comment on out success
                        UpdateDiv(GetLenDivName(findStack[0].len+1),"Match("+findStack[0].len+"): "+cWord+" + "+findStack[0].character+" = "+pWord+"<br>");
                        LogDiv(GetLenDivName(findStack[0].len+1),"<span id=len_"+findStack[0].len+" name=len_"+findStack[0].len+"></span>");

                        if(isDebugOn)LogStatus("<br>Match("+findStack[0].len+"): "+cWord+" + "+findStack[0].character+" = "+pWord);
                        
                        //Save this value
                        findStack[0].word = i;
                        
                        //quit
                        rtn=true;
                        break;
                    }
                }
            }
        }
    }else{
        //a root
        rtn = true;   
    }
    
    return rtn;
}

function GetLenDivName(len){
    return "len_"+len;
}

function NewNode(newLen,newCharacter){
    findStack.unshift({len:newLen,    //current word length
                    character:newCharacter,  //letter removed to get here
                    word:0,     //current word index
                    letter:0}); //removed letter index
}

function NewRoot(root){
    var newCharacter = "";
    findStack = new Array();
    findStack.unshift({len:root,    //current word length
                    character:newCharacter,  //letter removed to get here
                    word:0,     //current word index
                    letter:0}); //removed letter index
                    
    //Status Log:
    UpdateDiv("aag","Starting New Root: "+root+" - <span id=per_"+root+" name=per_"+root+"></span><br><span id=len_"+root+" name=len_"+root+"></span><br>");
}

function DoFindLongest(){
    if(HashMatch()){//most time spent in the HashMatch()
        //Are we done?
        if(findStack[0].len<=3){
            //Found it!!!
            //TODO: report
            LogTime("Done!<br>");
            LogStatus("<p><h1>We are Done!</h1>");            
            //End it All!!!
            return;    
        }

        while(findStack[0].word < dictLengthIndexes[findStack[0].len].length){
            //cycle through all the words...
    
            var cWordIdx = dictLengthIndexes[findStack[0].len][findStack[0].word];
            var cWord = orderedDict.raw[cWordIdx].word;
            var cOrdWord = orderedDict.raw[cWordIdx].ordWord;
    
            if(IsRoot()){
                //Update the percent Field
                var percent;
                percent = 100*findStack[0].word/dictLengthIndexes[findStack[0].len].length;
                UpdateDiv("per_"+findStack[0].len,percent+"%");
            }
    
            while(findStack[0].letter < cWord.length){
                //cycle through all the letters in this word...
                
                //Setup a new stack entry
                //Push
                var newLen; 
                var newCharacter;

                newLen = findStack[0].len-1;
                newCharacter = cOrdWord.charAt(findStack[0].letter);
                
                NewNode(newLen,newCharacter);
                
                //do we need to advance after pushing a new value onto the stack? yes, to the next letter
                findStack[1].letter++;

                //async-recurse
                timeoutId = window.setTimeout("DoFindLongest()",1);
                return;//die: we never loop in this while(letter) but it is here to provide subtext into our intentions.
            }

            if(IsRoot()){
                //only advance to the next word if this is a root 
                findStack[0].word++;
                findStack[0].letter=0;
            }else{
                //  else POP (do we delete this non-root node? -> no add-a-grams from this point down, so I think we should)
                //remove it...
                dictLengthIndexes[findStack[0].len].splice(findStack[0].word,1);

                //POP
                findStack.shift();
            }

            //async-recurse
            timeoutId = window.setTimeout("DoFindLongest()",1);
            return;//die: we never loop in this while(word) but it is here to provide subtext into our intentions.
        }


        //Oh shit, now what?  how did we get here? ANSWER: all vords in this root have been tried, and failed.
        NewRoot(findStack[0].len-1); //go to a new smaller root

    }else{
        //Pop    
        findStack.shift();
    }


    //async-recurse
    timeoutId = window.setTimeout("DoFindLongest()",1);
    return;//die as always
    
}


function FindLongest(){
    UpdateStatus("Starting a new add-a-gram search...<br><span id=aag name=aag></span>");
    //setup state
    NewRoot(longest);    //async recurse...
    timeoutId = window.setTimeout("DoFindLongest()",10);
}

function CreateOrderedDictionaries(){
    var longWordLength=0;
    var longWord='';
    
    //Init    
    orderedDict = new Array();            
    
    //longest word?
    for(i=0;i<origDict.length;i++){
        if(longWordLength<origDict[i].length){
            longest=longWordLength=origDict[i].length;
            longWord=origDict[i];
            
        }
    }
    LogStatus("Longest word is "+longWord+", "+longWordLength+"<br>");
    
    //Create OrderedWord DB
    orderedDict = new TAFFY([{word:"a",
                            ordWord:"a",
                            wLen:1}]);
    
    //Start the async recursion
    LogStatus("<br><div id=pniiod name=pniiod></div>");
    timeoutId = window.setTimeout("PopulateNextItemInOrderedDictionary(0,"+longWordLength+")",1);

}




function Initialize(){
    UpdateTime("Started<br>");
    AjaxDoWith(CreateOriginalDictionary,"http://addagram.mytestbench.com/WORD.LST");
}


//////////////////////////////////////////
// AJAX Helper Functions
var xmlHttp;

function GetXmlHttpObject(){
    var xmlHttp=null;
    try{
        // Firefox, Opera 8.0+, Safari
        xmlHttp=new XMLHttpRequest();
    }catch (e){
        // Internet Explorer
        try{
            xmlHttp=new ActiveXObject("Msxml2.XMLHTTP");
        }catch (e){
            xmlHttp=new ActiveXObject("Microsoft.XMLHTTP");
        }
    }
    return xmlHttp;
}

function AjaxDoWith(func,url){
    //Calls the "func" with whatever is at the endpoint "url"
    xmlHttp=GetXmlHttpObject();
    if (xmlHttp==null){
        return;
    } 
    
    //custom lambda function to handle this request
    xmlHttp.onreadystatechange= function () {
        if (xmlHttp.readyState == 4) {
            func(xmlHttp.responseText);
        }else{
//                alert('xmlHttp.readyState = '+xmlHttp.readyState);
        }
    }
    xmlHttp.open("GET",url,true);
    xmlHttp.send(null);
}


function Asserts(){
    var sampleIdx = 149;
    var sampleWord = "aberrance";
    var sampleFail = "zz99zz";
    
    UpdateStatus("Checking Assertions...<br>");
    
    if(origDict.length>100){
    
        //Which to Use?
        LogStatus("Which to Use: indexOf() / match() / search()? <br>");
            //indexOf()
            if(origDict[sampleIdx].indexOf(sampleWord)>=0){
                LogStatus("<li>indexOf() - passes<br>");
            }else{
                LogStatus("<li>indexOf() - fails<br>");
            }
            if(origDict[sampleIdx].indexOf(sampleFail)>=0){
                LogStatus("<li>indexOf() - fails<br>");
            }else{
                LogStatus("<li>indexOf() - passes<br>");
            }
            //match()
            if(origDict[sampleIdx].match(sampleWord)!=null){
                LogStatus("<li>match() - passes<br>");
            }else{
                LogStatus("<li>match() - fails<br>");
            }
            if(origDict[sampleIdx].match(sampleWord)==null){
                LogStatus("<li>match() - fails<br>");
            }else{
                LogStatus("<li>match() - passes<br>");
            }
            //search()
            if(origDict[sampleIdx].search(sampleWord)>=0){
                LogStatus("<li>search() - passes<br>");
            }else{
                LogStatus("<li>search() - fails<br>");
            }
            if(origDict[sampleIdx].search(sampleFail)>=0){
                LogStatus("<li>search() - fails<br>");
            }else{
                LogStatus("<li>search() - passes<br>");
            }
        
        //Does our word Hash Work?
        var testWord1="march";       
        var testWord2="charm";       
        var testWord3="harks";       
        var testWord4="charms";       
        var testHash1=WordSort(testWord1);
        var testHash2=WordSort(testWord2);
        
        testHash1.indexOf(testHash2)>=0
            ?LogStatus("Hash Test 1: PASSED<br>")
            :LogStatus("Hash Test 1: <b>FAILED</b><br>");
        
        testHash2.indexOf(testHash1)>=0
            ?LogStatus("Hash Test 2: PASSED<br>")
            :LogStatus("Hash Test 2: <b>FAILED</b><br>");
        
        testHash1.indexOf(WordSort(testWord2))>=0
            ?LogStatus("Hash Test 3: PASSED<br>")
            :LogStatus("Hash Test 3: <b>FAILED</b><br>");
        
        testHash2.indexOf(WordSort(testWord1))>=0
            ?LogStatus("Hash Test 4: PASSED<br>")
            :LogStatus("Hash Test 4: <b>FAILED</b><br>");
        
        testHash1.length==testHash2.length && testHash1.length==testWord1.length && testHash2.length==testWord1.length && testHash2.length==testWord2.length
            ?LogStatus("Hash Test 5: PASSED<br>")
            :LogStatus("Hash Test 5: <b>FAILED</b><br>");

        testHash2.indexOf(WordSort(testWord3))>=0
            ?LogStatus("Hash Test 6: <b>FAILED</b><br>")
            :LogStatus("Hash Test 6: PASSED  >>> Intentional Failure Test >>> "+testHash2+"!="+WordSort(testWord3)+"<br>");

        testHash2==testHash1
            ?LogStatus("Hash Test 7: PASSED<br>")
            :LogStatus("Hash Test 7: <b>FAILED</b> Possibly Okay, using == on strings was not likely to work... now we know.<br>");

        testHash2==WordSort(testWord1)
            ?LogStatus("Hash Test 8: PASSED<br>")
            :LogStatus("Hash Test 8: <b>FAILED</b> Possibly Okay, using == on strings was not likely to work... now we know.<br>");
 
 
         testHash1==WordSort(testWord3)
            ?LogStatus("Hash Test 9: <b>FAILED</b><br>")
            :LogStatus("Hash Test 9: PASSED  >>> Intentional Failure Test >>> "+testHash2+"!="+WordSort(testWord3)+"<br>");
 
 
        //pOrdWord = pOrdWord.replace(findStack[0].letter,"");
        //Test the replace function
        WordSort(testWord4).replace("s","")==WordSort(testWord1)
            ?LogStatus("<br>Replace Test 1: PASSED<br>")
            :LogStatus("Replace Test 1: <b>FAILED</b><br>");

        WordSort(testWord4).replace("s","")==WordSort(testWord2)
            ?LogStatus("Replace Test 2: PASSED<br>")
            :LogStatus("Replace Test 2: <b>FAILED</b><br>");

        WordSort(testWord4).replace("m","")==WordSort(testWord2)
            ?LogStatus("Replace Test 3: <b>FAILED</b><br>")
            :LogStatus("Replace Test 3: PASSED  >>> Intentional Failure Test >>> "+WordSort(testWord4).replace("m","")+"!="+WordSort(testWord2)+"<br>");
       
    }else{
        LogStatus("Error: we can't test basic assertions without a data dictionary.  Please initialize first.<br>");
    }
}

function ToggleDebug(){
    isDebugOn = isDebugOn ? false : true ;
    UpdateStatus("DEBUG is "+isDebugOn+"<br>");
}



/*******************************************************************************
This worked but it only removed about 5% of the dictionary... hardly worth the time and effort
*/
function StripDupHashInOrderedDictionary(len,current){
    var next=current+1;
    var end=Math.min(current+10,dictLengthIndexes[len].length);
    
    if(dictLengthIndexes[len].length>0&&dictLengthIndexes[len].length>next){
        for(;current<end;current++){
            var cHash = orderedDict.raw[dictLengthIndexes[len][current]].ordWord;
            //output stats Header
            if(current==0)LogStatus("Pruning Ordered Dictionary: Words of Len("+len+") = "+dictLengthIndexes[len].length+", <span name=prune_"+len+" id=prune_"+len+" ></span>");
            
            //remove duplicate hashes
            for(i=current+1;i<dictLengthIndexes[len].length;i++){
                var nHash = orderedDict.raw[dictLengthIndexes[len][i]].ordWord;
                if(cHash==nHash){
                    //found it, remove it
                    dictLengthIndexes[len].splice(i,1);
                    end--; //reduce the end point too.
                }
            }
        }

        if(dictLengthIndexes[len].length>current){
            var percent = (current*100/dictLengthIndexes[len].length);
            UpdateDiv("prune_"+len,percent+" %");

            //recurse from here    
            timeoutId = window.setTimeout("StripDupHashInOrderedDictionary("+len+","+current+")",1);
            return;
    
        }
    }

    //Clear percent count...
    UpdateDiv("prune_"+len," now reduced to ");

    //output stats footer
    dictLengthIndexes[len].length>1
        ?LogStatus(dictLengthIndexes[len].length+"<br>")
        :LogStatus("");

    //Go again?
    len--;
    if(len>=3){
        //output stats footer
        timeoutId = window.setTimeout("StripDupHashInOrderedDictionary("+len+",0)",1);
    }
}



function PruneOrderedDictionaries(){
    var longWordLength=0;
    var longWord='';
        
    //longest word?
    for(i=0;i<origDict.length;i++){
        if(longWordLength<origDict[i].length){
            longest=longWordLength=origDict[i].length;
            longWord=origDict[i];
            
        }
    }
    //Start the async recursion
    if(confirm("This will reduce about 10,000 duplicate hashes.  But it will take about 3 hours!  Not really worth it.  Click OK to prune the Ordered Dictionary or cancel to avoid it.")){
        UpdateStatus("Stripping Dupplicate Hash Values...<br>");
        timeoutId = window.setTimeout("StripDupHashInOrderedDictionary("+longWordLength+",0)",1);
    }
}