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