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
00038
00039
00040
00041
00042
00043 namespace Gecode { namespace Int { namespace GCC {
00044
00045 template<class Card>
00046 forceinline
00047 Val<Card>::Val(Home home,
00048 ViewArray<IntView>& x0, ViewArray<Card>& k0)
00049 : Propagator(home), x(x0), k(k0){
00050 x.subscribe(home, *this, PC_INT_VAL);
00051 k.subscribe(home, *this, PC_INT_VAL);
00052 }
00053
00054 template<class Card>
00055 forceinline
00056 Val<Card>::Val(Space& home, bool share, Val<Card>& p)
00057 : Propagator(home,share,p) {
00058 x.update(home,share, p.x);
00059 k.update(home,share, p.k);
00060 }
00061
00062 template<class Card>
00063 forceinline size_t
00064 Val<Card>::dispose(Space& home) {
00065 x.cancel(home,*this, PC_INT_VAL);
00066 k.cancel(home,*this, PC_INT_VAL);
00067 (void) Propagator::dispose(home);
00068 return sizeof(*this);
00069 }
00070
00071 template<class Card>
00072 Actor*
00073 Val<Card>::copy(Space& home, bool share) {
00074 return new (home) Val<Card>(home,share,*this);
00075 }
00076
00077 template<class Card>
00078 PropCost
00079 Val<Card>::cost(const Space&, const ModEventDelta&) const {
00080
00081
00082
00083
00084 return PropCost::linear(PropCost::HI,x.size());
00085 }
00086
00087 template<class Card>
00088 ExecStatus
00089 prop_val(Space& home, Propagator& p,
00090 ViewArray<IntView>& x, ViewArray<Card>& k) {
00091 assert(x.size() > 0);
00092
00093 Region r(home);
00094
00095 int* count = r.alloc<int>(k.size());
00096
00097
00098 int sum_min = 0;
00099 int removed = 0;
00100 for (int i = k.size(); i--; ) {
00101 removed += k[i].counter();
00102 sum_min += k[i].min();
00103 count[i] = 0;
00104 }
00105
00106
00107
00108 for (int i = k.size(); i--; )
00109 GECODE_ME_CHECK(k[i].lq(home, x.size()+removed-(sum_min - k[i].min())));
00110
00111
00112 int non = x.size();
00113
00114 for (int i = x.size(); i--; )
00115 if (x[i].assigned()) {
00116 int idx;
00117 if (!lookupValue(k,x[i].val(),idx)) {
00118 return ES_FAILED;
00119 }
00120 count[idx]++;
00121 non--;
00122 }
00123
00124
00125 if (non == 0) {
00126 for (int i = k.size(); i--; )
00127 GECODE_ME_CHECK((k[i].eq(home, count[i] + k[i].counter())));
00128 return home.ES_SUBSUMED(p);
00129 }
00130
00131
00132 int req = 0;
00133
00134 int n_r = 0;
00135
00136 int single = -1;
00137
00138 int t_noa = 0;
00139
00140 for (int i = k.size(); i--; ) {
00141 int ci = count[i] + k[i].counter();
00142 t_noa += ci;
00143 if (ci == 0) {
00144 req += k[i].min();
00145 n_r++;
00146 single = i;
00147 }
00148
00149
00150
00151 if (req > non) {
00152 return ES_FAILED;
00153 }
00154 }
00155
00156
00157 if ((req == non) && (n_r == 1)) {
00158
00159 for (int i = x.size(); i--; ) {
00160
00161 if (!x[i].assigned()) {
00162 GECODE_ME_CHECK(x[i].eq(home, k[single].card()));
00163 assert((single >= 0) && (single < k.size()));
00164 count[single]++;
00165 }
00166 }
00167 assert((single >= 0) && (single < k.size()));
00168
00169 for (int i = k.size(); i--; )
00170 GECODE_ME_CHECK(k[i].eq(home, count[i] + k[i].counter()));
00171 return home.ES_SUBSUMED(p);
00172 }
00173
00174
00175 Support::BitSet<Region> rem(r,static_cast<unsigned int>(k.size()));
00176
00177 for (int i = k.size(); i--; ) {
00178 int ci = count[i] + k[i].counter();
00179 if (ci == k[i].max()) {
00180 assert(!rem.get(i));
00181 rem.set(static_cast<unsigned int>(i));
00182 k[i].counter(ci);
00183
00184 GECODE_ME_CHECK(k[i].eq(home, ci));
00185 } else {
00186 if (ci > k[i].max()) {
00187 return ES_FAILED;
00188 }
00189
00190
00191 if (Card::propagate) {
00192 GECODE_ME_CHECK(k[i].gq(home, ci));
00193 int occupied = t_noa - ci;
00194 GECODE_ME_CHECK(k[i].lq(home, x.size() + removed - occupied));
00195 }
00196 }
00197
00198 count[i] = 0;
00199 }
00200
00201
00202 {
00203 int n_x = x.size();
00204 for (int i = n_x; i--; ) {
00205 if (x[i].assigned()) {
00206 int idx;
00207 if (!lookupValue(k,x[i].val(),idx)) {
00208 return ES_FAILED;
00209 }
00210 if (rem.get(static_cast<unsigned int>(idx)))
00211 x[i]=x[--n_x];
00212 }
00213 }
00214 x.size(n_x);
00215 }
00216
00217
00218 {
00219
00220 int* p = r.alloc<int>(k.size());
00221
00222 int n_p = 0;
00223 for (Iter::Values::BitSet<Support::BitSet<Region> > i(rem); i(); ++i)
00224 p[n_p++] = k[i.val()].card();
00225 Support::quicksort(p,n_p);
00226 for (int i = x.size(); i--;) {
00227 Iter::Values::Array pi(p,n_p);
00228 GECODE_ME_CHECK(x[i].minus_v(home, pi, false));
00229 }
00230 }
00231
00232 {
00233 bool all_assigned = true;
00234
00235 for (int i = x.size(); i--; ) {
00236 if (x[i].assigned()) {
00237 int idx;
00238 if (!lookupValue(k,x[i].val(),idx)) {
00239 return ES_FAILED;
00240 }
00241 count[idx]++;
00242 } else {
00243 all_assigned = false;
00244 }
00245 }
00246
00247 if (all_assigned) {
00248 for (int i = k.size(); i--; )
00249 GECODE_ME_CHECK((k[i].eq(home, count[i] + k[i].counter())));
00250 return home.ES_SUBSUMED(p);
00251 }
00252 }
00253
00254 if (Card::propagate) {
00255
00256 int reqmin = 0;
00257 int allmax = 0;
00258 for (int i = k.size(); i--; ) {
00259 if (k[i].counter() > k[i].max()) {
00260 return ES_FAILED;
00261 }
00262 allmax += k[i].max() - k[i].counter();
00263 if (k[i].counter() < k[i].min())
00264 reqmin += k[i].min() - k[i].counter();
00265 GECODE_ME_CHECK((k[i].lq(home, x.size()+k[i].counter())));
00266 }
00267
00268 if ((x.size() < reqmin) || (allmax < x.size())) {
00269 return ES_FAILED;
00270 }
00271 }
00272
00273 return ES_NOFIX;
00274 }
00275
00276 template<class Card>
00277 ExecStatus
00278 Val<Card>::propagate(Space& home, const ModEventDelta&) {
00279 return prop_val<Card>(home, *this, x, k);
00280 }
00281
00282 template<class Card>
00283 ExecStatus
00284 Val<Card>::post(Home home,
00285 ViewArray<IntView>& x, ViewArray<Card>& k) {
00286 GECODE_ES_CHECK((postSideConstraints<Card>(home,x,k)));
00287
00288 if (isDistinct<Card>(home,x,k))
00289 return Distinct::Val<IntView>::post(home,x);
00290
00291 (void) new (home) Val<Card>(home,x,k);
00292 return ES_OK;
00293 }
00294
00295
00296 }}}
00297
00298
00299