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
00035
00036
00037
00038 #include <cfloat>
00039
00040 namespace Gecode {
00041
00046 class Action {
00047 protected:
00048 template<class View>
00049 class Recorder;
00051 class Storage : public HeapAllocated {
00052 public:
00054 Support::Mutex m;
00056 unsigned int use_cnt;
00058 int n;
00060 double* a;
00062 double invd;
00064 template<class View>
00065 Storage(Home home, ViewArray<View>& x, double d,
00066 typename BranchTraits<typename View::VarType>::Merit bm);
00068 ~Storage(void);
00070 void update(int i);
00071 };
00072
00074 Storage* storage;
00076 void update(int i);
00078 void acquire(void);
00080 void release(void);
00081 public:
00083
00084
00091 Action(void);
00093 GECODE_KERNEL_EXPORT
00094 Action(const Action& a);
00096 GECODE_KERNEL_EXPORT
00097 Action& operator =(const Action& a);
00099 template<class View>
00100 Action(Home home, ViewArray<View>& x, double d,
00101 typename BranchTraits<typename View::VarType>::Merit bm);
00103 template<class View>
00104 void init(Home home, ViewArray<View>& x, double d,
00105 typename BranchTraits<typename View::VarType>::Merit bm);
00107 operator bool(void) const;
00109 GECODE_KERNEL_EXPORT static const Action def;
00111
00113
00114
00115 GECODE_KERNEL_EXPORT
00116 void update(Space& home, bool share, Action& a);
00118 GECODE_KERNEL_EXPORT
00119 ~Action(void);
00121
00123
00124
00125 double operator [](int i) const;
00127 int size(void) const;
00129
00131
00132
00133 GECODE_KERNEL_EXPORT
00134 void decay(Space& home, double d);
00136 GECODE_KERNEL_EXPORT
00137 double decay(const Space& home) const;
00139 };
00140
00142 template<class View>
00143 class Action::Recorder : public NaryPropagator<View,PC_GEN_NONE> {
00144 protected:
00145 using NaryPropagator<View,PC_GEN_NONE>::x;
00147 class Idx : public Advisor {
00148 protected:
00150 int _info;
00151 public:
00153 Idx(Space& home, Propagator& p, Council<Idx>& c, int i);
00155 Idx(Space& home, bool share, Idx& a);
00157 void mark(void);
00159 void unmark(void);
00161 bool marked(void) const;
00163 int idx(void) const;
00164 };
00166 Action a;
00168 Council<Idx> c;
00170 Recorder(Space& home, bool share, Recorder<View>& p);
00171 public:
00173 Recorder(Home home, ViewArray<View>& x, Action& a);
00175 virtual Propagator* copy(Space& home, bool share);
00177 virtual PropCost cost(const Space& home, const ModEventDelta& med) const;
00179 virtual void reschedule(Space& home);
00181 virtual ExecStatus advise(Space& home, Advisor& a, const Delta& d);
00183 virtual void advise(Space& home, Advisor& a);
00185 virtual ExecStatus propagate(Space& home, const ModEventDelta& med);
00187 virtual size_t dispose(Space& home);
00189 static ExecStatus post(Home home, ViewArray<View>& x, Action& a);
00190 };
00191
00196 template<class Char, class Traits>
00197 std::basic_ostream<Char,Traits>&
00198 operator <<(std::basic_ostream<Char,Traits>& os,
00199 const Action& a);
00200
00201
00202
00203
00204
00205
00206 template<class View>
00207 forceinline
00208 Action::Recorder<View>::Idx::Idx(Space& home, Propagator& p,
00209 Council<Idx>& c, int i)
00210 : Advisor(home,p,c), _info(i << 1) {}
00211 template<class View>
00212 forceinline
00213 Action::Recorder<View>::Idx::Idx(Space& home, bool share, Idx& a)
00214 : Advisor(home,share,a), _info(a._info) {
00215 }
00216 template<class View>
00217 forceinline void
00218 Action::Recorder<View>::Idx::mark(void) {
00219 _info |= 1;
00220 }
00221 template<class View>
00222 forceinline bool
00223 Action::Recorder<View>::Idx::marked(void) const {
00224 return (_info & 1) != 0;
00225 }
00226 template<class View>
00227 forceinline void
00228 Action::Recorder<View>::Idx::unmark(void) {
00229 assert(marked());
00230 _info -= 1;
00231 }
00232 template<class View>
00233 forceinline int
00234 Action::Recorder<View>::Idx::idx(void) const {
00235 return _info >> 1;
00236 }
00237
00238
00239
00240
00241
00242
00243 template<class View>
00244 forceinline
00245 Action::Recorder<View>::Recorder(Home home, ViewArray<View>& x,
00246 Action& a0)
00247 : NaryPropagator<View,PC_GEN_NONE>(home,x), a(a0), c(home) {
00248 home.notice(*this,AP_DISPOSE);
00249 for (int i=x.size(); i--; )
00250 if (!x[i].assigned())
00251 x[i].subscribe(home,*new (home) Idx(home,*this,c,i), true);
00252 }
00253
00254 template<class View>
00255 forceinline ExecStatus
00256 Action::Recorder<View>::post(Home home, ViewArray<View>& x, Action& a) {
00257 (void) new (home) Recorder<View>(home,x,a);
00258 return ES_OK;
00259 }
00260
00261
00262
00263
00264
00265
00266 template<class View>
00267 forceinline
00268 Action::Storage::Storage(Home home, ViewArray<View>& x, double d,
00269 typename
00270 BranchTraits<typename View::VarType>::Merit bm)
00271 : use_cnt(1), n(x.size()), a(heap.alloc<double>(x.size())),
00272 invd(1.0 / d) {
00273 if (bm)
00274 for (int i=n; i--; ) {
00275 typename View::VarType xi(x[i].varimp());
00276 a[i] = bm(home,xi,i);
00277 }
00278 else
00279 for (int i=n; i--; )
00280 a[i] = 1.0;
00281 }
00282 forceinline void
00283 Action::Storage::update(int i) {
00284
00285
00286
00287
00288 assert((i >= 0) && (i < n));
00289 a[i] = invd * (a[i] + 1.0);
00290 if (a[i] > Kernel::Config::rescale_limit)
00291 for (int j=n; j--; )
00292 a[j] *= Kernel::Config::rescale;
00293 }
00294 forceinline
00295 Action::Storage::~Storage(void) {
00296 heap.free<double>(a,n);
00297 }
00298
00299
00300
00301
00302
00303
00304
00305 forceinline void
00306 Action::update(int i) {
00307 storage->update(i);
00308 }
00309 forceinline double
00310 Action::operator [](int i) const {
00311 assert((i >= 0) && (i < storage->n));
00312 return storage->a[i];
00313 }
00314 forceinline int
00315 Action::size(void) const {
00316 return storage->n;
00317 }
00318 forceinline void
00319 Action::acquire(void) {
00320 storage->m.acquire();
00321 }
00322 forceinline void
00323 Action::release(void) {
00324 storage->m.release();
00325 }
00326
00327
00328 forceinline
00329 Action::Action(void) : storage(NULL) {}
00330
00331 forceinline
00332 Action::operator bool(void) const {
00333 return storage != NULL;
00334 }
00335
00336 template<class View>
00337 forceinline
00338 Action::Action(Home home, ViewArray<View>& x, double d,
00339 typename BranchTraits<typename View::VarType>::Merit bm) {
00340 assert(storage == NULL);
00341 storage = new Storage(home,x,d,bm);
00342 (void) Recorder<View>::post(home,x,*this);
00343 }
00344 template<class View>
00345 forceinline void
00346 Action::init(Home home, ViewArray<View>& x, double d,
00347 typename BranchTraits<typename View::VarType>::Merit bm) {
00348 assert(storage == NULL);
00349 storage = new Storage(home,x,d,bm);
00350 (void) Recorder<View>::post(home,x,*this);
00351 }
00352
00353 template<class Char, class Traits>
00354 std::basic_ostream<Char,Traits>&
00355 operator <<(std::basic_ostream<Char,Traits>& os,
00356 const Action& a) {
00357 std::basic_ostringstream<Char,Traits> s;
00358 s.copyfmt(os); s.width(0);
00359 s << '{';
00360 if (a.size() > 0) {
00361 s << a[0];
00362 for (int i=1; i<a.size(); i++)
00363 s << ", " << a[i];
00364 }
00365 s << '}';
00366 return os << s.str();
00367 }
00368
00369
00370
00371
00372
00373
00374 template<class View>
00375 forceinline
00376 Action::Recorder<View>::Recorder(Space& home, bool share, Recorder<View>& p)
00377 : NaryPropagator<View,PC_GEN_NONE>(home,share,p) {
00378 a.update(home, share, p.a);
00379 c.update(home, share, p.c);
00380 }
00381
00382 template<class View>
00383 Propagator*
00384 Action::Recorder<View>::copy(Space& home, bool share) {
00385 return new (home) Recorder<View>(home, share, *this);
00386 }
00387
00388 template<class View>
00389 inline size_t
00390 Action::Recorder<View>::dispose(Space& home) {
00391
00392 home.ignore(*this,AP_DISPOSE);
00393 a.~Action();
00394
00395 for (Advisors<Idx> as(c); as(); ++as)
00396 x[as.advisor().idx()].cancel(home,as.advisor(),true);
00397 c.dispose(home);
00398 (void) NaryPropagator<View,PC_GEN_NONE>::dispose(home);
00399 return sizeof(*this);
00400 }
00401
00402 template<class View>
00403 PropCost
00404 Action::Recorder<View>::cost(const Space&, const ModEventDelta&) const {
00405 return PropCost::record();
00406 }
00407
00408 template<class View>
00409 void
00410 Action::Recorder<View>::reschedule(Space& home) {
00411 View::schedule(home,*this,ME_GEN_ASSIGNED);
00412 }
00413
00414 template<class View>
00415 ExecStatus
00416 Action::Recorder<View>::advise(Space&, Advisor& a, const Delta&) {
00417 static_cast<Idx&>(a).mark();
00418 return ES_NOFIX;
00419 }
00420
00421 template<class View>
00422 void
00423 Action::Recorder<View>::advise(Space&, Advisor& a) {
00424 static_cast<Idx&>(a).mark();
00425 }
00426
00427 template<class View>
00428 ExecStatus
00429 Action::Recorder<View>::propagate(Space& home, const ModEventDelta&) {
00430
00431 a.acquire();
00432 for (Advisors<Idx> as(c); as(); ++as) {
00433 int i = as.advisor().idx();
00434 if (as.advisor().marked()) {
00435 as.advisor().unmark();
00436 a.update(i);
00437 if (x[i].assigned())
00438 as.advisor().dispose(home,c);
00439 }
00440 }
00441 a.release();
00442 return c.empty() ? home.ES_SUBSUMED(*this) : ES_FIX;
00443 }
00444
00445
00446 }
00447
00448