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 Count {
00039
00040
00041
00042
00043
00044
00045 template<class VX, class VY>
00046 forceinline
00047 BaseInt<VX,VY>::BaseInt(Home home,
00048 ViewArray<VX>& x0, int n_s0, VY y0, int c0)
00049 : Propagator(home), x(x0), n_s(n_s0), y(y0), c(c0) {
00050 for (int i=n_s; i--; )
00051 x[i].subscribe(home,*this,PC_INT_DOM);
00052 y.subscribe(home,*this,PC_INT_DOM);
00053 }
00054
00055 template<class VX, class VY>
00056 forceinline size_t
00057 BaseInt<VX,VY>::dispose(Space& home) {
00058 for (int i=n_s; i--; )
00059 x[i].cancel(home,*this,PC_INT_DOM);
00060 y.cancel(home,*this,PC_INT_DOM);
00061 (void) Propagator::dispose(home);
00062 return sizeof(*this);
00063 }
00064
00065 template<class VX, class VY>
00066 forceinline
00067 BaseInt<VX,VY>::BaseInt(Space& home, bool share, BaseInt<VX,VY>& p)
00068 : Propagator(home,share,p), n_s(p.n_s), c(p.c) {
00069 x.update(home,share,p.x);
00070 y.update(home,share,p.y);
00071 }
00072
00073 template<class VX, class VY>
00074 PropCost
00075 BaseInt<VX,VY>::cost(const Space&, const ModEventDelta&) const {
00076 return PropCost::linear(PropCost::LO,x.size());
00077 }
00078
00079
00080
00081
00082
00083 template<class VX, class VY>
00084 forceinline
00085 EqInt<VX,VY>::EqInt(Home home, ViewArray<VX>& x, int n_s, VY y, int c)
00086 : BaseInt<VX,VY>(home,x,n_s,y,c) {}
00087
00088 template<class VX, class VY>
00089 ExecStatus
00090 EqInt<VX,VY>::post(Home home, ViewArray<VX>& x, VY y, int c) {
00091
00092 int n_x = x.size();
00093 for (int i=n_x; i--; )
00094 switch (holds(x[i],y)) {
00095 case RT_FALSE:
00096 x[i] = x[--n_x]; break;
00097 case RT_TRUE:
00098 x[i] = x[--n_x]; c--; break;
00099 case RT_MAYBE:
00100 break;
00101 default:
00102 GECODE_NEVER;
00103 }
00104 x.size(n_x);
00105
00106 if ((c < 0) || (c > n_x))
00107 return ES_FAILED;
00108
00109 if (c == 0)
00110 return post_false(home,x,y) ? ES_FAILED : ES_OK;
00111
00112 if (c == n_x)
00113 return post_true(home,x,y) ? ES_FAILED : ES_OK;
00114
00115 int n_s = std::max(c,n_x-c)+1;
00116 assert(n_s <= n_x);
00117 (void) new (home) EqInt<VX,VY>(home,x,n_s,y,c);
00118 return ES_OK;
00119 }
00120
00121 template<class VX, class VY>
00122 forceinline
00123 EqInt<VX,VY>::EqInt(Space& home, bool share, EqInt<VX,VY>& p)
00124 : BaseInt<VX,VY>(home,share,p) {}
00125
00126 template<class VX, class VY>
00127 Actor*
00128 EqInt<VX,VY>::copy(Space& home, bool share) {
00129 return new (home) EqInt<VX,VY>(home,share,*this);
00130 }
00131
00132 template<class VX, class VY>
00133 ExecStatus
00134 EqInt<VX,VY>::propagate(Space& home, const ModEventDelta&) {
00135
00136 int n_x = x.size();
00137 for (int i=n_s; i--; )
00138 switch (holds(x[i],y)) {
00139 case RT_FALSE:
00140 x[i].cancel(home,*this,PC_INT_DOM);
00141 x[i]=x[--n_s]; x[n_s]=x[--n_x];
00142 break;
00143 case RT_TRUE:
00144 x[i].cancel(home,*this,PC_INT_DOM);
00145 x[i]=x[--n_s]; x[n_s]=x[--n_x]; c--;
00146 break;
00147 case RT_MAYBE:
00148 break;
00149 default:
00150 GECODE_NEVER;
00151 }
00152 x.size(n_x);
00153 if ((c < 0) || (c > n_x))
00154 return ES_FAILED;
00155
00156 for (int i=n_x; i-- > n_s; )
00157 switch (holds(x[i],y)) {
00158 case RT_FALSE: x[i]=x[--n_x]; break;
00159 case RT_TRUE: x[i]=x[--n_x]; c--; break;
00160 case RT_MAYBE: break;
00161 default: GECODE_NEVER;
00162 }
00163 x.size(n_x);
00164 if ((c < 0) || (c > n_x))
00165 return ES_FAILED;
00166 if (c == 0)
00167
00168 return post_false(home,x,y) ? ES_FAILED : home.ES_SUBSUMED(*this);
00169 if (c == n_x)
00170
00171 return post_true(home,x,y) ? ES_FAILED : home.ES_SUBSUMED(*this);
00172 int m = std::max(c,n_x-c)+1;
00173 assert(m <= n_x);
00174
00175 while (n_s < m)
00176 x[n_s++].subscribe(home,*this,PC_INT_DOM,false);
00177 return ES_FIX;
00178 }
00179
00180
00181
00182
00183
00184 template<class VX, class VY>
00185 forceinline
00186 GqInt<VX,VY>::GqInt(Home home, ViewArray<VX>& x, int n_s, VY y, int c)
00187 : BaseInt<VX,VY>(home,x,n_s,y,c) {}
00188
00189 template<class VX, class VY>
00190 ExecStatus
00191 GqInt<VX,VY>::post(Home home, ViewArray<VX>& x, VY y, int c) {
00192
00193 int n_x = x.size();
00194 for (int i=n_x; i--; )
00195 switch (holds(x[i],y)) {
00196 case RT_FALSE:
00197 x[i] = x[--n_x]; break;
00198 case RT_TRUE:
00199 x[i] = x[--n_x]; c--; break;
00200 case RT_MAYBE:
00201 break;
00202 default:
00203 GECODE_NEVER;
00204 }
00205 x.size(n_x);
00206
00207 if (n_x < c)
00208 return ES_FAILED;
00209
00210 if (c <= 0)
00211 return ES_OK;
00212
00213 if (c == n_x)
00214 return post_true(home,x,y) ? ES_FAILED : ES_OK;
00215 (void) new (home) GqInt<VX,VY>(home,x,c+1,y,c);
00216 return ES_OK;
00217 }
00218
00219 template<class VX, class VY>
00220 forceinline
00221 GqInt<VX,VY>::GqInt(Space& home, bool share, GqInt<VX,VY>& p)
00222 : BaseInt<VX,VY>(home,share,p) {}
00223
00224 template<class VX, class VY>
00225 Actor*
00226 GqInt<VX,VY>::copy(Space& home, bool share) {
00227 return new (home) GqInt<VX,VY>(home,share,*this);
00228 }
00229
00230 template<class VX, class VY>
00231 ExecStatus
00232 GqInt<VX,VY>::propagate(Space& home, const ModEventDelta&) {
00233
00234 int n_x = x.size();
00235 for (int i=n_s; i--; )
00236 switch (holds(x[i],y)) {
00237 case RT_FALSE:
00238 x[i].cancel(home,*this,PC_INT_DOM);
00239 x[i]=x[--n_s]; x[n_s]=x[--n_x];
00240 break;
00241 case RT_TRUE:
00242 x[i].cancel(home,*this,PC_INT_DOM);
00243 x[i]=x[--n_s]; x[n_s]=x[--n_x]; c--;
00244 break;
00245 case RT_MAYBE:
00246 break;
00247 default:
00248 GECODE_NEVER;
00249 }
00250 x.size(n_x);
00251 if (n_x < c)
00252 return ES_FAILED;
00253 if (c <= 0)
00254 return home.ES_SUBSUMED(*this);
00255
00256 for (int i=n_x; i-- > n_s; )
00257 switch (holds(x[i],y)) {
00258 case RT_FALSE: x[i]=x[--n_x]; break;
00259 case RT_TRUE: x[i]=x[--n_x]; c--; break;
00260 case RT_MAYBE: break;
00261 default: GECODE_NEVER;
00262 }
00263 x.size(n_x);
00264 if (n_x < c)
00265 return ES_FAILED;
00266 if (c <= 0)
00267 return home.ES_SUBSUMED(*this);
00268 if (c == n_x)
00269
00270 return post_true(home,x,y) ? ES_FAILED : home.ES_SUBSUMED(*this);
00271
00272 while (n_s <= c)
00273 x[n_s++].subscribe(home,*this,PC_INT_DOM,false);
00274 return ES_FIX;
00275 }
00276
00277
00278
00279
00280
00281 template<class VX, class VY>
00282 forceinline
00283 LqInt<VX,VY>::LqInt(Home home, ViewArray<VX>& x, int n_s, VY y, int c)
00284 : BaseInt<VX,VY>(home,x,n_s,y,c) {}
00285
00286 template<class VX, class VY>
00287 ExecStatus
00288 LqInt<VX,VY>::post(Home home, ViewArray<VX>& x, VY y, int c) {
00289
00290 int n_x = x.size();
00291 for (int i=n_x; i--; )
00292 switch (holds(x[i],y)) {
00293 case RT_FALSE:
00294 x[i] = x[--n_x]; break;
00295 case RT_TRUE:
00296 x[i] = x[--n_x]; c--; break;
00297 case RT_MAYBE:
00298 break;
00299 default:
00300 GECODE_NEVER;
00301 }
00302 x.size(n_x);
00303 if (c < 0)
00304 return ES_FAILED;
00305 if (c >= n_x)
00306 return ES_OK;
00307
00308 if (c == 0)
00309 return post_false(home,x,y) ? ES_FAILED : ES_OK;
00310 (void) new (home) LqInt<VX,VY>(home,x,n_x-c+1,y,c);
00311 return ES_OK;
00312 }
00313
00314 template<class VX, class VY>
00315 forceinline
00316 LqInt<VX,VY>::LqInt(Space& home, bool share, LqInt<VX,VY>& p)
00317 : BaseInt<VX,VY>(home,share,p) {}
00318
00319 template<class VX, class VY>
00320 Actor*
00321 LqInt<VX,VY>::copy(Space& home, bool share) {
00322 return new (home) LqInt<VX,VY>(home,share,*this);
00323 }
00324
00325 template<class VX, class VY>
00326 ExecStatus
00327 LqInt<VX,VY>::propagate(Space& home, const ModEventDelta&) {
00328
00329 int n_x = x.size();
00330 for (int i=n_s; i--; )
00331 switch (holds(x[i],y)) {
00332 case RT_FALSE:
00333 x[i].cancel(home,*this,PC_INT_DOM);
00334 x[i]=x[--n_s]; x[n_s]=x[--n_x];
00335 break;
00336 case RT_TRUE:
00337 x[i].cancel(home,*this,PC_INT_DOM);
00338 x[i]=x[--n_s]; x[n_s]=x[--n_x]; c--;
00339 break;
00340 case RT_MAYBE:
00341 break;
00342 default:
00343 GECODE_NEVER;
00344 }
00345 x.size(n_x);
00346 if (c < 0)
00347 return ES_FAILED;
00348 if (c >= n_x)
00349 return home.ES_SUBSUMED(*this);
00350
00351 for (int i=n_x; i-- > n_s; )
00352 switch (holds(x[i],y)) {
00353 case RT_FALSE: x[i]=x[--n_x]; break;
00354 case RT_TRUE: x[i]=x[--n_x]; c--; break;
00355 case RT_MAYBE: break;
00356 default: GECODE_NEVER;
00357 }
00358 x.size(n_x);
00359 if (c < 0)
00360 return ES_FAILED;
00361 if (c >= n_x)
00362 return home.ES_SUBSUMED(*this);
00363 if (c == 0)
00364
00365 return post_false(home,x,y) ? ES_FAILED : home.ES_SUBSUMED(*this);
00366
00367 int m = n_x-c;
00368 while (n_s <= m)
00369 x[n_s++].subscribe(home,*this,PC_INT_DOM,false);
00370 return ES_FIX;
00371 }
00372
00373
00374
00375
00376
00377 template<class VX, class VY>
00378 forceinline
00379 NqInt<VX,VY>::NqInt(Home home, ViewArray<VX>& x0, VY y0, int c0)
00380 : BinaryPropagator<VX,PC_INT_DOM>(home,
00381 x0[x0.size()-2],
00382 x0[x0.size()-1]), x(x0), y(y0), c(c0) {
00383 assert(x.size() >= 2);
00384 x.size(x.size()-2);
00385 y.subscribe(home,*this,PC_INT_DOM);
00386 }
00387
00388 template<class VX, class VY>
00389 forceinline size_t
00390 NqInt<VX,VY>::dispose(Space& home) {
00391 y.cancel(home,*this,PC_INT_DOM);
00392 (void) BinaryPropagator<VX,PC_INT_DOM>::dispose(home);
00393 return sizeof(*this);
00394 }
00395
00396 template<class VX, class VY>
00397 forceinline
00398 NqInt<VX,VY>::NqInt(Space& home, bool share, NqInt<VX,VY>& p)
00399 : BinaryPropagator<VX,PC_INT_DOM>(home,share,p), c(p.c) {
00400 x.update(home,share,p.x);
00401 y.update(home,share,p.y);
00402 }
00403
00404 template<class VX, class VY>
00405 forceinline ExecStatus
00406 NqInt<VX,VY>::post(Home home, ViewArray<VX>& x, VY y, int c) {
00407 int n = x.size();
00408 for (int i=n; i--; )
00409 switch (holds(x[i],y)) {
00410 case RT_FALSE: x[i]=x[--n]; break;
00411 case RT_TRUE: x[i]=x[--n]; c--; break;
00412 case RT_MAYBE: break;
00413 default: GECODE_NEVER;
00414 }
00415 x.size(n);
00416 if ((n < c) || (c < 0))
00417 return ES_OK;
00418 if (n == 0)
00419 return (c == 0) ? ES_FAILED : ES_OK;
00420 if (n == 1) {
00421 if (c == 1)
00422 return post_false(home,x[0],y) ? ES_FAILED : ES_OK;
00423 else
00424 return post_true(home,x[0],y) ? ES_FAILED : ES_OK;
00425 }
00426 (void) new (home) NqInt(home,x,y,c);
00427 return ES_OK;
00428 }
00429
00430 template<class VX, class VY>
00431 Actor*
00432 NqInt<VX,VY>::copy(Space& home, bool share) {
00433 return new (home) NqInt<VX,VY>(home,share,*this);
00434 }
00435
00436 template<class VX, class VY>
00437 PropCost
00438 NqInt<VX,VY>::cost(const Space&, const ModEventDelta&) const {
00439 return PropCost::linear(PropCost::LO,x.size());
00440 }
00441
00442 template<class VX, class VY>
00443 forceinline bool
00444 NqInt<VX,VY>::resubscribe(Space& home, VX& z) {
00445 switch (holds(z,y)) {
00446 case RT_FALSE: break;
00447 case RT_TRUE: c--; break;
00448 case RT_MAYBE: return true;
00449 default: GECODE_NEVER;
00450 }
00451 int n = x.size();
00452 for (int i=n; i--; )
00453 switch (holds(x[i],y)) {
00454 case RT_FALSE:
00455 x[i]=x[--n];
00456 break;
00457 case RT_TRUE:
00458 x[i]=x[--n]; c--;
00459 break;
00460 case RT_MAYBE:
00461
00462 z.cancel(home,*this,PC_INT_DOM);
00463 z=x[i]; x[i]=x[--n];
00464 x.size(n);
00465 z.subscribe(home,*this,PC_INT_DOM,false);
00466 return true;
00467 default:
00468 GECODE_NEVER;
00469 }
00470
00471 x.size(0);
00472 return false;
00473 }
00474
00475 template<class VX, class VY>
00476 ExecStatus
00477 NqInt<VX,VY>::propagate(Space& home, const ModEventDelta&) {
00478 bool s0 = resubscribe(home,x0);
00479 bool s1 = resubscribe(home,x1);
00480 int n = x.size() + s0 + s1;
00481 if ((n < c) || (c < 0))
00482 return home.ES_SUBSUMED(*this);
00483 if (n == 0)
00484 return (c == 0) ? ES_FAILED : home.ES_SUBSUMED(*this);
00485 if (n == 1) {
00486 if (s0)
00487 if (c == 1)
00488 return post_false(home,x0,y) ? ES_FAILED : home.ES_SUBSUMED(*this);
00489 else
00490 return post_true(home,x0,y) ? ES_FAILED : home.ES_SUBSUMED(*this);
00491 else
00492 if (c == 1)
00493 return post_false(home,x1,y) ? ES_FAILED : home.ES_SUBSUMED(*this);
00494 else
00495 return post_true(home,x1,y) ? ES_FAILED : home.ES_SUBSUMED(*this);
00496 }
00497 return ES_FIX;
00498 }
00499
00500 }}}
00501
00502
00503