46 int min =
x[
x.size()-1].min(),
max =
x[
x.size()-1].max();
47 for (
int i=
x.size()-1;
i--; ) {
107 operator ()(
const int i,
const int j) {
108 return x[
i].max() < x[j].max();
121 operator ()(
const int i,
const int j) {
122 return x[
i].min() < x[j].min();
131 operator ()(
const View&
x,
const View&
y) {
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();
218 if ((i < n) && (min < max)) {
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) {
257 ModEvent me = x[maxsorted[
i]].gq(home,m);
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) {
289 ModEvent me = x[minsorted[
i]].lq(home,m);
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 = 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=d;
i--; )
335 minbucket[
i]=maxbucket[
i]=0;
337 for (
int 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);
372 for (
int i=x.
size()-1;
i--; ) {
382 assert(
x.size() > 1);
388 return home.ES_SUBSUMED(*
this);
390 return home.ES_FIX_PARTIAL(*
this,View::med(
ME_INT_BND));
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=d;
i--; )
421 for (
unsigned int i=0;
i<
d;
i++) {
422 int t_min = minbucket[
i];
423 minbucket[
i] = c_min; c_min += t_min;
428 minsorted[minbucket[x[
i].
min() -
min_x]++] = x[
i];
435 int max = x[0].max()-1;
438 (x[i].val() <= max) || (x[i].val() > x[i+1].
min())) {
445 if (!x[i].
assigned() || (x[i].val() <= max))
451 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.
virtual PropCost cost(const Space &home, const ModEventDelta &med) const
Cost function.
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 .
virtual Actor * copy(Space &home)
Copy propagator during cloning.
int ModEvent
Type for modification events.
Base-class for propagators.
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.
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)
ModEventDelta med
A set of modification events (used during propagation)
virtual void reschedule(Space &home)
Schedule function.
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)
Post propagator for SetVar SetOpType SetVar SetRelType SetVar z
ModEventDelta modeventdelta(void) const
Return the modification event delta.
Post propagator for SetVar SetOpType SetVar SetRelType r
void min(Home home, FloatVar x0, FloatVar x1, FloatVar x2)
Post propagator for .
MinIncIdx(const ViewArray< View > &x0)
Post propagator for SetVar SetOpType SetVar y
IntType pathmin_t(const HallInfo< IntType > hall[], IntType i)
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 assigned(View x, int v)
Whether x is assigned to value v.
int max_x
Maximum (approximation) of view in x.
Binary disequality propagator.
Post propagator for SetVar x
Propagation has not computed fixpoint.
MaxIncIdx(const ViewArray< View > &x0)
Bounds consistent distinct propagator.
Gecode toplevel namespace
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 size(void) const
Return size of array (number of elements)
int ModEventDelta
Modification event deltas.
virtual size_t dispose(Space &home)
Destructor.
Home class for posting propagators
Sort-order by increasing minimum (by index)
bool me_failed(ModEvent me)
Check whether modification event me is failed.