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 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,
00594 const ModEventDelta& med) {
00595 if (IntView::me(med) == ME_INT_VAL) {
00596 GECODE_ES_CHECK(prop_val<Card>(home,*this,y,k));
00597 return ES_NOFIX_PARTIAL(*this,IntView::med(ME_INT_BND));
00598 }
00599
00600 if (Card::propagate)
00601 GECODE_ES_CHECK(pruneCards(home));
00602
00603 Region r(home);
00604 int* count = r.alloc<int>(k.size());
00605
00606 for (int i = k.size(); i--; )
00607 count[i] = 0;
00608 bool all_assigned = true;
00609 int noa = 0;
00610 for (int i = x.size(); i--; ) {
00611 if (x[i].assigned()) {
00612 noa++;
00613 int idx;
00614
00615
00616 if (!lookupValue(k,x[i].val(),idx))
00617 return ES_FAILED;
00618 count[idx]++;
00619 } else {
00620 all_assigned = false;
00621
00622
00623 if (!Card::propagate)
00624 break;
00625 }
00626 }
00627
00628 if (Card::propagate) {
00629
00630 if (noa > 0)
00631 for (int i = k.size(); i--; )
00632 if (!k[i].assigned()) {
00633 GECODE_ME_CHECK(k[i].lq(home, x.size() - (noa - count[i])));
00634 GECODE_ME_CHECK(k[i].gq(home, count[i]));
00635 }
00636
00637 if (!card_consistent<Card>(x, k))
00638 return ES_FAILED;
00639
00640 GECODE_ES_CHECK(prop_card<Card>(home, x, k));
00641
00642
00643
00644 for (int i = k.size(); i--; )
00645 count[i] = 0;
00646 all_assigned = true;
00647 for (int i = x.size(); i--; ) {
00648 if (x[i].assigned()) {
00649 int idx;
00650
00651
00652 if (!lookupValue(k,x[i].val(),idx))
00653 return ES_FAILED;
00654 count[idx]++;
00655 } else {
00656
00657
00658 all_assigned = false;
00659 break;
00660 }
00661 }
00662 }
00663
00664 if (all_assigned) {
00665 for (int i = k.size(); i--; )
00666 GECODE_ME_CHECK(k[i].eq(home, count[i]));
00667 return ES_SUBSUMED(*this,home);
00668 }
00669
00670 if (Card::propagate)
00671 GECODE_ES_CHECK(pruneCards(home));
00672
00673 int n = x.size();
00674
00675 int* mu = r.alloc<int>(n);
00676 int* nu = r.alloc<int>(n);
00677
00678 for (int i = n; i--; )
00679 nu[i] = mu[i] = i;
00680
00681
00682 MaxInc<IntView> max_inc(x);
00683 Support::quicksort<int, MaxInc<IntView> >(mu, n, max_inc);
00684
00685
00686 MinInc<IntView> min_inc(x);
00687 Support::quicksort<int, MinInc<IntView> >(nu, n, min_inc);
00688
00689
00690 MinIdx<Card> min_idx;
00691 Support::quicksort<Card, MinIdx<Card> >(&k[0], k.size(), min_idx);
00692
00693 if (!lps.initialized()) {
00694 assert (!ups.initialized());
00695 lps.init(home, k, false);
00696 ups.init(home, k, true);
00697 } else if (Card::propagate) {
00698
00699
00700 if (lps.check_update_min(k))
00701 lps.init(home, k, false);
00702 if (ups.check_update_max(k))
00703 ups.init(home, k, true);
00704 }
00705
00706
00707
00708 assert(lps.minValue() <= x[nu[0]].min());
00709
00710
00711
00712
00713
00714
00715
00716
00717
00718
00719
00720 HallInfo* hall = r.alloc<HallInfo>(2 * n + 2);
00721 Rank* rank = r.alloc<Rank>(n);
00722
00723 int nb = 0;
00724
00725 int min = x[nu[0]].min();
00726 int max = x[mu[0]].max() + 1;
00727 int last = lps.firstValue + 1;
00728 hall[0].bounds = last;
00729
00730
00731
00732
00733
00734
00735
00736
00737
00738 {
00739 int i = 0;
00740 int j = 0;
00741 while (true) {
00742 if (i < n && min < max) {
00743 if (min != last) {
00744 last = min;
00745 hall[++nb].bounds = last;
00746 }
00747 rank[nu[i]].min = nb;
00748 if (++i < n)
00749 min = x[nu[i]].min();
00750 } else {
00751 if (max != last) {
00752 last = max;
00753 hall[++nb].bounds = last;
00754 }
00755 rank[mu[j]].max = nb;
00756 if (++j == n)
00757 break;
00758 max = x[mu[j]].max() + 1;
00759 }
00760 }
00761 }
00762
00763 int rightmost = nb + 1;
00764 hall[rightmost].bounds = ups.lastValue + 1 ;
00765
00766 if (Card::propagate) {
00767 skip_lbc = true;
00768 for (int i = k.size(); i--; )
00769 if (k[i].min() != 0) {
00770 skip_lbc = false;
00771 break;
00772 }
00773 }
00774
00775 if (!card_fixed && !skip_lbc)
00776 GECODE_ES_CHECK((lbc(home, nb, hall, rank, mu, nu)));
00777
00778 GECODE_ES_CHECK((ubc(home, nb, hall, rank, mu, nu)));
00779
00780 if (Card::propagate)
00781 GECODE_ES_CHECK(prop_card<Card>(home, x, k));
00782
00783 for (int i = k.size(); i--; )
00784 count[i] = 0;
00785 for (int i = x.size(); i--; )
00786 if (x[i].assigned()) {
00787 int idx;
00788 if (!lookupValue(k,x[i].val(),idx))
00789 return ES_FAILED;
00790 count[idx]++;
00791 } else {
00792
00793
00794 return ES_NOFIX;
00795 }
00796
00797 for (int i = k.size(); i--; )
00798 GECODE_ME_CHECK(k[i].eq(home, count[i]));
00799
00800 return ES_SUBSUMED(*this,home);
00801 }
00802
00803
00804 template<class Card>
00805 ExecStatus
00806 Bnd<Card>::post(Home home,
00807 ViewArray<IntView>& x, ViewArray<Card>& k) {
00808 bool cardfix = true;
00809 for (int i=k.size(); i--; )
00810 if (!k[i].assigned()) {
00811 cardfix = false; break;
00812 }
00813 bool nolbc = true;
00814 for (int i=k.size(); i--; )
00815 if (k[i].min() != 0) {
00816 nolbc = false; break;
00817 }
00818
00819 GECODE_ES_CHECK(postSideConstraints<Card>(home, x, k));
00820
00821 if (isDistinct<Card>(home,x,k))
00822 return Distinct::Bnd<IntView>::post(home,x);
00823
00824 (void) new (home) Bnd<Card>(home,x,k,cardfix,nolbc);
00825 return ES_OK;
00826 }
00827
00828 }}}
00829
00830