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);
92 for (
int i=0; i<n; i++)
95 for (
int i=0; i<n; i++)
106 allbnd[i].
min = allbnd[i].
max = -1;
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++) {
118 for (
int j=n; j--;) {
129 for (
int i=0; i<n; i++) {
131 int minr = allbnd[i].
min;
133 int maxr = allbnd[i].
max;
141 me =
x[i].lq(home,
y[maxr].
max());
146 me =
z[i].gq(home, minr);
151 me =
z[i].lq(home, maxr);
190 bool subsumed =
true;
191 bool array_subs =
false;
193 bool noperm_bc =
false;
199 if (subsumed || array_subs)
224 for (
int i=0; i<
x.size(); i++) {
226 phiprime[i] = phi[i];
230 for (
int i = n; i--; )
231 if (!
y[i].assigned()) {
240 if (nofix && !match_fixed) {
243 for (
int j =
y.size(); j--; )
244 phi[j]=phiprime[j]=0;
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;
295 (home, tau, sinfo, scclist,
x,
z, repairpass, nofix))
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>
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;
397 bool subsumed =
false;
398 bool array_subs =
false;
399 bool match_fixed =
false;
408 bool noperm_bc =
false;
410 (home,
x,
y,
z, array_subs, match_fixed, nofix, noperm_bc))
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--; ) {
538 bool xbassigned =
true;
539 for (
int i =
x.size(); i--; ) {
540 if (
x[tau[i]].assigned() && xbassigned) {
555 for (
int i = 0; i <
x.size() - 1; i++) {
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++) {
580 if (
x[i].assigned() && xassigned) {
590 int tlb = std::min(
x[0].
min(),
y[0].
min());
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);
611 (home,
x,
y,
z, array_subs, match_fixed, nofix, noperm_bc))
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--; ) {
virtual size_t dispose(Space &home)
Delete actor and return its size.
Home class for posting propagators
static ExecStatus post(Home home, ViewArray< View > &x)
Post propagator for view array x.
static ExecStatus post(Home home, View0 x0, View1 x1)
Post bounds consistent propagator .
Item used to construct the OfflineMin sequence.
Storage class for mininmum and maximum of a variable.
int max
stores the mininmum of a variable
int min
stores the mininmum of a variable
Representation of a strongly connected component.
virtual ExecStatus propagate(Space &home, const ModEventDelta &med)
Perform propagation.
ViewArray< View > w
Original y array.
int reachable
connection to dropped view
virtual void reschedule(Space &home)
Schedule function.
static ExecStatus post(Home home, ViewArray< View > &x, ViewArray< View > &y, ViewArray< View > &z)
Post propagator for views x, y, and z.
ViewArray< View > x
Views to be sorted.
virtual PropCost cost(const Space &home, const ModEventDelta &med) const
Cost function returning low linear.
ViewArray< View > y
Views denoting the sorted version of x.
virtual size_t dispose(Space &home)
Delete propagator and return its size.
ViewArray< View > z
Permutation variables (none, if Perm is false)
Sorted(Home home, ViewArray< View > &x, ViewArray< View > &y, ViewArray< View > &z)
Constructor for posting.
virtual Actor * copy(Space &home)
Copy propagator during cloning.
static PropCost linear(PropCost::Mod m, unsigned int n)
Linear complexity for modifier pcm and size measure n.
Base-class for propagators.
size_t size
The size of the propagator (used during subsumption)
Propagator(Home home)
Constructor for posting.
int size(void) const
Return size of array (number of elements)
ExecStatus ES_SUBSUMED(Propagator &p)
Propagator p is subsumed
int ModEventDelta
Modification event deltas.
#define GECODE_ME_CHECK(me)
Check whether modification event me is failed, and forward failure.
#define GECODE_REWRITE(prop, post)
Rewrite propagator by executing post function.
bool me_failed(ModEvent me)
Check whether modification event me is failed.
#define GECODE_ES_CHECK(es)
Check whether execution status es is failed or subsumed, and forward failure or subsumption.
bool me_modified(ModEvent me)
Check whether modification event me describes variable modification.
bool narrow_domy(Space &home, ViewArray< View > &x, ViewArray< View > &y, int phi[], int phiprime[], bool &nofix)
Narrowing the domains of the y views.
void sort_tau(ViewArray< View > &x, ViewArray< View > &z, int tau[])
Build .
bool channel(Space &home, ViewArray< View > &x, ViewArray< View > &y, ViewArray< View > &z, bool &nofix)
Channel between x, y and z.
bool normalize(Space &home, ViewArray< View > &y, ViewArray< View > &x, bool &nofix)
Performing normalization on the views in y.
bool glover(ViewArray< View > &x, ViewArray< View > &y, int tau[], int phi[], OfflineMinItem sequence[], int vertices[])
Glover's maximum matching in a bipartite graph.
bool perm_bc(Space &home, int tau[], SccComponent sinfo[], int scclist[], ViewArray< View > &x, ViewArray< View > &z, bool &crossingedge, bool &nofix)
Bounds consistency on the permutation views.
bool narrow_domx(Space &home, ViewArray< View > &x, ViewArray< View > &y, ViewArray< View > &z, int tau[], int[], int scclist[], SccComponent sinfo[], bool &nofix)
Narrowing the domains of the x variables.
void computesccs(ViewArray< View > &x, ViewArray< View > &y, int phi[], SccComponent sinfo[], int scclist[])
Compute the sccs of the oriented intersection-graph.
bool array_assigned(Space &home, ViewArray< View > &x, ViewArray< View > &y, ViewArray< View > &z, bool &subsumed, bool &match_fixed, bool &, bool &noperm_bc)
Check for assignment of a variable array.
void sort_sigma(ViewArray< View > &x, ViewArray< View > &z)
Build .
bool revglover(ViewArray< View > &x, ViewArray< View > &y, int tau[], int phiprime[], OfflineMinItem sequence[], int vertices[])
Symmetric glover function for the upper domain bounds.
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.
bool check_subsumption(ViewArray< View > &x, ViewArray< View > &y, ViewArray< View > &z, bool &subsumed, int &dropfst)
Subsumption test.
const Gecode::PropCond PC_INT_BND
Propagate when minimum or maximum of a view changes.
Gecode toplevel namespace
Post propagator for SetVar SetOpType SetVar SetRelType r
void sequence(Home home, const IntVarArgs &x, const IntSet &s, int q, int l, int u, IntPropLevel ipl=IPL_DEF)
Post propagator for .
void min(Home home, FloatVar x0, FloatVar x1, FloatVar x2)
Post propagator for .
Post propagator for SetVar SetOpType SetVar SetRelType SetVar z
void range(Home home, const IntVarArgs &x, SetVar y, SetVar z)
Post constraint .
Post propagator for SetVar SetOpType SetVar y
@ ES_OK
Execution is okay.
@ ES_FIX
Propagation has computed fixpoint.
@ ES_FAILED
Execution has resulted in failure.
@ ES_NOFIX
Propagation has not computed fixpoint.
void max(Home home, FloatVar x0, FloatVar x1, FloatVar x2)
Post propagator for .
Post propagator for SetVar x
int ModEvent
Type for modification events.