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);
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;
734 hall[0].bounds = last;
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) {
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);
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.
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 .
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.
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.
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)
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.
Post propagator for SetVar SetOpType SetVar SetRelType SetVar z
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.
Post propagator for SetVar SetOpType SetVar SetRelType r
void min(Home home, FloatVar x0, FloatVar x1, FloatVar x2)
Post propagator for .
int newBound
Bound update.
Post propagator for SetVar SetOpType SetVar y
Maps domain bounds to their position in hall[].bounds.
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.
Post propagator for SetVar x
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.
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.
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.