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 #include <algorithm>
00035 #include <climits>
00036
00037 namespace Gecode { namespace Int { namespace Linear {
00038
00039 template<class View>
00040 inline void
00041 estimate(Term<View>* t, int n, int c, int& l, int &u) {
00042 long long int min = c;
00043 long long int max = c;
00044 for (int i=n; i--; ) {
00045 long long int a = t[i].a;
00046 if (a > 0) {
00047 min += a*t[i].x.min();
00048 max += a*t[i].x.max();
00049 } else {
00050 max += a*t[i].x.min();
00051 min += a*t[i].x.max();
00052 }
00053 }
00054 if (min < Limits::min)
00055 min = Limits::min;
00056 if (min > Limits::max)
00057 min = Limits::max;
00058 l = static_cast<int>(min);
00059 if (max < Limits::min)
00060 max = Limits::min;
00061 if (max > Limits::max)
00062 max = Limits::max;
00063 u = static_cast<int>(max);
00064 }
00065
00067 template<class View>
00068 class TermLess {
00069 public:
00070 forceinline bool
00071 operator ()(const Term<View>& a, const Term<View>& b) {
00072 return before(a.x,b.x);
00073 }
00074 };
00075
00077 inline int
00078 gcd(int a, int b) {
00079 if (b > a)
00080 std::swap(a,b);
00081 while (b > 0) {
00082 int t = b; b = a % b; a = t;
00083 }
00084 return a;
00085 }
00086
00087
00088
00113 template<class View>
00114 inline bool
00115 normalize(Term<View>* t, int &n,
00116 Term<View>* &t_p, int &n_p,
00117 Term<View>* &t_n, int &n_n,
00118 int& g) {
00119
00120
00121
00122
00123 {
00124
00125 TermLess<View> tl;
00126 Support::quicksort<Term<View>,TermLess<View> >(t,n,tl);
00127
00128
00129 int i = 0;
00130 int j = 0;
00131 while (i < n) {
00132 Limits::check(t[i].a,"Int::linear");
00133 long long int a = t[i].a;
00134 View x = t[i].x;
00135 while ((++i < n) && same(t[i].x,x)) {
00136 a += t[i].a;
00137 Limits::check(a,"Int::linear");
00138 }
00139 if (a != 0) {
00140 t[j].a = static_cast<int>(a); t[j].x = x; j++;
00141 }
00142 }
00143 n = j;
00144 }
00145
00146
00147
00148
00149
00150 if (n > 0) {
00151 int i = 0;
00152 int j = n-1;
00153 while (true) {
00154 while ((t[j].a < 0) && (--j >= 0)) ;
00155 while ((t[i].a > 0) && (++i < n)) ;
00156 if (j <= i) break;
00157 std::swap(t[i],t[j]);
00158 }
00159 t_p = t; n_p = i;
00160 t_n = t+n_p; n_n = n-n_p;
00161 } else {
00162 t_p = t; n_p = 0;
00163 t_n = t; n_n = 0;
00164 }
00165
00166
00167
00168
00169
00170 for (int i=n_n; i--; )
00171 t_n[i].a = -t_n[i].a;
00172
00173
00174
00175
00176
00177 if ((n > 0) && (g > 0)) {
00178 g = t[0].a;
00179 for (int i=1; (g > 1) && (i < n); i++)
00180 g = gcd(t[i].a,g);
00181 if (g > 1)
00182 for (int i=n; i--; )
00183 t[i].a /= g;
00184 } else {
00185 g = 1;
00186 }
00187
00188
00189
00190
00191
00192 for (int i=n; i--; )
00193 if (t[i].a != 1)
00194 return false;
00195 return true;
00196 }
00197
00198 }}}
00199
00200
00201