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