00001
00002
00003
00004
00005
00006
00007
00008
00009
00010
00011
00012
00013
00014
00015
00016
00017
00018
00019
00020
00021
00022
00023
00024 #include <config.h>
00025
00026 #include "Linear_Expression.defs.hh"
00027 #include "Constraint.defs.hh"
00028 #include "Generator.defs.hh"
00029 #include "Congruence.defs.hh"
00030 #include <stdexcept>
00031
00032 namespace PPL = Parma_Polyhedra_Library;
00033
00034 PPL::Linear_Expression::Linear_Expression(const Constraint& c)
00035 : Linear_Row(c.space_dimension() + 1, Linear_Row::Flags()) {
00036 Linear_Expression& e = *this;
00037 for (dimension_type i = size(); i-- > 0; )
00038 e[i] = c[i];
00039 }
00040
00041 PPL::Linear_Expression::Linear_Expression(const Generator& g)
00042 : Linear_Row(g.space_dimension() + 1, Linear_Row::Flags()) {
00043 Linear_Expression& e = *this;
00044
00045 for (dimension_type i = size(); --i > 0; )
00046 e[i] = g[i];
00047 }
00048
00049 PPL::Linear_Expression::Linear_Expression(const Congruence& cg)
00050 : Linear_Row(cg.space_dimension() + 1, Linear_Row::Flags()) {
00051 Linear_Expression& e = *this;
00052 for (dimension_type i = size(); i-- > 0; )
00053 e[i] = cg[i];
00054 }
00055
00056
00058 PPL::Linear_Expression
00059 PPL::operator+(const Linear_Expression& e1, const Linear_Expression& e2) {
00060 dimension_type e1_size = e1.size();
00061 dimension_type e2_size = e2.size();
00062 dimension_type min_size;
00063 dimension_type max_size;
00064 const Linear_Expression* p_e_max;
00065 if (e1_size > e2_size) {
00066 min_size = e2_size;
00067 max_size = e1_size;
00068 p_e_max = &e1;
00069 }
00070 else {
00071 min_size = e1_size;
00072 max_size = e2_size;
00073 p_e_max = &e2;
00074 }
00075
00076 Linear_Expression r(max_size, false);
00077 dimension_type i = max_size;
00078 while (i > min_size) {
00079 --i;
00080 r[i] = (*p_e_max)[i];
00081 }
00082 while (i > 0) {
00083 --i;
00084 r[i] = e1[i] + e2[i];
00085 }
00086
00087 return r;
00088 }
00089
00091 PPL::Linear_Expression
00092 PPL::operator+(Coefficient_traits::const_reference n,
00093 const Linear_Expression& e) {
00094 Linear_Expression r(e);
00095 r[0] += n;
00096 return r;
00097 }
00098
00100 PPL::Linear_Expression
00101 PPL::operator-(const Linear_Expression& e) {
00102 Linear_Expression r(e);
00103 for (dimension_type i = e.size(); i-- > 0; )
00104 neg_assign(r[i]);
00105 return r;
00106 }
00107
00109 PPL::Linear_Expression
00110 PPL::operator-(const Linear_Expression& e1, const Linear_Expression& e2) {
00111 dimension_type e1_size = e1.size();
00112 dimension_type e2_size = e2.size();
00113 if (e1_size > e2_size) {
00114 Linear_Expression r(e1_size, false);
00115 dimension_type i = e1_size;
00116 while (i > e2_size) {
00117 --i;
00118 r[i] = e1[i];
00119 }
00120 while (i > 0) {
00121 --i;
00122 r[i] = e1[i] - e2[i];
00123 }
00124 return r;
00125 }
00126 else {
00127 Linear_Expression r(e2_size, false);
00128 dimension_type i = e2_size;
00129 while (i > e1_size) {
00130 --i;
00131 r[i] = -e2[i];
00132 }
00133 while (i > 0) {
00134 --i;
00135 r[i] = e1[i] - e2[i];
00136 }
00137 return r;
00138 }
00139 }
00140
00142 PPL::Linear_Expression
00143 PPL::operator-(Coefficient_traits::const_reference n,
00144 const Linear_Expression& e) {
00145 Linear_Expression r(e);
00146 for (dimension_type i = e.size(); i-- > 0; )
00147 neg_assign(r[i]);
00148 r[0] += n;
00149
00150 return r;
00151 }
00152
00154 PPL::Linear_Expression
00155 PPL::operator*(Coefficient_traits::const_reference n,
00156 const Linear_Expression& e) {
00157 Linear_Expression r(e);
00158 for (dimension_type i = e.size(); i-- > 0; )
00159 r[i] *= n;
00160 return r;
00161 }
00162
00164 PPL::Linear_Expression&
00165 PPL::operator+=(Linear_Expression& e1, const Linear_Expression& e2) {
00166 dimension_type e1_size = e1.size();
00167 dimension_type e2_size = e2.size();
00168 if (e1_size >= e2_size)
00169 for (dimension_type i = e2_size; i-- > 0; )
00170 e1[i] += e2[i];
00171 else {
00172 Linear_Expression e(e2);
00173 for (dimension_type i = e1_size; i-- > 0; )
00174 e[i] += e1[i];
00175 std::swap(e1, e);
00176 }
00177 return e1;
00178 }
00179
00181 PPL::Linear_Expression&
00182 PPL::operator+=(Linear_Expression& e, const Variable v) {
00183 const dimension_type v_space_dim = v.space_dimension();
00184 if (v_space_dim > Linear_Expression::max_space_dimension())
00185 throw std::length_error("PPL::operator+=(e, v):\n"
00186 "v exceeds the maximum allowed space dimension.");
00187 const dimension_type e_size = e.size();
00188 if (e_size <= v_space_dim) {
00189 Linear_Expression new_e(e, v_space_dim+1);
00190 std::swap(e, new_e);
00191 }
00192 ++e[v_space_dim];
00193 return e;
00194 }
00195
00197 PPL::Linear_Expression&
00198 PPL::operator-=(Linear_Expression& e1, const Linear_Expression& e2) {
00199 dimension_type e1_size = e1.size();
00200 dimension_type e2_size = e2.size();
00201 if (e1_size >= e2_size)
00202 for (dimension_type i = e2_size; i-- > 0; )
00203 e1[i] -= e2[i];
00204 else {
00205 Linear_Expression e(e1, e2_size);
00206 for (dimension_type i = e2_size; i-- > 0; )
00207 e[i] -= e2[i];
00208 std::swap(e1, e);
00209 }
00210 return e1;
00211 }
00212
00214 PPL::Linear_Expression&
00215 PPL::operator-=(Linear_Expression& e, const Variable v) {
00216 const dimension_type v_space_dim = v.space_dimension();
00217 if (v_space_dim > Linear_Expression::max_space_dimension())
00218 throw std::length_error("PPL::operator-=(e, v):\n"
00219 "v exceeds the maximum allowed space dimension.");
00220 const dimension_type e_size = e.size();
00221 if (e_size <= v_space_dim) {
00222 Linear_Expression new_e(e, v_space_dim+1);
00223 std::swap(e, new_e);
00224 }
00225 --e[v_space_dim];
00226 return e;
00227 }
00228
00230 PPL::Linear_Expression&
00231 PPL::operator*=(Linear_Expression& e, Coefficient_traits::const_reference n) {
00232 dimension_type e_size = e.size();
00233 for (dimension_type i = e_size; i-- > 0; )
00234 e[i] *= n;
00235 return e;
00236 }
00237
00238 bool
00239 PPL::Linear_Expression::OK() const {
00240 dimension_type sz = size();
00241 return Linear_Row::OK(sz, sz);
00242 }
00243
00245 std::ostream&
00246 PPL::IO_Operators::operator<<(std::ostream& s, const Linear_Expression& e) {
00247 const int num_variables = e.space_dimension();
00248 bool first = true;
00249 for (int v = 0; v < num_variables; ++v) {
00250 Coefficient ev = e[v+1];
00251 if (ev != 0) {
00252 if (!first) {
00253 if (ev > 0)
00254 s << " + ";
00255 else {
00256 s << " - ";
00257 neg_assign(ev);
00258 }
00259 }
00260 else
00261 first = false;
00262 if (ev == -1)
00263 s << "-";
00264 else if (ev != 1)
00265 s << ev << "*";
00266 s << PPL::Variable(v);
00267 }
00268 }
00269
00270 Coefficient it = e[0];
00271 if (it != 0) {
00272 if (!first) {
00273 if (it > 0)
00274 s << " + ";
00275 else {
00276 s << " - ";
00277 neg_assign(it);
00278 }
00279 }
00280 else
00281 first = false;
00282 s << it;
00283 }
00284
00285 if (first)
00286
00287 s << Coefficient_zero();
00288 return s;
00289 }