50 int min =
x[
x.size()-1].min(),
max =
x[
x.size()-1].max();
51 for (
int i=
x.size()-1;
i--; ) {
69 :
Propagator(home,share,p), min_x(p.min_x), max_x(p.max_x) {
70 x.update(home,share,p.
x);
71 y.update(home,share,p.
y);
77 return new (home)
Bnd<View>(home,share,*
this);
106 return x[
i].max() < x[j].max();
120 return x[
i].min() < x[j].min();
130 return x.min() < y.min();
135 template<
class IntType>
141 template<
class IntType>
146 for (l=start; (k=
l) != end; hall[k].
t=to) {
151 template<
class IntType>
156 for (l=start; (k=
l) != end; hall[k].
h=to) {
161 template<
class IntType>
164 while (hall[i].h < i)
169 template<
class IntType>
172 while (hall[i].
t < i)
177 template<
class IntType>
180 while (hall[i].h > i)
185 template<
class IntType>
188 while (hall[i].
t > i)
193 template<
class View,
class IntType>
196 int* minsorted,
int* maxsorted) {
197 const int n = x.
size();
216 if ((i < n) && (min < max)) {
219 rank[minsorted[
i]].min = nb;
221 min = x[minsorted[
i]].min();
225 rank[maxsorted[j]].max = nb;
228 max = x[maxsorted[j]].max() + 1;
238 for (
int i=nb+2; --
i;) {
239 hall[
i].
t = hall[
i].
h =
i-1;
242 for (
int i=0;
i<
n;
i++) {
243 IntType x0 = rank[maxsorted[
i]].min;
246 if (--hall[z].
d == 0)
250 if (hall[z].
d < hall[z].bounds-hall[y].bounds)
252 if (hall[x0].h > x0) {
255 ModEvent me = x[maxsorted[
i]].gq(home,m);
263 if (hall[z].
d == hall[z].bounds-hall[y].bounds) {
270 for (
int i=nb+1;
i--;) {
271 hall[
i].
t = hall[
i].
h =
i+1;
274 for (
int i=n; --
i>=0; ) {
275 IntType x0 = rank[minsorted[
i]].max;
278 if (--hall[z].
d == 0)
282 if (hall[z].
d < hall[y].bounds-hall[z].bounds)
284 if (hall[x0].h < x0) {
287 ModEvent me = x[minsorted[
i]].lq(home,m);
295 if (hall[z].
d == hall[y].bounds-hall[z].bounds) {
308 const int n = x.
size();
312 int* minsorted = r.
alloc<
int>(
n);
313 int* maxsorted = r.
alloc<
int>(
n);
315 unsigned int d =
static_cast<unsigned int>(max_x - min_x) + 1;
317 if (d < static_cast<unsigned int>(n))
320 if (d > 2*static_cast<unsigned int>(n)) {
321 for (
int i = n;
i--; )
322 minsorted[
i]=maxsorted[
i]=
i;
325 Support::quicksort<int,MinIncIdx<View> >(minsorted,
n, min_inc);
327 Support::quicksort<int,MaxIncIdx<View> >(maxsorted,
n, max_inc);
330 int* minbucket = r.
alloc<
int>(
d);
331 int* maxbucket = r.
alloc<
int>(
d);
332 for (
unsigned int i=d;
i--; )
333 minbucket[
i]=maxbucket[
i]=0;
335 for (
int i=n;
i--; ) {
336 minbucket[x[
i].min() - min_x]++;
337 maxbucket[x[
i].max() - min_x]++;
340 int c_min = 0, c_max = 0;
341 for (
unsigned int i=0;
i<
d;
i++) {
342 int t_min = minbucket[
i];
343 int t_max = maxbucket[
i];
344 minbucket[
i] = c_min; c_min += t_min;
345 maxbucket[
i] = c_max; c_max += t_max;
347 assert((c_min == n) && (c_max == n));
349 for (
int i=n;
i--; ) {
350 minsorted[minbucket[x[
i].min() - min_x]++] =
i;
351 maxsorted[maxbucket[x[
i].max() - min_x]++] =
i;
356 min_x = x[minsorted[0]].min();
357 max_x = x[maxsorted[n-1]].max();
361 return prop_bnd<View,long long int>(home,
x,minsorted,maxsorted);
363 return prop_bnd<View,int>(home,
x,minsorted,maxsorted);
370 for (
int i=x.
size()-1;
i--; ) {
380 assert(
x.size() > 1);
386 return home.ES_SUBSUMED(*
this);
388 return home.ES_FIX_PARTIAL(*
this,View::med(
ME_INT_BND));
394 ExecStatus es = prop_bnd<View>(home,
x,min_x,max_x);
400 const int n = x.size();
402 if ((n > 2*y.size()) && (n > 6)) {
404 unsigned int d =
static_cast<unsigned int>(max_x - min_x) + 1;
405 if (d > 2*static_cast<unsigned int>(n)) {
407 Support::quicksort<View,MinInc<View> >(&x[0],
n, min_inc);
410 int* minbucket = r.
alloc<
int>(
d);
411 View* minsorted = r.
alloc<View>(
n);
413 for (
unsigned int i=d;
i--; )
416 minbucket[x[
i].
min() - min_x]++;
419 for (
unsigned int i=0;
i<
d;
i++) {
420 int t_min = minbucket[
i];
421 minbucket[
i] = c_min; c_min += t_min;
426 minsorted[minbucket[x[
i].
min() - min_x]++] = x[
i];
433 int max = x[0].max()-1;
436 (x[i].val() <= max) || (x[i].val() > x[i+1].
min())) {
443 if (!x[i].
assigned() || (x[i].val() <= max))
449 return home.ES_SUBSUMED(*
this);
Sort-order by increasing maximum (by index)
#define GECODE_REWRITE(prop, post)
Rewrite propagator by executing post function.
Propagator for negated equality
static PropCost quadratic(PropCost::Mod m, unsigned int n)
Quadratic complexity for modifier m and size measure n.
int min_x
Minimum (approximation) of view in x.
ViewArray< View > x
Views on which to perform bounds-propagation.
static PropCost linear(PropCost::Mod m, unsigned int n)
Linear complexity for modifier pcm and size measure n.
const FloatNum max
Largest allowed float value.
T * alloc(long unsigned int n)
Allocate block of n objects of type T from region.
void max(Home home, FloatVar x0, FloatVar x1, FloatVar x2)
Post propagator for .
int ModEvent
Type for modification events.
Base-class for propagators.
bool operator()(const View &x, const View &y)
Propagation has computed fixpoint.
const int max
Largest allowed integer value.
Bnd(Home home, ViewArray< View > &x)
Constructor for posting.
virtual ExecStatus propagate(Space &home, const ModEventDelta &med)
Perform propagation.
Base-class for both propagators and branchers.
#define GECODE_ES_CHECK(es)
Check whether execution status es is failed or subsumed, and forward failure or subsumption.
IntType pathmin_h(const HallInfo< IntType > hall[], IntType i)
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.
int n
Number of negative literals for node type.
ViewArray< View > y
Views on which to perform value-propagation (subset of x)
Execution has resulted in failure.
Information on Hall intervals.
virtual Actor * copy(Space &home, bool share)
Copy propagator during cloning.
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 pathset_t(HallInfo< IntType > hall[], IntType start, IntType end, IntType to)
const Gecode::ModEvent ME_INT_BND
Domain operation has changed the minimum or maximum of the domain.
IntType pathmax_h(const HallInfo< IntType > hall[], IntType i)
void min(Home home, FloatVar x0, FloatVar x1, FloatVar x2)
Post propagator for .
MinIncIdx(const ViewArray< View > &x0)
IntType pathmin_t(const HallInfo< IntType > hall[], IntType i)
Node * x
Pointer to corresponding Boolean expression node.
void pathset_h(HallInfo< IntType > hall[], IntType start, IntType end, IntType to)
virtual size_t dispose(Space &home)
Delete actor and return its size.
bool operator()(const int i, const int j)
bool assigned(View x, int v)
Whether x is assigned to value v.
int max_x
Maximum (approximation) of view in x.
Binary disequality propagator.
Propagation has not computed fixpoint.
MaxIncIdx(const ViewArray< View > &x0)
int size(void) const
Return size of array (number of elements)
Bounds consistent distinct propagator.
Gecode toplevel namespace
virtual PropCost cost(const Space &home, const ModEventDelta &med) const
Cost function.
IntType pathmax_t(const HallInfo< IntType > hall[], IntType i)
Sort-order by increasing minimum (direct)
IntType
Description of integer types.
ExecStatus prop_bnd(Space &home, ViewArray< View > &x, int *minsorted, int *maxsorted)
int ModEventDelta
Modification event deltas.
virtual size_t dispose(Space &home)
Destructor.
Home class for posting propagators
bool operator()(const int i, const int j)
Sort-order by increasing minimum (by index)
bool me_failed(ModEvent me)
Check whether modification event me is failed.