41 namespace Gecode {
namespace Int {
namespace Sorted {
75 template<
class View,
bool Perm>
88 int* tau = r.
alloc<
int>(n);
89 int* phi = r.
alloc<
int>(n);
90 int* phiprime = r.
alloc<
int>(n);
92 int* vertices = r.
alloc<
int>(n);
99 for (
int i = n;
i--; )
112 for (
int i=n;
i--;) {
113 int min = x[
i].min();
114 int max = x[
i].max();
115 for (
int j=0; j<n; j++) {
116 if ( (y[j].
min() > min) ||
117 (y[j].
min() <= min && min <= y[j].
max()) ) {
122 for (
int j=n; j--;) {
123 if (y[j].
min() > max) {
126 }
else if (y[j].
min() <= max && min <= y[j].
max()) {
133 for (
int i = n;
i--; ) {
135 int minr = allbnd[
i].
min;
137 int maxr = allbnd[
i].
max;
143 nofix |= (
me_modified(me) && (x[
i].min() != y[minr].min()));
145 me = x[
i].lq(home, y[maxr].
max());
148 nofix |= (
me_modified(me) && (x[
i].min() != y[maxr].max()));
150 me = z[
i].gq(home, minr);
155 me = z[
i].lq(home, maxr);
162 if (!
channel(home,x,y,z,nofix))
182 if (!
channel(home,x,y,z,nofix))
192 sort_sigma<View,Perm>(home,x,z);
195 bool array_subs =
false;
197 bool noperm_bc =
false;
199 if (!check_subsumption<View,Perm>(x,y,z,subsumed,dropfst) ||
200 !array_assigned<View,Perm>(home,x,y,z,array_subs,match_fixed,nofix,noperm_bc))
203 if (subsumed || array_subs)
204 return home.ES_SUBSUMED(p);
212 sort_tau<View,Perm>(x,z,tau);
225 if (!
glover(x,y,tau,phi,sequence,vertices))
228 for (
int i = x.
size();
i--; ) {
230 phiprime[
i] = phi[
i];
234 for (
int i = n;
i--; )
238 !
revglover(x,y,tau,phiprime,sequence,vertices))
244 if (nofix && !match_fixed) {
247 for (
int j = y.size(); j--; )
248 phi[j]=phiprime[j]=0;
250 if (!
glover(x,y,tau,phi,sequence,vertices))
253 if (!
revglover(x,y,tau,phiprime,sequence,vertices))
270 int* scclist = r.
alloc<
int>(n);
273 for(
int i = n;
i--; )
274 sinfo[
i].left=sinfo[
i].right=sinfo[
i].rightmost=sinfo[
i].leftmost=
i;
285 if (!narrow_domx<View,Perm>(home,x,y,z,tau,phi,scclist,sinfo,nofix))
291 (home, tau, sinfo, scclist, x,z, repairpass, nofix))
296 if (!
channel(home,x,y,z,nofix))
302 sort_tau<View,Perm>(x,z,tau);
308 for (
int i = x.
size() - 1;
i--; ) {
310 if (z[tau[
i]].
min() == z[tau[
i+1]].min() &&
311 z[tau[
i]].max() == z[tau[
i+1]].max() &&
312 z[tau[
i]].size() == 2 && z[tau[
i]].range()) {
314 if (x[tau[
i]].
max() < x[tau[
i+1]].max()) {
319 y[z[tau[
i]].min()].max() != x[tau[
i]].max());
321 me = y[z[tau[
i+1]].max()].lq(home, x[tau[
i+1]].
max());
325 y[z[tau[
i+1]].max()].max() != x[tau[
i+1]].max());
333 template<
class View,
bool Perm>
337 reachable(p.reachable) {
338 x.update(home, share, p.x);
339 y.update(home, share, p.y);
340 z.update(home, share, p.z);
341 w.update(home, share, p.w);
344 template<
class View,
bool Perm>
348 Propagator(home), x(x0), y(y0), z(z0), w(home,y0), reachable(-1) {
355 template<
class View,
bool Perm>
363 return sizeof(*this);
366 template<
class View,
bool Perm>
371 template<
class View,
bool Perm>
376 template<
class View,
bool Perm>
380 bool secondpass =
false;
385 bool array_subs =
false;
386 bool match_fixed =
false;
393 sort_sigma<View,Perm>(home,x,z);
395 bool noperm_bc =
false;
396 if (!array_assigned<View,Perm>
397 (home, x, y, z, array_subs, match_fixed, nofix, noperm_bc))
401 return home.ES_SUBSUMED(*
this);
403 sort_sigma<View,Perm>(home,x,z);
408 if (!check_subsumption<View,Perm>(x,y,z,subsumed,dropfst))
412 return home.ES_SUBSUMED(*
this);
417 reachable = w[dropfst - 1].max();
418 bool unreachable =
true;
419 for (
int i = x.
size(); unreachable &&
i-- ; ) {
420 unreachable &= (reachable < x[
i].min());
450 for (
int i = n;
i--; ){
451 if (z[
i].
max() > index)
454 shift = index -
valid;
460 for (
int i = n;
i--; ) {
469 (home,*
this,ox,oy,oz,secondpass,nofix,match_fixed)));
473 (home,*
this,ox,oy,oz,secondpass,nofix,match_fixed)));
477 (home,*
this,x,y,z,secondpass,nofix,match_fixed)));
481 (home,*
this,x,y,z,secondpass,nofix,match_fixed)));
500 (home, *
this, x, y, z,secondpass, nofix, match_fixed)));
508 int* tau = r.
alloc<
int>(n);
512 for (
int i = x.
size();
i--; ) {
517 for (
int i = n;
i--; ) {
522 sort_tau<View,Perm>(x,z,tau);
525 bool xbassigned =
true;
526 for (
int i = x.
size();
i--; ) {
527 if (x[tau[
i]].
assigned() && xbassigned) {
539 sort_sigma<View,Perm>(home,x,z);
542 for (
int i = 0;
i < x.
size() - 1;
i++) {
545 if (z[
i].
min() == z[
i+1].min() &&
546 z[
i].max() == z[
i+1].max() &&
547 z[
i].size() == 2 && z[
i].range()) {
548 if (x[
i].
min() < x[
i+1].min()) {
552 y[z[
i].min()].min() != x[
i].min());
554 me = y[z[
i+1].max()].gq(home, x[
i+1].
min());
557 y[z[
i+1].max()].min() != x[
i+1].min());
565 bool xassigned =
true;
566 for (
int i = 0;
i < x.
size();
i++) {
578 int tub =
std::max(x[x.size() - 1].max(), y[y.size() - 1].max());
579 for (
int i = x.
size();
i--; ) {
584 me = y[
i].gq(home, tlb);
588 me = x[
i].lq(home, tub);
592 me = x[
i].gq(home, tlb);
597 if (!array_assigned<View,Perm>
598 (home, x, y, z, array_subs, match_fixed, nofix, noperm_bc))
602 return home.ES_SUBSUMED(*
this);
604 if (!check_subsumption<View,Perm>(x,y,z,subsumed,dropfst))
608 return home.ES_SUBSUMED(*
this);
613 template<
class View,
bool Perm>
620 if ((x0[0].
max() < y0[0].
min()) || (y0[0].
max() < x0[0].
min()))
629 for (
int i=n;
i--; ) {