bool.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, 2006 00008 * 00009 * Last modified: 00010 * $Date: 2010-07-28 17:35:33 +0200 (Wed, 28 Jul 2010) $ by $Author: schulte $ 00011 * $Revision: 11294 $ 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 { 00039 00040 /* 00041 * Creation of new variable implementations 00042 * 00043 */ 00044 forceinline 00045 BoolVarImp::BoolVarImp(int n) { 00046 assert(bits() == 0); 00047 bits() |= (n << 1) | n; 00048 } 00049 forceinline 00050 BoolVarImp::BoolVarImp(Space& home, int min, int max) 00051 : BoolVarImpBase(home) { 00052 assert(bits() == 0); 00053 bits() |= (max << 1) | min; 00054 } 00055 00056 00057 /* 00058 * Operations on Boolean variable implementations 00059 * 00060 */ 00061 forceinline BoolStatus 00062 BoolVarImp::status(void) const { 00063 return bits() & 3; 00064 } 00065 forceinline int 00066 BoolVarImp::min(void) const { 00067 return static_cast<int>(bits() & 1); 00068 } 00069 forceinline int 00070 BoolVarImp::max(void) const { 00071 return static_cast<int>((bits() & 2) >> 1); 00072 } 00073 forceinline int 00074 BoolVarImp::med(void) const { 00075 return min(); 00076 } 00077 00078 forceinline int 00079 BoolVarImp::val(void) const { 00080 assert(status() != NONE); 00081 return min(); 00082 } 00083 00084 forceinline bool 00085 BoolVarImp::range(void) const { 00086 return true; 00087 } 00088 forceinline bool 00089 BoolVarImp::assigned(void) const { 00090 return status() != NONE; 00091 } 00092 00093 00094 forceinline unsigned int 00095 BoolVarImp::width(void) const { 00096 return assigned() ? 1U : 2U; 00097 } 00098 00099 forceinline unsigned int 00100 BoolVarImp::size(void) const { 00101 return assigned() ? 1U : 2U; 00102 } 00103 00104 forceinline unsigned int 00105 BoolVarImp::regret_min(void) const { 00106 return assigned() ? 1U : 0U; 00107 } 00108 forceinline unsigned int 00109 BoolVarImp::regret_max(void) const { 00110 return assigned() ? 1U : 0U; 00111 } 00112 00113 00114 00115 /* 00116 * Tests 00117 * 00118 */ 00119 00120 forceinline bool 00121 BoolVarImp::in(int n) const { 00122 return (n >= min()) && (n <= max()); 00123 } 00124 forceinline bool 00125 BoolVarImp::in(double n) const { 00126 return (n >= min()) && (n <= max()); 00127 } 00128 00129 00130 /* 00131 * Boolean domain tests 00132 * 00133 */ 00134 forceinline bool 00135 BoolVarImp::zero(void) const { 00136 return status() < NONE; 00137 } 00138 forceinline bool 00139 BoolVarImp::one(void) const { 00140 return status() > NONE; 00141 } 00142 forceinline bool 00143 BoolVarImp::none(void) const { 00144 return status() == NONE; 00145 } 00146 00147 00148 /* 00149 * Support for delta information 00150 * 00151 */ 00152 forceinline ModEvent 00153 BoolVarImp::modevent(const Delta&) { 00154 return ME_BOOL_VAL; 00155 } 00156 forceinline int 00157 BoolVarImp::min(const Delta& d) { 00158 return static_cast<const IntDelta&>(d).min(); 00159 } 00160 forceinline int 00161 BoolVarImp::max(const Delta& d) { 00162 return static_cast<const IntDelta&>(d).min(); 00163 } 00164 forceinline bool 00165 BoolVarImp::any(const Delta&) { 00166 return false; 00167 } 00168 forceinline bool 00169 BoolVarImp::zero(const Delta& d) { 00170 return static_cast<const IntDelta&>(d).min() != 0; 00171 } 00172 forceinline bool 00173 BoolVarImp::one(const Delta& d) { 00174 return static_cast<const IntDelta&>(d).min() == 0; 00175 } 00176 00177 00178 /* 00179 * Boolean tell operations 00180 * 00181 */ 00182 forceinline ModEvent 00183 BoolVarImp::zero(Space& home) { 00184 if (one()) return ME_BOOL_FAILED; 00185 if (zero()) return ME_BOOL_NONE; 00186 return zero_none(home); 00187 } 00188 forceinline ModEvent 00189 BoolVarImp::one(Space& home) { 00190 if (one()) return ME_BOOL_NONE; 00191 if (zero()) return ME_BOOL_FAILED; 00192 return one_none(home); 00193 } 00194 00195 00196 /* 00197 * Tell operations 00198 * 00199 */ 00200 forceinline ModEvent 00201 BoolVarImp::gq(Space& home, int n) { 00202 if (n <= 0) return ME_INT_NONE; 00203 if (n > 1) return ME_INT_FAILED; 00204 return one(home); 00205 } 00206 forceinline ModEvent 00207 BoolVarImp::gq(Space& home, double n) { 00208 if (n <= 0) return ME_INT_NONE; 00209 if (n > 1) return ME_INT_FAILED; 00210 return one(home); 00211 } 00212 00213 00214 forceinline ModEvent 00215 BoolVarImp::lq(Space& home, int n) { 00216 if (n < 0) return ME_INT_FAILED; 00217 if (n >= 1) return ME_INT_NONE; 00218 return zero(home); 00219 } 00220 forceinline ModEvent 00221 BoolVarImp::lq(Space& home, double n) { 00222 if (n < 0) return ME_INT_FAILED; 00223 if (n >= 1) return ME_INT_NONE; 00224 return zero(home); 00225 } 00226 00227 00228 forceinline ModEvent 00229 BoolVarImp::eq(Space& home, int n) { 00230 if ((n < 0) || (n > 1)) return ME_INT_FAILED; 00231 return (n == 0) ? zero(home): one(home); 00232 } 00233 forceinline ModEvent 00234 BoolVarImp::eq(Space& home, double n) { 00235 if ((n < 0) || (n > 1)) return ME_INT_FAILED; 00236 return (n == 0) ? zero(home): one(home); 00237 } 00238 00239 00240 forceinline ModEvent 00241 BoolVarImp::nq(Space& home, int n) { 00242 if ((n < 0) || (n > 1)) return ME_INT_NONE; 00243 return (n == 0) ? one(home): zero(home); 00244 } 00245 forceinline ModEvent 00246 BoolVarImp::nq(Space& home, double n) { 00247 if ((n < 0) || (n > 1)) return ME_INT_NONE; 00248 return (n == 0) ? one(home): zero(home); 00249 } 00250 00251 00252 /* 00253 * Copying a variable 00254 * 00255 */ 00256 00257 forceinline 00258 BoolVarImp::BoolVarImp(Space& home, bool share, BoolVarImp& x) 00259 : BoolVarImpBase(home,share,x) {} 00260 forceinline BoolVarImp* 00261 BoolVarImp::copy(Space& home, bool share) { 00262 if (copied()) 00263 return static_cast<BoolVarImp*>(forward()); 00264 else if (zero()) 00265 return &s_zero; 00266 else if (one()) 00267 return &s_one; 00268 else 00269 return new (home) BoolVarImp(home,share,*this); 00270 } 00271 00272 00273 /* 00274 * Iterator-based domain operations 00275 * 00276 */ 00277 template<class I> 00278 forceinline ModEvent 00279 BoolVarImp::narrow_r(Space& home, I& i, bool) { 00280 // Is new domain empty? 00281 if (!i()) 00282 return ME_INT_FAILED; 00283 assert((i.min() == 0) || (i.min() == 1)); 00284 assert((i.max() == 0) || (i.max() == 1)); 00285 if (i.max() == 0) { 00286 assert(!one()); 00287 // Assign domain to be zero (domain cannot be one) 00288 return zero(home); 00289 } 00290 if (i.min() == 1) { 00291 // Assign domain to be one (domain cannot be zero) 00292 assert(!zero()); 00293 return one(home); 00294 } 00295 assert(none()); 00296 return ME_INT_NONE; 00297 } 00298 template<class I> 00299 forceinline ModEvent 00300 BoolVarImp::inter_r(Space& home, I& i, bool) { 00301 // Skip all ranges that are too small 00302 while (i() && (i.max() < 0)) 00303 ++i; 00304 // Is new domain empty? 00305 if (!i() || (i.min() > 1)) 00306 return ME_INT_FAILED; 00307 assert(i.min() <= 1); 00308 if (i.min() == 1) 00309 return one(home); 00310 if (i.max() == 0) 00311 return zero(home); 00312 assert((i.min() <= 0) && (i.max() >= 1)); 00313 return ME_INT_NONE; 00314 } 00315 template<class I> 00316 forceinline ModEvent 00317 BoolVarImp::minus_r(Space& home, I& i, bool) { 00318 // Skip all ranges that are too small 00319 while (i() && (i.max() < 0)) 00320 ++i; 00321 // Is new domain empty? 00322 if (!i() || (i.min() > 1)) 00323 return ME_INT_NONE; 00324 assert(i.min() <= 1); 00325 if (i.min() == 1) 00326 return zero(home); 00327 if (i.max() == 0) 00328 return one(home); 00329 assert((i.min() <= 0) && (i.max() >= 1)); 00330 return ME_INT_FAILED; 00331 } 00332 00333 template<class I> 00334 forceinline ModEvent 00335 BoolVarImp::narrow_v(Space& home, I& i, bool) { 00336 if (!i()) 00337 return ME_INT_FAILED; 00338 if (!none()) 00339 return ME_INT_NONE; 00340 if (i.val() == 0) { 00341 do { 00342 ++i; 00343 } while (i() && (i.val() == 0)); 00344 if (!i()) 00345 return zero_none(home); 00346 return ME_INT_NONE; 00347 } else { 00348 assert(i.val() == 1); 00349 return one_none(home); 00350 } 00351 } 00352 template<class I> 00353 forceinline ModEvent 00354 BoolVarImp::inter_v(Space& home, I& i, bool) { 00355 while (i() && (i.val() < 0)) 00356 ++i; 00357 if (!i() || (i.val() > 1)) 00358 return ME_INT_FAILED; 00359 if (i.val() == 0) { 00360 do { 00361 ++i; 00362 } while (i() && (i.val() == 0)); 00363 if (!i() || (i.val() > 1)) 00364 return zero(home); 00365 return ME_INT_NONE; 00366 } else { 00367 assert(i.val() == 1); 00368 return one(home); 00369 } 00370 } 00371 template<class I> 00372 forceinline ModEvent 00373 BoolVarImp::minus_v(Space& home, I& i, bool) { 00374 while (i() && (i.val() < 0)) 00375 ++i; 00376 if (!i() || (i.val() > 1)) 00377 return ME_INT_NONE; 00378 if (i.val() == 0) { 00379 do { 00380 ++i; 00381 } while (i() && (i.val() == 0)); 00382 if (!i() || (i.val() > 1)) 00383 return one(home); 00384 return ME_INT_FAILED; 00385 } else { 00386 assert(i.val() == 1); 00387 return zero(home); 00388 } 00389 } 00390 00391 00392 00393 /* 00394 * Dependencies 00395 * 00396 */ 00397 forceinline void 00398 BoolVarImp::subscribe(Space& home, Propagator& p, PropCond, 00399 bool schedule) { 00400 // Subscription can be used with integer propagation conditions, 00401 // which must be remapped to the single Boolean propagation condition. 00402 BoolVarImpBase::subscribe(home,p,PC_BOOL_VAL,assigned(),schedule); 00403 } 00404 forceinline void 00405 BoolVarImp::cancel(Space& home, Propagator& p, PropCond) { 00406 BoolVarImpBase::cancel(home,p,PC_BOOL_VAL,assigned()); 00407 } 00408 00409 forceinline void 00410 BoolVarImp::subscribe(Space& home, Advisor& a) { 00411 BoolVarImpBase::subscribe(home,a,assigned()); 00412 } 00413 forceinline void 00414 BoolVarImp::cancel(Space& home, Advisor& a) { 00415 BoolVarImpBase::cancel(home,a,assigned()); 00416 } 00417 00418 forceinline void 00419 BoolVarImp::schedule(Space& home, Propagator& p, ModEvent me) { 00420 if (me == ME_GEN_ASSIGNED) 00421 BoolVarImpBase::schedule(home,p,me); 00422 } 00423 00424 forceinline ModEventDelta 00425 BoolVarImp::med(ModEvent me) { 00426 return BoolVarImpBase::med(me); 00427 } 00428 00429 }} 00430 00431 // STATISTICS: int-var