/**************************************************************
 * 
 * Licensed to the Apache Software Foundation (ASF) under one
 * or more contributor license agreements.  See the NOTICE file
 * distributed with this work for additional information
 * regarding copyright ownership.  The ASF licenses this file
 * to you under the Apache License, Version 2.0 (the
 * "License"); you may not use this file except in compliance
 * with the License.  You may obtain a copy of the License at
 * 
 *   http://www.apache.org/licenses/LICENSE-2.0
 * 
 * Unless required by applicable law or agreed to in writing,
 * software distributed under the License is distributed on an
 * "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY
 * KIND, either express or implied.  See the License for the
 * specific language governing permissions and limitations
 * under the License.
 * 
 *************************************************************/



package org.openoffice.xmerge.converter.xml.sxc.pexcel.records.formula;

import java.util.*;
import org.openoffice.xmerge.util.Debug;

/**
 * FormulaCompiler converts Calc formula string into PocketXL bytes 
 * and PocketXL formula bytes into Calc Formula strings
 * 
 * For converting from infix to Reverse Polish (or Postfix) notation the string is
 * converted into a vector of Tokens and then re-ordered based on a modified version
 * of the standard Infix to RPN conversion algorithms.
 * <pre>
 *	Infix2Rpn(tokens)
 *		while have more tokens
 *			if token is operand 
 *				push to stack
 *			else if token is function, argument separater, or open bracket
 *				push token
 *				extract tokens to matching close bracket into param
 *				Infix2Rpn(param)
 *			else if token is close bracket
 *				pop from stack into result until close bracket or function
 *			else 
 *				while stack.top.priority &gt;= token.priority
 *					add stack.pop to result
 *				push token onto stack
 * </pre>
 * For converting from RPN to Infix the following algorithm is applied:
 * <pre>
 * 		while have more tokens
 * 			if token is operand
 *				push token to stack
 *			else if token is function or operator
 *				pop from stack number of args required by token
 *				apply token to params to make expr
 *				push expr to stack
 *		return stack.pop
 * </pre>
 */
public class FormulaCompiler {
	/**
	 *	Constructs a FormulaCompiler object
	 */
    public FormulaCompiler() {
    }
    
    private boolean isPercent(Token pt) {
        return pt.getTokenID() == TokenConstants.TPERCENT;
    }
    
    private boolean isOpenBrace(Token pt) {
        return pt.getTokenID() == TokenConstants.TPAREN;
    }
    
    private boolean isCloseBrace(Token pt) {
        return pt.getValue().compareTo(")") == 0;
    }
    
    private boolean isParamDelimiter(Token pt) {
        return pt.getTokenID() == TokenConstants.TARGSEP;
    }    

	private boolean isBinaryOperator(Token pt) {
		return false;
	}
    
    /**
	 * Re-order into Infix format
	 * @param	tokens	The tokens in RPN form
	 * @return	The vector of tokens re-ordered in Infix notation
     */
    public Vector RPN2Infix(Vector tokens) {
        Vector infixExpr = new Vector(15);
        ListIterator iter = tokens.listIterator();
        Stack evalStack = new Stack();
        Stack args = new Stack();
        
        while (iter.hasNext()) {
            Token pt = (Token)iter.next();
            if (pt.isOperand()) {
                Vector expr = new Vector(5);
                expr.add(pt);
                evalStack.push(expr);
            } else if (pt.isOperator() || pt.isFunction()) {
                args.clear();
                for (int i=0; i< pt.getNumArgs(); i++) {
                    args.push(evalStack.pop());
                }
                evalStack.push(makeExpression(pt, args));
            }
        }
        return (Vector)evalStack.elementAt(0);
    }
    
    /**
	 * Convert the infix expression to RPN. Note that open brackets are saved onto the stack to preserve the users bracketing.
	 * <p>Also note that the open bracket following functions is not pushed onto the stack - it is always implied when
	 * writing out results
	 *
     * @param	tokens	The vector of tokens in Infix form
	 *
	 * @return	A vector of tokens for the expression in Reverse Polish Notation order
     */
    public Vector infix2RPN(Vector tokens) {
        Vector rpnExpr = new Vector(15);
        Stack evalStack = new Stack();
        ListIterator iter = tokens.listIterator();
        while (iter.hasNext()) {
            Token pt = (Token)iter.next();
            
            if (pt.isOperand()) { //Operands are output immediately
                rpnExpr.add(pt);
            } else if (pt.isFunction() || isParamDelimiter(pt) || isOpenBrace(pt)) { //Extract parameters after afunction or comma
                evalStack.push(pt);
				if (pt.isFunction()) {
					iter.next();
				}
                Vector param = extractParameter(iter);
				Debug.log(Debug.TRACE, "Extracted parameter " + param);        
                rpnExpr.addAll(infix2RPN(param));
            } else if (isCloseBrace(pt)) { //Pop off stack till you meet a function or an open bracket
                Token tmpTok = null;
                boolean bPop = true;
                while (bPop) {
                    if (evalStack.isEmpty()) {
                        bPop = false;
                    } else {
                        tmpTok = (Token)evalStack.pop();
                        //if (!(isOpenBrace(tmpTok) || isParamDelimiter(tmpTok))) { //Don't output brackets and commas
                        if (!isParamDelimiter(tmpTok)) { //Don't output commas
                            rpnExpr.add(tmpTok);
						}
                        if (tmpTok.isFunction() || isOpenBrace(tmpTok)) {
							bPop = false;        
                        }
                    }
                }
            } else {
                if (!evalStack.isEmpty()) {
                    while (!evalStack.isEmpty() && 
                            (((Token)evalStack.peek()).getTokenPriority() >=pt.getTokenPriority())) {
                    	Token topTok = (Token)evalStack.peek();
                        if (topTok.isFunction() || isOpenBrace(topTok)) {
                            break;
                        }
                       	rpnExpr.add(evalStack.pop());
                    }
                }
                evalStack.push(pt);                
            }
        }
        
        while (!evalStack.isEmpty()) {
            Token topTok = (Token)evalStack.peek();
            if (!(isOpenBrace(topTok) || isParamDelimiter(topTok))) { //Don't output brackets and commas
            	rpnExpr.add(evalStack.pop());
			}
			else
			{
				evalStack.pop();
			}
        }
        return rpnExpr;
    }
    
    /**
     * Extract a parameter or bracketed sub-expression
	 * @param iter an iterator into the list
	 * @return A complete sub-expression
     */
    protected Vector extractParameter(ListIterator iter) {
        Vector param = new Vector(5);
		int subExprCount = 0;
        
        while (iter.hasNext()) {
            Token pt = (Token)iter.next();
			Debug.log(Debug.TRACE, "Token is " + pt + " and subExprCount is " + subExprCount);        
			if (isOpenBrace(pt)) {
				subExprCount++;
                param.add(pt);
			} else if (isCloseBrace(pt)) {
				if (subExprCount == 0) {
					iter.previous();
					return param;
				} else {
					subExprCount--;
					param.add(pt);
				}
			} else if (isParamDelimiter(pt) && (subExprCount == 0)) {
				iter.previous();
				return param;
			} else {
				param.add(pt);
			}
        }
        return param;
    }
    
	/**
	 * Given the operator and it's operators
	 * @param 	pt	The operator token
	 * @param	args	The arguments for this operator
	 * @return	A correctly ordered expression
	 */
    protected Vector makeExpression(Token pt, Stack args) {
        Vector tmp = new Vector(5);
		TokenFactory tf = new TokenFactory();
        if (pt.isOperator()) {
            if (pt.getNumArgs()==2) { //Binary operator
                tmp.addAll((Vector)args.pop());
                tmp.add(pt);
                tmp.addAll((Vector)args.pop());
            } else if (pt.getNumArgs() == 1) {
				if(isPercent(pt)) {
					tmp.addAll((Vector)args.elementAt(0));
					tmp.add(pt);
				} else {
					tmp.add(pt);
					tmp.addAll((Vector)args.elementAt(0));
				}
				if (isOpenBrace(pt)) {
					tmp.add(tf.getOperatorToken(")",1));
				}
			}
        } else if (pt.isFunction()) {
	    	tmp.add(pt);
			tmp.add(tf.getOperatorToken("(",1));
			if (!args.isEmpty()) {
				Vector v = (Vector)args.pop();
				tmp.addAll(v);
			}
			while (!args.isEmpty()) {
				tmp.add(tf.getOperatorToken(",",1));
				Vector v = (Vector)args.pop();
				tmp.addAll(v);

			}
			tmp.add(tf.getOperatorToken(")",1));
        }

		return tmp;
    }
}