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