/**
 * Starter code for a parser for a Logo-like language;
 * used as part of an assignment in CIT594, Spring 2009.
 */
package parser;

import java.util.*;

import tokenizer.Tokenizer;
import tokenizer.TokenType;
import tokenizer.Token;
import tree.Tree;
/**
 * @author David Matuszek
 * @author // TODO fill in your name
 * @version March 19, 2009
 */
public class Parser {
    private Tokenizer tokenizer = null; 
    private Token LIST_TOKEN = new Token(TokenType.NAME, "list");
    private Token HEADER_TOKEN = new Token(TokenType.NAME, "header");
    private Token PROGRAM_TOKEN = new Token(TokenType.NAME, "program");
    private static final boolean DEBUG = false;
    
    /**
     * The stack used for holding Trees as they are created.
     */
    public Stack<Tree<Token>> stack = new Stack<Tree<Token>>();

    /**
     * Constructs a Parser for the given string.
     * @param text The string to be parsed.
     */
    public Parser(String text) {
        tokenizer = new Tokenizer(text);
    }
    
    /**
     * Returns this Parser's Tokenizer. Should be used <i>only</i>
     * for testing this Parser; external use of the Tokenizer will
     * change its state and invalidate this Parser.
     * 
     * @return This Parser's Tokenizer.
     */
    public Tokenizer getTokenizer() {
        return tokenizer;
    }

    /**
     * Tries to parse an &lt;expression&gt;.
     * <pre>&lt;expression&gt; ::= &lt;term&gt;
     *               | &lt;term&gt; &lt;add_operator&gt; &lt;expression&gt;</pre>
     * A <code>RuntimeException</code> will be thrown if the add_operator
     * is present but not followed by a valid &lt;expression&gt;.
     * @return <code>true</code> if an expression is recognized.
     */
    public boolean expression() {
        if (!term())
            return false;
        while (addOperator()) {
            if (!term())
                error("Error in expression after '+' or '-'");
            makeTree(2, 3, 1);
        }
        return true;
    }
    
    /**
     * Recognizes a comma-separated list of zero or more expressions,
     * and always returns <code>true</code>.
     * 
     * @return <code>true</code>.
     */
    public boolean listOfExpressions() {
        // Similar to listOfVariables(), but expressions are separated by commas
        return false;
    }

    /**
     * Tries to parse a &lt;term&gt;.
     * <pre>&lt;term&gt; ::= &lt;factor&gt;
     *         | &lt;factor&gt; &lt;multiply_operator&gt; &lt;term&gt;</pre>
     * A <code>RuntimeException</code> will be thrown if the multiply_operator
     * is present but not followed by a valid &lt;term&gt;.
     * @return <code>true</code> if a term is recognized.
     */
    public boolean term() {
        if (!factor())
            return false;
        while (multiplyOperator()) {
            if (!factor())
                error("No term after '*' or '/'");
            makeTree(2, 3, 1);
        }
        return true;
    }

    /**
     * Tries to parse a &lt;factor&gt;.
     * <pre>&lt;factor&gt; ::= &lt;name&gt;
     *           | &lt;number&gt;
     *           | "(" &lt;expression&gt; ")"</pre>
     * A <code>RuntimeException</code> will be thrown if the opening
     * parenthesis is present but not followed by a valid
     * &lt;expression&gt; and a closing parenthesis.
     * @return <code>true</code> if a factor is recognized.
     */
    public boolean factor() {
        if (name())
            return true;
        if (number())
            return true;
        if (symbol("(")) {
            stack.pop();
            if (!expression())
                error("Error in parenthesized expression");
            if (!symbol(")"))
                error("Unclosed parenthetical expression");
            stack.pop();
            return true;
        }
        return false;
    }

    /**
     * Tries to parse an &lt;add_operator&gt;.
     * <pre>&lt;add_operator&gt; ::= "+" | "-"</pre>
     * @return <code>true</code> if an addop is recognized.
     */
    public boolean addOperator() {
        return symbol("+") || symbol("-");
    }

    /**
     * Tries to parse a &lt;multiply_operator&gt;.
     * <pre>&lt;multiply_operator&gt; ::= "*" | "/"</pre>
     * @return <code>true</code> if a multiply_operator is recognized.
     */
    public boolean multiplyOperator() {
        return symbol("*") || symbol("/");
    }
    
    /**
     * Tries to parse a &lt;variable&gt;, which is just a "name".
     * 
     * @return <code>true</code> if a variable is recognized.
     */
    public boolean variable() {
        return name();
    }
    
    /**
     * Recognizes a list of zero or more variables, and always
     * returns <code>true</code>.
     * 
     * @return <code>true</code>.
     */
    public boolean listOfVariables() {
        stack.push(new Tree<Token>(LIST_TOKEN));
        while (variable()) {
            makeTree(2, 1);
        }
        return true;
    }
    
    public boolean program() {
        return false;
    }
    
    public boolean command() {
        return false;
    }
    
    /**
     * Recognizes a list of zero or more commands, and always
     * returns <code>true</code>.
     * 
     * @return <code>true</code>.
     */
    public boolean listOfCommands() {
        // Similar to listOfVariables()
        return false;
    }
    
    public boolean penup() {
        return false;
    }

    public boolean pendown() {
        return false;
    }
    
    public boolean color() {
        return false;
    }

    public boolean home() {
        return false;
    }
    
    public boolean set() {
        return false;
    }
    
    public boolean block() {
        return false;
    }
    
    public boolean repeatCommand() {
        return false;
    }
    
    public boolean whileCommand() {
        return false;
    }
    
    public boolean ifCommand() {
        return false;
    }
    
    public boolean call() {
        return false;
    }
    
    public boolean move() {
        return false;
    }
    
    public boolean condition() {
        return false;
    }
    
    public boolean comparator() {
        return false;
    }
    
    public boolean procedure() {
        return false;
    }
    
    /**
     * Recognizes a list of zero or more procedures, and always
     * returns <code>true</code>.
     * 
     * @return <code>true</code>.
     */
    public boolean listOfProcedures() {
        // Similar to listOfVariables()
        return false;
    }
        
    /**
     * Matches one or more EOLs but does <b>not</b> leave them
     * on the stack.
     * 
     * @return True if an EOL is the next token.
     */
    public boolean end() {
        return false;
    }
    
    //------------------------- Private "helper" methods

    /**
     * Tests whether the next token is a number. If it is, the token
     * is consumed, otherwise it is not.
     * 
     * @return <code>true</code> if the next token is a number.
     */
    private boolean number() {
        return nextTokenMatches(TokenType.NUMBER);
    }

    /**
     * Tests whether the next token is a name. If it is, the token
     * is consumed, otherwise it is not.
     * 
     * @return <code>true</code> if the next token is a name.
     */
    private boolean name() {
        return nextTokenMatches(TokenType.NAME);
    }

    /**
     * Tests whether the next token is the expected name. If it is, the token
     * is consumed, otherwise it is not.
     * 
     * @param expectedName The String value of the expected next token.
     * @return <code>true</code> if the next token is a name with the expected value.
     */
    private boolean name(String expectedName) {
        return nextTokenMatches(TokenType.NAME, expectedName);
    }

    /**
     * Tests whether the next token is the expected keyword. If it is,
     * the token is consumed, otherwise it is not.
     * 
     * @param expectedName The String value of the expected next token.
     * @return <code>true</code> if the next token is a name with the
     *        expected value.
     */
    private boolean keyword(String expectedName) {
        return nextTokenMatches(TokenType.KEYWORD, expectedName);
    }

    /**
     * Tests whether the next token is the expected symbol. If it is,
     * the token is consumed, otherwise it is not.
     * 
     * @return <code>true</code> if the next token is the expected symbol.
     */
    private boolean symbol(String expectedSymbol) {
        return nextTokenMatches(TokenType.SYMBOL, expectedSymbol);
    }

    /**
     * If the next Token has the expected type, it is used as the
     * value of a new (childless) Tree node, and that node
     * is then pushed onto the stack. If the next Token does not
     * have the expected type, this method effectively does nothing.
     * 
     * @param type The expected type of the next token.
     * @return <code>true</code> if the next token has the expected type.
     */
    private boolean nextTokenMatches(TokenType type) {
        Token t = tokenizer.next();
        if (t.getType() == type) {
            stack.push(new Tree(t));
            return true;
        }
        else
            tokenizer.backUp();
        return false;
    }

    /**
     * If the next Token has the expected type and value, it is used as
     * the value of a new (childless) Tree node, and that node
     * is then pushed onto the stack; otherwise, this method does
     * nothing.
     *
     * @param type The expected type of the next token.
     * @param value The expected value of the next token; must
     *              not be <code>null</code>.
     * @return <code>true</code> if the next token has the expected type.
     */
    private boolean nextTokenMatches(TokenType type, String value) {
        Token t = tokenizer.next();
        if (type == t.getType() && value.equals(t.getValue())) {
            stack.push(new Tree<Token>(t));
            return true;
        }
        else {
            tokenizer.backUp();
        }
        return false;
    }

    /**
     * Assembles some number of elements from the top of the global stack
     * into a new Tree, and replaces those elements with the new Tree.<p>
     * <b>Caution:</b> The arguments must be consecutive integers 1..N,
     * in any order, but with no gaps; for example, makeTree(2,4,1,5)
     * would cause problems (3 was omitted).
     * <p>Example: If the stack contains</p><pre>
     * 1  |  A  |                                     |    B    |       
     * 2  |  B  |                                     |   / \   |
     * 3  |  C  |  then makeTree(2, 3, 1) results in  |  C   A  |
     *    | ... |                                     |   ...   |
     *    |_____|                                     |_________|
     * @param rootIndex Which stack element (counting from top=1) to use as
     * the root of the new Tree.
     * @param childIndices Which stack elements to use as the children
     * of the root.
     */    
    private void makeTree(int rootIndex, int... childIndices) {
        // Get root from stack
        Tree<Token> root = getStackItem(rootIndex);
        // Get other trees from stack and add them as children of root
        for (int i = 0; i < childIndices.length; i++) {
            root.addChild(getStackItem(childIndices[i]));
        }
        // Pop root and all children from stack
        for (int i = 0; i <= childIndices.length; i++) {
            stack.pop();
        }
        // Put the root back on the stack
        stack.push(root);
    }
      
    /**
     * Returns, as a Tree, the nth element from the top of the
     * instance variable <code>stack</code> (the top element is 1).
     * 
     * @param n Which element of the stack, counting
     *          1 as the top element, to return.
     * @return The indicated stack element.
     */
    private Tree<Token> getStackItem(int n) {
        return stack.get(stack.size() - n);
    }

    /**
     * Utility routine to throw a <code>RuntimeException</code> with the
     * given message.
     * @param message The text to put in the <code>RuntimeException</code>.
     */
    private void error(String message) {
        if (DEBUG) {
            System.out.println("Stack = " + stack + " <--(top)");
            for (int i = 0; i < stack.size(); i++) {
                System.out.println("Stack " + i + ":");
                stack.get(i).print();
            }
        }
        throw new RuntimeException(message + "; stack = " + stack);
    }
}