PolyBoRi
|
00001 /* 00002 * pairs.h 00003 * PolyBoRi 00004 * 00005 * Created by Michael Brickenstein on 19.04.06. 00006 * Copyright 2006 The PolyBoRi Team. See LICENSE file. 00007 * 00008 */ 00009 #include <functional> 00010 #include "groebner_defs.h" 00011 #include "literal_factorization.h" 00012 #include <boost/shared_ptr.hpp> 00013 #include <queue> 00014 #include <algorithm> 00015 #include <utility> 00016 #include <set> 00017 00018 #ifndef PB_PAIR_H 00019 #define PB_PAIR_H 00020 00021 BEGIN_NAMESPACE_PBORIGB 00022 00023 class PolyEntry{ 00024 public: 00025 PolyEntry(const Polynomial &p); 00026 PolyEntry(){ 00027 00028 } 00029 bool operator==(const PolyEntry& other) const{ 00030 return p==other.p; 00031 } 00032 LiteralFactorization literal_factors; 00033 Polynomial p; 00034 Monomial lead; 00035 wlen_type weightedLength; 00036 len_type length; 00037 deg_type deg; 00038 deg_type leadDeg; 00039 Exponent leadExp; 00040 Monomial gcdOfTerms; 00041 Exponent usedVariables; 00042 Exponent tailVariables; 00043 Polynomial tail; 00045 std::set<idx_type> vPairCalculated; 00046 deg_type ecart() const{ 00047 return deg-leadDeg; 00048 } 00049 bool minimal; 00050 void recomputeInformation(); 00051 }; 00052 //using std::less; 00053 typedef std::vector<PolyEntry> PolyEntryVector; 00054 00055 class PairData{ 00056 public: 00057 //gives back encoded 00058 virtual ~PairData()=0; 00059 //we don't demand that the pair is in a consistent state later 00060 virtual Polynomial extract(const PolyEntryVector& v)=0; 00061 }; 00062 class IJPairData: public PairData{ 00063 public: 00064 int i; 00065 int j; 00066 Polynomial extract(const PolyEntryVector& v){ 00067 return spoly(v[i].p,v[j].p); 00068 } 00069 IJPairData(int i, int j){ 00070 this->i=i; 00071 this->j=j; 00072 } 00073 }; 00074 class PolyPairData: public PairData{ 00075 public: 00076 Polynomial p; 00077 Polynomial extract(const PolyEntryVector& v){ 00078 return p; 00079 } 00080 PolyPairData(const BoolePolynomial& p){ 00081 this->p=p; 00082 } 00083 }; 00084 00085 class VariablePairData: public PairData{ 00086 public: 00087 int i; 00088 idx_type v; 00089 Polynomial extract(const PolyEntryVector& gen){ 00090 return Monomial(Variable(v, gen[i].p.ring()))*gen[i].p; 00091 } 00092 VariablePairData(int i, idx_type v){ 00093 this->v=v; 00094 this->i=i; 00095 } 00096 }; 00097 typedef boost::shared_ptr<PairData> pair_data_ptr; 00098 enum { 00099 VARIABLE_PAIR, 00100 IJ_PAIR, 00101 DELAYED_PAIR 00102 }; 00103 00104 class PairLS{ 00105 private: 00106 int type; 00107 public: 00108 int getType() const{ 00109 return type; 00110 } 00111 wlen_type wlen; 00112 deg_type sugar; 00113 //three sorts of pairs 00114 //x*poly, poly, i,j 00115 pair_data_ptr data; 00116 Monomial lm; //must not be the real lm, can be lm of syzygy or something else 00117 Polynomial extract(const PolyEntryVector& v){ 00118 return data->extract(v); 00119 } 00120 PairLS(int i, int j, const PolyEntryVector &v): 00121 data(new IJPairData(i,j)), 00122 lm(v[i].lead*v[j].lead), 00123 wlen(v[i].weightedLength+v[j].weightedLength-2) 00124 { 00125 type=IJ_PAIR; 00126 sugar=lm.deg()+std::max(v[i].ecart(),v[j].ecart()); 00127 } 00128 PairLS(int i, idx_type v, const PolyEntryVector &gen,int type): 00129 data(new VariablePairData(i,v)), 00130 sugar(gen[i].deg+1), 00131 // sugar(gen[i].lmDeg+1),///@only do that because of bad criteria impl 00132 wlen(gen[i].weightedLength+gen[i].length), 00133 lm(gen[i].lead) 00134 00135 { 00136 assert(type==VARIABLE_PAIR); 00137 this->type=type; 00138 } 00139 00140 PairLS(const Polynomial& delayed): 00141 data(new PolyPairData(delayed)), 00142 lm(delayed.lead()), 00143 sugar(delayed.deg()), wlen(delayed.eliminationLength()){ 00144 this->type=DELAYED_PAIR; 00145 } 00146 00147 }; 00148 00149 class PairE{ 00150 private: 00151 int type; 00152 public: 00153 int getType() const{ 00154 return type; 00155 } 00156 wlen_type wlen; 00157 deg_type sugar; 00158 //three sorts of pairs 00159 //x*poly, poly, i,j 00160 pair_data_ptr data; 00161 Exponent lm; //must not be the real lm, can be lm of syzygy or something else 00162 Polynomial extract(const PolyEntryVector& v){ 00163 return data->extract(v); 00164 } 00165 PairE(int i, int j, const PolyEntryVector &v): 00166 data(new IJPairData(i,j)), 00167 lm(v[i].leadExp+v[j].leadExp), 00168 wlen(v[i].weightedLength+v[j].weightedLength-2) 00169 { 00170 type=IJ_PAIR; 00171 sugar=lm.deg()+std::max(v[i].ecart(),v[j].ecart()); 00172 } 00173 PairE(int i, idx_type v, const PolyEntryVector &gen,int type): 00174 data(new VariablePairData(i,v)), 00175 sugar(gen[i].deg+1), 00176 // sugar(gen[i].lmDeg+1),///@only do that because of bad criteria impl 00177 wlen(gen[i].weightedLength+gen[i].length), 00178 lm(gen[i].leadExp) 00179 00180 { 00181 assert(type==VARIABLE_PAIR); 00182 this->type=type; 00183 if (gen[i].leadExp==gen[i].usedVariables) 00184 sugar=gen[i].deg; 00185 if (gen[i].tailVariables.deg()<gen[i].deg) 00186 sugar=gen[i].deg; 00187 } 00188 00189 PairE(const Polynomial& delayed): 00190 data(new PolyPairData(delayed)), 00191 //lm(delayed.lead()), 00192 lm(delayed.leadExp()), 00193 sugar(delayed.deg()), wlen(delayed.eliminationLength()){ 00194 this->type=DELAYED_PAIR; 00195 } 00196 00197 }; 00198 00199 00200 00201 class PairLSCompare{ 00202 public: 00204 bool operator() (const PairLS& l, const PairLS& r){ 00205 if (l.sugar!=r.sugar) return l.sugar>r.sugar; //greater sugar, less importance 00206 if (l.wlen!=r.wlen) return l.wlen>r.wlen; 00207 if (l.lm!=r.lm) return l.lm>r.lm; 00208 00210 return false; 00211 } 00212 }; 00213 00214 class PairECompare{ 00215 public: 00217 bool operator() (const PairE& l, const PairE& r){ 00218 if (l.sugar!=r.sugar) return l.sugar>r.sugar; //greater sugar, less importance 00219 if (l.wlen!=r.wlen) return l.wlen>r.wlen; 00220 if (l.lm!=r.lm) return l.lm>r.lm; 00221 00223 return false; 00224 } 00225 }; 00226 typedef PairE Pair; 00227 00228 END_NAMESPACE_PBORIGB 00229 00230 #endif