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