/*
 * util.cpp
 *
 * Definitions of utility functions.
 *
 */

#include <assert.h>
#include <iostream.h>
#include "ctype.h"
#include "StackLi.h"
#include "expressionTree.h"

//
// Print out a token
//
void printExpressionTreeToken (const ExpressionTreeToken & expTreeToken)
{
    switch(expTreeToken.tokenType)
    {
    case OperatorTokenType:
        switch (expTreeToken.operatorToken)
        {
        case Plus:
            cout << "+ ";
            break;
        case Minus:
            cout << "- ";
            break;
        case Mult:
            cout << "* ";
            break;
        case Div:
            cout << "/ ";
            break;
        }
        break;
    case CellTokenType:
        cout << "["<< expTreeToken.cellID.column
            << ", " << expTreeToken.cellID.row
            << "] ";
        break;
    case LiteralTokenType:
        cout << expTreeToken.literalID << " ";
        break;
    default:
        // This case should NEVER happen
        assert(false);
        break;
    }
}

//
// isOperator
//
// Returns true if the char ch is an operator of a formula.
// Current operators are: +, -, *, /, (.
//
bool isOperator (const char ch)
{
    return ((ch == '+') ||
            (ch == '-') ||
            (ch == '*') ||
            (ch == '/') ||
            (ch == '(') );
}

//
// operatorPriority
//
// Given an operator, return its priority.
//
// priorities:
// +, - : 0
// *, / : 1
// (    : 2
//
int operatorPriority (const char ch)
{
    assert (isOperator(ch));
    switch (ch)
    {
    case '+':
        return 0;
        break;
    case '-':
        return 0;
        break;
    case '*':
        return 1;
        break;
    case '/':
        return 1;
        break;
    case '(':
        return 2;
        break;

    default:
        // This case should NEVER happen
        assert(false);
        return 0;
        break;
    }
}

//
// mapToOperatorToken
//
// Given a character that represents an operator,
// return the corresponding token.
//
OperatorToken mapToOperatorToken (char ch)
{
    assert(isOperator(ch));
    switch (ch)
    {
    case '+':
        return Plus;
        break;
    case '-':
        return Minus;
        break;
    case '*':
        return Mult;
        break;
    case '/':
        return Div;
        break;
    case '(':
        return LeftParen;
        break;

    default:
        // This case should NEVER happen
        assert(false);
        return Error;  // to keep the compiler happy
        break;
    }
}


//
// isCapitalLetter
//
// Returns true if the char ch is a capital letter.
//
bool isCapitalLetter (const char ch)
{
    return ((ch >= 'A') && (ch <= 'Z'));
}

//
// getcellToken
//
// Assuming that the next text input from the istream in is
// a cell reference, read it in and set cellID's column and
// row to the cell's column and row.
// If the cell reference is invalid, cellID.row and cellID.column
// are both set to -1.
//
// A cell reference is defined to be a sequence of CAPITAL letters,
// followed by a sequence of digits (0-9).  The letters refer to
// columns as follows: A = 0, B = 1, C = 2, ..., Z = 25, AA = 26,
// AB = 27, ..., AZ = 51, BA = 52, ..., ZA = 676, ..., ZZ = 701,
// AAA = 702.  The digits represent the row number.
//
istream & getcellToken ( istream & in, CellToken & cellID)
{
    bool error = false;
    char ch;
    int column = 0;
    int row = 0;

    // get rid of leading whitespace characters
    while (in.get(ch) && isspace(ch))
    {
    }

    // read CAPITAL alphabetic characters to calculate the column
    if (!isCapitalLetter(ch))
    {
        error = true;
    }
    else
    {
        column = ch - 'A';
    }

    while (in.get(ch) && isalpha(ch))
    {
        if (!isCapitalLetter(ch))
        {
            error = true;
            break;
        }
        else
        {
            column = ((column + 1) * 26) + (ch - 'A');
        }
    }

    // read numeric characters to calculate the row
    if (!isdigit(ch))
    {
        error = true;
    }
    else
    {
        row = ch - '0';
    }

    while (in.get(ch) && isdigit(ch))
    {
        row = (row * 10) + (ch - '0');
    }

    // the next character after the last digit should be whitespace
    if (!isspace(ch))
    {
        error = true;
    }
    else
    {
        in.putback(ch);
    }

    if (error)
    {
        cellID.column = -1;
        cellID.row = -1;
    }
    else
    {
        cellID.column = column;
        cellID.row = row;
    }
    return in;
}

//
// getformula
//
// Assuming that the next text input from the istream in is
// an infix expression, read it in and put ExpressionTreeTokens onto a
// stack so that the expression, when read from the bottom of
// the stack to the top of the stack, is a postfix expression.
//
// A formula is defined as a sequence of tokens that represents
// a legal infix expression.  Tokens must be separated by at least
// one whitespace character.  The last token must be followed immediately
// by a carriage return ('\n').
//
// A token can consist of a numeric literal, a cell reference, or an
// operator (+, -, *, /).
//
// Multiplication (*) and division (/) have higher precedence than
// addition (+) and subtraction (-).  Among operations within the same
// level of precedence, grouping is from left to right.
//
// This algorithm follows the algorithm described in Weiss, pages 105-108.
//
istream & getformula( istream & in, Stack<ExpressionTreeToken> & expTreeTokenStack)
{
    bool error = false;
    char ch = ' ';

    int literalValue = 0;

    CellToken cellToken;
    int column = 0;
    int row = 0;

    ExpressionTreeToken expressionTreeToken;

    Stack<char> operatorStack;

    while (ch != '\n')
    {
        // get rid of leading whitespace characters
        while (in.get(ch) && isspace(ch))
        {
        }

        // ASSERT: ch now contains the first character of the next token.
        if (isOperator(ch))
        {
            // We found an operator token
            switch (ch)
            {
            case '+':
            case '-':
            case '*':
            case '/':
            case '(':
                // push operatorTokens onto the output stack until
                // we reach an operator on the operator stack that has
                // lower priority than the current one.
                char stackChar;
                while (!operatorStack.isEmpty() &&
                    (stackChar = operatorStack.top()) &&
                    (operatorPriority(stackChar) >= operatorPriority(ch)) &&
                    (stackChar != '(') )
                {
                    operatorStack.pop();
                    expressionTreeToken.tokenType = OperatorTokenType;
                    expressionTreeToken.operatorToken =
                        mapToOperatorToken(stackChar);
                    expTreeTokenStack.push(expressionTreeToken);

                }
                break;

            default:
                // This case should NEVER happen
                assert(false);
                break;
            }
            // push the operator on the operator stack
            operatorStack.push(ch);

            // whitespace should follow an operator
            in.get(ch);
            if (!isspace(ch))
            {
                error = true;
            }

        }
        else if (ch == ')')
        {
            char stackChar;
            // This code does not handle operatorStack underflow.
            while ((stackChar = operatorStack.topAndPop()) != '(')
            {
                // pop operators off the stack until a '(' appears
                // place the operators on the output stack
                expressionTreeToken.tokenType = OperatorTokenType;
                switch (stackChar)
                {
                case '+':
                    expressionTreeToken.operatorToken = Plus;
                    break;
                case '-':
                    expressionTreeToken.operatorToken = Minus;
                    break;
                case '*':
                    expressionTreeToken.operatorToken = Mult;
                    break;
                case '/':
                    expressionTreeToken.operatorToken = Div;
                    break;
                default:
                    // This case should NEVER happen
                    assert(false);
                    break;
                }
                expTreeTokenStack.push(expressionTreeToken);
                
            }

            // whitespace should follow a ')'
            in.get(ch);
            if (!isspace(ch))
            {
                error = true;
            }
        }
        else if (isdigit(ch))
        {
            // We found a literal token
            literalValue = ch - '0';
            while (in.get(ch) && isdigit(ch))
            {
                literalValue = (literalValue * 10) + (ch - '0');
            }
            // whitespace should follow the last digit of the literal
            if (!isspace(ch))
            {
                error = true;
            }
            else
            {
                // place the literal on the output stack
                expressionTreeToken.tokenType = LiteralTokenType;
                expressionTreeToken.literalID = literalValue;
                expTreeTokenStack.push(expressionTreeToken);
            }
        }
        else if (isCapitalLetter(ch))
        {
            // We found a cell reference token
            in.putback(ch);
            getcellToken(in, cellToken);
            if (cellToken.row == -1)
            {
                error = true;
            }
            else
            {
                // place the cell reference on the output stack
                expressionTreeToken.tokenType = CellTokenType;
                expressionTreeToken.cellID = cellToken;
                expTreeTokenStack.push(expressionTreeToken);
            }

            // whitespace should follow a cell reference
            in.get(ch);
            if (!isspace(ch))
            {
                error = true;
            }
        }
        else
        {
            error = true;
        }
    }

    // pop all remaining operators off the operator stack
    char stackChar;
    while (!operatorStack.isEmpty() &&
        (stackChar = operatorStack.topAndPop()))
    {
        expressionTreeToken.tokenType = OperatorTokenType;
        expressionTreeToken.operatorToken =
            mapToOperatorToken(stackChar);
        expTreeTokenStack.push(expressionTreeToken);
    }


    if (error)
    {
        // a parse error; return the empty stack
        expTreeTokenStack.makeEmpty();
    }

    return in;
}