Generated on Wed Nov 1 15:04:32 2006 for Gecode by doxygen 1.4.5

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