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 }
00051
00052 template<class View>
00053 forceinline size_t
00054 Bnd<View>::dispose(Space& home) {
00055 y.cancel(home,*this,PC_INT_BND);
00056 (void) Propagator::dispose(home);
00057 return sizeof(*this);
00058 }
00059
00060 template<class View>
00061 forceinline
00062 Bnd<View>::Bnd(Space& home, bool share, Bnd<View>& p)
00063 : Propagator(home,share,p) {
00064 x.update(home,share,p.x);
00065 y.update(home,share,p.y);
00066 }
00067
00068 template<class View>
00069 Actor*
00070 Bnd<View>::copy(Space& home, bool share) {
00071 return new (home) Bnd<View>(home,share,*this);
00072 }
00073
00074 template<class View>
00075 PropCost
00076 Bnd<View>::cost(const Space&, const ModEventDelta& med) const {
00077 if (View::me(med) == ME_INT_VAL)
00078 return PropCost::linear(PropCost::LO, y.size());
00079 else
00080 return PropCost::quadratic(PropCost::LO, x.size());
00081 }
00082
00083
00085 class Rank {
00086 public:
00087 int min, max;
00088 };
00089
00091 template<class View>
00092 class MaxInc {
00093 protected:
00094 ViewArray<View> x;
00095 public:
00096 MaxInc(const ViewArray<View>& x0) : x(x0) {}
00097 forceinline bool
00098 operator ()(const int i, const int j) {
00099 return x[i].max() < x[j].max();
00100 }
00101 };
00102
00104 template<class View>
00105 class MinInc {
00106 public:
00107 forceinline bool
00108 operator ()(const View& x, const View& y) {
00109 return x.min() < y.min();
00110 }
00111 };
00112
00114 class HallInfo {
00115 public:
00116 int bounds, t, d, h;
00117 };
00118
00119 forceinline void
00120 pathset_t(HallInfo hall[], int start, int end, int to) {
00121 int k, l;
00122 for (l=start; (k=l) != end; hall[k].t=to) {
00123 l = hall[k].t;
00124 }
00125 }
00126
00127 forceinline void
00128 pathset_h(HallInfo hall[], int start, int end, int to) {
00129 int k, l;
00130 for (l=start; (k=l) != end; hall[k].h=to) {
00131 l = hall[k].h;
00132 }
00133 }
00134
00135 forceinline int
00136 pathmin_h(const HallInfo hall[], int i) {
00137 while (hall[i].h < i)
00138 i = hall[i].h;
00139 return i;
00140 }
00141
00142 forceinline int
00143 pathmin_t(const HallInfo hall[], int i) {
00144 while (hall[i].t < i)
00145 i = hall[i].t;
00146 return i;
00147 }
00148
00149 forceinline int
00150 pathmax_h(const HallInfo hall[], int i) {
00151 while (hall[i].h > i)
00152 i = hall[i].h;
00153 return i;
00154 }
00155
00156 forceinline int
00157 pathmax_t(const HallInfo hall[], int i) {
00158 while (hall[i].t > i)
00159 i = hall[i].t;
00160 return i;
00161 }
00162
00163 #define GECODE_INT_MINSORTED(i) (i)
00164 #define GECODE_INT_MAXSORTED(i) (_maxsorted[i])
00165
00166 template<class View>
00167 ExecStatus
00168 prop_bnd(Space& home, ViewArray<View>& x) {
00169 const int n = x.size();
00170
00171 {
00172 MinInc<View> min_inc;
00173 Support::insertion<View,MinInc<View> >(&x[0], n, min_inc);
00174 }
00175
00176 Region r(home);
00177
00178 int* _maxsorted = r.alloc<int>(n);
00179
00180 for (int i = n; i--; )
00181 _maxsorted[i]=i;
00182
00183 {
00184 MaxInc<View> max_inc(x);
00185 Support::insertion<int,MaxInc<View> >(_maxsorted, n, max_inc);
00186 }
00187
00188
00189 HallInfo* hall = r.alloc<HallInfo>(2*n+2);
00190 Rank* rank = r.alloc<Rank>(n);
00191
00192 int nb = 0;
00193 {
00194 int min = x[GECODE_INT_MINSORTED(0)].min();
00195 int max = x[GECODE_INT_MAXSORTED(0)].max() + 1;
00196 int last = min - 2;
00197
00198 hall[0].bounds = last;
00199
00200 int i = 0;
00201 int j = 0;
00202 while (true) {
00203 if ((i < n) && (min < max)) {
00204 if (min != last)
00205 hall[++nb].bounds = last = min;
00206 rank[GECODE_INT_MINSORTED(i)].min = nb;
00207 if (++i < n)
00208 min = x[GECODE_INT_MINSORTED(i)].min();
00209 } else {
00210 if (max != last)
00211 hall[++nb].bounds = last = max;
00212 rank[GECODE_INT_MAXSORTED(j)].max = nb;
00213 if (++j == n)
00214 break;
00215 max = x[GECODE_INT_MAXSORTED(j)].max() + 1;
00216 }
00217 }
00218 hall[nb+1].bounds = hall[nb].bounds + 2;
00219 }
00220
00221
00222 ExecStatus es = ES_FIX;
00223
00224
00225 for (int i=nb+2; --i;) {
00226 hall[i].t = hall[i].h = i-1;
00227 hall[i].d = hall[i].bounds - hall[i-1].bounds;
00228 }
00229 for (int i=0; i<n; i++) {
00230 int x0 = rank[GECODE_INT_MAXSORTED(i)].min;
00231 int z = pathmax_t(hall, x0+1);
00232 int j = hall[z].t;
00233 if (--hall[z].d == 0)
00234 hall[z = pathmax_t(hall, hall[z].t=z+1)].t = j;
00235 pathset_t(hall, x0+1, z, z);
00236 int y = rank[GECODE_INT_MAXSORTED(i)].max;
00237 if (hall[z].d < hall[z].bounds-hall[y].bounds)
00238 return ES_FAILED;
00239 if (hall[x0].h > x0) {
00240 int w = pathmax_h(hall, hall[x0].h);
00241 int m = hall[w].bounds;
00242 ModEvent me = x[GECODE_INT_MAXSORTED(i)].gq(home,m);
00243 if (me_failed(me))
00244 return ES_FAILED;
00245 if ((me == ME_INT_VAL) ||
00246 ((me == ME_INT_BND) && (m != x[GECODE_INT_MAXSORTED(i)].min())))
00247 es = ES_NOFIX;
00248 pathset_h(hall, x0, w, w);
00249 }
00250 if (hall[z].d == hall[z].bounds-hall[y].bounds) {
00251 pathset_h(hall, hall[y].h, j-1, y);
00252 hall[y].h = j-1;
00253 }
00254 }
00255
00256
00257 for (int i=nb+1; i--;) {
00258 hall[i].t = hall[i].h = i+1;
00259 hall[i].d = hall[i+1].bounds - hall[i].bounds;
00260 }
00261 for (int i=n; --i>=0; ) {
00262 int x0 = rank[GECODE_INT_MINSORTED(i)].max;
00263 int z = pathmin_t(hall, x0-1);
00264 int j = hall[z].t;
00265 if (--hall[z].d == 0)
00266 hall[z = pathmin_t(hall, hall[z].t=z-1)].t = j;
00267 pathset_t(hall, x0-1, z, z);
00268 int y = rank[GECODE_INT_MINSORTED(i)].min;
00269 if (hall[z].d < hall[y].bounds-hall[z].bounds)
00270 return ES_FAILED;
00271 if (hall[x0].h < x0) {
00272 int w = pathmin_h(hall, hall[x0].h);
00273 int m = hall[w].bounds - 1;
00274 ModEvent me = x[GECODE_INT_MINSORTED(i)].lq(home,m);
00275 if (me_failed(me))
00276 return ES_FAILED;
00277 if ((me == ME_INT_VAL) ||
00278 ((me == ME_INT_BND) && (m != x[GECODE_INT_MAXSORTED(i)].min())))
00279 es = ES_NOFIX;
00280 pathset_h(hall, x0, w, w);
00281 }
00282 if (hall[z].d == hall[y].bounds-hall[z].bounds) {
00283 pathset_h(hall, hall[y].h, j+1, y);
00284 hall[y].h = j+1;
00285 }
00286 }
00287
00288 return es;
00289 }
00290
00291 #undef GECODE_INT_MINSORTED
00292 #undef GECODE_INT_MAXSORTED
00293
00294 template<class View>
00295 ExecStatus
00296 Bnd<View>::propagate(Space& home, const ModEventDelta& med) {
00297 assert(x.size() > 1);
00298
00299 if (View::me(med) == ME_INT_VAL) {
00300 ExecStatus es = prop_val<View,false>(home,y);
00301 GECODE_ES_CHECK(es);
00302 if (y.size() < 2)
00303 return home.ES_SUBSUMED(*this);
00304 if (es == ES_FIX)
00305 return home.ES_FIX_PARTIAL(*this,View::med(ME_INT_BND));
00306 }
00307
00308 if (y.size() == 2)
00309 GECODE_REWRITE(*this,Rel::Nq<View>::post(home(*this),y[0],y[1]));
00310
00311 ExecStatus es = prop_bnd<View>(home,x);
00312
00313 GECODE_ES_CHECK(es);
00314
00315 const int n = x.size();
00316
00317 if ((n > 2*y.size()) && (n > 6)) {
00318
00319 MinInc<View> min_inc;
00320 Support::insertion<View,MinInc<View> >(&x[0], n, min_inc);
00321 int i = 0;
00322 int j = 0;
00323 int max = x[0].max()-1;
00324 while (i < n-1) {
00325 if (!x[i].assigned() ||
00326 (x[i].val() <= max) || (x[i].val() > x[i+1].min())) {
00327
00328 max = std::max(max,x[i].max());
00329 x[j++]=x[i];
00330 }
00331 i++;
00332 }
00333 if (!x[i].assigned() || (x[i].val() <= max))
00334 x[j++]=x[i];
00335 x.size(j);
00336 }
00337
00338 if (x.size() < 2)
00339 return home.ES_SUBSUMED(*this);
00340
00341 if (x.size() == 2)
00342 GECODE_REWRITE(*this,Rel::Nq<View>::post(home(*this),x[0],x[1]));
00343
00344 return es;
00345 }
00346
00347 template<class View>
00348 ExecStatus
00349 Bnd<View>::post(Home home, ViewArray<View>& x){
00350 if (x.size() == 2)
00351 return Rel::Nq<View>::post(home,x[0],x[1]);
00352 if (x.size() > 2)
00353 (void) new (home) Bnd<View>(home,x);
00354 return ES_OK;
00355 }
00356
00357 }}}
00358
00359
00360