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--;) {
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--; ) {
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;
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());
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++) {
558 if (
z[
i].
min() ==
z[
i+1].min() &&
559 z[
i].max() ==
z[
i+1].max() &&
560 z[
i].size() == 2 &&
z[
i].range()) {
561 if (
x[
i].
min() <
x[
i+1].min()) {
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.
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.
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.
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.
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.
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.
int p
Number of positive literals for node type.
const FloatNum max
Largest allowed float value.
Bounds consistent sortedness propagator.