00001
00002
00003
00004
00005
00006
00007
00008
00009
00010
00011
00012
00013
00014
00015
00016
00017
00018
00019
00020
00021
00022
00023
00024
00025
00026
00027
00028
00029
00030
00031
00032
00033
00034
00035
00036
00037
00038 namespace Gecode { namespace Int { namespace Distinct {
00039
00040 template<class View>
00041 forceinline
00042 Bnd<View>::Bnd(Home home, ViewArray<View>& x0)
00043 : Propagator(home), x(x0), y(home,x0) {
00044
00045
00046
00047
00048
00049 y.subscribe(home,*this,PC_INT_BND);
00050 int min = x[x.size()-1].min(), max = x[x.size()-1].max();
00051 for (int i=x.size()-1; i--; ) {
00052 min = std::min(min,x[i].min());
00053 max = std::max(max,x[i].max());
00054 }
00055 min_x = min; max_x = max;
00056 }
00057
00058 template<class View>
00059 forceinline size_t
00060 Bnd<View>::dispose(Space& home) {
00061 y.cancel(home,*this,PC_INT_BND);
00062 (void) Propagator::dispose(home);
00063 return sizeof(*this);
00064 }
00065
00066 template<class View>
00067 forceinline
00068 Bnd<View>::Bnd(Space& home, bool share, Bnd<View>& p)
00069 : Propagator(home,share,p), min_x(p.min_x), max_x(p.max_x) {
00070 x.update(home,share,p.x);
00071 y.update(home,share,p.y);
00072 }
00073
00074 template<class View>
00075 Actor*
00076 Bnd<View>::copy(Space& home, bool share) {
00077 return new (home) Bnd<View>(home,share,*this);
00078 }
00079
00080 template<class View>
00081 PropCost
00082 Bnd<View>::cost(const Space&, const ModEventDelta& med) const {
00083 if (View::me(med) == ME_INT_VAL)
00084 return PropCost::linear(PropCost::LO, y.size());
00085 else
00086 return PropCost::quadratic(PropCost::LO, x.size());
00087 }
00088
00089
00091 class Rank {
00092 public:
00093 int min, max;
00094 };
00095
00097 template<class View>
00098 class MaxIncIdx {
00099 protected:
00100 ViewArray<View> x;
00101 public:
00102 forceinline
00103 MaxIncIdx(const ViewArray<View>& x0) : x(x0) {}
00104 forceinline bool
00105 operator ()(const int i, const int j) {
00106 return x[i].max() < x[j].max();
00107 }
00108 };
00109
00111 template<class View>
00112 class MinIncIdx {
00113 protected:
00114 ViewArray<View> x;
00115 public:
00116 forceinline
00117 MinIncIdx(const ViewArray<View>& x0) : x(x0) {}
00118 forceinline bool
00119 operator ()(const int i, const int j) {
00120 return x[i].min() < x[j].min();
00121 }
00122 };
00123
00125 template<class View>
00126 class MinInc {
00127 public:
00128 forceinline bool
00129 operator ()(const View& x, const View& y) {
00130 return x.min() < y.min();
00131 }
00132 };
00133
00135 class HallInfo {
00136 public:
00137 int bounds, t, d, h;
00138 };
00139
00140 forceinline void
00141 pathset_t(HallInfo hall[], int start, int end, int to) {
00142 int k, l;
00143 for (l=start; (k=l) != end; hall[k].t=to) {
00144 l = hall[k].t;
00145 }
00146 }
00147
00148 forceinline void
00149 pathset_h(HallInfo hall[], int start, int end, int to) {
00150 int k, l;
00151 for (l=start; (k=l) != end; hall[k].h=to) {
00152 l = hall[k].h;
00153 }
00154 }
00155
00156 forceinline int
00157 pathmin_h(const HallInfo hall[], int i) {
00158 while (hall[i].h < i)
00159 i = hall[i].h;
00160 return i;
00161 }
00162
00163 forceinline int
00164 pathmin_t(const HallInfo hall[], int i) {
00165 while (hall[i].t < i)
00166 i = hall[i].t;
00167 return i;
00168 }
00169
00170 forceinline int
00171 pathmax_h(const HallInfo hall[], int i) {
00172 while (hall[i].h > i)
00173 i = hall[i].h;
00174 return i;
00175 }
00176
00177 forceinline int
00178 pathmax_t(const HallInfo hall[], int i) {
00179 while (hall[i].t > i)
00180 i = hall[i].t;
00181 return i;
00182 }
00183
00184 template<class View>
00185 ExecStatus
00186 prop_bnd(Space& home, ViewArray<View>& x, int& min_x, int& max_x) {
00187 const int n = x.size();
00188
00189 Region r(home);
00190
00191 int* minsorted = r.alloc<int>(n);
00192 int* maxsorted = r.alloc<int>(n);
00193
00194 unsigned int d = static_cast<unsigned int>(max_x - min_x) + 1;
00195
00196 if (d < static_cast<unsigned int>(n))
00197 return ES_FAILED;
00198
00199 if (d > 2*static_cast<unsigned int>(n)) {
00200 for (int i = n; i--; )
00201 minsorted[i]=maxsorted[i]=i;
00202
00203 MinIncIdx<View> min_inc(x);
00204 Support::quicksort<int,MinIncIdx<View> >(minsorted, n, min_inc);
00205 MaxIncIdx<View> max_inc(x);
00206 Support::quicksort<int,MaxIncIdx<View> >(maxsorted, n, max_inc);
00207 } else {
00208
00209 int* minbucket = r.alloc<int>(d);
00210 int* maxbucket = r.alloc<int>(d);
00211 for (unsigned int i=d; i--; )
00212 minbucket[i]=maxbucket[i]=0;
00213
00214 for (int i=n; i--; ) {
00215 minbucket[x[i].min() - min_x]++;
00216 maxbucket[x[i].max() - min_x]++;
00217 }
00218
00219 int c_min = 0, c_max = 0;
00220 for (unsigned int i=0; i<d; i++) {
00221 int t_min = minbucket[i];
00222 int t_max = maxbucket[i];
00223 minbucket[i] = c_min; c_min += t_min;
00224 maxbucket[i] = c_max; c_max += t_max;
00225 }
00226 assert((c_min == n) && (c_max == n));
00227
00228 for (int i=n; i--; ) {
00229 minsorted[minbucket[x[i].min() - min_x]++] = i;
00230 maxsorted[maxbucket[x[i].max() - min_x]++] = i;
00231 }
00232 }
00233
00234
00235 min_x = x[minsorted[0]].min();
00236 max_x = x[maxsorted[n-1]].max();
00237
00238
00239
00240 HallInfo* hall = r.alloc<HallInfo>(2*n+2);
00241 Rank* rank = r.alloc<Rank>(n);
00242
00243 int nb = 0;
00244 {
00245 int min = x[minsorted[0]].min();
00246 int max = x[maxsorted[0]].max() + 1;
00247 int last = min - 2;
00248
00249 hall[0].bounds = last;
00250
00251 int i = 0;
00252 int j = 0;
00253 while (true) {
00254 if ((i < n) && (min < max)) {
00255 if (min != last)
00256 hall[++nb].bounds = last = min;
00257 rank[minsorted[i]].min = nb;
00258 if (++i < n)
00259 min = x[minsorted[i]].min();
00260 } else {
00261 if (max != last)
00262 hall[++nb].bounds = last = max;
00263 rank[maxsorted[j]].max = nb;
00264 if (++j == n)
00265 break;
00266 max = x[maxsorted[j]].max() + 1;
00267 }
00268 }
00269 hall[nb+1].bounds = hall[nb].bounds + 2;
00270 }
00271
00272
00273 ExecStatus es = ES_FIX;
00274
00275
00276 for (int i=nb+2; --i;) {
00277 hall[i].t = hall[i].h = i-1;
00278 hall[i].d = hall[i].bounds - hall[i-1].bounds;
00279 }
00280 for (int i=0; i<n; i++) {
00281 int x0 = rank[maxsorted[i]].min;
00282 int z = pathmax_t(hall, x0+1);
00283 int j = hall[z].t;
00284 if (--hall[z].d == 0)
00285 hall[z = pathmax_t(hall, hall[z].t=z+1)].t = j;
00286 pathset_t(hall, x0+1, z, z);
00287 int y = rank[maxsorted[i]].max;
00288 if (hall[z].d < hall[z].bounds-hall[y].bounds)
00289 return ES_FAILED;
00290 if (hall[x0].h > x0) {
00291 int w = pathmax_h(hall, hall[x0].h);
00292 int m = hall[w].bounds;
00293 ModEvent me = x[maxsorted[i]].gq(home,m);
00294 if (me_failed(me))
00295 return ES_FAILED;
00296 if ((me == ME_INT_VAL) ||
00297 ((me == ME_INT_BND) && (m != x[maxsorted[i]].min())))
00298 es = ES_NOFIX;
00299 pathset_h(hall, x0, w, w);
00300 }
00301 if (hall[z].d == hall[z].bounds-hall[y].bounds) {
00302 pathset_h(hall, hall[y].h, j-1, y);
00303 hall[y].h = j-1;
00304 }
00305 }
00306
00307
00308 for (int i=nb+1; i--;) {
00309 hall[i].t = hall[i].h = i+1;
00310 hall[i].d = hall[i+1].bounds - hall[i].bounds;
00311 }
00312 for (int i=n; --i>=0; ) {
00313 int x0 = rank[minsorted[i]].max;
00314 int z = pathmin_t(hall, x0-1);
00315 int j = hall[z].t;
00316 if (--hall[z].d == 0)
00317 hall[z = pathmin_t(hall, hall[z].t=z-1)].t = j;
00318 pathset_t(hall, x0-1, z, z);
00319 int y = rank[minsorted[i]].min;
00320 if (hall[z].d < hall[y].bounds-hall[z].bounds)
00321 return ES_FAILED;
00322 if (hall[x0].h < x0) {
00323 int w = pathmin_h(hall, hall[x0].h);
00324 int m = hall[w].bounds - 1;
00325 ModEvent me = x[minsorted[i]].lq(home,m);
00326 if (me_failed(me))
00327 return ES_FAILED;
00328 if ((me == ME_INT_VAL) ||
00329 ((me == ME_INT_BND) && (m != x[maxsorted[i]].min())))
00330 es = ES_NOFIX;
00331 pathset_h(hall, x0, w, w);
00332 }
00333 if (hall[z].d == hall[y].bounds-hall[z].bounds) {
00334 pathset_h(hall, hall[y].h, j+1, y);
00335 hall[y].h = j+1;
00336 }
00337 }
00338
00339 return es;
00340 }
00341
00342 template<class View>
00343 ExecStatus
00344 prop_bnd(Space& home, ViewArray<View>& x) {
00345 int min = x[x.size()-1].min(), max = x[x.size()-1].max();
00346 for (int i=x.size()-1; i--; ) {
00347 min = std::min(min,x[i].min());
00348 max = std::max(max,x[i].max());
00349 }
00350 return prop_bnd(home, x, min, max);
00351 }
00352
00353 template<class View>
00354 ExecStatus
00355 Bnd<View>::propagate(Space& home, const ModEventDelta& med) {
00356 assert(x.size() > 1);
00357
00358 if (View::me(med) == ME_INT_VAL) {
00359 ExecStatus es = prop_val<View,false>(home,y);
00360 GECODE_ES_CHECK(es);
00361 if (y.size() < 2)
00362 return home.ES_SUBSUMED(*this);
00363 if (es == ES_FIX)
00364 return home.ES_FIX_PARTIAL(*this,View::med(ME_INT_BND));
00365 }
00366
00367 if (y.size() == 2)
00368 GECODE_REWRITE(*this,Rel::Nq<View>::post(home(*this),y[0],y[1]));
00369
00370 ExecStatus es = prop_bnd<View>(home,x,min_x,max_x);
00371
00372 GECODE_ES_CHECK(es);
00373 if (es == ES_NOFIX && View::me(modeventdelta()) == ME_INT_VAL)
00374 return es;
00375
00376 const int n = x.size();
00377
00378 if ((n > 2*y.size()) && (n > 6)) {
00379
00380 unsigned int d = static_cast<unsigned int>(max_x - min_x) + 1;
00381 if (d > 2*static_cast<unsigned int>(n)) {
00382 MinInc<View> min_inc;
00383 Support::quicksort<View,MinInc<View> >(&x[0], n, min_inc);
00384 } else {
00385 Region r(home);
00386 int* minbucket = r.alloc<int>(d);
00387 View* minsorted = r.alloc<View>(n);
00388
00389 for (unsigned int i=d; i--; )
00390 minbucket[i]=0;
00391 for (int i=n; i--; )
00392 minbucket[x[i].min() - min_x]++;
00393
00394 int c_min = 0;
00395 for (unsigned int i=0; i<d; i++) {
00396 int t_min = minbucket[i];
00397 minbucket[i] = c_min; c_min += t_min;
00398 }
00399 assert(c_min == n);
00400
00401 for (int i=n; i--;)
00402 minsorted[minbucket[x[i].min() - min_x]++] = x[i];
00403 for (int i=n; i--;)
00404 x[i] = minsorted[i];
00405 }
00406
00407 int i = 0;
00408 int j = 0;
00409 int max = x[0].max()-1;
00410 while (i < n-1) {
00411 if (!x[i].assigned() ||
00412 (x[i].val() <= max) || (x[i].val() > x[i+1].min())) {
00413
00414 max = std::max(max,x[i].max());
00415 x[j++]=x[i];
00416 }
00417 i++;
00418 }
00419 if (!x[i].assigned() || (x[i].val() <= max))
00420 x[j++]=x[i];
00421 x.size(j);
00422 }
00423
00424 if (x.size() < 2)
00425 return home.ES_SUBSUMED(*this);
00426
00427 if (x.size() == 2)
00428 GECODE_REWRITE(*this,Rel::Nq<View>::post(home(*this),x[0],x[1]));
00429
00430 return es;
00431 }
00432
00433 template<class View>
00434 ExecStatus
00435 Bnd<View>::post(Home home, ViewArray<View>& x){
00436 if (x.size() == 2)
00437 return Rel::Nq<View>::post(home,x[0],x[1]);
00438 if (x.size() > 2)
00439 (void) new (home) Bnd<View>(home,x);
00440 return ES_OK;
00441 }
00442
00443 }}}
00444
00445
00446