source: comparacioncriptosistemas/reescrituraDeCodigo/polynomial.H

/*
  Copyright (C) 2015
  Alejandro Mujica (amujica en cenditel.gob.ve)
  José Angel Contreras (jancontreras en cenditel.gob.ve)
  Antonio Araujo (aaraujo en cenditel.gob.ve)
  Pedro Buitrago (pbuitrago en cenditel.gob.ve)
 
  CENDITEL Fundación Centro Nacional de Desarrollo e Investigación en
  Tecnologías Libres
 
  Este programa es software libre; Usted puede usarlo bajo los términos de la
  licencia de software GPL versión 2.0 de la Free Software Foundation.
 
  Este programa se distribuye con la esperanza de que sea útil, pero SIN
  NINGUNA GARANTÍA; tampoco las implícitas garantías de MERCANTILIDAD o
  ADECUACIÓN A UN PROPÓSITO PARTICULAR.
  Consulte la licencia GPL para más detalles. Usted debe recibir una copia
  de la GPL junto con este programa; si no, escriba a la Free Software
  Foundation Inc. 51 Franklin Street,5 Piso, Boston, MA 02110-1301, USA.
*/

/*
  Este archivo contiene la definición e implementación de una plantilla de clase
  para representar polinomios.

  Creado por:        Alejandro J. Mujica
  Fecha de creación: 
*/


# ifndef POLYNOMIAL_H
# define POLYNOMIAL_H

# include <stdexcept>
# include <sstream>
# include <vector>
# include <limits>

# include<iostream>

/**
 *  Plantilla para representar polinomios de una variable.
 *
 *  @tparam NumberT Tipo de dato para los coeficientes.
 *
 *  @author Alejandro Mujica     (amujica en cenditel punto gob punto ve).
 *  @author José Angel Contreras (jancontreras en cenditel punto gob punto ve).
 */
template <typename NumberT = double>
class Polynomial
{
public:
  /// Tipo de conjunto para el polinomio.
  using PolynomialType = std::vector<NumberT>;
  /// Tipo de número para el grado.
  using DegreeType = typename PolynomialType::size_type;
  /// Tipo de número para los coeficientes.
  using NumberType = typename PolynomialType::value_type;

private:
  DegreeType     deg;
  PolynomialType pol;

public:
  /// Construcción de un polinomio dado un grado.
  Polynomial(const DegreeType & _deg = DegreeType(0));

  /// Construcción por medio de una lista de inicialización.
  Polynomial(const std::initializer_list<NumberType> &);

  /// Constructor copia
  Polynomial(const Polynomial &);

  /// Constructor de movimiento (move semantic)
  Polynomial(Polynomial &&);

  /// Retorna el grado del polinomio.
  const DegreeType & degree() const
  {
    return deg;
  }

  /**
   *  Retorna el coeficiente de la posición dada.
   *
   *  @param exp Grado del coeficiente deseado.
   *  @return Coeficiente de la posición dada.
   *  @throw overflow_error si el exponente es mayor que el grado del polinomio.
   */
  const NumberType & get_coefficient(const DegreeType & exp) const
  {
    if (exp > deg)
      throw std::overflow_error("exp is greater than polynomial degree");

    return pol.at(deg - exp);
  }

  /**
   *  Asigna valor al coeficiente de la posición dada.
   *
   *  @param exp Grado del coeficiente deseado.
   *  @param value Valor que se asignará al coeficiente.
   *  @throw overflow_error si el exponente es mayor que el grado del polinomio.
   */
  void set_coefficient(const DegreeType & exp, const NumberType & value)
  {
    if (exp > deg)
      throw std::overflow_error("exp is greater than polynomial degree");

    pol.at(deg - exp) = value;
  }

  /// Determina si el polinomio es nulo.
  bool is_null() const;

  bool operator ! () const;

  Polynomial operator + (const Polynomial &);

  Polynomial & operator += (const Polynomial &);

  Polynomial operator - (const Polynomial &);

  Polynomial & operator -= (const Polynomial &);

  Polynomial operator * (const Polynomial &);

  Polynomial operator / (const Polynomial &);

  Polynomial operator % (const Polynomial &);

  Polynomial & operator = (const Polynomial &);

  Polynomial & operator = (Polynomial &&);

  bool operator == (const Polynomial &) const;

  bool operator != (const Polynomial &) const;

  /// Retorna una representación del polinomio en cadena.
  std::string to_string(const char & var = 'x');
};

/**
 *  Constructor que funge de paramétrico y por omisión al mismo tiempo.
 *
 *  @param _deg Grado del polinomio. Por omisión es 0.
 */
template <typename NumberT>
Polynomial<NumberT>::Polynomial(const Polynomial::DegreeType & _deg)
  : deg(_deg), pol(deg + DegreeType(1), NumberType(0))
{
  // Empty
}

/**
 *  Construye un polinomio dada una lista de inicialización.
 *
 *  Para inicializar el polinomio se deben pasar los valores de los coeficientes
 *  entre llaves y separados por coma (,). Debe escribirse el polinomio
 *  completo.
 *
 *  Por ejemplo, si se quiere construir el polinomio
 *  @f$p(x) = x^5 + 2x^4 + 3x^3 + 4x^2 + 5x + 6;@f$
 *  la instanciación debe realizarse de la siguiente manera:
 *  @code{.cpp}Polynomial<> p = { 1, 2, 3, 4, 5, 6 };@endcode
 *
 *  @param l Lista de inicialización del polinomio.
 */
template <typename NumberT>
Polynomial<NumberT>::Polynomial(const std::initializer_list<NumberType> & l)
  : deg(DegreeType(l.size()) - DegreeType(1)), pol(l)
{
  // Empty
}

template <typename NumberT>
Polynomial<NumberT>::Polynomial(const Polynomial & p)
  : deg(p.deg), pol(p.pol)
{
  // Empty
}

template <typename NumberT>
Polynomial<NumberT>::Polynomial(Polynomial && p)
  : deg(DegreeType(0)), pol(deg + DegreeType(1), NumberType(0))
{
  std::swap(deg, p.deg);
  std::swap(pol, p.pol);
}


/**.
 *  Un polinomio es nulo si todos sus coeficientes son cero.
 *
 *  @return <code>true</code> si el polinomio es nulo y <code>false</code> en
 *          caso contrario.
 */
template <typename NumberT>
bool Polynomial<NumberT>::is_null() const
{
  for (const NumberType & c : pol)
    if (c != NumberType(0))
      return false;
  return true;
}

template <typename NumberT>
bool Polynomial<NumberT>::operator ! () const
{
  return is_null();
}

template <typename NumberT>
Polynomial<NumberT>
Polynomial<NumberT>::operator + (const Polynomial & p)
{
  const DegreeType & min_degree = std::min(deg, p.deg);
  const DegreeType & max_degree = std::max(deg, p.deg);

  Polynomial ret(max_degree);

  for (DegreeType i = DegreeType(0); i <= min_degree; ++i)
    ret.set_coefficient(i, get_coefficient(i) + p.get_coefficient(i));

  const Polynomial & max_degree_pol = deg > p.deg ? *this : p;

  for (DegreeType i = min_degree + DegreeType(1); i <= max_degree; ++i)
    ret.set_coefficient(i, max_degree_pol.get_coefficient(i));

  return ret;
}

template <typename NumberT>
Polynomial<NumberT> &
Polynomial<NumberT>::operator += (const Polynomial & p)
{
  *this = *this + p;
  return *this;
}

template <typename NumberT>
Polynomial<NumberT>
Polynomial<NumberT>::operator - (const Polynomial & p)
{
  const DegreeType & min_degree = std::min(deg, p.deg);
  const DegreeType & max_degree = std::max(deg, p.deg);

  Polynomial ret(max_degree);

  for (DegreeType i = DegreeType(0); i <= min_degree; ++i)
    ret.set_coefficient(i, get_coefficient(i) - p.get_coefficient(i));

  Polynomial & max_degree_pol = deg > p.deg ? *this : p;

  char sign = &max_degree_pol == this ? 1 : -1;

  for (DegreeType i = min_degree + DegreeType(1); i <= max_degree; ++i)
    ret.set_coefficient(i, sign * max_degree_pol.get_coefficient(i));

  return ret;
}

template <typename NumberT>
Polynomial<NumberT> &
Polynomial<NumberT>::operator -= (const Polynomial & p)
{
  *this = *this - p;
  return *this;
}

template <typename NumberT>
Polynomial<NumberT>
Polynomial<NumberT>::operator * (const Polynomial & p)
{
  Polynomial ret(deg + p.deg);

  for (DegreeType i = DegreeType(0); i <= deg; ++i)
    for (DegreeType j = DegreeType(0); j < p.deg; ++j)
      ret.set_coefficient(i + j,
        ret.get_coefficient(i + j) + get_coefficient(i) * p.get_coefficient(j));
        

  return ret;
}

template <typename NumberT>
Polynomial<NumberT>
Polynomial<NumberT>::operator / (const Polynomial & p)
{
  if (p.is_null())
    throw std::logic_error("Polynomial devision by 0");

  if (p.deg > deg)
    return Polynomial();

  Polynomial ret(deg - p.deg);

  NumberType inv = NumberType(0);

  if (p.deg > 0)
    {
      Polynomial tmp = *this;

      DegreeType last = p.deg;

      while (last > DegreeType(0) and p.get_coefficient(last) == NumberType(0))
        --last;

      inv = NumberType(1) / p.get_coefficient(last);

      for (DegreeType i = tmp.deg; i >= p.deg; --i)
        {
          ret.set_coefficient(i - p.deg, tmp.get_coefficient(i) * inv);

          for (DegreeType j = DegreeType(0); j <= p.deg; ++j) 
            tmp.set_coefficient(i - j,
              tmp.get_coefficient(i - j) - p.get_coefficient(p.deg - j) *
              ret.get_coefficient(i - p.deg));
        }

      return ret;
    }

  DegreeType first = DegreeType(0);

  while (first <= p.deg and p.get_coefficient(first) == NumberType(0))
    ++first;

  inv = NumberType(1) / p.get_coefficient(first);

  for (NumberType & c : ret.pol)
    c *= inv;

  return ret;
}

template <typename NumberT>
Polynomial<NumberT>
Polynomial<NumberT>::operator % (const Polynomial & p)
{
  if (p.is_null()) 
    throw std::logic_error("Polynomial denominator = 0");

  if (p.deg == DegreeType(0))
    return Polynomial();

  Polynomial ret = *this;

  DegreeType last = p.deg;

    while (last > DegreeType(0) and p.get_coefficient(last) == NumberType(0))
      --last;   

  NumberType inv = NumberType(1) / p.get_coefficient(last);

  for (DegreeType i = ret.deg; i >= p.deg; --i)
    {
      NumberType q = ret.get_coefficient(i) * inv;

      for (DegreeType j = DegreeType(0); j <= p.deg; ++j) 
        ret.set_coefficient(i - j, ret.get_coefficient(i - j) -
          p.get_coefficient(p.deg - j) * q);
    }

  while (ret.deg > DegreeType(0) and ret.get_coefficient(ret.deg) == NumberType(0))
    --ret.deg;

  return ret;
}

template <typename NumberT>
Polynomial<NumberT> &
Polynomial<NumberT>::operator = (const Polynomial & p)
{
  if (&p == this)
    return *this;

  deg = p.deg;
  pol = p.pol;

  return *this;
}

template <typename NumberT>
Polynomial<NumberT> &
Polynomial<NumberT>::operator = (Polynomial && p)
{
  std::swap(deg, p.deg);
  std::swap(pol, p.pol);

  return *this;
}

template <typename NumberT>
bool Polynomial<NumberT>::operator == (const Polynomial & p) const
{
  if (deg != p.deg)
    return false;

  for (DegreeType i = DegreeType(0); i <= deg; ++i)
    if (pol.at(i) != p.pol.at(i))
      return false;

  return true;
}

template <typename NumberT>
bool Polynomial<NumberT>::operator != (const Polynomial & p) const
{
  return not (*this == p);
}

template <typename NumberT>
std::string Polynomial<NumberT>::to_string(const char & var)
{
  std::stringstream sstr;

  if (deg > DegreeType(1))
    for (DegreeType i = DegreeType(0); i < deg - DegreeType(1); ++i)
      sstr << pol.at(i) << var << '^' << deg - i << " + ";

  if (deg > DegreeType(0))
    sstr << pol.at(deg - DegreeType(1)) << var << " + ";

  sstr << pol.at(deg);

  return sstr.str();
}

# endif // POLYNOMIAL_H