action.hpp

Go to the documentation of this file.

/* -*- mode: C++; c-basic-offset: 2; indent-tabs-mode: nil -*- */
/*
 *  Main authors:
 *     Christian Schulte <schulte@gecode.dev>
 *
 *  Copyright:
 *     Christian Schulte, 2012
 *
 *  This file is part of Gecode, the generic constraint
 *  development environment:
 *     http://www.gecode.dev
 *
 *  Permission is hereby granted, free of charge, to any person obtaining
 *  a copy of this software and associated documentation files (the
 *  "Software"), to deal in the Software without restriction, including
 *  without limitation the rights to use, copy, modify, merge, publish,
 *  distribute, sublicense, and/or sell copies of the Software, and to
 *  permit persons to whom the Software is furnished to do so, subject to
 *  the following conditions:
 *
 *  The above copyright notice and this permission notice shall be
 *  included in all copies or substantial portions of the Software.
 *
 *  THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,
 *  EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF
 *  MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND
 *  NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE
 *  LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION
 *  OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION
 *  WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
 *
 */
 
#include <cfloat>
 
namespace Gecode {

  class Action : public SharedHandle {
  protected:
    template<class View, bool p, bool f>
    class Recorder;
    class GECODE_VTABLE_EXPORT Storage : public SharedHandle::Object {
    public:
      GECODE_KERNEL_EXPORT static Support::Mutex m;
      int n;
      double invd;
      double* a;
      template<class View>
      Storage(Home home, ViewArray<View>& x, double d,
              typename BranchTraits<typename View::VarType>::Merit bm);
      void update(int i);
      GECODE_KERNEL_EXPORT
      ~Storage(void);
    };

    Storage& object(void) const;
    void object(Storage& o);
    void update(int i);
    void acquire(void);
    void release(void);
  public:


    Action(void);
    GECODE_KERNEL_EXPORT
    Action(const Action& a);
    GECODE_KERNEL_EXPORT
    Action& operator =(const Action& a);
    template<class View>
    Action(Home home, ViewArray<View>& x, double d, bool p, bool f,
           typename BranchTraits<typename View::VarType>::Merit bm);
    template<class View>
    void init(Home home, ViewArray<View>& x, double d, bool p, bool f,
              typename BranchTraits<typename View::VarType>::Merit bm);
    GECODE_KERNEL_EXPORT static const Action def;

    GECODE_KERNEL_EXPORT
    ~Action(void);



    double operator [](int i) const;
    int size(void) const;



    GECODE_KERNEL_EXPORT
    void decay(Space& home, double d);
    GECODE_KERNEL_EXPORT
    double decay(const Space& home) const;
  };

  template<class View, bool p, bool f>
  class Action::Recorder : public NaryPropagator<View,PC_GEN_NONE> {
  protected:
    using NaryPropagator<View,PC_GEN_NONE>::x;
    class Idx : public Advisor {
    protected:
      unsigned int _info;
    public:
      Idx(Space& home, Propagator& r, Council<Idx>& c, int i);
      Idx(Space& home, Idx& a);
      void propagate(void);
      void fail(void);
      bool propagated(void) const;
      bool failed(void) const;
      void clear(void);
      int idx(void) const;
    };

    Action a;
    Council<Idx> c;
    Recorder(Space& home, Recorder<View,p,f>& r);
  public:
    Recorder(Home home, ViewArray<View>& x, Action& a);
    virtual Propagator* copy(Space& home);
    virtual PropCost cost(const Space& home, const ModEventDelta& med) const;
    virtual void reschedule(Space& home);
    virtual ExecStatus advise(Space& home, Advisor& a, const Delta& d);
    virtual void advise(Space& home, Advisor& a);
    virtual ExecStatus propagate(Space& home, const ModEventDelta& med);
    virtual size_t dispose(Space& home);
    static ExecStatus post(Home home, ViewArray<View>& x, Action& a);
  };

  template<class Char, class Traits>
  std::basic_ostream<Char,Traits>&
  operator <<(std::basic_ostream<Char,Traits>& os,
             const Action& a);
 
 
  /*
   * Advisor for action recorder
   *
   */
  template<class View, bool p, bool f>
  forceinline
  Action::Recorder<View,p,f>::Idx::Idx(Space& home, Propagator& r,
                                       Council<Idx>& c, int i)
    : Advisor(home,r,c), _info(static_cast<unsigned int>(i) << 2U) {}
  template<class View, bool p, bool f>
  forceinline
  Action::Recorder<View,p,f>::Idx::Idx(Space& home, Idx& a)
    : Advisor(home,a), _info(a._info) {
  }
  template<class View, bool p, bool f>
  forceinline void
  Action::Recorder<View,p,f>::Idx::propagate(void) {
    _info |= 1U;
  }
  template<class View, bool p, bool f>
  forceinline void
  Action::Recorder<View,p,f>::Idx::fail(void) {
    _info |= 2U;
  }
  template<class View, bool p, bool f>
  forceinline bool
  Action::Recorder<View,p,f>::Idx::propagated(void) const {
    return (_info & 1U) != 0;
  }
  template<class View, bool p, bool f>
  forceinline bool
  Action::Recorder<View,p,f>::Idx::failed(void) const {
    return (_info & 2U) != 0;
  }
  template<class View, bool p, bool f>
  forceinline void
  Action::Recorder<View,p,f>::Idx::clear(void) {
    _info &= ~3U;
  }
  template<class View, bool p, bool f>
  forceinline int
  Action::Recorder<View,p,f>::Idx::idx(void) const {
    return static_cast<int>(_info >> 2);
  }
 
 
  /*
   * Posting of action recorder propagator
   *
   */
  template<class View, bool p, bool f>
  forceinline
  Action::Recorder<View,p,f>::Recorder(Home home, ViewArray<View>& x,
                                       Action& a0)
    : NaryPropagator<View,PC_GEN_NONE>(home,x), a(a0), c(home) {
    home.notice(*this,AP_DISPOSE);
    for (int i=0; i<x.size(); i++)
      if (!x[i].assigned())
        x[i].subscribe(home,*new (home) Idx(home,*this,c,i), true);
  }
 
  template<class View, bool p, bool f>
  forceinline ExecStatus
  Action::Recorder<View,p,f>::post(Home home, ViewArray<View>& x, Action& a) {
    (void) new (home) Recorder<View,p,f>(home,x,a);
    return ES_OK;
  }
 
 
  /*
   * Action value storage
   *
   */
 
  template<class View>
  forceinline
  Action::Storage::Storage(Home home, ViewArray<View>& x, double d,
                           typename
                           BranchTraits<typename View::VarType>::Merit bm)
    : n(x.size()), invd(1.0 / d), a(heap.alloc<double>(x.size())) {
    if (bm)
      for (int i=0; i<n; i++) {
        typename View::VarType xi(x[i].varimp());
        a[i] = bm(home,xi,i);
      }
    else
      for (int i=0; i<n; i++)
        a[i] = 1.0;
  }
  forceinline void
  Action::Storage::update(int i) {
    /*
     * The trick to inverse decay is from: An Extensible SAT-solver,
     * Niklas Eén, Niklas Sörensson, SAT 2003.
     */
    assert((i >= 0) && (i < n));
    a[i] = invd * (a[i] + 1.0);
    if (a[i] > Kernel::Config::rescale_limit)
      for (int j=0; j<n; j++)
        a[j] *= Kernel::Config::rescale;
  }
 
 
  /*
   * Action
   *
   */
 
  forceinline Action::Storage&
  Action::object(void) const {
    return static_cast<Action::Storage&>(*SharedHandle::object());
  }
 
  forceinline void
  Action::object(Action::Storage& o) {
    SharedHandle::object(&o);
  }
 
  forceinline void
  Action::update(int i) {
    object().update(i);
  }
  forceinline double
  Action::operator [](int i) const {
    assert((i >= 0) && (i < object().n));
    return object().a[i];
  }
  forceinline int
  Action::size(void) const {
    return object().n;
  }
  forceinline void
  Action::acquire(void) {
    object().m.acquire();
  }
  forceinline void
  Action::release(void) {
    object().m.release();
  }
 
 
  forceinline
  Action::Action(void) {}
 
  template<class View>
  forceinline
  Action::Action(Home home, ViewArray<View>& x, double d,
                 bool p, bool f,
                 typename BranchTraits<typename View::VarType>::Merit bm) {
    assert(!*this);
    if (!p && !f)
      return;
    object(*new Storage(home,x,d,bm));
    if (p && f)
      (void) Recorder<View,true,true>::post(home,x,*this);
    else if (p && !f)
      (void) Recorder<View,true,false>::post(home,x,*this);
    else if (!p && f)
      (void) Recorder<View,false,true>::post(home,x,*this);
  }
  template<class View>
  forceinline void
  Action::init(Home home, ViewArray<View>& x, double d,
               bool p, bool f,
               typename BranchTraits<typename View::VarType>::Merit bm) {
    assert(!*this);
    if (!p && !f)
      return;
    object(*new Storage(home,x,d,bm));
    if (p && f)
      (void) Recorder<View,true,true>::post(home,x,*this);
    else if (p && !f)
      (void) Recorder<View,true,false>::post(home,x,*this);
    else if (!p && f)
      (void) Recorder<View,false,true>::post(home,x,*this);
  }
 
  template<class Char, class Traits>
  std::basic_ostream<Char,Traits>&
  operator <<(std::basic_ostream<Char,Traits>& os,
              const Action& a) {
    std::basic_ostringstream<Char,Traits> s;
    s.copyfmt(os); s.width(0);
    s << '{';
    if (a.size() > 0) {
      s << a[0];
      for (int i=1; i<a.size(); i++)
        s << ", " << a[i];
    }
    s << '}';
    return os << s.str();
  }
 
 
  /*
   * Propagation for action recorder
   *
   */
  template<class View, bool p, bool f>
  forceinline
  Action::Recorder<View,p,f>::Recorder(Space& home, Recorder<View,p,f>& r)
    : NaryPropagator<View,PC_GEN_NONE>(home,r), a(r.a) {
    c.update(home, r.c);
  }
 
  template<class View, bool p, bool f>
  Propagator*
  Action::Recorder<View,p,f>::copy(Space& home) {
    return new (home) Recorder<View,p,f>(home, *this);
  }
 
  template<class View, bool p, bool f>
  inline size_t
  Action::Recorder<View,p,f>::dispose(Space& home) {
    // Delete access to action information
    home.ignore(*this,AP_DISPOSE);
    a.~Action();
    // Cancel remaining advisors
    for (Advisors<Idx> as(c); as(); ++as)
      x[as.advisor().idx()].cancel(home,as.advisor(),true);
    c.dispose(home);
    (void) NaryPropagator<View,PC_GEN_NONE>::dispose(home);
    return sizeof(*this);
  }
 
  template<class View, bool p, bool f>
  PropCost
  Action::Recorder<View,p,f>::cost(const Space&, const ModEventDelta&) const {
    return PropCost::record();
  }
 
  template<class View, bool p, bool f>
  void
  Action::Recorder<View,p,f>::reschedule(Space& home) {
    View::schedule(home,*this,ME_GEN_ASSIGNED);
  }
 
  template<class View, bool p, bool f>
  ExecStatus
  Action::Recorder<View,p,f>::advise(Space& home, Advisor& _a, const Delta&) {
    Idx& a = static_cast<Idx&>(_a);
    if (p) {
      a.propagate();
      return ES_NOFIX;
    } else {
      return x[a.idx()].assigned() ? home.ES_FIX_DISPOSE(c,a) : ES_FIX;
    }
  }
 
  template<class View, bool p, bool f>
  void
  Action::Recorder<View,p,f>::advise(Space&, Advisor& _a) {
    Idx& a = static_cast<Idx&>(_a);
    if (f)
      a.fail();
  }
 
  template<class View, bool p, bool f>
  ExecStatus
  Action::Recorder<View,p,f>::propagate(Space& home, const ModEventDelta&) {
    // Lock action information
    a.acquire();
    for (Advisors<Idx> as(c); as(); ++as) {
      int i = as.advisor().idx();
      if (p && as.advisor().propagated()) {
        as.advisor().clear();
        a.update(i);
        if (x[i].assigned())
          as.advisor().dispose(home,c);
      }
      if (f && as.advisor().failed()) {
        as.advisor().clear();
        a.update(i);
        if (x[i].assigned())
          as.advisor().dispose(home,c);
      }
    }
    a.release();
    return c.empty() ? home.ES_SUBSUMED(*this) : ES_FIX;
  }
 
 
}
 
// STATISTICS: kernel-branch