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.org>
*
* Copyright:
* Christian Schulte, 2012
*
* This file is part of Gecode, the generic constraint
* development environment:
* http://www.gecode.org
*
* 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>
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,
typename BranchTraits<typename View::VarType>::Merit bm);
template<class View>
void init(Home home, ViewArray<View>& x, double d,
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>
class Action::Recorder : public NaryPropagator<View,PC_GEN_NONE> {
protected:
using NaryPropagator<View,PC_GEN_NONE>::x;
class Idx : public Advisor {
protected:
int _info;
public:
Idx(Space& home, Propagator& p, Council<Idx>& c, int i);
Idx(Space& home, Idx& a);
void mark(void);
void unmark(void);
bool marked(void) const;
int idx(void) const;
};
Action a;
Council<Idx> c;
Recorder(Space& home, Recorder<View>& p);
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>
forceinline
Action::Recorder<View>::Idx::Idx(Space& home, Propagator& p,
Council<Idx>& c, int i)
: Advisor(home,p,c), _info(i << 1) {}
template<class View>
forceinline
Action::Recorder<View>::Idx::Idx(Space& home, Idx& a)
: Advisor(home,a), _info(a._info) {
}
template<class View>
forceinline void
Action::Recorder<View>::Idx::mark(void) {
_info |= 1;
}
template<class View>
forceinline bool
Action::Recorder<View>::Idx::marked(void) const {
return (_info & 1) != 0;
}
template<class View>
forceinline void
Action::Recorder<View>::Idx::unmark(void) {
assert(marked());
_info -= 1;
}
template<class View>
forceinline int
Action::Recorder<View>::Idx::idx(void) const {
return _info >> 1;
}
/*
* Posting of action recorder propagator
*
*/
template<class View>
forceinline
Action::Recorder<View>::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>
forceinline ExecStatus
Action::Recorder<View>::post(Home home, ViewArray<View>& x, Action& a) {
(void) new (home) Recorder<View>(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,
typename BranchTraits<typename View::VarType>::Merit bm) {
assert(!*this);
object(*new Storage(home,x,d,bm));
(void) Recorder<View>::post(home,x,*this);
}
template<class View>
forceinline void
Action::init(Home home, ViewArray<View>& x, double d,
typename BranchTraits<typename View::VarType>::Merit bm) {
assert(!*this);
object(*new Storage(home,x,d,bm));
(void) Recorder<View>::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>
forceinline
Action::Recorder<View>::Recorder(Space& home, Recorder<View>& p)
: NaryPropagator<View,PC_GEN_NONE>(home,p), a(p.a) {
c.update(home, p.c);
}
template<class View>
Propagator*
Action::Recorder<View>::copy(Space& home) {
return new (home) Recorder<View>(home, *this);
}
template<class View>
inline size_t
Action::Recorder<View>::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>
PropCost
Action::Recorder<View>::cost(const Space&, const ModEventDelta&) const {
return PropCost::record();
}
template<class View>
void
Action::Recorder<View>::reschedule(Space& home) {
View::schedule(home,*this,ME_GEN_ASSIGNED);
}
template<class View>
ExecStatus
Action::Recorder<View>::advise(Space&, Advisor& a, const Delta&) {
static_cast<Idx&>(a).mark();
return ES_NOFIX;
}
template<class View>
void
Action::Recorder<View>::advise(Space&, Advisor& a) {
static_cast<Idx&>(a).mark();
}
template<class View>
ExecStatus
Action::Recorder<View>::propagate(Space& home, const ModEventDelta&) {
// Lock action information
a.acquire();
for (Advisors<Idx> as(c); as(); ++as) {
int i = as.advisor().idx();
if (as.advisor().marked()) {
as.advisor().unmark();
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
Gecode::Action::Recorder::Idx
Advisor with index and change information.
Definition action.hpp:135
Gecode::Action::Recorder::Idx::Idx
Idx(Space &home, Propagator &p, Council< Idx > &c, int i)
Constructor for creation.
Definition action.hpp:196
Gecode::Action::Recorder::Idx::idx
int idx(void) const
Get index of view.
Definition action.hpp:222
Gecode::Action::Recorder::Idx::unmark
void unmark(void)
Mark advisor as unmodified.
Definition action.hpp:216
Gecode::Action::Recorder::Idx::_info
int _info
Index and mark information.
Definition action.hpp:138
Gecode::Action::Recorder::Idx::mark
void mark(void)
Mark advisor as modified.
Definition action.hpp:206
Gecode::Action::Recorder::Idx::marked
bool marked(void) const
Whether advisor's view has been marked.
Definition action.hpp:211
Gecode::Action::Recorder
Propagator for recording action information.
Definition action.hpp:131
Gecode::Action::Recorder::a
Action a
Access to action information.
Definition action.hpp:154
Gecode::Action::Recorder::dispose
virtual size_t dispose(Space &home)
Delete propagator and return its size.
Definition action.hpp:378
Gecode::Action::Recorder::advise
virtual ExecStatus advise(Space &home, Advisor &a, const Delta &d)
Give advice to propagator.
Definition action.hpp:404
Gecode::Action::Recorder::propagate
virtual ExecStatus propagate(Space &home, const ModEventDelta &med)
Perform propagation.
Definition action.hpp:417
Gecode::Action::Recorder::copy
virtual Propagator * copy(Space &home)
Copy propagator during cloning.
Definition action.hpp:372
Gecode::Action::Recorder::c
Council< Idx > c
The advisor council.
Definition action.hpp:156
Gecode::Action::Recorder::cost
virtual PropCost cost(const Space &home, const ModEventDelta &med) const
Cost function (record so that propagator runs last).
Definition action.hpp:392
Gecode::Action::Recorder::post
static ExecStatus post(Home home, ViewArray< View > &x, Action &a)
Post action recorder propagator.
Definition action.hpp:244
Gecode::Action::Recorder::reschedule
virtual void reschedule(Space &home)
Schedule function.
Definition action.hpp:398
Gecode::Action::Recorder::Recorder
Recorder(Space &home, Recorder< View > &p)
Constructor for cloning p.
Definition action.hpp:365
Gecode::Action::Storage
Object for storing action values.
Definition action.hpp:47
Gecode::Action::Storage::update
void update(int i)
Update action value at position i.
Definition action.hpp:271
Gecode::Action::Storage::invd
double invd
Inverse decay factor.
Definition action.hpp:54
Gecode::Action::Storage::a
double * a
Action values (more follow).
Definition action.hpp:56
Gecode::Action::Storage::m
static Support::Mutex m
Mutex to synchronize globally shared access.
Definition action.hpp:50
Gecode::Action::Storage::Storage
Storage(Home home, ViewArray< View > &x, double d, typename BranchTraits< typename View::VarType >::Merit bm)
Initialize action values.
Definition action.hpp:257
Gecode::Action::Storage::n
int n
Number of action values.
Definition action.hpp:52
Gecode::Action
Class for action management.
Definition action.hpp:42
Gecode::Action::object
Storage & object(void) const
Return object of correct type.
Definition action.hpp:290
Gecode::Action::update
void update(int i)
Update action value at position i.
Definition action.hpp:300
Gecode::Action::operator=
Action & operator=(const Action &a)
Assignment operator.
Definition action.cpp:50
Gecode::Action::size
int size(void) const
Return number of action values.
Definition action.hpp:309
Gecode::Action::operator[]
double operator[](int i) const
Return action value at position i.
Definition action.hpp:304
Gecode::Action::init
void init(Home home, ViewArray< View > &x, double d, typename BranchTraits< typename View::VarType >::Merit bm)
Initialize for views x and decay factor d and action as defined by bm.
Definition action.hpp:335
Gecode::Action::acquire
void acquire(void)
Acquire mutex.
Definition action.hpp:313
Gecode::Action::release
void release(void)
Release mutex.
Definition action.hpp:317
Gecode::Action::def
static const Action def
Default (empty) action information.
Definition action.hpp:103
Gecode::Action::operator<<
std::basic_ostream< Char, Traits > & operator<<(std::basic_ostream< Char, Traits > &os, const Action &a)
Print action values enclosed in curly brackets.
Definition action.hpp:344
Gecode::Action::Action
Action(void)
Construct as not yet intialized.
Definition action.hpp:323
Gecode::Action::~Action
~Action(void)
Destructor.
Definition action.cpp:55
Gecode::Action::decay
void decay(Space &home, double d)
Set decay factor to d.
Definition action.cpp:58
Gecode::ActorLink::Space
friend class Space
Definition core.hpp:595
Gecode::ActorLink::Propagator
friend class Propagator
Definition core.hpp:591
Gecode::Advisor::Advisor
Advisor(Space &home, Propagator &p, Council< A > &c)
Constructor for creation.
Definition core.hpp:3831
Gecode::Advisor::Council
friend class Council
Definition core.hpp:1294
Gecode::Advisors
Class to iterate over advisors of a council.
Definition core.hpp:1266
Gecode::BranchTraits
Traits for branching.
Definition traits.hpp:55
Gecode::Delta
Generic domain change information to be supplied to advisors.
Definition core.hpp:204
Gecode::FloatVal::size
FloatNum size(void) const
Return size of float value (distance between maximum and minimum).
Definition val.hpp:78
Gecode::Home
Home class for posting propagators
Definition core.hpp:856
Gecode::Home::notice
void notice(Actor &a, ActorProperty p, bool duplicate=false)
Notice actor property.
Definition core.hpp:3219
Gecode::NaryPropagator::dispose
virtual size_t dispose(Space &home)
Delete propagator and return its size.
Definition pattern.hpp:513
Gecode::NaryPropagator< View, PC_GEN_NONE >::x
ViewArray< View > x
Definition pattern.hpp:145
Gecode::NaryPropagator< View, PC_GEN_NONE >::NaryPropagator
NaryPropagator(Space &home, NaryPropagator &p)
Gecode::PropCost
Propagation cost.
Definition core.hpp:486
Gecode::PropCost::record
static PropCost record(void)
For recording information (no propagation allowed).
Definition core.hpp:4765
Gecode::Propagator
Base-class for propagators.
Definition core.hpp:1064
Gecode::Propagator::Space
friend class Space
Definition core.hpp:1066
Gecode::Propagator::Advisor
friend class Advisor
Definition core.hpp:1068
Gecode::Propagator::Council
friend class Council
Definition core.hpp:1069
Gecode::Propagator::med
ModEventDelta med
A set of modification events (used during propagation).
Definition core.hpp:1075
Gecode::Propagator::Propagator
Propagator(Home home)
Constructor for posting.
Definition core.hpp:3498
Gecode::SharedHandle::Object
The shared object.
Definition shared-object.hpp:53
Gecode::SharedHandle::SharedHandle
SharedHandle(void)
Create shared handle with no object pointing to.
Definition shared-object.hpp:122
Gecode::SharedHandle::object
SharedHandle::Object * object(void) const
Access to the shared object.
Definition shared-object.hpp:102
Gecode::Space
Computation spaces.
Definition core.hpp:1742
Gecode::Support::Mutex
A mutex for mutual exclausion among several threads.
Definition thread.hpp:96
Gecode::Support::Mutex::release
void release(void)
Release the mutex.
Definition none.hpp:48
Gecode::Support::Mutex::acquire
void acquire(void)
Acquire the mutex and possibly block.
Definition none.hpp:42
Gecode::View
Gecode::ViewArray
View arrays.
Definition array.hpp:253
Gecode::heap
Heap heap
The single global heap.
Definition heap.cpp:44
Gecode::Space::ES_SUBSUMED
ExecStatus ES_SUBSUMED(Propagator &p)
Definition core.hpp:3563
Gecode::Space::ignore
void ignore(Actor &a, ActorProperty p, bool duplicate=false)
Ignore actor property.
Definition core.hpp:4074
Gecode::ModEventDelta
int ModEventDelta
Modification event deltas.
Definition core.hpp:89
Gecode::AP_DISPOSE
@ AP_DISPOSE
Actor must always be disposed.
Definition core.hpp:562
GECODE_KERNEL_EXPORT
#define GECODE_KERNEL_EXPORT
Definition kernel.hh:70
Gecode::Kernel::Config::rescale_limit
const double rescale_limit
Rescale action and afc values when larger than this.
Definition kernel.hh:101
Gecode::Kernel::Config::rescale
const double rescale
Rescale factor for action and afc values.
Definition kernel.hh:99
Gecode
Gecode toplevel namespace
Gecode::operator<<
Archive & operator<<(Archive &e, FloatNumBranch nl)
Definition val-sel.hpp:39
Gecode::ExecStatus
ExecStatus
Definition core.hpp:472
Gecode::ES_OK
@ ES_OK
Execution is okay.
Definition core.hpp:476
Gecode::ES_FIX
@ ES_FIX
Propagation has computed fixpoint.
Definition core.hpp:477
Gecode::ES_NOFIX
@ ES_NOFIX
Propagation has not computed fixpoint.
Definition core.hpp:475
Gecode::ME_GEN_ASSIGNED
const ModEvent ME_GEN_ASSIGNED
Generic modification event: variable is assigned a value.
Definition core.hpp:69
Gecode::PC_GEN_NONE
const PropCond PC_GEN_NONE
Propagation condition to be ignored (convenience).
Definition core.hpp:74
forceinline
#define forceinline
Definition config.hpp:187
GECODE_VTABLE_EXPORT
#define GECODE_VTABLE_EXPORT
Definition support.hh:72