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 void
00386 Sorted<View,Perm>::reschedule(Space& home) {
00387 x.reschedule(home, *this, PC_INT_BND);
00388 y.reschedule(home, *this, PC_INT_BND);
00389 if (Perm)
00390 z.reschedule(home, *this, PC_INT_BND);
00391 }
00392
00393 template<class View, bool Perm>
00394 ExecStatus
00395 Sorted<View,Perm>::propagate(Space& home, const ModEventDelta&) {
00396 int n = x.size();
00397 bool secondpass = false;
00398 bool nofix = false;
00399 int dropfst = 0;
00400
00401 bool subsumed = false;
00402 bool array_subs = false;
00403 bool match_fixed = false;
00404
00405
00406 if (!normalize(home, y, x, nofix))
00407 return ES_FAILED;
00408
00409
00410 sort_sigma<View,Perm>(home,x,z);
00411
00412 bool noperm_bc = false;
00413 if (!array_assigned<View,Perm>
00414 (home, x, y, z, array_subs, match_fixed, nofix, noperm_bc))
00415 return ES_FAILED;
00416
00417 if (array_subs)
00418 return home.ES_SUBSUMED(*this);
00419
00420 sort_sigma<View,Perm>(home,x,z);
00421
00422
00423
00424
00425 if (!check_subsumption<View,Perm>(x,y,z,subsumed,dropfst))
00426 return ES_FAILED;
00427
00428 if (subsumed)
00429 return home.ES_SUBSUMED(*this);
00430
00431 if (Perm) {
00432
00433 if (dropfst) {
00434 reachable = w[dropfst - 1].max();
00435 bool unreachable = true;
00436 for (int i = x.size(); unreachable && i-- ; ) {
00437 unreachable &= (reachable < x[i].min());
00438 }
00439
00440 if (unreachable) {
00441 x.drop_fst(dropfst, home, *this, PC_INT_BND);
00442 y.drop_fst(dropfst, home, *this, PC_INT_BND);
00443 z.drop_fst(dropfst, home, *this, PC_INT_BND);
00444 } else {
00445 dropfst = 0;
00446 }
00447 }
00448
00449 n = x.size();
00450
00451 if (n < 2) {
00452 if (x[0].max() < y[0].min() || y[0].max() < x[0].min())
00453 return ES_FAILED;
00454 if (Perm) {
00455 GECODE_ME_CHECK(z[0].eq(home, w.size() - 1));
00456 }
00457 GECODE_REWRITE(*this,(Rel::EqBnd<View,View>::post(home(*this), x[0], y[0])));
00458 }
00459
00460
00461
00462
00463 int valid = n - 1;
00464 int index = 0;
00465 int shift = 0;
00466
00467 for (int i = n; i--; ){
00468 if (z[i].max() > index)
00469 index = z[i].max();
00470 if (index > valid)
00471 shift = index - valid;
00472 }
00473
00474 if (shift) {
00475 ViewArray<OffsetView> ox(home,n), oy(home,n), oz(home,n);
00476
00477 for (int i = n; i--; ) {
00478 GECODE_ME_CHECK(z[i].gq(home, shift));
00479
00480 oz[i] = OffsetView(z[i], -shift);
00481 ox[i] = OffsetView(x[i], 0);
00482 oy[i] = OffsetView(y[i], 0);
00483 }
00484
00485 GECODE_ES_CHECK((bounds_propagation<OffsetView,Perm>
00486 (home,*this,ox,oy,oz,secondpass,nofix,match_fixed)));
00487
00488 if (secondpass) {
00489 GECODE_ES_CHECK((bounds_propagation<OffsetView,Perm>
00490 (home,*this,ox,oy,oz,secondpass,nofix,match_fixed)));
00491 }
00492 } else {
00493 GECODE_ES_CHECK((bounds_propagation<View,Perm>
00494 (home,*this,x,y,z,secondpass,nofix,match_fixed)));
00495
00496 if (secondpass) {
00497 GECODE_ES_CHECK((bounds_propagation<View,Perm>
00498 (home,*this,x,y,z,secondpass,nofix,match_fixed)));
00499 }
00500 }
00501 } else {
00502
00503 if (dropfst) {
00504 x.drop_fst(dropfst, home, *this, PC_INT_BND);
00505 y.drop_fst(dropfst, home, *this, PC_INT_BND);
00506 }
00507
00508 n = x.size();
00509
00510 if (n < 2) {
00511 if (x[0].max() < y[0].min() || y[0].max() < x[0].min())
00512 return ES_FAILED;
00513 GECODE_REWRITE(*this,(Rel::EqBnd<View,View>::post(home(*this), x[0], y[0])));
00514 }
00515
00516 GECODE_ES_CHECK((bounds_propagation<View,Perm>
00517 (home, *this, x, y, z,secondpass, nofix, match_fixed)));
00518
00519 }
00520
00521 if (!normalize(home, y, x, nofix))
00522 return ES_FAILED;
00523
00524 Region r(home);
00525 int* tau = r.alloc<int>(n);
00526 if (match_fixed) {
00527
00528
00529 for (int i = x.size(); i--; ) {
00530 int pi = z[i].val();
00531 tau[pi] = i;
00532 }
00533 } else {
00534 for (int i = n; i--; ) {
00535 tau[i] = i;
00536 }
00537 }
00538
00539 sort_tau<View,Perm>(x,z,tau);
00540
00541
00542 bool xbassigned = true;
00543 for (int i = x.size(); i--; ) {
00544 if (x[tau[i]].assigned() && xbassigned) {
00545 GECODE_ME_CHECK(y[i].eq(home, x[tau[i]].val()));
00546 } else {
00547 xbassigned = false;
00548 }
00549 }
00550
00551 subsumed = true;
00552 array_subs = false;
00553 noperm_bc = false;
00554
00555
00556 sort_sigma<View,Perm>(home,x,z);
00557
00558 if (Perm) {
00559 for (int i = 0; i < x.size() - 1; i++) {
00560
00561
00562 if (z[i].min() == z[i+1].min() &&
00563 z[i].max() == z[i+1].max() &&
00564 z[i].size() == 2 && z[i].range()) {
00565 if (x[i].min() < x[i+1].min()) {
00566 ModEvent me = y[z[i].min()].gq(home, x[i].min());
00567 GECODE_ME_CHECK(me);
00568 nofix |= (me_modified(me) &&
00569 y[z[i].min()].min() != x[i].min());
00570
00571 me = y[z[i+1].max()].gq(home, x[i+1].min());
00572 GECODE_ME_CHECK(me);
00573 nofix |= (me_modified(me) &&
00574 y[z[i+1].max()].min() != x[i+1].min());
00575 }
00576 }
00577 }
00578 }
00579
00580
00581
00582 bool xassigned = true;
00583 for (int i = 0; i < x.size(); i++) {
00584 if (x[i].assigned() && xassigned) {
00585 GECODE_ME_CHECK(y[i].eq(home,x[i].val()));
00586 } else {
00587 xassigned = false;
00588 }
00589 }
00590
00591
00592
00593
00594 int tlb = std::min(x[0].min(), y[0].min());
00595 int tub = std::max(x[x.size() - 1].max(), y[y.size() - 1].max());
00596 for (int i = x.size(); i--; ) {
00597 ModEvent me = y[i].lq(home, tub);
00598 GECODE_ME_CHECK(me);
00599 nofix |= me_modified(me) && (y[i].max() != tub);
00600
00601 me = y[i].gq(home, tlb);
00602 GECODE_ME_CHECK(me);
00603 nofix |= me_modified(me) && (y[i].min() != tlb);
00604
00605 me = x[i].lq(home, tub);
00606 GECODE_ME_CHECK(me);
00607 nofix |= me_modified(me) && (x[i].max() != tub);
00608
00609 me = x[i].gq(home, tlb);
00610 GECODE_ME_CHECK(me);
00611 nofix |= me_modified(me) && (x[i].min() != tlb);
00612 }
00613
00614 if (!array_assigned<View,Perm>
00615 (home, x, y, z, array_subs, match_fixed, nofix, noperm_bc))
00616 return ES_FAILED;
00617
00618 if (array_subs)
00619 return home.ES_SUBSUMED(*this);
00620
00621 if (!check_subsumption<View,Perm>(x,y,z,subsumed,dropfst))
00622 return ES_FAILED;
00623
00624 if (subsumed)
00625 return home.ES_SUBSUMED(*this);
00626
00627 return nofix ? ES_NOFIX : ES_FIX;
00628 }
00629
00630 template<class View, bool Perm>
00631 ExecStatus
00632 Sorted<View,Perm>::
00633 post(Home home,
00634 ViewArray<View>& x0, ViewArray<View>& y0, ViewArray<View>& z0) {
00635 int n = x0.size();
00636 if (n < 2) {
00637 if ((x0[0].max() < y0[0].min()) || (y0[0].max() < x0[0].min()))
00638 return ES_FAILED;
00639 GECODE_ES_CHECK((Rel::EqBnd<View,View>::post(home,x0[0],y0[0])));
00640 if (Perm) {
00641 GECODE_ME_CHECK(z0[0].eq(home,0));
00642 }
00643 } else {
00644 if (Perm) {
00645 ViewArray<View> z(home,n);
00646 for (int i=n; i--; ) {
00647 z[i]=z0[i];
00648 GECODE_ME_CHECK(z[i].gq(home,0));
00649 GECODE_ME_CHECK(z[i].lq(home,n-1));
00650 }
00651 GECODE_ES_CHECK(Distinct::Bnd<View>::post(home,z));
00652 }
00653 new (home) Sorted<View,Perm>(home,x0,y0,z0);
00654 }
00655 return ES_OK;
00656 }
00657
00658 }}}
00659
00660
00661
00662
00663