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 : IntSetPropagator<View,PC_SET_ANY,
00054 Gecode::Int::PC_INT_BND> (home, y0, y1) {}
00055
00056 template<class View>
00057 forceinline ExecStatus
00058 MinElement<View>::post(Home home, View x0, Gecode::Int::IntView x1) {
00059 GECODE_ME_CHECK(x0.cardMin(home,1));
00060 (void) new (home) MinElement(home,x0,x1);
00061 return ES_OK;
00062 }
00063
00064 template<class View>
00065 forceinline
00066 MinElement<View>::MinElement(Space& home, bool share, MinElement& p)
00067 : IntSetPropagator<View,PC_SET_ANY,
00068 Gecode::Int::PC_INT_BND> (home, share, p) {}
00069
00070 template<class View>
00071 Actor*
00072 MinElement<View>::copy(Space& home, bool share) {
00073 return new (home) MinElement(home,share,*this);
00074 }
00075
00076 template<class View>
00077 ExecStatus
00078 MinElement<View>::propagate(Space& home, const ModEventDelta&) {
00079
00080
00081
00082
00083
00084
00085
00086
00087
00088
00089
00090 {
00091 LubRanges<View> ub(x0);
00092 GECODE_ME_CHECK(x1.inter_r(home,ub,false));
00093 }
00094 GECODE_ME_CHECK(x1.lq(home,x0.glbMin()));
00095
00096 assert(x0.cardMin()>=1);
00097
00098 {
00100 int size = 0;
00101 int maxN = BndSet::MAX_OF_EMPTY;
00102 for (LubRanges<View> ubr(x0); ubr(); ++ubr, ++size) {}
00103 Region r(home);
00104 int* ub = r.alloc<int>(size*2);
00105 int i=0;
00106 for (LubRanges<View> ubr(x0); ubr(); ++ubr, ++i) {
00107 ub[2*i] = ubr.min();
00108 ub[2*i+1] = ubr.max();
00109 }
00110 int x0cm = x0.cardMin()-1;
00111 for (int i=size; i--;) {
00112 int width = ub[2*i+1]-ub[2*i]+1;
00113 if (width > x0cm) {
00114 maxN = 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 ES_SUBSUMED(*this,home);
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 : IntSetPropagator<View,PC_SET_ANY,
00141 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 : IntSetPropagator<View,PC_SET_ANY,
00155 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 ES_SUBSUMED(*this, home);
00174
00175
00176 if (x1.assigned() && x1.val()==x0.lubMin()) {
00177 GECODE_ME_CHECK(x0.exclude(home,x1.val()));
00178 return ES_SUBSUMED(*this, home);
00179 }
00180
00181
00182 if (x0.glbMin() == x0.lubMin()) {
00183 GECODE_ME_CHECK(x1.nq(home,x0.glbMin()));
00184 return ES_SUBSUMED(*this, home);
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 ES_SUBSUMED(*this, home);
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 ES_SUBSUMED(*this, home);
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 int n = x0.cardMin();
00241 int nth_largest = BndSet::MAX_OF_EMPTY;
00242 for (int i=num_ranges; i--; ) {
00243
00244 int num_values = _ur[2*i+1]-_ur[2*i]+1;
00245
00246 if (num_values >= n) {
00247
00248 nth_largest = _ur[2*i+1]-n+1;
00249 break;
00250 }
00251
00252 n -= num_values;
00253 }
00254
00255 if (x1.min() > nth_largest)
00256 return ES_SUBSUMED(*this, home);
00257 }
00258 return ES_FIX;
00259 }
00260
00261 template<class View>
00262 forceinline
00263 ReMinElement<View>::ReMinElement(Home home, View y0, Gecode::Int::IntView y1,
00264 Gecode::Int::BoolView b2)
00265 : IntSetRePropagator<View,PC_SET_ANY,
00266 Gecode::Int::PC_INT_DOM> (home, y0, y1, b2) {}
00267
00268 template<class View>
00269 forceinline ExecStatus
00270 ReMinElement<View>::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>
00277 forceinline
00278 ReMinElement<View>::ReMinElement(Space& home, bool share, ReMinElement& p)
00279 : IntSetRePropagator<View,PC_SET_ANY,
00280 Gecode::Int::PC_INT_DOM> (home, share, p) {}
00281
00282 template<class View>
00283 Actor*
00284 ReMinElement<View>::copy(Space& home, bool share) {
00285 return new (home) ReMinElement(home,share,*this);
00286 }
00287
00288 template<class View>
00289 ExecStatus
00290 ReMinElement<View>::propagate(Space& home, const ModEventDelta&) {
00291
00292 if (b.one())
00293 GECODE_REWRITE(*this, (MinElement<View>::post(home(*this),x0,x1)));
00294 if (b.zero())
00295 GECODE_REWRITE(*this, (NotMinElement<View>::post(home(*this),x0,x1)));
00296
00297
00298
00299
00300 if ((x0.cardMax() == 0) ||
00301 ((x1.max() < x0.lubMin()) || (x1.min() > x0.lubMax())) ||
00302 ((x0.glbSize() > 0) && (x0.glbMin() < x1.min())))
00303 {
00304 GECODE_ME_CHECK(b.zero(home));
00305 return ES_SUBSUMED(*this, home);
00306 }
00307
00308 if (x0.glbMin() == x0.lubMin()) {
00309
00310 if (x1.assigned()) {
00311 if (x1.val() == x0.glbMin()) {
00312 GECODE_ME_CHECK(b.one(home));
00313 } else {
00314 GECODE_ME_CHECK(b.zero(home));
00315 }
00316 return ES_SUBSUMED(*this, home);
00317 }
00318
00319 else if ((x0.glbMin() < x1.min()) ||
00320 (x0.glbMin() > x1.max()) ||
00321 !x1.in(x0.glbMin()))
00322 {
00323 GECODE_ME_CHECK(b.zero(home));
00324 return ES_SUBSUMED(*this, home);
00325 }
00326 }
00327
00328
00329
00330
00331
00332
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 return ES_FIX;
00382 }
00383
00384 template<class View>
00385 forceinline
00386 MaxElement<View>::MaxElement(Home home, View y0, Gecode::Int::IntView y1)
00387 : IntSetPropagator<View,PC_SET_ANY,
00388 Gecode::Int::PC_INT_BND> (home, y0, y1) {}
00389
00390 template<class View>
00391 forceinline
00392 MaxElement<View>::MaxElement(Space& home, bool share, MaxElement& p)
00393 : IntSetPropagator<View,PC_SET_ANY,
00394 Gecode::Int::PC_INT_BND> (home, share, p) {}
00395
00396 template<class View>
00397 ExecStatus
00398 MaxElement<View>::post(Home home, View x0,
00399 Gecode::Int::IntView x1) {
00400 GECODE_ME_CHECK(x0.cardMin(home,1));
00401 (void) new (home) MaxElement(home,x0,x1);
00402 return ES_OK;
00403 }
00404
00405 template<class View>
00406 Actor*
00407 MaxElement<View>::copy(Space& home, bool share) {
00408 return new (home) MaxElement(home,share,*this);
00409 }
00410
00411 template<class View>
00412 ExecStatus
00413 MaxElement<View>::propagate(Space& home, const ModEventDelta&) {
00414 LubRanges<View> ub(x0);
00415 GECODE_ME_CHECK(x1.inter_r(home,ub,false));
00416 GECODE_ME_CHECK(x1.gq(home,x0.glbMax()));
00417 assert(x0.cardMin()>=1);
00418 GECODE_ME_CHECK(x1.gq(home,x0.lubMinN(x0.cardMin()-1)));
00419 GECODE_ME_CHECK(x0.exclude(home,
00420 x1.max()+1,Limits::max) );
00421
00422 if (x1.assigned()) {
00423 GECODE_ME_CHECK(x0.include(home,x1.val()));
00424 GECODE_ME_CHECK( x0.exclude(home,
00425 x1.val()+1,Limits::max) );
00426 return ES_SUBSUMED(*this,home);
00427 }
00428
00429 return ES_FIX;
00430 }
00431
00432 template<class View>
00433 forceinline
00434 NotMaxElement<View>::NotMaxElement(Home home, View y0,
00435 Gecode::Int::IntView y1)
00436 : IntSetPropagator<View,PC_SET_ANY,
00437 Gecode::Int::PC_INT_DOM> (home, y0, y1) {}
00438
00439 template<class View>
00440 forceinline
00441 NotMaxElement<View>::NotMaxElement(Space& home, bool share,
00442 NotMaxElement& p)
00443 : IntSetPropagator<View,PC_SET_ANY,
00444 Gecode::Int::PC_INT_DOM> (home, share, p) {}
00445
00446 template<class View>
00447 ExecStatus
00448 NotMaxElement<View>::post(Home home, View x0, Gecode::Int::IntView x1) {
00449 (void) new (home) NotMaxElement(home,x0,x1);
00450 return ES_OK;
00451 }
00452
00453 template<class View>
00454 Actor*
00455 NotMaxElement<View>::copy(Space& home, bool share) {
00456 return new (home) NotMaxElement(home,share,*this);
00457 }
00458
00459 template<class View>
00460 ExecStatus
00461 NotMaxElement<View>::propagate(Space& home, const ModEventDelta&) {
00462
00463
00464
00465
00466 if ((x0.cardMax() == 0) ||
00467 ((x1.max() < x0.lubMin()) || (x1.min() > x0.lubMax())) ||
00468 ((x0.glbSize() > 0) && (x0.glbMax() > x1.max())))
00469 return ES_SUBSUMED(*this, home);
00470
00471
00472 if (x1.assigned() && x1.val()==x0.lubMax()) {
00473 GECODE_ME_CHECK(x0.exclude(home,x1.val()));
00474 return ES_SUBSUMED(*this, home);
00475 }
00476
00477
00478 if (x0.glbMax() == x0.lubMax()) {
00479 GECODE_ME_CHECK(x1.nq(home,x0.glbMax()));
00480 return ES_SUBSUMED(*this, home);
00481 }
00482
00483
00484
00485 if (x1.assigned() && x0.glbSize() > 0 && x1.val()==x0.glbMax()) {
00486 unsigned int oldGlbSize = x0.glbSize();
00487
00488 UnknownRanges<View> ur(x0);
00489
00490
00491 while (ur.max() < x1.val()) {
00492 assert(ur());
00493 ++ur;
00494 };
00495
00496
00497 if (ur.width() == 1) {
00498 int i = ur.min();
00499 ++ur;
00500 if (!ur()) {
00501
00502 GECODE_ME_CHECK(x0.include(home,i));
00503 return ES_SUBSUMED(*this, home);
00504 }
00505 }
00506 GECODE_ME_CHECK(x0.cardMin(home, oldGlbSize+1));
00507 }
00508
00509 {
00510 LubRanges<View> ub(x0);
00511 Gecode::Int::ViewRanges<Gecode::Int::IntView> d(x1);
00512 Gecode::Iter::Ranges::Inter<LubRanges<View>,
00513 Gecode::Int::ViewRanges<Gecode::Int::IntView> > ir(ub,d);
00514 if (!ir()) return ES_SUBSUMED(*this, home);
00515 }
00516
00517
00518
00519 {
00520 unsigned int n = x0.cardMin();
00521 int nth_smallest = BndSet::MIN_OF_EMPTY;
00522 for (LubRanges<View> ur(x0); ur(); ++ur) {
00523 if (ur.width() >= n) {
00524
00525 nth_smallest = ur.min() + n - 1;
00526 break;
00527 }
00528
00529 n -= ur.width();
00530 }
00531
00532 if (x1.max() < nth_smallest)
00533 return ES_SUBSUMED(*this, home);
00534 }
00535 return ES_FIX;
00536 }
00537
00538 template<class View>
00539 forceinline
00540 ReMaxElement<View>::ReMaxElement(Home home, View y0, Gecode::Int::IntView y1,
00541 Gecode::Int::BoolView b2)
00542 : IntSetRePropagator<View,PC_SET_ANY,
00543 Gecode::Int::PC_INT_DOM> (home, y0, y1, b2) {}
00544
00545 template<class View>
00546 forceinline
00547 ReMaxElement<View>::ReMaxElement(Space& home, bool share, ReMaxElement& p)
00548 : IntSetRePropagator<View,PC_SET_ANY,
00549 Gecode::Int::PC_INT_DOM> (home, share, p) {}
00550
00551 template<class View>
00552 ExecStatus
00553 ReMaxElement<View>::post(Home home, View x0,
00554 Gecode::Int::IntView x1,
00555 Gecode::Int::BoolView b2) {
00556 (void) new (home) ReMaxElement(home,x0,x1,b2);
00557 return ES_OK;
00558 }
00559
00560 template<class View>
00561 Actor*
00562 ReMaxElement<View>::copy(Space& home, bool share) {
00563 return new (home) ReMaxElement(home,share,*this);
00564 }
00565
00566 template<class View>
00567 ExecStatus
00568 ReMaxElement<View>::propagate(Space& home, const ModEventDelta&) {
00569
00570 if (b.one())
00571 GECODE_REWRITE(*this, (MaxElement<View>::post(home(*this),x0,x1)));
00572 if (b.zero())
00573 GECODE_REWRITE(*this, (NotMaxElement<View>::post(home(*this),x0,x1)));
00574
00575
00576
00577
00578 if ((x0.cardMax() == 0) ||
00579 ((x1.max() < x0.lubMin()) || (x1.min() > x0.lubMax())) ||
00580 ((x0.glbSize() > 0) && (x0.glbMax() > x1.max())))
00581 {
00582 GECODE_ME_CHECK(b.zero(home));
00583 return ES_SUBSUMED(*this, home);
00584 }
00585
00586 if (x0.glbMax() == x0.lubMax()) {
00587
00588 if (x1.assigned()) {
00589 if (x1.val() == x0.glbMax()) {
00590 GECODE_ME_CHECK(b.one(home));
00591 } else {
00592 GECODE_ME_CHECK(b.zero(home));
00593 }
00594 return ES_SUBSUMED(*this, home);
00595 }
00596
00597 else if ((x0.glbMax() < x1.min()) ||
00598 (x0.glbMax() > x1.max()) ||
00599 !x1.in(x0.glbMax()))
00600 {
00601 GECODE_ME_CHECK(b.zero(home));
00602 return ES_SUBSUMED(*this, home);
00603 }
00604 }
00605
00606 {
00607 LubRanges<View> ub(x0);
00608 Gecode::Int::ViewRanges<Gecode::Int::IntView> d(x1);
00609 Gecode::Iter::Ranges::Inter<LubRanges<View>,
00610 Gecode::Int::ViewRanges<Gecode::Int::IntView> > ir(ub,d);
00611 if (!ir()) {
00612 GECODE_ME_CHECK(b.zero(home));
00613 return ES_SUBSUMED(*this, home);
00614 }
00615 }
00616
00617
00618
00619 {
00620 unsigned int n = x0.cardMin();
00621 int nth_smallest = BndSet::MIN_OF_EMPTY;
00622 for (LubRanges<View> ur(x0); ur(); ++ur) {
00623 if (ur.width() >= n)
00624 {
00625
00626 nth_smallest = ur.min() + n - 1;
00627 break;
00628 }
00629
00630 n -= ur.width();
00631 }
00632
00633 if (x1.max() < nth_smallest) {
00634 GECODE_ME_CHECK(b.zero(home));
00635 return ES_SUBSUMED(*this, home);
00636 }
00637 }
00638 return ES_FIX;
00639 }
00640
00641 }}}
00642
00643