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