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