common.hpp
Go to the documentation of this file.
00001 /* -*- mode: C++; c-basic-offset: 2; indent-tabs-mode: nil -*- */ 00002 /* 00003 * Main authors: 00004 * Guido Tack <tack@gecode.org> 00005 * Christian Schulte <schulte@gecode.org> 00006 * 00007 * Contributing authors: 00008 * Gabor Szokoli <szokoli@gecode.org> 00009 * 00010 * Copyright: 00011 * Guido Tack, 2004 00012 * Christian Schulte, 2004 00013 * Gabor Szokoli, 2004 00014 * 00015 * Last modified: 00016 * $Date: 2010-09-03 16:36:31 +0200 (Fri, 03 Sep 2010) $ by $Author: schulte $ 00017 * $Revision: 11390 $ 00018 * 00019 * This file is part of Gecode, the generic constraint 00020 * development environment: 00021 * http://www.gecode.org 00022 * 00023 * Permission is hereby granted, free of charge, to any person obtaining 00024 * a copy of this software and associated documentation files (the 00025 * "Software"), to deal in the Software without restriction, including 00026 * without limitation the rights to use, copy, modify, merge, publish, 00027 * distribute, sublicense, and/or sell copies of the Software, and to 00028 * permit persons to whom the Software is furnished to do so, subject to 00029 * the following conditions: 00030 * 00031 * The above copyright notice and this permission notice shall be 00032 * included in all copies or substantial portions of the Software. 00033 * 00034 * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, 00035 * EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF 00036 * MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND 00037 * NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE 00038 * LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION 00039 * OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION 00040 * WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE. 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 Space& home, 00052 const ViewArray<View0>& va, const View1& y) { 00053 return va.shared(home,y); 00054 } 00055 00056 template<> 00057 forceinline bool 00058 viewarrayshared<Set::SingletonView,Set::SetView> 00059 (const Space&, 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 Space&, 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 Space&, 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 * Detect sharing between 3 variables 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 interCard(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::Union<LubRanges<View0>, LubRanges<View1> > 00105 u1(x0ub,x1ub); 00106 unsigned int s1 = Iter::Ranges::size(u1); 00107 00108 if (x0.cardMin() + x1.cardMin() > s1) { 00109 GECODE_ME_CHECK_MODIFIED(modified, 00110 x2.cardMin(home, x0.cardMin()+x1.cardMin()-s1)); 00111 } 00112 00113 // unsigned int res = std::max(x0.cardMin()+ 00114 // (x1.cardMin()<s1 ? 00115 // 0 : x1.cardMin()-s1), 00116 // std::max(x0.cardMin(), 00117 // x1.cardMin())); 00118 // GECODE_ME_CHECK_MODIFIED(modified, x2.cardMin(home,res)); 00119 } 00120 00121 { 00122 GlbRanges<View0> x0lb(x0); 00123 GlbRanges<View1> x1lb(x1); 00124 Iter::Ranges::Union<GlbRanges<View0>, GlbRanges<View1> > 00125 u1(x0lb,x1lb); 00126 unsigned int s1 = Iter::Ranges::size(u1); 00127 GECODE_ME_CHECK_MODIFIED(modified, 00128 x2.cardMax(home, 00129 x0.cardMax()+x1.cardMax()-s1)); 00130 } 00131 00132 if (x2.cardMax() < x1.cardMin()) 00133 GECODE_ME_CHECK_MODIFIED(modified, 00134 x0.cardMax(home, 00135 Set::Limits::card+x2.cardMax()-x1.cardMin())); 00136 00137 if (x2.cardMax() < x0.cardMin()) 00138 GECODE_ME_CHECK_MODIFIED(modified, 00139 x1.cardMax(home, 00140 Set::Limits::card+x2.cardMax()-x0.cardMin())); 00141 00142 GECODE_ME_CHECK_MODIFIED(modified, 00143 x0.cardMin(home,x2.cardMin())); 00144 GECODE_ME_CHECK_MODIFIED(modified, 00145 x1.cardMin(home,x2.cardMin())); 00146 } while(modified); 00147 return ES_FIX; 00148 } 00149 template<class View0, class View1, class View2> 00150 ExecStatus unionCard(Space& home, 00151 bool& retmodified, View0& x0, View1& x1, View2& x2) { 00152 bool modified = false; 00153 do { 00154 retmodified |= modified; 00155 modified = false; 00156 00157 { 00158 LubRanges<View0> x0ub(x0); 00159 LubRanges<View1> x1ub(x1); 00160 Iter::Ranges::Inter<LubRanges<View0>, LubRanges<View1> > i1(x0ub,x1ub); 00161 unsigned int s1 = Iter::Ranges::size(i1); 00162 unsigned int res = std::max(x0.cardMin()+ 00163 (x1.cardMin()<s1 ? 00164 0 : x1.cardMin()-s1), 00165 std::max(x0.cardMin(), 00166 x1.cardMin())); 00167 GECODE_ME_CHECK_MODIFIED(modified, x2.cardMin(home,res)); 00168 } 00169 00170 { 00171 LubRanges<View0> x0ub(x0); 00172 LubRanges<View1> x1ub(x1); 00173 Iter::Ranges::Union<LubRanges<View0>, LubRanges<View1> > u1(x0ub,x1ub); 00174 unsigned int s1 = Iter::Ranges::size(u1); 00175 GECODE_ME_CHECK_MODIFIED(modified, 00176 x2.cardMax(home, 00177 std::min(x0.cardMax()+x1.cardMax(),s1))); 00178 } 00179 00180 if (x2.cardMin() > x1.cardMax()) 00181 GECODE_ME_CHECK_MODIFIED(modified, 00182 x0.cardMin(home,x2.cardMin() - x1.cardMax())); 00183 00184 if (x2.cardMin() > x0.cardMax()) 00185 GECODE_ME_CHECK_MODIFIED(modified, 00186 x1.cardMin(home,x2.cardMin() - x0.cardMax())); 00187 00188 GECODE_ME_CHECK_MODIFIED(modified, 00189 x0.cardMax(home,x2.cardMax())); 00190 GECODE_ME_CHECK_MODIFIED(modified, 00191 x1.cardMax(home,x2.cardMax())); 00192 } while(modified); 00193 return ES_FIX; 00194 } 00195 00196 template<class View0, class View1> 00197 ExecStatus 00198 unionNCard(Space& home, bool& modified, ViewArray<View0>& x, 00199 View1& y, GLBndSet& unionOfDets) { 00200 int xsize = x.size(); 00201 // Max(Xi.cardMin) <= y.card <= Sum(Xi.cardMax) 00202 // Xi.card <=y.cardMax 00203 unsigned int cardMaxSum=unionOfDets.size(); 00204 bool maxValid = true; 00205 for (int i=xsize; i--; ){ 00206 cardMaxSum+=x[i].cardMax(); 00207 if (cardMaxSum < x[i].cardMax()) { maxValid = false; } //overflow 00208 GECODE_ME_CHECK_MODIFIED(modified, y.cardMin(home,x[i].cardMin()) ); 00209 GECODE_ME_CHECK_MODIFIED(modified, x[i].cardMax(home,y.cardMax()) ); 00210 } 00211 if (maxValid) { 00212 GECODE_ME_CHECK_MODIFIED(modified, y.cardMax(home,cardMaxSum)); 00213 } 00214 //y.cardMin - Sum(Xj.cardMax) <= Xi.card 00215 00216 if (x.size() == 0) 00217 return ES_NOFIX; 00218 00219 Region r(home); 00220 //TODO: overflow management is a waste now. 00221 { 00222 unsigned int* rightSum = r.alloc<unsigned int>(xsize); 00223 rightSum[xsize-1]=0; 00224 00225 for (int i=x.size()-1;i--;) { 00226 rightSum[i] = rightSum[i+1] + x[i+1].cardMax(); 00227 if (rightSum[i] < rightSum[i+1]) { 00228 //overflow, fill the rest of the array. 00229 for (int j=i; j>0;j--) { 00230 rightSum[j]=Limits::card; 00231 } 00232 break; 00233 } 00234 } 00235 00236 //Size of union of determied vars missing from x sneaked in here: 00237 unsigned int leftAcc=unionOfDets.size(); 00238 00239 for (int i=0; i<xsize;i++) { 00240 unsigned int jsum = leftAcc+rightSum[i]; 00241 //If jsum did not overflow and is less than y.cardMin: 00242 if (jsum >= leftAcc && jsum < y.cardMin()) { 00243 GECODE_ME_CHECK_MODIFIED(modified, x[i].cardMin(home,y.cardMin()-jsum)); 00244 } 00245 leftAcc += x[i].cardMax(); 00246 if (leftAcc < x[i].cardMax()) {leftAcc = Limits::card;} 00247 } 00248 } 00249 00250 //y.cardMin - |U(Xj.ub)| <= Xi.card 00251 00252 { 00253 GLBndSet* rightUnion = 00254 static_cast<GLBndSet*>(r.ralloc(sizeof(GLBndSet)*xsize)); 00255 new (&rightUnion[xsize-1]) GLBndSet(home); 00256 for (int i=xsize-1;i--;){ 00257 BndSetRanges prev(rightUnion[i+1]); 00258 LubRanges<View0> prevX(x[i+1]); 00259 Iter::Ranges::Union< BndSetRanges,LubRanges<View0> > 00260 iter(prev,prevX); 00261 new (&rightUnion[i]) GLBndSet(home); 00262 rightUnion[i].includeI(home, iter); 00263 } 00264 00265 //union of determied vars missing from x sneaked in here: 00266 GLBndSet leftAcc; 00267 leftAcc.update(home,unionOfDets); 00268 for (int i=0; i<xsize; i++) { 00269 BndSetRanges left(leftAcc); 00270 BndSetRanges right(rightUnion[i]); 00271 Iter::Ranges::Union<BndSetRanges, 00272 BndSetRanges> iter(left, right); 00273 unsigned int unionSize = Iter::Ranges::size(iter); 00274 if (y.cardMin() > unionSize) { 00275 GECODE_ME_CHECK_MODIFIED(modified, 00276 x[i].cardMin(home, y.cardMin() - unionSize) ); 00277 } 00278 LubRanges<View0> xiub(x[i]); 00279 leftAcc.includeI(home, xiub); 00280 } 00281 00282 for (int i=xsize; i--;) 00283 rightUnion[i].dispose(home); 00284 leftAcc.dispose(home); 00285 } 00286 00287 //no need for this: |y.lb - U(Xj.cardMax)| <= S.card 00288 00289 return ES_NOFIX; 00290 00291 } 00292 00293 /* 00294 * Xi UB is subset of YUB 00295 * Subscribes to Y UB 00296 */ 00297 template<class View0, class View1> 00298 ExecStatus 00299 unionNXiUB(Space& home, 00300 bool& modified, ViewArray<View0>& x, View1& y, 00301 GLBndSet &) { 00302 int xsize = x.size(); 00303 for (int i=xsize; i--; ) { 00304 LubRanges<View1> yub(y); 00305 GECODE_ME_CHECK_MODIFIED(modified, x[i].intersectI(home, yub)); 00306 } 00307 return ES_FIX; 00308 } 00309 00310 // cardinality rules for PartitionN constraint 00311 template<class View0, class View1> 00312 ExecStatus 00313 partitionNCard(Space& home, 00314 bool& modified, ViewArray<View0>& x, View1& y, 00315 GLBndSet& unionOfDets) { 00316 unsigned int cardMinSum=unionOfDets.size(); 00317 unsigned int cardMaxSum=unionOfDets.size(); 00318 int xsize = x.size(); 00319 for (int i=xsize; i--; ) { 00320 cardMinSum+=x[i].cardMin(); 00321 if (cardMinSum < x[i].cardMin()) { 00322 //sum of mins overflows: fail the space. 00323 GECODE_ME_CHECK(ME_SET_FAILED); 00324 } 00325 } 00326 GECODE_ME_CHECK_MODIFIED(modified, y.cardMin(home,cardMinSum)); 00327 for (int i=xsize; i--; ) { 00328 cardMaxSum+=x[i].cardMax(); 00329 if (cardMaxSum < x[i].cardMax()) { 00330 //sum of maxes overflows: no useful information to tell. 00331 goto overflow; 00332 } 00333 } 00334 GECODE_ME_CHECK_MODIFIED(modified, y.cardMax(home,cardMaxSum)); 00335 00336 if (x.size() == 0) 00337 return ES_NOFIX; 00338 00339 overflow: 00340 00341 //Cardinality of each x[i] limited by cardinality of y minus all x[j]s: 00342 00343 { 00344 Region r(home); 00345 unsigned int* rightMinSum = r.alloc<unsigned int>(xsize); 00346 unsigned int* rightMaxSum = r.alloc<unsigned int>(xsize); 00347 rightMinSum[xsize-1]=0; 00348 rightMaxSum[xsize-1]=0; 00349 00350 for (int i=x.size()-1;i--;) { 00351 rightMaxSum[i] = rightMaxSum[i+1] + x[i+1].cardMax(); 00352 if (rightMaxSum[i] < rightMaxSum[i+1]) { 00353 //overflow, fill the rest of the array. 00354 for (int j=i; j>0;j--) { 00355 rightMaxSum[j]=Limits::card; 00356 } 00357 break; 00358 } 00359 } 00360 for (int i=x.size()-1;i--;) { 00361 rightMinSum[i] = rightMinSum[i+1] + x[i+1].cardMin(); 00362 if (rightMinSum[i] < rightMinSum[i+1]) { 00363 //overflow, fail the space 00364 GECODE_ME_CHECK(ME_SET_FAILED); 00365 } 00366 } 00367 unsigned int leftMinAcc=unionOfDets.size(); 00368 unsigned int leftMaxAcc=unionOfDets.size(); 00369 00370 for (int i=0; i<xsize;i++) { 00371 unsigned int maxSum = leftMaxAcc+rightMaxSum[i]; 00372 unsigned int minSum = leftMinAcc+rightMinSum[i]; 00373 //If maxSum did not overflow and is less than y.cardMin: 00374 if (maxSum >= leftMaxAcc && maxSum < y.cardMin()) { 00375 GECODE_ME_CHECK_MODIFIED(modified, x[i].cardMin(home,y.cardMin()-maxSum)); 00376 } 00377 00378 //Overflow, fail. 00379 if (minSum < leftMinAcc || y.cardMax() < minSum) { 00380 GECODE_ME_CHECK(ME_SET_FAILED); 00381 } 00382 else { 00383 GECODE_ME_CHECK_MODIFIED(modified, x[i].cardMax(home,y.cardMax()-minSum)); 00384 } 00385 00386 leftMaxAcc += x[i].cardMax(); 00387 if (leftMaxAcc < x[i].cardMax()) 00388 leftMaxAcc = Limits::card; 00389 leftMinAcc += x[i].cardMin(); 00390 if (leftMinAcc < x[i].cardMin()) 00391 GECODE_ME_CHECK(ME_SET_FAILED); 00392 } 00393 } 00394 00395 return ES_NOFIX; 00396 } 00397 00398 // Xi LB includes YLB minus union Xj UB 00399 // Xi UB is subset of YUB minus union of Xj LBs 00400 template<class View0, class View1> 00401 ExecStatus 00402 partitionNXi(Space& home, 00403 bool& modified, ViewArray<View0>& x, View1& y) { 00404 int xsize = x.size(); 00405 Region r(home); 00406 GLBndSet* afterUB = 00407 static_cast<GLBndSet*>(r.ralloc(sizeof(GLBndSet)*xsize)); 00408 GLBndSet* afterLB = 00409 static_cast<GLBndSet*>(r.ralloc(sizeof(GLBndSet)*xsize)); 00410 00411 { 00412 GLBndSet sofarAfterUB; 00413 GLBndSet sofarAfterLB; 00414 for (int i=xsize; i--;) { 00415 new (&afterUB[i]) GLBndSet(home); 00416 new (&afterLB[i]) GLBndSet(home); 00417 afterUB[i].update(home,sofarAfterUB); 00418 afterLB[i].update(home,sofarAfterLB); 00419 LubRanges<View0> xiub(x[i]); 00420 GlbRanges<View0> xilb(x[i]); 00421 sofarAfterUB.includeI(home,xiub); 00422 sofarAfterLB.includeI(home,xilb); 00423 } 00424 sofarAfterUB.dispose(home); 00425 sofarAfterLB.dispose(home); 00426 } 00427 00428 { 00429 GLBndSet sofarBeforeUB; 00430 GLBndSet sofarBeforeLB; 00431 for (int i=0; i<xsize; i++) { 00432 LubRanges<View1> yub(y); 00433 BndSetRanges slb(sofarBeforeLB); 00434 BndSetRanges afterlb(afterLB[i]); 00435 Iter::Ranges::Union<BndSetRanges, 00436 BndSetRanges> xjlb(slb, afterlb); 00437 Iter::Ranges::Diff<LubRanges<View1>, 00438 Iter::Ranges::Union<BndSetRanges, 00439 BndSetRanges> > diff1(yub, xjlb); 00440 GECODE_ME_CHECK_MODIFIED(modified, x[i].intersectI(home,diff1)); 00441 00442 GlbRanges<View1> ylb(y); 00443 BndSetRanges sub(sofarBeforeUB); 00444 BndSetRanges afterub(afterUB[i]); 00445 Iter::Ranges::Union<BndSetRanges, 00446 BndSetRanges> xjub(sub, afterub); 00447 Iter::Ranges::Diff<GlbRanges<View1>, 00448 Iter::Ranges::Union<BndSetRanges, 00449 BndSetRanges> > diff2(ylb, xjub); 00450 GECODE_ME_CHECK_MODIFIED(modified, x[i].includeI(home,diff2)); 00451 00452 LubRanges<View0> xiub(x[i]); 00453 GlbRanges<View0> xilb(x[i]); 00454 sofarBeforeUB.includeI(home,xiub); 00455 sofarBeforeLB.includeI(home,xilb); 00456 } 00457 sofarBeforeLB.dispose(home); 00458 sofarBeforeUB.dispose(home); 00459 } 00460 00461 for (int i=xsize;i--;) { 00462 afterUB[i].dispose(home); 00463 afterLB[i].dispose(home); 00464 } 00465 00466 return ES_NOFIX; 00467 } 00468 00469 // Xi UB is subset of YUB minus union of Xj LBs 00470 template<class View0, class View1> 00471 ExecStatus 00472 partitionNXiUB(Space& home, 00473 bool& modified, ViewArray<View0>& x, View1& y, 00474 GLBndSet& unionOfDets) { 00475 int xsize = x.size(); 00476 Region r(home); 00477 GLBndSet* afterLB = 00478 static_cast<GLBndSet*>(r.ralloc(sizeof(GLBndSet)*xsize)); 00479 00480 { 00481 GLBndSet sofarAfterLB; 00482 for (int i=xsize; i--;) { 00483 new (&afterLB[i]) GLBndSet(home); 00484 afterLB[i].update(home,sofarAfterLB); 00485 GlbRanges<View0> xilb(x[i]); 00486 sofarAfterLB.includeI(home,xilb); 00487 } 00488 sofarAfterLB.dispose(home); 00489 } 00490 00491 { 00492 GLBndSet sofarBeforeLB; 00493 sofarBeforeLB.update(home,unionOfDets); 00494 for (int i=0; i<xsize; i++) { 00495 LubRanges<View1> yub(y); 00496 BndSetRanges slb(sofarBeforeLB); 00497 BndSetRanges afterlb(afterLB[i]); 00498 Iter::Ranges::Union<BndSetRanges, 00499 BndSetRanges> xjlb(slb, afterlb); 00500 Iter::Ranges::Diff<LubRanges<View1>, 00501 Iter::Ranges::Union<BndSetRanges, 00502 BndSetRanges> > diff1(yub, xjlb); 00503 GECODE_ME_CHECK_MODIFIED(modified, x[i].intersectI(home,diff1)); 00504 00505 GlbRanges<View0> xilb(x[i]); 00506 sofarBeforeLB.includeI(home,xilb); 00507 } 00508 sofarBeforeLB.dispose(home); 00509 } 00510 for (int i=xsize; i--;) 00511 afterLB[i].dispose(home); 00512 return ES_NOFIX; 00513 } 00514 00515 // Xi LB includes YLB minus union Xj UB 00516 template<class View0, class View1> 00517 ExecStatus 00518 partitionNXiLB(Space& home, 00519 bool& modified, ViewArray<View0>& x, View1& y, 00520 GLBndSet& unionOfDets) { 00521 int xsize = x.size(); 00522 Region r(home); 00523 GLBndSet* afterUB = 00524 static_cast<GLBndSet*>(r.ralloc(sizeof(GLBndSet)*xsize)); 00525 00526 { 00527 GLBndSet sofarAfterUB; 00528 for (int i=xsize; i--;) { 00529 new (&afterUB[i]) GLBndSet(home); 00530 afterUB[i].update(home,sofarAfterUB); 00531 LubRanges<View0> xiub(x[i]); 00532 sofarAfterUB.includeI(home,xiub); 00533 } 00534 sofarAfterUB.dispose(home); 00535 } 00536 00537 { 00538 //The union of previously determined x[j]-s is added to the mix here: 00539 GLBndSet sofarBeforeUB; 00540 sofarBeforeUB.update(home,unionOfDets); 00541 for (int i=0; i<xsize; i++) { 00542 GlbRanges<View1> ylb(y); 00543 BndSetRanges sub(sofarBeforeUB); 00544 BndSetRanges afterub(afterUB[i]); 00545 Iter::Ranges::Union<BndSetRanges, 00546 BndSetRanges> xjub(sub, afterub); 00547 Iter::Ranges::Diff<GlbRanges<View1>, 00548 Iter::Ranges::Union<BndSetRanges, 00549 BndSetRanges> > diff2(ylb, xjub); 00550 GECODE_ME_CHECK_MODIFIED(modified, x[i].includeI(home,diff2)); 00551 00552 LubRanges<View0> xiub(x[i]); 00553 sofarBeforeUB.includeI(home,xiub); 00554 } 00555 sofarBeforeUB.dispose(home); 00556 } 00557 for (int i=xsize;i--;) 00558 afterUB[i].dispose(home); 00559 return ES_NOFIX; 00560 } 00561 00562 // Y LB contains union of X LBs 00563 template<class View0, class View1> 00564 ExecStatus 00565 partitionNYLB(Space& home, 00566 bool& modified, ViewArray<View0>& x, View1& y, 00567 GLBndSet& unionOfDets) { 00568 assert(unionOfDets.isConsistent()); 00569 int xsize = x.size(); 00570 Region r(home); 00571 GlbRanges<View0>* xLBs = r.alloc<GlbRanges<View0> >(xsize); 00572 int nonEmptyCounter=0; 00573 for (int i = xsize; i--; ) { 00574 GlbRanges<View0> r(x[i]); 00575 if (r()) { 00576 xLBs[nonEmptyCounter] = r; 00577 nonEmptyCounter++; 00578 } 00579 } 00580 if (nonEmptyCounter !=0) { 00581 Iter::Ranges::NaryUnion<GlbRanges<View0> > 00582 xLBUnion(r,xLBs,nonEmptyCounter); 00583 BndSetRanges dets(unionOfDets); 00584 Iter::Ranges::Union<Iter::Ranges::NaryUnion<GlbRanges<View0> >, 00585 BndSetRanges> 00586 allUnion(xLBUnion,dets); 00587 GECODE_ME_CHECK_MODIFIED(modified, y.includeI(home,allUnion)); 00588 } 00589 return ES_FIX; 00590 } 00591 00592 // Y UB is subset of union of X UBs 00593 template<class View0, class View1> 00594 ExecStatus 00595 partitionNYUB(Space& home, 00596 bool& modified, ViewArray<View0>& x, View1& y, 00597 GLBndSet& unionOfDets) { 00598 int xsize = x.size(); 00599 Region r(home); 00600 LubRanges<View0>* xUBs = r.alloc<LubRanges<View0> >(xsize); 00601 int nonEmptyCounter=0; 00602 for (int i = xsize; i--; ) { 00603 LubRanges<View0> r(x[i]); 00604 if (r()) { 00605 xUBs[nonEmptyCounter] = r; 00606 nonEmptyCounter++; 00607 } 00608 } 00609 if (nonEmptyCounter !=0) { 00610 Iter::Ranges::NaryUnion<LubRanges<View0> > 00611 xUBUnion(r,xUBs,nonEmptyCounter); 00612 BndSetRanges dets(unionOfDets); 00613 Iter::Ranges::Union<Iter::Ranges::NaryUnion<LubRanges<View0> >, 00614 BndSetRanges> 00615 fullUnion(xUBUnion, dets); 00616 GECODE_ME_CHECK_MODIFIED(modified, y.intersectI(home,fullUnion)); 00617 } 00618 return ES_FIX; 00619 } 00620 00621 }}} 00622 00623 #endif 00624 00625 // STATISTICS: set-prop