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++) {
116 if ( (y[j].
min() > min) ||
117 (y[j].
min() <= min && min <= y[j].
max()) ) {
122 for (
int j=n; j--;) {
123 if (y[j].
min() > max) {
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;
143 nofix |= (
me_modified(me) && (x[
i].min() != y[minr].min()));
145 me = x[
i].lq(home, y[maxr].
max());
148 nofix |= (
me_modified(me) && (x[
i].min() != y[maxr].max()));
150 me = z[
i].gq(home, minr);
155 me = z[
i].lq(home, maxr);
162 if (!
channel(home,x,y,z,nofix))
182 if (!
channel(home,x,y,z,nofix))
192 sort_sigma<View,Perm>(
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))
203 if (subsumed || array_subs)
204 return home.ES_SUBSUMED(p);
212 sort_tau<View,Perm>(
x,
z,tau);
225 if (!
glover(x,y,tau,phi,sequence,vertices))
228 for (
int i = x.
size();
i--; ) {
230 phiprime[
i] = phi[
i];
234 for (
int i = n;
i--; )
238 !
revglover(x,y,tau,phiprime,sequence,vertices))
244 if (nofix && !match_fixed) {
247 for (
int j = y.size(); j--; )
248 phi[j]=phiprime[j]=0;
250 if (!
glover(x,y,tau,phi,sequence,vertices))
253 if (!
revglover(x,y,tau,phiprime,sequence,vertices))
264 if (!
channel(home,x,y,z,nofix))
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))
304 if (!
channel(home,x,y,z,nofix))
310 sort_tau<View,Perm>(
x,
z,tau);
316 for (
int i = x.
size() - 1;
i--; ) {
318 if (z[tau[
i]].
min() == z[tau[
i+1]].min() &&
319 z[tau[
i]].max() == z[tau[
i+1]].max() &&
320 z[tau[
i]].size() == 2 && z[tau[
i]].range()) {
322 if (x[tau[
i]].
max() < x[tau[
i+1]].max()) {
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) {
352 template<
class View,
bool Perm>
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>(
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>(
x,
z);
425 if (!check_subsumption<View,Perm>(x,
y,
z,subsumed,dropfst))
435 bool unreachable =
true;
436 for (
int i = x.
size(); unreachable &&
i-- ; ) {
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--; ) {
544 if (x[tau[
i]].
assigned() && xbassigned) {
556 sort_sigma<View,Perm>(
x,
z);
559 for (
int i = 0;
i < x.
size() - 1;
i++) {
562 if (z[
i].
min() == z[
i+1].min() &&
563 z[
i].max() == z[
i+1].max() &&
564 z[
i].size() == 2 && z[
i].range()) {
565 if (x[
i].
min() < x[
i+1].min()) {
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--; ) {
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 > w
Original y array.
#define GECODE_REWRITE(prop, post)
Rewrite propagator by executing post function.
virtual size_t dispose(Space &home)
Delete propagator and return its size.
Bounds consistent sortedness propagator.
bool narrow_domy(Space &home, ViewArray< View > &x, ViewArray< View > &y, int phi[], int phiprime[], bool &nofix)
Narrowing the domains of the y views.
Storage class for mininmum and maximum of a variable.
bool valid(const FloatVal &n)
Return whether float n is a valid number.
int size(void) const
Return size of array (number of elements)
static PropCost linear(PropCost::Mod m, unsigned int n)
Linear complexity for modifier pcm and size measure n.
void sequence(Home home, const IntVarArgs &x, const IntSet &s, int q, int l, int u, IntPropLevel)
Post propagator for .
ExecStatus ES_SUBSUMED(Propagator &p)
const FloatNum max
Largest allowed float value.
Sorted(Home home, ViewArray< View > &x, ViewArray< View > &y, ViewArray< View > &z)
Constructor for posting.
ExecStatus subsumed(Space &home, Propagator &p, int c, TaskArray< Task > &t)
Check for subsumption (all tasks must be assigned)
T * alloc(long unsigned int n)
Allocate block of n objects of type T from region.
void max(Home home, FloatVar x0, FloatVar x1, FloatVar x2)
Post propagator for .
virtual Actor * copy(Space &home)
Copy propagator during cloning.
Item used to construct the OfflineMin sequence.
int ModEvent
Type for modification events.
Base-class for propagators.
bool revglover(ViewArray< View > &x, ViewArray< View > &y, int tau[], int phiprime[], OfflineMinItem sequence[], int vertices[])
Symmetric glover function for the upper domain bounds.
virtual PropCost cost(const Space &home, const ModEventDelta &med) const
Cost function returning low linear.
Propagation has computed fixpoint.
bool normalize(Space &home, ViewArray< View > &y, ViewArray< View > &x, bool &nofix)
Performing normalization on the views in y.
int reachable
connection to dropped view
Base-class for both propagators and branchers.
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.
#define GECODE_ES_CHECK(es)
Check whether execution status es is failed or subsumed, and forward failure or subsumption.
bool channel(Space &home, ViewArray< View > &x, ViewArray< View > &y, ViewArray< View > &z, bool &nofix)
Channel between x, y and z.
int p
Number of positive literals for node type.
const FloatNum min
Smallest allowed float value.
Gecode::IntArgs i(4, 1, 2, 3, 4)
int min
stores the mininmum of a variable
int n
Number of negative literals for node type.
Execution has resulted in failure.
const Gecode::PropCond PC_INT_BND
Propagate when minimum or maximum of a view changes.
Binary bounds consistent equality propagator.
Post propagator for SetVar SetOpType SetVar SetRelType SetVar z
ViewArray< View > z
Permutation variables (none, if Perm is false)
#define GECODE_ME_CHECK(me)
Check whether modification event me is failed, and forward failure.
Representation of a strongly connected component.
ViewArray< View > y
Views denoting the sorted version of x.
Post propagator for SetVar SetOpType SetVar SetRelType r
void min(Home home, FloatVar x0, FloatVar x1, FloatVar x2)
Post propagator for .
Post propagator for SetVar SetOpType SetVar y
static ExecStatus post(Home home, ViewArray< View > &x, ViewArray< View > &y, ViewArray< View > &z)
Post propagator for views x, y, and z.
virtual ExecStatus propagate(Space &home, const ModEventDelta &med)
Perform propagation.
virtual size_t dispose(Space &home)
Delete actor and return its size.
bool assigned(View x, int v)
Whether x is assigned to value v.
int max
stores the mininmum of a variable
ViewArray< View > x
Views to be sorted.
bool me_modified(ModEvent me)
Check whether modification event me describes variable modification.
Post propagator for SetVar x
Propagation has not computed fixpoint.
void computesccs(ViewArray< View > &x, ViewArray< View > &y, int phi[], SccComponent sinfo[], int scclist[])
Compute the sccs of the oriented intersection-graph.
Bounds consistent distinct propagator.
Gecode toplevel namespace
int ModEventDelta
Modification event deltas.
int size(void) const
Return size of array (number of elements)
Home class for posting propagators
virtual void reschedule(Space &home)
Schedule function.
bool me_failed(ModEvent me)
Check whether modification event me is failed.