00001
00002
00003
00004
00005
00006
00007
00008
00009
00010
00011
00012
00013
00014
00015
00016
00017
00018
00019
00020
00021
00022
00023 #include <config.h>
00024
00025 #include "Linear_Row.defs.hh"
00026 #include "Coefficient.defs.hh"
00027 #include <algorithm>
00028 #include <iostream>
00029
00030 namespace PPL = Parma_Polyhedra_Library;
00031
00032 void
00033 PPL::Linear_Row::sign_normalize() {
00034 if (is_line_or_equality()) {
00035 Linear_Row& x = *this;
00036 const dimension_type sz = x.size();
00037
00038
00039
00040 dimension_type first_non_zero;
00041 for (first_non_zero = 1; first_non_zero < sz; ++first_non_zero)
00042 if (x[first_non_zero] != 0)
00043 break;
00044 if (first_non_zero < sz)
00045
00046
00047 if (x[first_non_zero] < 0) {
00048 for (dimension_type j = first_non_zero; j < sz; ++j)
00049 neg_assign(x[j]);
00050
00051 neg_assign(x[0]);
00052 }
00053 }
00054 }
00055
00056 bool
00057 PPL::Linear_Row::check_strong_normalized() const {
00058 Linear_Row tmp = *this;
00059 tmp.strong_normalize();
00060 return compare(*this, tmp) == 0;
00061 }
00062
00064 int
00065 PPL::compare(const Linear_Row& x, const Linear_Row& y) {
00066 const bool x_is_line_or_equality = x.is_line_or_equality();
00067 const bool y_is_line_or_equality = y.is_line_or_equality();
00068 if (x_is_line_or_equality != y_is_line_or_equality)
00069
00070 return y_is_line_or_equality ? 2 : -2;
00071
00072
00073 const dimension_type xsz = x.size();
00074 const dimension_type ysz = y.size();
00075 const dimension_type min_sz = std::min(xsz, ysz);
00076 dimension_type i;
00077 for (i = 1; i < min_sz; ++i)
00078 if (const int comp = cmp(x[i], y[i]))
00079
00080 return (comp > 0) ? 2 : -2;
00081
00082
00083 if (xsz != ysz) {
00084 for( ; i < xsz; ++i)
00085 if (const int sign = sgn(x[i]))
00086 return (sign > 0) ? 2 : -2;
00087 for( ; i < ysz; ++i)
00088 if (const int sign = sgn(y[i]))
00089 return (sign < 0) ? 2 : -2;
00090 }
00091
00092
00093
00094
00095 if (const int comp = cmp(x[0], y[0]))
00096 return (comp > 0) ? 1 : -1;
00097
00098
00099 return 0;
00100 }
00101
00102 void
00103 PPL::Linear_Row::linear_combine(const Linear_Row& y, const dimension_type k) {
00104 Linear_Row& x = *this;
00105
00106 assert(x.size() == y.size());
00107 assert(y[k] != 0 && x[k] != 0);
00108
00109
00110
00111 TEMP_INTEGER(normalized_x_k);
00112 TEMP_INTEGER(normalized_y_k);
00113 normalize2(x[k], y[k], normalized_x_k, normalized_y_k);
00114 for (dimension_type i = size(); i-- > 0; )
00115 if (i != k) {
00116 Coefficient& x_i = x[i];
00117 x_i *= normalized_y_k;
00118 sub_mul_assign(x_i, y[i], normalized_x_k);
00119 }
00120 x[k] = 0;
00121 x.strong_normalize();
00122 }
00123
00124 bool
00125 PPL::Linear_Row::all_homogeneous_terms_are_zero() const {
00126 const Linear_Row& x = *this;
00127 for (dimension_type i = x.size(); --i > 0; )
00128 if (x[i] != 0)
00129 return false;
00130 return true;
00131 }
00132
00133 namespace {
00134
00135
00136 const char* rpi_valid = "RPI_V";
00137 const char* is_rpi = "RPI";
00138 const char* nnc_valid = "NNC_V";
00139 const char* is_nnc = "NNC";
00140 const char* bit_names[] = {rpi_valid, is_rpi, nnc_valid, is_nnc};
00141
00142 }
00143
00144 void
00145 PPL::Linear_Row::Flags::ascii_dump(std::ostream& s) const {
00146 s << (test_bits(1 << Flags::rpi_validity_bit) ? '+' : '-')
00147 << rpi_valid << ' '
00148 << (test_bits(1 << Flags::rpi_bit) ? '+' : '-')
00149 << is_rpi << ' '
00150 << ' '
00151 << (test_bits(1 << Flags::nnc_validity_bit) ? '+' : '-')
00152 << nnc_valid << ' '
00153 << (test_bits(1 << Flags::nnc_bit) ? '+' : '-')
00154 << is_nnc;
00155 }
00156
00157 PPL_OUTPUT_DEFINITIONS_ASCII_ONLY(Linear_Row::Flags);
00158
00159 bool
00160 PPL::Linear_Row::Flags::ascii_load(std::istream& s) {
00161 std::string str;
00162
00163 reset_bits(std::numeric_limits<base_type>::max());
00164 for (unsigned int bit = 0;
00165 bit < (sizeof(bit_names) / sizeof(char*));
00166 ++bit) {
00167 if (!(s >> str))
00168 return false;
00169 if (str[0] == '+')
00170 set_bits(1 << Row::Flags::first_free_bit + bit);
00171 else if (str[0] != '-')
00172 return false;
00173 if (str.compare(1, strlen(bit_names[bit]), bit_names[bit]) != 0)
00174 return false;
00175 }
00176 return true;
00177 }
00178
00179 void
00180 PPL::Linear_Row::ascii_dump(std::ostream& s) const {
00181 const Row& x = *this;
00182 dimension_type x_size = x.size();
00183 for (dimension_type i = 0; i < x_size; ++i)
00184 s << x[i] << ' ';
00185 s << "f ";
00186 flags().ascii_dump(s);
00187 s << "\n";
00188 }
00189
00190 PPL_OUTPUT_DEFINITIONS_ASCII_ONLY(Linear_Row);
00191
00192 bool
00193 PPL::Linear_Row::ascii_load(std::istream& s) {
00194 Row& x = *this;
00195 std::string str;
00196 const dimension_type x_size = x.size();
00197 for (dimension_type col = 0; col < x_size; ++col)
00198 if (!(s >> x[col]))
00199 return false;
00200 if (!(s >> str) || (str.compare("f") != 0))
00201 return false;
00202 return flags().ascii_load(s);
00203 }
00204
00205 bool
00206 PPL::Linear_Row::OK(const dimension_type row_size,
00207 const dimension_type row_capacity) const {
00208 return Row::OK(row_size, row_capacity);
00209 }