/* $Id$ */

/*
 * Copyright (C) 2006 Richard Braun
 * 
 * This program is free software; you can redistribute it and/or modify
 * it under the terms of the GNU General Public License as published by
 * the Free Software Foundation; either version 2 of the License, or
 * (at your option) any later version.
 * 
 * This program is distributed in the hope that it will be useful,
 * but WITHOUT ANY WARRANTY; without even the implied warranty of
 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
 * GNU General Public License for more details.
 * 
 * You should have received a copy of the GNU General Public License
 * along with this program; if not, write to the Free Software
 * Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA  02111-1307  USA
 */

#include <string>
#include <ctype.h>

#include "mtx.h"
#include "mtxvalue.h"
#include "mtxmatrix.h"
#include "mtxsymbol.h"
#include "mtxinteger.h"
#include "mtxrational.h"
#include "mtxexception.h"
#include "mtxexpression.h"

using namespace std;

/*
 * See mtxexpression.h.
 */
struct mtx_function MtxExpression::functions[] =
{
  {"det", MTXEXPRESSION_FUNCTION_DETERMINANT, 1},
  {"inverse", MTXEXPRESSION_FUNCTION_INVERSE, 1},
  {"transpose", MTXEXPRESSION_FUNCTION_TRANSPOSE, 1},
  {"augment", MTXEXPRESSION_FUNCTION_AUGMENT, 2},
  {"lu", MTXEXPRESSION_FUNCTION_LUDECOMPOSITION, 3},
  {NULL, MTXEXPRESSION_FUNCTION_NULL}
};

/*
 * See mtxexpression.h.
 */
struct mtx_operator MtxExpression::operators[][6] =
{
  {
    {"=", MTXEXPRESSION_FUNCTION_ASSIGNMENT, MTXEXPRESSION_RIGHT_TO_LEFT},
    {"+=", MTXEXPRESSION_FUNCTION_ADD_ASSIGN, MTXEXPRESSION_RIGHT_TO_LEFT},
    {"-=", MTXEXPRESSION_FUNCTION_SUBTRACT_ASSIGN, MTXEXPRESSION_RIGHT_TO_LEFT},
    {"*=", MTXEXPRESSION_FUNCTION_MULTIPLY_ASSIGN, MTXEXPRESSION_RIGHT_TO_LEFT},
    {"/=", MTXEXPRESSION_FUNCTION_DIVIDE_ASSIGN, MTXEXPRESSION_RIGHT_TO_LEFT},
    MTXEXPRESSION_OPERATOR_NULL
  },

  {
    {"+", MTXEXPRESSION_FUNCTION_ADDITION, MTXEXPRESSION_LEFT_TO_RIGHT},
    {"-", MTXEXPRESSION_FUNCTION_SUBTRACTION, MTXEXPRESSION_LEFT_TO_RIGHT},
    MTXEXPRESSION_OPERATOR_NULL,
    MTXEXPRESSION_OPERATOR_NULL,
    MTXEXPRESSION_OPERATOR_NULL,
    MTXEXPRESSION_OPERATOR_NULL
  },

  {
    {"*", MTXEXPRESSION_FUNCTION_MULTIPLY, MTXEXPRESSION_LEFT_TO_RIGHT},
    {"/", MTXEXPRESSION_FUNCTION_DIVIDE, MTXEXPRESSION_LEFT_TO_RIGHT},
    MTXEXPRESSION_OPERATOR_NULL,
    MTXEXPRESSION_OPERATOR_NULL,
    MTXEXPRESSION_OPERATOR_NULL,
    MTXEXPRESSION_OPERATOR_NULL
  },

  {
    MTXEXPRESSION_OPERATOR_NULL,
    MTXEXPRESSION_OPERATOR_NULL,
    MTXEXPRESSION_OPERATOR_NULL,
    MTXEXPRESSION_OPERATOR_NULL,
    MTXEXPRESSION_OPERATOR_NULL,
    MTXEXPRESSION_OPERATOR_NULL
  }
};

MtxExpression::MtxExpression(MtxLanguage *language,
                             mtx_expression_t &lexical_elements,
                             bool silent)
{
  if (lexical_elements.empty())
    throw MtxException("syntax error");

  /*
   * See mtxsymbol.h.
   */
  this->language = language;
  this->silent = silent;

  if (lexical_elements.size() == 1)
    {
      string element;

      element = *lexical_elements.begin();

      if (isOperator(element))
        throw MtxException("syntax error");

      else if (isdigit(element[0]) || element[0] == '.')
        {
          if (element.find(".") != string::npos)
            expressions.push_back(new MtxSymbol(language,
                                                MtxRational(element.c_str())));

          else
            expressions.push_back(new MtxSymbol(language,
                                                MtxInteger(element.c_str())));
        }

      else if (isVariableName(element))
        expressions.push_back(new MtxSymbol(language, element));

      else
        throw MtxException("invalid variable name");

      function = MTXEXPRESSION_FUNCTION_NULL;
    }

  else
    {
      mtx_expression_t first_operand, second_operand;
      size_t i, j, index = 0;

      i = 0;

      while (operators[i][0].str != NULL)
        {
          j = 0;

          if (operators[i][0].associativity == MTXEXPRESSION_RIGHT_TO_LEFT)
            {
              mtx_expression_t::iterator iterator, min_iterator, tmp;

              iterator = lexical_elements.end();

              while (operators[i][j].str != NULL)
                {
                  min_iterator = findOperator(lexical_elements,
                                              operators[i][j].str);

                  if (min_iterator < iterator)
                    {
                      iterator = min_iterator;
                      index = j;
                    }

                  j++;
                }

              if (iterator == lexical_elements.end())
                {
                  i++;
                  index = j;
                  continue;
                }

              for (tmp = lexical_elements.begin();
                   tmp != iterator;
                   tmp++)
                first_operand.push_back(*tmp);

              for (tmp = iterator + 1;
                   tmp != lexical_elements.end();
                   tmp++)
                second_operand.push_back(*tmp);
            }

          else
            {
              mtx_expression_t::reverse_iterator iterator, min_iterator, tmp;

              iterator = lexical_elements.rend();

              while (operators[i][j].str != NULL)
                {
                  min_iterator = rfindOperator(lexical_elements,
                                               operators[i][j].str);

                  if (min_iterator < iterator)
                    {
                      iterator = min_iterator;
                      index = j;
                    }

                  j++;
                }

              if (iterator == lexical_elements.rend())
                {
                  i++;
                  index = j;
                  continue;
                }

              for (tmp = lexical_elements.rend() - 1;
                   tmp != iterator;
                   tmp--)
                first_operand.push_back(*tmp);

              for (tmp = iterator - 1;
                   tmp != lexical_elements.rbegin() - 1;
                   tmp--)
                second_operand.push_back(*tmp);
            }

          break;
        }

      /*
       * An operator was found.
       */
      if (operators[i][index].str != NULL)
        {
          function = operators[i][index].id;

          if (!((function == MTXEXPRESSION_FUNCTION_ADDITION
                 || function == MTXEXPRESSION_FUNCTION_SUBTRACTION)
                && first_operand.empty()))
            expressions.push_back(new MtxExpression(language, first_operand));

          expressions.push_back(new MtxExpression(language, second_operand));
        }

      else if (lexical_elements.size() > 2 && lexical_elements[0] == "("
               && lexical_elements.back() == ")")
        {
          lexical_elements.erase(lexical_elements.begin());
          lexical_elements.erase(lexical_elements.end() - 1);
          expressions.push_back(new MtxExpression(language, lexical_elements));
          function = MTXEXPRESSION_FUNCTION_NULL;
        }

      else if (lexical_elements[0] == "[" && lexical_elements.back() == "]")
        {
          MtxRational *rational, *rationals;
          vector<MtxSymbol *> symbols;
          size_t i, rows, columns;
          MtxMatrix matrix;
          MtxValue *value;

          lexical_elements.erase(lexical_elements.begin());
          lexical_elements.erase(lexical_elements.end() - 1);
          parseMatrix(lexical_elements, symbols, rows, columns);
          rationals = new MtxRational[rows * columns];
          i = 0;

          for (i = 0; i < symbols.size(); i++)
            {
              value = symbols[i]->getSymbol().getValue()->clone();
              rational = dynamic_cast<MtxRational *>(value);

              if (rational == NULL)
                {
                  MtxInteger *integer;

                  integer = dynamic_cast<MtxInteger *>(value);

                  if (integer == NULL)
                    {
                      delete symbols[i];
                      delete value;
                      delete[] rationals;
                      throw MtxException("matrix cell not integer or "
                                         "rational");
                    }

                  else
                    rationals[i] = *integer;
                }

              else
                rationals[i] = *rational;

              delete symbols[i];
              delete value;
            }

          expressions.push_back(new MtxSymbol(language,
                                              MtxMatrix(rationals, rows,
                                                        columns)));
          delete[] rationals;
          function = MTXEXPRESSION_FUNCTION_NULL;
        }

      else if (lexical_elements.size() > 3 && lexical_elements[1] == "("
               && lexical_elements.back() == ")")
        {
          vector<MtxSymbol *> symbols;
          size_t i;

          i = 0;

          while (functions[i].str != NULL)
            {
              if (lexical_elements[0] == functions[i].str)
                break;

              i++;
            }

          if (functions[i].str == NULL)
            throw MtxException("call to unknown function");

          function = functions[i].id;
          lexical_elements.erase(lexical_elements.begin());
          lexical_elements.erase(lexical_elements.begin());
          lexical_elements.erase(lexical_elements.end() - 1);
          parseArguments(lexical_elements, symbols);

          if (symbols.size() != functions[i].argc)
            throw MtxException("wrong number of arguments in function call");

          for (i = 0; i < symbols.size(); i++)
            expressions.push_back(symbols[i]);
        }

      else
        throw MtxException("syntax error");
    }
}

MtxExpression::~MtxExpression()
{
  vector<MtxSymbol *>::iterator iterator;

  for (iterator = expressions.begin();
       iterator != expressions.end();
       iterator++)
    delete *iterator;
}

#define MATRIX_DIMENSIONS_ERROR(symbols) \
  { \
    freeSymbols(symbols); \
    throw MtxException("number of columns mismatch at matrix creation"); \
  }

void
MtxExpression::freeSymbols(vector<MtxSymbol *> &symbols) const
{
  vector<MtxSymbol *>::iterator iterator;

  for (iterator = symbols.begin();
       iterator != symbols.end();
       iterator++)
    delete *iterator;
}

void
MtxExpression::parseMatrix(const mtx_expression_t &lexical_elements,
                           vector<MtxSymbol *> &symbols,
                           size_t &rows, size_t &columns) const
{
  mtx_expression_t::const_iterator iterator;
  size_t p_level, b_level, tmp_columns;
  mtx_expression_t tmp;

  if (lexical_elements.empty())
    throw MtxException("syntax error");

  p_level = 0;
  b_level = 0;
  rows = 0;
  columns = 0;
  tmp_columns = 0;

  for (iterator = lexical_elements.begin();
       iterator != lexical_elements.end();
       iterator++)
    {
      if (p_level == 0 && b_level == 0
          && (*iterator == "," || *iterator == ";"))
        {
          if (tmp.empty())
            throw MtxException("syntax error");

          tmp_columns++;

          if (tmp_columns == 1)
            rows++;

          if (*iterator == ",")
            {
              if (rows > 1 && tmp_columns > columns)
                MATRIX_DIMENSIONS_ERROR(symbols);
            }

          else
            {
              if (rows == 1)
                columns = tmp_columns;

              else if (tmp_columns != columns)
                MATRIX_DIMENSIONS_ERROR(symbols);

              tmp_columns = 0;
            }

          symbols.push_back(new MtxExpression(language, tmp));
          tmp.clear();
        }

      else
        {
          if (*iterator == "(")
            p_level++;

          else if (*iterator == ")")
            p_level--;

          else if (*iterator == "[")
            b_level++;

          else if (*iterator == "]")
            b_level--;

          tmp.push_back(*iterator);
        }
    }

  if (!tmp.empty())
    {
      tmp_columns++;

      if (tmp_columns == 1)
        rows++;

      if (rows == 1)
        columns = tmp_columns;

      else if (tmp_columns != columns)
        MATRIX_DIMENSIONS_ERROR(symbols);

      symbols.push_back(new MtxExpression(language, tmp));
    }

  if (symbols.size() != (rows * columns))
    MATRIX_DIMENSIONS_ERROR(symbols);
}

void
MtxExpression::parseArguments(const mtx_expression_t &lexical_elements,
                              vector<MtxSymbol *> &symbols) const
{
  mtx_expression_t::const_iterator iterator;
  size_t p_level, b_level;
  mtx_expression_t tmp;

  if (lexical_elements.empty())
    throw MtxException("syntax error");

  p_level = 0;
  b_level = 0;

  for (iterator = lexical_elements.begin();
       iterator != lexical_elements.end();
       iterator++)
    {
      if (p_level == 0 && b_level == 0 && *iterator == ",")
        {
          if (tmp.empty())
            {
              freeSymbols(symbols);
              throw MtxException("syntax error");
            }

          symbols.push_back(new MtxExpression(language, tmp));
          tmp.clear();
        }

      else
        {
          if (*iterator == "(")
            p_level++;

          else if (*iterator == ")")
            p_level--;

          else if (*iterator == "[")
            b_level++;

          else if (*iterator == "]")
            b_level--;

          tmp.push_back(*iterator);
        }
    }

  if (tmp.empty())
    {
      freeSymbols(symbols);
      throw MtxException("syntax error");
    }

  symbols.push_back(new MtxExpression(language, tmp));
}

bool
MtxExpression::isOperator(const string &str)
{
  size_t i, j;

  i = 0;

  while (operators[i][0].str != NULL)
    {
      j = 0;

      while (operators[i][j].str != NULL)
        {
          if (str == operators[i][j].str)
            return true;

          j++;
        }

      i++;
    }

  return false;
}

bool
MtxExpression::isVariableName(const string &str)
{
  size_t i;

  if (str.length() == 0)
    return false;

  if (isdigit(str[0]))
    return false;

  for (i = 0; i < str.length(); i++)
    if (!(isalnum(str[i]) || str[i] == '_'))
      return false;

  return true;
}

mtx_expression_t::iterator
MtxExpression::findOperator(mtx_expression_t &lexical_elements, const char *str)
{
  mtx_expression_t::iterator iterator;
  size_t p_level, b_level;

  p_level = 0;
  b_level = 0;

  for (iterator = lexical_elements.begin();
       iterator != lexical_elements.end();
       iterator++)
    {
      if (p_level == 0 && b_level == 0 && *iterator == str)
        return iterator;

      else
        {
          if (*iterator == "(")
            p_level++;

          else if (*iterator == ")")
            p_level--;

          else if (*iterator == "[")
            b_level++;

          else if (*iterator == "]")
            b_level--;
        }
    }

  return iterator;
}

mtx_expression_t::reverse_iterator
MtxExpression::rfindOperator(mtx_expression_t &lexical_elements,
                             const char *str)
{
  mtx_expression_t::reverse_iterator iterator;
  size_t p_level, b_level;

  p_level = 0;
  b_level = 0;

  for (iterator = lexical_elements.rbegin();
       iterator != lexical_elements.rend();
       iterator++)
    {
      if (p_level == 0 && b_level == 0 && *iterator == str)
        return iterator;

      else
        {
          if (*iterator == ")")
            p_level++;

          else if (*iterator == "(")
            p_level--;

          else if (*iterator == "]")
            b_level++;

          else if (*iterator == "[")
            b_level--;
        }
    }

  return iterator;
}

MtxSymbol
MtxExpression::getSymbol(bool create, bool fail_if_special) const

{
  if (function == MTXEXPRESSION_FUNCTION_NULL && expressions.size() == 1)
    return expressions[0]->getSymbol(create, fail_if_special);

  else
    {
      MtxMatrix *matrix, *matrix2, *matrix3;
      MtxSymbol symbol, symbol2;
      MtxValue *value;

      /*
       * XXX I usually never do this, and was a little short on time.
       */
      switch (function)
        {
          case MTXEXPRESSION_FUNCTION_NULL:
            throw MtxException("internal error: null function executed");

          case MTXEXPRESSION_FUNCTION_ASSIGNMENT:
            symbol = expressions[1]->getSymbol();
            symbol.setName(expressions[0]->getSymbol(true).getName());
            language->setSymbol(symbol);
            return symbol;

          case MTXEXPRESSION_FUNCTION_ADDITION:
            if (expressions.size() == 1)
              return expressions[0]->getSymbol();

            else
              {
                value = expressions[0]->getSymbol().getValue()->add(
                        expressions[1]->getSymbol().getValue());
                symbol = MtxSymbol(language, *value);
                delete value;
                return symbol;
              }

          case MTXEXPRESSION_FUNCTION_ADD_ASSIGN:
            value = expressions[0]->getSymbol().getValue()->add(
                    expressions[1]->getSymbol().getValue());
            symbol = MtxSymbol(language, *value);
            delete value;
            symbol.setName(expressions[0]->getSymbol(true).getName());
            language->setSymbol(symbol);
            return symbol;

          case MTXEXPRESSION_FUNCTION_SUBTRACTION:
            if (expressions.size() == 1)
              {
                value = expressions[0]->getSymbol().getValue()->opposite();
                symbol = MtxSymbol(language, *value);
                delete value;
                return symbol;
              }

            else
              {
                value = expressions[0]->getSymbol().getValue()->subtract(
                        expressions[1]->getSymbol().getValue());
                symbol = MtxSymbol(language, *value);
                delete value;
                return symbol;
              }

          case MTXEXPRESSION_FUNCTION_SUBTRACT_ASSIGN:
            value = expressions[0]->getSymbol().getValue()->subtract(
                    expressions[1]->getSymbol().getValue());
            symbol = MtxSymbol(language, *value);
            delete value;
            symbol.setName(expressions[0]->getSymbol(true).getName());
            language->setSymbol(symbol);
            return symbol;

          case MTXEXPRESSION_FUNCTION_MULTIPLY:
            value = expressions[0]->getSymbol().getValue()->multiply(
                    expressions[1]->getSymbol().getValue());
            symbol = MtxSymbol(language, *value);
            delete value;
            return symbol;

          case MTXEXPRESSION_FUNCTION_MULTIPLY_ASSIGN:
            value = expressions[0]->getSymbol().getValue()->multiply(
                    expressions[1]->getSymbol().getValue());
            symbol = MtxSymbol(language, *value);
            delete value;
            symbol.setName(expressions[0]->getSymbol(true).getName());
            language->setSymbol(symbol);
            return symbol;

          case MTXEXPRESSION_FUNCTION_DIVIDE:
            value = expressions[0]->getSymbol().getValue()->divide(
                    expressions[1]->getSymbol().getValue());
            symbol = MtxSymbol(language, *value);
            delete value;
            return symbol;

          case MTXEXPRESSION_FUNCTION_DIVIDE_ASSIGN:
            value = expressions[0]->getSymbol().getValue()->divide(
                    expressions[1]->getSymbol().getValue());
            symbol = MtxSymbol(language, *value);
            delete value;
            symbol.setName(expressions[0]->getSymbol(true).getName());
            language->setSymbol(symbol);
            return symbol;

          case MTXEXPRESSION_FUNCTION_DETERMINANT:
            value = expressions[0]->getSymbol().getValue()->clone();
            matrix = dynamic_cast<MtxMatrix *>(value);

            if (matrix == NULL)
              {
                delete value;
                throw MtxException("argument is not a matrix");
              }

            symbol = MtxSymbol(language, matrix->determinant());
            delete matrix;
            return symbol;

          case MTXEXPRESSION_FUNCTION_INVERSE:
            value = expressions[0]->getSymbol().getValue()->clone();
            matrix = dynamic_cast<MtxMatrix *>(value);

            if (matrix == NULL)
              {
                delete value;
                throw MtxException("argument is not a matrix");
              }

            symbol = MtxSymbol(language, matrix->inverted());
            delete matrix;
            return symbol;

          case MTXEXPRESSION_FUNCTION_TRANSPOSE:
            value = expressions[0]->getSymbol().getValue()->clone();
            matrix = dynamic_cast<MtxMatrix *>(value);

            if (matrix == NULL)
              {
                delete value;
                throw MtxException("argument is not a matrix");
              }

            symbol = MtxSymbol(language, matrix->transpose());
            delete matrix;
            return symbol;

          case MTXEXPRESSION_FUNCTION_AUGMENT:
            value = expressions[0]->getSymbol().getValue()->clone();
            matrix = dynamic_cast<MtxMatrix *>(value);

            if (matrix == NULL)
              {
                delete value;
                throw MtxException("argument is not a matrix");
              }

            value = expressions[1]->getSymbol().getValue()->clone();
            matrix2 = dynamic_cast<MtxMatrix *>(value);

            if (matrix2 == NULL)
              {
                delete matrix;
                delete value;
                throw MtxException("argument is not a matrix");
              }

            symbol = MtxSymbol(language, matrix->augmented(*matrix2));
            delete matrix;
            delete matrix2;
            return symbol;

          case MTXEXPRESSION_FUNCTION_LUDECOMPOSITION:
            value = expressions[0]->getSymbol().getValue()->clone();
            matrix = dynamic_cast<MtxMatrix *>(value);

            if (matrix == NULL)
              {
                delete value;
                throw MtxException("argument is not a matrix");
              }

            matrix2 = new MtxMatrix();
            matrix3 = new MtxMatrix();

            try
              {
                matrix->luDecomposition(*matrix2, *matrix3);

                symbol = MtxSymbol(language,
                                   expressions[1]->getSymbol(true).getName(),
                                   *matrix2);
                language->setSymbol(symbol);
                symbol2 = MtxSymbol(language,
                                    expressions[2]->getSymbol(true).getName(),
                                    *matrix3);
                language->setSymbol(symbol2);
              }

            catch (MtxException &exception)
              {
                delete matrix3;
                delete matrix2;
                delete matrix;
                throw exception;
              }

            delete matrix3;
            delete matrix2;
            delete matrix;
            return MtxSymbol(language, MtxInteger(1));
        }

      throw MtxException("operator/function not yet implemented");
    }
}

string
MtxExpression::getName() const
{
  return getSymbol().getName();
}

MtxValue *
MtxExpression::getValue() const
{
  return getSymbol().getValue();
}

string
MtxExpression::toString() const
{
  return getSymbol().toString();
}

bool
MtxExpression::isSilent() const
{
  return silent;
}