Go to the documentation of this file.
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;
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;
572 for (
int i=k.size();
i--;)
578 int*
z =
r.alloc<
int>(n_z);
581 for (
int i=0;
i<k.size();
i++)
582 if (k[
i].
max() == 0) {
583 z[n_z++] = k[
i].card();
589 for (
int i=
x.size();
i--;) {
593 lps.reinit(); ups.reinit();
610 int*
count =
r.alloc<
int>(k.size());
612 for (
int i = k.size();
i--; )
614 bool all_assigned =
true;
616 for (
int i =
x.size();
i--; ) {
626 all_assigned =
false;
629 if (!Card::propagate)
634 if (Card::propagate) {
637 for (
int i = k.size();
i--; )
643 if (!card_consistent<Card>(
x, k))
650 for (
int i = k.size();
i--; )
653 for (
int i =
x.size();
i--; ) {
664 all_assigned =
false;
671 for (
int i = k.size();
i--; )
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);
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;
753 rank[nu[
i]].min = nb;
755 min =
x[nu[
i]].min();
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) {
781 if (!card_fixed && !skip_lbc)
789 for (
int i = k.size();
i--; )
791 for (
int i =
x.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);
void pathset_h(HallInfo hall[], int start, int end, int to)
Path compression for hall pointer structure.
Post propagator for SetVar x
int t
Critical capacity pointer t represents a predecessor function where denotes the predecessor of i in ...
Post propagator for SetVar SetOpType SetVar y
Compares two indices i, j of two views according to the ascending order of the views upper bounds.
void update(Space &, bool share, ViewArray< View > &a)
Update array to be a clone of array a.
void max(Home home, FloatVar x0, FloatVar x1, FloatVar x2)
Post propagator for .
void subscribe(Space &home, Propagator &p, PropCond pc, bool schedule=true)
Subscribe propagator p with propagation condition pc to variable.
ExecStatus ES_SUBSUMED(Propagator &p)
virtual size_t dispose(Space &home)
Destructor.
static ExecStatus post(Home home, ViewArray< View > &x)
Post propagator for view array x.
int newBound
Bound update.
bool assigned(View x, int v)
Whether x is assigned to value v.
Value iterator for array of integers
Post propagator for SetVar SetOpType SetVar SetRelType SetVar z
Gecode::IntArgs i(4, 1, 2, 3, 4)
int pathmin_h(const HallInfo hall[], int i)
Path minimum for hall pointer structure.
int d
Difference between critical capacities.
const FloatNum min
Smallest allowed float value.
virtual ExecStatus propagate(Space &home, const ModEventDelta &med)
Perform propagation.
static PropCost linear(PropCost::Mod m, unsigned int n)
Linear complexity for modifier pcm and size measure n.
ExecStatus ES_NOFIX_PARTIAL(Propagator &p, const ModEventDelta &med)
Propagator p has not computed partial fixpoint
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...
Base-class for both propagators and branchers.
static PropCost quadratic(PropCost::Mod m, unsigned int n)
Quadratic complexity for modifier m and size measure n.
virtual PropCost cost(const Space &home, const ModEventDelta &med) const
Cost funtion.
bool lookupValue(T &a, int v, int &i)
Return index of v in array a.
ViewArray< IntView > y
Views on which to perform value-propagation (subset of x)
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
Base-class for propagators.
int pathmax_t(const HallInfo hall[], int i)
Path maximum for capacity pointer structure.
#define GECODE_ES_CHECK(es)
Check whether execution status es is failed or subsumed, and forward failure or subsumption.
Home class for posting propagators
int pathmin_t(const HallInfo hall[], int i)
Path minimum for capacity pointer structure.
const Gecode::ModEvent ME_INT_BND
Domain operation has changed the minimum or maximum of the domain.
static ModEvent me(const ModEventDelta &med)
Return modification event for view type in med.
virtual void reschedule(Space &home)
Schedule function.
Post propagator for SetVar SetOpType SetVar SetRelType r
void pathset_ps(HallInfo hall[], int start, int end, int to)
Path compression for potentially stable set structure.
Maps domain bounds to their position in hall[].bounds.
int pathmax_ps(const HallInfo hall[], int i)
Path maximum for potentially stable set pointer structure.
void pathset_t(HallInfo hall[], int start, int end, int to)
Path compression for capacity pointer structure.
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 ...
const Gecode::PropCond PC_INT_BND
Propagate when minimum or maximum of a view changes.
Bnd(Space &home, bool share, Bnd< Card > &p)
Constructor for cloning p.
int bounds
Represents the union of all lower and upper domain bounds.
int ps
Potentially Stable Set pointer.
void pathset_s(HallInfo hall[], int start, int end, int to)
Path compression for stable set structure.
virtual Actor * copy(Space &home, bool share)
Copy propagator during cloning.
ExecStatus pruneCards(Space &home)
Prune cardinality variables with 0 maximum occurrence.
Container class provding information about the Hall structure of the problem variables.
void count(Home home, const IntVarArgs &x, int n, IntRelType irt, int m, IntPropLevel)
Post propagator for .
ViewArray< Card > k
Array containing either fixed cardinalities or CardViews.
ViewArray< IntView > x
Views on which to perform bounds-propagation.
int size(void) const
Return size of array (number of elements)
int pathmax_h(const HallInfo hall[], int i)
Path maximum for hall pointer structure.
#define GECODE_ME_CHECK(me)
Check whether modification event me is failed, and forward failure.
Compares two cardinality views according to the index.
virtual size_t dispose(Space &home)
Delete actor and return its size.
void min(Home home, FloatVar x0, FloatVar x1, FloatVar x2)
Post propagator for .
Bounds consistent global cardinality propagator.
int n
Number of negative literals for node type.
@ ES_FAILED
Execution has resulted in failure.
int med(void) const
Return median of domain (greatest element not greater than the median)
static ExecStatus post(Home home, ViewArray< IntView > &x, ViewArray< Card > &k)
Post propagator for views x and cardinalities k.
int ModEventDelta
Modification event deltas.
@ ES_NOFIX
Propagation has not computed fixpoint.
int pathmax_s(const HallInfo hall[], int i)
Path maximum for stable set pointer structure.
@ ES_OK
Execution is okay.
int p
Number of positive literals for node type.
Compares two indices i, j of two views according to the ascending order of the views lower bounds.