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