00001
00002
00003
00004
00005
00006
00007
00008
00009
00010
00011
00012
00013
00014
00015
00016
00017
00018
00019
00020
00021
00022 namespace Gecode { namespace Int { namespace Sortedness {
00023
00024
00025
00026
00027
00028
00029
00030
00031
00032
00033
00034
00035
00036
00037
00038
00039
00056 template<class View, class Tuple, bool Perm>
00057 ExecStatus
00058 bounds_propagation(Space* home,
00059 ViewArray<Tuple>& xz,
00060 ViewArray<View>& y,
00061 bool& repairpass,
00062 bool& nofix,
00063 bool& match_fixed){
00064
00065 int n = xz.size();
00066
00067 GECODE_AUTOARRAY(int, tau, n);
00068 GECODE_AUTOARRAY(int, phi, n);
00069 GECODE_AUTOARRAY(int, phiprime, n);
00070 GECODE_AUTOARRAY(OfflineMinItem, sequence, n);
00071 GECODE_AUTOARRAY(int, vertices, n);
00072
00073 if (match_fixed) {
00074
00075
00076 for (int i = xz.size(); i--; ) {
00077 int pi = xz[i][1].val();
00078 tau[pi] = i;
00079 }
00080 } else {
00081 for (int i = n; i--; ) {
00082 tau[i] = i;
00083 }
00084 }
00085
00086 bool yval = true;
00087 bool ysorted = true;
00088 for (int i = n; i--; ) {
00089 yval &= y[i].assigned();
00090 if (i) {
00091 ysorted &= (y[i].min() <= y[i - 1].min() &&
00092 y[i].max() <= y[i - 1].max());
00093 }
00094 }
00095
00096 if (Perm) {
00097
00098
00099
00100
00101
00102 int mib = y[0].min();
00103
00104 int mab = y[n - 1].max();
00105
00106 int ivs = (mab - mib + 1);
00107 GECODE_AUTOARRAY(Rank, allbnd, ivs);
00108 int iter = mib;
00109 int idx = 0;
00110 while(iter <= mab && idx < n) {
00111 if (y[idx].min() > iter) {
00112
00113 assert(idx > 0);
00114 allbnd[iter - mib].min = idx;
00115 allbnd[iter - mib].max = idx - 1;
00116 iter++;
00117 } else {
00118 if (y[idx].min() <= iter && iter <= y[idx].max() ) {
00119 allbnd[iter - mib].min = idx;
00120 allbnd[iter - mib].max = idx;
00121 iter++;
00122 } else {
00123 idx++;
00124 }
00125 }
00126 }
00127
00128 iter = mab;
00129 idx = n -1;
00130 while(iter >= mib && idx >= 0) {
00131 if (y[idx].min() > iter) {
00132
00133 assert(idx > 0);
00134 allbnd[iter - mib].max = idx - 1;
00135 iter--;
00136 } else {
00137 if (y[idx].min() <= iter && iter <= y[idx].max() ) {
00138 allbnd[iter - mib].max = idx;
00139 iter--;
00140 } else {
00141 idx--;
00142 }
00143 }
00144 }
00145
00146 for (int i = n; i--; ) {
00147
00148 int minr = allbnd[xz[i][0].min() - mib].min;
00149 int maxr = allbnd[xz[i][0].max() - mib].max;
00150
00151 ModEvent me = xz[i][0].gq(home, y[minr].min());
00152 if (me_failed(me)) {
00153 return ES_FAILED;
00154 }
00155 nofix |= (me_modified(me) &&
00156 xz[i][0].min() != y[minr].min());
00157
00158 me = xz[i][0].lq(home, y[maxr].max());
00159 if (me_failed(me)) {
00160 return ES_FAILED;
00161 }
00162 nofix |= (me_modified(me) &&
00163 xz[i][0].min() != y[maxr].max());
00164
00165 me = xz[i][1].gq(home, minr);
00166 if (me_failed(me)) {
00167 return ES_FAILED;
00168 }
00169 nofix |= (me_modified(me) && xz[i][1].min() != minr);
00170
00171 me = xz[i][1].lq(home, maxr);
00172 if (me_failed(me)) {
00173 return ES_FAILED;
00174 }
00175 nofix |= (me_modified(me) && xz[i][1].max() != maxr);
00176
00177 }
00178
00179
00180 if (!channel<View, Tuple, Perm>(home, xz, y, nofix)) {
00181 return ES_FAILED;
00182 }
00183 if (nofix) {
00184 return ES_NOFIX;
00185 }
00186 }
00187
00188
00189
00190
00191
00192
00193
00194
00195
00196
00197 if (!normalize<View, Tuple>(home, y, xz, nofix)) {
00198 return ES_FAILED;
00199 }
00200
00201 if (Perm) {
00202
00203 if (!channel<View, Tuple, Perm>(home, xz, y, nofix)) {
00204 return ES_FAILED;
00205 }
00206 if (nofix) {
00207 return ES_NOFIX;
00208 }
00209 }
00210
00211
00212
00213
00214
00215 sort_sigma<View, Tuple, Perm>(xz, match_fixed);
00216
00217 bool subsumed = true;
00218 bool array_subs = false;
00219 int dropfst = 0;
00220 bool noperm_bc = false;
00221
00222 if (!(check_subsumption<View, Tuple, Perm>
00223 (home, xz, y, subsumed, dropfst)) ||
00224 !(array_assigned<View, Tuple, Perm>
00225 (home, xz, y, array_subs, match_fixed, nofix, noperm_bc))) {
00226 return ES_FAILED;
00227 }
00228
00229 if (subsumed || array_subs) {
00230 return ES_SUBSUMED;
00231 }
00232
00233
00234
00235
00236
00237
00238
00239
00240 sort_tau<View, Tuple, Perm>(xz, tau);
00241
00242
00243
00244
00245
00246
00247
00248
00249
00250
00251
00252 if (!match_fixed) {
00253 if (!glover<View, Tuple, Perm>
00254 (home, xz, y, tau, phi, sequence, vertices)) {
00255 return ES_FAILED;
00256 }
00257 } else {
00258 for (int i = xz.size(); i--; ) {
00259 phi[i] = xz[i][1].val();
00260 phiprime[i] = phi[i];
00261 }
00262 }
00263
00264 if(!yval) {
00265
00266 if (!match_fixed) {
00267 if (!revglover<View, Tuple, Perm>
00268 (home, xz, y, tau, phiprime, sequence, vertices)) {
00269 return ES_FAILED;
00270 }
00271 }
00272
00273 if (!narrow_domy<View, Tuple, Perm>
00274 (home, xz, y, phi, phiprime, nofix)) {
00275 return ES_FAILED;
00276 }
00277
00278 if (nofix && !match_fixed) {
00279
00280
00281 for (int i = y.size(); i--; ) {
00282 phi[i] = 0;
00283 phiprime[i] = 0;
00284 }
00285 if (!glover<View, Tuple, Perm>
00286 (home, xz, y, tau, phi, sequence, vertices)) {
00287 return ES_FAILED;
00288 }
00289
00290 if (!revglover<View, Tuple, Perm>
00291 (home, xz, y, tau, phiprime, sequence, vertices)) {
00292 return ES_FAILED;
00293 }
00294
00295 if (!narrow_domy<View, Tuple, Perm>
00296 (home, xz, y, phi, phiprime, nofix)) {
00297 return ES_FAILED;
00298 }
00299 }
00300 }
00301
00302
00303
00304
00305
00306
00307
00308
00309
00310 GECODE_AUTOARRAY(int, scclist, n);
00311 GECODE_AUTOARRAY(SccComponent, sinfo , n);
00312
00313 for(int i = n; i--; ) {
00314 sinfo[i].left = i;
00315 sinfo[i].right = i;
00316 sinfo[i].rightmost = i;
00317 sinfo[i].leftmost = i;
00318 }
00319
00320 computesccs<View>(home, xz, y, phi, sinfo, scclist);
00321
00322
00323
00324
00325
00326
00327
00328
00329 if (!narrow_domx<View, Tuple, Perm>
00330 (home, xz, y, tau, phi, scclist, sinfo, nofix)) {
00331 return ES_FAILED;
00332 }
00333
00334 if (Perm) {
00335 if (!noperm_bc) {
00336 if (!perm_bc<View, Tuple, Perm>
00337 (home, tau, sinfo, scclist, xz, repairpass, nofix)) {
00338 return ES_FAILED;
00339 }
00340 }
00341
00342
00343
00344 if (!channel<View, Tuple, Perm>(home, xz, y, nofix)) {
00345 return ES_FAILED;
00346 }
00347 if (nofix) {
00348 return ES_NOFIX;
00349 }
00350 }
00351
00352 sort_tau<View, Tuple, Perm>(xz, tau);
00353
00354 if (Perm) {
00355
00356
00357
00358 for (int i = xz.size() - 1; i--; ) {
00359
00360 if (xz[tau[i]][1].min() == xz[tau[i+1]][1].min() &&
00361 xz[tau[i]][1].max() == xz[tau[i+1]][1].max() &&
00362 xz[tau[i]][1].size() == 2 && xz[tau[i]][1].range()) {
00363
00364 if (xz[tau[i]][0].max() < xz[tau[i+1]][0].max()) {
00365 ModEvent me = y[xz[tau[i]][1].min()].lq(home, xz[tau[i]][0].max());
00366 if (me_failed(me)) {
00367 return ES_FAILED;
00368 }
00369 nofix |= (y[xz[tau[i]][1].min()].modified() &&
00370 y[xz[tau[i]][1].min()].max() != xz[tau[i]][0].max());
00371
00372 me = y[xz[tau[i+1]][1].max()].lq(home, xz[tau[i+1]][0].max());
00373 if (me_failed(me)) {
00374 return ES_FAILED;
00375 }
00376 nofix |= (y[xz[tau[i+1]][1].max()].modified() &&
00377 y[xz[tau[i+1]][1].max()].max() != xz[tau[i+1]][0].max());
00378 }
00379 }
00380 }
00381 }
00382 return nofix ? ES_NOFIX : ES_FIX;
00383 }
00384
00385 template<class View, class Tuple, bool Perm>
00386 forceinline Sortedness<View, Tuple, Perm>::
00387 Sortedness(Space* home, bool share, Sortedness<View, Tuple, Perm>& p):
00388 Propagator(home, share, p),
00389 reachable(p.reachable) {
00390 xz.update(home, share, p.xz);
00391 y.update(home, share, p.y);
00392 w.update(home, share, p.w);
00393 }
00394
00395 template<class View, class Tuple, bool Perm>
00396 Sortedness<View, Tuple, Perm>::
00397 Sortedness(Space* home, ViewArray<Tuple>& xz0, ViewArray<View>& y0):
00398 Propagator(home), xz(xz0), y(y0), w(home, y0), reachable(-1) {
00399 xz.subscribe(home, this, PC_INT_BND);
00400 y.subscribe(home, this, PC_INT_BND);
00401
00402 }
00403
00404 template<class View, class Tuple, bool Perm>
00405 size_t
00406 Sortedness<View, Tuple, Perm>::dispose(Space* home) {
00407 assert(!home->failed());
00408 xz.cancel(home,this, PC_INT_BND);
00409 y.cancel(home,this, PC_INT_BND);
00410 (void) Propagator::dispose(home);
00411 return sizeof(*this);
00412 }
00413
00414 template<class View, class Tuple, bool Perm>
00415 Actor* Sortedness<View, Tuple, Perm>::copy(Space* home, bool share) {
00416 return new (home) Sortedness<View, Tuple, Perm>(home, share, *this);
00417 }
00418
00419 template<class View, class Tuple, bool Perm>
00420 PropCost Sortedness<View, Tuple, Perm>::cost(void) const {
00421 return cost_hi(xz.size(), PC_LINEAR_HI);
00422 }
00423
00424 template<class View, class Tuple, bool Perm>
00425 ExecStatus
00426 Sortedness<View, Tuple, Perm>::propagate(Space* home) {
00427
00428 int n = xz.size();
00429 bool secondpass = false;
00430 bool nofix = false;
00431 int dropfst = 0;
00432
00433 bool subsumed = false;
00434 bool array_subs = false;
00435 bool match_fixed = false;
00436
00437
00438 if (!normalize<View, Tuple>(home, y, xz, nofix)) {
00439 return ES_FAILED;
00440 }
00441
00442
00443 sort_sigma<View, Tuple, Perm>(xz, match_fixed);
00444
00445 bool noperm_bc = false;
00446 if (!array_assigned<View, Tuple, Perm>
00447 (home, xz, y, array_subs, match_fixed, nofix, noperm_bc)) {
00448 return ES_FAILED;
00449 }
00450
00451 if (array_subs) {
00452 return ES_SUBSUMED;
00453 }
00454
00455 sort_sigma<View, Tuple, Perm>(xz, match_fixed);
00456
00457
00458
00459
00460 if (!check_subsumption<View, Tuple, Perm>
00461 (home, xz, y, subsumed, dropfst)) {
00462 return ES_FAILED;
00463 }
00464
00465 if (subsumed) {
00466 return ES_SUBSUMED;
00467 }
00468
00469 if (Perm) {
00470
00471 if (dropfst) {
00472 reachable = w[dropfst - 1].max();
00473 bool unreachable = true;
00474 for (int i = xz.size(); unreachable && i-- ; ) {
00475 unreachable &= (reachable < xz[i][0].min());
00476 }
00477
00478 if (unreachable) {
00479 xz.drop_fst(dropfst, home, this, PC_INT_BND);
00480 y.drop_fst (dropfst, home, this, PC_INT_BND);
00481 } else {
00482 dropfst = 0;
00483 }
00484 }
00485
00486 n = xz.size();
00487
00488 if (n < 2) {
00489 if (xz[0][0].max() < y[0].min() || y[0].max() < xz[0][0].min()) {
00490 return ES_FAILED;
00491 } else {
00492 if (Perm) {
00493 GECODE_ME_CHECK(xz[0][1].eq(home, w.size() - 1));
00494 }
00495 Rel::EqBnd<View,View>::post(home, xz[0][0], y[0]);
00496 return ES_SUBSUMED;
00497
00498 }
00499 }
00500
00501
00502
00503
00504 int valid = n - 1;
00505 int index = 0;
00506 int shift = 0;
00507
00508 for (int i = n; i--; ){
00509 if (xz[i][1].max() > index) {
00510 index = xz[i][1].max();
00511 }
00512 if (index > valid) {
00513 shift = index - valid;
00514 }
00515 }
00516
00517 if (shift) {
00518 ViewArray<ViewTuple<OffsetView,2> > oxz(home, n);
00519 ViewArray<OffsetView> oy(home, n);
00520
00521 for (int i = n; i--; ) {
00522
00523 GECODE_ME_CHECK(xz[i][1].gq(home, shift));
00524
00525 oxz[i][1] = OffsetView(xz[i][1], -shift);
00526 oxz[i][0] = OffsetView(xz[i][0], 0);
00527 oy[i] = OffsetView(y[i], 0);
00528 }
00529
00530 GECODE_ES_CHECK((bounds_propagation<OffsetView,
00531 ViewTuple<OffsetView,2>, Perm>
00532 (home, oxz, oy, secondpass, nofix, match_fixed)));
00533
00534 if (secondpass) {
00535 GECODE_ES_CHECK((bounds_propagation<OffsetView,
00536 ViewTuple<OffsetView,2>, Perm>
00537 (home, oxz, oy, secondpass, nofix, match_fixed)));
00538 }
00539 } else {
00540 GECODE_ES_CHECK((bounds_propagation<View, Tuple, Perm>
00541 (home, xz, y, secondpass, nofix, match_fixed)));
00542
00543 if (secondpass) {
00544 GECODE_ES_CHECK((bounds_propagation<View, Tuple, Perm>
00545 (home, xz, y, secondpass, nofix, match_fixed)));
00546 }
00547 }
00548 } else {
00549
00550 if (dropfst) {
00551 xz.drop_fst(dropfst, home, this, PC_INT_BND);
00552 y.drop_fst (dropfst, home, this, PC_INT_BND);
00553 }
00554
00555 n = xz.size();
00556
00557 if (n < 2) {
00558 if (xz[0][0].max() < y[0].min() || y[0].max() < xz[0][0].min()) {
00559 return ES_FAILED;
00560 } else {
00561 Rel::EqBnd<View,View>::post(home, xz[0][0], y[0]);
00562 return ES_SUBSUMED;
00563 }
00564 }
00565 GECODE_ES_CHECK((bounds_propagation<View, Tuple, Perm>
00566 (home, xz, y, secondpass, nofix, match_fixed)));
00567
00568 }
00569
00570 if (!normalize<View, Tuple>(home, y, xz, nofix)) {
00571 return ES_FAILED;
00572 }
00573
00574 GECODE_AUTOARRAY(int, tau, n);
00575 if (match_fixed) {
00576
00577
00578 for (int i = xz.size(); i--; ) {
00579 int pi = xz[i][1].val();
00580 tau[pi] = i;
00581 }
00582 } else {
00583 for (int i = n; i--; ) {
00584 tau[i] = i;
00585 }
00586 }
00587
00588 sort_tau<View, Tuple, Perm>(xz, tau);
00589
00590
00591 bool xbassigned = true;
00592 for (int i = xz.size(); i--; ) {
00593 if (xz[tau[i]][0].assigned() && xbassigned) {
00594 ModEvent me = y[i].eq(home, xz[tau[i]][0].val());
00595 if (me_failed(me)) {
00596 return ES_FAILED;
00597 }
00598 } else {
00599 xbassigned = false;
00600 }
00601 }
00602
00603 subsumed = true;
00604 array_subs = false;
00605 noperm_bc = false;
00606
00607
00608 sort_sigma<View, Tuple, Perm>(xz, match_fixed);
00609
00610 if (Perm) {
00611 for (int i = 0; i < xz.size() - 1; i++) {
00612
00613
00614 if (xz[i][1].min() == xz[i+1][1].min() &&
00615 xz[i][1].max() == xz[i+1][1].max() &&
00616 xz[i][1].size() == 2 && xz[i][1].range()) {
00617 if (xz[i][0].min() < xz[i+1][0].min()) {
00618 ModEvent me = y[xz[i][1].min()].gq(home, xz[i][0].min());
00619 if (me_failed(me)) {
00620 return ES_FAILED;
00621 }
00622 nofix |= (y[xz[i][1].min()].modified() &&
00623 y[xz[i][1].min()].min() != xz[i][0].min());
00624
00625 me = y[xz[i+1][1].max()].gq(home, xz[i+1][0].min());
00626 if (me_failed(me)) {
00627 return ES_FAILED;
00628 }
00629 nofix |= (y[xz[i+1][1].max()].modified() &&
00630 y[xz[i+1][1].max()].min() != xz[i+1][0].min());
00631 }
00632 }
00633 }
00634 }
00635
00636
00637
00638 bool xassigned = true;
00639 for (int i = 0; i < xz.size(); i++) {
00640 if (xz[i][0].assigned() && xassigned) {
00641 ModEvent me = y[i].eq(home, xz[i][0].val());
00642 if (me_failed(me)) {
00643 return ES_FAILED;
00644 }
00645 } else {
00646 xassigned = false;
00647 }
00648 }
00649
00650
00651
00652
00653 int tlb = std::min(xz[0][0].min(), y[0].min());
00654 int tub = std::max(xz[xz.size() - 1][0].max(), y[y.size() - 1].max());
00655 for (int i = xz.size(); i--; ) {
00656 ModEvent me = y[i].lq(home, tub);
00657 if (me_failed(me)) {
00658 return ES_FAILED;
00659 }
00660 nofix |= y[i].modified() && y[i].max() != tub;
00661
00662 me = y[i].gq(home, tlb);
00663 if (me_failed(me)) {
00664 return ES_FAILED;
00665 }
00666 nofix |= y[i].modified() && y[i].min() != tlb;
00667
00668 me = xz[i][0].lq(home, tub);
00669 if (me_failed(me)) {
00670 return ES_FAILED;
00671 }
00672 nofix |= xz[i][0].modified() && xz[i][0].max() != tub;
00673
00674 me = xz[i][0].gq(home, tlb);
00675 if (me_failed(me)) {
00676 return ES_FAILED;
00677 }
00678 nofix |= xz[i][0].modified() && xz[i][0].min() != tlb;
00679 }
00680
00681 if (!array_assigned<View, Tuple, Perm>
00682 (home, xz, y, array_subs, match_fixed, nofix, noperm_bc)) {
00683 return ES_FAILED;
00684 }
00685
00686 if (array_subs) {
00687 return ES_SUBSUMED;
00688 }
00689
00690 if (!check_subsumption<View, Tuple, Perm>
00691 (home, xz, y, subsumed, dropfst)) {
00692 return ES_FAILED;
00693 }
00694
00695 if (subsumed) {
00696 return ES_SUBSUMED;
00697 }
00698
00699 return nofix ? ES_NOFIX : ES_FIX;
00700 }
00701
00702 template<class View, class Tuple, bool Perm>
00703 ExecStatus
00704 Sortedness<View, Tuple, Perm>::
00705 post(Space* home, ViewArray<Tuple>& xz0, ViewArray<View>& y0) {
00706 int n = xz0.size();
00707 if (n < 2) {
00708 if ((xz0[0][0].max() < y0[0].min()) || (y0[0].max() < xz0[0][0].min())) {
00709 return ES_FAILED;
00710 } else {
00711 Rel::EqBnd<View,View>::post(home, xz0[0][0], y0[0]);
00712 if (Perm) {
00713 GECODE_ME_CHECK(xz0[0][1].eq(home, 0));
00714 }
00715 }
00716 } else {
00717 new (home) Sortedness<View, Tuple, Perm>(home, xz0, y0);
00718 }
00719 return ES_OK;
00720 }
00721
00722 }}}
00723
00724
00725
00726
00727