00001
00002
00003
00004
00005
00006
00007
00008
00009
00010
00011
00012
00013
00014
00015
00016
00017
00018
00019
00020
00021
00022
00023 #include <ppl-config.h>
00024
00025 #include "Row.defs.hh"
00026 #include "Coefficient.defs.hh"
00027 #include <iostream>
00028 #include <iomanip>
00029 #include <cassert>
00030
00031 namespace PPL = Parma_Polyhedra_Library;
00032
00033 void
00034 PPL::Row_Impl_Handler::
00035 Impl::expand_within_capacity(const dimension_type new_size) {
00036 assert(size() <= new_size && new_size <= max_size());
00037 #if !PPL_CXX_SUPPORTS_FLEXIBLE_ARRAYS
00038
00039 if (size() == 0 && new_size > 0)
00040 bump_size();
00041 #endif
00042 for (dimension_type i = size(); i < new_size; ++i) {
00043 new (&vec_[i]) Coefficient();
00044 bump_size();
00045 }
00046 }
00047
00048 void
00049 PPL::Row_Impl_Handler::Impl::shrink(dimension_type new_size) {
00050 const dimension_type old_size = size();
00051 assert(new_size <= old_size);
00052
00053 set_size(new_size);
00054 #if !PPL_CXX_SUPPORTS_FLEXIBLE_ARRAYS
00055
00056 if (new_size == 0)
00057 ++new_size;
00058 #endif
00059
00060
00061 for (dimension_type i = old_size; i-- > new_size; )
00062 vec_[i].~Coefficient();
00063 }
00064
00065 void
00066 PPL::Row_Impl_Handler::Impl::copy_construct_coefficients(const Impl& y) {
00067 const dimension_type y_size = y.size();
00068 #if PPL_CXX_SUPPORTS_FLEXIBLE_ARRAYS
00069 for (dimension_type i = 0; i < y_size; ++i) {
00070 new (&vec_[i]) Coefficient(y.vec_[i]);
00071 bump_size();
00072 }
00073 #else
00074 assert(y_size > 0);
00075 if (y_size > 0) {
00076 vec_[0] = y.vec_[0];
00077 bump_size();
00078 for (dimension_type i = 1; i < y_size; ++i) {
00079 new (&vec_[i]) Coefficient(y.vec_[i]);
00080 bump_size();
00081 }
00082 }
00083 #endif
00084 }
00085
00086 void
00087 PPL::Row::normalize() {
00088 Row& x = *this;
00089
00090 const dimension_type sz = size();
00091 dimension_type i = sz;
00092 TEMP_INTEGER(gcd);
00093 while (i > 0) {
00094 const Coefficient& x_i = x[--i];
00095 if (const int x_i_sign = sgn(x_i)) {
00096 gcd = x_i;
00097 if (x_i_sign < 0)
00098 neg_assign(gcd);
00099 goto compute_gcd;
00100 }
00101 }
00102
00103 return;
00104
00105 compute_gcd:
00106 if (gcd == 1)
00107 return;
00108 while (i > 0) {
00109 const Coefficient& x_i = x[--i];
00110 if (x_i != 0) {
00111
00112
00113
00114
00115
00116
00117
00118
00119
00120
00121
00122 gcd_assign(gcd, x_i, gcd);
00123 if (gcd == 1)
00124 return;
00125 }
00126 }
00127
00128 for (dimension_type j = sz; j-- > 0; ) {
00129 Coefficient& x_j = x[j];
00130 exact_div_assign(x_j, x_j, gcd);
00131 }
00132 }
00133
00134 void
00135 PPL::Row::Flags::ascii_dump(std::ostream& s) const {
00136 s << "0x";
00137 std::istream::fmtflags f = s.setf(std::istream::hex);
00138 std::streamsize sz = s.width(2*sizeof(Flags::base_type));
00139 std::ostream::char_type ch = s.fill('0');
00140 s << bits;
00141 s.fill(ch);
00142 s.width(sz);
00143 s.flags(f);
00144 }
00145
00146 PPL_OUTPUT_DEFINITIONS_ASCII_ONLY(Row::Flags)
00147
00148 bool
00149 PPL::Row::Flags::ascii_load(std::istream& s) {
00150 std::string str;
00151 std::streamsize sz = s.width(2);
00152 if (!(s >> str) || (str.compare("0x") != 0))
00153 return false;
00154 s.width(sz);
00155 std::istream::fmtflags f = s.setf(std::istream::hex);
00156 bool r = s >> bits;
00157 s.flags(f);
00158 return r;
00159 }
00160
00161 void
00162 PPL::Row::ascii_dump(std::ostream& s) const {
00163 const Row& x = *this;
00164 const dimension_type x_size = x.size();
00165 s << "size " << x_size << " ";
00166 for (dimension_type i = 0; i < x_size; ++i)
00167 s << x[i] << ' ';
00168 s << "f ";
00169 flags().ascii_dump(s);
00170 s << "\n";
00171 }
00172
00173 PPL_OUTPUT_DEFINITIONS_ASCII_ONLY(Row)
00174
00175 bool
00176 PPL::Row::ascii_load(std::istream& s) {
00177 std::string str;
00178 if (!(s >> str) || str != "size")
00179 return false;
00180 dimension_type new_size;
00181 if (!(s >> new_size))
00182 return false;
00183
00184 Row& x = *this;
00185 const dimension_type old_size = x.size();
00186 if (new_size < old_size)
00187 x.shrink(new_size);
00188 else if (new_size > old_size) {
00189 Row y(new_size, Row::Flags());
00190 x.swap(y);
00191 }
00192
00193 for (dimension_type col = 0; col < new_size; ++col)
00194 if (!(s >> x[col]))
00195 return false;
00196 if (!(s >> str) || (str.compare("f") != 0))
00197 return false;
00198 return flags().ascii_load(s);
00199 }
00200
00201 PPL::memory_size_type
00202 PPL::Row_Impl_Handler::Impl::external_memory_in_bytes() const {
00203 memory_size_type n = 0;
00204 for (dimension_type i = size(); i-- > 0; )
00205 n += PPL::external_memory_in_bytes(vec_[i]);
00206 return n;
00207 }
00208
00209 bool
00210 PPL::Row::OK() const {
00211 #ifndef NDEBUG
00212 using std::endl;
00213 using std::cerr;
00214 #endif
00215
00216 bool is_broken = false;
00217 #if PPL_ROW_EXTRA_DEBUG
00218 # if !PPL_CXX_SUPPORTS_FLEXIBLE_ARRAYS
00219 if (capacity_ == 0) {
00220 cerr << "Illegal row capacity: is 0, should be at least 1"
00221 << endl;
00222 is_broken = true;
00223 }
00224 else
00225 # endif // !PPL_CXX_SUPPORTS_FLEXIBLE_ARRAYS
00226 if (capacity_ > max_size()) {
00227 cerr << "Row capacity exceeds the maximum allowed size:"
00228 << endl
00229 << "is " << capacity_
00230 << ", should be less than or equal to " << max_size() << "."
00231 << endl;
00232 is_broken = true;
00233 }
00234 #endif // PPL_ROW_EXTRA_DEBUG
00235 if (size() > max_size()) {
00236 #ifndef NDEBUG
00237 cerr << "Row size exceeds the maximum allowed size:"
00238 << endl
00239 << "is " << size()
00240 << ", should be less than or equal to " << max_size() << "."
00241 << endl;
00242 #endif
00243 is_broken = true;
00244 }
00245 #if PPL_ROW_EXTRA_DEBUG
00246 if (capacity_ < size()) {
00247 #ifndef NDEBUG
00248 cerr << "Row is completely broken: capacity is " << capacity_
00249 << ", size is " << size() << "."
00250 << endl;
00251 #endif
00252 is_broken = true;
00253 }
00254 #endif // PPL_ROW_EXTRA_DEBUG
00255 return !is_broken;
00256 }
00257
00258 bool
00259 PPL::Row::OK(const dimension_type row_size,
00260 const dimension_type
00261 #if PPL_ROW_EXTRA_DEBUG
00262 row_capacity
00263 #endif
00264 ) const {
00265 #ifndef NDEBUG
00266 using std::endl;
00267 using std::cerr;
00268 #endif
00269
00270 bool is_broken = !OK();
00271
00272 #if PPL_ROW_EXTRA_DEBUG
00273
00274 # if !PPL_CXX_SUPPORTS_FLEXIBLE_ARRAYS
00275 if (capacity_ == 1 && row_capacity == 0)
00276
00277 ;
00278 else
00279 # endif // !PPL_CXX_SUPPORTS_FLEXIBLE_ARRAYS
00280 if (capacity_ != row_capacity) {
00281 cerr << "Row capacity mismatch: is " << capacity_
00282 << ", should be " << row_capacity << "."
00283 << endl;
00284 is_broken = true;
00285 }
00286 #endif // PPL_ROW_EXTRA_DEBUG
00287
00288
00289 if (size() != row_size) {
00290 #ifndef NDEBUG
00291 cerr << "Row size mismatch: is " << size()
00292 << ", should be " << row_size << "."
00293 << endl;
00294 #endif
00295 is_broken = true;
00296 }
00297 return !is_broken;
00298 }
00299
00301 bool
00302 PPL::operator==(const Row& x, const Row& y) {
00303 const dimension_type x_size = x.size();
00304 const dimension_type y_size = y.size();
00305 if (x_size != y_size)
00306 return false;
00307
00308 if (x.flags() != y.flags())
00309 return false;
00310
00311 for (dimension_type i = x_size; i-- > 0; )
00312 if (x[i] != y[i])
00313 return false;
00314
00315 return true;
00316 }