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 namespace Gecode { namespace Int { namespace Linear {
00035
00043 class SupportSet {
00044 private:
00046 Support::BitSetBase bs;
00047 public:
00049 SupportSet(void);
00051 void init(Region& r, unsigned int n);
00053 void support(unsigned int i);
00055 bool supported(unsigned int i) const;
00056
00057 private:
00059 class ResultIter : public ViewValues<IntView> {
00060 protected:
00062 const SupportSet& s;
00064 unsigned int p;
00065 public:
00067 ResultIter(const SupportSet& s0, const IntView& x);
00069 void operator ++(void);
00070 };
00071
00072 public:
00074 ModEvent tell(Space& home, IntView& x) const;
00075 };
00076
00081 template<class Val>
00082 class SupportIter {
00083 protected:
00085 int a;
00087 IntView x;
00089 SupportSet s;
00091 int c;
00093 unsigned int p;
00095 Val l;
00097 Val u;
00098 public:
00100 void init(Region& r, int a, const IntView& x, Val l, Val u);
00102 void support(void);
00104 ModEvent tell(Space& home);
00105 };
00106
00107
00112 template<class Val>
00113 class PosSupportIter : public SupportIter<Val> {
00114 private:
00116 IntVarImpFwd i;
00117
00118 using SupportIter<Val>::a;
00119 using SupportIter<Val>::x;
00120 using SupportIter<Val>::s;
00121 using SupportIter<Val>::c;
00122 using SupportIter<Val>::p;
00123 using SupportIter<Val>::l;
00124 using SupportIter<Val>::u;
00125 public:
00127 bool reset(Val& d);
00129 bool adjust(Val& d);
00130 };
00131
00132
00137 template<class Val>
00138 class NegSupportIter : public SupportIter<Val> {
00139 private:
00141 IntVarImpBwd i;
00142
00143 using SupportIter<Val>::a;
00144 using SupportIter<Val>::x;
00145 using SupportIter<Val>::s;
00146 using SupportIter<Val>::c;
00147 using SupportIter<Val>::p;
00148 using SupportIter<Val>::l;
00149 using SupportIter<Val>::u;
00150 public:
00152 bool reset(Val& d);
00154 bool adjust(Val& d);
00155 };
00156
00157
00158
00159
00160
00161
00162 forceinline
00163 SupportSet::SupportSet(void) {}
00164 forceinline void
00165 SupportSet::init(Region& r, unsigned int n) {
00166 bs.init(r,n);
00167 }
00168 forceinline void
00169 SupportSet::support(unsigned int i) {
00170 bs.set(i);
00171 }
00172 forceinline bool
00173 SupportSet::supported(unsigned int i) const {
00174 return bs.get(i);
00175 }
00176
00177 forceinline
00178 SupportSet::ResultIter::ResultIter(const SupportSet& s0, const IntView& x)
00179 : ViewValues<IntView>(x), s(s0), p(0) {
00180 while (ViewValues<IntView>::operator ()() && s.supported(p)) {
00181 ViewValues<IntView>::operator ++(); ++p;
00182 }
00183 }
00184 forceinline void
00185 SupportSet::ResultIter::operator ++(void) {
00186 do {
00187 ViewValues<IntView>::operator ++(); ++p;
00188 } while (ViewValues<IntView>::operator ()() && s.supported(p));
00189 }
00190
00191
00192 forceinline ModEvent
00193 SupportSet::tell(Space& home, IntView& x) const {
00194 switch (bs.status()) {
00195 case Support::BSS_NONE:
00196 return ME_INT_FAILED;
00197 case Support::BSS_ALL:
00198 return ME_INT_NONE;
00199 case Support::BSS_SOME:
00200 {
00201 ResultIter i(*this,x);
00202 return x.minus_v(home,i);
00203 }
00204 default:
00205 GECODE_NEVER;
00206 }
00207 return ME_INT_NONE;
00208 }
00209
00210
00211
00212
00213
00214
00215 template<class Val>
00216 forceinline void
00217 SupportIter<Val>::init(Region& r,
00218 int a0, const IntView& x0, Val l0, Val u0) {
00219 a=a0; x=x0; l=l0; u=u0;
00220 s.init(r,x.size());
00221 }
00222 template<class Val>
00223 forceinline void
00224 SupportIter<Val>::support(void) {
00225 s.support(p);
00226 }
00227 template<class Val>
00228 forceinline ModEvent
00229 SupportIter<Val>::tell(Space& home) {
00230 return s.tell(home,x);
00231 }
00232
00233
00234
00235
00236
00237
00238 template<class Val>
00239 forceinline bool
00240 PosSupportIter<Val>::reset(Val& d) {
00241
00242 if (d + static_cast<Val>(a)*x.max() < u)
00243 return false;
00244
00245 i.init(x.varimp()); p = 0;
00246
00247 while (d + static_cast<Val>(a)*i.max() < u) {
00248 p += i.width(); ++i;
00249 }
00250
00251 assert(i());
00252
00253 c = i.min();
00254
00255 while (d + static_cast<Val>(a)*c < u) {
00256 p++; c++;
00257 }
00258
00259 d += static_cast<Val>(a) * c;
00260 return true;
00261 }
00262 template<class Val>
00263 forceinline bool
00264 PosSupportIter<Val>::adjust(Val& d) {
00265
00266 Val v = static_cast<Val>(a) * c;
00267
00268 d -= v;
00269
00270 p++;
00271
00272 if (c < i.max()) {
00273
00274 c += 1; v += a;
00275 } else {
00276
00277 ++i;
00278 if (!i())
00279 return false;
00280 c = i.min(); v = static_cast<Val>(a) * c;
00281 }
00282
00283 if (d + v > l)
00284 return false;
00285
00286 d += v;
00287 return true;
00288 }
00289
00290
00291
00292
00293
00294
00295 template<class Val>
00296 forceinline bool
00297 NegSupportIter<Val>::reset(Val& d) {
00298
00299 if (d + static_cast<Val>(a)*x.min() < u)
00300 return false;
00301
00302 i.init(x.varimp()); p = x.size()-1;
00303
00304 while (d + static_cast<Val>(a)*i.min() < u) {
00305 p -= i.width(); ++i;
00306 }
00307
00308 assert(i());
00309
00310 c = i.max();
00311
00312 while (d + static_cast<Val>(a)*c < u) {
00313 p--; c--;
00314 }
00315
00316 d += static_cast<Val>(a) * c;
00317 return true;
00318 }
00319 template<class Val>
00320 forceinline bool
00321 NegSupportIter<Val>::adjust(Val& d) {
00322
00323 Val v = static_cast<Val>(a) * c;
00324
00325 d -= v;
00326
00327 p--;
00328
00329 if (c > i.min()) {
00330
00331 c -= 1; v -= a;
00332 } else {
00333
00334 ++i;
00335 if (!i())
00336 return false;
00337 c = i.max(); v = static_cast<Val>(a) * c;
00338 }
00339
00340 if (d + v > l)
00341 return false;
00342
00343 d += v;
00344 return true;
00345 }
00346
00347
00348
00349
00350
00351
00352
00353 template<class Val, class View>
00354 forceinline
00355 DomEq<Val,View>::DomEq(Home home,
00356 ViewArray<View >& x, ViewArray<View >& y,
00357 Val c)
00358 : Lin<Val,View,View,PC_INT_DOM>(home,x,y,c) {}
00359
00360 template<class Val, class View>
00361 ExecStatus
00362 DomEq<Val,View>::post(Home home,
00363 ViewArray<View>& x, ViewArray<View>& y,
00364 Val c) {
00365 (void) new (home) DomEq<Val,View>(home,x,y,c);
00366 return ES_OK;
00367 }
00368
00369 template<class Val, class View>
00370 forceinline
00371 DomEq<Val,View>::DomEq(Space& home, DomEq<Val,View>& p)
00372 : Lin<Val,View,View,PC_INT_DOM>(home,p) {}
00373
00374 template<class Val, class View>
00375 Actor*
00376 DomEq<Val,View>::copy(Space& home) {
00377 return new (home) DomEq<Val,View>(home,*this);
00378 }
00379
00380 template<class Val, class View>
00381 PropCost
00382 DomEq<Val,View>::cost(const Space&, const ModEventDelta& med) const {
00383 if (View::me(med) != ME_INT_DOM)
00384 return PropCost::linear(PropCost::LO, x.size()+y.size());
00385 else
00386 return PropCost::crazy(PropCost::HI, x.size()+y.size());
00387 }
00388
00389 template<class Val, class View>
00390 ExecStatus
00391 DomEq<Val,View>::propagate(Space& home, const ModEventDelta& med) {
00392 if (View::me(med) != ME_INT_DOM) {
00393 ExecStatus es = prop_bnd<Val,View,View>(home,med,*this,x,y,c);
00394 GECODE_ES_CHECK(es);
00395 return home.ES_FIX_PARTIAL(*this,View::med(ME_INT_DOM));
00396 }
00397
00398
00399 Val d = -c;
00400
00401 int n = x.size();
00402 int m = y.size();
00403
00404 Region r;
00405
00406 PosSupportIter<Val>* xp = r.alloc<PosSupportIter<Val> >(n);
00407 NegSupportIter<Val>* yp = r.alloc<NegSupportIter<Val> >(m);
00408
00409
00410 {
00411 Val l = 0;
00412 Val u = 0;
00413 for (int j=m; j--; ) {
00414 yp[j].init(r,-y[j].scale(),y[j].base(),l,u);
00415 l += y[j].max(); u += y[j].min();
00416 }
00417 for (int i=n; i--; ) {
00418 xp[i].init(r,x[i].scale(),x[i].base(),l,u);
00419 l -= x[i].min(); u -= x[i].max();
00420 }
00421 }
00422
00423
00424 {
00425
00426 int i = 0;
00427 int j = 0;
00428
00429 next_i:
00430
00431 while (i<n) {
00432 if (!xp[i].reset(d)) goto prev_i;
00433 i++;
00434 }
00435 next_j:
00436
00437 while (j<m) {
00438 if (!yp[j].reset(d)) goto prev_j;
00439 j++;
00440 }
00441
00442 if (d == 0) {
00443
00444 for (int is=n; is--; ) xp[is].support();
00445 for (int js=m; js--; ) yp[js].support();
00446 }
00447 prev_j:
00448
00449 while (j>0) {
00450 if (yp[j-1].adjust(d)) goto next_j;
00451 j--;
00452 }
00453 prev_i:
00454
00455 while (i>0) {
00456 if (xp[i-1].adjust(d)) goto next_i;
00457 i--;
00458 }
00459 }
00460
00461
00462 bool assigned = true;
00463 for (int i=n; i--; ) {
00464 GECODE_ME_CHECK(xp[i].tell(home));
00465 if (!x[i].assigned())
00466 assigned = false;
00467 }
00468 for (int j=m; j--; ) {
00469 GECODE_ME_CHECK(yp[j].tell(home));
00470 if (!y[j].assigned())
00471 assigned = false;
00472 }
00473 if (assigned)
00474 return home.ES_SUBSUMED(*this);
00475 return ES_FIX;
00476 }
00477
00478 }}}
00479
00480