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);
106 return x[
i].max() <
x[j].max();
120 return x[
i].min() <
x[j].min();
130 return x.min() < y.min();
143 for (
l=start; (k=
l) != end; hall[k].
t=to) {
151 for (
l=start; (k=
l) != end; hall[k].
h=to) {
158 while (hall[
i].h <
i)
165 while (hall[
i].
t <
i)
172 while (hall[
i].h >
i)
179 while (hall[
i].
t >
i)
187 const int n =
x.size();
191 int* minsorted =
r.alloc<
int>(
n);
192 int* maxsorted =
r.alloc<
int>(
n);
194 unsigned int d = static_cast<unsigned int>(max_x - min_x) + 1;
196 if (
d < static_cast<unsigned int>(
n))
199 if (
d > 2*static_cast<unsigned int>(
n)) {
200 for (
int i =
n;
i--; )
201 minsorted[
i]=maxsorted[
i]=
i;
204 Support::quicksort<int,MinIncIdx<View> >(minsorted,
n, min_inc);
206 Support::quicksort<int,MaxIncIdx<View> >(maxsorted,
n, max_inc);
209 int* minbucket =
r.alloc<
int>(
d);
210 int* maxbucket =
r.alloc<
int>(
d);
211 for (
unsigned int i=
d;
i--; )
212 minbucket[
i]=maxbucket[
i]=0;
214 for (
int i=
n;
i--; ) {
215 minbucket[
x[
i].min() - min_x]++;
216 maxbucket[
x[
i].max() - min_x]++;
219 int c_min = 0, c_max = 0;
220 for (
unsigned int i=0;
i<
d;
i++) {
221 int t_min = minbucket[
i];
222 int t_max = maxbucket[
i];
223 minbucket[
i] = c_min; c_min += t_min;
224 maxbucket[
i] = c_max; c_max += t_max;
226 assert((c_min ==
n) && (c_max ==
n));
228 for (
int i=
n;
i--; ) {
229 minsorted[minbucket[
x[
i].min() - min_x]++] =
i;
230 maxsorted[maxbucket[
x[
i].max() - min_x]++] =
i;
235 min_x =
x[minsorted[0]].min();
236 max_x =
x[maxsorted[
n-1]].max();
245 int min =
x[minsorted[0]].min();
246 int max =
x[maxsorted[0]].max() + 1;
257 rank[minsorted[
i]].min = nb;
259 min =
x[minsorted[
i]].min();
263 rank[maxsorted[j]].max = nb;
266 max =
x[maxsorted[j]].max() + 1;
276 for (
int i=nb+2; --
i;) {
277 hall[
i].
t = hall[
i].
h =
i-1;
280 for (
int i=0;
i<
n;
i++) {
281 int x0 = rank[maxsorted[
i]].min;
284 if (--hall[z].
d == 0)
287 int y = rank[maxsorted[
i]].max;
288 if (hall[z].
d < hall[z].bounds-hall[y].bounds)
290 if (hall[x0].h > x0) {
301 if (hall[z].
d == hall[z].bounds-hall[y].bounds) {
308 for (
int i=nb+1;
i--;) {
309 hall[
i].
t = hall[
i].
h =
i+1;
312 for (
int i=
n; --
i>=0; ) {
313 int x0 = rank[minsorted[
i]].max;
316 if (--hall[z].
d == 0)
319 int y = rank[minsorted[
i]].min;
320 if (hall[z].
d < hall[y].bounds-hall[z].bounds)
322 if (hall[x0].h < x0) {
324 int m = hall[w].
bounds - 1;
333 if (hall[z].
d == hall[y].bounds-hall[z].bounds) {
345 int min =
x[
x.size()-1].min(),
max =
x[
x.size()-1].max();
346 for (
int i=
x.size()-1;
i--; ) {
356 assert(
x.size() > 1);
370 ExecStatus es = prop_bnd<View>(home,
x,min_x,max_x);
376 const int n =
x.size();
378 if ((
n > 2*y.size()) && (
n > 6)) {
380 unsigned int d = static_cast<unsigned int>(max_x - min_x) + 1;
381 if (
d > 2*static_cast<unsigned int>(
n)) {
383 Support::quicksort<View,MinInc<View> >(&
x[0],
n, min_inc);
386 int* minbucket =
r.alloc<
int>(
d);
387 View* minsorted =
r.alloc<View>(
n);
389 for (
unsigned int i=
d;
i--; )
392 minbucket[
x[
i].
min() - min_x]++;
395 for (
unsigned int i=0;
i<
d;
i++) {
396 int t_min = minbucket[
i];
397 minbucket[
i] = c_min; c_min += t_min;
402 minsorted[minbucket[
x[
i].
min() - min_x]++] =
x[
i];
409 int max =
x[0].max()-1;
Sort-order by increasing maximum (by index)
void pathset_h(HallInfo hall[], int start, int end, int to)
#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.
ExecStatus ES_SUBSUMED(Propagator &p)
const FloatNum max
Largest allowed float value.
virtual PropCost cost(const Space &home, const ModEventDelta &med) const
Cost function.
void max(Home home, FloatVar x0, FloatVar x1, FloatVar x2)
Post propagator for .
int pathmin_t(const HallInfo hall[], int i)
int ModEvent
Type for modification events.
Base-class for propagators.
bool operator()(const View &x, const View &y)
ExecStatus prop_bnd(Space &home, ViewArray< View > &x, int &min_x, int &max_x)
Perform bounds consistent distinct propagation.
int pathmax_t(const HallInfo hall[], int i)
Propagation has computed fixpoint.
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.
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.
int pathmin_h(const HallInfo hall[], int i)
ViewArray< View > y
Views on which to perform value-propagation (subset of x)
int pathmax_h(const HallInfo hall[], int i)
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)
const Gecode::ModEvent ME_INT_BND
Domain operation has changed the minimum or maximum of the domain.
ExecStatus ES_FIX_PARTIAL(Propagator &p, const ModEventDelta &med)
Propagator p has computed partial fixpoint
void min(Home home, FloatVar x0, FloatVar x1, FloatVar x2)
Post propagator for .
MinIncIdx(const ViewArray< View > &x0)
Node * x
Pointer to corresponding Boolean expression node.
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)
Bounds consistent distinct propagator.
Gecode toplevel namespace
void pathset_t(HallInfo hall[], int start, int end, int to)
Sort-order by increasing minimum (direct)
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.