37namespace 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);
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>
341 reachable(
p.reachable) {
348 template<
class View,
bool Perm>
352 Propagator(home),
x(x0),
y(y0),
z(z0), w(home,y0), reachable(-1) {
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))
430 reachable = w[dropfst - 1].max();
431 bool unreachable =
true;
432 for (
int i =
x.size(); unreachable && i-- ; ) {
433 unreachable &= (reachable <
x[i].min());
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++) {
560 z[i].size() == 2 &&
z[i].
range()) {
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--; ) {
int p
Number of positive literals for node type.
int n
Number of negative literals for node type.
Base-class for both propagators and branchers.
virtual size_t dispose(Space &home)
Delete actor and return its size.
Home class for posting propagators
Bounds consistent distinct propagator.
Binary bounds consistent equality 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.
Bounds consistent sortedness propagator.
virtual ExecStatus propagate(Space &home, const ModEventDelta &med)
Perform propagation.
ViewArray< View > w
Original y array.
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.
int size(void) const
Return size of array (number of elements)
ExecStatus ES_SUBSUMED(Propagator &p)
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.