Generated on Tue May 22 09:40:03 2018 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  *  This file is part of Gecode, the generic constraint
00010  *  development environment:
00011  *     http://www.gecode.org
00012  *
00013  *  Permission is hereby granted, free of charge, to any person obtaining
00014  *  a copy of this software and associated documentation files (the
00015  *  "Software"), to deal in the Software without restriction, including
00016  *  without limitation the rights to use, copy, modify, merge, publish,
00017  *  distribute, sublicense, and/or sell copies of the Software, and to
00018  *  permit persons to whom the Software is furnished to do so, subject to
00019  *  the following conditions:
00020  *
00021  *  The above copyright notice and this permission notice shall be
00022  *  included in all copies or substantial portions of the Software.
00023  *
00024  *  THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,
00025  *  EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF
00026  *  MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND
00027  *  NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE
00028  *  LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION
00029  *  OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION
00030  *  WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
00031  *
00032  */
00033 
00034 #include <gecode/int/rel.hh>
00035 #include <gecode/int/bool.hh>
00036 
00037 namespace Gecode { namespace Int { namespace NValues {
00038 
00039   template<class VY>
00040   forceinline
00041   EqBool<VY>::EqBool(Home home, int status, ViewArray<BoolView>& x, VY y)
00042     : BoolBase<VY>(home,status,x,y) {}
00043 
00044   template<class VY>
00045   forceinline
00046   EqBool<VY>::EqBool(Space& home, EqBool<VY>& p)
00047     : BoolBase<VY>(home,p) {}
00048 
00049   template<class VY>
00050   Actor*
00051   EqBool<VY>::copy(Space& home) {
00052     return new (home) EqBool<VY>(home,*this);
00053   }
00054 
00055   template<class VY>
00056   inline ExecStatus
00057   EqBool<VY>::post(Home home, ViewArray<BoolView>& x, VY y) {
00058     if (x.size() == 0) {
00059       GECODE_ME_CHECK(y.eq(home,0));
00060       return ES_OK;
00061     }
00062 
00063     x.unique();
00064 
00065     if (x.size() == 1) {
00066       GECODE_ME_CHECK(y.eq(home,1));
00067       return ES_OK;
00068     }
00069 
00070     GECODE_ME_CHECK(y.gq(home,1));
00071     GECODE_ME_CHECK(y.lq(home,2));
00072 
00073     if (y.max() == 1) {
00074       assert(y.assigned());
00075       ViewArray<BoolView> xc(home,x);
00076       return Bool::NaryEq<BoolView>::post(home,xc);
00077     }
00078 
00079     if (y.min() == 2) {
00080       assert(y.assigned());
00081       ViewArray<BoolView> xc(home,x);
00082       return Rel::NaryNq<BoolView>::post(home,xc);
00083     }
00084 
00085     int n = x.size();
00086     int status = 0;
00087     for (int i=n; i--; )
00088       if (x[i].zero()) {
00089         if (status & VS_ONE) {
00090           GECODE_ME_CHECK(y.eq(home,2));
00091           return ES_OK;
00092         }
00093         x[i] = x[--n];
00094         status |= VS_ZERO;
00095       } else if (x[i].one()) {
00096         if (status & VS_ZERO) {
00097           GECODE_ME_CHECK(y.eq(home,2));
00098           return ES_OK;
00099         }
00100         x[i] = x[--n];
00101         status |= VS_ONE;
00102       }
00103 
00104     assert(status != (VS_ZERO | VS_ONE));
00105     if (n == 0) {
00106       assert(status != 0);
00107       GECODE_ME_CHECK(y.eq(home,1));
00108       return ES_OK;
00109     }
00110     x.size(n);
00111 
00112     (void) new (home) EqBool<VY>(home,status,x,y);
00113     return ES_OK;
00114   }
00115 
00116   template<class VY>
00117   ExecStatus
00118   EqBool<VY>::propagate(Space& home, const ModEventDelta&) {
00119     if (status == (VS_ZERO | VS_ONE)) {
00120       GECODE_ME_CHECK(y.eq(home,2));
00121       return home.ES_SUBSUMED(*this);
00122     }
00123 
00124     if (c.empty()) {
00125       assert(status != 0);
00126       GECODE_ME_CHECK(y.eq(home,1));
00127       return home.ES_SUBSUMED(*this);
00128     }
00129 
00130     if (y.max() == 1) {
00131       if (status == VS_ZERO) {
00132         // Mark that everything is done
00133         status = VS_ZERO | VS_ONE;
00134         for (Advisors<ViewAdvisor<BoolView> > as(c); as(); ++as)
00135           GECODE_ME_CHECK(as.advisor().view().zero(home));
00136         return home.ES_SUBSUMED(*this);
00137       }
00138       if (status == VS_ONE) {
00139         // Mark that everything is done
00140         status = VS_ZERO | VS_ONE;
00141         for (Advisors<ViewAdvisor<BoolView> > as(c); as(); ++as)
00142           GECODE_ME_CHECK(as.advisor().view().one(home));
00143         return home.ES_SUBSUMED(*this);
00144       }
00145     }
00146 
00147     if (y.min() == 2) {
00148       Advisors<ViewAdvisor<BoolView> > as(c);
00149       assert(as());
00150       ViewAdvisor<BoolView>& a(as.advisor());
00151       ++as;
00152       if (!as()) {
00153         // Only a single view is left
00154         if (status == VS_ZERO) {
00155           GECODE_ME_CHECK(a.view().one(home));
00156         } else if (status == VS_ONE) {
00157           GECODE_ME_CHECK(a.view().zero(home));
00158         } else {
00159           return ES_FAILED;
00160         }
00161         return home.ES_SUBSUMED(*this);
00162       }
00163     }
00164 
00165     return ES_FIX;
00166   }
00167 
00168 }}}
00169 
00170 // STATISTICS: int-prop