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 #include "gecode/int/gcc.hh"
00041 #include "gecode/int/distinct.hh"
00042
00043 namespace Gecode { namespace Int { namespace GCC {
00044
00055 template<class Card, bool isView>
00056 inline bool
00057 check_alldiff(int n, ViewArray<Card>& k){
00058 if (isView) {
00059 if (k.size() == n) {
00060 for (int i=k.size(); i--;)
00061 if (k[i].min() != 1 || k[i].max() != 1)
00062 return false;
00063 return true;
00064 }
00065 return false;
00066 } else {
00067 for (int i=k.size(); i--;)
00068 if (k[i].min() != 0 || k[i].max() != 1)
00069 return false;
00070 return true;
00071 }
00072 }
00073
00078 template <class View>
00079 inline int
00080 x_card(ViewArray<View>& x, IntConLevel) {
00081 int n = x.size();
00082 GECODE_AUTOARRAY(ViewRanges<View>, xrange, n);
00083 for (int i = n; i--; ){
00084 ViewRanges<View> iter(x[i]);
00085 xrange[i] = iter;
00086 }
00087
00088 Iter::Ranges::NaryUnion<ViewRanges<View> > drl(&xrange[0], x.size());
00089 return Iter::Ranges::size(drl);
00090 }
00091
00092
00100 template<class Card, bool isView>
00101 inline ExecStatus
00102 card_cons(Space* home, ViewArray<Card>& k, int n) {
00103
00104 int smin = 0;
00105 int smax = 0;
00106 int m = k.size();
00107 for (int i = m; i--; ) {
00108 int ci = k[i].counter();
00109 if (ci > k[i].max() ) {
00110
00111 return ES_FAILED;
00112 } else {
00113 smax += (k[i].max() - ci);
00114 if (ci < k[i].min()) {
00115 smin += (k[i].min() - ci);
00116 }
00117 }
00118 if (k[i].min() > n) {
00119
00120 return ES_FAILED;
00121 }
00122 if (!k[i].assigned()) {
00123 ModEvent me = k[i].lq(home, n);
00124 if (me_failed(me)) {
00125 return ES_FAILED;
00126 }
00127 }
00128 }
00129
00130 if (n < smin) {
00131
00132 return ES_FAILED;
00133 }
00134
00135
00136 if (smax < n) {
00137
00138 return ES_FAILED;
00139 }
00140 return ES_OK;
00141 }
00142
00148 template<class Card, bool isView>
00149 inline void
00150 post_template(Space* home, ViewArray<IntView>& x, ViewArray<Card>& k,
00151 IntConLevel& icl){
00152 int n = x_card(x, icl);
00153 bool rewrite = false;
00154 rewrite = check_alldiff<Card,isView>(n, k);
00155 GECODE_ES_FAIL(home, (card_cons<Card, isView>(home, k, x.size())));
00156 if (rewrite) {
00157 if (x.same())
00158 throw ArgumentSame("Int::distinct");
00159 if (home->failed()) return;
00160 switch (icl) {
00161 case ICL_BND:
00162 GECODE_ES_FAIL(home,Distinct::Bnd<IntView>::post(home,x));
00163 break;
00164 case ICL_DOM:
00165 GECODE_ES_FAIL(home,Distinct::Dom<IntView>::post(home,x));
00166 break;
00167 default:
00168 GECODE_ES_FAIL(home,Distinct::Val<IntView>::post(home,x));
00169 }
00170 } else {
00171 switch (icl) {
00172 case ICL_BND: {
00173 GECODE_ES_FAIL(home, (GCC::Bnd<IntView, Card, isView>::post(home, x, k)));
00174 break;
00175 }
00176 case ICL_DOM: {
00177 GECODE_ES_FAIL(home, (GCC::Dom<IntView, Card, isView>::post(home, x, k)));
00178 break;
00179 }
00180 default: {
00181 GECODE_ES_FAIL(home, (GCC::Val<IntView, Card, isView>::post(home, x, k)));
00182 }
00183 }
00184 }
00185 }
00186
00187 }}
00188
00189 using namespace Int;
00190 using namespace Int::GCC;
00191 using namespace Support;
00192
00193
00194
00195 void count(Space* home, const IntVarArgs& x,
00196 const IntVarArgs& c, const IntArgs& v,
00197 IntConLevel icl, PropKind) {
00198
00199
00200
00201
00202 unsigned int vsize = v.size();
00203 unsigned int csize = c.size();
00204 if (vsize != csize)
00205 throw ArgumentSizeMismatch("Int::count");
00206 if (x.same())
00207 throw ArgumentSame("Int::count");
00208
00209 if (home->failed())
00210 return;
00211
00212 ViewArray<IntView> xv(home, x);
00213
00214
00215 IntSet valid(&v[0], vsize);
00216
00217
00218
00219 for (int i = xv.size(); i--; ) {
00220 IntSetRanges ir(valid);
00221 GECODE_ME_FAIL(home, xv[i].inter_r(home, ir));
00222 }
00223
00224 linear(home, c, IRT_EQ, xv.size());
00225
00226 ViewArray<CardView> cv(home, c);
00227
00228
00229 for (int i = vsize; i--; ) {
00230 cv[i].card(v[i]);
00231 cv[i].counter(0);
00232 }
00233 GCC::post_template<CardView, true>(home, xv, cv, icl);
00234 }
00235
00236
00237 void count(Space* home, const IntVarArgs& x, const IntVarArgs& c,
00238 IntConLevel icl, PropKind) {
00239 IntArgs values(c.size());
00240 for (int i = c.size(); i--; )
00241 values[i] = i;
00242 count(home, x, c, values, icl);
00243 }
00244
00245
00246 void count(Space* home, const IntVarArgs& x,
00247 const IntSetArgs& c, const IntArgs& v,
00248 IntConLevel icl, PropKind) {
00249 int vsize = v.size();
00250 int csize = c.size();
00251 if (vsize != csize)
00252 throw ArgumentSizeMismatch("Int::count");
00253 if (x.same())
00254 throw ArgumentSame("Int::count");
00255 for (int i=c.size(); i--; ) {
00256 Limits::check(v[i],"Int::count");
00257 Limits::check(c[i].min(),"Int::count");
00258 Limits::check(c[i].max(),"Int::count");
00259 }
00260
00261 if (home->failed())
00262 return;
00263
00264
00265
00266
00267 ViewArray<IntView> xv(home, x);
00268
00269
00270 IntSet valid(&v[0], vsize);
00271
00272
00273
00274 for (int i = xv.size(); i--; ) {
00275 IntSetRanges ir(valid);
00276 GECODE_ME_FAIL(home, xv[i].inter_r(home, ir));
00277 }
00278
00279 bool hole_found = false;
00280 for (int i = vsize; i--; ) {
00281 hole_found |= (c[i].size() > 1);
00282 }
00283
00284 if (hole_found) {
00285
00286 ViewArray<CardView> cv(home, vsize);
00287 IntVarArgs cvargs(vsize);
00288 for (int i = vsize; i--; ) {
00289 IntVar card(home, c[i]);
00290 cvargs[i] = card;
00291 IntView viewc(card);
00292 cv[i] = viewc;
00293 }
00294
00295
00296 for (int i = vsize; i--; ) {
00297 cv[i].card(v[i]);
00298 cv[i].counter(0);
00299 }
00300
00301 linear(home, cvargs, IRT_EQ, xv.size());
00302
00303 GCC::post_template<CardView, true>(home, xv, cv, icl);
00304 } else {
00305
00306
00307 ViewArray<OccurBndsView> cv(home, csize);
00308
00309 int z = 0;
00310
00311 for (int i = csize; i--; ) {
00312 cv[i].card(v[i]);
00313 cv[i].counter(0);
00314 cv[i].min(c[i].min());
00315 cv[i].max(c[i].max());
00316 if (cv[i].max() == 0){
00317 z++;
00318 }
00319 }
00320
00321
00322 if (z > 0) {
00323
00324 IntArgs rem(z);
00325 z = 0;
00326 for (int j = cv.size(); j--;) {
00327 if (cv[j].max() == 0){
00328 rem[z++] = cv[j].card();
00329 }
00330 }
00331
00332 IntSet remzero(&rem[0], z);
00333 for (int i = xv.size(); i--; ) {
00334 IntSetRanges remzeror(remzero);
00335 GECODE_ME_FAIL(home, xv[i].minus_r(home, remzeror, false));
00336 }
00337
00338 GCC::post_template<OccurBndsView,false>(home, xv, cv, icl);
00339 } else {
00340 GCC::post_template<OccurBndsView,false>(home, xv, cv, icl);
00341 }
00342 }
00343 }
00344
00345
00346 void count(Space* home, const IntVarArgs& x, const IntSetArgs& c,
00347 IntConLevel icl, PropKind) {
00348 IntArgs values(c.size());
00349 for (int i = c.size(); i--; )
00350 values[i] = i;
00351 count(home, x, c, values, icl);
00352 }
00353
00354 void count(Space* home, const IntVarArgs& x,
00355 const IntSet& c, const IntArgs& v,
00356 IntConLevel icl, PropKind) {
00357 IntSetArgs cards(v.size());
00358 for (int i = v.size(); i--; )
00359 cards[i] = c;
00360 count(home, x, cards, v, icl);
00361 }
00362
00363 GECODE_REGISTER3(Int::GCC::Dom<Gecode::Int::IntView, Gecode::Int::GCC::OccurBndsView, false>);
00364 GECODE_REGISTER3(Int::GCC::Dom<Gecode::Int::IntView, Gecode::Int::GCC::CardView, true>);
00365 GECODE_REGISTER3(Int::GCC::Val<Gecode::Int::IntView, Gecode::Int::GCC::OccurBndsView, false>);
00366 GECODE_REGISTER3(Int::GCC::Val<Gecode::Int::IntView, Gecode::Int::GCC::CardView, true>);
00367 GECODE_REGISTER4(Int::GCC::BndImp<Gecode::Int::IntView, Gecode::Int::GCC::OccurBndsView, false, false>);
00368 GECODE_REGISTER4(Int::GCC::BndImp<Gecode::Int::IntView, Gecode::Int::GCC::OccurBndsView, false, true>);
00369 GECODE_REGISTER4(Int::GCC::BndImp<Gecode::Int::IntView, Gecode::Int::GCC::CardView, true, false>);
00370 GECODE_REGISTER4(Int::GCC::BndImp<Gecode::Int::IntView, Gecode::Int::GCC::CardView, true, true>);
00371 }
00372
00373
00374