Generated on Sun Feb 17 15:24:21 2019 for Gecode by doxygen 1.6.3

bool-gq.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 
00036 namespace Gecode { namespace Int { namespace NValues {
00037 
00038   template<class VY>
00039   forceinline
00040   GqBool<VY>::GqBool(Home home, int status, ViewArray<BoolView>& x, VY y)
00041     : BoolBase<VY>(home,status,x,y) {}
00042 
00043   template<class VY>
00044   forceinline
00045   GqBool<VY>::GqBool(Space& home, GqBool<VY>& p)
00046     : BoolBase<VY>(home,p) {}
00047 
00048   template<class VY>
00049   Actor*
00050   GqBool<VY>::copy(Space& home) {
00051     return new (home) GqBool<VY>(home,*this);
00052   }
00053 
00054   template<class VY>
00055   inline ExecStatus
00056   GqBool<VY>::post(Home home, ViewArray<BoolView>& x, VY y) {
00057     if (x.size() == 0) {
00058       GECODE_ME_CHECK(y.lq(home,0));
00059       return ES_OK;
00060     }
00061 
00062     x.unique();
00063 
00064     if (x.size() == 1) {
00065       GECODE_ME_CHECK(y.lq(home,1));
00066       return ES_OK;
00067     }
00068 
00069     GECODE_ME_CHECK(y.lq(home,2));
00070 
00071     if (y.max() <= 1)
00072       return ES_OK;
00073 
00074     if (y.min() == 2) {
00075       assert(y.assigned());
00076       ViewArray<BoolView> xc(home,x);
00077       return Rel::NaryNq<BoolView>::post(home,xc);
00078     }
00079 
00080     int n = x.size();
00081     int status = 0;
00082     for (int i=n; i--; )
00083       if (x[i].zero()) {
00084         if (status & VS_ONE)
00085           return ES_OK;
00086         x[i] = x[--n];
00087         status |= VS_ZERO;
00088       } else if (x[i].one()) {
00089         if (status & VS_ZERO)
00090           return ES_OK;
00091         x[i] = x[--n];
00092         status |= VS_ONE;
00093       }
00094 
00095     assert(status != (VS_ZERO | VS_ONE));
00096     if (n == 0) {
00097       assert(status != 0);
00098       GECODE_ME_CHECK(y.lq(home,1));
00099       return ES_OK;
00100     }
00101     x.size(n);
00102 
00103     (void) new (home) GqBool<VY>(home,status,x,y);
00104     return ES_OK;
00105   }
00106 
00107   template<class VY>
00108   ExecStatus
00109   GqBool<VY>::propagate(Space& home, const ModEventDelta&) {
00110     if (status == (VS_ZERO | VS_ONE))
00111       return home.ES_SUBSUMED(*this);
00112 
00113     if (c.empty()) {
00114       assert(status != 0);
00115       GECODE_ME_CHECK(y.lq(home,1));
00116       return home.ES_SUBSUMED(*this);
00117     }
00118 
00119     if (y.max() <= 1)
00120       return home.ES_SUBSUMED(*this);
00121 
00122     if (y.min() == 2) {
00123       Advisors<ViewAdvisor<BoolView> > as(c);
00124       assert(as());
00125       ViewAdvisor<BoolView>& a(as.advisor());
00126       ++as;
00127       if (!as()) {
00128         // Only a single view is left
00129         if (status == VS_ZERO) {
00130           GECODE_ME_CHECK(a.view().one(home));
00131         } else if (status == VS_ONE) {
00132           GECODE_ME_CHECK(a.view().zero(home));
00133         } else {
00134           return ES_FAILED;
00135         }
00136         return home.ES_SUBSUMED(*this);
00137       }
00138     }
00139 
00140     return ES_FIX;
00141   }
00142 
00143 }}}
00144 
00145 // STATISTICS: int-prop