Generated on Tue Jul 27 2010 21:59:16 for Gecode by doxygen 1.7.1

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