Generated on Thu Jul 6 07:06:43 2006 for Gecode by doxygen 1.4.7

view.icc

Go to the documentation of this file.
00001 /*
00002  *  Main authors:
00003  *     Christian Schulte <schulte@gecode.org>
00004  *
00005  *  Contributing authors:
00006  *     Guido Tack <tack@gecode.org>
00007  *
00008  *  Copyright:
00009  *     Christian Schulte, 2004
00010  *     Guido Tack, 2004
00011  *
00012  *  Last modified:
00013  *     $Date: 2006-05-29 09:42:21 +0200 (Mon, 29 May 2006) $ by $Author: schulte $
00014  *     $Revision: 3246 $
00015  *
00016  *  This file is part of Gecode, the generic constraint
00017  *  development environment:
00018  *     http://www.gecode.org
00019  *
00020  *  See the file "LICENSE" for information on usage and
00021  *  redistribution of this file, and for a
00022  *     DISCLAIMER OF ALL WARRANTIES.
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    * Base class
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     // 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 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    * Generic scanning: does all but computing new domain for result
00205    * (which is specific to bounds/domain version)
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      * Prunes pairs of index, variable
00216      *  - checks for idx value removed
00217      *  - checks for disequal variables
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    * Bounds-consistent propagator
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     // Compute new result
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    * Domain consistent propagator
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       // Compute new result
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 // STATISTICS: int-prop
00442