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 void
00144 View<VA,VB,VC,pc_ac>::reschedule(Space& home) {
00145 x0.reschedule(home,*this,PC_INT_DOM);
00146 x1.reschedule(home,*this,pc_ac);
00147 iv.reschedule(home,*this,pc_ac);
00148 }
00149
00150 template<class VA, class VB, class VC, PropCond pc_ac>
00151 forceinline size_t
00152 View<VA,VB,VC,pc_ac>::dispose(Space& home) {
00153 x0.cancel(home,*this,PC_INT_DOM);
00154 x1.cancel(home,*this,pc_ac);
00155 iv.cancel(home,*this,pc_ac);
00156 (void) Propagator::dispose(home);
00157 return sizeof(*this);
00158 }
00159
00160
00161
00162
00167 template<class View>
00168 class IterIdxView {
00169 private:
00170 const IdxView<View> *cur, *end;
00171 public:
00172 IterIdxView(void);
00173 IterIdxView(const IdxView<View>*, const IdxView<View>*);
00174 void init(const IdxView<View>*, const IdxView<View>*);
00175 bool operator ()(void) const;
00176 void operator ++(void);
00177 int val(void) const;
00178 };
00179
00180 template<class View>
00181 forceinline
00182 IterIdxView<View>::IterIdxView(void) {}
00183 template<class View>
00184 forceinline
00185 IterIdxView<View>::IterIdxView(const IdxView<View>* b,
00186 const IdxView<View>* e)
00187 : cur(b), end(e) {}
00188 template<class View>
00189 forceinline void
00190 IterIdxView<View>::init(const IdxView<View>* b,
00191 const IdxView<View>* e) {
00192 cur=b; end=e;
00193 }
00194 template<class View>
00195 forceinline bool
00196 IterIdxView<View>::operator ()(void) const {
00197 return cur < end;
00198 }
00199 template<class View>
00200 forceinline void
00201 IterIdxView<View>::operator ++(void) {
00202 cur++;
00203 }
00204 template<class View>
00205 forceinline int
00206 IterIdxView<View>::val(void) const {
00207 return cur->idx;
00208 }
00209
00210
00211
00212
00213
00214
00215
00216
00217
00218
00219 template<class VA, class VB, class VC, PropCond pc_ac, class RelTest>
00220 ExecStatus
00221 scan(Space& home, IdxViewArray<VA>& iv,
00222 VB x0, VC x1, Propagator& p, RelTest rt) {
00223 assert(iv.size() > 1);
00224
00225
00226
00227
00228
00229
00230 ViewValues<VB> vx0(x0);
00231 int i = 0;
00232 int j = 0;
00233 while (vx0() && (i < iv.size())) {
00234 if (iv[i].idx < vx0.val()) {
00235 iv[i].view.cancel(home,p,pc_ac);
00236 ++i;
00237 } else if (iv[i].idx > vx0.val()) {
00238 ++vx0;
00239 } else {
00240 assert(iv[i].idx == vx0.val());
00241 switch (rt(iv[i].view,x1)) {
00242 case RT_FALSE:
00243 iv[i].view.cancel(home,p,pc_ac);
00244 break;
00245 case RT_TRUE:
00246 case RT_MAYBE:
00247 iv[j++] = iv[i];
00248 break;
00249 default: GECODE_NEVER;
00250 }
00251 ++vx0; ++i;
00252 }
00253 }
00254 while (i < iv.size())
00255 iv[i++].view.cancel(home,p,pc_ac);
00256 bool adjust = (j<iv.size());
00257 iv.size(j);
00258
00259 if (iv.size() == 0)
00260 return ES_FAILED;
00261
00262 if (iv.size() == 1) {
00263 GECODE_ME_CHECK(x0.eq(home,iv[0].idx));
00264 } else if (adjust) {
00265 IterIdxView<VA> v(&iv[0],&iv[0]+iv.size());
00266 GECODE_ME_CHECK(x0.narrow_v(home,v,false));
00267 assert(x0.size() == static_cast<unsigned int>(iv.size()));
00268 }
00269 return ES_OK;
00270 }
00271
00272
00273
00274
00275
00276
00277
00278
00279
00280 template<class VA, class VB, class VC>
00281 forceinline
00282 ViewBnd<VA,VB,VC>::ViewBnd(Home home,
00283 IdxViewArray<VA>& iv, VB x0, VC x1)
00284 : View<VA,VB,VC,PC_INT_BND>(home,iv,x0,x1) {}
00285
00286 template<class VA, class VB, class VC>
00287 ExecStatus
00288 ViewBnd<VA,VB,VC>::post(Home home,
00289 IdxViewArray<VA>& iv, VB x0, VC x1) {
00290 GECODE_ME_CHECK(x0.gq(home,0));
00291 GECODE_ME_CHECK(x0.le(home,iv.size()));
00292 if (x0.assigned()) {
00293 (void) new (home) Rel::EqBnd<VA,VC>(home,iv[x0.val()].view,x1);
00294 return ES_OK;
00295 } else {
00296 assert(iv.size()>1);
00297 (void) new (home) ViewBnd<VA,VB,VC>(home,iv,x0,x1);
00298 }
00299 return ES_OK;
00300 }
00301
00302
00303 template<class VA, class VB, class VC>
00304 forceinline
00305 ViewBnd<VA,VB,VC>::ViewBnd(Space& home, bool share, ViewBnd& p)
00306 : View<VA,VB,VC,PC_INT_BND>(home,share,p) {}
00307
00308 template<class VA, class VB, class VC>
00309 Actor*
00310 ViewBnd<VA,VB,VC>::copy(Space& home, bool share) {
00311 return new (home) ViewBnd<VA,VB,VC>(home,share,*this);
00312 }
00313
00314 template<class VA, class VB, class VC>
00315 ExecStatus
00316 ViewBnd<VA,VB,VC>::propagate(Space& home, const ModEventDelta&) {
00317 assert(iv.size() > 1);
00318 RelTestBnd<VA,VC> rt;
00319 GECODE_ES_CHECK((scan<VA,VB,VC,PC_INT_BND,RelTestBnd<VA,VC> >
00320 (home,iv,x0,x1,*this,rt)));
00321 if (iv.size() == 1) {
00322 ExecStatus es = home.ES_SUBSUMED(*this);
00323 (void) new (home) Rel::EqBnd<VA,VC>(home(*this),iv[0].view,x1);
00324 return es;
00325 }
00326 assert(iv.size() > 1);
00327
00328 int min = iv[iv.size()-1].view.min();
00329 int max = iv[iv.size()-1].view.max();
00330 for (int i=iv.size()-1; i--; ) {
00331 min = std::min(iv[i].view.min(),min);
00332 max = std::max(iv[i].view.max(),max);
00333 }
00334 ExecStatus es = shared(x0,x1) ? ES_NOFIX : ES_FIX;
00335 {
00336 ModEvent me = x1.lq(home,max);
00337 if (me_failed(me))
00338 return ES_FAILED;
00339 if (me_modified(me) && (x1.max() != max))
00340 es = ES_NOFIX;
00341 }
00342 {
00343 ModEvent me = x1.gq(home,min);
00344 if (me_failed(me))
00345 return ES_FAILED;
00346 if (me_modified(me) && (x1.min() != min))
00347 es = ES_NOFIX;
00348 }
00349 return (x1.assigned() && (min == max)) ?
00350 home.ES_SUBSUMED(*this) : es;
00351 }
00352
00353
00354
00355
00356
00357
00358
00359
00360
00361
00362 template<class VA, class VB, class VC>
00363 forceinline
00364 ViewDom<VA,VB,VC>::ViewDom(Home home,
00365 IdxViewArray<VA>& iv, VB x0, VC x1)
00366 : View<VA,VB,VC,PC_INT_DOM>(home,iv,x0,x1) {}
00367
00368 template<class VA, class VB, class VC>
00369 ExecStatus
00370 ViewDom<VA,VB,VC>::post(Home home,
00371 IdxViewArray<VA>& iv, VB x0, VC x1){
00372 GECODE_ME_CHECK(x0.gq(home,0));
00373 GECODE_ME_CHECK(x0.le(home,iv.size()));
00374 if (x0.assigned()) {
00375 (void) new (home) Rel::EqDom<VA,VC>(home,iv[x0.val()].view,x1);
00376 return ES_OK;
00377 } else {
00378 assert(iv.size()>1);
00379 (void) new (home) ViewDom<VA,VB,VC>(home,iv,x0,x1);
00380 }
00381 return ES_OK;
00382 }
00383
00384
00385 template<class VA, class VB, class VC>
00386 forceinline
00387 ViewDom<VA,VB,VC>::ViewDom(Space& home, bool share, ViewDom& p)
00388 : View<VA,VB,VC,PC_INT_DOM>(home,share,p) {}
00389
00390 template<class VA, class VB, class VC>
00391 Actor*
00392 ViewDom<VA,VB,VC>::copy(Space& home, bool share) {
00393 return new (home) ViewDom<VA,VB,VC>(home,share,*this);
00394 }
00395
00396
00397 template<class VA, class VB, class VC>
00398 PropCost
00399 ViewDom<VA,VB,VC>::cost(const Space&, const ModEventDelta& med) const {
00400 return PropCost::linear((VA::me(med) != ME_INT_DOM) ?
00401 PropCost::LO : PropCost::HI, iv.size()+2);
00402 }
00403
00404 template<class VA, class VB, class VC>
00405 ExecStatus
00406 ViewDom<VA,VB,VC>::propagate(Space& home, const ModEventDelta& med) {
00407 assert(iv.size() > 1);
00408 if (VA::me(med) != ME_INT_DOM) {
00409 RelTestBnd<VA,VC> rt;
00410 GECODE_ES_CHECK((scan<VA,VB,VC,PC_INT_DOM,RelTestBnd<VA,VC> >
00411 (home,iv,x0,x1,*this,rt)));
00412 if (iv.size() == 1) {
00413 ExecStatus es = home.ES_SUBSUMED(*this);
00414 (void) new (home) Rel::EqDom<VA,VC>(home(*this),iv[0].view,x1);
00415 return es;
00416 }
00417
00418 int min = iv[iv.size()-1].view.min();
00419 int max = iv[iv.size()-1].view.max();
00420 for (int i=iv.size()-1; i--; ) {
00421 min = std::min(iv[i].view.min(),min);
00422 max = std::max(iv[i].view.max(),max);
00423 }
00424 GECODE_ME_CHECK(x1.lq(home,max));
00425 GECODE_ME_CHECK(x1.gq(home,min));
00426 return (x1.assigned() && (min == max)) ?
00427 home.ES_SUBSUMED(*this) :
00428 home.ES_NOFIX_PARTIAL(*this,VA::med(ME_INT_DOM));
00429 }
00430 RelTestDom<VA,VC> rt;
00431 GECODE_ES_CHECK((scan<VA,VB,VC,PC_INT_DOM,RelTestDom<VA,VC> >
00432 (home,iv,x0,x1,*this,rt)));
00433 if (iv.size() == 1) {
00434 ExecStatus es = home.ES_SUBSUMED(*this);
00435 (void) new (home) Rel::EqDom<VA,VC>(home(*this),iv[0].view,x1);
00436 return es;
00437 }
00438 assert(iv.size() > 1);
00439
00440 if (x1.assigned()) {
00441 for (int i = iv.size(); i--; )
00442 if (iv[i].view.in(x1.val()))
00443 return shared(x0,x1) ? ES_NOFIX : ES_FIX;
00444 return ES_FAILED;
00445 } else {
00446 Region r(home);
00447 ViewRanges<VA>* i_view = r.alloc<ViewRanges<VA> >(iv.size());
00448 for (int i = iv.size(); i--; )
00449 i_view[i].init(iv[i].view);
00450 Iter::Ranges::NaryUnion i_val(r, i_view, iv.size());
00451 ModEvent me = x1.inter_r(home,i_val);
00452 r.free<ViewRanges<VA> >(i_view,iv.size());
00453 GECODE_ME_CHECK(me);
00454 return (shared(x0,x1) || me_modified(me)) ? ES_NOFIX : ES_FIX;
00455 }
00456 }
00457
00458 }}}
00459
00460
00461