00001
00002
00003
00004
00005
00006
00007
00008
00009
00010
00011
00012
00013
00014
00015
00016
00017
00018
00019
00020
00021
00022 #include "gecode/support/sort.hh"
00023
00024 namespace Gecode { namespace Int { namespace Distinct {
00025
00026 template <class View>
00027 inline
00028 Bnd<View>::Bnd(Space* home, ViewArray<View>& x0)
00029 : Propagator(home), x(x0), y(home,x0) {
00030
00031
00032
00033
00034
00035 y.subscribe(home,this,PC_INT_BND);
00036 }
00037
00038 template <class View>
00039 size_t
00040 Bnd<View>::dispose(Space* home) {
00041 assert(!home->failed());
00042 y.cancel(home,this,PC_INT_BND);
00043 (void) Propagator::dispose(home);
00044 return sizeof(*this);
00045 }
00046
00047 template <class View>
00048 forceinline
00049 Bnd<View>::Bnd(Space* home, bool share, Bnd<View>& p)
00050 : Propagator(home,share,p) {
00051 x.update(home,share,p.x);
00052 y.update(home,share,p.y);
00053 }
00054
00055 template <class View>
00056 Actor*
00057 Bnd<View>::copy(Space* home, bool share) {
00058 return new (home) Bnd<View>(home,share,*this);
00059 }
00060
00061 template <class View>
00062 PropCost
00063 Bnd<View>::cost(void) const {
00064 return (View::pme(this) == ME_INT_VAL)
00065 ? cost_lo(y.size(),PC_LINEAR_LO)
00066 : cost_hi(x.size(),PC_LINEAR_HI);
00067 }
00068
00069
00071 class Rank {
00072 public:
00073 int min, max;
00074 };
00075
00077 template <class View>
00078 class MaxInc {
00079 protected:
00080 ViewArray<View> x;
00081 public:
00082 MaxInc(const ViewArray<View>& x0) : x(x0) {}
00083 forceinline bool
00084 operator()(const int i, const int j) {
00085 return x[i].max() < x[j].max();
00086 }
00087 };
00088
00090 template <class View>
00091 class MinInc {
00092 public:
00093 forceinline bool
00094 operator()(const View& x, const View& y) {
00095 return x.min() < y.min();
00096 }
00097 };
00098
00100 class HallInfo {
00101 public:
00102 int bounds, t, d, h;
00103 };
00104
00105 inline void
00106 pathset_t(HallInfo hall[], int start, int end, int to) {
00107 int k, l;
00108 for (l=start; (k=l) != end; hall[k].t=to) {
00109 l = hall[k].t;
00110 }
00111 }
00112
00113 inline void
00114 pathset_h(HallInfo hall[], int start, int end, int to) {
00115 int k, l;
00116 for (l=start; (k=l) != end; hall[k].h=to) {
00117 l = hall[k].h;
00118 }
00119 }
00120
00121 forceinline int
00122 pathmin_h(const HallInfo hall[], int i) {
00123 while (hall[i].h < i)
00124 i = hall[i].h;
00125 return i;
00126 }
00127
00128 forceinline int
00129 pathmin_t(const HallInfo hall[], int i) {
00130 while (hall[i].t < i)
00131 i = hall[i].t;
00132 return i;
00133 }
00134
00135 forceinline int
00136 pathmax_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 pathmax_t(const HallInfo hall[], int i) {
00144 while (hall[i].t > i)
00145 i = hall[i].t;
00146 return i;
00147 }
00148
00149 #define minsorted(i) (i)
00150 #define maxsorted(i) (_maxsorted[i])
00151
00152 template <class View>
00153 ExecStatus
00154 prop_bnd(Space* home, ViewArray<View>& x) {
00155
00156 MinInc<View> min_inc;
00157 Support::insertion<View,MinInc<View> >(&x[0], x.size(), min_inc);
00158
00159 const int n = x.size();
00160
00161 GECODE_AUTOARRAY(int, _maxsorted, n);
00162 for (int i = n; i--; )
00163 _maxsorted[i]=i;
00164
00165 MaxInc<View> max_inc(x);
00166 Support::insertion<int,MaxInc<View> >(_maxsorted, n, max_inc);
00167
00168
00169 GECODE_AUTOARRAY(HallInfo, hall, 2*n+2);
00170 GECODE_AUTOARRAY(Rank, rank, n);
00171
00172 int nb = 0;
00173 {
00174 int min = x[minsorted(0)].min();
00175 int max = x[maxsorted(0)].max() + 1;
00176 int last = min - 2;
00177
00178 hall[0].bounds = last;
00179
00180 int i = 0;
00181 int j = 0;
00182 while (true) {
00183 if (i < n && min < max) {
00184 if (min != last)
00185 hall[++nb].bounds = last = min;
00186 rank[minsorted(i)].min = nb;
00187 if (++i < n)
00188 min = x[minsorted(i)].min();
00189 } else {
00190 if (max != last)
00191 hall[++nb].bounds = last = max;
00192 rank[maxsorted(j)].max = nb;
00193 if (++j == n)
00194 break;
00195 max = x[maxsorted(j)].max() + 1;
00196 }
00197 }
00198 hall[nb+1].bounds = hall[nb].bounds + 2;
00199 }
00200
00201
00202 ExecStatus es = ES_FIX;
00203
00204
00205 for (int i=nb+2; --i;) {
00206 hall[i].t = hall[i].h = i-1;
00207 hall[i].d = hall[i].bounds - hall[i-1].bounds;
00208 }
00209 for (int i=0; i<n; i++) {
00210 int x0 = rank[maxsorted(i)].min;
00211 int z = pathmax_t(hall, x0+1);
00212 int j = hall[z].t;
00213 if (--hall[z].d == 0)
00214 hall[z = pathmax_t(hall, hall[z].t=z+1)].t = j;
00215 pathset_t(hall, x0+1, z, z);
00216 int y = rank[maxsorted(i)].max;
00217 if (hall[z].d < hall[z].bounds-hall[y].bounds)
00218 return ES_FAILED;
00219 if (hall[x0].h > x0) {
00220 int w = pathmax_h(hall, hall[x0].h);
00221 int m = hall[w].bounds;
00222 ModEvent me = x[maxsorted(i)].gq(home,m);
00223 if (me_failed(me))
00224 return ES_FAILED;
00225 if (me_modified(me) && (m != x[maxsorted(i)].min()))
00226 es = ES_NOFIX;
00227 pathset_h(hall, x0, w, w);
00228 }
00229 if (hall[z].d == hall[z].bounds-hall[y].bounds) {
00230 pathset_h(hall, hall[y].h, j-1, y);
00231 hall[y].h = j-1;
00232 }
00233 }
00234
00235
00236 for (int i=nb+1; i--;) {
00237 hall[i].t = hall[i].h = i+1;
00238 hall[i].d = hall[i+1].bounds - hall[i].bounds;
00239 }
00240 for (int i=n; --i>=0; ) {
00241 int x0 = rank[minsorted(i)].max;
00242 int z = pathmin_t(hall, x0-1);
00243 int j = hall[z].t;
00244 if (--hall[z].d == 0)
00245 hall[z = pathmin_t(hall, hall[z].t=z-1)].t = j;
00246 pathset_t(hall, x0-1, z, z);
00247 int y = rank[minsorted(i)].min;
00248 if (hall[z].d < hall[y].bounds-hall[z].bounds)
00249 return ES_FAILED;
00250 if (hall[x0].h < x0) {
00251 int w = pathmin_h(hall, hall[x0].h);
00252 int m = hall[w].bounds - 1;
00253 ModEvent me = x[minsorted(i)].lq(home,m);
00254 if (me_failed(me))
00255 return ES_FAILED;
00256 if (me_modified(me) && (m != x[minsorted(i)].max()))
00257 es = ES_NOFIX;
00258 pathset_h(hall, x0, w, w);
00259 }
00260 if (hall[z].d == hall[y].bounds-hall[z].bounds) {
00261 pathset_h(hall, hall[y].h, j+1, y);
00262 hall[y].h = j+1;
00263 }
00264 }
00265
00266 return es;
00267 }
00268
00269 #undef minsorted
00270 #undef maxsorted
00271
00272 template <class View>
00273 ExecStatus
00274 Bnd<View>::propagate(Space* home) {
00275 assert(x.size() > 1);
00276
00277 if (View::pme(this) == ME_INT_VAL) {
00278 ExecStatus es = prop_val<View,false>(home,y);
00279 if ((es == ES_FAILED) || (es == ES_SUBSUMED))
00280 return es;
00281 if (es == ES_FIX)
00282 return ES_FIX_PARTIAL(View::pme(ME_INT_BND));
00283 }
00284
00285 if (y.size() == 2) {
00286 GECODE_ES_CHECK(Rel::Nq<View>::post(home,y[0],y[1]));
00287 return ES_SUBSUMED;
00288 }
00289
00290 return prop_bnd<View>(home,x);
00291 }
00292
00293 template <class View>
00294 ExecStatus
00295 Bnd<View>::post(Space* home, ViewArray<View>& x){
00296 if (x.size() == 2)
00297 return Rel::Nq<View>::post(home,x[0],x[1]);
00298 if (x.size() > 2)
00299 (void) new (home) Bnd<View>(home,x);
00300 return ES_OK;
00301 }
00302
00303
00304 }}}
00305
00306
00307