Generated on Thu Mar 22 10:39:40 2012 for Gecode by doxygen 1.6.3

bool-eq.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, 2011
00008  *
00009  *  Last modified:
00010  *     $Date: 2011-08-13 14:25:20 +0200 (Sat, 13 Aug 2011) $ by $Author: schulte $
00011  *     $Revision: 12288 $
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 #include <gecode/int/rel.hh>
00039 #include <gecode/int/bool.hh>
00040 
00041 namespace Gecode { namespace Int { namespace NValues {
00042 
00043   template<class VY>
00044   forceinline
00045   EqBool<VY>::EqBool(Home home, int status, ViewArray<BoolView>& x, VY y)
00046     : BoolBase<VY>(home,status,x,y) {}
00047 
00048   template<class VY>
00049   forceinline
00050   EqBool<VY>::EqBool(Space& home, bool share, EqBool<VY>& p)
00051     : BoolBase<VY>(home,share,p) {}
00052 
00053   template<class VY>
00054   Actor*
00055   EqBool<VY>::copy(Space& home, bool share) {
00056     return new (home) EqBool<VY>(home,share,*this);
00057   }
00058 
00059   template<class VY>
00060   inline ExecStatus
00061   EqBool<VY>::post(Home home, ViewArray<BoolView>& x, VY y) {
00062     if (x.size() == 0) {
00063       GECODE_ME_CHECK(y.eq(home,0));
00064       return ES_OK;
00065     }
00066 
00067     x.unique(home);
00068 
00069     if (x.size() == 1) {
00070       GECODE_ME_CHECK(y.eq(home,1));
00071       return ES_OK;
00072     }
00073 
00074     GECODE_ME_CHECK(y.gq(home,1));
00075     GECODE_ME_CHECK(y.lq(home,2));
00076 
00077     if (y.max() == 1) {
00078       assert(y.assigned());
00079       ViewArray<BoolView> xc(home,x);
00080       return Bool::NaryEq<BoolView>::post(home,xc);
00081     }
00082     
00083     if (y.min() == 2) {
00084       assert(y.assigned());
00085       ViewArray<BoolView> xc(home,x);
00086       return Rel::NaryNq<BoolView>::post(home,xc);
00087     }
00088 
00089     int n = x.size();
00090     int status = 0;
00091     for (int i=n; i--; )
00092       if (x[i].zero()) {
00093         if (status & VS_ONE) {
00094           GECODE_ME_CHECK(y.eq(home,2));
00095           return ES_OK;
00096         }
00097         x[i] = x[--n];
00098         status |= VS_ZERO;
00099       } else if (x[i].one()) {
00100         if (status & VS_ZERO) {
00101           GECODE_ME_CHECK(y.eq(home,2));
00102           return ES_OK;
00103         }
00104         x[i] = x[--n];
00105         status |= VS_ONE;
00106       }
00107     
00108     assert(status != (VS_ZERO | VS_ONE));
00109     if (n == 0) {
00110       assert(status != 0);
00111       GECODE_ME_CHECK(y.eq(home,1));
00112       return ES_OK;
00113     }
00114     x.size(n);
00115 
00116     (void) new (home) EqBool<VY>(home,status,x,y);
00117     return ES_OK;
00118   }
00119 
00120   template<class VY>
00121   ExecStatus
00122   EqBool<VY>::propagate(Space& home, const ModEventDelta&) {
00123     if (status == (VS_ZERO | VS_ONE)) {
00124       GECODE_ME_CHECK(y.eq(home,2));
00125       return home.ES_SUBSUMED(*this);
00126     }
00127 
00128     if (c.empty()) {
00129       assert(status != 0);
00130       GECODE_ME_CHECK(y.eq(home,1));
00131       return home.ES_SUBSUMED(*this);
00132     }
00133 
00134     if (y.max() == 1) {
00135       if (status == VS_ZERO) {
00136         // Mark that everything is done
00137         status = VS_ZERO | VS_ONE;
00138         for (Advisors<ViewAdvisor<BoolView> > as(c); as(); ++as)
00139           GECODE_ME_CHECK(as.advisor().view().zero(home));
00140         return home.ES_SUBSUMED(*this);
00141       }
00142       if (status == VS_ONE) {
00143         // Mark that everything is done
00144         status = VS_ZERO | VS_ONE;
00145         for (Advisors<ViewAdvisor<BoolView> > as(c); as(); ++as)
00146           GECODE_ME_CHECK(as.advisor().view().one(home));
00147         return home.ES_SUBSUMED(*this);
00148       }
00149     }
00150 
00151     if (y.min() == 2) {
00152       Advisors<ViewAdvisor<BoolView> > as(c);
00153       assert(as());
00154       ViewAdvisor<BoolView>& a(as.advisor());
00155       ++as;
00156       if (!as()) {
00157         // Only a single view is left
00158         if (status == VS_ZERO) {
00159           GECODE_ME_CHECK(a.view().one(home));
00160         } else if (status == VS_ONE) {
00161           GECODE_ME_CHECK(a.view().zero(home));
00162         } else {
00163           return ES_FAILED;
00164         }
00165         return home.ES_SUBSUMED(*this);
00166       }
00167     }
00168 
00169     return ES_FIX;
00170   }
00171 
00172 }}}
00173 
00174 // STATISTICS: int-prop