00001
00002
00003
00004
00005
00006
00007
00008
00009
00010
00011
00012
00013
00014
00015
00016
00017
00018
00019
00020
00021
00022
00023
00024
00025
00026
00027
00028
00029
00030
00031
00032
00033
00034 #include <cfloat>
00035
00036 namespace Gecode {
00037
00042 class Action : public SharedHandle {
00043 protected:
00044 template<class View>
00045 class Recorder;
00047 class GECODE_VTABLE_EXPORT Storage : public SharedHandle::Object {
00048 public:
00050 GECODE_KERNEL_EXPORT static Support::Mutex m;
00052 int n;
00054 double invd;
00056 double* a;
00058 template<class View>
00059 Storage(Home home, ViewArray<View>& x, double d,
00060 typename BranchTraits<typename View::VarType>::Merit bm);
00062 void update(int i);
00064 GECODE_KERNEL_EXPORT
00065 ~Storage(void);
00066 };
00068 Storage& object(void) const;
00070 void object(Storage& o);
00072 void update(int i);
00074 void acquire(void);
00076 void release(void);
00077 public:
00079
00080
00087 Action(void);
00089 GECODE_KERNEL_EXPORT
00090 Action(const Action& a);
00092 GECODE_KERNEL_EXPORT
00093 Action& operator =(const Action& a);
00095 template<class View>
00096 Action(Home home, ViewArray<View>& x, double d,
00097 typename BranchTraits<typename View::VarType>::Merit bm);
00099 template<class View>
00100 void init(Home home, ViewArray<View>& x, double d,
00101 typename BranchTraits<typename View::VarType>::Merit bm);
00103 GECODE_KERNEL_EXPORT static const Action def;
00105
00107 GECODE_KERNEL_EXPORT
00108 ~Action(void);
00109
00111
00112
00113 double operator [](int i) const;
00115 int size(void) const;
00117
00119
00120
00121 GECODE_KERNEL_EXPORT
00122 void decay(Space& home, double d);
00124 GECODE_KERNEL_EXPORT
00125 double decay(const Space& home) const;
00127 };
00128
00130 template<class View>
00131 class Action::Recorder : public NaryPropagator<View,PC_GEN_NONE> {
00132 protected:
00133 using NaryPropagator<View,PC_GEN_NONE>::x;
00135 class Idx : public Advisor {
00136 protected:
00138 int _info;
00139 public:
00141 Idx(Space& home, Propagator& p, Council<Idx>& c, int i);
00143 Idx(Space& home, Idx& a);
00145 void mark(void);
00147 void unmark(void);
00149 bool marked(void) const;
00151 int idx(void) const;
00152 };
00154 Action a;
00156 Council<Idx> c;
00158 Recorder(Space& home, Recorder<View>& p);
00159 public:
00161 Recorder(Home home, ViewArray<View>& x, Action& a);
00163 virtual Propagator* copy(Space& home);
00165 virtual PropCost cost(const Space& home, const ModEventDelta& med) const;
00167 virtual void reschedule(Space& home);
00169 virtual ExecStatus advise(Space& home, Advisor& a, const Delta& d);
00171 virtual void advise(Space& home, Advisor& a);
00173 virtual ExecStatus propagate(Space& home, const ModEventDelta& med);
00175 virtual size_t dispose(Space& home);
00177 static ExecStatus post(Home home, ViewArray<View>& x, Action& a);
00178 };
00179
00184 template<class Char, class Traits>
00185 std::basic_ostream<Char,Traits>&
00186 operator <<(std::basic_ostream<Char,Traits>& os,
00187 const Action& a);
00188
00189
00190
00191
00192
00193
00194 template<class View>
00195 forceinline
00196 Action::Recorder<View>::Idx::Idx(Space& home, Propagator& p,
00197 Council<Idx>& c, int i)
00198 : Advisor(home,p,c), _info(i << 1) {}
00199 template<class View>
00200 forceinline
00201 Action::Recorder<View>::Idx::Idx(Space& home, Idx& a)
00202 : Advisor(home,a), _info(a._info) {
00203 }
00204 template<class View>
00205 forceinline void
00206 Action::Recorder<View>::Idx::mark(void) {
00207 _info |= 1;
00208 }
00209 template<class View>
00210 forceinline bool
00211 Action::Recorder<View>::Idx::marked(void) const {
00212 return (_info & 1) != 0;
00213 }
00214 template<class View>
00215 forceinline void
00216 Action::Recorder<View>::Idx::unmark(void) {
00217 assert(marked());
00218 _info -= 1;
00219 }
00220 template<class View>
00221 forceinline int
00222 Action::Recorder<View>::Idx::idx(void) const {
00223 return _info >> 1;
00224 }
00225
00226
00227
00228
00229
00230
00231 template<class View>
00232 forceinline
00233 Action::Recorder<View>::Recorder(Home home, ViewArray<View>& x,
00234 Action& a0)
00235 : NaryPropagator<View,PC_GEN_NONE>(home,x), a(a0), c(home) {
00236 home.notice(*this,AP_DISPOSE);
00237 for (int i=x.size(); i--; )
00238 if (!x[i].assigned())
00239 x[i].subscribe(home,*new (home) Idx(home,*this,c,i), true);
00240 }
00241
00242 template<class View>
00243 forceinline ExecStatus
00244 Action::Recorder<View>::post(Home home, ViewArray<View>& x, Action& a) {
00245 (void) new (home) Recorder<View>(home,x,a);
00246 return ES_OK;
00247 }
00248
00249
00250
00251
00252
00253
00254
00255 template<class View>
00256 forceinline
00257 Action::Storage::Storage(Home home, ViewArray<View>& x, double d,
00258 typename
00259 BranchTraits<typename View::VarType>::Merit bm)
00260 : n(x.size()), invd(1.0 / d), a(heap.alloc<double>(x.size())) {
00261 if (bm)
00262 for (int i=n; i--; ) {
00263 typename View::VarType xi(x[i].varimp());
00264 a[i] = bm(home,xi,i);
00265 }
00266 else
00267 for (int i=n; i--; )
00268 a[i] = 1.0;
00269 }
00270 forceinline void
00271 Action::Storage::update(int i) {
00272
00273
00274
00275
00276 assert((i >= 0) && (i < n));
00277 a[i] = invd * (a[i] + 1.0);
00278 if (a[i] > Kernel::Config::rescale_limit)
00279 for (int j=n; j--; )
00280 a[j] *= Kernel::Config::rescale;
00281 }
00282
00283
00284
00285
00286
00287
00288
00289 forceinline Action::Storage&
00290 Action::object(void) const {
00291 return static_cast<Action::Storage&>(*SharedHandle::object());
00292 }
00293
00294 forceinline void
00295 Action::object(Action::Storage& o) {
00296 SharedHandle::object(&o);
00297 }
00298
00299 forceinline void
00300 Action::update(int i) {
00301 object().update(i);
00302 }
00303 forceinline double
00304 Action::operator [](int i) const {
00305 assert((i >= 0) && (i < object().n));
00306 return object().a[i];
00307 }
00308 forceinline int
00309 Action::size(void) const {
00310 return object().n;
00311 }
00312 forceinline void
00313 Action::acquire(void) {
00314 object().m.acquire();
00315 }
00316 forceinline void
00317 Action::release(void) {
00318 object().m.release();
00319 }
00320
00321
00322 forceinline
00323 Action::Action(void) {}
00324
00325 template<class View>
00326 forceinline
00327 Action::Action(Home home, ViewArray<View>& x, double d,
00328 typename BranchTraits<typename View::VarType>::Merit bm) {
00329 assert(!*this);
00330 object(*new Storage(home,x,d,bm));
00331 (void) Recorder<View>::post(home,x,*this);
00332 }
00333 template<class View>
00334 forceinline void
00335 Action::init(Home home, ViewArray<View>& x, double d,
00336 typename BranchTraits<typename View::VarType>::Merit bm) {
00337 assert(!*this);
00338 object(*new Storage(home,x,d,bm));
00339 (void) Recorder<View>::post(home,x,*this);
00340 }
00341
00342 template<class Char, class Traits>
00343 std::basic_ostream<Char,Traits>&
00344 operator <<(std::basic_ostream<Char,Traits>& os,
00345 const Action& a) {
00346 std::basic_ostringstream<Char,Traits> s;
00347 s.copyfmt(os); s.width(0);
00348 s << '{';
00349 if (a.size() > 0) {
00350 s << a[0];
00351 for (int i=1; i<a.size(); i++)
00352 s << ", " << a[i];
00353 }
00354 s << '}';
00355 return os << s.str();
00356 }
00357
00358
00359
00360
00361
00362
00363 template<class View>
00364 forceinline
00365 Action::Recorder<View>::Recorder(Space& home, Recorder<View>& p)
00366 : NaryPropagator<View,PC_GEN_NONE>(home,p), a(p.a) {
00367 c.update(home, p.c);
00368 }
00369
00370 template<class View>
00371 Propagator*
00372 Action::Recorder<View>::copy(Space& home) {
00373 return new (home) Recorder<View>(home, *this);
00374 }
00375
00376 template<class View>
00377 inline size_t
00378 Action::Recorder<View>::dispose(Space& home) {
00379
00380 home.ignore(*this,AP_DISPOSE);
00381 a.~Action();
00382
00383 for (Advisors<Idx> as(c); as(); ++as)
00384 x[as.advisor().idx()].cancel(home,as.advisor(),true);
00385 c.dispose(home);
00386 (void) NaryPropagator<View,PC_GEN_NONE>::dispose(home);
00387 return sizeof(*this);
00388 }
00389
00390 template<class View>
00391 PropCost
00392 Action::Recorder<View>::cost(const Space&, const ModEventDelta&) const {
00393 return PropCost::record();
00394 }
00395
00396 template<class View>
00397 void
00398 Action::Recorder<View>::reschedule(Space& home) {
00399 View::schedule(home,*this,ME_GEN_ASSIGNED);
00400 }
00401
00402 template<class View>
00403 ExecStatus
00404 Action::Recorder<View>::advise(Space&, Advisor& a, const Delta&) {
00405 static_cast<Idx&>(a).mark();
00406 return ES_NOFIX;
00407 }
00408
00409 template<class View>
00410 void
00411 Action::Recorder<View>::advise(Space&, Advisor& a) {
00412 static_cast<Idx&>(a).mark();
00413 }
00414
00415 template<class View>
00416 ExecStatus
00417 Action::Recorder<View>::propagate(Space& home, const ModEventDelta&) {
00418
00419 a.acquire();
00420 for (Advisors<Idx> as(c); as(); ++as) {
00421 int i = as.advisor().idx();
00422 if (as.advisor().marked()) {
00423 as.advisor().unmark();
00424 a.update(i);
00425 if (x[i].assigned())
00426 as.advisor().dispose(home,c);
00427 }
00428 }
00429 a.release();
00430 return c.empty() ? home.ES_SUBSUMED(*this) : ES_FIX;
00431 }
00432
00433
00434 }
00435
00436