add_up.h
Go to the documentation of this file.
// -*- c++ -*-
//*****************************************************************************
//*****************************************************************************
#ifndef polybori_groebner_add_up_h_
#define polybori_groebner_add_up_h_
// include basic definitions
#include "groebner_defs.h"
#include "LexOrderGreaterComparer.h"
BEGIN_NAMESPACE_PBORIGB
inline MonomialSet
add_up_lex_sorted_monomials(const BoolePolyRing& ring,
std::vector<Monomial>& vec, int start, int end){
PBORI_ASSERT(end<=vec.size());
PBORI_ASSERT(start>=0);
int d=end-start;
PBORI_ASSERT(d>=0);
if (d<=2){
switch(d){
case 0:return MonomialSet(ring);
case 1:return vec[start].diagram();
case 2:
return (vec[start]+vec[start+1]).diagram();
}
}
//more than two monomial, lex sorted, so if first is constant, all are constant
if (vec[start].isOne()) return Polynomial(end-start, vec[start].ring()).diagram();
PBORI_ASSERT (!(vec[start].isOne()));
idx_type idx=*vec[start].begin();
int limes=end;
vec[start].popFirst();
for(limes=start+1;limes<end;limes++){
if (vec[limes].isOne()||(*vec[limes].begin()!=idx)){
PBORI_ASSERT((vec[limes].isOne())||(*vec[limes].begin()>idx));
break;
} else
vec[limes].popFirst();
//vec[limes].changeAssign(idx);
}
return MonomialSet(idx,add_up_lex_sorted_monomials(ring, vec,start,limes),add_up_lex_sorted_monomials(ring,vec,limes,end));
}
inline MonomialSet
add_up_lex_sorted_exponents(const BoolePolyRing& ring,
std::vector<Exponent>& vec, int start, int end){
PBORI_ASSERT(end<=vec.size());
PBORI_ASSERT(start>=0);
int d=end-start;
PBORI_ASSERT(d>=0);
if (d<=2){
switch(d){
case 0:return MonomialSet(ring);
case 1:return Monomial(vec[start], ring).diagram();
case 2:
Polynomial res=Monomial(vec[start], ring) +
Monomial(vec[start+1],ring);
return MonomialSet(res.diagram());
}
}
//more than two monomial, lex sorted, so if first is constant, all are constant
if (vec[start].deg()==0) return Polynomial(end-start, ring).diagram();
PBORI_ASSERT (!(vec[start].deg()==0));
idx_type idx=*vec[start].begin();
int limes=end;
vec[start].popFirst();
for(limes=start+1;limes<end;limes++){
if (PBORI_UNLIKELY((vec[limes].deg()==0)||(*vec[limes].begin()!=idx))){
PBORI_ASSERT((vec[limes].deg()==0)||(*vec[limes].begin()>idx));
break;
} else
vec[limes].popFirst();
//vec[limes].changeAssign(idx);
}
return MonomialSet(idx, add_up_lex_sorted_exponents(ring, vec,start,limes),
add_up_lex_sorted_exponents(ring, vec,limes,end));
}
#if 0
inline MonomialSet add_up_lex_sorted_monomial_navs(const BoolePolyRing& ring,
std::vector<Monomial::const_iterator>& vec, int start, int end){
PBORI_ASSERT(end<=vec.size());
PBORI_ASSERT(start>=0);
int d=end-start;
PBORI_ASSERT(d>=0);
if (d<=2){
switch(d){
case 0:return MonomialSet(const BoolePolyRing& ring,);
case 1:return MonomialSet(vec[start]);
case 2:
Polynomial res=Polynomial(vec[start])+Polynomial(vec[start+1]);
return MonomialSet(res.diagram());
}
}
//more than two monomial, lex sorted, so if first is constant, all are constant
if (vec[start].isConstant()) return Polynomial(end-start).diagram();
PBORI_ASSERT (!(vec[start].isConstant()));
idx_type idx=*vec[start];
int limes=end;
vec[start]++;
for(limes=start+1;limes<end;limes++){
if (vec[limes].isConstant()||(*vec[limes]!=idx)){
PBORI_ASSERT((vec[limes].isTerminated())||(*vec[limes]>idx));
break;
} else
vec[limes]++;
//vec[limes].changeAssign(idx);
}
return MonomialSet(idx,add_up_lex_sorted_monomial_navs(vec,start,limes),add_up_lex_sorted_monomial_navs(vec,limes,end));
}
#endif
inline Polynomial
add_up_exponents(const std::vector<Exponent>& vec,
const Polynomial& init){
//return add_up_generic(vec);
std::vector<Exponent> vec_sorted=vec;
std::sort(vec_sorted.begin(),vec_sorted.end(),LexOrderGreaterComparer());
return add_up_lex_sorted_exponents(init.ring(),
vec_sorted,0,vec_sorted.size());
}
inline Polynomial
unite_polynomials(const std::vector<Polynomial>& res_vec, int
start, int end, Polynomial init){
//we assume the polynomials to be pairwise different
int s=end-start;
if PBORI_UNLIKELY(s==0) return init;
if (s==1) return res_vec[start];
int h=s/2;
return Polynomial(unite_polynomials(res_vec,start,start+h,
init).diagram().unite(unite_polynomials(res_vec,start+h,end,
init).diagram()));
//return add_up_monomials(res_vec,start,start+h)+add_up_monomials(res_vec,start+h,end);
}
inline Polynomial
unite_polynomials(const std::vector<Polynomial>& res_vec,
Polynomial init){
//we assume the polynomials to be pairwise different
int s=res_vec.size();
if PBORI_UNLIKELY(s==0) return init;
if (s==1) return res_vec[0];
int h=s/2;
return Polynomial(unite_polynomials(res_vec,0,h, init).diagram().unite(unite_polynomials(res_vec,h,s,init).diagram()));
}
// inline Polynomial add_up_polynomials(const std::vector<Polynomial>& res_vec, int
// start, int end, Polynomial init){
// //we assume the polynomials to be pairwise different
// int s=end-start;
// if (s==0) return init;
// if (s==1) return res_vec[start];
// int h=s/2;
// return add_up_polynomials(res_vec,start,start+h,
// init)+add_up_polynomials(res_vec,start+h,end,
// init);
// //return add_up_monomials(res_vec,start,start+h)+add_up_monomials(res_vec,start+h,end);
// }
// static Polynomial add_up_polynomials(const std::vector<Polynomial>& res_vec,
// Polynomial init){
// //we assume the polynomials to be pairwise different
// int s=res_vec.size();
// if (s==0) return init;
// if (s==1) return res_vec[0];
// int h=s/2;
//
// return add_up_polynomials(res_vec,0,h, init)+add_up_polynomials(res_vec,h,s,init);
// }
template <class T>
inline Polynomial
add_up_generic(const std::vector<T>& res_vec, int
start, int end, Polynomial init){
//we assume the polynomials to be pairwise different
int s=end-start;
if (s==0) return init;
if (s==1) return Polynomial(res_vec[start]);
int h=s/2;
return add_up_generic(res_vec,start,start+h,init) +
add_up_generic(res_vec,start+h,end, init);
}
template <class T>
inline Polynomial
add_up_generic(const std::vector<T>& res_vec,
Polynomial init){
//we assume the polynomials to be pairwise different
int s=res_vec.size();
if (s==0) return init;
if (s==1) return (Polynomial) res_vec[0];
int h=s/2;
return add_up_generic(res_vec,0,h, init) +
add_up_generic(res_vec,h,s, init);
}
inline Polynomial
add_up_monomials(const std::vector<Monomial>& vec,
const Polynomial& init){
return add_up_generic(vec, init);
}
inline Polynomial
add_up_polynomials(const std::vector<Polynomial>& vec,
const Polynomial& init){
return add_up_generic(vec, init);
}
END_NAMESPACE_PBORIGB
#endif /* polybori_groebner_add_up_h_ */