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 #include <algorithm>
00027
00028 #include "gecode/iter.hh"
00029
00030 namespace Gecode { namespace Int { namespace Element {
00031
00036 template <class View>
00037 class IdxView {
00038 public:
00039 int idx; View view;
00040
00041 static IdxView* allocate(Space*, int);
00042 static IdxView* init(Space*, const IntVarArgs&);
00043 };
00044
00045
00046 template <class View>
00047 forceinline IdxView<View>*
00048 IdxView<View>::allocate(Space* home, int n) {
00049 return reinterpret_cast<IdxView<View>*>
00050 (home->alloc(sizeof(IdxView<View>)*n));
00051 }
00052
00053 template <class View>
00054 forceinline IdxView<View>*
00055 IdxView<View>::init(Space* home, const IntVarArgs& x) {
00056 IdxView<View>* iv = allocate(home,x.size());
00057 for (int i = x.size(); i--; ) {
00058 iv[i].idx = i; iv[i].view = x[i];
00059 }
00060 return iv;
00061 }
00062
00063
00064
00069 template <class View>
00070 class RelTestBnd {
00071 public:
00072 RelTest operator()(View,View);
00073 };
00074
00079 template <class View>
00080 class RelTestDom {
00081 public:
00082 RelTest operator()(View,View);
00083 };
00084
00085
00086 template <class View>
00087 forceinline RelTest
00088 RelTestBnd<View>::operator()(View x, View y) {
00089 return rtest_eq_bnd(x,y);
00090 }
00091
00092 template <class View>
00093 forceinline RelTest
00094 RelTestDom<View>::operator()(View x, View y) {
00095 return rtest_eq_dom(x,y);
00096 }
00097
00098
00099
00100
00101
00102
00103
00104
00105
00106 template <class ViewA, class ViewB, PropCond pcb>
00107 View<ViewA,ViewB,pcb>::View(Space* home, IdxView<ViewB>* iv0, int n0,
00108 ViewA y0, ViewB y1)
00109 : Propagator(home), x0(y0), x1(y1), n(n0), iv(iv0) {
00110 x0.subscribe(home,this,PC_INT_DOM);
00111 x1.subscribe(home,this,pcb);
00112 for (int i=n; i--; )
00113 iv[i].view.subscribe(home,this,pcb);
00114 }
00115
00116 template <class ViewA, class ViewB, PropCond pcb>
00117 forceinline
00118 View<ViewA,ViewB,pcb>::View(Space* home, bool share, View& p)
00119 : Propagator(home,share,p), n(p.n) {
00120 x0.update(home,share,p.x0);
00121 x1.update(home,share,p.x1);
00122 iv = IdxView<ViewB>::allocate(home,n);
00123 for (int i=n; i--; ) {
00124 iv[i].idx = p.iv[i].idx;
00125 iv[i].view.update(home,share,p.iv[i].view);
00126 }
00127 }
00128
00129 template <class ViewA, class ViewB, PropCond pcb>
00130 PropCost
00131 View<ViewA,ViewB,pcb>::cost(void) const {
00132
00133
00134
00135 return PC_LINEAR_LO;
00136 }
00137
00138 template <class ViewA, class ViewB, PropCond pcb>
00139 size_t
00140 View<ViewA,ViewB,pcb>::dispose(Space* home) {
00141 assert(!home->failed());
00142 x0.cancel(home,this,PC_INT_DOM);
00143 x1.cancel(home,this,pcb);
00144 for (int i=n; i--;)
00145 iv[i].view.cancel(home,this,pcb);
00146 (void) Propagator::dispose(home);
00147 return sizeof(*this);
00148 }
00149
00150
00151
00152
00157 template <class View>
00158 class IterIdxView {
00159 private:
00160 const IdxView<View> *cur, *end;
00161 public:
00162 IterIdxView(void);
00163 IterIdxView(const IdxView<View>*, const IdxView<View>*);
00164 void init(const IdxView<View>*, const IdxView<View>*);
00165 bool operator()(void) const;
00166 void operator++(void);
00167 int val(void) const;
00168 };
00169
00170 template <class View>
00171 forceinline
00172 IterIdxView<View>::IterIdxView(void) {}
00173 template <class View>
00174 forceinline
00175 IterIdxView<View>::IterIdxView(const IdxView<View>* b,
00176 const IdxView<View>* e)
00177 : cur(b), end(e) {}
00178 template <class View>
00179 forceinline void
00180 IterIdxView<View>::init(const IdxView<View>* b,
00181 const IdxView<View>* e) {
00182 cur=b; end=e;
00183 }
00184 template <class View>
00185 forceinline bool
00186 IterIdxView<View>::operator()(void) const {
00187 return cur < end;
00188 }
00189 template <class View>
00190 forceinline void
00191 IterIdxView<View>::operator++(void) {
00192 cur++;
00193 }
00194 template <class View>
00195 forceinline int
00196 IterIdxView<View>::val(void) const {
00197 return cur->idx;
00198 }
00199
00200
00201
00202
00203
00204
00205
00206
00207
00208
00209 template <class ViewA, class ViewB, PropCond pcb, class RelTest>
00210 void
00211 scan(Space* home, IdxView<ViewB>* iv, int& n,
00212 ViewA x0, ViewB x1, Propagator* p, RelTest rt) {
00213 assert(n > 1);
00214
00215
00216
00217
00218
00219
00220 ViewValues<ViewA> vx0(x0);
00221 int i = 0;
00222 int j = 0;
00223 while (vx0() && (i < n)) {
00224 if (iv[i].idx < vx0.val()) {
00225 iv[i].view.cancel(home,p,pcb);
00226 ++i;
00227 } else if (iv[i].idx > vx0.val()) {
00228 ++vx0;
00229 } else {
00230 assert(iv[i].idx == vx0.val());
00231 switch (rt(iv[i].view,x1)) {
00232 case RT_FALSE:
00233 iv[i].view.cancel(home,p,pcb);
00234 break;
00235 case RT_TRUE:
00236 case RT_MAYBE:
00237 iv[j++] = iv[i];
00238 break;
00239 default: GECODE_NEVER;
00240 }
00241 ++vx0; ++i;
00242 }
00243 }
00244 while (i < n)
00245 iv[i++].view.cancel(home,p,pcb);
00246 bool adjust = (j<n);
00247 n = j;
00248
00249 if (n == 0)
00250 return;
00251
00252 if (n == 1) {
00253 (void) x0.eq(home,iv[0].idx);
00254 } else if (adjust) {
00255 IterIdxView<ViewA> i(&iv[0],&iv[n]);
00256 Iter::Values::ToRanges<IterIdxView<ViewA> > ri(i);
00257 (void) x0.narrow(home,ri);
00258 assert(x0.size() == static_cast<unsigned int>(n));
00259 }
00260 }
00261
00262
00263
00264
00265
00266
00267
00268
00269
00270 template <class ViewA, class ViewB>
00271 forceinline
00272 ViewBnd<ViewA,ViewB>::ViewBnd(Space* home,
00273 IdxView<ViewB>* iv, int n, ViewA x0, ViewB x1)
00274 : View<ViewA,ViewB,PC_INT_BND>(home,iv,n,x0,x1) {}
00275
00276 template <class ViewA, class ViewB>
00277 ExecStatus
00278 ViewBnd<ViewA,ViewB>::post(Space* home,
00279 IdxView<ViewB>* iv, int n, ViewA x0, ViewB x1) {
00280 GECODE_ME_CHECK(x0.gq(home,0));
00281 GECODE_ME_CHECK(x0.le(home,n));
00282 if (x0.assigned()) {
00283 return Rel::EqBnd<ViewB,ViewB>::post(home,iv[x0.val()].view,x1);
00284 } else {
00285 assert(n>1);
00286 (void) new (home) ViewBnd<ViewA,ViewB>(home,iv,n,x0,x1);
00287 }
00288 return ES_OK;
00289 }
00290
00291
00292 template <class ViewA, class ViewB>
00293 forceinline
00294 ViewBnd<ViewA,ViewB>::ViewBnd(Space* home, bool share, ViewBnd& p)
00295 : View<ViewA,ViewB,PC_INT_BND>(home,share,p) {}
00296
00297 template <class ViewA, class ViewB>
00298 Actor*
00299 ViewBnd<ViewA,ViewB>::copy(Space* home, bool share) {
00300 return new (home) ViewBnd<ViewA,ViewB>(home,share,*this);
00301 }
00302
00303
00304 template <class ViewA, class ViewB>
00305 ExecStatus
00306 ViewBnd<ViewA,ViewB>::propagate(Space* home) {
00307 assert(n > 1);
00308 RelTestBnd<ViewB> rt;
00309 scan<ViewA,ViewB,PC_INT_BND,RelTestBnd<ViewB> >
00310 (home,iv,n,x0,x1,this,rt);
00311 if (n == 0)
00312 return ES_FAILED;
00313 if (n == 1) {
00314 GECODE_ES_CHECK((Rel::EqBnd<ViewB,ViewB>::post(home,iv[0].view,x1)));
00315 return ES_SUBSUMED;
00316 }
00317 assert(n > 1);
00318
00319 int min = iv[n-1].view.min();
00320 int max = iv[n-1].view.max();
00321 for (int i=n-1; i--; ) {
00322 min = std::min(iv[i].view.min(),min);
00323 max = std::max(iv[i].view.max(),max);
00324 }
00325 ExecStatus es = shared(x0,x1) ? ES_NOFIX : ES_FIX;
00326 {
00327 ModEvent me = x1.lq(home,max);
00328 if (me_failed(me))
00329 return ES_FAILED;
00330 if (me_modified(me) && (x1.max() != max))
00331 es = ES_NOFIX;
00332 }
00333 {
00334 ModEvent me = x1.gq(home,min);
00335 if (me_failed(me))
00336 return ES_FAILED;
00337 if (me_modified(me) && (x1.min() != min))
00338 es = ES_NOFIX;
00339 }
00340 return (x1.assigned() && (min == max)) ? ES_SUBSUMED : es;
00341 }
00342
00343
00344
00345
00346
00347
00348
00349
00350
00351
00352 template <class ViewA, class ViewB>
00353 forceinline
00354 ViewDom<ViewA,ViewB>::ViewDom(Space* home,
00355 IdxView<ViewB>* iv, int n, ViewA x0, ViewB x1)
00356 : View<ViewA,ViewB,PC_INT_DOM>(home,iv,n,x0,x1) {}
00357
00358 template <class ViewA, class ViewB>
00359 ExecStatus
00360 ViewDom<ViewA,ViewB>::post(Space* home,
00361 IdxView<ViewB>* iv, int n, ViewA x0, ViewB x1){
00362 GECODE_ME_CHECK(x0.gq(home,0));
00363 GECODE_ME_CHECK(x0.le(home,n));
00364 if (x0.assigned()) {
00365 return Rel::EqDom<ViewB,ViewB>::post(home,iv[x0.val()].view,x1);
00366 } else {
00367 assert(n>1);
00368 (void) new (home) ViewDom<ViewA,ViewB>(home,iv,n,x0,x1);
00369 }
00370 return ES_OK;
00371 }
00372
00373
00374 template <class ViewA, class ViewB>
00375 forceinline
00376 ViewDom<ViewA,ViewB>::ViewDom(Space* home, bool share, ViewDom& p)
00377 : View<ViewA,ViewB,PC_INT_DOM>(home,share,p) {}
00378
00379 template <class ViewA, class ViewB>
00380 Actor*
00381 ViewDom<ViewA,ViewB>::copy(Space* home, bool share) {
00382 return new (home) ViewDom<ViewA,ViewB>(home,share,*this);
00383 }
00384
00385
00386 template <class ViewA, class ViewB>
00387 PropCost
00388 ViewDom<ViewA,ViewB>::cost(void) const {
00389 if (ViewA::pme(this) != ME_INT_DOM)
00390 return PC_LINEAR_LO;
00391 else
00392 return PC_LINEAR_HI;
00393 }
00394
00395 template <class ViewA, class ViewB>
00396 ExecStatus
00397 ViewDom<ViewA,ViewB>::propagate(Space* home) {
00398 assert(n > 1);
00399 if (ViewA::pme(this) != ME_INT_DOM) {
00400 RelTestBnd<ViewB> rt;
00401 scan<ViewA,ViewB,PC_INT_DOM,RelTestBnd<ViewB> >
00402 (home,iv,n,x0,x1,this,rt);
00403 if (n == 0)
00404 return ES_FAILED;
00405 if (n == 1) {
00406 GECODE_ES_CHECK((Rel::EqDom<ViewB,ViewB>::post(home,iv[0].view,x1)));
00407 return ES_SUBSUMED;
00408 }
00409
00410 int min = iv[n-1].view.min();
00411 int max = iv[n-1].view.max();
00412 for (int i=n-1; i--; ) {
00413 min = std::min(iv[i].view.min(),min);
00414 max = std::max(iv[i].view.max(),max);
00415 }
00416 GECODE_ME_CHECK(x1.lq(home,max));
00417 GECODE_ME_CHECK(x1.gq(home,min));
00418 return (x1.assigned() && (min == max)) ?
00419 ES_SUBSUMED :
00420 this->ES_NOFIX_PARTIAL(ViewA::pme(ME_INT_DOM));
00421 }
00422 RelTestDom<ViewB> rt;
00423 scan<ViewA,ViewB,PC_INT_DOM,RelTestDom<ViewB> >
00424 (home,iv,n,x0,x1,this,rt);
00425 if (n == 0)
00426 return ES_FAILED;
00427 if (n == 1) {
00428 GECODE_ES_CHECK((Rel::EqDom<ViewB,ViewB>::post(home,iv[0].view,x1)));
00429 return ES_SUBSUMED;
00430 }
00431 assert(n > 1);
00432 GECODE_AUTOARRAY(ViewRanges<ViewB>,i_view,n);
00433 for (int i = n; i--; )
00434 i_view[i].init(iv[i].view);
00435 Iter::Ranges::NaryUnion<ViewRanges<ViewB> > i_val(i_view, n);
00436 GECODE_ME_CHECK(x1.inter(home,i_val));
00437 return x1.modified() ? ES_NOFIX : ES_FIX;
00438 }
00439
00440 }}}
00441
00442
00443