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 Rel {
00039
00040 template <class View>
00041 inline
00042 Lex<View>::Lex(Space* home,
00043 ViewArray<View>& x0, ViewArray<View>& y0, bool s)
00044 : Propagator(home), x(x0), y(y0), strict(s) {
00045 x.subscribe(home, this, PC_INT_BND);
00046 y.subscribe(home, this, PC_INT_BND);
00047 }
00048
00049 template <class View>
00050 forceinline
00051 Lex<View>::Lex(Space* home, bool share, Lex<View>& p)
00052 : Propagator(home,share,p), strict(p.strict) {
00053 x.update(home,share,p.x);
00054 y.update(home,share,p.y);
00055 }
00056
00057 template <class View>
00058 Actor*
00059 Lex<View>::copy(Space* home, bool share) {
00060 return new (home) Lex<View>(home,share,*this);
00061 }
00062
00063 template <class View>
00064 inline Support::Symbol
00065 Lex<View>::ati(void) {
00066 return Reflection::mangle<View>("Gecode::Int::Rel::Lex");
00067 }
00068
00069 template <class View>
00070 Reflection::ActorSpec
00071 Lex<View>::spec(const Space* home, Reflection::VarMap& m) const {
00072 Reflection::ActorSpec s(ati());
00073 return s << x.spec(home,m) << y.spec(home,m) << strict;
00074 }
00075
00076 template <class View>
00077 void
00078 Lex<View>::post(Space* home, Reflection::VarMap& vars,
00079 const Reflection::ActorSpec& spec) {
00080 spec.checkArity(3);
00081 ViewArray<View> x(home, vars, spec[0]);
00082 ViewArray<View> y(home, vars, spec[1]);
00083 bool s = spec[2]->toInt();
00084 (void) new (home) Lex<View>(home,x,y,s);
00085 }
00086
00087 template <class View>
00088 PropCost
00089 Lex<View>::cost(ModEventDelta) const {
00090 return cost_lo(x.size(), PC_LINEAR_LO);
00091 }
00092
00093 template <class View>
00094 ExecStatus
00095 Lex<View>::propagate(Space* home, ModEventDelta) {
00096
00097
00098
00099
00100 {
00101 int i = 0;
00102 int n = x.size();
00103
00104 while ((i < n) && (x[i].min() == y[i].max())) {
00105
00106 GECODE_ME_CHECK(x[i].lq(home,y[i].max()));
00107 GECODE_ME_CHECK(y[i].gq(home,x[i].min()));
00108 i++;
00109 }
00110
00111 if (i == n)
00112 return strict ? ES_FAILED : ES_SUBSUMED(this,sizeof(*this));
00113
00114
00115 GECODE_ME_CHECK(x[i].lq(home,y[i].max()));
00116 GECODE_ME_CHECK(y[i].gq(home,x[i].min()));
00117
00118 if (x[i].max() < y[i].min())
00119 return ES_SUBSUMED(this,home);
00120
00121
00122 assert(!(x[i].assigned() && y[i].assigned() &&
00123 x[i].val() == y[i].val()));
00124
00125 x.drop_fst(i); y.drop_fst(i);
00126
00127 }
00128
00129
00130
00131
00132
00133
00134 {
00135 int i = 1;
00136 int n = x.size();
00137
00138 while ((i < n) &&
00139 (x[i].min() == y[i].max()) &&
00140 (x[i].max() == y[i].min())) {
00141 assert(x[i].assigned() && y[i].assigned() &&
00142 (x[i].val() == y[i].val()));
00143 i++;
00144 }
00145
00146 if (i == n) {
00147 if (strict)
00148 goto rewrite_le;
00149 else
00150 goto rewrite_lq;
00151 }
00152
00153 if (x[i].max() < y[i].min())
00154 goto rewrite_lq;
00155
00156 if (x[i].min() > y[i].max())
00157 goto rewrite_le;
00158
00159 if (i > 1) {
00160
00161 x[i-1]=x[0]; x.drop_fst(i-1);
00162 y[i-1]=y[0]; y.drop_fst(i-1);
00163 }
00164 }
00165
00166 if (x[1].max() <= y[1].min()) {
00167
00168
00169
00170
00171
00172
00173 int i = 2;
00174 int n = x.size();
00175
00176 while ((i < n) && (x[i].max() == y[i].min()))
00177 i++;
00178
00179 if (i == n) {
00180 if (strict)
00181 return ES_FIX;
00182 else
00183 goto rewrite_lq;
00184 }
00185
00186 if (x[i].max() < y[i].min())
00187 goto rewrite_lq;
00188
00189 if (x[i].min() > y[i].max()) {
00190
00191 for (int j=i; j<n; j++) {
00192 x[j].cancel(home,this,PC_INT_BND);
00193 y[j].cancel(home,this,PC_INT_BND);
00194 }
00195 x.size(i); y.size(i);
00196 strict = true;
00197 }
00198
00199 return ES_FIX;
00200 }
00201
00202 if (x[1].min() >= y[1].max()) {
00203
00204
00205
00206
00207
00208
00209 int i = 2;
00210 int n = x.size();
00211
00212 while ((i < n) && (x[i].min() == y[i].max()))
00213
00214 i++;
00215
00216 if (i == n) {
00217 if (strict)
00218 goto rewrite_le;
00219 else
00220 return ES_FIX;
00221 }
00222
00223 if (x[i].min() > y[i].max())
00224 goto rewrite_le;
00225
00226 if (x[i].max() < y[i].min()) {
00227
00228 for (int j=i; j<n; j++) {
00229 x[j].cancel(home,this,PC_INT_BND);
00230 y[j].cancel(home,this,PC_INT_BND);
00231 }
00232 x.size(i); y.size(i);
00233 strict = false;
00234 }
00235
00236 return ES_FIX;
00237 }
00238
00239 return ES_FIX;
00240
00241 rewrite_le:
00242 GECODE_REWRITE(this,Le<View>::post(home,x[0],y[0]));
00243 rewrite_lq:
00244 GECODE_REWRITE(this,Lq<View>::post(home,x[0],y[0]));
00245 }
00246
00247 template <class View>
00248 ExecStatus
00249 Lex<View>::post(Space* home,
00250 ViewArray<View>& x, ViewArray<View>& y, bool strict){
00251 if (x.size() == 0)
00252 return strict ? ES_FAILED : ES_OK;
00253 if (x.size() == 1) {
00254 if (strict)
00255 return Le<View>::post(home,x[0],y[0]);
00256 else
00257 return Lq<View>::post(home,x[0],y[0]);
00258 }
00259 (void) new (home) Lex<View>(home,x,y,strict);
00260 return ES_OK;
00261 }
00262
00263 template <class View>
00264 size_t
00265 Lex<View>::dispose(Space* home) {
00266 assert(!home->failed());
00267 x.cancel(home,this,PC_INT_BND);
00268 y.cancel(home,this,PC_INT_BND);
00269 (void) Propagator::dispose(home);
00270 return sizeof(*this);
00271 }
00272
00273 }}}
00274
00275