Generated on Thu Mar 22 10:39:37 2012 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  *  Last modified:
00014  *     $Date: 2011-08-08 18:04:53 +0200 (Mon, 08 Aug 2011) $ by $Author: schulte $
00015  *     $Revision: 12253 $
00016  *
00017  *  This file is part of Gecode, the generic constraint
00018  *  development environment:
00019  *     http://www.gecode.org
00020  *
00021  *  Permission is hereby granted, free of charge, to any person obtaining
00022  *  a copy of this software and associated documentation files (the
00023  *  "Software"), to deal in the Software without restriction, including
00024  *  without limitation the rights to use, copy, modify, merge, publish,
00025  *  distribute, sublicense, and/or sell copies of the Software, and to
00026  *  permit persons to whom the Software is furnished to do so, subject to
00027  *  the following conditions:
00028  *
00029  *  The above copyright notice and this permission notice shall be
00030  *  included in all copies or substantial portions of the Software.
00031  *
00032  *  THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,
00033  *  EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF
00034  *  MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND
00035  *  NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE
00036  *  LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION
00037  *  OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION
00038  *  WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
00039  *
00040  */
00041 
00042 #include <algorithm>
00043 
00044 namespace Gecode { namespace Int { namespace Element {
00045 
00047   template<>
00048   class ViewToVarArg<IntView> {
00049   public:
00050     typedef IntVarArgs argtype;
00051   };
00053   template<>
00054   class ViewToVarArg<BoolView> {
00055   public:
00056     typedef BoolVarArgs argtype;
00057   };
00058 
00063   template<class View>
00064   class IdxView {
00065   public:
00066     int idx; View view;
00067 
00068     static IdxView* allocate(Space&, int);
00069   };
00070 
00071   template<class View>
00072   forceinline IdxView<View>*
00073   IdxView<View>::allocate(Space& home, int n) {
00074     return home.alloc<IdxView<View> >(n);
00075   }
00076 
00077   template<class View>
00078   IdxViewArray<View>::IdxViewArray(void) : xs(NULL), n(0) {}
00079 
00080   template<class View>
00081   IdxViewArray<View>::IdxViewArray(const IdxViewArray<View>& a) {
00082     n = a.n; xs = a.xs;
00083   }
00084 
00085   template<class View>
00086   IdxViewArray<View>::IdxViewArray(Space& home,
00087     const typename ViewToVarArg<View>::argtype& xa) : xs(NULL) {
00088     n = xa.size();
00089     if (n>0) {
00090       xs = IdxView<View>::allocate(home, n);
00091       for (int i = n; i--; ) {
00092         xs[i].idx = i; xs[i].view = xa[i];
00093       }
00094     }
00095   }
00096 
00097   template<class View>
00098   IdxViewArray<View>::IdxViewArray(Space& home, int n0) : xs(NULL) {
00099     n = n0;
00100     if (n>0) {
00101       xs = IdxView<View>::allocate(home, n);
00102     }
00103   }
00104 
00105   template<class View>
00106   forceinline int
00107   IdxViewArray<View>::size(void) const {
00108     return n;
00109   }
00110 
00111   template<class View>
00112   forceinline void
00113   IdxViewArray<View>::size(int n0) {
00114     n = n0;
00115   }
00116 
00117   template<class View>
00118   forceinline IdxView<View>&
00119   IdxViewArray<View>::operator [](int i) {
00120     assert((i >= 0) && (i < size()));
00121     return xs[i];
00122   }
00123 
00124   template<class View>
00125   forceinline const IdxView<View>&
00126   IdxViewArray<View>::operator [](int i) const {
00127     assert((i >= 0) && (i < size()));
00128     return xs[i];
00129   }
00130 
00131   template<class View>
00132   void
00133   IdxViewArray<View>::subscribe(Space& home, Propagator& p, PropCond pc,
00134                                 bool process) {
00135     for (int i = n; i--; )
00136       xs[i].view.subscribe(home,p,pc,process);
00137   }
00138 
00139   template<class View>
00140   void
00141   IdxViewArray<View>::cancel(Space& home, Propagator& p, PropCond pc) {
00142     for (int i = n; i--; )
00143       xs[i].view.cancel(home,p,pc);
00144   }
00145 
00146   template<class View>
00147   void
00148   IdxViewArray<View>::update(Space& home, bool share, IdxViewArray<View>& a) {
00149     n = a.size();
00150     if (n>0) {
00151       xs = IdxView<View>::allocate(home,n);
00152       for (int i=n; i--; ) {
00153         xs[i].idx = a[i].idx;
00154         xs[i].view.update(home,share,a[i].view);
00155       }
00156     }
00157   }
00158 
00159 
00164   template<class VA, class VC>
00165   class RelTestBnd {
00166   public:
00167     RelTest operator ()(VA,VC);
00168   };
00173   template<class VA>
00174   class RelTestBnd<VA,ConstIntView> {
00175   public:
00176     RelTest operator ()(VA,ConstIntView);
00177   };
00178 
00183   template<class VA, class VC>
00184   class RelTestDom {
00185   public:
00186     RelTest operator ()(VA,VC);
00187   };
00192   template<class VA>
00193   class RelTestDom<VA,ConstIntView> {
00194   public:
00195     RelTest operator ()(VA,ConstIntView);
00196   };
00197 
00198 
00199   template<class VA, class VC>
00200   forceinline RelTest
00201   RelTestBnd<VA,VC>::operator ()(VA x, VC y) {
00202     return rtest_eq_bnd(x,y);
00203   }
00204   template<class VA>
00205   forceinline RelTest
00206   RelTestBnd<VA,ConstIntView>::operator ()(VA x, ConstIntView y) {
00207     return rtest_eq_bnd(x,y.val());
00208   }
00209 
00210   template<class VA, class VC>
00211   forceinline RelTest
00212   RelTestDom<VA,VC>::operator ()(VA x, VC y) {
00213     return rtest_eq_dom(x,y);
00214   }
00215   template<class VA>
00216   forceinline RelTest
00217   RelTestDom<VA,ConstIntView>::operator ()(VA x, ConstIntView y) {
00218     return rtest_eq_dom(x,y.val());
00219   }
00220 
00221 
00222 
00223 
00224   /*
00225    * Base class
00226    *
00227    */
00228 
00229   template<class VA, class VB, class VC, PropCond pc_ac>
00230   View<VA,VB,VC,pc_ac>::View(Home home, IdxViewArray<VA>& iv0,
00231                              VB y0, VC y1)
00232     : Propagator(home), iv(iv0), x0(y0), x1(y1) {
00233     x0.subscribe(home,*this,PC_INT_DOM);
00234     x1.subscribe(home,*this,pc_ac);
00235     iv.subscribe(home,*this,pc_ac);
00236   }
00237 
00238   template<class VA, class VB, class VC, PropCond pc_ac>
00239   forceinline
00240   View<VA,VB,VC,pc_ac>::View(Space& home, bool share, View& p)
00241     : Propagator(home,share,p) {
00242     x0.update(home,share,p.x0);
00243     x1.update(home,share,p.x1);
00244     iv.update(home,share,p.iv);
00245   }
00246 
00247   template<class VA, class VB, class VC, PropCond pc_ac>
00248   PropCost
00249   View<VA,VB,VC,pc_ac>::cost(const Space&, const ModEventDelta&) const {
00250     // This is required for subscribing to variables in the
00251     // above constructor, but this is then the only time this
00252     // virtual function is ever used!
00253     return PropCost::linear(PropCost::LO,iv.size()+2);
00254   }
00255 
00256   template<class VA, class VB, class VC, PropCond pc_ac>
00257   forceinline size_t
00258   View<VA,VB,VC,pc_ac>::dispose(Space& home) {
00259     x0.cancel(home,*this,PC_INT_DOM);
00260     x1.cancel(home,*this,pc_ac);
00261     iv.cancel(home,*this,pc_ac);
00262     (void) Propagator::dispose(home);
00263     return sizeof(*this);
00264   }
00265 
00266 
00267 
00268 
00273   template<class View>
00274   class IterIdxView {
00275   private:
00276     const IdxView<View> *cur, *end;
00277   public:
00278     IterIdxView(void);
00279     IterIdxView(const IdxView<View>*, const IdxView<View>*);
00280     void init(const IdxView<View>*, const IdxView<View>*);
00281     bool operator ()(void) const;
00282     void operator ++(void);
00283     int  val(void) const;
00284   };
00285 
00286   template<class View>
00287   forceinline
00288   IterIdxView<View>::IterIdxView(void) {}
00289   template<class View>
00290   forceinline
00291   IterIdxView<View>::IterIdxView(const IdxView<View>* b,
00292                                  const IdxView<View>* e)
00293     : cur(b), end(e) {}
00294   template<class View>
00295   forceinline void
00296   IterIdxView<View>::init(const IdxView<View>* b,
00297                           const IdxView<View>* e) {
00298     cur=b; end=e;
00299   }
00300   template<class View>
00301   forceinline bool
00302   IterIdxView<View>::operator ()(void) const {
00303     return cur < end;
00304   }
00305   template<class View>
00306   forceinline void
00307   IterIdxView<View>::operator ++(void) {
00308     cur++;
00309   }
00310   template<class View>
00311   forceinline int
00312   IterIdxView<View>::val(void) const {
00313     return cur->idx;
00314   }
00315 
00316 
00317 
00318 
00319   /*
00320    * Generic scanning: does all but computing new domain for result
00321    * (which is specific to bounds/domain version)
00322    *
00323    */
00324 
00325   template<class VA, class VB, class VC, PropCond pc_ac, class RelTest>
00326   ExecStatus
00327   scan(Space& home, IdxViewArray<VA>& iv,
00328        VB x0, VC x1, Propagator& p, RelTest rt) {
00329     assert(iv.size() > 1);
00330     /*
00331      * Prunes pairs of index, variable
00332      *  - checks for idx value removed
00333      *  - checks for disequal variables
00334      *
00335      */
00336     ViewValues<VB> vx0(x0);
00337     int i = 0;
00338     int j = 0;
00339     while (vx0() && (i < iv.size())) {
00340       if (iv[i].idx < vx0.val()) {
00341         iv[i].view.cancel(home,p,pc_ac);
00342         ++i;
00343       } else if (iv[i].idx > vx0.val()) {
00344         ++vx0;
00345       } else {
00346         assert(iv[i].idx == vx0.val());
00347         switch (rt(iv[i].view,x1)) {
00348         case RT_FALSE:
00349           iv[i].view.cancel(home,p,pc_ac);
00350           break;
00351         case RT_TRUE:
00352         case RT_MAYBE:
00353           iv[j++] = iv[i];
00354           break;
00355         default: GECODE_NEVER;
00356         }
00357         ++vx0; ++i;
00358       }
00359     }
00360     while (i < iv.size())
00361       iv[i++].view.cancel(home,p,pc_ac);
00362     bool adjust = (j<iv.size());
00363     iv.size(j);
00364 
00365     if (iv.size() == 0)
00366       return ES_FAILED;
00367 
00368     if (iv.size() == 1) {
00369       GECODE_ME_CHECK(x0.eq(home,iv[0].idx));
00370     } else if (adjust) {
00371       IterIdxView<VA> v(&iv[0],&iv[0]+iv.size());
00372       GECODE_ME_CHECK(x0.narrow_v(home,v,false));
00373       assert(x0.size() == static_cast<unsigned int>(iv.size()));
00374     }
00375     return ES_OK;
00376   }
00377 
00378 
00379 
00380 
00381   /*
00382    * Bounds consistent propagator
00383    *
00384    */
00385 
00386   template<class VA, class VB, class VC>
00387   forceinline
00388   ViewBnd<VA,VB,VC>::ViewBnd(Home home,
00389                              IdxViewArray<VA>& iv, VB x0, VC x1)
00390     : View<VA,VB,VC,PC_INT_BND>(home,iv,x0,x1) {}
00391 
00392   template<class VA, class VB, class VC>
00393   ExecStatus
00394   ViewBnd<VA,VB,VC>::post(Home home,
00395                           IdxViewArray<VA>& iv, VB x0, VC x1) {
00396     GECODE_ME_CHECK(x0.gq(home,0));
00397     GECODE_ME_CHECK(x0.le(home,iv.size()));
00398     if (x0.assigned()) {
00399       (void) new (home) Rel::EqBnd<VA,VC>(home,iv[x0.val()].view,x1);
00400       return ES_OK;
00401     } else {
00402       assert(iv.size()>1);
00403       (void) new (home) ViewBnd<VA,VB,VC>(home,iv,x0,x1);
00404     }
00405     return ES_OK;
00406   }
00407 
00408 
00409   template<class VA, class VB, class VC>
00410   forceinline
00411   ViewBnd<VA,VB,VC>::ViewBnd(Space& home, bool share, ViewBnd& p)
00412     : View<VA,VB,VC,PC_INT_BND>(home,share,p) {}
00413 
00414   template<class VA, class VB, class VC>
00415   Actor*
00416   ViewBnd<VA,VB,VC>::copy(Space& home, bool share) {
00417     return new (home) ViewBnd<VA,VB,VC>(home,share,*this);
00418   }
00419 
00420   template<class VA, class VB, class VC>
00421   ExecStatus
00422   ViewBnd<VA,VB,VC>::propagate(Space& home, const ModEventDelta&) {
00423     assert(iv.size() > 1);
00424     RelTestBnd<VA,VC> rt;
00425     GECODE_ES_CHECK((scan<VA,VB,VC,PC_INT_BND,RelTestBnd<VA,VC> >
00426                      (home,iv,x0,x1,*this,rt)));
00427     if (iv.size() == 1) {
00428       ExecStatus es = home.ES_SUBSUMED(*this);
00429       (void) new (home) Rel::EqBnd<VA,VC>(home,iv[0].view,x1);
00430       return es;
00431     }
00432     assert(iv.size() > 1);
00433     // Compute new result
00434     int min = iv[iv.size()-1].view.min();
00435     int max = iv[iv.size()-1].view.max();
00436     for (int i=iv.size()-1; i--; ) {
00437       min = std::min(iv[i].view.min(),min);
00438       max = std::max(iv[i].view.max(),max);
00439     }
00440     ExecStatus es = shared(x0,x1) ? ES_NOFIX : ES_FIX;
00441     {
00442      ModEvent me = x1.lq(home,max);
00443      if (me_failed(me))
00444        return ES_FAILED;
00445      if (me_modified(me) && (x1.max() != max))
00446        es = ES_NOFIX;
00447     }
00448     {
00449      ModEvent me = x1.gq(home,min);
00450      if (me_failed(me))
00451        return ES_FAILED;
00452      if (me_modified(me) && (x1.min() != min))
00453        es = ES_NOFIX;
00454     }
00455     return (x1.assigned() && (min == max)) ?
00456       home.ES_SUBSUMED(*this) : es;
00457   }
00458 
00459 
00460 
00461 
00462 
00463   /*
00464    * Domain consistent propagator
00465    *
00466    */
00467 
00468   template<class VA, class VB, class VC>
00469   forceinline
00470   ViewDom<VA,VB,VC>::ViewDom(Home home,
00471                              IdxViewArray<VA>& iv, VB x0, VC x1)
00472     : View<VA,VB,VC,PC_INT_DOM>(home,iv,x0,x1) {}
00473 
00474   template<class VA, class VB, class VC>
00475   ExecStatus
00476   ViewDom<VA,VB,VC>::post(Home home,
00477                           IdxViewArray<VA>& iv, VB x0, VC x1){
00478     GECODE_ME_CHECK(x0.gq(home,0));
00479     GECODE_ME_CHECK(x0.le(home,iv.size()));
00480     if (x0.assigned()) {
00481       (void) new (home) Rel::EqDom<VA,VC>(home,iv[x0.val()].view,x1);
00482       return ES_OK;
00483     } else {
00484       assert(iv.size()>1);
00485       (void) new (home) ViewDom<VA,VB,VC>(home,iv,x0,x1);
00486     }
00487     return ES_OK;
00488   }
00489 
00490 
00491   template<class VA, class VB, class VC>
00492   forceinline
00493   ViewDom<VA,VB,VC>::ViewDom(Space& home, bool share, ViewDom& p)
00494     : View<VA,VB,VC,PC_INT_DOM>(home,share,p) {}
00495 
00496   template<class VA, class VB, class VC>
00497   Actor*
00498   ViewDom<VA,VB,VC>::copy(Space& home, bool share) {
00499     return new (home) ViewDom<VA,VB,VC>(home,share,*this);
00500   }
00501 
00502 
00503   template<class VA, class VB, class VC>
00504   PropCost
00505   ViewDom<VA,VB,VC>::cost(const Space&, const ModEventDelta& med) const {
00506     return PropCost::linear((VA::me(med) != ME_INT_DOM) ?
00507                             PropCost::LO : PropCost::HI, iv.size()+2);
00508   }
00509 
00510   template<class VA, class VB, class VC>
00511   ExecStatus
00512   ViewDom<VA,VB,VC>::propagate(Space& home, const ModEventDelta& med) {
00513     assert(iv.size() > 1);
00514     if (VA::me(med) != ME_INT_DOM) {
00515       RelTestBnd<VA,VC> rt;
00516       GECODE_ES_CHECK((scan<VA,VB,VC,PC_INT_DOM,RelTestBnd<VA,VC> >
00517                        (home,iv,x0,x1,*this,rt)));
00518       if (iv.size() == 1) {
00519         ExecStatus es = home.ES_SUBSUMED(*this);
00520         (void) new (home) Rel::EqDom<VA,VC>(home,iv[0].view,x1);
00521         return es;
00522       }
00523       // Compute new result
00524       int min = iv[iv.size()-1].view.min();
00525       int max = iv[iv.size()-1].view.max();
00526       for (int i=iv.size()-1; i--; ) {
00527         min = std::min(iv[i].view.min(),min);
00528         max = std::max(iv[i].view.max(),max);
00529       }
00530       GECODE_ME_CHECK(x1.lq(home,max));
00531       GECODE_ME_CHECK(x1.gq(home,min));
00532       return (x1.assigned() && (min == max)) ?
00533         home.ES_SUBSUMED(*this) :
00534         home.ES_NOFIX_PARTIAL(*this,VA::med(ME_INT_DOM));
00535     }
00536     RelTestDom<VA,VC> rt;
00537     GECODE_ES_CHECK((scan<VA,VB,VC,PC_INT_DOM,RelTestDom<VA,VC> >
00538                      (home,iv,x0,x1,*this,rt)));
00539     if (iv.size() == 1) {
00540       ExecStatus es = home.ES_SUBSUMED(*this);
00541       (void) new (home) Rel::EqDom<VA,VC>(home,iv[0].view,x1);
00542       return es;
00543     }
00544     assert(iv.size() > 1);
00545     Region r(home);
00546     ViewRanges<VA>* i_view = r.alloc<ViewRanges<VA> >(iv.size());
00547     for (int i = iv.size(); i--; )
00548       i_view[i].init(iv[i].view);
00549     Iter::Ranges::NaryUnion i_val(r, i_view, iv.size());
00550     ModEvent me = x1.inter_r(home,i_val);
00551     r.free<ViewRanges<VA> >(i_view,iv.size());
00552     GECODE_ME_CHECK(me);
00553     return (shared(x0,x1) || me_modified(me)) ? ES_NOFIX : ES_FIX;
00554   }
00555 
00556 }}}
00557 
00558 // STATISTICS: int-prop
00559