44 namespace Gecode {
namespace Int {
namespace GCC {
50 bool cf,
bool nolbc) :
52 card_fixed(cf), skip_lbc(nolbc) {
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;
241 if (--hall[z].
d == 0) {
253 if (hall[x0].h > x0) {
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;
359 if (--hall[z].
d == 0) {
365 if (hall[x0].h < x0) {
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) {
473 if (hall[x0].h > x0) {
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;
571 int* z = r.
alloc<
int>(n_z);
575 if (
k[
i].
max() == 0) {
576 z[n_z++] =
k[
i].card();
586 lps.reinit();
ups.reinit();
607 bool all_assigned =
true;
609 for (
int i =
x.
size();
i--; ) {
619 all_assigned =
false;
622 if (!Card::propagate)
627 if (Card::propagate) {
636 if (!card_consistent<Card>(
x,
k))
646 for (
int i =
x.
size();
i--; ) {
657 all_assigned =
false;
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) {
782 for (
int i = k.
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.
PartialSum< Card > lps
Data structure storing the sum of the views lower bounds Necessary for reasoning about the interval c...
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.
PartialSum< Card > ups
Data structure storing the sum of the views upper bounds.
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)
ModEventDelta med
A set of modification events (used during propagation)
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.
void cancel(Space &home, Propagator &p, PropCond pc)
Cancel subscription of propagator p with propagation condition pc to all views.
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.
bool skip_lbc
Stores whether the minium required occurences of the cardinalities are all zero. If so...
int ModEventDelta
Modification event deltas.
Compares two cardinality views according to the index.
Home class for posting propagators
Bounds consistent global cardinality propagator.
bool card_fixed
Stores whether cardinalities are all assigned.
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.