PolyBoRi
|
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_ */