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