Generated on Wed Jan 4 17:49:09 2006 for Gecode by doxygen 1.4.6

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: 2005-11-22 10:50:38 +0100 (Tue, 22 Nov 2005) $ by $Author: schulte $
00014  *     $Revision: 2612 $
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 "iter.hh"
00029 
00030 #ifdef NDEBUG
00031 #define GECODE_ASSERTION_VARIABLE(c)
00032 #else
00033 #define GECODE_ASSERTION_VARIABLE(c) c
00034 #endif
00035 
00036 namespace Gecode { namespace Int { namespace Element {
00037 
00042   template <class View>
00043   class IdxView {
00044   public:
00045     int idx; View view;
00046 
00047     static IdxView* allocate(Space*, int);
00048     static IdxView* init(Space*, const IntVarArgs&);
00049   };
00050 
00051 
00052   template <class View>
00053   forceinline IdxView<View>*
00054   IdxView<View>::allocate(Space* home, int n) {
00055       return reinterpret_cast<IdxView<View>*>
00056         (home->alloc(sizeof(IdxView<View>)*n));
00057     }
00058 
00059   template <class View>
00060   forceinline IdxView<View>*
00061   IdxView<View>::init(Space* home, const IntVarArgs& x) {
00062     IdxView<View>* iv = allocate(home,x.size());
00063     for (int i = x.size(); i--; ) {
00064       iv[i].idx = i; iv[i].view = x[i];
00065     }
00066     return iv;
00067   }
00068 
00069 
00070 
00075   template <class View>
00076   class RelTestBnd {
00077   public:
00078     RelTest operator()(View,View);
00079   };
00080 
00085   template <class View>
00086   class RelTestDom {
00087   public:
00088     RelTest operator()(View,View);
00089   };
00090 
00091 
00092   template <class View>
00093   forceinline RelTest
00094   RelTestBnd<View>::operator()(View x, View y) {
00095     return rtest_eq_bnd(x,y);
00096   }
00097 
00098   template <class View>
00099   forceinline RelTest
00100   RelTestDom<View>::operator()(View x, View y) {
00101     return rtest_eq_dom(x,y);
00102   }
00103 
00104 
00105 
00106 
00107   /*
00108    * Base class
00109    *
00110    */
00111 
00112   template <class ViewA, class ViewB, PropCond pcb>
00113   View<ViewA,ViewB,pcb>::View(Space* home, IdxView<ViewB>* iv0, int n0,
00114                               ViewA y0, ViewB y1)
00115     : Propagator(home), x0(y0), x1(y1), n(n0), iv(iv0) {
00116     x0.subscribe(home,this,PC_INT_DOM);
00117     x1.subscribe(home,this,pcb);
00118     for (int i=n; i--; )
00119       iv[i].view.subscribe(home,this,pcb);
00120   }
00121 
00122   template <class ViewA, class ViewB, PropCond pcb>
00123   forceinline
00124   View<ViewA,ViewB,pcb>::View(Space* home, bool share, View& p)
00125     : Propagator(home,share,p), n(p.n) {
00126     x0.update(home,share,p.x0);
00127     x1.update(home,share,p.x1);
00128     iv = IdxView<ViewB>::allocate(home,n);
00129     for (int i=n; i--; ) {
00130       iv[i].idx = p.iv[i].idx;
00131       iv[i].view.update(home,share,p.iv[i].view);
00132     }
00133   }
00134 
00135   template <class ViewA, class ViewB, PropCond pcb>
00136   PropCost
00137   View<ViewA,ViewB,pcb>::cost(void) const {
00138     // This is required for subscribing to variables in the
00139     // above constructor, but this is then the only time this
00140     // virtual function is ever used!
00141     return PC_LINEAR_LO;
00142   }
00143 
00144   template <class ViewA, class ViewB, PropCond pcb>
00145   View<ViewA,ViewB,pcb>::~View(void) {
00146     x0.cancel(this,PC_INT_DOM);
00147     x1.cancel(this,pcb);
00148     for (int i=n; i--;)
00149       iv[i].view.cancel(this,pcb);
00150   }
00151 
00152 
00153 
00154 
00159   template <class View>
00160   class IterIdxView {
00161   private:
00162     const IdxView<View> *cur, *end;
00163   public:
00164     IterIdxView(void);
00165     IterIdxView(const IdxView<View>*, const IdxView<View>*);
00166     void init(const IdxView<View>*, const IdxView<View>*);
00167     bool operator()(void) const;
00168     void operator++(void);
00169     int  val(void) const;
00170   };
00171 
00172   template <class View>
00173   forceinline
00174   IterIdxView<View>::IterIdxView(void) {}
00175   template <class View>
00176   forceinline
00177   IterIdxView<View>::IterIdxView(const IdxView<View>* b,
00178                                  const IdxView<View>* e)
00179     : cur(b), end(e) {}
00180   template <class View>
00181   forceinline void
00182   IterIdxView<View>::init(const IdxView<View>* b,
00183                           const IdxView<View>* e) {
00184     cur=b; end=e;
00185   }
00186   template <class View>
00187   forceinline bool
00188   IterIdxView<View>::operator()(void) const {
00189     return cur < end;
00190   }
00191   template <class View>
00192   forceinline void
00193   IterIdxView<View>::operator++(void) {
00194     cur++;
00195   }
00196   template <class View>
00197   forceinline int
00198   IterIdxView<View>::val(void) const {
00199     return cur->idx;
00200   }
00201 
00202 
00203 
00204 
00205   /*
00206    * Generic scanning: does all but computing new domain for result
00207    * (which is specific to bounds/domain version)
00208    *
00209    */
00210 
00211   template <class ViewA, class ViewB, PropCond pcb, class RelTest>
00212   void
00213   scan(Space* home, IdxView<ViewB>* iv, int& n,
00214        ViewA x0, ViewB x1, Propagator* p, RelTest rt) {
00215     assert(n > 1);
00216     /*
00217      * Prunes pairs of index, variable
00218      *  - checks for idx value removed
00219      *  - checks for disequal variables
00220      *
00221      */
00222     ViewValues<ViewA> vx0(x0);
00223     int i = 0;
00224     int j = 0;
00225     while (vx0() && (i < n)) {
00226       if (iv[i].idx < vx0.val()) {
00227         iv[i].view.cancel(p,pcb);
00228         ++i;
00229       } else if (iv[i].idx > vx0.val()) {
00230         ++vx0;
00231       } else {
00232         assert(iv[i].idx == vx0.val());
00233         switch (rt(iv[i].view,x1)) {
00234         case RT_FALSE:
00235           iv[i].view.cancel(p,pcb);
00236           break;
00237         case RT_TRUE:
00238         case RT_MAYBE:
00239           iv[j++] = iv[i];
00240           break;
00241         }
00242         ++vx0; ++i;
00243       }
00244     }
00245     while (i < n)
00246       iv[i++].view.cancel(p,pcb);
00247     bool adjust = (j<n);
00248     n = j;
00249 
00250     if (n == 0)
00251       return;
00252 
00253     if (n == 1) {
00254       GECODE_ASSERTION_VARIABLE(ModEvent me = )
00255         x0.eq(home,iv[0].idx);
00256       assert(!me_failed(me));
00257     } else if (adjust) {
00258       IterIdxView<ViewA> i(&iv[0],&iv[n]);
00259       Iter::Values::ToRanges<IterIdxView<ViewA> > ri(i);
00260       GECODE_ASSERTION_VARIABLE(ModEvent me = )
00261         x0.narrow(home,ri);
00262       assert(!me_failed(me));
00263       assert(x0.size() == static_cast<unsigned int>(n));
00264     }
00265   }
00266 
00267 
00268 
00269 
00270   /*
00271    * Bounds-consistent propagator
00272    *
00273    */
00274 
00275   template <class ViewA, class ViewB>
00276   forceinline
00277   ViewBnd<ViewA,ViewB>::ViewBnd(Space* home, 
00278                                 IdxView<ViewB>* iv, int n, ViewA x0, ViewB x1)
00279     : View<ViewA,ViewB,PC_INT_BND>(home,iv,n,x0,x1) {}
00280 
00281   template <class ViewA, class ViewB>
00282   ExecStatus
00283   ViewBnd<ViewA,ViewB>::post(Space* home, 
00284                              IdxView<ViewB>* iv, int n, ViewA x0, ViewB x1) {
00285     GECODE_ME_CHECK(x0.gq(home,0));
00286     GECODE_ME_CHECK(x0.le(home,n));
00287     if (x0.assigned()) {
00288       return Rel::EqBnd<ViewB>::post(home,iv[x0.val()].view,x1);
00289     } else {
00290       assert(n>1);
00291       (void) new (home) ViewBnd<ViewA,ViewB>(home,iv,n,x0,x1);
00292     }
00293     return ES_OK;
00294   }
00295 
00296 
00297   template <class ViewA, class ViewB>
00298   forceinline
00299   ViewBnd<ViewA,ViewB>::ViewBnd(Space* home, bool share, ViewBnd& p)
00300     : View<ViewA,ViewB,PC_INT_BND>(home,share,p) {}
00301 
00302   template <class ViewA, class ViewB>
00303   Actor*
00304   ViewBnd<ViewA,ViewB>::copy(Space* home, bool share) {
00305     return new (home) ViewBnd<ViewA,ViewB>(home,share,*this);
00306   }
00307 
00308 
00309   template <class ViewA, class ViewB>
00310   ExecStatus
00311   ViewBnd<ViewA,ViewB>::propagate(Space* home) {
00312     assert(n > 1);
00313     RelTestBnd<ViewB> rt;
00314     scan<ViewA,ViewB,PC_INT_BND,RelTestBnd<ViewB> >
00315       (home,iv,n,x0,x1,this,rt);
00316     if (n == 0)
00317       return ES_FAILED;
00318     if (n == 1) {
00319       GECODE_ES_CHECK(Rel::EqBnd<ViewB>::post(home,iv[0].view,x1));
00320       return ES_SUBSUMED;
00321     }
00322     assert(n > 1);
00323     // Compute new result
00324     int min = iv[n-1].view.min();
00325     int max = iv[n-1].view.max();
00326     for (int i=n-1; i--; ) {
00327       min = std::min(iv[i].view.min(),min);
00328       max = std::max(iv[i].view.max(),max);
00329     }
00330     ExecStatus es = x1.modified() ? 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)) ? ES_SUBSUMED : es;
00346   }
00347 
00348 
00349 
00350 
00351 
00352   /*
00353    * Domain consistent propagator
00354    *
00355    */
00356 
00357   template <class ViewA, class ViewB>
00358   forceinline
00359   ViewDom<ViewA,ViewB>::ViewDom(Space* home, 
00360                                 IdxView<ViewB>* iv, int n, ViewA x0, ViewB x1)
00361     : View<ViewA,ViewB,PC_INT_DOM>(home,iv,n,x0,x1) {}
00362 
00363   template <class ViewA, class ViewB>
00364   ExecStatus
00365   ViewDom<ViewA,ViewB>::post(Space* home, 
00366                              IdxView<ViewB>* iv, int n, ViewA x0, ViewB x1){
00367     GECODE_ME_CHECK(x0.gq(home,0));
00368     GECODE_ME_CHECK(x0.le(home,n));
00369     if (x0.assigned()) {
00370       return Rel::EqDom<ViewB>::post(home,iv[x0.val()].view,x1);
00371     } else {
00372       assert(n>1);
00373       (void) new (home) ViewDom<ViewA,ViewB>(home,iv,n,x0,x1);
00374     }
00375     return ES_OK;
00376   }
00377 
00378 
00379   template <class ViewA, class ViewB>
00380   forceinline
00381   ViewDom<ViewA,ViewB>::ViewDom(Space* home, bool share, ViewDom& p)
00382     : View<ViewA,ViewB,PC_INT_DOM>(home,share,p) {}
00383 
00384   template <class ViewA, class ViewB>
00385   Actor*
00386   ViewDom<ViewA,ViewB>::copy(Space* home, bool share) {
00387     return new (home) ViewDom<ViewA,ViewB>(home,share,*this);
00388   }
00389 
00390 
00391   template <class ViewA, class ViewB>
00392   PropCost
00393   ViewDom<ViewA,ViewB>::cost(void) const {
00394     if (ViewA::pme(this) != ME_INT_DOM)
00395       return PC_LINEAR_LO;
00396     else
00397       return PC_LINEAR_HI;
00398   }
00399 
00400   template <class ViewA, class ViewB>
00401   ExecStatus
00402   ViewDom<ViewA,ViewB>::propagate(Space* home) {
00403     assert(n > 1);
00404     if (ViewA::pme(this) != ME_INT_DOM) {
00405       RelTestBnd<ViewB> rt;
00406       scan<ViewA,ViewB,PC_INT_DOM,RelTestBnd<ViewB> >
00407         (home,iv,n,x0,x1,this,rt);
00408       if (n == 0)
00409         return ES_FAILED;
00410       if (n == 1) {
00411         GECODE_ES_CHECK(Rel::EqDom<ViewB>::post(home,iv[0].view,x1));
00412         return ES_SUBSUMED;
00413       }
00414       // Compute new result
00415       int min = iv[n-1].view.min();
00416       int max = iv[n-1].view.max();
00417       for (int i=n-1; i--; ) {
00418         min = std::min(iv[i].view.min(),min);
00419         max = std::max(iv[i].view.max(),max);
00420       }
00421       GECODE_ME_CHECK(x1.lq(home,max));
00422       GECODE_ME_CHECK(x1.gq(home,min));
00423       return (x1.assigned() && (min == max)) ? 
00424         ES_SUBSUMED : 
00425         this->ES_NOFIX_PARTIAL(ViewA::pme(ME_INT_DOM));
00426     }
00427     RelTestDom<ViewB> rt;
00428     scan<ViewA,ViewB,PC_INT_DOM,RelTestDom<ViewB> >
00429       (home,iv,n,x0,x1,this,rt);
00430     if (n == 0)
00431       return ES_FAILED;
00432     if (n == 1) {
00433       GECODE_ES_CHECK(Rel::EqDom<ViewB>::post(home,iv[0].view,x1));
00434       return ES_SUBSUMED;
00435     }
00436     assert(n > 1);
00437     GECODE_AUTOARRAY(ViewRanges<ViewB>,i_view,n);
00438     for (int i = n; i--; )
00439       i_view[i].init(iv[i].view);
00440     Iter::Ranges::NaryUnion<ViewRanges<ViewB> > i_val(i_view, n);
00441     GECODE_ME_CHECK(x1.inter(home,i_val));
00442     return x1.modified() ? ES_NOFIX : ES_FIX;
00443   }
00444 
00445 }}}
00446 
00447 #undef GECODE_ASSERTION_VARIABLE
00448 
00449 // STATISTICS: int-prop
00450