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(Home 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 PropCost
00065 Lex<View>::cost(const Space&, const ModEventDelta&) const {
00066 return PropCost::linear(PropCost::LO, x.size());
00067 }
00068
00069 template<class View>
00070 ExecStatus
00071 Lex<View>::propagate(Space& home, const ModEventDelta&) {
00072
00073
00074
00075
00076 {
00077 int i = 0;
00078 int n = x.size();
00079
00080 while ((i < n) && (x[i].min() == y[i].max())) {
00081
00082 GECODE_ME_CHECK(x[i].lq(home,y[i].max()));
00083 GECODE_ME_CHECK(y[i].gq(home,x[i].min()));
00084 i++;
00085 }
00086
00087 if (i == n)
00088 return strict ? ES_FAILED : ES_SUBSUMED(*this,sizeof(*this));
00089
00090
00091 GECODE_ME_CHECK(x[i].lq(home,y[i].max()));
00092 GECODE_ME_CHECK(y[i].gq(home,x[i].min()));
00093
00094 if (x[i].max() < y[i].min())
00095 return ES_SUBSUMED(*this,home);
00096
00097
00098 assert(!(x[i].assigned() && y[i].assigned() &&
00099 x[i].val() == y[i].val()));
00100
00101 x.drop_fst(i); y.drop_fst(i);
00102
00103 }
00104
00105
00106
00107
00108
00109
00110 {
00111 int i = 1;
00112 int n = x.size();
00113
00114 while ((i < n) &&
00115 (x[i].min() == y[i].max()) &&
00116 (x[i].max() == y[i].min())) {
00117 assert(x[i].assigned() && y[i].assigned() &&
00118 (x[i].val() == y[i].val()));
00119 i++;
00120 }
00121
00122 if (i == n) {
00123 if (strict)
00124 goto rewrite_le;
00125 else
00126 goto rewrite_lq;
00127 }
00128
00129 if (x[i].max() < y[i].min())
00130 goto rewrite_lq;
00131
00132 if (x[i].min() > y[i].max())
00133 goto rewrite_le;
00134
00135 if (i > 1) {
00136
00137 x[i-1]=x[0]; x.drop_fst(i-1);
00138 y[i-1]=y[0]; y.drop_fst(i-1);
00139 }
00140 }
00141
00142 if (x[1].max() <= y[1].min()) {
00143
00144
00145
00146
00147
00148
00149 int i = 2;
00150 int n = x.size();
00151
00152 while ((i < n) && (x[i].max() == y[i].min()))
00153 i++;
00154
00155 if (i == n) {
00156 if (strict)
00157 return ES_FIX;
00158 else
00159 goto rewrite_lq;
00160 }
00161
00162 if (x[i].max() < y[i].min())
00163 goto rewrite_lq;
00164
00165 if (x[i].min() > y[i].max()) {
00166
00167 for (int j=i; j<n; j++) {
00168 x[j].cancel(home,*this,PC_INT_BND);
00169 y[j].cancel(home,*this,PC_INT_BND);
00170 }
00171 x.size(i); y.size(i);
00172 strict = true;
00173 }
00174
00175 return ES_FIX;
00176 }
00177
00178 if (x[1].min() >= y[1].max()) {
00179
00180
00181
00182
00183
00184
00185 int i = 2;
00186 int n = x.size();
00187
00188 while ((i < n) && (x[i].min() == y[i].max()))
00189
00190 i++;
00191
00192 if (i == n) {
00193 if (strict)
00194 goto rewrite_le;
00195 else
00196 return ES_FIX;
00197 }
00198
00199 if (x[i].min() > y[i].max())
00200 goto rewrite_le;
00201
00202 if (x[i].max() < y[i].min()) {
00203
00204 for (int j=i; j<n; j++) {
00205 x[j].cancel(home,*this,PC_INT_BND);
00206 y[j].cancel(home,*this,PC_INT_BND);
00207 }
00208 x.size(i); y.size(i);
00209 strict = false;
00210 }
00211
00212 return ES_FIX;
00213 }
00214
00215 return ES_FIX;
00216
00217 rewrite_le:
00218 GECODE_REWRITE(*this,Le<View>::post(home(*this),x[0],y[0]));
00219 rewrite_lq:
00220 GECODE_REWRITE(*this,Lq<View>::post(home(*this),x[0],y[0]));
00221 }
00222
00223 template<class View>
00224 ExecStatus
00225 Lex<View>::post(Home home,
00226 ViewArray<View>& x, ViewArray<View>& y, bool strict){
00227 if (x.size() == 0)
00228 return strict ? ES_FAILED : ES_OK;
00229 if (x.size() == 1) {
00230 if (strict)
00231 return Le<View>::post(home,x[0],y[0]);
00232 else
00233 return Lq<View>::post(home,x[0],y[0]);
00234 }
00235 (void) new (home) Lex<View>(home,x,y,strict);
00236 return ES_OK;
00237 }
00238
00239 template<class View>
00240 size_t
00241 Lex<View>::dispose(Space& home) {
00242 assert(!home.failed());
00243 x.cancel(home,*this,PC_INT_BND);
00244 y.cancel(home,*this,PC_INT_BND);
00245 (void) Propagator::dispose(home);
00246 return sizeof(*this);
00247 }
00248
00249 }}}
00250
00251