Generated on Tue May 22 09:39:44 2018 for Gecode by doxygen 1.6.3

action.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  *  Copyright:
00007  *     Christian Schulte, 2012
00008  *
00009  *  This file is part of Gecode, the generic constraint
00010  *  development environment:
00011  *     http://www.gecode.org
00012  *
00013  *  Permission is hereby granted, free of charge, to any person obtaining
00014  *  a copy of this software and associated documentation files (the
00015  *  "Software"), to deal in the Software without restriction, including
00016  *  without limitation the rights to use, copy, modify, merge, publish,
00017  *  distribute, sublicense, and/or sell copies of the Software, and to
00018  *  permit persons to whom the Software is furnished to do so, subject to
00019  *  the following conditions:
00020  *
00021  *  The above copyright notice and this permission notice shall be
00022  *  included in all copies or substantial portions of the Software.
00023  *
00024  *  THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,
00025  *  EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF
00026  *  MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND
00027  *  NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE
00028  *  LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION
00029  *  OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION
00030  *  WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
00031  *
00032  */
00033 
00034 #include <cfloat>
00035 
00036 namespace Gecode {
00037 
00042   class Action : public SharedHandle {
00043   protected:
00044     template<class View>
00045     class Recorder;
00047     class GECODE_VTABLE_EXPORT Storage : public SharedHandle::Object {
00048     public:
00050       GECODE_KERNEL_EXPORT static Support::Mutex m;
00052       int n;
00054       double invd;
00056       double* a;
00058       template<class View>
00059       Storage(Home home, ViewArray<View>& x, double d,
00060               typename BranchTraits<typename View::VarType>::Merit bm);
00062       void update(int i);
00064       GECODE_KERNEL_EXPORT
00065       ~Storage(void);
00066     };
00068     Storage& object(void) const;
00070     void object(Storage& o);
00072     void update(int i);
00074     void acquire(void);
00076     void release(void);
00077   public:
00079 
00080 
00087     Action(void);
00089     GECODE_KERNEL_EXPORT
00090     Action(const Action& a);
00092     GECODE_KERNEL_EXPORT
00093     Action& operator =(const Action& a);
00095     template<class View>
00096     Action(Home home, ViewArray<View>& x, double d,
00097            typename BranchTraits<typename View::VarType>::Merit bm);
00099     template<class View>
00100     void init(Home home, ViewArray<View>& x, double d,
00101               typename BranchTraits<typename View::VarType>::Merit bm);
00103     GECODE_KERNEL_EXPORT static const Action def;
00105 
00107     GECODE_KERNEL_EXPORT
00108     ~Action(void);
00109 
00111 
00112 
00113     double operator [](int i) const;
00115     int size(void) const;
00117 
00119 
00120 
00121     GECODE_KERNEL_EXPORT
00122     void decay(Space& home, double d);
00124     GECODE_KERNEL_EXPORT
00125     double decay(const Space& home) const;
00127   };
00128 
00130   template<class View>
00131   class Action::Recorder : public NaryPropagator<View,PC_GEN_NONE> {
00132   protected:
00133     using NaryPropagator<View,PC_GEN_NONE>::x;
00135     class Idx : public Advisor {
00136     protected:
00138       int _info;
00139     public:
00141       Idx(Space& home, Propagator& p, Council<Idx>& c, int i);
00143       Idx(Space& home, Idx& a);
00145       void mark(void);
00147       void unmark(void);
00149       bool marked(void) const;
00151       int idx(void) const;
00152     };
00154     Action a;
00156     Council<Idx> c;
00158     Recorder(Space& home, Recorder<View>& p);
00159   public:
00161     Recorder(Home home, ViewArray<View>& x, Action& a);
00163     virtual Propagator* copy(Space& home);
00165     virtual PropCost cost(const Space& home, const ModEventDelta& med) const;
00167     virtual void reschedule(Space& home);
00169     virtual ExecStatus advise(Space& home, Advisor& a, const Delta& d);
00171     virtual void advise(Space& home, Advisor& a);
00173     virtual ExecStatus propagate(Space& home, const ModEventDelta& med);
00175     virtual size_t dispose(Space& home);
00177     static ExecStatus post(Home home, ViewArray<View>& x, Action& a);
00178   };
00179 
00184   template<class Char, class Traits>
00185   std::basic_ostream<Char,Traits>&
00186   operator <<(std::basic_ostream<Char,Traits>& os,
00187              const Action& a);
00188 
00189 
00190   /*
00191    * Advisor for action recorder
00192    *
00193    */
00194   template<class View>
00195   forceinline
00196   Action::Recorder<View>::Idx::Idx(Space& home, Propagator& p,
00197                                    Council<Idx>& c, int i)
00198     : Advisor(home,p,c), _info(i << 1) {}
00199   template<class View>
00200   forceinline
00201   Action::Recorder<View>::Idx::Idx(Space& home, Idx& a)
00202     : Advisor(home,a), _info(a._info) {
00203   }
00204   template<class View>
00205   forceinline void
00206   Action::Recorder<View>::Idx::mark(void) {
00207     _info |= 1;
00208   }
00209   template<class View>
00210   forceinline bool
00211   Action::Recorder<View>::Idx::marked(void) const {
00212     return (_info & 1) != 0;
00213   }
00214   template<class View>
00215   forceinline void
00216   Action::Recorder<View>::Idx::unmark(void) {
00217     assert(marked());
00218     _info -= 1;
00219   }
00220   template<class View>
00221   forceinline int
00222   Action::Recorder<View>::Idx::idx(void) const {
00223     return _info >> 1;
00224   }
00225 
00226 
00227   /*
00228    * Posting of action recorder propagator
00229    *
00230    */
00231   template<class View>
00232   forceinline
00233   Action::Recorder<View>::Recorder(Home home, ViewArray<View>& x,
00234                                    Action& a0)
00235     : NaryPropagator<View,PC_GEN_NONE>(home,x), a(a0), c(home) {
00236     home.notice(*this,AP_DISPOSE);
00237     for (int i=x.size(); i--; )
00238       if (!x[i].assigned())
00239         x[i].subscribe(home,*new (home) Idx(home,*this,c,i), true);
00240   }
00241 
00242   template<class View>
00243   forceinline ExecStatus
00244   Action::Recorder<View>::post(Home home, ViewArray<View>& x, Action& a) {
00245     (void) new (home) Recorder<View>(home,x,a);
00246     return ES_OK;
00247   }
00248 
00249 
00250   /*
00251    * Action value storage
00252    *
00253    */
00254 
00255   template<class View>
00256   forceinline
00257   Action::Storage::Storage(Home home, ViewArray<View>& x, double d,
00258                            typename
00259                            BranchTraits<typename View::VarType>::Merit bm)
00260     : n(x.size()), invd(1.0 / d), a(heap.alloc<double>(x.size())) {
00261     if (bm)
00262       for (int i=n; i--; ) {
00263         typename View::VarType xi(x[i].varimp());
00264         a[i] = bm(home,xi,i);
00265       }
00266     else
00267       for (int i=n; i--; )
00268         a[i] = 1.0;
00269   }
00270   forceinline void
00271   Action::Storage::update(int i) {
00272     /*
00273      * The trick to inverse decay is from: An Extensible SAT-solver,
00274      * Niklas En, Niklas Srensson, SAT 2003.
00275      */
00276     assert((i >= 0) && (i < n));
00277     a[i] = invd * (a[i] + 1.0);
00278     if (a[i] > Kernel::Config::rescale_limit)
00279       for (int j=n; j--; )
00280         a[j] *= Kernel::Config::rescale;
00281   }
00282 
00283 
00284   /*
00285    * Action
00286    *
00287    */
00288 
00289   forceinline Action::Storage&
00290   Action::object(void) const {
00291     return static_cast<Action::Storage&>(*SharedHandle::object());
00292   }
00293 
00294   forceinline void
00295   Action::object(Action::Storage& o) {
00296     SharedHandle::object(&o);
00297   }
00298 
00299   forceinline void
00300   Action::update(int i) {
00301     object().update(i);
00302   }
00303   forceinline double
00304   Action::operator [](int i) const {
00305     assert((i >= 0) && (i < object().n));
00306     return object().a[i];
00307   }
00308   forceinline int
00309   Action::size(void) const {
00310     return object().n;
00311   }
00312   forceinline void
00313   Action::acquire(void) {
00314     object().m.acquire();
00315   }
00316   forceinline void
00317   Action::release(void) {
00318     object().m.release();
00319   }
00320 
00321 
00322   forceinline
00323   Action::Action(void) {}
00324 
00325   template<class View>
00326   forceinline
00327   Action::Action(Home home, ViewArray<View>& x, double d,
00328                  typename BranchTraits<typename View::VarType>::Merit bm) {
00329     assert(!*this);
00330     object(*new Storage(home,x,d,bm));
00331     (void) Recorder<View>::post(home,x,*this);
00332   }
00333   template<class View>
00334   forceinline void
00335   Action::init(Home home, ViewArray<View>& x, double d,
00336                typename BranchTraits<typename View::VarType>::Merit bm) {
00337     assert(!*this);
00338     object(*new Storage(home,x,d,bm));
00339     (void) Recorder<View>::post(home,x,*this);
00340   }
00341 
00342   template<class Char, class Traits>
00343   std::basic_ostream<Char,Traits>&
00344   operator <<(std::basic_ostream<Char,Traits>& os,
00345               const Action& a) {
00346     std::basic_ostringstream<Char,Traits> s;
00347     s.copyfmt(os); s.width(0);
00348     s << '{';
00349     if (a.size() > 0) {
00350       s << a[0];
00351       for (int i=1; i<a.size(); i++)
00352         s << ", " << a[i];
00353     }
00354     s << '}';
00355     return os << s.str();
00356   }
00357 
00358 
00359   /*
00360    * Propagation for action recorder
00361    *
00362    */
00363   template<class View>
00364   forceinline
00365   Action::Recorder<View>::Recorder(Space& home, Recorder<View>& p)
00366     : NaryPropagator<View,PC_GEN_NONE>(home,p), a(p.a) {
00367     c.update(home, p.c);
00368   }
00369 
00370   template<class View>
00371   Propagator*
00372   Action::Recorder<View>::copy(Space& home) {
00373     return new (home) Recorder<View>(home, *this);
00374   }
00375 
00376   template<class View>
00377   inline size_t
00378   Action::Recorder<View>::dispose(Space& home) {
00379     // Delete access to action information
00380     home.ignore(*this,AP_DISPOSE);
00381     a.~Action();
00382     // Cancel remaining advisors
00383     for (Advisors<Idx> as(c); as(); ++as)
00384       x[as.advisor().idx()].cancel(home,as.advisor(),true);
00385     c.dispose(home);
00386     (void) NaryPropagator<View,PC_GEN_NONE>::dispose(home);
00387     return sizeof(*this);
00388   }
00389 
00390   template<class View>
00391   PropCost
00392   Action::Recorder<View>::cost(const Space&, const ModEventDelta&) const {
00393     return PropCost::record();
00394   }
00395 
00396   template<class View>
00397   void
00398   Action::Recorder<View>::reschedule(Space& home) {
00399     View::schedule(home,*this,ME_GEN_ASSIGNED);
00400   }
00401 
00402   template<class View>
00403   ExecStatus
00404   Action::Recorder<View>::advise(Space&, Advisor& a, const Delta&) {
00405     static_cast<Idx&>(a).mark();
00406     return ES_NOFIX;
00407   }
00408 
00409   template<class View>
00410   void
00411   Action::Recorder<View>::advise(Space&, Advisor& a) {
00412     static_cast<Idx&>(a).mark();
00413   }
00414 
00415   template<class View>
00416   ExecStatus
00417   Action::Recorder<View>::propagate(Space& home, const ModEventDelta&) {
00418     // Lock action information
00419     a.acquire();
00420     for (Advisors<Idx> as(c); as(); ++as) {
00421       int i = as.advisor().idx();
00422       if (as.advisor().marked()) {
00423         as.advisor().unmark();
00424         a.update(i);
00425         if (x[i].assigned())
00426           as.advisor().dispose(home,c);
00427       }
00428     }
00429     a.release();
00430     return c.empty() ? home.ES_SUBSUMED(*this) : ES_FIX;
00431   }
00432 
00433 
00434 }
00435 
00436 // STATISTICS: kernel-branch