import java.util.NoSuchElementException;
import java.util.HashMap;
import java.io.*;

/**
 * A data object representing a Jam token
 */
interface Token {
}

/** Token classes */

/**
 * The illegal token class used by the lexer for reserved words.
 */
class VoidToken implements Token {
    /**
     * Singleton instance.
     */

    static final VoidToken ONLY = new VoidToken();

    /**
     * Singleton constructor.
     */
    private VoidToken() {
    }
}

/**
 * The singleton class representing the Jam token "null".
 */
class NullConstant implements Token, Constant {
    /**
     * Singleton instance.
     */
    public static final NullConstant ONLY = new NullConstant();

    /**
     * Singleton constructor.
     */
    private NullConstant() {
    }

    /**
     * Visitor hook.
     * @param v visitor to execute
     * @return visitor-specific return value
     */
    public <T> T accept(ASTVisitor<T> v) {
        return v.forNullConstant(this);
    }

    /**
     * Return the string representation.
     * @return string representation
     */
    public String toString() {
        return "null";
    }
}

/**
 * The class that represents Jam variables; they are only created by the Lexer which guarantees that they are unique.
 */
class Variable implements Token, Term, WithVariable {
    /**
     * Variable name.
     */
    private String name;

    /**
     * Constructor for a Variable.
     * @param n name
     */
    Variable(String n) {
        name = n;
    }

    /**
     * Accessor for the variable.
     * @return returns this
     */
    public Variable var() {
        return this;
    }

    /**
     * Accessor for the name.
     * @return name
     */
    public String name() {
        return name;
    }

    /**
     * Visitor hook.
     * @param v visitor to execute
     * @return visitor-specific return value
     */
    public <RtnType> RtnType accept(ASTVisitor<RtnType> v) {
        return v.forVariable(this);
    }

    /**
     * Return the string representation.
     * @return string representation
     */
    public String toString() {
        return name;
    }
}

/**
 * The class representing operator tokens.
 */
class OpToken implements Token {
    /**
     * Symbol.
     */
    private String symbol;

    /**
     * True if this operator is unary.
     */
    private boolean isUnOp;

    /**
     * True if this operator is binary.
     */
    private boolean isBinOp;

    /**
     * The corresponding unary operator in UnOp.
     */
    private UnOp unOp;

    /**
     * The corresponding binary operator in BinOp.
     */
    private BinOp binOp;

    /**
     * Constructor for a new OpToken.
     * @param s syombol
     * @param iu is this unary?
     * @param ib is this binary?
     * @param u unary operator
     * @param b binary operator
     */
    private OpToken(String s, boolean iu, boolean ib, UnOp u, BinOp b) {
        symbol = s;
        isUnOp = iu;
        isBinOp = ib;
        unOp = u;
        binOp = b;
    }

    /**
     * Factory method for constructing OpToken serving as both UnOp and BinOp.
     * @param s symbol
     * @param u unary operator
     * @param b binary operator
     * @return operator token
     */
    public static OpToken newBothOpToken(String s, UnOp u, BinOp b) {
        return new OpToken(s, true, true, u, b);
    }

    /**
      * Factory method for constructing OpToken serving as BinOp only.
      * @param s symbol
      * @param b binary operator
      * @return operator token
      */
    public static OpToken newBinOpToken(String s, BinOp b) {
        return new OpToken(s, false, true, null, b);
    }

    /**
      * Factory method for constructing OpToken serving as UnOp only.
      * @param s symbol
      * @param u unary operator
      * @return operator token
      */
    public static OpToken newUnOpToken(String s, UnOp u) {
        return new OpToken(s, true, false, u, null);
    }

    /**
     * Accessor for the symbol.
     * @return symbol.
     */
    public String symbol() {
        return symbol;
    }

    /**
     * Is this a unary operator?
     * @return true if this token represents a unary operator
     */
    public boolean isUnOp() {
        return isUnOp;
    }

    /**
     * Is this a binary operator?
     * @return true if this token represents a binary operator
     */
    public boolean isBinOp() {
        return isBinOp;
    }

    /**
     * Return the corresponding unary operator.
     * @return unary operator.
     */
    public UnOp toUnOp() {
        if (unOp == null) {
            throw new NoSuchElementException("OpToken " + this + " does not denote a unary operator");
        }
        return unOp;
    }

    /**
     * Return the corresponding binary operator.
     * @return unary operator.
     */
    public BinOp toBinOp() {
        if (binOp == null) {
            throw new NoSuchElementException("OpToken " + this + " does not denote a binary operator");
        }
        return binOp;
    }

    /**
     * Return the string representation.
     * @return string representation
     */
    public String toString() {
        return symbol;
    }
}

/**
 * Class representing keyword tokens.
 */
class KeyWord implements Token {
    /**
     * Name.
     */
    private String name;

    /**
     * Constructor for new Keyword tokens.
     * @param n name
     */
    KeyWord(String n) {
        name = n;
    }

    /**
     * Accessor for the name.
     * @return name
     */
    public String name() {
        return name;
    }

    /**
     * Return the string representation.
     * @return string representation
     */
    public String toString() {
        return name;
    }
}

/**
 * Class for the ( token.
 */
class LeftParen implements Token {
    /**
     * Return the string representation.
     * @return string representation
     */
    public String toString() {
        return "(";
    }

    /**
     * Singleton constructor.
     */
    private LeftParen() {
    }

    /**
     * Singleton instance.
     */
    public static final LeftParen ONLY = new LeftParen();
}

/**
 * Class for the ) token.
 */
class RightParen implements Token {
    /**
     * Return the string representation.
     * @return string representation
     */
    public String toString() {
        return ")";
    }

    /**
     * Singleton constructor.
     */
    private RightParen() {
    }

    /**
     * Singleton instance.
     */
    public static final RightParen ONLY = new RightParen();
}

/**
 * Class for the [ token.
 */
class LeftBrack implements Token {
    /**
     * Return the string representation.
     * @return string representation
     */
    public String toString() {
        return "[";
    }

    /**
     * Singleton constructor.
     */
    private LeftBrack() {
    }

    /**
     * Singleton instance.
     */
    public static final LeftBrack ONLY = new LeftBrack();
}

/**
 * Class for the ] token.
 */
class RightBrack implements Token {
    /**
     * Return the string representation.
     * @return string representation
     */
    public String toString() {
        return "]";
    }

    /**
     * Singleton constructor.
     */
    private RightBrack() {
    }

    /**
     * Singleton instance.
     */
    public static final RightBrack ONLY = new RightBrack();
}

/**
 * Class for the { token.
 */
class LeftBrace implements Token {
    /**
     * Return the string representation.
     * @return string representation
     */
    public String toString() {
        return "{";
    }

    /**
     * Singleton constructor.
     */
    private LeftBrace() {
    }

    /**
     * Singleton instance.
     */
    public static final LeftBrace ONLY = new LeftBrace();
}

/**
 * Class for the } token.
 */
class RightBrace implements Token {
    /**
     * Return the string representation.
     * @return string representation
     */
    public String toString() {
        return "}";
    }

    /**
     * Singleton constructor.
     */
    private RightBrace() {
    }

    /**
     * Singleton instance.
     */
    public static final RightBrace ONLY = new RightBrace();
}

/**
 * Class for the , token.
 */
class Comma implements Token {
    /**
     * Return the string representation.
     * @return string representation
     */
    public String toString() {
        return ",";
    }

    /**
     * Singleton constructor.
     */
    private Comma() {
    }

    /**
     * Singleton instance.
     */
    public static final Comma ONLY = new Comma();
}

/**
 * Class for the ; token.
 */
class SemiColon implements Token {
    /**
     * Return the string representation.
     * @return string representation
     */
    public String toString() {
        return ";";
    }

    /**
     * Singleton constructor.
     */
    private SemiColon() {
    }

    /**
     * Singleton instance.
     */
    public static final SemiColon ONLY = new SemiColon();
}

/**
 * Jam lexer class. Given a Lexer object, the next token in that input stream being processed by the Lexer is returned
 * by static method readToken(); it throws a ParseException (an extension of IOException) if it encounters a syntax
 * error.  Calling readToken() advances the cursor in the input stream to the next token.
 * <p/>
 * The static method peek() in the Lexer class has the same behavior as readToken() except for the fact that it does not
 * advance the cursor.
 */
class Lexer extends StreamTokenizer {
    /**
     * The wordtable for classifying words (identifiers/operators) in token stream
     */
    public HashMap<String, Token> wordTable = new HashMap<String, Token>();

    /* Lexer peek() method cannot be implemented using StreamTokenizer pushBack
     * because some Tokens are composed of two StreamTokenizer tokens.
     */

    /**
     * The one token buffer used to implement the peek() operation
     */
    Token buffer;

    /**
     * Constructs a Lexer for input stream in Reader r.
     * @param r Reader object
     */
    Lexer(Reader r) {
        super(new BufferedReader(r));
        initLexer();
    }

    /**
     * Constructs a Lexer for input stream in the file named filename.
     * @param fileName file name
     */
    Lexer(String fileName) throws IOException {
        this(new FileReader(fileName));
    }

    /**
     * Initializes the state of the Lexer including StreamTokenizer settings.
     */
    private void initLexer() {
        // configure StreamTokenizer portion of this
        resetSyntax();
        parseNumbers();
        ordinaryChar('-');
        slashSlashComments(true);
        wordChars('0', '9');
        wordChars('a', 'z');
        wordChars('A', 'Z');
        wordChars('_', '_');
        wordChars('?', '?');
        whitespaceChars(0, ' ');

        // `+' `-' `*' `/' `~' `=' `!' `<' `>' `&' `|' `:' `;' `,'
        // `(' `)' `[' `]'  are ordinary characters (self-delimiting)

        initWordTable();
        buffer = null;  // buffer initially empty
    }

    /**
     * Skips through the input stream until an EOL is encountered.
     */
    public void flush() throws IOException {
        eolIsSignificant(true);
        while(nextToken() != TT_EOL) {
            // eat tokens until EOL
        }
        eolIsSignificant(false);
    }

    /**
     * Returns the next token without consuming it.
     * @return next token
     */
    public Token peek() {
        if (buffer == null) {
            buffer = readToken();
        }
        return buffer;
    }

    /**
     * Performs a nextToken() operation from StreamTokenizer except for throwing an unchecked ParseException instead of
     * a checked IOException
     * @return next token
     */
    private int getToken() {
        try {
            return nextToken();
        }
        catch(IOException e) {
            throw new ParseException("IOException " + e + "thrown by nextToken()");
        }
    }

    /**
     * Reads the next token from the input stream and consumes it; Returns the Token object representing this token.
     * @return next token
     */
    public Token readToken() {

        // NOTES:
        // 1. Token representations for all Token classes except
        //    IntConstant are unique; a HashMap is used to avoid duplication.
        //    Hence, == can safely be used to compare all Tokens except IntConstants
        //    for equality.
        // 2. In some cases, a scanned Token consists of more than one StreamTokenizer token

        if (buffer != null) {
            Token token = buffer;
            buffer = null;          // clear buffer
            return token;
        }
        int tokenType = getToken();
        // Process the token returned by StreamTokenizer
        switch(tokenType) {
            case TT_NUMBER:
                int value = (int)nval;
                if (nval == (double)value) {
                    return new IntConstant(value);
                }
                throw
                new ParseException("The number " + nval + " is not a 32 bit integer");
            case TT_WORD:
                Token regToken = wordTable.get(sval);
                if (regToken == null) {
                    // must be new variable name
                    Variable newVar = new Variable(sval);
                    wordTable.put(sval, newVar);
                    return newVar;
                }
                return regToken;
            case TT_EOF:
                return null;
            case '(':
                return LeftParen.ONLY;
            case ')':
                return RightParen.ONLY;
            case '[':
                return LeftBrack.ONLY;
            case ']':
                return RightBrack.ONLY;
                // case '{': return LeftBrace.ONLY;   // Supports the addition of blocks to Jam
                // case '}': return RightBrace.ONLY;  // Supports the addition of blocks to Jam
                case ',':
                return Comma.ONLY;
            case ';':
                return SemiColon.ONLY;
            case '+':
                return wordTable.get("+");
            case '-':
                return wordTable.get("-");
            case '*':
                return wordTable.get("*");
            case '/':
                return wordTable.get("/");
            case '~':
                return wordTable.get("~");
            case '=':
                return wordTable.get("=");
            case '<':
                tokenType = getToken();
                if (tokenType == '=') {
                    return wordTable.get("<=");
                }
                // if (tokenType == '-') return wordTable.get("<-");  // Support the addition of ref cells to Jam
                pushBack();
                return wordTable.get("<");
            case '>':
                tokenType = getToken();
                if (tokenType == '=') {
                    return wordTable.get(">=");
                }
                pushBack();
                return wordTable.get(">");
            case '!':
                tokenType = getToken();
                if (tokenType == '=') {
                    return wordTable.get("!=");
                }
                throw new
                ParseException("`" + ((char)tokenType) + "' is not a legal token");
                // Support the addition of ref cells to Java (remove preceding statement)
                // pushBack();
                // return wordTable.get("!");
                case '&':
                return wordTable.get("&");
            case '|':
                return wordTable.get("|");
            case ':':{
                    tokenType = getToken();
                    if (tokenType == '=') {
                        return wordTable.get(":=");
                    }
                    pushBack();
                    throw new ParseException("`:' is not a legal token");
                }
            default:
                throw new
                ParseException("`" + ((char)tokenType) + "' is not a legal token");
        }
    }

    /**
     * Initialize the word table used by the lexer to classify Tokens.
     */
    private void initWordTable() {
        // initialize wordTable

        // constants
        // <null>  ::= null
        // <bool>  ::= true | false

        wordTable.put("null", NullConstant.ONLY);
        wordTable.put("true", BoolConstant.TRUE);
        wordTable.put("false", BoolConstant.FALSE);

        //  Install symbols constructed from self-delimiting characters

        // operators
        // <unop>  ::= <sign> | ~   // formerly | ! | ref
        // <binop> ::= <sign> | "*" | / | = | != | < | > | <= | >= | & | "|"
        // <sign>  ::= "+" | -

        //  Note: there is no class distinction between <unop> and <binop> at
        //  lexical level because of ambiguity; <sign> belongs to both

        wordTable.put("+", OpToken.newBothOpToken("+", UnOpPlus.ONLY, BinOpPlus.ONLY));
        wordTable.put("-", OpToken.newBothOpToken("-", UnOpMinus.ONLY, BinOpMinus.ONLY));
        wordTable.put("~", OpToken.newUnOpToken("~", OpTilde.ONLY));
        // Supports addition of ref cells to Jam
        // wordTable.put("!",   OpToken.newUnOpToken("!",   OpBang.ONLY));
        // wordTable.put("ref", OpToken.newUnOpToken("ref", OpRef.ONLY));

        wordTable.put("*", OpToken.newBinOpToken("*", OpTimes.ONLY));
        wordTable.put("/", OpToken.newBinOpToken("/", OpDivide.ONLY));
        wordTable.put("=", OpToken.newBinOpToken("=", OpEquals.ONLY));
        wordTable.put("!=", OpToken.newBinOpToken("!=", OpNotEquals.ONLY));
        wordTable.put("<", OpToken.newBinOpToken("<", OpLessThan.ONLY));
        wordTable.put(">", OpToken.newBinOpToken(">", OpGreaterThan.ONLY));
        wordTable.put("<=", OpToken.newBinOpToken("<=", OpLessThanEquals.ONLY));
        wordTable.put(">=", OpToken.newBinOpToken(">=", OpGreaterThanEquals.ONLY));
        wordTable.put("&", OpToken.newBinOpToken("&", OpAnd.ONLY));
        wordTable.put("|", OpToken.newBinOpToken("|", OpOr.ONLY));
        // Supports addition of ref cells to Jam
        // wordTable.put("<-",  OpToken.newBinOpToken("<-",OpGets.ONLY));

        // Install primitive functions
        // <prim>  ::= number? | function? | list? | null? | cons? ref? |
        //             arity | cons | first | rest

        wordTable.put("number?", NumberPPrim.ONLY);
        wordTable.put("function?", FunctionPPrim.ONLY);
        wordTable.put("list?", ListPPrim.ONLY);
        wordTable.put("null?", NullPPrim.ONLY);
        wordTable.put("cons?", ConsPPrim.ONLY);
//        wordTable.put("ref?", RefPPrim.ONLY);
        wordTable.put("arity", ArityPrim.ONLY);
        wordTable.put("cons", ConsPrim.ONLY);
        wordTable.put("first", FirstPrim.ONLY);
        wordTable.put("rest", RestPrim.ONLY);


        // keywords: if then else let in map to :=
        wordTable.put("if", new KeyWord("if"));
        wordTable.put("then", new KeyWord("then"));
        wordTable.put("else", new KeyWord("else"));
        wordTable.put("let", new KeyWord("let"));
        wordTable.put("in", new KeyWord("in"));
        wordTable.put("map", new KeyWord("map"));
        wordTable.put("to", new KeyWord("to"));
        wordTable.put(":=", new KeyWord(":="));
    }
}