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(Space* 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(ModEventDelta) const {
00076 return cost_lo(x.size(),PC_LINEAR_LO);
00077 }
00078
00079 template <class VX, class VY>
00080 Reflection::ActorSpec
00081 BaseInt<VX,VY>::spec(const Space* home, Reflection::VarMap& m,
00082 const Support::Symbol& ati) const {
00083 Reflection::ActorSpec s(ati);
00084 return s << x.spec(home, m)
00085 << n_s
00086 << y.spec(home, m)
00087 << c;
00088 }
00089
00090
00091
00092
00093
00094 template <class VX, class VY>
00095 forceinline
00096 EqInt<VX,VY>::EqInt(Space* home, ViewArray<VX>& x, int n_s, VY y, int c)
00097 : BaseInt<VX,VY>(home,x,n_s,y,c) {}
00098
00099 template <class VX, class VY>
00100 ExecStatus
00101 EqInt<VX,VY>::post(Space* home, ViewArray<VX>& x, VY y, int c) {
00102
00103 int n_x = x.size();
00104 for (int i=n_x; i--; )
00105 switch (holds(x[i],y)) {
00106 case RT_FALSE:
00107 x[i] = x[--n_x]; break;
00108 case RT_TRUE:
00109 x[i] = x[--n_x]; c--; break;
00110 case RT_MAYBE:
00111 break;
00112 default:
00113 GECODE_NEVER;
00114 }
00115 x.size(n_x);
00116
00117 if ((c < 0) || (c > n_x))
00118 return ES_FAILED;
00119
00120 if (c == 0)
00121 return post_false(home,x,y) ? ES_FAILED : ES_OK;
00122
00123 if (c == n_x)
00124 return post_true(home,x,y) ? ES_FAILED : ES_OK;
00125
00126 int n_s = std::max(c,n_x-c)+1;
00127 assert(n_s <= n_x);
00128 (void) new (home) EqInt<VX,VY>(home,x,n_s,y,c);
00129 return ES_OK;
00130 }
00131
00132 template <class VX, class VY>
00133 forceinline
00134 EqInt<VX,VY>::EqInt(Space* home, bool share, EqInt<VX,VY>& p)
00135 : BaseInt<VX,VY>(home,share,p) {}
00136
00137 template <class VX, class VY>
00138 Actor*
00139 EqInt<VX,VY>::copy(Space* home, bool share) {
00140 return new (home) EqInt<VX,VY>(home,share,*this);
00141 }
00142
00143 template <class VX, class VY>
00144 Support::Symbol
00145 EqInt<VX,VY>::ati(void) {
00146 return Reflection::mangle<VX,VY>("Gecode::Int::Count::EqInt");
00147 }
00148
00149 template <class VX, class VY>
00150 Reflection::ActorSpec
00151 EqInt<VX,VY>::spec(const Space* home, Reflection::VarMap& m) const {
00152 return BaseInt<VX,VY>::spec(home, m, ati());
00153 }
00154
00155 template <class VX, class VY>
00156 void
00157 EqInt<VX,VY>::post(Space* home, Reflection::VarMap& vars,
00158 const Reflection::ActorSpec& spec) {
00159 spec.checkArity(4);
00160 ViewArray<VX> x(home, vars, spec[0]);
00161 int n_s = spec[1]->toInt();
00162 VY y(home, vars, spec[2]);
00163 int c = spec[3]->toInt();
00164 (void) new (home) EqInt(home, x, n_s, y, c);
00165 }
00166
00167 template <class VX, class VY>
00168 ExecStatus
00169 EqInt<VX,VY>::propagate(Space* home, ModEventDelta) {
00170
00171 int n_x = x.size();
00172 for (int i=n_s; i--; )
00173 switch (holds(x[i],y)) {
00174 case RT_FALSE:
00175 x[i].cancel(home,this,PC_INT_DOM);
00176 x[i]=x[--n_s]; x[n_s]=x[--n_x];
00177 break;
00178 case RT_TRUE:
00179 x[i].cancel(home,this,PC_INT_DOM);
00180 x[i]=x[--n_s]; x[n_s]=x[--n_x]; c--;
00181 break;
00182 case RT_MAYBE:
00183 break;
00184 default:
00185 GECODE_NEVER;
00186 }
00187 x.size(n_x);
00188 if ((c < 0) || (c > n_x))
00189 return ES_FAILED;
00190
00191 for (int i=n_x; i-- > n_s; )
00192 switch (holds(x[i],y)) {
00193 case RT_FALSE: x[i]=x[--n_x]; break;
00194 case RT_TRUE: x[i]=x[--n_x]; c--; break;
00195 case RT_MAYBE: break;
00196 default: GECODE_NEVER;
00197 }
00198 x.size(n_x);
00199 if ((c < 0) || (c > n_x))
00200 return ES_FAILED;
00201 if (c == 0)
00202
00203 return post_false(home,x,y) ? ES_FAILED : ES_SUBSUMED(this,home);
00204 if (c == n_x)
00205
00206 return post_true(home,x,y) ? ES_FAILED : ES_SUBSUMED(this,home);
00207 int m = std::max(c,n_x-c)+1;
00208 assert(m <= n_x);
00209
00210 while (n_s < m)
00211 x[n_s++].subscribe(home,this,PC_INT_DOM,false);
00212 return ES_FIX;
00213 }
00214
00215
00216
00217
00218
00219 template <class VX, class VY>
00220 forceinline
00221 GqInt<VX,VY>::GqInt(Space* home, ViewArray<VX>& x, int n_s, VY y, int c)
00222 : BaseInt<VX,VY>(home,x,n_s,y,c) {}
00223
00224 template <class VX, class VY>
00225 ExecStatus
00226 GqInt<VX,VY>::post(Space* home, ViewArray<VX>& x, VY y, int c) {
00227
00228 int n_x = x.size();
00229 for (int i=n_x; i--; )
00230 switch (holds(x[i],y)) {
00231 case RT_FALSE:
00232 x[i] = x[--n_x]; break;
00233 case RT_TRUE:
00234 x[i] = x[--n_x]; c--; break;
00235 case RT_MAYBE:
00236 break;
00237 default:
00238 GECODE_NEVER;
00239 }
00240 x.size(n_x);
00241
00242 if (n_x < c)
00243 return ES_FAILED;
00244
00245 if (c <= 0)
00246 return ES_OK;
00247
00248 if (c == n_x)
00249 return post_true(home,x,y) ? ES_FAILED : ES_OK;
00250 (void) new (home) GqInt<VX,VY>(home,x,c+1,y,c);
00251 return ES_OK;
00252 }
00253
00254 template <class VX, class VY>
00255 forceinline
00256 GqInt<VX,VY>::GqInt(Space* home, bool share, GqInt<VX,VY>& p)
00257 : BaseInt<VX,VY>(home,share,p) {}
00258
00259 template <class VX, class VY>
00260 Actor*
00261 GqInt<VX,VY>::copy(Space* home, bool share) {
00262 return new (home) GqInt<VX,VY>(home,share,*this);
00263 }
00264
00265 template <class VX, class VY>
00266 Support::Symbol
00267 GqInt<VX,VY>::ati(void) {
00268 return Reflection::mangle<VX,VY>("Gecode::Int::Count::GqInt");
00269 }
00270
00271 template <class VX, class VY>
00272 Reflection::ActorSpec
00273 GqInt<VX,VY>::spec(const Space* home, Reflection::VarMap& m) const {
00274 return BaseInt<VX,VY>::spec(home, m, ati());
00275 }
00276
00277 template <class VX, class VY>
00278 void
00279 GqInt<VX,VY>::post(Space* home, Reflection::VarMap& vars,
00280 const Reflection::ActorSpec& spec) {
00281 spec.checkArity(4);
00282 ViewArray<VX> x(home, vars, spec[0]);
00283 int n_s = spec[1]->toInt();
00284 VY y(home, vars, spec[2]);
00285 int c = spec[3]->toInt();
00286 (void) new (home) GqInt(home, x, n_s, y, c);
00287 }
00288
00289 template <class VX, class VY>
00290 ExecStatus
00291 GqInt<VX,VY>::propagate(Space* home, ModEventDelta) {
00292
00293 int n_x = x.size();
00294 for (int i=n_s; i--; )
00295 switch (holds(x[i],y)) {
00296 case RT_FALSE:
00297 x[i].cancel(home,this,PC_INT_DOM);
00298 x[i]=x[--n_s]; x[n_s]=x[--n_x];
00299 break;
00300 case RT_TRUE:
00301 x[i].cancel(home,this,PC_INT_DOM);
00302 x[i]=x[--n_s]; x[n_s]=x[--n_x]; c--;
00303 break;
00304 case RT_MAYBE:
00305 break;
00306 default:
00307 GECODE_NEVER;
00308 }
00309 x.size(n_x);
00310 if (n_x < c)
00311 return ES_FAILED;
00312 if (c <= 0)
00313 return ES_SUBSUMED(this,home);
00314
00315 for (int i=n_x; i-- > n_s; )
00316 switch (holds(x[i],y)) {
00317 case RT_FALSE: x[i]=x[--n_x]; break;
00318 case RT_TRUE: x[i]=x[--n_x]; c--; break;
00319 case RT_MAYBE: break;
00320 default: GECODE_NEVER;
00321 }
00322 x.size(n_x);
00323 if (n_x < c)
00324 return ES_FAILED;
00325 if (c <= 0)
00326 return ES_SUBSUMED(this,home);
00327 if (c == n_x)
00328
00329 return post_true(home,x,y) ? ES_FAILED : ES_SUBSUMED(this,home);
00330
00331 while (n_s <= c)
00332 x[n_s++].subscribe(home,this,PC_INT_DOM,false);
00333 return ES_FIX;
00334 }
00335
00336
00337
00338
00339
00340 template <class VX, class VY>
00341 forceinline
00342 LqInt<VX,VY>::LqInt(Space* home, ViewArray<VX>& x, int n_s, VY y, int c)
00343 : BaseInt<VX,VY>(home,x,n_s,y,c) {}
00344
00345 template <class VX, class VY>
00346 ExecStatus
00347 LqInt<VX,VY>::post(Space* home, ViewArray<VX>& x, VY y, int c) {
00348
00349 int n_x = x.size();
00350 for (int i=n_x; i--; )
00351 switch (holds(x[i],y)) {
00352 case RT_FALSE:
00353 x[i] = x[--n_x]; break;
00354 case RT_TRUE:
00355 x[i] = x[--n_x]; c--; break;
00356 case RT_MAYBE:
00357 break;
00358 default:
00359 GECODE_NEVER;
00360 }
00361 x.size(n_x);
00362 if (c < 0)
00363 return ES_FAILED;
00364 if (c >= n_x)
00365 return ES_OK;
00366
00367 if (c == 0)
00368 return post_false(home,x,y) ? ES_FAILED : ES_OK;
00369 (void) new (home) LqInt<VX,VY>(home,x,n_x-c+1,y,c);
00370 return ES_OK;
00371 }
00372
00373 template <class VX, class VY>
00374 forceinline
00375 LqInt<VX,VY>::LqInt(Space* home, bool share, LqInt<VX,VY>& p)
00376 : BaseInt<VX,VY>(home,share,p) {}
00377
00378 template <class VX, class VY>
00379 Actor*
00380 LqInt<VX,VY>::copy(Space* home, bool share) {
00381 return new (home) LqInt<VX,VY>(home,share,*this);
00382 }
00383
00384 template <class VX, class VY>
00385 Support::Symbol
00386 LqInt<VX,VY>::ati(void) {
00387 return Reflection::mangle<VX,VY>("Gecode::Int::Count::LqInt");
00388 }
00389
00390 template <class VX, class VY>
00391 Reflection::ActorSpec
00392 LqInt<VX,VY>::spec(const Space* home, Reflection::VarMap& m) const {
00393 return BaseInt<VX,VY>::spec(home, m, ati());
00394 }
00395
00396 template <class VX, class VY>
00397 void
00398 LqInt<VX,VY>::post(Space* home, Reflection::VarMap& vars,
00399 const Reflection::ActorSpec& spec) {
00400 spec.checkArity(4);
00401 ViewArray<VX> x(home, vars, spec[0]);
00402 int n_s = spec[1]->toInt();
00403 VY y(home, vars, spec[2]);
00404 int c = spec[3]->toInt();
00405 (void) new (home) LqInt(home, x, n_s, y, c);
00406 }
00407
00408 template <class VX, class VY>
00409 ExecStatus
00410 LqInt<VX,VY>::propagate(Space* home, ModEventDelta) {
00411
00412 int n_x = x.size();
00413 for (int i=n_s; i--; )
00414 switch (holds(x[i],y)) {
00415 case RT_FALSE:
00416 x[i].cancel(home,this,PC_INT_DOM);
00417 x[i]=x[--n_s]; x[n_s]=x[--n_x];
00418 break;
00419 case RT_TRUE:
00420 x[i].cancel(home,this,PC_INT_DOM);
00421 x[i]=x[--n_s]; x[n_s]=x[--n_x]; c--;
00422 break;
00423 case RT_MAYBE:
00424 break;
00425 default:
00426 GECODE_NEVER;
00427 }
00428 x.size(n_x);
00429 if (c < 0)
00430 return ES_FAILED;
00431 if (c >= n_x)
00432 return ES_SUBSUMED(this,home);
00433
00434 for (int i=n_x; i-- > n_s; )
00435 switch (holds(x[i],y)) {
00436 case RT_FALSE: x[i]=x[--n_x]; break;
00437 case RT_TRUE: x[i]=x[--n_x]; c--; break;
00438 case RT_MAYBE: break;
00439 default: GECODE_NEVER;
00440 }
00441 x.size(n_x);
00442 if (c < 0)
00443 return ES_FAILED;
00444 if (c >= n_x)
00445 return ES_SUBSUMED(this,home);
00446 if (c == 0)
00447
00448 return post_false(home,x,y) ? ES_FAILED : ES_SUBSUMED(this,home);
00449
00450 int m = n_x-c;
00451 while (n_s <= m)
00452 x[n_s++].subscribe(home,this,PC_INT_DOM,false);
00453 return ES_FIX;
00454 }
00455
00456
00457
00458
00459
00460 template<class VX, class VY>
00461 forceinline
00462 NqInt<VX,VY>::NqInt(Space* home, ViewArray<VX>& x0, VY y0, int c0)
00463 : BinaryPropagator<VX,PC_INT_DOM>(home,
00464 x0[x0.size()-2],
00465 x0[x0.size()-1]), x(x0), y(y0), c(c0) {
00466 assert(x.size() >= 2);
00467 x.size(x.size()-2);
00468 y.subscribe(home,this,PC_INT_DOM);
00469 }
00470
00471 template <class VX, class VY>
00472 forceinline size_t
00473 NqInt<VX,VY>::dispose(Space* home) {
00474 y.cancel(home,this,PC_INT_DOM);
00475 (void) BinaryPropagator<VX,PC_INT_DOM>::dispose(home);
00476 return sizeof(*this);
00477 }
00478
00479 template<class VX, class VY>
00480 forceinline
00481 NqInt<VX,VY>::NqInt(Space* home, bool share, NqInt<VX,VY>& p)
00482 : BinaryPropagator<VX,PC_INT_DOM>(home,share,p), c(p.c) {
00483 x.update(home,share,p.x);
00484 y.update(home,share,p.y);
00485 }
00486
00487 template<class VX, class VY>
00488 forceinline ExecStatus
00489 NqInt<VX,VY>::post(Space* home, ViewArray<VX>& x, VY y, int c) {
00490 int n = x.size();
00491 for (int i=n; i--; )
00492 switch (holds(x[i],y)) {
00493 case RT_FALSE: x[i]=x[--n]; break;
00494 case RT_TRUE: x[i]=x[--n]; c--; break;
00495 case RT_MAYBE: break;
00496 default: GECODE_NEVER;
00497 }
00498 x.size(n);
00499 if ((n < c) || (c < 0))
00500 return ES_OK;
00501 if (n == 0)
00502 return (c == 0) ? ES_FAILED : ES_OK;
00503 if (n == 1)
00504 if (c == 1)
00505 return post_false(home,x[0],y) ? ES_FAILED : ES_OK;
00506 else
00507 return post_true(home,x[0],y) ? ES_FAILED : ES_OK;
00508 (void) new (home) NqInt(home,x,y,c);
00509 return ES_OK;
00510 }
00511
00512 template<class VX, class VY>
00513 Actor*
00514 NqInt<VX,VY>::copy(Space* home, bool share) {
00515 return new (home) NqInt<VX,VY>(home,share,*this);
00516 }
00517
00518 template<class VX, class VY>
00519 PropCost
00520 NqInt<VX,VY>::cost(ModEventDelta) const {
00521 return PC_LINEAR_LO;
00522 }
00523
00524 template <class VX, class VY>
00525 Support::Symbol
00526 NqInt<VX,VY>::ati(void) {
00527 return Reflection::mangle<VX,VY>("Gecode::Int::Count::NqInt");
00528 }
00529
00530 template <class VX, class VY>
00531 Reflection::ActorSpec
00532 NqInt<VX,VY>::spec(const Space* home, Reflection::VarMap& m) const {
00533 Reflection::ActorSpec s =
00534 BinaryPropagator<VX, PC_INT_DOM>::spec(home, m, ati());
00535 return s << x.spec(home, m)
00536 << y.spec(home, m)
00537 << c;
00538 }
00539
00540 template <class VX, class VY>
00541 void
00542 NqInt<VX,VY>::post(Space* home, Reflection::VarMap& vars,
00543 const Reflection::ActorSpec& spec) {
00544 spec.checkArity(5);
00545 VX x0(home, vars, spec[0]);
00546 VX x1(home, vars, spec[1]);
00547 ViewArray<VX> xx(home, vars, spec[2]);
00548 ViewArray<VX> x(home, xx.size()+2);
00549 for (int i=xx.size(); i--; )
00550 x[i] = xx[i];
00551 x[xx.size()] = x0;
00552 x[xx.size()+1] = x1;
00553 VY y(home, vars, spec[3]);
00554 int c = spec[4]->toInt();
00555 (void) new (home) NqInt(home, x, y, c);
00556 }
00557
00558 template<class VX, class VY>
00559 forceinline bool
00560 NqInt<VX,VY>::resubscribe(Space* home, VX& z) {
00561 switch (holds(z,y)) {
00562 case RT_FALSE: break;
00563 case RT_TRUE: c--; break;
00564 case RT_MAYBE: return true;
00565 default: GECODE_NEVER;
00566 }
00567 int n = x.size();
00568 for (int i=n; i--; )
00569 switch (holds(x[i],y)) {
00570 case RT_FALSE:
00571 x[i]=x[--n];
00572 break;
00573 case RT_TRUE:
00574 x[i]=x[--n]; c--;
00575 break;
00576 case RT_MAYBE:
00577
00578 z.cancel(home,this,PC_INT_DOM);
00579 z=x[i]; x[i]=x[--n];
00580 x.size(n);
00581 z.subscribe(home,this,PC_INT_DOM,false);
00582 return true;
00583 default:
00584 GECODE_NEVER;
00585 }
00586
00587 x.size(0);
00588 return false;
00589 }
00590
00591 template<class VX, class VY>
00592 ExecStatus
00593 NqInt<VX,VY>::propagate(Space* home, ModEventDelta) {
00594 bool s0 = resubscribe(home,x0);
00595 bool s1 = resubscribe(home,x1);
00596 int n = x.size() + s0 + s1;
00597 if ((n < c) || (c < 0))
00598 return ES_SUBSUMED(this,home);
00599 if (n == 0)
00600 return (c == 0) ? ES_FAILED : ES_SUBSUMED(this,home);
00601 if (n == 1) {
00602 if (s0)
00603 if (c == 1)
00604 return post_false(home,x0,y) ? ES_FAILED : ES_SUBSUMED(this,home);
00605 else
00606 return post_true(home,x0,y) ? ES_FAILED : ES_SUBSUMED(this,home);
00607 else
00608 if (c == 1)
00609 return post_false(home,x1,y) ? ES_FAILED : ES_SUBSUMED(this,home);
00610 else
00611 return post_true(home,x1,y) ? ES_FAILED : ES_SUBSUMED(this,home);
00612 }
00613 return ES_FIX;
00614 }
00615
00616 }}}
00617
00618
00619