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
00043
00044 namespace Gecode { namespace Set { namespace Precede {
00045
00046 template<class View>
00047 forceinline
00048 Single<View>::Index::Index(Space& home, Propagator& p,
00049 Council<Index>& c, int i0)
00050 : Advisor(home,p,c), i(i0) {}
00051
00052 template<class View>
00053 forceinline
00054 Single<View>::Index::Index(Space& home, bool share, Index& a)
00055 : Advisor(home,share,a), i(a.i) {}
00056
00057
00058 template<class View>
00059 forceinline ExecStatus
00060 Single<View>::updateAlpha(Space& home) {
00061 int n = x.size();
00062 while (alpha < n) {
00063 if (x[alpha].notContains(s)) {
00064 GECODE_ME_CHECK(x[alpha].exclude(home, t));
00065 } else if (x[alpha].contains(t)) {
00066 GECODE_ME_CHECK(x[alpha].include(home, s));
00067 } else {
00068 break;
00069 }
00070 alpha++;
00071 }
00072 return ES_OK;
00073 }
00074
00075 template<class View>
00076 forceinline ExecStatus
00077 Single<View>::updateBeta(Space& home) {
00078 int n = x.size();
00079 do {
00080 beta++;
00081 } while ((beta < n) &&
00082 (x[beta].notContains(s) || x[beta].contains(t)));
00083 if (beta > gamma) {
00084 GECODE_ME_CHECK(x[alpha].exclude(home, t));
00085 GECODE_ME_CHECK(x[alpha].include(home, s));
00086 }
00087 return ES_OK;
00088 }
00089
00090 template<class View>
00091 forceinline
00092 Single<View>::Single(Home home, ViewArray<View>& x0,
00093 int s0, int t0, int b, int g)
00094 : NaryPropagator<View, PC_SET_NONE>(home,x0),
00095 c(home), s(s0), t(t0), alpha(0), beta(b), gamma(g) {
00096 for (int i=x.size(); i--; )
00097 if (!x[i].assigned())
00098 x[i].subscribe(home,*new (home) Index(home,*this,c,i));
00099 View::schedule(home, *this, ME_SET_BB);
00100 }
00101
00102 template<class View>
00103 inline ExecStatus
00104 Single<View>::post(Home home, ViewArray<View>& x, int s, int t) {
00105 {
00106 int alpha = 0;
00107 while (alpha < x.size()) {
00108 if (x[alpha].notContains(s)) {
00109 GECODE_ME_CHECK(x[alpha].exclude(home, t));
00110 } else if (x[alpha].contains(t)) {
00111 GECODE_ME_CHECK(x[alpha].include(home, s));
00112 } else {
00113 break;
00114 }
00115 alpha++;
00116 }
00117 x.drop_fst(alpha);
00118 if (x.size() == 0)
00119 return ES_OK;
00120 }
00121
00122 int beta = 0, gamma = 0;
00123 do {
00124 gamma++;
00125 } while ((gamma < x.size()) &&
00126 (!x[gamma].notContains(s) || !x[gamma].contains(t)));
00127 do {
00128 beta++;
00129 } while ((beta < x.size()) &&
00130 (x[beta].notContains(s) || x[beta].contains(t)));
00131 if (beta > gamma) {
00132 GECODE_ME_CHECK(x[0].exclude(home, t));
00133 GECODE_ME_CHECK(x[0].include(home, s));
00134 return ES_OK;
00135 }
00136 if (gamma < x.size())
00137 x.drop_lst(gamma);
00138 (void) new (home) Single<View>(home, x, s, t, beta, gamma);
00139 return ES_OK;
00140 }
00141
00142
00143
00144 template<class View>
00145 forceinline
00146 Single<View>::Single(Space& home, bool share, Single& p)
00147 : NaryPropagator<View,PC_SET_NONE>(home, share, p),
00148 s(p.s), t(p.t),
00149 alpha(p.alpha), beta(p.beta), gamma(p.gamma) {
00150 c.update(home, share, p.c);
00151 }
00152 template<class View>
00153 Propagator*
00154 Single<View>::copy(Space& home, bool share) {
00155
00156 if (alpha > 0) {
00157 int i = 0;
00158 while ((i < alpha) && x[i].assigned())
00159 i++;
00160 x.drop_fst(i);
00161 for (Advisors<Index> as(c); as(); ++as)
00162 as.advisor().i -= i;
00163 alpha -= i; beta -= i; gamma -= i;
00164 }
00165
00166 if (gamma < x.size()) {
00167 int i = x.size()-1;
00168 while ((i > gamma) && x[i].assigned())
00169 i--;
00170 x.drop_lst(i);
00171 }
00172 return new (home) Single<View>(home, share, *this);
00173 }
00174
00175
00176 template<class View>
00177 inline size_t
00178 Single<View>::dispose(Space& home) {
00179
00180 for (Advisors<Index> as(c); as(); ++as)
00181 x[as.advisor().i].cancel(home,as.advisor());
00182 c.dispose(home);
00183 (void) NaryPropagator<View,PC_SET_NONE>::dispose(home);
00184 return sizeof(*this);
00185 }
00186
00187 template<class View>
00188 PropCost
00189 Single<View>::cost(const Space&, const ModEventDelta&) const {
00190 return PropCost::linear(PropCost::LO, x.size());
00191 }
00192
00193 template<class View>
00194 void
00195 Single<View>::reschedule(Space& home) {
00196 View::schedule(home, *this, ME_SET_BB);
00197 }
00198
00199 template<class View>
00200 ExecStatus
00201 Single<View>::advise(Space& home, Advisor& a0, const Delta&) {
00202 Index& a(static_cast<Index&>(a0));
00203 int i = a.i;
00204
00205 if ((beta <= gamma) && (i < gamma) &&
00206 x[i].notContains(s) && x[i].contains(t))
00207 gamma = i;
00208 if (x[i].assigned()) {
00209 a.dispose(home,c);
00210 if (c.empty())
00211 return ES_NOFIX;
00212 } else if ((i < alpha) || (i > gamma)) {
00213 x[i].cancel(home,a);
00214 a.dispose(home,c);
00215 return (c.empty()) ? ES_NOFIX : ES_FIX;
00216 }
00217 if (beta > gamma)
00218 return ES_NOFIX;
00219 if ((alpha == i) || (beta == i))
00220 return ES_NOFIX;
00221 return ES_FIX;
00222 }
00223
00224 template<class View>
00225 ExecStatus
00226 Single<View>::propagate(Space& home, const ModEventDelta&) {
00227 int n = x.size();
00228 if (beta > gamma) {
00229 GECODE_ME_CHECK(x[alpha].exclude(home, t));
00230 GECODE_ME_CHECK(x[alpha].include(home, s));
00231 return home.ES_SUBSUMED(*this);
00232 }
00233 if (alpha < n && (x[alpha].notContains(s) || x[alpha].contains(t))) {
00234 if (x[alpha].notContains(s)) {
00235 GECODE_ME_CHECK(x[alpha].exclude(home, t));
00236 } else {
00237 GECODE_ME_CHECK(x[alpha].include(home, s));
00238 }
00239 alpha++;
00240 while (alpha < beta) {
00241 if (x[alpha].notContains(s)) {
00242 GECODE_ME_CHECK(x[alpha].exclude(home, t));
00243 } else {
00244 GECODE_ME_CHECK(x[alpha].include(home, s));
00245 }
00246 alpha++;
00247 }
00248 GECODE_ES_CHECK(updateAlpha(home));
00249 beta = alpha;
00250 if (alpha < n)
00251 GECODE_ES_CHECK(updateBeta(home));
00252 } else if ((beta < n) && (x[beta].notContains(s) || x[beta].contains(t))) {
00253 GECODE_ES_CHECK(updateBeta(home));
00254 }
00255
00256 return (c.empty()) ? home.ES_SUBSUMED(*this) : ES_FIX;
00257 }
00258
00259 }}}
00260
00261