Generated on Sat Jan 20 2018 22:21:11 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: 2017-03-09 09:51:58 +0100 (Thu, 09 Mar 2017) $ by $Author: schulte $
11  * $Revision: 15565 $
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 {
47  protected:
48  template<class View>
49  class Recorder;
51  class Storage : public HeapAllocated {
52  public:
56  unsigned int use_cnt;
58  int n;
60  double* a;
62  double invd;
64  template<class View>
65  Storage(Home home, ViewArray<View>& x, double d,
68  ~Storage(void);
70  void update(int i);
71  };
72 
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,
107  operator bool(void) const;
111 
113 
116  void update(Space& home, bool share, Action& a);
119  ~Action(void);
121 
123 
124  double operator [](int i) const;
127  int size(void) const;
129 
131 
134  void decay(Space& home, double d);
137  double decay(const Space& home) const;
139  };
140 
142  template<class View>
143  class Action::Recorder : public NaryPropagator<View,PC_GEN_NONE> {
144  protected:
147  class Idx : public Advisor {
148  protected:
150  int _info;
151  public:
153  Idx(Space& home, Propagator& p, Council<Idx>& c, int i);
155  Idx(Space& home, bool share, Idx& a);
157  void mark(void);
159  void unmark(void);
161  bool marked(void) const;
163  int idx(void) const;
164  };
170  Recorder(Space& home, bool share, Recorder<View>& p);
171  public:
173  Recorder(Home home, ViewArray<View>& x, Action& a);
175  virtual Propagator* copy(Space& home, bool share);
177  virtual PropCost cost(const Space& home, const ModEventDelta& med) const;
179  virtual void reschedule(Space& home);
181  virtual ExecStatus advise(Space& home, Advisor& a, const Delta& d);
183  virtual void advise(Space& home, Advisor& a);
185  virtual ExecStatus propagate(Space& home, const ModEventDelta& med);
187  virtual size_t dispose(Space& home);
189  static ExecStatus post(Home home, ViewArray<View>& x, Action& a);
190  };
191 
196  template<class Char, class Traits>
197  std::basic_ostream<Char,Traits>&
198  operator <<(std::basic_ostream<Char,Traits>& os,
199  const Action& a);
200 
201 
202  /*
203  * Advisor for action recorder
204  *
205  */
206  template<class View>
209  Council<Idx>& c, int i)
210  : Advisor(home,p,c), _info(i << 1) {}
211  template<class View>
214  : Advisor(home,share,a), _info(a._info) {
215  }
216  template<class View>
217  forceinline void
219  _info |= 1;
220  }
221  template<class View>
222  forceinline bool
224  return (_info & 1) != 0;
225  }
226  template<class View>
227  forceinline void
229  assert(marked());
230  _info -= 1;
231  }
232  template<class View>
233  forceinline int
235  return _info >> 1;
236  }
237 
238 
239  /*
240  * Posting of action recorder propagator
241  *
242  */
243  template<class View>
246  Action& a0)
247  : NaryPropagator<View,PC_GEN_NONE>(home,x), a(a0), c(home) {
248  home.notice(*this,AP_DISPOSE);
249  for (int i=x.size(); i--; )
250  if (!x[i].assigned())
251  x[i].subscribe(home,*new (home) Idx(home,*this,c,i), true);
252  }
253 
254  template<class View>
257  (void) new (home) Recorder<View>(home,x,a);
258  return ES_OK;
259  }
260 
261 
262  /*
263  * Action value storage
264  *
265  */
266  template<class View>
269  typename
271  : use_cnt(1), n(x.size()), a(heap.alloc<double>(x.size())),
272  invd(1.0 / d) {
273  if (bm)
274  for (int i=n; i--; ) {
275  typename View::VarType xi(x[i].varimp());
276  a[i] = bm(home,xi,i);
277  }
278  else
279  for (int i=n; i--; )
280  a[i] = 1.0;
281  }
282  forceinline void
284  /*
285  * The trick to inverse decay is from: An Extensible SAT-solver,
286  * Niklas Eén, Niklas Sörensson, SAT 2003.
287  */
288  assert((i >= 0) && (i < n));
289  a[i] = invd * (a[i] + 1.0);
291  for (int j=n; j--; )
293  }
296  heap.free<double>(a,n);
297  }
298 
299 
300  /*
301  * Action
302  *
303  */
304 
305  forceinline void
307  storage->update(i);
308  }
309  forceinline double
310  Action::operator [](int i) const {
311  assert((i >= 0) && (i < storage->n));
312  return storage->a[i];
313  }
314  forceinline int
315  Action::size(void) const {
316  return storage->n;
317  }
318  forceinline void
320  storage->m.acquire();
321  }
322  forceinline void
324  storage->m.release();
325  }
326 
327 
329  Action::Action(void) : storage(NULL) {}
330 
332  Action::operator bool(void) const {
333  return storage != NULL;
334  }
335 
336  template<class View>
340  assert(storage == NULL);
341  storage = new Storage(home,x,d,bm);
342  (void) Recorder<View>::post(home,x,*this);
343  }
344  template<class View>
345  forceinline void
348  assert(storage == NULL);
349  storage = new Storage(home,x,d,bm);
350  (void) Recorder<View>::post(home,x,*this);
351  }
352 
353  template<class Char, class Traits>
354  std::basic_ostream<Char,Traits>&
355  operator <<(std::basic_ostream<Char,Traits>& os,
356  const Action& a) {
357  std::basic_ostringstream<Char,Traits> s;
358  s.copyfmt(os); s.width(0);
359  s << '{';
360  if (a.size() > 0) {
361  s << a[0];
362  for (int i=1; i<a.size(); i++)
363  s << ", " << a[i];
364  }
365  s << '}';
366  return os << s.str();
367  }
368 
369 
370  /*
371  * Propagation for action recorder
372  *
373  */
374  template<class View>
377  : NaryPropagator<View,PC_GEN_NONE>(home,share,p) {
378  a.update(home, share, p.a);
379  c.update(home, share, p.c);
380  }
381 
382  template<class View>
383  Propagator*
384  Action::Recorder<View>::copy(Space& home, bool share) {
385  return new (home) Recorder<View>(home, share, *this);
386  }
387 
388  template<class View>
389  inline size_t
391  // Delete access to action information
392  home.ignore(*this,AP_DISPOSE);
393  a.~Action();
394  // Cancel remaining advisors
395  for (Advisors<Idx> as(c); as(); ++as)
396  x[as.advisor().idx()].cancel(home,as.advisor(),true);
397  c.dispose(home);
399  return sizeof(*this);
400  }
401 
402  template<class View>
403  PropCost
405  return PropCost::record();
406  }
407 
408  template<class View>
409  void
411  View::schedule(home,*this,ME_GEN_ASSIGNED);
412  }
413 
414  template<class View>
415  ExecStatus
417  static_cast<Idx&>(a).mark();
418  return ES_NOFIX;
419  }
420 
421  template<class View>
422  void
424  static_cast<Idx&>(a).mark();
425  }
426 
427  template<class View>
428  ExecStatus
430  // Lock action information
431  a.acquire();
432  for (Advisors<Idx> as(c); as(); ++as) {
433  int i = as.advisor().idx();
434  if (as.advisor().marked()) {
435  as.advisor().unmark();
436  a.update(i);
437  if (x[i].assigned())
438  as.advisor().dispose(home,c);
439  }
440  }
441  a.release();
442  return c.empty() ? home.ES_SUBSUMED(*this) : ES_FIX;
443  }
444 
445 
446 }
447 
448 // STATISTICS: kernel-branch
double * a
Action values.
Definition: action.hpp:60
void mark(void)
Mark advisor as modified.
Definition: action.hpp:218
const PropCond PC_GEN_NONE
Propagation condition to be ignored (convenience)
Definition: core.hpp:154
bool marked(void *p)
Check whether p is marked.
Council of advisors
Definition: core.hpp:232
int size(void) const
Return size of array (number of elements)
Definition: array.hpp:1669
void update(int i)
Update action value at position i.
Definition: action.hpp:283
ExecStatus ES_SUBSUMED(Propagator &p)
Definition: core.hpp:3614
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:630
virtual ExecStatus advise(Space &home, Advisor &a, const Delta &d)
Give advice to propagator.
Definition: action.hpp:416
Council< Idx > c
The advisor council.
Definition: action.hpp:168
Action(void)
Construct as not yet intialized.
Definition: action.hpp:329
int size(void) const
Return number of action values.
Definition: action.hpp:315
~Action(void)
Destructor.
Definition: action.cpp:74
const ModEvent ME_GEN_ASSIGNED
Generic modification event: variable is assigned a value.
Definition: core.hpp:149
ViewArray< View > x
Array of views.
Definition: propagator.hpp:152
void acquire(void)
Acquire the mutex and possibly block.
Definition: none.hpp:46
Base-class for propagators.
Definition: core.hpp:1092
void acquire(void)
Acquire mutex.
Definition: action.hpp:319
Base-class for advisors.
Definition: core.hpp:1294
virtual void reschedule(Space &home)
Schedule function.
Definition: action.hpp:410
static PropCost record(void)
For recording information (no propagation allowed)
Definition: core.hpp:4810
Class to iterate over advisors of a council.
Definition: core.hpp:233
void * mark(void *p)
Return marked pointer for unmarked pointer p.
void release(void)
Release mutex.
Definition: action.hpp:323
Recorder(Space &home, bool share, Recorder< View > &p)
Constructor for cloning p.
Definition: action.hpp:376
Propagation has computed fixpoint.
Definition: core.hpp:545
Storage(Home home, ViewArray< View > &x, double d, typename BranchTraits< typename View::VarType >::Merit bm)
Allocate action values.
Definition: action.hpp:268
Computation spaces.
Definition: core.hpp:1748
Advisor with index and change information.
Definition: action.hpp:147
A mutex for mutual exclausion among several threads.
Definition: thread.hpp:99
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:404
struct Gecode::@579::NNF::@61::@63 a
For atomic nodes.
Gecode::FloatVal c(-8, 8)
int p
Number of positive literals for node type.
Definition: bool-expr.cpp:236
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
int n
Number of action values.
Definition: action.hpp:58
bool marked(void) const
Whether advisor&#39;s view has been marked.
Definition: action.hpp:223
void update(int i)
Update action value at position i.
Definition: action.hpp:306
void subscribe(Space &home, Propagator &p, IntSet &y)
Definition: rel.hpp:75
unsigned int use_cnt
How many references exist for this object.
Definition: action.hpp:56
void decay(Space &home, double d)
Set decay factor to d.
Definition: action.cpp:94
double operator[](int i) const
Return action value at position i.
Definition: action.hpp:310
double invd
Inverse decay factor.
Definition: action.hpp:62
size_t size
The size of the propagator (used during subsumption)
Definition: core.hpp:1105
n-ary propagator
Definition: propagator.hpp:149
#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:234
Storage * storage
Pointer to storage object.
Definition: action.hpp:74
void notice(Actor &a, ActorProperty p, bool duplicate=false)
Notice actor property.
Definition: core.hpp:3321
int idx(void) const
Get index of view.
Definition: action.hpp:234
int _info
Index and mark information.
Definition: action.hpp:150
~Storage(void)
Delete object.
Definition: action.hpp:295
virtual ExecStatus propagate(Space &home, const ModEventDelta &med)
Perform propagation.
Definition: action.hpp:429
void free(T *b, long unsigned int n)
Delete n objects starting at b.
Definition: heap.hpp:461
Generic domain change information to be supplied to advisors.
Definition: core.hpp:281
Idx(Space &home, Propagator &p, Council< Idx > &c, int i)
Constructor for creation.
Definition: action.hpp:208
void ignore(Actor &a, ActorProperty p, bool duplicate=false)
Ignore actor property.
Definition: core.hpp:4141
Propagation cost.
Definition: core.hpp:554
ExecStatus
Definition: core.hpp:540
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
#define forceinline
Definition: config.hpp:173
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:390
virtual Propagator * copy(Space &home, bool share)
Copy propagator during cloning.
Definition: action.hpp:384
Propagator for recording action information.
Definition: action.hpp:49
Action a
Access to action information.
Definition: action.hpp:166
static const Action def
Default (empty) action information.
Definition: action.hpp:109
Post propagator for SetVar x
Definition: set.hh:784
Execution is okay.
Definition: core.hpp:544
Propagation has not computed fixpoint.
Definition: core.hpp:543
void unmark(void)
Mark advisor as unmodified.
Definition: action.hpp:228
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:346
Class for action management.
Definition: action.hpp:46
static ExecStatus post(Home home, ViewArray< View > &x, Action &a)
Post action recorder propagator.
Definition: action.hpp:256
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:1215
int ModEventDelta
Modification event deltas.
Definition: core.hpp:169
Home class for posting propagators
Definition: core.hpp:922
Base class for heap allocated objects.
Definition: heap.hpp:344
Traits for branching.
TFE post(PropagatorGroup g)
Only post functions (but not propagators) from g are considered.