/* $Id$ */

/*
 * Copyright (C) 2005-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 <cstdio>
#include <cstdlib>
#include <cstring>

#include "mtx.h"
#include "mtxinteger.h"

MtxInteger::MtxInteger ()
{
  digits = NULL;
  setDigits ("0");
}

MtxInteger::MtxInteger (int integer)
{
  char *tmp;

  digits = NULL;
  tmp = parseInt (integer);
  setDigits (tmp);
  delete [] tmp;
}

MtxInteger::MtxInteger (unsigned int integer)
{
  char *tmp;

  digits = NULL;
  tmp = parseInt (integer);
  setDigits (tmp);
  delete [] tmp;
}

MtxInteger::MtxInteger (double integer)
{
  char *tmp;

  digits = NULL;
  tmp = parseDouble (integer);
  setDigits (tmp);
  delete [] tmp;
}

MtxInteger::MtxInteger (const char *digits)
{
  this->digits = NULL;
  setDigits (digits);
}

MtxInteger::MtxInteger (const MtxInteger &integer)
{
  digits = NULL;
  setDigits (integer.digits);
  sign = integer.sign;
}

MtxInteger::~MtxInteger ()
{
  delete [] digits;
}

MtxInteger &
MtxInteger::operator= (const MtxInteger &integer)
{
  if (this != &integer)
    {
      setDigits (integer.digits);
      sign = integer.sign;
    }

  return *this;
}

MtxInteger
MtxInteger::operator+ () const
{
  return MtxInteger (*this);
}

MtxInteger
MtxInteger::operator- () const
{
  MtxInteger new_integer (*this);

  new_integer.sign = ((new_integer.sign == MTX_POSITIVE)
                      && (new_integer != 0))
                   ? MTX_NEGATIVE
                   : MTX_POSITIVE;
  return new_integer;
}

static int
charToInt (char c)
{
  switch (c)
    {
      case '0' :
        return 0;
        break;
      case '1' :
        return 1;
        break;
      case '2' :
        return 2;
        break;
      case '3' :
        return 3;
        break;
      case '4' :
        return 4;
        break;
      case '5' :
        return 5;
        break;
      case '6' :
        return 6;
        break;
      case '7' :
        return 7;
        break;
      case '8' :
        return 8;
        break;
      case '9' :
        return 9;
        break;
    }

  return -1;
}

static char
intToChar (int n)
{
  switch (n)
    {
      case 0 :
        return '0';
        break;
      case 1 :
        return '1';
        break;
      case 2 :
        return '2';
        break;
      case 3 :
        return '3';
        break;
      case 4 :
        return '4';
        break;
      case 5 :
        return '5';
        break;
      case 6 :
        return '6';
        break;
      case 7 :
        return '7';
        break;
      case 8 :
        return '8';
        break;
      case 9 :
        return '9';
        break;
    }

  return -1;
}

bool
MtxInteger::operator== (const MtxInteger &integer) const
{
  if (sign == integer.sign && strcmp (digits, integer.digits) == 0)
    return true;

  else
    return false;
}

bool
MtxInteger::operator!= (const MtxInteger &integer) const
{
  return !(*this == integer);
}

bool
MtxInteger::operator> (const MtxInteger &integer) const
{
  if (this == &integer)
    return false;

  else if (*this == integer)
    return false;

  else if (sign != integer.sign)
    {
      if (sign == MTX_POSITIVE)
        return true;

      else
        return false;
    }

  else
    {
      size_t i, length, length1, length2;
      bool result;
      int a, b;

      length1 = strlen (digits);
      length2 = strlen (integer.digits);
      length = (length1 > length2) ? length1 : length2;

      for (i = 0; i < length; i++)
        {
          a = ((length - length1) > i)
              ? 0
              : charToInt (digits[i - (length - length1)]);
          b = ((length - length2) > i)
              ? 0
              : charToInt (integer.digits[i - (length - length2)]);

          if (a != b)
            {
              if (a > b)
                result = true;

              else
                result = false;

              if (sign == MTX_POSITIVE)
                return result;

              else
                return !result;
            }
        }

      return false;
    }
}

bool
MtxInteger::operator>= (const MtxInteger &integer) const
{
  return (*this > integer || *this == integer);
}

bool
MtxInteger::operator< (const MtxInteger &integer) const
{
  return integer > *this;
}

bool
MtxInteger::operator<= (const MtxInteger &integer) const
{
  return (*this < integer || *this == integer);
}

MtxInteger
MtxInteger::operator+ (const MtxInteger &integer) const
{
  if (sign != integer.sign)
      return *this - (-integer);

  else
    {
      size_t i, length, length1, length2;
      MtxInteger new_integer;
      int a, b, c, tmp_int;
      char *tmp;

      length1 = strlen (digits);
      length2 = strlen (integer.digits);

      /*
       * Allocate enough memory for any possible decimal addition.
       */
      length = ((length1 > length2) ? length1 : length2) + 1;
      tmp = new char[length + 1];
      tmp[length] = '\0';
      tmp_int = 0;

      for (i = 0; i < length; i++)
        {
          a = (i >= length1)
              ? 0
              : charToInt (digits[length1 - 1 - i]);
          b = (i >= length2)
              ? 0
              : charToInt (integer.digits[length2 - 1 - i]);
          c = a + b + tmp_int;
          tmp_int = c / 10;

          if (tmp_int)
            c -= 10;

          tmp[length - 1 - i] = intToChar (c);
        }

      new_integer.setDigits (tmp);

      delete [] tmp;

      if (sign == MTX_POSITIVE)
        return new_integer;

      else
        return -new_integer;
    }
}

MtxInteger &
MtxInteger::operator++ ()
{
  *this = *this + 1;
  return *this;
}

MtxInteger &
MtxInteger::operator++ (int a)
{
  *this = *this + 1;
  return *this;
}

MtxInteger &
MtxInteger::operator+= (const MtxInteger &integer)
{
  *this = *this + integer;
  return *this;
}

MtxInteger
MtxInteger::operator- (const MtxInteger &integer) const
{
  if (sign != integer.sign)
    return *this + (-integer);

  else
    {
      size_t i, length, length1, length2;
      const MtxInteger *i1, *i2;
      MtxInteger new_integer;
      int a, b, c, tmp_int;
      char *tmp;

      if (abs() >= integer.abs ())
        {
          i1 = this;
          i2 = &integer;
        }

      else
        {
          i1 = &integer;
          i2 = this;
        }

      length1 = strlen (i1->digits);
      length2 = strlen (i2->digits);
      length = (length1 > length2) ? length1 : length2;
      tmp = new char[length + 1];
      tmp[length] = '\0';
      tmp_int = 0;

      for (i = 0; i < length; i++)
        {
          a = (i >= length1)
              ? 0
              : charToInt (i1->digits[length1 - 1 - i]);
          b = (i >= length2)
              ? 0
              : charToInt (i2->digits[length2 - 1 - i]);
          c = a - (b + tmp_int);

          if (c < 0)
            {
              tmp_int = 1;
              c += 10;
            }

          else
            tmp_int = 0;

          tmp[length - 1 - i] = intToChar (c);
        }

      new_integer.setDigits (tmp);

      delete [] tmp;

      if (i1 == &integer)
        new_integer = -new_integer;

      if (sign == MTX_POSITIVE)
        return new_integer;

      else
        return -new_integer;
    }
}

MtxInteger &
MtxInteger::operator-- ()
{
  *this = *this - 1;
  return *this;
}

MtxInteger &
MtxInteger::operator-- (int a)
{
  *this = *this - 1;
  return *this;
}

MtxInteger &
MtxInteger::operator-= (const MtxInteger &integer)
{
  *this = *this - integer;
  return *this;
}

MtxInteger
MtxInteger::operator* (const MtxInteger &integer) const
{
  if (*this == 0 || integer == 0)
    return 0;

  else if (*this == 1)
    return integer;

  else if (integer == 1)
    return *this;

  else
    {
      size_t i, j, length1, length2;
      MtxInteger new_integer;

      length1 = strlen (digits);
      length2 = strlen (integer.digits);

      for (i = 1; i <= length1; i++)
        for(j = 1; j <= length2; j++)
          new_integer += pot (charToInt (digits[length1 - i])
                              * charToInt (integer.digits[length2 - j]),
                                   (i - 1) + (j - 1));

      if(sign == integer.sign)
        return new_integer;

      else
        return -new_integer;
    }
}

MtxInteger &
MtxInteger::operator*= (const MtxInteger &integer)
{
  *this = *this * integer;
  return *this;
}

MtxInteger
MtxInteger::divideByTwo () const
{
  MtxInteger new_integer;
  int a, n, tmp_int;
  size_t i, length;
  char *tmp;

  length = strlen (digits);
  tmp = new char[length + 1];
  tmp[length] = '\0';
  tmp_int = 0;

  for (i = 0; i < length; i++)
    {
      n = charToInt (digits[i]);

      switch (tmp_int + n)
        {
          case 0 : case 1 :
            a = '0';
            break;
          case 2 : case 3 :
            a = '1';
            break;
          case 4 : case 5 :
            a = '2';
            break;
          case 6 : case 7 :
            a = '3';
            break;
          case 8 : case 9 :
            a = '4';
            break;
          case 10 : case 11 :
            a = '5';
            break;
          case 12 : case 13 :
            a = '6';
            break;
          case 14 : case 15 :
            a = '7';
            break;
          case 16 : case 17 :
            a = '8';
            break;
          case 18 : case 19 :
            a = '9';
            break;
        }

      tmp_int = n % 2;

      if (tmp_int)
        tmp_int = 10;

      tmp[i] = a;
    }

  new_integer.setDigits (tmp);
  delete [] tmp;
  new_integer.sign = sign;
  return new_integer;
}

MtxInteger
MtxInteger::divide (const MtxInteger &integer, bool modulo0) const
{
  /*
   * TODO: When I know how to use exceptions ... :-)
   */
  if (integer == 0)
    return 0;

  else if (*this == 0)
    return 0;

  else if (*this == integer)
    {
      if (modulo0)
        return 0;

      else
        return 1;
    }

  else if (*this == -integer)
    {
      if (modulo0)
        return 0;

      else
        return -1;
    }

  else if (integer == 1)
    {
      if (modulo0)
        return 0;

      else
        return *this;
    }

  else if (integer == -1)
    {
      if (modulo0)
        return 0;

      else
        return -*this;
    }

  else if (abs () < integer.abs ())
    {
      if (modulo0)
        return *this;

      else
        return 0;
    }

  else
    {
      MtxInteger inf, sup, tmp, result, this_abs, integer_abs, modulo;

      this_abs = abs ();
      integer_abs = integer.abs ();
      inf = 0;
      sup = this_abs;

      do
        {
          result = inf + (sup - inf).divideByTwo ();
          tmp = result * integer_abs;

          if (tmp > this_abs)
            sup = result;

          else
            {
              modulo = this_abs - tmp;

              if (modulo < integer_abs)
                break;

              inf = result;
            }
        } while(true);

      if (modulo0)
        {
          if (sign == MTX_POSITIVE)
            return modulo;

          else
            return -modulo;
        }

      else
        {
          if (sign == integer.sign)
            return result;

          else
            return -result;
        }
    }
}

MtxInteger
MtxInteger::operator/ (const MtxInteger &integer) const
{
  return divide (integer, false);
}

MtxInteger &
MtxInteger::operator/= (const MtxInteger &integer)
{
  *this = *this / integer;
  return *this;
}

MtxInteger
MtxInteger::operator% (const MtxInteger &integer) const
{
  return divide (integer, true);
}

MtxInteger &
MtxInteger::operator%= (const MtxInteger &integer)
{
  *this = *this % integer;
  return *this;
}

int
MtxInteger::getSign () const
{
  return sign;
}

MtxInteger
MtxInteger::abs () const
{
  MtxInteger new_integer (*this);

  new_integer.sign = MTX_POSITIVE;
  return new_integer;
}

void
MtxInteger::setDigits (const char *digits)
{
  size_t size;

  /*
   * this->digits must be NULL or a pointer to an already allocated area.
   */
  delete [] this->digits;

  /*
   * TODO: When I know how to use exceptions in C++, implement format
   * checking here.
   */

  if (digits[0] == '-')
    {
      sign = MTX_NEGATIVE;
      digits++;
    }

  else
    {
      sign = MTX_POSITIVE;

      if (digits[0] == '+')
        digits++;
    }

  while (*digits == '0')
    digits++;

  if (*digits == '\0')
    {
      digits--;
      sign = MTX_POSITIVE;
    }

  size = strlen (digits);
  this->digits = new char[size + 1];
  strncpy (this->digits, digits, size);
  this->digits[size] = '\0';
}

char *
MtxInteger::toString () const
{
  char *string, *ptr;
  size_t length;

  length = strlen (digits);

  if (sign == MTX_NEGATIVE)
    length++;

  string = new char[length + 1];

  if (sign == MTX_NEGATIVE)
    {
      *string = '-';
      ptr = string + 1;
    }

  else
    ptr = string;

  strcpy (ptr, digits);
  return string;
}

int
MtxInteger::toInt () const
{
  int integer;

  integer = atoi (digits);

  if (sign == MTX_NEGATIVE)
    integer = -integer;

  return integer;
}

char *
MtxInteger::parseInt (int n)
{
  char *tmp;
  int size;

  size = snprintf (NULL, 0, "%d", n) + 1;
  tmp = new char[size];
  snprintf (tmp, size, "%d", n);
  return tmp;
}

char *
MtxInteger::parseInt (unsigned int n)
{
  char *tmp;
  int size;

  size = snprintf (NULL, 0, "%u", n) + 1;
  tmp = new char[size];
  snprintf (tmp, size, "%u", n);
  return tmp;
}

char *
MtxInteger::parseDouble (double d)
{
  char *tmp;
  int size;

  size = snprintf (NULL, 0, "%.0f", d) + 1;
  tmp = new char[size];
  snprintf (tmp, size, "%.0f", d);
  return tmp;
}

MtxInteger
MtxInteger::pot (int integer0, unsigned int power)
{
  MtxInteger integer, new_integer;
  size_t length, length1;
  char *tmp, *ptr;

  integer = integer0;
  length1 = strlen (integer.digits);
  length = length1 + power;
  tmp = new char[length + 1];
  tmp[length] = '\0';
  ptr = tmp;
  memcpy (ptr, integer.digits, length1);
  ptr += length1;
  memset (ptr, '0', power);
  new_integer.setDigits (tmp);
  new_integer.sign = integer.sign;
  return new_integer;
}

MtxInteger
MtxInteger::gcd (MtxInteger a, MtxInteger b)
{
  MtxInteger tmp;

  a = a.abs ();
  b = b.abs ();

  while (b != 0)
    {
      tmp = b;
      b = a % b;
      a = tmp;
    }

  return a;
}