00001 #include "mterm.hh"
00002 #include "signals.hh"
00003 #include "ppsig.hh"
00004 #include <assert.h>
00005
00006
00007 #undef TRACE
00008
00009 using namespace std;
00010
00011 typedef map<Tree,int> MP;
00012
00013 mterm::mterm () : fCoef(sigInt(0)) {}
00014 mterm::mterm (int k) : fCoef(sigInt(k)) {}
00015 mterm::mterm (double k) : fCoef(sigReal(k)) {}
00016 mterm::mterm (const mterm& m) : fCoef(m.fCoef), fFactors(m.fFactors) {}
00017
00021 mterm::mterm (Tree t) : fCoef(sigInt(1))
00022 {
00023
00024 *this *= t;
00025
00026 }
00027
00031 bool mterm::isNotZero() const
00032 {
00033 return !isZero(fCoef);
00034 }
00035
00039 bool mterm::isNegative() const
00040 {
00041 return !isGEZero(fCoef);
00042 }
00043
00047 ostream& mterm::print(ostream& dst) const
00048 {
00049 const char* sep = "";
00050 if (!isOne(fCoef) || fFactors.empty()) { dst << ppsig(fCoef); sep = " * "; }
00051
00052 for (MP::const_iterator p = fFactors.begin(); p != fFactors.end(); p++) {
00053 dst << sep << ppsig(p->first);
00054 if (p->second != 1) dst << "**" << p->second;
00055 sep = " * ";
00056 }
00057 return dst;
00058 }
00059
00064 int mterm::complexity() const
00065 {
00066 int c = isOne(fCoef) ? 0 : 1;
00067 for (MP::const_iterator p = fFactors.begin(); p != fFactors.end(); ++p) {
00068 c += (1+getSigOrder(p->first))*abs(p->second);
00069 }
00070 return c;
00071 }
00072
00073
00078 const mterm& mterm::operator *= (Tree t)
00079 {
00080 int op;
00081 Tree x,y;
00082
00083 assert(t!=0);
00084
00085 if (isNum(t)) {
00086 fCoef = mulNums(fCoef,t);
00087
00088 } else if (isSigBinOp(t, &op, x, y) && (op == kMul)) {
00089 *this *= x;
00090 *this *= y;
00091
00092 } else if (isSigBinOp(t, &op, x, y) && (op == kDiv)) {
00093 *this *= x;
00094 *this /= y;
00095
00096 } else {
00097 Tree tnorm = t;
00098 fFactors[tnorm] += 1;
00099 }
00100 return *this;
00101 }
00102
00107 const mterm& mterm::operator /= (Tree t)
00108 {
00109
00110 int op;
00111 Tree x,y;
00112
00113 assert(t!=0);
00114
00115 if (isNum(t)) {
00116 fCoef = divExtendedNums(fCoef,t);
00117
00118 } else if (isSigBinOp(t, &op, x, y) && (op == kMul)) {
00119 *this /= x;
00120 *this /= y;
00121
00122 } else if (isSigBinOp(t, &op, x, y) && (op == kDiv)) {
00123 *this /= x;
00124 *this *= y;
00125
00126 } else {
00127 fFactors[t] -= 1;
00128 }
00129 return *this;
00130 }
00131
00135 const mterm& mterm::operator = (const mterm& m)
00136 {
00137 fCoef = m.fCoef;
00138 fFactors = m.fFactors;
00139 return *this;
00140 }
00141
00145 void mterm::cleanup()
00146 {
00147 if (isZero(fCoef)) {
00148 fFactors.clear();
00149 } else {
00150 for (MP::iterator p = fFactors.begin(); p != fFactors.end(); ) {
00151 if (p->second == 0) {
00152 fFactors.erase(p++);
00153 } else {
00154 p++;
00155 }
00156 }
00157 }
00158 }
00159
00164 const mterm& mterm::operator += (const mterm& m)
00165 {
00166 if (isZero(m.fCoef)) {
00167
00168 } else if (isZero(fCoef)) {
00169
00170 fCoef = m.fCoef;
00171 fFactors = m.fFactors;
00172 } else {
00173
00174 assert(signatureTree() == m.signatureTree());
00175 fCoef = addNums(fCoef, m.fCoef);
00176 }
00177 cleanup();
00178 return *this;
00179 }
00180
00185 const mterm& mterm::operator -= (const mterm& m)
00186 {
00187 if (isZero(m.fCoef)) {
00188
00189 } else if (isZero(fCoef)) {
00190
00191 fCoef = minusNum(m.fCoef);
00192 fFactors = m.fFactors;
00193 } else {
00194
00195 assert(signatureTree() == m.signatureTree());
00196 fCoef = subNums(fCoef, m.fCoef);
00197 }
00198 cleanup();
00199 return *this;
00200 }
00201
00205 const mterm& mterm::operator *= (const mterm& m)
00206 {
00207 fCoef = mulNums(fCoef,m.fCoef);
00208 for (MP::const_iterator p = m.fFactors.begin(); p != m.fFactors.end(); p++) {
00209 fFactors[p->first] += p->second;
00210 }
00211 cleanup();
00212 return *this;
00213 }
00214
00218 const mterm& mterm::operator /= (const mterm& m)
00219 {
00220
00221 fCoef = divExtendedNums(fCoef,m.fCoef);
00222 for (MP::const_iterator p = m.fFactors.begin(); p != m.fFactors.end(); p++) {
00223 fFactors[p->first] -= p->second;
00224 }
00225 cleanup();
00226 return *this;
00227 }
00228
00232 mterm mterm::operator * (const mterm& m) const
00233 {
00234 mterm r(*this);
00235 r *= m;
00236 return r;
00237 }
00238
00242 mterm mterm::operator / (const mterm& m) const
00243 {
00244 mterm r(*this);
00245 r /= m;
00246 return r;
00247 }
00248
00252 static int common(int a, int b)
00253 {
00254 if (a > 0 & b > 0) {
00255 return min(a,b);
00256 } else if (a < 0 & b < 0) {
00257 return max(a,b);
00258 } else {
00259 return 0;
00260 }
00261 }
00262
00263
00267 mterm gcd (const mterm& m1, const mterm& m2)
00268 {
00269
00270
00271 Tree c = (m1.fCoef == m2.fCoef) ? m1.fCoef : tree(1);
00272 mterm R(c);
00273 for (MP::const_iterator p1 = m1.fFactors.begin(); p1 != m1.fFactors.end(); p1++) {
00274 Tree t = p1->first;
00275 MP::const_iterator p2 = m2.fFactors.find(t);
00276 if (p2 != m2.fFactors.end()) {
00277 int v1 = p1->second;
00278 int v2 = p2->second;
00279 int c = common(v1,v2);
00280 if (c != 0) {
00281 R.fFactors[t] = c;
00282 }
00283 }
00284 }
00285
00286 return R;
00287 }
00288
00293 static bool contains(int a, int b)
00294 {
00295 return (b == 0) || (a/b > 0);
00296 }
00297
00305 bool mterm::hasDivisor (const mterm& n) const
00306 {
00307 for (MP::const_iterator p1 = n.fFactors.begin(); p1 != n.fFactors.end(); p1++) {
00308
00309 Tree f = p1->first;
00310 int v = p1->second;
00311
00312
00313 MP::const_iterator p2 = fFactors.find(f);
00314 if (p2 == fFactors.end()) return false;
00315
00316
00317 int u = p2->second;
00318 if (! contains(u,v) ) return false;
00319 }
00320 return true;
00321 }
00322
00330 static Tree buildPowTerm(Tree f, int q)
00331 {
00332 assert(f);
00333 assert(q>0);
00334 Tree r = f;
00335 for (int c=2; c<=q; c++) { r = sigMul(r,f); }
00336 assert(r);
00337 return r;
00338 }
00339
00343 static void combineMulLeft(Tree& R, Tree A)
00344 {
00345 if (R && A) R = sigMul(R,A);
00346 else if (A) R = A;
00347 }
00348
00352 static void combineDivLeft(Tree& R, Tree A)
00353 {
00354 if (R && A) R = sigDiv(R,A);
00355 else if (A) R = sigDiv(tree(1.0f),A);
00356 }
00357
00361 static void combineMulDiv(Tree& M, Tree& D, Tree f, int q)
00362 {
00363 #ifdef TRACE
00364 cerr << "combineMulDiv (" << M << "/" << D << "*" << ppsig(f)<< "**" << q << endl;
00365 #endif
00366 if (f) {
00367 if (q > 0) {
00368 combineMulLeft(M, buildPowTerm(f,q));
00369 } else if (q < 0) {
00370 combineMulLeft(D, buildPowTerm(f,-q));
00371 }
00372 }
00373 }
00374
00375
00380 Tree mterm::signatureTree() const
00381 {
00382 return normalizedTree(true);
00383 }
00384
00391 Tree mterm::normalizedTree(bool signatureMode, bool negativeMode) const
00392 {
00393 if (fFactors.empty() || isZero(fCoef)) {
00394
00395 if (signatureMode) return tree(1);
00396 if (negativeMode) return minusNum(fCoef);
00397 else return fCoef;
00398 } else {
00399
00400 Tree A[4], B[4];
00401
00402
00403 for (int order = 0; order < 4; order++) {
00404 A[order] = 0; B[order] = 0;
00405 for (MP::const_iterator p = fFactors.begin(); p != fFactors.end(); p++) {
00406 Tree f = p->first;
00407 int q = p->second;
00408 if (f && q && getSigOrder(f)==order) {
00409
00410 combineMulDiv (A[order], B[order], f, q);
00411 }
00412 }
00413 }
00414 if (A[0] != 0) cerr << "A[0] == " << *A[0] << endl;
00415 if (B[0] != 0) cerr << "B[0] == " << *B[0] << endl;
00416
00417 assert(A[0] == 0);
00418 assert(B[0] == 0);
00419
00420
00421 if (! (signatureMode | isOne(fCoef))) {
00422 A[0] = (negativeMode) ? minusNum(fCoef) : fCoef;
00423 }
00424
00425 if (signatureMode) {
00426 A[0] = 0;
00427 } else if (negativeMode) {
00428 if (isMinusOne(fCoef)) { A[0] = 0; } else { A[0] = minusNum(fCoef); }
00429 } else if (isOne(fCoef)) {
00430 A[0] = 0;
00431 } else {
00432 A[0] = fCoef;
00433 }
00434
00435
00436 Tree RR = 0;
00437 for (int order = 0; order < 4; order++) {
00438 if (A[order] && B[order]) combineMulLeft(RR,sigDiv(A[order],B[order]));
00439 else if (A[order]) combineMulLeft(RR,A[order]);
00440 else if (B[order]) combineDivLeft(RR,B[order]);
00441 }
00442 if (RR == 0) RR = tree(1);
00443
00444 assert(RR);
00445
00446 return RR;
00447 }
00448 }
00449