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
00039
00040
00041
00042 #include <algorithm>
00043
00044 namespace Gecode { namespace Int { namespace Element {
00045
00050 template<class VA, class VC>
00051 class RelTestBnd {
00052 public:
00053 RelTest operator ()(VA,VC);
00054 };
00059 template<class VA>
00060 class RelTestBnd<VA,ConstIntView> {
00061 public:
00062 RelTest operator ()(VA,ConstIntView);
00063 };
00064
00069 template<class VA, class VC>
00070 class RelTestDom {
00071 public:
00072 RelTest operator ()(VA,VC);
00073 };
00078 template<class VA>
00079 class RelTestDom<VA,ConstIntView> {
00080 public:
00081 RelTest operator ()(VA,ConstIntView);
00082 };
00083
00084
00085 template<class VA, class VC>
00086 forceinline RelTest
00087 RelTestBnd<VA,VC>::operator ()(VA x, VC y) {
00088 return rtest_eq_bnd(x,y);
00089 }
00090 template<class VA>
00091 forceinline RelTest
00092 RelTestBnd<VA,ConstIntView>::operator ()(VA x, ConstIntView y) {
00093 return rtest_eq_bnd(x,y.val());
00094 }
00095
00096 template<class VA, class VC>
00097 forceinline RelTest
00098 RelTestDom<VA,VC>::operator ()(VA x, VC y) {
00099 return rtest_eq_dom(x,y);
00100 }
00101 template<class VA>
00102 forceinline RelTest
00103 RelTestDom<VA,ConstIntView>::operator ()(VA x, ConstIntView y) {
00104 return rtest_eq_dom(x,y.val());
00105 }
00106
00107
00108
00109
00110
00111
00112
00113
00114
00115 template<class VA, class VB, class VC, PropCond pc_ac>
00116 View<VA,VB,VC,pc_ac>::View(Home home, IdxViewArray<VA>& iv0,
00117 VB y0, VC y1)
00118 : Propagator(home), iv(iv0), x0(y0), x1(y1) {
00119 x0.subscribe(home,*this,PC_INT_DOM);
00120 x1.subscribe(home,*this,pc_ac);
00121 iv.subscribe(home,*this,pc_ac);
00122 }
00123
00124 template<class VA, class VB, class VC, PropCond pc_ac>
00125 forceinline
00126 View<VA,VB,VC,pc_ac>::View(Space& home, bool share, View& p)
00127 : Propagator(home,share,p) {
00128 x0.update(home,share,p.x0);
00129 x1.update(home,share,p.x1);
00130 iv.update(home,share,p.iv);
00131 }
00132
00133 template<class VA, class VB, class VC, PropCond pc_ac>
00134 PropCost
00135 View<VA,VB,VC,pc_ac>::cost(const Space&, const ModEventDelta&) const {
00136
00137
00138
00139 return PropCost::linear(PropCost::LO,iv.size()+2);
00140 }
00141
00142 template<class VA, class VB, class VC, PropCond pc_ac>
00143 forceinline size_t
00144 View<VA,VB,VC,pc_ac>::dispose(Space& home) {
00145 x0.cancel(home,*this,PC_INT_DOM);
00146 x1.cancel(home,*this,pc_ac);
00147 iv.cancel(home,*this,pc_ac);
00148 (void) Propagator::dispose(home);
00149 return sizeof(*this);
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 VA, class VB, class VC, PropCond pc_ac, class RelTest>
00212 ExecStatus
00213 scan(Space& home, IdxViewArray<VA>& iv,
00214 VB x0, VC x1, Propagator& p, RelTest rt) {
00215 assert(iv.size() > 1);
00216
00217
00218
00219
00220
00221
00222 ViewValues<VB> vx0(x0);
00223 int i = 0;
00224 int j = 0;
00225 while (vx0() && (i < iv.size())) {
00226 if (iv[i].idx < vx0.val()) {
00227 iv[i].view.cancel(home,p,pc_ac);
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(home,p,pc_ac);
00236 break;
00237 case RT_TRUE:
00238 case RT_MAYBE:
00239 iv[j++] = iv[i];
00240 break;
00241 default: GECODE_NEVER;
00242 }
00243 ++vx0; ++i;
00244 }
00245 }
00246 while (i < iv.size())
00247 iv[i++].view.cancel(home,p,pc_ac);
00248 bool adjust = (j<iv.size());
00249 iv.size(j);
00250
00251 if (iv.size() == 0)
00252 return ES_FAILED;
00253
00254 if (iv.size() == 1) {
00255 GECODE_ME_CHECK(x0.eq(home,iv[0].idx));
00256 } else if (adjust) {
00257 IterIdxView<VA> v(&iv[0],&iv[0]+iv.size());
00258 GECODE_ME_CHECK(x0.narrow_v(home,v,false));
00259 assert(x0.size() == static_cast<unsigned int>(iv.size()));
00260 }
00261 return ES_OK;
00262 }
00263
00264
00265
00266
00267
00268
00269
00270
00271
00272 template<class VA, class VB, class VC>
00273 forceinline
00274 ViewBnd<VA,VB,VC>::ViewBnd(Home home,
00275 IdxViewArray<VA>& iv, VB x0, VC x1)
00276 : View<VA,VB,VC,PC_INT_BND>(home,iv,x0,x1) {}
00277
00278 template<class VA, class VB, class VC>
00279 ExecStatus
00280 ViewBnd<VA,VB,VC>::post(Home home,
00281 IdxViewArray<VA>& iv, VB x0, VC x1) {
00282 GECODE_ME_CHECK(x0.gq(home,0));
00283 GECODE_ME_CHECK(x0.le(home,iv.size()));
00284 if (x0.assigned()) {
00285 (void) new (home) Rel::EqBnd<VA,VC>(home,iv[x0.val()].view,x1);
00286 return ES_OK;
00287 } else {
00288 assert(iv.size()>1);
00289 (void) new (home) ViewBnd<VA,VB,VC>(home,iv,x0,x1);
00290 }
00291 return ES_OK;
00292 }
00293
00294
00295 template<class VA, class VB, class VC>
00296 forceinline
00297 ViewBnd<VA,VB,VC>::ViewBnd(Space& home, bool share, ViewBnd& p)
00298 : View<VA,VB,VC,PC_INT_BND>(home,share,p) {}
00299
00300 template<class VA, class VB, class VC>
00301 Actor*
00302 ViewBnd<VA,VB,VC>::copy(Space& home, bool share) {
00303 return new (home) ViewBnd<VA,VB,VC>(home,share,*this);
00304 }
00305
00306 template<class VA, class VB, class VC>
00307 ExecStatus
00308 ViewBnd<VA,VB,VC>::propagate(Space& home, const ModEventDelta&) {
00309 assert(iv.size() > 1);
00310 RelTestBnd<VA,VC> rt;
00311 GECODE_ES_CHECK((scan<VA,VB,VC,PC_INT_BND,RelTestBnd<VA,VC> >
00312 (home,iv,x0,x1,*this,rt)));
00313 if (iv.size() == 1) {
00314 ExecStatus es = home.ES_SUBSUMED(*this);
00315 (void) new (home) Rel::EqBnd<VA,VC>(home,iv[0].view,x1);
00316 return es;
00317 }
00318 assert(iv.size() > 1);
00319
00320 int min = iv[iv.size()-1].view.min();
00321 int max = iv[iv.size()-1].view.max();
00322 for (int i=iv.size()-1; i--; ) {
00323 min = std::min(iv[i].view.min(),min);
00324 max = std::max(iv[i].view.max(),max);
00325 }
00326 ExecStatus es = shared(x0,x1) ? ES_NOFIX : ES_FIX;
00327 {
00328 ModEvent me = x1.lq(home,max);
00329 if (me_failed(me))
00330 return ES_FAILED;
00331 if (me_modified(me) && (x1.max() != max))
00332 es = ES_NOFIX;
00333 }
00334 {
00335 ModEvent me = x1.gq(home,min);
00336 if (me_failed(me))
00337 return ES_FAILED;
00338 if (me_modified(me) && (x1.min() != min))
00339 es = ES_NOFIX;
00340 }
00341 return (x1.assigned() && (min == max)) ?
00342 home.ES_SUBSUMED(*this) : es;
00343 }
00344
00345
00346
00347
00348
00349
00350
00351
00352
00353
00354 template<class VA, class VB, class VC>
00355 forceinline
00356 ViewDom<VA,VB,VC>::ViewDom(Home home,
00357 IdxViewArray<VA>& iv, VB x0, VC x1)
00358 : View<VA,VB,VC,PC_INT_DOM>(home,iv,x0,x1) {}
00359
00360 template<class VA, class VB, class VC>
00361 ExecStatus
00362 ViewDom<VA,VB,VC>::post(Home home,
00363 IdxViewArray<VA>& iv, VB x0, VC x1){
00364 GECODE_ME_CHECK(x0.gq(home,0));
00365 GECODE_ME_CHECK(x0.le(home,iv.size()));
00366 if (x0.assigned()) {
00367 (void) new (home) Rel::EqDom<VA,VC>(home,iv[x0.val()].view,x1);
00368 return ES_OK;
00369 } else {
00370 assert(iv.size()>1);
00371 (void) new (home) ViewDom<VA,VB,VC>(home,iv,x0,x1);
00372 }
00373 return ES_OK;
00374 }
00375
00376
00377 template<class VA, class VB, class VC>
00378 forceinline
00379 ViewDom<VA,VB,VC>::ViewDom(Space& home, bool share, ViewDom& p)
00380 : View<VA,VB,VC,PC_INT_DOM>(home,share,p) {}
00381
00382 template<class VA, class VB, class VC>
00383 Actor*
00384 ViewDom<VA,VB,VC>::copy(Space& home, bool share) {
00385 return new (home) ViewDom<VA,VB,VC>(home,share,*this);
00386 }
00387
00388
00389 template<class VA, class VB, class VC>
00390 PropCost
00391 ViewDom<VA,VB,VC>::cost(const Space&, const ModEventDelta& med) const {
00392 return PropCost::linear((VA::me(med) != ME_INT_DOM) ?
00393 PropCost::LO : PropCost::HI, iv.size()+2);
00394 }
00395
00396 template<class VA, class VB, class VC>
00397 ExecStatus
00398 ViewDom<VA,VB,VC>::propagate(Space& home, const ModEventDelta& med) {
00399 assert(iv.size() > 1);
00400 if (VA::me(med) != ME_INT_DOM) {
00401 RelTestBnd<VA,VC> rt;
00402 GECODE_ES_CHECK((scan<VA,VB,VC,PC_INT_DOM,RelTestBnd<VA,VC> >
00403 (home,iv,x0,x1,*this,rt)));
00404 if (iv.size() == 1) {
00405 ExecStatus es = home.ES_SUBSUMED(*this);
00406 (void) new (home) Rel::EqDom<VA,VC>(home,iv[0].view,x1);
00407 return es;
00408 }
00409
00410 int min = iv[iv.size()-1].view.min();
00411 int max = iv[iv.size()-1].view.max();
00412 for (int i=iv.size()-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 home.ES_SUBSUMED(*this) :
00420 home.ES_NOFIX_PARTIAL(*this,VA::med(ME_INT_DOM));
00421 }
00422 RelTestDom<VA,VC> rt;
00423 GECODE_ES_CHECK((scan<VA,VB,VC,PC_INT_DOM,RelTestDom<VA,VC> >
00424 (home,iv,x0,x1,*this,rt)));
00425 if (iv.size() == 1) {
00426 ExecStatus es = home.ES_SUBSUMED(*this);
00427 (void) new (home) Rel::EqDom<VA,VC>(home,iv[0].view,x1);
00428 return es;
00429 }
00430 assert(iv.size() > 1);
00431
00432 if (x1.assigned()) {
00433 for (int i = iv.size(); i--; )
00434 if (iv[i].view.in(x1.val()))
00435 return shared(x0,x1) ? ES_NOFIX : ES_FIX;
00436 return ES_FAILED;
00437 } else {
00438 Region r(home);
00439 ViewRanges<VA>* i_view = r.alloc<ViewRanges<VA> >(iv.size());
00440 for (int i = iv.size(); i--; )
00441 i_view[i].init(iv[i].view);
00442 Iter::Ranges::NaryUnion i_val(r, i_view, iv.size());
00443 ModEvent me = x1.inter_r(home,i_val);
00444 r.free<ViewRanges<VA> >(i_view,iv.size());
00445 GECODE_ME_CHECK(me);
00446 return (shared(x0,x1) || me_modified(me)) ? ES_NOFIX : ES_FIX;
00447 }
00448 }
00449
00450 }}}
00451
00452
00453