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