Generated on Thu Apr 11 13:59:01 2019 for Gecode by doxygen 1.6.3

view.hpp

Go to the documentation of this file.
00001 /* -*- mode: C++; c-basic-offset: 2; indent-tabs-mode: nil -*- */
00002 /*
00003  *  Main authors:
00004  *     Christian Schulte <schulte@gecode.org>
00005  *
00006  *  Contributing authors:
00007  *     Guido Tack <tack@gecode.org>
00008  *
00009  *  Copyright:
00010  *     Christian Schulte, 2004
00011  *     Guido Tack, 2004
00012  *
00013  *  This file is part of Gecode, the generic constraint
00014  *  development environment:
00015  *     http://www.gecode.org
00016  *
00017  *  Permission is hereby granted, free of charge, to any person obtaining
00018  *  a copy of this software and associated documentation files (the
00019  *  "Software"), to deal in the Software without restriction, including
00020  *  without limitation the rights to use, copy, modify, merge, publish,
00021  *  distribute, sublicense, and/or sell copies of the Software, and to
00022  *  permit persons to whom the Software is furnished to do so, subject to
00023  *  the following conditions:
00024  *
00025  *  The above copyright notice and this permission notice shall be
00026  *  included in all copies or substantial portions of the Software.
00027  *
00028  *  THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,
00029  *  EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF
00030  *  MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND
00031  *  NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE
00032  *  LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION
00033  *  OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION
00034  *  WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
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    * Base class
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     // This is required for subscribing to variables in the
00133     // above constructor, but this is then the only time this
00134     // virtual function is ever used!
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    * Generic scanning: does all but computing new domain for result
00211    * (which is specific to bounds/domain version)
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      * Prunes pairs of index, variable
00222      *  - checks for idx value removed
00223      *  - checks for disequal variables
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    * Bounds consistent propagator
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     // Compute new result
00324     int min = iv[0].view.min();
00325     int max = iv[0].view.max();
00326     for (int i=1; i<iv.size(); 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    * Domain consistent propagator
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       // Compute new result
00414       int min = iv[0].view.min();
00415       int max = iv[0].view.max();
00416       for (int i=1; i<iv.size(); 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=0; 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=0; 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 // STATISTICS: int-prop
00457