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;
148 int rightmost = nb + 1;
158 for (i = bsize; --
i; ) {
162 hall[
i].
d =
lps.sumup(hall[pred].bounds, hall[i].bounds - 1);
169 if (hall[i].
d == 0) {
178 for (i = bsize; i--; ) {
180 if (hall[i].
d == 0) {
200 for (i = 0; i <
n; i++) {
202 int x0 = rank[mu[
i]].
min;
203 int y = rank[mu[
i]].
max;
248 if (--hall[z].
d == 0) {
260 if (hall[x0].h > x0) {
305 for (i = bsize; --
i;)
319 int x0 = rank[mu[
i]].
min;
320 int y = rank[mu[
i]].
max;
322 if ((hall[x0].s <= x0) || (y > hall[x0].s)) {
324 int m =
lps.skipNonNullElementsRight(hall[hall[i].newBound].bounds);
331 for (i = 0; i <= nb; i++) {
332 hall[
i].
d =
lps.sumup(hall[i].bounds, hall[i + 1].bounds - 1);
333 if (hall[i].
d == 0) {
343 for (i = 1; i <= nb; i++)
344 if (hall[i - 1].
d == 0) {
355 int x0 = rank[nu[
i]].
max;
356 int y = rank[nu[
i]].
min;
366 if (--hall[z].
d == 0) {
372 if (hall[x0].h < x0) {
395 int x0 = rank[nu[
i]].
min;
396 int y = rank[nu[
i]].
max;
397 if ((hall[x0].s <= x0) || (y > hall[x0].s)) {
398 int m =
lps.skipNonNullElementsLeft(hall[hall[i].newBound].bounds - 1);
410 int rightmost = nb + 1;
426 for (
int i = bsize; --
i; ) {
427 hall[
i].
h = hall[
i].
t =
i-1;
428 hall[
i].
d =
ups.sumup(hall[
i-1].bounds, hall[
i].bounds - 1);
433 for (
int i = 0;
i <
n;
i++) {
435 int x0 = rank[mu[
i]].
min;
437 int y = rank[mu[
i]].
max;
456 if (--hall[z].
d == 0) {
480 if (hall[x0].h > x0) {
517 for (
int i = 0;
i < rightmost;
i++) {
518 hall[
i].
h = hall[
i].
t =
i+1;
519 hall[
i].
d =
ups.sumup(hall[
i].bounds, hall[
i+1].bounds - 1);
522 for (
int i = n;
i--; ) {
524 int x0 = rank[nu[
i]].
max;
526 int y = rank[nu[
i]].
min;
531 if (--hall[z].
d == 0) {
547 if (hall[x0].h < x0) {
549 int m = hall[w].
bounds - 1;
578 int* z = r.
alloc<
int>(n_z);
582 if (
k[
i].
max() == 0) {
583 z[n_z++] =
k[
i].card();
593 lps.reinit();
ups.reinit();
614 bool all_assigned =
true;
616 for (
int i =
x.
size();
i--; ) {
626 all_assigned =
false;
629 if (!Card::propagate)
634 if (Card::propagate) {
643 if (!card_consistent<Card>(
x,
k))
653 for (
int i =
x.
size();
i--; ) {
664 all_assigned =
false;
681 int* mu = r.
alloc<
int>(
n);
682 int* nu = r.
alloc<
int>(
n);
684 for (
int i = n;
i--; )
689 Support::quicksort<int, MaxInc<IntView> >(mu,
n, max_inc);
693 Support::quicksort<int, MinInc<IntView> >(nu,
n, min_inc);
697 Support::quicksort<Card, MinIdx<Card> >(&
k[0], k.
size(), min_idx);
699 if (!
lps.initialized()) {
700 assert (!
ups.initialized());
701 lps.init(home, k,
false);
702 ups.init(home, k,
true);
703 }
else if (Card::propagate) {
706 if (
lps.check_update_min(k))
707 lps.init(home, k,
false);
708 if (
ups.check_update_max(k))
709 ups.init(home, k,
true);
714 assert(
lps.minValue() <=
x[nu[0]].min());
731 int min =
x[nu[0]].min();
732 int max =
x[mu[0]].max() + 1;
733 int last =
lps.firstValue + 1;
734 hall[0].bounds = last;
748 if (i < n && min < max) {
751 hall[++nb].bounds = last;
753 rank[nu[
i]].min = nb;
755 min =
x[nu[
i]].min();
759 hall[++nb].bounds = last;
761 rank[mu[j]].max = nb;
764 max =
x[mu[j]].max() + 1;
769 int rightmost = nb + 1;
770 hall[rightmost].bounds =
ups.lastValue + 1 ;
772 if (Card::propagate) {
774 for (
int i = k.
size();
i--; )
775 if (k[
i].
min() != 0) {
789 for (
int i = k.
size();
i--; )
803 for (
int i = k.
size();
i--; )
815 for (
int i=k.
size();
i--; )
817 cardfix =
false;
break;
820 for (
int i=k.
size();
i--; )
821 if (k[
i].
min() != 0) {
822 nolbc =
false;
break;
827 if (isDistinct<Card>(home,x,k))
830 (void)
new (home)
Bnd<Card>(home,
x,
k,cardfix,nolbc);
virtual PropCost cost(const Space &home, const ModEventDelta &med) const
Cost funtion.
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.
void reschedule(Space &home, Propagator &p, PropCond pc)
Re-schedule propagator p with propagation condition pc.
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.
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.
ExecStatus ES_SUBSUMED(Propagator &p)
void count(Home home, const IntVarArgs &x, int n, IntRelType irt, int m, IntPropLevel)
Post propagator for .
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.
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.
void subscribe(Space &home, Propagator &p, PropCond pc, bool schedule=true)
Subscribe propagator p with propagation condition pc to variable.
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.
int med(void) const
Return median of domain (greatest element not greater than the median)
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.
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.
Propagation has not computed fixpoint.
ViewArray< IntView > y
Views on which to perform value-propagation (subset of x)
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 size(void) const
Return size of array (number of elements)
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.
virtual void reschedule(Space &home)
Schedule function.