/*
 * CYKParser.java
 *
 * Created on 8 december 2005, 9:28
 *
 */

package DOPParser;

/**
 *
 * @author gideon
 */

import java.util.*;

public class CYKParser {
    
    protected int chartDimension    ;
    protected ChartCell[][] myChart;
    protected Grammar myGrammar;
    protected String[] parseSentence;
    //protected ArrayList<Rule> viterbiParse = new ArrayList<Rule>();
    protected  ArrayList<parseTree> parseForest, parseForestCFG;    //parseForest for a single sentence
    protected TreeMap<Double, SearchPath> SearchPathBeam;  //best 1000 or so searchpaths for a single sentence
    protected TreeMap<Double, SearchPath> SearchPathBeamCandidates;  //temporarily stores additional searchpaths in the course of an iteration over the Beam
    
    
    /* nested class ChartCell - n-best version
    * contains a HashSet of NonTerminals, which have pointers, inside and Viterbi probabilities
    */
    public class ChartCell {
        
        public HashMap<String, TreeMap<Double, NonTerminalInChart>> setOfNonTerminalArrays;
        
        public ChartCell(){
            this.setOfNonTerminalArrays = new HashMap<String, TreeMap<Double, NonTerminalInChart>>();
        }
        
        public void addNonTerminalArray(String myName, TreeMap<Double, NonTerminalInChart> myNonTerminalArray){
            this.setOfNonTerminalArrays.put(myName, myNonTerminalArray);
        }
        
        public HashMap<String, TreeMap<Double, NonTerminalInChart>> getSetOfNonTerminalArrays(){
            return this.setOfNonTerminalArrays;
        }
    }
    
    //nested class
    //contains pointers to RHS of rule and to the cells that contributed the derivation (k), inside and Viterbi probabilities
    public class NonTerminalInChart {
        
        protected NonTerminal A;
        protected Rule myRule;
          protected int pointerToCell;
        
        /**
         * Creates a new instance of NonTerminalInChart 
         */
        public NonTerminalInChart(NonTerminal myA, Rule aRule, int myPointer) {
            this.A = myA;
            this.myRule = aRule;
            this.pointerToCell = myPointer;
          }
        
        public String getNonTerminalName(){
            return this.A.getName();
        }
        
        
        
        public int getPointer(){
            return this.pointerToCell;
        }
        
        public Rule getRule(){
            return this.myRule;
        }
        
        public void setPointer(int k){
            this.pointerToCell=k;
        }
        
        public void setRule(Rule rule){
            this.myRule=rule;
        }
       
    }
    
    //nested class
    //contains pointer to Chart Cell, to nonterminalname and to index within array of nonterminalincharts
    public class SearchPathNode implements Cloneable {
          
        protected String nonTerminalName ;
        protected int ChartCellXCoordinate;
        protected int ChartCellYCoordinate;
        protected double indexToTreeMap;
        protected boolean blnExpandedChildren = false;
        
        /**
         * Creates a new instance of SearchPathNode 
         */
        public SearchPathNode(int myX, int myY, String myNonTerminalName, Double myTreeMapIndex) {
            this.nonTerminalName = myNonTerminalName;
            this.ChartCellXCoordinate = myX;
            this.ChartCellYCoordinate = myY;
            this.indexToTreeMap = myTreeMapIndex;
        }
        
        public Double getArrayIndex(){
            return this.indexToTreeMap;
        }
        
        public int getXcoordinate(){
            return this.ChartCellXCoordinate;
        }
        
        public int getYcoordinate(){
            return this.ChartCellYCoordinate;
        }
        
         public String getNonTerminalName(){
            return this.nonTerminalName;
        }
         
         public boolean getExpanded(){
            return this.blnExpandedChildren;
        }
        
         public void setExpanded(boolean blnExpanded) {
             this.blnExpandedChildren = blnExpanded;
         }
         
         public Object clone() {
            try {
                SearchPathNode aobj = (SearchPathNode) super.clone();
                aobj.nonTerminalName = this.nonTerminalName;
                aobj.ChartCellXCoordinate = this.ChartCellXCoordinate;
                aobj.ChartCellYCoordinate = this.ChartCellYCoordinate;
                aobj.indexToTreeMap = this.indexToTreeMap;
                aobj.blnExpandedChildren  = this.blnExpandedChildren;
                
                return aobj;
            }
            catch (CloneNotSupportedException e) {
                throw new InternalError(e.toString());
            }
        }
    }
    
    //nested class
    //HashMap of SearchPathNodes
    public class SearchPath {
          
        protected ArrayList<SearchPathNode> mySearchPath;
        protected boolean blnFullyExpanded = false;
        protected double pathProbability;
        /**
         * Creates a new instance of SearchPath: HashMap of  SearchPathNodes plus bln blnFullyExpanded
         */
        public SearchPath(double myProbability) {
            this.mySearchPath = new ArrayList<SearchPathNode>();
            this.pathProbability = myProbability;
        }
        
        public ArrayList<SearchPathNode> getSearchPath() {
            return this.mySearchPath;
        }
        
        public double getProbability(){
            return this.pathProbability;
        }
        
        public void setProbability(double myProbability) {
             this.pathProbability = myProbability;
         }
         public boolean getFullyExpanded(){
            return this.blnFullyExpanded;
        }
        
         public void setFullyExpanded(boolean blnExpanded) {
             this.blnFullyExpanded = blnExpanded;
         }
    }
    /** Creates a new instance of CYKParser */
    public CYKParser(Grammar aGrammar, String[] mySentence) {
        
        this.parseSentence = mySentence;
        this.myGrammar = aGrammar;
        
        //instantiate chart with length of sentence
        this.chartDimension = mySentence.length +1;
        //xxx check: it should include 0 and n
        this.myChart = new ChartCell[chartDimension][];
        for (int i=0; i < chartDimension; i++){
            this.myChart[i] = new ChartCell[chartDimension];
        }
        
        //System.out.println("Starting Initialization...");
        doInitialization();

        //System.out.println("Starting Induction...");
        doNBestInduction();
        
        //System.out.println("Starting AddTop...");
        addTOP();
    }
    
    
    public void doInitialization(){ //old version
        
        //add nonTerminal A to E(i-1, i) iff there is a rule: A --> W(i)
        //inside(<i-1, A, i>) =P(A--> W(i) | A)
        
        double ruleProbability = 0d;
        
        for (int i=0; i < chartDimension-1; i++){   //# words = chartDimension-1
            myChart[i][i+1] = new ChartCell();
            //System.out.println("Initialization of chart cell (" + i + "," + (i+1) + ")");
            //this cell should derive parseSentence[i], so find rule with RHS = parseSentence[i] in grammar
            String myRHS = new String(this.parseSentence[i] + "*");
            //System.out.println("myRHS=" + myRHS);
            if (myGrammar.rulesIndexedByUnaryRHS.get(myRHS)!= null) {
                //there is only one, but iterate anyway, for generality
                for (Rule aRule : myGrammar.rulesIndexedByUnaryRHS.get(myRHS)){
                    
                    //create NonTerminalInChart, calculate probs etc
                    ruleProbability = aRule.getRuleProbability();
                    NonTerminalInChart temp = new NonTerminalInChart(aRule.getLeftHandSide(), aRule, 0);
                    TreeMap<Double, NonTerminalInChart> tempTreeMap = new TreeMap<Double, NonTerminalInChart>();
                    tempTreeMap.put((Double) ruleProbability, temp);
                    //add to cell
                    myChart[i][i+1].addNonTerminalArray(aRule.getLeftHandSide().getName(), tempTreeMap);
                }       
            }  
        }         
    }
    
    
    public void doNBestInduction(){
        int jColumn;
        TreeMap<Double, NonTerminalInChart> tempTreeMap;
        double ruleProbability, viterbiProbability;
        //Double KeyMaxProbB, KeyMaxProbC;
        String keyC;
        String myLHS;
        
        //traverse the diagonals, start 2 off the middle (initialization is 1 off the middle diagonal)
        for (int span = 2; span < chartDimension; span ++ ){
            //traverse a single diagonal in the chart from left top to right bottom
            for (int iRow = 0; iRow < chartDimension - span; iRow++) {
                jColumn = iRow + span;
                myChart[iRow][jColumn] = new ChartCell();
                //System.out.println("Induction of chart cell (" + iRow + "," + jColumn + ")");
                for (int k = iRow +1; k < jColumn ; k++) {
                    //System.out.println("k=" + k);
                    //the chosen k yields two subordinate Cells whom you can combine: myChart(iRow,k) and myChart(k,jColumn)
                    //enumerate the NonTerminals of both cells and look at all combinations
                    //int tellerB = 0;
                    //int tellerC = 0;
                    //int tellerRules = 0;
                    
                    for(String keyB : myChart[iRow][k].getSetOfNonTerminalArrays().keySet()) {
                        //tellerB++;
                        //System.out.println("##################tellerB=" + tellerB);
                        if (myGrammar.rulesIndexedByBodyLeftNonT.get(keyB)!= null) {
                            //enumerate all rules that have RHS starting with keyB (rulesIndexedByBodyLeftNonT contains only binary rules A --> B C)
                            for(Rule aRule : myGrammar.rulesIndexedByBodyLeftNonT.get(keyB)) {
                                //for those rules, keyC is the second part of RHS
                                //XXX TEMP
                                if (aRule.getRightHandSide().get(1)==null) System.out.println("Nullp.e. for Rule LHS=" + aRule.getLeftHandSide().getName() + "-->" + aRule.getRightHandSide().get(0).getName() + "; RHSSize=" + aRule.getRightHandSide().size());
                                keyC = aRule.getRightHandSide().get(1).getName();    //can occur more than once
                                //continue only if in the other chart cell there is a nonterminal equal to second part of RHS
                                if (myChart[k][jColumn].getSetOfNonTerminalArrays().get(keyC) != null) {
                             
                                    //tellerRules++;
                                    //if (tellerRules%10 ==0) System.out.println("XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXtellerRules=" + tellerRules);
                                    //create  a new NonTerminalInChart, calculate probs etc
                                    //ruleProbability = aRule.getRuleProbability();
                                    myLHS = aRule.getLeftHandSide().getName();

                                    //now enumerate over all the instances of the BESTN TreeMaps   
                                    for (Double KeyMaxProbB : myChart[iRow][k].getSetOfNonTerminalArrays().get(keyB).keySet()){
                                        //KeyMaxProbB.value and KeyMaxProbC are the NonTerminalInCharts inside the TreeMap of Bs and Cs, each of them should have different branches
                                        for (Double KeyMaxProbC : myChart[k][jColumn].getSetOfNonTerminalArrays().get(keyC).keySet()){

                                            viterbiProbability = aRule.getRuleProbability()*KeyMaxProbB.doubleValue()*KeyMaxProbC.doubleValue();

                                            //determine if this kind of NonTerminal has already been added to the list of the cell myChart[iRow][jColumn] (if myLHS corresponds to one of the nonterminals in the current cell)
                                            //if so: then update maxProbability, and if this probability is max, also update pointers to B, C and k
                                            if (myChart[iRow][jColumn].getSetOfNonTerminalArrays().get(myLHS)!=null) {
                                                //get a reference to the NonTerminalInChartArray which is the same as the LHS of the rule: you want only one of them in cell
                                                tempTreeMap = myChart[iRow][jColumn].getSetOfNonTerminalArrays().get(myLHS);
                                                } 
                                            else    //no single nonterminal of this label so no NonTerminalArray has yet been added to the list of the cell myChart[iRow][jColumn]
                                                {
                                                //create TreeMap
                                                tempTreeMap = new TreeMap<Double, NonTerminalInChart>();
                                                //add to cell
                                                myChart[iRow][jColumn].addNonTerminalArray(myLHS, tempTreeMap);   //to setOfNonTerminals
                                            }
                                            //if array is not full you may add another same nonterminal, otherwise you'll have to compare MaxProbabilities        
                                            if (tempTreeMap.size() < Main.BRANCHING_FACTOR || viterbiProbability > tempTreeMap.firstKey().doubleValue()) {  //always add NonTerminalInChart to ArrayList as long as there is place
                                                //if TreeMap has reached max size remove the one in the array with the lowest probability
                                                if (tempTreeMap.size() >= Main.BRANCHING_FACTOR) tempTreeMap.remove(tempTreeMap.firstKey());

                                                tempTreeMap.put((Double) viterbiProbability, new NonTerminalInChart(aRule.getLeftHandSide(), aRule, k));
                                                }
                                            
                                         }   //array myC
                                    }   //array myB  
                                }
                            }
                        }
                    }
                }
            }
        }
    }
    
    // Adds "TOP" and the corresponding rule to the chart cell at [0][chartDimension - 1]
    //since doInduction method searches only for binary rules (A -> B C) it misses unary rules
    //only at TOP unary rules are permitted, so in the TOP NonTerminalInChartArray you have to consider also 
    //all derivations that start with a unary rule (TOP -> A) and reconsider the BestN probabilities
    //Another thing is that because they are unary rules the RHS is in the same cell as the LHS, because the nonterminal in the RHS 
    //already derives the entire sentence (so it is also in the topcell). The CYK algorithm however never looks in the same cell for nonterminals of the RHS
    //therefore you have to add this
    protected void addTOP(){
        ChartCell topCell = myChart[0][chartDimension - 1];
        //first put aside all the existing derivations from the TOP NonTerminalInChartArray in the top cell of chart                                     
        TreeMap<Double, NonTerminalInChart> myTOPArray = topCell.getSetOfNonTerminalArrays().get("TOP");  //.remove("TOP");
        NonTerminal nonTerminalTOP = myGrammar.nonTerminals.get("TOP");
        
        if(myTOPArray == null){  //if it was not in top cell of chart
            //public NonTerminalInChart(NonTerminal myA, Rule aRule, double mymaxProbability, int myPointer, int myIndexB, int myIndexC) {
            //rule, k, indexB and indexC will be modified later in case you find a rule
            //NonTerminalInChart temp = new NonTerminalInChart(nonTerminalTOP, null, 0d, chartDimension - 1,0,0);
            myTOPArray = new TreeMap<Double, NonTerminalInChart>();   //still empty
            
        }
           
        //add the BESTN NonTerminalInCharts
        for(String nonTerminalName : topCell.getSetOfNonTerminalArrays().keySet() ){
            //get all UNARY rules of grammar that have RHS String starting with one of the entries in top cell
            HashSet<Rule> rules = myGrammar.getRulesFromRHS(nonTerminalName + "*");
            //System.out.println("nonTerminalName=" + nonTerminalName);
            if(rules == null) continue;
            
            for(Rule aRule : rules){
                //vind rules waarvoor RHS gelijk is aan een nonT uit topcell, en LHS gelijk aan TOP, dus unary TOP-->A
                //if there is a rule in grammar with LHS top and RHS starting with entry from top cell
                if(aRule.getLeftHandSide().getName().equals("TOP")){
                    
                    double ruleProbability = aRule.getRuleProbability();
                    double viterbiProbability = 0d;
                    //iterate over the entries of NonTerminalArrays containing RHS
                    for ( Double maxProbKey : topCell.getSetOfNonTerminalArrays().get(nonTerminalName).keySet()) {
                    
                        viterbiProbability = ruleProbability* maxProbKey.doubleValue();
                        if (myTOPArray.size()< Main.BRANCHING_FACTOR || viterbiProbability > myTOPArray.firstKey().doubleValue()) {  //always add NonTerminalInChart to ArrayList as long as there is place
                            //kick out first key
                            if (myTOPArray.size()>= Main.BRANCHING_FACTOR) myTOPArray.remove(myTOPArray.firstKey());
                            
                            myTOPArray.put((Double) viterbiProbability, new NonTerminalInChart(nonTerminalTOP, aRule, chartDimension - 1));
                            }
                         
                        
                    }
                }
            }
        }
        
        //if there wasn't a TOP array yet, and if you have added TOP NonTerminalInCharts to the TOP array
        //then put a TOP array in the top cell
        if (topCell.getSetOfNonTerminalArrays().get("TOP")==null && myTOPArray.size()>0) {
            topCell.addNonTerminalArray("TOP", myTOPArray);
         }
    }
    
    public parseTree readoutViterbiParse(){
        
        SearchPathBeam = new TreeMap<Double, SearchPath>();
        SearchPathBeamCandidates = new TreeMap<Double, SearchPath>();
        
        if (myChart[0][chartDimension - 1].getSetOfNonTerminalArrays().get("TOP")!=null) {
           
        //there may be more than one TOP, you must iterate over all the TOPs in NonTerminalInChartArray with name TOP
        //SearchPathNode
            int myArrayIndex =0;
            for ( Double maxProbKey : myChart[0][chartDimension - 1].getSetOfNonTerminalArrays().get("TOP").keySet()) {
            //for (NonTerminalInChart myNonT : myChart[0][chartDimension - 1].getSetOfNonTerminalArrays().get("TOP")) {
                //for each entry in TOP array, create a new SearchPathNode, create a new SearchPath and add node to it,
                //add SearchPath to SearchPathBeam with prob is its key, and send SearchPath to beam search (to expand one leaf nonterminal)
                SearchPathNode tempSearchPathNode = new SearchPathNode(0, chartDimension - 1, "TOP", maxProbKey);
                SearchPath tempSearchPath = new SearchPath(maxProbKey.doubleValue());
                
                tempSearchPath.getSearchPath().add(tempSearchPathNode);
                SearchPathBeam.put(maxProbKey, tempSearchPath);
                
                doExpandOneLeaf(tempSearchPath);
              myArrayIndex++;
          }
        }
        //else System.out.println("no TOP in top right cell of the chart");
        
        //now, continue expanding the entire Beam, untill all of the searchpaths are fully expanded
        boolean allSearchPathsFullyExpanded = false;
        while(!allSearchPathsFullyExpanded) {
            //clear candidate beam 
            SearchPathBeamCandidates.clear();
            
            //iterate over searchbeam, keep count of fully expanded searchpaths
            boolean atLeastOneSearchPathExpanded = false;
            for ( Double key : SearchPathBeam.keySet()) {
                if (!SearchPathBeam.get(key).getFullyExpanded()){
                    atLeastOneSearchPathExpanded = true;
                    doExpandOneLeaf(SearchPathBeam.get(key));
                }
            }
            
            //add candidate beam to search beam
            SearchPathBeam.putAll(SearchPathBeamCandidates);
            
            //if no SearchPath needed to be expanded then get out of while loop
            if (!atLeastOneSearchPathExpanded) allSearchPathsFullyExpanded=true;
        }
        
        //if everything went right so far, you now have a beam containing the best 1000 fully expanded paths (w/o terminals)
        //you now have to convert the searchPaths to parseTrees, creating nodes on the way
        
        parseForest = new ArrayList<parseTree>();
        parseForestCFG = new ArrayList<parseTree>();
        
        if (SearchPathBeam.size()>0) {
            for ( Double key : SearchPathBeam.keySet()) {

                SearchPath mySearchPath = SearchPathBeam.get(key);
                //System.out.println("prob=" + mySearchPath.getProbability());
                parseTree myParseTree = new parseTree(); 

                //TOP node already made in constructor of parseTree
                Node myNode = myParseTree.getNodes().get(0);
                //set span
                myNode.setLeftSpan(0);
                myNode.setRightSpan(chartDimension-1);

                //find SearchPathNode that corresponds to top cell in SearchPath
                //it should be the first one...
                SearchPathNode myTOPSearchPathNode = mySearchPath.getSearchPath().get(0);
                //public void doRecursivePathToTreeConversion(SearchPathNode currentSearchPathNode, SearchPath mySearchPath, Node currentNode, parseTree myParse) {
                doRecursivePathToTreeConversion(myTOPSearchPathNode, mySearchPath, myNode, myParseTree);

                //compare myParseTree to existing parseTrees in forest and only if it doesn't exist yet, add it to forest
                boolean myParseTreeExists = false;
                for (parseTree uniqueParseTree : parseForest) {
                    //XXX have to check this: equals method in Node only compares NodeName and spans
                    if (uniqueParseTree.getNodes().equals(myParseTree.getNodes())){
                        //add probability of SearchPath to that of parse
                        uniqueParseTree.setProbability(uniqueParseTree.getProbability() + mySearchPath.getProbability());
                        myParseTreeExists = true;
                        break;
                    }
                }
                //add to parseForest
                if (!myParseTreeExists) {
                    myParseTree.setProbability(mySearchPath.getProbability());
                    parseForest.add(myParseTree);
                }

            }

            //then convert all parseTrees in forest them back to CFG format, for the entire parseForest at once
            boolean myCFGParseTreeExists = false;
            for (parseTree parseTreeCNF : parseForest) {
                
                parseTreeCNF.transformBackToCFG();

                //after conversion again compare them one to the other, create another parse forest with only unique parses (so merge identical parses), and add up probablilities of the parses
                for (parseTree parseTreeCFG : parseForestCFG) {
                    //XXX have to check this: equals method in Node only compares NodeName and spans
                    if (parseTreeCFG.getNodes().equals(parseTreeCNF.getNodes())){
                        myCFGParseTreeExists = true;
                        break;
                    }
                }
                //add to parseForestCFG
                if (!myCFGParseTreeExists) parseForestCFG.add(parseTreeCNF);
            }


            //and finally you can find most probable parse
            parseTree mostProbableParse = null;
            double maxProb = -1d;
            for (parseTree someParseTree : parseForestCFG) {
                //System.out.println("probCFG=" + someParseTree.getProbability());
                //someParseTree.printToLatex(false, true, "computed" );

                if (someParseTree.getProbability()> maxProb){
                    maxProb = someParseTree.getProbability();
                    mostProbableParse = someParseTree;
                }
            }


            //printout
            //System.out.println("");
            //System.out.println("The most probable parse with probability= " + maxProb + ": ");

            return mostProbableParse;
            
        } //searchbeam.size()>0
        else {
            System.out.println("no parse found");
            return null;
        }
        //EN DAT WAS 'M!!!
    }

    
    public boolean doExpandOneLeaf(SearchPath mySearchPath){
        
        SearchPathNode NodeToExpand = null;
        ChartCell myChartCell  = null;
        int chartRow = 0;
        int chartColumn = 0;
        
        //iterate through mySearchPath to find first unexpanded SearchPathNode (nonterminal: terminals should have expanded = true)
        for (SearchPathNode tempSearchPadNode : mySearchPath.getSearchPath()) {
            //if searchpathnode is not yet expanded
            if (!tempSearchPadNode.getExpanded()) {
                NodeToExpand = tempSearchPadNode;
                //from key reconstruct cell in chart
                chartRow = NodeToExpand.getXcoordinate(); 
                chartColumn = NodeToExpand.getYcoordinate(); 
                myChartCell = this.myChart[chartRow][chartColumn];
                break;
            }
        }
        
        if (NodeToExpand==null) {
              mySearchPath.setFullyExpanded(true)  ;
              return false;
        }
        
        // find RHS of rule + pointer
        String myNodeName = NodeToExpand.getNonTerminalName();
        NonTerminalInChart myNonTerminalInChart =  myChartCell.getSetOfNonTerminalArrays().get(myNodeName).get(NodeToExpand.getArrayIndex());
        Rule myRule = myNonTerminalInChart.getRule();
        
        //locate NonTerminalInChartArrays for both nonterminals in RHS, so you have Array1.size()*Array2.size()
        //possible combinations for expansion
        if (myRule.countSymbolsinRHS()==2 )  {
            
            //get references to both NonTerminalInChartArrays in two different cells
            int k = myNonTerminalInChart.getPointer();
            //call Cell(iRow, k) with NonTerminal B
            String NonTerminalBName =  myRule.getRightHandSide().get(0).getName();
            String NonTerminalCName =  myRule.getRightHandSide().get(1).getName();
            
            TreeMap<Double, NonTerminalInChart> ArrayListB = myChart[chartRow][k].getSetOfNonTerminalArrays().get(NonTerminalBName);
            TreeMap<Double, NonTerminalInChart> ArrayListC = myChart[k][chartColumn].getSetOfNonTerminalArrays().get(NonTerminalCName);
            
            //mark current node as expanded in search path //XXX uitkijken als je er reference van hebt binnen andere searchpath
            NodeToExpand.setExpanded(true);
            
            //find highest probable NonTerminalInChart in both arrays: is obvious from TreeMap
            double maxProbB = ArrayListB.lastKey().doubleValue();
            double maxProbC = ArrayListC.lastKey().doubleValue();
            
            //create 2 searchpathnodes, and add them to current searchpath (w/o changing probability)
            //the highest probability NonTerminalInChart is always preserved in the beam: for this one, add two SearchPathNodes to the SearchPath
            //first add the others if either the beam is not full yet, or if their probability is higher then 
            
            
            for ( Double keyB : ArrayListB.keySet()) {
            //for (NonTerminalInChart NonTerminalB : ArrayListB) {
                for ( Double keyC : ArrayListC.keySet()) {
                //for (NonTerminalInChart NonTerminalC : ArrayListC) {
                    //not the same one you just expanded
                    //if (NonTerminalB.getMaxProbability() != maxProbB && NonTerminalC.getMaxProbability() != maxProbC) {
                    if (!keyB.equals(ArrayListB.lastKey()) && !keyC.equals(ArrayListC.lastKey())) {
                        boolean addCandidate = false;
                        //calculate probability for new searchpath
                        //double candidateProb = (NonTerminalB.getMaxProbability()/maxProbB)*(NonTerminalC.getMaxProbability()/maxProbC)*mySearchPath.getProbability();
                        double candidateProb = (keyB.doubleValue()/maxProbB)*(keyC.doubleValue()/maxProbC)*mySearchPath.getProbability();
                        
                        if (SearchPathBeam.size() + SearchPathBeamCandidates.size()< Main.BEAM_WIDTH){
                        //there is place in search beam, so you may simply add extra searchpath (as candidate)
                            addCandidate = true;
                        }
                        else {
                        //compare with lowest prob from both SearchPathBeam and SearchPathBeamCandidates
                            if (candidateProb > SearchPathBeam.firstKey().doubleValue() && candidateProb > SearchPathBeamCandidates.firstKey().doubleValue()) {
                                addCandidate = true;
                            } 
                        //you need to kick one out: the lowest of SearchPathBeam and SearchPathBeamCandidates
                            if (SearchPathBeam.firstKey().doubleValue() < SearchPathBeamCandidates.firstKey().doubleValue()) {
                                //remove one of SearchPathBeam
                                SearchPathBeam.remove(SearchPathBeam.firstKey());
                            }
                            else {  //remove one of SearchPathBeamCandidates
                                SearchPathBeamCandidates.remove(SearchPathBeamCandidates.firstKey());
                            }
                        }
                        // now add to SearchPathBeamCandidates
                        if (addCandidate){
                            
                            //create new searchpaths
                            //and create a new searchpath, by copying (reference to) SearchPathNodes of the original up to here, and adding two nodes
                            SearchPath newSearchPath = new SearchPath(candidateProb);
                            //enumerate the SearchPathNodes of the original and add reference to new one
                            for ( SearchPathNode tempSearchPathNode1 : mySearchPath.getSearchPath()) {
                                //XXX temp: check if cloning them solves the buhg
                                newSearchPath.getSearchPath().add((SearchPathNode) tempSearchPathNode1.clone());
                            }    
                            //change probability by ratio, and add it as key to SearchPathBeamCandidates
                            //cellPointerB and C and NonTerminalBName, NonTerminalCName are the same for all candidates, only arrayIndexB/C is different
                            SearchPathNode alternativeSearchPathNodeB = new SearchPathNode(chartRow, k, NonTerminalBName, keyB);    //was arrayIndexB
                            SearchPathNode alternativeSearchPathNodeC = new SearchPathNode(k, chartColumn, NonTerminalCName, keyC); //was arrayIndexC
            
                            newSearchPath.getSearchPath().add(alternativeSearchPathNodeB);
                            newSearchPath.getSearchPath().add(alternativeSearchPathNodeC);
                            //add new searchpath to temporary beamsearch, so you can add it later to real beamsearch
                            //add to SearchPathBeamCandidates
                            SearchPathBeamCandidates.put(candidateProb, newSearchPath);
                            
                        }
                        
                     }   //end if not the same as the maxProb natural successor    
                 }
            }
           
            //now expand the original SearchPath with the maxProb SearchPathNodes
            //you do this after the alternatives, because you don't want to copy newSearchPathNodeB/C to alternatives
            //public SearchPathNode(String myPointerToCell, String myNonTerminalName, int myArrayIndex) {
            SearchPathNode newSearchPathNodeB = new SearchPathNode(chartRow, k, NonTerminalBName, ArrayListB.lastKey());
            SearchPathNode newSearchPathNodeC = new SearchPathNode(k, chartColumn, NonTerminalCName, ArrayListC.lastKey());
            //add them to search path
            mySearchPath.getSearchPath().add(newSearchPathNodeB);
            mySearchPath.getSearchPath().add(newSearchPathNodeC);
            
        }
        else    {   //UNARY RULES
           
            if( myRule.getLeftHandSide().getName().equals("TOP")) {
            //let op: unary rule vanaf TOP zit in zelfde cel!!!
                 //get references to NonTerminalInChartArray
                int k = myNonTerminalInChart.getPointer();
                //call Cell(iRow, k) with NonTerminal B
                String NonTerminalBName =  myRule.getRightHandSide().get(0).getName();
 
                if (myChart[chartRow][k]==null) System.out.println("myNonTerminalInChart=" + myNonTerminalInChart.getNonTerminalName() + "; RHS=" + myNonTerminalInChart.getRule().getRightHandSide().get(0).getName() + "; chartRow=" +chartRow +"; k=" + k);
                
                TreeMap<Double, NonTerminalInChart> ArrayListB = myChart[chartRow][k].getSetOfNonTerminalArrays().get(NonTerminalBName);
 
                //mark current node as expanded in search path //XXX uitkijken als je er reference van hebt binnen andere searchpath
                NodeToExpand.setExpanded(true);

                
                //find highest probable NonTerminalInChart in arrays
                double maxProbB = ArrayListB.lastKey().doubleValue();
                
                
                //create 1 searchpathnode, and add it to current searchpath (w/o changing probability)
                //the highest probability NonTerminalInChart is always preserved in the beam: for this one, add two SearchPathNodes to the SearchPath
                //String cellPointerB = ((Integer) (chartRow)).toString() + "_" + ((Integer) (k)).toString();
           
                
                //first add the others if either the beam is not full yet, or if their probability is higher then 
                for ( Double keyB : ArrayListB.keySet()) {
                //for (NonTerminalInChart NonTerminalB : ArrayListB) {
                    
                        //not the same one you just expanded
                        //if (NonTerminalB.getMaxProbability() != maxProbB) {
                        if (keyB.doubleValue() != maxProbB) {
                            boolean addCandidate = false;
                            //calculate probability for new searchpath
                            double candidateProb = (keyB.doubleValue()/maxProbB)*mySearchPath.getProbability();

                            if (SearchPathBeam.size() + SearchPathBeamCandidates.size()< Main.BEAM_WIDTH){
                            //there is place in search beam, so you may simply add extra searchpath (as candidate)
                                addCandidate = true;
                            }
                            else {
                            //compare with lowest prob from both SearchPathBeam and SearchPathBeamCandidates
                                if (candidateProb > SearchPathBeam.firstKey().doubleValue() && candidateProb > SearchPathBeamCandidates.firstKey().doubleValue()) {
                                    addCandidate = true;
                                } 
                            //you need to kick one out: the lowest of SearchPathBeam and SearchPathBeamCandidates
                                if (SearchPathBeam.firstKey().doubleValue() < SearchPathBeamCandidates.firstKey().doubleValue()) {
                                    //remove one of SearchPathBeam
                                    SearchPathBeam.remove(SearchPathBeam.firstKey());
                                }
                                else {  //remove one of SearchPathBeamCandidates
                                    SearchPathBeamCandidates.remove(SearchPathBeamCandidates.firstKey());
                                }
                            }
                            // now add to SearchPathBeamCandidates
                            if (addCandidate){

                                //create new searchpaths
                                //and create a new searchpath, by copying (reference to) SearchPathNodes of the original up to here, and adding two nodes
                                SearchPath newSearchPath = new SearchPath(candidateProb);
                                //enumerate the SearchPathNodes of the original and add reference to new one
                                for ( SearchPathNode tempSearchPathNode2 : mySearchPath.getSearchPath()) {
                                    //XXX temp: check if cloning them solves the buhg
                                    newSearchPath.getSearchPath().add((SearchPathNode) tempSearchPathNode2.clone());
                                }    
                                //change probability by ratio, and add it as key to SearchPathBeamCandidates
                                //XXX check this: if unary rule then coordinates should be 0, chartdimension-1
                                SearchPathNode alternativeSearchPathNodeB = new SearchPathNode(chartRow, k, NonTerminalBName, keyB);    //was arrayIndexB
                          
                                newSearchPath.getSearchPath().add(alternativeSearchPathNodeB);
                                //add new searchpath to temporary beamsearch, so you can add it later to real beamsearch
                                //add to SearchPathBeamCandidates
                                SearchPathBeamCandidates.put(candidateProb, newSearchPath);

                            }
                        }
                    }

                //now expand the original SearchPath with the maxProb SearchPathNodes
                //you do this after the alternatives, because you don't want to copy newSearchPathNodeB/C to alternatives
                //public SearchPathNode(String myPointerToCell, String myNonTerminalName, int myArrayIndex) {
                SearchPathNode newSearchPathNodeB = new SearchPathNode(chartRow, k, NonTerminalBName, ArrayListB.lastKey());
                //add them to search path
                mySearchPath.getSearchPath().add(newSearchPathNodeB);
             }
            else {  //RHS is terminal
                //mark current node as expanded in search path //XXX uitkijken als je er reference van hebt binnen andere searchpath
                NodeToExpand.setExpanded(true);
                //the nonterminal in that particular cell can point only to one single terminal, so no need to consider
                //alternative search paths or change probabilities
            }
        }
       
        return true;   //if there still was something to expand
    }
    
    //you are at a branching NonTerminalInChart with an index to indicate its place within a NonTerminalInChart array
    //NO: there is one optimal (the indexed) NonTerminalInChart in the array that retains maxprob, and there are other nonterminals in the array
    //that also derive the sentence, but with a suboptimal maxprob: for these you have to recalculate maxprob of the Viterbi-parse (till TOP)
    //so you must also call backtrack with current maxprob.
    //first find best 1000 w/o doing backtrack, remember pointers.
    
    //keep a collection of best 1000 partial trees
    //for all children of leave nodes 
    //1) input A (plus index?), return all the other NonT of the same array together with their probs and indices
    //2) after you have collected all, find best 1000, and put them as nodes in parseTrees
    //3) for all children of the best 1000 (iterate over all those different cells and different NonT arrays) goto 1 (send also tree)
    
    public void doRecursivePathToTreeConversion(SearchPathNode currentSearchPathNode, SearchPath mySearchPath, Node currentNode, parseTree myParse) {
        //NonTerminalName is necessary because label is stripped of from node name
        //extract rule from the specified cell
        //first retrieve NonTerminalInChartArray, then specific one according to myIndex
        //System.out.println("NonTerminalName=" + NonTerminalName + "; index=" + myIndex);
        //System.out.println("getSetOfNonTerminalArraysSize=" +this.myChart[iRow][jColumn].getSetOfNonTerminalArrays().get(NonTerminalName).size());
        
        //get to the right NonTerminalInChart in the chart, through info in searchpath node
        int iRow = currentSearchPathNode.getXcoordinate();  //java.lang.Integer.parseInt(currentSearchPathNode.getPointerToCell().split("_")[0]);
        int jColumn = currentSearchPathNode.getYcoordinate();   //java.lang.Integer.parseInt(currentSearchPathNode.getPointerToCell().split("_")[1]);
        String NonTerminalName = currentSearchPathNode.getNonTerminalName();
        //probability is used as index for which NonTerminal from TreeMap
        Double myArrayIndex = currentSearchPathNode.getArrayIndex();
        
        NonTerminalInChart currentNonTerminalInChart = this.myChart[iRow][jColumn].getSetOfNonTerminalArrays().get(NonTerminalName).get(myArrayIndex);   
        Rule myRule = currentNonTerminalInChart.getRule();
        
        //if RHS is Terminal, then do nothing, otherwise, do two recursive calls
        //assuming there are always exactly 2 nonTerminals in RHS, which should be the case (except for TOP->A)
        
        if (myRule.countSymbolsinRHS()==1 && myRule.getRightHandSide().get(0) instanceof Terminal) {    //EXCLUDES TOPunary rules     
                //add a terminal node 
                Node terminalNode = new Node(myRule.getRightHandSide().get(0).getName(), currentNode);
                terminalNode.setType(Main.TERMINAL);
                //set pointer to this in parent
                currentNode.addChildNode(terminalNode);
                //you don't need span of terminal, because PARSEVAL disregards it
                //add to parseTree 
                myParse.addNode(terminalNode);

        } else    { //BINARY RULE OR UNARY RULE WITH LHS TOP
            
            int k = currentNonTerminalInChart.getPointer();
            //call Cell(iRow, k) with NonTerminal B
            String NonTerminalB =  myRule.getRightHandSide().get(0).getName();
            
            //create a node with label stripped off 
            //XXX let op: moet je nodes dubbel aanmaken??
            //als je set union wilt doen wordt dat lastig
            Node myNodeB = new Node(NonTerminalB.split("@")[0], currentNode);
            myNodeB.setType(Main.NONTERMINAL);
            //set pointer to this in parent
            currentNode.addChildNode(myNodeB);
            //set node span :read from chart 
            myNodeB.setLeftSpan(iRow);
            myNodeB.setRightSpan(k);
            //String myPointerToCellB = ((Integer) (iRow)).toString() + "_" + ((Integer) (k)).toString();
            //this is necessary, because SearchPathNode contains reference to selected index within array of NonTerminalInCharts
            //XXX helaas dit werkt niet meer
            //find out which node to expand next: iterate over SearchPath
            SearchPathNode nextSearchPathNodeB = null;
            for (SearchPathNode tempSearchPathNode : mySearchPath.getSearchPath()){
                if (tempSearchPathNode.getXcoordinate()==iRow && tempSearchPathNode.getYcoordinate()==k && tempSearchPathNode.getNonTerminalName().equals(NonTerminalB)){
                    nextSearchPathNodeB = tempSearchPathNode;
                    break;
                }
            }
            //SearchPathNode nextSearchPathNodeB = mySearchPath.getSearchPath().get(myPointerToCellB);
            //add to parseTree 
            myParse.addNode(myNodeB);
            
            if (nextSearchPathNodeB==null) {
                Rule testRule;
                int testK;
                ChartCell tempCell;
                System.out.println("Something went wrong here");
                System.out.println("We are at node " + NonTerminalName + "; RHS=" + NonTerminalB + "; pointer=" + myArrayIndex);
                System.out.println("Other possible nodes in same array");
                for (Double testKey : this.myChart[iRow][jColumn].getSetOfNonTerminalArrays().get(NonTerminalName).keySet()) {
                    testRule = this.myChart[iRow][jColumn].getSetOfNonTerminalArrays().get(NonTerminalName).get(testKey).getRule();
                    testK = this.myChart[iRow][jColumn].getSetOfNonTerminalArrays().get(NonTerminalName).get(testKey).getPointer();
                    System.out.println("leftRHS=" + testRule.getRightHandSide().get(0).getName() + " at Xcoordinate=" + iRow + "; Ycoordinate=" + testK + "; probPointer=" + testKey);
                }   
                System.out.println("Requested: Xcoordinate=" + iRow + "; Ycoordinate=" + k + "; NonTerminalName=" + NonTerminalB);
                System.out.println("Actual values:");
                for (SearchPathNode tempSearchPathNode : mySearchPath.getSearchPath()){
                    String tempName = tempSearchPathNode.getNonTerminalName();
                    System.out.println("Xcoordinate=" + tempSearchPathNode.getXcoordinate() + "; Ycoordinate=" + tempSearchPathNode.getYcoordinate()  + "; NonTerminalName=" +  tempName);  
                    //get rule through tempSearchPathNode.getArrayIndex() 
                    tempCell = this.myChart[tempSearchPathNode.getXcoordinate()][tempSearchPathNode.getYcoordinate()];
                    //for (Double KeyMaxProbB : myChart[iRow][k].getSetOfNonTerminalArrays().get(keyB).keySet()){
                    for (Double testKey : tempCell.getSetOfNonTerminalArrays().get(tempName).keySet()) {
                        testRule = tempCell.getSetOfNonTerminalArrays().get(tempName).get(testKey).getRule();
                        testK = tempCell.getSetOfNonTerminalArrays().get(tempName).get(testKey).getPointer();
                        //int tempArray = tempCell.getSetOfNonTerminalArrays().get(tempName).get(testKey).
                        System.out.println("    points to " + testRule.getRightHandSide().get(0).getName() + " at Xcoordinate=" + tempSearchPathNode.getXcoordinate() + "; Ycoordinate=" + testK + "; probPointer=" + testKey);
                    }
                    
                }
            }
            //public void doRecursivePathToTreeConversion(SearchPathNode currentSearchPathNode, SearchPath mySearchPath, Node currentNode, parseTree myParse) {
            doRecursivePathToTreeConversion(nextSearchPathNodeB, mySearchPath, myNodeB, myParse) ;
            
            //if we are not dealing with "TOP -> B" rule, ie. RHS has two items ("A ->BC"), we can process the second item
            if(myRule.getRightHandSide().size() > 1){
                String NonTerminalC =  myRule.getRightHandSide().get(1).getName();
                
                //create a node with label stripped off 
                //
                Node myNodeC = new Node(NonTerminalC.split("@")[0], currentNode);
                myNodeC.setType(Main.NONTERMINAL);
                //set pointer to this in parent XXX
                currentNode.addChildNode(myNodeC);
                //set node span :read from chart 
                myNodeC.setLeftSpan(k);
                myNodeC.setRightSpan(jColumn);
                String myPointerToCellC = ((Integer) (k)).toString() + "_" + ((Integer) (jColumn)).toString();
                //find out which searchpathnode to expand next
                SearchPathNode nextSearchPathNodeC = null;
                for (SearchPathNode tempSearchPathNode : mySearchPath.getSearchPath()){
                    if (tempSearchPathNode.getXcoordinate()==k && tempSearchPathNode.getYcoordinate()==jColumn && tempSearchPathNode.getNonTerminalName().equals(NonTerminalC)){
                        nextSearchPathNodeC = tempSearchPathNode;
                        break;
                    }
                }
                //SearchPathNode nextSearchPathNodeC = mySearchPath.getSearchPath().get(myPointerToCellC);
                //add to parseTree 
                myParse.addNode(myNodeC);
            
                doRecursivePathToTreeConversion(nextSearchPathNodeC, mySearchPath, myNodeC, myParse) ;
            }
        }
    }

}