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 namespace Gecode {
00029
00030 template <class View0, class View1>
00031 forceinline bool
00032 viewarrayshared(const ViewArray<View0>& va,
00033 const View1& y) {
00034 return va.shared(y);
00035 }
00036
00037 template <>
00038 forceinline bool
00039 viewarrayshared<Set::SingletonView,Set::SetView>
00040 (const ViewArray<Set::SingletonView>& va, const Set::SetView& y) {
00041 return false;
00042 }
00043
00044 template <>
00045 forceinline bool
00046 viewarrayshared<Set::ComplementView<Set::SingletonView>,Set::SetView>
00047 (const ViewArray<Set::ComplementView<Set::SingletonView> >& va,
00048 const Set::SetView& y) {
00049 return false;
00050 }
00051
00052 template <>
00053 forceinline bool
00054 viewarrayshared<Set::ComplementView<Set::SingletonView>,
00055 Set::ComplementView<Set::SetView> >
00056 (const ViewArray<Set::ComplementView<Set::SingletonView> >& va,
00057 const Set::ComplementView<Set::SetView>& y) {
00058 return false;
00059 }
00060
00061
00062 namespace Set { namespace RelOp {
00063
00064 #define GECODE_ME_CHECK_B(modified, tell) \
00065 { \
00066 ModEvent me = (tell); \
00067 modified |= me_modified(me); \
00068 GECODE_ME_CHECK(me); \
00069 }
00070
00071 #define GECODE_ME_CHECK_VAL(p,f) { \
00072 ModEvent __me__ ## __LINE__ = (p); \
00073 if (me_failed(__me__ ## __LINE__)) return ES_FAILED; \
00074 if (ME_GEN_ASSIGNED==(__me__ ## __LINE__))f=true; }
00075
00076 #define GECODE_ME_CHECK_VAL_B(modified, tell, f) \
00077 { \
00078 ModEvent me = (tell); \
00079 modified |= me_modified(me); \
00080 if (ME_GEN_ASSIGNED==(me))f=true; \
00081 GECODE_ME_CHECK(me); \
00082 }
00083
00084
00085
00086
00087
00088 template <class View0, class View1, class View2>
00089 forceinline bool
00090 shared(View0 v0, View1 v1, View2 v2) {
00091 return shared(v0,v1) || shared(v0,v2) || shared(v1,v2);
00092 }
00093
00094 template <class View0, class View1, class View2>
00095 ExecStatus unionCard(Space* home,
00096 bool& retmodified, View0& x0, View1& x1, View2& x2) {
00097 bool modified = false;
00098 do {
00099 retmodified |= modified;
00100 modified = false;
00101
00102 {
00103 LubRanges<View0> x0ub(x0);
00104 LubRanges<View1> x1ub(x1);
00105 Iter::Ranges::Inter<LubRanges<View0>, LubRanges<View1> > i1(x0ub,x1ub);
00106 unsigned int s1 = Iter::Ranges::size(i1);
00107 unsigned int res = std::max(x0.cardMin()+
00108 (x1.cardMin()<s1 ?
00109 0 : x1.cardMin()-s1),
00110 std::max(x0.cardMin(),
00111 x1.cardMin()));
00112 GECODE_ME_CHECK_B(modified, x2.cardMin(home,res));
00113 }
00114
00115 {
00116 LubRanges<View0> x0ub(x0);
00117 LubRanges<View1> x1ub(x1);
00118 Iter::Ranges::Union<LubRanges<View0>, LubRanges<View1> > u1(x0ub,x1ub);
00119 unsigned int s1 = Iter::Ranges::size(u1);
00120 GECODE_ME_CHECK_B(modified, x2.cardMax(home,s1) );
00121 }
00122
00123 if (x2.cardMin() > x1.cardMax())
00124 GECODE_ME_CHECK_B(modified,
00125 x0.cardMin(home,x2.cardMin() - x1.cardMax()));
00126
00127 if (x2.cardMin() > x0.cardMax())
00128 GECODE_ME_CHECK_B(modified,
00129 x1.cardMin(home,x2.cardMin() - x0.cardMax()));
00130
00131 GECODE_ME_CHECK_B(modified,
00132 x0.cardMax(home,x2.cardMax()));
00133 GECODE_ME_CHECK_B(modified,
00134 x1.cardMax(home,x2.cardMax()));
00135 } while(modified);
00136 return ES_FIX;
00137 }
00138
00139 template <class View0, class View1>
00140 ExecStatus
00141 unionNCard(Space* home, bool& modified, ViewArray<View0>& x,
00142 View1& y, GLBndSet& unionOfDets) {
00143 int xsize = x.size();
00144
00145
00146 unsigned int cardMaxSum=unionOfDets.size();
00147 bool maxValid = true;
00148 for (int i=xsize; i--; ){
00149 cardMaxSum+=x[i].cardMax();
00150 if (cardMaxSum < x[i].cardMax()) { maxValid = false; }
00151 GECODE_ME_CHECK_B(modified, y.cardMin(home,x[i].cardMin()) );
00152 GECODE_ME_CHECK_B(modified, x[i].cardMax(home,y.cardMax()) );
00153 }
00154 if (maxValid) {
00155 GECODE_ME_CHECK_B(modified, y.cardMax(home,cardMaxSum));
00156 }
00157
00158
00159
00160 {
00161 GECODE_AUTOARRAY(unsigned int, rightSum, xsize);
00162 rightSum[xsize-1]=0;
00163
00164 for (int i=x.size()-1;i--;) {
00165 rightSum[i] = rightSum[i+1] + x[i+1].cardMax();
00166 if (rightSum[i] < rightSum[i+1]) {
00167
00168 for (int j=i; j>0;j--) {
00169 rightSum[j]=Limits::Set::card_max;
00170 }
00171 break;
00172 }
00173 }
00174
00175
00176 unsigned int leftAcc=unionOfDets.size();
00177
00178 for (int i=0; i<xsize;i++) {
00179 unsigned int jsum = leftAcc+rightSum[i];
00180
00181 if (jsum >= leftAcc && jsum < y.cardMin()) {
00182 GECODE_ME_CHECK_B(modified, x[i].cardMin(home,y.cardMin()-jsum));
00183 }
00184 leftAcc += x[i].cardMax();
00185 if (leftAcc < x[i].cardMax()) {leftAcc = Limits::Set::card_max;}
00186 }
00187 }
00188
00189
00190
00191 {
00192 GECODE_AUTOARRAY(GLBndSet, rightUnion, xsize);
00193 rightUnion[xsize-1].init(home);
00194 for (int i=xsize-1;i--;){
00195 BndSetRanges prev(rightUnion[i+1]);
00196 LubRanges<View0> prevX(x[i+1]);
00197 Iter::Ranges::Union< BndSetRanges,LubRanges<View0> >
00198 iter(prev,prevX);
00199 rightUnion[i].init(home);
00200 rightUnion[i].includeI(home, iter);
00201 }
00202
00203
00204 GLBndSet leftAcc;
00205 leftAcc.update(home,unionOfDets);
00206 for (int i=0; i<xsize; i++) {
00207 BndSetRanges left(leftAcc);
00208 BndSetRanges right(rightUnion[i]);
00209 Iter::Ranges::Union<BndSetRanges,
00210 BndSetRanges> iter(left, right);
00211 unsigned int unionSize = Iter::Ranges::size(iter);
00212 if (y.cardMin() > unionSize) {
00213 GECODE_ME_CHECK_B(modified,
00214 x[i].cardMin(home, y.cardMin() - unionSize) );
00215 }
00216 LubRanges<View0> xiub(x[i]);
00217 leftAcc.includeI(home, xiub);
00218 }
00219
00220 for (int i=xsize; i--;)
00221 rightUnion[i].dispose(home);
00222 leftAcc.dispose(home);
00223 }
00224
00225
00226
00227 return ES_NOFIX;
00228
00229 }
00230
00231
00232
00233
00234
00235 template <class View0, class View1>
00236 ExecStatus
00237 unionNXiUB(Space* home,
00238 bool& modified, ViewArray<View0>& x, View1& y,
00239 GLBndSet & unionOfDets) {
00240 int xsize = x.size();
00241 for (int i=xsize; i--; ) {
00242 LubRanges<View1> yub(y);
00243 GECODE_ME_CHECK_B(modified, x[i].intersectI(home, yub));
00244 }
00245 return ES_FIX;
00246 }
00247
00248
00249 template <class View0, class View1>
00250 ExecStatus
00251 partitionNCard(Space* home,
00252 bool& modified, ViewArray<View0>& x, View1& y,
00253 GLBndSet& unionOfDets) {
00254 unsigned int cardMinSum=unionOfDets.size();
00255 unsigned int cardMaxSum=unionOfDets.size();
00256 int xsize = x.size();
00257 for (int i=xsize; i--; ) {
00258 cardMinSum+=x[i].cardMin();
00259 if (cardMinSum < x[i].cardMin()) {
00260
00261 GECODE_ME_CHECK(ME_SET_FAILED);
00262 }
00263 }
00264 GECODE_ME_CHECK_B(modified, y.cardMin(home,cardMinSum));
00265 for (int i=xsize; i--; ) {
00266 cardMaxSum+=x[i].cardMax();
00267 if (cardMaxSum < x[i].cardMax()) {
00268
00269 goto overflow;
00270 }
00271 }
00272 GECODE_ME_CHECK_B(modified, y.cardMax(home,cardMaxSum));
00273 overflow:
00274
00275
00276
00277 {
00278 GECODE_AUTOARRAY(unsigned int, rightMinSum, xsize);
00279 GECODE_AUTOARRAY(unsigned int, rightMaxSum, xsize);
00280 rightMinSum[xsize-1]=0;
00281 rightMaxSum[xsize-1]=0;
00282
00283 for (int i=x.size()-1;i--;) {
00284 rightMaxSum[i] = rightMaxSum[i+1] + x[i+1].cardMax();
00285 if (rightMaxSum[i] < rightMaxSum[i+1]) {
00286
00287 for (int j=i; j>0;j--) {
00288 rightMaxSum[j]=Limits::Set::card_max;
00289 }
00290 break;
00291 }
00292
00293 rightMinSum[i] = rightMinSum[i+1] + x[i+1].cardMin();
00294 if (rightMinSum[i] < rightMinSum[i+1]) {
00295
00296 GECODE_ME_CHECK(ME_SET_FAILED);
00297 }
00298
00299
00300 }
00301 unsigned int leftMinAcc=unionOfDets.size();
00302 unsigned int leftMaxAcc=unionOfDets.size();
00303
00304 for (int i=0; i<xsize;i++) {
00305 unsigned int maxSum = leftMaxAcc+rightMaxSum[i];
00306 unsigned int minSum = leftMinAcc+rightMinSum[i];
00307
00308 if (maxSum >= leftMaxAcc && maxSum < y.cardMin()) {
00309 GECODE_ME_CHECK_B(modified, x[i].cardMin(home,y.cardMin()-maxSum));
00310 }
00311
00312
00313 if (minSum < leftMinAcc || y.cardMax() < minSum) {
00314 GECODE_ME_CHECK(ME_SET_FAILED);
00315 }
00316 else {
00317 GECODE_ME_CHECK_B(modified, x[i].cardMax(home,y.cardMax()-minSum));
00318 }
00319
00320 leftMaxAcc += x[i].cardMax();
00321 if (leftMaxAcc < x[i].cardMax()) {leftMaxAcc = Limits::Set::card_max;}
00322 leftMinAcc += x[i].cardMin();
00323 if (leftMinAcc < x[i].cardMin()) {GECODE_ME_CHECK(ME_SET_FAILED);}
00324 }
00325 }
00326
00327 return ES_NOFIX;
00328 }
00329
00330
00331
00332 template <class View0, class View1>
00333 ExecStatus
00334 partitionNXi(Space* home,
00335 bool& modified, ViewArray<View0>& x, View1& y) {
00336 int xsize = x.size();
00337 GECODE_AUTOARRAY(GLBndSet, afterUB, xsize);
00338 GECODE_AUTOARRAY(GLBndSet, afterLB, xsize);
00339
00340 {
00341 GLBndSet sofarAfterUB;
00342 GLBndSet sofarAfterLB;
00343 for (int i=xsize; i--;) {
00344 afterUB[i].init(home);
00345 afterLB[i].init(home);
00346 afterUB[i].update(home,sofarAfterUB);
00347 afterLB[i].update(home,sofarAfterLB);
00348 LubRanges<View0> xiub(x[i]);
00349 GlbRanges<View0> xilb(x[i]);
00350 sofarAfterUB.includeI(home,xiub);
00351 sofarAfterLB.includeI(home,xilb);
00352 }
00353 sofarAfterUB.dispose(home);
00354 sofarAfterLB.dispose(home);
00355 }
00356
00357 {
00358 GLBndSet sofarBeforeUB;
00359 GLBndSet sofarBeforeLB;
00360 for (int i=0; i<xsize; i++) {
00361 LubRanges<View1> yub(y);
00362 BndSetRanges slb(sofarBeforeLB);
00363 BndSetRanges afterlb(afterLB[i]);
00364 Iter::Ranges::Union<BndSetRanges,
00365 BndSetRanges> xjlb(slb, afterlb);
00366 Iter::Ranges::Diff<LubRanges<View1>,
00367 Iter::Ranges::Union<BndSetRanges,
00368 BndSetRanges> > diff1(yub, xjlb);
00369 GECODE_ME_CHECK_B(modified, x[i].intersectI(home,diff1));
00370
00371 GlbRanges<View1> ylb(y);
00372 BndSetRanges sub(sofarBeforeUB);
00373 BndSetRanges afterub(afterUB[i]);
00374 Iter::Ranges::Union<BndSetRanges,
00375 BndSetRanges> xjub(sub, afterub);
00376 Iter::Ranges::Diff<GlbRanges<View1>,
00377 Iter::Ranges::Union<BndSetRanges,
00378 BndSetRanges> > diff2(ylb, xjub);
00379 GECODE_ME_CHECK_B(modified, x[i].includeI(home,diff2));
00380
00381 LubRanges<View0> xiub(x[i]);
00382 GlbRanges<View0> xilb(x[i]);
00383 sofarBeforeUB.includeI(home,xiub);
00384 sofarBeforeLB.includeI(home,xilb);
00385 }
00386 sofarBeforeLB.dispose(home);
00387 sofarBeforeUB.dispose(home);
00388 }
00389
00390 for (int i=xsize;i--;) {
00391 afterUB[i].dispose(home);
00392 afterLB[i].dispose(home);
00393 }
00394
00395 return ES_NOFIX;
00396 }
00397
00398
00399 template <class View0, class View1>
00400 ExecStatus
00401 partitionNXiUB(Space* home,
00402 bool& modified, ViewArray<View0>& x, View1& y,
00403 GLBndSet& unionOfDets) {
00404 int xsize = x.size();
00405 GECODE_AUTOARRAY(GLBndSet, afterLB, xsize);
00406
00407 {
00408 GLBndSet sofarAfterLB;
00409 for (int i=xsize; i--;) {
00410 afterLB[i].init(home);
00411 afterLB[i].update(home,sofarAfterLB);
00412 GlbRanges<View0> xilb(x[i]);
00413 sofarAfterLB.includeI(home,xilb);
00414 }
00415 sofarAfterLB.dispose(home);
00416 }
00417
00418 {
00419 GLBndSet sofarBeforeLB;
00420 sofarBeforeLB.update(home,unionOfDets);
00421 for (int i=0; i<xsize; i++) {
00422 LubRanges<View1> yub(y);
00423 BndSetRanges slb(sofarBeforeLB);
00424 BndSetRanges afterlb(afterLB[i]);
00425 Iter::Ranges::Union<BndSetRanges,
00426 BndSetRanges> xjlb(slb, afterlb);
00427 Iter::Ranges::Diff<LubRanges<View1>,
00428 Iter::Ranges::Union<BndSetRanges,
00429 BndSetRanges> > diff1(yub, xjlb);
00430 GECODE_ME_CHECK_B(modified, x[i].intersectI(home,diff1));
00431
00432 GlbRanges<View0> xilb(x[i]);
00433 sofarBeforeLB.includeI(home,xilb);
00434 }
00435 sofarBeforeLB.dispose(home);
00436 }
00437 for (int i=xsize; i--;)
00438 afterLB[i].dispose(home);
00439 return ES_NOFIX;
00440 }
00441
00442
00443 template <class View0, class View1>
00444 ExecStatus
00445 partitionNXiLB(Space* home,
00446 bool& modified, ViewArray<View0>& x, View1& y,
00447 GLBndSet& unionOfDets) {
00448 int xsize = x.size();
00449 GECODE_AUTOARRAY(GLBndSet, afterUB, xsize);
00450
00451 {
00452 GLBndSet sofarAfterUB;
00453 for (int i=xsize; i--;) {
00454 afterUB[i].init(home);
00455 afterUB[i].update(home,sofarAfterUB);
00456 LubRanges<View0> xiub(x[i]);
00457 sofarAfterUB.includeI(home,xiub);
00458 }
00459 sofarAfterUB.dispose(home);
00460 }
00461
00462 {
00463
00464 GLBndSet sofarBeforeUB;
00465 sofarBeforeUB.update(home,unionOfDets);
00466 for (int i=0; i<xsize; i++) {
00467 GlbRanges<View1> ylb(y);
00468 BndSetRanges sub(sofarBeforeUB);
00469 BndSetRanges afterub(afterUB[i]);
00470 Iter::Ranges::Union<BndSetRanges,
00471 BndSetRanges> xjub(sub, afterub);
00472 Iter::Ranges::Diff<GlbRanges<View1>,
00473 Iter::Ranges::Union<BndSetRanges,
00474 BndSetRanges> > diff2(ylb, xjub);
00475 GECODE_ME_CHECK_B(modified, x[i].includeI(home,diff2));
00476
00477 LubRanges<View0> xiub(x[i]);
00478 sofarBeforeUB.includeI(home,xiub);
00479 }
00480 sofarBeforeUB.dispose(home);
00481 }
00482 for (int i=xsize;i--;)
00483 afterUB[i].dispose(home);
00484 return ES_NOFIX;
00485 }
00486
00487
00488 template <class View0, class View1>
00489 ExecStatus
00490 partitionNYLB(Space* home,
00491 bool& modified, ViewArray<View0>& x, View1& y,
00492 GLBndSet& unionOfDets) {
00493 assert(unionOfDets.isConsistent());
00494 int xsize = x.size();
00495 GECODE_AUTOARRAY(GlbRanges<View0>,xLBs,xsize);
00496 int nonEmptyCounter=0;
00497 for (int i = xsize; i--; ) {
00498 GlbRanges<View0> r(x[i]);
00499 if (r()) {
00500 xLBs[nonEmptyCounter] = r;
00501 nonEmptyCounter++;
00502 }
00503 }
00504 if (nonEmptyCounter !=0) {
00505 Iter::Ranges::NaryUnion<GlbRanges<View0> >
00506 xLBUnion(xLBs,nonEmptyCounter);
00507 BndSetRanges dets(unionOfDets);
00508 Iter::Ranges::Union<Iter::Ranges::NaryUnion<GlbRanges<View0> >,
00509 BndSetRanges>
00510 allUnion(xLBUnion,dets);
00511 GECODE_ME_CHECK_B(modified, y.includeI(home,allUnion));
00512 }
00513 return ES_FIX;
00514 }
00515
00516
00517 template <class View0, class View1>
00518 ExecStatus
00519 partitionNYUB(Space* home,
00520 bool& modified, ViewArray<View0>& x, View1& y,
00521 GLBndSet& unionOfDets) {
00522 int xsize = x.size();
00523 GECODE_AUTOARRAY(LubRanges<View0>,xUBs,xsize);
00524 int nonEmptyCounter=0;
00525 for (int i = xsize; i--; ) {
00526 LubRanges<View0> r(x[i]);
00527 if (r()) {
00528 xUBs[nonEmptyCounter] = r;
00529 nonEmptyCounter++;
00530 }
00531 }
00532 if (nonEmptyCounter !=0) {
00533 Iter::Ranges::NaryUnion<LubRanges<View0> >
00534 xUBUnion(xUBs,nonEmptyCounter);
00535 BndSetRanges dets(unionOfDets);
00536 Iter::Ranges::Union<Iter::Ranges::NaryUnion<LubRanges<View0> >,
00537 BndSetRanges>
00538 fullUnion(xUBUnion, dets);
00539 GECODE_ME_CHECK_B(modified, y.intersectI(home,fullUnion));
00540 }
00541 return ES_FIX;
00542 }
00543
00544 }}}
00545
00546