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