sparse_polynom.hpp

Go to the documentation of this file.

/*****************************************************************************
    
    sparse_polynom.hpp

    This file is a part of Arageli library.

    Copyright (C) Nikolai Yu. Zolotykh, 1999--2006
    Copyright (C) Sergey S. Lyalin, 2005
    University of Nizhni Novgorod, Russia

*****************************************************************************/

#ifndef _ARAGELI_sparse_polynom_hpp_
#define _ARAGELI_sparse_polynom_hpp_

#include "config.hpp"

#include <iostream>
#include <list>
#include <iomanip>
#include <algorithm>
#include <cmath>

#include "frwrddecl.hpp"

#include "type_traits.hpp"
#include "config.hpp"
#include "exception.hpp"
#include "refcntr.hpp"
#include "iteradapt.hpp"
#include "type_opers.hpp"
#include "factory.hpp"
#include "cmp.hpp"
#include "io.hpp"
#include "powerest.hpp"
#include "big_int.hpp"
#include "rational.hpp"
#include "_utility.hpp"

#include "std_import.hpp"

//****************************************************************************

namespace Arageli
{

template <typename T> class rational;



template
<
    typename F,
    typename I
>
class monom
{
    template <typename F1, typename I1>
    friend class monom;

public:

    typedef F coef_type;    
    typedef I degree_type;  


    monom () : coef_m(factory<coef_type>::null()), degree_m(factory<degree_type>::null()) {}


    monom (const F& c) : coef_m(c), degree_m(factory<degree_type>::null()) {}


    monom (const F& c, const I& d) : coef_m(c), degree_m(d) {}

    template <typename F1, typename I1>
    monom (const monom<F1, I1>& x)
    : coef_m(x.coef_m), degree_m(x.degree_m) {}


    monom (const char* s);

    template <typename F1, typename I1>
    monom& operator= (const monom<F1, I1>& x)
    {
        coef_m = x.coef_m; degree_m = x.degree_m;
        return *this;
    }

    monom& operator= (const char* s)
    { return *this = monom(s); }


    bool is_const () const { return Arageli::is_null(degree_m); }


    bool is_null () const { return Arageli::is_null(coef_m); }


    bool is_unit () const
    { return Arageli::is_unit(coef_m) && Arageli::is_null(degree_m); }


    bool is_opposite_unit () const
    {
        return Arageli::is_opposite_unit(coef_m) &&
            Arageli::is_null(degree_m);
    }

    

    bool is_x () const
    { return Arageli::is_unit(coef_m) && Arageli::is_unit(degree_m); }

    const coef_type& coef () const { return coef_m; }
    
    coef_type& coef () { return coef_m; }
    
    const degree_type& degree () const { return degree_m; }
    
    degree_type& degree () { return degree_m; }


    template <typename F1, typename I1>
    bool can_add (const monom<F1, I1>& x) const
    { return degree_m == x.degree_m; }

    monom& opposite ()
    {
        Arageli::opposite(&coef_m);
        return *this;
    }
    
    monom operator- () const
    { return monom(Arageli::opposite(coef_m), degree_m); }
    
    const monom& operator+ () const { return *this; }

    monom& operator++ ()
    {
        ARAGELI_ASSERT_0(is_const());
        ++coef_m;
        return *this;
    }

    monom operator++ (int) { monom t = *this; operator++(); return t; }

    monom& operator-- ()
    {
        ARAGELI_ASSERT_0(is_const());
        --coef_m;
        return *this;
    }

    monom operator-- (int) { monom t = *this; operator--(); return t; }


    template <typename F1>
    monom& operator+= (const F1& x)
    {
        ARAGELI_ASSERT_0(is_const());
        coef_m += x;
        return *this;
    }
    

    template <typename F1>
    monom& operator-= (const F1& x)
    {
        ARAGELI_ASSERT_0(is_const());
        coef_m -= x;
        return *this;
    }
    

    template <typename F1>
    monom& operator*= (const F1& x)
    {
        coef_m *= x;
        return *this;
    }
    

    template <typename F1>
    monom& operator/= (const F1& x)
    {
        ARAGELI_ASSERT_0(!Arageli::is_null(x));
        coef_m /= x;
        return *this;
    }
    

    template <typename F1>
    monom& operator%= (const F1& x)
    {
        ARAGELI_ASSERT_0(!Arageli::is_null(x));
        coef_m %= x;
        return *this;
    }
    

    template <typename F1, typename I1>
    monom& operator+= (const monom<F1, I1>& x)
    {
        ARAGELI_ASSERT_0(can_add(x));
        coef_m += x.coef_m;
        return *this;
    }
    

    template <typename F1, typename I1>
    monom& operator-= (const monom<F1, I1>& x)
    {
        ARAGELI_ASSERT_0(can_add(x));
        coef_m -= x.coef_m;
        return *this;
    }


    template <typename F1, typename I1>
    monom& operator*= (const monom<F1, I1>& x)
    {
        coef_m *= x.coef_m;
        degree_m += x.degree_m;
        return *this;
    }
    

    template <typename F1, typename I1>
    monom& operator/= (const monom<F1, I1>& x)
    {
        ARAGELI_ASSERT_0(!Arageli::is_null(x.coef_m));
        
        if(degree_m >= x.degree_m)
        {
            coef_m /= x.coef_m;
            degree_m -= x.degree_m;
        }
        else
        {
            coef_m = factory<coef_type>::null();
            degree_m = null<degree_type>();
        }
        
        return *this;
    }
    

    template <typename F1, typename I1>
    monom& operator%= (const monom<F1, I1>& x)
    {
        ARAGELI_ASSERT_0(!Arageli::is_null(x.coef_m));
        if(degree_m >= x.degree_m)coef_m %= x.coef_m;
        return *this;
    }

    template <typename F1, typename I1>
    void swap (monom<F1, I1>& x)
    {
        std::swap(coef_m, x.coef_m);
        std::swap(degree_m, x.degree_m);
    }

private:

    coef_type coef_m;
    degree_type degree_m;

};


//++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++


template <typename F, typename I>
struct type_traits<monom<F, I> >
    : public type_traits_default<monom<F, I> >
{
    static const bool is_specialized =
                        type_traits<F>::is_specialized &&
                        type_traits<I>::is_specialized;

    static const bool is_integer_number = false;
    static const bool is_polynom = false;
    static const bool is_real_number = false;
    static const bool is_rational_number = false;
    static const bool is_complex_number = false;
    static const bool is_ring = false;
    static const bool is_field = false;
    
    static const bool is_finite =
                        type_traits<F>::is_finite &&
                        type_traits<I>::is_finite;
    
    static const bool is_additive_group = type_traits<F>::is_ring;
    static const bool is_multiplicative_group = false;

    static const bool has_zero_divisor =
                        type_traits<F>::has_zero_divisor &&
                        type_traits<I>::has_null;

    static const bool is_integer_modulo_ring = false;
    static const bool is_matrix = false;
    static const bool is_vector = false;

    static const bool has_commutative_multiplication =
                        type_traits<F>::has_commutative_multiplication &&
                        type_traits<I>::has_commutative_addition;

    static const bool has_commutative_addition =
                        type_traits<F>::has_commutative_addition;
    
    static const bool has_null =
                        type_traits<F>::has_null &&
                        type_traits<I>::has_null;

    static const bool has_unit =
                        type_traits<F>::has_unit &&
                        type_traits<I>::has_null;

    static const bool has_opposite_unit =
                        type_traits<F>::has_opposite_unit &&
                        type_traits<I>::has_null;
    
    static const bool is_aggregate = true;
    
    typedef F element_type;

};




//++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++

template <typename F, typename I>
struct factory<monom<F, I> >
{
    static const bool is_specialized = true;

    static const monom<F, I>& unit ()
    {
        static const monom<F, I> unit_s(Arageli::unit<F>());
        return unit_s;
    }

    static monom<F, I> unit (const monom<F, I>& x)
    { return monom<F, I>(Arageli::unit(x.coef())); }

    static const monom<F, I>& opposite_unit ()
    {
        static const monom<F, I> opposite_unit_s(Arageli::opposite_unit<F>());  
        return opposite_unit_s;
    }

    static monom<F, I> opposite_unit (const monom<F, I>& x)
    { return monom<F, I>(opposite_unit(x.coef())); }

    static const monom<F, I>& null ()
    {
        static const monom<F, I> null_s(Arageli::null<F>());
        return null_s;
    }

    static monom<F, I> null (const monom<F, I>& x)
    { return monom<F, I>(Arageli::null(x.coef())); }

};


template <typename F, typename I>
inline bool is_unit (const monom<F, I>& x)
{ return x.is_unit(); }

template <typename F, typename I>
inline bool is_opposite_unit (const monom<F, I>& x)
{ return x.is_opposite_unit(); }

template <typename F, typename I>
inline bool is_null (const monom<F, I>& x)
{ return x.is_null(); }

template <typename F, typename I>
inline monom<F, I> opposite (const monom<F, I>& x)
{ return -x; }

template <typename F, typename I>
inline monom<F, I>& opposite (const monom<F, I>& x, monom<F, I>* y)
{ return (*y = x).opposite(); }

template <typename F, typename I>
inline monom<F, I>& opposite (monom<F, I>* x)
{ return x->opposite(); }

template <typename F, typename I>
inline monom<F, I> inverse (const monom<F, I>& x)
{
    ARAGELI_ASSERT_0(x.is_const());
    return inverse(x.coef());
}

template <typename F, typename I>
inline monom<F, I>& inverse (const monom<F, I>& x, monom<F, I>* y)
{
    ARAGELI_ASSERT_0(x.is_const());
    inverse(x.coef(), &y->coef());
    y->degree() = x.degree();
    return *y;
}

template <typename F, typename I>
inline monom<F, I>& inverse (monom<F, I>* x)
{
    ARAGELI_ASSERT_0(x.is_const());
    inverse(&x->coef());
    return *x;
}

template <typename F, typename I>
inline std::ostream& output_polynom_first (std::ostream& out, const monom<F, I>& x)
{ return out << '(' << x << ')'; }

template <typename F, typename I>
inline std::ostream& output_polynom_internal
(std::ostream& out, const monom<F, I>& x)
{ return out << "+(" << x << ')'; }

template <typename F, typename I>
inline std::ostream& output_pow (std::ostream& out, const monom<F, I>& x)
{ return out << '(' << x << ')'; }

template <typename F, typename I>
std::istream& input_polynom_first (std::istream& in, monom<F, I>& x);

template <typename F, typename I>
std::istream& input_polynom_internal
(std::istream& in, monom<F, I>& x);

template <typename F, typename I>
inline std::istream& input_pow (std::istream& in, monom<F, I>& x)
{ return input_polynom_first(in, x); }

---