PolyBoRi
add_up.h
Go to the documentation of this file.
1 // -*- c++ -*-
2 //*****************************************************************************
14 //*****************************************************************************
15 
16 #ifndef polybori_groebner_add_up_h_
17 #define polybori_groebner_add_up_h_
18 
19 // include basic definitions
20 #include "groebner_defs.h"
23 
24 inline MonomialSet
26  std::vector<Monomial>& vec, int start, int end){
27  PBORI_ASSERT(end<=vec.size());
28  PBORI_ASSERT(start>=0);
29  int d=end-start;
30  PBORI_ASSERT(d>=0);
31  if (d<=2){
32  switch(d){
33  case 0:return MonomialSet(ring);
34  case 1:return vec[start].diagram();
35  case 2:
36  return (vec[start]+vec[start+1]).diagram();
37  }
38 
39 
40  }
41 
42  //more than two monomial, lex sorted, so if first is constant, all are constant
43  if (vec[start].isOne()) return Polynomial(end-start, vec[start].ring()).diagram();
44  PBORI_ASSERT (!(vec[start].isOne()));
45  idx_type idx=*vec[start].begin();
46  int limes=end;
47  vec[start].popFirst();
48  for(limes=start+1;limes<end;limes++){
49  if (vec[limes].isOne()||(*vec[limes].begin()!=idx)){
50  PBORI_ASSERT((vec[limes].isOne())||(*vec[limes].begin()>idx));
51  break;
52  } else
53  vec[limes].popFirst();
54  //vec[limes].changeAssign(idx);
55  }
56 
57  return MonomialSet(idx,add_up_lex_sorted_monomials(ring, vec,start,limes),add_up_lex_sorted_monomials(ring,vec,limes,end));
58 }
59 
60 inline MonomialSet
62  std::vector<Exponent>& vec, int start, int end){
63  PBORI_ASSERT(end<=vec.size());
64  PBORI_ASSERT(start>=0);
65  int d=end-start;
66  PBORI_ASSERT(d>=0);
67  if (d<=2){
68  switch(d){
69  case 0:return MonomialSet(ring);
70  case 1:return Monomial(vec[start], ring).diagram();
71  case 2:
72  Polynomial res=Monomial(vec[start], ring) +
73  Monomial(vec[start+1],ring);
74  return MonomialSet(res.diagram());
75  }
76 
77 
78  }
79 
80  //more than two monomial, lex sorted, so if first is constant, all are constant
81  if (vec[start].deg()==0) return Polynomial(end-start, ring).diagram();
82  PBORI_ASSERT (!(vec[start].deg()==0));
83  idx_type idx=*vec[start].begin();
84  int limes=end;
85  vec[start].popFirst();
86  for(limes=start+1;limes<end;limes++){
87  if (PBORI_UNLIKELY((vec[limes].deg()==0)||(*vec[limes].begin()!=idx))){
88  PBORI_ASSERT((vec[limes].deg()==0)||(*vec[limes].begin()>idx));
89  break;
90  } else
91  vec[limes].popFirst();
92  //vec[limes].changeAssign(idx);
93  }
94 
95  return MonomialSet(idx, add_up_lex_sorted_exponents(ring, vec,start,limes),
96  add_up_lex_sorted_exponents(ring, vec,limes,end));
97 }
98 
101 #if 0
102 inline MonomialSet add_up_lex_sorted_monomial_navs(const BoolePolyRing& ring,
103  std::vector<Monomial::const_iterator>& vec, int start, int end){
104  PBORI_ASSERT(end<=vec.size());
105  PBORI_ASSERT(start>=0);
106  int d=end-start;
107  PBORI_ASSERT(d>=0);
108  if (d<=2){
109  switch(d){
110  case 0:return MonomialSet(const BoolePolyRing& ring,);
111  case 1:return MonomialSet(vec[start]);
112  case 2:
113  Polynomial res=Polynomial(vec[start])+Polynomial(vec[start+1]);
114  return MonomialSet(res.diagram());
115  }
116 
117 
118  }
119 
120  //more than two monomial, lex sorted, so if first is constant, all are constant
121  if (vec[start].isConstant()) return Polynomial(end-start).diagram();
122  PBORI_ASSERT (!(vec[start].isConstant()));
123  idx_type idx=*vec[start];
124  int limes=end;
125  vec[start]++;
126  for(limes=start+1;limes<end;limes++){
127  if (vec[limes].isConstant()||(*vec[limes]!=idx)){
128  PBORI_ASSERT((vec[limes].isTerminated())||(*vec[limes]>idx));
129  break;
130  } else
131  vec[limes]++;
132  //vec[limes].changeAssign(idx);
133  }
134 
135  return MonomialSet(idx,add_up_lex_sorted_monomial_navs(vec,start,limes),add_up_lex_sorted_monomial_navs(vec,limes,end));
136 }
137 #endif
138 
139 inline Polynomial
140 add_up_exponents(const std::vector<Exponent>& vec,
141  const Polynomial& init){
142  //return add_up_generic(vec);
143  std::vector<Exponent> vec_sorted=vec;
144  std::sort(vec_sorted.begin(),vec_sorted.end(),LexOrderGreaterComparer());
145 
146 
147  return add_up_lex_sorted_exponents(init.ring(),
148  vec_sorted,0,vec_sorted.size());
149 }
150 
151 
152 inline Polynomial
153 unite_polynomials(const std::vector<Polynomial>& res_vec, int
154 start, int end, Polynomial init){
155  //we assume the polynomials to be pairwise different
156  int s=end-start;
157  if PBORI_UNLIKELY(s==0) return init;
158  if (s==1) return res_vec[start];
159  int h=s/2;
160  return Polynomial(unite_polynomials(res_vec,start,start+h,
161  init).diagram().unite(unite_polynomials(res_vec,start+h,end,
162  init).diagram()));
163  //return add_up_monomials(res_vec,start,start+h)+add_up_monomials(res_vec,start+h,end);
164 }
165 
166 inline Polynomial
167 unite_polynomials(const std::vector<Polynomial>& res_vec,
168  Polynomial init){
169  //we assume the polynomials to be pairwise different
170  int s=res_vec.size();
171  if PBORI_UNLIKELY(s==0) return init;
172  if (s==1) return res_vec[0];
173  int h=s/2;
174 
175  return Polynomial(unite_polynomials(res_vec,0,h, init).diagram().unite(unite_polynomials(res_vec,h,s,init).diagram()));
176 }
177 
178 // inline Polynomial add_up_polynomials(const std::vector<Polynomial>& res_vec, int
179 // start, int end, Polynomial init){
180 // //we assume the polynomials to be pairwise different
181 // int s=end-start;
182 // if (s==0) return init;
183 // if (s==1) return res_vec[start];
184 // int h=s/2;
185 // return add_up_polynomials(res_vec,start,start+h,
186 // init)+add_up_polynomials(res_vec,start+h,end,
187 // init);
188 // //return add_up_monomials(res_vec,start,start+h)+add_up_monomials(res_vec,start+h,end);
189 // }
190 // static Polynomial add_up_polynomials(const std::vector<Polynomial>& res_vec,
191 // Polynomial init){
192 // //we assume the polynomials to be pairwise different
193 // int s=res_vec.size();
194 // if (s==0) return init;
195 // if (s==1) return res_vec[0];
196 // int h=s/2;
197 //
198 // return add_up_polynomials(res_vec,0,h, init)+add_up_polynomials(res_vec,h,s,init);
199 // }
200 
201 
202 
203 template <class T>
204 inline Polynomial
205 add_up_generic(const std::vector<T>& res_vec, int
206 start, int end, Polynomial init){
207  //we assume the polynomials to be pairwise different
208  int s=end-start;
209  if (s==0) return init;
210  if (s==1) return Polynomial(res_vec[start]);
211  int h=s/2;
212  return add_up_generic(res_vec,start,start+h,init) +
213  add_up_generic(res_vec,start+h,end, init);
214 }
215 
216 template <class T>
217 inline Polynomial
218 add_up_generic(const std::vector<T>& res_vec,
219  Polynomial init){
220  //we assume the polynomials to be pairwise different
221  int s=res_vec.size();
222  if (s==0) return init;
223  if (s==1) return (Polynomial) res_vec[0];
224  int h=s/2;
225 
226  return add_up_generic(res_vec,0,h, init) +
227  add_up_generic(res_vec,h,s, init);
228 }
229 
230 inline Polynomial
231 add_up_monomials(const std::vector<Monomial>& vec,
232  const Polynomial& init){
233  return add_up_generic(vec, init);
234 
235 }
236 
237 inline Polynomial
238 add_up_polynomials(const std::vector<Polynomial>& vec,
239  const Polynomial& init){
240  return add_up_generic(vec, init);
241 
242 }
243 
244 
246 
247 #endif /* polybori_groebner_add_up_h_ */