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);
92 for (
int i=0;
i<
n;
i++)
95 for (
int i=0;
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++) {
118 for (
int j=
n; j--;) {
122 }
else if (
y[j].
min() <=
max &&
min <=
y[j].max()) {
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);
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))
208 sort_tau<View,Perm>(
x,
z,tau);
224 for (
int i=0;
i<
x.size();
i++) {
226 phiprime[
i] = phi[
i];
230 for (
int i =
n;
i--; )
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;
289 if (!narrow_domx<View,Perm>(home,
x,
y,
z,tau,phi,scclist,sinfo,nofix))
295 (home, tau, sinfo, scclist,
x,
z, repairpass, nofix))
306 sort_tau<View,Perm>(
x,
z,tau);
312 for (
int i =
x.size() - 1;
i--; ) {
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;
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))
430 reachable = w[dropfst - 1].max();
431 bool unreachable =
true;
432 for (
int i =
x.size(); unreachable &&
i-- ; ) {
433 unreachable &= (reachable <
x[
i].min());
448 if (
x[0].
max() <
y[0].min() ||
y[0].max() <
x[0].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--; ) {
535 sort_tau<View,Perm>(
x,
z,tau);
538 bool xbassigned =
true;
539 for (
int i =
x.size();
i--; ) {
552 sort_sigma<View,Perm>(
x,
z);
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++) {
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--; ) {
void range(Home home, const IntVarArgs &x, SetVar y, SetVar z)
Post constraint .
int p
Number of positive literals for node type.
int n
Number of negative literals for node type.
Node * x
Pointer to corresponding Boolean expression node.
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.
ViewArray< View > w
Original y array.
ViewArray< View > x
Views to be sorted.
ViewArray< View > y
Views denoting the sorted version of x.
ViewArray< View > z
Permutation variables (none, if Perm is false)
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)
@ 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.
int ModEvent
Type for modification events.
void sequence(Home home, const IntVarArgs &x, const IntSet &s, int q, int l, int u, IntPropLevel)
Post propagator for .
Post propagator for SetVar SetOpType SetVar SetRelType SetVar z
Post propagator for SetVar SetOpType SetVar y
void post(Home home, Term *t, int n, FloatRelType frt, FloatVal c)
Post propagator for linear constraint over floats.
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.
const FloatNum max
Largest allowed float value.
bool valid(const FloatVal &n)
Return whether float n is a valid number.
const FloatNum min
Smallest allowed float value.
void reschedule(Space &home, Propagator &p, IntSet &y)
ExecStatus subsumed(Space &home, Propagator &p, int c, TaskArray< Task > &t)
Check for subsumption (all tasks must be assigned)
bool assigned(View x, int v)
Whether x is assigned to value v.
bool narrow_domy(Space &home, ViewArray< View > &x, ViewArray< View > &y, int phi[], int phiprime[], bool &nofix)
Narrowing the domains of the y views.
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.
void computesccs(ViewArray< View > &x, ViewArray< View > &y, int phi[], SccComponent sinfo[], int scclist[])
Compute the sccs of the oriented intersection-graph.
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.
const Gecode::PropCond PC_INT_BND
Propagate when minimum or maximum of a view changes.
unsigned int size(I &i)
Size of all ranges of range iterator i.
Gecode::IntArgs i({1, 2, 3, 4})