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