00001
00002
00003
00004
00005
00006
00007
00008
00009
00010
00011
00012
00013
00014
00015
00016
00017
00018
00019
00020
00021
00022 #include "gecode/int/linear.hh"
00023
00024 #include "gecode/iter.hh"
00025
00026 namespace Gecode { namespace Int { namespace Linear {
00027
00035 class SupportSet {
00036 private:
00038 static const unsigned int bpui = sizeof(unsigned int) * 8;
00040 unsigned int* bits;
00041 public:
00043 void init(unsigned int n);
00045 void support(unsigned int i);
00047 bool supported(unsigned int i) const;
00048
00049 private:
00051 class ResultIter : public ViewValues<IntView> {
00052 protected:
00054 const SupportSet* s;
00056 unsigned int p;
00057 public:
00059 ResultIter(const SupportSet* s0, const IntView& x);
00061 void operator++(void);
00062 };
00063
00064 public:
00066 ModEvent tell(Space* home, IntView& x) const;
00068 void dispose(void);
00069 };
00070
00075 template <class Val>
00076 class SupportIter {
00077 protected:
00079 int a;
00081 IntView x;
00083 SupportSet s;
00085 int c;
00087 unsigned int p;
00089 Val l;
00091 Val u;
00092 public:
00094 void init(int a, const IntView& x, Val l, Val u);
00096 void support(void);
00098 ModEvent tell(Space* home);
00100 void dispose(void);
00101 };
00102
00103
00108 template <class Val>
00109 class PosSupportIter : public SupportIter<Val> {
00110 private:
00112 IntVarImpFwd i;
00113
00114 using SupportIter<Val>::a;
00115 using SupportIter<Val>::x;
00116 using SupportIter<Val>::s;
00117 using SupportIter<Val>::c;
00118 using SupportIter<Val>::p;
00119 using SupportIter<Val>::l;
00120 using SupportIter<Val>::u;
00121 public:
00123 bool reset(Val& d);
00125 bool adjust(Val& d);
00126 };
00127
00128
00133 template <class Val>
00134 class NegSupportIter : public SupportIter<Val> {
00135 private:
00137 IntVarImpBwd i;
00138
00139 using SupportIter<Val>::a;
00140 using SupportIter<Val>::x;
00141 using SupportIter<Val>::s;
00142 using SupportIter<Val>::c;
00143 using SupportIter<Val>::p;
00144 using SupportIter<Val>::l;
00145 using SupportIter<Val>::u;
00146 public:
00148 bool reset(Val& d);
00150 bool adjust(Val& d);
00151 };
00152
00153
00154
00155
00156
00157
00158 forceinline void
00159 SupportSet::init(unsigned int n) {
00160 bits = Memory::bmalloc<unsigned int>((n / bpui) + 1);
00161 for (unsigned int i = (n / bpui) + 1; i--; )
00162 bits[i] = 0;
00163 }
00164 forceinline void
00165 SupportSet::support(unsigned int i) {
00166 unsigned int p = i / bpui;
00167 bits[p] |= 1 << (i-p*bpui);
00168 }
00169 forceinline bool
00170 SupportSet::supported(unsigned int i) const {
00171 unsigned int p = i / bpui;
00172 return (bits[p] & (1 << (i-p*bpui))) != 0;
00173 }
00174
00175 forceinline
00176 SupportSet::ResultIter::ResultIter(const SupportSet* s0, const IntView& x)
00177 : ViewValues<IntView>(x), s(s0), p(0) {
00178 while (ViewValues<IntView>::operator()() && !s->supported(p)) {
00179 ViewValues<IntView>::operator++(); ++p;
00180 }
00181 }
00182 forceinline void
00183 SupportSet::ResultIter::operator++(void) {
00184 do {
00185 ViewValues<IntView>::operator++(); ++p;
00186 } while (ViewValues<IntView>::operator()() && !s->supported(p));
00187 }
00188
00189
00190 inline ModEvent
00191 SupportSet::tell(Space* home, IntView& x) const {
00192 unsigned int n = x.size() / bpui;
00193
00194 for (unsigned int i=n+1; i--; )
00195 if (bits[i] != 0)
00196 goto all;
00197 return ME_INT_FAILED;
00198 all:
00199
00200 for (unsigned int i=n; i--; )
00201 if (bits[i] != ~0U)
00202 goto tell;
00203
00204 for (unsigned int i=n*bpui; i<x.size(); i++)
00205 if (!supported(i))
00206 goto tell;
00207 return ME_INT_NONE;
00208 tell:
00209 {
00210 ResultIter i(this,x);
00211 Iter::Values::ToRanges<ResultIter> r(i);
00212 return x.narrow(home,r);
00213 }
00214 }
00215
00216 forceinline void
00217 SupportSet::dispose(void) {
00218 Memory::free(bits);
00219 }
00220
00221
00222
00223
00224
00225
00226 template <class Val>
00227 forceinline void
00228 SupportIter<Val>::init(int a0, const IntView& x0, Val l0, Val u0) {
00229 a=a0; x=x0; l=l0; u=u0;
00230 s.init(x.size());
00231 }
00232 template <class Val>
00233 forceinline void
00234 SupportIter<Val>::support(void) {
00235 s.support(p);
00236 }
00237 template <class Val>
00238 forceinline ModEvent
00239 SupportIter<Val>::tell(Space* home) {
00240 return s.tell(home,x);
00241 }
00242 template <class Val>
00243 forceinline void
00244 SupportIter<Val>::dispose(void) {
00245 s.dispose();
00246 }
00247
00248
00249
00250
00251
00252
00253 template <class Val>
00254 forceinline bool
00255 PosSupportIter<Val>::reset(Val& d) {
00256
00257 if (d + static_cast<Val>(a)*x.max() < u)
00258 return false;
00259
00260 i.init(x.variable()); p = 0;
00261
00262 while (d + static_cast<Val>(a)*i.max() < u) {
00263 p += i.width(); ++i;
00264 }
00265
00266 assert(i());
00267
00268 c = i.min();
00269
00270 while (d + static_cast<Val>(a)*c < u) {
00271 p++; c++;
00272 }
00273
00274 d += static_cast<Val>(a) * c;
00275 return true;
00276 }
00277 template <class Val>
00278 forceinline bool
00279 PosSupportIter<Val>::adjust(Val& d) {
00280
00281 Val v = static_cast<Val>(a) * c;
00282
00283 d -= v;
00284
00285 p++;
00286
00287 if (c < i.max()) {
00288
00289 c += 1; v += a;
00290 } else {
00291
00292 ++i;
00293 if (!i())
00294 return false;
00295 c = i.min(); v = static_cast<Val>(a) * c;
00296 }
00297
00298 if (d + v > l)
00299 return false;
00300
00301 d += v;
00302 return true;
00303 }
00304
00305
00306
00307
00308
00309
00310 template <class Val>
00311 forceinline bool
00312 NegSupportIter<Val>::reset(Val& d) {
00313
00314 if (d + static_cast<Val>(a)*x.min() < u)
00315 return false;
00316
00317 i.init(x.variable()); p = x.size()-1;
00318
00319 while (d + static_cast<Val>(a)*i.min() < u) {
00320 p -= i.width(); ++i;
00321 }
00322
00323 assert(i());
00324
00325 c = i.max();
00326
00327 while (d + static_cast<Val>(a)*c < u) {
00328 p--; c--;
00329 }
00330
00331 d += static_cast<Val>(a) * c;
00332 return true;
00333 }
00334 template <class Val>
00335 forceinline bool
00336 NegSupportIter<Val>::adjust(Val& d) {
00337
00338 Val v = static_cast<Val>(a) * c;
00339
00340 d -= v;
00341
00342 p--;
00343
00344 if (c > i.min()) {
00345
00346 c -= 1; v -= a;
00347 } else {
00348
00349 ++i;
00350 if (!i())
00351 return false;
00352 c = i.max(); v = static_cast<Val>(a) * c;
00353 }
00354
00355 if (d + v > l)
00356 return false;
00357
00358 d += v;
00359 return true;
00360 }
00361
00362
00363
00364
00365
00366
00367
00368 template <class Val, class View>
00369 forceinline
00370 DomEq<Val,View>::DomEq(Space* home,
00371 ViewArray<View >& x, ViewArray<View >& y,
00372 Val c)
00373 : Lin<Val,View,View,PC_INT_DOM>(home,x,y,c) {}
00374
00375 template <class Val, class View>
00376 ExecStatus
00377 DomEq<Val,View>::post(Space* home,
00378 ViewArray<View>& x, ViewArray<View>& y,
00379 Val c) {
00380 (void) new (home) DomEq<Val,View>(home,x,y,c);
00381 return ES_OK;
00382 }
00383
00384 template <class Val, class View>
00385 forceinline
00386 DomEq<Val,View>::DomEq(Space* home, bool share, DomEq<Val,View>& p)
00387 : Lin<Val,View,View,PC_INT_DOM>(home,share,p) {}
00388
00389 template <class Val, class View>
00390 Actor*
00391 DomEq<Val,View>::copy(Space* home, bool share) {
00392 return new (home) DomEq<Val,View>(home,share,*this);
00393 }
00394
00395 template <class Val, class View>
00396 PropCost
00397 DomEq<Val,View>::cost(void) const {
00398 return (View::pme(this) != ME_INT_DOM)
00399 ? cost_hi(x.size()+y.size(),PC_LINEAR_LO)
00400 : cost_hi(x.size()+y.size(),PC_CRAZY_HI);
00401 }
00402
00403 template <class Val, class View>
00404 ExecStatus
00405 DomEq<Val,View>::propagate(Space* home) {
00406 if (View::pme(this) != ME_INT_DOM) {
00407 ExecStatus es = prop_bnd<Val,View,View>(this,home,x,y,c);
00408 if ((es == ES_SUBSUMED) || (es == ES_FAILED))
00409 return es;
00410 return ES_FIX_PARTIAL(View::pme(ME_INT_DOM));
00411 }
00412
00413
00414 Val d = -c;
00415
00416 int n = x.size();
00417 int m = y.size();
00418
00419
00420 GECODE_AUTOARRAY(PosSupportIter<Val>, xp, n);
00421 GECODE_AUTOARRAY(NegSupportIter<Val>, yp, m);
00422
00423
00424 {
00425 Val l = 0;
00426 Val u = 0;
00427 for (int j=m; j--; ) {
00428 yp[j].init(-y[j].scale(),y[j].base(),l,u);
00429 l += y[j].max(); u += y[j].min();
00430 }
00431 for (int i=n; i--; ) {
00432 xp[i].init(x[i].scale(),x[i].base(),l,u);
00433 l -= x[i].min(); u -= x[i].max();
00434 }
00435 }
00436
00437
00438 {
00439
00440 int i = 0;
00441 int j = 0;
00442
00443 next_i:
00444
00445 while (i<n) {
00446 if (!xp[i].reset(d)) goto prev_i;
00447 i++;
00448 }
00449 next_j:
00450
00451 while (j<m) {
00452 if (!yp[j].reset(d)) goto prev_j;
00453 j++;
00454 }
00455
00456 if (d == 0) {
00457
00458 for (int is=n; is--; ) xp[is].support();
00459 for (int js=m; js--; ) yp[js].support();
00460 }
00461 prev_j:
00462
00463 while (j>0) {
00464 if (yp[j-1].adjust(d)) goto next_j;
00465 j--;
00466 }
00467 prev_i:
00468
00469 while (i>0) {
00470 if (xp[i-1].adjust(d)) goto next_i;
00471 i--;
00472 }
00473 }
00474
00475
00476 ExecStatus es = ES_SUBSUMED;
00477 for (int i=n; i--; ) {
00478 ModEvent me = xp[i].tell(home);
00479 if (me_failed(me)) {
00480 es = ES_FAILED; goto dispose;
00481 }
00482 if (!x[i].assigned())
00483 es = ES_FIX;
00484 }
00485 for (int j=m; j--; ) {
00486 ModEvent me = yp[j].tell(home);
00487 if (me_failed(me)) {
00488 es = ES_FAILED; goto dispose;
00489 }
00490 if (!y[j].assigned())
00491 es = ES_FIX;
00492 }
00493
00494
00495 dispose:
00496 for (int i=n; i--; ) xp[i].dispose();
00497 for (int j=m; j--; ) yp[j].dispose();
00498 return es;
00499 }
00500
00501 }}}
00502
00503