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