Generated on Sat May 25 2013 18:00:33 for Gecode by doxygen 1.8.3.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-02-19 13:26:08 +0100 (Tue, 19 Feb 2013) $ by $Author: schulte $
11  * $Revision: 13313 $
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;
118 
120 
121 
123  void update(Space& home, bool share, Activity& a);
126  ~Activity(void);
128 
130 
131 
132  double operator [](int i) const;
134  int size(void) const;
136 
138 
139 
141  void decay(Space& home, double d);
144  double decay(const Space& home) const;
146  };
147 
149  template<class View>
150  class Activity::Recorder : public NaryPropagator<View,PC_GEN_NONE> {
151  protected:
154  class Idx : public Advisor {
155  protected:
157  int _info;
158  public:
160  Idx(Space& home, Propagator& p, Council<Idx>& c, int i);
162  Idx(Space& home, bool share, Idx& a);
164  void mark(void);
166  void unmark(void);
168  bool marked(void) const;
170  int idx(void) const;
171  };
177  Recorder(Space& home, bool share, Recorder<View>& p);
178  public:
182  virtual Propagator* copy(Space& home, bool share);
184  virtual PropCost cost(const Space& home, const ModEventDelta& med) const;
186  virtual ExecStatus advise(Space& home, Advisor& a, const Delta& d);
188  virtual ExecStatus propagate(Space& home, const ModEventDelta& med);
190  virtual size_t dispose(Space& home);
192  static ExecStatus post(Home home, ViewArray<View>& x, Activity& a);
193  };
194 
199  template<class Char, class Traits>
200  std::basic_ostream<Char,Traits>&
201  operator <<(std::basic_ostream<Char,Traits>& os,
202  const Activity& a);
203 
204 
205  /*
206  * Advisor for activity recorder
207  *
208  */
209  template<class View>
212  Council<Idx>& c, int i)
213  : Advisor(home,p,c), _info(i << 1) {}
214  template<class View>
217  : Advisor(home,share,a), _info(a._info) {
218  }
219  template<class View>
220  forceinline void
222  _info |= 1;
223  }
224  template<class View>
225  forceinline void
227  _info &= ~1;
228  }
229  template<class View>
230  forceinline bool
232  return (_info & 1) != 0;
233  }
234  template<class View>
235  forceinline int
237  return _info >> 1;
238  }
239 
240 
241 
242  /*
243  * Posting of activity recorder propagator
244  *
245  */
246  template<class View>
249  Activity& a0)
250  : NaryPropagator<View,PC_GEN_NONE>(home,x), a(a0), c(home) {
251  home.notice(*this,AP_DISPOSE);
252  for (int i=x.size(); i--; )
253  if (!x[i].assigned())
254  x[i].subscribe(home,*new (home) Idx(home,*this,c,i));
255  }
256 
257  template<class View>
260  Activity& a) {
261  (void) new (home) Recorder<View>(home,x,a);
262  return ES_OK;
263  }
264 
265 
266  /*
267  * Activity value storage
268  *
269  */
270  forceinline void*
271  Activity::Storage::operator new(size_t s) {
272  return Gecode::heap.ralloc(s);
273  }
274  forceinline void
275  Activity::Storage::operator delete(void* p) {
277  }
279  Activity::Storage::Storage(int n0, double d0)
280  : use_cnt(1), a(heap.alloc<double>(n0)), n(n0), d(d0) {
281  for (int i=n; i--; )
282  a[i] = 0.0;
283  }
286  heap.free<double>(a,n);
287  }
288 
289 
290  /*
291  * Activity
292  *
293  */
294 
295  forceinline void
297  assert(storage != NULL);
298  assert((i >= 0) && (i < storage->n));
299  storage->a[i] += 1.0;
300  }
301  forceinline void
303  assert(storage != NULL);
304  assert((i >= 0) && (i < storage->n));
305  storage->a[i] *= storage->d;
306  }
307  forceinline double
309  assert(storage != NULL);
310  assert((i >= 0) && (i < storage->n));
311  return storage->a[i];
312  }
313  forceinline int
314  Activity::size(void) const {
315  return storage->n;
316  }
317  forceinline void
319  storage->m.acquire();
320  }
321  forceinline void
323  storage->m.release();
324  }
325 
326 
328  Activity::Activity(void) : storage(NULL) {}
329 
330  forceinline bool
331  Activity::initialized(void) const {
332  return storage != NULL;
333  }
334 
335  template<class View>
338  init(x.size(),d);
339  (void) Recorder<View>::post(home,x,*this);
340  }
341  template<class View>
342  forceinline void
344  init(x.size(),d);
345  (void) Recorder<View>::post(home,x,*this);
346  }
347 
348  template<class Char, class Traits>
349  std::basic_ostream<Char,Traits>&
350  operator <<(std::basic_ostream<Char,Traits>& os,
351  const Activity& a) {
352  std::basic_ostringstream<Char,Traits> s;
353  s.copyfmt(os); s.width(0);
354  s << '{';
355  if (a.size() > 0) {
356  s << a[0];
357  for (int i=1; i<a.size(); i++)
358  s << ", " << a[i];
359  }
360  s << '}';
361  return os << s.str();
362  }
363 
364 
365  /*
366  * Propagation for activity recorder
367  *
368  */
369  template<class View>
372  Recorder<View>& p)
373  : NaryPropagator<View,PC_GEN_NONE>(home,share,p) {
374  a.update(home, share, p.a);
375  c.update(home, share, p.c);
376  }
377 
378  template<class View>
379  Propagator*
381  return new (home) Recorder<View>(home, share, *this);
382  }
383 
384  template<class View>
385  inline size_t
387  // Delete access to activity information
388  home.ignore(*this,AP_DISPOSE);
389  a.~Activity();
390  // Cancel remaining advisors
391  for (Advisors<Idx> as(c); as(); ++as)
392  x[as.advisor().idx()].cancel(home,as.advisor());
393  c.dispose(home);
395  return sizeof(*this);
396  }
397 
398  template<class View>
399  PropCost
401  return PropCost::crazy(PropCost::HI,1000);
402  }
403 
404  template<class View>
405  ExecStatus
407  static_cast<Idx&>(a).mark();
408  return ES_NOFIX;
409  }
410 
411  template<class View>
412  ExecStatus
414  // Lock activity information
415  a.acquire();
416  for (Advisors<Idx> as(c); as(); ++as) {
417  int i = as.advisor().idx();
418  if (as.advisor().marked()) {
419  as.advisor().unmark();
420  a.update(i);
421  if (x[i].assigned())
422  as.advisor().dispose(home,c);
423  } else {
424  assert(!x[i].assigned());
425  a.decay(i);
426  }
427  }
428  a.release();
429  return c.empty() ? home.ES_SUBSUMED(*this) : ES_FIX;
430  }
431 
432 }
433 
434 // STATISTICS: kernel-branch