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-05-29 12:02:54 +0200 (Sat, 29 May 2010) $ by $Author: schulte $ 00011 * $Revision: 10988 $ 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 Iter::Ranges::IsRangeIter<I>(); 00281 // Is new domain empty? 00282 if (!i()) 00283 return ME_INT_FAILED; 00284 assert((i.min() == 0) || (i.min() == 1)); 00285 assert((i.max() == 0) || (i.max() == 1)); 00286 if (i.max() == 0) { 00287 assert(!one()); 00288 // Assign domain to be zero (domain cannot be one) 00289 return zero(home); 00290 } 00291 if (i.min() == 1) { 00292 // Assign domain to be one (domain cannot be zero) 00293 assert(!zero()); 00294 return one(home); 00295 } 00296 assert(none()); 00297 return ME_INT_NONE; 00298 } 00299 template<class I> 00300 forceinline ModEvent 00301 BoolVarImp::inter_r(Space& home, I& i, bool) { 00302 Iter::Ranges::IsRangeIter<I>(); 00303 // Skip all ranges that are too small 00304 while (i() && (i.max() < 0)) 00305 ++i; 00306 // Is new domain empty? 00307 if (!i() || (i.min() > 1)) 00308 return ME_INT_FAILED; 00309 assert(i.min() <= 1); 00310 if (i.min() == 1) 00311 return one(home); 00312 if (i.max() == 0) 00313 return zero(home); 00314 assert((i.min() <= 0) && (i.max() >= 1)); 00315 return ME_INT_NONE; 00316 } 00317 template<class I> 00318 forceinline ModEvent 00319 BoolVarImp::minus_r(Space& home, I& i, bool) { 00320 Iter::Ranges::IsRangeIter<I>(); 00321 // Skip all ranges that are too small 00322 while (i() && (i.max() < 0)) 00323 ++i; 00324 // Is new domain empty? 00325 if (!i() || (i.min() > 1)) 00326 return ME_INT_NONE; 00327 assert(i.min() <= 1); 00328 if (i.min() == 1) 00329 return zero(home); 00330 if (i.max() == 0) 00331 return one(home); 00332 assert((i.min() <= 0) && (i.max() >= 1)); 00333 return ME_INT_FAILED; 00334 } 00335 00336 template<class I> 00337 forceinline ModEvent 00338 BoolVarImp::narrow_v(Space& home, I& i, bool) { 00339 Iter::Values::IsValueIter<I>(); 00340 if (!i()) 00341 return ME_INT_FAILED; 00342 if (!none()) 00343 return ME_INT_NONE; 00344 if (i.val() == 0) { 00345 do { 00346 ++i; 00347 } while (i() && (i.val() == 0)); 00348 if (!i()) 00349 return zero_none(home); 00350 return ME_INT_NONE; 00351 } else { 00352 assert(i.val() == 1); 00353 return one_none(home); 00354 } 00355 } 00356 template<class I> 00357 forceinline ModEvent 00358 BoolVarImp::inter_v(Space& home, I& i, bool) { 00359 Iter::Values::IsValueIter<I>(); 00360 while (i() && (i.val() < 0)) 00361 ++i; 00362 if (!i() || (i.val() > 1)) 00363 return ME_INT_FAILED; 00364 if (i.val() == 0) { 00365 do { 00366 ++i; 00367 } while (i() && (i.val() == 0)); 00368 if (!i() || (i.val() > 1)) 00369 return zero(home); 00370 return ME_INT_NONE; 00371 } else { 00372 assert(i.val() == 1); 00373 return one(home); 00374 } 00375 } 00376 template<class I> 00377 forceinline ModEvent 00378 BoolVarImp::minus_v(Space& home, I& i, bool) { 00379 Iter::Values::IsValueIter<I>(); 00380 while (i() && (i.val() < 0)) 00381 ++i; 00382 if (!i() || (i.val() > 1)) 00383 return ME_INT_NONE; 00384 if (i.val() == 0) { 00385 do { 00386 ++i; 00387 } while (i() && (i.val() == 0)); 00388 if (!i() || (i.val() > 1)) 00389 return one(home); 00390 return ME_INT_FAILED; 00391 } else { 00392 assert(i.val() == 1); 00393 return zero(home); 00394 } 00395 } 00396 00397 00398 00399 /* 00400 * Dependencies 00401 * 00402 */ 00403 forceinline void 00404 BoolVarImp::subscribe(Space& home, Propagator& p, PropCond, 00405 bool schedule) { 00406 // Subscription can be used with integer propagation conditions, 00407 // which must be remapped to the single Boolean propagation condition. 00408 BoolVarImpBase::subscribe(home,p,PC_BOOL_VAL,assigned(),schedule); 00409 } 00410 forceinline void 00411 BoolVarImp::cancel(Space& home, Propagator& p, PropCond) { 00412 BoolVarImpBase::cancel(home,p,PC_BOOL_VAL,assigned()); 00413 } 00414 00415 forceinline void 00416 BoolVarImp::subscribe(Space& home, Advisor& a) { 00417 BoolVarImpBase::subscribe(home,a,assigned()); 00418 } 00419 forceinline void 00420 BoolVarImp::cancel(Space& home, Advisor& a) { 00421 BoolVarImpBase::cancel(home,a,assigned()); 00422 } 00423 00424 forceinline void 00425 BoolVarImp::schedule(Space& home, Propagator& p, ModEvent me) { 00426 if (me == ME_GEN_ASSIGNED) 00427 BoolVarImpBase::schedule(home,p,me); 00428 } 00429 00430 forceinline ModEventDelta 00431 BoolVarImp::med(ModEvent me) { 00432 return BoolVarImpBase::med(me); 00433 } 00434 00435 }} 00436 00437 // STATISTICS: int-var