00001
00002
00003
00004
00005
00006
00007
00008
00009
00010
00011
00012
00013
00014
00015
00016
00017
00018
00019
00020
00021
00022 #include "int/gcc.hh"
00023 #include "int/linear.hh"
00024 #include "int/distinct.hh"
00025
00026 namespace Gecode { namespace Int { namespace GCC {
00027
00038 template<class Card>
00039 forceinline bool
00040 check_alldiff(int n, Card& k){
00041 int left = 0;
00042 int right = k.size() - 1;
00043 bool alldiff = true;
00044
00045 if (k.size() == 1) {
00046 return (n == 1 && k[0].min() == 1 && k[0].max() == 1);
00047 }
00048 if (n == k.size()) {
00049 while (left < right) {
00050 alldiff &= (k[left].max() == 1 &&
00051 k[left].min() == 1 &&
00052 k[right].max() == 1 &&
00053 k[left].max() == 1);
00054 if (!alldiff) {
00055 break;
00056 }
00057
00058 left++;
00059 right--;
00060 }
00061 } else {
00062 if (n < k.size()) {
00063 while (left < right) {
00064 alldiff &= (k[left].max() == 1 &&
00065 k[left].min() == 0 &&
00066 k[right].max() == 1 &&
00067 k[left].max() == 0);
00068 if (!alldiff) {
00069 break;
00070 }
00071 left++;
00072 right--;
00073 }
00074 } else {
00075 return false;
00076 }
00077 }
00078 return alldiff;
00079 }
00080
00084 template <class View>
00085 forceinline void
00086 x_setidx(ViewArray<View>& x) {
00087 for (int i = x.size(); i--; ) {
00088 x[i].index(i);
00089 x[i].oldindex(i);
00090 }
00091 }
00092
00097 template <class View>
00098 forceinline int
00099 x_card(ViewArray<View>& x) {
00100
00101 int n = x.size();
00102
00103 GECODE_AUTOARRAY(ViewRanges<View>, xrange, n);
00104 for (int i = n; i--; ){
00105 ViewRanges<View> iter(x[i]);
00106 xrange[i] = iter;
00107 }
00108
00109 Gecode::Iter::Ranges::NaryUnion<ViewRanges<View> > drl(&xrange[0], x.size());
00110 int r = 0;
00111 for ( ; drl(); ++drl){
00112 for (int v = drl.min(); v <=drl.max(); v++) {
00113 r ++;
00114 }
00115 }
00116 return r;
00117 }
00118
00124 template <class Card, class View>
00125 forceinline void
00126 initcard(Space* home, ViewArray<View>& x, Card& k, int lb, int ub) {
00127 GECODE_AUTOARRAY(ViewRanges<View>, xrange, x.size());
00128 for (int i = x.size(); i--; ){
00129 ViewRanges<View> iter(x[i]);
00130 xrange[i] = iter;
00131 }
00132
00133 Iter::Ranges::NaryUnion<ViewRanges<View> > drl(&xrange[0], x.size());
00134 int idx = 0;
00135 for ( ; drl(); ++drl){
00136 for (int v = drl.min(); v <= drl.max(); v++){
00137 k[idx].init(home, lb, ub, v);
00138 idx++;
00139 }
00140 }
00141 }
00142
00148 template <class Card, class View, bool isView>
00149 forceinline void
00150 setcard(Space* home, ViewArray<View>& x, Card& k, int xmin, int xmax) {
00151
00152 int idx = 0;
00153 for (int v = xmin; v <= xmax; v++) {
00154 k[idx].card(v);
00155 k[idx].counter(0);
00156 idx++;
00157 }
00158
00159 bool assigned = true;
00160 for (int i = x.size(); i--; ) {
00161 assigned &= x[i].assigned();
00162 }
00163
00164 if (assigned) {
00165
00166 int size = xmax - (xmin - 1);
00167 GECODE_AUTOARRAY(int, count, size);
00168 for (int i = size; i--; ) {
00169 count[i] = 0;
00170 }
00171 for (int i = x.size(); i--; ) {
00172 count[x[i].val() - xmin]++;
00173 }
00174 for (int i = k.size(); i--; ) {
00175 if (k[i].min() > count[i]) {
00176 home->fail();
00177 }
00178 }
00179 }
00180 }
00181
00182
00190 template<class Card, bool isView>
00191 forceinline ExecStatus
00192 card_cons(Space* home, Card& k, int n) {
00193 for (int i = k.size(); i--; ) {
00194 if (k[i].min() > n) {
00195 return ES_FAILED;
00196 }
00197 ModEvent me = k[i].lq(home, n);
00198 if (me_failed(me)) {
00199 return ES_FAILED;
00200 }
00201 }
00202 return ES_OK;
00203 }
00204
00210 template<class View, class Card, bool isView>
00211 forceinline void
00212 post_template(Space* home, ViewArray<View>& x, Card& k, IntConLevel& icl){
00213
00214 int n = x_card(x);
00215 bool rewrite = false;
00216 if (!isView) {
00217 rewrite = check_alldiff(n, k);
00218 }
00219
00220 GECODE_ES_FAIL(home, (card_cons<Card, isView>(home, k, x.size())));
00221
00222 if (!isView && rewrite) {
00223 switch (icl) {
00224 case ICL_BND:
00225 GECODE_ES_FAIL(home,Distinct::Bnd<View>::post(home, x));
00226 break;
00227 case ICL_DOM:
00228 GECODE_ES_FAIL(home,Distinct::Dom<View>::post(home, x));
00229 break;
00230 default:
00231 GECODE_ES_FAIL(home,Distinct::Val<View>::post(home, x));
00232 }
00233 } else {
00234 switch (icl) {
00235 case ICL_BND:
00236 GECODE_ES_FAIL(home, (GCC::Bnd<View, Card, isView>::post(home, x, k)));
00237 break;
00238 case ICL_DOM:
00239 GECODE_ES_FAIL(home, (GCC::Dom<View, Card, isView>::post(home, x, k)));
00240 break;
00241 default:
00242 GECODE_ES_FAIL(home, (GCC::Val<View, Card, isView>::post(home, x, k)));
00243 }
00244 }
00245 }
00246
00247 }}
00248
00249 using namespace Int;
00250 using namespace Support;
00251
00252
00253
00254 void gcc(Space* home, const IntVarArgs& x, const IntArgs& c,
00255 int m, int unspec_low, int unspec_up, int min, int max,
00256 IntConLevel icl) {
00257
00258 if (home->failed()) {
00259 return;
00260 }
00261
00262 GccIdxView xv(home, x);
00263
00264 x_setidx(xv);
00265
00266 FixCard cv(c, xv, m, (m / 3), (max - (min - 1)),
00267 min, max, unspec_low, unspec_up);
00268
00269
00270 int z = 0;
00271 for (int j = cv.size(); j--; ){
00272 if (cv[j].max() == 0){
00273 z++;
00274 }
00275 }
00276
00277
00278 if (z > 0) {
00279
00280
00281 FixCard red(cv.size() - z);
00282 IntArgs rem(z);
00283 z = 0;
00284 int c = 0;
00285 int r = red.size() - 1;
00286 for (int j = cv.size(); j--;) {
00287 if (cv[j].max() == 0){
00288 rem[z] = cv[j].card();
00289 z++;
00290 } else {
00291 red[r]= cv[j];
00292 r--;
00293 }
00294 c++;
00295 }
00296
00297 IntSet zero(&rem[0], z);
00298 IntSetRanges remzero(zero);
00299 int n = xv.size();
00300 for (int i = n; i--; ) {
00301 GECODE_ME_FAIL(home, xv[i].minus(home, remzero));
00302 }
00303 GCC::post_template<GCC::IdxView, FixCard, false>(home, xv, red, icl);
00304 } else {
00305 GCC::post_template<GCC::IdxView, FixCard, false>(home, xv, cv, icl);
00306 }
00307 }
00308
00309 void gcc(Space* home, const IntVarArgs& x, const IntArgs& c,
00310 int m, int unspec, int min, int max,
00311 IntConLevel icl) {
00312 gcc(home, x, c, m, 0, unspec, min, max, icl);
00313 }
00314
00315 void gcc(Space* home, const IntVarArgs& x, int lb, int ub,
00316 IntConLevel icl) {
00317 if (home->failed()) {
00318 return;
00319 }
00320
00321 GccIdxView xv(home,x);
00322 x_setidx(xv);
00323
00324 int values = x_card(xv);
00325 FixCard c(home, values);
00326 GCC::initcard(home, xv, c, lb, ub);
00327 GCC::post_template<GCC::IdxView, FixCard, false>(home, xv, c, icl);
00328 }
00329
00330
00331
00332 void gcc(Space* home, const IntVarArgs& x, int ub, IntConLevel icl) {
00333 gcc(home, x, ub, ub, icl);
00334 }
00335
00336 void gcc(Space* home, const IntVarArgs& x, const IntVarArgs& c,
00337 int min, int max, IntConLevel icl) {
00338
00339 if (home->failed()) {
00340 return;
00341 }
00342
00343 GccIdxView xv(home, x);
00344 x_setidx(xv);
00345
00346 linear(home, c, IRT_EQ, xv.size());
00347
00348 VarCard cv(home, c);
00349
00350 int interval = max - (min - 1);
00351
00352 GECODE_AUTOARRAY(bool, done, interval);
00353 for (int i = 0; i < interval; i++) {
00354 done[i] = false;
00355 }
00356
00357 GECODE_AUTOARRAY(ViewRanges<Gecode::Int::GCC::IdxView>, xrange, xv.size());
00358 for (int i = xv.size(); i--; ){
00359 ViewRanges<Gecode::Int::GCC::IdxView> iter(xv[i]);
00360 xrange[i] = iter;
00361 }
00362
00363 Gecode::Iter::Ranges::NaryUnion<ViewRanges<Gecode::Int::GCC::IdxView> >
00364 drl(&xrange[0], xv.size());
00365 Gecode::Iter::Ranges::Cache<
00366 Gecode::Iter::Ranges::
00367 NaryUnion<ViewRanges<Gecode::Int::GCC::IdxView> > > crl(drl);
00368 for ( ; crl(); ++crl) {
00369 for (int v = crl.min(); v <= crl.max(); v++) {
00370 done[v - min] = true;
00371 }
00372 }
00373
00374 for (int i = 0; i < interval; i++) {
00375 if (!done[i]) {
00376 GECODE_ME_FAIL(home, cv[i].eq(home, 0));
00377 }
00378 }
00379
00380 GCC::setcard<VarCard, Gecode::Int::GCC::IdxView, true>
00381 (home, xv, cv, min, max);
00382
00383 GCC::post_template<GCC::IdxView, VarCard, true>(home, xv, cv, icl);
00384 }
00385
00386 void gcc(Space* home, const IntVarArgs& x, const IntArgs& v,
00387 const IntVarArgs& c,int m, int unspec, bool all,
00388 int xmin, int xmax, IntConLevel icl) {
00389 gcc(home, x, v, c, m, 0, unspec, all, xmin, xmax, icl);
00390 }
00391
00392 void gcc(Space* home, const IntVarArgs& x, const IntArgs& v,
00393 const IntVarArgs& c,int m,
00394 int unspec_low, int unspec_up, bool all,
00395 int xmin, int xmax, IntConLevel icl) {
00396
00397 if (m != c.size()) {
00398 throw ArgumentSizeMismatch("Int::gcc");
00399 }
00400 if (home->failed()) {
00401 return;
00402 }
00403
00404 GccIdxView xv(home, x);
00405 x_setidx(xv);
00406
00407 int interval = xmax - (xmin - 1);
00408
00409 GECODE_AUTOARRAY(bool, done, interval);
00410 for (int i = 0; i < interval; i++) {
00411 done[i] = false;
00412 }
00413
00414 GECODE_AUTOARRAY(ViewRanges<Gecode::Int::GCC::IdxView>, xrange, xv.size());
00415 for (int i = xv.size(); i--; ){
00416 ViewRanges<Gecode::Int::GCC::IdxView> iter(xv[i]);
00417 xrange[i] = iter;
00418 }
00419
00420 Gecode::Iter::Ranges::NaryUnion<ViewRanges<Gecode::Int::GCC::IdxView> >
00421 drl(&xrange[0], xv.size());
00422 Gecode::Iter::Ranges::Cache<
00423 Gecode::Iter::Ranges::
00424 NaryUnion<ViewRanges<Gecode::Int::GCC::IdxView> > > crl(drl);
00425 for ( ; crl(); ++crl) {
00426 for (int v = crl.min(); v <= crl.max(); v++) {
00427 done[v - xmin] = true;
00428 }
00429 }
00430
00431 if (all) {
00432 for (int i = 0; i < interval; i++) {
00433 done[i] = true;
00434 }
00435 }
00436
00437
00438 int ci = 0;
00439
00440 int cvi = 0;
00441 IntVarArgs cv(interval);
00442 for (int i = xmin; i <= xmax; i++) {
00443
00444 if (done[i - xmin]) {
00445 if (ci < m) {
00446
00447 if (i == v[ci]) {
00448 cv[cvi] = c[ci];
00449 ci++;
00450 cvi++;
00451 } else {
00452
00453 IntVar iv(home, unspec_low, unspec_up);
00454 cv[cvi] = iv;
00455 cvi++;
00456 }
00457 } else {
00458
00459 IntVar iv(home, unspec_low, unspec_up);
00460 cv[cvi] = iv;
00461 cvi++;
00462 }
00463 } else {
00464
00465 if (ci < m) {
00466
00467 if (i == v[ci]) {
00468 cv[cvi] = c[ci];
00469 ci++;
00470 cvi++;
00471 } else {
00472
00473 IntVar iv(home, unspec_low, unspec_up);
00474 cv[cvi] = iv;
00475 cvi++;
00476 }
00477 } else {
00478
00479 IntVar iv(home, unspec_low, unspec_up);
00480 cv[cvi] = iv;
00481 cvi++;
00482 }
00483 }
00484 }
00485
00486 if (ci < m) {
00487
00488 for (; ci < m; ci++) {
00489 cv[cvi] = c[ci];
00490 ci++;
00491 cvi++;
00492 }
00493 }
00494
00495 linear(home, c, IRT_LQ, xv.size());
00496 VarCard cardv(home, cv);
00497
00498 GCC::setcard<VarCard, Gecode::Int::GCC::IdxView, true>
00499 (home, xv, cardv, xmin, xmax);
00500 GCC::post_template<GCC::IdxView, VarCard, true>(home, xv, cardv, icl);
00501 }
00502 }
00503
00504
00505
00506