source: comparacioncriptosistemas/polynomial.H @ 1b57940

/*
  Copyright (C) 2015
  Alejandro Mujica (amujica en cenditel.gob.ve)
  José Ángel 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 clase tipo
  plantilla 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 con tipo de coeficientes paramétrico.
 *
 *  @param Number_Type El tipo de dato para los coeficientes. Debe pertenecer
 *                     a los tipos aritméticos de la biblioteca estándar de C++.
 *                     Por omisión es de tipo double.
 *
 *  @author Alejandro Mujica     (amujica en cenditel punto gob punto ve).
 *  @author José Angel Contreras (jancontreras en cenditel punto gob punto ve).
 */
template <typename Number_Type = double>
class Polynomial
{
public:
  /// Tipo de conjunto para el polinomio.
  typedef std::vector<Number_Type> pol_t;
  /// Tipo de número para el grado.
  typedef typename pol_t::size_type  degree_t;
  /// Tipo de número para los coeficientes.
  typedef typename pol_t::value_type number_t;

private:
  degree_t deg;
  pol_t    pol;

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

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

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

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

  /// Retorna el grado del polinomio.
  const degree_t & 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 number_t & get_coefficient(const degree_t & 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 degree_t & exp, const number_t & 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 Number_Type>
Polynomial<Number_Type>::Polynomial(const Polynomial::degree_t & _deg)
  : deg(_deg), pol(deg + degree_t(1), number_t(0))
{
  // Empty
}

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

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

template <typename Number_Type>
Polynomial<Number_Type>::Polynomial(Polynomial && p)
  : deg(degree_t(0)), pol(deg + degree_t(1), number_t(0))
{
  std::swap(deg, p.deg);
  std::swap(pol, p.pol);
}


/**
 *  Determina si un polinomio es nulo.
 *  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 Number_Type>
bool Polynomial<Number_Type>::is_null() const
{
  for (const number_t & c : pol)
    if (c != number_t(0))
      return false;
  return true;
}

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

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

  Polynomial ret(max_degree);

  for (degree_t i = degree_t(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 (degree_t i = min_degree + degree_t(1); i <= max_degree; ++i)
    ret.set_coefficient(i, max_degree_pol.get_coefficient(i));

  return ret;
}

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

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

  Polynomial ret(max_degree);

  for (degree_t i = degree_t(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 (degree_t i = min_degree + degree_t(1); i <= max_degree; ++i)
    ret.set_coefficient(i, sign * max_degree_pol.get_coefficient(i));

  return ret;
}

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

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

  for (degree_t i = degree_t(0); i <= deg; ++i)
    for (degree_t j = degree_t(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 Number_Type>
Polynomial<Number_Type>
Polynomial<Number_Type>::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);

  number_t inv = number_t(0);

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

      degree_t last = p.deg;

      while (last > degree_t(0) and p.get_coefficient(last) == number_t(0))
        --last;

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

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

          for (degree_t j = degree_t(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;
    }

  degree_t first = degree_t(0);

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

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

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

  return ret;
}

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

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

  Polynomial ret = *this;

  degree_t last = p.deg;

    while (last > degree_t(0) and p.get_coefficient(last) == number_t(0))
      --last;   

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

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

      for (degree_t j = degree_t(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 > degree_t(0) and ret.get_coefficient(ret.deg) == number_t(0))
    --ret.deg;

  return ret;
}

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

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

  return *this;
}

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

  return *this;
}

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

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

  return true;
}

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

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

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

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

  sstr << pol.at(deg);

  return sstr.str();
}

# endif // POLYNOMIAL_H