Generated on Sat Feb 7 2015 02:01:15 for Gecode by doxygen 1.8.9.1
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: 2013-07-27 00:49:48 +0200 (Sat, 27 Jul 2013) $ by $Author: tack $
11  * $Revision: 13949 $
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 {
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);
68  static void* operator new(size_t s);
70  static void operator delete(void* p);
71  };
72 
76  void update(int i);
78  void decay(int i);
80  void acquire(void);
82  void release(void);
83  public:
85 
86 
93  Activity(void);
96  Activity(const Activity& a);
99  Activity& operator =(const Activity& a);
101  template<class View>
102  Activity(Home home, ViewArray<View>& x, double d,
105  template<class View>
106  void init(Home home, ViewArray<View>& x, double d,
109  bool initialized(void) const;
112  void set(Space& home, double a=0.0);
116 
118 
121  void update(Space& home, bool share, Activity& a);
124  ~Activity(void);
126 
128 
129  double operator [](int i) const;
132  int size(void) const;
134 
136 
139  void decay(Space& home, double d);
142  double decay(const Space& home) const;
144  };
145 
147  template<class View>
148  class Activity::Recorder : public NaryPropagator<View,PC_GEN_NONE> {
149  protected:
152  class Idx : public Advisor {
153  protected:
155  int _info;
156  public:
158  Idx(Space& home, Propagator& p, Council<Idx>& c, int i);
160  Idx(Space& home, bool share, Idx& a);
162  void mark(void);
164  void unmark(void);
166  bool marked(void) const;
168  int idx(void) const;
169  };
175  Recorder(Space& home, bool share, Recorder<View>& p);
176  public:
178  Recorder(Home home, ViewArray<View>& x, Activity& a);
180  virtual Propagator* copy(Space& home, bool share);
182  virtual PropCost cost(const Space& home, const ModEventDelta& med) const;
184  virtual ExecStatus advise(Space& home, Advisor& a, const Delta& d);
186  virtual ExecStatus propagate(Space& home, const ModEventDelta& med);
188  virtual size_t dispose(Space& home);
190  static ExecStatus post(Home home, ViewArray<View>& x, Activity& a);
191  };
192 
197  template<class Char, class Traits>
198  std::basic_ostream<Char,Traits>&
199  operator <<(std::basic_ostream<Char,Traits>& os,
200  const Activity& a);
201 
202 
203  /*
204  * Advisor for activity recorder
205  *
206  */
207  template<class View>
210  Council<Idx>& c, int i)
211  : Advisor(home,p,c), _info(i << 1) {}
212  template<class View>
215  : Advisor(home,share,a), _info(a._info) {
216  }
217  template<class View>
218  forceinline void
220  _info |= 1;
221  }
222  template<class View>
223  forceinline void
225  _info &= ~1;
226  }
227  template<class View>
228  forceinline bool
230  return (_info & 1) != 0;
231  }
232  template<class View>
233  forceinline int
235  return _info >> 1;
236  }
237 
238 
239 
240  /*
241  * Posting of activity recorder propagator
242  *
243  */
244  template<class View>
247  Activity& a0)
248  : NaryPropagator<View,PC_GEN_NONE>(home,x), a(a0), c(home) {
249  home.notice(*this,AP_DISPOSE);
250  for (int i=x.size(); i--; )
251  if (!x[i].assigned())
252  x[i].subscribe(home,*new (home) Idx(home,*this,c,i));
253  }
254 
255  template<class View>
258  Activity& a) {
259  (void) new (home) Recorder<View>(home,x,a);
260  return ES_OK;
261  }
262 
263 
264  /*
265  * Activity value storage
266  *
267  */
268  forceinline void*
269  Activity::Storage::operator new(size_t s) {
270  return Gecode::heap.ralloc(s);
271  }
272  forceinline void
273  Activity::Storage::operator delete(void* p) {
275  }
276  template<class View>
279  typename
281  : use_cnt(1), a(heap.alloc<double>(x.size())), n(x.size()), d(d0) {
282  if (bm != NULL)
283  for (int i=n; i--; ) {
284  typename View::VarType xi(x[i].varimp());
285  a[i] = bm(home,xi,i);
286  }
287  else
288  for (int i=n; i--; )
289  a[i] = 0.0;
290  }
293  heap.free<double>(a,n);
294  }
295 
296 
297  /*
298  * Activity
299  *
300  */
301 
302  forceinline void
304  assert(storage != NULL);
305  assert((i >= 0) && (i < storage->n));
306  storage->a[i] += 1.0;
307  }
308  forceinline void
310  assert(storage != NULL);
311  assert((i >= 0) && (i < storage->n));
312  storage->a[i] *= storage->d;
313  }
314  forceinline double
316  assert(storage != NULL);
317  assert((i >= 0) && (i < storage->n));
318  return storage->a[i];
319  }
320  forceinline int
321  Activity::size(void) const {
322  return storage->n;
323  }
324  forceinline void
326  storage->m.acquire();
327  }
328  forceinline void
330  storage->m.release();
331  }
332 
333 
335  Activity::Activity(void) : storage(NULL) {}
336 
337  forceinline bool
338  Activity::initialized(void) const {
339  return storage != NULL;
340  }
341 
342  template<class View>
346  assert(storage == NULL);
347  storage = new Storage(home,x,d,bm);
348  (void) Recorder<View>::post(home,x,*this);
349  }
350  template<class View>
351  forceinline void
354  assert(storage == NULL);
355  storage = new Storage(home,x,d,bm);
356  (void) Recorder<View>::post(home,x,*this);
357  }
358 
359  template<class Char, class Traits>
360  std::basic_ostream<Char,Traits>&
361  operator <<(std::basic_ostream<Char,Traits>& os,
362  const Activity& a) {
363  std::basic_ostringstream<Char,Traits> s;
364  s.copyfmt(os); s.width(0);
365  s << '{';
366  if (a.size() > 0) {
367  s << a[0];
368  for (int i=1; i<a.size(); i++)
369  s << ", " << a[i];
370  }
371  s << '}';
372  return os << s.str();
373  }
374 
375 
376  /*
377  * Propagation for activity recorder
378  *
379  */
380  template<class View>
383  Recorder<View>& p)
384  : NaryPropagator<View,PC_GEN_NONE>(home,share,p) {
385  a.update(home, share, p.a);
386  c.update(home, share, p.c);
387  }
388 
389  template<class View>
390  Propagator*
392  return new (home) Recorder<View>(home, share, *this);
393  }
394 
395  template<class View>
396  inline size_t
398  // Delete access to activity information
399  home.ignore(*this,AP_DISPOSE);
400  a.~Activity();
401  // Cancel remaining advisors
402  for (Advisors<Idx> as(c); as(); ++as)
403  x[as.advisor().idx()].cancel(home,as.advisor());
404  c.dispose(home);
406  return sizeof(*this);
407  }
408 
409  template<class View>
410  PropCost
412  return PropCost::crazy(PropCost::HI,1000);
413  }
414 
415  template<class View>
416  ExecStatus
418  static_cast<Idx&>(a).mark();
419  return ES_NOFIX;
420  }
421 
422  template<class View>
423  ExecStatus
425  // Lock activity information
426  a.acquire();
427  for (Advisors<Idx> as(c); as(); ++as) {
428  int i = as.advisor().idx();
429  if (as.advisor().marked()) {
430  as.advisor().unmark();
431  a.update(i);
432  if (x[i].assigned())
433  as.advisor().dispose(home,c);
434  } else {
435  assert(!x[i].assigned());
436  a.decay(i);
437  }
438  }
439  a.release();
440  return c.empty() ? home.ES_SUBSUMED(*this) : ES_FIX;
441  }
442 
443 }
444 
445 // STATISTICS: kernel-branch
void acquire(void)
Acquire mutex.
Definition: activity.hpp:325
void update(int i)
Update activity value at position i.
Definition: activity.hpp:303
const PropCond PC_GEN_NONE
Propagation condition to be ignored (convenience)
Definition: core.hpp:158
bool initialized(void) const
Test whether already initialized.
Definition: activity.hpp:338
Council of advisors
Definition: core.hpp:226
Advisor with index and change information.
Definition: activity.hpp:152
ExecStatus ES_SUBSUMED(Propagator &p)
Definition: core.hpp:2973
void rfree(void *p)
Free memory block starting at p.
Definition: heap.hpp:355
Actor must always be disposed.
Definition: core.hpp:610
int size(void) const
Return size of array (number of elements)
Definition: array.hpp:1662
void mark(void)
Mark advisor as modified.
Definition: activity.hpp:219
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:257
virtual PropCost cost(const Space &home, const ModEventDelta &med) const
Cost function (crazy so that propagator is likely to run last)
Definition: activity.hpp:411
virtual ExecStatus advise(Space &home, Advisor &a, const Delta &d)
Give advice to propagator.
Definition: activity.hpp:417
ViewArray< View > x
Array of views.
Definition: propagator.hpp:146
void acquire(void)
Acquire the mutex and possibly block.
Definition: none.hpp:46
Base-class for propagators.
Definition: core.hpp:755
Expensive.
Definition: core.hpp:564
void * ralloc(size_t s)
Allocate s bytes from heap.
Definition: heap.hpp:341
Base-class for advisors.
Definition: core.hpp:926
void set(Space &home, double a=0.0)
Set activity to a.
Definition: activity.cpp:94
Class to iterate over advisors of a council.
Definition: core.hpp:227
void * mark(void *p)
Return marked pointer for p.
Propagation has computed fixpoint.
Definition: core.hpp:528
Activity a
Access to activity information.
Definition: activity.hpp:171
Computation spaces.
Definition: core.hpp:1362
Storage(Home home, ViewArray< View > &x, double d, typename BranchTraits< typename View::VarType >::Merit bm)
Allocate activity values.
Definition: activity.hpp:278
double operator[](int i) const
Return activity value at position i.
Definition: activity.hpp:315
Heap heap
The single global heap.
Definition: heap.cpp:49
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:224
void release(void)
Release the mutex.
Definition: none.hpp:52
Gecode::FloatVal c(-8, 8)
double * a
Activity values.
Definition: activity.hpp:56
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:335
virtual Propagator * copy(Space &home, bool share)
Copy propagator during cloning.
Definition: activity.hpp:391
void release(void)
Release mutex.
Definition: activity.hpp:329
int idx(void) const
Get index of view.
Definition: activity.hpp:234
void subscribe(Space &home, Propagator &p, IntSet &y)
Definition: rel.hpp:74
int n
Number of activity values.
Definition: activity.hpp:58
ModEventDelta med
A set of modification events (used during propagation)
Definition: core.hpp:764
bool marked(void) const
Whether advisor's view has been marked.
Definition: activity.hpp:229
n-ary propagator
Definition: propagator.hpp:143
~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
View arrays.
Definition: array.hpp:234
Storage * storage
Pointer to storage object.
Definition: activity.hpp:74
void notice(Actor &a, ActorProperty p, bool duplicate=false)
Notice actor property.
Definition: core.hpp:2849
Council< Idx > c
The advisor council.
Definition: activity.hpp:173
int _info
Index and mark information.
Definition: activity.hpp:155
void free(T *b, long unsigned int n)
Delete n objects starting at b.
Definition: heap.hpp:426
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:275
void ignore(Actor &a, ActorProperty p, bool duplicate=false)
Ignore actor property.
Definition: core.cpp:169
virtual size_t dispose(Space &home)
Delete propagator and return its size.
Definition: activity.hpp:397
~Storage(void)
Delete object.
Definition: activity.hpp:292
Recorder(Space &home, bool share, Recorder< View > &p)
Constructor for cloning p.
Definition: activity.hpp:382
Propagation cost.
Definition: core.hpp:537
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:352
ExecStatus
Definition: core.hpp:523
bool assigned(View x, int v)
Whether x is assigned to value v.
Definition: single.hpp:47
#define forceinline
Definition: config.hpp:132
static PropCost crazy(PropCost::Mod m, unsigned int n)
Exponential complexity for modifier m and size measure n.
Definition: core.hpp:4014
static const Activity def
Default (empty) activity information.
Definition: activity.hpp:114
void decay(int i)
Decay activity value at position i.
Definition: activity.hpp:309
Execution is okay.
Definition: core.hpp:527
Propagation has not computed fixpoint.
Definition: core.hpp:526
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
int size(void) const
Return size of array (number of elements)
Definition: array.hpp:1215
Gecode toplevel namespace
virtual ExecStatus propagate(Space &home, const ModEventDelta &med)
Perform propagation.
Definition: activity.hpp:424
int size(void) const
Return number of activity values.
Definition: activity.hpp:321
Class for activity management.
Definition: activity.hpp:44
int ModEventDelta
Modification event deltas.
Definition: core.hpp:173
Home class for posting propagators
Definition: core.hpp:717
Traits for branching.
Idx(Space &home, Propagator &p, Council< Idx > &c, int i)
Constructor for creation.
Definition: activity.hpp:209
struct Gecode::@518::NNF::@57::@59 a
For atomic nodes.
double d
Decay factor.
Definition: activity.hpp:60