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 }
00240 ++vx0; ++i;
00241 }
00242 }
00243 while (i < n)
00244 iv[i++].view.cancel(home,p,pcb);
00245 bool adjust = (j<n);
00246 n = j;
00247
00248 if (n == 0)
00249 return;
00250
00251 if (n == 1) {
00252 (void) x0.eq(home,iv[0].idx);
00253 } else if (adjust) {
00254 IterIdxView<ViewA> i(&iv[0],&iv[n]);
00255 Iter::Values::ToRanges<IterIdxView<ViewA> > ri(i);
00256 (void) x0.narrow(home,ri);
00257 assert(x0.size() == static_cast<unsigned int>(n));
00258 }
00259 }
00260
00261
00262
00263
00264
00265
00266
00267
00268
00269 template <class ViewA, class ViewB>
00270 forceinline
00271 ViewBnd<ViewA,ViewB>::ViewBnd(Space* home,
00272 IdxView<ViewB>* iv, int n, ViewA x0, ViewB x1)
00273 : View<ViewA,ViewB,PC_INT_BND>(home,iv,n,x0,x1) {}
00274
00275 template <class ViewA, class ViewB>
00276 ExecStatus
00277 ViewBnd<ViewA,ViewB>::post(Space* home,
00278 IdxView<ViewB>* iv, int n, ViewA x0, ViewB x1) {
00279 GECODE_ME_CHECK(x0.gq(home,0));
00280 GECODE_ME_CHECK(x0.le(home,n));
00281 if (x0.assigned()) {
00282 return Rel::EqBnd<ViewB,ViewB>::post(home,iv[x0.val()].view,x1);
00283 } else {
00284 assert(n>1);
00285 (void) new (home) ViewBnd<ViewA,ViewB>(home,iv,n,x0,x1);
00286 }
00287 return ES_OK;
00288 }
00289
00290
00291 template <class ViewA, class ViewB>
00292 forceinline
00293 ViewBnd<ViewA,ViewB>::ViewBnd(Space* home, bool share, ViewBnd& p)
00294 : View<ViewA,ViewB,PC_INT_BND>(home,share,p) {}
00295
00296 template <class ViewA, class ViewB>
00297 Actor*
00298 ViewBnd<ViewA,ViewB>::copy(Space* home, bool share) {
00299 return new (home) ViewBnd<ViewA,ViewB>(home,share,*this);
00300 }
00301
00302
00303 template <class ViewA, class ViewB>
00304 ExecStatus
00305 ViewBnd<ViewA,ViewB>::propagate(Space* home) {
00306 assert(n > 1);
00307 RelTestBnd<ViewB> rt;
00308 scan<ViewA,ViewB,PC_INT_BND,RelTestBnd<ViewB> >
00309 (home,iv,n,x0,x1,this,rt);
00310 if (n == 0)
00311 return ES_FAILED;
00312 if (n == 1) {
00313 GECODE_ES_CHECK((Rel::EqBnd<ViewB,ViewB>::post(home,iv[0].view,x1)));
00314 return ES_SUBSUMED;
00315 }
00316 assert(n > 1);
00317
00318 int min = iv[n-1].view.min();
00319 int max = iv[n-1].view.max();
00320 for (int i=n-1; i--; ) {
00321 min = std::min(iv[i].view.min(),min);
00322 max = std::max(iv[i].view.max(),max);
00323 }
00324 ExecStatus es = shared(x0,x1) ? ES_NOFIX : ES_FIX;
00325 {
00326 ModEvent me = x1.lq(home,max);
00327 if (me_failed(me))
00328 return ES_FAILED;
00329 if (me_modified(me) && (x1.max() != max))
00330 es = ES_NOFIX;
00331 }
00332 {
00333 ModEvent me = x1.gq(home,min);
00334 if (me_failed(me))
00335 return ES_FAILED;
00336 if (me_modified(me) && (x1.min() != min))
00337 es = ES_NOFIX;
00338 }
00339 return (x1.assigned() && (min == max)) ? ES_SUBSUMED : es;
00340 }
00341
00342
00343
00344
00345
00346
00347
00348
00349
00350
00351 template <class ViewA, class ViewB>
00352 forceinline
00353 ViewDom<ViewA,ViewB>::ViewDom(Space* home,
00354 IdxView<ViewB>* iv, int n, ViewA x0, ViewB x1)
00355 : View<ViewA,ViewB,PC_INT_DOM>(home,iv,n,x0,x1) {}
00356
00357 template <class ViewA, class ViewB>
00358 ExecStatus
00359 ViewDom<ViewA,ViewB>::post(Space* home,
00360 IdxView<ViewB>* iv, int n, ViewA x0, ViewB x1){
00361 GECODE_ME_CHECK(x0.gq(home,0));
00362 GECODE_ME_CHECK(x0.le(home,n));
00363 if (x0.assigned()) {
00364 return Rel::EqDom<ViewB,ViewB>::post(home,iv[x0.val()].view,x1);
00365 } else {
00366 assert(n>1);
00367 (void) new (home) ViewDom<ViewA,ViewB>(home,iv,n,x0,x1);
00368 }
00369 return ES_OK;
00370 }
00371
00372
00373 template <class ViewA, class ViewB>
00374 forceinline
00375 ViewDom<ViewA,ViewB>::ViewDom(Space* home, bool share, ViewDom& p)
00376 : View<ViewA,ViewB,PC_INT_DOM>(home,share,p) {}
00377
00378 template <class ViewA, class ViewB>
00379 Actor*
00380 ViewDom<ViewA,ViewB>::copy(Space* home, bool share) {
00381 return new (home) ViewDom<ViewA,ViewB>(home,share,*this);
00382 }
00383
00384
00385 template <class ViewA, class ViewB>
00386 PropCost
00387 ViewDom<ViewA,ViewB>::cost(void) const {
00388 if (ViewA::pme(this) != ME_INT_DOM)
00389 return PC_LINEAR_LO;
00390 else
00391 return PC_LINEAR_HI;
00392 }
00393
00394 template <class ViewA, class ViewB>
00395 ExecStatus
00396 ViewDom<ViewA,ViewB>::propagate(Space* home) {
00397 assert(n > 1);
00398 if (ViewA::pme(this) != ME_INT_DOM) {
00399 RelTestBnd<ViewB> rt;
00400 scan<ViewA,ViewB,PC_INT_DOM,RelTestBnd<ViewB> >
00401 (home,iv,n,x0,x1,this,rt);
00402 if (n == 0)
00403 return ES_FAILED;
00404 if (n == 1) {
00405 GECODE_ES_CHECK((Rel::EqDom<ViewB,ViewB>::post(home,iv[0].view,x1)));
00406 return ES_SUBSUMED;
00407 }
00408
00409 int min = iv[n-1].view.min();
00410 int max = iv[n-1].view.max();
00411 for (int i=n-1; i--; ) {
00412 min = std::min(iv[i].view.min(),min);
00413 max = std::max(iv[i].view.max(),max);
00414 }
00415 GECODE_ME_CHECK(x1.lq(home,max));
00416 GECODE_ME_CHECK(x1.gq(home,min));
00417 return (x1.assigned() && (min == max)) ?
00418 ES_SUBSUMED :
00419 this->ES_NOFIX_PARTIAL(ViewA::pme(ME_INT_DOM));
00420 }
00421 RelTestDom<ViewB> rt;
00422 scan<ViewA,ViewB,PC_INT_DOM,RelTestDom<ViewB> >
00423 (home,iv,n,x0,x1,this,rt);
00424 if (n == 0)
00425 return ES_FAILED;
00426 if (n == 1) {
00427 GECODE_ES_CHECK((Rel::EqDom<ViewB,ViewB>::post(home,iv[0].view,x1)));
00428 return ES_SUBSUMED;
00429 }
00430 assert(n > 1);
00431 GECODE_AUTOARRAY(ViewRanges<ViewB>,i_view,n);
00432 for (int i = n; i--; )
00433 i_view[i].init(iv[i].view);
00434 Iter::Ranges::NaryUnion<ViewRanges<ViewB> > i_val(i_view, n);
00435 GECODE_ME_CHECK(x1.inter(home,i_val));
00436 return x1.modified() ? ES_NOFIX : ES_FIX;
00437 }
00438
00439 }}}
00440
00441
00442