Go to the documentation of this file.
40 namespace Gecode {
namespace Int {
namespace GCC {
46 bool cf,
bool nolbc) :
48 card_fixed(cf), skip_lbc(nolbc) {
58 card_fixed(
p.card_fixed), skip_lbc(
p.skip_lbc) {
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);
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--; ) {
622 all_assigned =
false;
625 if (!Card::propagate)
630 if (Card::propagate) {
633 for (
int i = k.
size();
i--; )
639 if (!card_consistent<Card>(
x, k))
646 for (
int i = k.
size();
i--; )
649 for (
int i =
x.size();
i--; ) {
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--; )
685 Support::quicksort<int, MaxInc<IntView> >(mu,
n, max_inc);
689 Support::quicksort<int, MinInc<IntView> >(nu,
n, min_inc);
693 Support::quicksort<Card, MinIdx<Card> >(&k[0], k.size(), min_idx);
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;
730 hall[0].bounds = last;
747 hall[++nb].bounds = last;
749 rank[nu[
i]].min = nb;
751 min =
x[nu[
i]].min();
755 hall[++nb].bounds = last;
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) {
777 if (!card_fixed && !skip_lbc)
785 for (
int i = k.
size();
i--; )
787 for (
int i =
x.size();
i--; )
799 for (
int i = k.
size();
i--; )
811 for (
int i=k.
size();
i--; )
813 cardfix =
false;
break;
816 for (
int i=k.
size();
i--; )
817 if (k[
i].
min() != 0) {
818 nolbc =
false;
break;
823 if (isDistinct<Card>(
x,k))
826 (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 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
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.
void update(Space &home, ViewArray< View > &a)
Update array to be a clone of array a.
Home class for posting propagators
static ModEvent me(const ModEventDelta &med)
Return modification event for view type in med.
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.
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, 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.
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 .
int size(void) const
Return size of array (number of elements)
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.
virtual Actor * copy(Space &home)
Copy propagator during cloning.
#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.
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.
Propagation has not computed fixpoint.
Gecode::IntArgs i({1, 2, 3, 4})
int pathmax_s(const HallInfo hall[], int i)
Path maximum for stable set pointer structure.
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.