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