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, bool shared>
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 for (int i = n; i--; ) {
00098 if (xz[i][1].assigned()) {
00099
00100
00101
00102 int v = xz[i][1].val();
00103 if (xz[i][0].assigned()) {
00104
00105 if (shared && y[v].modified()) {
00106 return ES_NOFIX;
00107 }
00108 GECODE_ME_CHECK(y[v].eq(home, xz[i][0].val()));
00109 } else {
00110 if (y[v].assigned()) {
00111
00112 if (shared && xz[i][0].modified()) {
00113 return ES_NOFIX;
00114 }
00115 GECODE_ME_CHECK(xz[i][0].eq(home, y[v].val()));
00116 } else {
00117
00118 if (shared && xz[i][0].modified()) {
00119 return ES_NOFIX;
00120 }
00121 ModEvent me = xz[i][0].lq(home, y[v].max());
00122 if (me_failed(me)) {
00123 return ES_FAILED;
00124 }
00125 nofix |= (me_modified(me) && xz[i][0].max() != y[v].max());
00126
00127
00128 if (shared && xz[i][0].modified()) {
00129 return ES_NOFIX;
00130 }
00131
00132 me = xz[i][0].gq(home, y[v].min());
00133 if (me_failed(me)) {
00134 return ES_FAILED;
00135 }
00136 nofix |= (me_modified(me) && xz[i][0].min() != y[v].min());
00137
00138
00139
00140 if (shared && y[v].modified()) {
00141 return ES_NOFIX;
00142 }
00143
00144 me = y[v].lq(home, xz[i][0].max());
00145 if (me_failed(me)) {
00146 return ES_FAILED;
00147 }
00148 nofix |= (me_modified(me) && y[v].max() != xz[i][0].max());
00149
00150
00151 if (shared && y[v].modified()) {
00152 return ES_NOFIX;
00153 }
00154
00155 me = y[v].gq(home, xz[i][0].min());
00156 if (me_failed(me)) {
00157 return ES_FAILED;
00158 }
00159 nofix |= (me_modified(me) && y[v].min() != xz[i][0].min());
00160 }
00161 }
00162 } else {
00163
00164
00165 int l = xz[i][1].min();
00166 int r = xz[i][1].max();
00167 if (xz[i][0].assigned()) {
00168
00169 int v = xz[i][0].val();
00170
00171 while (y[l].max() < v) {
00172 ModEvent me = xz[i][1].gr(home, l);
00173 if (me_failed(me)) {
00174 return ES_FAILED;
00175 }
00176 nofix |= ( me_modified(me) && xz[i][1].min() != l + 1);
00177 l = xz[i][1].min();
00178 }
00179
00180 while (y[r].min() > v) {
00181 ModEvent me = xz[i][1].le(home, r);
00182 if (me_failed(me)) {
00183 return ES_FAILED;
00184 }
00185 nofix |= ( me_modified(me) && xz[i][1].max() != r - 1);
00186 r = xz[i][1].max();
00187 }
00188 } else {
00189
00190
00191 if (shared && xz[i][0].modified()) {
00192 return ES_NOFIX;
00193 }
00194
00195 ModEvent me = xz[i][0].lq(home, y[r].max());
00196 if (me_failed(me)) {
00197 return ES_FAILED;
00198 }
00199 nofix |= (me_modified(me) && xz[i][0].max() != y[r].max());
00200
00201
00202 if (shared && xz[i][0].modified()) {
00203 return ES_NOFIX;
00204 }
00205
00206 me = xz[i][0].gq(home, y[l].min());
00207 if (me_failed(me)) {
00208 return ES_FAILED;
00209 }
00210 nofix |= (me_modified(me) && xz[i][0].min() != y[l].min());
00211 }
00212 }
00213 }
00214 }
00215
00216
00217
00218
00219 if (!match_fixed) {
00220 sort_sigma<View, Tuple, Perm>(xz, match_fixed);
00221 }
00222
00223
00224 bool subsumed = true;
00225 bool array_subs = false;
00226 int dropfst = 0;
00227
00228 if (!(check_subsumption<View, Tuple, Perm>
00229 (home, xz, y, subsumed, dropfst)) ||
00230 !(array_assigned<View, Tuple, Perm, shared>
00231 (home, xz, y, array_subs, match_fixed, nofix))) {
00232 return ES_FAILED;
00233 }
00234
00235 if (shared && nofix) {
00236 return ES_NOFIX;
00237 }
00238
00239 if (subsumed || array_subs) {
00240 return ES_SUBSUMED;
00241 }
00242
00243
00244
00245
00246
00247
00248
00249
00250
00251
00252 if (!normalize<View, Tuple, shared>(home, y, xz, nofix)) {
00253 return ES_FAILED;
00254 }
00255
00256 if (shared && nofix) {
00257 return ES_NOFIX;
00258 }
00259
00260
00261
00262
00263
00264
00265
00266 sort_tau<View, Tuple, Perm>(xz, tau);
00267
00268
00269
00270
00271
00272
00273
00274
00275
00276
00277
00278 if (!match_fixed) {
00279
00280 if (!glover<View, Tuple, Perm>
00281 (home, xz, y, tau, phi, sequence, vertices)) {
00282 return ES_FAILED;
00283 }
00284 } else {
00285 for (int i = xz.size(); i--; ) {
00286 phi[i] = xz[i][1].val();
00287 phiprime[i] = phi[i];
00288 }
00289 }
00290
00291 if(!yval) {
00292
00293 if (!match_fixed) {
00294 if (!revglover<View, Tuple, Perm>
00295 (home, xz, y, tau, phiprime, sequence, vertices)) {
00296 return ES_FAILED;
00297 }
00298 }
00299
00300 if (!narrow_domy<View, Tuple, Perm, shared>
00301 (home, xz, y, phi, phiprime, nofix)) {
00302 return ES_FAILED;
00303 }
00304
00305 if (shared && nofix) {
00306 return ES_NOFIX;
00307 }
00308
00309 if (nofix && !match_fixed) {
00310
00311
00312 for (int i = y.size(); i--; ) {
00313 phi[i] = 0;
00314 phiprime[i] = 0;
00315 }
00316 if (!glover<View, Tuple, Perm>
00317 (home, xz, y, tau, phi, sequence, vertices)) {
00318 return ES_FAILED;
00319 }
00320
00321 if (!revglover<View, Tuple, Perm>
00322 (home, xz, y, tau, phiprime, sequence, vertices)) {
00323 return ES_FAILED;
00324 }
00325
00326 if (!narrow_domy<View, Tuple, Perm, shared>
00327 (home, xz, y, phi, phiprime, nofix)) {
00328 return ES_FAILED;
00329 }
00330
00331 if (shared && nofix) {
00332 return ES_NOFIX;
00333 }
00334
00335 }
00336 }
00337
00338
00339
00340
00341
00342
00343
00344
00345
00346 GECODE_AUTOARRAY(int, scclist, n);
00347 GECODE_AUTOARRAY(SccComponent, sinfo , n);
00348
00349 for(int i = n; i--; ) {
00350 sinfo[i].left = i;
00351 sinfo[i].right = i;
00352 sinfo[i].rightmost = i;
00353 sinfo[i].leftmost = i;
00354 }
00355
00356 computesccs<View>(home, xz, y, phi, sinfo, scclist);
00357
00358
00359
00360
00361
00362
00363
00364
00365 if (!narrow_domx<View, Tuple, Perm, shared>
00366 (home, xz, y, tau, phi, scclist, sinfo, nofix)) {
00367 return ES_FAILED;
00368 }
00369
00370 if (shared && nofix) {
00371 return ES_NOFIX;
00372 }
00373
00374
00375 if (Perm) {
00376 if (!perm_bc<View, Tuple, Perm, shared>
00377 (home, tau, xz, repairpass, nofix)) {
00378 return ES_FAILED;
00379 }
00380
00381 if (shared && nofix) {
00382 return ES_NOFIX;
00383 }
00384
00385 }
00386
00387 return nofix ? ES_NOFIX : ES_FIX;
00388 }
00389
00390 template<class View, class Tuple, bool Perm, bool shared>
00391 Sortedness<View, Tuple, Perm, shared>::
00392 Sortedness(Space* home, bool share, Sortedness<View, Tuple, Perm, shared>& p):
00393 Propagator(home, share, p),
00394 reachable(p.reachable) {
00395 xz.update(home, share, p.xz);
00396 y.update(home, share, p.y);
00397 w.update(home, share, p.w);
00398 }
00399
00400 template<class View, class Tuple, bool Perm, bool shared>
00401 Sortedness<View, Tuple, Perm, shared>::
00402 Sortedness(Space* home, ViewArray<Tuple>& xz0, ViewArray<View>& y0):
00403 Propagator(home,true), xz(xz0), y(y0), w(home, y0), reachable(-1) {
00404 xz.subscribe(home, this, PC_INT_BND);
00405 y.subscribe(home, this, PC_INT_BND);
00406
00407 }
00408
00409 template<class View, class Tuple, bool Perm, bool shared>
00410 Sortedness<View, Tuple, Perm, shared>::~Sortedness(void) {
00411 xz.cancel(this, PC_INT_BND);
00412 y.cancel(this, PC_INT_BND);
00413 }
00414
00415 template<class View, class Tuple, bool Perm, bool shared>
00416 Actor* Sortedness<View, Tuple, Perm, shared>::copy(Space* home, bool share) {
00417 return new (home) Sortedness<View, Tuple, Perm, shared>(home, share, *this);
00418 }
00419
00420 template<class View, class Tuple, bool Perm, bool shared>
00421 PropCost Sortedness<View, Tuple, Perm, shared>::cost(void) const {
00422 return PC_LINEAR_LO;
00423 }
00424
00425 template<class View, class Tuple, bool Perm, bool shared>
00426 ExecStatus
00427 Sortedness<View, Tuple, Perm, shared>::propagate(Space* home) {
00428
00429 int n = xz.size();
00430 bool secondpass = false;
00431 bool nofix = false;
00432 int dropfst = 0;
00433
00434 bool subsumed = false;
00435 bool array_subs = false;
00436 bool match_fixed = false;
00437
00438
00439 sort_sigma<View, Tuple, Perm>(xz, match_fixed);
00440
00441
00442 if (!normalize<View, Tuple, shared>(home, y, xz, nofix)) {
00443 return ES_FAILED;
00444 }
00445
00446 if (shared && nofix) {
00447 return ES_NOFIX;
00448 }
00449
00450 if (!array_assigned<View, Tuple, Perm, shared>
00451 (home, xz, y, array_subs, match_fixed, nofix)) {
00452 return ES_FAILED;
00453 }
00454
00455 if (shared && nofix) {
00456 return ES_NOFIX;
00457 }
00458
00459 if (array_subs) {
00460 return ES_SUBSUMED;
00461 }
00462
00463 if (match_fixed) {
00464 sort_sigma<View, Tuple, Perm>(xz, match_fixed);
00465 }
00466
00467
00468
00469
00470 if (!check_subsumption<View, Tuple, Perm>
00471 (home, xz, y, subsumed, dropfst)) {
00472 return ES_FAILED;
00473 }
00474
00475 if (shared && nofix) {
00476 return ES_NOFIX;
00477 }
00478
00479 if (subsumed) {
00480 return ES_SUBSUMED;
00481 }
00482
00483
00484
00485 if (Perm) {
00486
00487
00488 if (dropfst) {
00489 reachable = w[dropfst - 1].max();
00490 bool unreachable = true;
00491 for (int i = xz.size(); unreachable && i-- ; ) {
00492 unreachable &= (reachable < xz[i][0].min());
00493 }
00494
00495 if (unreachable) {
00496 xz.drop_fst(dropfst, this, PC_INT_BND);
00497 y.drop_fst (dropfst, this, PC_INT_BND);
00498 } else {
00499 dropfst = 0;
00500 }
00501 }
00502
00503 n = xz.size();
00504
00505 if (n < 2) {
00506 if (xz[0][0].max() < y[0].min() || y[0].max() < xz[0][0].min()) {
00507 return ES_FAILED;
00508 } else {
00509 Rel::EqBnd<View>::post(home, xz[0][0], y[0]);
00510
00511
00512 if (shared && xz[0][1].modified()) {
00513 return ES_NOFIX;
00514 }
00515
00516 GECODE_ME_CHECK(xz[0][1].eq(home, w.size() - 1));
00517
00518 return ES_SUBSUMED;
00519 }
00520 }
00521
00522
00523
00524
00525
00526 int valid = n - 1;
00527 int index = 0;
00528 int shift = 0;
00529
00530 for (int i = n; i--; ){
00531 if (xz[i][1].max() > index) {
00532 index = xz[i][1].max();
00533 }
00534 if (index > valid) {
00535 shift = index - valid;
00536 }
00537 }
00538
00539 if (shift) {
00540
00541 ViewArray<ViewTuple<OffsetView,2> > oxz(home, n);
00542 ViewArray<OffsetView> oy(home, n);
00543
00544 for (int i = n; i--; ) {
00545
00546 GECODE_ME_CHECK(xz[i][1].gq(home, shift));
00547
00548 oxz[i][1] = OffsetView(xz[i][1], -shift);
00549 oxz[i][0] = OffsetView(xz[i][0], 0);
00550 oy[i] = OffsetView(y[i], 0);
00551 }
00552
00553 GECODE_ES_CHECK((bounds_propagation<OffsetView,
00554 ViewTuple<OffsetView,2>, Perm, shared >
00555 (home, oxz, oy, secondpass, nofix, match_fixed)));
00556
00557 if (secondpass) {
00558 GECODE_ES_CHECK((bounds_propagation<OffsetView,
00559 ViewTuple<OffsetView,2>, Perm, shared >
00560 (home, oxz, oy, secondpass, nofix, match_fixed)));
00561 }
00562 } else {
00563 GECODE_ES_CHECK((bounds_propagation<View, Tuple, Perm, shared>
00564 (home, xz, y, secondpass, nofix, match_fixed)));
00565
00566 if (secondpass) {
00567 GECODE_ES_CHECK((bounds_propagation<View, Tuple, Perm, shared>
00568 (home, xz, y, secondpass, nofix, match_fixed)));
00569 }
00570 }
00571 } else {
00572
00573
00574 if (dropfst) {
00575 xz.drop_fst(dropfst, this, PC_INT_BND);
00576 y.drop_fst (dropfst, this, PC_INT_BND);
00577 }
00578
00579 n = xz.size();
00580
00581 if (n < 2) {
00582 if (xz[0][0].max() < y[0].min() || y[0].max() < xz[0][0].min()) {
00583 return ES_FAILED;
00584 } else {
00585 Rel::EqBnd<View>::post(home, xz[0][0], y[0]);
00586 return ES_SUBSUMED;
00587 }
00588 }
00589 GECODE_ES_CHECK((bounds_propagation<View, Tuple, Perm, shared>
00590 (home, xz, y, secondpass, nofix, match_fixed)));
00591
00592 }
00593
00594 if (!normalize<View, Tuple, shared>(home, y, xz, nofix)) {
00595 return ES_FAILED;
00596 }
00597
00598 subsumed = true;
00599 array_subs = false;
00600
00601
00602 if (!match_fixed) {
00603 sort_sigma<View, Tuple, Perm>(xz, match_fixed);
00604 }
00605
00606 if (!array_assigned<View, Tuple, Perm, shared>
00607 (home, xz, y, array_subs, match_fixed, nofix)) {
00608 return ES_FAILED;
00609 }
00610
00611 if (array_subs) {
00612 return ES_SUBSUMED;
00613 }
00614
00615 if (!check_subsumption<View, Tuple, Perm>
00616 (home, xz, y, subsumed, dropfst)) {
00617 return ES_FAILED;
00618 }
00619
00620 if (subsumed) {
00621 return ES_SUBSUMED;
00622 }
00623
00624 return nofix ? ES_NOFIX : ES_FIX;
00625 }
00626
00627 template<class View, class Tuple, bool Perm, bool shared>
00628 ExecStatus
00629 Sortedness<View, Tuple, Perm, shared>::
00630 post(Space* home, ViewArray<Tuple>& xz0, ViewArray<View>& y0) {
00631 int n = xz0.size();
00632 if (n < 2) {
00633 if ((xz0[0][0].max() < y0[0].min()) || (y0[0].max() < xz0[0][0].min())) {
00634 return ES_FAILED;
00635 } else {
00636 Rel::EqBnd<View>::post(home, xz0[0][0], y0[0]);
00637 if (Perm) {
00638 GECODE_ME_CHECK(xz0[0][1].eq(home, 0));
00639 }
00640 }
00641 } else {
00642 new (home) Sortedness<View, Tuple, Perm, shared>(home, xz0, y0);
00643 }
00644 return ES_OK;
00645 }
00646
00647 }}}
00648
00649
00650
00651
00652