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 <ppl-config.h>
00025
00026 #include "Linear_Expression.defs.hh"
00027 #include "Constraint.defs.hh"
00028 #include "Generator.defs.hh"
00029 #include "Grid_Generator.defs.hh"
00030 #include "Congruence.defs.hh"
00031 #include <stdexcept>
00032
00033 namespace PPL = Parma_Polyhedra_Library;
00034
00035 PPL::Linear_Expression::Linear_Expression(const Constraint& c)
00036 : Linear_Row(c.space_dimension() + 1, Linear_Row::Flags()) {
00037 Linear_Expression& e = *this;
00038 for (dimension_type i = size(); i-- > 0; )
00039 e[i] = c[i];
00040 }
00041
00042 PPL::Linear_Expression::Linear_Expression(const Generator& g)
00043 : Linear_Row(g.space_dimension() + 1, Linear_Row::Flags()) {
00044 Linear_Expression& e = *this;
00045
00046 for (dimension_type i = size(); --i > 0; )
00047 e[i] = g[i];
00048 }
00049
00050 PPL::Linear_Expression::Linear_Expression(const Grid_Generator& g)
00051 : Linear_Row(g.space_dimension() + 1, Linear_Row::Flags()) {
00052 Linear_Expression& e = *this;
00053
00054 for (dimension_type i = size(); --i > 0; )
00055 e[i] = g[i];
00056 }
00057
00058 const PPL::Linear_Expression* PPL::Linear_Expression::zero_p = 0;
00059
00060 void
00061 PPL::Linear_Expression::initialize() {
00062 assert(zero_p == 0);
00063 zero_p = new Linear_Expression(Coefficient_zero());
00064 }
00065
00066 void
00067 PPL::Linear_Expression::finalize() {
00068 assert(zero_p != 0);
00069 delete zero_p;
00070 zero_p = 0;
00071 }
00072
00073 PPL::Linear_Expression::Linear_Expression(const Congruence& cg)
00074 : Linear_Row(cg.space_dimension() + 1, Linear_Row::Flags()) {
00075 Linear_Expression& e = *this;
00076 for (dimension_type i = size(); i-- > 0; )
00077 e[i] = cg[i];
00078 }
00079
00081 PPL::Linear_Expression
00082 PPL::operator+(const Linear_Expression& e1, const Linear_Expression& e2) {
00083 dimension_type e1_size = e1.size();
00084 dimension_type e2_size = e2.size();
00085 dimension_type min_size;
00086 dimension_type max_size;
00087 const Linear_Expression* p_e_max;
00088 if (e1_size > e2_size) {
00089 min_size = e2_size;
00090 max_size = e1_size;
00091 p_e_max = &e1;
00092 }
00093 else {
00094 min_size = e1_size;
00095 max_size = e2_size;
00096 p_e_max = &e2;
00097 }
00098
00099 Linear_Expression r(max_size, false);
00100 dimension_type i = max_size;
00101 while (i > min_size) {
00102 --i;
00103 r[i] = (*p_e_max)[i];
00104 }
00105 while (i > 0) {
00106 --i;
00107 r[i] = e1[i] + e2[i];
00108 }
00109
00110 return r;
00111 }
00112
00114 PPL::Linear_Expression
00115 PPL::operator+(Coefficient_traits::const_reference n,
00116 const Linear_Expression& e) {
00117 Linear_Expression r(e);
00118 r[0] += n;
00119 return r;
00120 }
00121
00123 PPL::Linear_Expression
00124 PPL::operator-(const Linear_Expression& e) {
00125 Linear_Expression r(e);
00126 for (dimension_type i = e.size(); i-- > 0; )
00127 neg_assign(r[i]);
00128 return r;
00129 }
00130
00132 PPL::Linear_Expression
00133 PPL::operator-(const Linear_Expression& e1, const Linear_Expression& e2) {
00134 dimension_type e1_size = e1.size();
00135 dimension_type e2_size = e2.size();
00136 if (e1_size > e2_size) {
00137 Linear_Expression r(e1_size, false);
00138 dimension_type i = e1_size;
00139 while (i > e2_size) {
00140 --i;
00141 r[i] = e1[i];
00142 }
00143 while (i > 0) {
00144 --i;
00145 r[i] = e1[i] - e2[i];
00146 }
00147 return r;
00148 }
00149 else {
00150 Linear_Expression r(e2_size, false);
00151 dimension_type i = e2_size;
00152 while (i > e1_size) {
00153 --i;
00154 r[i] = -e2[i];
00155 }
00156 while (i > 0) {
00157 --i;
00158 r[i] = e1[i] - e2[i];
00159 }
00160 return r;
00161 }
00162 }
00163
00165 PPL::Linear_Expression
00166 PPL::operator-(Coefficient_traits::const_reference n,
00167 const Linear_Expression& e) {
00168 Linear_Expression r(e);
00169 for (dimension_type i = e.size(); i-- > 0; )
00170 neg_assign(r[i]);
00171 r[0] += n;
00172
00173 return r;
00174 }
00175
00177 PPL::Linear_Expression
00178 PPL::operator*(Coefficient_traits::const_reference n,
00179 const Linear_Expression& e) {
00180 Linear_Expression r(e);
00181 for (dimension_type i = e.size(); i-- > 0; )
00182 r[i] *= n;
00183 return r;
00184 }
00185
00187 PPL::Linear_Expression&
00188 PPL::operator+=(Linear_Expression& e1, const Linear_Expression& e2) {
00189 dimension_type e1_size = e1.size();
00190 dimension_type e2_size = e2.size();
00191 if (e1_size >= e2_size)
00192 for (dimension_type i = e2_size; i-- > 0; )
00193 e1[i] += e2[i];
00194 else {
00195 Linear_Expression e(e2);
00196 for (dimension_type i = e1_size; i-- > 0; )
00197 e[i] += e1[i];
00198 std::swap(e1, e);
00199 }
00200 return e1;
00201 }
00202
00204 PPL::Linear_Expression&
00205 PPL::operator+=(Linear_Expression& e, const Variable v) {
00206 const dimension_type v_space_dim = v.space_dimension();
00207 if (v_space_dim > Linear_Expression::max_space_dimension())
00208 throw std::length_error("PPL::operator+=(e, v):\n"
00209 "v exceeds the maximum allowed space dimension.");
00210 const dimension_type e_size = e.size();
00211 if (e_size <= v_space_dim) {
00212 Linear_Expression new_e(e, v_space_dim+1);
00213 std::swap(e, new_e);
00214 }
00215 ++e[v_space_dim];
00216 return e;
00217 }
00218
00220 PPL::Linear_Expression&
00221 PPL::operator-=(Linear_Expression& e1, const Linear_Expression& e2) {
00222 dimension_type e1_size = e1.size();
00223 dimension_type e2_size = e2.size();
00224 if (e1_size >= e2_size)
00225 for (dimension_type i = e2_size; i-- > 0; )
00226 e1[i] -= e2[i];
00227 else {
00228 Linear_Expression e(e1, e2_size);
00229 for (dimension_type i = e2_size; i-- > 0; )
00230 e[i] -= e2[i];
00231 std::swap(e1, e);
00232 }
00233 return e1;
00234 }
00235
00237 PPL::Linear_Expression&
00238 PPL::operator-=(Linear_Expression& e, const Variable v) {
00239 const dimension_type v_space_dim = v.space_dimension();
00240 if (v_space_dim > Linear_Expression::max_space_dimension())
00241 throw std::length_error("PPL::operator-=(e, v):\n"
00242 "v exceeds the maximum allowed space dimension.");
00243 const dimension_type e_size = e.size();
00244 if (e_size <= v_space_dim) {
00245 Linear_Expression new_e(e, v_space_dim+1);
00246 std::swap(e, new_e);
00247 }
00248 --e[v_space_dim];
00249 return e;
00250 }
00251
00253 PPL::Linear_Expression&
00254 PPL::operator*=(Linear_Expression& e, Coefficient_traits::const_reference n) {
00255 dimension_type e_size = e.size();
00256 for (dimension_type i = e_size; i-- > 0; )
00257 e[i] *= n;
00258 return e;
00259 }
00260
00261 bool
00262 PPL::Linear_Expression::OK() const {
00263 return Linear_Row::OK();
00264 }
00265
00267 std::ostream&
00268 PPL::IO_Operators::operator<<(std::ostream& s, const Linear_Expression& e) {
00269 const dimension_type num_variables = e.space_dimension();
00270 TEMP_INTEGER(ev);
00271 bool first = true;
00272 for (dimension_type v = 0; v < num_variables; ++v) {
00273 ev = e[v+1];
00274 if (ev != 0) {
00275 if (!first) {
00276 if (ev > 0)
00277 s << " + ";
00278 else {
00279 s << " - ";
00280 neg_assign(ev);
00281 }
00282 }
00283 else
00284 first = false;
00285 if (ev == -1)
00286 s << "-";
00287 else if (ev != 1)
00288 s << ev << "*";
00289 s << PPL::Variable(v);
00290 }
00291 }
00292
00293 TEMP_INTEGER(it);
00294 it = e[0];
00295 if (it != 0) {
00296 if (!first) {
00297 if (it > 0)
00298 s << " + ";
00299 else {
00300 s << " - ";
00301 neg_assign(it);
00302 }
00303 }
00304 else
00305 first = false;
00306 s << it;
00307 }
00308
00309 if (first)
00310
00311 s << Coefficient_zero();
00312 return s;
00313 }
00314
00315 PPL_OUTPUT_DEFINITIONS(Linear_Expression)