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