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))
264 if (!
channel(home,x,y,z,nofix))
278 int* scclist = r.
alloc<
int>(
n);
281 for(
int i = n;
i--; )
282 sinfo[
i].left=sinfo[
i].right=sinfo[
i].rightmost=sinfo[
i].leftmost=
i;
293 if (!narrow_domx<View,Perm>(home,x,y,z,tau,phi,scclist,sinfo,nofix))
299 (home, tau, sinfo, scclist, x,z, repairpass, nofix))
304 if (!
channel(home,x,y,z,nofix))
310 sort_tau<View,Perm>(
x,z,tau);
316 for (
int i = x.
size() - 1;
i--; ) {
318 if (z[tau[
i]].
min() == z[tau[
i+1]].min() &&
319 z[tau[
i]].max() == z[tau[
i+1]].max() &&
320 z[tau[
i]].size() == 2 && z[tau[
i]].range()) {
322 if (x[tau[
i]].
max() < x[tau[
i+1]].max()) {
327 y[z[tau[
i]].min()].max() != x[tau[
i]].max());
329 me = y[z[tau[
i+1]].max()].lq(home, x[tau[
i+1]].
max());
333 y[z[tau[
i+1]].max()].max() != x[tau[
i+1]].max());
341 template<
class View,
bool Perm>
345 reachable(p.reachable) {
346 x.update(home, share, p.x);
347 y.update(home, share, p.y);
348 z.update(home, share, p.z);
349 w.update(home, share, p.w);
352 template<
class View,
bool Perm>
356 Propagator(home),
x(x0), y(y0), z(z0), w(home,y0), reachable(-1) {
363 template<
class View,
bool Perm>
371 return sizeof(*this);
374 template<
class View,
bool Perm>
379 template<
class View,
bool Perm>
384 template<
class View,
bool Perm>
388 bool secondpass =
false;
393 bool array_subs =
false;
394 bool match_fixed =
false;
401 sort_sigma<View,Perm>(home,
x,z);
403 bool noperm_bc =
false;
404 if (!array_assigned<View,Perm>
405 (home, x, y, z, array_subs, match_fixed, nofix, noperm_bc))
409 return home.ES_SUBSUMED(*
this);
411 sort_sigma<View,Perm>(home,
x,z);
416 if (!check_subsumption<View,Perm>(x,y,z,subsumed,dropfst))
420 return home.ES_SUBSUMED(*
this);
425 reachable = w[dropfst - 1].max();
426 bool unreachable =
true;
427 for (
int i = x.
size(); unreachable &&
i-- ; ) {
428 unreachable &= (reachable < x[
i].min());
458 for (
int i = n;
i--; ){
459 if (z[
i].
max() > index)
462 shift = index -
valid;
468 for (
int i = n;
i--; ) {
477 (home,*
this,ox,oy,oz,secondpass,nofix,match_fixed)));
481 (home,*
this,ox,oy,oz,secondpass,nofix,match_fixed)));
485 (home,*
this,x,y,z,secondpass,nofix,match_fixed)));
489 (home,*
this,x,y,z,secondpass,nofix,match_fixed)));
508 (home, *
this, x, y, z,secondpass, nofix, match_fixed)));
516 int* tau = r.
alloc<
int>(
n);
520 for (
int i = x.
size();
i--; ) {
525 for (
int i = n;
i--; ) {
530 sort_tau<View,Perm>(
x,z,tau);
533 bool xbassigned =
true;
534 for (
int i = x.
size();
i--; ) {
535 if (x[tau[
i]].
assigned() && xbassigned) {
547 sort_sigma<View,Perm>(home,
x,z);
550 for (
int i = 0;
i < x.
size() - 1;
i++) {
553 if (z[
i].
min() == z[
i+1].min() &&
554 z[
i].max() == z[
i+1].max() &&
555 z[
i].size() == 2 && z[
i].range()) {
556 if (x[
i].
min() < x[
i+1].min()) {
560 y[z[
i].min()].min() != x[
i].min());
562 me = y[z[
i+1].max()].gq(home, x[
i+1].
min());
565 y[z[
i+1].max()].min() != x[
i+1].min());
573 bool xassigned =
true;
574 for (
int i = 0;
i < x.
size();
i++) {
586 int tub =
std::max(x[x.size() - 1].max(), y[y.size() - 1].max());
587 for (
int i = x.
size();
i--; ) {
592 me = y[
i].gq(home, tlb);
596 me = x[
i].lq(home, tub);
600 me = x[
i].gq(home, tlb);
605 if (!array_assigned<View,Perm>
606 (home, x, y, z, array_subs, match_fixed, nofix, noperm_bc))
610 return home.ES_SUBSUMED(*
this);
612 if (!check_subsumption<View,Perm>(x,y,z,subsumed,dropfst))
616 return home.ES_SUBSUMED(*
this);
621 template<
class View,
bool Perm>
628 if ((x0[0].
max() < y0[0].
min()) || (y0[0].
max() < x0[0].
min()))
637 for (
int i=n;
i--; ) {