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 namespace Gecode { namespace Int { namespace GCC {
00038
00039 template <class View, class Card, bool isView>
00040 inline
00041 Val<View, Card, isView>::Val(Space* home, ViewArray<View>& x0,
00042 ViewArray<Card>& k0)
00043 : Propagator(home), x(x0), k(k0){
00044 force(home);
00045 x.subscribe(home, this, PC_INT_VAL);
00046 k.subscribe(home, this, PC_INT_VAL);
00047 }
00048
00049 template <class View, class Card, bool isView>
00050 forceinline
00051 Val<View, Card, isView>::Val(Space* home, bool share,
00052 Val<View, Card, isView>& p)
00053 : Propagator(home,share,p) {
00054 x.update(home,share, p.x);
00055 k.update(home,share, p.k);
00056 }
00057
00058 template <class View, class Card, bool isView>
00059 size_t
00060 Val<View, Card, isView>::dispose(Space* home) {
00061 unforce(home);
00062 x.cancel(home,this, PC_INT_VAL);
00063 k.cancel(home,this, PC_INT_VAL);
00064 (void) Propagator::dispose(home);
00065 return sizeof(*this);
00066 }
00067
00068 template <class View, class Card, bool isView>
00069 Actor*
00070 Val<View, Card, isView>::copy(Space* home, bool share) {
00071 return new (home) Val<View, Card, isView>(home,share,*this);
00072 }
00073
00074 template <class View, class Card, bool isView>
00075 ExecStatus
00076 Val<View, Card, isView>::post(Space* home,
00077 ViewArray<View>& x0,
00078 ViewArray<Card>& k0) {
00079 new (home) Val<View, Card, isView>(home, x0, k0);
00080 return ES_OK;
00081 }
00082
00088 template <class View, class Card, bool isView>
00089 PropCost
00090 Val<View, Card, isView>::cost(ModEventDelta) const {
00091 return PC_LINEAR_HI;
00092 }
00093
00094 template <class View, class Card, bool isView>
00095 Support::Symbol
00096 Val<View, Card, isView>::ati(void) {
00097 return Reflection::mangle<View,Card>("Gecode::Int::GCC::Val",isView);
00098 }
00099
00100 template <class View, class Card, bool isView>
00101 Reflection::ActorSpec
00102 Val<View,Card,isView>::spec(const Space* home,
00103 Reflection::VarMap& m) const {
00104 Reflection::ActorSpec s(ati());
00105 return s << x.spec(home, m) << k.spec(home, m);
00106 }
00107
00108 template <class View, class Card, bool isView>
00109 void
00110 Val<View,Card,isView>::post(Space* home, Reflection::VarMap& vars,
00111 const Reflection::ActorSpec& spec) {
00112 spec.checkArity(2);
00113 ViewArray<View> x(home, vars, spec[0]);
00114 ViewArray<Card> k(home, vars, spec[1]);
00115 (void) new (home) Val(home, x, k);
00116 }
00117
00118 template <class View, class Card, bool isView>
00119 ExecStatus
00120 Val<View, Card, isView>::propagate(Space* home, ModEventDelta) {
00121 assert(x.size() > 0);
00122
00123 bool mod = false;
00124 int n = x.size();
00125 int m = k.size();
00126
00127
00128 GECODE_AUTOARRAY(int, count, m);
00129
00130 GECODE_AUTOARRAY(int, rem, m);
00131
00132 GECODE_AUTOARRAY(bool, onrem, m);
00133
00134 int rs = 0;
00135
00136
00137 int sum_min = 0;
00138 int removed = 0;
00139 for (int i = m; i--; ) {
00140
00141 removed += k[i].counter();
00142 sum_min += k[i].min();
00143
00144 count[i] = 0;
00145 onrem[i] = false;
00146 }
00147
00148 for (int i = m; i--; ) {
00149
00150
00151 if (!k[i].assigned()) {
00152 int mub = n + removed - (sum_min - k[i].min());
00153 ModEvent me = k[i].lq(home, mub);
00154 GECODE_ME_CHECK(me);
00155 mod |= (me_modified(me) && k[i].max() != mub);
00156 }
00157 }
00158
00159
00160 bool all_assigned = true;
00161
00162 int noa = 0;
00163
00164 int t_noa = 0;
00165 for (int i = n; i--; ) {
00166 bool b = x[i].assigned();
00167 all_assigned &= b;
00168 if (b) {
00169 int idx = lookupValue(k,x[i].val());
00170 if (idx == -1)
00171 return ES_FAILED;
00172 count[idx]++;
00173 noa++;
00174 }
00175 }
00176
00177
00178 int non = x.size() - noa;
00179
00180
00181 if (all_assigned) {
00182
00183 for (int i = m; i--; ) {
00184 int ci = count[i] + k[i].counter();
00185 if (!(k[i].min() <= ci && ci <= k[i].max())) {
00186 return ES_FAILED;
00187 }
00188
00189 if (isView) {
00190 if (!k[i].assigned()) {
00191 ModEvent me = k[i].eq(home, ci);
00192 GECODE_ME_CHECK(me);
00193 mod |= k[i].assigned();
00194 }
00195 }
00196 }
00197 return ES_SUBSUMED(this,home);
00198 }
00199
00200
00201 int req = 0;
00202
00203
00204 int n_r = 0;
00205
00206
00207 int single = 0;
00208
00209 for (int i = m; i--; ) {
00210 int ci = count[i] + k[i].counter();
00211 t_noa += ci;
00212 if (ci == 0) {
00213 req += k[i].min();
00214 n_r++;
00215 single = i;
00216 }
00217
00218
00219
00220 if (req > non) {
00221 return ES_FAILED;
00222 }
00223 }
00224
00225
00226 if (req == non && n_r == 1) {
00227 for (int i = n; i--; ) {
00228
00229 if (!x[i].assigned()) {
00230 ModEvent me = x[i].eq(home, k[single].card());
00231 count[single]++;
00232 GECODE_ME_CHECK(me);
00233 }
00234 }
00235
00236 if (x.shared() && count[single] < k[single].min()) {
00237 count[single] = k[single].min();
00238 }
00239
00240 for (int i = m; i--; ) {
00241 int ci = count[i] + k[i].counter();
00242
00243 if (!(k[i].min() <= ci && ci <= k[i].max())) {
00244 return ES_FAILED;
00245 }
00246
00247 if (isView) {
00248 if (!k[i].assigned()) {
00249 ModEvent me = k[i].eq(home, ci);
00250 GECODE_ME_CHECK(me);
00251 }
00252 }
00253 }
00254 return ES_SUBSUMED(this,home);
00255 }
00256
00257 for (int i = m; i--; ) {
00258 int ci = count[i] + k[i].counter();
00259 if (ci == k[i].max() && !onrem[i]) {
00260 rem[rs] = k[i].card();
00261 k[i].counter(ci);
00262 rs++;
00263 onrem[i] = true;
00264 if (isView) {
00265
00266 if (!k[i].assigned()) {
00267 ModEvent me = k[i].eq(home, ci);
00268 GECODE_ME_CHECK(me);
00269 mod |= k[i].assigned();
00270 }
00271 }
00272 } else {
00273 if (ci > k[i].max())
00274 return ES_FAILED;
00275
00276
00277 if (isView) {
00278 if (!k[i].assigned()) {
00279 if (ci > k[i].min()) {
00280 ModEvent me = k[i].gq(home, ci);
00281 GECODE_ME_CHECK(me);
00282 mod |= k[i].assigned();
00283 mod |= (me_modified(me) && k[i].min() != ci);
00284 }
00285 int occupied = t_noa - ci;
00286 int mub = x.size() + removed - occupied;
00287
00288 ModEvent me = k[i].lq(home, mub);
00289 GECODE_ME_CHECK(me);
00290 mod |= k[i].assigned();
00291 mod |= (me_failed(me) && k[i].max() != mub);
00292 }
00293 }
00294 }
00295
00296 count[i] = 0;
00297 }
00298
00299
00300 for (int i = n; i--; ) {
00301 bool b = x[i].assigned();
00302 if (b) {
00303 int idx = lookupValue(k,x[i].val());
00304 if (idx == -1)
00305 return ES_FAILED;
00306 if (onrem[idx]) {
00307 x[i] = x[--n];
00308 x.size(n);
00309 }
00310 }
00311 }
00312
00313
00314 if (rs > 0) {
00315 IntSet remset(&rem[0], rs);
00316 for (int i = x.size(); i--;) {
00317 IntSetRanges rr(remset);
00318 if (!x[i].assigned()) {
00319 ModEvent me = x[i].minus_r(home, rr);
00320 if (me_failed(me))
00321 return ES_FAILED;
00322 mod |= x[i].assigned();
00323 }
00324 }
00325 }
00326
00327 all_assigned = true;
00328
00329 for (int i = x.size(); i--; ) {
00330 bool b = x[i].assigned();
00331 all_assigned &= b;
00332 if (b) {
00333 int idx = lookupValue(k,x[i].val());
00334 if (idx == -1)
00335 return ES_FAILED;
00336 count[idx]++;
00337 }
00338 }
00339
00340 if (all_assigned) {
00341 for (int i = k.size(); i--; ) {
00342 int ci = count[i] + k[i].counter();
00343 if (!(k[i].min() <= ci && ci <= k[i].max())) {
00344 return ES_FAILED;
00345 }
00346
00347 if (isView) {
00348 if (!k[i].assigned()) {
00349 ModEvent me = k[i].eq(home, ci);
00350 GECODE_ME_CHECK(me);
00351 mod |= k[i].assigned();
00352 }
00353 }
00354 }
00355 return ES_SUBSUMED(this,home);
00356 }
00357
00358 if (isView) {
00359
00360 int reqmin = 0;
00361 int allmax = 0;
00362 m = k.size();
00363 n = x.size();
00364 for (int i = m; i--; ) {
00365 int ci = k[i].counter();
00366 if (ci > k[i].max() ) {
00367 return ES_FAILED;
00368 } else {
00369 allmax += (k[i].max() - ci);
00370 if (ci < k[i].min()) {
00371 reqmin += (k[i].min() - ci);
00372 }
00373 }
00374 if (k[i].min() > n) {
00375 return ES_FAILED;
00376 }
00377 if (!k[i].assigned()) {
00378 ModEvent me = k[i].lq(home, n);
00379 if (me_failed(me)) {
00380 return ES_FAILED;
00381 }
00382 }
00383 }
00384
00385 if (n < reqmin) {
00386 return ES_FAILED;
00387 }
00388
00389 if (allmax < n) {
00390 return ES_FAILED;
00391 }
00392 }
00393
00394 return mod ? ES_NOFIX : ES_FIX;
00395 }
00396
00397 }}}
00398
00399
00400