this repo has no description
dekker.one
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 * This file is part of Gecode, the generic constraint
10 * development environment:
11 * http://www.gecode.org
12 *
13 * Permission is hereby granted, free of charge, to any person obtaining
14 * a copy of this software and associated documentation files (the
15 * "Software"), to deal in the Software without restriction, including
16 * without limitation the rights to use, copy, modify, merge, publish,
17 * distribute, sublicense, and/or sell copies of the Software, and to
18 * permit persons to whom the Software is furnished to do so, subject to
19 * the following conditions:
20 *
21 * The above copyright notice and this permission notice shall be
22 * included in all copies or substantial portions of the Software.
23 *
24 * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,
25 * EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF
26 * MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND
27 * NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE
28 * LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION
29 * OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION
30 * WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
31 *
32 */
33
34#include <cfloat>
35
36namespace Gecode {
37
38 /**
39 * \brief Class for action management
40 *
41 */
42 class Action : public SharedHandle {
43 protected:
44 template<class View, bool p, bool f>
45 class Recorder;
46 /// Object for storing action values
47 class GECODE_VTABLE_EXPORT Storage : public SharedHandle::Object {
48 public:
49 /// Mutex to synchronize globally shared access
50 GECODE_KERNEL_EXPORT static Support::Mutex m;
51 /// Number of action values
52 int n;
53 /// Inverse decay factor
54 double invd;
55 /// Action values (more follow)
56 double* a;
57 /// Initialize action values
58 template<class View>
59 Storage(Home home, ViewArray<View>& x, double d,
60 typename BranchTraits<typename View::VarType>::Merit bm);
61 /// Update action value at position \a i
62 void update(int i);
63 /// Delete object
64 GECODE_KERNEL_EXPORT
65 ~Storage(void);
66 };
67 /// Return object of correct type
68 Storage& object(void) const;
69 /// Set object to \a o
70 void object(Storage& o);
71 /// Update action value at position \a i
72 void update(int i);
73 /// Acquire mutex
74 void acquire(void);
75 /// Release mutex
76 void release(void);
77 public:
78 /// \name Constructors and initialization
79 //@{
80 /**
81 * \brief Construct as not yet intialized
82 *
83 * The only member functions that can be used on a constructed but not
84 * yet initialized action storage is init and the assignment operator.
85 *
86 */
87 Action(void);
88 /// Copy constructor
89 GECODE_KERNEL_EXPORT
90 Action(const Action& a);
91 /// Assignment operator
92 GECODE_KERNEL_EXPORT
93 Action& operator =(const Action& a);
94 /**
95 * \brief Initialize for views \a x and decay factor \a d and action as defined by \a bm
96 *
97 * Count propagation if \a p is true, count failure if \a f is true.
98 */
99 template<class View>
100 Action(Home home, ViewArray<View>& x, double d, bool p, bool f,
101 typename BranchTraits<typename View::VarType>::Merit bm);
102 /**
103 * \brief Initialize for views \a x and decay factor \a d and action as defined by \a bm
104 *
105 * Count propagation if \a p is true, count failure if \a f is true.
106 */
107 template<class View>
108 void init(Home home, ViewArray<View>& x, double d, bool p, bool f,
109 typename BranchTraits<typename View::VarType>::Merit bm);
110 /// Default (empty) action information
111 GECODE_KERNEL_EXPORT static const Action def;
112 //@}
113
114 /// Destructor
115 GECODE_KERNEL_EXPORT
116 ~Action(void);
117
118 /// \name Information access
119 //@{
120 /// Return action value at position \a i
121 double operator [](int i) const;
122 /// Return number of action values
123 int size(void) const;
124 //@}
125
126 /// \name Decay factor for aging
127 //@{
128 /// Set decay factor to \a d
129 GECODE_KERNEL_EXPORT
130 void decay(Space& home, double d);
131 /// Return decay factor
132 GECODE_KERNEL_EXPORT
133 double decay(const Space& home) const;
134 //@}
135 };
136
137 /// Propagator for recording action information
138 template<class View, bool p, bool f>
139 class Action::Recorder : public NaryPropagator<View,PC_GEN_NONE> {
140 protected:
141 using NaryPropagator<View,PC_GEN_NONE>::x;
142 /// Advisor with index and change information
143 class Idx : public Advisor {
144 protected:
145 /// Index and mark/failed information
146 unsigned int _info;
147 public:
148 /// Constructor for creation
149 Idx(Space& home, Propagator& r, Council<Idx>& c, int i);
150 /// Constructor for cloning \a a
151 Idx(Space& home, Idx& a);
152 /// Mark index as propagated
153 void propagate(void);
154 /// Mark index as failed
155 void fail(void);
156 /// Whether index has been propagated
157 bool propagated(void) const;
158 /// Whether index has been failed
159 bool failed(void) const;
160 /// Clear any information
161 void clear(void);
162 /// Get index of view
163 int idx(void) const;
164 };
165 /// Access to action information
166 Action a;
167 /// The advisor council
168 Council<Idx> c;
169 /// Constructor for cloning \a r
170 Recorder(Space& home, Recorder<View,p,f>& r);
171 public:
172 /// Constructor for creation
173 Recorder(Home home, ViewArray<View>& x, Action& a);
174 /// Copy propagator during cloning
175 virtual Propagator* copy(Space& home);
176 /// Cost function (record so that propagator runs last)
177 virtual PropCost cost(const Space& home, const ModEventDelta& med) const;
178 /// Schedule function
179 virtual void reschedule(Space& home);
180 /// Give advice to propagator
181 virtual ExecStatus advise(Space& home, Advisor& a, const Delta& d);
182 /// Give advice to propagator when \a home has failed
183 virtual void advise(Space& home, Advisor& a);
184 /// Perform propagation
185 virtual ExecStatus propagate(Space& home, const ModEventDelta& med);
186 /// Delete propagator and return its size
187 virtual size_t dispose(Space& home);
188 /// Post action recorder propagator
189 static ExecStatus post(Home home, ViewArray<View>& x, Action& a);
190 };
191
192 /**
193 * \brief Print action values enclosed in curly brackets
194 * \relates Action
195 */
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, bool p, bool f>
207 forceinline
208 Action::Recorder<View,p,f>::Idx::Idx(Space& home, Propagator& r,
209 Council<Idx>& c, int i)
210 : Advisor(home,r,c), _info(static_cast<unsigned int>(i) << 2U) {}
211 template<class View, bool p, bool f>
212 forceinline
213 Action::Recorder<View,p,f>::Idx::Idx(Space& home, Idx& a)
214 : Advisor(home,a), _info(a._info) {
215 }
216 template<class View, bool p, bool f>
217 forceinline void
218 Action::Recorder<View,p,f>::Idx::propagate(void) {
219 _info |= 1U;
220 }
221 template<class View, bool p, bool f>
222 forceinline void
223 Action::Recorder<View,p,f>::Idx::fail(void) {
224 _info |= 2U;
225 }
226 template<class View, bool p, bool f>
227 forceinline bool
228 Action::Recorder<View,p,f>::Idx::propagated(void) const {
229 return (_info & 1U) != 0;
230 }
231 template<class View, bool p, bool f>
232 forceinline bool
233 Action::Recorder<View,p,f>::Idx::failed(void) const {
234 return (_info & 2U) != 0;
235 }
236 template<class View, bool p, bool f>
237 forceinline void
238 Action::Recorder<View,p,f>::Idx::clear(void) {
239 _info &= ~3U;
240 }
241 template<class View, bool p, bool f>
242 forceinline int
243 Action::Recorder<View,p,f>::Idx::idx(void) const {
244 return static_cast<int>(_info >> 2);
245 }
246
247
248 /*
249 * Posting of action recorder propagator
250 *
251 */
252 template<class View, bool p, bool f>
253 forceinline
254 Action::Recorder<View,p,f>::Recorder(Home home, ViewArray<View>& x,
255 Action& a0)
256 : NaryPropagator<View,PC_GEN_NONE>(home,x), a(a0), c(home) {
257 home.notice(*this,AP_DISPOSE);
258 for (int i=0; i<x.size(); i++)
259 if (!x[i].assigned())
260 x[i].subscribe(home,*new (home) Idx(home,*this,c,i), true);
261 }
262
263 template<class View, bool p, bool f>
264 forceinline ExecStatus
265 Action::Recorder<View,p,f>::post(Home home, ViewArray<View>& x, Action& a) {
266 (void) new (home) Recorder<View,p,f>(home,x,a);
267 return ES_OK;
268 }
269
270
271 /*
272 * Action value storage
273 *
274 */
275
276 template<class View>
277 forceinline
278 Action::Storage::Storage(Home home, ViewArray<View>& x, double d,
279 typename
280 BranchTraits<typename View::VarType>::Merit bm)
281 : n(x.size()), invd(1.0 / d), a(heap.alloc<double>(x.size())) {
282 if (bm)
283 for (int i=0; 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=0; i<n; i++)
289 a[i] = 1.0;
290 }
291 forceinline void
292 Action::Storage::update(int i) {
293 /*
294 * The trick to inverse decay is from: An Extensible SAT-solver,
295 * Niklas Eén, Niklas Sörensson, SAT 2003.
296 */
297 assert((i >= 0) && (i < n));
298 a[i] = invd * (a[i] + 1.0);
299 if (a[i] > Kernel::Config::rescale_limit)
300 for (int j=0; j<n; j++)
301 a[j] *= Kernel::Config::rescale;
302 }
303
304
305 /*
306 * Action
307 *
308 */
309
310 forceinline Action::Storage&
311 Action::object(void) const {
312 return static_cast<Action::Storage&>(*SharedHandle::object());
313 }
314
315 forceinline void
316 Action::object(Action::Storage& o) {
317 SharedHandle::object(&o);
318 }
319
320 forceinline void
321 Action::update(int i) {
322 object().update(i);
323 }
324 forceinline double
325 Action::operator [](int i) const {
326 assert((i >= 0) && (i < object().n));
327 return object().a[i];
328 }
329 forceinline int
330 Action::size(void) const {
331 return object().n;
332 }
333 forceinline void
334 Action::acquire(void) {
335 object().m.acquire();
336 }
337 forceinline void
338 Action::release(void) {
339 object().m.release();
340 }
341
342
343 forceinline
344 Action::Action(void) {}
345
346 template<class View>
347 forceinline
348 Action::Action(Home home, ViewArray<View>& x, double d,
349 bool p, bool f,
350 typename BranchTraits<typename View::VarType>::Merit bm) {
351 assert(!*this);
352 if (!p && !f)
353 return;
354 object(*new Storage(home,x,d,bm));
355 if (p && f)
356 (void) Recorder<View,true,true>::post(home,x,*this);
357 else if (p && !f)
358 (void) Recorder<View,true,false>::post(home,x,*this);
359 else if (!p && f)
360 (void) Recorder<View,false,true>::post(home,x,*this);
361 }
362 template<class View>
363 forceinline void
364 Action::init(Home home, ViewArray<View>& x, double d,
365 bool p, bool f,
366 typename BranchTraits<typename View::VarType>::Merit bm) {
367 assert(!*this);
368 if (!p && !f)
369 return;
370 object(*new Storage(home,x,d,bm));
371 if (p && f)
372 (void) Recorder<View,true,true>::post(home,x,*this);
373 else if (p && !f)
374 (void) Recorder<View,true,false>::post(home,x,*this);
375 else if (!p && f)
376 (void) Recorder<View,false,true>::post(home,x,*this);
377 }
378
379 template<class Char, class Traits>
380 std::basic_ostream<Char,Traits>&
381 operator <<(std::basic_ostream<Char,Traits>& os,
382 const Action& a) {
383 std::basic_ostringstream<Char,Traits> s;
384 s.copyfmt(os); s.width(0);
385 s << '{';
386 if (a.size() > 0) {
387 s << a[0];
388 for (int i=1; i<a.size(); i++)
389 s << ", " << a[i];
390 }
391 s << '}';
392 return os << s.str();
393 }
394
395
396 /*
397 * Propagation for action recorder
398 *
399 */
400 template<class View, bool p, bool f>
401 forceinline
402 Action::Recorder<View,p,f>::Recorder(Space& home, Recorder<View,p,f>& r)
403 : NaryPropagator<View,PC_GEN_NONE>(home,r), a(r.a) {
404 c.update(home, r.c);
405 }
406
407 template<class View, bool p, bool f>
408 Propagator*
409 Action::Recorder<View,p,f>::copy(Space& home) {
410 return new (home) Recorder<View,p,f>(home, *this);
411 }
412
413 template<class View, bool p, bool f>
414 inline size_t
415 Action::Recorder<View,p,f>::dispose(Space& home) {
416 // Delete access to action information
417 home.ignore(*this,AP_DISPOSE);
418 a.~Action();
419 // Cancel remaining advisors
420 for (Advisors<Idx> as(c); as(); ++as)
421 x[as.advisor().idx()].cancel(home,as.advisor(),true);
422 c.dispose(home);
423 (void) NaryPropagator<View,PC_GEN_NONE>::dispose(home);
424 return sizeof(*this);
425 }
426
427 template<class View, bool p, bool f>
428 PropCost
429 Action::Recorder<View,p,f>::cost(const Space&, const ModEventDelta&) const {
430 return PropCost::record();
431 }
432
433 template<class View, bool p, bool f>
434 void
435 Action::Recorder<View,p,f>::reschedule(Space& home) {
436 View::schedule(home,*this,ME_GEN_ASSIGNED);
437 }
438
439 template<class View, bool p, bool f>
440 ExecStatus
441 Action::Recorder<View,p,f>::advise(Space& home, Advisor& _a, const Delta&) {
442 Idx& a = static_cast<Idx&>(_a);
443 if (p) {
444 a.propagate();
445 return ES_NOFIX;
446 } else {
447 return x[a.idx()].assigned() ? home.ES_FIX_DISPOSE(c,a) : ES_FIX;
448 }
449 }
450
451 template<class View, bool p, bool f>
452 void
453 Action::Recorder<View,p,f>::advise(Space&, Advisor& _a) {
454 Idx& a = static_cast<Idx&>(_a);
455 if (f)
456 a.fail();
457 }
458
459 template<class View, bool p, bool f>
460 ExecStatus
461 Action::Recorder<View,p,f>::propagate(Space& home, const ModEventDelta&) {
462 // Lock action information
463 a.acquire();
464 for (Advisors<Idx> as(c); as(); ++as) {
465 int i = as.advisor().idx();
466 if (p && as.advisor().propagated()) {
467 as.advisor().clear();
468 a.update(i);
469 if (x[i].assigned())
470 as.advisor().dispose(home,c);
471 }
472 if (f && as.advisor().failed()) {
473 as.advisor().clear();
474 a.update(i);
475 if (x[i].assigned())
476 as.advisor().dispose(home,c);
477 }
478 }
479 a.release();
480 return c.empty() ? home.ES_SUBSUMED(*this) : ES_FIX;
481 }
482
483
484}
485
486// STATISTICS: kernel-branch