Go to the documentation of this file.
50 int min =
x[
x.size()-1].min(),
max =
x[
x.size()-1].max();
51 for (
int i=
x.size()-1;
i--; ) {
70 x.update(home,share,
p.x);
71 y.update(home,share,
p.y);
77 return new (home)
Bnd<View>(home,share,*
this);
112 return x[
i].max() <
x[j].max();
126 return x[
i].min() <
x[j].min();
136 return x.min() <
y.min();
141 template<
class IntType>
147 template<
class IntType>
152 for (
l=start; (k=
l) != end; hall[k].
t=to) {
157 template<
class IntType>
162 for (
l=start; (k=
l) != end; hall[k].
h=to) {
167 template<
class IntType>
170 while (hall[
i].h <
i)
175 template<
class IntType>
178 while (hall[
i].
t <
i)
183 template<
class IntType>
186 while (hall[
i].h >
i)
191 template<
class IntType>
194 while (hall[
i].
t >
i)
199 template<
class View,
class IntType>
202 int* minsorted,
int* maxsorted) {
203 const int n =
x.size();
225 rank[minsorted[
i]].min = nb;
227 min =
x[minsorted[
i]].min();
231 rank[maxsorted[j]].max = nb;
234 max =
x[maxsorted[j]].max() + 1;
244 for (
int i=nb+2; --
i;) {
245 hall[
i].
t = hall[
i].
h =
i-1;
248 for (
int i=0;
i<
n;
i++) {
249 IntType x0 = rank[maxsorted[
i]].min;
252 if (--hall[
z].
d == 0)
256 if (hall[
z].
d < hall[
z].bounds-hall[
y].bounds)
258 if (hall[x0].h > x0) {
269 if (hall[
z].
d == hall[
z].bounds-hall[
y].bounds) {
276 for (
int i=nb+1;
i--;) {
277 hall[
i].
t = hall[
i].
h =
i+1;
280 for (
int i=
n; --
i>=0; ) {
281 IntType x0 = rank[minsorted[
i]].max;
284 if (--hall[
z].
d == 0)
288 if (hall[
z].
d < hall[
y].bounds-hall[
z].bounds)
290 if (hall[x0].h < x0) {
301 if (hall[
z].
d == hall[
y].bounds-hall[
z].bounds) {
314 const int n =
x.size();
318 int* minsorted =
r.alloc<
int>(
n);
319 int* maxsorted =
r.alloc<
int>(
n);
321 unsigned int d =
static_cast<unsigned int>(max_x - min_x) + 1;
323 if (
d <
static_cast<unsigned int>(
n))
326 if (
d > 2*
static_cast<unsigned int>(
n)) {
327 for (
int i =
n;
i--; )
328 minsorted[
i]=maxsorted[
i]=
i;
331 Support::quicksort<int,MinIncIdx<View> >(minsorted,
n, min_inc);
333 Support::quicksort<int,MaxIncIdx<View> >(maxsorted,
n, max_inc);
336 int* minbucket =
r.alloc<
int>(
d);
337 int* maxbucket =
r.alloc<
int>(
d);
338 for (
unsigned int i=
d;
i--; )
339 minbucket[
i]=maxbucket[
i]=0;
341 for (
int i=
n;
i--; ) {
342 minbucket[
x[
i].min() - min_x]++;
343 maxbucket[
x[
i].max() - min_x]++;
346 int c_min = 0, c_max = 0;
347 for (
unsigned int i=0;
i<
d;
i++) {
348 int t_min = minbucket[
i];
349 int t_max = maxbucket[
i];
350 minbucket[
i] = c_min; c_min += t_min;
351 maxbucket[
i] = c_max; c_max += t_max;
353 assert((c_min ==
n) && (c_max ==
n));
355 for (
int i=
n;
i--; ) {
356 minsorted[minbucket[
x[
i].min() - min_x]++] =
i;
357 maxsorted[maxbucket[
x[
i].max() - min_x]++] =
i;
362 min_x =
x[minsorted[0]].min();
363 max_x =
x[maxsorted[
n-1]].max();
367 return prop_bnd<View,long long int>(home,
x,minsorted,maxsorted);
369 return prop_bnd<View,int>(home,
x,minsorted,maxsorted);
375 int min =
x[
x.size()-1].min(),
max =
x[
x.size()-1].max();
376 for (
int i=
x.size()-1;
i--; ) {
386 assert(
x.size() > 1);
400 ExecStatus es = prop_bnd<View>(home,
x,min_x,max_x);
406 const int n =
x.size();
408 if ((
n > 2*
y.size()) && (
n > 6)) {
410 unsigned int d =
static_cast<unsigned int>(max_x - min_x) + 1;
411 if (
d > 2*
static_cast<unsigned int>(
n)) {
413 Support::quicksort<View,MinInc<View> >(&
x[0],
n, min_inc);
416 int* minbucket =
r.alloc<
int>(
d);
417 View* minsorted =
r.alloc<View>(
n);
419 for (
unsigned int i=
d;
i--; )
422 minbucket[
x[
i].
min() - min_x]++;
425 for (
unsigned int i=0;
i<
d;
i++) {
426 int t_min = minbucket[
i];
427 minbucket[
i] = c_min; c_min += t_min;
432 minsorted[minbucket[
x[
i].
min() - min_x]++] =
x[
i];
439 int max =
x[0].max()-1;
Post propagator for SetVar x
Post propagator for SetVar SetOpType SetVar y
Bnd(Home home, ViewArray< View > &x)
Constructor for posting.
bool me_failed(ModEvent me)
Check whether modification event me is failed.
void max(Home home, FloatVar x0, FloatVar x1, FloatVar x2)
Post propagator for .
ExecStatus ES_SUBSUMED(Propagator &p)
Bounds consistent distinct propagator.
static ExecStatus post(Home home, ViewArray< View > &x)
Post propagator for view array x.
static ExecStatus post(Home home, V0 x0, V1 x1)
Post propagator .
IntType pathmax_t(const HallInfo< IntType > hall[], IntType i)
virtual ExecStatus propagate(Space &home, const ModEventDelta &med)
Perform propagation.
ExecStatus prop_bnd(Space &home, ViewArray< View > &x, int *minsorted, int *maxsorted)
Information on Hall intervals.
bool operator()(const int i, const int j)
bool assigned(View x, int v)
Whether x is assigned to value v.
bool operator()(const View &x, const View &y)
Post propagator for SetVar SetOpType SetVar SetRelType SetVar z
Gecode::IntArgs i(4, 1, 2, 3, 4)
MaxIncIdx(const ViewArray< View > &x0)
const FloatNum min
Smallest allowed float value.
static PropCost linear(PropCost::Mod m, unsigned int n)
Linear complexity for modifier pcm and size measure n.
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 Actor * copy(Space &home, bool share)
Copy propagator during cloning.
virtual size_t dispose(Space &home)
Destructor.
Binary disequality propagator.
const Gecode::ModEvent ME_INT_VAL
Domain operation has resulted in a value (assigned variable)
bool operator()(const int i, const int j)
Gecode toplevel namespace
Base-class for propagators.
#define GECODE_ES_CHECK(es)
Check whether execution status es is failed or subsumed, and forward failure or subsumption.
Home class for posting propagators
const Gecode::ModEvent ME_INT_BND
Domain operation has changed the minimum or maximum of the domain.
Post propagator for SetVar SetOpType SetVar SetRelType r
IntType pathmin_t(const HallInfo< IntType > hall[], IntType i)
int min_x
Minimum (approximation) of view in x.
const int max
Largest allowed integer value.
virtual void reschedule(Space &home)
Schedule function.
Sort-order by increasing minimum (by index)
virtual PropCost cost(const Space &home, const ModEventDelta &med) const
Cost function.
void pathset_t(HallInfo< IntType > hall[], IntType start, IntType end, IntType to)
IntType pathmin_h(const HallInfo< IntType > hall[], IntType i)
const Gecode::PropCond PC_INT_BND
Propagate when minimum or maximum of a view changes.
int ModEvent
Type for modification events.
ViewArray< View > y
Views on which to perform value-propagation (subset of x)
Propagator for negated equality
Sort-order by increasing maximum (by index)
IntType
Description of integer types.
@ ES_FIX
Propagation has computed fixpoint.
IntType pathmax_h(const HallInfo< IntType > hall[], IntType i)
int max_x
Maximum (approximation) of view in x.
Sort-order by increasing minimum (direct)
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 .
int n
Number of negative literals for node type.
@ ES_FAILED
Execution has resulted in failure.
ExecStatus ES_FIX_PARTIAL(Propagator &p, const ModEventDelta &med)
Propagator p has computed partial fixpoint
ViewArray< View > x
Views on which to perform bounds-propagation.
int ModEventDelta
Modification event deltas.
@ ES_NOFIX
Propagation has not computed fixpoint.
#define GECODE_REWRITE(prop, post)
Rewrite propagator by executing post function.
@ ES_OK
Execution is okay.
int p
Number of positive literals for node type.
MinIncIdx(const ViewArray< View > &x0)
void pathset_h(HallInfo< IntType > hall[], IntType start, IntType end, IntType to)
const FloatNum max
Largest allowed float value.