00001
00002
00003
00004
00005
00006
00007
00008
00009
00010
00011
00012
00013
00014
00015
00016
00017
00018
00019
00020
00021
00022 namespace Gecode { namespace Int { namespace Linear {
00023
00024
00025
00026
00027
00028 template <class View>
00029 LinBool<View>::LinBool(Space* home, ViewArray<BoolView>& x0, int n0, View y0)
00030 : Propagator(home), x(x0), n(n0), y(y0) {
00031 x.subscribe(home,this,PC_INT_VAL);
00032 y.subscribe(home,this,PC_INT_BND);
00033 }
00034
00035 template <class View>
00036 size_t
00037 LinBool<View>::dispose(Space* home) {
00038 assert(!home->failed());
00039 x.cancel(home,this,PC_INT_VAL);
00040 y.cancel(home,this,PC_INT_BND);
00041 (void) Propagator::dispose(home);
00042 return sizeof(*this);
00043 }
00044
00045 template <class View>
00046 forceinline
00047 LinBool<View>::LinBool(Space* home, bool share, LinBool& p)
00048 : Propagator(home,share,p), n(p.n) {
00049 x.update(home,share,p.x);
00050 y.update(home,share,p.y);
00051 }
00052
00053 template <class View>
00054 PropCost
00055 LinBool<View>::cost(void) const {
00056 return cost_lo(x.size(),PC_LINEAR_LO);
00057 }
00058
00059 template <class View>
00060 void
00061 LinBool<View>::eliminate(void) {
00062 int e = 0;
00063 int m = x.size();
00064 for (int i = m; i--; )
00065 if (x[i].assigned()) {
00066 e+=x[i].val(); x[i]=x[--m];
00067 }
00068 x.size(m);
00069 n -= e;
00070 }
00071
00072 template <class View>
00073 void
00074 LinBool<View>::all_one(Space* home) {
00075 for (int i = x.size(); i--; )
00076 x[i].t_one_none(home);
00077 }
00078
00079 template <class View>
00080 void
00081 LinBool<View>::all_zero(Space* home) {
00082 for (int i = x.size(); i--; )
00083 x[i].t_zero_none(home);
00084 }
00085
00086
00087
00088
00089
00090
00091 template <class View>
00092 forceinline
00093 EqBool<View>::EqBool(Space* home, ViewArray<BoolView>& x, int n, View y)
00094 : LinBool<View>(home,x,n,y) {}
00095
00096 template <class View>
00097 ExecStatus
00098 EqBool<View>::post(Space* home, ViewArray<BoolView>& x, int n, View y) {
00099 (void) new (home) EqBool<View>(home,x,n,y);
00100 return ES_OK;
00101 }
00102
00103 template <class View>
00104 forceinline
00105 EqBool<View>::EqBool(Space* home, bool share, EqBool<View>& p)
00106 : LinBool<View>(home,share,p) {}
00107
00108 template <class View>
00109 Actor*
00110 EqBool<View>::copy(Space* home, bool share) {
00111 return new (home) EqBool<View>(home,share,*this);
00112 }
00113
00114 template <class View>
00115 ExecStatus
00116 EqBool<View>::propagate(Space* home) {
00117 this->eliminate();
00118 GECODE_ME_CHECK(y.lq(home,x.size() - n));
00119 GECODE_ME_CHECK(y.gq(home,-n));
00120 if (x.size() == 0)
00121 return ES_SUBSUMED;
00122 if (y.min()+n == x.size()) {
00123 assert(y.assigned());
00124 this->all_one(home); return ES_SUBSUMED;
00125 }
00126 if (y.max()+n == 0) {
00127 assert(y.assigned());
00128 this->all_zero(home); return ES_SUBSUMED;
00129 }
00130 return ES_FIX;
00131 }
00132
00133
00134
00135
00136
00137
00138 template <class View>
00139 forceinline
00140 NqBool<View>::NqBool(Space* home, ViewArray<BoolView>& x, int n, View y)
00141 : LinBool<View>(home,x,n,y) {}
00142
00143 template <class View>
00144 ExecStatus
00145 NqBool<View>::post(Space* home, ViewArray<BoolView>& x, int n, View y) {
00146 (void) new (home) NqBool<View>(home,x,n,y);
00147 return ES_OK;
00148 }
00149
00150
00151 template <class View>
00152 forceinline
00153 NqBool<View>::NqBool(Space* home, bool share, NqBool<View>& p)
00154 : LinBool<View>(home,share,p) {}
00155
00156 template <class View>
00157 Actor*
00158 NqBool<View>::copy(Space* home, bool share) {
00159 return new (home) NqBool<View>(home,share,*this);
00160 }
00161
00162
00163 template <class View>
00164 ExecStatus
00165 NqBool<View>::propagate(Space* home) {
00166 this->eliminate();
00167 if ((x.size()-n < y.min() ) || (-n > y.max()))
00168 return ES_SUBSUMED;
00169 if (x.size() == 0) {
00170 GECODE_ME_CHECK(y.nq(home,-n));
00171 return ES_SUBSUMED;
00172 }
00173 if ((x.size() == 1) && y.assigned()) {
00174 if (y.val()+n == 1) {
00175 x[0].t_zero_none(home);
00176 } else {
00177 assert(y.val()+n == 0);
00178 x[0].t_one_none(home);
00179 }
00180 return ES_SUBSUMED;
00181 }
00182 return ES_FIX;
00183 }
00184
00185
00186
00187
00188
00189
00190
00191
00192 template <class View>
00193 forceinline
00194 LqBool<View>::LqBool(Space* home, ViewArray<BoolView>& x, int n, View y)
00195 : LinBool<View>(home,x,n,y) {}
00196
00197 template <class View>
00198 ExecStatus
00199 LqBool<View>::post(Space* home, ViewArray<BoolView>& x, int n, View y) {
00200 (void) new (home) LqBool<View>(home,x,n,y);
00201 return ES_OK;
00202 }
00203
00204
00205 template <class View>
00206 forceinline
00207 LqBool<View>::LqBool(Space* home, bool share, LqBool<View>& p)
00208 : LinBool<View>(home,share,p) {}
00209
00210 template <class View>
00211 Actor*
00212 LqBool<View>::copy(Space* home, bool share) {
00213 return new (home) LqBool<View>(home,share,*this);
00214 }
00215
00216
00217 template <class View>
00218 ExecStatus
00219 LqBool<View>::propagate(Space* home) {
00220 this->eliminate();
00221 GECODE_ME_CHECK(y.gq(home,-n));
00222 if (x.size() <= y.min()+n)
00223 return ES_SUBSUMED;
00224 if (y.max()+n == 0) {
00225 this->all_zero(home); return ES_SUBSUMED;
00226 }
00227 return ES_FIX;
00228 }
00229
00230
00231
00232
00233
00234
00235
00236 template <class View>
00237 forceinline
00238 GqBool<View>::GqBool(Space* home, ViewArray<BoolView>& x, int n, View y)
00239 : LinBool<View>(home,x,n,y) {}
00240
00241 template <class View>
00242 ExecStatus
00243 GqBool<View>::post(Space* home, ViewArray<BoolView>& x, int n, View y) {
00244 (void) new (home) GqBool<View>(home,x,n,y);
00245 return ES_OK;
00246 }
00247
00248
00249 template <class View>
00250 forceinline
00251 GqBool<View>::GqBool(Space* home, bool share, GqBool<View>& p)
00252 : LinBool<View>(home,share,p) {}
00253
00254 template <class View>
00255 Actor*
00256 GqBool<View>::copy(Space* home, bool share) {
00257 return new (home) GqBool<View>(home,share,*this);
00258 }
00259
00260
00261 template <class View>
00262 ExecStatus
00263 GqBool<View>::propagate(Space* home) {
00264 this->eliminate();
00265 GECODE_ME_CHECK(y.lq(home,x.size() - n));
00266 if (-n >= y.max())
00267 return ES_SUBSUMED;
00268 if (y.min()+n == x.size()) {
00269 this->all_one(home); return ES_SUBSUMED;
00270 }
00271 return ES_FIX;
00272 }
00273
00274 }}}
00275
00276
00277