post.icc
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 double min = c;
00047 double max = c;
00048 for (int i=n; i--; )
00049 if (t[i].a > 0) {
00050 min += t[i].a*t[i].x.min();
00051 max += t[i].a*t[i].x.max();
00052 } else {
00053 max += t[i].a*t[i].x.min();
00054 min += t[i].a*t[i].x.max();
00055 }
00056 if (min < Limits::min)
00057 min = Limits::min;
00058 l = static_cast<int>(min);
00059 if (max > Limits::max)
00060 max = Limits::max;
00061 u = static_cast<int>(max);
00062 }
00063
00065 template<class View>
00066 class TermLess {
00067 public:
00068 forceinline bool
00069 operator()(const Term<View>& a, const Term<View>& b) {
00070 return before(a.x,b.x);
00071 }
00072 };
00073
00074 template<class View>
00075 inline bool
00076 normalize(Term<View>* t, int &n,
00077 Term<View>* &t_p, int &n_p,
00078 Term<View>* &t_n, int &n_n) {
00079
00080
00081
00082
00083 {
00084
00085 TermLess<View> tl;
00086 Support::quicksort<Term<View>,TermLess<View> >(t,n,tl);
00087
00088
00089 int i = 0;
00090 int j = 0;
00091 while (i < n) {
00092 Limits::check(t[i].a,"Int::linear");
00093 double a = t[i].a;
00094 View x = t[i].x;
00095 while ((++i < n) && same(t[i].x,x)) {
00096 a += t[i].a;
00097 Limits::check(a,"Int::linear");
00098 }
00099 if (a != 0.0) {
00100 t[j].a = static_cast<int>(a); t[j].x = x; j++;
00101 }
00102 }
00103 n = j;
00104 }
00105
00106
00107
00108
00109
00110 if (n > 0) {
00111 int i = 0;
00112 int j = n-1;
00113 while (true) {
00114 while ((t[j].a < 0) && (--j >= 0)) ;
00115 while ((t[i].a > 0) && (++i < n)) ;
00116 if (j <= i) break;
00117 std::swap(t[i],t[j]);
00118 }
00119 t_p = t; n_p = i;
00120 t_n = t+n_p; n_n = n-n_p;
00121 } else {
00122 t_p = t; n_p = 0;
00123 t_n = t; n_n = 0;
00124 }
00125
00126
00127
00128
00129
00130 for (int i=n_n; i--; )
00131 t_n[i].a = -t_n[i].a;
00132
00133
00134
00135
00136
00137 for (int i=n; i--; )
00138 if (t[i].a != 1)
00139 return false;
00140 return true;
00141 }
00142
00143 }}}
00144
00145
00146