sparse_polynom.cpp

Go to the documentation of this file.

/*****************************************************************************
    
    sparse_polynom.cpp -- Îïèñàíèå ñì. â ôàéëå sparse_polynom.hpp.

    Ýòîò ôàéë ÿâëÿåòñÿ ÷àñòüþ áèáëèîòåêè Arageli.

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

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

#include "config.hpp"

#if !defined(ARAGELI_INCLUDE_CPP_WITH_EXPORT_TEMPLATE) || \
    defined(ARAGELI_INCLUDE_CPP_WITH_EXPORT_TEMPLATE_SPARSE_POLYNOM)

#include <iomanip>
#include <algorithm>
#include <algorithm>
#include <cstring>
#include <cctype>
#include <iostream>
#include <sstream>

#include "sparse_polynom.hpp"
#include "vector.hpp"
#include "_utility.hpp"
#include "polyalg.hpp"
#include "functional.hpp"

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

namespace Arageli
{


template <typename F, typename I>
monom<F, I>::monom (const char* s)
{
    std::stringstream buf(s);
    // WARNING. Correct if there are no virtual function.
    buf >> *this;
    if(!buf && !buf.eof())throw incorrect_string(s);
}


template
<
    typename Ch, typename ChT,
    typename F, typename I
>
std::basic_ostream<Ch, ChT>& output_var
(
    std::basic_ostream<Ch, ChT>& out,
    const monom<F, I>& x,
    bool first,
    const char* var,
    const char* mul,
    const char* pow
)
{
    if(x.is_const())
        if(first)
            output_polynom_first(out, x.coef());
        else
            output_polynom_internal(out, x.coef());
    else
    {
        if(is_opposite_unit(x.coef()))
            out << '-';
        else if(is_unit(x.coef()))
            { if(!first)out << '+'; }
        else if(first)
            output_polynom_first(out, x.coef()) << mul;
        else
            output_polynom_internal(out, x.coef()) << mul;
        out << var;
        if(!is_unit(x.degree()))
        {
            out << pow;
            output_pow(out, x.degree());
        }
    }
    return out;
}


template
<
    typename Ch, typename ChT,
    typename F, typename I
>
std::basic_istream<Ch, ChT>& input_list
(
    std::basic_istream<Ch, ChT>& in,
    monom<F, I>& x,
    const char* fb,
    const char* sb,
    const char* sep
)
{
    ARAGELI_ASSERT_0(_Internal::is_not_contains_spaces(fb));
    ARAGELI_ASSERT_0(_Internal::is_not_contains_spaces(sb));
    ARAGELI_ASSERT_0(_Internal::is_not_contains_spaces(sep));

    monom<F, I> tmp;
    if
    (!(
        !_Internal::read_literal(in, fb)  ||
        !input_polynom_first(in, tmp.coef())  ||
        !_Internal::read_literal(in, sep)  ||
        !input_pow(in, tmp.degree())  ||
        !_Internal::read_literal(in, sb)
    ))
        x = tmp;

    return in;  
}


template
<
    typename Ch, typename ChT,
    typename F, typename I, typename Factory_coef
>
std::basic_istream<Ch, ChT>& input_var
(
    std::basic_istream<Ch, ChT>& in,
    monom<F, I>& x,
    bool first_a,
    const Factory_coef& fctr,
    const char* var,
    const char* mul,
    const char* pow
)
{
    ARAGELI_ASSERT_0(_Internal::is_not_contains_spaces(var));
    ARAGELI_ASSERT_0(_Internal::is_not_contains_spaces(mul));
    ARAGELI_ASSERT_0(_Internal::is_not_contains_spaces(pow));
    
    monom<F, I> res;
    char ch, ch1 = 0;

    in >> ch1;
    if(!in)return in;

    if(ch1 != '-' && ch1 != '+')
    {
        in.putback(ch1);
        
        if(!first_a)
        {
            in.clear(std::ios_base::failbit);
            return in;
        }
    }

    if(_Internal::read_literal(in, var))
    {
        if(ch1 == '-')
            res.coef() = fctr.opposite_unit(x.coef());
        else res.coef() = fctr.unit(x.coef());
        
        ch = in.get();
        in.clear();
        in.putback(ch);

        if(ch != '\n' && _Internal::read_literal(in, pow))
        {
            input_pow(in, res.degree());
            if(!in && !in.eof())
            {
                ARAGELI_ASSERT_1(!in.good());
                return in;
            }
        }
        else res.degree() = unit(x.degree());

        x = res;
        in.clear();
        return in;
    }

    //std::cerr << "\n" << in.good();
    if(ch1 == '-' || ch1 == '+')in.putback(ch1);
    in.clear();
    //std::cerr << "\n" << in.good();

    if(first_a)
        input_polynom_first(in, res.coef());
    else
        input_polynom_internal(in, res.coef());

    if(!in)
    {
        if(!in.eof())
        {
            ARAGELI_ASSERT_1(!in.good());
            return in;
        }
    }
    else
    {
        ch = in.get();
        in.putback(ch);
        in.clear();

        if(!in.eof() && ch != '\n')
        {
            if(_Internal::read_literal(in, mul))
            {
                if(!_Internal::read_literal(in, var))
                {
                    in.clear(std::ios_base::badbit);
                    return in;
                }
                
                ch = in.get();
                in.clear();
                in.putback(ch);
                
                if(ch != '\n' && _Internal::read_literal(in, pow))
                {
                    input_pow(in, res.degree());
                    if(!in && !in.eof())
                    {
                        ARAGELI_ASSERT_1(!in.good());
                        return in;
                    }
                }
                else res.degree() = unit(x.degree());
            }
        }
    }

    x = res;

    in.clear();
    return in;
}


template <typename F, typename I, bool REFCNT>
sparse_polynom<F, I, REFCNT>::sparse_polynom (const char* str)
{
    std::istringstream buf(str);
    // WARNING. It's correct if and only if sparse_polynom has no virtual functions.
    static_cast<std::istream&>(buf) >> *this;
    if(!buf && !buf.eof())throw incorrect_string(str);
    //ARAGELI_ASSERT_0(buf.good() || buf.eof());
}


template <typename F, typename I, bool REFCNT>
bool sparse_polynom<F, I, REFCNT>::is_normal () const
{
    return std::adjacent_find
    (
        rep().begin(), rep().end(),
        std::not2(monom_degree_less<monom>())
    ) == rep().end()
    &&
    (
        rep().empty() ||
        !rep().front().is_null()
    );
}

    
template <typename F, typename I, bool REFCNT>
sparse_polynom<F, I, REFCNT>& sparse_polynom<F, I, REFCNT>::opposite ()
{
    ARAGELI_ASSERT_0(is_normal());
    
    if(is_null())return *this;
    store.unique();

    std::for_each
    (
        rep().begin(), rep().end(),
        std::mem_fun_ref(&monom::opposite)
    );

    return *this;
}


template <typename F, typename I, bool REFCNT>
template <typename F1>
sparse_polynom<F, I, REFCNT>& sparse_polynom<F, I, REFCNT>::add_scalar
(const F1& x)
{
    ARAGELI_ASSERT_0(is_normal());
    
    if(Arageli::is_null(x))return *this;
    store.unique();
    
    if(rep().empty() || !rep().front().is_const())
        rep().push_front(monom(x));
    else if((rep().front() += x).is_null())
        rep().pop_front();
    
    return *this;   
}


template <typename F, typename I, bool REFCNT>
template <typename F1>
sparse_polynom<F, I, REFCNT>& sparse_polynom<F, I, REFCNT>::sub_scalar
(const F1& x)
{
    ARAGELI_ASSERT_0(is_normal());
    
    if(Arageli::is_null(x))return *this;
    store.unique();
    
    if(rep().empty() || !rep().front().is_const())
        rep().push_front(-monom(x));
    else if((rep().front() -= x).is_null())
        rep().pop_front();
    
    return *this;   
}


#define _ARAGELI_SPARSE_POLYNOM_OPERATOR_ASSIGN_1(MNEM, OPER)       \
    template <typename F, typename I, bool REFCNT>                  \
    template <typename F1>                                          \
    sparse_polynom<F, I, REFCNT>&                                   \
    sparse_polynom<F, I, REFCNT>::MNEM##_scalar                     \
    (const F1& x)                                                   \
    {                                                               \
        ARAGELI_ASSERT_0(is_normal());                              \
        if(is_null())return *this;                                  \
                                                                    \
        for                                                         \
        (                                                           \
            coef_iterator i = coefs_begin(), iend = coefs_end();    \
            i != iend;                                              \
            ++i                                                     \
        )                                                           \
            /*if(Arageli::is_null(*i OPER x))                       \
                i = erase(i.base());*/                              \
            *i OPER x;                                              \
                                                                    \
        normalize();    /* WARNING! We don't need full normalize! */\
        return *this;                                               \
    }

_ARAGELI_SPARSE_POLYNOM_OPERATOR_ASSIGN_1(mul, *=);
_ARAGELI_SPARSE_POLYNOM_OPERATOR_ASSIGN_1(div, /=);
_ARAGELI_SPARSE_POLYNOM_OPERATOR_ASSIGN_1(mod, %=);
_ARAGELI_SPARSE_POLYNOM_OPERATOR_ASSIGN_1(bitor, |=);
_ARAGELI_SPARSE_POLYNOM_OPERATOR_ASSIGN_1(bitand, &=);
_ARAGELI_SPARSE_POLYNOM_OPERATOR_ASSIGN_1(bitxor, ^=);
_ARAGELI_SPARSE_POLYNOM_OPERATOR_ASSIGN_1(shl, <<=);
_ARAGELI_SPARSE_POLYNOM_OPERATOR_ASSIGN_1(shr, >>=);


//template <typename F, typename I, bool REFCNT>
//template <typename F1>
//sparse_polynom<F, I, REFCNT>& sparse_polynom<F, I, REFCNT>::div_scalar
//(const F1& x)
//{
//  // ÏÐÅÄÓÏÐÅÆÄÅÍÈÅ. Ïðîñòàÿ, íî ìåäëåííàÿ ðåàëèçàöèÿ. Ìîæíî áûñòðåå.
//
//  return operator/=(monom(x));
//}
//
//
//template <typename F, typename I, bool REFCNT>
//template <typename F1>
//sparse_polynom<F, I, REFCNT>& sparse_polynom<F, I, REFCNT>::operator%=
//(const F1& x)
//{
//  // ÏÐÅÄÓÏÐÅÆÄÅÍÈÅ. Ïðîñòàÿ, íî ìåäëåííàÿ ðåàëèçàöèÿ. Ìîæíî áûñòðåå.
//
//  return operator%=(monom(x));
//}


template <typename F, typename I, bool REFCNT>
template <typename F1, typename I1>
sparse_polynom<F, I, REFCNT>& sparse_polynom<F, I, REFCNT>::operator+=
(const Arageli::monom<F1, I1>& x)
{
    ARAGELI_ASSERT_0(is_normal());
    
    if(x.is_null())return *this;
    store.unique();
    typename Rep::iterator i = find_pos(x);

    if(i != rep().end() && x.can_add(*i))
    {
        if((*i += x).is_null())
            rep().erase(i);
    }
    else
        rep().insert(i, x);

    return *this;
}


template <typename F, typename I, bool REFCNT>
template <typename F1, typename I1>
sparse_polynom<F, I, REFCNT>& sparse_polynom<F, I, REFCNT>::operator-=
(const Arageli::monom<F1, I1>& x)
{
    ARAGELI_ASSERT_0(is_normal());
    
    // ÏÐÅÄÓÏÐÅÆÄÅÍÈÅ. Ïðîñòàÿ, íî ìåäëåííàÿ ðåàëèçàöèÿ, ìîæíî áûñòðåå.
    
    return operator+=(-x);  
}


template <typename F, typename I, bool REFCNT>
template <typename F1, typename I1>
sparse_polynom<F, I, REFCNT>& sparse_polynom<F, I, REFCNT>::operator*=
(const Arageli::monom<F1, I1>& x)
{
    ARAGELI_ASSERT_0(is_normal());
    
    if(x.is_unit())return *this;

    if(x.is_null())
    {
        if(store.unique_clear())rep().clear();
        return *this;
    }

    store.unique();

    // WARNING!!!
    Arageli::monom<F1, I1> xx = x;  // copy because x maybe part of this polynomial

    for(typename Rep::iterator i = rep().begin(); i != rep().end();)
        if((*i *= xx).is_null())
            i = rep().erase(i);
        else ++i;

    return *this;
}


template <typename F, typename I, bool REFCNT>
template <typename F1, typename I1>
sparse_polynom<F, I, REFCNT>& sparse_polynom<F, I, REFCNT>::operator/=
(const Arageli::monom<F1, I1>& x)
{
    ARAGELI_ASSERT_0(is_normal());
    ARAGELI_ASSERT_0(!x.is_null());
    
    if(x.is_unit())return *this;
    store.unique();

    Arageli::monom<F1, I1> xx = x;  // copy because x maybe part of this polynomial

    for(typename Rep::iterator i = find_pos(x); i != rep().end();)
        if((*i /= xx).is_null())
            i = rep().erase(i);
        else ++i;

    return *this;
}


template <typename F, typename I, bool REFCNT>
template <typename T1>
sparse_polynom<F, I, REFCNT>&
sparse_polynom<F, I, REFCNT>::add_sparse_polynom
(const T1& x)
{
    ARAGELI_ASSERT_0(is_normal());
    ARAGELI_ASSERT_0(x.is_normal());

    if(x.is_null())return *this;

    store.unique();
    if
    (
        reinterpret_cast<const void*>(this) ==
        reinterpret_cast<const void*>(&x))
    {
        ARAGELI_ASSERT_0(!is_null());
        for(typename Rep::iterator i = rep().begin(); i != rep().end();)
            if((*i += *i).is_null())
                i = rep().erase(i);
            else ++i;
    }
    else
    {
        monom_iterator i1 = monoms_begin(), i1end = monoms_end();
        typename T1::monom_const_iterator i2 = x.monoms_begin(),
            i2end = x.monoms_end();

        while(i1 != i1end && i2 != i2end)
        {
            if(i1->degree() < i2->degree())++i1;
            else if(i1->degree() == i2->degree())
            {
                if((*i1 += *i2).is_null())
                    i1 = rep().erase(i1);
                else ++i1;
                ++i2;
            }
            else
            { // i1->degree() > i2->degree()
                rep().insert(i1, *i2);
                ++i2;
            }
        }

        if(i2 != x.rep().end())
        {
            ARAGELI_ASSERT_1(i1 == monoms_end());
            rep().insert(i1, i2, x.monoms_end());
        }
    }

    return *this;
}


template <typename F, typename I, bool REFCNT>
template <typename T1>
sparse_polynom<F, I, REFCNT>&
sparse_polynom<F, I, REFCNT>::sub_sparse_polynom
(const T1& x)
{
    ARAGELI_ASSERT_0(is_normal());
    ARAGELI_ASSERT_0(x.is_normal());

    // ÏÐÅÄÓÏÐÅÆÄÅÍÈÅ. Ïðîñòàÿ, íî ìåäëåííàÿ ðåàëèçàöèÿ, ìîæíî áûñòðåå.
    
    return operator+=(-x);
}


template <typename F, typename I, bool REFCNT>
template <typename T1>
sparse_polynom<F, I, REFCNT>&
sparse_polynom<F, I, REFCNT>::mul_sparse_polynom
(const T1& x)
{
    ARAGELI_ASSERT_0(is_normal());
    ARAGELI_ASSERT_0(x.is_normal());

    // ÏÐÅÄÓÏÐÅÆÄÅÍÈÅ. Ïðîñòàÿ, íî ìåäëåííàÿ ðåàëèçàöèÿ, ìîæíî áûñòðåå.

    if(is_null())return *this;
    if(x.is_null())
    {
        if(store.unique_clear())rep().clear();
        return *this;
    }

    sparse_polynom res;
    for
    (
        typename T1::monom_const_iterator i =
            x.monoms_begin(), iend = x.monoms_end();
        i != iend;
        ++i
    )
    {
        sparse_polynom t(*this);
        t *= *i;
        res += t;
    }

    *this = res;
    return *this;
}


template <typename F, typename I, bool REFCNT>
template <typename T1>
sparse_polynom<F, I, REFCNT>&
sparse_polynom<F, I, REFCNT>::div_sparse_polynom
(const T1& x)
{
    ARAGELI_ASSERT_0(x.is_normal());
    ARAGELI_ASSERT_0(is_normal());

    if(is_null())return *this;
    if(x.is_null())throw division_by_zero();
    
    if(degree() < x.degree())
    {
        if(store.unique_clear())rep().clear();
        return *this;
    }

    assign_div(*this, x);
    return *this;
}


// WARNING! The second arg should more common.
template <typename F, typename I, bool REFCNT>
template <typename F1, typename I1, bool REFCNT1>
void sparse_polynom<F, I, REFCNT>::assign_div_common
(
    sparse_polynom& x,
    const sparse_polynom<F1, I1, REFCNT1>& y
)
{
    ARAGELI_ASSERT_1(x.is_normal());
    ARAGELI_ASSERT_1(y.is_normal());

#if 1

    sparse_polynom pq, pr;
    polynom_divide(x, y, pq, pr);
    x = pq;

#else

    ARAGELI_ASSERT_1(!x.is_null());
    ARAGELI_ASSERT_1(!y.is_null());
    
    // ÏÐÅÄÓÏÐÅÆÄÅÍÈÅ. Ïðîñòàÿ, íî ìåäëåííàÿ ðåàëèçàöèÿ, ìîæíî áûñòðåå.
    // WARNING. This implementation is simple but is slow, may be quicker.

    // WARNING. This algorithm works only if F and F1 are fields.

    sparse_polynom t(x);
    sparse_polynom res;

    while(!t.is_null() && t.degree() >= y.degree())
    {
        ARAGELI_ASSERT_0(!t.is_null());
        monom mt = t.leading_monom();
        mt /= y.leading_monom();    // maybe integer division
        if(mt.is_null())break;
        sparse_polynom<F1, I1, REFCNT1> tx(y);
        //std::cout << "\ntx before = " << tx;
        tx *= mt;
        //std::cout << "\nmt sumtraction = " << mt;
        //std::cout << "\ntx after = " << tx;
        //std::cout << "\nt before sumtraction = " << t;
        ARAGELI_ASSERT_0(!tx.is_null());
        t -= tx;
        //std::cout << "\nt after sumtraction = " << t;
        res += mt;
    }

    x = res;

#endif
}


//template <typename F, typename I, bool REFCNT, typename FT, typename IT>
//template
//<
//  typename I1, bool REFCNT1, typename FT1, typename IT1,
//  typename I2, bool REFCNT2, typename FT2, typename IT2,
//  typename TT3, typename TT4
//>
//void sparse_polynom<F, I, REFCNT, FT, IT>::assign_div
//(
//  sparse_polynom<rational<big_int>, I1, REFCNT1, FT1, IT1>& x,
//  const sparse_polynom<rational<big_int, TT4>, I2, REFCNT2, FT2, IT2>& y
//)
//{
//  ARAGELI_ASSERT_1(x.is_normal());
//  ARAGELI_ASSERT_1(y.is_normal());
//  ARAGELI_ASSERT_1(!x.is_null());
//  ARAGELI_ASSERT_1(!y.is_null());
//  
//  ARAGELI_ASSERT_1
//  ((
//      equal_types
//      <
//          sparse_polynom<F, I, REFCNT, FT, IT>,
//          sparse_polynom<rational<big_int>, I1, REFCNT1, FT1, IT1>
//      >::bvalue
//  ));
//
//  typedef
//      typename sparse_polynom
//          <rational<big_int, TT4>, I2, REFCNT2, FT2, IT2>::coef_const_iterator
//              Iter_y;
//  
//  vector<big_int> numers(x.size()), denoms(y.size());
//  //vector<big_int>
//  //  numers(x.coefs_begin(), x.coefs_end()),
//  //  denoms(y.coefs_begin(), y.coefs_end());
//
//  std::transform
//  (
//      x.coefs_begin(), x.coefs_end(),
//      numers.begin(), select_denom<big_int>()
//  );
//
//  std::transform
//  (
//      y.coefs_begin(), y.coefs_end(),
//      denoms.begin(), select_denom<big_int, TT4>()
//  );
//
//  std::cout << "\nthe first polynomial: " << x;
//  std::cout << "\nthe second polynomial: " << y;
//  std::cout << "\nnumber: ";
//  vector_output_row(std::cout, numers);
//  std::cout << "\ndenoms: ";
//  vector_output_row(std::cout, denoms);
//
//  //std::copy(x.coefs_begin(), x.coefs_end(), numers);
//  //std::copy(y.coefs_begin(), y.coefs_end(), denoms);
//  //std::size_t ii = 0;
//  //for(coef_iterator i = x.coefs_begin(); i != x.coefs_end(); ++i, ++ii)
//  //  numers[ii] = i->denominator();
//
//  //ii = 0;
//  //for(Iter_y i = y.coefs_begin(); i != y.coefs_end(); ++i)
//  //  denoms[ii] = i->denominator();
//
//  big_int numerator = product(numers), denominator = product(denoms);
//
//  std::cout << "\nnumer: " << numerator;
//  std::cout << "\ndenom: " << denominator;
//
//  sparse_polynom<big_int, I2, REFCNT2, TT4, IT2>
//      yy = y*denominator; // yy contains only integer coefficients
//
//  ARAGELI_ASSERT_1(yy == y*denominator);
//
//  numerator *= power(yy.leading_coef(), x.degree());
//
//  std::cout << "\nnumer: " << numerator;
//
//  sparse_polynom<big_int, I1, REFCNT1, IT1>
//      xx = x*numerator;   // x contains only integer coefficients
//
//  ARAGELI_ASSERT_1(xx == x*numerator);
//
//  std::cout << "\nthe xx polynomial: " << xx;
//  std::cout << "\nthe yy polynomial: " << yy << std::flush;
//
//  xx /= yy;   // division without remainders in integer division
//
//  ARAGELI_DEBUG_EXEC_1(sparse_polynom tt = x);
//  ARAGELI_DEBUG_EXEC_1(assign_div_common(tt, y));
//  
//  x = xx;
//  
//  for(coef_iterator i = x.coefs_begin(); i != x.coefs_end(); ++i)
//      *i = *i / numerator * denominator;
//
//  std::cout << "\nthe result: " << x;
//  
//  ARAGELI_ASSERT_1(tt == x);
//  ARAGELI_DEBUG_EXEC_1(std::cout << "\nthe common result: " << tt);
//  std::cout << std::flush;
//}


template <typename F, typename I, bool REFCNT>
template <typename T1>
sparse_polynom<F, I, REFCNT>&
sparse_polynom<F, I, REFCNT>::mod_sparse_polynom
(const T1& x)
{
    ARAGELI_ASSERT_0(is_normal());
    ARAGELI_ASSERT_0(x.is_normal());

    // ÏÐÅÄÓÏÐÅÆÄÅÍÈÅ. Ïðîñòàÿ, íî ìåäëåííàÿ ðåàëèçàöèÿ, ìîæíî áûñòðåå.
    // WARNING. This implementation is simple but is slow, maybe quicker.

    if(is_null())return *this;
    if(x.is_null())throw division_by_zero();
    
#if 1

    sparse_polynom pq, pr;
    polynom_divide(*this, x, pq, pr);
    *this = pr;

#else

    if(degree() < x.degree())return *this;
    sparse_polynom res(*this);

    while(!res.is_null() && res.degree() >= x.degree())
    {
        monom mt = res.leading_monom();
        mt /= x.leading_monom();
        if(mt.is_null())break;
        T1 tx(x);
        tx *= mt;
        res -= tx;
    }

    *this = res;

#endif

    return *this;
}


//template <typename F, typename I, bool REFCNT, typename FT, typename IT>
//template <typename I1>
//sparse_polynom<F, I, REFCNT, FT, IT>& sparse_polynom<F, I, REFCNT, FT, IT>::pow (I1 x)
//{
//  // Íåÿâíî ïðåäïîëàãàåòñÿ, ÷òî x >= 0. Ïîêà íåëüçÿ íàïèñàòü assert, òàê êàê
//  // â type_traits íåò ôóíêöèè, êîòîðàÿ îïðåäåëÿåò çíàê ýëåìåíòà.
//
//  if(is_null() && type_traits<I1>::is_null(x))throw zero_in_zero_degree();
//  
//  if(type_traits<I1>::is_null(x))
//  {
//      if(store.unique_clear())rep().clear();
//      rep().push_back(monom(coef_traits::unit()));
//  }
//  else if(!type_traits<I1>::is_unit(x))
//  {
//      sparse_polynom t = *this;
//      for(--x; !type_traits<I1>::is_null(x); --x)
//          *this *= t;
//  }
//
//  return *this;
//}


template <typename F, typename I, bool REFCNT>
template <typename Iter>
void sparse_polynom<F, I, REFCNT>::add
(Iter first, Iter last, const any_monom_seq_t&)
{
    // ÏÐÅÄÓÏÐÅÆÄÅÍÈÅ. 'first' è 'last' íå äîëæíû áûòü èòåðàòîðàìè
    // äëÿ äàííîãî îáúåêòà ïîëèíîìà.

    // ÏÐÅÄÓÏÐÅÆÄÅÍÈÅ. Ïðîñòàÿ, íî ìåäëåííàÿ ðåàëèçàöèÿ, ìîæíî áûñòðåå.

    while(first != last)*this += *first++;
}


template <typename F, typename I, bool REFCNT>
template <typename Iter>
void sparse_polynom<F, I, REFCNT>::add
(Iter first, Iter last, const norm_monom_seq_t&)
{
    // ÏÐÅÄÓÏÐÅÆÄÅÍÈÅ. 'first' è 'last' íå äîëæíû áûòü èòåðàòîðàìè
    // äëÿ äàííîãî îáúåêòà ïîëèíîìà.

    // ÏÐÅÄÓÏÐÅÆÄÅÍÈÅ. Ïðîñòàÿ, íî ìåäëåííàÿ ðåàëèçàöèÿ, ìîæíî áûñòðåå.

    while(first != last)*this += *first++;
}


template <typename F, typename I, bool REFCNT>
template <typename Iter>
void sparse_polynom<F, I, REFCNT>::sub
(Iter first, Iter last, const any_monom_seq_t&)
{
    // ÏÐÅÄÓÏÐÅÆÄÅÍÈÅ. 'first' è 'last' íå äîëæíû áûòü èòåðàòîðàìè
    // äëÿ äàííîãî îáúåêòà ïîëèíîìà.

    // ÏÐÅÄÓÏÐÅÆÄÅÍÈÅ. Ïðîñòàÿ, íî ìåäëåííàÿ ðåàëèçàöèÿ, ìîæíî áûñòðåå.

    while(first != last)*this -= *first++;
}


template <typename F, typename I, bool REFCNT>
template <typename Iter>
void sparse_polynom<F, I, REFCNT>::sub
(Iter first, Iter last, const norm_monom_seq_t&)
{
    // ÏÐÅÄÓÏÐÅÆÄÅÍÈÅ. 'first' è 'last' íå äîëæíû áûòü èòåðàòîðàìè
    // äëÿ äàííîãî îáúåêòà ïîëèíîìà.

    // ÏÐÅÄÓÏÐÅÆÄÅÍÈÅ. Ïðîñòàÿ, íî ìåäëåííàÿ ðåàëèçàöèÿ, ìîæíî áûñòðåå.

    while(first != last)*this -= *first++;
}


template <typename F, typename I, bool REFCNT>
template <typename F1, typename I1, bool REFCNT1>
void sparse_polynom<F, I, REFCNT>::addsub
(
    sparse_polynom<F1, I1, REFCNT1>& x,
    typename sparse_polynom<F1, I1, REFCNT1>::monom_iterator pos
)
{
    // Ïðåäïîëàãàåòñÿ, ÷òî F1 != F èëè I1 != I.
    //  ïðîòèâíîì ñëó÷àå äîëæíà âûçûâàòüñÿ äðóãàÿ ñïåöèàëèçàöèÿ ýòîé ôóíêöèè.
    // Òèïû 'Rep' äëÿ *this è äëÿ x ðàçëè÷íû, ïîýòîìó ìû íå ìîæåì ïåðåìåùàòü
    // ìîíîìû ìåæäó ýòèìè ñïèñêàìè áåç êîïèðîâàíèÿ.

    ARAGELI_ASSERT_0(pos != x.rep().end());

    *this += *pos;
    x.erase(pos);
}


template <typename F, typename I, bool REFCNT>
template <bool REFCNT1>
void sparse_polynom<F, I, REFCNT>::addsub
(
    sparse_polynom<F, I, REFCNT1>& x,
    typename sparse_polynom<F, I, REFCNT1>::monom_iterator pos
)
{
    // Òàê êàê F è I äëÿ îáîèõ ïîëèíîìîâ (è äëÿ '*this' è äëÿ 'x') îäèíàêîâû,
    // òî òèïû 'Rep' äëÿ íèõ äîëæíû áûòü ýêâèâàëåíòíû.
    // Ïîýòîìó ïðèìåíÿåì îáû÷íûå îïåðàöèè ñî ñïèñêàìè, ãäå ýòî âîçìîæíî.

    ARAGELI_ASSERT_0(pos != x.rep().end());

    unique();

    typename Rep::iterator i = find_pos(*pos);
    if(i != rep().end() && pos->can_add(*i))
    {
        if((*i += *pos).is_null())rep().erase(i);
        x.erase(pos);
    }
    else
        rep().splice(i, x.rep(), pos);
}


template <typename F, typename I, bool REFCNT>
template <typename F1, typename I1, bool REFCNT1>
void sparse_polynom<F, I, REFCNT>::addsub
(
    sparse_polynom<F1, I1, REFCNT1>& x,
    typename sparse_polynom<F1, I1, REFCNT1>::monom_iterator first,
    typename sparse_polynom<F1, I1, REFCNT1>::monom_iterator last,
    const any_monom_seq_t&
)
{
    // Ïðåäïîëàãàåòñÿ, ÷òî F1 != F èëè I1 != I.
    //  ïðîòèâíîì ñëó÷àå äîëæíà âûçûâàòüñÿ äðóãàÿ ñïåöèàëèçàöèÿ ýòîé ôóíêöèè.
    // Òèïû 'Rep' äëÿ *this è äëÿ x ðàçëè÷íû, ïîýòîìó ìû íå ìîæåì ïåðåìåùàòü
    // ìîíîìû ìåæäó ýòèìè ñïèñêàìè áåç êîïèðîâàíèÿ.

    ARAGELI_ASSERT_1(static_cast<sparse_polynom_base*>(&x) != static_cast<sparse_polynom_base*>(this));

    // ÏÐÅÄÓÏÐÅÆÄÅÍÈÅ. Ïðîñòàÿ, íî ìåäëåííàÿ ðåàëèçàöèÿ, ìîæíî áûñòðåå.

    while(first != last)addsub(x, first++);
}


template <typename F, typename I, bool REFCNT>
template <bool REFCNT1>
void sparse_polynom<F, I, REFCNT>::addsub
(
    sparse_polynom<F, I, REFCNT1>& x,
    typename sparse_polynom<F, I, REFCNT1>::monom_iterator first,
    typename sparse_polynom<F, I, REFCNT1>::monom_iterator last,
    const any_monom_seq_t&
)
{
    // Ïðåäïîëàãàåòñÿ, ÷òî F1 != F èëè I1 != I.
    //  ïðîòèâíîì ñëó÷àå äîëæíà âûçûâàòüñÿ äðóãàÿ ñïåöèàëèçàöèÿ ýòîé ôóíêöèè.
    // Òèïû 'Rep' äëÿ *this è äëÿ x ðàçëè÷íû, ïîýòîìó ìû íå ìîæåì ïåðåìåùàòü
    // ìîíîìû ìåæäó ýòèìè ñïèñêàìè áåç êîïèðîâàíèÿ.

    ARAGELI_ASSERT_0(static_cast<sparse_polynom_base*>(&x) != static_cast<sparse_polynom_base*>(this));

    // ÏÐÅÄÓÏÐÅÆÄÅÍÈÅ. Ïðîñòàÿ, íî ìåäëåííàÿ ðåàëèçàöèÿ, ìîæíî áûñòðåå.

    while(first != last)addsub(x, first++);
}


template <typename F, typename I, bool REFCNT>
template <typename F1, typename I1, bool REFCNT1>
void sparse_polynom<F, I, REFCNT>::addsub
(
    sparse_polynom<F1, I1, REFCNT1>& x,
    typename sparse_polynom<F1, I1, REFCNT1>::monom_iterator first,
    typename sparse_polynom<F1, I1, REFCNT1>::monom_iterator last,
    const norm_monom_seq_t&
)
{
    // Ïðåäïîëàãàåòñÿ, ÷òî F1 != F èëè I1 != I.
    //  ïðîòèâíîì ñëó÷àå äîëæíà âûçûâàòüñÿ äðóãàÿ ñïåöèàëèçàöèÿ ýòîé ôóíêöèè.
    // Òèïû 'Rep' äëÿ *this è äëÿ x ðàçëè÷íû, ïîýòîìó ìû íå ìîæåì ïåðåìåùàòü
    // ìîíîìû ìåæäó ýòèìè ñïèñêàìè áåç êîïèðîâàíèÿ.

    ARAGELI_ASSERT_1(static_cast<sparse_polynom_base*>(&x) != static_cast<sparse_polynom_base*>(this));

    // ÏÐÅÄÓÏÐÅÆÄÅÍÈÅ. Ïðîñòàÿ, íî ìåäëåííàÿ ðåàëèçàöèÿ, ìîæíî áûñòðåå.

    while(first != last)addsub(x, first++);
}


template <typename F, typename I, bool REFCNT>
template <bool REFCNT1>
void sparse_polynom<F, I, REFCNT>::addsub
(
    sparse_polynom<F, I, REFCNT1>& x,
    typename sparse_polynom<F, I, REFCNT1>::monom_iterator first,
    typename sparse_polynom<F, I, REFCNT1>::monom_iterator last,
    const norm_monom_seq_t&
)
{
    // Ïðåäïîëàãàåòñÿ, ÷òî F1 != F èëè I1 != I.
    //  ïðîòèâíîì ñëó÷àå äîëæíà âûçûâàòüñÿ äðóãàÿ ñïåöèàëèçàöèÿ ýòîé ôóíêöèè.
    // Òèïû 'Rep' äëÿ *this è äëÿ x ðàçëè÷íû, ïîýòîìó ìû íå ìîæåì ïåðåìåùàòü
    // ìîíîìû ìåæäó ýòèìè ñïèñêàìè áåç êîïèðîâàíèÿ.

    ARAGELI_ASSERT_0(static_cast<sparse_polynom_base*>(&x) != static_cast<sparse_polynom_base*>(this));

    // ÏÐÅÄÓÏÐÅÆÄÅÍÈÅ. Ïðîñòàÿ, íî ìåäëåííàÿ ðåàëèçàöèÿ, ìîæíî áûñòðåå.

    while(first != last)addsub(x, first++);
}


template <typename F, typename I, bool REFCNT>
template <typename F1, typename I1, bool REFCNT1>
void sparse_polynom<F, I, REFCNT>::addsub
(
    sparse_polynom<F1, I1, REFCNT1>& x,
    const any_monom_seq_t&
)
{
    // Ïðåäïîëàãàåòñÿ, ÷òî F1 != F èëè I1 != I.
    //  ïðîòèâíîì ñëó÷àå äîëæíà âûçûâàòüñÿ äðóãàÿ ñïåöèàëèçàöèÿ ýòîé ôóíêöèè.
    // Òèïû 'Rep' äëÿ *this è äëÿ x ðàçëè÷íû, ïîýòîìó ìû íå ìîæåì ïåðåìåùàòü
    // ìîíîìû ìåæäó ýòèìè ñïèñêàìè áåç êîïèðîâàíèÿ.

    ARAGELI_ASSERT_1(static_cast<sparse_polynom_base*>(&x) != static_cast<sparse_polynom_base*>(this));

    // ÏÐÅÄÓÏÐÅÆÄÅÍÈÅ. Ïðîñòàÿ, íî ìåäëåííàÿ ðåàëèçàöèÿ, ìîæíî áûñòðåå.

    addsub(x, x.monoms_begin(), x.monoms_end(), any_monom_seq);
}


template <typename F, typename I, bool REFCNT>
template <bool REFCNT1>
void sparse_polynom<F, I, REFCNT>::addsub
(
    sparse_polynom<F, I, REFCNT1>& x,
    const any_monom_seq_t&
)
{
    // Ïðåäïîëàãàåòñÿ, ÷òî F1 != F èëè I1 != I.
    //  ïðîòèâíîì ñëó÷àå äîëæíà âûçûâàòüñÿ äðóãàÿ ñïåöèàëèçàöèÿ ýòîé ôóíêöèè.
    // Òèïû 'Rep' äëÿ *this è äëÿ x ðàçëè÷íû, ïîýòîìó ìû íå ìîæåì ïåðåìåùàòü
    // ìîíîìû ìåæäó ýòèìè ñïèñêàìè áåç êîïèðîâàíèÿ.

    ARAGELI_ASSERT_0(static_cast<sparse_polynom_base*>(&x) != static_cast<sparse_polynom_base*>(this));

    // ÏÐÅÄÓÏÐÅÆÄÅÍÈÅ. Ïðîñòàÿ, íî ìåäëåííàÿ ðåàëèçàöèÿ, ìîæíî áûñòðåå.

    addsub(x, x.monoms_begin(), x.monoms_end(), any_monom_seq);
}


template <typename F, typename I, bool REFCNT>
template <typename F1, typename I1, bool REFCNT1>
void sparse_polynom<F, I, REFCNT>::addsub
(
    sparse_polynom<F1, I1, REFCNT1>& x,
    const norm_monom_seq_t&
)
{
    // Ïðåäïîëàãàåòñÿ, ÷òî F1 != F èëè I1 != I.
    //  ïðîòèâíîì ñëó÷àå äîëæíà âûçûâàòüñÿ äðóãàÿ ñïåöèàëèçàöèÿ ýòîé ôóíêöèè.
    // Òèïû 'Rep' äëÿ *this è äëÿ x ðàçëè÷íû, ïîýòîìó ìû íå ìîæåì ïåðåìåùàòü
    // ìîíîìû ìåæäó ýòèìè ñïèñêàìè áåç êîïèðîâàíèÿ.

    ARAGELI_ASSERT_0(static_cast<sparse_polynom_base*>(&x) != static_cast<sparse_polynom_base*>(this));

    // ÏÐÅÄÓÏÐÅÆÄÅÍÈÅ. Ïðîñòàÿ, íî ìåäëåííàÿ ðåàëèçàöèÿ, ìîæíî áûñòðåå.

    addsub(x, x.monoms_begin(), x.monoms_end(), norm_monom_seq);
}


template <typename F, typename I, bool REFCNT>
template <bool REFCNT1>
void sparse_polynom<F, I, REFCNT>::addsub
(
    sparse_polynom<F, I, REFCNT1>& x,
    const norm_monom_seq_t&
)
{
    // Ïðåäïîëàãàåòñÿ, ÷òî F1 != F èëè I1 != I.
    //  ïðîòèâíîì ñëó÷àå äîëæíà âûçûâàòüñÿ äðóãàÿ ñïåöèàëèçàöèÿ ýòîé ôóíêöèè.
    // Òèïû 'Rep' äëÿ *this è äëÿ x ðàçëè÷íû, ïîýòîìó ìû íå ìîæåì ïåðåìåùàòü
    // ìîíîìû ìåæäó ýòèìè ñïèñêàìè áåç êîïèðîâàíèÿ.

    ARAGELI_ASSERT_0(static_cast<sparse_polynom_base*>(&x) != static_cast<sparse_polynom_base*>(this));

    // ÏÐÅÄÓÏÐÅÆÄÅÍÈÅ. Ïðîñòàÿ, íî ìåäëåííàÿ ðåàëèçàöèÿ, ìîæíî áûñòðåå.

    addsub(x, x.monoms_begin(), x.monoms_end(), norm_monom_seq);
}


template
<typename F, typename I, bool REFCNT>
void sparse_polynom<F, I, REFCNT>::normalize ()
{
    store.unique();
    rep().remove_if(func::is_null<monom>());
    rep().sort(monom_degree_less<monom>());
    
    for(typename Rep::iterator i = rep().begin();;)
    {
        i = std::adjacent_find
            (
                i, rep().end(),
                monom_degree_equal<monom>()
            );
        
        if(i == rep().end())break;

        typename Rep::iterator j = i;
        ++j;
        ARAGELI_ASSERT_1(j != rep().end());
        ARAGELI_ASSERT_1(!Arageli::is_null(*i));
        ARAGELI_ASSERT_1(!Arageli::is_null(*j));
        
        if((*j += *i).is_null())
            i = rep().erase(i);
        i = rep().erase(i);
    }   
}


// WARNING!!!
template <typename T1, typename T2>
T1 sparse_polynom_subs_helper (T1 a, const T2& b)
{ return a *= b; }


// WARNING!!!
template <typename T1, bool REFCNT, typename T2>
vector<T1, REFCNT> sparse_polynom_subs_helper (vector<T1, REFCNT> a, const T2& b)
{ return a = a*T1(b); }


// WARNING!!!
template <typename T1, bool REFCNT, typename T2>
matrix<T1, REFCNT> sparse_polynom_subs_helper (matrix<T1, REFCNT> a, const T2& b)
{ return a = a*T1(b); }


// WARNING!!!
template <typename T1, bool REFCNT, typename T2, bool REFCNT2>
matrix<T1, REFCNT> sparse_polynom_subs_helper (matrix<T1, REFCNT> a, const matrix<T2, REFCNT2>& b)
{ return a = a*b; }





template <typename F, typename I, bool REFCNT>
template <typename F1, typename Coef_factory>
F1 sparse_polynom<F, I, REFCNT>::subs (const F1& x, const Coef_factory& fctr) const
{
    ARAGELI_ASSERT_0(is_normal());

    // ÏÐÅÄÓÏÐÅÆÄÅÍÈÅ. Ýòî íå ñõåìà Ãîðíåðà.

    typedef typename Rep::const_iterator Iter;
    F1 xx = fctr.unit(x);
    F1 res = fctr.null(x);
    //std::cout << "\nxx = " << xx << "\nres = " << res;
    degree_type j = null<degree_type>();    // ñòåïåíü ýëåìåíòà x õðàíèòñÿ â xx

    // ÂÍÈÌÀÍÈÅ! ÊÎÍÖÅÏÒÓÀËÜÍÎÅ ÇÀÌÅ×ÀÍÈÅ. Ïðè âû÷èñëåíèè ïî ñõåìå Ãîðíåðà
    // òðåáóåòñÿ ðåâåðñèâíûé îáõîä ïî îòíîøåíèþ ê òîìó, êîòîðûé ïðèíÿò äëÿ
    // ïîëèíîìîâ. Îí áóäåò íå âîçìîæåí, åñëè áóäåò èñïîëüçîâàòüñÿ
    // îäíîíîñâÿçíûé êîíòåéíåð (íà ÷òî óêàçûâàåòñÿ ïðè îïðåäåëåíèè Rep).

    for(Iter i = rep().begin(); i != rep().end(); ++i)
    {
        if(j < i->degree())
        {
            xx *= power(x, i->degree() - j, fctr);
            j = i->degree();
        }

        // WARNING!!!
        //F1 xxx = xx;
        //if(type_traits<F1>::is_rational)
        //  xxx *= i->coef();
        //else
        //  xxx *= (typename type_traits<F1>::element_type)i->coef();
        //res += /*F1(*/i->coef()/*)*/ * xx;
        res += sparse_polynom_subs_helper(xx, i->coef());
        //res += xxx;
        //std::cout << "\nxx = " << xx << "\nres = " << res;
    }

    return res;
}


template <typename F, typename I, bool REFCNT>
sparse_polynom<F, I, REFCNT> diff
(const sparse_polynom<F, I, REFCNT>& x)
{
    ARAGELI_ASSERT_0(x.is_normal());

    typedef sparse_polynom<F, I, REFCNT> P;
    typedef typename P::monom_const_iterator Pmi;
    typedef typename P::monom Pm;

    if(x.is_null() || x.is_const())return P();

    P res;
    Pmi i = x.monoms_begin();
    if(is_null(i->degree()))++i;
    for(; i != x.monoms_end(); ++i)
    {
        ARAGELI_ASSERT_1(!is_null(i->degree()));
        res += Pm(i->coef() * i->degree(), i->degree() - 1);
    }
        
    return res; 
}


template <typename In, typename Ch, typename ChT>
std::basic_ostream<Ch, ChT>& polynom_output_list
(
    std::basic_ostream<Ch, ChT>& out,
    In begin, In end,
    const char* first_bracket,
    const char* second_bracket,
    const char* separator
)
{
    out << first_bracket;

    if(begin != end)
    {
        In i = begin;
        output_list(out, *i, first_bracket, second_bracket, separator);
        
        for(++i; i != end; ++i)
        {
            out << separator;
            output_list(out, *i, first_bracket, second_bracket, separator);
        }
    }

    out << second_bracket;
    return out;
}


template
<
    typename F, typename I, bool REFCNT,
    typename Ch, typename ChT
>
std::basic_ostream<Ch, ChT>& output_list
(
    std::basic_ostream<Ch, ChT>& out,
    const sparse_polynom<F, I, REFCNT>& x,
    monoms_order mo,
    const char* first_bracket,
    const char* second_bracket,
    const char* separator
)
{
    switch(mo)
    {
        case mo_inc:
            return polynom_output_list
            (
                out, _Internal::make_reverse_iterator(x.monoms_end()),
                _Internal::make_reverse_iterator(x.monoms_begin()),
                first_bracket, second_bracket, separator
            );
        case mo_dec:
            return polynom_output_list
            (
                out, x.monoms_begin(), x.monoms_end(),
                first_bracket, second_bracket, separator
            );
    }
}


template <typename In, typename Ch, typename ChT>
std::basic_ostream<Ch, ChT>& polynom_output_var
(
    std::basic_ostream<Ch, ChT>& out,
    In begin, In end,
    monoms_order mo,
    const char* var,
    const char* mul,
    const char* pow
)
{
    if(begin == end)out << "0";
    else
    {
        In i = begin;
        output_var(out, *i, true, var, mul, pow);
        
        for(++i; i != end; ++i)
            output_var(out, *i, false, var, mul, pow);
    }
    
    return out;
}


template
<
    typename F, typename I, bool REFCNT,
    typename Ch, typename ChT
>
std::basic_ostream<Ch, ChT>& output_var
(
    std::basic_ostream<Ch, ChT>& out,
    const sparse_polynom<F, I, REFCNT>& x,
    monoms_order mo,
    const char* var,
    const char* mul,
    const char* pow
)
{
    ARAGELI_ASSERT_0(mo == mo_inc || mo == mo_dec);

    switch(mo)
    {
        case mo_inc:
            return polynom_output_var
            (
                out, _Internal::make_reverse_iterator(x.monoms_end()),
                _Internal::make_reverse_iterator(x.monoms_begin()),
                mo, var, mul, pow
            );
        case mo_dec:
            return polynom_output_var
            (
                out, x.monoms_begin(), x.monoms_end(),
                mo, var, mul, pow
            );
        default:
            return out;
    }
}


template
<
    typename F, typename I, bool REFCNT,
    typename Ch, typename ChT
>
std::basic_istream<Ch, ChT>& input_list
(
    std::basic_istream<Ch, ChT>& in,
    sparse_polynom<F, I, REFCNT>& x,
    const char* fb,
    const char* sb,
    const char* sep
)
{
    ARAGELI_ASSERT_0(_Internal::is_not_contains_spaces(fb));
    ARAGELI_ASSERT_0(_Internal::is_not_contains_spaces(sb));
    ARAGELI_ASSERT_0(_Internal::is_not_contains_spaces(sep));
    ARAGELI_ASSERT_0(*sep);

    if(!_Internal::read_literal(in, fb))return in;
    typedef sparse_polynom<F, I, REFCNT> P;
    P tmp;
    typename P::monom m;
    if(!input_list(in, m))return in;
    tmp += m;
    
    while(_Internal::read_literal(in, sep)) // ïîýòîìó sep íå äîëæåí áûòü ""
    {
        if(!input_list(in, m))return in;
        tmp += m;
    }

    if(!_Internal::read_literal(in, sb))return in;
    x = tmp;

    return in;
}


template
<
    typename F, typename I, bool REFCNT,
    typename Ch, typename ChT, typename Coef_factory
>
std::basic_istream<Ch, ChT>& input_var
(
    std::basic_istream<Ch, ChT>& in,
    sparse_polynom<F, I, REFCNT>& x,
    const Coef_factory& fctr,
    const char* var,
    const char* mul,
    const char* pow
)
{
    sparse_polynom<F, I, REFCNT> res;

    char ch = 0;
    in >> ch;
    bool brackets = false;
    if(ch == '(')brackets = true;
    else in.putback(ch);

    typedef typename sparse_polynom<F, I, REFCNT>::monom monom;
    monom m;
    input_var(in, m, true, fctr, var, mul, pow);

    if(!in)
    {
        if(in.eof())
        {
            if(brackets)in.clear(std::ios_base::badbit);
            else x = m;
        }

        return in;
    }

    ch = in.get();

    if(in.eof())
    {
        if(brackets)in.clear(std::ios_base::badbit);
        else x = m;
        return in;
    }

    in.clear();
    in.putback(ch);
    
    if(ch == '\n')
    {
        if(brackets)in.clear(std::ios_base::badbit);
        else x = m;
        return in;
    }

    res += m;

    for(;;)
    {
        m = monom();
        input_var(in, m, false, fctr, var, mul, pow);
        
        if(!in)
        {
            if(in.eof())res += m;
            break;
        }

        ch = in.get();

        if(in.eof())
        {
            if(brackets)
            {
                in.clear(std::ios_base::badbit);
                return in;
            }
            
            res += m;
            break;
        }

        in.clear();
        in.putback(ch);

        if(ch == '\n')
        {
            if(brackets)
            {
                in.clear(std::ios_base::badbit);
                return in;
            }
            
            res += m;
            break;
        }

        res += m;
    }

    in.clear();
    if(brackets && !_Internal::read_literal(in, ")"))
        in.clear(std::ios_base::badbit);
    else x = res;

    return in;
}



//template
//<
//  typename F1, typename I1, bool REFCNT1, typename FT1, typename IT1,
//  typename F2, typename I2, bool REFCNT2, typename FT2, typename IT2
//>
//bool operator==
//(const sparse_polynom<F1, I1, REFCNT1, FT1, IT1>& a, const sparse_polynom<F2, I2, REFCNT2, FT2, IT2>& b)
//{
//  ARAGELI_ASSERT_0(a.is_normal());
//  ARAGELI_ASSERT_0(b.is_normal());
//
//  return a.size() == b.size() && std::equal
//  (
//      a.monoms_begin(),
//      a.monoms_end(),
//      b.monoms_begin()
//  );
//}


template <typename F, typename I>
std::istream& input_polynom_first
(std::istream& in, monom<F, I>& x)
{
    char fb = 0, sb = 0;
    monom<F, I> res;
    in >> fb >> res >> sb;
    if(fb != '(' || sb != ')')
    {
        in.clear(std::istream::badbit);
        return in;
    }

    x = res;
    return in;
}


template <typename F, typename I>
std::istream& input_polynom_internal
(std::istream& in, monom<F, I>& x)
{
    char sign = 0, fb = 0, sb = 0;
    monom<F, I> res;
    in >> sign >> fb >> res >> sb;
    if(sign != '+' || sign != '-' || fb != '(' || sb != ')')
    {
        in.clear(std::istream::badbit);
        return in;
    }

    x = res;
    if(sign == '-')x.opposite();
    return in;
}


template <typename F, typename I, bool REFCNT>
std::istream& input_polynom_first
(std::istream& in, sparse_polynom<F, I, REFCNT>& x)
{
    char fb = 0, sb = 0;
    sparse_polynom<F, I, REFCNT> res;
    in >> fb >> res >> sb;
    if(fb != '(' || sb != ')')
    {
        in.clear(std::istream::badbit);
        return in;
    }

    x = res;
    return in;
}


template <typename F, typename I, bool REFCNT>
std::istream& input_polynom_internal
(std::istream& in, sparse_polynom<F, I, REFCNT>& x)
{
    char sign = 0, fb = 0, sb = 0;
    sparse_polynom<F, I, REFCNT> res;
    in >> sign >> fb >> res >> sb;
    if((sign != '+' && sign != '-') || fb != '(' || sb != ')')
    {
        in.clear(std::istream::badbit);
        return in;
    }

    x = res;
    if(sign == '-')x.opposite();
    return in;
}


} // namespace Arageli


#else


#include "sparse_polynom.hpp"

namespace Arageli
{

const char* monom_input_list_first_bracket_default = "(";
const char* monom_output_list_first_bracket_default = "(";
const char* monom_input_list_second_bracket_default = ")";
const char* monom_output_list_second_bracket_default = ")";
const char* monom_input_list_separator_default = ",";
const char* monom_output_list_separator_default = ", ";
const char* monom_input_var_mul_default = "*";
const char* monom_output_var_mul_default = "*";
const char* monom_input_var_var_default = "x";
const char* monom_output_var_var_default = "x";
const char* monom_input_var_pow_default = "^";
const char* monom_output_var_pow_default = "^";

}

#endif

---