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