Generated on Thu Apr 11 13:59:12 2019 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  *     Guido Tack <tack@gecode.org>
00009  *
00010  *  Copyright:
00011  *     Christopher Mears, 2011
00012  *     Christian Schulte, 2011
00013  *     Guido Tack, 2011
00014  *
00015  *  This file is part of Gecode, the generic constraint
00016  *  development environment:
00017  *     http://www.gecode.org
00018  *
00019  *  Permission is hereby granted, free of charge, to any person obtaining
00020  *  a copy of this software and associated documentation files (the
00021  *  "Software"), to deal in the Software without restriction, including
00022  *  without limitation the rights to use, copy, modify, merge, publish,
00023  *  distribute, sublicense, and/or sell copies of the Software, and to
00024  *  permit persons to whom the Software is furnished to do so, subject to
00025  *  the following conditions:
00026  *
00027  *  The above copyright notice and this permission notice shall be
00028  *  included in all copies or substantial portions of the Software.
00029  *
00030  *  THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,
00031  *  EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF
00032  *  MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND
00033  *  NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE
00034  *  LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION
00035  *  OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION
00036  *  WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
00037  *
00038  */
00039 
00040 namespace Gecode { namespace Set { namespace Precede {
00041 
00042   template<class View>
00043   forceinline
00044   Single<View>::Index::Index(Space& home, Propagator& p,
00045                              Council<Index>& c, int i0)
00046     : Advisor(home,p,c), i(i0) {}
00047 
00048   template<class View>
00049   forceinline
00050   Single<View>::Index::Index(Space& home, Index& a)
00051     : Advisor(home,a), i(a.i) {}
00052 
00053 
00054   template<class View>
00055   forceinline ExecStatus
00056   Single<View>::updateAlpha(Space& home) {
00057     int n = x.size();
00058     while (alpha < n) {
00059       if (x[alpha].notContains(s)) {
00060         GECODE_ME_CHECK(x[alpha].exclude(home, t));
00061       } else if (x[alpha].contains(t)) {
00062         GECODE_ME_CHECK(x[alpha].include(home, s));
00063       } else {
00064         break;
00065       }
00066       alpha++;
00067     }
00068     return ES_OK;
00069   }
00070 
00071   template<class View>
00072   forceinline ExecStatus
00073   Single<View>::updateBeta(Space& home) {
00074     int n = x.size();
00075     do {
00076       beta++;
00077     } while ((beta < n) &&
00078              (x[beta].notContains(s) || x[beta].contains(t)));
00079     if (beta > gamma) {
00080       GECODE_ME_CHECK(x[alpha].exclude(home, t));
00081       GECODE_ME_CHECK(x[alpha].include(home, s));
00082     }
00083     return ES_OK;
00084   }
00085 
00086   template<class View>
00087   forceinline
00088   Single<View>::Single(Home home, ViewArray<View>& x0,
00089                        int s0, int t0, int b, int g)
00090     : NaryPropagator<View, PC_SET_NONE>(home,x0),
00091       c(home), s(s0), t(t0), alpha(0), beta(b), gamma(g) {
00092     for (int i=x.size(); i--; )
00093       if (!x[i].assigned())
00094         x[i].subscribe(home,*new (home) Index(home,*this,c,i));
00095     View::schedule(home, *this, ME_SET_BB);
00096   }
00097 
00098   template<class View>
00099   inline ExecStatus
00100   Single<View>::post(Home home, ViewArray<View>& x, int s, int t) {
00101     {
00102       int alpha = 0;
00103       while (alpha < x.size()) {
00104         if (x[alpha].notContains(s)) {
00105           GECODE_ME_CHECK(x[alpha].exclude(home, t));
00106         } else if (x[alpha].contains(t)) {
00107           GECODE_ME_CHECK(x[alpha].include(home, s));
00108         } else {
00109           break;
00110         }
00111         alpha++;
00112       }
00113       x.drop_fst(alpha);
00114       if (x.size() == 0)
00115         return ES_OK;
00116     }
00117     // alpha has been normalized to 0
00118     int beta = 0, gamma = 0;
00119     do {
00120       gamma++;
00121     } while ((gamma < x.size()) &&
00122              (!x[gamma].notContains(s) || !x[gamma].contains(t)));
00123     do {
00124       beta++;
00125     } while ((beta < x.size()) &&
00126              (x[beta].notContains(s) || x[beta].contains(t)));
00127     if (beta > gamma) {
00128       GECODE_ME_CHECK(x[0].exclude(home, t));
00129       GECODE_ME_CHECK(x[0].include(home, s));
00130       return ES_OK;
00131     }
00132     if (gamma < x.size())
00133       x.drop_lst(gamma);
00134     (void) new (home) Single<View>(home, x, s, t, beta, gamma);
00135     return ES_OK;
00136   }
00137 
00138 
00139 
00140   template<class View>
00141   forceinline
00142   Single<View>::Single(Space& home, Single& p)
00143     : NaryPropagator<View,PC_SET_NONE>(home, p),
00144       s(p.s), t(p.t),
00145       alpha(p.alpha), beta(p.beta), gamma(p.gamma) {
00146     c.update(home, p.c);
00147   }
00148   template<class View>
00149   Propagator*
00150   Single<View>::copy(Space& home) {
00151     // Try to eliminate assigned views at the beginning
00152     if (alpha > 0) {
00153       int i = 0;
00154       while ((i < alpha) && x[i].assigned())
00155         i++;
00156       x.drop_fst(i);
00157       for (Advisors<Index> as(c); as(); ++as)
00158         as.advisor().i -= i;
00159       alpha -= i; beta -= i; gamma -= i;
00160     }
00161     // Try to eliminate assigned views at the end
00162     if (gamma < x.size()) {
00163       int i = x.size()-1;
00164       while ((i > gamma) && x[i].assigned())
00165         i--;
00166       x.drop_lst(i);
00167     }
00168     return new (home) Single<View>(home, *this);
00169   }
00170 
00171 
00172   template<class View>
00173   inline size_t
00174   Single<View>::dispose(Space& home) {
00175     // Cancel remaining advisors
00176     for (Advisors<Index> as(c); as(); ++as)
00177       x[as.advisor().i].cancel(home,as.advisor());
00178     c.dispose(home);
00179     (void) NaryPropagator<View,PC_SET_NONE>::dispose(home);
00180     return sizeof(*this);
00181   }
00182 
00183   template<class View>
00184   PropCost
00185   Single<View>::cost(const Space&, const ModEventDelta&) const {
00186     return PropCost::linear(PropCost::LO, x.size());
00187   }
00188 
00189   template<class View>
00190   void
00191   Single<View>::reschedule(Space& home) {
00192     View::schedule(home, *this, ME_SET_BB);
00193   }
00194 
00195   template<class View>
00196   ExecStatus
00197   Single<View>::advise(Space& home, Advisor& a0, const Delta&) {
00198     Index& a(static_cast<Index&>(a0));
00199     int i = a.i;
00200     // Check for gamma
00201     if ((beta <= gamma) && (i < gamma) &&
00202         x[i].notContains(s) && x[i].contains(t))
00203       gamma = i;
00204     if (x[i].assigned()) {
00205       a.dispose(home,c);
00206       if (c.empty())
00207         return ES_NOFIX;
00208     } else if ((i < alpha) || (i > gamma)) {
00209       x[i].cancel(home,a);
00210       a.dispose(home,c);
00211       return (c.empty()) ? ES_NOFIX : ES_FIX;
00212     }
00213     if (beta > gamma)
00214       return ES_NOFIX;
00215     if ((alpha == i) || (beta == i))
00216       return ES_NOFIX;
00217     return ES_FIX;
00218   }
00219 
00220   template<class View>
00221   ExecStatus
00222   Single<View>::propagate(Space& home, const ModEventDelta&) {
00223     int n = x.size();
00224     if (beta > gamma) {
00225       GECODE_ME_CHECK(x[alpha].exclude(home, t));
00226       GECODE_ME_CHECK(x[alpha].include(home, s));
00227       return home.ES_SUBSUMED(*this);
00228     }
00229     if (alpha < n && (x[alpha].notContains(s) || x[alpha].contains(t))) {
00230       if (x[alpha].notContains(s)) {
00231         GECODE_ME_CHECK(x[alpha].exclude(home, t));
00232       } else {
00233         GECODE_ME_CHECK(x[alpha].include(home, s));
00234       }
00235       alpha++;
00236       while (alpha < beta) {
00237         if (x[alpha].notContains(s)) {
00238           GECODE_ME_CHECK(x[alpha].exclude(home, t));
00239         } else {
00240           GECODE_ME_CHECK(x[alpha].include(home, s));
00241         }
00242         alpha++;
00243       }
00244       GECODE_ES_CHECK(updateAlpha(home));
00245       beta = alpha;
00246       if (alpha < n)
00247         GECODE_ES_CHECK(updateBeta(home));
00248     } else if ((beta < n) && (x[beta].notContains(s) || x[beta].contains(t))) {
00249       GECODE_ES_CHECK(updateBeta(home));
00250     }
00251 
00252     return (c.empty()) ? home.ES_SUBSUMED(*this) : ES_FIX;
00253   }
00254 
00255 }}}
00256 
00257 // STATISTICS: set-prop