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 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 count[idx]++;
00120 non--;
00121 }
00122
00123
00124 if (non == 0) {
00125 for (int i = k.size(); i--; )
00126 GECODE_ME_CHECK((k[i].eq(home, count[i] + k[i].counter())));
00127 return ES_SUBSUMED(p,home);
00128 }
00129
00130
00131 int req = 0;
00132
00133 int n_r = 0;
00134
00135 int single = -1;
00136
00137 int t_noa = 0;
00138
00139 for (int i = k.size(); i--; ) {
00140 int ci = count[i] + k[i].counter();
00141 t_noa += ci;
00142 if (ci == 0) {
00143 req += k[i].min();
00144 n_r++;
00145 single = i;
00146 }
00147
00148
00149
00150 if (req > non)
00151 return ES_FAILED;
00152 }
00153
00154
00155 if ((req == non) && (n_r == 1)) {
00156
00157 for (int i = x.size(); i--; ) {
00158
00159 if (!x[i].assigned()) {
00160 GECODE_ME_CHECK(x[i].eq(home, k[single].card()));
00161 assert((single >= 0) && (single < k.size()));
00162 count[single]++;
00163 }
00164 }
00165 assert((single >= 0) && (single < k.size()));
00166
00167 for (int i = k.size(); i--; )
00168 GECODE_ME_CHECK(k[i].eq(home, count[i] + k[i].counter()));
00169 return ES_SUBSUMED(p,home);
00170 }
00171
00172
00173 Support::BitSet<Region> rem(r,k.size());
00174
00175 for (int i = k.size(); i--; ) {
00176 int ci = count[i] + k[i].counter();
00177 if ((ci == k[i].max()) && !rem.get(i)) {
00178 rem.set(i);
00179 k[i].counter(ci);
00180
00181 if (Card::propagate)
00182 GECODE_ME_CHECK(k[i].eq(home, ci));
00183 } else {
00184 if (ci > k[i].max())
00185 return ES_FAILED;
00186
00187
00188 if (Card::propagate) {
00189 GECODE_ME_CHECK(k[i].gq(home, ci));
00190 int occupied = t_noa - ci;
00191 GECODE_ME_CHECK(k[i].lq(home, x.size() + removed - occupied));
00192 }
00193 }
00194
00195 count[i] = 0;
00196 }
00197
00198
00199 {
00200 int n_x = x.size();
00201 for (int i = n_x; i--; ) {
00202 if (x[i].assigned()) {
00203 int idx;
00204 if (!lookupValue(k,x[i].val(),idx))
00205 return ES_FAILED;
00206 if (rem.get(idx))
00207 x[i]=x[--n_x];
00208 }
00209 }
00210 x.size(n_x);
00211 }
00212
00213
00214 {
00215
00216 int* p = r.alloc<int>(k.size());
00217
00218 int n_p = 0;
00219 for (Iter::Values::BitSet<Support::BitSet<Region> > i(rem); i(); ++i)
00220 p[n_p++] = k[i.val()].card();
00221 Support::quicksort(p,n_p);
00222 for (int i = x.size(); i--;) {
00223 Iter::Values::Array pi(p,n_p);
00224 GECODE_ME_CHECK(x[i].minus_v(home, pi, false));
00225 }
00226 }
00227
00228 {
00229 bool all_assigned = true;
00230
00231 for (int i = x.size(); i--; ) {
00232 if (x[i].assigned()) {
00233 int idx;
00234 if (!lookupValue(k,x[i].val(),idx))
00235 return ES_FAILED;
00236 count[idx]++;
00237 } else {
00238 all_assigned = false;
00239 }
00240 }
00241
00242 if (all_assigned) {
00243 for (int i = k.size(); i--; )
00244 GECODE_ME_CHECK((k[i].eq(home, count[i] + k[i].counter())));
00245 return ES_SUBSUMED(p,home);
00246 }
00247 }
00248
00249 if (Card::propagate) {
00250
00251 int reqmin = 0;
00252 int allmax = 0;
00253 for (int i = k.size(); i--; ) {
00254 if (k[i].counter() > k[i].max())
00255 return ES_FAILED;
00256 allmax += k[i].max() - k[i].counter();
00257 if (k[i].counter() < k[i].min())
00258 reqmin += k[i].min() - k[i].counter();
00259 if (k[i].min() > x.size())
00260 return ES_FAILED;
00261 GECODE_ME_CHECK((k[i].lq(home, x.size())));
00262 }
00263
00264 if ((x.size() < reqmin) || (allmax < x.size()))
00265 return ES_FAILED;
00266 }
00267
00268 return ES_NOFIX;
00269 }
00270
00271 template<class Card>
00272 ExecStatus
00273 Val<Card>::propagate(Space& home, const ModEventDelta&) {
00274 return prop_val<Card>(home, *this, x, k);
00275 }
00276
00277 template<class Card>
00278 ExecStatus
00279 Val<Card>::post(Home home,
00280 ViewArray<IntView>& x, ViewArray<Card>& k) {
00281 GECODE_ES_CHECK((postSideConstraints<Card>(home,x,k)));
00282
00283 if (isDistinct<Card>(home,x,k))
00284 return Distinct::Val<IntView>::post(home,x);
00285
00286 (void) new (home) Val<Card>(home,x,k);
00287 return ES_OK;
00288 }
00289
00290
00291 }}}
00292
00293
00294