Generated on Thu Mar 16 2017 03:24:15 for Gecode by doxygen 1.8.13
activity.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: 2016-07-01 15:14:18 +0200 (Fri, 01 Jul 2016) $ by $Author: schulte $
11  * $Revision: 15140 $
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 namespace Gecode {
39 
44  class Activity {
45  protected:
46  template<class View>
47  class Recorder;
49  class Storage : public HeapAllocated {
50  public:
54  unsigned int use_cnt;
56  double* a;
58  int n;
60  double d;
62  template<class View>
63  Storage(Home home, ViewArray<View>& x, double d,
66  ~Storage(void);
67  };
68 
72  void update(int i);
74  void decay(int i);
76  void acquire(void);
78  void release(void);
79  public:
81 
82 
89  Activity(void);
92  Activity(const Activity& a);
95  Activity& operator =(const Activity& a);
97  template<class View>
98  Activity(Home home, ViewArray<View>& x, double d,
101  template<class View>
102  void init(Home home, ViewArray<View>& x, double d,
105  bool initialized(void) const;
108  void set(Space& home, double a=0.0);
112 
114 
117  void update(Space& home, bool share, Activity& a);
120  ~Activity(void);
122 
124 
125  double operator [](int i) const;
128  int size(void) const;
130 
132 
135  void decay(Space& home, double d);
138  double decay(const Space& home) const;
140  };
141 
143  template<class View>
144  class Activity::Recorder : public NaryPropagator<View,PC_GEN_NONE> {
145  protected:
148  class Idx : public Advisor {
149  protected:
151  int _info;
152  public:
154  Idx(Space& home, Propagator& p, Council<Idx>& c, int i);
156  Idx(Space& home, bool share, Idx& a);
158  void mark(void);
160  void unmark(void);
162  bool marked(void) const;
164  int idx(void) const;
165  };
171  Recorder(Space& home, bool share, Recorder<View>& p);
172  public:
174  Recorder(Home home, ViewArray<View>& x, Activity& a);
176  virtual Propagator* copy(Space& home, bool share);
178  virtual PropCost cost(const Space& home, const ModEventDelta& med) const;
180  virtual void reschedule(Space& home);
182  virtual ExecStatus advise(Space& home, Advisor& a, const Delta& d);
184  virtual ExecStatus propagate(Space& home, const ModEventDelta& med);
186  virtual size_t dispose(Space& home);
188  static ExecStatus post(Home home, ViewArray<View>& x, Activity& a);
189  };
190 
195  template<class Char, class Traits>
196  std::basic_ostream<Char,Traits>&
197  operator <<(std::basic_ostream<Char,Traits>& os,
198  const Activity& a);
199 
200 
201  /*
202  * Advisor for activity recorder
203  *
204  */
205  template<class View>
208  Council<Idx>& c, int i)
209  : Advisor(home,p,c), _info(i << 1) {}
210  template<class View>
213  : Advisor(home,share,a), _info(a._info) {
214  }
215  template<class View>
216  forceinline void
218  _info |= 1;
219  }
220  template<class View>
221  forceinline void
223  _info &= ~1;
224  }
225  template<class View>
226  forceinline bool
228  return (_info & 1) != 0;
229  }
230  template<class View>
231  forceinline int
233  return _info >> 1;
234  }
235 
236 
237 
238  /*
239  * Posting of activity recorder propagator
240  *
241  */
242  template<class View>
245  Activity& a0)
246  : NaryPropagator<View,PC_GEN_NONE>(home,x), a(a0), c(home) {
247  home.notice(*this,AP_DISPOSE);
248  for (int i=x.size(); i--; )
249  if (!x[i].assigned())
250  x[i].subscribe(home,*new (home) Idx(home,*this,c,i));
251  }
252 
253  template<class View>
256  Activity& a) {
257  (void) new (home) Recorder<View>(home,x,a);
258  return ES_OK;
259  }
260 
261 
262  /*
263  * Activity value storage
264  *
265  */
266  template<class View>
269  typename
271  : use_cnt(1), a(heap.alloc<double>(x.size())), n(x.size()), d(d0) {
272  if (bm != NULL)
273  for (int i=n; i--; ) {
274  typename View::VarType xi(x[i].varimp());
275  a[i] = bm(home,xi,i);
276  }
277  else
278  for (int i=n; i--; )
279  a[i] = 0.0;
280  }
283  heap.free<double>(a,n);
284  }
285 
286 
287  /*
288  * Activity
289  *
290  */
291 
292  forceinline void
294  assert(storage != NULL);
295  assert((i >= 0) && (i < storage->n));
296  storage->a[i] += 1.0;
297  }
298  forceinline void
300  assert(storage != NULL);
301  assert((i >= 0) && (i < storage->n));
302  storage->a[i] *= storage->d;
303  }
304  forceinline double
306  assert(storage != NULL);
307  assert((i >= 0) && (i < storage->n));
308  return storage->a[i];
309  }
310  forceinline int
311  Activity::size(void) const {
312  return storage->n;
313  }
314  forceinline void
316  storage->m.acquire();
317  }
318  forceinline void
320  storage->m.release();
321  }
322 
323 
325  Activity::Activity(void) : storage(NULL) {}
326 
327  forceinline bool
328  Activity::initialized(void) const {
329  return storage != NULL;
330  }
331 
332  template<class View>
336  assert(storage == NULL);
337  storage = new Storage(home,x,d,bm);
338  (void) Recorder<View>::post(home,x,*this);
339  }
340  template<class View>
341  forceinline void
344  assert(storage == NULL);
345  storage = new Storage(home,x,d,bm);
346  (void) Recorder<View>::post(home,x,*this);
347  }
348 
349  template<class Char, class Traits>
350  std::basic_ostream<Char,Traits>&
351  operator <<(std::basic_ostream<Char,Traits>& os,
352  const Activity& a) {
353  std::basic_ostringstream<Char,Traits> s;
354  s.copyfmt(os); s.width(0);
355  s << '{';
356  if (a.size() > 0) {
357  s << a[0];
358  for (int i=1; i<a.size(); i++)
359  s << ", " << a[i];
360  }
361  s << '}';
362  return os << s.str();
363  }
364 
365 
366  /*
367  * Propagation for activity recorder
368  *
369  */
370  template<class View>
373  Recorder<View>& p)
374  : NaryPropagator<View,PC_GEN_NONE>(home,share,p) {
375  a.update(home, share, p.a);
376  c.update(home, share, p.c);
377  }
378 
379  template<class View>
380  Propagator*
382  return new (home) Recorder<View>(home, share, *this);
383  }
384 
385  template<class View>
386  inline size_t
388  // Delete access to activity information
389  home.ignore(*this,AP_DISPOSE);
390  a.~Activity();
391  // Cancel remaining advisors
392  for (Advisors<Idx> as(c); as(); ++as)
393  x[as.advisor().idx()].cancel(home,as.advisor());
394  c.dispose(home);
396  return sizeof(*this);
397  }
398 
399  template<class View>
400  PropCost
402  return PropCost::record();
403  }
404 
405  template<class View>
406  void
408  View::schedule(home,*this,ME_GEN_ASSIGNED);
409  }
410 
411  template<class View>
412  ExecStatus
414  static_cast<Idx&>(a).mark();
415  return ES_NOFIX;
416  }
417 
418  template<class View>
419  ExecStatus
421  // Lock activity information
422  a.acquire();
423  for (Advisors<Idx> as(c); as(); ++as) {
424  int i = as.advisor().idx();
425  if (as.advisor().marked()) {
426  as.advisor().unmark();
427  a.update(i);
428  if (x[i].assigned())
429  as.advisor().dispose(home,c);
430  } else {
431  assert(!x[i].assigned());
432  a.decay(i);
433  }
434  }
435  a.release();
436  return c.empty() ? home.ES_SUBSUMED(*this) : ES_FIX;
437  }
438 
439 }
440 
441 // STATISTICS: kernel-branch
void acquire(void)
Acquire mutex.
Definition: activity.hpp:315
void update(int i)
Update activity value at position i.
Definition: activity.hpp:293
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:228
Advisor with index and change information.
Definition: activity.hpp:148
int size(void) const
Return size of array (number of elements)
Definition: array.hpp:1669
int size(void) const
Return number of activity values.
Definition: activity.hpp:311
ExecStatus ES_SUBSUMED(Propagator &p)
Definition: core.hpp:3484
Actor must always be disposed.
Definition: core.hpp:626
void mark(void)
Mark advisor as modified.
Definition: activity.hpp:217
Object for storing activity values.
Definition: activity.hpp:49
Propagator for recording activity information.
Definition: activity.hpp:47
static ExecStatus post(Home home, ViewArray< View > &x, Activity &a)
Post activity recorder propagator.
Definition: activity.hpp:255
const ModEvent ME_GEN_ASSIGNED
Generic modification event: variable is assigned a value.
Definition: core.hpp:149
virtual ExecStatus advise(Space &home, Advisor &a, const Delta &d)
Give advice to propagator.
Definition: activity.hpp:413
ViewArray< View > x
Array of views.
Definition: propagator.hpp:152
void acquire(void)
Acquire the mutex and possibly block.
Definition: none.hpp:46
bool initialized(void) const
Test whether already initialized.
Definition: activity.hpp:328
Base-class for propagators.
Definition: core.hpp:1012
Base-class for advisors.
Definition: core.hpp:1212
static PropCost record(void)
For recording information (no propagation allowed)
Definition: core.hpp:4546
Class to iterate over advisors of a council.
Definition: core.hpp:229
void * mark(void *p)
Return marked pointer for p.
Propagation has computed fixpoint.
Definition: core.hpp:541
Activity a
Access to activity information.
Definition: activity.hpp:167
Computation spaces.
Definition: core.hpp:1672
Storage(Home home, ViewArray< View > &x, double d, typename BranchTraits< typename View::VarType >::Merit bm)
Allocate activity values.
Definition: activity.hpp:268
A mutex for mutual exclausion among several threads.
Definition: thread.hpp:99
Gecode::IntSet d(v, 7)
void unmark(void)
Mark advisor as unmodified.
Definition: activity.hpp:222
void release(void)
Release the mutex.
Definition: none.hpp:52
Gecode::FloatVal c(-8, 8)
double * a
Activity values.
Definition: activity.hpp:56
struct Gecode::@554::NNF::@60::@62 a
For atomic nodes.
int p
Number of positive literals for node type.
Definition: bool-expr.cpp:236
Gecode::IntArgs i(4, 1, 2, 3, 4)
int n
Number of negative literals for node type.
Definition: bool-expr.cpp:238
Activity(void)
Construct as not yet intialized.
Definition: activity.hpp:325
virtual Propagator * copy(Space &home, bool share)
Copy propagator during cloning.
Definition: activity.hpp:381
void release(void)
Release mutex.
Definition: activity.hpp:319
void subscribe(Space &home, Propagator &p, IntSet &y)
Definition: rel.hpp:75
int n
Number of activity values.
Definition: activity.hpp:58
double operator[](int i) const
Return activity value at position i.
Definition: activity.hpp:305
bool marked(void) const
Whether advisor&#39;s view has been marked.
Definition: activity.hpp:227
size_t size
The size of the propagator (used during subsumption)
Definition: core.hpp:1024
n-ary propagator
Definition: propagator.hpp:149
~Activity(void)
Destructor.
Definition: activity.cpp:74
Activity & operator=(const Activity &a)
Assignment operator.
Definition: activity.cpp:54
#define GECODE_KERNEL_EXPORT
Definition: kernel.hh:70
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: activity.hpp:70
void notice(Actor &a, ActorProperty p, bool duplicate=false)
Notice actor property.
Definition: core.hpp:3253
Council< Idx > c
The advisor council.
Definition: activity.hpp:169
int _info
Index and mark information.
Definition: activity.hpp:151
virtual void reschedule(Space &home)
Schedule function.
Definition: activity.hpp:407
void free(T *b, long unsigned int n)
Delete n objects starting at b.
Definition: heap.hpp:461
Node * x
Pointer to corresponding Boolean expression node.
Definition: bool-expr.cpp:253
Generic domain change information to be supplied to advisors.
Definition: core.hpp:277
void ignore(Actor &a, ActorProperty p, bool duplicate=false)
Ignore actor property.
Definition: core.cpp:167
virtual size_t dispose(Space &home)
Delete propagator and return its size.
Definition: activity.hpp:387
~Storage(void)
Delete object.
Definition: activity.hpp:282
Recorder(Space &home, bool share, Recorder< View > &p)
Constructor for cloning p.
Definition: activity.hpp:372
Propagation cost.
Definition: core.hpp:550
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 activity as defined by bm.
Definition: activity.hpp:342
ExecStatus
Definition: core.hpp:536
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
#define forceinline
Definition: config.hpp:173
static const Activity def
Default (empty) activity information.
Definition: activity.hpp:110
void decay(int i)
Decay activity value at position i.
Definition: activity.hpp:299
Execution is okay.
Definition: core.hpp:540
int idx(void) const
Get index of view.
Definition: activity.hpp:232
Propagation has not computed fixpoint.
Definition: core.hpp:539
virtual PropCost cost(const Space &home, const ModEventDelta &med) const
Cost function (record so that propagator runs last)
Definition: activity.hpp:401
Support::Mutex m
Mutex to synchronize globally shared access.
Definition: activity.hpp:52
unsigned int use_cnt
How many references exist for this object.
Definition: activity.hpp:54
Gecode toplevel namespace
virtual ExecStatus propagate(Space &home, const ModEventDelta &med)
Perform propagation.
Definition: activity.hpp:420
Class for activity management.
Definition: activity.hpp:44
void reschedule(Space &home, Propagator &p, IntSet &y)
Definition: rel.hpp:96
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:905
Base class for heap allocated objects.
Definition: heap.hpp:344
Traits for branching.
Idx(Space &home, Propagator &p, Council< Idx > &c, int i)
Constructor for creation.
Definition: activity.hpp:207
TFE post(PropagatorGroup g)
Only post functions (but not propagators) from g are considered.
double d
Decay factor.
Definition: activity.hpp:60