Go to the documentation of this file.
46 int min =
x[0].min(),
max =
x[0].max();
47 for (
int i=1;
i<
x.size();
i++) {
108 return x[
i].max() <
x[j].max();
122 return x[
i].min() <
x[j].min();
132 return x.min() <
y.min();
137 template<
class IntType>
143 template<
class IntType>
148 for (
l=start; (k=
l) != end; hall[k].
t=to) {
153 template<
class IntType>
158 for (
l=start; (k=
l) != end; hall[k].
h=to) {
163 template<
class IntType>
166 while (hall[
i].h <
i)
171 template<
class IntType>
174 while (hall[
i].
t <
i)
179 template<
class IntType>
182 while (hall[
i].h >
i)
187 template<
class IntType>
190 while (hall[
i].
t >
i)
195 template<
class View,
class IntType>
198 int* minsorted,
int* maxsorted) {
199 const int n =
x.size();
221 rank[minsorted[
i]].min = nb;
223 min =
x[minsorted[
i]].min();
227 rank[maxsorted[j]].max = nb;
230 max =
x[maxsorted[j]].max() + 1;
240 for (
int i=nb+2; --
i;) {
241 hall[
i].
t = hall[
i].
h =
i-1;
244 for (
int i=0;
i<
n;
i++) {
245 IntType x0 = rank[maxsorted[
i]].min;
248 if (--hall[
z].
d == 0)
252 if (hall[
z].
d < hall[
z].bounds-hall[
y].bounds)
254 if (hall[x0].h > x0) {
265 if (hall[
z].
d == hall[
z].bounds-hall[
y].bounds) {
272 for (
int i=nb+1;
i--;) {
273 hall[
i].
t = hall[
i].
h =
i+1;
276 for (
int i=
n; --
i>=0; ) {
277 IntType x0 = rank[minsorted[
i]].max;
280 if (--hall[
z].
d == 0)
284 if (hall[
z].
d < hall[
y].bounds-hall[
z].bounds)
286 if (hall[x0].h < x0) {
297 if (hall[
z].
d == hall[
y].bounds-hall[
z].bounds) {
310 const int n =
x.size();
314 int* minsorted =
r.alloc<
int>(
n);
315 int* maxsorted =
r.alloc<
int>(
n);
317 unsigned int d = static_cast<unsigned int>(max_x - min_x) + 1;
319 if (
d < static_cast<unsigned int>(
n))
322 if (
d > 2*static_cast<unsigned int>(
n)) {
323 for (
int i=0;
i<
n;
i++)
324 minsorted[
i]=maxsorted[
i]=
i;
327 Support::quicksort<int,MinIncIdx<View> >(minsorted,
n, min_inc);
329 Support::quicksort<int,MaxIncIdx<View> >(maxsorted,
n, max_inc);
332 int* minbucket =
r.alloc<
int>(
d);
333 int* maxbucket =
r.alloc<
int>(
d);
334 for (
unsigned int i=0;
i<
d;
i++)
335 minbucket[
i]=maxbucket[
i]=0;
337 for (
int i=0;
i<
n;
i++) {
338 minbucket[
x[
i].min() - min_x]++;
339 maxbucket[
x[
i].max() - min_x]++;
342 int c_min = 0, c_max = 0;
343 for (
unsigned int i=0;
i<
d;
i++) {
344 int t_min = minbucket[
i];
345 int t_max = maxbucket[
i];
346 minbucket[
i] = c_min; c_min += t_min;
347 maxbucket[
i] = c_max; c_max += t_max;
349 assert((c_min ==
n) && (c_max ==
n));
351 for (
int i=
n;
i--; ) {
352 minsorted[minbucket[
x[
i].min() - min_x]++] =
i;
353 maxsorted[maxbucket[
x[
i].max() - min_x]++] =
i;
358 min_x =
x[minsorted[0]].min();
359 max_x =
x[maxsorted[
n-1]].max();
363 return prop_bnd<View,long long int>(home,
x,minsorted,maxsorted);
365 return prop_bnd<View,int>(home,
x,minsorted,maxsorted);
371 int min =
x[0].min(),
max =
x[0].max();
372 for (
int i=1;
i<
x.size();
i++) {
382 assert(
x.size() > 1);
396 ExecStatus es = prop_bnd<View>(home,
x,min_x,max_x);
402 const int n =
x.size();
404 if ((
n > 2*
y.size()) && (
n > 6)) {
406 unsigned int d = static_cast<unsigned int>(max_x - min_x) + 1;
407 if (
d > 2*static_cast<unsigned int>(
n)) {
409 Support::quicksort<View,MinInc<View> >(&
x[0],
n, min_inc);
412 int* minbucket =
r.alloc<
int>(
d);
413 View* minsorted =
r.alloc<View>(
n);
415 for (
unsigned int i=0;
i<
d;
i++)
417 for (
int i=0;
i<
n;
i++)
418 minbucket[
x[
i].
min() - min_x]++;
421 for (
unsigned int i=0;
i<
d;
i++) {
422 int t_min = minbucket[
i];
423 minbucket[
i] = c_min; c_min += t_min;
427 for (
int i=0;
i<
n;
i++)
428 minsorted[minbucket[
x[
i].
min() - min_x]++] =
x[
i];
429 for (
int i=0;
i<
n;
i++)
435 int max =
x[0].max()-1;
459 #ifdef GECODE_HAS_CBS
463 cbsdistinct(home,this->
id(),
x,send);
468 Bnd<View>::domainsizesum(Propagator::InDecision in,
unsigned int&
size,
469 unsigned int& size_b)
const {
470 cbssize(
x,in,
size,size_b);
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.
IntType pathmax_t(const HallInfo< IntType > hall[], IntType i)
unsigned int size(I &i)
Size of all ranges of range iterator 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
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 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.
Propagation has computed fixpoint.
IntType pathmax_h(const HallInfo< IntType > hall[], IntType i)
virtual Actor * copy(Space &home)
Copy propagator during cloning.
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.
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.
Propagation has not computed fixpoint.
Gecode::IntArgs i({1, 2, 3, 4})
#define GECODE_REWRITE(prop, post)
Rewrite propagator by executing post function.
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.