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