int-ter.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 * Ternary linear propagators 00042 * 00043 */ 00044 template<class Val, class A, class B, class C, PropCond pc> 00045 forceinline 00046 LinTer<Val,A,B,C,pc>::LinTer(Home home, A y0, B y1, C y2, Val c0) 00047 : Propagator(home), x0(y0), x1(y1), x2(y2), c(c0) { 00048 x0.subscribe(home,*this,pc); 00049 x1.subscribe(home,*this,pc); 00050 x2.subscribe(home,*this,pc); 00051 } 00052 00053 template<class Val, class A, class B, class C, PropCond pc> 00054 forceinline 00055 LinTer<Val,A,B,C,pc>::LinTer(Space& home, bool share, 00056 LinTer<Val,A,B,C,pc>& p) 00057 : Propagator(home,share,p), c(p.c) { 00058 x0.update(home,share,p.x0); 00059 x1.update(home,share,p.x1); 00060 x2.update(home,share,p.x2); 00061 } 00062 00063 template<class Val, class A, class B, class C, PropCond pc> 00064 forceinline 00065 LinTer<Val,A,B,C,pc>::LinTer(Space& home, bool share, Propagator& p, 00066 A y0, B y1, C y2, Val c0) 00067 : Propagator(home,share,p), c(c0) { 00068 x0.update(home,share,y0); 00069 x1.update(home,share,y1); 00070 x2.update(home,share,y2); 00071 } 00072 00073 template<class Val, class A, class B, class C, PropCond pc> 00074 PropCost 00075 LinTer<Val,A,B,C,pc>::cost(const Space&, const ModEventDelta&) const { 00076 return PropCost::ternary(PropCost::LO); 00077 } 00078 00079 template<class Val, class A, class B, class C, PropCond pc> 00080 forceinline size_t 00081 LinTer<Val,A,B,C,pc>::dispose(Space& home) { 00082 x0.cancel(home,*this,pc); 00083 x1.cancel(home,*this,pc); 00084 x2.cancel(home,*this,pc); 00085 (void) Propagator::dispose(home); 00086 return sizeof(*this); 00087 } 00088 00089 /* 00090 * Equality propagator 00091 * 00092 */ 00093 00094 template<class Val, class A, class B, class C> 00095 forceinline 00096 EqTer<Val,A,B,C>::EqTer(Home home, A x0, B x1, C x2, Val c) 00097 : LinTer<Val,A,B,C,PC_INT_BND>(home,x0,x1,x2,c) {} 00098 00099 template<class Val, class A, class B, class C> 00100 ExecStatus 00101 EqTer<Val,A,B,C>::post(Home home, A x0, B x1, C x2, Val c) { 00102 (void) new (home) EqTer<Val,A,B,C>(home,x0,x1,x2,c); 00103 return ES_OK; 00104 } 00105 00106 00107 template<class Val, class A, class B, class C> 00108 forceinline 00109 EqTer<Val,A,B,C>::EqTer(Space& home, bool share, EqTer<Val,A,B,C>& p) 00110 : LinTer<Val,A,B,C,PC_INT_BND>(home,share,p) {} 00111 00112 template<class Val, class A, class B, class C> 00113 forceinline 00114 EqTer<Val,A,B,C>::EqTer(Space& home, bool share, Propagator& p, 00115 A x0, B x1, C x2, Val c) 00116 : LinTer<Val,A,B,C,PC_INT_BND>(home,share,p,x0,x1,x2,c) {} 00117 00118 template<class Val, class A, class B, class C> 00119 Actor* 00120 EqTer<Val,A,B,C>::copy(Space& home, bool share) { 00121 return new (home) EqTer<Val,A,B,C>(home,share,*this); 00122 } 00123 00125 enum TerMod { 00126 TM_X0_MIN = 1<<0, 00127 TM_X0_MAX = 1<<1, 00128 TM_X1_MIN = 1<<2, 00129 TM_X1_MAX = 1<<3, 00130 TM_X2_MIN = 1<<4, 00131 TM_X2_MAX = 1<<5, 00132 TM_ALL = TM_X0_MIN|TM_X0_MAX|TM_X1_MIN|TM_X1_MAX|TM_X2_MIN|TM_X2_MAX 00133 }; 00134 00135 #define GECODE_INT_PV(CASE,TELL,UPDATE) \ 00136 if (bm & (CASE)) { \ 00137 bm -= (CASE); ModEvent me = (TELL); \ 00138 if (me_failed(me)) return ES_FAILED; \ 00139 if (me_modified(me)) bm |= (UPDATE); \ 00140 } 00141 00142 template<class Val, class A, class B, class C> 00143 ExecStatus 00144 EqTer<Val,A,B,C>::propagate(Space& home, const ModEventDelta&) { 00145 int bm = TM_ALL; 00146 do { 00147 GECODE_INT_PV(TM_X0_MIN, x0.gq(home,c-x1.max()-x2.max()), 00148 TM_X1_MAX | TM_X2_MAX); 00149 GECODE_INT_PV(TM_X1_MIN, x1.gq(home,c-x0.max()-x2.max()), 00150 TM_X0_MAX | TM_X2_MAX); 00151 GECODE_INT_PV(TM_X2_MIN, x2.gq(home,c-x0.max()-x1.max()), 00152 TM_X0_MAX | TM_X1_MAX); 00153 GECODE_INT_PV(TM_X0_MAX, x0.lq(home,c-x1.min()-x2.min()), 00154 TM_X1_MIN | TM_X2_MIN); 00155 GECODE_INT_PV(TM_X1_MAX, x1.lq(home,c-x0.min()-x2.min()), 00156 TM_X0_MIN | TM_X2_MIN); 00157 GECODE_INT_PV(TM_X2_MAX, x2.lq(home,c-x0.min()-x1.min()), 00158 TM_X0_MIN | TM_X1_MIN); 00159 } while (bm); 00160 return (x0.assigned() && x1.assigned()) ? 00161 home.ES_SUBSUMED(*this) : ES_FIX; 00162 } 00163 00164 #undef GECODE_INT_PV 00165 00166 00167 00168 /* 00169 * Disequality propagator 00170 * 00171 */ 00172 00173 template<class Val, class A, class B, class C> 00174 forceinline 00175 NqTer<Val,A,B,C>::NqTer(Home home, A x0, B x1, C x2, Val c) 00176 : LinTer<Val,A,B,C,PC_INT_VAL>(home,x0,x1,x2,c) {} 00177 00178 template<class Val, class A, class B, class C> 00179 ExecStatus 00180 NqTer<Val,A,B,C>::post(Home home, A x0, B x1, C x2, Val c) { 00181 (void) new (home) NqTer<Val,A,B,C>(home,x0,x1,x2,c); 00182 return ES_OK; 00183 } 00184 00185 00186 template<class Val, class A, class B, class C> 00187 forceinline 00188 NqTer<Val,A,B,C>::NqTer(Space& home, bool share, NqTer<Val,A,B,C>& p) 00189 : LinTer<Val,A,B,C,PC_INT_VAL>(home,share,p) {} 00190 00191 template<class Val, class A, class B, class C> 00192 Actor* 00193 NqTer<Val,A,B,C>::copy(Space& home, bool share) { 00194 return new (home) NqTer<Val,A,B,C>(home,share,*this); 00195 } 00196 00197 template<class Val, class A, class B, class C> 00198 forceinline 00199 NqTer<Val,A,B,C>::NqTer(Space& home, bool share, Propagator& p, 00200 A x0, B x1, C x2, Val c) 00201 : LinTer<Val,A,B,C,PC_INT_VAL>(home,share,p,x0,x1,x2,c) {} 00202 00203 00204 template<class Val, class A, class B, class C> 00205 ExecStatus 00206 NqTer<Val,A,B,C>::propagate(Space& home, const ModEventDelta&) { 00207 if (x0.assigned() && x1.assigned()) { 00208 GECODE_ME_CHECK(x2.nq(home,c-x0.val()-x1.val())); 00209 return home.ES_SUBSUMED(*this); 00210 } 00211 if (x0.assigned() && x2.assigned()) { 00212 GECODE_ME_CHECK(x1.nq(home,c-x0.val()-x2.val())); 00213 return home.ES_SUBSUMED(*this); 00214 } 00215 if (x1.assigned() && x2.assigned()) { 00216 GECODE_ME_CHECK(x0.nq(home,c-x1.val()-x2.val())); 00217 return home.ES_SUBSUMED(*this); 00218 } 00219 return ES_FIX; 00220 } 00221 00222 00223 00224 /* 00225 * Inequality propagator 00226 * 00227 */ 00228 00229 template<class Val, class A, class B, class C> 00230 forceinline 00231 LqTer<Val,A,B,C>::LqTer(Home home, A x0, B x1, C x2, Val c) 00232 : LinTer<Val,A,B,C,PC_INT_BND>(home,x0,x1,x2,c) {} 00233 00234 template<class Val, class A, class B, class C> 00235 ExecStatus 00236 LqTer<Val,A,B,C>::post(Home home, A x0, B x1, C x2, Val c) { 00237 (void) new (home) LqTer<Val,A,B,C>(home,x0,x1,x2,c); 00238 return ES_OK; 00239 } 00240 00241 00242 template<class Val, class A, class B, class C> 00243 forceinline 00244 LqTer<Val,A,B,C>::LqTer(Space& home, bool share, LqTer<Val,A,B,C>& p) 00245 : LinTer<Val,A,B,C,PC_INT_BND>(home,share,p) {} 00246 00247 template<class Val, class A, class B, class C> 00248 Actor* 00249 LqTer<Val,A,B,C>::copy(Space& home, bool share) { 00250 return new (home) LqTer<Val,A,B,C>(home,share,*this); 00251 } 00252 00253 00254 template<class Val, class A, class B, class C> 00255 forceinline 00256 LqTer<Val,A,B,C>::LqTer(Space& home, bool share, Propagator& p, 00257 A x0, B x1, C x2, Val c) 00258 : LinTer<Val,A,B,C,PC_INT_BND>(home,share,p,x0,x1,x2,c) {} 00259 00260 template<class Val, class A, class B, class C> 00261 ExecStatus 00262 LqTer<Val,A,B,C>::propagate(Space& home, const ModEventDelta&) { 00263 GECODE_ME_CHECK(x0.lq(home,c-x1.min()-x2.min())); 00264 GECODE_ME_CHECK(x1.lq(home,c-x0.min()-x2.min())); 00265 GECODE_ME_CHECK(x2.lq(home,c-x0.min()-x1.min())); 00266 return (x0.max()+x1.max()+x2.max() <= c) ? 00267 home.ES_SUBSUMED(*this) : ES_FIX; 00268 } 00269 00270 }}} 00271 00272 // STATISTICS: int-prop 00273