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