post.hpp
Go to the documentation of this file.00001
00002
00003
00004
00005
00006
00007
00008
00009
00010
00011
00012
00013
00014
00015
00016
00017
00018
00019
00020
00021
00022
00023
00024
00025
00026
00027
00028
00029
00030
00031
00032
00033
00034
00035
00036
00037
00038 #include <algorithm>
00039 #include <climits>
00040
00041 namespace Gecode { namespace Int { namespace Linear {
00042
00043 template<class View>
00044 inline void
00045 estimate(Term<View>* t, int n, int c, int& l, int &u) {
00046 long long int min = c;
00047 long long int max = c;
00048 for (int i=n; i--; ) {
00049 long long int a = t[i].a;
00050 if (a > 0) {
00051 min += a*t[i].x.min();
00052 max += a*t[i].x.max();
00053 } else {
00054 max += a*t[i].x.min();
00055 min += a*t[i].x.max();
00056 }
00057 }
00058 if (min < Limits::min)
00059 min = Limits::min;
00060 if (min > Limits::max)
00061 min = Limits::max;
00062 l = static_cast<int>(min);
00063 if (max < Limits::min)
00064 max = Limits::min;
00065 if (max > Limits::max)
00066 max = Limits::max;
00067 u = static_cast<int>(max);
00068 }
00069
00071 template<class View>
00072 class TermLess {
00073 public:
00074 forceinline bool
00075 operator ()(const Term<View>& a, const Term<View>& b) {
00076 return before(a.x,b.x);
00077 }
00078 };
00079
00081 inline int
00082 gcd(int a, int b) {
00083 if (b > a)
00084 std::swap(a,b);
00085 while (b > 0) {
00086 int t = b; b = a % b; a = t;
00087 }
00088 return a;
00089 }
00090
00091
00092
00117 template<class View>
00118 inline bool
00119 normalize(Term<View>* t, int &n,
00120 Term<View>* &t_p, int &n_p,
00121 Term<View>* &t_n, int &n_n,
00122 int& g) {
00123
00124
00125
00126
00127 {
00128
00129 TermLess<View> tl;
00130 Support::quicksort<Term<View>,TermLess<View> >(t,n,tl);
00131
00132
00133 int i = 0;
00134 int j = 0;
00135 while (i < n) {
00136 Limits::check(t[i].a,"Int::linear");
00137 long long int a = t[i].a;
00138 View x = t[i].x;
00139 while ((++i < n) && same(t[i].x,x)) {
00140 a += t[i].a;
00141 Limits::check(a,"Int::linear");
00142 }
00143 if (a != 0) {
00144 t[j].a = static_cast<int>(a); t[j].x = x; j++;
00145 }
00146 }
00147 n = j;
00148 }
00149
00150
00151
00152
00153
00154 if (n > 0) {
00155 int i = 0;
00156 int j = n-1;
00157 while (true) {
00158 while ((t[j].a < 0) && (--j >= 0)) ;
00159 while ((t[i].a > 0) && (++i < n)) ;
00160 if (j <= i) break;
00161 std::swap(t[i],t[j]);
00162 }
00163 t_p = t; n_p = i;
00164 t_n = t+n_p; n_n = n-n_p;
00165 } else {
00166 t_p = t; n_p = 0;
00167 t_n = t; n_n = 0;
00168 }
00169
00170
00171
00172
00173
00174 for (int i=n_n; i--; )
00175 t_n[i].a = -t_n[i].a;
00176
00177
00178
00179
00180
00181 if ((n > 0) && (g > 0)) {
00182 g = t[0].a;
00183 for (int i=1; (g > 1) && (i < n); i++)
00184 g = gcd(t[i].a,g);
00185 if (g > 1)
00186 for (int i=n; i--; )
00187 t[i].a /= g;
00188 } else {
00189 g = 1;
00190 }
00191
00192
00193
00194
00195
00196 for (int i=n; i--; )
00197 if (t[i].a != 1)
00198 return false;
00199 return true;
00200 }
00201
00202 }}}
00203
00204
00205