Go to the documentation of this file.
41 namespace Gecode {
namespace Int {
namespace Sorted {
75 template<
class View,
bool Perm>
88 int* tau =
r.alloc<
int>(
n);
89 int* phi =
r.alloc<
int>(
n);
90 int* phiprime =
r.alloc<
int>(
n);
92 int* vertices =
r.alloc<
int>(
n);
99 for (
int i =
n;
i--; )
112 for (
int i=
n;
i--;) {
113 int min =
x[
i].min();
114 int max =
x[
i].max();
115 for (
int j=0; j<
n; j++) {
122 for (
int j=
n; j--;) {
126 }
else if (
y[j].
min() <=
max &&
min <=
y[j].max()) {
133 for (
int i =
n;
i--; ) {
135 int minr = allbnd[
i].
min;
137 int maxr = allbnd[
i].
max;
145 me =
x[
i].lq(home,
y[maxr].
max());
150 me =
z[
i].gq(home, minr);
155 me =
z[
i].lq(home, maxr);
192 sort_sigma<View,Perm>(home,
x,
z);
195 bool array_subs =
false;
197 bool noperm_bc =
false;
199 if (!check_subsumption<View,Perm>(
x,
y,
z,
subsumed,dropfst) ||
200 !array_assigned<View,Perm>(home,
x,
y,
z,array_subs,match_fixed,nofix,noperm_bc))
212 sort_tau<View,Perm>(
x,
z,tau);
228 for (
int i =
x.size();
i--; ) {
230 phiprime[
i] = phi[
i];
234 for (
int i =
n;
i--; )
244 if (nofix && !match_fixed) {
247 for (
int j =
y.size(); j--; )
248 phi[j]=phiprime[j]=0;
278 int* scclist =
r.alloc<
int>(
n);
281 for(
int i =
n;
i--; )
282 sinfo[
i].left=sinfo[
i].right=sinfo[
i].rightmost=sinfo[
i].leftmost=
i;
293 if (!narrow_domx<View,Perm>(home,
x,
y,
z,tau,phi,scclist,sinfo,nofix))
299 (home, tau, sinfo, scclist,
x,
z, repairpass, nofix))
310 sort_tau<View,Perm>(
x,
z,tau);
316 for (
int i =
x.size() - 1;
i--; ) {
327 y[
z[tau[
i]].min()].max() !=
x[tau[
i]].max());
329 me =
y[
z[tau[
i+1]].max()].lq(home,
x[tau[
i+1]].
max());
333 y[
z[tau[
i+1]].max()].max() !=
x[tau[
i+1]].max());
341 template<
class View,
bool Perm>
345 reachable(
p.reachable) {
346 x.update(home, share,
p.x);
347 y.update(home, share,
p.y);
348 z.update(home, share,
p.z);
349 w.update(home, share,
p.w);
352 template<
class View,
bool Perm>
356 Propagator(home),
x(x0),
y(y0),
z(z0), w(home,y0), reachable(-1) {
363 template<
class View,
bool Perm>
371 return sizeof(*this);
374 template<
class View,
bool Perm>
379 template<
class View,
bool Perm>
384 template<
class View,
bool Perm>
393 template<
class View,
bool Perm>
397 bool secondpass =
false;
402 bool array_subs =
false;
403 bool match_fixed =
false;
410 sort_sigma<View,Perm>(home,
x,
z);
412 bool noperm_bc =
false;
413 if (!array_assigned<View,Perm>
414 (home,
x,
y,
z, array_subs, match_fixed, nofix, noperm_bc))
420 sort_sigma<View,Perm>(home,
x,
z);
425 if (!check_subsumption<View,Perm>(
x,
y,
z,
subsumed,dropfst))
434 reachable = w[dropfst - 1].max();
435 bool unreachable =
true;
436 for (
int i =
x.size(); unreachable &&
i-- ; ) {
437 unreachable &= (reachable <
x[
i].min());
452 if (
x[0].
max() <
y[0].min() ||
y[0].max() <
x[0].min())
467 for (
int i =
n;
i--; ){
468 if (
z[
i].
max() > index)
471 shift = index -
valid;
477 for (
int i =
n;
i--; ) {
486 (home,*
this,ox,oy,oz,secondpass,nofix,match_fixed)));
490 (home,*
this,ox,oy,oz,secondpass,nofix,match_fixed)));
494 (home,*
this,
x,
y,
z,secondpass,nofix,match_fixed)));
498 (home,*
this,
x,
y,
z,secondpass,nofix,match_fixed)));
517 (home, *
this,
x,
y,
z,secondpass, nofix, match_fixed)));
525 int* tau =
r.alloc<
int>(
n);
529 for (
int i =
x.size();
i--; ) {
534 for (
int i =
n;
i--; ) {
539 sort_tau<View,Perm>(
x,
z,tau);
542 bool xbassigned =
true;
543 for (
int i =
x.size();
i--; ) {
556 sort_sigma<View,Perm>(home,
x,
z);
559 for (
int i = 0;
i <
x.size() - 1;
i++) {
569 y[
z[
i].min()].min() !=
x[
i].min());
571 me =
y[
z[
i+1].max()].gq(home,
x[
i+1].
min());
574 y[
z[
i+1].max()].min() !=
x[
i+1].min());
582 bool xassigned =
true;
583 for (
int i = 0;
i <
x.size();
i++) {
595 int tub =
std::max(
x[
x.size() - 1].max(),
y[
y.size() - 1].max());
596 for (
int i =
x.size();
i--; ) {
601 me =
y[
i].gq(home, tlb);
605 me =
x[
i].lq(home, tub);
609 me =
x[
i].gq(home, tlb);
614 if (!array_assigned<View,Perm>
615 (home,
x,
y,
z, array_subs, match_fixed, nofix, noperm_bc))
621 if (!check_subsumption<View,Perm>(
x,
y,
z,
subsumed,dropfst))
630 template<
class View,
bool Perm>
637 if ((x0[0].
max() < y0[0].
min()) || (y0[0].
max() < x0[0].
min()))
646 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
Gecode::IntArgs i(4, 1, 2, 3, 4)
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.
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)
void computesccs(Space &home, ViewArray< View > &x, ViewArray< View > &y, int phi[], SccComponent sinfo[], int scclist[])
Compute the sccs of the oriented intersection-graph.
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.
#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.