PolyBoRi
add_up.h
Go to the documentation of this file.
00001 // -*- c++ -*-
00002 //*****************************************************************************
00014 //*****************************************************************************
00015 
00016 #ifndef polybori_groebner_add_up_h_
00017 #define polybori_groebner_add_up_h_
00018 
00019 // include basic definitions
00020 #include "groebner_defs.h"
00021 #include "LexOrderGreaterComparer.h"
00022 BEGIN_NAMESPACE_PBORIGB
00023 
00024 inline MonomialSet
00025 add_up_lex_sorted_monomials(const BoolePolyRing& ring,
00026                                                std::vector<Monomial>& vec, int start, int end){
00027     PBORI_ASSERT(end<=vec.size());
00028     PBORI_ASSERT(start>=0);
00029     int d=end-start;
00030     PBORI_ASSERT(d>=0);
00031     if (d<=2){
00032         switch(d){
00033             case 0:return MonomialSet(ring);
00034             case 1:return vec[start].diagram();
00035             case 2: 
00036               return (vec[start]+vec[start+1]).diagram();
00037         }
00038 
00039     
00040     }
00041     
00042     //more than two monomial, lex sorted, so if first is  constant, all are constant
00043     if (vec[start].isOne()) return Polynomial(end-start, vec[start].ring()).diagram();
00044     PBORI_ASSERT (!(vec[start].isOne()));
00045     idx_type idx=*vec[start].begin();
00046     int limes=end;
00047     vec[start].popFirst();
00048     for(limes=start+1;limes<end;limes++){
00049         if (vec[limes].isOne()||(*vec[limes].begin()!=idx)){
00050             PBORI_ASSERT((vec[limes].isOne())||(*vec[limes].begin()>idx));
00051             break;
00052         } else 
00053            vec[limes].popFirst();
00054             //vec[limes].changeAssign(idx);
00055     }
00056     
00057     return MonomialSet(idx,add_up_lex_sorted_monomials(ring, vec,start,limes),add_up_lex_sorted_monomials(ring,vec,limes,end));
00058 }
00059 
00060 inline MonomialSet
00061 add_up_lex_sorted_exponents(const BoolePolyRing& ring,
00062                             std::vector<Exponent>& vec, int start, int end){
00063     PBORI_ASSERT(end<=vec.size());
00064     PBORI_ASSERT(start>=0);
00065     int d=end-start;
00066     PBORI_ASSERT(d>=0);
00067     if (d<=2){
00068         switch(d){
00069             case 0:return MonomialSet(ring);
00070         case 1:return Monomial(vec[start], ring).diagram();
00071             case 2: 
00072               Polynomial res=Monomial(vec[start], ring) + 
00073                 Monomial(vec[start+1],ring);
00074               return MonomialSet(res.diagram());
00075         }
00076 
00077     
00078     }
00079     
00080     //more than two monomial, lex sorted, so if first is  constant, all are constant
00081     if (vec[start].deg()==0) return Polynomial(end-start, ring).diagram();
00082     PBORI_ASSERT (!(vec[start].deg()==0));
00083     idx_type idx=*vec[start].begin();
00084     int limes=end;
00085     vec[start].popFirst();
00086     for(limes=start+1;limes<end;limes++){
00087         if (PBORI_UNLIKELY((vec[limes].deg()==0)||(*vec[limes].begin()!=idx))){
00088             PBORI_ASSERT((vec[limes].deg()==0)||(*vec[limes].begin()>idx));
00089             break;
00090         } else 
00091            vec[limes].popFirst();
00092             //vec[limes].changeAssign(idx);
00093     }
00094     
00095     return MonomialSet(idx, add_up_lex_sorted_exponents(ring, vec,start,limes),
00096                        add_up_lex_sorted_exponents(ring, vec,limes,end));
00097 }
00098 
00101 #if 0
00102 inline MonomialSet add_up_lex_sorted_monomial_navs(const BoolePolyRing& ring,
00103   std::vector<Monomial::const_iterator>& vec, int start, int end){
00104     PBORI_ASSERT(end<=vec.size());
00105     PBORI_ASSERT(start>=0);
00106     int d=end-start;
00107     PBORI_ASSERT(d>=0);
00108     if (d<=2){
00109         switch(d){
00110             case 0:return MonomialSet(const BoolePolyRing& ring,);
00111             case 1:return MonomialSet(vec[start]);
00112             case 2: 
00113               Polynomial res=Polynomial(vec[start])+Polynomial(vec[start+1]);
00114               return MonomialSet(res.diagram());
00115         }
00116 
00117     
00118     }
00119     
00120     //more than two monomial, lex sorted, so if first is  constant, all are constant
00121     if (vec[start].isConstant()) return Polynomial(end-start).diagram();
00122     PBORI_ASSERT (!(vec[start].isConstant()));
00123     idx_type idx=*vec[start];
00124     int limes=end;
00125     vec[start]++;
00126     for(limes=start+1;limes<end;limes++){
00127         if (vec[limes].isConstant()||(*vec[limes]!=idx)){
00128             PBORI_ASSERT((vec[limes].isTerminated())||(*vec[limes]>idx));
00129             break;
00130         } else 
00131            vec[limes]++;
00132             //vec[limes].changeAssign(idx);
00133     }
00134     
00135     return MonomialSet(idx,add_up_lex_sorted_monomial_navs(vec,start,limes),add_up_lex_sorted_monomial_navs(vec,limes,end));
00136 }
00137 #endif
00138 
00139 inline Polynomial
00140 add_up_exponents(const std::vector<Exponent>& vec,
00141                             const Polynomial& init){
00142     //return add_up_generic(vec);
00143     std::vector<Exponent> vec_sorted=vec;
00144     std::sort(vec_sorted.begin(),vec_sorted.end(),LexOrderGreaterComparer());
00145     
00146    
00147     return add_up_lex_sorted_exponents(init.ring(),
00148                                        vec_sorted,0,vec_sorted.size());
00149 }
00150 
00151 
00152 inline Polynomial
00153 unite_polynomials(const std::vector<Polynomial>& res_vec, int
00154 start, int end, Polynomial init){
00155     //we assume the polynomials to be pairwise different
00156     int s=end-start;
00157     if PBORI_UNLIKELY(s==0) return init;
00158     if (s==1) return res_vec[start];
00159     int h=s/2;
00160     return Polynomial(unite_polynomials(res_vec,start,start+h,
00161              init).diagram().unite(unite_polynomials(res_vec,start+h,end, 
00162                                                      init).diagram()));
00163     //return add_up_monomials(res_vec,start,start+h)+add_up_monomials(res_vec,start+h,end);
00164 }
00165 
00166 inline Polynomial
00167 unite_polynomials(const std::vector<Polynomial>& res_vec,
00168                                     Polynomial init){
00169     //we assume the polynomials to be pairwise different
00170     int s=res_vec.size();
00171     if PBORI_UNLIKELY(s==0) return init;
00172     if (s==1) return res_vec[0];
00173     int h=s/2;
00174     
00175     return Polynomial(unite_polynomials(res_vec,0,h, init).diagram().unite(unite_polynomials(res_vec,h,s,init).diagram()));
00176 }
00177 
00178 // inline Polynomial add_up_polynomials(const std::vector<Polynomial>& res_vec, int
00179 // start, int end, Polynomial init){
00180 //     //we assume the polynomials to be pairwise different
00181 //     int s=end-start;
00182 //     if (s==0) return init;
00183 //     if (s==1) return res_vec[start];
00184 //     int h=s/2;
00185 //     return add_up_polynomials(res_vec,start,start+h,
00186 //              init)+add_up_polynomials(res_vec,start+h,end, 
00187 //                                                      init);
00188 //     //return add_up_monomials(res_vec,start,start+h)+add_up_monomials(res_vec,start+h,end);
00189 // }
00190 // static Polynomial add_up_polynomials(const std::vector<Polynomial>& res_vec,
00191 //                                     Polynomial init){
00192 //     //we assume the polynomials to be pairwise different
00193 //     int s=res_vec.size();
00194 //     if (s==0) return init;
00195 //     if (s==1) return res_vec[0];
00196 //     int h=s/2;
00197 //     
00198 //     return add_up_polynomials(res_vec,0,h, init)+add_up_polynomials(res_vec,h,s,init);
00199 // }
00200 
00201 
00202 
00203 template <class T>
00204 inline Polynomial
00205 add_up_generic(const std::vector<T>& res_vec, int
00206 start, int end, Polynomial init){
00207     //we assume the polynomials to be pairwise different
00208     int s=end-start;
00209     if (s==0) return init;
00210     if (s==1) return Polynomial(res_vec[start]);
00211     int h=s/2;
00212     return add_up_generic(res_vec,start,start+h,init) +
00213       add_up_generic(res_vec,start+h,end, init);
00214 }
00215 
00216 template <class T>
00217 inline Polynomial
00218 add_up_generic(const std::vector<T>& res_vec,
00219                                              Polynomial init){
00220     //we assume the polynomials to be pairwise different
00221     int s=res_vec.size();
00222     if (s==0) return init;
00223     if (s==1) return (Polynomial) res_vec[0];
00224     int h=s/2;
00225     
00226     return add_up_generic(res_vec,0,h, init) + 
00227       add_up_generic(res_vec,h,s, init);
00228 }
00229 
00230 inline Polynomial
00231 add_up_monomials(const std::vector<Monomial>& vec,
00232                             const Polynomial& init){
00233   return add_up_generic(vec, init);
00234 
00235 }
00236 
00237 inline Polynomial
00238 add_up_polynomials(const std::vector<Polynomial>& vec,
00239                               const Polynomial& init){
00240   return add_up_generic(vec, init);
00241 
00242 }
00243 
00244 
00245 END_NAMESPACE_PBORIGB
00246 
00247 #endif /* polybori_groebner_add_up_h_ */