Generated on Fri Oct 19 11:25:08 2018 for Gecode by doxygen 1.6.3

single.hpp

Go to the documentation of this file.
00001 /* -*- mode: C++; c-basic-offset: 2; indent-tabs-mode: nil -*- */
00002 /*
00003  *  Main authors:
00004  *     Christopher Mears <Chris.Mears@monash.edu>
00005  *
00006  *  Contributing authors:
00007  *     Christian Schulte <schulte@gecode.org>
00008  *
00009  *  Copyright:
00010  *     Christopher Mears, 2011
00011  *     Christian Schulte, 2011
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 { namespace Precede {
00039 
00041   template<class View>
00042   forceinline bool
00043   assigned(View x, int v) {
00044     return x.assigned() && (x.val() == v);
00045   }
00046 
00047   template<class View>
00048   forceinline
00049   Single<View>::Index::Index(Space& home, Propagator& p,
00050                              Council<Index>& c, int i0)
00051     : Advisor(home,p,c), i(i0) {}
00052 
00053   template<class View>
00054   forceinline
00055   Single<View>::Index::Index(Space& home, Index& a)
00056     : Advisor(home,a), i(a.i) {}
00057 
00058 
00059   template<class View>
00060   forceinline ExecStatus
00061   Single<View>::updateAlpha(Space& home) {
00062     int n = x.size();
00063     while ((alpha < n) && !x[alpha].in(s))
00064       GECODE_ME_CHECK(x[alpha++].nq(home, t));
00065     if (alpha < n)
00066       GECODE_ME_CHECK(x[alpha].nq(home, t));
00067     return ES_OK;
00068   }
00069 
00070   template<class View>
00071   forceinline ExecStatus
00072   Single<View>::updateBeta(Space& home) {
00073     int n = x.size();
00074     do {
00075       beta++;
00076     } while ((beta < n) && !x[beta].in(s));
00077     if (beta > gamma)
00078       GECODE_ME_CHECK(x[alpha].eq(home, s));
00079     return ES_OK;
00080   }
00081 
00082   template<class View>
00083   forceinline
00084   Single<View>::Single(Home home, ViewArray<View>& x0,
00085                        int s0, int t0, int b, int g)
00086     : NaryPropagator<View, PC_INT_NONE>(home,x0),
00087       c(home), s(s0), t(t0), alpha(0), beta(b), gamma(g) {
00088     for (int i=0; i<x.size(); i++)
00089       if (!x[i].assigned())
00090         x[i].subscribe(home,*new (home) Index(home,*this,c,i));
00091     View::schedule(home, *this, ME_INT_BND);
00092   }
00093 
00094   template<class View>
00095   inline ExecStatus
00096   Single<View>::post(Home home, ViewArray<View>& x, int s, int t) {
00097     {
00098       int alpha = 0;
00099       while ((alpha < x.size()) && !x[alpha].in(s))
00100         GECODE_ME_CHECK(x[alpha++].nq(home,t));
00101       x.drop_fst(alpha);
00102       if (x.size() == 0)
00103         return ES_OK;
00104     }
00105     // alpha has been normalized to 0
00106     int beta = 0, gamma = 0;
00107     GECODE_ME_CHECK(x[0].nq(home,t));
00108     do {
00109       gamma++;
00110     } while ((gamma < x.size()) && !assigned(x[gamma],t));
00111     do {
00112       beta++;
00113     } while ((beta < x.size()) && !x[beta].in(s));
00114     if (beta > gamma) {
00115       GECODE_ME_CHECK(x[0].eq(home, s));
00116       return ES_OK;
00117     }
00118     if (gamma < x.size())
00119       x.drop_lst(gamma);
00120     (void) new (home) Single<View>(home, x, s, t, beta, gamma);
00121     return ES_OK;
00122   }
00123 
00124 
00125 
00126   template<class View>
00127   forceinline
00128   Single<View>::Single(Space& home, Single& p)
00129     : NaryPropagator<View,PC_INT_NONE>(home, p),
00130       s(p.s), t(p.t),
00131       alpha(p.alpha), beta(p.beta), gamma(p.gamma) {
00132     c.update(home, p.c);
00133   }
00134   template<class View>
00135   Propagator*
00136   Single<View>::copy(Space& home) {
00137     // Try to eliminate assigned views at the beginning
00138     if (alpha > 0) {
00139       int i = 0;
00140       while ((i < alpha) && x[i].assigned())
00141         i++;
00142       x.drop_fst(i);
00143       for (Advisors<Index> as(c); as(); ++as)
00144         as.advisor().i -= i;
00145       alpha -= i; beta -= i; gamma -= i;
00146     }
00147     // Try to eliminate assigned views at the end
00148     if (gamma < x.size()) {
00149       int i = x.size()-1;
00150       while ((i > gamma) && x[i].assigned())
00151         i--;
00152       x.drop_lst(i);
00153     }
00154     return new (home) Single<View>(home, *this);
00155   }
00156 
00157 
00158   template<class View>
00159   inline size_t
00160   Single<View>::dispose(Space& home) {
00161     // Cancel remaining advisors
00162     for (Advisors<Index> as(c); as(); ++as)
00163       x[as.advisor().i].cancel(home,as.advisor());
00164     c.dispose(home);
00165     (void) NaryPropagator<View,PC_INT_NONE>::dispose(home);
00166     return sizeof(*this);
00167   }
00168 
00169   template<class View>
00170   PropCost
00171   Single<View>::cost(const Space&, const ModEventDelta&) const {
00172     return PropCost::linear(PropCost::LO, x.size());
00173   }
00174 
00175   template<class View>
00176   void
00177   Single<View>::reschedule(Space& home) {
00178     View::schedule(home, *this, ME_INT_BND);
00179   }
00180 
00181   template<class View>
00182   ExecStatus
00183   Single<View>::advise(Space& home, Advisor& a0, const Delta& d) {
00184     Index& a(static_cast<Index&>(a0));
00185     int i = a.i;
00186     // Check for gamma
00187     if ((beta <= gamma) && (i < gamma) && assigned(x[i],t))
00188       gamma = i;
00189     if (x[i].assigned()) {
00190       a.dispose(home,c);
00191       if (c.empty())
00192         return ES_NOFIX;
00193     } else if ((i < alpha) || (i > gamma)) {
00194       x[i].cancel(home,a);
00195       a.dispose(home,c);
00196       return (c.empty()) ? ES_NOFIX : ES_FIX;
00197     }
00198     if (beta > gamma)
00199       return ES_NOFIX;
00200     if ((alpha == i) || (beta == i)) {
00201       if (x[i].any(d) && !x[i].in(s))
00202         return ES_NOFIX;
00203       if ((x[i].min(d) <= s) && (s <= x[i].max(d)))
00204         return ES_NOFIX;
00205     }
00206     return ES_FIX;
00207   }
00208 
00209   template<class View>
00210   ExecStatus
00211   Single<View>::propagate(Space& home, const ModEventDelta&) {
00212     int n = x.size();
00213     if (beta > gamma) {
00214       GECODE_ME_CHECK(x[alpha].eq(home, s));
00215       return home.ES_SUBSUMED(*this);
00216     }
00217     if ((alpha < n) && !x[alpha].in(s)) {
00218       alpha++;
00219       while (alpha < beta)
00220         GECODE_ME_CHECK(x[alpha++].nq(home, t));
00221       GECODE_ES_CHECK(updateAlpha(home));
00222       beta = alpha;
00223       if (alpha < n)
00224         GECODE_ES_CHECK(updateBeta(home));
00225     } else if ((beta < n) && !x[beta].in(s)) {
00226       GECODE_ES_CHECK(updateBeta(home));
00227     }
00228 
00229     return (c.empty()) ? home.ES_SUBSUMED(*this) : ES_FIX;
00230   }
00231 
00232 }}}
00233 
00234 // STATISTICS: int-prop