37 namespace Gecode {
namespace Int {
namespace Sorted {
71 template<
class View,
bool Perm>
84 int* tau = r.
alloc<
int>(
n);
85 int* phi = r.
alloc<
int>(
n);
86 int* phiprime = r.
alloc<
int>(
n);
88 int* vertices = r.
alloc<
int>(
n);
95 for (
int i = n;
i--; )
108 for (
int i=n;
i--;) {
109 int min = x[
i].min();
110 int max = x[
i].max();
111 for (
int j=0; j<
n; j++) {
112 if ( (y[j].
min() > min) ||
113 (y[j].
min() <= min && min <= y[j].
max()) ) {
118 for (
int j=n; j--;) {
119 if (y[j].
min() > max) {
122 }
else if (y[j].
min() <= max && min <= y[j].
max()) {
129 for (
int i = n;
i--; ) {
131 int minr = allbnd[
i].
min;
133 int maxr = allbnd[
i].
max;
139 nofix |= (
me_modified(me) && (x[
i].min() != y[minr].min()));
141 me = x[
i].lq(home, y[maxr].
max());
144 nofix |= (
me_modified(me) && (x[
i].min() != y[maxr].max()));
146 me = z[
i].gq(home, minr);
151 me = z[
i].lq(home, maxr);
158 if (!
channel(home,x,y,z,nofix))
178 if (!
channel(home,x,y,z,nofix))
188 sort_sigma<View,Perm>(
x,
z);
191 bool array_subs =
false;
193 bool noperm_bc =
false;
195 if (!check_subsumption<View,Perm>(x,y,z,subsumed,dropfst) ||
196 !array_assigned<View,Perm>(home,
x,
y,
z,array_subs,match_fixed,nofix,noperm_bc))
199 if (subsumed || array_subs)
200 return home.ES_SUBSUMED(p);
208 sort_tau<View,Perm>(
x,
z,tau);
221 if (!
glover(x,y,tau,phi,sequence,vertices))
224 for (
int i = x.
size();
i--; ) {
226 phiprime[
i] = phi[
i];
230 for (
int i = n;
i--; )
234 !
revglover(x,y,tau,phiprime,sequence,vertices))
240 if (nofix && !match_fixed) {
243 for (
int j = y.size(); j--; )
244 phi[j]=phiprime[j]=0;
246 if (!
glover(x,y,tau,phi,sequence,vertices))
249 if (!
revglover(x,y,tau,phiprime,sequence,vertices))
260 if (!
channel(home,x,y,z,nofix))
274 int* scclist = r.
alloc<
int>(
n);
277 for(
int i = n;
i--; )
278 sinfo[
i].left=sinfo[
i].right=sinfo[
i].rightmost=sinfo[
i].leftmost=
i;
289 if (!narrow_domx<View,Perm>(home,x,y,z,tau,phi,scclist,sinfo,nofix))
295 (home, tau, sinfo, scclist, x,z, repairpass, nofix))
300 if (!
channel(home,x,y,z,nofix))
306 sort_tau<View,Perm>(
x,
z,tau);
312 for (
int i = x.
size() - 1;
i--; ) {
314 if (z[tau[
i]].
min() == z[tau[
i+1]].min() &&
315 z[tau[
i]].max() == z[tau[
i+1]].max() &&
316 z[tau[
i]].size() == 2 && z[tau[
i]].range()) {
318 if (x[tau[
i]].
max() < x[tau[
i+1]].max()) {
323 y[z[tau[
i]].min()].max() != x[tau[
i]].max());
325 me = y[z[tau[
i+1]].max()].lq(home, x[tau[
i+1]].
max());
329 y[z[tau[
i+1]].max()].max() != x[tau[
i+1]].max());
337 template<
class View,
bool Perm>
341 reachable(p.reachable) {
348 template<
class View,
bool Perm>
359 template<
class View,
bool Perm>
367 return sizeof(*this);
370 template<
class View,
bool Perm>
375 template<
class View,
bool Perm>
380 template<
class View,
bool Perm>
389 template<
class View,
bool Perm>
393 bool secondpass =
false;
398 bool array_subs =
false;
399 bool match_fixed =
false;
406 sort_sigma<View,Perm>(
x,
z);
408 bool noperm_bc =
false;
409 if (!array_assigned<View,Perm>
410 (home, x,
y,
z, array_subs, match_fixed, nofix, noperm_bc))
416 sort_sigma<View,Perm>(
x,
z);
421 if (!check_subsumption<View,Perm>(x,
y,
z,subsumed,dropfst))
431 bool unreachable =
true;
432 for (
int i = x.
size(); unreachable &&
i-- ; ) {
463 for (
int i = n;
i--; ){
464 if (
z[
i].
max() > index)
467 shift = index -
valid;
473 for (
int i = n;
i--; ) {
482 (home,*
this,ox,oy,oz,secondpass,nofix,match_fixed)));
486 (home,*
this,ox,oy,oz,secondpass,nofix,match_fixed)));
490 (home,*
this,x,
y,
z,secondpass,nofix,match_fixed)));
494 (home,*
this,x,
y,
z,secondpass,nofix,match_fixed)));
513 (home, *
this, x,
y,
z,secondpass, nofix, match_fixed)));
521 int* tau = r.
alloc<
int>(
n);
525 for (
int i = x.
size();
i--; ) {
530 for (
int i = n;
i--; ) {
535 sort_tau<View,Perm>(
x,
z,tau);
538 bool xbassigned =
true;
539 for (
int i = x.
size();
i--; ) {
540 if (x[tau[
i]].
assigned() && xbassigned) {
552 sort_sigma<View,Perm>(
x,
z);
555 for (
int i = 0;
i < x.
size() - 1;
i++) {
558 if (z[
i].
min() == z[
i+1].min() &&
559 z[
i].max() == z[
i+1].max() &&
560 z[
i].size() == 2 && z[
i].range()) {
561 if (x[
i].
min() < x[
i+1].min()) {
565 y[z[
i].min()].min() != x[
i].min());
567 me =
y[z[
i+1].max()].gq(home, x[
i+1].
min());
570 y[z[
i+1].max()].min() != x[
i+1].min());
578 bool xassigned =
true;
579 for (
int i = 0;
i < x.
size();
i++) {
591 int tub =
std::max(x[x.size() - 1].max(),
y[
y.size() - 1].max());
592 for (
int i = x.
size();
i--; ) {
597 me =
y[
i].gq(home, tlb);
601 me = x[
i].lq(home, tub);
605 me = x[
i].gq(home, tlb);
610 if (!array_assigned<View,Perm>
611 (home, x,
y, z, array_subs, match_fixed, nofix, noperm_bc))
617 if (!check_subsumption<View,Perm>(x,
y,z,subsumed,dropfst))
626 template<
class View,
bool Perm>
633 if ((x0[0].
max() < y0[0].
min()) || (y0[0].
max() < x0[0].
min()))
642 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.
virtual size_t dispose(Space &home)
Delete propagator and return its size.
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.
int size(void) const
Return size of array (number of elements)
static PropCost linear(PropCost::Mod m, unsigned int n)
Linear complexity for modifier pcm and size measure n.
void sequence(Home home, const IntVarArgs &x, const IntSet &s, int q, int l, int u, IntPropLevel)
Post propagator for .
ExecStatus ES_SUBSUMED(Propagator &p)
const FloatNum max
Largest allowed float value.
Sorted(Home home, ViewArray< View > &x, ViewArray< View > &y, ViewArray< View > &z)
Constructor for posting.
ExecStatus subsumed(Space &home, Propagator &p, int c, TaskArray< Task > &t)
Check for subsumption (all tasks must be assigned)
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 .
virtual Actor * copy(Space &home)
Copy propagator during cloning.
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.
virtual PropCost cost(const Space &home, const ModEventDelta &med) const
Cost function returning low linear.
Propagation has computed fixpoint.
bool normalize(Space &home, ViewArray< View > &y, ViewArray< View > &x, bool &nofix)
Performing normalization on the views in y.
int reachable
connection to dropped view
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.
#define GECODE_ES_CHECK(es)
Check whether execution status es is failed or subsumed, and forward failure or subsumption.
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.
Post propagator for SetVar SetOpType SetVar SetRelType SetVar z
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.
Post propagator for SetVar SetOpType SetVar SetRelType r
void min(Home home, FloatVar x0, FloatVar x1, FloatVar x2)
Post propagator for .
Post propagator for SetVar SetOpType SetVar y
static ExecStatus post(Home home, ViewArray< View > &x, ViewArray< View > &y, ViewArray< View > &z)
Post propagator for views x, y, and z.
virtual ExecStatus propagate(Space &home, const ModEventDelta &med)
Perform propagation.
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.
Post propagator for SetVar x
Propagation has not computed fixpoint.
void computesccs(ViewArray< View > &x, ViewArray< View > &y, int phi[], SccComponent sinfo[], int scclist[])
Compute the sccs of the oriented intersection-graph.
Bounds consistent distinct propagator.
Gecode toplevel namespace
int ModEventDelta
Modification event deltas.
int size(void) const
Return size of array (number of elements)
Home class for posting propagators
virtual void reschedule(Space &home)
Schedule function.
bool me_failed(ModEvent me)
Check whether modification event me is failed.