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
00039
00040
00041
00042 namespace Gecode { namespace Int { namespace Precede {
00043
00045 template<class View>
00046 forceinline bool
00047 assigned(View x, int v) {
00048 return x.assigned() && (x.val() == v);
00049 }
00050
00051 template<class View>
00052 forceinline
00053 Single<View>::Index::Index(Space& home, Propagator& p,
00054 Council<Index>& c, int i0)
00055 : Advisor(home,p,c), i(i0) {}
00056
00057 template<class View>
00058 forceinline
00059 Single<View>::Index::Index(Space& home, bool share, Index& a)
00060 : Advisor(home,share,a), i(a.i) {}
00061
00062
00063 template<class View>
00064 forceinline ExecStatus
00065 Single<View>::updateAlpha(Space& home) {
00066 int n = x.size();
00067 while ((alpha < n) && !x[alpha].in(s))
00068 GECODE_ME_CHECK(x[alpha++].nq(home, t));
00069 if (alpha < n)
00070 GECODE_ME_CHECK(x[alpha].nq(home, t));
00071 return ES_OK;
00072 }
00073
00074 template<class View>
00075 forceinline ExecStatus
00076 Single<View>::updateBeta(Space& home) {
00077 int n = x.size();
00078 do {
00079 beta++;
00080 } while ((beta < n) && !x[beta].in(s));
00081 if (beta > gamma)
00082 GECODE_ME_CHECK(x[alpha].eq(home, s));
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_INT_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_INT_BND);
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()) && !x[alpha].in(s))
00104 GECODE_ME_CHECK(x[alpha++].nq(home,t));
00105 x.drop_fst(alpha);
00106 if (x.size() == 0)
00107 return ES_OK;
00108 }
00109
00110 int beta = 0, gamma = 0;
00111 GECODE_ME_CHECK(x[0].nq(home,t));
00112 do {
00113 gamma++;
00114 } while ((gamma < x.size()) && !assigned(x[gamma],t));
00115 do {
00116 beta++;
00117 } while ((beta < x.size()) && !x[beta].in(s));
00118 if (beta > gamma) {
00119 GECODE_ME_CHECK(x[0].eq(home, s));
00120 return ES_OK;
00121 }
00122 if (gamma < x.size())
00123 x.drop_lst(gamma);
00124 (void) new (home) Single<View>(home, x, s, t, beta, gamma);
00125 return ES_OK;
00126 }
00127
00128
00129
00130 template<class View>
00131 forceinline
00132 Single<View>::Single(Space& home, bool share, Single& p)
00133 : NaryPropagator<View,PC_INT_NONE>(home, share, p),
00134 s(p.s), t(p.t),
00135 alpha(p.alpha), beta(p.beta), gamma(p.gamma) {
00136 c.update(home, share, p.c);
00137 }
00138 template<class View>
00139 Propagator*
00140 Single<View>::copy(Space& home, bool share) {
00141
00142 if (alpha > 0) {
00143 int i = 0;
00144 while ((i < alpha) && x[i].assigned())
00145 i++;
00146 x.drop_fst(i);
00147 for (Advisors<Index> as(c); as(); ++as)
00148 as.advisor().i -= i;
00149 alpha -= i; beta -= i; gamma -= i;
00150 }
00151
00152 if (gamma < x.size()) {
00153 int i = x.size()-1;
00154 while ((i > gamma) && x[i].assigned())
00155 i--;
00156 x.drop_lst(i);
00157 }
00158 return new (home) Single<View>(home, share, *this);
00159 }
00160
00161
00162 template<class View>
00163 inline size_t
00164 Single<View>::dispose(Space& home) {
00165
00166 for (Advisors<Index> as(c); as(); ++as)
00167 x[as.advisor().i].cancel(home,as.advisor());
00168 c.dispose(home);
00169 (void) NaryPropagator<View,PC_INT_NONE>::dispose(home);
00170 return sizeof(*this);
00171 }
00172
00173 template<class View>
00174 PropCost
00175 Single<View>::cost(const Space&, const ModEventDelta&) const {
00176 return PropCost::linear(PropCost::LO, x.size());
00177 }
00178
00179 template<class View>
00180 ExecStatus
00181 Single<View>::advise(Space& home, Advisor& a0, const Delta& d) {
00182 Index& a(static_cast<Index&>(a0));
00183 int i = a.i;
00184
00185 if ((beta <= gamma) && (i < gamma) && assigned(x[i],t))
00186 gamma = i;
00187 if (x[i].assigned()) {
00188 a.dispose(home,c);
00189 if (c.empty())
00190 return ES_NOFIX;
00191 } else if ((i < alpha) || (i > gamma)) {
00192 x[i].cancel(home,a);
00193 a.dispose(home,c);
00194 return (c.empty()) ? ES_NOFIX : ES_FIX;
00195 }
00196 if (beta > gamma)
00197 return ES_NOFIX;
00198 if ((alpha == i) || (beta == i)) {
00199 if (x[i].any(d) && !x[i].in(s))
00200 return ES_NOFIX;
00201 if ((x[i].min(d) <= s) && (s <= x[i].max(d)))
00202 return ES_NOFIX;
00203 }
00204 return ES_FIX;
00205 }
00206
00207 template<class View>
00208 ExecStatus
00209 Single<View>::propagate(Space& home, const ModEventDelta&) {
00210 int n = x.size();
00211 if (beta > gamma) {
00212 GECODE_ME_CHECK(x[alpha].eq(home, s));
00213 return home.ES_SUBSUMED(*this);
00214 }
00215 if ((alpha < n) && !x[alpha].in(s)) {
00216 alpha++;
00217 while (alpha < beta)
00218 GECODE_ME_CHECK(x[alpha++].nq(home, t));
00219 GECODE_ES_CHECK(updateAlpha(home));
00220 beta = alpha;
00221 if (alpha < n)
00222 GECODE_ES_CHECK(updateBeta(home));
00223 } else if ((beta < n) && !x[beta].in(s)) {
00224 GECODE_ES_CHECK(updateBeta(home));
00225 }
00226
00227 return (c.empty()) ? home.ES_SUBSUMED(*this) : ES_FIX;
00228 }
00229
00230 }}}
00231
00232