46 bool cf,
bool nolbc) :
83 int n_k = Card::propagate ?
k.size() : 0;
144 int rightmost = nb + 1;
154 for (i = bsize; --i; ) {
158 hall[i].
d =
lps.sumup(hall[pred].bounds, hall[i].bounds - 1);
165 if (hall[i].d == 0) {
174 for (i = bsize; i--; ) {
176 if (hall[i].d == 0) {
196 for (i = 0; i < n; i++) {
198 int x0 = rank[mu[i]].
min;
199 int y = rank[mu[i]].
max;
244 if (--hall[
z].d == 0) {
256 if (hall[x0].h > x0) {
301 for (i = bsize; --i;)
315 int x0 = rank[mu[i]].
min;
316 int y = rank[mu[i]].
max;
318 if ((hall[x0].s <= x0) || (
y > hall[x0].s)) {
320 int m =
lps.skipNonNullElementsRight(hall[hall[i].newBound].bounds);
327 for (i = 0; i <= nb; i++) {
328 hall[i].
d =
lps.sumup(hall[i].bounds, hall[i + 1].bounds - 1);
329 if (hall[i].d == 0) {
339 for (i = 1; i <= nb; i++)
340 if (hall[i - 1].d == 0) {
351 int x0 = rank[nu[i]].
max;
352 int y = rank[nu[i]].
min;
362 if (--hall[
z].d == 0) {
368 if (hall[x0].h < x0) {
391 int x0 = rank[nu[i]].
min;
392 int y = rank[nu[i]].
max;
393 if ((hall[x0].s <= x0) || (
y > hall[x0].s)) {
394 int m =
lps.skipNonNullElementsLeft(hall[hall[i].newBound].bounds - 1);
406 int rightmost = nb + 1;
422 for (
int i = bsize; --i; ) {
423 hall[i].
h = hall[i].
t = i-1;
424 hall[i].
d =
ups.sumup(hall[i-1].bounds, hall[i].bounds - 1);
429 for (
int i = 0; i < n; i++) {
431 int x0 = rank[mu[i]].
min;
433 int y = rank[mu[i]].
max;
452 if (--hall[
z].d == 0) {
476 if (hall[x0].h > x0) {
513 for (
int i = 0; i < rightmost; i++) {
514 hall[i].
h = hall[i].
t = i+1;
515 hall[i].
d =
ups.sumup(hall[i].bounds, hall[i+1].bounds - 1);
518 for (
int i = n; i--; ) {
520 int x0 = rank[nu[i]].
max;
522 int y = rank[nu[i]].
min;
527 if (--hall[
z].d == 0) {
543 if (hall[x0].h < x0) {
545 int m = hall[w].
bounds - 1;
568 for (
int i=
k.size(); i--;)
574 int*
z =
r.alloc<
int>(n_z);
577 for (
int i=0; i<
k.size(); i++)
578 if (
k[i].
max() == 0) {
579 z[n_z++] =
k[i].card();
585 for (
int i=
x.size(); i--;) {
589 lps.reinit();
ups.reinit();
606 int*
count =
r.alloc<
int>(
k.size());
608 for (
int i =
k.size(); i--; )
610 bool all_assigned =
true;
612 for (
int i =
x.size(); i--; ) {
613 if (
x[i].assigned()) {
622 all_assigned =
false;
625 if (!Card::propagate)
630 if (Card::propagate) {
633 for (
int i =
k.size(); i--; )
634 if (!
k[i].assigned()) {
646 for (
int i =
k.size(); i--; )
649 for (
int i =
x.size(); i--; ) {
650 if (
x[i].assigned()) {
660 all_assigned =
false;
667 for (
int i =
k.size(); i--; )
677 int* mu =
r.alloc<
int>(n);
678 int* nu =
r.alloc<
int>(n);
680 for (
int i = n; i--; )
697 lps.init(home,
k,
false);
698 ups.init(home,
k,
true);
699 }
else if (Card::propagate) {
702 if (
lps.check_update_min(
k))
703 lps.init(home,
k,
false);
704 if (
ups.check_update_max(
k))
705 ups.init(home,
k,
true);
710 assert(
lps.minValue() <=
x[nu[0]].min());
727 int min =
x[nu[0]].min();
728 int max =
x[mu[0]].max() + 1;
729 int last =
lps.firstValue + 1;
749 rank[nu[i]].min = nb;
751 min =
x[nu[i]].min();
757 rank[mu[j]].max = nb;
760 max =
x[mu[j]].max() + 1;
765 int rightmost = nb + 1;
766 hall[rightmost].
bounds =
ups.lastValue + 1 ;
768 if (Card::propagate) {
770 for (
int i =
k.size(); i--; )
771 if (
k[i].
min() != 0) {
785 for (
int i =
k.size(); i--; )
787 for (
int i =
x.size(); i--; )
788 if (
x[i].assigned()) {
799 for (
int i =
k.size(); i--; )
811 for (
int i=
k.size(); i--; )
812 if (!
k[i].assigned()) {
813 cardfix =
false;
break;
816 for (
int i=
k.size(); i--; )
817 if (
k[i].
min() != 0) {
818 nolbc =
false;
break;
826 (void)
new (home)
Bnd<Card>(home,
x,
k,cardfix,nolbc);
Base-class for both propagators and branchers.
virtual size_t dispose(Space &home)
Delete actor and return its size.
Home class for posting propagators
static ExecStatus post(Home home, ViewArray< View > &x)
Post propagator for view array x.
PartialSum< Card > ups
Data structure storing the sum of the views upper bounds.
Bnd(Space &home, Bnd< Card > &p)
Constructor for cloning p.
bool skip_lbc
Stores whether the minium required occurences of the cardinalities are all zero. If so,...
static ExecStatus post(Home home, ViewArray< IntView > &x, ViewArray< Card > &k)
Post propagator for views x and cardinalities k.
virtual Actor * copy(Space &home)
Copy propagator during cloning.
ViewArray< Card > k
Array containing either fixed cardinalities or CardViews.
ExecStatus ubc(Space &home, int &nb, HallInfo hall[], Rank rank[], int mu[], int nu[])
Upper Bounds constraint (UBC) stating Hence the ubc constraints the variables such that no value oc...
ExecStatus pruneCards(Space &home)
Prune cardinality variables with 0 maximum occurrence.
bool card_fixed
Stores whether cardinalities are all assigned.
ViewArray< IntView > y
Views on which to perform value-propagation (subset of x)
virtual size_t dispose(Space &home)
Destructor.
virtual ExecStatus propagate(Space &home, const ModEventDelta &med)
Perform propagation.
virtual void reschedule(Space &home)
Schedule function.
ViewArray< IntView > x
Views on which to perform bounds-propagation.
PartialSum< Card > lps
Data structure storing the sum of the views lower bounds Necessary for reasoning about the interval c...
virtual PropCost cost(const Space &home, const ModEventDelta &med) const
Cost funtion.
ExecStatus lbc(Space &home, int &nb, HallInfo hall[], Rank rank[], int mu[], int nu[])
Lower Bounds constraint (LBC) stating Hence the lbc constraints the variables such that every value...
Container class provding information about the Hall structure of the problem variables.
int t
Critical capacity pointer t represents a predecessor function where denotes the predecessor of i in ...
int newBound
Bound update.
int bounds
Represents the union of all lower and upper domain bounds.
int ps
Potentially Stable Set pointer.
int d
Difference between critical capacities.
Compares two indices i, j of two views according to the ascending order of the views upper bounds.
Compares two cardinality views according to the index.
Compares two indices i, j of two views according to the ascending order of the views lower bounds.
Maps domain bounds to their position in hall[].bounds.
int med(void) const
Return median of domain (greatest element not greater than the median)
Value iterator for array of integers
static PropCost quadratic(PropCost::Mod m, unsigned int n)
Quadratic complexity for modifier m and size measure n.
static PropCost linear(PropCost::Mod m, unsigned int n)
Linear complexity for modifier pcm and size measure n.
ModEventDelta med
A set of modification events (used during propagation)
Propagator(Home home)
Constructor for posting.
static ModEvent me(const ModEventDelta &med)
bool card_consistent(ViewArray< IntView > &x, ViewArray< Card > &k)
Consistency check, whether the cardinality values are feasible.
ExecStatus prop_card(Space &home, ViewArray< IntView > &x, ViewArray< Card > &k)
Bounds consistency check for cardinality variables.
ExecStatus ES_NOFIX_PARTIAL(Propagator &p, const ModEventDelta &med)
Propagator p has not computed partial fixpoint
ExecStatus ES_SUBSUMED(Propagator &p)
Propagator p is subsumed
int ModEventDelta
Modification event deltas.
#define GECODE_ME_CHECK(me)
Check whether modification event me is failed, and forward failure.
#define GECODE_ES_CHECK(es)
Check whether execution status es is failed or subsumed, and forward failure or subsumption.
Global cardinality propagators (Counting)
int pathmin_h(const HallInfo hall[], int i)
Path minimum for hall pointer structure.
int pathmax_t(const HallInfo hall[], int i)
Path maximum for capacity pointer structure.
void pathset_ps(HallInfo hall[], int start, int end, int to)
Path compression for potentially stable set structure.
bool isDistinct(ViewArray< IntView > &x, ViewArray< Card > &k)
Check if GCC is equivalent to distinct.
int pathmax_s(const HallInfo hall[], int i)
Path maximum for stable set pointer structure.
void pathset_t(HallInfo hall[], int start, int end, int to)
Path compression for capacity pointer structure.
ExecStatus prop_val(Space &home, Propagator &p, ViewArray< IntView > &x, ViewArray< Card > &k)
int pathmin_t(const HallInfo hall[], int i)
Path minimum for capacity pointer structure.
void pathset_h(HallInfo hall[], int start, int end, int to)
Path compression for hall pointer structure.
void pathset_s(HallInfo hall[], int start, int end, int to)
Path compression for stable set structure.
bool lookupValue(T &a, int v, int &i)
Return index of v in array a.
int pathmax_h(const HallInfo hall[], int i)
Path maximum for hall pointer structure.
ExecStatus postSideConstraints(Home home, ViewArray< IntView > &x, ViewArray< Card > &k)
Post side constraints for the GCC.
int pathmax_ps(const HallInfo hall[], int i)
Path maximum for potentially stable set pointer structure.
const Gecode::ModEvent ME_INT_BND
Domain operation has changed the minimum or maximum of the domain.
const Gecode::PropCond PC_INT_BND
Propagate when minimum or maximum of a view changes.
const Gecode::ModEvent ME_INT_VAL
Domain operation has resulted in a value (assigned variable)
void quicksort(Type *l, Type *r, Less &less)
Standard quick sort.
Gecode toplevel namespace
void count(Home home, const IntVarArgs &x, int n, IntRelType irt, int m, IntPropLevel ipl=IPL_DEF)
Post propagator for .
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 SetRelType SetVar z
@ ES_OK
Execution is okay.
@ ES_FAILED
Execution has resulted in failure.
@ ES_NOFIX
Propagation has not computed fixpoint.
void max(Home home, FloatVar x0, FloatVar x1, FloatVar x2)
Post propagator for .