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
00039
00040
00041
00042
00043
00044
00045 namespace Gecode {
00046
00047 class Space;
00048
00071 class SharedHandle {
00072 public:
00080 class Object {
00081 friend class Space;
00082 friend class SharedHandle;
00083 private:
00085 unsigned int use_cnt;
00087 Object* next;
00089 Object* fwd;
00090 public:
00092 Object(void);
00094 virtual Object* copy(void) const = 0;
00096 virtual ~Object(void);
00098 static void* operator new(size_t s);
00100 static void operator delete(void* p);
00101 };
00102 private:
00104 Object* o;
00106 void subscribe(void);
00108 void cancel(void);
00109 public:
00111 SharedHandle(void);
00113 SharedHandle(Object* so);
00115 SharedHandle(const SharedHandle& sh);
00117 SharedHandle& operator=(const SharedHandle& sh);
00119 void update(Space* home, bool share, SharedHandle& sh);
00121 ~SharedHandle(void);
00122 protected:
00124 Object* object(void) const;
00126 void object(Object* n);
00127 };
00128
00129
00138
00139 typedef int ModEvent;
00140
00142 const ModEvent ME_GEN_FAILED = -1;
00144 const ModEvent ME_GEN_NONE = 0;
00146 const ModEvent ME_GEN_ASSIGNED = 1;
00147
00149 typedef int PropCond;
00151 const PropCond PC_GEN_NONE = -1;
00153 const PropCond PC_GEN_ASSIGNED = 0;
00155
00166 typedef int ModEventDelta;
00167
00168 }
00169
00170 #include "gecode/kernel/var-type.icc"
00171
00172 namespace Gecode {
00173
00175 class NoIdxVarImpConf {
00176 public:
00178 static const int idx_c = -1;
00180 static const int idx_d = -1;
00182 static const PropCond pc_max = PC_GEN_ASSIGNED;
00184 static const int free_bits = 0;
00186 static const int med_fst = 0;
00188 static const int med_lst = 0;
00190 static const int med_mask = 0;
00192 static Gecode::ModEvent me_combine(ModEvent me1, ModEvent me2);
00194 static bool med_update(ModEventDelta& med, ModEvent me);
00196 static GECODE_KERNEL_EXPORT const Support::Symbol vti;
00197 };
00198
00199 forceinline ModEvent
00200 NoIdxVarImpConf::me_combine(ModEvent, ModEvent) {
00201 GECODE_NEVER; return 0;
00202 }
00203 forceinline bool
00204 NoIdxVarImpConf::med_update(ModEventDelta&, ModEvent) {
00205 GECODE_NEVER; return false;
00206 }
00207
00208
00209
00210
00211
00212
00213 class ActorLink;
00214 class Actor;
00215 class Propagator;
00216 class Advisor;
00217 template <class A> class Council;
00218 template <class A> class Advisors;
00219 template <class VIC> class VarImp;
00220
00221
00222
00223
00224
00225
00226
00234 class VarImpBase {};
00235
00242 class GECODE_VTABLE_EXPORT VarDisposerBase {
00243 public:
00245 GECODE_KERNEL_EXPORT virtual void dispose(Space* home, VarImpBase* x);
00247 GECODE_KERNEL_EXPORT virtual ~VarDisposerBase(void);
00248 };
00249
00256 template <class VarType>
00257 class VarDisposer : public VarDisposerBase {
00258 public:
00260 VarDisposer(void);
00262 virtual void dispose(Space* home, VarImpBase* x);
00263 };
00264
00266 class Delta {
00267 template <class VIC> friend class VarImp;
00268 private:
00270 ModEvent me;
00271 public:
00273 ModEvent modevent(void) const;
00274 };
00275
00283 template <class VIC>
00284 class VarImp : public VarImpBase {
00285 friend class Space;
00286 friend class Propagator;
00287 template <class VarType> friend class VarDisposer;
00288 private:
00290 static const int idx_c = VIC::idx_c;
00292 static const int idx_d = VIC::idx_d;
00294 static const int free_bits = VIC::free_bits;
00296 unsigned int free_and_bits;
00298 static const Gecode::PropCond pc_max = VIC::pc_max;
00314 ActorLink** idx[pc_max+3];
00315
00322 void update(VarImp* x, ActorLink**& sub);
00329 static void update(Space* home, ActorLink**& sub);
00330
00332 void enter(Space* home, ActorLink* a, PropCond pc);
00334 void resize(Space* home);
00336 void remove(Space* home, ActorLink* a, PropCond pc);
00337
00338 protected:
00339 #ifdef GECODE_HAS_VAR_DISPOSE
00341 static VarImp<VIC>* vars_d(Space* home);
00343 static void vars_d(Space* home, VarImp<VIC>* x);
00344 #endif
00345
00346 public:
00348 VarImp(Space* home);
00350 VarImp(void);
00351
00353
00354
00366 void subscribe(Space* home, Propagator* p, PropCond pc,
00367 bool assigned, ModEvent me, bool schedule);
00373 void cancel(Space* home, Propagator* p, PropCond pc,
00374 bool assigned);
00380 void subscribe(Space* home, Advisor* a, bool assigned);
00386 void cancel(Space* home, Advisor* p, bool assigned);
00388 void cancel(Space* home);
00395 unsigned int degree(void) const;
00401 bool advise(Space* home, ModEvent me, Delta* d);
00403
00405
00406
00407 VarImp(Space* home, bool share, VarImp& x);
00409 bool copied(void) const;
00411 VarImp* forward(void) const;
00413 VarImp* next(void) const;
00415
00417
00418
00419 static void schedule(Space* home, Propagator* p, ModEvent me);
00421 static ModEvent me(ModEventDelta med);
00423 static ModEventDelta med(ModEvent me);
00425 static ModEvent me_combine(ModEvent me1, ModEvent me2);
00427
00429 unsigned int bits(void) const;
00431 unsigned int& bits(void);
00432
00433 protected:
00435 void schedule(Space* home, PropCond pc1, PropCond pc2, ModEvent me);
00436
00437 public:
00439
00440
00441 static void* operator new(size_t,Space*);
00443 static void operator delete(void*,Space*);
00445 static void operator delete(void*);
00447
00449
00450
00451 static const Support::Symbol vti;
00453
00454 };
00455
00456 template <class VIC>
00457 const Support::Symbol
00458 VarImp<VIC>::vti = VIC::vti;
00459
00460
00461 namespace Reflection {
00462 class ActorSpecIter;
00463 class ActorSpec;
00464 class BranchingSpec;
00465 class VarMap;
00466 }
00467
00476 enum ExecStatus {
00477 __ES_SUBSUMED = -2,
00478 ES_FAILED = -1,
00479 ES_NOFIX = 0,
00480 ES_OK = 0,
00481 ES_FIX = 1,
00482 __ES_PARTIAL = 2,
00483 };
00484
00489 enum PropCost {
00490 PC_CRAZY_LO = 0,
00491 PC_CRAZY_HI = 0,
00492 PC_CUBIC_LO = 1,
00493 PC_CUBIC_HI = 1,
00494 PC_QUADRATIC_LO = 2,
00495 PC_QUADRATIC_HI = 2,
00496 PC_LINEAR_HI = 3,
00497 PC_LINEAR_LO = 4,
00498 PC_TERNARY_HI = 5,
00499 PC_BINARY_HI = 6,
00500 PC_TERNARY_LO = 6,
00501 PC_BINARY_LO = 7,
00502 PC_UNARY_LO = 7,
00503 PC_UNARY_HI = 7,
00504 PC_MAX = 7
00505 };
00506
00514 class ActorLink {
00515 friend class Actor;
00516 friend class Propagator;
00517 friend class Advisor;
00518 friend class Branching;
00519 friend class Space;
00520 template <class VIC> friend class VarImp;
00521 private:
00522 ActorLink* _next; ActorLink* _prev;
00523 public:
00525
00526 ActorLink* prev(void) const; void prev(ActorLink*);
00527 ActorLink* next(void) const; void next(ActorLink*);
00528 ActorLink** next_ref(void);
00530
00532 void init(void);
00534 void unlink(void);
00536 void head(ActorLink* al);
00538 void tail(ActorLink* al);
00540 template <class T> static ActorLink* cast(T* a);
00542 template <class T> static const ActorLink* cast(const T* a);
00543 };
00544
00545
00550 class GECODE_VTABLE_EXPORT Actor : private ActorLink {
00551 friend class ActorLink;
00552 friend class Space;
00553 friend class Propagator;
00554 friend class Advisor;
00555 friend class Branching;
00556 friend class Reflection::ActorSpecIter;
00557 template <class VIC> friend class VarImp;
00558 template <class A> friend class Council;
00559 private:
00561 static Actor* cast(ActorLink* al);
00563 static const Actor* cast(const ActorLink* al);
00564 public:
00566 virtual Actor* copy(Space*,bool) = 0;
00567
00569
00570
00571 GECODE_KERNEL_EXPORT
00572 virtual size_t allocated(void) const;
00574 GECODE_KERNEL_EXPORT
00575 virtual size_t dispose(Space* home);
00577 void force(Space* home);
00579 void unforce(Space* home);
00581 static void* operator new(size_t s, Space* home);
00583 static void operator delete(void* p, Space* home);
00585 GECODE_KERNEL_EXPORT
00586 virtual Reflection::ActorSpec spec(const Space* home,
00587 Reflection::VarMap& m) const;
00588 private:
00589 #ifndef __GNUC__
00591 static void operator delete(void* p);
00592 #endif
00594 static void* operator new(size_t s);
00595
00596 #ifdef __GNUC__
00597 public:
00599 GECODE_KERNEL_EXPORT virtual ~Actor(void);
00601 static void operator delete(void* p);
00602 #endif
00603 };
00604
00605
00625 ExecStatus ES_SUBSUMED(Propagator* p, size_t s);
00636 ExecStatus ES_SUBSUMED(Propagator* p, Space* home);
00647 ExecStatus ES_FIX_PARTIAL(Propagator* p, ModEventDelta med);
00658 ExecStatus ES_NOFIX_PARTIAL(Propagator* p, ModEventDelta med);
00659
00664 class GECODE_VTABLE_EXPORT Propagator : public Actor {
00665 friend class ActorLink;
00666 friend class Space;
00667 template <class VIC> friend class VarImp;
00668 friend ExecStatus ES_SUBSUMED(Propagator*, size_t);
00669 friend ExecStatus ES_SUBSUMED(Propagator*, Space*);
00670 friend ExecStatus ES_FIX_PARTIAL(Propagator*, ModEventDelta);
00671 friend ExecStatus ES_NOFIX_PARTIAL(Propagator*, ModEventDelta);
00672 friend class Advisor;
00673 template <class A> friend class Council;
00674 private:
00675 union {
00677 ModEventDelta med;
00679 size_t size;
00681 Gecode::ActorLink* advisors;
00682 } u;
00684 static Propagator* cast(ActorLink* al);
00686 static const Propagator* cast(const ActorLink* al);
00687 protected:
00689 Propagator(Space* home);
00691 Propagator(Space* home, bool share, Propagator& p);
00692
00693 public:
00695
00696
00719 virtual ExecStatus propagate(Space* home, ModEventDelta med) = 0;
00721 virtual PropCost cost(ModEventDelta med) const = 0;
00751 GECODE_KERNEL_EXPORT
00752 virtual ExecStatus advise(Space* home, Advisor* a, const Delta* d);
00754 };
00755
00756
00764 template <class A>
00765 class Council {
00766 friend class Advisor;
00767 friend class Advisors<A>;
00768 private:
00770 mutable ActorLink* advisors;
00771 public:
00773 Council(void);
00775 Council(Space* home);
00777 bool empty(void) const;
00779 void update(Space* home, bool share, Council<A>& c);
00781 void dispose(Space* home);
00782 };
00783
00784
00789 template <class A>
00790 class Advisors {
00791 private:
00793 ActorLink* a;
00794 public:
00796 Advisors(const Council<A>& c);
00798 bool operator()(void) const;
00800 void operator++(void);
00802 A* advisor(void) const;
00803 };
00804
00805
00817 template <class A>
00818 ExecStatus ES_SUBSUMED_FIX(A* a, Space* home, Council<A>& c);
00830 template <class A>
00831 ExecStatus ES_SUBSUMED_NOFIX(A* a, Space* home, Council<A>& c);
00832
00843 class Advisor : private ActorLink {
00844 template <class VIC> friend class VarImp;
00845 template <class A> friend class Council;
00846 template <class A> friend class Advisors;
00847 private:
00849 bool disposed(void) const;
00850 protected:
00852 Propagator* propagator(void) const;
00853 public:
00855 template <class A>
00856 Advisor(Space* home, Propagator* p, Council<A>& c);
00858 Advisor(Space* home, bool share, Advisor& a);
00859
00861
00862
00863 template <class A>
00864 void dispose(Space* home, Council<A>& c);
00866 static void* operator new(size_t s, Space* home);
00868 static void operator delete(void* p, Space* home);
00870 private:
00871 #ifndef __GNUC__
00873 static void operator delete(void* p);
00874 #endif
00876 static void* operator new(size_t s);
00877 };
00878
00879
00880 class Branching;
00881
00891 class BranchingDesc {
00892 friend class Space;
00893 friend class Reflection::BranchingSpec;
00894 private:
00895 unsigned int _id;
00896 unsigned int _alt;
00897
00899 unsigned int id(void) const;
00900 protected:
00902 BranchingDesc(const Branching* b, const unsigned int a);
00903 public:
00905 unsigned int alternatives(void) const;
00907 GECODE_KERNEL_EXPORT virtual ~BranchingDesc(void);
00909 virtual size_t size(void) const = 0;
00911 static void* operator new(size_t);
00913 static void operator delete(void*);
00914 };
00915
00925 class GECODE_VTABLE_EXPORT Branching : public Actor {
00926 friend class ActorLink;
00927 friend class Space;
00928 friend class BranchingDesc;
00929 friend class Reflection::ActorSpecIter;
00930 private:
00932 unsigned int id;
00934 static Branching* cast(ActorLink* al);
00936 static const Branching* cast(const ActorLink* al);
00937 protected:
00939 Branching(Space* home);
00941 Branching(Space* home, bool share, Branching& b);
00942
00943 public:
00945
00946
00954 virtual bool status(const Space* home) const = 0;
00964 virtual const BranchingDesc* description(const Space* home) const = 0;
00972 virtual ExecStatus commit(Space* home, const BranchingDesc* d,
00973 unsigned int a) = 0;
00975
00977
00978
00979 virtual GECODE_KERNEL_EXPORT Reflection::BranchingSpec
00980 branchingSpec(const Space* home,
00981 Reflection::VarMap& m, const BranchingDesc* d) const;
00983 };
00984
00985
00986
00991 enum SpaceStatus {
00992 SS_FAILED,
00993 SS_SOLVED,
00994 SS_BRANCH
00995 };
00996
01000 class GECODE_VTABLE_EXPORT Space {
01001 friend class Actor;
01002 friend class Propagator;
01003 friend class Branching;
01004 friend class Advisor;
01005 friend class Reflection::ActorSpecIter;
01006 template <class VIC> friend class VarImp;
01007 template <class VarType> friend class VarDisposer;
01008 friend class SharedHandle;
01009 private:
01011 MemoryManager mm;
01018 ActorLink a_actors;
01024 Branching* b_status;
01036 Branching* b_commit;
01037 union {
01039 struct {
01052 ActorLink* active;
01054 ActorLink queue[PC_MAX+1];
01056 unsigned int branch_id;
01058 unsigned int n_sub;
01059 } p;
01061 struct {
01063 VarImpBase* vars_u[AllVarConf::idx_c];
01065 VarImpBase* vars_noidx;
01067 SharedHandle::Object* shared;
01068 } c;
01069 } pc;
01071 void enqueue(Propagator* p);
01076 #ifdef GECODE_HAS_VAR_DISPOSE
01078 GECODE_KERNEL_EXPORT static VarDisposerBase* vd[AllVarConf::idx_d];
01080 VarImpBase* _vars_d[AllVarConf::idx_d];
01082 template <class VIC> VarImpBase* vars_d(void) const;
01084 template <class VIC> void vars_d(VarImpBase* x);
01085 #endif
01087 void update(ActorLink** sub);
01088
01089
01091 Actor** d_fst;
01093 Actor** d_cur;
01095 Actor** d_lst;
01097 GECODE_KERNEL_EXPORT void d_resize(void);
01098
01100 GECODE_KERNEL_EXPORT static unsigned long int unused_uli;
01101 public:
01106 GECODE_KERNEL_EXPORT Space(void);
01111 GECODE_KERNEL_EXPORT virtual ~Space(void);
01122 GECODE_KERNEL_EXPORT Space(bool share, Space& s);
01129 virtual Space* copy(bool share) = 0;
01134 static void* operator new(size_t);
01139 static void operator delete(void*);
01140
01141
01142
01143
01144
01145
01146
01158 GECODE_KERNEL_EXPORT SpaceStatus status(unsigned long int& pn=unused_uli);
01159
01175 const BranchingDesc* description(void) const;
01176
01193 GECODE_KERNEL_EXPORT Space* clone(bool share=true);
01194
01224 GECODE_KERNEL_EXPORT void commit(const BranchingDesc* d, unsigned int a);
01225
01233 void fail(void);
01242 bool failed(void) const;
01247 bool stable(void) const;
01254 GECODE_KERNEL_EXPORT unsigned int propagators(void) const;
01261 GECODE_KERNEL_EXPORT unsigned int branchings(void) const;
01262
01267
01268 GECODE_KERNEL_EXPORT
01269 virtual void getVars(Reflection::VarMap& m, bool registerOnly);
01271 GECODE_KERNEL_EXPORT
01272 Reflection::BranchingSpec branchingSpec(Reflection::VarMap& m,
01273 const BranchingDesc* d) const;
01275
01281
01282 void* alloc(size_t);
01284 void reuse(void*,size_t);
01286 template <size_t> void* fl_alloc(void);
01292 template <size_t> void fl_dispose(FreeList* f, FreeList* l);
01299 GECODE_KERNEL_EXPORT
01300 size_t allocated(void) const;
01302 };
01303
01304
01305
01306
01307
01308
01309
01310
01311
01312
01313 forceinline void*
01314 SharedHandle::Object::operator new(size_t s) {
01315 return Memory::malloc(s);
01316 }
01317 forceinline void
01318 SharedHandle::Object::operator delete(void* p) {
01319 Memory::free(p);
01320 }
01321
01322 forceinline void*
01323 Space::operator new(size_t s) {
01324 return Memory::malloc(s);
01325 }
01326 forceinline void
01327 Space::operator delete(void* p) {
01328 Memory::free(p);
01329 }
01330
01331 forceinline void
01332 BranchingDesc::operator delete(void* p) {
01333 Memory::free(p);
01334 }
01335 forceinline void*
01336 BranchingDesc::operator new(size_t s) {
01337 return Memory::malloc(s);
01338 }
01339
01340
01341 forceinline void*
01342 Space::alloc(size_t s) {
01343 return mm.alloc(s);
01344 }
01345 forceinline void
01346 Space::reuse(void* p, size_t s) {
01347 return mm.reuse(p,s);
01348 }
01349 template <size_t s>
01350 forceinline void*
01351 Space::fl_alloc(void) {
01352 return mm.template fl_alloc<s>();
01353 }
01354 template <size_t s>
01355 forceinline void
01356 Space::fl_dispose(FreeList* f, FreeList* l) {
01357 mm.template fl_dispose<s>(f,l);
01358 }
01359
01360 #ifdef GECODE_HAS_VAR_DISPOSE
01361 template <class VIC>
01362 forceinline VarImpBase*
01363 Space::vars_d(void) const {
01364 return _vars_d[VIC::idx_d];
01365 }
01366 template <class VIC>
01367 forceinline void
01368 Space::vars_d(VarImpBase* x) {
01369 _vars_d[VIC::idx_d] = x;
01370 }
01371 #endif
01372
01373
01374 forceinline void
01375 Actor::operator delete(void*) {}
01376 forceinline void
01377 Actor::operator delete(void*, Space*) {}
01378 forceinline void*
01379 Actor::operator new(size_t s, Space* home) {
01380 return home->alloc(s);
01381 }
01382
01383 template <class VIC>
01384 forceinline void
01385 VarImp<VIC>::operator delete(void*) {}
01386 template <class VIC>
01387 forceinline void
01388 VarImp<VIC>::operator delete(void*, Space*) {}
01389 template <class VIC>
01390 forceinline void*
01391 VarImp<VIC>::operator new(size_t s, Space* home) {
01392 return home->alloc(s);
01393 }
01394
01395 #ifndef __GNUC__
01396 forceinline void
01397 Advisor::operator delete(void*) {}
01398 #endif
01399 forceinline void
01400 Advisor::operator delete(void*, Space*) {}
01401 forceinline void*
01402 Advisor::operator new(size_t s, Space* home) {
01403 return home->alloc(s);
01404 }
01405
01406
01407
01408
01409
01410
01411 forceinline
01412 SharedHandle::Object::Object(void)
01413 : use_cnt(0), fwd(NULL) {}
01414 forceinline
01415 SharedHandle::Object::~Object(void) {
01416 assert(use_cnt == 0);
01417 }
01418
01419 forceinline void
01420 SharedHandle::subscribe(void) {
01421 if (o != NULL) o->use_cnt++;
01422 }
01423 forceinline void
01424 SharedHandle::cancel(void) {
01425 if ((o != NULL) && (--o->use_cnt == 0))
01426 delete o;
01427 o = NULL;
01428 }
01429 forceinline
01430 SharedHandle::SharedHandle(void) : o(NULL) {}
01431 forceinline
01432 SharedHandle::SharedHandle(SharedHandle::Object* so) : o(so) {
01433 subscribe();
01434 }
01435 forceinline
01436 SharedHandle::SharedHandle(const SharedHandle& sh) : o(sh.o) {
01437 subscribe();
01438 }
01439 forceinline SharedHandle&
01440 SharedHandle::operator=(const SharedHandle& sh) {
01441 if (&sh != this) {
01442 cancel(); o = sh.o; subscribe();
01443 }
01444 return *this;
01445 }
01446 forceinline void
01447 SharedHandle::update(Space* home, bool share, SharedHandle& sh) {
01448 if (sh.o == NULL) {
01449 o = NULL;
01450 } else if (share) {
01451 o = sh.o; subscribe();
01452 } else if (sh.o->fwd != NULL) {
01453 o = sh.o->fwd; subscribe();
01454 } else {
01455 o = sh.o->copy();
01456 sh.o->fwd = o;
01457 sh.o->next = home->pc.c.shared;
01458 home->pc.c.shared = sh.o;
01459 subscribe();
01460 }
01461 }
01462 forceinline
01463 SharedHandle::~SharedHandle(void) {
01464 cancel();
01465 }
01466 forceinline SharedHandle::Object*
01467 SharedHandle::object(void) const {
01468 return o;
01469 }
01470 forceinline void
01471 SharedHandle::object(SharedHandle::Object* n) {
01472 if (n != o) {
01473 cancel(); o=n; subscribe();
01474 }
01475 }
01476
01477
01478
01479
01480
01481
01482
01483 forceinline ActorLink*
01484 ActorLink::prev(void) const {
01485 return _prev;
01486 }
01487
01488 forceinline ActorLink*
01489 ActorLink::next(void) const {
01490 return _next;
01491 }
01492
01493 forceinline ActorLink**
01494 ActorLink::next_ref(void) {
01495 return &_next;
01496 }
01497
01498 forceinline void
01499 ActorLink::prev(ActorLink* al) {
01500 _prev = al;
01501 }
01502
01503 forceinline void
01504 ActorLink::next(ActorLink* al) {
01505 _next = al;
01506 }
01507
01508 forceinline void
01509 ActorLink::unlink(void) {
01510 ActorLink* p = _prev; ActorLink* n = _next;
01511 p->_next = n; n->_prev = p;
01512 }
01513
01514 forceinline void
01515 ActorLink::init(void) {
01516 _next = this; _prev =this;
01517 }
01518
01519 forceinline void
01520 ActorLink::head(ActorLink* a) {
01521
01522 ActorLink* n = _next;
01523 this->_next = a; a->_prev = this;
01524 a->_next = n; n->_prev = a;
01525 }
01526
01527 forceinline void
01528 ActorLink::tail(ActorLink* a) {
01529
01530 ActorLink* p = _prev;
01531 a->_next = this; this->_prev = a;
01532 p->_next = a; a->_prev = p;
01533 }
01534
01535 template <class T>
01536 forceinline ActorLink*
01537 ActorLink::cast(T* a) {
01538
01539 GECODE_NOT_NULL(a);
01540 ActorLink& t = *a;
01541 return static_cast<ActorLink*>(&t);
01542 }
01543
01544 template <class T>
01545 forceinline const ActorLink*
01546 ActorLink::cast(const T* a) {
01547
01548 GECODE_NOT_NULL(a);
01549 const ActorLink& t = *a;
01550 return static_cast<const ActorLink*>(&t);
01551 }
01552
01553
01554
01555
01556
01557
01558 forceinline Actor*
01559 Actor::cast(ActorLink* al) {
01560
01561 GECODE_NOT_NULL(al);
01562 ActorLink& t = *al;
01563 return static_cast<Actor*>(&t);
01564 }
01565
01566 forceinline const Actor*
01567 Actor::cast(const ActorLink* al) {
01568
01569 GECODE_NOT_NULL(al);
01570 const ActorLink& t = *al;
01571 return static_cast<const Actor*>(&t);
01572 }
01573
01574 forceinline void
01575 Actor::force(Space* home) {
01576 if (home->d_cur == home->d_lst)
01577 home->d_resize();
01578 *(home->d_cur++) = this;
01579 }
01580
01581 forceinline void
01582 Actor::unforce(Space* home) {
01583
01584
01585 Actor** f = home->d_fst;
01586 if (f != NULL) {
01587 while (this != *f)
01588 f++;
01589 *f = *(--home->d_cur);
01590 }
01591 }
01592
01593 forceinline size_t
01594 Actor::dispose(Space*) {
01595 return sizeof(*this);
01596 }
01597
01598
01599
01600
01601
01602
01603 forceinline Propagator*
01604 Propagator::cast(ActorLink* al) {
01605
01606 GECODE_NOT_NULL(al);
01607 ActorLink& t = *al;
01608 return static_cast<Propagator*>(&t);
01609 }
01610
01611 forceinline const Propagator*
01612 Propagator::cast(const ActorLink* al) {
01613
01614 GECODE_NOT_NULL(al);
01615 const ActorLink& t = *al;
01616 return static_cast<const Propagator*>(&t);
01617 }
01618
01619 forceinline
01620 Propagator::Propagator(Space* home) {
01621 u.advisors = NULL;
01622 assert(u.med == 0 && u.size == 0);
01623 home->a_actors.head(this);
01624 }
01625
01626 forceinline
01627 Propagator::Propagator(Space*, bool, Propagator& p) {
01628 u.advisors = NULL;
01629 assert(u.med == 0 && u.size == 0);
01630
01631 p.prev(this);
01632 }
01633
01634 forceinline ExecStatus
01635 ES_SUBSUMED(Propagator* p, size_t s) {
01636 p->u.size = s;
01637 return __ES_SUBSUMED;
01638 }
01639
01640 forceinline ExecStatus
01641 ES_SUBSUMED(Propagator* p, Space* home) {
01642 p->u.size = p->dispose(home);
01643 return __ES_SUBSUMED;
01644 }
01645
01646 forceinline ExecStatus
01647 ES_FIX_PARTIAL(Propagator* p, ModEventDelta med) {
01648 p->u.med = med;
01649 return __ES_PARTIAL;
01650 }
01651
01652 forceinline ExecStatus
01653 ES_NOFIX_PARTIAL(Propagator* p, ModEventDelta med) {
01654 p->u.med ^= AllVarConf::med_combine(p->u.med,med);
01655 return __ES_PARTIAL;
01656 }
01657
01658
01659
01660
01661
01662
01663
01664 forceinline Branching*
01665 Branching::cast(ActorLink* al) {
01666
01667 GECODE_NOT_NULL(al);
01668 ActorLink& t = *al;
01669 return static_cast<Branching*>(&t);
01670 }
01671
01672 forceinline const Branching*
01673 Branching::cast(const ActorLink* al) {
01674
01675 GECODE_NOT_NULL(al);
01676 const ActorLink& t = *al;
01677 return static_cast<const Branching*>(&t);
01678 }
01679
01680 forceinline
01681 Branching::Branching(Space* home) {
01682
01683 id = home->pc.p.branch_id++;
01684
01685 if (home->b_status == &(home->a_actors)) {
01686 home->b_status = this;
01687 if (home->b_commit == &(home->a_actors))
01688 home->b_commit = this;
01689 }
01690 home->a_actors.tail(this);
01691 }
01692
01693 forceinline
01694 Branching::Branching(Space*, bool, Branching& b)
01695 : id(b.id) {
01696
01697 b.prev(this);
01698 }
01699
01700
01701
01702
01703
01704
01705
01706 forceinline
01707 BranchingDesc::BranchingDesc(const Branching* b, const unsigned int a)
01708 : _id(b->id), _alt(a) {}
01709
01710 forceinline unsigned int
01711 BranchingDesc::alternatives(void) const {
01712 return _alt;
01713 }
01714
01715 forceinline unsigned int
01716 BranchingDesc::id(void) const {
01717 return _id;
01718 }
01719
01720 forceinline
01721 BranchingDesc::~BranchingDesc(void) {}
01722
01723
01724
01725
01726
01727
01728
01729 forceinline ModEvent
01730 Delta::modevent(void) const {
01731 return me;
01732 }
01733
01734
01735
01736
01737
01738
01739
01740 template <class A>
01741 forceinline
01742 Advisor::Advisor(Space*, Propagator* p, Council<A>& c) {
01743 assert(p != NULL);
01744
01745 ActorLink::prev(p);
01746
01747 ActorLink::next(c.advisors); c.advisors = static_cast<A*>(this);
01748 }
01749
01750 forceinline
01751 Advisor::Advisor(Space*, bool, Advisor&) {}
01752
01753 forceinline bool
01754 Advisor::disposed(void) const {
01755 return prev() == NULL;
01756 }
01757
01758 forceinline Propagator*
01759 Advisor::propagator(void) const {
01760 assert(!disposed());
01761 return Propagator::cast(ActorLink::prev());
01762 }
01763
01764 template <class A>
01765 forceinline void
01766 Advisor::dispose(Space*,Council<A>&) {
01767 assert(!disposed());
01768 ActorLink::prev(NULL);
01769
01770 Advisor* n = static_cast<Advisor*>(next());
01771 if ((n != NULL) && n->disposed())
01772 next(n->next());
01773 }
01774
01775 template <class A>
01776 forceinline ExecStatus
01777 ES_SUBSUMED_FIX(A* a, Space* home, Council<A>& c) {
01778 a->dispose(home,c);
01779 return ES_FIX;
01780 }
01781
01782 template <class A>
01783 forceinline ExecStatus
01784 ES_SUBSUMED_NOFIX(A* a, Space* home, Council<A>& c) {
01785 a->dispose(home,c);
01786 return ES_NOFIX;
01787 }
01788
01789
01790
01791
01792
01793
01794
01795 template <class A>
01796 forceinline
01797 Council<A>::Council(void) {}
01798
01799 template <class A>
01800 forceinline
01801 Council<A>::Council(Space*)
01802 : advisors(NULL) {}
01803
01804 template <class A>
01805 forceinline bool
01806 Council<A>::empty(void) const {
01807 ActorLink* a = advisors;
01808 while ((a != NULL) && static_cast<A*>(a)->disposed())
01809 a = a->next();
01810 advisors = a;
01811 return a == NULL;
01812 }
01813
01814 template <class A>
01815 forceinline void
01816 Council<A>::update(Space* home, bool share, Council<A>& c) {
01817
01818 {
01819 ActorLink* a = c.advisors;
01820 while ((a != NULL) && static_cast<A*>(a)->disposed())
01821 a = a->next();
01822 c.advisors = a;
01823 }
01824
01825 if (c.advisors != NULL) {
01826
01827 Propagator* p_f = static_cast<A*>(c.advisors)->propagator();
01828
01829 Propagator* p_t = static_cast<Propagator*>(p_f->prev());
01830
01831 ActorLink** a_f = &c.advisors;
01832
01833 A* a_t = NULL;
01834 while (*a_f != NULL) {
01835 if (static_cast<A*>(*a_f)->disposed()) {
01836 *a_f = (*a_f)->next();
01837 } else {
01838
01839 A* a = new (home) A(home,share,*static_cast<A*>(*a_f));
01840
01841 a->prev(p_t);
01842
01843 (*a_f)->prev(a);
01844
01845 a->next(a_t);
01846 a_t = a;
01847 a_f = (*a_f)->next_ref();
01848 }
01849 }
01850 advisors = a_t;
01851
01852 assert(p_f->u.advisors == NULL);
01853 p_f->u.advisors = c.advisors;
01854 }
01855 }
01856
01857 template <class A>
01858 forceinline void
01859 Council<A>::dispose(Space* home) {
01860 ActorLink* a = advisors;
01861 while (a != NULL) {
01862 if (!static_cast<A*>(a)->disposed())
01863 static_cast<A*>(a)->dispose(home,*this);
01864 a = a->next();
01865 }
01866 }
01867
01868
01869
01870
01871
01872
01873
01874 template <class A>
01875 forceinline
01876 Advisors<A>::Advisors(const Council<A>& c)
01877 : a(c.advisors) {
01878 while ((a != NULL) && static_cast<A*>(a)->disposed())
01879 a = a->next();
01880 }
01881
01882 template <class A>
01883 forceinline bool
01884 Advisors<A>::operator()(void) const {
01885 return a != NULL;
01886 }
01887
01888 template <class A>
01889 forceinline void
01890 Advisors<A>::operator++(void) {
01891 do {
01892 a = a->next();
01893 } while ((a != NULL) && static_cast<A*>(a)->disposed());
01894 }
01895
01896 template <class A>
01897 forceinline A*
01898 Advisors<A>::advisor(void) const {
01899 return static_cast<A*>(a);
01900 }
01901
01902
01903
01904
01905
01906
01907
01908 forceinline void
01909 Space::enqueue(Propagator* p) {
01910 ActorLink::cast(p)->unlink();
01911 ActorLink* c = &pc.p.queue[p->cost(p->u.med)];
01912 c->tail(ActorLink::cast(p));
01913 if (c > pc.p.active)
01914 pc.p.active = c;
01915 }
01916
01917 forceinline const BranchingDesc*
01918 Space::description(void) const {
01919 return b_status->description(this);
01920 }
01921
01922 forceinline void
01923 Space::fail(void) {
01924 pc.p.active = NULL;
01925 }
01926
01927 forceinline bool
01928 Space::failed(void) const {
01929 return pc.p.active == NULL;
01930 }
01931
01932 forceinline bool
01933 Space::stable(void) const {
01934 return pc.p.active < &pc.p.queue[0];
01935 }
01936
01937
01938
01939
01940
01941
01942
01943 template <class VIC>
01944 forceinline
01945 VarImp<VIC>::VarImp(Space*) {
01946 for (PropCond i=0; i<pc_max+3; i++)
01947 idx[i] = NULL;
01948 free_and_bits = 0;
01949 }
01950
01951 template <class VIC>
01952 forceinline
01953 VarImp<VIC>::VarImp(void) {
01954 for (PropCond i=0; i<pc_max+3; i++)
01955 idx[i] = NULL;
01956 free_and_bits = 0;
01957 }
01958
01959 template <class VIC>
01960 forceinline unsigned int
01961 VarImp<VIC>::degree(void) const {
01962 assert(!copied());
01963 return static_cast<unsigned int>(idx[pc_max+2] - idx[0]);
01964 }
01965
01966 template <class VIC>
01967 forceinline unsigned int
01968 VarImp<VIC>::bits(void) const {
01969 return free_and_bits;
01970 }
01971
01972 template <class VIC>
01973 forceinline unsigned int&
01974 VarImp<VIC>::bits(void) {
01975 return free_and_bits;
01976 }
01977
01978 #ifdef GECODE_HAS_VAR_DISPOSE
01979 template <class VIC>
01980 forceinline VarImp<VIC>*
01981 VarImp<VIC>::vars_d(Space* home) {
01982 return static_cast<VarImp<VIC>*>(home->vars_d<VIC>());
01983 }
01984
01985 template <class VIC>
01986 forceinline void
01987 VarImp<VIC>::vars_d(Space* home, VarImp<VIC>* x) {
01988 home->vars_d<VIC>(x);
01989 }
01990 #endif
01991
01992 template <class VIC>
01993 forceinline bool
01994 VarImp<VIC>::copied(void) const {
01995 return Support::marked(idx[0]);
01996 }
01997
01998 template <class VIC>
01999 forceinline VarImp<VIC>*
02000 VarImp<VIC>::forward(void) const {
02001 assert(copied());
02002 return reinterpret_cast<VarImp<VIC>*>(Support::unmark(idx[0]));
02003 }
02004
02005 template <class VIC>
02006 forceinline VarImp<VIC>*
02007 VarImp<VIC>::next(void) const {
02008 assert(copied());
02009 return reinterpret_cast<VarImp<VIC>*>(idx[1]);
02010 }
02011
02012 template <class VIC>
02013 forceinline
02014 VarImp<VIC>::VarImp(Space* home, bool, VarImp<VIC>& x) {
02015 VarImpBase** reg;
02016 free_and_bits = x.free_and_bits & ((1 << free_bits) - 1);
02017 if (x.idx[0] == NULL) {
02018
02019 for (PropCond i=0; i<pc_max+3; i++)
02020 idx[i] = NULL;
02021 reg = &home->pc.c.vars_noidx;
02022 } else {
02023
02024 idx[0] = x.idx[0];
02025 idx[1] = x.idx[1];
02026 reg = &home->pc.c.vars_u[idx_c];
02027 }
02028
02029 x.idx[0] = reinterpret_cast<ActorLink**>(Support::mark(this));
02030
02031 x.idx[1] = reinterpret_cast<ActorLink**>(*reg); *reg = &x;
02032 }
02033
02034 template <class VIC>
02035 forceinline ModEvent
02036 VarImp<VIC>::me(ModEventDelta med) {
02037 return static_cast<ModEvent>((med & VIC::med_mask) >> VIC::med_fst);
02038 }
02039
02040 template <class VIC>
02041 forceinline ModEventDelta
02042 VarImp<VIC>::med(ModEvent me) {
02043 return static_cast<ModEventDelta>(me << VIC::med_fst);
02044 }
02045
02046 template <class VIC>
02047 forceinline ModEvent
02048 VarImp<VIC>::me_combine(ModEvent me1, ModEvent me2) {
02049 return VIC::me_combine(me1,me2);
02050 }
02051
02052 template <class VIC>
02053 forceinline void
02054 VarImp<VIC>::schedule(Space* home, Propagator* p, ModEvent me) {
02055 if (VIC::med_update(p->u.med,me))
02056 home->enqueue(p);
02057 }
02058
02059 template <class VIC>
02060 forceinline void
02061 VarImp<VIC>::schedule(Space* home, PropCond pc1, PropCond pc2, ModEvent me) {
02062 ActorLink** b = idx[pc1];
02063 ActorLink** p = idx[pc2+1];
02064 while (p-- > b)
02065 schedule(home,Propagator::cast(*p),me);
02066 }
02067
02068 template <class VIC>
02069 forceinline void
02070 VarImp<VIC>::enter(Space* home, ActorLink* a, PropCond pc) {
02071
02072 home->pc.p.n_sub += 1;
02073 if ((free_and_bits >> free_bits) == 0)
02074 resize(home);
02075 free_and_bits -= 1 << free_bits;
02076
02077 --idx[0];
02078 for (PropCond i = 0; i < pc; i++)
02079 *(idx[i]) = *(--idx[i+1]);
02080 *idx[pc]=a;
02081 }
02082
02083 template <class VIC>
02084 void
02085 VarImp<VIC>::resize(Space* home) {
02086 if (idx[0] == NULL) {
02087 assert((free_and_bits >> free_bits) == 0);
02088
02089 free_and_bits += 4 << free_bits;
02090 ActorLink** prop = static_cast<ActorLink**>
02091 (home->alloc(4*sizeof(ActorLink*))) + 4;
02092 for (PropCond i=0; i<pc_max+3; i++)
02093 idx[i] = prop;
02094 } else {
02095
02096 unsigned int n = static_cast<unsigned int>(idx[pc_max+2] - idx[0]);
02097
02098
02099
02100 ActorLink** s = static_cast<ActorLink**>
02101 (home->mm.subscriptions());
02102 unsigned int m =
02103 ((s <= idx[0]) && (idx[0] < s+home->pc.p.n_sub)) ?
02104 (n+4) : ((n+1)*3>>1);
02105 ActorLink** prop = static_cast<ActorLink**>
02106 (home->alloc(m*sizeof(ActorLink*))) + m-n;
02107 free_and_bits += (m-n) << free_bits;
02108
02109 memcpy(prop, idx[0], n*sizeof(ActorLink*));
02110 home->reuse(idx[0], n*sizeof(ActorLink*));
02111
02112 ptrdiff_t o = prop - idx[0];
02113 idx[0] = prop;
02114 for (PropCond i = pc_max+2; i > 0; i--)
02115 idx[i] += o;
02116 }
02117 }
02118
02119 template <class VIC>
02120 void
02121 VarImp<VIC>::subscribe(Space* home, Propagator* p, PropCond pc,
02122 bool assigned, ModEvent me, bool schedule) {
02123 if (assigned) {
02124
02125 if (schedule)
02126 VarImp<VIC>::schedule(home,p,ME_GEN_ASSIGNED);
02127 } else {
02128 enter(home,ActorLink::cast(p),pc);
02129
02130 if (schedule && (pc != PC_GEN_ASSIGNED))
02131 VarImp<VIC>::schedule(home,p,me);
02132 }
02133 }
02134
02135 template <class VIC>
02136 forceinline void
02137 VarImp<VIC>::subscribe(Space* home, Advisor* a, bool assigned) {
02138 if (!assigned)
02139 enter(home,a,pc_max+1);
02140 }
02141
02142 template <class VIC>
02143 forceinline void
02144 VarImp<VIC>::remove(Space* home, ActorLink* a, PropCond pc) {
02145
02146
02147
02148
02149
02150 ActorLink** f = idx[pc];
02151 #ifdef GECODE_AUDIT
02152 while (f < idx[pc+1])
02153 if (*f == a)
02154 goto found;
02155 else
02156 f++;
02157 GECODE_NEVER;
02158 found: ;
02159 #else
02160 while (*f != a) f++;
02161 #endif
02162 *f=*idx[pc];
02163 for (PropCond i=pc; i>0; i--)
02164 *(idx[i]++)=*(idx[i-1]);
02165 idx[0]++;
02166 free_and_bits += 1 << free_bits;
02167 home->pc.p.n_sub -= 1;
02168 }
02169
02170 template <class VIC>
02171 forceinline void
02172 VarImp<VIC>::cancel(Space* home, Propagator* p, PropCond pc, bool assigned) {
02173 if (!assigned)
02174 remove(home,ActorLink::cast(p),pc);
02175 }
02176
02177 template <class VIC>
02178 forceinline void
02179 VarImp<VIC>::cancel(Space* home, Advisor* a, bool assigned) {
02180 if (!assigned)
02181 remove(home,a,pc_max+1);
02182 }
02183
02184 template <class VIC>
02185 forceinline void
02186 VarImp<VIC>::cancel(Space* home) {
02187
02188
02189 ActorLink** b = idx[0]; idx[0] = NULL;
02190 ActorLink** p = idx[pc_max+2]; idx[pc_max+2] = NULL;
02191 home->pc.p.n_sub -= (p-b);
02192 unsigned int n = (free_and_bits >> VIC::free_bits) + (p-b);
02193 home->reuse(p-n,n*sizeof(ActorLink*));
02194 }
02195
02196 template <class VIC>
02197 forceinline bool
02198 VarImp<VIC>::advise(Space* home, ModEvent me, Delta* d) {
02199
02200
02201
02202
02203
02204 ActorLink** la = idx[pc_max+1];
02205 ActorLink** le = idx[pc_max+2];
02206 if (la == le)
02207 return true;
02208 d->me = me;
02209
02210
02211
02212 do {
02213 Advisor* a = static_cast<Advisor*>(*la);
02214 Propagator* p = a->propagator();
02215 switch (p->advise(home,a,d)) {
02216 case ES_FIX:
02217 break;
02218 case ES_FAILED:
02219 return false;
02220 case ES_NOFIX:
02221 schedule(home,p,me);
02222 break;
02223 default:
02224 GECODE_NEVER;
02225 }
02226 } while (++la < le);
02227 return true;
02228 }
02229
02230 template <class VIC>
02231 forceinline void
02232 VarImp<VIC>::update(VarImp<VIC>* x, ActorLink**& sub) {
02233
02234
02235
02236 x->idx[0] = idx[0];
02237 ActorLink** f = x->idx[0];
02238 x->idx[1] = idx[1];
02239 int n = static_cast<int>(x->idx[pc_max+2] - f);
02240 ActorLink** t = sub;
02241 sub += n;
02242 idx[0] = t;
02243 ptrdiff_t o = t - f;
02244 for (PropCond i = 1; i<pc_max+3; i++)
02245 idx[i] = x->idx[i]+o;
02246 while ((n-4) >= 0) {
02247 n -= 4;
02248 t[0]=f[0]->prev(); t[1]=f[1]->prev();
02249 t[2]=f[2]->prev(); t[3]=f[3]->prev();
02250 t += 4; f += 4;
02251 }
02252 if ((n-2) >= 0) {
02253 n -= 2;
02254 t[0]=f[0]->prev(); t[1]=f[1]->prev();
02255 t += 2; f += 2;
02256 }
02257 if (n > 0) {
02258 t[0]=f[0]->prev();
02259 }
02260 }
02261
02262 template <class VIC>
02263 forceinline void
02264 VarImp<VIC>::update(Space* home, ActorLink**& sub) {
02265 VarImp<VIC>* x = static_cast<VarImp<VIC>*>(home->pc.c.vars_u[idx_c]);
02266 while (x != NULL) {
02267 VarImp<VIC>* n = x->next(); x->forward()->update(x,sub); x = n;
02268 }
02269 }
02270
02271
02272
02273
02274
02275
02276
02277 template <class VarType>
02278 VarDisposer<VarType>::VarDisposer(void) {
02279 #ifdef GECODE_HAS_VAR_DISPOSE
02280 Space::vd[VarType::idx_d] = this;
02281 #endif
02282 }
02283
02284 template <class VarType>
02285 void
02286 VarDisposer<VarType>::dispose(Space* home, VarImpBase* _x) {
02287 VarType* x = static_cast<VarType*>(_x);
02288 do {
02289 x->dispose(home); x = static_cast<VarType*>(x->next_d());
02290 } while (x != NULL);
02291 }
02292
02293 }
02294
02295