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