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 template<class View>
00090 void
00091 Bnd<View>::reschedule(Space& home) {
00092 y.reschedule(home,*this,PC_INT_BND);
00093 }
00094
00095
00097 class Rank {
00098 public:
00099 int min, max;
00100 };
00101
00103 template<class View>
00104 class MaxIncIdx {
00105 protected:
00106 ViewArray<View> x;
00107 public:
00108 forceinline
00109 MaxIncIdx(const ViewArray<View>& x0) : x(x0) {}
00110 forceinline bool
00111 operator ()(const int i, const int j) {
00112 return x[i].max() < x[j].max();
00113 }
00114 };
00115
00117 template<class View>
00118 class MinIncIdx {
00119 protected:
00120 ViewArray<View> x;
00121 public:
00122 forceinline
00123 MinIncIdx(const ViewArray<View>& x0) : x(x0) {}
00124 forceinline bool
00125 operator ()(const int i, const int j) {
00126 return x[i].min() < x[j].min();
00127 }
00128 };
00129
00131 template<class View>
00132 class MinInc {
00133 public:
00134 forceinline bool
00135 operator ()(const View& x, const View& y) {
00136 return x.min() < y.min();
00137 }
00138 };
00139
00141 template<class IntType>
00142 class HallInfo {
00143 public:
00144 IntType bounds, t, d, h;
00145 };
00146
00147 template<class IntType>
00148 forceinline void
00149 pathset_t(HallInfo<IntType> hall[],
00150 IntType start, IntType end, IntType to) {
00151 IntType k, l;
00152 for (l=start; (k=l) != end; hall[k].t=to) {
00153 l = hall[k].t;
00154 }
00155 }
00156
00157 template<class IntType>
00158 forceinline void
00159 pathset_h(HallInfo<IntType> hall[],
00160 IntType start, IntType end, IntType to) {
00161 IntType k, l;
00162 for (l=start; (k=l) != end; hall[k].h=to) {
00163 l = hall[k].h;
00164 }
00165 }
00166
00167 template<class IntType>
00168 forceinline IntType
00169 pathmin_h(const HallInfo<IntType> hall[], IntType i) {
00170 while (hall[i].h < i)
00171 i = hall[i].h;
00172 return i;
00173 }
00174
00175 template<class IntType>
00176 forceinline IntType
00177 pathmin_t(const HallInfo<IntType> hall[], IntType i) {
00178 while (hall[i].t < i)
00179 i = hall[i].t;
00180 return i;
00181 }
00182
00183 template<class IntType>
00184 forceinline IntType
00185 pathmax_h(const HallInfo<IntType> hall[], IntType i) {
00186 while (hall[i].h > i)
00187 i = hall[i].h;
00188 return i;
00189 }
00190
00191 template<class IntType>
00192 forceinline IntType
00193 pathmax_t(const HallInfo<IntType> hall[], IntType i) {
00194 while (hall[i].t > i)
00195 i = hall[i].t;
00196 return i;
00197 }
00198
00199 template<class View, class IntType>
00200 forceinline ExecStatus
00201 prop_bnd(Space& home, ViewArray<View>& x,
00202 int* minsorted, int* maxsorted) {
00203 const int n = x.size();
00204
00205 Region r(home);
00206
00207
00208 HallInfo<IntType>* hall = r.alloc<HallInfo<IntType> >(2*n+2);
00209 Rank* rank = r.alloc<Rank>(n);
00210
00211 int nb = 0;
00212 {
00213 IntType min = x[minsorted[0]].min();
00214 IntType max = x[maxsorted[0]].max() + 1;
00215 IntType last = min - 2;
00216
00217 hall[0].bounds = last;
00218
00219 int i = 0;
00220 int j = 0;
00221 while (true) {
00222 if ((i < n) && (min < max)) {
00223 if (min != last)
00224 hall[++nb].bounds = last = min;
00225 rank[minsorted[i]].min = nb;
00226 if (++i < n)
00227 min = x[minsorted[i]].min();
00228 } else {
00229 if (max != last)
00230 hall[++nb].bounds = last = max;
00231 rank[maxsorted[j]].max = nb;
00232 if (++j == n)
00233 break;
00234 max = x[maxsorted[j]].max() + 1;
00235 }
00236 }
00237 hall[nb+1].bounds = hall[nb].bounds + 2;
00238 }
00239
00240
00241 ExecStatus es = ES_FIX;
00242
00243
00244 for (int i=nb+2; --i;) {
00245 hall[i].t = hall[i].h = i-1;
00246 hall[i].d = hall[i].bounds - hall[i-1].bounds;
00247 }
00248 for (int i=0; i<n; i++) {
00249 IntType x0 = rank[maxsorted[i]].min;
00250 IntType z = pathmax_t(hall, x0+1);
00251 IntType j = hall[z].t;
00252 if (--hall[z].d == 0)
00253 hall[z = pathmax_t(hall, hall[z].t=z+1)].t = j;
00254 pathset_t(hall, x0+1, z, z);
00255 IntType y = rank[maxsorted[i]].max;
00256 if (hall[z].d < hall[z].bounds-hall[y].bounds)
00257 return ES_FAILED;
00258 if (hall[x0].h > x0) {
00259 IntType w = pathmax_h(hall, hall[x0].h);
00260 IntType m = hall[w].bounds;
00261 ModEvent me = x[maxsorted[i]].gq(home,m);
00262 if (me_failed(me))
00263 return ES_FAILED;
00264 if ((me == ME_INT_VAL) ||
00265 ((me == ME_INT_BND) && (m != x[maxsorted[i]].min())))
00266 es = ES_NOFIX;
00267 pathset_h(hall, x0, w, w);
00268 }
00269 if (hall[z].d == hall[z].bounds-hall[y].bounds) {
00270 pathset_h(hall, hall[y].h, j-1, y);
00271 hall[y].h = j-1;
00272 }
00273 }
00274
00275
00276 for (int i=nb+1; i--;) {
00277 hall[i].t = hall[i].h = i+1;
00278 hall[i].d = hall[i+1].bounds - hall[i].bounds;
00279 }
00280 for (int i=n; --i>=0; ) {
00281 IntType x0 = rank[minsorted[i]].max;
00282 IntType z = pathmin_t(hall, x0-1);
00283 IntType j = hall[z].t;
00284 if (--hall[z].d == 0)
00285 hall[z = pathmin_t(hall, hall[z].t=z-1)].t = j;
00286 pathset_t(hall, x0-1, z, z);
00287 IntType y = rank[minsorted[i]].min;
00288 if (hall[z].d < hall[y].bounds-hall[z].bounds)
00289 return ES_FAILED;
00290 if (hall[x0].h < x0) {
00291 IntType w = pathmin_h(hall, hall[x0].h);
00292 IntType m = hall[w].bounds - 1;
00293 ModEvent me = x[minsorted[i]].lq(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[y].bounds-hall[z].bounds) {
00302 pathset_h(hall, hall[y].h, j+1, y);
00303 hall[y].h = j+1;
00304 }
00305 }
00306
00307 return es;
00308 }
00309
00310 template<class View>
00311 forceinline ExecStatus
00312 prop_bnd(Space& home, ViewArray<View>& x, int& min_x, int& max_x) {
00313
00314 const int n = x.size();
00315
00316 Region r(home);
00317
00318 int* minsorted = r.alloc<int>(n);
00319 int* maxsorted = r.alloc<int>(n);
00320
00321 unsigned int d = static_cast<unsigned int>(max_x - min_x) + 1;
00322
00323 if (d < static_cast<unsigned int>(n))
00324 return ES_FAILED;
00325
00326 if (d > 2*static_cast<unsigned int>(n)) {
00327 for (int i = n; i--; )
00328 minsorted[i]=maxsorted[i]=i;
00329
00330 MinIncIdx<View> min_inc(x);
00331 Support::quicksort<int,MinIncIdx<View> >(minsorted, n, min_inc);
00332 MaxIncIdx<View> max_inc(x);
00333 Support::quicksort<int,MaxIncIdx<View> >(maxsorted, n, max_inc);
00334 } else {
00335
00336 int* minbucket = r.alloc<int>(d);
00337 int* maxbucket = r.alloc<int>(d);
00338 for (unsigned int i=d; i--; )
00339 minbucket[i]=maxbucket[i]=0;
00340
00341 for (int i=n; i--; ) {
00342 minbucket[x[i].min() - min_x]++;
00343 maxbucket[x[i].max() - min_x]++;
00344 }
00345
00346 int c_min = 0, c_max = 0;
00347 for (unsigned int i=0; i<d; i++) {
00348 int t_min = minbucket[i];
00349 int t_max = maxbucket[i];
00350 minbucket[i] = c_min; c_min += t_min;
00351 maxbucket[i] = c_max; c_max += t_max;
00352 }
00353 assert((c_min == n) && (c_max == n));
00354
00355 for (int i=n; i--; ) {
00356 minsorted[minbucket[x[i].min() - min_x]++] = i;
00357 maxsorted[maxbucket[x[i].max() - min_x]++] = i;
00358 }
00359 }
00360
00361
00362 min_x = x[minsorted[0]].min();
00363 max_x = x[maxsorted[n-1]].max();
00364
00365
00366 if (d > (static_cast<unsigned int>(Int::Limits::max) / 2U))
00367 return prop_bnd<View,long long int>(home,x,minsorted,maxsorted);
00368 else
00369 return prop_bnd<View,int>(home,x,minsorted,maxsorted);
00370 }
00371
00372 template<class View>
00373 ExecStatus
00374 prop_bnd(Space& home, ViewArray<View>& x) {
00375 int min = x[x.size()-1].min(), max = x[x.size()-1].max();
00376 for (int i=x.size()-1; i--; ) {
00377 min = std::min(min,x[i].min());
00378 max = std::max(max,x[i].max());
00379 }
00380 return prop_bnd(home, x, min, max);
00381 }
00382
00383 template<class View>
00384 ExecStatus
00385 Bnd<View>::propagate(Space& home, const ModEventDelta& med) {
00386 assert(x.size() > 1);
00387
00388 if (View::me(med) == ME_INT_VAL) {
00389 ExecStatus es = prop_val<View,false>(home,y);
00390 GECODE_ES_CHECK(es);
00391 if (y.size() < 2)
00392 return home.ES_SUBSUMED(*this);
00393 if (es == ES_FIX)
00394 return home.ES_FIX_PARTIAL(*this,View::med(ME_INT_BND));
00395 }
00396
00397 if (y.size() == 2)
00398 GECODE_REWRITE(*this,(Rel::Nq<View,View>::post(home(*this),y[0],y[1])));
00399
00400 ExecStatus es = prop_bnd<View>(home,x,min_x,max_x);
00401
00402 GECODE_ES_CHECK(es);
00403 if (es == ES_NOFIX && View::me(modeventdelta()) == ME_INT_VAL)
00404 return es;
00405
00406 const int n = x.size();
00407
00408 if ((n > 2*y.size()) && (n > 6)) {
00409
00410 unsigned int d = static_cast<unsigned int>(max_x - min_x) + 1;
00411 if (d > 2*static_cast<unsigned int>(n)) {
00412 MinInc<View> min_inc;
00413 Support::quicksort<View,MinInc<View> >(&x[0], n, min_inc);
00414 } else {
00415 Region r(home);
00416 int* minbucket = r.alloc<int>(d);
00417 View* minsorted = r.alloc<View>(n);
00418
00419 for (unsigned int i=d; i--; )
00420 minbucket[i]=0;
00421 for (int i=n; i--; )
00422 minbucket[x[i].min() - min_x]++;
00423
00424 int c_min = 0;
00425 for (unsigned int i=0; i<d; i++) {
00426 int t_min = minbucket[i];
00427 minbucket[i] = c_min; c_min += t_min;
00428 }
00429 assert(c_min == n);
00430
00431 for (int i=n; i--;)
00432 minsorted[minbucket[x[i].min() - min_x]++] = x[i];
00433 for (int i=n; i--;)
00434 x[i] = minsorted[i];
00435 }
00436
00437 int i = 0;
00438 int j = 0;
00439 int max = x[0].max()-1;
00440 while (i < n-1) {
00441 if (!x[i].assigned() ||
00442 (x[i].val() <= max) || (x[i].val() > x[i+1].min())) {
00443
00444 max = std::max(max,x[i].max());
00445 x[j++]=x[i];
00446 }
00447 i++;
00448 }
00449 if (!x[i].assigned() || (x[i].val() <= max))
00450 x[j++]=x[i];
00451 x.size(j);
00452 }
00453
00454 if (x.size() < 2)
00455 return home.ES_SUBSUMED(*this);
00456
00457 if (x.size() == 2)
00458 GECODE_REWRITE(*this,(Rel::Nq<View,View>::post(home(*this),x[0],x[1])));
00459
00460 return es;
00461 }
00462
00463 template<class View>
00464 ExecStatus
00465 Bnd<View>::post(Home home, ViewArray<View>& x){
00466 if (x.size() == 2)
00467 return Rel::Nq<View,View>::post(home,x[0],x[1]);
00468 if (x.size() > 2)
00469 (void) new (home) Bnd<View>(home,x);
00470 return ES_OK;
00471 }
00472
00473 }}}
00474
00475
00476