bool-view.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, 2004 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 * Base-class 00042 * 00043 */ 00044 template<class XV, class YV> 00045 LinBoolView<XV,YV>::LinBoolView(Home home, 00046 ViewArray<XV>& x0, YV y0, int c0) 00047 : Propagator(home), x(x0), y(y0), c(c0) { 00048 x.subscribe(home,*this,PC_INT_VAL); 00049 y.subscribe(home,*this,PC_INT_BND); 00050 } 00051 00052 template<class XV, class YV> 00053 forceinline size_t 00054 LinBoolView<XV,YV>::dispose(Space& home) { 00055 x.cancel(home,*this,PC_INT_VAL); 00056 y.cancel(home,*this,PC_INT_BND); 00057 (void) Propagator::dispose(home); 00058 return sizeof(*this); 00059 } 00060 00061 template<class XV, class YV> 00062 forceinline 00063 LinBoolView<XV,YV>::LinBoolView(Space& home, bool share, LinBoolView& p) 00064 : Propagator(home,share,p), c(p.c) { 00065 x.update(home,share,p.x); 00066 y.update(home,share,p.y); 00067 } 00068 00069 template<class XV, class YV> 00070 PropCost 00071 LinBoolView<XV,YV>::cost(const Space&, const ModEventDelta&) const { 00072 return PropCost::linear(PropCost::LO, x.size()); 00073 } 00074 00075 00076 /* 00077 * Equality propagator 00078 * 00079 */ 00080 template<class XV, class YV> 00081 forceinline 00082 EqBoolView<XV,YV>::EqBoolView(Home home, ViewArray<XV>& x, YV y, int c) 00083 : LinBoolView<XV,YV>(home,x,y,c) {} 00084 00085 template<class XV, class YV> 00086 ExecStatus 00087 EqBoolView<XV,YV>::post(Home home, ViewArray<XV>& x, YV y, int c) { 00088 if (y.assigned()) 00089 return EqBoolInt<XV>::post(home,x,y.val()+c); 00090 int n = x.size(); 00091 for (int i = n; i--; ) 00092 if (x[i].one()) { 00093 x[i]=x[--n]; c--; 00094 } else if (x[i].zero()) { 00095 x[i]=x[--n]; 00096 } 00097 x.size(n); 00098 GECODE_ME_CHECK(y.lq(home,n-c)); 00099 GECODE_ME_CHECK(y.gq(home,-c)); 00100 if (n == 0) 00101 return ES_OK; 00102 if (y.min()+c == n) { 00103 assert(y.assigned()); 00104 for (int i = n; i--; ) 00105 GECODE_ME_CHECK(x[i].one_none(home)); 00106 return ES_OK; 00107 } 00108 if (y.max()+c == 0) { 00109 assert(y.assigned()); 00110 for (int i = n; i--; ) 00111 GECODE_ME_CHECK(x[i].zero_none(home)); 00112 return ES_OK; 00113 } 00114 (void) new (home) EqBoolView<XV,YV>(home,x,y,c); 00115 return ES_OK; 00116 } 00117 00118 template<class XV, class YV> 00119 forceinline 00120 EqBoolView<XV,YV>::EqBoolView(Space& home, bool share, EqBoolView<XV,YV>& p) 00121 : LinBoolView<XV,YV>(home,share,p) {} 00122 00123 template<class XV, class YV> 00124 Actor* 00125 EqBoolView<XV,YV>::copy(Space& home, bool share) { 00126 return new (home) EqBoolView<XV,YV>(home,share,*this); 00127 } 00128 00129 template<class XV, class YV> 00130 ExecStatus 00131 EqBoolView<XV,YV>::propagate(Space& home, const ModEventDelta&) { 00132 int n = x.size(); 00133 for (int i = n; i--; ) 00134 if (x[i].one()) { 00135 x[i]=x[--n]; c--; 00136 } else if (x[i].zero()) { 00137 x[i]=x[--n]; 00138 } 00139 x.size(n); 00140 GECODE_ME_CHECK(y.lq(home,n-c)); 00141 GECODE_ME_CHECK(y.gq(home,-c)); 00142 if (n == 0) 00143 return home.ES_SUBSUMED(*this); 00144 if (y.min()+c == n) { 00145 assert(y.assigned()); 00146 for (int i = n; i--; ) 00147 GECODE_ME_CHECK(x[i].one_none(home)); 00148 return home.ES_SUBSUMED(*this); 00149 } 00150 if (y.max()+c == 0) { 00151 assert(y.assigned()); 00152 for (int i = n; i--; ) 00153 GECODE_ME_CHECK(x[i].zero_none(home)); 00154 return home.ES_SUBSUMED(*this); 00155 } 00156 if (y.assigned()) 00157 GECODE_REWRITE(*this,EqBoolInt<XV>::post(home(*this),x,y.val()+c)); 00158 return ES_FIX; 00159 } 00160 00161 00162 /* 00163 * Disequality propagator 00164 * 00165 */ 00166 template<class XV, class YV> 00167 forceinline 00168 NqBoolView<XV,YV>::NqBoolView(Home home, ViewArray<XV>& x, YV y, int c) 00169 : LinBoolView<XV,YV>(home,x,y,c) {} 00170 00171 template<class XV, class YV> 00172 ExecStatus 00173 NqBoolView<XV,YV>::post(Home home, ViewArray<XV>& x, YV y, int c) { 00174 if (y.assigned()) 00175 return NqBoolInt<XV>::post(home,x,y.val()+c); 00176 int n = x.size(); 00177 for (int i = n; i--; ) 00178 if (x[i].one()) { 00179 x[i]=x[--n]; c--; 00180 } else if (x[i].zero()) { 00181 x[i]=x[--n]; 00182 } 00183 x.size(n); 00184 if ((n-c < y.min() ) || (-c > y.max())) 00185 return ES_OK; 00186 if (n == 0) { 00187 GECODE_ME_CHECK(y.nq(home,-c)); 00188 return ES_OK; 00189 } 00190 if ((n == 1) && y.assigned()) { 00191 if (y.val()+c == 1) { 00192 GECODE_ME_CHECK(x[0].zero_none(home)); 00193 } else { 00194 assert(y.val()+c == 0); 00195 GECODE_ME_CHECK(x[0].one_none(home)); 00196 } 00197 return ES_OK; 00198 } 00199 (void) new (home) NqBoolView<XV,YV>(home,x,y,c); 00200 return ES_OK; 00201 } 00202 00203 00204 template<class XV, class YV> 00205 forceinline 00206 NqBoolView<XV,YV>::NqBoolView(Space& home, bool share, NqBoolView<XV,YV>& p) 00207 : LinBoolView<XV,YV>(home,share,p) {} 00208 00209 template<class XV, class YV> 00210 Actor* 00211 NqBoolView<XV,YV>::copy(Space& home, bool share) { 00212 return new (home) NqBoolView<XV,YV>(home,share,*this); 00213 } 00214 00215 template<class XV, class YV> 00216 ExecStatus 00217 NqBoolView<XV,YV>::propagate(Space& home, const ModEventDelta&) { 00218 int n = x.size(); 00219 for (int i = n; i--; ) 00220 if (x[i].one()) { 00221 x[i]=x[--n]; c--; 00222 } else if (x[i].zero()) { 00223 x[i]=x[--n]; 00224 } 00225 x.size(n); 00226 if ((n-c < y.min() ) || (-c > y.max())) 00227 return home.ES_SUBSUMED(*this); 00228 if (n == 0) { 00229 GECODE_ME_CHECK(y.nq(home,-c)); 00230 return home.ES_SUBSUMED(*this); 00231 } 00232 if ((n == 1) && y.assigned()) { 00233 if (y.val()+c == 1) { 00234 GECODE_ME_CHECK(x[0].zero_none(home)); 00235 } else { 00236 assert(y.val()+c == 0); 00237 GECODE_ME_CHECK(x[0].one_none(home)); 00238 } 00239 return home.ES_SUBSUMED(*this); 00240 } 00241 return ES_FIX; 00242 } 00243 00244 00245 /* 00246 * Greater or equal propagator 00247 * 00248 */ 00249 template<class XV, class YV> 00250 forceinline 00251 GqBoolView<XV,YV>::GqBoolView(Home home, ViewArray<XV>& x, YV y, int c) 00252 : LinBoolView<XV,YV>(home,x,y,c) {} 00253 00254 template<class XV, class YV> 00255 ExecStatus 00256 GqBoolView<XV,YV>::post(Home home, ViewArray<XV>& x, YV y, int c) { 00257 if (y.assigned()) 00258 return GqBoolInt<XV>::post(home,x,y.val()+c); 00259 // Eliminate assigned views 00260 int n = x.size(); 00261 for (int i = n; i--; ) 00262 if (x[i].one()) { 00263 x[i]=x[--n]; c--; 00264 } else if (x[i].zero()) { 00265 x[i]=x[--n]; 00266 } 00267 x.size(n); 00268 GECODE_ME_CHECK(y.lq(home,n-c)); 00269 if (-c >= y.max()) 00270 return ES_OK; 00271 if (y.min()+c == n) { 00272 for (int i = n; i--; ) 00273 GECODE_ME_CHECK(x[i].one_none(home)); 00274 return ES_OK; 00275 } 00276 (void) new (home) GqBoolView<XV,YV>(home,x,y,c); 00277 return ES_OK; 00278 } 00279 00280 00281 template<class XV, class YV> 00282 forceinline 00283 GqBoolView<XV,YV>::GqBoolView(Space& home, bool share, GqBoolView<XV,YV>& p) 00284 : LinBoolView<XV,YV>(home,share,p) {} 00285 00286 template<class XV, class YV> 00287 Actor* 00288 GqBoolView<XV,YV>::copy(Space& home, bool share) { 00289 return new (home) GqBoolView<XV,YV>(home,share,*this); 00290 } 00291 00292 template<class XV, class YV> 00293 ExecStatus 00294 GqBoolView<XV,YV>::propagate(Space& home, const ModEventDelta&) { 00295 int n = x.size(); 00296 for (int i = n; i--; ) 00297 if (x[i].one()) { 00298 x[i]=x[--n]; c--; 00299 } else if (x[i].zero()) { 00300 x[i]=x[--n]; 00301 } 00302 x.size(n); 00303 GECODE_ME_CHECK(y.lq(home,n-c)); 00304 if (-c >= y.max()) 00305 return home.ES_SUBSUMED(*this); 00306 if (y.min()+c == n) { 00307 for (int i = n; i--; ) 00308 GECODE_ME_CHECK(x[i].one_none(home)); 00309 return home.ES_SUBSUMED(*this); 00310 } 00311 if (y.assigned()) 00312 GECODE_REWRITE(*this,GqBoolInt<XV>::post(home(*this),x,y.val()+c)); 00313 return ES_FIX; 00314 } 00315 00316 }}} 00317 00318 // STATISTICS: int-prop 00319