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
00044 namespace Gecode { namespace Int { namespace GCC {
00045
00046 template<class Card>
00047 forceinline
00048 Bnd<Card>::
00049 Bnd(Home home, ViewArray<IntView>& x0, ViewArray<Card>& k0,
00050 bool cf, bool nolbc) :
00051 Propagator(home), x(x0), y(home, x0), k(k0),
00052 card_fixed(cf), skip_lbc(nolbc) {
00053 y.subscribe(home, *this, PC_INT_BND);
00054 k.subscribe(home, *this, PC_INT_BND);
00055 }
00056
00057 template<class Card>
00058 forceinline
00059 Bnd<Card>::
00060 Bnd(Space& home, bool share, Bnd<Card>& p)
00061 : Propagator(home, share, p),
00062 card_fixed(p.card_fixed), skip_lbc(p.skip_lbc) {
00063 x.update(home, share, p.x);
00064 y.update(home, share, p.y);
00065 k.update(home, share, p.k);
00066 }
00067
00068 template<class Card>
00069 forceinline size_t
00070 Bnd<Card>::dispose(Space& home) {
00071 y.cancel(home,*this, PC_INT_BND);
00072 k.cancel(home,*this, PC_INT_BND);
00073 (void) Propagator::dispose(home);
00074 return sizeof(*this);
00075 }
00076
00077 template<class Card>
00078 Actor*
00079 Bnd<Card>::copy(Space& home, bool share) {
00080 return new (home) Bnd<Card>(home,share,*this);
00081 }
00082
00083 template<class Card>
00084 PropCost
00085 Bnd<Card>::cost(const Space&,
00086 const ModEventDelta& med) const {
00087 int n_k = Card::propagate ? k.size() : 0;
00088 if (IntView::me(med) == ME_INT_VAL)
00089 return PropCost::linear(PropCost::LO, y.size() + n_k);
00090 else
00091 return PropCost::quadratic(PropCost::LO, x.size() + n_k);
00092 }
00093
00094
00095 template<class Card>
00096 forceinline ExecStatus
00097 Bnd<Card>::lbc(Space& home, int& nb,
00098 HallInfo hall[], Rank rank[], int mu[], int nu[]) {
00099 int n = x.size();
00100
00101
00102
00103
00104
00105
00106
00107
00108
00109
00110
00111
00112
00113
00114
00115
00116
00117
00118
00119
00120
00121
00122
00123
00124
00125
00126
00127
00128
00129
00130
00131
00132
00133
00134 int i = 0;
00135 int j = 0;
00136 int w = 0;
00137 int z = 0;
00138 int v = 0;
00139
00140
00141 int rightmost = nb + 1;
00142 int bsize = nb + 2;
00143 w = rightmost;
00144
00145
00146
00147 hall[0].d = 0;
00148 hall[0].s = 0;
00149 hall[0].ps = 0;
00150
00151 for (i = bsize; --i; ) {
00152 int pred = i - 1;
00153 hall[i].s = pred;
00154 hall[i].ps = pred;
00155 hall[i].d = lps.sumup(hall[pred].bounds, hall[i].bounds - 1);
00156
00157
00158
00159
00160
00161
00162 if (hall[i].d == 0) {
00163 hall[pred].h = w;
00164 } else {
00165 hall[w].h = pred;
00166 w = pred;
00167 }
00168 }
00169
00170 w = rightmost;
00171 for (i = bsize; i--; ) {
00172 hall[i].t = i - 1;
00173 if (hall[i].d == 0) {
00174 hall[i].t = w;
00175 } else {
00176 hall[w].t = i;
00177 w = i;
00178 }
00179 }
00180
00181
00182
00183
00184
00185
00186
00187
00188
00189
00190
00191
00192
00193 for (i = 0; i < n; i++) {
00194
00195 int x0 = rank[mu[i]].min;
00196 int y = rank[mu[i]].max;
00197 int succ = x0 + 1;
00198 z = pathmax_t(hall, succ);
00199 j = hall[z].t;
00200
00201
00202
00203
00204
00205
00206
00207
00208 if (z != succ) {
00209 w = pathmax_ps(hall, succ);
00210 v = hall[w].ps;
00211 pathset_ps(hall, succ, w, w);
00212 w = std::min(y, z);
00213 pathset_ps(hall, hall[w].ps, v, w);
00214 hall[w].ps = v;
00215 }
00216
00217
00218
00219
00220
00221
00222
00223
00224 if (hall[z].d <= lps.sumup(hall[y].bounds, hall[z].bounds - 1)) {
00225 w = pathmax_s(hall, hall[y].ps);
00226 pathset_s(hall, hall[y].ps, w, w);
00227
00228 v = hall[w].s;
00229 pathset_s(hall, hall[y].s, v, y);
00230 hall[y].s = v;
00231 } else {
00232
00233
00234
00235
00236
00237
00238
00239
00240
00241 if (--hall[z].d == 0) {
00242 hall[z].t = z + 1;
00243 z = pathmax_t(hall, hall[z].t);
00244 hall[z].t = j;
00245 }
00246
00247
00248
00249
00250
00251
00252
00253 if (hall[x0].h > x0) {
00254 hall[i].newBound = pathmax_h(hall, x0);
00255 w = hall[i].newBound;
00256 pathset_h(hall, x0, w, w);
00257 } else {
00258
00259 hall[i].newBound = x0;
00260 }
00261
00262
00263
00264
00265
00266
00267
00268
00269 if (hall[z].d == lps.sumup(hall[y].bounds, hall[z].bounds - 1)) {
00270 if (hall[y].h > y)
00271
00272
00273
00274
00275 y = hall[y].h;
00276
00277 pathset_h(hall, hall[y].h, j-1, y);
00278
00279 hall[y].h = j-1;
00280 }
00281 }
00282 pathset_t(hall, succ, z, z);
00283 }
00284
00285
00286
00287
00288
00289
00290 if (hall[nb].h != 0)
00291 return ES_FAILED;
00292
00293
00294
00295
00296
00297
00298 for (i = bsize; --i;)
00299 if (hall[i].s > i)
00300 hall[i].s = w;
00301 else
00302 w = i;
00303
00304
00305
00306
00307
00308
00309
00310
00311 for (i = n; i--; ) {
00312 int x0 = rank[mu[i]].min;
00313 int y = rank[mu[i]].max;
00314
00315 if ((hall[x0].s <= x0) || (y > hall[x0].s)) {
00316
00317 int m = lps.skipNonNullElementsRight(hall[hall[i].newBound].bounds);
00318 GECODE_ME_CHECK(x[mu[i]].gq(home, m));
00319 }
00320 }
00321
00322
00323 w = 0;
00324 for (i = 0; i <= nb; i++) {
00325 hall[i].d = lps.sumup(hall[i].bounds, hall[i + 1].bounds - 1);
00326 if (hall[i].d == 0) {
00327 hall[i].t = w;
00328 } else {
00329 hall[w].t = i;
00330 w = i;
00331 }
00332 }
00333 hall[w].t = i;
00334
00335 w = 0;
00336 for (i = 1; i <= nb; i++)
00337 if (hall[i - 1].d == 0) {
00338 hall[i].h = w;
00339 } else {
00340 hall[w].h = i;
00341 w = i;
00342 }
00343 hall[w].h = i;
00344
00345 for (i = n; i--; ) {
00346
00347
00348 int x0 = rank[nu[i]].max;
00349 int y = rank[nu[i]].min;
00350 int pred = x0 - 1;
00351 z = pathmin_t(hall, pred);
00352 j = hall[z].t;
00353
00354
00355
00356
00357 if (hall[z].d > lps.sumup(hall[z].bounds, hall[y].bounds - 1)) {
00358
00359 if (--hall[z].d == 0) {
00360 hall[z].t = z - 1;
00361 z = pathmin_t(hall, hall[z].t);
00362 hall[z].t = j;
00363 }
00364
00365 if (hall[x0].h < x0) {
00366 w = pathmin_h(hall, hall[x0].h);
00367 hall[i].newBound = w;
00368 pathset_h(hall, x0, w, w);
00369 } else {
00370 hall[i].newBound = x0;
00371 }
00372
00373 if (hall[z].d == lps.sumup(hall[z].bounds, hall[y].bounds - 1)) {
00374 if (hall[y].h < y) {
00375 y = hall[y].h;
00376 }
00377 int succj = j + 1;
00378
00379 pathset_h(hall, hall[y].h, succj, y);
00380 hall[y].h = succj;
00381 }
00382 }
00383 pathset_t(hall, pred, z, z);
00384 }
00385
00386
00387 for (i = n; i--; ) {
00388 int x0 = rank[nu[i]].min;
00389 int y = rank[nu[i]].max;
00390 if ((hall[x0].s <= x0) || (y > hall[x0].s)) {
00391 int m = lps.skipNonNullElementsLeft(hall[hall[i].newBound].bounds - 1);
00392 GECODE_ME_CHECK(x[nu[i]].lq(home, m));
00393 }
00394 }
00395 return ES_OK;
00396 }
00397
00398
00399 template<class Card>
00400 forceinline ExecStatus
00401 Bnd<Card>::ubc(Space& home, int& nb,
00402 HallInfo hall[], Rank rank[], int mu[], int nu[]) {
00403 int rightmost = nb + 1;
00404 int bsize = nb + 2;
00405
00406
00407
00408
00409
00410
00411
00412
00413
00414
00415 hall[0].h = 0;
00416 hall[0].t = 0;
00417 hall[0].d = 0;
00418
00419 for (int i = bsize; --i; ) {
00420 hall[i].h = hall[i].t = i-1;
00421 hall[i].d = ups.sumup(hall[i-1].bounds, hall[i].bounds - 1);
00422 }
00423
00424 int n = x.size();
00425
00426 for (int i = 0; i < n; i++) {
00427
00428 int x0 = rank[mu[i]].min;
00429 int succ = x0 + 1;
00430 int y = rank[mu[i]].max;
00431 int z = pathmax_t(hall, succ);
00432 int j = hall[z].t;
00433
00434
00435
00436
00437
00438
00439
00440
00441
00442
00443
00444
00445
00446
00447
00448
00449 if (--hall[z].d == 0) {
00450 hall[z].t = z + 1;
00451 z = pathmax_t(hall, hall[z].t);
00452 if (z >= bsize)
00453 z--;
00454 hall[z].t = j;
00455 }
00456 pathset_t(hall, succ, z, z);
00457
00458
00459
00460
00461
00462
00463
00464
00465 if (hall[z].d < ups.sumup(hall[y].bounds, hall[z].bounds - 1))
00466 return ES_FAILED;
00467
00468
00469
00470
00471
00472
00473 if (hall[x0].h > x0) {
00474 int w = pathmax_h(hall, hall[x0].h);
00475 int m = hall[w].bounds;
00476 GECODE_ME_CHECK(x[mu[i]].gq(home, m));
00477 pathset_h(hall, x0, w, w);
00478 }
00479
00480
00481
00482
00483
00484
00485
00486
00487
00488
00489
00490
00491
00492
00493
00494
00495
00496 if (hall[z].d == ups.sumup(hall[y].bounds, hall[z].bounds - 1)) {
00497
00498
00499
00500
00501 int predj = j - 1;
00502 pathset_h(hall, hall[y].h, predj, y);
00503 hall[y].h = predj;
00504 }
00505 }
00506
00507
00508
00509
00510 for (int i = 0; i < rightmost; i++) {
00511 hall[i].h = hall[i].t = i+1;
00512 hall[i].d = ups.sumup(hall[i].bounds, hall[i+1].bounds - 1);
00513 }
00514
00515 for (int i = n; i--; ) {
00516
00517 int x0 = rank[nu[i]].max;
00518 int pred = x0 - 1;
00519 int y = rank[nu[i]].min;
00520 int z = pathmin_t(hall, pred);
00521 int j = hall[z].t;
00522
00523
00524 if (--hall[z].d == 0) {
00525 hall[z].t = z - 1;
00526 z = pathmin_t(hall, hall[z].t);
00527 hall[z].t = j;
00528 }
00529 pathset_t(hall, pred, z, z);
00530
00531
00532 if (hall[z].d < ups.sumup(hall[z].bounds,hall[y].bounds-1))
00533 return ES_FAILED;
00534
00535
00536
00537
00538
00539
00540 if (hall[x0].h < x0) {
00541 int w = pathmin_h(hall, hall[x0].h);
00542 int m = hall[w].bounds - 1;
00543 GECODE_ME_CHECK(x[nu[i]].lq(home, m));
00544 pathset_h(hall, x0, w, w);
00545 }
00546
00547
00548 if (hall[z].d == ups.sumup(hall[z].bounds, hall[y].bounds - 1)) {
00549
00550 pathset_h(hall, hall[y].h, j+1, y);
00551 hall[y].h = j+1;
00552 }
00553 }
00554 return ES_OK;
00555 }
00556
00557 template<class Card>
00558 ExecStatus
00559 Bnd<Card>::pruneCards(Space& home) {
00560
00561
00562
00563
00564 int n_z = 0;
00565 for (int i=k.size(); i--;)
00566 if (k[i].max() == 0)
00567 n_z++;
00568
00569 if (n_z > 0) {
00570 Region r(home);
00571 int* z = r.alloc<int>(n_z);
00572 n_z = 0;
00573 int n_k = 0;
00574 for (int i=0; i<k.size(); i++)
00575 if (k[i].max() == 0) {
00576 z[n_z++] = k[i].card();
00577 } else {
00578 k[n_k++] = k[i];
00579 }
00580 k.size(n_k);
00581 Support::quicksort(z,n_z);
00582 for (int i=x.size(); i--;) {
00583 Iter::Values::Array zi(z,n_z);
00584 GECODE_ME_CHECK(x[i].minus_v(home,zi,false));
00585 }
00586 lps.reinit(); ups.reinit();
00587 }
00588 return ES_OK;
00589 }
00590
00591 template<class Card>
00592 ExecStatus
00593 Bnd<Card>::propagate(Space& home, const ModEventDelta& med) {
00594 if (IntView::me(med) == ME_INT_VAL) {
00595 GECODE_ES_CHECK(prop_val<Card>(home,*this,y,k));
00596 return home.ES_NOFIX_PARTIAL(*this,IntView::med(ME_INT_BND));
00597 }
00598
00599 if (Card::propagate)
00600 GECODE_ES_CHECK(pruneCards(home));
00601
00602 Region r(home);
00603 int* count = r.alloc<int>(k.size());
00604
00605 for (int i = k.size(); i--; )
00606 count[i] = 0;
00607 bool all_assigned = true;
00608 int noa = 0;
00609 for (int i = x.size(); i--; ) {
00610 if (x[i].assigned()) {
00611 noa++;
00612 int idx;
00613
00614
00615 if (!lookupValue(k,x[i].val(),idx))
00616 return ES_FAILED;
00617 count[idx]++;
00618 } else {
00619 all_assigned = false;
00620
00621
00622 if (!Card::propagate)
00623 break;
00624 }
00625 }
00626
00627 if (Card::propagate) {
00628
00629 if (noa > 0)
00630 for (int i = k.size(); i--; )
00631 if (!k[i].assigned()) {
00632 GECODE_ME_CHECK(k[i].lq(home, x.size() - (noa - count[i])));
00633 GECODE_ME_CHECK(k[i].gq(home, count[i]));
00634 }
00635
00636 if (!card_consistent<Card>(x, k))
00637 return ES_FAILED;
00638
00639 GECODE_ES_CHECK(prop_card<Card>(home, x, k));
00640
00641
00642
00643 for (int i = k.size(); i--; )
00644 count[i] = 0;
00645 all_assigned = true;
00646 for (int i = x.size(); i--; ) {
00647 if (x[i].assigned()) {
00648 int idx;
00649
00650
00651 if (!lookupValue(k,x[i].val(),idx))
00652 return ES_FAILED;
00653 count[idx]++;
00654 } else {
00655
00656
00657 all_assigned = false;
00658 break;
00659 }
00660 }
00661 }
00662
00663 if (all_assigned) {
00664 for (int i = k.size(); i--; )
00665 GECODE_ME_CHECK(k[i].eq(home, count[i]));
00666 return home.ES_SUBSUMED(*this);
00667 }
00668
00669 if (Card::propagate)
00670 GECODE_ES_CHECK(pruneCards(home));
00671
00672 int n = x.size();
00673
00674 int* mu = r.alloc<int>(n);
00675 int* nu = r.alloc<int>(n);
00676
00677 for (int i = n; i--; )
00678 nu[i] = mu[i] = i;
00679
00680
00681 MaxInc<IntView> max_inc(x);
00682 Support::quicksort<int, MaxInc<IntView> >(mu, n, max_inc);
00683
00684
00685 MinInc<IntView> min_inc(x);
00686 Support::quicksort<int, MinInc<IntView> >(nu, n, min_inc);
00687
00688
00689 MinIdx<Card> min_idx;
00690 Support::quicksort<Card, MinIdx<Card> >(&k[0], k.size(), min_idx);
00691
00692 if (!lps.initialized()) {
00693 assert (!ups.initialized());
00694 lps.init(home, k, false);
00695 ups.init(home, k, true);
00696 } else if (Card::propagate) {
00697
00698
00699 if (lps.check_update_min(k))
00700 lps.init(home, k, false);
00701 if (ups.check_update_max(k))
00702 ups.init(home, k, true);
00703 }
00704
00705
00706
00707 assert(lps.minValue() <= x[nu[0]].min());
00708
00709
00710
00711
00712
00713
00714
00715
00716
00717
00718
00719 HallInfo* hall = r.alloc<HallInfo>(2 * n + 2);
00720 Rank* rank = r.alloc<Rank>(n);
00721
00722 int nb = 0;
00723
00724 int min = x[nu[0]].min();
00725 int max = x[mu[0]].max() + 1;
00726 int last = lps.firstValue + 1;
00727 hall[0].bounds = last;
00728
00729
00730
00731
00732
00733
00734
00735
00736
00737 {
00738 int i = 0;
00739 int j = 0;
00740 while (true) {
00741 if (i < n && min < max) {
00742 if (min != last) {
00743 last = min;
00744 hall[++nb].bounds = last;
00745 }
00746 rank[nu[i]].min = nb;
00747 if (++i < n)
00748 min = x[nu[i]].min();
00749 } else {
00750 if (max != last) {
00751 last = max;
00752 hall[++nb].bounds = last;
00753 }
00754 rank[mu[j]].max = nb;
00755 if (++j == n)
00756 break;
00757 max = x[mu[j]].max() + 1;
00758 }
00759 }
00760 }
00761
00762 int rightmost = nb + 1;
00763 hall[rightmost].bounds = ups.lastValue + 1 ;
00764
00765 if (Card::propagate) {
00766 skip_lbc = true;
00767 for (int i = k.size(); i--; )
00768 if (k[i].min() != 0) {
00769 skip_lbc = false;
00770 break;
00771 }
00772 }
00773
00774 if (!card_fixed && !skip_lbc)
00775 GECODE_ES_CHECK((lbc(home, nb, hall, rank, mu, nu)));
00776
00777 GECODE_ES_CHECK((ubc(home, nb, hall, rank, mu, nu)));
00778
00779 if (Card::propagate)
00780 GECODE_ES_CHECK(prop_card<Card>(home, x, k));
00781
00782 for (int i = k.size(); i--; )
00783 count[i] = 0;
00784 for (int i = x.size(); i--; )
00785 if (x[i].assigned()) {
00786 int idx;
00787 if (!lookupValue(k,x[i].val(),idx))
00788 return ES_FAILED;
00789 count[idx]++;
00790 } else {
00791
00792
00793 return ES_NOFIX;
00794 }
00795
00796 for (int i = k.size(); i--; )
00797 GECODE_ME_CHECK(k[i].eq(home, count[i]));
00798
00799 return home.ES_SUBSUMED(*this);
00800 }
00801
00802
00803 template<class Card>
00804 ExecStatus
00805 Bnd<Card>::post(Home home,
00806 ViewArray<IntView>& x, ViewArray<Card>& k) {
00807 bool cardfix = true;
00808 for (int i=k.size(); i--; )
00809 if (!k[i].assigned()) {
00810 cardfix = false; break;
00811 }
00812 bool nolbc = true;
00813 for (int i=k.size(); i--; )
00814 if (k[i].min() != 0) {
00815 nolbc = false; break;
00816 }
00817
00818 GECODE_ES_CHECK(postSideConstraints<Card>(home, x, k));
00819
00820 if (isDistinct<Card>(home,x,k))
00821 return Distinct::Bnd<IntView>::post(home,x);
00822
00823 (void) new (home) Bnd<Card>(home,x,k,cardfix,nolbc);
00824 return ES_OK;
00825 }
00826
00827 }}}
00828
00829