sparse_polynom.cpp

Go to the documentation of this file.
00001 /*****************************************************************************
00002     
00003     sparse_polynom.cpp -- Описание см. в файле sparse_polynom.hpp.
00004 
00005     Этот файл является частью библиотеки Arageli.
00006 
00007     Copyright (C) Nikolai Yu. Zolotykh, 1999--2006
00008     Copyright (C) Sergey S. Lyalin, 2005
00009     University of Nizhni Novgorod, Russia
00010 
00011 *****************************************************************************/
00012 
00013 #include "config.hpp"
00014 
00015 #if !defined(ARAGELI_INCLUDE_CPP_WITH_EXPORT_TEMPLATE) || \
00016     defined(ARAGELI_INCLUDE_CPP_WITH_EXPORT_TEMPLATE_SPARSE_POLYNOM)
00017 
00018 #include <iomanip>
00019 #include <algorithm>
00020 #include <algorithm>
00021 #include <cstring>
00022 #include <cctype>
00023 #include <iostream>
00024 #include <sstream>
00025 
00026 #include "sparse_polynom.hpp"
00027 #include "vector.hpp"
00028 #include "_utility.hpp"
00029 #include "polyalg.hpp"
00030 #include "functional.hpp"
00031 
00032 //****************************************************************************
00033 
00034 namespace Arageli
00035 {
00036 
00037 
00038 template <typename F, typename I>
00039 monom<F, I>::monom (const char* s)
00040 {
00041     std::stringstream buf(s);
00042     // WARNING. Correct if there are no virtual function.
00043     buf >> *this;
00044     if(!buf && !buf.eof())throw incorrect_string(s);
00045 }
00046 
00047 
00048 template
00049 <
00050     typename Ch, typename ChT,
00051     typename F, typename I
00052 >
00053 std::basic_ostream<Ch, ChT>& output_var
00054 (
00055     std::basic_ostream<Ch, ChT>& out,
00056     const monom<F, I>& x,
00057     bool first,
00058     const char* var,
00059     const char* mul,
00060     const char* pow
00061 )
00062 {
00063     if(x.is_const())
00064         if(first)
00065             output_polynom_first(out, x.coef());
00066         else
00067             output_polynom_internal(out, x.coef());
00068     else
00069     {
00070         if(is_opposite_unit(x.coef()))
00071             out << '-';
00072         else if(is_unit(x.coef()))
00073             { if(!first)out << '+'; }
00074         else if(first)
00075             output_polynom_first(out, x.coef()) << mul;
00076         else
00077             output_polynom_internal(out, x.coef()) << mul;
00078         out << var;
00079         if(!is_unit(x.degree()))
00080         {
00081             out << pow;
00082             output_pow(out, x.degree());
00083         }
00084     }
00085     return out;
00086 }
00087 
00088 
00089 template
00090 <
00091     typename Ch, typename ChT,
00092     typename F, typename I
00093 >
00094 std::basic_istream<Ch, ChT>& input_list
00095 (
00096     std::basic_istream<Ch, ChT>& in,
00097     monom<F, I>& x,
00098     const char* fb,
00099     const char* sb,
00100     const char* sep
00101 )
00102 {
00103     ARAGELI_ASSERT_0(_Internal::is_not_contains_spaces(fb));
00104     ARAGELI_ASSERT_0(_Internal::is_not_contains_spaces(sb));
00105     ARAGELI_ASSERT_0(_Internal::is_not_contains_spaces(sep));
00106 
00107     monom<F, I> tmp;
00108     if
00109     (!(
00110         !_Internal::read_literal(in, fb)  ||
00111         !input_polynom_first(in, tmp.coef())  ||
00112         !_Internal::read_literal(in, sep)  ||
00113         !input_pow(in, tmp.degree())  ||
00114         !_Internal::read_literal(in, sb)
00115     ))
00116         x = tmp;
00117 
00118     return in;  
00119 }
00120 
00121 
00122 template
00123 <
00124     typename Ch, typename ChT,
00125     typename F, typename I, typename Factory_coef
00126 >
00127 std::basic_istream<Ch, ChT>& input_var
00128 (
00129     std::basic_istream<Ch, ChT>& in,
00130     monom<F, I>& x,
00131     bool first_a,
00132     const Factory_coef& fctr,
00133     const char* var,
00134     const char* mul,
00135     const char* pow
00136 )
00137 {
00138     ARAGELI_ASSERT_0(_Internal::is_not_contains_spaces(var));
00139     ARAGELI_ASSERT_0(_Internal::is_not_contains_spaces(mul));
00140     ARAGELI_ASSERT_0(_Internal::is_not_contains_spaces(pow));
00141     
00142     monom<F, I> res;
00143     char ch, ch1 = 0;
00144 
00145     in >> ch1;
00146     if(!in)return in;
00147 
00148     if(ch1 != '-' && ch1 != '+')
00149     {
00150         in.putback(ch1);
00151         
00152         if(!first_a)
00153         {
00154             in.clear(std::ios_base::failbit);
00155             return in;
00156         }
00157     }
00158 
00159     if(_Internal::read_literal(in, var))
00160     {
00161         if(ch1 == '-')
00162             res.coef() = fctr.opposite_unit(x.coef());
00163         else res.coef() = fctr.unit(x.coef());
00164         
00165         ch = in.get();
00166         in.clear();
00167         in.putback(ch);
00168 
00169         if(ch != '\n' && _Internal::read_literal(in, pow))
00170         {
00171             input_pow(in, res.degree());
00172             if(!in && !in.eof())
00173             {
00174                 ARAGELI_ASSERT_1(!in.good());
00175                 return in;
00176             }
00177         }
00178         else res.degree() = unit(x.degree());
00179 
00180         x = res;
00181         in.clear();
00182         return in;
00183     }
00184 
00185     //std::cerr << "\n" << in.good();
00186     if(ch1 == '-' || ch1 == '+')in.putback(ch1);
00187     in.clear();
00188     //std::cerr << "\n" << in.good();
00189 
00190     if(first_a)
00191         input_polynom_first(in, res.coef());
00192     else
00193         input_polynom_internal(in, res.coef());
00194 
00195     if(!in)
00196     {
00197         if(!in.eof())
00198         {
00199             ARAGELI_ASSERT_1(!in.good());
00200             return in;
00201         }
00202     }
00203     else
00204     {
00205         ch = in.get();
00206         in.putback(ch);
00207         in.clear();
00208 
00209         if(!in.eof() && ch != '\n')
00210         {
00211             if(_Internal::read_literal(in, mul))
00212             {
00213                 if(!_Internal::read_literal(in, var))
00214                 {
00215                     in.clear(std::ios_base::badbit);
00216                     return in;
00217                 }
00218                 
00219                 ch = in.get();
00220                 in.clear();
00221                 in.putback(ch);
00222                 
00223                 if(ch != '\n' && _Internal::read_literal(in, pow))
00224                 {
00225                     input_pow(in, res.degree());
00226                     if(!in && !in.eof())
00227                     {
00228                         ARAGELI_ASSERT_1(!in.good());
00229                         return in;
00230                     }
00231                 }
00232                 else res.degree() = unit(x.degree());
00233             }
00234         }
00235     }
00236 
00237     x = res;
00238 
00239     in.clear();
00240     return in;
00241 }
00242 
00243 
00244 template <typename F, typename I, bool REFCNT>
00245 sparse_polynom<F, I, REFCNT>::sparse_polynom (const char* str)
00246 {
00247     std::istringstream buf(str);
00248     // WARNING. It's correct if and only if sparse_polynom has no virtual functions.
00249     static_cast<std::istream&>(buf) >> *this;
00250     if(!buf && !buf.eof())throw incorrect_string(str);
00251     //ARAGELI_ASSERT_0(buf.good() || buf.eof());
00252 }
00253 
00254 
00255 template <typename F, typename I, bool REFCNT>
00256 bool sparse_polynom<F, I, REFCNT>::is_normal () const
00257 {
00258     return std::adjacent_find
00259     (
00260         rep().begin(), rep().end(),
00261         std::not2(monom_degree_less<monom>())
00262     ) == rep().end()
00263     &&
00264     (
00265         rep().empty() ||
00266         !rep().front().is_null()
00267     );
00268 }
00269 
00270     
00271 template <typename F, typename I, bool REFCNT>
00272 sparse_polynom<F, I, REFCNT>& sparse_polynom<F, I, REFCNT>::opposite ()
00273 {
00274     ARAGELI_ASSERT_0(is_normal());
00275     
00276     if(is_null())return *this;
00277     store.unique();
00278 
00279     std::for_each
00280     (
00281         rep().begin(), rep().end(),
00282         std::mem_fun_ref(&monom::opposite)
00283     );
00284 
00285     return *this;
00286 }
00287 
00288 
00289 template <typename F, typename I, bool REFCNT>
00290 template <typename F1>
00291 sparse_polynom<F, I, REFCNT>& sparse_polynom<F, I, REFCNT>::add_scalar
00292 (const F1& x)
00293 {
00294     ARAGELI_ASSERT_0(is_normal());
00295     
00296     if(Arageli::is_null(x))return *this;
00297     store.unique();
00298     
00299     if(rep().empty() || !rep().front().is_const())
00300         rep().push_front(monom(x));
00301     else if((rep().front() += x).is_null())
00302         rep().pop_front();
00303     
00304     return *this;   
00305 }
00306 
00307 
00308 template <typename F, typename I, bool REFCNT>
00309 template <typename F1>
00310 sparse_polynom<F, I, REFCNT>& sparse_polynom<F, I, REFCNT>::sub_scalar
00311 (const F1& x)
00312 {
00313     ARAGELI_ASSERT_0(is_normal());
00314     
00315     if(Arageli::is_null(x))return *this;
00316     store.unique();
00317     
00318     if(rep().empty() || !rep().front().is_const())
00319         rep().push_front(-monom(x));
00320     else if((rep().front() -= x).is_null())
00321         rep().pop_front();
00322     
00323     return *this;   
00324 }
00325 
00326 
00327 #define _ARAGELI_SPARSE_POLYNOM_OPERATOR_ASSIGN_1(MNEM, OPER)       \
00328     template <typename F, typename I, bool REFCNT>                  \
00329     template <typename F1>                                          \
00330     sparse_polynom<F, I, REFCNT>&                                   \
00331     sparse_polynom<F, I, REFCNT>::MNEM##_scalar                     \
00332     (const F1& x)                                                   \
00333     {                                                               \
00334         ARAGELI_ASSERT_0(is_normal());                              \
00335         if(is_null())return *this;                                  \
00336                                                                     \
00337         for                                                         \
00338         (                                                           \
00339             coef_iterator i = coefs_begin(), iend = coefs_end();    \
00340             i != iend;                                              \
00341             ++i                                                     \
00342         )                                                           \
00343             /*if(Arageli::is_null(*i OPER x))                       \
00344                 i = erase(i.base());*/                              \
00345             *i OPER x;                                              \
00346                                                                     \
00347         normalize();    /* WARNING! We don't need full normalize! */\
00348         return *this;                                               \
00349     }
00350 
00351 _ARAGELI_SPARSE_POLYNOM_OPERATOR_ASSIGN_1(mul, *=);
00352 _ARAGELI_SPARSE_POLYNOM_OPERATOR_ASSIGN_1(div, /=);
00353 _ARAGELI_SPARSE_POLYNOM_OPERATOR_ASSIGN_1(mod, %=);
00354 _ARAGELI_SPARSE_POLYNOM_OPERATOR_ASSIGN_1(bitor, |=);
00355 _ARAGELI_SPARSE_POLYNOM_OPERATOR_ASSIGN_1(bitand, &=);
00356 _ARAGELI_SPARSE_POLYNOM_OPERATOR_ASSIGN_1(bitxor, ^=);
00357 _ARAGELI_SPARSE_POLYNOM_OPERATOR_ASSIGN_1(shl, <<=);
00358 _ARAGELI_SPARSE_POLYNOM_OPERATOR_ASSIGN_1(shr, >>=);
00359 
00360 
00361 //template <typename F, typename I, bool REFCNT>
00362 //template <typename F1>
00363 //sparse_polynom<F, I, REFCNT>& sparse_polynom<F, I, REFCNT>::div_scalar
00364 //(const F1& x)
00365 //{
00366 //  // ПРЕДУПРЕЖДЕНИЕ. Простая, но медленная реализация. Можно быстрее.
00367 //
00368 //  return operator/=(monom(x));
00369 //}
00370 //
00371 //
00372 //template <typename F, typename I, bool REFCNT>
00373 //template <typename F1>
00374 //sparse_polynom<F, I, REFCNT>& sparse_polynom<F, I, REFCNT>::operator%=
00375 //(const F1& x)
00376 //{
00377 //  // ПРЕДУПРЕЖДЕНИЕ. Простая, но медленная реализация. Можно быстрее.
00378 //
00379 //  return operator%=(monom(x));
00380 //}
00381 
00382 
00383 template <typename F, typename I, bool REFCNT>
00384 template <typename F1, typename I1>
00385 sparse_polynom<F, I, REFCNT>& sparse_polynom<F, I, REFCNT>::operator+=
00386 (const Arageli::monom<F1, I1>& x)
00387 {
00388     ARAGELI_ASSERT_0(is_normal());
00389     
00390     if(x.is_null())return *this;
00391     store.unique();
00392     typename Rep::iterator i = find_pos(x);
00393 
00394     if(i != rep().end() && x.can_add(*i))
00395     {
00396         if((*i += x).is_null())
00397             rep().erase(i);
00398     }
00399     else
00400         rep().insert(i, x);
00401 
00402     return *this;
00403 }
00404 
00405 
00406 template <typename F, typename I, bool REFCNT>
00407 template <typename F1, typename I1>
00408 sparse_polynom<F, I, REFCNT>& sparse_polynom<F, I, REFCNT>::operator-=
00409 (const Arageli::monom<F1, I1>& x)
00410 {
00411     ARAGELI_ASSERT_0(is_normal());
00412     
00413     // ПРЕДУПРЕЖДЕНИЕ. Простая, но медленная реализация, можно быстрее.
00414     
00415     return operator+=(-x);  
00416 }
00417 
00418 
00419 template <typename F, typename I, bool REFCNT>
00420 template <typename F1, typename I1>
00421 sparse_polynom<F, I, REFCNT>& sparse_polynom<F, I, REFCNT>::operator*=
00422 (const Arageli::monom<F1, I1>& x)
00423 {
00424     ARAGELI_ASSERT_0(is_normal());
00425     
00426     if(x.is_unit())return *this;
00427 
00428     if(x.is_null())
00429     {
00430         if(store.unique_clear())rep().clear();
00431         return *this;
00432     }
00433 
00434     store.unique();
00435 
00436     // WARNING!!!
00437     Arageli::monom<F1, I1> xx = x;  // copy because x maybe part of this polynomial
00438 
00439     for(typename Rep::iterator i = rep().begin(); i != rep().end();)
00440         if((*i *= xx).is_null())
00441             i = rep().erase(i);
00442         else ++i;
00443 
00444     return *this;
00445 }
00446 
00447 
00448 template <typename F, typename I, bool REFCNT>
00449 template <typename F1, typename I1>
00450 sparse_polynom<F, I, REFCNT>& sparse_polynom<F, I, REFCNT>::operator/=
00451 (const Arageli::monom<F1, I1>& x)
00452 {
00453     ARAGELI_ASSERT_0(is_normal());
00454     ARAGELI_ASSERT_0(!x.is_null());
00455     
00456     if(x.is_unit())return *this;
00457     store.unique();
00458 
00459     Arageli::monom<F1, I1> xx = x;  // copy because x maybe part of this polynomial
00460 
00461     for(typename Rep::iterator i = find_pos(x); i != rep().end();)
00462         if((*i /= xx).is_null())
00463             i = rep().erase(i);
00464         else ++i;
00465 
00466     return *this;
00467 }
00468 
00469 
00470 template <typename F, typename I, bool REFCNT>
00471 template <typename T1>
00472 sparse_polynom<F, I, REFCNT>&
00473 sparse_polynom<F, I, REFCNT>::add_sparse_polynom
00474 (const T1& x)
00475 {
00476     ARAGELI_ASSERT_0(is_normal());
00477     ARAGELI_ASSERT_0(x.is_normal());
00478 
00479     if(x.is_null())return *this;
00480 
00481     store.unique();
00482     if
00483     (
00484         reinterpret_cast<const void*>(this) ==
00485         reinterpret_cast<const void*>(&x))
00486     {
00487         ARAGELI_ASSERT_0(!is_null());
00488         for(typename Rep::iterator i = rep().begin(); i != rep().end();)
00489             if((*i += *i).is_null())
00490                 i = rep().erase(i);
00491             else ++i;
00492     }
00493     else
00494     {
00495         monom_iterator i1 = monoms_begin(), i1end = monoms_end();
00496         typename T1::monom_const_iterator i2 = x.monoms_begin(),
00497             i2end = x.monoms_end();
00498 
00499         while(i1 != i1end && i2 != i2end)
00500         {
00501             if(i1->degree() < i2->degree())++i1;
00502             else if(i1->degree() == i2->degree())
00503             {
00504                 if((*i1 += *i2).is_null())
00505                     i1 = rep().erase(i1);
00506                 else ++i1;
00507                 ++i2;
00508             }
00509             else
00510             { // i1->degree() > i2->degree()
00511                 rep().insert(i1, *i2);
00512                 ++i2;
00513             }
00514         }
00515 
00516         if(i2 != x.rep().end())
00517         {
00518             ARAGELI_ASSERT_1(i1 == monoms_end());
00519             rep().insert(i1, i2, x.monoms_end());
00520         }
00521     }
00522 
00523     return *this;
00524 }
00525 
00526 
00527 template <typename F, typename I, bool REFCNT>
00528 template <typename T1>
00529 sparse_polynom<F, I, REFCNT>&
00530 sparse_polynom<F, I, REFCNT>::sub_sparse_polynom
00531 (const T1& x)
00532 {
00533     ARAGELI_ASSERT_0(is_normal());
00534     ARAGELI_ASSERT_0(x.is_normal());
00535 
00536     // ПРЕДУПРЕЖДЕНИЕ. Простая, но медленная реализация, можно быстрее.
00537     
00538     return operator+=(-x);
00539 }
00540 
00541 
00542 template <typename F, typename I, bool REFCNT>
00543 template <typename T1>
00544 sparse_polynom<F, I, REFCNT>&
00545 sparse_polynom<F, I, REFCNT>::mul_sparse_polynom
00546 (const T1& x)
00547 {
00548     ARAGELI_ASSERT_0(is_normal());
00549     ARAGELI_ASSERT_0(x.is_normal());
00550 
00551     // ПРЕДУПРЕЖДЕНИЕ. Простая, но медленная реализация, можно быстрее.
00552 
00553     if(is_null())return *this;
00554     if(x.is_null())
00555     {
00556         if(store.unique_clear())rep().clear();
00557         return *this;
00558     }
00559 
00560     sparse_polynom res;
00561     for
00562     (
00563         typename T1::monom_const_iterator i =
00564             x.monoms_begin(), iend = x.monoms_end();
00565         i != iend;
00566         ++i
00567     )
00568     {
00569         sparse_polynom t(*this);
00570         t *= *i;
00571         res += t;
00572     }
00573 
00574     *this = res;
00575     return *this;
00576 }
00577 
00578 
00579 template <typename F, typename I, bool REFCNT>
00580 template <typename T1>
00581 sparse_polynom<F, I, REFCNT>&
00582 sparse_polynom<F, I, REFCNT>::div_sparse_polynom
00583 (const T1& x)
00584 {
00585     ARAGELI_ASSERT_0(x.is_normal());
00586     ARAGELI_ASSERT_0(is_normal());
00587 
00588     if(is_null())return *this;
00589     if(x.is_null())throw division_by_zero();
00590     
00591     if(degree() < x.degree())
00592     {
00593         if(store.unique_clear())rep().clear();
00594         return *this;
00595     }
00596 
00597     assign_div(*this, x);
00598     return *this;
00599 }
00600 
00601 
00602 // WARNING! The second arg should more common.
00603 template <typename F, typename I, bool REFCNT>
00604 template <typename F1, typename I1, bool REFCNT1>
00605 void sparse_polynom<F, I, REFCNT>::assign_div_common
00606 (
00607     sparse_polynom& x,
00608     const sparse_polynom<F1, I1, REFCNT1>& y
00609 )
00610 {
00611     ARAGELI_ASSERT_1(x.is_normal());
00612     ARAGELI_ASSERT_1(y.is_normal());
00613 
00614 #if 1
00615 
00616     sparse_polynom pq, pr;
00617     polynom_divide(x, y, pq, pr);
00618     x = pq;
00619 
00620 #else
00621 
00622     ARAGELI_ASSERT_1(!x.is_null());
00623     ARAGELI_ASSERT_1(!y.is_null());
00624     
00625     // ПРЕДУПРЕЖДЕНИЕ. Простая, но медленная реализация, можно быстрее.
00626     // WARNING. This implementation is simple but is slow, may be quicker.
00627 
00628     // WARNING. This algorithm works only if F and F1 are fields.
00629 
00630     sparse_polynom t(x);
00631     sparse_polynom res;
00632 
00633     while(!t.is_null() && t.degree() >= y.degree())
00634     {
00635         ARAGELI_ASSERT_0(!t.is_null());
00636         monom mt = t.leading_monom();
00637         mt /= y.leading_monom();    // maybe integer division
00638         if(mt.is_null())break;
00639         sparse_polynom<F1, I1, REFCNT1> tx(y);
00640         //std::cout << "\ntx before = " << tx;
00641         tx *= mt;
00642         //std::cout << "\nmt sumtraction = " << mt;
00643         //std::cout << "\ntx after = " << tx;
00644         //std::cout << "\nt before sumtraction = " << t;
00645         ARAGELI_ASSERT_0(!tx.is_null());
00646         t -= tx;
00647         //std::cout << "\nt after sumtraction = " << t;
00648         res += mt;
00649     }
00650 
00651     x = res;
00652 
00653 #endif
00654 }
00655 
00656 
00657 //template <typename F, typename I, bool REFCNT, typename FT, typename IT>
00658 //template
00659 //<
00660 //  typename I1, bool REFCNT1, typename FT1, typename IT1,
00661 //  typename I2, bool REFCNT2, typename FT2, typename IT2,
00662 //  typename TT3, typename TT4
00663 //>
00664 //void sparse_polynom<F, I, REFCNT, FT, IT>::assign_div
00665 //(
00666 //  sparse_polynom<rational<big_int>, I1, REFCNT1, FT1, IT1>& x,
00667 //  const sparse_polynom<rational<big_int, TT4>, I2, REFCNT2, FT2, IT2>& y
00668 //)
00669 //{
00670 //  ARAGELI_ASSERT_1(x.is_normal());
00671 //  ARAGELI_ASSERT_1(y.is_normal());
00672 //  ARAGELI_ASSERT_1(!x.is_null());
00673 //  ARAGELI_ASSERT_1(!y.is_null());
00674 //  
00675 //  ARAGELI_ASSERT_1
00676 //  ((
00677 //      equal_types
00678 //      <
00679 //          sparse_polynom<F, I, REFCNT, FT, IT>,
00680 //          sparse_polynom<rational<big_int>, I1, REFCNT1, FT1, IT1>
00681 //      >::bvalue
00682 //  ));
00683 //
00684 //  typedef
00685 //      typename sparse_polynom
00686 //          <rational<big_int, TT4>, I2, REFCNT2, FT2, IT2>::coef_const_iterator
00687 //              Iter_y;
00688 //  
00689 //  vector<big_int> numers(x.size()), denoms(y.size());
00690 //  //vector<big_int>
00691 //  //  numers(x.coefs_begin(), x.coefs_end()),
00692 //  //  denoms(y.coefs_begin(), y.coefs_end());
00693 //
00694 //  std::transform
00695 //  (
00696 //      x.coefs_begin(), x.coefs_end(),
00697 //      numers.begin(), select_denom<big_int>()
00698 //  );
00699 //
00700 //  std::transform
00701 //  (
00702 //      y.coefs_begin(), y.coefs_end(),
00703 //      denoms.begin(), select_denom<big_int, TT4>()
00704 //  );
00705 //
00706 //  std::cout << "\nthe first polynomial: " << x;
00707 //  std::cout << "\nthe second polynomial: " << y;
00708 //  std::cout << "\nnumber: ";
00709 //  vector_output_row(std::cout, numers);
00710 //  std::cout << "\ndenoms: ";
00711 //  vector_output_row(std::cout, denoms);
00712 //
00713 //  //std::copy(x.coefs_begin(), x.coefs_end(), numers);
00714 //  //std::copy(y.coefs_begin(), y.coefs_end(), denoms);
00715 //  //std::size_t ii = 0;
00716 //  //for(coef_iterator i = x.coefs_begin(); i != x.coefs_end(); ++i, ++ii)
00717 //  //  numers[ii] = i->denominator();
00718 //
00719 //  //ii = 0;
00720 //  //for(Iter_y i = y.coefs_begin(); i != y.coefs_end(); ++i)
00721 //  //  denoms[ii] = i->denominator();
00722 //
00723 //  big_int numerator = product(numers), denominator = product(denoms);
00724 //
00725 //  std::cout << "\nnumer: " << numerator;
00726 //  std::cout << "\ndenom: " << denominator;
00727 //
00728 //  sparse_polynom<big_int, I2, REFCNT2, TT4, IT2>
00729 //      yy = y*denominator; // yy contains only integer coefficients
00730 //
00731 //  ARAGELI_ASSERT_1(yy == y*denominator);
00732 //
00733 //  numerator *= power(yy.leading_coef(), x.degree());
00734 //
00735 //  std::cout << "\nnumer: " << numerator;
00736 //
00737 //  sparse_polynom<big_int, I1, REFCNT1, IT1>
00738 //      xx = x*numerator;   // x contains only integer coefficients
00739 //
00740 //  ARAGELI_ASSERT_1(xx == x*numerator);
00741 //
00742 //  std::cout << "\nthe xx polynomial: " << xx;
00743 //  std::cout << "\nthe yy polynomial: " << yy << std::flush;
00744 //
00745 //  xx /= yy;   // division without remainders in integer division
00746 //
00747 //  ARAGELI_DEBUG_EXEC_1(sparse_polynom tt = x);
00748 //  ARAGELI_DEBUG_EXEC_1(assign_div_common(tt, y));
00749 //  
00750 //  x = xx;
00751 //  
00752 //  for(coef_iterator i = x.coefs_begin(); i != x.coefs_end(); ++i)
00753 //      *i = *i / numerator * denominator;
00754 //
00755 //  std::cout << "\nthe result: " << x;
00756 //  
00757 //  ARAGELI_ASSERT_1(tt == x);
00758 //  ARAGELI_DEBUG_EXEC_1(std::cout << "\nthe common result: " << tt);
00759 //  std::cout << std::flush;
00760 //}
00761 
00762 
00763 template <typename F, typename I, bool REFCNT>
00764 template <typename T1>
00765 sparse_polynom<F, I, REFCNT>&
00766 sparse_polynom<F, I, REFCNT>::mod_sparse_polynom
00767 (const T1& x)
00768 {
00769     ARAGELI_ASSERT_0(is_normal());
00770     ARAGELI_ASSERT_0(x.is_normal());
00771 
00772     // ПРЕДУПРЕЖДЕНИЕ. Простая, но медленная реализация, можно быстрее.
00773     // WARNING. This implementation is simple but is slow, maybe quicker.
00774 
00775     if(is_null())return *this;
00776     if(x.is_null())throw division_by_zero();
00777     
00778 #if 1
00779 
00780     sparse_polynom pq, pr;
00781     polynom_divide(*this, x, pq, pr);
00782     *this = pr;
00783 
00784 #else
00785 
00786     if(degree() < x.degree())return *this;
00787     sparse_polynom res(*this);
00788 
00789     while(!res.is_null() && res.degree() >= x.degree())
00790     {
00791         monom mt = res.leading_monom();
00792         mt /= x.leading_monom();
00793         if(mt.is_null())break;
00794         T1 tx(x);
00795         tx *= mt;
00796         res -= tx;
00797     }
00798 
00799     *this = res;
00800 
00801 #endif
00802 
00803     return *this;
00804 }
00805 
00806 
00807 //template <typename F, typename I, bool REFCNT, typename FT, typename IT>
00808 //template <typename I1>
00809 //sparse_polynom<F, I, REFCNT, FT, IT>& sparse_polynom<F, I, REFCNT, FT, IT>::pow (I1 x)
00810 //{
00811 //  // Неявно предполагается, что x >= 0. Пока нельзя написать assert, так как
00812 //  // в type_traits нет функции, которая определяет знак элемента.
00813 //
00814 //  if(is_null() && type_traits<I1>::is_null(x))throw zero_in_zero_degree();
00815 //  
00816 //  if(type_traits<I1>::is_null(x))
00817 //  {
00818 //      if(store.unique_clear())rep().clear();
00819 //      rep().push_back(monom(coef_traits::unit()));
00820 //  }
00821 //  else if(!type_traits<I1>::is_unit(x))
00822 //  {
00823 //      sparse_polynom t = *this;
00824 //      for(--x; !type_traits<I1>::is_null(x); --x)
00825 //          *this *= t;
00826 //  }
00827 //
00828 //  return *this;
00829 //}
00830 
00831 
00832 template <typename F, typename I, bool REFCNT>
00833 template <typename Iter>
00834 void sparse_polynom<F, I, REFCNT>::add
00835 (Iter first, Iter last, const any_monom_seq_t&)
00836 {
00837     // ПРЕДУПРЕЖДЕНИЕ. 'first' и 'last' не должны быть итераторами
00838     // для данного объекта полинома.
00839 
00840     // ПРЕДУПРЕЖДЕНИЕ. Простая, но медленная реализация, можно быстрее.
00841 
00842     while(first != last)*this += *first++;
00843 }
00844 
00845 
00846 template <typename F, typename I, bool REFCNT>
00847 template <typename Iter>
00848 void sparse_polynom<F, I, REFCNT>::add
00849 (Iter first, Iter last, const norm_monom_seq_t&)
00850 {
00851     // ПРЕДУПРЕЖДЕНИЕ. 'first' и 'last' не должны быть итераторами
00852     // для данного объекта полинома.
00853 
00854     // ПРЕДУПРЕЖДЕНИЕ. Простая, но медленная реализация, можно быстрее.
00855 
00856     while(first != last)*this += *first++;
00857 }
00858 
00859 
00860 template <typename F, typename I, bool REFCNT>
00861 template <typename Iter>
00862 void sparse_polynom<F, I, REFCNT>::sub
00863 (Iter first, Iter last, const any_monom_seq_t&)
00864 {
00865     // ПРЕДУПРЕЖДЕНИЕ. 'first' и 'last' не должны быть итераторами
00866     // для данного объекта полинома.
00867 
00868     // ПРЕДУПРЕЖДЕНИЕ. Простая, но медленная реализация, можно быстрее.
00869 
00870     while(first != last)*this -= *first++;
00871 }
00872 
00873 
00874 template <typename F, typename I, bool REFCNT>
00875 template <typename Iter>
00876 void sparse_polynom<F, I, REFCNT>::sub
00877 (Iter first, Iter last, const norm_monom_seq_t&)
00878 {
00879     // ПРЕДУПРЕЖДЕНИЕ. 'first' и 'last' не должны быть итераторами
00880     // для данного объекта полинома.
00881 
00882     // ПРЕДУПРЕЖДЕНИЕ. Простая, но медленная реализация, можно быстрее.
00883 
00884     while(first != last)*this -= *first++;
00885 }
00886 
00887 
00888 template <typename F, typename I, bool REFCNT>
00889 template <typename F1, typename I1, bool REFCNT1>
00890 void sparse_polynom<F, I, REFCNT>::addsub
00891 (
00892     sparse_polynom<F1, I1, REFCNT1>& x,
00893     typename sparse_polynom<F1, I1, REFCNT1>::monom_iterator pos
00894 )
00895 {
00896     // Предполагается, что F1 != F или I1 != I.
00897     // В противном случае должна вызываться другая специализация этой функции.
00898     // Типы 'Rep' для *this и для x различны, поэтому мы не можем перемещать
00899     // мономы между этими списками без копирования.
00900 
00901     ARAGELI_ASSERT_0(pos != x.rep().end());
00902 
00903     *this += *pos;
00904     x.erase(pos);
00905 }
00906 
00907 
00908 template <typename F, typename I, bool REFCNT>
00909 template <bool REFCNT1>
00910 void sparse_polynom<F, I, REFCNT>::addsub
00911 (
00912     sparse_polynom<F, I, REFCNT1>& x,
00913     typename sparse_polynom<F, I, REFCNT1>::monom_iterator pos
00914 )
00915 {
00916     // Так как F и I для обоих полиномов (и для '*this' и для 'x') одинаковы,
00917     // то типы 'Rep' для них должны быть эквивалентны.
00918     // Поэтому применяем обычные операции со списками, где это возможно.
00919 
00920     ARAGELI_ASSERT_0(pos != x.rep().end());
00921 
00922     unique();
00923 
00924     typename Rep::iterator i = find_pos(*pos);
00925     if(i != rep().end() && pos->can_add(*i))
00926     {
00927         if((*i += *pos).is_null())rep().erase(i);
00928         x.erase(pos);
00929     }
00930     else
00931         rep().splice(i, x.rep(), pos);
00932 }
00933 
00934 
00935 template <typename F, typename I, bool REFCNT>
00936 template <typename F1, typename I1, bool REFCNT1>
00937 void sparse_polynom<F, I, REFCNT>::addsub
00938 (
00939     sparse_polynom<F1, I1, REFCNT1>& x,
00940     typename sparse_polynom<F1, I1, REFCNT1>::monom_iterator first,
00941     typename sparse_polynom<F1, I1, REFCNT1>::monom_iterator last,
00942     const any_monom_seq_t&
00943 )
00944 {
00945     // Предполагается, что F1 != F или I1 != I.
00946     // В противном случае должна вызываться другая специализация этой функции.
00947     // Типы 'Rep' для *this и для x различны, поэтому мы не можем перемещать
00948     // мономы между этими списками без копирования.
00949 
00950     ARAGELI_ASSERT_1(static_cast<sparse_polynom_base*>(&x) != static_cast<sparse_polynom_base*>(this));
00951 
00952     // ПРЕДУПРЕЖДЕНИЕ. Простая, но медленная реализация, можно быстрее.
00953 
00954     while(first != last)addsub(x, first++);
00955 }
00956 
00957 
00958 template <typename F, typename I, bool REFCNT>
00959 template <bool REFCNT1>
00960 void sparse_polynom<F, I, REFCNT>::addsub
00961 (
00962     sparse_polynom<F, I, REFCNT1>& x,
00963     typename sparse_polynom<F, I, REFCNT1>::monom_iterator first,
00964     typename sparse_polynom<F, I, REFCNT1>::monom_iterator last,
00965     const any_monom_seq_t&
00966 )
00967 {
00968     // Предполагается, что F1 != F или I1 != I.
00969     // В противном случае должна вызываться другая специализация этой функции.
00970     // Типы 'Rep' для *this и для x различны, поэтому мы не можем перемещать
00971     // мономы между этими списками без копирования.
00972 
00973     ARAGELI_ASSERT_0(static_cast<sparse_polynom_base*>(&x) != static_cast<sparse_polynom_base*>(this));
00974 
00975     // ПРЕДУПРЕЖДЕНИЕ. Простая, но медленная реализация, можно быстрее.
00976 
00977     while(first != last)addsub(x, first++);
00978 }
00979 
00980 
00981 template <typename F, typename I, bool REFCNT>
00982 template <typename F1, typename I1, bool REFCNT1>
00983 void sparse_polynom<F, I, REFCNT>::addsub
00984 (
00985     sparse_polynom<F1, I1, REFCNT1>& x,
00986     typename sparse_polynom<F1, I1, REFCNT1>::monom_iterator first,
00987     typename sparse_polynom<F1, I1, REFCNT1>::monom_iterator last,
00988     const norm_monom_seq_t&
00989 )
00990 {
00991     // Предполагается, что F1 != F или I1 != I.
00992     // В противном случае должна вызываться другая специализация этой функции.
00993     // Типы 'Rep' для *this и для x различны, поэтому мы не можем перемещать
00994     // мономы между этими списками без копирования.
00995 
00996     ARAGELI_ASSERT_1(static_cast<sparse_polynom_base*>(&x) != static_cast<sparse_polynom_base*>(this));
00997 
00998     // ПРЕДУПРЕЖДЕНИЕ. Простая, но медленная реализация, можно быстрее.
00999 
01000     while(first != last)addsub(x, first++);
01001 }
01002 
01003 
01004 template <typename F, typename I, bool REFCNT>
01005 template <bool REFCNT1>
01006 void sparse_polynom<F, I, REFCNT>::addsub
01007 (
01008     sparse_polynom<F, I, REFCNT1>& x,
01009     typename sparse_polynom<F, I, REFCNT1>::monom_iterator first,
01010     typename sparse_polynom<F, I, REFCNT1>::monom_iterator last,
01011     const norm_monom_seq_t&
01012 )
01013 {
01014     // Предполагается, что F1 != F или I1 != I.
01015     // В противном случае должна вызываться другая специализация этой функции.
01016     // Типы 'Rep' для *this и для x различны, поэтому мы не можем перемещать
01017     // мономы между этими списками без копирования.
01018 
01019     ARAGELI_ASSERT_0(static_cast<sparse_polynom_base*>(&x) != static_cast<sparse_polynom_base*>(this));
01020 
01021     // ПРЕДУПРЕЖДЕНИЕ. Простая, но медленная реализация, можно быстрее.
01022 
01023     while(first != last)addsub(x, first++);
01024 }
01025 
01026 
01027 template <typename F, typename I, bool REFCNT>
01028 template <typename F1, typename I1, bool REFCNT1>
01029 void sparse_polynom<F, I, REFCNT>::addsub
01030 (
01031     sparse_polynom<F1, I1, REFCNT1>& x,
01032     const any_monom_seq_t&
01033 )
01034 {
01035     // Предполагается, что F1 != F или I1 != I.
01036     // В противном случае должна вызываться другая специализация этой функции.
01037     // Типы 'Rep' для *this и для x различны, поэтому мы не можем перемещать
01038     // мономы между этими списками без копирования.
01039 
01040     ARAGELI_ASSERT_1(static_cast<sparse_polynom_base*>(&x) != static_cast<sparse_polynom_base*>(this));
01041 
01042     // ПРЕДУПРЕЖДЕНИЕ. Простая, но медленная реализация, можно быстрее.
01043 
01044     addsub(x, x.monoms_begin(), x.monoms_end(), any_monom_seq);
01045 }
01046 
01047 
01048 template <typename F, typename I, bool REFCNT>
01049 template <bool REFCNT1>
01050 void sparse_polynom<F, I, REFCNT>::addsub
01051 (
01052     sparse_polynom<F, I, REFCNT1>& x,
01053     const any_monom_seq_t&
01054 )
01055 {
01056     // Предполагается, что F1 != F или I1 != I.
01057     // В противном случае должна вызываться другая специализация этой функции.
01058     // Типы 'Rep' для *this и для x различны, поэтому мы не можем перемещать
01059     // мономы между этими списками без копирования.
01060 
01061     ARAGELI_ASSERT_0(static_cast<sparse_polynom_base*>(&x) != static_cast<sparse_polynom_base*>(this));
01062 
01063     // ПРЕДУПРЕЖДЕНИЕ. Простая, но медленная реализация, можно быстрее.
01064 
01065     addsub(x, x.monoms_begin(), x.monoms_end(), any_monom_seq);
01066 }
01067 
01068 
01069 template <typename F, typename I, bool REFCNT>
01070 template <typename F1, typename I1, bool REFCNT1>
01071 void sparse_polynom<F, I, REFCNT>::addsub
01072 (
01073     sparse_polynom<F1, I1, REFCNT1>& x,
01074     const norm_monom_seq_t&
01075 )
01076 {
01077     // Предполагается, что F1 != F или I1 != I.
01078     // В противном случае должна вызываться другая специализация этой функции.
01079     // Типы 'Rep' для *this и для x различны, поэтому мы не можем перемещать
01080     // мономы между этими списками без копирования.
01081 
01082     ARAGELI_ASSERT_0(static_cast<sparse_polynom_base*>(&x) != static_cast<sparse_polynom_base*>(this));
01083 
01084     // ПРЕДУПРЕЖДЕНИЕ. Простая, но медленная реализация, можно быстрее.
01085 
01086     addsub(x, x.monoms_begin(), x.monoms_end(), norm_monom_seq);
01087 }
01088 
01089 
01090 template <typename F, typename I, bool REFCNT>
01091 template <bool REFCNT1>
01092 void sparse_polynom<F, I, REFCNT>::addsub
01093 (
01094     sparse_polynom<F, I, REFCNT1>& x,
01095     const norm_monom_seq_t&
01096 )
01097 {
01098     // Предполагается, что F1 != F или I1 != I.
01099     // В противном случае должна вызываться другая специализация этой функции.
01100     // Типы 'Rep' для *this и для x различны, поэтому мы не можем перемещать
01101     // мономы между этими списками без копирования.
01102 
01103     ARAGELI_ASSERT_0(static_cast<sparse_polynom_base*>(&x) != static_cast<sparse_polynom_base*>(this));
01104 
01105     // ПРЕДУПРЕЖДЕНИЕ. Простая, но медленная реализация, можно быстрее.
01106 
01107     addsub(x, x.monoms_begin(), x.monoms_end(), norm_monom_seq);
01108 }
01109 
01110 
01111 template
01112 <typename F, typename I, bool REFCNT>
01113 void sparse_polynom<F, I, REFCNT>::normalize ()
01114 {
01115     store.unique();
01116     rep().remove_if(func::is_null<monom>());
01117     rep().sort(monom_degree_less<monom>());
01118     
01119     for(typename Rep::iterator i = rep().begin();;)
01120     {
01121         i = std::adjacent_find
01122             (
01123                 i, rep().end(),
01124                 monom_degree_equal<monom>()
01125             );
01126         
01127         if(i == rep().end())break;
01128 
01129         typename Rep::iterator j = i;
01130         ++j;
01131         ARAGELI_ASSERT_1(j != rep().end());
01132         ARAGELI_ASSERT_1(!Arageli::is_null(*i));
01133         ARAGELI_ASSERT_1(!Arageli::is_null(*j));
01134         
01135         if((*j += *i).is_null())
01136             i = rep().erase(i);
01137         i = rep().erase(i);
01138     }   
01139 }
01140 
01141 
01142 // WARNING!!!
01143 template <typename T1, typename T2>
01144 T1 sparse_polynom_subs_helper (T1 a, const T2& b)
01145 { return a *= b; }
01146 
01147 
01148 // WARNING!!!
01149 template <typename T1, bool REFCNT, typename T2>
01150 vector<T1, REFCNT> sparse_polynom_subs_helper (vector<T1, REFCNT> a, const T2& b)
01151 { return a = a*T1(b); }
01152 
01153 
01154 // WARNING!!!
01155 template <typename T1, bool REFCNT, typename T2>
01156 matrix<T1, REFCNT> sparse_polynom_subs_helper (matrix<T1, REFCNT> a, const T2& b)
01157 { return a = a*T1(b); }
01158 
01159 
01160 // WARNING!!!
01161 template <typename T1, bool REFCNT, typename T2, bool REFCNT2>
01162 matrix<T1, REFCNT> sparse_polynom_subs_helper (matrix<T1, REFCNT> a, const matrix<T2, REFCNT2>& b)
01163 { return a = a*b; }
01164 
01165 
01166 
01167 
01168 
01169 template <typename F, typename I, bool REFCNT>
01170 template <typename F1, typename Coef_factory>
01171 F1 sparse_polynom<F, I, REFCNT>::subs (const F1& x, const Coef_factory& fctr) const
01172 {
01173     ARAGELI_ASSERT_0(is_normal());
01174 
01175     // ПРЕДУПРЕЖДЕНИЕ. Это не схема Горнера.
01176 
01177     typedef typename Rep::const_iterator Iter;
01178     F1 xx = fctr.unit(x);
01179     F1 res = fctr.null(x);
01180     //std::cout << "\nxx = " << xx << "\nres = " << res;
01181     degree_type j = null<degree_type>();    // степень элемента x хранится в xx
01182 
01183     // ВНИМАНИЕ! КОНЦЕПТУАЛЬНОЕ ЗАМЕЧАНИЕ. При вычислении по схеме Горнера
01184     // требуется реверсивный обход по отношению к тому, который принят для
01185     // полиномов. Он будет не возможен, если будет использоваться
01186     // одноносвязный контейнер (на что указывается при определении Rep).
01187 
01188     for(Iter i = rep().begin(); i != rep().end(); ++i)
01189     {
01190         if(j < i->degree())
01191         {
01192             xx *= power(x, i->degree() - j, fctr);
01193             j = i->degree();
01194         }
01195 
01196         // WARNING!!!
01197         //F1 xxx = xx;
01198         //if(type_traits<F1>::is_rational)
01199         //  xxx *= i->coef();
01200         //else
01201         //  xxx *= (typename type_traits<F1>::element_type)i->coef();
01202         //res += /*F1(*/i->coef()/*)*/ * xx;
01203         res += sparse_polynom_subs_helper(xx, i->coef());
01204         //res += xxx;
01205         //std::cout << "\nxx = " << xx << "\nres = " << res;
01206     }
01207 
01208     return res;
01209 }
01210 
01211 
01212 template <typename F, typename I, bool REFCNT>
01213 sparse_polynom<F, I, REFCNT> diff
01214 (const sparse_polynom<F, I, REFCNT>& x)
01215 {
01216     ARAGELI_ASSERT_0(x.is_normal());
01217 
01218     typedef sparse_polynom<F, I, REFCNT> P;
01219     typedef typename P::monom_const_iterator Pmi;
01220     typedef typename P::monom Pm;
01221 
01222     if(x.is_null() || x.is_const())return P();
01223 
01224     P res;
01225     Pmi i = x.monoms_begin();
01226     if(is_null(i->degree()))++i;
01227     for(; i != x.monoms_end(); ++i)
01228     {
01229         ARAGELI_ASSERT_1(!is_null(i->degree()));
01230         res += Pm(i->coef() * i->degree(), i->degree() - 1);
01231     }
01232         
01233     return res; 
01234 }
01235 
01236 
01237 template <typename In, typename Ch, typename ChT>
01238 std::basic_ostream<Ch, ChT>& polynom_output_list
01239 (
01240     std::basic_ostream<Ch, ChT>& out,
01241     In begin, In end,
01242     const char* first_bracket,
01243     const char* second_bracket,
01244     const char* separator
01245 )
01246 {
01247     out << first_bracket;
01248 
01249     if(begin != end)
01250     {
01251         In i = begin;
01252         output_list(out, *i, first_bracket, second_bracket, separator);
01253         
01254         for(++i; i != end; ++i)
01255         {
01256             out << separator;
01257             output_list(out, *i, first_bracket, second_bracket, separator);
01258         }
01259     }
01260 
01261     out << second_bracket;
01262     return out;
01263 }
01264 
01265 
01266 template
01267 <
01268     typename F, typename I, bool REFCNT,
01269     typename Ch, typename ChT
01270 >
01271 std::basic_ostream<Ch, ChT>& output_list
01272 (
01273     std::basic_ostream<Ch, ChT>& out,
01274     const sparse_polynom<F, I, REFCNT>& x,
01275     monoms_order mo,
01276     const char* first_bracket,
01277     const char* second_bracket,
01278     const char* separator
01279 )
01280 {
01281     switch(mo)
01282     {
01283         case mo_inc:
01284             return polynom_output_list
01285             (
01286                 out, _Internal::make_reverse_iterator(x.monoms_end()),
01287                 _Internal::make_reverse_iterator(x.monoms_begin()),
01288                 first_bracket, second_bracket, separator
01289             );
01290         case mo_dec:
01291             return polynom_output_list
01292             (
01293                 out, x.monoms_begin(), x.monoms_end(),
01294                 first_bracket, second_bracket, separator
01295             );
01296     }
01297 }
01298 
01299 
01300 template <typename In, typename Ch, typename ChT>
01301 std::basic_ostream<Ch, ChT>& polynom_output_var
01302 (
01303     std::basic_ostream<Ch, ChT>& out,
01304     In begin, In end,
01305     monoms_order mo,
01306     const char* var,
01307     const char* mul,
01308     const char* pow
01309 )
01310 {
01311     if(begin == end)out << "0";
01312     else
01313     {
01314         In i = begin;
01315         output_var(out, *i, true, var, mul, pow);
01316         
01317         for(++i; i != end; ++i)
01318             output_var(out, *i, false, var, mul, pow);
01319     }
01320     
01321     return out;
01322 }
01323 
01324 
01325 template
01326 <
01327     typename F, typename I, bool REFCNT,
01328     typename Ch, typename ChT
01329 >
01330 std::basic_ostream<Ch, ChT>& output_var
01331 (
01332     std::basic_ostream<Ch, ChT>& out,
01333     const sparse_polynom<F, I, REFCNT>& x,
01334     monoms_order mo,
01335     const char* var,
01336     const char* mul,
01337     const char* pow
01338 )
01339 {
01340     ARAGELI_ASSERT_0(mo == mo_inc || mo == mo_dec);
01341 
01342     switch(mo)
01343     {
01344         case mo_inc:
01345             return polynom_output_var
01346             (
01347                 out, _Internal::make_reverse_iterator(x.monoms_end()),
01348                 _Internal::make_reverse_iterator(x.monoms_begin()),
01349                 mo, var, mul, pow
01350             );
01351         case mo_dec:
01352             return polynom_output_var
01353             (
01354                 out, x.monoms_begin(), x.monoms_end(),
01355                 mo, var, mul, pow
01356             );
01357         default:
01358             return out;
01359     }
01360 }
01361 
01362 
01363 template
01364 <
01365     typename F, typename I, bool REFCNT,
01366     typename Ch, typename ChT
01367 >
01368 std::basic_istream<Ch, ChT>& input_list
01369 (
01370     std::basic_istream<Ch, ChT>& in,
01371     sparse_polynom<F, I, REFCNT>& x,
01372     const char* fb,
01373     const char* sb,
01374     const char* sep
01375 )
01376 {
01377     ARAGELI_ASSERT_0(_Internal::is_not_contains_spaces(fb));
01378     ARAGELI_ASSERT_0(_Internal::is_not_contains_spaces(sb));
01379     ARAGELI_ASSERT_0(_Internal::is_not_contains_spaces(sep));
01380     ARAGELI_ASSERT_0(*sep);
01381 
01382     if(!_Internal::read_literal(in, fb))return in;
01383     typedef sparse_polynom<F, I, REFCNT> P;
01384     P tmp;
01385     typename P::monom m;
01386     if(!input_list(in, m))return in;
01387     tmp += m;
01388     
01389     while(_Internal::read_literal(in, sep)) // поэтому sep не должен быть ""
01390     {
01391         if(!input_list(in, m))return in;
01392         tmp += m;
01393     }
01394 
01395     if(!_Internal::read_literal(in, sb))return in;
01396     x = tmp;
01397 
01398     return in;
01399 }
01400 
01401 
01402 template
01403 <
01404     typename F, typename I, bool REFCNT,
01405     typename Ch, typename ChT, typename Coef_factory
01406 >
01407 std::basic_istream<Ch, ChT>& input_var
01408 (
01409     std::basic_istream<Ch, ChT>& in,
01410     sparse_polynom<F, I, REFCNT>& x,
01411     const Coef_factory& fctr,
01412     const char* var,
01413     const char* mul,
01414     const char* pow
01415 )
01416 {
01417     sparse_polynom<F, I, REFCNT> res;
01418 
01419     char ch = 0;
01420     in >> ch;
01421     bool brackets = false;
01422     if(ch == '(')brackets = true;
01423     else in.putback(ch);
01424 
01425     typedef typename sparse_polynom<F, I, REFCNT>::monom monom;
01426     monom m;
01427     input_var(in, m, true, fctr, var, mul, pow);
01428 
01429     if(!in)
01430     {
01431         if(in.eof())
01432         {
01433             if(brackets)in.clear(std::ios_base::badbit);
01434             else x = m;
01435         }
01436 
01437         return in;
01438     }
01439 
01440     ch = in.get();
01441 
01442     if(in.eof())
01443     {
01444         if(brackets)in.clear(std::ios_base::badbit);
01445         else x = m;
01446         return in;
01447     }
01448 
01449     in.clear();
01450     in.putback(ch);
01451     
01452     if(ch == '\n')
01453     {
01454         if(brackets)in.clear(std::ios_base::badbit);
01455         else x = m;
01456         return in;
01457     }
01458 
01459     res += m;
01460 
01461     for(;;)
01462     {
01463         m = monom();
01464         input_var(in, m, false, fctr, var, mul, pow);
01465         
01466         if(!in)
01467         {
01468             if(in.eof())res += m;
01469             break;
01470         }
01471 
01472         ch = in.get();
01473 
01474         if(in.eof())
01475         {
01476             if(brackets)
01477             {
01478                 in.clear(std::ios_base::badbit);
01479                 return in;
01480             }
01481             
01482             res += m;
01483             break;
01484         }
01485 
01486         in.clear();
01487         in.putback(ch);
01488 
01489         if(ch == '\n')
01490         {
01491             if(brackets)
01492             {
01493                 in.clear(std::ios_base::badbit);
01494                 return in;
01495             }
01496             
01497             res += m;
01498             break;
01499         }
01500 
01501         res += m;
01502     }
01503 
01504     in.clear();
01505     if(brackets && !_Internal::read_literal(in, ")"))
01506         in.clear(std::ios_base::badbit);
01507     else x = res;
01508 
01509     return in;
01510 }
01511 
01512 
01513 
01514 //template
01515 //<
01516 //  typename F1, typename I1, bool REFCNT1, typename FT1, typename IT1,
01517 //  typename F2, typename I2, bool REFCNT2, typename FT2, typename IT2
01518 //>
01519 //bool operator==
01520 //(const sparse_polynom<F1, I1, REFCNT1, FT1, IT1>& a, const sparse_polynom<F2, I2, REFCNT2, FT2, IT2>& b)
01521 //{
01522 //  ARAGELI_ASSERT_0(a.is_normal());
01523 //  ARAGELI_ASSERT_0(b.is_normal());
01524 //
01525 //  return a.size() == b.size() && std::equal
01526 //  (
01527 //      a.monoms_begin(),
01528 //      a.monoms_end(),
01529 //      b.monoms_begin()
01530 //  );
01531 //}
01532 
01533 
01534 template <typename F, typename I>
01535 std::istream& input_polynom_first
01536 (std::istream& in, monom<F, I>& x)
01537 {
01538     char fb = 0, sb = 0;
01539     monom<F, I> res;
01540     in >> fb >> res >> sb;
01541     if(fb != '(' || sb != ')')
01542     {
01543         in.clear(std::istream::badbit);
01544         return in;
01545     }
01546 
01547     x = res;
01548     return in;
01549 }
01550 
01551 
01552 template <typename F, typename I>
01553 std::istream& input_polynom_internal
01554 (std::istream& in, monom<F, I>& x)
01555 {
01556     char sign = 0, fb = 0, sb = 0;
01557     monom<F, I> res;
01558     in >> sign >> fb >> res >> sb;
01559     if(sign != '+' || sign != '-' || fb != '(' || sb != ')')
01560     {
01561         in.clear(std::istream::badbit);
01562         return in;
01563     }
01564 
01565     x = res;
01566     if(sign == '-')x.opposite();
01567     return in;
01568 }
01569 
01570 
01571 template <typename F, typename I, bool REFCNT>
01572 std::istream& input_polynom_first
01573 (std::istream& in, sparse_polynom<F, I, REFCNT>& x)
01574 {
01575     char fb = 0, sb = 0;
01576     sparse_polynom<F, I, REFCNT> res;
01577     in >> fb >> res >> sb;
01578     if(fb != '(' || sb != ')')
01579     {
01580         in.clear(std::istream::badbit);
01581         return in;
01582     }
01583 
01584     x = res;
01585     return in;
01586 }
01587 
01588 
01589 template <typename F, typename I, bool REFCNT>
01590 std::istream& input_polynom_internal
01591 (std::istream& in, sparse_polynom<F, I, REFCNT>& x)
01592 {
01593     char sign = 0, fb = 0, sb = 0;
01594     sparse_polynom<F, I, REFCNT> res;
01595     in >> sign >> fb >> res >> sb;
01596     if((sign != '+' && sign != '-') || fb != '(' || sb != ')')
01597     {
01598         in.clear(std::istream::badbit);
01599         return in;
01600     }
01601 
01602     x = res;
01603     if(sign == '-')x.opposite();
01604     return in;
01605 }
01606 
01607 
01608 } // namespace Arageli
01609 
01610 
01611 #else
01612 
01613 
01614 #include "sparse_polynom.hpp"
01615 
01616 namespace Arageli
01617 {
01618 
01619 const char* monom_input_list_first_bracket_default = "(";
01620 const char* monom_output_list_first_bracket_default = "(";
01621 const char* monom_input_list_second_bracket_default = ")";
01622 const char* monom_output_list_second_bracket_default = ")";
01623 const char* monom_input_list_separator_default = ",";
01624 const char* monom_output_list_separator_default = ", ";
01625 const char* monom_input_var_mul_default = "*";
01626 const char* monom_output_var_mul_default = "*";
01627 const char* monom_input_var_var_default = "x";
01628 const char* monom_output_var_var_default = "x";
01629 const char* monom_input_var_pow_default = "^";
01630 const char* monom_output_var_pow_default = "^";
01631 
01632 }
01633 
01634 #endif

Generated on Thu Aug 31 17:38:11 2006 for Arageli by  doxygen 1.4.7