00001
00002
00003
00004
00005
00006
00007
00008
00009
00010
00011
00012
00013
00014
00015
00016
00017
00018
00019
00020
00021 namespace Gecode { namespace Int { namespace GCC {
00022
00023 template <class View, class Card, bool isView>
00024 forceinline ExecStatus
00025 prop_val(Space* home, ViewArray<View>& x, Card& k){
00026
00027 bool mod = false;
00028 int n = x.size();
00029 int m = k.size();
00030
00031
00032 GECODE_AUTOARRAY(int, count, m);
00033
00034 GECODE_AUTOARRAY(int, rem, m);
00035
00036 GECODE_AUTOARRAY(bool, onrem, m);
00037
00038 int rs = 0;
00039
00040
00041
00042 int sum_min = 0;
00043 int removed = 0;
00044 for (int i = m; i--; ) {
00045
00046 removed += k[i].counter();
00047 sum_min += k[i].min();
00048
00049 count[i] = 0;
00050 onrem[i] = false;
00051
00052 }
00053
00054 for (int i = m; i--; ) {
00055
00056
00057 if (!k[i].assigned()) {
00058 int mub = n + removed - (sum_min - k[i].min());
00059 ModEvent me = k[i].lq(home, mub);
00060 GECODE_ME_CHECK(me);
00061 if (me_modified(me) && k[i].max() != mub) {
00062 mod |= ES_NOFIX;
00063 }
00064 }
00065 }
00066
00067
00068
00069 bool all_assigned = true;
00070
00071 int noa = 0;
00072
00073 int t_noa = 0;
00074 for (int i = n; i--; ) {
00075 bool b = x[i].assigned();
00076 all_assigned &= b;
00077 if (b) {
00078 int idx = k.lookup(x[i].val());
00079 if (idx == -1) {
00080 return ES_FAILED;
00081 }
00082 count[idx]++;
00083 noa++;
00084 }
00085 }
00086
00087
00088 int non = x.size() - noa;
00089
00090
00091 if (all_assigned) {
00092
00093 for (int i = m; i--; ) {
00094 int ci = count[i] + k[i].counter();
00095 if (!(k[i].min() <= ci && ci <= k[i].max())) {
00096 return ES_FAILED;
00097 }
00098
00099 if (isView) {
00100 ModEvent me = k[i].eq(home, ci);
00101 GECODE_ME_CHECK(me);
00102 mod |= k[i].assigned();
00103 }
00104 }
00105 return ES_SUBSUMED;
00106 }
00107
00108
00109 int req = 0;
00110
00111
00112 int n_r = 0;
00113
00114
00115 int single = 0;
00116
00117 for (int i = m; i--; ) {
00118 int ci = count[i] + k[i].counter();
00119 t_noa += ci;
00120 if (ci == 0) {
00121 req += k[i].min();
00122 n_r++;
00123 single = i;
00124 }
00125
00126
00127
00128 if (req > non) {
00129 return ES_FAILED;
00130 }
00131 }
00132
00133
00134 if (req == non && n_r == 1) {
00135 for (int i = n; i--; ) {
00136
00137 if (!x[i].assigned()) {
00138 ModEvent me = x[i].eq(home, k[single].card());
00139 count[single]++;
00140 GECODE_ME_CHECK(me);
00141 }
00142 }
00143
00144 for (int i = m; i--; ) {
00145 int ci = count[i] + k[i].counter();
00146
00147 if (!(k[i].min() <= ci && ci <= k[i].max())) {
00148 return ES_FAILED;
00149 }
00150
00151 if (isView) {
00152 ModEvent me = k[i].eq(home, ci);
00153 GECODE_ME_CHECK(me);
00154 }
00155 }
00156 return ES_SUBSUMED;
00157 }
00158
00159 for (int i = m; i--; ) {
00160 int ci = count[i] + k[i].counter();
00161 if (ci == k[i].max() && !onrem[i]) {
00162 rem[rs] = k[i].card();
00163 k[i].counter(ci);
00164 rs++;
00165 onrem[i] = true;
00166 if (isView) {
00167
00168 ModEvent me = k[i].eq(home, ci);
00169 GECODE_ME_CHECK(me);
00170 mod |= k[i].assigned();
00171 }
00172 } else {
00173 if (ci > k[i].max()) {
00174 return ES_FAILED;
00175 }
00176
00177
00178 if (isView) {
00179 if (ci > k[i].min()) {
00180 ModEvent me = k[i].gq(home, ci);
00181 GECODE_ME_CHECK(me);
00182 if (me_modified(me) && k[i].min() != ci) {
00183 mod |= ES_NOFIX;
00184 }
00185 mod |= k[i].assigned();
00186 }
00187 int occupied = t_noa - ci;
00188 int mub = x.size() + removed - occupied;
00189 ModEvent me = k[i].lq(home, mub);
00190 GECODE_ME_CHECK(me);
00191 if (me_failed(me) && k[i].max() != mub) {
00192 mod |= ES_NOFIX;
00193 }
00194 mod |= k[i].assigned();
00195 }
00196 }
00197 }
00198
00199
00200 for (int i = n; i--; ) {
00201 bool b = x[i].assigned();
00202 if (b) {
00203 int idx = k.lookup(x[i].val());
00204 if (idx == -1) {
00205 return ES_FAILED;
00206 }
00207 if (onrem[idx]) {
00208 x.move_lst(i);
00209 }
00210 }
00211 }
00212
00213
00214 if (rs > 0) {
00215 IntSet remset(&rem[0], rs);
00216 IntSetRanges rr(remset);
00217 for (int i = x.size(); i--;) {
00218 if (!x[i].assigned()) {
00219 ModEvent me = x[i].minus(home, rr);
00220 if (me_failed(me)) {
00221 return ES_FAILED;
00222 }
00223 mod |= x[i].assigned();
00224 }
00225 }
00226 }
00227
00228
00229
00230 int cmin = x[x.size() - 1].min();
00231 int cmax = x[x.size() - 1].max();
00232
00233 for (int i = x.size() - 1; i--; ) {
00234 if (x[i].min() < cmin) {
00235 cmin = x[i].min();
00236 }
00237 if (x[i].max() > cmax) {
00238 cmax = x[i].max();
00239 }
00240 }
00241
00242 all_assigned = true;
00243
00244 for (int i = m; i--; ) {
00245 count[i] = 0;
00246 }
00247
00248 for (int i = x.size(); i--; ) {
00249 bool b = x[i].assigned();
00250 all_assigned &= b;
00251 if (b) {
00252 int idx = k.lookup(x[i].val());
00253 if (idx == -1) {
00254 return ES_FAILED;
00255 }
00256 count[idx]++;
00257 }
00258 }
00259
00260 if (all_assigned) {
00261 for (int i = k.size(); i--; ) {
00262 int ci = count[i] + k[i].counter();
00263 if (!(k[i].min() <= ci && ci <= k[i].max())) {
00264 return ES_FAILED;
00265 }
00266
00267 if (isView) {
00268 ModEvent me = k[i].eq(home, ci);
00269 GECODE_ME_CHECK(me);
00270 mod |= k[i].assigned();
00271 }
00272 }
00273 return ES_SUBSUMED;
00274 }
00275
00276 return mod ? ES_NOFIX : ES_FIX;
00277 }
00278
00279
00280
00281
00282
00283
00284 template <class View, class Card, bool isView>
00285 forceinline
00286 Val<View, Card, isView>::Val(Space* home, ViewArray<View>& x0, Card& k0)
00287 :Propagator(home, true), x(x0), k(k0){
00288 x.subscribe(home, this, PC_INT_VAL);
00289 k.subscribe(home, this, PC_INT_VAL);
00290 }
00291
00292 template <class View, class Card, bool isView>
00293 forceinline
00294 Val<View, Card, isView>::Val(Space* home, bool share,
00295 Val<View, VarCard, isView>& p)
00296 : Propagator(home,share,p){
00297 x.update(home,share, p.x);
00298 k.update(home,share, p.k);
00299 }
00300
00301 template <class View, class Card, bool isView>
00302 forceinline
00303 Val<View, Card, isView>::Val(Space* home, bool share,
00304 Val<View, FixCard, isView>& p)
00305 : Propagator(home,share,p), k(p.k.size()){
00306 x.update(home,share, p.x);
00307 k.update(home,share, p.k);
00308 }
00309
00310 template <class View, class Card, bool isView>
00311 Val<View, Card, isView>::~Val(void){
00312 x.cancel(this, PC_INT_VAL);
00313 k.cancel(this, PC_INT_VAL);
00314 }
00315
00316 template <class View, class Card, bool isView>
00317 Actor*
00318 Val<View, Card, isView>::copy(Space* home, bool share) {
00319 return new (home) Val<View, Card, isView>(home,share,*this);
00320 }
00321
00322 template <class View, class Card, bool isView>
00323 ExecStatus Val<View, Card, isView>::post(Space* home,
00324 ViewArray<View>& x0,
00325 Card& k0) {
00326 new (home) Val<View, Card, isView>(home, x0, k0);
00327 return ES_OK;
00328 }
00329
00335 template <class View, class Card, bool isView>
00336 forceinline PropCost
00337 Val<View, Card, isView>::cost (void) const {
00338 return PC_LINEAR_HI;
00339 }
00340
00341 template <class View, class Card, bool isView>
00342 forceinline ExecStatus
00343 Val<View, Card, isView>::propagate(Space* home) {
00344 assert(x.size() > 0);
00345
00346 int max = x[0].max();
00347 for (int i = 1; i < x.size(); i++) {
00348 if (x[i].max() > max) {
00349 max = x[i].max();
00350 }
00351 }
00352
00353 for (int i = 0; i < k.size(); i++) {
00354 if (k[i].card() > max &&
00355 k[i].min() > 0 &&
00356 k[i].max() != k[i].counter() ){
00357 return ES_FAILED;
00358 }
00359 }
00360 ExecStatus es = prop_val<View, Card, isView>(home, x, k);
00361 return es;
00362 }
00363
00364 }}}
00365
00366
00367