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