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
00046
00047
00048
00049 #include <iostream>
00050
00051 namespace Gecode {
00052
00053 class Space;
00054
00079 class SharedHandle {
00080 public:
00088 class Object {
00089 friend class Space;
00090 friend class SharedHandle;
00091 private:
00093 Object* next;
00095 Object* fwd;
00097 unsigned int use_cnt;
00098 public:
00100 Object(void);
00102 virtual Object* copy(void) const = 0;
00104 virtual ~Object(void);
00106 static void* operator new(size_t s);
00108 static void operator delete(void* p);
00109 };
00110 private:
00112 Object* o;
00114 void subscribe(void);
00116 void cancel(void);
00117 public:
00119 SharedHandle(void);
00121 SharedHandle(SharedHandle::Object* so);
00123 SharedHandle(const SharedHandle& sh);
00125 SharedHandle& operator =(const SharedHandle& sh);
00127 void update(Space& home, bool share, SharedHandle& sh);
00129 ~SharedHandle(void);
00130 protected:
00132 SharedHandle::Object* object(void) const;
00134 void object(SharedHandle::Object* n);
00135 };
00136
00145
00146 typedef int ModEvent;
00147
00149 const ModEvent ME_GEN_FAILED = -1;
00151 const ModEvent ME_GEN_NONE = 0;
00153 const ModEvent ME_GEN_ASSIGNED = 1;
00154
00156 typedef int PropCond;
00158 const PropCond PC_GEN_NONE = -1;
00160 const PropCond PC_GEN_ASSIGNED = 0;
00162
00173 typedef int ModEventDelta;
00174
00175 }
00176
00177 #include <gecode/kernel/var-type.hpp>
00178
00179 namespace Gecode {
00180
00182 class NoIdxVarImpConf {
00183 public:
00185 static const int idx_c = -1;
00187 static const int idx_d = -1;
00189 static const PropCond pc_max = PC_GEN_ASSIGNED;
00191 static const int free_bits = 0;
00193 static const int med_fst = 0;
00195 static const int med_lst = 0;
00197 static const int med_mask = 0;
00199 static Gecode::ModEvent me_combine(ModEvent me1, ModEvent me2);
00201 static bool med_update(ModEventDelta& med, ModEvent me);
00202 };
00203
00204 forceinline ModEvent
00205 NoIdxVarImpConf::me_combine(ModEvent, ModEvent) {
00206 GECODE_NEVER; return 0;
00207 }
00208 forceinline bool
00209 NoIdxVarImpConf::med_update(ModEventDelta&, ModEvent) {
00210 GECODE_NEVER; return false;
00211 }
00212
00213
00214
00215
00216
00217
00218 class ActorLink;
00219 class Actor;
00220 class Propagator;
00221 class LocalObject;
00222 class Advisor;
00223 class AFC;
00224 class Brancher;
00225 class BrancherHandle;
00226 template<class A> class Council;
00227 template<class A> class Advisors;
00228 template<class VIC> class VarImp;
00229
00230
00231
00232
00233
00234
00235
00243 class VarImpBase {};
00244
00251 class GECODE_VTABLE_EXPORT VarImpDisposerBase {
00252 public:
00254 GECODE_KERNEL_EXPORT virtual void dispose(Space& home, VarImpBase* x);
00256 GECODE_KERNEL_EXPORT virtual ~VarImpDisposerBase(void);
00257 };
00258
00265 template<class VarImp>
00266 class VarImpDisposer : public VarImpDisposerBase {
00267 public:
00269 VarImpDisposer(void);
00271 virtual void dispose(Space& home, VarImpBase* x);
00272 };
00273
00275 class Delta {
00276 template<class VIC> friend class VarImp;
00277 private:
00279 ModEvent me;
00280 };
00281
00289 template<class VIC>
00290 class VarImp : public VarImpBase {
00291 friend class Space;
00292 friend class Propagator;
00293 template<class VarImp> friend class VarImpDisposer;
00294 private:
00295 union {
00303 ActorLink** base;
00312 VarImp<VIC>* fwd;
00313 } b;
00314
00316 static const int idx_c = VIC::idx_c;
00318 static const int idx_d = VIC::idx_d;
00320 static const int free_bits = VIC::free_bits;
00322 unsigned int entries;
00324 unsigned int free_and_bits;
00326 static const Gecode::PropCond pc_max = VIC::pc_max;
00327
00328 union {
00339 unsigned int idx[pc_max+1];
00341 VarImp<VIC>* next;
00342 } u;
00343
00345 ActorLink** actor(PropCond pc);
00347 ActorLink** actorNonZero(PropCond pc);
00349 unsigned int& idx(PropCond pc);
00351 unsigned int idx(PropCond pc) const;
00352
00359 void update(VarImp* x, ActorLink**& sub);
00366 static void update(Space& home, ActorLink**& sub);
00367
00369 void enter(Space& home, Propagator* p, PropCond pc);
00371 void enter(Space& home, Advisor* a);
00373 void resize(Space& home);
00375 void remove(Space& home, Propagator* p, PropCond pc);
00377 void remove(Space& home, Advisor* a);
00378
00379
00380 protected:
00382 void cancel(Space& home);
00388 bool advise(Space& home, ModEvent me, Delta& d);
00389 #ifdef GECODE_HAS_VAR_DISPOSE
00390
00391 static VarImp<VIC>* vars_d(Space& home);
00393 static void vars_d(Space& home, VarImp<VIC>* x);
00394 #endif
00395
00396 public:
00398 VarImp(Space& home);
00400 VarImp(void);
00401
00403
00404
00416 void subscribe(Space& home, Propagator& p, PropCond pc,
00417 bool assigned, ModEvent me, bool schedule);
00423 void cancel(Space& home, Propagator& p, PropCond pc,
00424 bool assigned);
00430 void subscribe(Space& home, Advisor& a, bool assigned);
00436 void cancel(Space& home, Advisor& a, bool assigned);
00437
00444 unsigned int degree(void) const;
00451 double afc(const Space& home) const;
00453
00455
00456
00457 VarImp(Space& home, bool share, VarImp& x);
00459 bool copied(void) const;
00461 VarImp* forward(void) const;
00463 VarImp* next(void) const;
00465
00467
00468
00475 static void schedule(Space& home, Propagator& p, ModEvent me,
00476 bool force = false);
00478 static ModEvent me(const ModEventDelta& med);
00480 static ModEventDelta med(ModEvent me);
00482 static ModEvent me_combine(ModEvent me1, ModEvent me2);
00484
00486
00487
00488 static ModEvent modevent(const Delta& d);
00490
00492
00493
00494 unsigned int bits(void) const;
00496 unsigned int& bits(void);
00498
00499 protected:
00501 void schedule(Space& home, PropCond pc1, PropCond pc2, ModEvent me);
00502
00503 public:
00505
00506
00507 static void* operator new(size_t,Space&);
00509 static void operator delete(void*,Space&);
00511 static void operator delete(void*);
00513 };
00514
00523 enum ExecStatus {
00524 __ES_SUBSUMED = -2,
00525 ES_FAILED = -1,
00526 ES_NOFIX = 0,
00527 ES_OK = 0,
00528 ES_FIX = 1,
00529 ES_NOFIX_FORCE = 2,
00530 __ES_PARTIAL = 2
00531 };
00532
00537 class PropCost {
00538 friend class Space;
00539 public:
00541 enum ActualCost {
00542 AC_CRAZY_LO = 0,
00543 AC_CRAZY_HI = 0,
00544 AC_CUBIC_LO = 1,
00545 AC_CUBIC_HI = 1,
00546 AC_QUADRATIC_LO = 2,
00547 AC_QUADRATIC_HI = 2,
00548 AC_LINEAR_HI = 3,
00549 AC_LINEAR_LO = 4,
00550 AC_TERNARY_HI = 4,
00551 AC_BINARY_HI = 5,
00552 AC_TERNARY_LO = 5,
00553 AC_BINARY_LO = 6,
00554 AC_UNARY_LO = 6,
00555 AC_UNARY_HI = 6,
00556 AC_MAX = 6
00557 };
00559 ActualCost ac;
00560 public:
00562 enum Mod {
00563 LO,
00564 HI
00565 };
00566 private:
00568 static PropCost cost(Mod m, ActualCost lo, ActualCost hi, unsigned int n);
00570 PropCost(ActualCost ac);
00571 public:
00573 static PropCost crazy(PropCost::Mod m, unsigned int n);
00575 static PropCost crazy(PropCost::Mod m, int n);
00577 static PropCost cubic(PropCost::Mod m, unsigned int n);
00579 static PropCost cubic(PropCost::Mod m, int n);
00581 static PropCost quadratic(PropCost::Mod m, unsigned int n);
00583 static PropCost quadratic(PropCost::Mod m, int n);
00585 static PropCost linear(PropCost::Mod m, unsigned int n);
00587 static PropCost linear(PropCost::Mod m, int n);
00589 static PropCost ternary(PropCost::Mod m);
00591 static PropCost binary(PropCost::Mod m);
00593 static PropCost unary(PropCost::Mod m);
00594 };
00595
00596
00601 enum ActorProperty {
00610 AP_DISPOSE = (1 << 0),
00616 AP_WEAKLY = (1 << 1)
00617 };
00618
00619
00627 class ActorLink {
00628 friend class Actor;
00629 friend class Propagator;
00630 friend class Advisor;
00631 friend class Brancher;
00632 friend class LocalObject;
00633 friend class Space;
00634 template<class VIC> friend class VarImp;
00635 private:
00636 ActorLink* _next; ActorLink* _prev;
00637 public:
00639
00640 ActorLink* prev(void) const; void prev(ActorLink*);
00641 ActorLink* next(void) const; void next(ActorLink*);
00642 ActorLink** next_ref(void);
00644
00646 void init(void);
00648 void unlink(void);
00650 void head(ActorLink* al);
00652 void tail(ActorLink* al);
00654 bool empty(void) const;
00656 template<class T> static ActorLink* cast(T* a);
00658 template<class T> static const ActorLink* cast(const T* a);
00659 };
00660
00661
00666 class GECODE_VTABLE_EXPORT Actor : private ActorLink {
00667 friend class ActorLink;
00668 friend class Space;
00669 friend class Propagator;
00670 friend class Advisor;
00671 friend class Brancher;
00672 friend class LocalObject;
00673 template<class VIC> friend class VarImp;
00674 template<class A> friend class Council;
00675 private:
00677 static Actor* cast(ActorLink* al);
00679 static const Actor* cast(const ActorLink* al);
00681 GECODE_KERNEL_EXPORT static Actor* sentinel;
00682 public:
00684 virtual Actor* copy(Space& home, bool share) = 0;
00685
00687
00688
00689 GECODE_KERNEL_EXPORT
00690 virtual size_t dispose(Space& home);
00692 static void* operator new(size_t s, Space& home);
00694 static void operator delete(void* p, Space& home);
00695 private:
00696 #ifndef __GNUC__
00697
00698 static void operator delete(void* p);
00699 #endif
00700
00701 static void* operator new(size_t s);
00703 #ifdef __GNUC__
00704 public:
00706 GECODE_KERNEL_EXPORT virtual ~Actor(void);
00708 static void operator delete(void* p);
00709 #endif
00710 };
00711
00712
00713
00717 class Home {
00718 protected:
00720 Space& s;
00722 Propagator* p;
00723 public:
00725
00726
00727 Home(Space& s, Propagator* p=NULL);
00729 Home& operator =(const Home& h);
00731 operator Space&(void);
00733
00734
00735
00736 Home operator ()(Propagator& p);
00738 Propagator* propagator(void) const;
00740
00741
00742
00743 bool failed(void) const;
00745 void fail(void);
00747 void notice(Actor& a, ActorProperty p, bool duplicate=false);
00749 };
00750
00755 class GECODE_VTABLE_EXPORT Propagator : public Actor {
00756 friend class ActorLink;
00757 friend class Space;
00758 template<class VIC> friend class VarImp;
00759 friend class Advisor;
00760 template<class A> friend class Council;
00761 private:
00762 union {
00764 ModEventDelta med;
00766 size_t size;
00768 Gecode::ActorLink* advisors;
00769 } u;
00771 GlobalAFC::Counter& gafc;
00773 static Propagator* cast(ActorLink* al);
00775 static const Propagator* cast(const ActorLink* al);
00776 protected:
00778 Propagator(Home home);
00780 Propagator(Space& home, bool share, Propagator& p);
00782 Propagator* fwd(void) const;
00783
00784 public:
00786
00787
00810 virtual ExecStatus propagate(Space& home, const ModEventDelta& med) = 0;
00812 virtual PropCost cost(const Space& home, const ModEventDelta& med) const = 0;
00820 ModEventDelta modeventdelta(void) const;
00856 GECODE_KERNEL_EXPORT
00857 virtual ExecStatus advise(Space& home, Advisor& a, const Delta& d);
00859
00860
00861
00862 double afc(const Space& home) const;
00864 };
00865
00866
00874 template<class A>
00875 class Council {
00876 friend class Advisor;
00877 friend class Advisors<A>;
00878 private:
00880 mutable ActorLink* advisors;
00881 public:
00883 Council(void);
00885 Council(Space& home);
00887 bool empty(void) const;
00889 void update(Space& home, bool share, Council<A>& c);
00891 void dispose(Space& home);
00892 };
00893
00894
00899 template<class A>
00900 class Advisors {
00901 private:
00903 ActorLink* a;
00904 public:
00906 Advisors(const Council<A>& c);
00908 bool operator ()(void) const;
00910 void operator ++(void);
00912 A& advisor(void) const;
00913 };
00914
00915
00926 class Advisor : private ActorLink {
00927 template<class VIC> friend class VarImp;
00928 template<class A> friend class Council;
00929 template<class A> friend class Advisors;
00930 private:
00932 bool disposed(void) const;
00934 static Advisor* cast(ActorLink* al);
00936 static const Advisor* cast(const ActorLink* al);
00937 protected:
00939 Propagator& propagator(void) const;
00940 public:
00942 template<class A>
00943 Advisor(Space& home, Propagator& p, Council<A>& c);
00945 Advisor(Space& home, bool share, Advisor& a);
00946
00948
00949
00950 template<class A>
00951 void dispose(Space& home, Council<A>& c);
00953 static void* operator new(size_t s, Space& home);
00955 static void operator delete(void* p, Space& home);
00957 private:
00958 #ifndef __GNUC__
00959
00960 static void operator delete(void* p);
00961 #endif
00962
00963 static void* operator new(size_t s);
00964 };
00965
00966
00971 class GECODE_VTABLE_EXPORT NGL {
00972 private:
00974 void* nl;
00975 public:
00977 enum Status {
00978 FAILED,
00979 SUBSUMED,
00980 NONE
00981 };
00983 NGL(void);
00985 NGL(Space& home);
00987 NGL(Space& home, bool share, NGL& ngl);
00989 virtual void subscribe(Space& home, Propagator& p) = 0;
00991 virtual void cancel(Space& home, Propagator& p) = 0;
00993 virtual NGL::Status status(const Space& home) const = 0;
00995 virtual ExecStatus prune(Space& home) = 0;
00997 virtual NGL* copy(Space& home, bool share) = 0;
00999 GECODE_KERNEL_EXPORT
01000 virtual bool notice(void) const;
01002 virtual size_t dispose(Space& home);
01004
01005
01006 bool leaf(void) const;
01008 NGL* next(void) const;
01010 void leaf(bool l);
01012 void next(NGL* n);
01014 NGL* add(NGL* n, bool l);
01016
01017
01018
01019 static void* operator new(size_t s, Space& home);
01021 static void operator delete(void* s, Space& home);
01023 static void operator delete(void* p);
01025 };
01026
01036 class GECODE_VTABLE_EXPORT Choice {
01037 friend class Space;
01038 private:
01039 unsigned int _id;
01040 unsigned int _alt;
01041
01043 unsigned int id(void) const;
01044 protected:
01046 Choice(const Brancher& b, const unsigned int a);
01047 public:
01049 unsigned int alternatives(void) const;
01051 GECODE_KERNEL_EXPORT virtual ~Choice(void);
01053 virtual size_t size(void) const = 0;
01055 static void* operator new(size_t);
01057 static void operator delete(void*);
01059 GECODE_KERNEL_EXPORT virtual void archive(Archive& e) const;
01060 };
01061
01071 class GECODE_VTABLE_EXPORT Brancher : public Actor {
01072 friend class ActorLink;
01073 friend class Space;
01074 friend class Choice;
01075 private:
01077 unsigned int _id;
01079 static Brancher* cast(ActorLink* al);
01081 static const Brancher* cast(const ActorLink* al);
01082 protected:
01084 Brancher(Home home);
01086 Brancher(Space& home, bool share, Brancher& b);
01087 public:
01089
01090
01091 unsigned int id(void) const;
01100 virtual bool status(const Space& home) const = 0;
01108 virtual const Choice* choice(Space& home) = 0;
01110 virtual const Choice* choice(const Space& home, Archive& e) = 0;
01117 virtual ExecStatus commit(Space& home, const Choice& c,
01118 unsigned int a) = 0;
01132 GECODE_KERNEL_EXPORT
01133 virtual NGL* ngl(Space& home, const Choice& c, unsigned int a) const;
01143 GECODE_KERNEL_EXPORT
01144 virtual void print(const Space& home, const Choice& c, unsigned int a,
01145 std::ostream& o) const;
01147 };
01148
01157 class BrancherHandle {
01158 private:
01160 unsigned int _id;
01161 public:
01163 BrancherHandle(void);
01165 BrancherHandle(const Brancher& b);
01167 void update(Space& home, bool share, BrancherHandle& bh);
01169 unsigned int id(void) const;
01171 bool operator ()(const Space& home) const;
01173 void kill(Space& home);
01174 };
01175
01183 class LocalObject : public Actor {
01184 friend class ActorLink;
01185 friend class Space;
01186 friend class LocalHandle;
01187 protected:
01189 LocalObject(Home home);
01191 LocalObject(Space& home, bool share, LocalObject& l);
01193 static LocalObject* cast(ActorLink* al);
01195 static const LocalObject* cast(const ActorLink* al);
01196 private:
01198 GECODE_KERNEL_EXPORT void fwdcopy(Space& home, bool share);
01199 public:
01201 LocalObject* fwd(Space& home, bool share);
01202 };
01203
01210 class LocalHandle {
01211 private:
01213 LocalObject* o;
01214 protected:
01216 LocalHandle(void);
01218 LocalHandle(LocalObject* lo);
01220 LocalHandle(const LocalHandle& lh);
01221 public:
01223 LocalHandle& operator =(const LocalHandle& lh);
01225 void update(Space& home, bool share, LocalHandle& lh);
01227 ~LocalHandle(void);
01228 protected:
01230 LocalObject* object(void) const;
01232 void object(LocalObject* n);
01233 };
01234
01235
01240 class GECODE_VTABLE_EXPORT NoGoods {
01241 protected:
01243 unsigned long int n;
01244 public:
01246 NoGoods(void);
01248 GECODE_KERNEL_EXPORT
01249 virtual void post(Space& home);
01251 unsigned long int ng(void) const;
01253 void ng(unsigned long int n);
01255 virtual ~NoGoods(void);
01256 };
01257
01258
01263 enum SpaceStatus {
01264 SS_FAILED,
01265 SS_SOLVED,
01266 SS_BRANCH
01267 };
01268
01273 class StatusStatistics {
01274 public:
01276 unsigned long int propagate;
01278 bool wmp;
01280 StatusStatistics(void);
01282 void reset(void);
01284 StatusStatistics operator +(const StatusStatistics& s);
01286 StatusStatistics& operator +=(const StatusStatistics& s);
01287 };
01288
01293 class CloneStatistics {
01294 public:
01296 CloneStatistics(void);
01298 void reset(void);
01300 CloneStatistics operator +(const CloneStatistics& s);
01302 CloneStatistics& operator +=(const CloneStatistics& s);
01303 };
01304
01309 class CommitStatistics {
01310 public:
01312 CommitStatistics(void);
01314 void reset(void);
01316 CommitStatistics operator +(const CommitStatistics& s);
01318 CommitStatistics& operator +=(const CommitStatistics& s);
01319 };
01320
01321
01325 class GECODE_VTABLE_EXPORT Space {
01326 friend class Actor;
01327 friend class Propagator;
01328 friend class Brancher;
01329 friend class Advisor;
01330 template<class VIC> friend class VarImp;
01331 template<class VarImp> friend class VarImpDisposer;
01332 friend class SharedHandle;
01333 friend class LocalObject;
01334 friend class Region;
01335 friend class AFC;
01336 friend class BrancherHandle;
01337 private:
01339 SharedMemory* sm;
01341 MemoryManager mm;
01343 GlobalAFC gafc;
01345 ActorLink pl;
01347 ActorLink bl;
01353 Brancher* b_status;
01365 Brancher* b_commit;
01367 Brancher* brancher(unsigned int id);
01369 GECODE_KERNEL_EXPORT
01370 void kill_brancher(unsigned int id);
01372 static const unsigned reserved_branch_id = 0U;
01373 union {
01375 struct {
01388 ActorLink* active;
01390 ActorLink queue[PropCost::AC_MAX+1];
01392 unsigned int branch_id;
01394 unsigned int n_sub;
01395 } p;
01397 struct {
01399 VarImpBase* vars_u[AllVarConf::idx_c];
01401 VarImpBase* vars_noidx;
01403 SharedHandle::Object* shared;
01405 LocalObject* local;
01406 } c;
01407 } pc;
01409 void enqueue(Propagator* p);
01414 #ifdef GECODE_HAS_VAR_DISPOSE
01415
01416 GECODE_KERNEL_EXPORT static VarImpDisposerBase* vd[AllVarConf::idx_d];
01418 VarImpBase* _vars_d[AllVarConf::idx_d];
01420 template<class VIC> VarImpBase* vars_d(void) const;
01422 template<class VIC> void vars_d(VarImpBase* x);
01423 #endif
01424
01425 void update(ActorLink** sub);
01427
01429 Actor** d_fst;
01431 Actor** d_cur;
01433 Actor** d_lst;
01434
01446 unsigned int _wmp_afc;
01448 void afc_enable(void);
01450 bool afc_enabled(void) const;
01452 void wmp(unsigned int n);
01454 unsigned int wmp(void) const;
01455
01457 GECODE_KERNEL_EXPORT static StatusStatistics unused_status;
01459 GECODE_KERNEL_EXPORT static CloneStatistics unused_clone;
01461 GECODE_KERNEL_EXPORT static CommitStatistics unused_commit;
01462
01481 GECODE_KERNEL_EXPORT Space* _clone(bool share=true);
01482
01515 GECODE_KERNEL_EXPORT
01516 void _commit(const Choice& c, unsigned int a);
01517
01548 GECODE_KERNEL_EXPORT
01549 void _trycommit(const Choice& c, unsigned int a);
01550
01551 public:
01556 GECODE_KERNEL_EXPORT Space(void);
01561 GECODE_KERNEL_EXPORT virtual ~Space(void);
01572 GECODE_KERNEL_EXPORT Space(bool share, Space& s);
01579 virtual Space* copy(bool share) = 0;
01590 GECODE_KERNEL_EXPORT virtual void constrain(const Space& best);
01604 GECODE_KERNEL_EXPORT
01605 virtual void master(unsigned long int i, const Space* s,
01606 NoGoods& ng);
01619 GECODE_KERNEL_EXPORT
01620 virtual void slave(unsigned long int i, const Space* s);
01625 static void* operator new(size_t);
01630 static void operator delete(void*);
01631
01632
01633
01634
01635
01636
01637
01649 GECODE_KERNEL_EXPORT
01650 SpaceStatus status(StatusStatistics& stat=unused_status);
01651
01683 GECODE_KERNEL_EXPORT
01684 const Choice* choice(void);
01685
01695 GECODE_KERNEL_EXPORT
01696 const Choice* choice(Archive& e) const;
01697
01718 Space* clone(bool share=true, CloneStatistics& stat=unused_clone) const;
01719
01754 void commit(const Choice& c, unsigned int a,
01755 CommitStatistics& stat=unused_commit);
01788 void trycommit(const Choice& c, unsigned int a,
01789 CommitStatistics& stat=unused_commit);
01808 GECODE_KERNEL_EXPORT
01809 NGL* ngl(const Choice& c, unsigned int a);
01810
01825 GECODE_KERNEL_EXPORT
01826 void print(const Choice& c, unsigned int a, std::ostream& o) const;
01827
01836 GECODE_KERNEL_EXPORT
01837 void notice(Actor& a, ActorProperty p, bool duplicate=false);
01845 GECODE_KERNEL_EXPORT
01846 void ignore(Actor& a, ActorProperty p, bool duplicate=false);
01847
01848
01859 ExecStatus ES_SUBSUMED(Propagator& p);
01874 ExecStatus ES_SUBSUMED_DISPOSED(Propagator& p, size_t s);
01885 ExecStatus ES_FIX_PARTIAL(Propagator& p, const ModEventDelta& med);
01896 ExecStatus ES_NOFIX_PARTIAL(Propagator& p, const ModEventDelta& med);
01897
01908 template<class A>
01909 ExecStatus ES_FIX_DISPOSE(Council<A>& c, A& a);
01920 template<class A>
01921 ExecStatus ES_NOFIX_DISPOSE(Council<A>& c, A& a);
01933 template<class A>
01934 ExecStatus ES_NOFIX_DISPOSE_FORCE(Council<A>& c, A& a);
01935
01943 void fail(void);
01952 bool failed(void) const;
01957 bool stable(void) const;
01964 GECODE_KERNEL_EXPORT unsigned int propagators(void) const;
01971 GECODE_KERNEL_EXPORT unsigned int branchers(void) const;
01972
01974
01975
01976 Home operator ()(Propagator& p);
01978
01990 template<class T>
01991 T* alloc(long unsigned int n);
01998 template<class T>
01999 T* alloc(long int n);
02006 template<class T>
02007 T* alloc(unsigned int n);
02014 template<class T>
02015 T* alloc(int n);
02025 template<class T>
02026 void free(T* b, long unsigned int n);
02036 template<class T>
02037 void free(T* b, long int n);
02047 template<class T>
02048 void free(T* b, unsigned int n);
02058 template<class T>
02059 void free(T* b, int n);
02071 template<class T>
02072 T* realloc(T* b, long unsigned int n, long unsigned int m);
02084 template<class T>
02085 T* realloc(T* b, long int n, long int m);
02097 template<class T>
02098 T* realloc(T* b, unsigned int n, unsigned int m);
02110 template<class T>
02111 T* realloc(T* b, int n, int m);
02119 template<class T>
02120 T** realloc(T** b, long unsigned int n, long unsigned int m);
02128 template<class T>
02129 T** realloc(T** b, long int n, long int m);
02137 template<class T>
02138 T** realloc(T** b, unsigned int n, unsigned int m);
02146 template<class T>
02147 T** realloc(T** b, int n, int m);
02149 void* ralloc(size_t s);
02151 void rfree(void* p, size_t s);
02153 void* rrealloc(void* b, size_t n, size_t m);
02155 template<size_t> void* fl_alloc(void);
02161 template<size_t> void fl_dispose(FreeList* f, FreeList* l);
02170 GECODE_KERNEL_EXPORT void flush(void);
02172
02173
02174
02177 template<class T>
02178 T& construct(void);
02184 template<class T, typename A1>
02185 T& construct(A1 const& a1);
02191 template<class T, typename A1, typename A2>
02192 T& construct(A1 const& a1, A2 const& a2);
02198 template<class T, typename A1, typename A2, typename A3>
02199 T& construct(A1 const& a1, A2 const& a2, A3 const& a3);
02205 template<class T, typename A1, typename A2, typename A3, typename A4>
02206 T& construct(A1 const& a1, A2 const& a2, A3 const& a3, A4 const& a4);
02212 template<class T, typename A1, typename A2, typename A3, typename A4, typename A5>
02213 T& construct(A1 const& a1, A2 const& a2, A3 const& a3, A4 const& a4, A5 const& a5);
02215
02221 class Propagators {
02222 private:
02224 const Space& home;
02226 const ActorLink* q;
02228 const ActorLink* c;
02230 const ActorLink* e;
02231 public:
02233 Propagators(const Space& home);
02235 bool operator ()(void) const;
02237 void operator ++(void);
02239 const Propagator& propagator(void) const;
02240 };
02241
02247 class Branchers {
02248 private:
02250 const ActorLink* c;
02252 const ActorLink* e;
02253 public:
02255 Branchers(const Space& home);
02257 bool operator ()(void) const;
02259 void operator ++(void);
02261 const Brancher& brancher(void) const;
02262 };
02263
02265
02266
02267 GECODE_KERNEL_EXPORT
02268 void afc_decay(double d);
02270 double afc_decay(void) const;
02272 GECODE_KERNEL_EXPORT
02273 void afc_set(double a);
02275 };
02276
02277
02278
02279
02280
02281
02282
02283
02284
02285
02286 forceinline void*
02287 SharedHandle::Object::operator new(size_t s) {
02288 return heap.ralloc(s);
02289 }
02290 forceinline void
02291 SharedHandle::Object::operator delete(void* p) {
02292 heap.rfree(p);
02293 }
02294
02295 forceinline void*
02296 Space::operator new(size_t s) {
02297 return heap.ralloc(s);
02298 }
02299 forceinline void
02300 Space::operator delete(void* p) {
02301 heap.rfree(p);
02302 }
02303
02304 forceinline void
02305 Choice::operator delete(void* p) {
02306 heap.rfree(p);
02307 }
02308 forceinline void*
02309 Choice::operator new(size_t s) {
02310 return heap.ralloc(s);
02311 }
02312
02313
02314
02315 forceinline void*
02316 Space::ralloc(size_t s) {
02317 return mm.alloc(sm,s);
02318 }
02319 forceinline void
02320 Space::rfree(void* p, size_t s) {
02321 return mm.reuse(p,s);
02322 }
02323 forceinline void*
02324 Space::rrealloc(void* _b, size_t n, size_t m) {
02325 char* b = static_cast<char*>(_b);
02326 if (n < m) {
02327 char* p = static_cast<char*>(ralloc(m));
02328 memcpy(p,b,n);
02329 rfree(b,n);
02330 return p;
02331 } else {
02332 rfree(b+m,m-n);
02333 return b;
02334 }
02335 }
02336
02337 template<size_t s>
02338 forceinline void*
02339 Space::fl_alloc(void) {
02340 return mm.template fl_alloc<s>(sm);
02341 }
02342 template<size_t s>
02343 forceinline void
02344 Space::fl_dispose(FreeList* f, FreeList* l) {
02345 mm.template fl_dispose<s>(f,l);
02346 }
02347
02348
02349
02350
02351
02352 template<class T>
02353 forceinline T*
02354 Space::alloc(long unsigned int n) {
02355 T* p = static_cast<T*>(ralloc(sizeof(T)*n));
02356 for (long unsigned int i=n; i--; )
02357 (void) new (p+i) T();
02358 return p;
02359 }
02360 template<class T>
02361 forceinline T*
02362 Space::alloc(long int n) {
02363 assert(n >= 0);
02364 return alloc<T>(static_cast<long unsigned int>(n));
02365 }
02366 template<class T>
02367 forceinline T*
02368 Space::alloc(unsigned int n) {
02369 return alloc<T>(static_cast<long unsigned int>(n));
02370 }
02371 template<class T>
02372 forceinline T*
02373 Space::alloc(int n) {
02374 assert(n >= 0);
02375 return alloc<T>(static_cast<long unsigned int>(n));
02376 }
02377
02378 template<class T>
02379 forceinline void
02380 Space::free(T* b, long unsigned int n) {
02381 for (long unsigned int i=n; i--; )
02382 b[i].~T();
02383 rfree(b,n*sizeof(T));
02384 }
02385 template<class T>
02386 forceinline void
02387 Space::free(T* b, long int n) {
02388 assert(n >= 0);
02389 free<T>(b,static_cast<long unsigned int>(n));
02390 }
02391 template<class T>
02392 forceinline void
02393 Space::free(T* b, unsigned int n) {
02394 free<T>(b,static_cast<long unsigned int>(n));
02395 }
02396 template<class T>
02397 forceinline void
02398 Space::free(T* b, int n) {
02399 assert(n >= 0);
02400 free<T>(b,static_cast<long unsigned int>(n));
02401 }
02402
02403 template<class T>
02404 forceinline T*
02405 Space::realloc(T* b, long unsigned int n, long unsigned int m) {
02406 if (n < m) {
02407 T* p = static_cast<T*>(ralloc(sizeof(T)*m));
02408 for (long unsigned int i=n; i--; )
02409 (void) new (p+i) T(b[i]);
02410 for (long unsigned int i=n; i<m; i++)
02411 (void) new (p+i) T();
02412 free<T>(b,n);
02413 return p;
02414 } else {
02415 free<T>(b+m,m-n);
02416 return b;
02417 }
02418 }
02419 template<class T>
02420 forceinline T*
02421 Space::realloc(T* b, long int n, long int m) {
02422 assert((n >= 0) && (m >= 0));
02423 return realloc<T>(b,static_cast<long unsigned int>(n),
02424 static_cast<long unsigned int>(m));
02425 }
02426 template<class T>
02427 forceinline T*
02428 Space::realloc(T* b, unsigned int n, unsigned int m) {
02429 return realloc<T>(b,static_cast<long unsigned int>(n),
02430 static_cast<long unsigned int>(m));
02431 }
02432 template<class T>
02433 forceinline T*
02434 Space::realloc(T* b, int n, int m) {
02435 assert((n >= 0) && (m >= 0));
02436 return realloc<T>(b,static_cast<long unsigned int>(n),
02437 static_cast<long unsigned int>(m));
02438 }
02439
02440 #define GECODE_KERNEL_REALLOC(T) \
02441 template<> \
02442 forceinline T* \
02443 Space::realloc<T>(T* b, long unsigned int n, long unsigned int m) { \
02444 return static_cast<T*>(rrealloc(b,n*sizeof(T),m*sizeof(T))); \
02445 } \
02446 template<> \
02447 forceinline T* \
02448 Space::realloc<T>(T* b, long int n, long int m) { \
02449 assert((n >= 0) && (m >= 0)); \
02450 return realloc<T>(b,static_cast<long unsigned int>(n), \
02451 static_cast<long unsigned int>(m)); \
02452 } \
02453 template<> \
02454 forceinline T* \
02455 Space::realloc<T>(T* b, unsigned int n, unsigned int m) { \
02456 return realloc<T>(b,static_cast<long unsigned int>(n), \
02457 static_cast<long unsigned int>(m)); \
02458 } \
02459 template<> \
02460 forceinline T* \
02461 Space::realloc<T>(T* b, int n, int m) { \
02462 assert((n >= 0) && (m >= 0)); \
02463 return realloc<T>(b,static_cast<long unsigned int>(n), \
02464 static_cast<long unsigned int>(m)); \
02465 }
02466
02467 GECODE_KERNEL_REALLOC(bool)
02468 GECODE_KERNEL_REALLOC(signed char)
02469 GECODE_KERNEL_REALLOC(unsigned char)
02470 GECODE_KERNEL_REALLOC(signed short int)
02471 GECODE_KERNEL_REALLOC(unsigned short int)
02472 GECODE_KERNEL_REALLOC(signed int)
02473 GECODE_KERNEL_REALLOC(unsigned int)
02474 GECODE_KERNEL_REALLOC(signed long int)
02475 GECODE_KERNEL_REALLOC(unsigned long int)
02476 GECODE_KERNEL_REALLOC(float)
02477 GECODE_KERNEL_REALLOC(double)
02478
02479 #undef GECODE_KERNEL_REALLOC
02480
02481 template<class T>
02482 forceinline T**
02483 Space::realloc(T** b, long unsigned int n, long unsigned int m) {
02484 return static_cast<T**>(rrealloc(b,n*sizeof(T),m*sizeof(T*)));
02485 }
02486 template<class T>
02487 forceinline T**
02488 Space::realloc(T** b, long int n, long int m) {
02489 assert((n >= 0) && (m >= 0));
02490 return realloc<T*>(b,static_cast<long unsigned int>(n),
02491 static_cast<long unsigned int>(m));
02492 }
02493 template<class T>
02494 forceinline T**
02495 Space::realloc(T** b, unsigned int n, unsigned int m) {
02496 return realloc<T*>(b,static_cast<long unsigned int>(n),
02497 static_cast<long unsigned int>(m));
02498 }
02499 template<class T>
02500 forceinline T**
02501 Space::realloc(T** b, int n, int m) {
02502 assert((n >= 0) && (m >= 0));
02503 return realloc<T*>(b,static_cast<long unsigned int>(n),
02504 static_cast<long unsigned int>(m));
02505 }
02506
02507
02508 #ifdef GECODE_HAS_VAR_DISPOSE
02509 template<class VIC>
02510 forceinline VarImpBase*
02511 Space::vars_d(void) const {
02512 return _vars_d[VIC::idx_d];
02513 }
02514 template<class VIC>
02515 forceinline void
02516 Space::vars_d(VarImpBase* x) {
02517 _vars_d[VIC::idx_d] = x;
02518 }
02519 #endif
02520
02521
02522 forceinline void
02523 Actor::operator delete(void*) {}
02524 forceinline void
02525 Actor::operator delete(void*, Space&) {}
02526 forceinline void*
02527 Actor::operator new(size_t s, Space& home) {
02528 return home.ralloc(s);
02529 }
02530
02531 template<class VIC>
02532 forceinline void
02533 VarImp<VIC>::operator delete(void*) {}
02534 template<class VIC>
02535 forceinline void
02536 VarImp<VIC>::operator delete(void*, Space&) {}
02537 template<class VIC>
02538 forceinline void*
02539 VarImp<VIC>::operator new(size_t s, Space& home) {
02540 return home.ralloc(s);
02541 }
02542
02543 #ifndef __GNUC__
02544 forceinline void
02545 Advisor::operator delete(void*) {}
02546 #endif
02547 forceinline void
02548 Advisor::operator delete(void*, Space&) {}
02549 forceinline void*
02550 Advisor::operator new(size_t s, Space& home) {
02551 return home.ralloc(s);
02552 }
02553
02554 forceinline void
02555 NGL::operator delete(void*) {}
02556 forceinline void
02557 NGL::operator delete(void*, Space&) {}
02558 forceinline void*
02559 NGL::operator new(size_t s, Space& home) {
02560 return home.ralloc(s);
02561 }
02562
02563
02564
02565
02566
02567 forceinline
02568 SharedHandle::Object::Object(void)
02569 : next(NULL), fwd(NULL), use_cnt(0) {}
02570 forceinline
02571 SharedHandle::Object::~Object(void) {
02572 assert(use_cnt == 0);
02573 }
02574
02575 forceinline SharedHandle::Object*
02576 SharedHandle::object(void) const {
02577 return o;
02578 }
02579 forceinline void
02580 SharedHandle::subscribe(void) {
02581 if (o != NULL) o->use_cnt++;
02582 }
02583 forceinline void
02584 SharedHandle::cancel(void) {
02585 if ((o != NULL) && (--o->use_cnt == 0))
02586 delete o;
02587 o=NULL;
02588 }
02589 forceinline void
02590 SharedHandle::object(SharedHandle::Object* n) {
02591 if (n != o) {
02592 cancel(); o=n; subscribe();
02593 }
02594 }
02595 forceinline
02596 SharedHandle::SharedHandle(void) : o(NULL) {}
02597 forceinline
02598 SharedHandle::SharedHandle(SharedHandle::Object* so) : o(so) {
02599 subscribe();
02600 }
02601 forceinline
02602 SharedHandle::SharedHandle(const SharedHandle& sh) : o(sh.o) {
02603 subscribe();
02604 }
02605 forceinline SharedHandle&
02606 SharedHandle::operator =(const SharedHandle& sh) {
02607 if (&sh != this) {
02608 cancel(); o=sh.o; subscribe();
02609 }
02610 return *this;
02611 }
02612 forceinline void
02613 SharedHandle::update(Space& home, bool share, SharedHandle& sh) {
02614 if (sh.o == NULL) {
02615 o=NULL; return;
02616 } else if (share) {
02617 o=sh.o;
02618 } else if (sh.o->fwd != NULL) {
02619 o=sh.o->fwd;
02620 } else {
02621 o = sh.o->copy();
02622 sh.o->fwd = o;
02623 sh.o->next = home.pc.c.shared;
02624 home.pc.c.shared = sh.o;
02625 }
02626 subscribe();
02627 }
02628 forceinline
02629 SharedHandle::~SharedHandle(void) {
02630 cancel();
02631 }
02632
02633
02634
02635
02636
02637
02638
02639 forceinline
02640 NoGoods::NoGoods(void)
02641 : n(0) {}
02642 forceinline unsigned long int
02643 NoGoods::ng(void) const {
02644 return n;
02645 }
02646 forceinline void
02647 NoGoods::ng(unsigned long int n0) {
02648 n=n0;
02649 }
02650 forceinline
02651 NoGoods::~NoGoods(void) {}
02652
02653
02654
02655
02656
02657
02658 forceinline ActorLink*
02659 ActorLink::prev(void) const {
02660 return _prev;
02661 }
02662
02663 forceinline ActorLink*
02664 ActorLink::next(void) const {
02665 return _next;
02666 }
02667
02668 forceinline ActorLink**
02669 ActorLink::next_ref(void) {
02670 return &_next;
02671 }
02672
02673 forceinline void
02674 ActorLink::prev(ActorLink* al) {
02675 _prev = al;
02676 }
02677
02678 forceinline void
02679 ActorLink::next(ActorLink* al) {
02680 _next = al;
02681 }
02682
02683 forceinline void
02684 ActorLink::unlink(void) {
02685 ActorLink* p = _prev; ActorLink* n = _next;
02686 p->_next = n; n->_prev = p;
02687 }
02688
02689 forceinline void
02690 ActorLink::init(void) {
02691 _next = this; _prev =this;
02692 }
02693
02694 forceinline void
02695 ActorLink::head(ActorLink* a) {
02696
02697 ActorLink* n = _next;
02698 this->_next = a; a->_prev = this;
02699 a->_next = n; n->_prev = a;
02700 }
02701
02702 forceinline void
02703 ActorLink::tail(ActorLink* a) {
02704
02705 ActorLink* p = _prev;
02706 a->_next = this; this->_prev = a;
02707 p->_next = a; a->_prev = p;
02708 }
02709
02710 forceinline bool
02711 ActorLink::empty(void) const {
02712 return _next == this;
02713 }
02714
02715 template<class T>
02716 forceinline ActorLink*
02717 ActorLink::cast(T* a) {
02718
02719 GECODE_NOT_NULL(a);
02720 ActorLink& t = *a;
02721 return static_cast<ActorLink*>(&t);
02722 }
02723
02724 template<class T>
02725 forceinline const ActorLink*
02726 ActorLink::cast(const T* a) {
02727
02728 GECODE_NOT_NULL(a);
02729 const ActorLink& t = *a;
02730 return static_cast<const ActorLink*>(&t);
02731 }
02732
02733
02734
02735
02736
02737
02738 forceinline Actor*
02739 Actor::cast(ActorLink* al) {
02740
02741 GECODE_NOT_NULL(al);
02742 ActorLink& t = *al;
02743 return static_cast<Actor*>(&t);
02744 }
02745
02746 forceinline const Actor*
02747 Actor::cast(const ActorLink* al) {
02748
02749 GECODE_NOT_NULL(al);
02750 const ActorLink& t = *al;
02751 return static_cast<const Actor*>(&t);
02752 }
02753
02754 forceinline void
02755 Space::afc_enable(void) {
02756 _wmp_afc |= 1U;
02757 }
02758 forceinline bool
02759 Space::afc_enabled(void) const {
02760 return (_wmp_afc & 1U) != 0U;
02761 }
02762 forceinline void
02763 Space::wmp(unsigned int n) {
02764 _wmp_afc = (_wmp_afc & 1U) | (n << 1);
02765 }
02766 forceinline unsigned int
02767 Space::wmp(void) const {
02768 return _wmp_afc >> 1U;
02769 }
02770
02771 forceinline void
02772 Home::notice(Actor& a, ActorProperty p, bool duplicate) {
02773 s.notice(a,p,duplicate);
02774 }
02775
02776 forceinline Space*
02777 Space::clone(bool share, CloneStatistics&) const {
02778
02779
02780
02781 return const_cast<Space*>(this)->_clone(share);
02782 }
02783
02784 forceinline void
02785 Space::commit(const Choice& c, unsigned int a, CommitStatistics&) {
02786 _commit(c,a);
02787 }
02788
02789 forceinline void
02790 Space::trycommit(const Choice& c, unsigned int a, CommitStatistics&) {
02791 _trycommit(c,a);
02792 }
02793
02794 forceinline double
02795 Space::afc_decay(void) const {
02796 return gafc.decay();
02797 }
02798
02799 forceinline size_t
02800 Actor::dispose(Space&) {
02801 return sizeof(*this);
02802 }
02803
02804
02805
02806
02807
02808
02809 forceinline
02810 Home::Home(Space& s0, Propagator* p0) : s(s0), p(p0) {}
02811 forceinline Home&
02812 Home::operator =(const Home& h) {
02813 s=h.s; p=h.p;
02814 return *this;
02815 }
02816 forceinline
02817 Home::operator Space&(void) {
02818 return s;
02819 }
02820 forceinline Home
02821 Home::operator ()(Propagator& p) {
02822 return Home(s,&p);
02823 }
02824 forceinline Home
02825 Space::operator ()(Propagator& p) {
02826 return Home(*this,&p);
02827 }
02828 forceinline Propagator*
02829 Home::propagator(void) const {
02830 return p;
02831 }
02832
02833
02834
02835
02836
02837 forceinline Propagator*
02838 Propagator::cast(ActorLink* al) {
02839
02840 GECODE_NOT_NULL(al);
02841 ActorLink& t = *al;
02842 return static_cast<Propagator*>(&t);
02843 }
02844
02845 forceinline const Propagator*
02846 Propagator::cast(const ActorLink* al) {
02847
02848 GECODE_NOT_NULL(al);
02849 const ActorLink& t = *al;
02850 return static_cast<const Propagator*>(&t);
02851 }
02852
02853 forceinline Propagator*
02854 Propagator::fwd(void) const {
02855 return static_cast<Propagator*>(prev());
02856 }
02857
02858 forceinline
02859 Propagator::Propagator(Home home)
02860 : gafc((home.propagator() != NULL) ?
02861
02862 home.propagator()->gafc :
02863
02864 static_cast<Space&>(home).gafc.allocate()) {
02865 u.advisors = NULL;
02866 assert((u.med == 0) && (u.size == 0));
02867 static_cast<Space&>(home).pl.head(this);
02868 }
02869
02870 forceinline
02871 Propagator::Propagator(Space&, bool, Propagator& p)
02872 : gafc(p.gafc) {
02873 u.advisors = NULL;
02874 assert((u.med == 0) && (u.size == 0));
02875
02876 p.prev(this);
02877 }
02878
02879 forceinline ModEventDelta
02880 Propagator::modeventdelta(void) const {
02881 return u.med;
02882 }
02883
02884 forceinline double
02885 Propagator::afc(const Space& home) const {
02886 return const_cast<Space&>(home).gafc.afc(gafc);
02887 }
02888
02889 forceinline ExecStatus
02890 Space::ES_SUBSUMED_DISPOSED(Propagator& p, size_t s) {
02891 p.u.size = s;
02892 return __ES_SUBSUMED;
02893 }
02894
02895 forceinline ExecStatus
02896 Space::ES_SUBSUMED(Propagator& p) {
02897 p.u.size = p.dispose(*this);
02898 return __ES_SUBSUMED;
02899 }
02900
02901 forceinline ExecStatus
02902 Space::ES_FIX_PARTIAL(Propagator& p, const ModEventDelta& med) {
02903 p.u.med = med;
02904 assert(p.u.med != 0);
02905 return __ES_PARTIAL;
02906 }
02907
02908 forceinline ExecStatus
02909 Space::ES_NOFIX_PARTIAL(Propagator& p, const ModEventDelta& med) {
02910 p.u.med = AllVarConf::med_combine(p.u.med,med);
02911 assert(p.u.med != 0);
02912 return __ES_PARTIAL;
02913 }
02914
02915
02916
02917
02918
02919
02920
02921 forceinline Brancher*
02922 Brancher::cast(ActorLink* al) {
02923
02924 GECODE_NOT_NULL(al);
02925 ActorLink& t = *al;
02926 return static_cast<Brancher*>(&t);
02927 }
02928
02929 forceinline const Brancher*
02930 Brancher::cast(const ActorLink* al) {
02931
02932 GECODE_NOT_NULL(al);
02933 const ActorLink& t = *al;
02934 return static_cast<const Brancher*>(&t);
02935 }
02936
02937 forceinline
02938 Brancher::Brancher(Home home) :
02939 _id(static_cast<Space&>(home).pc.p.branch_id++) {
02940 if (static_cast<Space&>(home).pc.p.branch_id == 0U)
02941 throw TooManyBranchers("Brancher::Brancher");
02942
02943 if (static_cast<Space&>(home).b_status == &static_cast<Space&>(home).bl) {
02944 static_cast<Space&>(home).b_status = this;
02945 if (static_cast<Space&>(home).b_commit == &static_cast<Space&>(home).bl)
02946 static_cast<Space&>(home).b_commit = this;
02947 }
02948 static_cast<Space&>(home).bl.tail(this);
02949 }
02950
02951 forceinline
02952 Brancher::Brancher(Space&, bool, Brancher& b)
02953 : _id(b._id) {
02954
02955 b.prev(this);
02956 }
02957
02958 forceinline unsigned int
02959 Brancher::id(void) const {
02960 return _id;
02961 }
02962
02963 forceinline Brancher*
02964 Space::brancher(unsigned int id) {
02965
02966
02967
02968
02969
02970
02971
02972
02973
02974
02975
02976
02977
02978
02979 Brancher* b_old = b_commit;
02980
02981 while (b_commit != Brancher::cast(&bl))
02982 if (id != b_commit->id())
02983 b_commit = Brancher::cast(b_commit->next());
02984 else
02985 return b_commit;
02986 if (b_commit == Brancher::cast(&bl)) {
02987
02988 b_commit = Brancher::cast(bl.next());
02989 while (b_commit != b_old)
02990 if (id != b_commit->id())
02991 b_commit = Brancher::cast(b_commit->next());
02992 else
02993 return b_commit;
02994 }
02995 return NULL;
02996 }
02997
02998
02999
03000
03001
03002 forceinline
03003 BrancherHandle::BrancherHandle(void)
03004 : _id(Space::reserved_branch_id) {}
03005 forceinline
03006 BrancherHandle::BrancherHandle(const Brancher& b)
03007 : _id(b.id()) {}
03008 forceinline void
03009 BrancherHandle::update(Space&, bool, BrancherHandle& bh) {
03010 _id = bh._id;
03011 }
03012 forceinline unsigned int
03013 BrancherHandle::id(void) const {
03014 return _id;
03015 }
03016 forceinline bool
03017 BrancherHandle::operator ()(const Space& home) const {
03018 return const_cast<Space&>(home).brancher(_id) != NULL;
03019 }
03020 forceinline void
03021 BrancherHandle::kill(Space& home) {
03022 home.kill_brancher(_id);
03023 }
03024
03025
03026
03027
03028
03029
03030
03031 forceinline LocalObject*
03032 LocalObject::cast(ActorLink* al) {
03033
03034 GECODE_NOT_NULL(al);
03035 ActorLink& t = *al;
03036 return static_cast<LocalObject*>(&t);
03037 }
03038
03039 forceinline const LocalObject*
03040 LocalObject::cast(const ActorLink* al) {
03041
03042 GECODE_NOT_NULL(al);
03043 const ActorLink& t = *al;
03044 return static_cast<const LocalObject*>(&t);
03045 }
03046
03047 forceinline
03048 LocalObject::LocalObject(Home) {
03049 ActorLink::cast(this)->prev(NULL);
03050 }
03051
03052 forceinline
03053 LocalObject::LocalObject(Space&,bool,LocalObject&) {
03054 ActorLink::cast(this)->prev(NULL);
03055 }
03056
03057 forceinline LocalObject*
03058 LocalObject::fwd(Space& home, bool share) {
03059 if (prev() == NULL)
03060 fwdcopy(home,share);
03061 return LocalObject::cast(prev());
03062 }
03063
03064 forceinline
03065 LocalHandle::LocalHandle(void) : o(NULL) {}
03066 forceinline
03067 LocalHandle::LocalHandle(LocalObject* lo) : o(lo) {}
03068 forceinline
03069 LocalHandle::LocalHandle(const LocalHandle& lh) : o(lh.o) {}
03070 forceinline LocalHandle&
03071 LocalHandle::operator =(const LocalHandle& lh) {
03072 o = lh.o;
03073 return *this;
03074 }
03075 forceinline
03076 LocalHandle::~LocalHandle(void) {}
03077 forceinline LocalObject*
03078 LocalHandle::object(void) const { return o; }
03079 forceinline void
03080 LocalHandle::object(LocalObject* n) { o = n; }
03081 forceinline void
03082 LocalHandle::update(Space& home, bool share, LocalHandle& lh) {
03083 object(lh.object()->fwd(home,share));
03084 }
03085
03086
03087
03088
03089
03090
03091 forceinline
03092 Choice::Choice(const Brancher& b, const unsigned int a)
03093 : _id(b.id()), _alt(a) {}
03094
03095 forceinline unsigned int
03096 Choice::alternatives(void) const {
03097 return _alt;
03098 }
03099
03100 forceinline unsigned int
03101 Choice::id(void) const {
03102 return _id;
03103 }
03104
03105 forceinline
03106 Choice::~Choice(void) {}
03107
03108
03109
03110
03111
03112
03113
03114 forceinline bool
03115 NGL::leaf(void) const {
03116 return Support::marked(nl);
03117 }
03118 forceinline NGL*
03119 NGL::next(void) const {
03120 return static_cast<NGL*>(Support::funmark(nl));
03121 }
03122 forceinline void
03123 NGL::leaf(bool l) {
03124 nl = l ? Support::fmark(nl) : Support::funmark(nl);
03125 }
03126 forceinline void
03127 NGL::next(NGL* n) {
03128 nl = Support::marked(nl) ? Support::mark(n) : n;
03129 }
03130 forceinline NGL*
03131 NGL::add(NGL* n, bool l) {
03132 nl = Support::marked(nl) ? Support::mark(n) : n;
03133 n->leaf(l);
03134 return n;
03135 }
03136
03137 forceinline
03138 NGL::NGL(void)
03139 : nl(NULL) {}
03140 forceinline
03141 NGL::NGL(Space&)
03142 : nl(NULL) {}
03143 forceinline
03144 NGL::NGL(Space&, bool, NGL&)
03145 : nl(NULL) {}
03146 forceinline size_t
03147 NGL::dispose(Space&) {
03148 return sizeof(*this);
03149 }
03150
03151
03152
03153
03154
03155 template<class A>
03156 forceinline
03157 Advisor::Advisor(Space&, Propagator& p, Council<A>& c) {
03158
03159 ActorLink::prev(&p);
03160
03161 ActorLink::next(c.advisors); c.advisors = static_cast<A*>(this);
03162 }
03163
03164 forceinline
03165 Advisor::Advisor(Space&, bool, Advisor&) {}
03166
03167 forceinline bool
03168 Advisor::disposed(void) const {
03169 return prev() == NULL;
03170 }
03171
03172 forceinline Advisor*
03173 Advisor::cast(ActorLink* al) {
03174 return static_cast<Advisor*>(al);
03175 }
03176
03177 forceinline const Advisor*
03178 Advisor::cast(const ActorLink* al) {
03179 return static_cast<const Advisor*>(al);
03180 }
03181
03182 forceinline Propagator&
03183 Advisor::propagator(void) const {
03184 assert(!disposed());
03185 return *Propagator::cast(ActorLink::prev());
03186 }
03187
03188 template<class A>
03189 forceinline void
03190 Advisor::dispose(Space&,Council<A>&) {
03191 assert(!disposed());
03192 ActorLink::prev(NULL);
03193
03194 Advisor* n = Advisor::cast(next());
03195 if ((n != NULL) && n->disposed())
03196 next(n->next());
03197 }
03198
03199 template<class A>
03200 forceinline ExecStatus
03201 Space::ES_FIX_DISPOSE(Council<A>& c, A& a) {
03202 a.dispose(*this,c);
03203 return ES_FIX;
03204 }
03205
03206 template<class A>
03207 forceinline ExecStatus
03208 Space::ES_NOFIX_DISPOSE(Council<A>& c, A& a) {
03209 a.dispose(*this,c);
03210 return ES_NOFIX;
03211 }
03212
03213 template<class A>
03214 forceinline ExecStatus
03215 Space::ES_NOFIX_DISPOSE_FORCE(Council<A>& c, A& a) {
03216 a.dispose(*this,c);
03217 return ES_NOFIX_FORCE;
03218 }
03219
03220
03221
03222
03223
03224
03225
03226 template<class A>
03227 forceinline
03228 Council<A>::Council(void) {}
03229
03230 template<class A>
03231 forceinline
03232 Council<A>::Council(Space&)
03233 : advisors(NULL) {}
03234
03235 template<class A>
03236 forceinline bool
03237 Council<A>::empty(void) const {
03238 ActorLink* a = advisors;
03239 while ((a != NULL) && static_cast<A*>(a)->disposed())
03240 a = a->next();
03241 advisors = a;
03242 return a == NULL;
03243 }
03244
03245 template<class A>
03246 forceinline void
03247 Council<A>::update(Space& home, bool share, Council<A>& c) {
03248
03249 {
03250 ActorLink* a = c.advisors;
03251 while ((a != NULL) && static_cast<A*>(a)->disposed())
03252 a = a->next();
03253 c.advisors = a;
03254 }
03255
03256 if (c.advisors != NULL) {
03257
03258 Propagator* p_f = &static_cast<A*>(c.advisors)->propagator();
03259
03260 Propagator* p_t = Propagator::cast(p_f->prev());
03261
03262 ActorLink** a_f = &c.advisors;
03263
03264 A* a_t = NULL;
03265 while (*a_f != NULL) {
03266 if (static_cast<A*>(*a_f)->disposed()) {
03267 *a_f = (*a_f)->next();
03268 } else {
03269
03270 A* a = new (home) A(home,share,*static_cast<A*>(*a_f));
03271
03272 a->prev(p_t);
03273
03274 (*a_f)->prev(a);
03275
03276 a->next(a_t);
03277 a_t = a;
03278 a_f = (*a_f)->next_ref();
03279 }
03280 }
03281 advisors = a_t;
03282
03283 assert(p_f->u.advisors == NULL);
03284 p_f->u.advisors = c.advisors;
03285 } else {
03286 advisors = NULL;
03287 }
03288 }
03289
03290 template<class A>
03291 forceinline void
03292 Council<A>::dispose(Space& home) {
03293 ActorLink* a = advisors;
03294 while (a != NULL) {
03295 if (!static_cast<A*>(a)->disposed())
03296 static_cast<A*>(a)->dispose(home,*this);
03297 a = a->next();
03298 }
03299 }
03300
03301
03302
03303
03304
03305
03306
03307 template<class A>
03308 forceinline
03309 Advisors<A>::Advisors(const Council<A>& c)
03310 : a(c.advisors) {
03311 while ((a != NULL) && static_cast<A*>(a)->disposed())
03312 a = a->next();
03313 }
03314
03315 template<class A>
03316 forceinline bool
03317 Advisors<A>::operator ()(void) const {
03318 return a != NULL;
03319 }
03320
03321 template<class A>
03322 forceinline void
03323 Advisors<A>::operator ++(void) {
03324 do {
03325 a = a->next();
03326 } while ((a != NULL) && static_cast<A*>(a)->disposed());
03327 }
03328
03329 template<class A>
03330 forceinline A&
03331 Advisors<A>::advisor(void) const {
03332 return *static_cast<A*>(a);
03333 }
03334
03335
03336
03337
03338
03339
03340
03341 forceinline void
03342 Space::enqueue(Propagator* p) {
03343 ActorLink::cast(p)->unlink();
03344 ActorLink* c = &pc.p.queue[p->cost(*this,p->u.med).ac];
03345 c->tail(ActorLink::cast(p));
03346 if (c > pc.p.active)
03347 pc.p.active = c;
03348 }
03349
03350 forceinline void
03351 Space::fail(void) {
03352
03353
03354
03355
03356
03357 pc.p.active = &pc.p.queue[PropCost::AC_MAX+1]+1;
03358 }
03359 forceinline void
03360 Home::fail(void) {
03361 s.fail();
03362 }
03363
03364 forceinline bool
03365 Space::failed(void) const {
03366 return pc.p.active > &pc.p.queue[PropCost::AC_MAX+1];
03367 }
03368 forceinline bool
03369 Home::failed(void) const {
03370 return s.failed();
03371 }
03372
03373 forceinline bool
03374 Space::stable(void) const {
03375 return ((pc.p.active < &pc.p.queue[0]) ||
03376 (pc.p.active > &pc.p.queue[PropCost::AC_MAX+1]));
03377 }
03378
03379
03380
03381
03382
03383
03384
03385 template<class VIC>
03386 forceinline ActorLink**
03387 VarImp<VIC>::actor(PropCond pc) {
03388 assert((pc >= 0) && (pc < pc_max+2));
03389 return (pc == 0) ? b.base : b.base+u.idx[pc-1];
03390 }
03391
03392 template<class VIC>
03393 forceinline ActorLink**
03394 VarImp<VIC>::actorNonZero(PropCond pc) {
03395 assert((pc > 0) && (pc < pc_max+2));
03396 return b.base+u.idx[pc-1];
03397 }
03398
03399 template<class VIC>
03400 forceinline unsigned int&
03401 VarImp<VIC>::idx(PropCond pc) {
03402 assert((pc > 0) && (pc < pc_max+2));
03403 return u.idx[pc-1];
03404 }
03405
03406 template<class VIC>
03407 forceinline unsigned int
03408 VarImp<VIC>::idx(PropCond pc) const {
03409 assert((pc > 0) && (pc < pc_max+2));
03410 return u.idx[pc-1];
03411 }
03412
03413 template<class VIC>
03414 forceinline
03415 VarImp<VIC>::VarImp(Space&) {
03416 b.base = NULL; entries = 0;
03417 for (PropCond pc=1; pc<pc_max+2; pc++)
03418 idx(pc) = 0;
03419 free_and_bits = 0;
03420 }
03421
03422 template<class VIC>
03423 forceinline
03424 VarImp<VIC>::VarImp(void) {
03425 b.base = NULL; entries = 0;
03426 for (PropCond pc=1; pc<pc_max+2; pc++)
03427 idx(pc) = 0;
03428 free_and_bits = 0;
03429 }
03430
03431 template<class VIC>
03432 forceinline unsigned int
03433 VarImp<VIC>::degree(void) const {
03434 assert(!copied());
03435 return entries;
03436 }
03437
03438 template<class VIC>
03439 forceinline double
03440 VarImp<VIC>::afc(const Space& home) const {
03441 double d = 0.0;
03442
03443 {
03444 ActorLink** a = const_cast<VarImp<VIC>*>(this)->actor(0);
03445 ActorLink** e = const_cast<VarImp<VIC>*>(this)->actorNonZero(pc_max+1);
03446 while (a < e) {
03447 d += Propagator::cast(*a)->afc(home); a++;
03448 }
03449 }
03450
03451 {
03452 ActorLink** a = const_cast<VarImp<VIC>*>(this)->actorNonZero(pc_max+1);
03453 ActorLink** e = const_cast<VarImp<VIC>*>(this)->b.base+entries;
03454 while (a < e) {
03455 d += Advisor::cast(*a)->propagator().afc(home); a++;
03456 }
03457 }
03458 return d;
03459 }
03460
03461 template<class VIC>
03462 forceinline ModEvent
03463 VarImp<VIC>::modevent(const Delta& d) {
03464 return d.me;
03465 }
03466
03467 template<class VIC>
03468 forceinline unsigned int
03469 VarImp<VIC>::bits(void) const {
03470 return free_and_bits;
03471 }
03472
03473 template<class VIC>
03474 forceinline unsigned int&
03475 VarImp<VIC>::bits(void) {
03476 return free_and_bits;
03477 }
03478
03479 #ifdef GECODE_HAS_VAR_DISPOSE
03480 template<class VIC>
03481 forceinline VarImp<VIC>*
03482 VarImp<VIC>::vars_d(Space& home) {
03483 return static_cast<VarImp<VIC>*>(home.vars_d<VIC>());
03484 }
03485
03486 template<class VIC>
03487 forceinline void
03488 VarImp<VIC>::vars_d(Space& home, VarImp<VIC>* x) {
03489 home.vars_d<VIC>(x);
03490 }
03491 #endif
03492
03493 template<class VIC>
03494 forceinline bool
03495 VarImp<VIC>::copied(void) const {
03496 return Support::marked(b.fwd);
03497 }
03498
03499 template<class VIC>
03500 forceinline VarImp<VIC>*
03501 VarImp<VIC>::forward(void) const {
03502 assert(copied());
03503 return static_cast<VarImp<VIC>*>(Support::unmark(b.fwd));
03504 }
03505
03506 template<class VIC>
03507 forceinline VarImp<VIC>*
03508 VarImp<VIC>::next(void) const {
03509 assert(copied());
03510 return u.next;
03511 }
03512
03513 template<class VIC>
03514 forceinline
03515 VarImp<VIC>::VarImp(Space& home, bool, VarImp<VIC>& x) {
03516 VarImpBase** reg;
03517 free_and_bits = x.free_and_bits & ((1 << free_bits) - 1);
03518 if (x.b.base == NULL) {
03519
03520 reg = &home.pc.c.vars_noidx;
03521 assert(x.degree() == 0);
03522 } else {
03523 reg = &home.pc.c.vars_u[idx_c];
03524 }
03525
03526 b.base = x.b.base;
03527 entries = x.entries;
03528 for (PropCond pc=1; pc<pc_max+2; pc++)
03529 idx(pc) = x.idx(pc);
03530
03531
03532 x.b.fwd = static_cast<VarImp<VIC>*>(Support::mark(this));
03533
03534 x.u.next = static_cast<VarImp<VIC>*>(*reg); *reg = &x;
03535 }
03536
03537 template<class VIC>
03538 forceinline ModEvent
03539 VarImp<VIC>::me(const ModEventDelta& med) {
03540 return static_cast<ModEvent>((med & VIC::med_mask) >> VIC::med_fst);
03541 }
03542
03543 template<class VIC>
03544 forceinline ModEventDelta
03545 VarImp<VIC>::med(ModEvent me) {
03546 return static_cast<ModEventDelta>(me << VIC::med_fst);
03547 }
03548
03549 template<class VIC>
03550 forceinline ModEvent
03551 VarImp<VIC>::me_combine(ModEvent me1, ModEvent me2) {
03552 return VIC::me_combine(me1,me2);
03553 }
03554
03555 template<class VIC>
03556 forceinline void
03557 VarImp<VIC>::schedule(Space& home, Propagator& p, ModEvent me,
03558 bool force) {
03559 if (VIC::med_update(p.u.med,me) || force)
03560 home.enqueue(&p);
03561 }
03562
03563 template<class VIC>
03564 forceinline void
03565 VarImp<VIC>::schedule(Space& home, PropCond pc1, PropCond pc2, ModEvent me) {
03566 ActorLink** b = actor(pc1);
03567 ActorLink** p = actorNonZero(pc2+1);
03568 while (p-- > b)
03569 schedule(home,*Propagator::cast(*p),me);
03570 }
03571
03572 template<class VIC>
03573 forceinline void
03574 VarImp<VIC>::enter(Space& home, Propagator* p, PropCond pc) {
03575 assert(pc <= pc_max);
03576
03577 home.pc.p.n_sub += 1;
03578 if ((free_and_bits >> free_bits) == 0)
03579 resize(home);
03580 free_and_bits -= 1 << free_bits;
03581
03582
03583 b.base[entries] = *actorNonZero(pc_max+1);
03584 entries++;
03585 for (PropCond j = pc_max; j > pc; j--) {
03586 *actorNonZero(j+1) = *actorNonZero(j);
03587 idx(j+1)++;
03588 }
03589 *actorNonZero(pc+1) = *actor(pc);
03590 idx(pc+1)++;
03591 *actor(pc) = ActorLink::cast(p);
03592
03593 #ifdef GECODE_AUDIT
03594 ActorLink** f = actor(pc);
03595 while (f < (pc == pc_max+1 ? b.base+entries : actorNonZero(pc+1)))
03596 if (*f == p)
03597 goto found;
03598 else
03599 f++;
03600 GECODE_NEVER;
03601 found: ;
03602 #endif
03603 }
03604
03605 template<class VIC>
03606 forceinline void
03607 VarImp<VIC>::enter(Space& home, Advisor* a) {
03608
03609 home.pc.p.n_sub += 1;
03610 if ((free_and_bits >> free_bits) == 0)
03611 resize(home);
03612 free_and_bits -= 1 << free_bits;
03613
03614
03615 b.base[entries++] = *actorNonZero(pc_max+1);
03616 *actorNonZero(pc_max+1) = a;
03617 }
03618
03619 template<class VIC>
03620 void
03621 VarImp<VIC>::resize(Space& home) {
03622 if (b.base == NULL) {
03623 assert((free_and_bits >> free_bits) == 0);
03624
03625 free_and_bits += 4 << free_bits;
03626 b.base = home.alloc<ActorLink*>(4);
03627 for (int i=0; i<pc_max+1; i++)
03628 u.idx[i] = 0;
03629 } else {
03630
03631 unsigned int n = degree();
03632
03633
03634
03635 ActorLink** s = static_cast<ActorLink**>(home.mm.subscriptions());
03636 unsigned int m =
03637 ((s <= b.base) && (b.base < s+home.pc.p.n_sub)) ?
03638 (n+4) : ((n+1)*3>>1);
03639 ActorLink** prop = home.alloc<ActorLink*>(m);
03640 free_and_bits += (m-n) << free_bits;
03641
03642 Heap::copy<ActorLink*>(prop, b.base, n);
03643 home.free<ActorLink*>(b.base,n);
03644 b.base = prop;
03645 }
03646 }
03647
03648 template<class VIC>
03649 void
03650 VarImp<VIC>::subscribe(Space& home, Propagator& p, PropCond pc,
03651 bool assigned, ModEvent me, bool schedule) {
03652 if (assigned) {
03653
03654 if (schedule)
03655 VarImp<VIC>::schedule(home,p,ME_GEN_ASSIGNED);
03656 } else {
03657 enter(home,&p,pc);
03658
03659 if (schedule && (pc != PC_GEN_ASSIGNED))
03660 VarImp<VIC>::schedule(home,p,me);
03661 }
03662 }
03663
03664 template<class VIC>
03665 forceinline void
03666 VarImp<VIC>::subscribe(Space& home, Advisor& a, bool assigned) {
03667 if (!assigned)
03668 enter(home,&a);
03669 }
03670
03671 template<class VIC>
03672 forceinline void
03673 VarImp<VIC>::remove(Space& home, Propagator* p, PropCond pc) {
03674 assert(pc <= pc_max);
03675 ActorLink* a = ActorLink::cast(p);
03676
03677 ActorLink** f = actor(pc);
03678 #ifdef GECODE_AUDIT
03679 while (f < actorNonZero(pc+1))
03680 if (*f == a)
03681 goto found;
03682 else
03683 f++;
03684 GECODE_NEVER;
03685 found: ;
03686 #else
03687 while (*f != a) f++;
03688 #endif
03689
03690 *f = *(actorNonZero(pc+1)-1);
03691 for (PropCond j = pc+1; j< pc_max+1; j++) {
03692 *(actorNonZero(j)-1) = *(actorNonZero(j+1)-1);
03693 idx(j)--;
03694 }
03695 *(actorNonZero(pc_max+1)-1) = b.base[entries-1];
03696 idx(pc_max+1)--;
03697 entries--;
03698 free_and_bits += 1 << free_bits;
03699 home.pc.p.n_sub -= 1;
03700 }
03701
03702 template<class VIC>
03703 forceinline void
03704 VarImp<VIC>::remove(Space& home, Advisor* a) {
03705
03706 ActorLink** f = actorNonZero(pc_max+1);
03707 #ifdef GECODE_AUDIT
03708 while (f < b.base+entries)
03709 if (*f == a)
03710 goto found;
03711 else
03712 f++;
03713 GECODE_NEVER;
03714 found: ;
03715 #else
03716 while (*f != a) f++;
03717 #endif
03718
03719 *f = b.base[--entries];
03720 free_and_bits += 1 << free_bits;
03721 home.pc.p.n_sub -= 1;
03722 }
03723
03724 template<class VIC>
03725 forceinline void
03726 VarImp<VIC>::cancel(Space& home, Propagator& p, PropCond pc, bool assigned) {
03727 if (!assigned)
03728 remove(home,&p,pc);
03729 }
03730
03731 template<class VIC>
03732 forceinline void
03733 VarImp<VIC>::cancel(Space& home, Advisor& a, bool assigned) {
03734 if (!assigned)
03735 remove(home,&a);
03736 }
03737
03738 template<class VIC>
03739 forceinline void
03740 VarImp<VIC>::cancel(Space& home) {
03741 unsigned int n_sub = degree();
03742 home.pc.p.n_sub -= n_sub;
03743 unsigned int n = (free_and_bits >> VIC::free_bits) + n_sub;
03744 home.free<ActorLink*>(b.base,n);
03745
03746 b.base = NULL;
03747
03748 entries = 0;
03749 }
03750
03751 template<class VIC>
03752 forceinline bool
03753 VarImp<VIC>::advise(Space& home, ModEvent me, Delta& d) {
03754
03755
03756
03757
03758
03759 ActorLink** la = actorNonZero(pc_max+1);
03760 ActorLink** le = b.base+entries;
03761 if (la == le)
03762 return true;
03763 d.me = me;
03764
03765
03766
03767 do {
03768 Advisor* a = Advisor::cast(*la);
03769 assert(!a->disposed());
03770 Propagator& p = a->propagator();
03771 switch (p.advise(home,*a,d)) {
03772 case ES_FIX:
03773 break;
03774 case ES_FAILED:
03775 if (home.afc_enabled())
03776 home.gafc.fail(p.gafc);
03777 return false;
03778 case ES_NOFIX:
03779 schedule(home,p,me);
03780 break;
03781 case ES_NOFIX_FORCE:
03782 schedule(home,p,me,true);
03783 break;
03784 default:
03785 GECODE_NEVER;
03786 }
03787 } while (++la < le);
03788 return true;
03789 }
03790
03791 template<class VIC>
03792 forceinline void
03793 VarImp<VIC>::update(VarImp<VIC>* x, ActorLink**& sub) {
03794
03795
03796
03797 x->b.base = b.base;
03798 x->u.idx[0] = u.idx[0];
03799 if (pc_max > 0 && sizeof(ActorLink**) > sizeof(unsigned int))
03800 x->u.idx[1] = u.idx[1];
03801
03802 ActorLink** f = x->b.base;
03803 unsigned int n = x->degree();
03804 ActorLink** t = sub;
03805 sub += n;
03806 b.base = t;
03807
03808 while (n >= 4) {
03809 n -= 4;
03810 t[0]=f[0]->prev(); t[1]=f[1]->prev();
03811 t[2]=f[2]->prev(); t[3]=f[3]->prev();
03812 t += 4; f += 4;
03813 }
03814 if (n >= 2) {
03815 n -= 2;
03816 t[0]=f[0]->prev(); t[1]=f[1]->prev();
03817 t += 2; f += 2;
03818 }
03819 if (n > 0) {
03820 t[0]=f[0]->prev();
03821 }
03822 }
03823
03824 template<class VIC>
03825 forceinline void
03826 VarImp<VIC>::update(Space& home, ActorLink**& sub) {
03827 VarImp<VIC>* x = static_cast<VarImp<VIC>*>(home.pc.c.vars_u[idx_c]);
03828 while (x != NULL) {
03829 VarImp<VIC>* n = x->next(); x->forward()->update(x,sub); x = n;
03830 }
03831 }
03832
03833
03834
03835
03836
03837
03838
03839 template<class VarImp>
03840 VarImpDisposer<VarImp>::VarImpDisposer(void) {
03841 #ifdef GECODE_HAS_VAR_DISPOSE
03842 Space::vd[VarImp::idx_d] = this;
03843 #endif
03844 }
03845
03846 template<class VarImp>
03847 void
03848 VarImpDisposer<VarImp>::dispose(Space& home, VarImpBase* _x) {
03849 VarImp* x = static_cast<VarImp*>(_x);
03850 do {
03851 x->dispose(home); x = static_cast<VarImp*>(x->next_d());
03852 } while (x != NULL);
03853 }
03854
03855
03856
03857
03858
03859 forceinline void
03860 StatusStatistics::reset(void) {
03861 propagate = 0;
03862 wmp = false;
03863 }
03864 forceinline
03865 StatusStatistics::StatusStatistics(void) {
03866 reset();
03867 }
03868 forceinline StatusStatistics&
03869 StatusStatistics::operator +=(const StatusStatistics& s) {
03870 propagate += s.propagate;
03871 wmp |= s.wmp;
03872 return *this;
03873 }
03874 forceinline StatusStatistics
03875 StatusStatistics::operator +(const StatusStatistics& s) {
03876 StatusStatistics t(s);
03877 return t += *this;
03878 }
03879
03880 forceinline void
03881 CloneStatistics::reset(void) {}
03882
03883 forceinline
03884 CloneStatistics::CloneStatistics(void) {
03885 reset();
03886 }
03887 forceinline CloneStatistics
03888 CloneStatistics::operator +(const CloneStatistics&) {
03889 CloneStatistics s;
03890 return s;
03891 }
03892 forceinline CloneStatistics&
03893 CloneStatistics::operator +=(const CloneStatistics&) {
03894 return *this;
03895 }
03896
03897 forceinline void
03898 CommitStatistics::reset(void) {}
03899
03900 forceinline
03901 CommitStatistics::CommitStatistics(void) {
03902 reset();
03903 }
03904 forceinline CommitStatistics
03905 CommitStatistics::operator +(const CommitStatistics&) {
03906 CommitStatistics s;
03907 return s;
03908 }
03909 forceinline CommitStatistics&
03910 CommitStatistics::operator +=(const CommitStatistics&) {
03911 return *this;
03912 }
03913
03914
03915
03916
03917
03918
03919 forceinline
03920 PropCost::PropCost(PropCost::ActualCost ac0) : ac(ac0) {}
03921
03922 forceinline PropCost
03923 PropCost::cost(PropCost::Mod m,
03924 PropCost::ActualCost lo, PropCost::ActualCost hi,
03925 unsigned int n) {
03926 if (n < 2)
03927 return (m == LO) ? AC_UNARY_LO : AC_UNARY_HI;
03928 else if (n == 2)
03929 return (m == LO) ? AC_BINARY_LO : AC_BINARY_HI;
03930 else if (n == 3)
03931 return (m == LO) ? AC_TERNARY_LO : AC_TERNARY_HI;
03932 else
03933 return (m == LO) ? lo : hi;
03934 }
03935
03936 forceinline PropCost
03937 PropCost::crazy(PropCost::Mod m, unsigned int n) {
03938 return cost(m,AC_CRAZY_LO,AC_CRAZY_HI,n);
03939 }
03940 forceinline PropCost
03941 PropCost::crazy(PropCost::Mod m, int n) {
03942 assert(n >= 0);
03943 return crazy(m,static_cast<unsigned int>(n));
03944 }
03945 forceinline PropCost
03946 PropCost::cubic(PropCost::Mod m, unsigned int n) {
03947 return cost(m,AC_CUBIC_LO,AC_CUBIC_HI,n);
03948 }
03949 forceinline PropCost
03950 PropCost::cubic(PropCost::Mod m, int n) {
03951 assert(n >= 0);
03952 return cubic(m,static_cast<unsigned int>(n));
03953 }
03954 forceinline PropCost
03955 PropCost::quadratic(PropCost::Mod m, unsigned int n) {
03956 return cost(m,AC_QUADRATIC_LO,AC_QUADRATIC_HI,n);
03957 }
03958 forceinline PropCost
03959 PropCost::quadratic(PropCost::Mod m, int n) {
03960 assert(n >= 0);
03961 return quadratic(m,static_cast<unsigned int>(n));
03962 }
03963 forceinline PropCost
03964 PropCost::linear(PropCost::Mod m, unsigned int n) {
03965 return cost(m,AC_LINEAR_LO,AC_LINEAR_HI,n);
03966 }
03967 forceinline PropCost
03968 PropCost::linear(PropCost::Mod m, int n) {
03969 assert(n >= 0);
03970 return linear(m,static_cast<unsigned int>(n));
03971 }
03972 forceinline PropCost
03973 PropCost::ternary(PropCost::Mod m) {
03974 return (m == LO) ? AC_TERNARY_LO : AC_TERNARY_HI;
03975 }
03976 forceinline PropCost
03977 PropCost::binary(PropCost::Mod m) {
03978 return (m == LO) ? AC_BINARY_LO : AC_BINARY_HI;
03979 }
03980 forceinline PropCost
03981 PropCost::unary(PropCost::Mod m) {
03982 return (m == LO) ? AC_UNARY_LO : AC_UNARY_HI;
03983 }
03984
03985
03986
03987
03988
03989 forceinline
03990 Space::Propagators::Propagators(const Space& home0)
03991 : home(home0), q(home.pc.p.active) {
03992 while (q >= &home.pc.p.queue[0]) {
03993 if (q->next() != q) {
03994 c = q->next(); e = q; q--;
03995 return;
03996 }
03997 q--;
03998 }
03999 q = NULL;
04000 if (!home.pl.empty()) {
04001 c = Propagator::cast(home.pl.next());
04002 e = Propagator::cast(&home.pl);
04003 } else {
04004 c = e = NULL;
04005 }
04006 }
04007 forceinline bool
04008 Space::Propagators::operator ()(void) const {
04009 return c != NULL;
04010 }
04011 forceinline void
04012 Space::Propagators::operator ++(void) {
04013 c = c->next();
04014 if (c == e) {
04015 if (q == NULL) {
04016 c = NULL;
04017 } else {
04018 while (q >= &home.pc.p.queue[0]) {
04019 if (q->next() != q) {
04020 c = q->next(); e = q; q--;
04021 return;
04022 }
04023 q--;
04024 }
04025 q = NULL;
04026 if (!home.pl.empty()) {
04027 c = Propagator::cast(home.pl.next());
04028 e = Propagator::cast(&home.pl);
04029 } else {
04030 c = NULL;
04031 }
04032 }
04033 }
04034 }
04035 forceinline const Propagator&
04036 Space::Propagators::propagator(void) const {
04037 return *Propagator::cast(c);
04038 }
04039
04040 forceinline
04041 Space::Branchers::Branchers(const Space& home)
04042 : c(Brancher::cast(home.bl.next())), e(&home.bl) {}
04043 forceinline bool
04044 Space::Branchers::operator ()(void) const {
04045 return c != e;
04046 }
04047 forceinline void
04048 Space::Branchers::operator ++(void) {
04049 c = c->next();
04050 }
04051 forceinline const Brancher&
04052 Space::Branchers::brancher(void) const {
04053 return *Brancher::cast(c);
04054 }
04055
04056
04057
04058
04059
04060 template<class T>
04061 forceinline T&
04062 Space::construct(void) {
04063 return alloc<T>(1);
04064 }
04065 template<class T, typename A1>
04066 forceinline T&
04067 Space::construct(A1 const& a1) {
04068 T& t = *static_cast<T*>(ralloc(sizeof(T)));
04069 new (&t) T(a1);
04070 return t;
04071 }
04072 template<class T, typename A1, typename A2>
04073 forceinline T&
04074 Space::construct(A1 const& a1, A2 const& a2) {
04075 T& t = *static_cast<T*>(ralloc(sizeof(T)));
04076 new (&t) T(a1,a2);
04077 return t;
04078 }
04079 template<class T, typename A1, typename A2, typename A3>
04080 forceinline T&
04081 Space::construct(A1 const& a1, A2 const& a2, A3 const& a3) {
04082 T& t = *static_cast<T*>(ralloc(sizeof(T)));
04083 new (&t) T(a1,a2,a3);
04084 return t;
04085 }
04086 template<class T, typename A1, typename A2, typename A3, typename A4>
04087 forceinline T&
04088 Space::construct(A1 const& a1, A2 const& a2, A3 const& a3, A4 const& a4) {
04089 T& t = *static_cast<T*>(ralloc(sizeof(T)));
04090 new (&t) T(a1,a2,a3,a4);
04091 return t;
04092 }
04093 template<class T, typename A1, typename A2, typename A3, typename A4, typename A5>
04094 forceinline T&
04095 Space::construct(A1 const& a1, A2 const& a2, A3 const& a3, A4 const& a4, A5 const& a5) {
04096 T& t = *static_cast<T*>(ralloc(sizeof(T)));
04097 new (&t) T(a1,a2,a3,a4,a5);
04098 return t;
04099 }
04100
04101 }
04102
04103