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