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>
146 IntType start, IntType end, IntType to) {
148 for (l=start; (k=l) != end; hall[k].
t=to) {
153 template<
class IntType>
156 IntType start, IntType end, IntType to) {
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();
209 IntType
min =
x[minsorted[0]].min();
210 IntType
max =
x[maxsorted[0]].max() + 1;
211 IntType last =
min - 2;
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;
247 IntType j = hall[
z].
t;
248 if (--hall[
z].d == 0)
251 IntType
y = rank[maxsorted[i]].max;
252 if (hall[
z].d < hall[
z].bounds-hall[
y].bounds)
254 if (hall[x0].h > x0) {
256 IntType m = hall[w].
bounds;
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;
279 IntType j = hall[
z].
t;
280 if (--hall[
z].d == 0)
283 IntType
y = rank[minsorted[i]].min;
284 if (hall[
z].d < hall[
y].bounds-hall[
z].bounds)
286 if (hall[x0].h < x0) {
288 IntType m = hall[w].
bounds - 1;
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=0; i<n; i++)
324 minsorted[i]=maxsorted[i]=i;
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();
371 int min =
x[0].min(),
max =
x[0].max();
372 for (
int i=1; i<
x.size(); i++) {
382 assert(
x.size() > 1);
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)) {
412 int* minbucket =
r.alloc<
int>(d);
415 for (
unsigned int i=0; i<d; i++)
417 for (
int i=0; i<n; 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;
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;
437 if (!
x[i].assigned() ||
438 (
x[i].val() <=
max) || (
x[i].val() >
x[i+1].
min())) {
445 if (!
x[i].assigned() || (
x[i].val() <=
max))
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);
Base-class for both propagators and branchers.
virtual size_t dispose(Space &home)
Delete actor and return its size.
Home class for posting propagators
Bounds consistent distinct propagator.
int max_x
Maximum (approximation) of view in x.
static ExecStatus post(Home home, ViewArray< View > &x)
Post propagator for view array x.
virtual ExecStatus propagate(Space &home, const ModEventDelta &med)
Perform propagation.
virtual void reschedule(Space &home)
Schedule function.
virtual Actor * copy(Space &home)
Copy propagator during cloning.
ViewArray< View > y
Views on which to perform value-propagation (subset of x)
virtual PropCost cost(const Space &home, const ModEventDelta &med) const
Cost function.
Bnd(Home home, ViewArray< View > &x)
Constructor for posting.
virtual size_t dispose(Space &home)
Destructor.
ViewArray< View > x
Views on which to perform bounds-propagation.
int min_x
Minimum (approximation) of view in x.
Information on Hall intervals.
Sort-order by increasing maximum (by index)
MaxIncIdx(const ViewArray< View > &x0)
bool operator()(const int i, const int j)
Sort-order by increasing minimum (by index)
MinIncIdx(const ViewArray< View > &x0)
bool operator()(const int i, const int j)
Sort-order by increasing minimum (direct)
bool operator()(const View &x, const View &y)
static ExecStatus post(Home home, V0 x0, V1 x1)
Post propagator .
static PropCost quadratic(PropCost::Mod m, unsigned int n)
Quadratic complexity for modifier m and size measure n.
static PropCost linear(PropCost::Mod m, unsigned int n)
Linear complexity for modifier pcm and size measure n.
ModEventDelta modeventdelta(void) const
Return the modification event delta.
ModEventDelta med
A set of modification events (used during propagation)
Propagator(Home home)
Constructor for posting.
ExecStatus ES_FIX_PARTIAL(Propagator &p, const ModEventDelta &med)
Propagator p has computed partial fixpoint
ExecStatus ES_SUBSUMED(Propagator &p)
Propagator p is subsumed
int ModEventDelta
Modification event deltas.
#define GECODE_REWRITE(prop, post)
Rewrite propagator by executing post function.
bool me_failed(ModEvent me)
Check whether modification event me is failed.
#define GECODE_ES_CHECK(es)
Check whether execution status es is failed or subsumed, and forward failure or subsumption.
ExecStatus prop_bnd(Space &home, ViewArray< View > &x, int &min_x, int &max_x)
Perform bounds consistent distinct propagation.
void pathset_h(HallInfo< IntType > hall[], IntType start, IntType end, IntType to)
IntType pathmin_t(const HallInfo< IntType > hall[], IntType i)
ExecStatus prop_val(Space &home, ViewArray< View > &)
Eliminate singletons by naive value propagation.
IntType pathmax_t(const HallInfo< IntType > hall[], IntType i)
IntType pathmax_h(const HallInfo< IntType > hall[], IntType i)
IntType pathmin_h(const HallInfo< IntType > hall[], IntType i)
void pathset_t(HallInfo< IntType > hall[], IntType start, IntType end, IntType to)
const int max
Largest allowed integer value.
const Gecode::ModEvent ME_INT_BND
Domain operation has changed the minimum or maximum of the domain.
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 quicksort(Type *l, Type *r, Less &less)
Standard quick sort.
Gecode toplevel namespace
Post propagator for SetVar SetOpType SetVar SetRelType r
void min(Home home, FloatVar x0, FloatVar x1, FloatVar x2)
Post propagator for .
Post propagator for SetVar SetOpType SetVar SetRelType SetVar z
Post propagator for SetVar SetOpType SetVar y
@ ES_OK
Execution is okay.
@ ES_FIX
Propagation has computed fixpoint.
@ ES_FAILED
Execution has resulted in failure.
@ ES_NOFIX
Propagation has not computed fixpoint.
void max(Home home, FloatVar x0, FloatVar x1, FloatVar x2)
Post propagator for .
Post propagator for SetVar x
int ModEvent
Type for modification events.