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 Linear {
00039
00040
00041
00042
00043
00044 template<class XV, class YV>
00045 LinBoolView<XV,YV>::LinBoolView(Home home,
00046 ViewArray<XV>& x0, YV y0, int c0)
00047 : Propagator(home), x(x0), y(y0), c(c0) {
00048 x.subscribe(home,*this,PC_INT_VAL);
00049 y.subscribe(home,*this,PC_INT_BND);
00050 }
00051
00052 template<class XV, class YV>
00053 forceinline size_t
00054 LinBoolView<XV,YV>::dispose(Space& home) {
00055 assert(!home.failed());
00056 x.cancel(home,*this,PC_INT_VAL);
00057 y.cancel(home,*this,PC_INT_BND);
00058 (void) Propagator::dispose(home);
00059 return sizeof(*this);
00060 }
00061
00062 template<class XV, class YV>
00063 forceinline
00064 LinBoolView<XV,YV>::LinBoolView(Space& home, bool share, LinBoolView& p)
00065 : Propagator(home,share,p), c(p.c) {
00066 x.update(home,share,p.x);
00067 y.update(home,share,p.y);
00068 }
00069
00070 template<class XV, class YV>
00071 PropCost
00072 LinBoolView<XV,YV>::cost(const Space&, const ModEventDelta&) const {
00073 return PropCost::linear(PropCost::LO, x.size());
00074 }
00075
00076
00077
00078
00079
00080
00081 template<class XV, class YV>
00082 forceinline
00083 EqBoolView<XV,YV>::EqBoolView(Home home, ViewArray<XV>& x, YV y, int c)
00084 : LinBoolView<XV,YV>(home,x,y,c) {}
00085
00086 template<class XV, class YV>
00087 ExecStatus
00088 EqBoolView<XV,YV>::post(Home home, ViewArray<XV>& x, YV y, int c) {
00089 if (y.assigned())
00090 return EqBoolInt<XV>::post(home,x,y.val()+c);
00091 int n = x.size();
00092 for (int i = n; i--; )
00093 if (x[i].one()) {
00094 x[i]=x[--n]; c--;
00095 } else if (x[i].zero()) {
00096 x[i]=x[--n];
00097 }
00098 x.size(n);
00099 GECODE_ME_CHECK(y.lq(home,n-c));
00100 GECODE_ME_CHECK(y.gq(home,-c));
00101 if (n == 0)
00102 return ES_OK;
00103 if (y.min()+c == n) {
00104 assert(y.assigned());
00105 for (int i = n; i--; )
00106 GECODE_ME_CHECK(x[i].one_none(home));
00107 return ES_OK;
00108 }
00109 if (y.max()+c == 0) {
00110 assert(y.assigned());
00111 for (int i = n; i--; )
00112 GECODE_ME_CHECK(x[i].zero_none(home));
00113 return ES_OK;
00114 }
00115 (void) new (home) EqBoolView<XV,YV>(home,x,y,c);
00116 return ES_OK;
00117 }
00118
00119 template<class XV, class YV>
00120 forceinline
00121 EqBoolView<XV,YV>::EqBoolView(Space& home, bool share, EqBoolView<XV,YV>& p)
00122 : LinBoolView<XV,YV>(home,share,p) {}
00123
00124 template<class XV, class YV>
00125 Actor*
00126 EqBoolView<XV,YV>::copy(Space& home, bool share) {
00127 return new (home) EqBoolView<XV,YV>(home,share,*this);
00128 }
00129
00130 template<class XV, class YV>
00131 ExecStatus
00132 EqBoolView<XV,YV>::propagate(Space& home, const ModEventDelta&) {
00133 int n = x.size();
00134 for (int i = n; i--; )
00135 if (x[i].one()) {
00136 x[i]=x[--n]; c--;
00137 } else if (x[i].zero()) {
00138 x[i]=x[--n];
00139 }
00140 x.size(n);
00141 GECODE_ME_CHECK(y.lq(home,n-c));
00142 GECODE_ME_CHECK(y.gq(home,-c));
00143 if (n == 0)
00144 return ES_SUBSUMED(*this,sizeof(*this));
00145 if (y.min()+c == n) {
00146 assert(y.assigned());
00147 for (int i = n; i--; )
00148 GECODE_ME_CHECK(x[i].one_none(home));
00149 return ES_SUBSUMED(*this,sizeof(*this));
00150 }
00151 if (y.max()+c == 0) {
00152 assert(y.assigned());
00153 for (int i = n; i--; )
00154 GECODE_ME_CHECK(x[i].zero_none(home));
00155 return ES_SUBSUMED(*this,sizeof(*this));
00156 }
00157 if (y.assigned())
00158 GECODE_REWRITE(*this,EqBoolInt<XV>::post(home(*this),x,y.val()+c));
00159 return ES_FIX;
00160 }
00161
00162
00163
00164
00165
00166
00167 template<class XV, class YV>
00168 forceinline
00169 NqBoolView<XV,YV>::NqBoolView(Home home, ViewArray<XV>& x, YV y, int c)
00170 : LinBoolView<XV,YV>(home,x,y,c) {}
00171
00172 template<class XV, class YV>
00173 ExecStatus
00174 NqBoolView<XV,YV>::post(Home home, ViewArray<XV>& x, YV y, int c) {
00175 if (y.assigned())
00176 return NqBoolInt<XV>::post(home,x,y.val()+c);
00177 int n = x.size();
00178 for (int i = n; i--; )
00179 if (x[i].one()) {
00180 x[i]=x[--n]; c--;
00181 } else if (x[i].zero()) {
00182 x[i]=x[--n];
00183 }
00184 x.size(n);
00185 if ((n-c < y.min() ) || (-c > y.max()))
00186 return ES_OK;
00187 if (n == 0) {
00188 GECODE_ME_CHECK(y.nq(home,-c));
00189 return ES_OK;
00190 }
00191 if ((n == 1) && y.assigned()) {
00192 if (y.val()+c == 1) {
00193 GECODE_ME_CHECK(x[0].zero_none(home));
00194 } else {
00195 assert(y.val()+c == 0);
00196 GECODE_ME_CHECK(x[0].one_none(home));
00197 }
00198 return ES_OK;
00199 }
00200 (void) new (home) NqBoolView<XV,YV>(home,x,y,c);
00201 return ES_OK;
00202 }
00203
00204
00205 template<class XV, class YV>
00206 forceinline
00207 NqBoolView<XV,YV>::NqBoolView(Space& home, bool share, NqBoolView<XV,YV>& p)
00208 : LinBoolView<XV,YV>(home,share,p) {}
00209
00210 template<class XV, class YV>
00211 Actor*
00212 NqBoolView<XV,YV>::copy(Space& home, bool share) {
00213 return new (home) NqBoolView<XV,YV>(home,share,*this);
00214 }
00215
00216 template<class XV, class YV>
00217 ExecStatus
00218 NqBoolView<XV,YV>::propagate(Space& home, const ModEventDelta&) {
00219 int n = x.size();
00220 for (int i = n; i--; )
00221 if (x[i].one()) {
00222 x[i]=x[--n]; c--;
00223 } else if (x[i].zero()) {
00224 x[i]=x[--n];
00225 }
00226 x.size(n);
00227 if ((n-c < y.min() ) || (-c > y.max()))
00228 return ES_SUBSUMED(*this,home);
00229 if (n == 0) {
00230 GECODE_ME_CHECK(y.nq(home,-c));
00231 return ES_SUBSUMED(*this,home);
00232 }
00233 if ((n == 1) && y.assigned()) {
00234 if (y.val()+c == 1) {
00235 GECODE_ME_CHECK(x[0].zero_none(home));
00236 } else {
00237 assert(y.val()+c == 0);
00238 GECODE_ME_CHECK(x[0].one_none(home));
00239 }
00240 return ES_SUBSUMED(*this,sizeof(*this));
00241 }
00242 return ES_FIX;
00243 }
00244
00245
00246
00247
00248
00249
00250 template<class XV, class YV>
00251 forceinline
00252 GqBoolView<XV,YV>::GqBoolView(Home home, ViewArray<XV>& x, YV y, int c)
00253 : LinBoolView<XV,YV>(home,x,y,c) {}
00254
00255 template<class XV, class YV>
00256 ExecStatus
00257 GqBoolView<XV,YV>::post(Home home, ViewArray<XV>& x, YV y, int c) {
00258 if (y.assigned())
00259 return GqBoolInt<XV>::post(home,x,y.val()+c);
00260
00261 int n = x.size();
00262 for (int i = n; i--; )
00263 if (x[i].one()) {
00264 x[i]=x[--n]; c--;
00265 } else if (x[i].zero()) {
00266 x[i]=x[--n];
00267 }
00268 x.size(n);
00269 GECODE_ME_CHECK(y.lq(home,n-c));
00270 if (-c >= y.max())
00271 return ES_OK;
00272 if (y.min()+c == n) {
00273 for (int i = n; i--; )
00274 GECODE_ME_CHECK(x[i].one_none(home));
00275 return ES_OK;
00276 }
00277 (void) new (home) GqBoolView<XV,YV>(home,x,y,c);
00278 return ES_OK;
00279 }
00280
00281
00282 template<class XV, class YV>
00283 forceinline
00284 GqBoolView<XV,YV>::GqBoolView(Space& home, bool share, GqBoolView<XV,YV>& p)
00285 : LinBoolView<XV,YV>(home,share,p) {}
00286
00287 template<class XV, class YV>
00288 Actor*
00289 GqBoolView<XV,YV>::copy(Space& home, bool share) {
00290 return new (home) GqBoolView<XV,YV>(home,share,*this);
00291 }
00292
00293 template<class XV, class YV>
00294 ExecStatus
00295 GqBoolView<XV,YV>::propagate(Space& home, const ModEventDelta&) {
00296 int n = x.size();
00297 for (int i = n; i--; )
00298 if (x[i].one()) {
00299 x[i]=x[--n]; c--;
00300 } else if (x[i].zero()) {
00301 x[i]=x[--n];
00302 }
00303 x.size(n);
00304 GECODE_ME_CHECK(y.lq(home,n-c));
00305 if (-c >= y.max())
00306 return ES_SUBSUMED(*this,home);
00307 if (y.min()+c == n) {
00308 for (int i = n; i--; )
00309 GECODE_ME_CHECK(x[i].one_none(home));
00310 return ES_SUBSUMED(*this,home);
00311 }
00312 if (y.assigned())
00313 GECODE_REWRITE(*this,GqBoolInt<XV>::post(home(*this),x,y.val()+c));
00314 return ES_FIX;
00315 }
00316
00317 }}}
00318
00319
00320