00001
00002
00003
00004
00005
00006
00007
00008
00009
00010
00011
00012
00013
00014
00015
00016
00017
00018
00019
00020
00021
00022
00023
00024
00025
00026
00027
00028
00029
00030
00031
00032
00033
00034
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=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
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
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
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
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
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