Generated on Wed Jan 1 2020 10:37:59 for Gecode by doxygen 1.8.16
action.hpp
Go to the documentation of this file.
1 /* -*- mode: C++; c-basic-offset: 2; indent-tabs-mode: nil -*- */
2 /*
3  * Main authors:
4  * Christian Schulte <schulte@gecode.org>
5  *
6  * Copyright:
7  * Christian Schulte, 2012
8  *
9  * This file is part of Gecode, the generic constraint
10  * development environment:
11  * http://www.gecode.org
12  *
13  * Permission is hereby granted, free of charge, to any person obtaining
14  * a copy of this software and associated documentation files (the
15  * "Software"), to deal in the Software without restriction, including
16  * without limitation the rights to use, copy, modify, merge, publish,
17  * distribute, sublicense, and/or sell copies of the Software, and to
18  * permit persons to whom the Software is furnished to do so, subject to
19  * the following conditions:
20  *
21  * The above copyright notice and this permission notice shall be
22  * included in all copies or substantial portions of the Software.
23  *
24  * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,
25  * EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF
26  * MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND
27  * NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE
28  * LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION
29  * OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION
30  * WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
31  *
32  */
33 
34 #include <cfloat>
35 
36 namespace Gecode {
37 
42  class Action : public SharedHandle {
43  protected:
44  template<class View>
45  class Recorder;
48  public:
52  int n;
54  double invd;
56  double* a;
58  template<class View>
59  Storage(Home home, ViewArray<View>& x, double d,
62  void update(int i);
65  ~Storage(void);
66  };
68  Storage& object(void) const;
70  void object(Storage& o);
72  void update(int i);
74  void acquire(void);
76  void release(void);
77  public:
79 
80 
87  Action(void);
90  Action(const Action& a);
93  Action& operator =(const Action& a);
95  template<class View>
96  Action(Home home, ViewArray<View>& x, double d,
99  template<class View>
100  void init(Home home, ViewArray<View>& x, double d,
105 
108  ~Action(void);
109 
111 
112  double operator [](int i) const;
115  int size(void) const;
117 
119 
122  void decay(Space& home, double d);
125  double decay(const Space& home) const;
127  };
128 
130  template<class View>
131  class Action::Recorder : public NaryPropagator<View,PC_GEN_NONE> {
132  protected:
135  class Idx : public Advisor {
136  protected:
138  int _info;
139  public:
141  Idx(Space& home, Propagator& p, Council<Idx>& c, int i);
143  Idx(Space& home, Idx& a);
145  void mark(void);
147  void unmark(void);
149  bool marked(void) const;
151  int idx(void) const;
152  };
158  Recorder(Space& home, Recorder<View>& p);
159  public:
163  virtual Propagator* copy(Space& home);
165  virtual PropCost cost(const Space& home, const ModEventDelta& med) const;
167  virtual void reschedule(Space& home);
169  virtual ExecStatus advise(Space& home, Advisor& a, const Delta& d);
171  virtual void advise(Space& home, Advisor& a);
173  virtual ExecStatus propagate(Space& home, const ModEventDelta& med);
175  virtual size_t dispose(Space& home);
177  static ExecStatus post(Home home, ViewArray<View>& x, Action& a);
178  };
179 
184  template<class Char, class Traits>
185  std::basic_ostream<Char,Traits>&
186  operator <<(std::basic_ostream<Char,Traits>& os,
187  const Action& a);
188 
189 
190  /*
191  * Advisor for action recorder
192  *
193  */
194  template<class View>
197  Council<Idx>& c, int i)
198  : Advisor(home,p,c), _info(i << 1) {}
199  template<class View>
202  : Advisor(home,a), _info(a._info) {
203  }
204  template<class View>
205  forceinline void
207  _info |= 1;
208  }
209  template<class View>
210  forceinline bool
212  return (_info & 1) != 0;
213  }
214  template<class View>
215  forceinline void
217  assert(marked());
218  _info -= 1;
219  }
220  template<class View>
221  forceinline int
223  return _info >> 1;
224  }
225 
226 
227  /*
228  * Posting of action recorder propagator
229  *
230  */
231  template<class View>
234  Action& a0)
235  : NaryPropagator<View,PC_GEN_NONE>(home,x), a(a0), c(home) {
236  home.notice(*this,AP_DISPOSE);
237  for (int i=0; i<x.size(); i++)
238  if (!x[i].assigned())
239  x[i].subscribe(home,*new (home) Idx(home,*this,c,i), true);
240  }
241 
242  template<class View>
245  (void) new (home) Recorder<View>(home,x,a);
246  return ES_OK;
247  }
248 
249 
250  /*
251  * Action value storage
252  *
253  */
254 
255  template<class View>
258  typename
260  : n(x.size()), invd(1.0 / d), a(heap.alloc<double>(x.size())) {
261  if (bm)
262  for (int i=0; i<n; i++) {
263  typename View::VarType xi(x[i].varimp());
264  a[i] = bm(home,xi,i);
265  }
266  else
267  for (int i=0; i<n; i++)
268  a[i] = 1.0;
269  }
270  forceinline void
272  /*
273  * The trick to inverse decay is from: An Extensible SAT-solver,
274  * Niklas Eén, Niklas Sörensson, SAT 2003.
275  */
276  assert((i >= 0) && (i < n));
277  a[i] = invd * (a[i] + 1.0);
279  for (int j=0; j<n; j++)
281  }
282 
283 
284  /*
285  * Action
286  *
287  */
288 
290  Action::object(void) const {
291  return static_cast<Action::Storage&>(*SharedHandle::object());
292  }
293 
294  forceinline void
297  }
298 
299  forceinline void
301  object().update(i);
302  }
303  forceinline double
304  Action::operator [](int i) const {
305  assert((i >= 0) && (i < object().n));
306  return object().a[i];
307  }
308  forceinline int
309  Action::size(void) const {
310  return object().n;
311  }
312  forceinline void
314  object().m.acquire();
315  }
316  forceinline void
318  object().m.release();
319  }
320 
321 
323  Action::Action(void) {}
324 
325  template<class View>
329  assert(!*this);
330  object(*new Storage(home,x,d,bm));
331  (void) Recorder<View>::post(home,x,*this);
332  }
333  template<class View>
334  forceinline void
337  assert(!*this);
338  object(*new Storage(home,x,d,bm));
339  (void) Recorder<View>::post(home,x,*this);
340  }
341 
342  template<class Char, class Traits>
343  std::basic_ostream<Char,Traits>&
344  operator <<(std::basic_ostream<Char,Traits>& os,
345  const Action& a) {
346  std::basic_ostringstream<Char,Traits> s;
347  s.copyfmt(os); s.width(0);
348  s << '{';
349  if (a.size() > 0) {
350  s << a[0];
351  for (int i=1; i<a.size(); i++)
352  s << ", " << a[i];
353  }
354  s << '}';
355  return os << s.str();
356  }
357 
358 
359  /*
360  * Propagation for action recorder
361  *
362  */
363  template<class View>
366  : NaryPropagator<View,PC_GEN_NONE>(home,p), a(p.a) {
367  c.update(home, p.c);
368  }
369 
370  template<class View>
371  Propagator*
373  return new (home) Recorder<View>(home, *this);
374  }
375 
376  template<class View>
377  inline size_t
379  // Delete access to action information
380  home.ignore(*this,AP_DISPOSE);
381  a.~Action();
382  // Cancel remaining advisors
383  for (Advisors<Idx> as(c); as(); ++as)
384  x[as.advisor().idx()].cancel(home,as.advisor(),true);
385  c.dispose(home);
387  return sizeof(*this);
388  }
389 
390  template<class View>
391  PropCost
393  return PropCost::record();
394  }
395 
396  template<class View>
397  void
399  View::schedule(home,*this,ME_GEN_ASSIGNED);
400  }
401 
402  template<class View>
403  ExecStatus
405  static_cast<Idx&>(a).mark();
406  return ES_NOFIX;
407  }
408 
409  template<class View>
410  void
412  static_cast<Idx&>(a).mark();
413  }
414 
415  template<class View>
416  ExecStatus
418  // Lock action information
419  a.acquire();
420  for (Advisors<Idx> as(c); as(); ++as) {
421  int i = as.advisor().idx();
422  if (as.advisor().marked()) {
423  as.advisor().unmark();
424  a.update(i);
425  if (x[i].assigned())
426  as.advisor().dispose(home,c);
427  }
428  }
429  a.release();
430  return c.empty() ? home.ES_SUBSUMED(*this) : ES_FIX;
431  }
432 
433 
434 }
435 
436 // STATISTICS: kernel-branch
void notice(Actor &a, ActorProperty p, bool duplicate=false)
Notice actor property.
Definition: core.hpp:3219
Class for action management.
Definition: action.hpp:42
const ModEvent ME_GEN_ASSIGNED
Generic modification event: variable is assigned a value.
Definition: core.hpp:69
Post propagator for SetVar x
Definition: set.hh:767
static PropCost record(void)
For recording information (no propagation allowed)
Definition: core.hpp:4765
Advisor with index and change information.
Definition: action.hpp:135
#define GECODE_VTABLE_EXPORT
Definition: support.hh:72
virtual void reschedule(Space &home)
Schedule function.
Definition: action.hpp:398
ExecStatus ES_SUBSUMED(Propagator &p)
Definition: core.hpp:3563
void acquire(void)
Acquire the mutex and possibly block.
Definition: none.hpp:42
double operator[](int i) const
Return action value at position i.
Definition: action.hpp:304
bool assigned(View x, int v)
Whether x is assigned to value v.
Definition: single.hpp:43
Class to iterate over advisors of a council.
Definition: core.hpp:156
virtual Propagator * copy(Space &home)
Copy propagator during cloning.
Definition: action.hpp:372
SharedHandle::Object * object(void) const
Access to the shared object.
Storage(Home home, ViewArray< View > &x, double d, typename BranchTraits< typename View::VarType >::Merit bm)
Initialize action values.
Definition: action.hpp:257
The shared object.
Computation spaces.
Definition: core.hpp:1742
ViewArray< View > x
Array of views.
Definition: pattern.hpp:145
virtual size_t dispose(Space &home)
Delete propagator and return its size.
Definition: action.hpp:378
Traits for branching.
Definition: traits.hpp:55
Gecode toplevel namespace
Base-class for propagators.
Definition: core.hpp:1064
Action & operator=(const Action &a)
Assignment operator.
Definition: action.cpp:50
bool marked(void) const
Whether advisor's view has been marked.
Definition: action.hpp:211
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
struct Gecode::@602::NNF::@65::@67 a
For atomic nodes.
Action a
Access to action information.
Definition: action.hpp:154
Generic domain change information to be supplied to advisors.
Definition: core.hpp:204
static const Action def
Default (empty) action information.
Definition: action.hpp:103
Home class for posting propagators
Definition: core.hpp:856
Actor must always be disposed.
Definition: core.hpp:562
int _info
Index and mark information.
Definition: action.hpp:138
Council< Idx > c
The advisor council.
Definition: action.hpp:156
n-ary propagator
Definition: pattern.hpp:142
Action(void)
Construct as not yet intialized.
Definition: action.hpp:323
int size(void) const
Return number of action values.
Definition: action.hpp:309
int n
Number of action values.
Definition: action.hpp:52
virtual PropCost cost(const Space &home, const ModEventDelta &med) const
Cost function (record so that propagator runs last)
Definition: action.hpp:392
ModEventDelta med
A set of modification events (used during propagation)
Definition: core.hpp:1075
int idx(void) const
Get index of view.
Definition: action.hpp:222
#define GECODE_KERNEL_EXPORT
Definition: kernel.hh:70
void acquire(void)
Acquire mutex.
Definition: action.hpp:313
static ExecStatus post(Home home, ViewArray< View > &x, Action &a)
Post action recorder propagator.
Definition: action.hpp:244
~Action(void)
Destructor.
Definition: action.cpp:55
void update(int i)
Update action value at position i.
Definition: action.hpp:271
Heap heap
The single global heap.
Definition: heap.cpp:44
Propagation cost.
Definition: core.hpp:486
double * a
Action values (more follow)
Definition: action.hpp:56
static Support::Mutex m
Mutex to synchronize globally shared access.
Definition: action.hpp:50
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
Council of advisors
Definition: core.hpp:155
void release(void)
Release mutex.
Definition: action.hpp:317
Gecode::IntSet d(v, 7)
Idx(Space &home, Propagator &p, Council< Idx > &c, int i)
Constructor for creation.
Definition: action.hpp:196
Base-class for advisors.
Definition: core.hpp:1292
Propagation has computed fixpoint.
Definition: core.hpp:477
#define forceinline
Definition: config.hpp:185
void update(int i)
Update action value at position i.
Definition: action.hpp:300
double invd
Inverse decay factor.
Definition: action.hpp:54
Recorder(Space &home, Recorder< View > &p)
Constructor for cloning p.
Definition: action.hpp:365
Storage & object(void) const
Return object of correct type.
Definition: action.hpp:290
void ignore(Actor &a, ActorProperty p, bool duplicate=false)
Ignore actor property.
Definition: core.hpp:4074
The shared handle.
void mark(void)
Mark advisor as modified.
Definition: action.hpp:206
virtual ExecStatus advise(Space &home, Advisor &a, const Delta &d)
Give advice to propagator.
Definition: action.hpp:404
Gecode::FloatVal c(-8, 8)
void unmark(void)
Mark advisor as unmodified.
Definition: action.hpp:216
View arrays.
Definition: array.hpp:253
const PropCond PC_GEN_NONE
Propagation condition to be ignored (convenience)
Definition: core.hpp:74
void release(void)
Release the mutex.
Definition: none.hpp:48
A mutex for mutual exclausion among several threads.
Definition: thread.hpp:96
int n
Number of negative literals for node type.
Definition: bool-expr.cpp:234
int ModEventDelta
Modification event deltas.
Definition: core.hpp:89
Propagation has not computed fixpoint.
Definition: core.hpp:475
virtual ExecStatus propagate(Space &home, const ModEventDelta &med)
Perform propagation.
Definition: action.hpp:417
Gecode::IntArgs i({1, 2, 3, 4})
Propagator for recording action information.
Definition: action.hpp:45
void decay(Space &home, double d)
Set decay factor to d.
Definition: action.cpp:58
Execution is okay.
Definition: core.hpp:476
int p
Number of positive literals for node type.
Definition: bool-expr.cpp:232
Archive & operator<<(Archive &e, FloatNumBranch nl)
Definition: val-sel.hpp:39
Object for storing action values.
Definition: action.hpp:47
bool marked(void *p)
Check whether p is marked.
const double rescale
Rescale factor for action and afc values.
Definition: kernel.hh:99
ExecStatus
Definition: core.hpp:472
const double rescale_limit
Rescale action and afc values when larger than this.
Definition: kernel.hh:101