44 namespace Gecode {
namespace Int {
namespace GCC {
50 bool cf,
bool nolbc) :
52 card_fixed(cf), skip_lbc(nolbc) {
62 card_fixed(p.card_fixed), skip_lbc(p.skip_lbc) {
80 return new (home)
Bnd<Card>(home,share,*
this);
87 int n_k = Card::propagate ? k.size() : 0;
141 int rightmost = nb + 1;
151 for (i = bsize; --
i; ) {
155 hall[
i].
d = lps.sumup(hall[pred].bounds, hall[i].bounds - 1);
162 if (hall[i].
d == 0) {
171 for (i = bsize; i--; ) {
173 if (hall[i].
d == 0) {
193 for (i = 0; i <
n; i++) {
195 int x0 = rank[mu[
i]].
min;
196 int y = rank[mu[
i]].
max;
224 if (hall[z].
d <= lps.sumup(hall[y].
bounds, hall[z].
bounds - 1)) {
241 if (--hall[z].
d == 0) {
253 if (hall[x0].h > x0) {
269 if (hall[z].
d == lps.sumup(hall[y].
bounds, hall[z].
bounds - 1)) {
298 for (i = bsize; --
i;)
312 int x0 = rank[mu[
i]].
min;
313 int y = rank[mu[
i]].
max;
315 if ((hall[x0].s <= x0) || (y > hall[x0].s)) {
317 int m = lps.skipNonNullElementsRight(hall[hall[i].newBound].bounds);
324 for (i = 0; i <= nb; i++) {
325 hall[
i].
d = lps.sumup(hall[i].bounds, hall[i + 1].bounds - 1);
326 if (hall[i].
d == 0) {
336 for (i = 1; i <= nb; i++)
337 if (hall[i - 1].
d == 0) {
348 int x0 = rank[nu[
i]].
max;
349 int y = rank[nu[
i]].
min;
357 if (hall[z].
d > lps.sumup(hall[z].
bounds, hall[y].
bounds - 1)) {
359 if (--hall[z].
d == 0) {
365 if (hall[x0].h < x0) {
373 if (hall[z].
d == lps.sumup(hall[z].
bounds, hall[y].
bounds - 1)) {
388 int x0 = rank[nu[
i]].
min;
389 int y = rank[nu[
i]].
max;
390 if ((hall[x0].s <= x0) || (y > hall[x0].s)) {
391 int m = lps.skipNonNullElementsLeft(hall[hall[i].newBound].bounds - 1);
403 int rightmost = nb + 1;
419 for (
int i = bsize; --
i; ) {
420 hall[
i].
h = hall[
i].
t =
i-1;
421 hall[
i].
d = ups.sumup(hall[
i-1].bounds, hall[
i].bounds - 1);
426 for (
int i = 0;
i <
n;
i++) {
428 int x0 = rank[mu[
i]].
min;
430 int y = rank[mu[
i]].
max;
449 if (--hall[z].
d == 0) {
465 if (hall[z].
d < ups.sumup(hall[y].
bounds, hall[z].
bounds - 1))
473 if (hall[x0].h > x0) {
496 if (hall[z].
d == ups.sumup(hall[y].
bounds, hall[z].
bounds - 1)) {
510 for (
int i = 0;
i < rightmost;
i++) {
511 hall[
i].
h = hall[
i].
t =
i+1;
512 hall[
i].
d = ups.sumup(hall[
i].bounds, hall[
i+1].bounds - 1);
515 for (
int i = n;
i--; ) {
517 int x0 = rank[nu[
i]].
max;
519 int y = rank[nu[
i]].
min;
524 if (--hall[z].
d == 0) {
540 if (hall[x0].h < x0) {
542 int m = hall[w].
bounds - 1;
548 if (hall[z].
d == ups.sumup(hall[z].
bounds, hall[y].
bounds - 1)) {
565 for (
int i=k.
size();
i--;)
571 int* z = r.
alloc<
int>(n_z);
575 if (k[
i].
max() == 0) {
576 z[n_z++] = k[
i].card();
582 for (
int i=
x.size();
i--;) {
586 lps.reinit(); ups.reinit();
605 for (
int i = k.
size();
i--; )
607 bool all_assigned =
true;
609 for (
int i =
x.size();
i--; ) {
619 all_assigned =
false;
622 if (!Card::propagate)
627 if (Card::propagate) {
630 for (
int i = k.
size();
i--; )
636 if (!card_consistent<Card>(
x, k))
643 for (
int i = k.
size();
i--; )
646 for (
int i =
x.size();
i--; ) {
657 all_assigned =
false;
664 for (
int i = k.
size();
i--; )
674 int* mu = r.
alloc<
int>(
n);
675 int* nu = r.
alloc<
int>(
n);
677 for (
int i = n;
i--; )
682 Support::quicksort<int, MaxInc<IntView> >(mu,
n, max_inc);
686 Support::quicksort<int, MinInc<IntView> >(nu,
n, min_inc);
690 Support::quicksort<Card, MinIdx<Card> >(&k[0], k.size(), min_idx);
692 if (!lps.initialized()) {
693 assert (!ups.initialized());
694 lps.init(home, k,
false);
695 ups.init(home, k,
true);
696 }
else if (Card::propagate) {
699 if (lps.check_update_min(k))
700 lps.init(home, k,
false);
701 if (ups.check_update_max(k))
702 ups.init(home, k,
true);
707 assert(lps.minValue() <=
x[nu[0]].min());
724 int min =
x[nu[0]].min();
725 int max =
x[mu[0]].max() + 1;
726 int last = lps.firstValue + 1;
727 hall[0].bounds = last;
741 if (i < n && min < max) {
744 hall[++nb].bounds = last;
746 rank[nu[
i]].min = nb;
748 min =
x[nu[
i]].min();
752 hall[++nb].bounds = last;
754 rank[mu[j]].max = nb;
757 max =
x[mu[j]].max() + 1;
762 int rightmost = nb + 1;
763 hall[rightmost].bounds = ups.lastValue + 1 ;
765 if (Card::propagate) {
767 for (
int i = k.
size();
i--; )
768 if (k[
i].
min() != 0) {
774 if (!card_fixed && !skip_lbc)
782 for (
int i = k.
size();
i--; )
784 for (
int i =
x.size();
i--; )
796 for (
int i = k.
size();
i--; )
808 for (
int i=k.
size();
i--; )
810 cardfix =
false;
break;
813 for (
int i=k.
size();
i--; )
814 if (k[
i].
min() != 0) {
815 nolbc =
false;
break;
820 if (isDistinct<Card>(home,x,k))
823 (void)
new (home)
Bnd<Card>(home,
x,k,cardfix,nolbc);
Bnd(Space &home, bool share, Bnd< Card > &p)
Constructor for cloning p.
int d
Difference between critical capacities.
void update(Space &, bool share, ViewArray< View > &a)
Update array to be a clone of array a.
virtual Actor * copy(Space &home, bool share)
Copy propagator during cloning.
static PropCost quadratic(PropCost::Mod m, unsigned int n)
Quadratic complexity for modifier m and size measure n.
Container class provding information about the Hall structure of the problem variables.
static PropCost linear(PropCost::Mod m, unsigned int n)
Linear complexity for modifier pcm and size measure n.
ExecStatus ES_SUBSUMED(Propagator &p)
int size(void) const
Return size of array (number of elements)
T * alloc(long unsigned int n)
Allocate block of n objects of type T from region.
Value iterator for array of integers
ExecStatus ES_NOFIX_PARTIAL(Propagator &p, const ModEventDelta &med)
Propagator p has not computed partial fixpoint
bool lookupValue(T &a, int v, int &i)
Return index of v in array a.
void pathset_s(HallInfo hall[], int start, int end, int to)
Path compression for stable set structure.
virtual PropCost cost(const Space &home, const ModEventDelta &med) const
Cost funtion.
void max(Home home, FloatVar x0, FloatVar x1, FloatVar x2)
Post propagator for .
void pathset_h(HallInfo hall[], int start, int end, int to)
Path compression for hall pointer structure.
ViewArray< Card > k
Array containing either fixed cardinalities or CardViews.
Base-class for propagators.
int pathmax_t(const HallInfo hall[], int i)
Path maximum for capacity pointer structure.
int pathmin_h(const HallInfo hall[], int i)
Path minimum for hall pointer structure.
int pathmin_t(const HallInfo hall[], int i)
Path minimum for capacity pointer structure.
Base-class for both propagators and branchers.
Compares two indices i, j of two views according to the ascending order of the views lower bounds...
int pathmax_h(const HallInfo hall[], int i)
Path maximum for hall pointer structure.
#define GECODE_ES_CHECK(es)
Check whether execution status es is failed or subsumed, and forward failure or subsumption.
int p
Number of positive literals for node type.
const FloatNum min
Smallest allowed float value.
Gecode::IntArgs i(4, 1, 2, 3, 4)
static ExecStatus post(Home home, ViewArray< View > &x)
Post propagator for view array x.
void quicksort(Type *l, Type *r, Less &less)
Standard quick sort.
int n
Number of negative literals for node type.
int t
Critical capacity pointer t represents a predecessor function where denotes the predecessor of i in ...
Compares two indices i, j of two views according to the ascending order of the views upper bounds...
Execution has resulted in failure.
virtual size_t dispose(Space &home)
Destructor.
void subscribe(Space &home, Propagator &p, PropCond pc, bool process=true)
Subscribe propagator p with propagation condition pc to variable.
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)
int pathmax_ps(const HallInfo hall[], int i)
Path maximum for potentially stable set pointer structure.
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 occ...
const Gecode::ModEvent ME_INT_BND
Domain operation has changed the minimum or maximum of the domain.
static ExecStatus post(Home home, ViewArray< IntView > &x, ViewArray< Card > &k)
Post propagator for views x and cardinalities k.
ExecStatus pruneCards(Space &home)
Prune cardinality variables with 0 maximum occurrence.
#define GECODE_ME_CHECK(me)
Check whether modification event me is failed, and forward failure.
int bounds
Represents the union of all lower and upper domain bounds.
void pathset_t(HallInfo hall[], int start, int end, int to)
Path compression for capacity pointer structure.
void min(Home home, FloatVar x0, FloatVar x1, FloatVar x2)
Post propagator for .
int newBound
Bound update.
Maps domain bounds to their position in hall[].bounds.
Node * x
Pointer to corresponding Boolean expression node.
void count(Home home, const IntVarArgs &x, int n, IntRelType irt, int m, IntConLevel)
Post propagator for .
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.
static ModEvent me(const ModEventDelta &med)
Return modification event for view type in med.
int pathmax_s(const HallInfo hall[], int i)
Path maximum for stable set pointer structure.
int med(void) const
Return median of domain (greatest element not greater than the median)
Propagation has not computed fixpoint.
ViewArray< IntView > y
Views on which to perform value-propagation (subset of x)
int size(void) const
Return size of array (number of elements)
int ps
Potentially Stable Set pointer.
Gecode toplevel namespace
virtual ExecStatus propagate(Space &home, const ModEventDelta &med)
Perform propagation.
ViewArray< IntView > x
Views on which to perform bounds-propagation.
int ModEventDelta
Modification event deltas.
Compares two cardinality views according to the index.
Home class for posting propagators
Bounds consistent global cardinality propagator.
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 ...
void pathset_ps(HallInfo hall[], int start, int end, int to)
Path compression for potentially stable set structure.