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