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
00039
00040
00041 #include <gecode/set.hh>
00042 #include <gecode/int.hh>
00043
00044 namespace Gecode { namespace Set { namespace Int {
00045
00046 template<class View>
00047 forceinline
00048 MinElement<View>::MinElement(Home home, View y0, Gecode::Int::IntView y1)
00049 : MixBinaryPropagator<View,PC_SET_ANY,Gecode::Int::IntView,Gecode::Int::PC_INT_BND> (home, y0, y1) {}
00050
00051 template<class View>
00052 forceinline ExecStatus
00053 MinElement<View>::post(Home home, View x0, Gecode::Int::IntView x1) {
00054 GECODE_ME_CHECK(x0.cardMin(home,1));
00055 (void) new (home) MinElement(home,x0,x1);
00056 return ES_OK;
00057 }
00058
00059 template<class View>
00060 forceinline
00061 MinElement<View>::MinElement(Space& home, MinElement& p)
00062 : MixBinaryPropagator<View,PC_SET_ANY,Gecode::Int::IntView,Gecode::Int::PC_INT_BND> (home, p) {}
00063
00064 template<class View>
00065 Actor*
00066 MinElement<View>::copy(Space& home) {
00067 return new (home) MinElement(home,*this);
00068 }
00069
00070 template<class View>
00071 ExecStatus
00072 MinElement<View>::propagate(Space& home, const ModEventDelta&) {
00073
00074
00075
00076
00077
00078
00079
00080
00081
00082
00083
00084 {
00085 LubRanges<View> ub(x0);
00086 GECODE_ME_CHECK(x1.inter_r(home,ub,false));
00087 }
00088 GECODE_ME_CHECK(x1.lq(home,x0.glbMin()));
00089
00090 assert(x0.cardMin()>=1);
00091
00092 {
00094 unsigned int size = 0;
00095 int maxN = BndSet::MAX_OF_EMPTY;
00096 for (LubRanges<View> ubr(x0); ubr(); ++ubr, ++size) {}
00097 Region r;
00098 int* ub = r.alloc<int>(size*2);
00099 {
00100 int i=0;
00101 for (LubRanges<View> ubr(x0); ubr(); ++ubr, ++i) {
00102 ub[2*i] = ubr.min();
00103 ub[2*i+1] = ubr.max();
00104 }
00105 }
00106 unsigned int x0cm = x0.cardMin()-1;
00107 for (unsigned int i=size; i--;) {
00108 unsigned int width = static_cast<unsigned int>(ub[2*i+1]-ub[2*i]+1);
00109 if (width > x0cm) {
00110 maxN = static_cast<int>(ub[2*i+1]-x0cm);
00111 break;
00112 }
00113 x0cm -= width;
00114 }
00115 GECODE_ME_CHECK(x1.lq(home,maxN));
00116 }
00117
00118 GECODE_ME_CHECK( x0.exclude(home,
00119 Limits::min, x1.min()-1) );
00120
00121 if (x1.assigned()) {
00122 GECODE_ME_CHECK(x0.include(home,x1.val()));
00123 GECODE_ME_CHECK(x0.exclude(home,
00124 Limits::min, x1.val()-1));
00125 return home.ES_SUBSUMED(*this);
00126 }
00127
00128 return ES_FIX;
00129 }
00130
00131
00132 template<class View>
00133 forceinline
00134 NotMinElement<View>::NotMinElement(Home home, View y0,
00135 Gecode::Int::IntView y1)
00136 : MixBinaryPropagator<View,PC_SET_ANY,
00137 Gecode::Int::IntView,Gecode::Int::PC_INT_DOM> (home, y0, y1) {}
00138
00139 template<class View>
00140 forceinline ExecStatus
00141 NotMinElement<View>::post(Home home, View x0, Gecode::Int::IntView x1) {
00142 (void) new (home) NotMinElement(home,x0,x1);
00143 return ES_OK;
00144 }
00145
00146 template<class View>
00147 forceinline
00148 NotMinElement<View>::NotMinElement(Space& home, NotMinElement& p)
00149 : MixBinaryPropagator<View,PC_SET_ANY,
00150 Gecode::Int::IntView,Gecode::Int::PC_INT_DOM> (home, p) {}
00151
00152 template<class View>
00153 Actor*
00154 NotMinElement<View>::copy(Space& home) {
00155 return new (home) NotMinElement(home,*this);
00156 }
00157
00158 template<class View>
00159 ExecStatus
00160 NotMinElement<View>::propagate(Space& home, const ModEventDelta&) {
00161
00162
00163
00164
00165 if ((x0.cardMax() == 0) ||
00166 ((x1.max() < x0.lubMin()) || (x1.min() > x0.lubMax())) ||
00167 ((x0.glbSize() > 0) && (x0.glbMin() < x1.min())))
00168 return home.ES_SUBSUMED(*this);
00169
00170
00171 if (x1.assigned() && x1.val()==x0.lubMin()) {
00172 GECODE_ME_CHECK(x0.exclude(home,x1.val()));
00173 return home.ES_SUBSUMED(*this);
00174 }
00175
00176
00177 if (x0.glbMin() == x0.lubMin()) {
00178 GECODE_ME_CHECK(x1.nq(home,x0.glbMin()));
00179 return home.ES_SUBSUMED(*this);
00180 }
00181
00182
00183
00184 if (x1.assigned() && x0.glbSize() > 0 && x1.val()==x0.glbMin()) {
00185 unsigned int oldGlbSize = x0.glbSize();
00186
00187 UnknownRanges<View> ur(x0);
00188 assert(ur());
00189
00190
00191
00192
00193
00194
00195 if (ur.width()==1) {
00196 int i=ur.min();
00197 ++ur;
00198 if (!ur() || ur.min()>x1.val()) {
00199 GECODE_ME_CHECK(x0.include(home,i));
00200 return home.ES_SUBSUMED(*this);
00201 }
00202 }
00203 GECODE_ME_CHECK(x0.cardMin(home, oldGlbSize+1));
00204 }
00205
00206 {
00207 LubRanges<View> ub(x0);
00208 Gecode::Int::ViewRanges<Gecode::Int::IntView> d(x1);
00209 Gecode::Iter::Ranges::Inter<LubRanges<View>,
00210 Gecode::Int::ViewRanges<Gecode::Int::IntView> > ir(ub,d);
00211 if (!ir()) return home.ES_SUBSUMED(*this);
00212 }
00213
00214
00215
00216 {
00217
00218
00219
00220
00221
00222 int num_ranges = 0;
00223 for (LubRanges<View> ur(x0); ur(); ++ur, ++num_ranges) {}
00224
00225 Region r;
00226 int* _ur = r.alloc<int>(num_ranges*2);
00227
00228 int i = 0;
00229 for (LubRanges<View> ur(x0); ur(); ++ur, ++i) {
00230 _ur[2*i ] = ur.min();
00231 _ur[2*i+1] = ur.max();
00232 }
00233
00234
00235 unsigned int n = x0.cardMin();
00236 int nth_largest = BndSet::MAX_OF_EMPTY;
00237 for (int i=num_ranges; i--; ) {
00238
00239 unsigned int num_values = static_cast<unsigned int>(_ur[2*i+1]-_ur[2*i]+1);
00240
00241 if (num_values >= n) {
00242
00243 nth_largest = static_cast<int>(_ur[2*i+1]-n+1);
00244 break;
00245 }
00246
00247 n -= num_values;
00248 }
00249
00250 if (x1.min() > nth_largest)
00251 return home.ES_SUBSUMED(*this);
00252 }
00253 return ES_FIX;
00254 }
00255
00256 template<class View, ReifyMode rm>
00257 forceinline
00258 ReMinElement<View,rm>::ReMinElement(Home home, View y0,
00259 Gecode::Int::IntView y1,
00260 Gecode::Int::BoolView b2)
00261 : Gecode::Int::ReMixBinaryPropagator<View,PC_SET_ANY,
00262 Gecode::Int::IntView,Gecode::Int::PC_INT_DOM,
00263 Gecode::Int::BoolView> (home, y0, y1, b2) {}
00264
00265 template<class View, ReifyMode rm>
00266 forceinline ExecStatus
00267 ReMinElement<View,rm>::post(Home home, View x0, Gecode::Int::IntView x1,
00268 Gecode::Int::BoolView b2) {
00269 (void) new (home) ReMinElement(home,x0,x1,b2);
00270 return ES_OK;
00271 }
00272
00273 template<class View, ReifyMode rm>
00274 forceinline
00275 ReMinElement<View,rm>::ReMinElement(Space& home, ReMinElement& p)
00276 : Gecode::Int::ReMixBinaryPropagator<View,PC_SET_ANY,
00277 Gecode::Int::IntView,Gecode::Int::PC_INT_DOM,
00278 Gecode::Int::BoolView> (home, p) {}
00279
00280 template<class View, ReifyMode rm>
00281 Actor*
00282 ReMinElement<View,rm>::copy(Space& home) {
00283 return new (home) ReMinElement(home,*this);
00284 }
00285
00286 template<class View, ReifyMode rm>
00287 ExecStatus
00288 ReMinElement<View,rm>::propagate(Space& home, const ModEventDelta&) {
00289
00290 if (b.one()) {
00291 if (rm == RM_PMI)
00292 return home.ES_SUBSUMED(*this);
00293 GECODE_REWRITE(*this, (MinElement<View>::post(home(*this),x0,x1)));
00294 }
00295 if (b.zero()) {
00296 if (rm == RM_IMP)
00297 return home.ES_SUBSUMED(*this);
00298 GECODE_REWRITE(*this, (NotMinElement<View>::post(home(*this),x0,x1)));
00299 }
00300
00301
00302
00303
00304 if ((x0.cardMax() == 0) ||
00305 ((x1.max() < x0.lubMin()) || (x1.min() > x0.lubMax())) ||
00306 ((x0.glbSize() > 0) && (x0.glbMin() < x1.min())))
00307 {
00308 if (rm != RM_PMI)
00309 GECODE_ME_CHECK(b.zero(home));
00310 return home.ES_SUBSUMED(*this);
00311 }
00312
00313 if (x0.glbMin() == x0.lubMin()) {
00314
00315 if (x1.assigned()) {
00316 if (x1.val() == x0.glbMin()) {
00317 if (rm != RM_IMP)
00318 GECODE_ME_CHECK(b.one(home));
00319 } else {
00320 if (rm != RM_PMI)
00321 GECODE_ME_CHECK(b.zero(home));
00322 }
00323 return home.ES_SUBSUMED(*this);
00324 }
00325
00326 else if ((x0.glbMin() < x1.min()) ||
00327 (x0.glbMin() > x1.max()) ||
00328 !x1.in(x0.glbMin()))
00329 {
00330 if (rm != RM_PMI)
00331 GECODE_ME_CHECK(b.zero(home));
00332 return home.ES_SUBSUMED(*this);
00333 }
00334 }
00335
00336
00337
00338
00339
00340
00341
00342
00343
00344
00345
00346
00347
00348
00349
00350
00351
00352
00353
00354
00355
00356
00357
00358
00359
00360
00361
00362
00363
00364
00365
00366
00367
00368
00369
00370
00371
00372
00373
00374
00375
00376
00377
00378
00379
00380
00381
00382
00383
00384
00385
00386
00387
00388
00389 return ES_FIX;
00390 }
00391
00392 template<class View>
00393 forceinline
00394 MaxElement<View>::MaxElement(Home home, View y0, Gecode::Int::IntView y1)
00395 : MixBinaryPropagator<View,PC_SET_ANY,
00396 Gecode::Int::IntView,Gecode::Int::PC_INT_BND> (home, y0, y1) {}
00397
00398 template<class View>
00399 forceinline
00400 MaxElement<View>::MaxElement(Space& home, MaxElement& p)
00401 : MixBinaryPropagator<View,PC_SET_ANY,
00402 Gecode::Int::IntView,Gecode::Int::PC_INT_BND> (home, p) {}
00403
00404 template<class View>
00405 ExecStatus
00406 MaxElement<View>::post(Home home, View x0,
00407 Gecode::Int::IntView x1) {
00408 GECODE_ME_CHECK(x0.cardMin(home,1));
00409 (void) new (home) MaxElement(home,x0,x1);
00410 return ES_OK;
00411 }
00412
00413 template<class View>
00414 Actor*
00415 MaxElement<View>::copy(Space& home) {
00416 return new (home) MaxElement(home,*this);
00417 }
00418
00419 template<class View>
00420 ExecStatus
00421 MaxElement<View>::propagate(Space& home, const ModEventDelta&) {
00422 LubRanges<View> ub(x0);
00423 GECODE_ME_CHECK(x1.inter_r(home,ub,false));
00424 GECODE_ME_CHECK(x1.gq(home,x0.glbMax()));
00425 assert(x0.cardMin()>=1);
00426 GECODE_ME_CHECK(x1.gq(home,x0.lubMinN(x0.cardMin()-1)));
00427 GECODE_ME_CHECK(x0.exclude(home,
00428 x1.max()+1,Limits::max) );
00429
00430 if (x1.assigned()) {
00431 GECODE_ME_CHECK(x0.include(home,x1.val()));
00432 GECODE_ME_CHECK( x0.exclude(home,
00433 x1.val()+1,Limits::max) );
00434 return home.ES_SUBSUMED(*this);
00435 }
00436
00437 return ES_FIX;
00438 }
00439
00440 template<class View>
00441 forceinline
00442 NotMaxElement<View>::NotMaxElement(Home home, View y0,
00443 Gecode::Int::IntView y1)
00444 : MixBinaryPropagator<View,PC_SET_ANY,
00445 Gecode::Int::IntView,Gecode::Int::PC_INT_DOM> (home, y0, y1) {}
00446
00447 template<class View>
00448 forceinline
00449 NotMaxElement<View>::NotMaxElement(Space& home, NotMaxElement& p)
00450 : MixBinaryPropagator<View,PC_SET_ANY,
00451 Gecode::Int::IntView,Gecode::Int::PC_INT_DOM> (home, p) {}
00452
00453 template<class View>
00454 ExecStatus
00455 NotMaxElement<View>::post(Home home, View x0, Gecode::Int::IntView x1) {
00456 (void) new (home) NotMaxElement(home,x0,x1);
00457 return ES_OK;
00458 }
00459
00460 template<class View>
00461 Actor*
00462 NotMaxElement<View>::copy(Space& home) {
00463 return new (home) NotMaxElement(home,*this);
00464 }
00465
00466 template<class View>
00467 ExecStatus
00468 NotMaxElement<View>::propagate(Space& home, const ModEventDelta&) {
00469
00470
00471
00472
00473 if ((x0.cardMax() == 0) ||
00474 ((x1.max() < x0.lubMin()) || (x1.min() > x0.lubMax())) ||
00475 ((x0.glbSize() > 0) && (x0.glbMax() > x1.max())))
00476 return home.ES_SUBSUMED(*this);
00477
00478
00479 if (x1.assigned() && x1.val()==x0.lubMax()) {
00480 GECODE_ME_CHECK(x0.exclude(home,x1.val()));
00481 return home.ES_SUBSUMED(*this);
00482 }
00483
00484
00485 if (x0.glbMax() == x0.lubMax()) {
00486 GECODE_ME_CHECK(x1.nq(home,x0.glbMax()));
00487 return home.ES_SUBSUMED(*this);
00488 }
00489
00490
00491
00492 if (x1.assigned() && x0.glbSize() > 0 && x1.val()==x0.glbMax()) {
00493 unsigned int oldGlbSize = x0.glbSize();
00494
00495 UnknownRanges<View> ur(x0);
00496
00497
00498 while (ur.max() < x1.val()) {
00499 assert(ur());
00500 ++ur;
00501 };
00502
00503
00504 if (ur.width() == 1) {
00505 int i = ur.min();
00506 ++ur;
00507 if (!ur()) {
00508
00509 GECODE_ME_CHECK(x0.include(home,i));
00510 return home.ES_SUBSUMED(*this);
00511 }
00512 }
00513 GECODE_ME_CHECK(x0.cardMin(home, oldGlbSize+1));
00514 }
00515
00516 {
00517 LubRanges<View> ub(x0);
00518 Gecode::Int::ViewRanges<Gecode::Int::IntView> d(x1);
00519 Gecode::Iter::Ranges::Inter<LubRanges<View>,
00520 Gecode::Int::ViewRanges<Gecode::Int::IntView> > ir(ub,d);
00521 if (!ir()) return home.ES_SUBSUMED(*this);
00522 }
00523
00524
00525
00526 {
00527 unsigned int n = x0.cardMin();
00528 int nth_smallest = BndSet::MIN_OF_EMPTY;
00529 for (LubRanges<View> ur(x0); ur(); ++ur) {
00530 if (ur.width() >= n) {
00531
00532 nth_smallest = static_cast<int>(ur.min() + n - 1);
00533 break;
00534 }
00535
00536 n -= ur.width();
00537 }
00538
00539 if (x1.max() < nth_smallest)
00540 return home.ES_SUBSUMED(*this);
00541 }
00542 return ES_FIX;
00543 }
00544
00545 template<class View, ReifyMode rm>
00546 forceinline
00547 ReMaxElement<View,rm>::ReMaxElement(Home home, View y0,
00548 Gecode::Int::IntView y1,
00549 Gecode::Int::BoolView b2)
00550 : Gecode::Int::ReMixBinaryPropagator<View,PC_SET_ANY,
00551 Gecode::Int::IntView,Gecode::Int::PC_INT_DOM,
00552 Gecode::Int::BoolView> (home, y0, y1, b2) {}
00553
00554 template<class View, ReifyMode rm>
00555 forceinline
00556 ReMaxElement<View,rm>::ReMaxElement(Space& home, ReMaxElement& p)
00557 : Gecode::Int::ReMixBinaryPropagator<View,PC_SET_ANY,
00558 Gecode::Int::IntView,Gecode::Int::PC_INT_DOM,
00559 Gecode::Int::BoolView> (home, p) {}
00560
00561 template<class View, ReifyMode rm>
00562 ExecStatus
00563 ReMaxElement<View,rm>::post(Home home, View x0,
00564 Gecode::Int::IntView x1,
00565 Gecode::Int::BoolView b2) {
00566 (void) new (home) ReMaxElement(home,x0,x1,b2);
00567 return ES_OK;
00568 }
00569
00570 template<class View, ReifyMode rm>
00571 Actor*
00572 ReMaxElement<View,rm>::copy(Space& home) {
00573 return new (home) ReMaxElement(home,*this);
00574 }
00575
00576 template<class View, ReifyMode rm>
00577 ExecStatus
00578 ReMaxElement<View,rm>::propagate(Space& home, const ModEventDelta&) {
00579
00580 if (b.one()) {
00581 if (rm == RM_PMI)
00582 return home.ES_SUBSUMED(*this);
00583 GECODE_REWRITE(*this, (MaxElement<View>::post(home(*this),x0,x1)));
00584 }
00585 if (b.zero()) {
00586 if (rm == RM_IMP)
00587 return home.ES_SUBSUMED(*this);
00588 GECODE_REWRITE(*this, (NotMaxElement<View>::post(home(*this),x0,x1)));
00589 }
00590
00591
00592
00593
00594 if ((x0.cardMax() == 0) ||
00595 ((x1.max() < x0.lubMin()) || (x1.min() > x0.lubMax())) ||
00596 ((x0.glbSize() > 0) && (x0.glbMax() > x1.max())))
00597 {
00598 if (rm != RM_PMI)
00599 GECODE_ME_CHECK(b.zero(home));
00600 return home.ES_SUBSUMED(*this);
00601 }
00602
00603 if (x0.glbMax() == x0.lubMax()) {
00604
00605 if (x1.assigned()) {
00606 if (x1.val() == x0.glbMax()) {
00607 if (rm != RM_IMP)
00608 GECODE_ME_CHECK(b.one(home));
00609 } else {
00610 if (rm != RM_PMI)
00611 GECODE_ME_CHECK(b.zero(home));
00612 }
00613 return home.ES_SUBSUMED(*this);
00614 }
00615
00616 else if ((x0.glbMax() < x1.min()) ||
00617 (x0.glbMax() > x1.max()) ||
00618 !x1.in(x0.glbMax()))
00619 {
00620 if (rm != RM_PMI)
00621 GECODE_ME_CHECK(b.zero(home));
00622 return home.ES_SUBSUMED(*this);
00623 }
00624 }
00625
00626 {
00627 LubRanges<View> ub(x0);
00628 Gecode::Int::ViewRanges<Gecode::Int::IntView> d(x1);
00629 Gecode::Iter::Ranges::Inter<LubRanges<View>,
00630 Gecode::Int::ViewRanges<Gecode::Int::IntView> > ir(ub,d);
00631 if (!ir()) {
00632 if (rm != RM_PMI)
00633 GECODE_ME_CHECK(b.zero(home));
00634 return home.ES_SUBSUMED(*this);
00635 }
00636 }
00637
00638
00639
00640 {
00641 unsigned int n = x0.cardMin();
00642 int nth_smallest = BndSet::MIN_OF_EMPTY;
00643 for (LubRanges<View> ur(x0); ur(); ++ur) {
00644 if (ur.width() >= n)
00645 {
00646
00647 nth_smallest = static_cast<int>(ur.min() + n - 1);
00648 break;
00649 }
00650
00651 n -= ur.width();
00652 }
00653
00654 if (x1.max() < nth_smallest) {
00655 if (rm != RM_PMI)
00656 GECODE_ME_CHECK(b.zero(home));
00657 return home.ES_SUBSUMED(*this);
00658 }
00659 }
00660 return ES_FIX;
00661 }
00662
00663 }}}
00664
00665