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