38 namespace Gecode {
namespace Int {
namespace Distinct {
50 int min =
x[
x.size()-1].min(),
max =
x[
x.size()-1].max();
51 for (
int i=
x.size()-1;
i--; ) {
69 :
Propagator(home,share,p), min_x(p.min_x), max_x(p.max_x) {
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;
254 if ((i < n) && (min < max)) {
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)
285 hall[z =
pathmax_t(hall, hall[z].t=z+1)].
t = j;
287 int y = rank[maxsorted[
i]].max;
288 if (hall[z].d < hall[z].bounds-hall[y].bounds)
290 if (hall[x0].h > x0) {
293 ModEvent me = x[maxsorted[
i]].gq(home,m);
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)
317 hall[z =
pathmin_t(hall, hall[z].t=z-1)].
t = j;
319 int y = rank[minsorted[
i]].min;
320 if (hall[z].d < hall[y].bounds-hall[z].bounds)
322 if (hall[x0].h < x0) {
325 ModEvent me = x[minsorted[
i]].lq(home,m);
333 if (hall[z].d == hall[y].bounds-hall[z].bounds) {
346 for (
int i=x.
size()-1;
i--; ) {
356 assert(x.size() > 1);
362 return home.ES_SUBSUMED(*
this);
364 return home.ES_FIX_PARTIAL(*
this,View::med(
ME_INT_BND));
370 ExecStatus es = prop_bnd<View>(home,x,min_x,max_x);
374 const int n = x.size();
376 if ((n > 2*y.size()) && (n > 6)) {
378 unsigned int d =
static_cast<unsigned int>(max_x - min_x) + 1;
379 if (d > 2*static_cast<unsigned int>(n)) {
381 Support::quicksort<View,MinInc<View> >(&x[0], n, min_inc);
384 int* minbucket = r.
alloc<
int>(
d);
385 View* minsorted = r.
alloc<View>(n);
387 for (
unsigned int i=d;
i--; )
390 minbucket[x[
i].
min() - min_x]++;
393 for (
unsigned int i=0;
i<
d;
i++) {
394 int t_min = minbucket[
i];
395 minbucket[
i] = c_min; c_min += t_min;
400 minsorted[minbucket[x[
i].
min() - min_x]++] = x[
i];
407 int max = x[0].max()-1;
410 (x[i].val() <= max) || (x[i].val() > x[i+1].
min())) {
417 if (!x[i].
assigned() || (x[i].val() <= max))
423 return home.ES_SUBSUMED(*
this);