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