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