GiNaCRA  0.6.4
MultivariateMonomialMR.cpp
Go to the documentation of this file.
00001 /*
00002  * GiNaCRA - GiNaC Real Algebra package
00003  * Copyright (C) 2010-2012  Ulrich Loup, Joachim Redies, Sebastian Junges
00004  *
00005  * This file is part of GiNaCRA.
00006  *
00007  * GiNaCRA is free software: you can redistribute it and/or modify
00008  * it under the terms of the GNU General Public License as published by
00009  * the Free Software Foundation, either version 3 of the License, or
00010  * (at your option) any later version.
00011  *
00012  * GiNaCRA is distributed in the hope that it will be useful,
00013  * but WITHOUT ANY WARRANTY; without even the implied warranty of
00014  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
00015  * GNU General Public License for more details.
00016  *
00017  * You should have received a copy of the GNU General Public License
00018  * along with GiNaCRA.  If not, see <http://www.gnu.org/licenses/>.
00019  *
00020  */
00021 
00022 
00023 // #define GINACRA_OPENINTERVAL_DEBUG
00024 
00036 #include "MultivariateMonomialMR.h"
00037 #include "utilities.h"
00038 #include "VariableListPool.h"
00039 
00040 using std::vector;
00041 using std::ostream;
00042 
00043 namespace GiNaCRA
00044 {
00045     bool sort_first( const std::pair<unsigned, unsigned>& p1, const std::pair<unsigned, unsigned>& p2 )
00046     {
00047         return p1.first < p2.first;
00048     }
00049 
00050     bool compare_first( const std::pair<unsigned, unsigned>& p1, const std::pair<unsigned, unsigned>& p2 )
00051     {
00052         return p1.first == p2.first;
00053     }
00054 
00055     MultivariateMonomialMR::MultivariateMonomialMR():
00056         mExponents(),
00057         mTotDeg( 0 )
00058     {}
00059 
00060     MultivariateMonomialMR::MultivariateMonomialMR( unsigned nrVars ):
00061         mExponents(),
00062         mTotDeg( 0 )
00063     {
00064         mExponents.reserve( nrVars );
00065     }
00066 
00067     MultivariateMonomialMR::MultivariateMonomialMR( unsigned varIndex, int exponent ):
00068         mExponents( 1, pui( varIndex, exponent ))
00069     {
00070         mTotDeg = exponent;
00071     }
00072 
00073     MultivariateMonomialMR::MultivariateMonomialMR( vui_cIt vecBegin, vui_cIt vecEnd )
00074     {
00075         mExponents = std::vector<pui>( vecBegin, vecEnd );
00076         std::sort( mExponents.begin(), mExponents.end(), sort_first );
00077         std::unique( mExponents.begin(), mExponents.end(), compare_first );
00078         mTotDeg = std::accumulate( vecBegin, vecEnd, 0, plus_second() );
00079     }
00080 
00081     GiNaC::ex MultivariateMonomialMR::toEx() const
00082     {
00083         GiNaC::ex expr = GiNaC::ex( 1 );
00084         for( vui_cIt it = mExponents.begin(); it != mExponents.end(); ++it )
00085         {
00086             expr *= GiNaC::pow( VariableListPool::getVariableSymbol( it->first ), it->second );
00087         }
00088         return expr;
00089     }
00090 
00091     const MultivariateMonomialMR MultivariateMonomialMR::lcm( const MultivariateMonomialMR& m1, const MultivariateMonomialMR& m2 )
00092     {
00093         if( m1.mExponents.empty() )
00094             return m2;
00095         if( m2.mExponents.empty() )
00096             return m1;
00097 
00098         vui_cIt m1it  = m1.mExponents.begin();
00099         vui_cIt m2it  = m2.mExponents.begin();
00100 
00101         vui_cIt m1end = m1.mExponents.end();
00102         vui_cIt m2end = m2.mExponents.end();
00103         unsigned tdeg = 0;
00104         MultivariateMonomialMR newMon( m1.mExponents.size() + m2.mExponents.size() );
00105 
00106         while( true )
00107         {
00108             while( m1it->first == m2it->first )
00109             {
00110                 unsigned deg = std::max( m1it->second, m2it->second );
00111                 newMon.mExponents.push_back( pui( m1it->first, deg ));
00112                 tdeg += deg;
00113                 ++m1it;
00114                 ++m2it;
00115                 if( m1it == m1end )
00116                 {
00117                     newMon.mExponents.insert( newMon.mExponents.end(), m2it, m2end );
00118                     newMon.mTotDeg = std::accumulate( m2it, m2end, tdeg, plus_second() );
00119                     return newMon;
00120                 }
00121                 if( m2it == m2end )
00122                 {
00123                     newMon.mExponents.insert( newMon.mExponents.end(), m1it, m1end );
00124                     newMon.mTotDeg = std::accumulate( m1it, m1end, tdeg, plus_second() );
00125                     return newMon;
00126                 }
00127             }
00128             while( m1it->first < m2it->first )
00129             {
00130                 newMon.mExponents.push_back( *m1it );
00131                 tdeg += m1it->second;
00132                 ++m1it;
00133                 if( m1it == m1end )
00134                 {
00135                     newMon.mExponents.insert( newMon.mExponents.end(), m2it, m2end );
00136                     newMon.mTotDeg = std::accumulate( m2it, m2end, tdeg, plus_second() );
00137                     return newMon;
00138                 }
00139             }
00140             while( m1it->first > m2it->first )
00141             {
00142                 newMon.mExponents.push_back( *m2it );
00143                 tdeg += m2it->second;
00144                 ++m2it;
00145                 if( m2it == m2end )
00146                 {
00147                     newMon.mExponents.insert( newMon.mExponents.end(), m1it, m1end );
00148                     newMon.mTotDeg = std::accumulate( m1it, m1end, tdeg, plus_second() );
00149                     return newMon;
00150                 }
00151             }
00152         }
00153     }
00154 
00155     bool operator ==( const MultivariateMonomialMR& lhs, const MultivariateMonomialMR& rhs )
00156     {
00157         if( lhs.mTotDeg != rhs.mTotDeg )
00158             return false;
00159         return (lhs.mExponents == rhs.mExponents);
00160     }
00161 
00162     bool operator !=( const MultivariateMonomialMR& lhs, const MultivariateMonomialMR& rhs )
00163     {
00164         return !(lhs == rhs);
00165     }
00166 
00167     std::ostream& operator <<( ostream& os, const MultivariateMonomialMR& rhs )
00168     {
00169         os << "[";
00170         for( vui_cIt it = rhs.mExponents.begin(); it != rhs.mExponents.end(); ++it )
00171         {
00172             os << "x_" << it->first << "^" << it->second;
00173         }
00174         return (os << "]");
00175     }
00176 
00177     bool MultivariateMonomialMR::LexCompare( const MultivariateMonomialMR& m1, const MultivariateMonomialMR& m2 )
00178     {
00179         if( m1.tdeg() == 0 && m2.tdeg() != 0 )
00180             return true;
00181         if( m2.tdeg() == 0 )
00182             return false;
00183         vui_cIt m1it = m1.mExponents.begin();
00184         vui_cIt m2it = m2.mExponents.begin();
00185 
00186         while( m1it != m1.mExponents.end() )
00187         {
00188             if( m2it == m2.mExponents.end() )
00189                 return false;
00190             //which variable occurs first
00191             if( m1it->first == m2it->first )
00192             {
00193                 //equal variables
00194                 if( m1it->second < m2it->second )
00195                     return true;
00196                 if( m1it->second > m2it->second )
00197                     return false;
00198             }
00199             else
00200             {
00201                 return (m1it->first > m2it->first);
00202             }
00203             ++m1it;
00204             ++m2it;
00205         }
00206         if( m2it == m2.mExponents.end() )
00207             return false;
00208         return true;
00209     }
00210 
00211     bool MultivariateMonomialMR::GrLexCompare( const MultivariateMonomialMR& m1, const MultivariateMonomialMR& m2 )
00212     {
00213         unsigned m1deg = m1.tdeg();
00214         unsigned m2deg = m2.tdeg();
00215         if( m1deg > m2deg )
00216             return false;
00217         if( m2deg > m1deg )
00218             return true;
00219         return LexCompare( m1, m2 );
00220     }
00221 
00222     bool MultivariateMonomialMR::GrRevLexCompare( const MultivariateMonomialMR& m1, const MultivariateMonomialMR& m2 )
00223     {
00224         unsigned m1deg = m1.tdeg();
00225         unsigned m2deg = m2.tdeg();
00226         if( m1deg > m2deg )
00227             return false;
00228         if( m2deg > m1deg )
00229             return true;
00230         return LexCompare( m2, m1 );
00231     }
00232 
00233     const MultivariateMonomialMR operator *( const MultivariateMonomialMR& m1, const MultivariateMonomialMR& m2 )
00234     {
00235         if( m1.mExponents.empty() )
00236             return m2;
00237         if( m2.mExponents.empty() )
00238             return m1;
00239 
00240         vui_cIt m1it  = m1.mExponents.begin();
00241         vui_cIt m2it  = m2.mExponents.begin();
00242 
00243         vui_cIt m1end = m1.mExponents.end();
00244         vui_cIt m2end = m2.mExponents.end();
00245 
00246         MultivariateMonomialMR newMon( m1.mExponents.size() + m2.mExponents.size() );
00247         newMon.mTotDeg = m1.mTotDeg + m2.mTotDeg;
00248 
00249         while( true )
00250         {
00251             while( m1it->first == m2it->first )
00252             {
00253                 newMon.mExponents.push_back( pui( m1it->first, (m1it->second + m2it->second) ) );
00254                 ++m1it;
00255                 ++m2it;
00256                 if( m1it == m1end )
00257                 {
00258                     newMon.mExponents.insert( newMon.mExponents.end(), m2it, m2end );
00259                     return newMon;
00260                 }
00261                 if( m2it == m2end )
00262                 {
00263                     newMon.mExponents.insert( newMon.mExponents.end(), m1it, m1end );
00264                     return newMon;
00265                 }
00266             }
00267             while( m1it->first < m2it->first )
00268             {
00269                 newMon.mExponents.push_back( *m1it );
00270                 ++m1it;
00271                 if( m1it == m1end )
00272                 {
00273                     newMon.mExponents.insert( newMon.mExponents.end(), m2it, m2end );
00274                     return newMon;
00275                 }
00276             }
00277             while( m1it->first > m2it->first )
00278             {
00279                 newMon.mExponents.push_back( *m2it );
00280                 ++m2it;
00281                 if( m2it == m2end )
00282                 {
00283                     newMon.mExponents.insert( newMon.mExponents.end(), m1it, m1end );
00284                     return newMon;
00285                 }
00286             }
00287         }
00288     }
00289 
00294 }