Generated on Thu Apr 5 2018 19:44:19 for Gecode by doxygen 1.8.13
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  * Last modified:
10  * $Date$ by $Author$
11  * $Revision$
12  *
13  * This file is part of Gecode, the generic constraint
14  * development environment:
15  * http://www.gecode.org
16  *
17  * Permission is hereby granted, free of charge, to any person obtaining
18  * a copy of this software and associated documentation files (the
19  * "Software"), to deal in the Software without restriction, including
20  * without limitation the rights to use, copy, modify, merge, publish,
21  * distribute, sublicense, and/or sell copies of the Software, and to
22  * permit persons to whom the Software is furnished to do so, subject to
23  * the following conditions:
24  *
25  * The above copyright notice and this permission notice shall be
26  * included in all copies or substantial portions of the Software.
27  *
28  * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,
29  * EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF
30  * MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND
31  * NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE
32  * LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION
33  * OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION
34  * WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
35  *
36  */
37 
38 #include <cfloat>
39 
40 namespace Gecode {
41 
46  class Action : public SharedHandle {
47  protected:
48  template<class View>
49  class Recorder;
52  public:
56  int n;
58  double invd;
60  double* a;
62  template<class View>
63  Storage(Home home, ViewArray<View>& x, double d,
66  void update(int i);
69  ~Storage(void);
70  };
72  Storage& object(void) const;
74  void object(Storage& o);
76  void update(int i);
78  void acquire(void);
80  void release(void);
81  public:
83 
84 
91  Action(void);
94  Action(const Action& a);
97  Action& operator =(const Action& a);
99  template<class View>
100  Action(Home home, ViewArray<View>& x, double d,
103  template<class View>
104  void init(Home home, ViewArray<View>& x, double d,
109 
112  ~Action(void);
113 
115 
116  double operator [](int i) const;
119  int size(void) const;
121 
123 
126  void decay(Space& home, double d);
129  double decay(const Space& home) const;
131  };
132 
134  template<class View>
135  class Action::Recorder : public NaryPropagator<View,PC_GEN_NONE> {
136  protected:
139  class Idx : public Advisor {
140  protected:
142  int _info;
143  public:
145  Idx(Space& home, Propagator& p, Council<Idx>& c, int i);
147  Idx(Space& home, Idx& a);
149  void mark(void);
151  void unmark(void);
153  bool marked(void) const;
155  int idx(void) const;
156  };
162  Recorder(Space& home, Recorder<View>& p);
163  public:
165  Recorder(Home home, ViewArray<View>& x, Action& a);
167  virtual Propagator* copy(Space& home);
169  virtual PropCost cost(const Space& home, const ModEventDelta& med) const;
171  virtual void reschedule(Space& home);
173  virtual ExecStatus advise(Space& home, Advisor& a, const Delta& d);
175  virtual void advise(Space& home, Advisor& a);
177  virtual ExecStatus propagate(Space& home, const ModEventDelta& med);
179  virtual size_t dispose(Space& home);
181  static ExecStatus post(Home home, ViewArray<View>& x, Action& a);
182  };
183 
188  template<class Char, class Traits>
189  std::basic_ostream<Char,Traits>&
190  operator <<(std::basic_ostream<Char,Traits>& os,
191  const Action& a);
192 
193 
194  /*
195  * Advisor for action recorder
196  *
197  */
198  template<class View>
201  Council<Idx>& c, int i)
202  : Advisor(home,p,c), _info(i << 1) {}
203  template<class View>
206  : Advisor(home,a), _info(a._info) {
207  }
208  template<class View>
209  forceinline void
211  _info |= 1;
212  }
213  template<class View>
214  forceinline bool
216  return (_info & 1) != 0;
217  }
218  template<class View>
219  forceinline void
221  assert(marked());
222  _info -= 1;
223  }
224  template<class View>
225  forceinline int
227  return _info >> 1;
228  }
229 
230 
231  /*
232  * Posting of action recorder propagator
233  *
234  */
235  template<class View>
238  Action& a0)
239  : NaryPropagator<View,PC_GEN_NONE>(home,x), a(a0), c(home) {
240  home.notice(*this,AP_DISPOSE);
241  for (int i=x.size(); i--; )
242  if (!x[i].assigned())
243  x[i].subscribe(home,*new (home) Idx(home,*this,c,i), true);
244  }
245 
246  template<class View>
249  (void) new (home) Recorder<View>(home,x,a);
250  return ES_OK;
251  }
252 
253 
254  /*
255  * Action value storage
256  *
257  */
258 
259  template<class View>
262  typename
264  : n(x.size()), invd(1.0 / d), a(heap.alloc<double>(x.size())) {
265  if (bm)
266  for (int i=n; i--; ) {
267  typename View::VarType xi(x[i].varimp());
268  a[i] = bm(home,xi,i);
269  }
270  else
271  for (int i=n; i--; )
272  a[i] = 1.0;
273  }
274  forceinline void
276  /*
277  * The trick to inverse decay is from: An Extensible SAT-solver,
278  * Niklas Eén, Niklas Sörensson, SAT 2003.
279  */
280  assert((i >= 0) && (i < n));
281  a[i] = invd * (a[i] + 1.0);
283  for (int j=n; j--; )
285  }
286 
287 
288  /*
289  * Action
290  *
291  */
292 
294  Action::object(void) const {
295  return static_cast<Action::Storage&>(*SharedHandle::object());
296  }
297 
298  forceinline void
301  }
302 
303  forceinline void
305  object().update(i);
306  }
307  forceinline double
308  Action::operator [](int i) const {
309  assert((i >= 0) && (i < object().n));
310  return object().a[i];
311  }
312  forceinline int
313  Action::size(void) const {
314  return object().n;
315  }
316  forceinline void
318  object().m.acquire();
319  }
320  forceinline void
322  object().m.release();
323  }
324 
325 
327  Action::Action(void) {}
328 
329  template<class View>
333  assert(!*this);
334  object(*new Storage(home,x,d,bm));
335  (void) Recorder<View>::post(home,x,*this);
336  }
337  template<class View>
338  forceinline void
341  assert(!*this);
342  object(*new Storage(home,x,d,bm));
343  (void) Recorder<View>::post(home,x,*this);
344  }
345 
346  template<class Char, class Traits>
347  std::basic_ostream<Char,Traits>&
348  operator <<(std::basic_ostream<Char,Traits>& os,
349  const Action& a) {
350  std::basic_ostringstream<Char,Traits> s;
351  s.copyfmt(os); s.width(0);
352  s << '{';
353  if (a.size() > 0) {
354  s << a[0];
355  for (int i=1; i<a.size(); i++)
356  s << ", " << a[i];
357  }
358  s << '}';
359  return os << s.str();
360  }
361 
362 
363  /*
364  * Propagation for action recorder
365  *
366  */
367  template<class View>
370  : NaryPropagator<View,PC_GEN_NONE>(home,p), a(p.a) {
371  c.update(home, p.c);
372  }
373 
374  template<class View>
375  Propagator*
377  return new (home) Recorder<View>(home, *this);
378  }
379 
380  template<class View>
381  inline size_t
383  // Delete access to action information
384  home.ignore(*this,AP_DISPOSE);
385  a.~Action();
386  // Cancel remaining advisors
387  for (Advisors<Idx> as(c); as(); ++as)
388  x[as.advisor().idx()].cancel(home,as.advisor(),true);
389  c.dispose(home);
391  return sizeof(*this);
392  }
393 
394  template<class View>
395  PropCost
397  return PropCost::record();
398  }
399 
400  template<class View>
401  void
403  View::schedule(home,*this,ME_GEN_ASSIGNED);
404  }
405 
406  template<class View>
407  ExecStatus
409  static_cast<Idx&>(a).mark();
410  return ES_NOFIX;
411  }
412 
413  template<class View>
414  void
416  static_cast<Idx&>(a).mark();
417  }
418 
419  template<class View>
420  ExecStatus
422  // Lock action information
423  a.acquire();
424  for (Advisors<Idx> as(c); as(); ++as) {
425  int i = as.advisor().idx();
426  if (as.advisor().marked()) {
427  as.advisor().unmark();
428  a.update(i);
429  if (x[i].assigned())
430  as.advisor().dispose(home,c);
431  }
432  }
433  a.release();
434  return c.empty() ? home.ES_SUBSUMED(*this) : ES_FIX;
435  }
436 
437 
438 }
439 
440 // STATISTICS: kernel-branch
double * a
Action values (more follow)
Definition: action.hpp:60
void mark(void)
Mark advisor as modified.
Definition: action.hpp:210
const PropCond PC_GEN_NONE
Propagation condition to be ignored (convenience)
Definition: core.hpp:76
bool marked(void *p)
Check whether p is marked.
Council of advisors
Definition: core.hpp:156
virtual Propagator * copy(Space &home)
Copy propagator during cloning.
Definition: action.hpp:376
The shared handle.
int size(void) const
Return size of array (number of elements)
Definition: array.hpp:1657
void update(int i)
Update action value at position i.
Definition: action.hpp:275
ExecStatus ES_SUBSUMED(Propagator &p)
Definition: core.hpp:3433
const double rescale_limit
Rescale action and afc values when larger than this.
Definition: kernel.hh:105
Actor must always be disposed.
Definition: core.hpp:554
virtual ExecStatus advise(Space &home, Advisor &a, const Delta &d)
Give advice to propagator.
Definition: action.hpp:408
Council< Idx > c
The advisor council.
Definition: action.hpp:160
Action(void)
Construct as not yet intialized.
Definition: action.hpp:327
int size(void) const
Return number of action values.
Definition: action.hpp:313
~Action(void)
Destructor.
Definition: action.cpp:59
Storage & object(void) const
Return object of correct type.
Definition: action.hpp:294
const ModEvent ME_GEN_ASSIGNED
Generic modification event: variable is assigned a value.
Definition: core.hpp:71
ViewArray< View > x
Array of views.
Definition: pattern.hpp:149
void acquire(void)
Acquire the mutex and possibly block.
Definition: none.hpp:46
Base-class for propagators.
Definition: core.hpp:1016
void acquire(void)
Acquire mutex.
Definition: action.hpp:317
Base-class for advisors.
Definition: core.hpp:1218
virtual void reschedule(Space &home)
Schedule function.
Definition: action.hpp:402
static PropCost record(void)
For recording information (no propagation allowed)
Definition: core.hpp:4612
Class to iterate over advisors of a council.
Definition: core.hpp:157
void * mark(void *p)
Return marked pointer for unmarked pointer p.
void release(void)
Release mutex.
Definition: action.hpp:321
#define forceinline
Definition: config.hpp:182
Propagation has computed fixpoint.
Definition: core.hpp:469
Storage(Home home, ViewArray< View > &x, double d, typename BranchTraits< typename View::VarType >::Merit bm)
Initialize action values.
Definition: action.hpp:261
Computation spaces.
Definition: core.hpp:1668
Advisor with index and change information.
Definition: action.hpp:139
A mutex for mutual exclausion among several threads.
Definition: thread.hpp:105
Gecode::IntSet d(v, 7)
void release(void)
Release the mutex.
Definition: none.hpp:52
virtual PropCost cost(const Space &home, const ModEventDelta &med) const
Cost function (record so that propagator runs last)
Definition: action.hpp:396
Gecode::FloatVal c(-8, 8)
int p
Number of positive literals for node type.
Definition: bool-expr.cpp:236
static Support::Mutex m
Mutex to synchronize globally shared access.
Definition: action.hpp:54
Gecode::IntArgs i(4, 1, 2, 3, 4)
int n
Number of negative literals for node type.
Definition: bool-expr.cpp:238
SharedHandle::Object * object(void) const
Access to the shared object.
int n
Number of action values.
Definition: action.hpp:56
bool marked(void) const
Whether advisor&#39;s view has been marked.
Definition: action.hpp:215
void update(int i)
Update action value at position i.
Definition: action.hpp:304
void decay(Space &home, double d)
Set decay factor to d.
Definition: action.cpp:62
double operator[](int i) const
Return action value at position i.
Definition: action.hpp:308
double invd
Inverse decay factor.
Definition: action.hpp:58
size_t size
The size of the propagator (used during subsumption)
Definition: core.hpp:1029
n-ary propagator
Definition: pattern.hpp:146
#define GECODE_KERNEL_EXPORT
Definition: kernel.hh:74
void * unmark(void *p)
Return unmarked pointer for a marked pointer p.
View arrays.
Definition: array.hpp:228
void notice(Actor &a, ActorProperty p, bool duplicate=false)
Notice actor property.
Definition: core.hpp:3139
int idx(void) const
Get index of view.
Definition: action.hpp:226
int _info
Index and mark information.
Definition: action.hpp:142
virtual ExecStatus propagate(Space &home, const ModEventDelta &med)
Perform propagation.
Definition: action.hpp:421
Generic domain change information to be supplied to advisors.
Definition: core.hpp:205
Idx(Space &home, Propagator &p, Council< Idx > &c, int i)
Constructor for creation.
Definition: action.hpp:200
void ignore(Actor &a, ActorProperty p, bool duplicate=false)
Ignore actor property.
Definition: core.hpp:3944
struct Gecode::@585::NNF::@62::@64 a
For atomic nodes.
Propagation cost.
Definition: core.hpp:478
ExecStatus
Definition: core.hpp:464
Heap heap
The single global heap.
Definition: heap.cpp:48
bool assigned(View x, int v)
Whether x is assigned to value v.
Definition: single.hpp:47
Action & operator=(const Action &a)
Assignment operator.
Definition: action.cpp:54
const double rescale
Rescale factor for action and afc values.
Definition: kernel.hh:103
virtual size_t dispose(Space &home)
Delete propagator and return its size.
Definition: action.hpp:382
Propagator for recording action information.
Definition: action.hpp:49
Action a
Access to action information.
Definition: action.hpp:158
static const Action def
Default (empty) action information.
Definition: action.hpp:107
Post propagator for SetVar x
Definition: set.hh:769
Execution is okay.
Definition: core.hpp:468
Propagation has not computed fixpoint.
Definition: core.hpp:467
void unmark(void)
Mark advisor as unmodified.
Definition: action.hpp:220
Gecode toplevel namespace
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:339
Class for action management.
Definition: action.hpp:46
#define GECODE_VTABLE_EXPORT
Definition: support.hh:76
static ExecStatus post(Home home, ViewArray< View > &x, Action &a)
Post action recorder propagator.
Definition: action.hpp:248
void reschedule(Space &home, Propagator &p, IntSet &y)
Definition: rel.hpp:96
Object for storing action values.
Definition: action.hpp:51
int size(void) const
Return size of array (number of elements)
Definition: array.hpp:1203
int ModEventDelta
Modification event deltas.
Definition: core.hpp:91
Home class for posting propagators
Definition: core.hpp:846
Traits for branching.
Definition: traits.hpp:59
TFE post(PropagatorGroup g)
Only post functions (but not propagators) from g are considered.
Definition: filter.cpp:142
Recorder(Space &home, Recorder< View > &p)
Constructor for cloning p.
Definition: action.hpp:369