Generated on Tue Oct 22 2013 00:49:00 for Gecode by doxygen 1.8.4
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-04-17 20:35:47 +0200 (Wed, 17 Apr 2013) $ by $Author: schulte $
11  * $Revision: 13584 $
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  Storage(int n0, double d0);
64  ~Storage(void);
66  static void* operator new(size_t s);
68  static void operator delete(void* p);
69  };
70 
74  void update(int i);
76  void decay(int i);
78  void acquire(void);
80  void release(void);
89  void init(int n, double d);
90  public:
92 
93 
100  Activity(void);
103  Activity(const Activity& a);
106  Activity& operator =(const Activity& a);
108  template<class View>
109  Activity(Home home, ViewArray<View>& x, double d);
111  template<class View>
112  void init(Home home, ViewArray<View>& x, double d);
114  bool initialized(void) const;
117  void set(Space& home, double a=0.0);
121 
123 
126  void update(Space& home, bool share, Activity& a);
129  ~Activity(void);
131 
133 
134  double operator [](int i) const;
137  int size(void) const;
139 
141 
144  void decay(Space& home, double d);
147  double decay(const Space& home) const;
149  };
150 
152  template<class View>
153  class Activity::Recorder : public NaryPropagator<View,PC_GEN_NONE> {
154  protected:
157  class Idx : public Advisor {
158  protected:
160  int _info;
161  public:
163  Idx(Space& home, Propagator& p, Council<Idx>& c, int i);
165  Idx(Space& home, bool share, Idx& a);
167  void mark(void);
169  void unmark(void);
171  bool marked(void) const;
173  int idx(void) const;
174  };
180  Recorder(Space& home, bool share, Recorder<View>& p);
181  public:
185  virtual Propagator* copy(Space& home, bool share);
187  virtual PropCost cost(const Space& home, const ModEventDelta& med) const;
189  virtual ExecStatus advise(Space& home, Advisor& a, const Delta& d);
191  virtual ExecStatus propagate(Space& home, const ModEventDelta& med);
193  virtual size_t dispose(Space& home);
195  static ExecStatus post(Home home, ViewArray<View>& x, Activity& a);
196  };
197 
202  template<class Char, class Traits>
203  std::basic_ostream<Char,Traits>&
204  operator <<(std::basic_ostream<Char,Traits>& os,
205  const Activity& a);
206 
207 
208  /*
209  * Advisor for activity recorder
210  *
211  */
212  template<class View>
215  Council<Idx>& c, int i)
216  : Advisor(home,p,c), _info(i << 1) {}
217  template<class View>
220  : Advisor(home,share,a), _info(a._info) {
221  }
222  template<class View>
223  forceinline void
225  _info |= 1;
226  }
227  template<class View>
228  forceinline void
230  _info &= ~1;
231  }
232  template<class View>
233  forceinline bool
235  return (_info & 1) != 0;
236  }
237  template<class View>
238  forceinline int
240  return _info >> 1;
241  }
242 
243 
244 
245  /*
246  * Posting of activity recorder propagator
247  *
248  */
249  template<class View>
252  Activity& a0)
253  : NaryPropagator<View,PC_GEN_NONE>(home,x), a(a0), c(home) {
254  home.notice(*this,AP_DISPOSE);
255  for (int i=x.size(); i--; )
256  if (!x[i].assigned())
257  x[i].subscribe(home,*new (home) Idx(home,*this,c,i));
258  }
259 
260  template<class View>
263  Activity& a) {
264  (void) new (home) Recorder<View>(home,x,a);
265  return ES_OK;
266  }
267 
268 
269  /*
270  * Activity value storage
271  *
272  */
273  forceinline void*
274  Activity::Storage::operator new(size_t s) {
275  return Gecode::heap.ralloc(s);
276  }
277  forceinline void
278  Activity::Storage::operator delete(void* p) {
280  }
282  Activity::Storage::Storage(int n0, double d0)
283  : use_cnt(1), a(heap.alloc<double>(n0)), n(n0), d(d0) {
284  for (int i=n; i--; )
285  a[i] = 0.0;
286  }
289  heap.free<double>(a,n);
290  }
291 
292 
293  /*
294  * Activity
295  *
296  */
297 
298  forceinline void
300  assert(storage != NULL);
301  assert((i >= 0) && (i < storage->n));
302  storage->a[i] += 1.0;
303  }
304  forceinline void
306  assert(storage != NULL);
307  assert((i >= 0) && (i < storage->n));
308  storage->a[i] *= storage->d;
309  }
310  forceinline double
312  assert(storage != NULL);
313  assert((i >= 0) && (i < storage->n));
314  return storage->a[i];
315  }
316  forceinline int
317  Activity::size(void) const {
318  return storage->n;
319  }
320  forceinline void
322  storage->m.acquire();
323  }
324  forceinline void
326  storage->m.release();
327  }
328 
329 
331  Activity::Activity(void) : storage(NULL) {}
332 
333  forceinline bool
334  Activity::initialized(void) const {
335  return storage != NULL;
336  }
337 
338  template<class View>
341  init(x.size(),d);
342  (void) Recorder<View>::post(home,x,*this);
343  }
344  template<class View>
345  forceinline void
347  init(x.size(),d);
348  (void) Recorder<View>::post(home,x,*this);
349  }
350 
351  template<class Char, class Traits>
352  std::basic_ostream<Char,Traits>&
353  operator <<(std::basic_ostream<Char,Traits>& os,
354  const Activity& a) {
355  std::basic_ostringstream<Char,Traits> s;
356  s.copyfmt(os); s.width(0);
357  s << '{';
358  if (a.size() > 0) {
359  s << a[0];
360  for (int i=1; i<a.size(); i++)
361  s << ", " << a[i];
362  }
363  s << '}';
364  return os << s.str();
365  }
366 
367 
368  /*
369  * Propagation for activity recorder
370  *
371  */
372  template<class View>
375  Recorder<View>& p)
376  : NaryPropagator<View,PC_GEN_NONE>(home,share,p) {
377  a.update(home, share, p.a);
378  c.update(home, share, p.c);
379  }
380 
381  template<class View>
382  Propagator*
384  return new (home) Recorder<View>(home, share, *this);
385  }
386 
387  template<class View>
388  inline size_t
390  // Delete access to activity information
391  home.ignore(*this,AP_DISPOSE);
392  a.~Activity();
393  // Cancel remaining advisors
394  for (Advisors<Idx> as(c); as(); ++as)
395  x[as.advisor().idx()].cancel(home,as.advisor());
396  c.dispose(home);
398  return sizeof(*this);
399  }
400 
401  template<class View>
402  PropCost
404  return PropCost::crazy(PropCost::HI,1000);
405  }
406 
407  template<class View>
408  ExecStatus
410  static_cast<Idx&>(a).mark();
411  return ES_NOFIX;
412  }
413 
414  template<class View>
415  ExecStatus
417  // Lock activity information
418  a.acquire();
419  for (Advisors<Idx> as(c); as(); ++as) {
420  int i = as.advisor().idx();
421  if (as.advisor().marked()) {
422  as.advisor().unmark();
423  a.update(i);
424  if (x[i].assigned())
425  as.advisor().dispose(home,c);
426  } else {
427  assert(!x[i].assigned());
428  a.decay(i);
429  }
430  }
431  a.release();
432  return c.empty() ? home.ES_SUBSUMED(*this) : ES_FIX;
433  }
434 
435 }
436 
437 // STATISTICS: kernel-branch