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--; ) {
bool glover(ViewArray< View > &x, ViewArray< View > &y, int tau[], int phi[], OfflineMinItem sequence[], int vertices[])
Glover's maximum matching in a bipartite graph.
ViewArray< View > w
Original y array.
#define GECODE_REWRITE(prop, post)
Rewrite propagator by executing post function.
Bounds consistent sortedness propagator.
bool narrow_domy(Space &home, ViewArray< View > &x, ViewArray< View > &y, int phi[], int phiprime[], bool &nofix)
Narrowing the domains of the y views.
Storage class for mininmum and maximum of a variable.
bool valid(const FloatVal &n)
Return whether float n is a valid number.
void post(Home home, Term *t, int n, FloatRelType frt, FloatVal c)
Post propagator for linear constraint over floats.
static PropCost linear(PropCost::Mod m, unsigned int n)
Linear complexity for modifier pcm and size measure n.
const FloatNum max
Largest allowed float value.
int size(void) const
Return size of array (number of elements)
T * alloc(long unsigned int n)
Allocate block of n objects of type T from region.
void max(Home home, FloatVar x0, FloatVar x1, FloatVar x2)
Post propagator for .
Item used to construct the OfflineMin sequence.
int ModEvent
Type for modification events.
Base-class for propagators.
bool revglover(ViewArray< View > &x, ViewArray< View > &y, int tau[], int phiprime[], OfflineMinItem sequence[], int vertices[])
Symmetric glover function for the upper domain bounds.
Propagation has computed fixpoint.
bool normalize(Space &home, ViewArray< View > &y, ViewArray< View > &x, bool &nofix)
Performing normalization on the views in y.
Base-class for both propagators and branchers.
ExecStatus bounds_propagation(Space &home, Propagator &p, ViewArray< View > &x, ViewArray< View > &y, ViewArray< View > &z, bool &repairpass, bool &nofix, bool &match_fixed)
Perform bounds consistent sortedness propagation.
void sequence(Home home, const IntVarArgs &x, const IntSet &s, int q, int l, int u, IntConLevel)
Post propagator for .
#define GECODE_ES_CHECK(es)
Check whether execution status es is failed or subsumed, and forward failure or subsumption.
void computesccs(Space &home, ViewArray< View > &x, ViewArray< View > &y, int phi[], SccComponent sinfo[], int scclist[])
Compute the sccs of the oriented intersection-graph.
bool channel(Space &home, ViewArray< View > &x, ViewArray< View > &y, ViewArray< View > &z, bool &nofix)
Channel between x, y and z.
int p
Number of positive literals for node type.
const FloatNum min
Smallest allowed float value.
Gecode::IntArgs i(4, 1, 2, 3, 4)
int min
stores the mininmum of a variable
int n
Number of negative literals for node type.
Execution has resulted in failure.
const Gecode::PropCond PC_INT_BND
Propagate when minimum or maximum of a view changes.
Binary bounds consistent equality propagator.
ViewArray< View > z
Permutation variables (none, if Perm is false)
#define GECODE_ME_CHECK(me)
Check whether modification event me is failed, and forward failure.
Representation of a strongly connected component.
ViewArray< View > y
Views denoting the sorted version of x.
void min(Home home, FloatVar x0, FloatVar x1, FloatVar x2)
Post propagator for .
ExecStatus subsumed(Space &home, Propagator &p, TaskArray< Task > &t)
Check tasks t for subsumption.
Node * x
Pointer to corresponding Boolean expression node.
virtual size_t dispose(Space &home)
Delete actor and return its size.
bool assigned(View x, int v)
Whether x is assigned to value v.
int max
stores the mininmum of a variable
ViewArray< View > x
Views to be sorted.
bool me_modified(ModEvent me)
Check whether modification event me describes variable modification.
Propagation has not computed fixpoint.
int size(void) const
Return size of array (number of elements)
Bounds consistent distinct propagator.
Gecode toplevel namespace
int ModEventDelta
Modification event deltas.
Home class for posting propagators
bool me_failed(ModEvent me)
Check whether modification event me is failed.