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 namespace Gecode { namespace Float { namespace Linear {
00037
00038
00039
00040
00041
00042 template<class P, class N, PropCond pc>
00043 forceinline
00044 Lin<P,N,pc>::Lin(Home home, ViewArray<P>& x0, ViewArray<N>& y0, FloatVal c0)
00045 : Propagator(home), x(x0), y(y0), c(c0) {
00046 x.subscribe(home,*this,pc);
00047 y.subscribe(home,*this,pc);
00048 }
00049
00050 template<class P, class N, PropCond pc>
00051 forceinline
00052 Lin<P,N,pc>::Lin(Space& home, Lin<P,N,pc>& p)
00053 : Propagator(home,p), c(p.c) {
00054 x.update(home,p.x);
00055 y.update(home,p.y);
00056 }
00057
00058 template<class P, class N, PropCond pc>
00059 PropCost
00060 Lin<P,N,pc>::cost(const Space&, const ModEventDelta&) const {
00061 return PropCost::linear(PropCost::LO, x.size()+y.size());
00062 }
00063
00064 template<class P, class N, PropCond pc>
00065 void
00066 Lin<P,N,pc>::reschedule(Space& home) {
00067 x.reschedule(home,*this,pc);
00068 y.reschedule(home,*this,pc);
00069 }
00070
00071 template<class P, class N, PropCond pc>
00072 forceinline size_t
00073 Lin<P,N,pc>::dispose(Space& home) {
00074 x.cancel(home,*this,pc);
00075 y.cancel(home,*this,pc);
00076 (void) Propagator::dispose(home);
00077 return sizeof(*this);
00078 }
00079
00080
00081 template<class View>
00082 void
00083 eliminate_p(ModEventDelta med, ViewArray<View>& x, FloatVal& c) {
00084 int n = x.size();
00085
00086 if (FloatView::me(med) == ME_FLOAT_VAL) {
00087 for (int i = n; i--; ) {
00088 if (x[i].assigned()) {
00089 c -= x[i].val(); x[i] = x[--n];
00090 }
00091 }
00092 x.size(n);
00093 }
00094 }
00095
00096 template<class View>
00097 void
00098 eliminate_n(ModEventDelta med, ViewArray<View>& y, FloatVal& c) {
00099 int n = y.size();
00100 if (FloatView::me(med) == ME_FLOAT_VAL) {
00101 for (int i = n; i--; ) {
00102 if (y[i].assigned()) {
00103 c += y[i].val(); y[i] = y[--n];
00104 }
00105 }
00106 y.size(n);
00107 }
00108 }
00109
00110 forceinline bool
00111 infty(const FloatNum& n) {
00112 return ((n == std::numeric_limits<FloatNum>::infinity()) ||
00113 (n == -std::numeric_limits<FloatNum>::infinity()));
00114 }
00115
00116
00117
00118
00119
00120
00121 template<class P, class N>
00122 forceinline
00123 Eq<P,N>::Eq(Home home, ViewArray<P>& x, ViewArray<N>& y, FloatVal c)
00124 : Lin<P,N,PC_FLOAT_BND>(home,x,y,c) {}
00125
00126 template<class P, class N>
00127 ExecStatus
00128 Eq<P,N>::post(Home home, ViewArray<P>& x, ViewArray<N>& y, FloatVal c) {
00129 (void) new (home) Eq<P,N>(home,x,y,c);
00130 return ES_OK;
00131 }
00132
00133
00134 template<class P, class N>
00135 forceinline
00136 Eq<P,N>::Eq(Space& home, Eq<P,N>& p)
00137 : Lin<P,N,PC_FLOAT_BND>(home,p) {}
00138
00139 template<class P, class N>
00140 Actor*
00141 Eq<P,N>::copy(Space& home) {
00142 return new (home) Eq<P,N>(home,*this);
00143 }
00144
00145 template<class P, class N>
00146 ExecStatus
00147 Eq<P,N>::propagate(Space& home, const ModEventDelta& med) {
00148
00149 Rounding r;
00150 eliminate_p<P>(med, x, c);
00151 eliminate_n<N>(med, y, c);
00152
00153 if ((FloatView::me(med) == ME_FLOAT_VAL) && ((x.size() + y.size()) <= 1)) {
00154 if (x.size() == 1) {
00155 GECODE_ME_CHECK(x[0].eq(home,c));
00156 return home.ES_SUBSUMED(*this);
00157 }
00158 if (y.size() == 1) {
00159 GECODE_ME_CHECK(y[0].eq(home,-c));
00160 return home.ES_SUBSUMED(*this);
00161 }
00162 return (c.in(0.0)) ? home.ES_SUBSUMED(*this) : ES_FAILED;
00163 }
00164
00165 ExecStatus es = ES_FIX;
00166 bool assigned = true;
00167
00168
00169 for (int i = x.size(); i--; ) {
00170
00171 FloatNum sl = c.max();
00172 for (int j = x.size(); j--; ) {
00173 if (i == j) continue;
00174 sl = r.sub_up(sl,x[j].min());
00175 }
00176 for (int j = y.size(); j--; )
00177 sl = r.add_up(sl,y[j].max());
00178 ModEvent me = x[i].lq(home,sl);
00179 if (me_failed(me))
00180 return ES_FAILED;
00181 if (me != ME_FLOAT_VAL)
00182 assigned = false;
00183 if (me_modified(me))
00184 es = ES_NOFIX;
00185 }
00186
00187 for (int i = y.size(); i--; ) {
00188
00189 FloatNum sl = -c.max();
00190 for (int j = x.size(); j--; )
00191 sl = r.add_down(sl,x[j].min());
00192 for (int j = y.size(); j--; ) {
00193 if (i == j) continue;
00194 sl = r.sub_down(sl,y[j].max());
00195 }
00196 ModEvent me = y[i].gq(home,sl);
00197 if (me_failed(me))
00198 return ES_FAILED;
00199 if (me != ME_FLOAT_VAL)
00200 assigned = false;
00201 if (me_modified(me))
00202 es = ES_NOFIX;
00203 }
00204
00205
00206 for (int i = x.size(); i--; ) {
00207
00208 FloatNum su = c.min();
00209 for (int j = x.size(); j--; ) {
00210 if (i == j) continue;
00211 su = r.sub_down(su,x[j].max());
00212 }
00213 for (int j = y.size(); j--; )
00214 su = r.add_down(su,y[j].min());
00215 ModEvent me = x[i].gq(home,su);
00216 if (me_failed(me))
00217 return ES_FAILED;
00218 if (me != ME_FLOAT_VAL)
00219 assigned = false;
00220 if (me_modified(me))
00221 es = ES_NOFIX;
00222 }
00223
00224 for (int i = y.size(); i--; ) {
00225
00226 FloatNum su = -c.min();
00227 for (int j = x.size(); j--; )
00228 su = r.add_up(su,x[j].max());
00229 for (int j = y.size(); j--; ) {
00230 if (i == j) continue;
00231 su = r.sub_up(su,y[j].min());
00232 }
00233 ModEvent me = y[i].lq(home,su);
00234 if (me_failed(me))
00235 return ES_FAILED;
00236 if (me != ME_FLOAT_VAL)
00237 assigned = false;
00238 if (me_modified(me))
00239 es = ES_NOFIX;
00240 }
00241
00242 return assigned ? home.ES_SUBSUMED(*this) : es;
00243 }
00244
00245
00246
00247
00248
00249
00250
00251 template<class P, class N>
00252 forceinline
00253 Lq<P,N>::Lq(Home home, ViewArray<P>& x, ViewArray<N>& y, FloatVal c)
00254 : Lin<P,N,PC_FLOAT_BND>(home,x,y,c) {}
00255
00256 template<class P, class N>
00257 ExecStatus
00258 Lq<P,N>::post(Home home, ViewArray<P>& x, ViewArray<N>& y, FloatVal c) {
00259 (void) new (home) Lq<P,N>(home,x,y,c);
00260 return ES_OK;
00261 }
00262
00263 template<class P, class N>
00264 forceinline
00265 Lq<P,N>::Lq(Space& home, Lq<P,N>& p)
00266 : Lin<P,N,PC_FLOAT_BND>(home,p) {}
00267
00268 template<class P, class N>
00269 Actor*
00270 Lq<P,N>::copy(Space& home) {
00271 return new (home) Lq<P,N>(home,*this);
00272 }
00273
00274 template<class P, class N>
00275 ExecStatus
00276 Lq<P,N>::propagate(Space& home, const ModEventDelta& med) {
00277
00278 FloatNum sl = 0.0;
00279
00280 Rounding r;
00281
00282 if (FloatView::me(med) == ME_FLOAT_VAL) {
00283 for (int i = x.size(); i--; ) {
00284 if (x[i].assigned()) {
00285 c -= x[i].val(); x.move_lst(i);
00286 } else {
00287 sl = r.sub_up(sl,x[i].min());
00288 }
00289 }
00290 for (int i = y.size(); i--; ) {
00291 if (y[i].assigned()) {
00292 c += y[i].val(); y.move_lst(i);
00293 } else {
00294 sl = r.add_up(sl,y[i].max());
00295 }
00296 }
00297 if ((x.size() + y.size()) <= 1) {
00298 if (x.size() == 1) {
00299 GECODE_ME_CHECK(x[0].lq(home,c.max()));
00300 return home.ES_SUBSUMED(*this);
00301 }
00302 if (y.size() == 1) {
00303 GECODE_ME_CHECK(y[0].gq(home,(-c).min()));
00304 return home.ES_SUBSUMED(*this);
00305 }
00306 return (c.max() >= 0) ? home.ES_SUBSUMED(*this) : ES_FAILED;
00307 }
00308 } else {
00309 for (int i = x.size(); i--; )
00310 sl = r.sub_up(sl,x[i].min());
00311 for (int i = y.size(); i--; )
00312 sl = r.add_up(sl,y[i].max());
00313 }
00314
00315 sl = r.add_up(sl,c.max());
00316
00317 ExecStatus es = ES_FIX;
00318 bool assigned = true;
00319 for (int i = x.size(); i--; ) {
00320 assert(!x[i].assigned());
00321 FloatNum slx = r.add_up(sl,x[i].min());
00322 ModEvent me = x[i].lq(home,slx);
00323 if (me == ME_FLOAT_FAILED)
00324 return ES_FAILED;
00325 if (me != ME_FLOAT_VAL)
00326 assigned = false;
00327 if (me_modified(me))
00328 es = ES_NOFIX;
00329 }
00330
00331 for (int i = y.size(); i--; ) {
00332 assert(!y[i].assigned());
00333 FloatNum sly = r.sub_up(y[i].max(),sl);
00334 ModEvent me = y[i].gq(home,sly);
00335 if (me == ME_FLOAT_FAILED)
00336 return ES_FAILED;
00337 if (me != ME_FLOAT_VAL)
00338 assigned = false;
00339 if (me_modified(me))
00340 es = ES_NOFIX;
00341 }
00342
00343 return assigned ? home.ES_SUBSUMED(*this) : es;
00344 }
00345
00346 }}}
00347
00348
00349