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 GCC {
00023
00024 template <class View, class Card, bool shared, bool isView>
00025 inline ExecStatus
00026 prop_bnd(Space* home, ViewArray<View>& x, Card& k,
00027 PartialSum<Card>* lps, PartialSum<Card>* ups){
00028
00029 ExecStatus es_ubc = ES_FIX;
00030 ExecStatus es_lbc = ES_FIX;
00031 int n = x.size();
00032
00033 GECODE_AUTOARRAY(int, mu, n);
00034 GECODE_AUTOARRAY(int, nu, n);
00035
00036 for (int i = n; i--; ) {
00037 nu[i] = i;
00038 mu[i] = i;
00039 }
00040
00041 MaxInc<View> max_inc(x);
00042 Support::quicksort<int, MaxInc<View> >(mu, n, max_inc);
00043
00044
00045 MinInc<View> min_inc(x);
00046 Support::quicksort<int, MinInc<View> >(nu, n, min_inc);
00047
00048
00049 assert(lps->minValue() == ups->minValue());
00050 assert(lps->maxValue() == ups->maxValue());
00051 assert(lps->minValue() <= x[nu[0]].min());
00052 assert(x[mu[x.size() - 1]].max()>= ups->maxValue());
00053
00054
00055
00056
00057
00058
00059
00060
00061
00062 GECODE_AUTOARRAY(HallInfo, hall, (2 * n + 2));
00063 GECODE_AUTOARRAY(Rank, rank, n);
00064
00065 int nb = 0;
00066
00067 int min = x[nu[0]].min();
00068 int max = x[mu[0]].max() + 1;
00069 int last = lps->firstValue + 1;
00070 hall[0].bounds = last;
00071
00072
00073
00074
00075
00076
00077
00078
00079
00080 {
00081 int i = 0;
00082 int j = 0;
00083 while (true) {
00084 if (i < n && min < max) {
00085 if (min != last) {
00086 last = min;
00087 hall[++nb].bounds = last;
00088 }
00089 rank[nu[i]].min = nb;
00090 if (++i < n) {
00091 min = x[nu[i]].min();
00092 }
00093 } else {
00094 if (max != last) {
00095 last = max;
00096 hall[++nb].bounds = last;
00097 }
00098 rank[mu[j]].max = nb;
00099 if (++j == n) {
00100 break;
00101 }
00102 max = x[mu[j]].max() + 1;
00103 }
00104 }
00105 }
00106
00107 int rightmost = nb + 1;
00108 hall[rightmost].bounds = ups->lastValue + 1 ;
00109
00110 GECODE_ES_CHECK(es_lbc = (lbc<View, Card, shared>(home, x, nb, hall, rank,
00111 lps, mu, nu)));
00112 if (es_lbc == ES_NOFIX) {
00113 return ES_NOFIX;
00114 }
00115
00116
00117 MaxInc<View> newmax(x);
00118 Support::quicksort<int, MaxInc<View> >(mu, n, newmax);
00119
00120 MinInc<View> newmin(x);
00121 Support::quicksort<int, MinInc<View> >(nu, n, newmin);
00122
00123 GECODE_ES_CHECK(es_ubc = (ubc<View, Card, shared>(home, x, nb, hall, rank,
00124 ups, mu, nu)));
00125
00126 if (es_ubc == ES_NOFIX || es_lbc == ES_NOFIX) {
00127 return ES_NOFIX;
00128 } else {
00129 return ES_FIX;
00130 }
00131 }
00132
00133
00134 template <class View, class Card, bool isView, bool shared>
00135 forceinline
00136 BndImp<View, Card, isView, shared>::
00137 BndImp(Space* home, ViewArray<View>& x0, Card& k0)
00138 : Propagator(home, true), x(x0), y(home,x0), k(k0),
00139 lps(NULL), ups(NULL){
00140
00141 y.subscribe(home, this, PC_INT_BND);
00142 k.subscribe(home, this, PC_INT_BND);
00143 }
00144
00145
00146 template <class View, class Card, bool isView, bool shared>
00147 forceinline
00148 BndImp<View, Card, isView, shared>::
00149 BndImp(Space* home, bool share, BndImp<View, VarCard, isView, shared>& p)
00150 : Propagator(home, share, p), lps(NULL), ups(NULL) {
00151 x.update(home, share, p.x);
00152 y.update(home, share, p.y);
00153 k.update(home, share, p.k);
00154 }
00155
00156 template <class View, class Card, bool isView, bool shared>
00157 forceinline
00158 BndImp<View, Card, isView, shared>::
00159 BndImp(Space* home, bool share, BndImp<View, FixCard, isView, shared>& p)
00160 : Propagator(home, share, p), k(p.k.size()),
00161 lps(NULL), ups(NULL){
00162 x.update(home, share, p.x);
00163 y.update(home, share, p.y);
00164 k.update(home, share, p.k);
00165 }
00166
00167 template <class View, class Card, bool isView, bool shared>
00168 forceinline
00169 BndImp<View, Card, isView, shared>::~BndImp(void){
00170 y.cancel(this, PC_INT_BND);
00171 k.cancel(this, PC_INT_BND);
00172 delete lps;
00173 lps = NULL;
00174 delete ups;
00175 ups = NULL;
00176 }
00177
00178 template <class View, class Card, bool isView, bool shared>
00179 forceinline Actor*
00180 BndImp<View, Card, isView, shared>::copy(Space* home, bool share){
00181 return new (home) BndImp<View, Card, isView, shared>(home, share, *this);
00182 }
00183
00184 template <class View, class Card, bool isView, bool shared>
00185 forceinline PropCost
00186 BndImp<View, Card, isView, shared>::cost (void) const {
00187
00188
00189
00190
00191
00192
00193
00194 return (View::pme(this) == ME_INT_VAL)
00195 ? cost_lo(y.size(),PC_LINEAR_LO)
00196 : cost_hi(x.size(),PC_LINEAR_HI);
00197 }
00198
00199 template <class View, class Card, bool isView, bool shared>
00200 forceinline ExecStatus
00201 BndImp<View, Card, isView, shared>::propagate(Space* home) {
00202
00203 bool all_assigned = true;
00204 bool mod = false;
00205
00206 GECODE_AUTOARRAY(int, count, k.size());
00207 for (int i = k.size(); i--; ) {
00208 count[i] = 0;
00209 }
00210
00211 for (int i = x.size(); i--; ) {
00212 bool b = x[i].assigned();
00213 all_assigned &= b;
00214 if (b) {
00215 int idx = k.lookup(x[i].val());
00216
00217
00218 if (idx == -1) {
00219 return ES_FAILED;
00220 }
00221 count[idx]++;
00222 }
00223 }
00224
00225 if (all_assigned) {
00226 for (int i = k.size(); i--; ) {
00227 int ci = count[i];
00228 if (! (k[i].min() <= ci && ci <= k[i].max())) {
00229 return ES_FAILED;
00230 } else {
00231 if (isView) {
00232 ModEvent me = k[i].eq(home, ci);
00233 GECODE_ME_CHECK(me);
00234 mod |= k[i].assigned();
00235 }
00236 }
00237 }
00238 return ES_SUBSUMED;
00239 }
00240
00241
00242 ExecStatus es =
00243 prop_val<View, Card, isView>(home, y, k);
00244 if (es == ES_FAILED || es == ES_SUBSUMED) {
00245 return es;
00246 }
00247
00248 int cmin = x[x.size() - 1].min();
00249 int cmax = x[x.size() - 1].max();
00250
00251 for (int i = x.size() - 1; i--; ) {
00252 if (x[i].min() < cmin) {
00253 cmin = x[i].min();
00254 }
00255 if (x[i].max() > cmax) {
00256 cmax = x[i].max();
00257 }
00258 }
00259
00260
00261 reduce_card(cmin, cmax, k);
00262
00263 if (lps == NULL) {
00264 assert (ups == NULL);
00265 lps = new PartialSum<Card>(cmin, k.size(), k, false);
00266 ups = new PartialSum<Card>(cmin, k.size(), k, true);
00267 }
00268
00269 if (isView) {
00270
00271
00272 if (lps->check_update_min(k)) {
00273 delete lps;
00274 lps = new PartialSum<Card>(cmin, k.size(), k, false);
00275 }
00276
00277 if (ups->check_update_max(k)) {
00278 delete ups;
00279 ups = new PartialSum<Card>(cmin, k.size(), k, true);
00280 }
00281 }
00282
00283 bool minima_equal = lps->minValue() == ups->minValue();
00284 bool maxima_equal = lps->maxValue() == ups->maxValue();
00285 bool min_is_valid = lps->minValue() <= cmin;
00286 bool max_is_valid = cmax >= ups->maxValue();
00287
00288 if (!minima_equal ||
00289 !maxima_equal ||
00290 !min_is_valid ||
00291 !max_is_valid) {
00292 delete lps;
00293 lps = new PartialSum<Card>(cmin, k.size(), k, false);
00294 delete ups;
00295 ups = new PartialSum<Card>(cmin, k.size(), k, true);
00296 }
00297
00298 assert(lps->minValue() == ups->minValue());
00299 assert(lps->maxValue() == ups->maxValue());
00300 assert(lps->minValue() <= cmin);
00301 assert(cmax>= ups->maxValue());
00302
00303 GECODE_ES_CHECK((prop_bnd<View, Card, shared, isView>(home, x, k, lps, ups)));
00304
00305 all_assigned = true;
00306
00307 for (int i = k.size(); i--; ) {
00308 count[i] = 0;
00309 }
00310
00311 for (int i = x.size(); i--; ) {
00312 bool b = x[i].assigned();
00313 all_assigned &= b;
00314 if (b) {
00315 int idx = k.lookup(x[i].val());
00316 count[idx]++;
00317 }
00318 }
00319
00320 if (all_assigned) {
00321 for (int i = k.size(); i--; ) {
00322 int ci = count[i];
00323 if (! (k[i].min() <= ci && ci <= k[i].max())) {
00324 return ES_FAILED;
00325 } else {
00326 if (isView) {
00327 ModEvent me = k[i].eq(home, ci);
00328 GECODE_ME_CHECK(me);
00329 mod |= k[i].assigned();
00330 }
00331 }
00332 }
00333 return ES_SUBSUMED;
00334 }
00335
00336 return (mod) ? ES_NOFIX : ES_FIX;
00337 }
00338
00339 template <class View, class Card, bool isView>
00340 inline ExecStatus
00341 Bnd<View, Card, isView>::post(Space* home, ViewArray<View>& x0, Card& k0) {
00342 if (x0.shared()) {
00343 new (home) BndImp<View, Card, isView, true>(home, x0, k0);
00344 } else {
00345 new (home) BndImp<View, Card, isView, false>(home, x0, k0);
00346 }
00347 return ES_OK;
00348 }
00349
00350 template <class View, class Card, bool isView, bool shared>
00351 void
00352 BndImp<View, Card, isView, shared>::flush(void){
00353 delete lps;
00354 lps = NULL;
00355 delete ups;
00356 ups = NULL;
00357 }
00358
00359 }}}
00360
00361
00362