40 namespace Gecode {
namespace Int {
namespace GCC {
46 bool cf,
bool nolbc) :
48 card_fixed(cf), skip_lbc(nolbc) {
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;
574 int*
z = r.
alloc<
int>(n_z);
578 if (
k[
i].
max() == 0) {
579 z[n_z++] =
k[
i].card();
589 lps.reinit();
ups.reinit();
610 bool all_assigned =
true;
612 for (
int i =
x.
size();
i--; ) {
622 all_assigned =
false;
625 if (!Card::propagate)
630 if (Card::propagate) {
639 if (!card_consistent<Card>(
x,
k))
649 for (
int i =
x.
size();
i--; ) {
660 all_assigned =
false;
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;
744 if (i < n && min < max) {
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) {
785 for (
int i = k.
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);
virtual PropCost cost(const Space &home, const ModEventDelta &med) const
Cost funtion.
int d
Difference between critical capacities.
void reschedule(Space &home, Propagator &p, PropCond pc)
Re-schedule propagator p with propagation condition pc.
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.
void update(Space &home, ViewArray< View > &a)
Update array to be a clone of array a.
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.
virtual Actor * copy(Space &home)
Copy propagator during cloning.
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.
Post propagator for SetVar SetOpType SetVar SetRelType SetVar z
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.
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.
Bnd(Space &home, Bnd< Card > &p)
Constructor for cloning p.
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.
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.