Generated on Tue Apr 18 10:21:57 2017 for Gecode by doxygen 1.6.3

re-prop.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: 2016-11-08 17:23:24 +0100 (Tue, 08 Nov 2016) $ by $Author: schulte $
00011  *     $Revision: 15253 $
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 
00040 namespace Gecode { namespace Int { namespace Member {
00041 
00042   template<class View, ReifyMode rm>
00043   forceinline
00044   ReProp<View,rm>::ReProp(Home home, ValSet& vs, ViewArray<View>& x, View y,
00045                           BoolView b0)
00046     : Prop<View>(home,vs,x,y), b(b0) {
00047     b.subscribe(home,*this,PC_BOOL_VAL);
00048   }
00049 
00050   template<class View, ReifyMode rm>
00051   inline ExecStatus
00052   ReProp<View,rm>::post(Home home, ViewArray<View>& x, View y, BoolView b) {
00053     if (x.size() == 0) {
00054       if (rm != RM_PMI)
00055         GECODE_ME_CHECK(b.zero(home));
00056       return ES_OK;
00057     }
00058 
00059     x.unique(home);
00060 
00061     if (x.size() == 1)
00062       return Rel::ReEqDom<View,BoolView,rm>::post(home,x[0],y,b);
00063 
00064     if (x.same(home,y)) {
00065       if (rm != RM_IMP)
00066         GECODE_ME_CHECK(b.one(home));
00067       return ES_OK;
00068     }
00069 
00070     // Eliminate assigned views and store them into the value set
00071     ValSet vs;
00072     add(home, vs, x);
00073 
00074     switch (vs.compare(y)) {
00075     case Iter::Ranges::CS_SUBSET:
00076       if (rm != RM_IMP)
00077         GECODE_ME_CHECK(b.one(home));
00078       return ES_OK;
00079     case Iter::Ranges::CS_DISJOINT:
00080       if (x.size() == 0) {
00081         if (rm != RM_PMI)
00082           GECODE_ME_CHECK(b.zero(home));
00083         return ES_OK;
00084       }
00085       break;
00086     case Iter::Ranges::CS_NONE:
00087       break;
00088     default:
00089       GECODE_NEVER;
00090     }
00091 
00092     (void) new (home) ReProp<View,rm>(home, vs, x, y, b);
00093     return ES_OK;
00094   }
00095 
00096   template<class View, ReifyMode rm>
00097   forceinline
00098   ReProp<View,rm>::ReProp(Space& home, bool share, ReProp<View,rm>& p)
00099     : Prop<View>(home, share, p) {
00100     b.update(home, share, p.b);
00101   }
00102 
00103   template<class View, ReifyMode rm>
00104   Propagator*
00105   ReProp<View,rm>::copy(Space& home, bool share) {
00106     return new (home) ReProp<View,rm>(home, share, *this);
00107   }
00108 
00109   template<class View, ReifyMode rm>
00110   forceinline size_t
00111   ReProp<View,rm>::dispose(Space& home) {
00112     b.cancel(home, *this, PC_BOOL_VAL);
00113     (void) Prop<View>::dispose(home);
00114     return sizeof(*this);
00115   }
00116 
00117   template<class View, ReifyMode rm>
00118   ExecStatus
00119   ReProp<View,rm>::propagate(Space& home, const ModEventDelta& med) {
00120     // Add assigned views to value set
00121     if (View::me(med) == ME_INT_VAL)
00122       add(home,vs,x);
00123 
00124     if (b.one()) {
00125       if (rm == RM_PMI)
00126         return home.ES_SUBSUMED(*this);
00127       ValSet vsc(vs);
00128       vs.flush();
00129       GECODE_REWRITE(*this,Prop<View>::post(home(*this),vsc,x,y));
00130     }
00131 
00132     if (b.zero()) {
00133       if (rm != RM_IMP) {
00134         ValSet::Ranges vsr(vs);
00135         GECODE_ME_CHECK(y.minus_r(home,vsr,false));
00136         for (int i=x.size(); i--; )
00137           GECODE_ES_CHECK((Rel::Nq<View,View>::post(Home(home),x[i],y)));
00138       }
00139       return home.ES_SUBSUMED(*this);
00140     }
00141 
00142     // Eliminate views from x
00143     eliminate(home);
00144 
00145     switch (vs.compare(y)) {
00146     case Iter::Ranges::CS_SUBSET:
00147       if (rm != RM_IMP)
00148         GECODE_ME_CHECK(b.one(home));
00149       return home.ES_SUBSUMED(*this);
00150     case Iter::Ranges::CS_DISJOINT:
00151       if (x.size() == 0) {
00152         if (rm != RM_PMI)
00153           GECODE_ME_CHECK(b.zero(home));
00154         return home.ES_SUBSUMED(*this);
00155       }
00156       break;
00157     case Iter::Ranges::CS_NONE:
00158       break;
00159     default:
00160       GECODE_NEVER;
00161     }
00162 
00163     // Check whether y is in union of x and value set
00164     if (x.size() > 0) {
00165       Region r(home);
00166 
00167       ValSet::Ranges vsr(vs);
00168       ViewRanges<View> xsr(x[x.size()-1]);
00169       Iter::Ranges::NaryUnion  u(r,vsr,xsr);
00170       for (int i=x.size()-1; i--; ) {
00171         ViewRanges<View> xir(x[i]);
00172         u |= xir;
00173       }
00174 
00175       ViewRanges<View> yr(y);
00176 
00177       if (Iter::Ranges::disjoint(u,yr)) {
00178         if (rm != RM_PMI)
00179           GECODE_ME_CHECK(b.zero(home));
00180         return home.ES_SUBSUMED(*this);
00181       }
00182     }
00183 
00184     return ES_FIX;
00185   }
00186 
00187 }}}
00188 
00189 // STATISTICS: int-prop