int-bin.hpp
Go to the documentation of this file.
00001 /* -*- mode: C++; c-basic-offset: 2; indent-tabs-mode: nil -*- */ 00002 /* 00003 * Main authors: 00004 * Christian Schulte <schulte@gecode.org> 00005 * 00006 * Copyright: 00007 * Christian Schulte, 2003 00008 * 00009 * Last modified: 00010 * $Date: 2010-03-03 17:32:21 +0100 (Wed, 03 Mar 2010) $ by $Author: schulte $ 00011 * $Revision: 10364 $ 00012 * 00013 * This file is part of Gecode, the generic constraint 00014 * development environment: 00015 * http://www.gecode.org 00016 * 00017 * Permission is hereby granted, free of charge, to any person obtaining 00018 * a copy of this software and associated documentation files (the 00019 * "Software"), to deal in the Software without restriction, including 00020 * without limitation the rights to use, copy, modify, merge, publish, 00021 * distribute, sublicense, and/or sell copies of the Software, and to 00022 * permit persons to whom the Software is furnished to do so, subject to 00023 * the following conditions: 00024 * 00025 * The above copyright notice and this permission notice shall be 00026 * included in all copies or substantial portions of the Software. 00027 * 00028 * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, 00029 * EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF 00030 * MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND 00031 * NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE 00032 * LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION 00033 * OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION 00034 * WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE. 00035 * 00036 */ 00037 00038 namespace Gecode { namespace Int { namespace Linear { 00039 00040 /* 00041 * Binary linear propagators 00042 * 00043 */ 00044 template<class Val, class A, class B, PropCond pc> 00045 forceinline 00046 LinBin<Val,A,B,pc>::LinBin(Home home, A y0, B y1, Val c0) 00047 : Propagator(home), x0(y0), x1(y1), c(c0) { 00048 x0.subscribe(home,*this,pc); 00049 x1.subscribe(home,*this,pc); 00050 } 00051 00052 template<class Val, class A, class B, PropCond pc> 00053 forceinline 00054 LinBin<Val,A,B,pc>::LinBin(Space& home, bool share, LinBin<Val,A,B,pc>& p) 00055 : Propagator(home,share,p), c(p.c) { 00056 x0.update(home,share,p.x0); 00057 x1.update(home,share,p.x1); 00058 } 00059 00060 template<class Val, class A, class B, PropCond pc> 00061 forceinline 00062 LinBin<Val,A,B,pc>::LinBin(Space& home, bool share, Propagator& p, 00063 A y0, B y1, Val c0) 00064 : Propagator(home,share,p), c(c0) { 00065 x0.update(home,share,y0); 00066 x1.update(home,share,y1); 00067 } 00068 00069 template<class Val, class A, class B, PropCond pc> 00070 PropCost 00071 LinBin<Val,A,B,pc>::cost(const Space&, const ModEventDelta&) const { 00072 return PropCost::binary(PropCost::LO); 00073 } 00074 00075 template<class Val, class A, class B, PropCond pc> 00076 forceinline size_t 00077 LinBin<Val,A,B,pc>::dispose(Space& home) { 00078 x0.cancel(home,*this,pc); 00079 x1.cancel(home,*this,pc); 00080 (void) Propagator::dispose(home); 00081 return sizeof(*this); 00082 } 00083 00084 00085 /* 00086 * Binary reified linear propagators 00087 * 00088 */ 00089 template<class Val, class A, class B, PropCond pc, class Ctrl> 00090 forceinline 00091 ReLinBin<Val,A,B,pc,Ctrl>::ReLinBin(Home home, A y0, B y1, Val c0, Ctrl b0) 00092 : Propagator(home), x0(y0), x1(y1), c(c0), b(b0) { 00093 x0.subscribe(home,*this,pc); 00094 x1.subscribe(home,*this,pc); 00095 b.subscribe(home,*this,PC_INT_VAL); 00096 } 00097 00098 template<class Val, class A, class B, PropCond pc, class Ctrl> 00099 forceinline 00100 ReLinBin<Val,A,B,pc,Ctrl>::ReLinBin(Space& home, bool share, 00101 ReLinBin<Val,A,B,pc,Ctrl>& p) 00102 : Propagator(home,share,p), c(p.c) { 00103 x0.update(home,share,p.x0); 00104 x1.update(home,share,p.x1); 00105 b.update(home,share,p.b); 00106 } 00107 00108 template<class Val, class A, class B, PropCond pc, class Ctrl> 00109 PropCost 00110 ReLinBin<Val,A,B,pc,Ctrl>::cost(const Space&, const ModEventDelta&) const { 00111 return PropCost::binary(PropCost::LO); 00112 } 00113 00114 template<class Val, class A, class B, PropCond pc, class Ctrl> 00115 forceinline size_t 00116 ReLinBin<Val,A,B,pc,Ctrl>::dispose(Space& home) { 00117 x0.cancel(home,*this,pc); 00118 x1.cancel(home,*this,pc); 00119 b.cancel(home,*this,PC_BOOL_VAL); 00120 (void) Propagator::dispose(home); 00121 return sizeof(*this); 00122 } 00123 00124 /* 00125 * Binary bounds consistent linear equality 00126 * 00127 */ 00128 00129 template<class Val, class A, class B> 00130 forceinline 00131 EqBin<Val,A,B>::EqBin(Home home, A x0, B x1, Val c) 00132 : LinBin<Val,A,B,PC_INT_BND>(home,x0,x1,c) {} 00133 00134 template<class Val, class A, class B> 00135 ExecStatus 00136 EqBin<Val,A,B>::post(Home home, A x0, B x1, Val c) { 00137 (void) new (home) EqBin<Val,A,B>(home,x0,x1,c); 00138 return ES_OK; 00139 } 00140 00141 00142 template<class Val, class A, class B> 00143 forceinline 00144 EqBin<Val,A,B>::EqBin(Space& home, bool share, EqBin<Val,A,B>& p) 00145 : LinBin<Val,A,B,PC_INT_BND>(home,share,p) {} 00146 00147 template<class Val, class A, class B> 00148 forceinline 00149 EqBin<Val,A,B>::EqBin(Space& home, bool share, Propagator& p, 00150 A x0, B x1, Val c) 00151 : LinBin<Val,A,B,PC_INT_BND>(home,share,p,x0,x1,c) {} 00152 00153 template<class Val, class A, class B> 00154 Actor* 00155 EqBin<Val,A,B>::copy(Space& home, bool share) { 00156 return new (home) EqBin<Val,A,B>(home,share,*this); 00157 } 00158 00160 enum BinMod { 00161 BM_X0_MIN = 1<<0, 00162 BM_X0_MAX = 1<<1, 00163 BM_X1_MIN = 1<<2, 00164 BM_X1_MAX = 1<<3, 00165 BM_ALL = BM_X0_MIN|BM_X0_MAX|BM_X1_MIN|BM_X1_MAX 00166 }; 00167 00168 #define GECODE_INT_PV(CASE,TELL,UPDATE) \ 00169 if (bm & (CASE)) { \ 00170 bm -= (CASE); ModEvent me = (TELL); \ 00171 if (me_failed(me)) return ES_FAILED; \ 00172 if (me_modified(me)) bm |= (UPDATE); \ 00173 } 00174 00175 template<class Val, class A, class B> 00176 ExecStatus 00177 EqBin<Val,A,B>::propagate(Space& home, const ModEventDelta&) { 00178 int bm = BM_ALL; 00179 do { 00180 GECODE_INT_PV(BM_X0_MIN, x0.gq(home,c-x1.max()), BM_X1_MAX); 00181 GECODE_INT_PV(BM_X1_MIN, x1.gq(home,c-x0.max()), BM_X0_MAX); 00182 GECODE_INT_PV(BM_X0_MAX, x0.lq(home,c-x1.min()), BM_X1_MIN); 00183 GECODE_INT_PV(BM_X1_MAX, x1.lq(home,c-x0.min()), BM_X0_MIN); 00184 } while (bm); 00185 return x0.assigned() ? home.ES_SUBSUMED(*this) : ES_FIX; 00186 } 00187 00188 #undef GECODE_INT_PV 00189 00190 00191 00192 00193 00194 /* 00195 * Reified binary bounds consistent linear equality 00196 * 00197 */ 00198 00199 template<class Val, class A, class B, class Ctrl> 00200 forceinline 00201 ReEqBin<Val,A,B,Ctrl>::ReEqBin(Home home, A x0, B x1, Val c, Ctrl b) 00202 : ReLinBin<Val,A,B,PC_INT_BND,Ctrl>(home,x0,x1,c,b) {} 00203 00204 template<class Val, class A, class B, class Ctrl> 00205 ExecStatus 00206 ReEqBin<Val,A,B,Ctrl>::post(Home home, A x0, B x1, Val c, Ctrl b) { 00207 (void) new (home) ReEqBin<Val,A,B,Ctrl>(home,x0,x1,c,b); 00208 return ES_OK; 00209 } 00210 00211 00212 template<class Val, class A, class B, class Ctrl> 00213 forceinline 00214 ReEqBin<Val,A,B,Ctrl>::ReEqBin(Space& home, bool share, 00215 ReEqBin<Val,A,B,Ctrl>& p) 00216 : ReLinBin<Val,A,B,PC_INT_BND,Ctrl>(home,share,p) {} 00217 00218 template<class Val, class A, class B, class Ctrl> 00219 Actor* 00220 ReEqBin<Val,A,B,Ctrl>::copy(Space& home, bool share) { 00221 return new (home) ReEqBin<Val,A,B,Ctrl>(home,share,*this); 00222 } 00223 00224 template<class Val, class A, class B, class Ctrl> 00225 ExecStatus 00226 ReEqBin<Val,A,B,Ctrl>::propagate(Space& home, const ModEventDelta&) { 00227 if (b.zero()) 00228 GECODE_REWRITE(*this,(NqBin<Val,A,B>::post(home(*this),x0,x1,c))); 00229 if (b.one()) 00230 GECODE_REWRITE(*this,(EqBin<Val,A,B>::post(home(*this),x0,x1,c))); 00231 if ((x0.min() + x1.min() > c) || (x0.max() + x1.max() < c)) { 00232 GECODE_ME_CHECK(b.zero_none(home)); return home.ES_SUBSUMED(*this); 00233 } 00234 if (x0.assigned() && x1.assigned()) { 00235 assert(x0.val() + x1.val() == c); 00236 GECODE_ME_CHECK(b.one_none(home)); return home.ES_SUBSUMED(*this); 00237 } 00238 return ES_FIX; 00239 } 00240 00241 00242 00243 00244 /* 00245 * Binary domain consistent linear disequality 00246 * 00247 */ 00248 template<class Val, class A, class B> 00249 forceinline 00250 NqBin<Val,A,B>::NqBin(Home home, A x0, B x1, Val c) 00251 : LinBin<Val,A,B,PC_INT_VAL>(home,x0,x1,c) {} 00252 00253 template<class Val, class A, class B> 00254 ExecStatus 00255 NqBin<Val,A,B>::post(Home home, A x0, B x1, Val c) { 00256 (void) new (home) NqBin<Val,A,B>(home,x0,x1,c); 00257 return ES_OK; 00258 } 00259 00260 00261 template<class Val, class A, class B> 00262 forceinline 00263 NqBin<Val,A,B>::NqBin(Space& home, bool share, NqBin<Val,A,B>& p) 00264 : LinBin<Val,A,B,PC_INT_VAL>(home,share,p) {} 00265 00266 template<class Val, class A, class B> 00267 Actor* 00268 NqBin<Val,A,B>::copy(Space& home, bool share) { 00269 return new (home) NqBin<Val,A,B>(home,share,*this); 00270 } 00271 00272 template<class Val, class A, class B> 00273 forceinline 00274 NqBin<Val,A,B>::NqBin(Space& home, bool share, Propagator& p, 00275 A x0, B x1, Val c) 00276 : LinBin<Val,A,B,PC_INT_VAL>(home,share,p,x0,x1,c) {} 00277 00278 00279 00280 template<class Val, class A, class B> 00281 PropCost 00282 NqBin<Val,A,B>::cost(const Space&, const ModEventDelta&) const { 00283 return PropCost::unary(PropCost::LO); 00284 } 00285 00286 template<class Val, class A, class B> 00287 ExecStatus 00288 NqBin<Val,A,B>::propagate(Space& home, const ModEventDelta&) { 00289 if (x0.assigned()) { 00290 GECODE_ME_CHECK(x1.nq(home,c-x0.val())); 00291 } else { 00292 assert(x1.assigned()); 00293 GECODE_ME_CHECK(x0.nq(home,c-x1.val())); 00294 } 00295 return home.ES_SUBSUMED(*this); 00296 } 00297 00298 00299 /* 00300 * Binary domain consistent less equal 00301 * 00302 */ 00303 00304 template<class Val, class A, class B> 00305 forceinline 00306 LqBin<Val,A,B>::LqBin(Home home, A x0, B x1, Val c) 00307 : LinBin<Val,A,B,PC_INT_BND>(home,x0,x1,c) {} 00308 00309 template<class Val, class A, class B> 00310 ExecStatus 00311 LqBin<Val,A,B>::post(Home home, A x0, B x1, Val c) { 00312 (void) new (home) LqBin<Val,A,B>(home,x0,x1,c); 00313 return ES_OK; 00314 } 00315 00316 00317 template<class Val, class A, class B> 00318 forceinline 00319 LqBin<Val,A,B>::LqBin(Space& home, bool share, LqBin<Val,A,B>& p) 00320 : LinBin<Val,A,B,PC_INT_BND>(home,share,p) {} 00321 00322 template<class Val, class A, class B> 00323 Actor* 00324 LqBin<Val,A,B>::copy(Space& home, bool share) { 00325 return new (home) LqBin<Val,A,B>(home,share,*this); 00326 } 00327 00328 template<class Val, class A, class B> 00329 forceinline 00330 LqBin<Val,A,B>::LqBin(Space& home, bool share, Propagator& p, 00331 A x0, B x1, Val c) 00332 : LinBin<Val,A,B,PC_INT_BND>(home,share,p,x0,x1,c) {} 00333 00334 template<class Val, class A, class B> 00335 ExecStatus 00336 LqBin<Val,A,B>::propagate(Space& home, const ModEventDelta&) { 00337 GECODE_ME_CHECK(x0.lq(home,c-x1.min())); 00338 GECODE_ME_CHECK(x1.lq(home,c-x0.min())); 00339 return (x0.max()+x1.max() <= c) ? home.ES_SUBSUMED(*this) : ES_FIX; 00340 } 00341 00342 00343 00344 00345 /* 00346 * Binary domain consistent greater equal 00347 * 00348 */ 00349 00350 template<class Val, class A, class B> 00351 forceinline 00352 GqBin<Val,A,B>::GqBin(Home home, A x0, B x1, Val c) 00353 : LinBin<Val,A,B,PC_INT_BND>(home,x0,x1,c) {} 00354 00355 template<class Val, class A, class B> 00356 ExecStatus 00357 GqBin<Val,A,B>::post(Home home, A x0, B x1, Val c) { 00358 (void) new (home) GqBin<Val,A,B>(home,x0,x1,c); 00359 return ES_OK; 00360 } 00361 00362 00363 template<class Val, class A, class B> 00364 forceinline 00365 GqBin<Val,A,B>::GqBin(Space& home, bool share, GqBin<Val,A,B>& p) 00366 : LinBin<Val,A,B,PC_INT_BND>(home,share,p) {} 00367 00368 template<class Val, class A, class B> 00369 Actor* 00370 GqBin<Val,A,B>::copy(Space& home, bool share) { 00371 return new (home) GqBin<Val,A,B>(home,share,*this); 00372 } 00373 00374 template<class Val, class A, class B> 00375 forceinline 00376 GqBin<Val,A,B>::GqBin(Space& home, bool share, Propagator& p, 00377 A x0, B x1, Val c) 00378 : LinBin<Val,A,B,PC_INT_BND>(home,share,p,x0,x1,c) {} 00379 00380 template<class Val, class A, class B> 00381 ExecStatus 00382 GqBin<Val,A,B>::propagate(Space& home, const ModEventDelta&) { 00383 GECODE_ME_CHECK(x0.gq(home,c-x1.max())); 00384 GECODE_ME_CHECK(x1.gq(home,c-x0.max())); 00385 return (x0.min()+x1.min() >= c) ? home.ES_SUBSUMED(*this) : ES_FIX; 00386 } 00387 00388 00389 00390 00391 /* 00392 * Reified binary domain consistent less equal 00393 * 00394 */ 00395 00396 template<class Val, class A, class B> 00397 forceinline 00398 ReLqBin<Val,A,B>::ReLqBin(Home home, A x0, B x1, Val c, BoolView b) 00399 : ReLinBin<Val,A,B,PC_INT_BND,BoolView>(home,x0,x1,c,b) {} 00400 00401 template<class Val, class A, class B> 00402 ExecStatus 00403 ReLqBin<Val,A,B>::post(Home home, A x0, B x1, Val c, BoolView b) { 00404 (void) new (home) ReLqBin<Val,A,B>(home,x0,x1,c,b); 00405 return ES_OK; 00406 } 00407 00408 00409 template<class Val, class A, class B> 00410 forceinline 00411 ReLqBin<Val,A,B>::ReLqBin(Space& home, bool share, ReLqBin<Val,A,B>& p) 00412 : ReLinBin<Val,A,B,PC_INT_BND,BoolView>(home,share,p) {} 00413 00414 template<class Val, class A, class B> 00415 Actor* 00416 ReLqBin<Val,A,B>::copy(Space& home, bool share) { 00417 return new (home) ReLqBin<Val,A,B>(home,share,*this); 00418 } 00419 00420 template<class Val, class A, class B> 00421 ExecStatus 00422 ReLqBin<Val,A,B>::propagate(Space& home, const ModEventDelta&) { 00423 if (b.one()) 00424 GECODE_REWRITE(*this,(LqBin<Val,A,B>::post(home(*this),x0,x1,c))); 00425 if (b.zero()) 00426 GECODE_REWRITE(*this,(GqBin<Val,A,B>::post(home(*this),x0,x1,c+1))); 00427 if (x0.max() + x1.max() <= c) { 00428 GECODE_ME_CHECK(b.one_none(home)); return home.ES_SUBSUMED(*this); 00429 } 00430 if (x0.min() + x1.min() > c) { 00431 GECODE_ME_CHECK(b.zero_none(home)); return home.ES_SUBSUMED(*this); 00432 } 00433 return ES_FIX; 00434 } 00435 00436 }}} 00437 00438 // STATISTICS: int-prop 00439