minmax.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 * Gabor Szokoli <szokoli@gecode.org> 00007 * Denys Duchier <denys.duchier@univ-orleans.fr> 00008 * 00009 * Copyright: 00010 * Guido Tack, 2004 00011 * Christian Schulte, 2004 00012 * Gabor Szokoli, 2004 00013 * 00014 * Last modified: 00015 * $Date: 2010-07-14 17:46:18 +0200 (Wed, 14 Jul 2010) $ by $Author: schulte $ 00016 * $Revision: 11192 $ 00017 * 00018 * This file is part of Gecode, the generic constraint 00019 * development environment: 00020 * http://www.gecode.org 00021 * 00022 * Permission is hereby granted, free of charge, to any person obtaining 00023 * a copy of this software and associated documentation files (the 00024 * "Software"), to deal in the Software without restriction, including 00025 * without limitation the rights to use, copy, modify, merge, publish, 00026 * distribute, sublicense, and/or sell copies of the Software, and to 00027 * permit persons to whom the Software is furnished to do so, subject to 00028 * the following conditions: 00029 * 00030 * The above copyright notice and this permission notice shall be 00031 * included in all copies or substantial portions of the Software. 00032 * 00033 * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, 00034 * EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF 00035 * MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND 00036 * NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE 00037 * LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION 00038 * OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION 00039 * WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE. 00040 * 00041 */ 00042 00043 00044 00045 #include <gecode/set.hh> 00046 #include <gecode/int.hh> 00047 00048 namespace Gecode { namespace Set { namespace Int { 00049 00050 template<class View> 00051 forceinline 00052 MinElement<View>::MinElement(Home home, View y0, Gecode::Int::IntView y1) 00053 : MixBinaryPropagator<View,PC_SET_ANY,Gecode::Int::IntView,Gecode::Int::PC_INT_BND> (home, y0, y1) {} 00054 00055 template<class View> 00056 forceinline ExecStatus 00057 MinElement<View>::post(Home home, View x0, Gecode::Int::IntView x1) { 00058 GECODE_ME_CHECK(x0.cardMin(home,1)); 00059 (void) new (home) MinElement(home,x0,x1); 00060 return ES_OK; 00061 } 00062 00063 template<class View> 00064 forceinline 00065 MinElement<View>::MinElement(Space& home, bool share, MinElement& p) 00066 : MixBinaryPropagator<View,PC_SET_ANY,Gecode::Int::IntView,Gecode::Int::PC_INT_BND> (home, share, p) {} 00067 00068 template<class View> 00069 Actor* 00070 MinElement<View>::copy(Space& home, bool share) { 00071 return new (home) MinElement(home,share,*this); 00072 } 00073 00074 template<class View> 00075 ExecStatus 00076 MinElement<View>::propagate(Space& home, const ModEventDelta&) { 00077 //x1 is an element of x0.ub 00078 //x1 =< smallest element of x0.lb 00079 //x1 =< x0.cardinialityMin-est largest element of x0.ub 00080 //(these 2 take care of determined x0) 00081 //No element in x0 is smaller than x1 00082 //if x1 is determined, it is part of the ub. 00083 00084 //Consequently: 00085 //The domain of x1 is a subset of x0.ub up to the first element in x0.lb. 00086 //x0 lacks everything smaller than smallest possible x1. 00087 00088 { 00089 LubRanges<View> ub(x0); 00090 GECODE_ME_CHECK(x1.inter_r(home,ub,false)); 00091 } 00092 GECODE_ME_CHECK(x1.lq(home,x0.glbMin())); 00093 //if cardMin>lbSize? 00094 assert(x0.cardMin()>=1); 00095 00096 { 00098 unsigned int size = 0; 00099 int maxN = BndSet::MAX_OF_EMPTY; 00100 for (LubRanges<View> ubr(x0); ubr(); ++ubr, ++size) {} 00101 Region r(home); 00102 int* ub = r.alloc<int>(size*2); 00103 int i=0; 00104 for (LubRanges<View> ubr(x0); ubr(); ++ubr, ++i) { 00105 ub[2*i] = ubr.min(); 00106 ub[2*i+1] = ubr.max(); 00107 } 00108 unsigned int x0cm = x0.cardMin()-1; 00109 for (unsigned int i=size; i--;) { 00110 unsigned int width = static_cast<unsigned int>(ub[2*i+1]-ub[2*i]+1); 00111 if (width > x0cm) { 00112 maxN = static_cast<int>(ub[2*i+1]-x0cm); 00113 break; 00114 } 00115 x0cm -= width; 00116 } 00117 GECODE_ME_CHECK(x1.lq(home,maxN)); 00118 } 00119 00120 GECODE_ME_CHECK( x0.exclude(home, 00121 Limits::min, x1.min()-1) ); 00122 00123 if (x1.assigned()) { 00124 GECODE_ME_CHECK(x0.include(home,x1.val())); 00125 GECODE_ME_CHECK(x0.exclude(home, 00126 Limits::min, x1.val()-1)); 00127 return home.ES_SUBSUMED(*this); 00128 } 00129 00130 return ES_FIX; 00131 } 00132 00133 00134 template<class View> 00135 forceinline 00136 NotMinElement<View>::NotMinElement(Home home, View y0, 00137 Gecode::Int::IntView y1) 00138 : MixBinaryPropagator<View,PC_SET_ANY, 00139 Gecode::Int::IntView,Gecode::Int::PC_INT_DOM> (home, y0, y1) {} 00140 00141 template<class View> 00142 forceinline ExecStatus 00143 NotMinElement<View>::post(Home home, View x0, Gecode::Int::IntView x1) { 00144 (void) new (home) NotMinElement(home,x0,x1); 00145 return ES_OK; 00146 } 00147 00148 template<class View> 00149 forceinline 00150 NotMinElement<View>::NotMinElement(Space& home, bool share, 00151 NotMinElement& p) 00152 : MixBinaryPropagator<View,PC_SET_ANY, 00153 Gecode::Int::IntView,Gecode::Int::PC_INT_DOM> (home, share, p) {} 00154 00155 template<class View> 00156 Actor* 00157 NotMinElement<View>::copy(Space& home, bool share) { 00158 return new (home) NotMinElement(home,share,*this); 00159 } 00160 00161 template<class View> 00162 ExecStatus 00163 NotMinElement<View>::propagate(Space& home, const ModEventDelta&) { 00164 // cheap tests for entailment: 00165 // if x0 is empty, then entailed 00166 // if max(x1) < min(x0.lub) or min(x1) > max(x0.lub), then entailed 00167 // if min(x0.glb) < min(x1), then entailed 00168 if ((x0.cardMax() == 0) || 00169 ((x1.max() < x0.lubMin()) || (x1.min() > x0.lubMax())) || 00170 ((x0.glbSize() > 0) && (x0.glbMin() < x1.min()))) 00171 return home.ES_SUBSUMED(*this); 00172 // if x1 is determined and = x0.lub.min: remove it from x0, 00173 // then entailed 00174 if (x1.assigned() && x1.val()==x0.lubMin()) { 00175 GECODE_ME_CHECK(x0.exclude(home,x1.val())); 00176 return home.ES_SUBSUMED(*this); 00177 } 00178 // if min(x0) is decided: remove min(x0) from the domain of x1 00179 // then entailed 00180 if (x0.glbMin() == x0.lubMin()) { 00181 GECODE_ME_CHECK(x1.nq(home,x0.glbMin())); 00182 return home.ES_SUBSUMED(*this); 00183 } 00184 // if x1 is determined and = x0.glb.min, then we need at least 00185 // one more element; if there is only one below, then we must 00186 // take it. 00187 if (x1.assigned() && x0.glbSize() > 0 && x1.val()==x0.glbMin()) { 00188 unsigned int oldGlbSize = x0.glbSize(); 00189 // if there is only 1 unknown below x1, then we must take it 00190 UnknownRanges<View> ur(x0); 00191 assert(ur()); 00192 // the iterator is not empty: otherwise x0 would be determined 00193 // and min(x0) would have been decided and the preceding if 00194 // would have caught it. Also, the first range is not above 00195 // x1 otherwise the very first if would have caught it. 00196 // so let's check if the very first range of unknowns is of 00197 // size 1 and there is no second one or it starts above x1. 00198 if (ur.width()==1) { 00199 int i=ur.min(); 00200 ++ur; 00201 if (!ur() || ur.min()>x1.val()) { 00202 GECODE_ME_CHECK(x0.include(home,i)); 00203 return home.ES_SUBSUMED(*this); 00204 } 00205 } 00206 GECODE_ME_CHECK(x0.cardMin(home, oldGlbSize+1)); 00207 } 00208 // if dom(x1) and lub(x0) are disjoint, then entailed; 00209 { 00210 LubRanges<View> ub(x0); 00211 Gecode::Int::ViewRanges<Gecode::Int::IntView> d(x1); 00212 Gecode::Iter::Ranges::Inter<LubRanges<View>, 00213 Gecode::Int::ViewRanges<Gecode::Int::IntView> > ir(ub,d); 00214 if (!ir()) return home.ES_SUBSUMED(*this); 00215 } 00216 // x0 is fated to eventually contain at least x0.cardMin elements. 00217 // therefore min(x0) <= x0.cardMin-th largest element of x0.lub 00218 // if x1 > than that, then entailed. 00219 { 00220 // to find the x0.cardMin-th largest element of x0.lub, we need 00221 // some sort of reverse range iterator. we will need to fake one 00222 // by storing the ranges of the forward iterator in an array. 00223 // first we need to know how large the array needs to be. so, let's 00224 // count the ranges: 00225 int num_ranges = 0; 00226 for (LubRanges<View> ur(x0); ur(); ++ur, ++num_ranges) {} 00227 // create an array for storing min and max of each range 00228 Region r(home); 00229 int* _ur = r.alloc<int>(num_ranges*2); 00230 // now, we fill the array: 00231 int i = 0; 00232 for (LubRanges<View> ur(x0); ur(); ++ur, ++i) { 00233 _ur[2*i ] = ur.min(); 00234 _ur[2*i+1] = ur.max(); 00235 } 00236 // now we search from the top the range that contains the 00237 // nth largest value. 00238 unsigned int n = x0.cardMin(); 00239 int nth_largest = BndSet::MAX_OF_EMPTY; 00240 for (int i=num_ranges; i--; ) { 00241 // number of values in range 00242 unsigned int num_values = static_cast<unsigned int>(_ur[2*i+1]-_ur[2*i]+1); 00243 // does the range contain the value? 00244 if (num_values >= n) { 00245 // record it and exit the loop 00246 nth_largest = static_cast<int>(_ur[2*i+1]-n+1); 00247 break; 00248 } 00249 // otherwise, we skipped num_values 00250 n -= num_values; 00251 } 00252 // if x1.min > nth_largest, then entailed 00253 if (x1.min() > nth_largest) 00254 return home.ES_SUBSUMED(*this); 00255 } 00256 return ES_FIX; 00257 } 00258 00259 template<class View> 00260 forceinline 00261 ReMinElement<View>::ReMinElement(Home home, View y0, Gecode::Int::IntView y1, 00262 Gecode::Int::BoolView b2) 00263 : Gecode::Int::ReMixBinaryPropagator<View,PC_SET_ANY, 00264 Gecode::Int::IntView,Gecode::Int::PC_INT_DOM, 00265 Gecode::Int::BoolView> (home, y0, y1, b2) {} 00266 00267 template<class View> 00268 forceinline ExecStatus 00269 ReMinElement<View>::post(Home home, View x0, Gecode::Int::IntView x1, 00270 Gecode::Int::BoolView b2) { 00271 (void) new (home) ReMinElement(home,x0,x1,b2); 00272 return ES_OK; 00273 } 00274 00275 template<class View> 00276 forceinline 00277 ReMinElement<View>::ReMinElement(Space& home, bool share, ReMinElement& p) 00278 : Gecode::Int::ReMixBinaryPropagator<View,PC_SET_ANY, 00279 Gecode::Int::IntView,Gecode::Int::PC_INT_DOM, 00280 Gecode::Int::BoolView> (home, share, p) {} 00281 00282 template<class View> 00283 Actor* 00284 ReMinElement<View>::copy(Space& home, bool share) { 00285 return new (home) ReMinElement(home,share,*this); 00286 } 00287 00288 template<class View> 00289 ExecStatus 00290 ReMinElement<View>::propagate(Space& home, const ModEventDelta&) { 00291 // check if b is determined 00292 if (b.one()) 00293 GECODE_REWRITE(*this, (MinElement<View>::post(home(*this),x0,x1))); 00294 if (b.zero()) 00295 GECODE_REWRITE(*this, (NotMinElement<View>::post(home(*this),x0,x1))); 00296 // cheap tests for => b=0 00297 // if x0 is empty, then b=0 and entailed 00298 // if max(x1) < min(x0.lub) or min(x1) > max(x0.lub), then b=0 and entailed 00299 // if min(x0.glb) < min(x1), then b=0 and entailed 00300 if ((x0.cardMax() == 0) || 00301 ((x1.max() < x0.lubMin()) || (x1.min() > x0.lubMax())) || 00302 ((x0.glbSize() > 0) && (x0.glbMin() < x1.min()))) 00303 { 00304 GECODE_ME_CHECK(b.zero(home)); 00305 return home.ES_SUBSUMED(*this); 00306 } 00307 // if min(x0) is decided 00308 if (x0.glbMin() == x0.lubMin()) { 00309 // if x1 is det: check if = min(x0), assign b, entailed 00310 if (x1.assigned()) { 00311 if (x1.val() == x0.glbMin()) { 00312 GECODE_ME_CHECK(b.one(home)); 00313 } else { 00314 GECODE_ME_CHECK(b.zero(home)); 00315 } 00316 return home.ES_SUBSUMED(*this); 00317 } 00318 // if min(x0) not in dom(x1): b=0, entailed 00319 else if ((x0.glbMin() < x1.min()) || 00320 (x0.glbMin() > x1.max()) || 00321 !x1.in(x0.glbMin())) 00322 { 00323 GECODE_ME_CHECK(b.zero(home)); 00324 return home.ES_SUBSUMED(*this); 00325 } 00326 } 00327 // // if dom(x1) and lub(x0) are disjoint, then b=0, entailed; 00328 // { 00329 // LubRanges<View> ub(x0); 00330 // Gecode::Int::ViewRanges<Gecode::Int::IntView> d(x1); 00331 // Gecode::Iter::Ranges::Inter<LubRanges<View>, 00332 // Gecode::Int::ViewRanges<Gecode::Int::IntView> > ir(ub,d); 00333 // if (!ir()) { 00334 // GECODE_ME_CHECK(b.zero(home)); 00335 // return home.ES_SUBSUMED(*this); 00336 // } 00337 // } 00338 // // x0 is fated to eventually contain at least x0.cardMin elements. 00339 // // therefore min(x0) <= x0.cardMin-th largest element of x0.lub 00340 // // if x1 > than that, then b=0 and entailed. 00341 // { 00342 // // to find the x0.cardMin-th largest element of x0.lub, we need 00343 // // some sort of reverse range iterator. we will need to fake one 00344 // // by storing the ranges of the forward iterator in an array. 00345 // // first we need to know how large the array needs to be. so, let's 00346 // // count the ranges: 00347 // int num_ranges = 0; 00348 // for (LubRanges<View> ur(x0); ur(); ++ur, ++num_ranges) {} 00349 // // create an array for storing min and max of each range 00350 // Region re(home); 00351 // int* _ur = re.alloc<int>(num_ranges*2); 00352 // // now, we fill the array: 00353 // int i = 0; 00354 // for (LubRanges<View> ur(x0); ur(); ++ur, ++i) { 00355 // _ur[2*i ] = ur.min(); 00356 // _ur[2*i+1] = ur.max(); 00357 // } 00358 // // now we search from the top the range that contains the 00359 // // nth largest value. 00360 // int n = x0.cardMin(); 00361 // int nth_largest = BndSet::MAX_OF_EMPTY; 00362 // for (int i=num_ranges; i--; ) { 00363 // // number of values in range 00364 // int num_values = _ur[2*i+1]-_ur[2*i]+1; 00365 // // does the range contain the value? 00366 // if (num_values >= n) 00367 // { 00368 // // record it and exit the loop 00369 // nth_largest = _ur[2*i+1]-n+1; 00370 // break; 00371 // } 00372 // // otherwise, we skipped num_values 00373 // n -= num_values; 00374 // } 00375 // // if x1.min > nth_largest, then entailed 00376 // if (x1.min() > nth_largest) { 00377 // GECODE_ME_CHECK(b.zero(home)); 00378 // return home.ES_SUBSUMED(*this); 00379 // } 00380 // } 00381 return ES_FIX; 00382 } 00383 00384 template<class View> 00385 forceinline 00386 MaxElement<View>::MaxElement(Home home, View y0, Gecode::Int::IntView y1) 00387 : MixBinaryPropagator<View,PC_SET_ANY, 00388 Gecode::Int::IntView,Gecode::Int::PC_INT_BND> (home, y0, y1) {} 00389 00390 template<class View> 00391 forceinline 00392 MaxElement<View>::MaxElement(Space& home, bool share, MaxElement& p) 00393 : MixBinaryPropagator<View,PC_SET_ANY, 00394 Gecode::Int::IntView,Gecode::Int::PC_INT_BND> (home, share, p) {} 00395 00396 template<class View> 00397 ExecStatus 00398 MaxElement<View>::post(Home home, View x0, 00399 Gecode::Int::IntView x1) { 00400 GECODE_ME_CHECK(x0.cardMin(home,1)); 00401 (void) new (home) MaxElement(home,x0,x1); 00402 return ES_OK; 00403 } 00404 00405 template<class View> 00406 Actor* 00407 MaxElement<View>::copy(Space& home, bool share) { 00408 return new (home) MaxElement(home,share,*this); 00409 } 00410 00411 template<class View> 00412 ExecStatus 00413 MaxElement<View>::propagate(Space& home, const ModEventDelta&) { 00414 LubRanges<View> ub(x0); 00415 GECODE_ME_CHECK(x1.inter_r(home,ub,false)); 00416 GECODE_ME_CHECK(x1.gq(home,x0.glbMax())); 00417 assert(x0.cardMin()>=1); 00418 GECODE_ME_CHECK(x1.gq(home,x0.lubMinN(x0.cardMin()-1))); 00419 GECODE_ME_CHECK(x0.exclude(home, 00420 x1.max()+1,Limits::max) ); 00421 00422 if (x1.assigned()) { 00423 GECODE_ME_CHECK(x0.include(home,x1.val())); 00424 GECODE_ME_CHECK( x0.exclude(home, 00425 x1.val()+1,Limits::max) ); 00426 return home.ES_SUBSUMED(*this); 00427 } 00428 00429 return ES_FIX; 00430 } 00431 00432 template<class View> 00433 forceinline 00434 NotMaxElement<View>::NotMaxElement(Home home, View y0, 00435 Gecode::Int::IntView y1) 00436 : MixBinaryPropagator<View,PC_SET_ANY, 00437 Gecode::Int::IntView,Gecode::Int::PC_INT_DOM> (home, y0, y1) {} 00438 00439 template<class View> 00440 forceinline 00441 NotMaxElement<View>::NotMaxElement(Space& home, bool share, 00442 NotMaxElement& p) 00443 : MixBinaryPropagator<View,PC_SET_ANY, 00444 Gecode::Int::IntView,Gecode::Int::PC_INT_DOM> (home, share, p) {} 00445 00446 template<class View> 00447 ExecStatus 00448 NotMaxElement<View>::post(Home home, View x0, Gecode::Int::IntView x1) { 00449 (void) new (home) NotMaxElement(home,x0,x1); 00450 return ES_OK; 00451 } 00452 00453 template<class View> 00454 Actor* 00455 NotMaxElement<View>::copy(Space& home, bool share) { 00456 return new (home) NotMaxElement(home,share,*this); 00457 } 00458 00459 template<class View> 00460 ExecStatus 00461 NotMaxElement<View>::propagate(Space& home, const ModEventDelta&) { 00462 // cheap tests for entailment: 00463 // if x0 is empty, then entailed 00464 // if max(x1) < min(x0.lub) or min(x1) > max(x0.lub), then entailed 00465 // if max(x0.glb) > max(x1), then entailed 00466 if ((x0.cardMax() == 0) || 00467 ((x1.max() < x0.lubMin()) || (x1.min() > x0.lubMax())) || 00468 ((x0.glbSize() > 0) && (x0.glbMax() > x1.max()))) 00469 return home.ES_SUBSUMED(*this); 00470 // if x1 is determined and = max(x0.lub): remove it from x0, 00471 // then entailed 00472 if (x1.assigned() && x1.val()==x0.lubMax()) { 00473 GECODE_ME_CHECK(x0.exclude(home,x1.val())); 00474 return home.ES_SUBSUMED(*this); 00475 } 00476 // if max(x0) is decided: remove max(x0) from the domain of x1 00477 // then entailed 00478 if (x0.glbMax() == x0.lubMax()) { 00479 GECODE_ME_CHECK(x1.nq(home,x0.glbMax())); 00480 return home.ES_SUBSUMED(*this); 00481 } 00482 // if x1 is determined and = max(x0.glb), then we need at least 00483 // one more element; if there is only one above, then we must 00484 // take it. 00485 if (x1.assigned() && x0.glbSize() > 0 && x1.val()==x0.glbMax()) { 00486 unsigned int oldGlbSize = x0.glbSize(); 00487 // if there is only 1 unknown above x1, then we must take it 00488 UnknownRanges<View> ur(x0); 00489 // there is at least one unknown above x1 otherwise it would 00490 // have been caught by the if for x1=max(x0.lub) 00491 while (ur.max() < x1.val()) { 00492 assert(ur()); 00493 ++ur; 00494 }; 00495 // if the first range above x1 contains just 1 element, 00496 // and is the last range, then take that element 00497 if (ur.width() == 1) { 00498 int i = ur.min(); 00499 ++ur; 00500 if (!ur()) { 00501 // last range 00502 GECODE_ME_CHECK(x0.include(home,i)); 00503 return home.ES_SUBSUMED(*this); 00504 } 00505 } 00506 GECODE_ME_CHECK(x0.cardMin(home, oldGlbSize+1)); 00507 } 00508 // if dom(x1) and lub(x0) are disjoint, then entailed 00509 { 00510 LubRanges<View> ub(x0); 00511 Gecode::Int::ViewRanges<Gecode::Int::IntView> d(x1); 00512 Gecode::Iter::Ranges::Inter<LubRanges<View>, 00513 Gecode::Int::ViewRanges<Gecode::Int::IntView> > ir(ub,d); 00514 if (!ir()) return home.ES_SUBSUMED(*this); 00515 } 00516 // x0 is fated to eventually contain at least x0.cardMin elements. 00517 // therefore max(x0) >= x0.cardMin-th smallest element of x0.lub. 00518 // if x1 < than that, then entailed. 00519 { 00520 unsigned int n = x0.cardMin(); 00521 int nth_smallest = BndSet::MIN_OF_EMPTY; 00522 for (LubRanges<View> ur(x0); ur(); ++ur) { 00523 if (ur.width() >= n) { 00524 // record it and exit the loop 00525 nth_smallest = static_cast<int>(ur.min() + n - 1); 00526 break; 00527 } 00528 // otherwise, we skipped ur.width() values 00529 n -= ur.width(); 00530 } 00531 // if x1.max < nth_smallest, then entailed 00532 if (x1.max() < nth_smallest) 00533 return home.ES_SUBSUMED(*this); 00534 } 00535 return ES_FIX; 00536 } 00537 00538 template<class View> 00539 forceinline 00540 ReMaxElement<View>::ReMaxElement(Home home, View y0, Gecode::Int::IntView y1, 00541 Gecode::Int::BoolView b2) 00542 : Gecode::Int::ReMixBinaryPropagator<View,PC_SET_ANY, 00543 Gecode::Int::IntView,Gecode::Int::PC_INT_DOM, 00544 Gecode::Int::BoolView> (home, y0, y1, b2) {} 00545 00546 template<class View> 00547 forceinline 00548 ReMaxElement<View>::ReMaxElement(Space& home, bool share, ReMaxElement& p) 00549 : Gecode::Int::ReMixBinaryPropagator<View,PC_SET_ANY, 00550 Gecode::Int::IntView,Gecode::Int::PC_INT_DOM, 00551 Gecode::Int::BoolView> (home, share, p) {} 00552 00553 template<class View> 00554 ExecStatus 00555 ReMaxElement<View>::post(Home home, View x0, 00556 Gecode::Int::IntView x1, 00557 Gecode::Int::BoolView b2) { 00558 (void) new (home) ReMaxElement(home,x0,x1,b2); 00559 return ES_OK; 00560 } 00561 00562 template<class View> 00563 Actor* 00564 ReMaxElement<View>::copy(Space& home, bool share) { 00565 return new (home) ReMaxElement(home,share,*this); 00566 } 00567 00568 template<class View> 00569 ExecStatus 00570 ReMaxElement<View>::propagate(Space& home, const ModEventDelta&) { 00571 // check if b is determined 00572 if (b.one()) 00573 GECODE_REWRITE(*this, (MaxElement<View>::post(home(*this),x0,x1))); 00574 if (b.zero()) 00575 GECODE_REWRITE(*this, (NotMaxElement<View>::post(home(*this),x0,x1))); 00576 // cheap tests for => b=0 00577 // if x0 is empty, then b=0 and entailed 00578 // if max(x1) < min(x0.lub) or min(x1) > max(x0.lub), then b=0 and entailed 00579 // if max(x0.glb) > max(x1), then b=0 and entailed 00580 if ((x0.cardMax() == 0) || 00581 ((x1.max() < x0.lubMin()) || (x1.min() > x0.lubMax())) || 00582 ((x0.glbSize() > 0) && (x0.glbMax() > x1.max()))) 00583 { 00584 GECODE_ME_CHECK(b.zero(home)); 00585 return home.ES_SUBSUMED(*this); 00586 } 00587 // if max(x0) is decided 00588 if (x0.glbMax() == x0.lubMax()) { 00589 // if x1 is det: check if = max(x0), assign b, entailed 00590 if (x1.assigned()) { 00591 if (x1.val() == x0.glbMax()) { 00592 GECODE_ME_CHECK(b.one(home)); 00593 } else { 00594 GECODE_ME_CHECK(b.zero(home)); 00595 } 00596 return home.ES_SUBSUMED(*this); 00597 } 00598 // if max(x0) not in dom(x1): b=0, entailed 00599 else if ((x0.glbMax() < x1.min()) || 00600 (x0.glbMax() > x1.max()) || 00601 !x1.in(x0.glbMax())) 00602 { 00603 GECODE_ME_CHECK(b.zero(home)); 00604 return home.ES_SUBSUMED(*this); 00605 } 00606 } 00607 // if dom(x1) and lub(x0) are disjoint, then b=0, entailed 00608 { 00609 LubRanges<View> ub(x0); 00610 Gecode::Int::ViewRanges<Gecode::Int::IntView> d(x1); 00611 Gecode::Iter::Ranges::Inter<LubRanges<View>, 00612 Gecode::Int::ViewRanges<Gecode::Int::IntView> > ir(ub,d); 00613 if (!ir()) { 00614 GECODE_ME_CHECK(b.zero(home)); 00615 return home.ES_SUBSUMED(*this); 00616 } 00617 } 00618 // x0 is fated to eventually contain at least x0.cardMin elements. 00619 // therefore max(x0) >= x0.cardMin-th smallest element of x0.lub. 00620 // if x1 < than that, then b=0, entailed. 00621 { 00622 unsigned int n = x0.cardMin(); 00623 int nth_smallest = BndSet::MIN_OF_EMPTY; 00624 for (LubRanges<View> ur(x0); ur(); ++ur) { 00625 if (ur.width() >= n) 00626 { 00627 // record it and exit the loop 00628 nth_smallest = static_cast<int>(ur.min() + n - 1); 00629 break; 00630 } 00631 // otherwise, we skipped ur.width() values 00632 n -= ur.width(); 00633 } 00634 // if x1.max < nth_smallest, then entailed 00635 if (x1.max() < nth_smallest) { 00636 GECODE_ME_CHECK(b.zero(home)); 00637 return home.ES_SUBSUMED(*this); 00638 } 00639 } 00640 return ES_FIX; 00641 } 00642 00643 }}} 00644 00645 // STATISTICS: set-prop