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 namespace Gecode {
00050
00051 class Space;
00052
00077 class SharedHandle {
00078 public:
00086 class Object {
00087 friend class Space;
00088 friend class SharedHandle;
00089 private:
00091 Object* next;
00093 Object* fwd;
00095 unsigned int use_cnt;
00096 public:
00098 Object(void);
00100 virtual Object* copy(void) const = 0;
00102 virtual ~Object(void);
00104 static void* operator new(size_t s);
00106 static void operator delete(void* p);
00107 };
00108 private:
00110 Object* o;
00112 void subscribe(void);
00114 void cancel(void);
00115 public:
00117 SharedHandle(void);
00119 SharedHandle(SharedHandle::Object* so);
00121 SharedHandle(const SharedHandle& sh);
00123 SharedHandle& operator =(const SharedHandle& sh);
00125 void update(Space& home, bool share, SharedHandle& sh);
00127 ~SharedHandle(void);
00128 protected:
00130 SharedHandle::Object* object(void) const;
00132 void object(SharedHandle::Object* n);
00133 };
00134
00143
00144 typedef int ModEvent;
00145
00147 const ModEvent ME_GEN_FAILED = -1;
00149 const ModEvent ME_GEN_NONE = 0;
00151 const ModEvent ME_GEN_ASSIGNED = 1;
00152
00154 typedef int PropCond;
00156 const PropCond PC_GEN_NONE = -1;
00158 const PropCond PC_GEN_ASSIGNED = 0;
00160
00171 typedef int ModEventDelta;
00172
00173 }
00174
00175 #include <gecode/kernel/var-type.hpp>
00176
00177 namespace Gecode {
00178
00180 class NoIdxVarImpConf {
00181 public:
00183 static const int idx_c = -1;
00185 static const int idx_d = -1;
00187 static const PropCond pc_max = PC_GEN_ASSIGNED;
00189 static const int free_bits = 0;
00191 static const int med_fst = 0;
00193 static const int med_lst = 0;
00195 static const int med_mask = 0;
00197 static Gecode::ModEvent me_combine(ModEvent me1, ModEvent me2);
00199 static bool med_update(ModEventDelta& med, ModEvent me);
00200 };
00201
00202 forceinline ModEvent
00203 NoIdxVarImpConf::me_combine(ModEvent, ModEvent) {
00204 GECODE_NEVER; return 0;
00205 }
00206 forceinline bool
00207 NoIdxVarImpConf::med_update(ModEventDelta&, ModEvent) {
00208 GECODE_NEVER; return false;
00209 }
00210
00211
00212
00213
00214
00215
00216 class ActorLink;
00217 class Actor;
00218 class Propagator;
00219 class LocalObject;
00220 class Advisor;
00221 template<class A> class Council;
00222 template<class A> class Advisors;
00223 template<class VIC> class VarImp;
00224
00225
00226
00227
00228
00229
00230
00238 class VarImpBase {};
00239
00246 class GECODE_VTABLE_EXPORT VarImpDisposerBase {
00247 public:
00249 GECODE_KERNEL_EXPORT virtual void dispose(Space& home, VarImpBase* x);
00251 GECODE_KERNEL_EXPORT virtual ~VarImpDisposerBase(void);
00252 };
00253
00260 template<class VarImp>
00261 class VarImpDisposer : public VarImpDisposerBase {
00262 public:
00264 VarImpDisposer(void);
00266 virtual void dispose(Space& home, VarImpBase* x);
00267 };
00268
00270 class Delta {
00271 template<class VIC> friend class VarImp;
00272 private:
00274 ModEvent me;
00275 };
00276
00284 template<class VIC>
00285 class VarImp : public VarImpBase {
00286 friend class Space;
00287 friend class Propagator;
00288 template<class VarImp> friend class VarImpDisposer;
00289 private:
00301 ActorLink** base;
00302
00304 static const int idx_c = VIC::idx_c;
00306 static const int idx_d = VIC::idx_d;
00308 static const int free_bits = VIC::free_bits;
00310 unsigned int entries;
00312 unsigned int free_and_bits;
00314 static const Gecode::PropCond pc_max = VIC::pc_max;
00315
00316 union {
00327 unsigned int idx[pc_max+1];
00329 VarImp<VIC>* next;
00330 } u;
00331
00333 ActorLink** actor(PropCond pc);
00335 ActorLink** actorNonZero(PropCond pc);
00337 unsigned int& idx(PropCond pc);
00339 unsigned int idx(PropCond pc) const;
00340
00347 void update(VarImp* x, ActorLink**& sub);
00354 static void update(Space& home, ActorLink**& sub);
00355
00357 void enter(Space& home, Propagator* p, PropCond pc);
00359 void enter(Space& home, Advisor* a);
00361 void resize(Space& home);
00363 void remove(Space& home, Propagator* p, PropCond pc);
00365 void remove(Space& home, Advisor* a);
00366
00367
00368 protected:
00370 void cancel(Space& home);
00376 bool advise(Space& home, ModEvent me, Delta& d);
00377 #ifdef GECODE_HAS_VAR_DISPOSE
00378
00379 static VarImp<VIC>* vars_d(Space& home);
00381 static void vars_d(Space& home, VarImp<VIC>* x);
00382 #endif
00383
00384 public:
00386 VarImp(Space& home);
00388 VarImp(void);
00389
00391
00392
00404 void subscribe(Space& home, Propagator& p, PropCond pc,
00405 bool assigned, ModEvent me, bool schedule);
00411 void cancel(Space& home, Propagator& p, PropCond pc,
00412 bool assigned);
00418 void subscribe(Space& home, Advisor& a, bool assigned);
00424 void cancel(Space& home, Advisor& a, bool assigned);
00425
00432 unsigned int degree(void) const;
00439 double afc(void) const;
00441
00443
00444
00445 VarImp(Space& home, bool share, VarImp& x);
00447 bool copied(void) const;
00449 VarImp* forward(void) const;
00451 VarImp* next(void) const;
00453
00455
00456
00463 static void schedule(Space& home, Propagator& p, ModEvent me,
00464 bool force = false);
00466 static ModEvent me(const ModEventDelta& med);
00468 static ModEventDelta med(ModEvent me);
00470 static ModEvent me_combine(ModEvent me1, ModEvent me2);
00472
00474
00475
00476 static ModEvent modevent(const Delta& d);
00478
00480
00481
00482 unsigned int bits(void) const;
00484 unsigned int& bits(void);
00486
00487 protected:
00489 void schedule(Space& home, PropCond pc1, PropCond pc2, ModEvent me);
00490
00491 public:
00493
00494
00495 static void* operator new(size_t,Space&);
00497 static void operator delete(void*,Space&);
00499 static void operator delete(void*);
00501 };
00502
00511 enum ExecStatus {
00512 __ES_SUBSUMED = -2,
00513 ES_FAILED = -1,
00514 ES_NOFIX = 0,
00515 ES_OK = 0,
00516 ES_FIX = 1,
00517 ES_NOFIX_FORCE = 2,
00518 __ES_PARTIAL = 2
00519 };
00520
00525 class PropCost {
00526 friend class Space;
00527 public:
00529 enum ActualCost {
00530 AC_CRAZY_LO = 0,
00531 AC_CRAZY_HI = 0,
00532 AC_CUBIC_LO = 1,
00533 AC_CUBIC_HI = 1,
00534 AC_QUADRATIC_LO = 2,
00535 AC_QUADRATIC_HI = 2,
00536 AC_LINEAR_HI = 3,
00537 AC_LINEAR_LO = 4,
00538 AC_TERNARY_HI = 4,
00539 AC_BINARY_HI = 5,
00540 AC_TERNARY_LO = 5,
00541 AC_BINARY_LO = 6,
00542 AC_UNARY_LO = 6,
00543 AC_UNARY_HI = 6,
00544 AC_MAX = 6
00545 };
00547 ActualCost ac;
00548 public:
00550 enum Mod {
00551 LO,
00552 HI
00553 };
00554 private:
00556 static PropCost cost(Mod m, ActualCost lo, ActualCost hi, unsigned int n);
00558 PropCost(ActualCost ac);
00559 public:
00561 static PropCost crazy(PropCost::Mod m, unsigned int n);
00563 static PropCost crazy(PropCost::Mod m, int n);
00565 static PropCost cubic(PropCost::Mod m, unsigned int n);
00567 static PropCost cubic(PropCost::Mod m, int n);
00569 static PropCost quadratic(PropCost::Mod m, unsigned int n);
00571 static PropCost quadratic(PropCost::Mod m, int n);
00573 static PropCost linear(PropCost::Mod m, unsigned int n);
00575 static PropCost linear(PropCost::Mod m, int n);
00577 static PropCost ternary(PropCost::Mod m);
00579 static PropCost binary(PropCost::Mod m);
00581 static PropCost unary(PropCost::Mod m);
00582 };
00583
00584
00589 enum ActorProperty {
00598 AP_DISPOSE = (1 << 0),
00604 AP_WEAKLY = (1 << 1)
00605 };
00606
00607
00615 class ActorLink {
00616 friend class Actor;
00617 friend class Propagator;
00618 friend class Advisor;
00619 friend class Brancher;
00620 friend class LocalObject;
00621 friend class Space;
00622 template<class VIC> friend class VarImp;
00623 private:
00624 ActorLink* _next; ActorLink* _prev;
00625 public:
00627
00628 ActorLink* prev(void) const; void prev(ActorLink*);
00629 ActorLink* next(void) const; void next(ActorLink*);
00630 ActorLink** next_ref(void);
00632
00634 void init(void);
00636 void unlink(void);
00638 void head(ActorLink* al);
00640 void tail(ActorLink* al);
00642 bool empty(void) const;
00644 template<class T> static ActorLink* cast(T* a);
00646 template<class T> static const ActorLink* cast(const T* a);
00647 };
00648
00649
00654 class GECODE_VTABLE_EXPORT Actor : private ActorLink {
00655 friend class ActorLink;
00656 friend class Space;
00657 friend class Propagator;
00658 friend class Advisor;
00659 friend class Brancher;
00660 friend class LocalObject;
00661 template<class VIC> friend class VarImp;
00662 template<class A> friend class Council;
00663 private:
00665 static Actor* cast(ActorLink* al);
00667 static const Actor* cast(const ActorLink* al);
00668 public:
00670 virtual Actor* copy(Space& home, bool share) = 0;
00671
00673
00674
00675 GECODE_KERNEL_EXPORT
00676 virtual size_t allocated(void) const;
00678 GECODE_KERNEL_EXPORT
00679 virtual size_t dispose(Space& home);
00681 static void* operator new(size_t s, Space& home);
00683 static void operator delete(void* p, Space& home);
00684 private:
00685 #ifndef __GNUC__
00686
00687 static void operator delete(void* p);
00688 #endif
00689
00690 static void* operator new(size_t s);
00692 #ifdef __GNUC__
00693 public:
00695 GECODE_KERNEL_EXPORT virtual ~Actor(void);
00697 static void operator delete(void* p);
00698 #endif
00699 };
00700
00701
00702
00706 class Home {
00707 protected:
00709 Space& s;
00711 Propagator* p;
00712 public:
00714
00715
00716 Home(Space& s, Propagator* p=NULL);
00718 operator Space&(void);
00720
00721
00722
00723 Home operator ()(Propagator& p);
00725 Propagator* propagator(void) const;
00727
00728
00729
00730 bool failed(void) const;
00732 void fail(void);
00734 void notice(Actor& a, ActorProperty p);
00736 };
00737
00742 class GECODE_VTABLE_EXPORT Propagator : public Actor {
00743 friend class ActorLink;
00744 friend class Space;
00745 template<class VIC> friend class VarImp;
00746 friend class Advisor;
00747 template<class A> friend class Council;
00748 private:
00749 union {
00751 ModEventDelta med;
00753 size_t size;
00755 Gecode::ActorLink* advisors;
00756 } u;
00758 PropInfo& pi;
00760 static Propagator* cast(ActorLink* al);
00762 static const Propagator* cast(const ActorLink* al);
00763 protected:
00765 Propagator(Home home);
00767 Propagator(Space& home, bool share, Propagator& p);
00768
00769 public:
00771
00772
00795 virtual ExecStatus propagate(Space& home, const ModEventDelta& med) = 0;
00797 virtual PropCost cost(const Space& home, const ModEventDelta& med) const = 0;
00833 GECODE_KERNEL_EXPORT
00834 virtual ExecStatus advise(Space& home, Advisor& a, const Delta& d);
00836
00837
00838
00839 double afc(void) const;
00841 };
00842
00843
00851 template<class A>
00852 class Council {
00853 friend class Advisor;
00854 friend class Advisors<A>;
00855 private:
00857 mutable ActorLink* advisors;
00858 public:
00860 Council(void);
00862 Council(Space& home);
00864 bool empty(void) const;
00866 void update(Space& home, bool share, Council<A>& c);
00868 void dispose(Space& home);
00869 };
00870
00871
00876 template<class A>
00877 class Advisors {
00878 private:
00880 ActorLink* a;
00881 public:
00883 Advisors(const Council<A>& c);
00885 bool operator ()(void) const;
00887 void operator ++(void);
00889 A& advisor(void) const;
00890 };
00891
00892
00903 class Advisor : private ActorLink {
00904 template<class VIC> friend class VarImp;
00905 template<class A> friend class Council;
00906 template<class A> friend class Advisors;
00907 private:
00909 bool disposed(void) const;
00911 static Advisor* cast(ActorLink* al);
00913 static const Advisor* cast(const ActorLink* al);
00914 protected:
00916 Propagator& propagator(void) const;
00917 public:
00919 template<class A>
00920 Advisor(Space& home, Propagator& p, Council<A>& c);
00922 Advisor(Space& home, bool share, Advisor& a);
00923
00925
00926
00927 template<class A>
00928 void dispose(Space& home, Council<A>& c);
00930 static void* operator new(size_t s, Space& home);
00932 static void operator delete(void* p, Space& home);
00934 private:
00935 #ifndef __GNUC__
00936
00937 static void operator delete(void* p);
00938 #endif
00939
00940 static void* operator new(size_t s);
00941 };
00942
00943
00944 class Brancher;
00945
00955 class Choice {
00956 friend class Space;
00957 private:
00958 unsigned int _id;
00959 unsigned int _alt;
00960
00962 unsigned int id(void) const;
00963 protected:
00965 Choice(const Brancher& b, const unsigned int a);
00966 public:
00968 unsigned int alternatives(void) const;
00970 GECODE_KERNEL_EXPORT virtual ~Choice(void);
00972 virtual size_t size(void) const = 0;
00974 static void* operator new(size_t);
00976 static void operator delete(void*);
00977 };
00978
00988 class GECODE_VTABLE_EXPORT Brancher : public Actor {
00989 friend class ActorLink;
00990 friend class Space;
00991 friend class Choice;
00992 private:
00994 unsigned int _id;
00996 static Brancher* cast(ActorLink* al);
00998 static const Brancher* cast(const ActorLink* al);
00999 protected:
01001 Brancher(Home home);
01003 Brancher(Space& home, bool share, Brancher& b);
01004 public:
01006
01007
01015 virtual bool status(const Space& home) const = 0;
01023 virtual const Choice* choice(Space& home) = 0;
01030 virtual ExecStatus commit(Space& home, const Choice& c,
01031 unsigned int a) = 0;
01033 unsigned int id(void) const;
01035 };
01036
01044 class LocalObject : public Actor {
01045 friend class ActorLink;
01046 friend class Space;
01047 friend class LocalHandle;
01048 protected:
01050 LocalObject(Home home);
01052 LocalObject(Space& home, bool share, LocalObject& l);
01054 static LocalObject* cast(ActorLink* al);
01056 static const LocalObject* cast(const ActorLink* al);
01057 private:
01059 GECODE_KERNEL_EXPORT void fwdcopy(Space& home, bool share);
01060 public:
01062 LocalObject* fwd(Space& home, bool share);
01063 };
01064
01071 class LocalHandle {
01072 private:
01074 LocalObject* o;
01075 protected:
01077 LocalHandle(void);
01079 LocalHandle(LocalObject* lo);
01081 LocalHandle(const LocalHandle& lh);
01082 public:
01084 LocalHandle& operator =(const LocalHandle& lh);
01086 void update(Space& home, bool share, LocalHandle& lh);
01088 ~LocalHandle(void);
01089 protected:
01091 LocalObject* object(void) const;
01093 void object(LocalObject* n);
01094 };
01095
01096
01101 enum SpaceStatus {
01102 SS_FAILED,
01103 SS_SOLVED,
01104 SS_BRANCH
01105 };
01106
01111 class StatusStatistics {
01112 public:
01114 unsigned long int propagate;
01116 bool wmp;
01118 StatusStatistics(void);
01120 void reset(void);
01122 StatusStatistics operator +(const StatusStatistics& s);
01124 StatusStatistics& operator +=(const StatusStatistics& s);
01125 };
01126
01131 class CloneStatistics {
01132 public:
01134 CloneStatistics(void);
01136 void reset(void);
01138 CloneStatistics operator +(const CloneStatistics& s);
01140 CloneStatistics& operator +=(const CloneStatistics& s);
01141 };
01142
01147 class CommitStatistics {
01148 public:
01150 CommitStatistics(void);
01152 void reset(void);
01154 CommitStatistics operator +(const CommitStatistics& s);
01156 CommitStatistics& operator +=(const CommitStatistics& s);
01157 };
01158
01162 class GECODE_VTABLE_EXPORT Space {
01163 friend class Actor;
01164 friend class Propagator;
01165 friend class Brancher;
01166 friend class Advisor;
01167 template<class VIC> friend class VarImp;
01168 template<class VarImp> friend class VarImpDisposer;
01169 friend class SharedHandle;
01170 friend class LocalObject;
01171 friend class Region;
01172 private:
01174 SharedMemory* sm;
01176 MemoryManager mm;
01178 GlobalPropInfo gpi;
01180 ActorLink pl;
01182 ActorLink bl;
01188 Brancher* b_status;
01200 Brancher* b_commit;
01201 union {
01203 struct {
01216 ActorLink* active;
01218 ActorLink queue[PropCost::AC_MAX+1];
01220 unsigned int branch_id;
01222 unsigned int n_sub;
01223 } p;
01225 struct {
01227 VarImpBase* vars_u[AllVarConf::idx_c];
01229 VarImpBase* vars_noidx;
01231 SharedHandle::Object* shared;
01233 LocalObject* local;
01234 } c;
01235 } pc;
01237 void enqueue(Propagator* p);
01242 #ifdef GECODE_HAS_VAR_DISPOSE
01243
01244 GECODE_KERNEL_EXPORT static VarImpDisposerBase* vd[AllVarConf::idx_d];
01246 VarImpBase* _vars_d[AllVarConf::idx_d];
01248 template<class VIC> VarImpBase* vars_d(void) const;
01250 template<class VIC> void vars_d(VarImpBase* x);
01251 #endif
01252
01253 void update(ActorLink** sub);
01255
01257 Actor** d_fst;
01259 Actor** d_cur;
01261 Actor** d_lst;
01263 GECODE_KERNEL_EXPORT void d_resize(void);
01264
01272 unsigned int n_wmp;
01273
01275 GECODE_KERNEL_EXPORT static StatusStatistics unused_status;
01277 GECODE_KERNEL_EXPORT static CloneStatistics unused_clone;
01279 GECODE_KERNEL_EXPORT static CommitStatistics unused_commit;
01281 GECODE_KERNEL_EXPORT static unsigned long int unused_uli;
01283 GECODE_KERNEL_EXPORT static bool unused_b;
01284
01299 GECODE_KERNEL_EXPORT Space* _clone(bool share=true);
01300
01333 GECODE_KERNEL_EXPORT
01334 void _commit(const Choice& c, unsigned int a);
01335
01336 public:
01341 GECODE_KERNEL_EXPORT Space(void);
01346 GECODE_KERNEL_EXPORT virtual ~Space(void);
01357 GECODE_KERNEL_EXPORT Space(bool share, Space& s);
01364 virtual Space* copy(bool share) = 0;
01376 GECODE_KERNEL_EXPORT virtual void constrain(const Space& best);
01381 static void* operator new(size_t);
01386 static void operator delete(void*);
01387
01388
01389
01390
01391
01392
01393
01405 GECODE_KERNEL_EXPORT
01406 SpaceStatus status(StatusStatistics& stat=unused_status);
01407
01439 GECODE_KERNEL_EXPORT
01440 const Choice* choice(void);
01441
01459 Space* clone(bool share=true, CloneStatistics& stat=unused_clone) const;
01460
01495 void commit(const Choice& c, unsigned int a,
01496 CommitStatistics& stat=unused_commit);
01497
01505 void notice(Actor& a, ActorProperty p);
01513 void ignore(Actor& a, ActorProperty p);
01514
01515
01526 ExecStatus ES_SUBSUMED(Propagator& p);
01541 ExecStatus ES_SUBSUMED_DISPOSED(Propagator& p, size_t s);
01552 ExecStatus ES_FIX_PARTIAL(Propagator& p, const ModEventDelta& med);
01563 ExecStatus ES_NOFIX_PARTIAL(Propagator& p, const ModEventDelta& med);
01564
01575 template<class A>
01576 ExecStatus ES_FIX_DISPOSE(Council<A>& c, A& a);
01587 template<class A>
01588 ExecStatus ES_NOFIX_DISPOSE(Council<A>& c, A& a);
01600 template<class A>
01601 ExecStatus ES_NOFIX_DISPOSE_FORCE(Council<A>& c, A& a);
01602
01610 void fail(void);
01619 bool failed(void) const;
01624 bool stable(void) const;
01631 GECODE_KERNEL_EXPORT unsigned int propagators(void) const;
01638 GECODE_KERNEL_EXPORT unsigned int branchers(void) const;
01639
01641
01642
01643 Home operator ()(Propagator& p);
01645
01657 template<class T>
01658 T* alloc(long unsigned int n);
01665 template<class T>
01666 T* alloc(long int n);
01673 template<class T>
01674 T* alloc(unsigned int n);
01681 template<class T>
01682 T* alloc(int n);
01692 template<class T>
01693 void free(T* b, long unsigned int n);
01703 template<class T>
01704 void free(T* b, long int n);
01714 template<class T>
01715 void free(T* b, unsigned int n);
01725 template<class T>
01726 void free(T* b, int n);
01738 template<class T>
01739 T* realloc(T* b, long unsigned int n, long unsigned int m);
01751 template<class T>
01752 T* realloc(T* b, long int n, long int m);
01764 template<class T>
01765 T* realloc(T* b, unsigned int n, unsigned int m);
01777 template<class T>
01778 T* realloc(T* b, int n, int m);
01786 template<class T>
01787 T** realloc(T** b, long unsigned int n, long unsigned int m);
01795 template<class T>
01796 T** realloc(T** b, long int n, long int m);
01804 template<class T>
01805 T** realloc(T** b, unsigned int n, unsigned int m);
01813 template<class T>
01814 T** realloc(T** b, int n, int m);
01816 void* ralloc(size_t s);
01818 void rfree(void* p, size_t s);
01820 void* rrealloc(void* b, size_t n, size_t m);
01822 template<size_t> void* fl_alloc(void);
01828 template<size_t> void fl_dispose(FreeList* f, FreeList* l);
01835 size_t allocated(void) const;
01845 GECODE_KERNEL_EXPORT void flush(void);
01847
01848
01849
01852 template<class T>
01853 T& construct(void);
01859 template<class T, typename A1>
01860 T& construct(A1 const& a1);
01866 template<class T, typename A1, typename A2>
01867 T& construct(A1 const& a1, A2 const& a2);
01873 template<class T, typename A1, typename A2, typename A3>
01874 T& construct(A1 const& a1, A2 const& a2, A3 const& a3);
01880 template<class T, typename A1, typename A2, typename A3, typename A4>
01881 T& construct(A1 const& a1, A2 const& a2, A3 const& a3, A4 const& a4);
01887 template<class T, typename A1, typename A2, typename A3, typename A4, typename A5>
01888 T& construct(A1 const& a1, A2 const& a2, A3 const& a3, A4 const& a4, A5 const& a5);
01890
01896 class Propagators {
01897 private:
01899 const Space& home;
01901 const ActorLink* q;
01903 const ActorLink* c;
01905 const ActorLink* e;
01906 public:
01908 Propagators(const Space& home);
01910 bool operator ()(void) const;
01912 void operator ++(void);
01914 const Propagator& propagator(void) const;
01915 };
01916
01922 class Branchers {
01923 private:
01925 const ActorLink* c;
01927 const ActorLink* e;
01928 public:
01930 Branchers(const Space& home);
01932 bool operator ()(void) const;
01934 void operator ++(void);
01936 const Brancher& brancher(void) const;
01937 };
01938 };
01939
01940
01941
01942
01943
01944
01945
01946
01947
01948
01949 forceinline void*
01950 SharedHandle::Object::operator new(size_t s) {
01951 return heap.ralloc(s);
01952 }
01953 forceinline void
01954 SharedHandle::Object::operator delete(void* p) {
01955 heap.rfree(p);
01956 }
01957
01958 forceinline void*
01959 Space::operator new(size_t s) {
01960 return heap.ralloc(s);
01961 }
01962 forceinline void
01963 Space::operator delete(void* p) {
01964 heap.rfree(p);
01965 }
01966
01967 forceinline void
01968 Choice::operator delete(void* p) {
01969 heap.rfree(p);
01970 }
01971 forceinline void*
01972 Choice::operator new(size_t s) {
01973 return heap.ralloc(s);
01974 }
01975
01976
01977 forceinline void*
01978 Space::ralloc(size_t s) {
01979 return mm.alloc(sm,s);
01980 }
01981 forceinline void
01982 Space::rfree(void* p, size_t s) {
01983 return mm.reuse(p,s);
01984 }
01985 forceinline void*
01986 Space::rrealloc(void* _b, size_t n, size_t m) {
01987 char* b = static_cast<char*>(_b);
01988 if (n < m) {
01989 char* p = static_cast<char*>(ralloc(m));
01990 memcpy(p,b,n);
01991 rfree(b,n);
01992 return p;
01993 } else {
01994 rfree(b+m,m-n);
01995 return b;
01996 }
01997 }
01998
01999 template<size_t s>
02000 forceinline void*
02001 Space::fl_alloc(void) {
02002 return mm.template fl_alloc<s>(sm);
02003 }
02004 template<size_t s>
02005 forceinline void
02006 Space::fl_dispose(FreeList* f, FreeList* l) {
02007 mm.template fl_dispose<s>(f,l);
02008 }
02009
02010 forceinline size_t
02011 Space::allocated(void) const {
02012 size_t s = mm.allocated();
02013 for (Actor** a = d_fst; a < d_cur; a++)
02014 s += (*a)->allocated();
02015 return s;
02016 }
02017
02018
02019
02020
02021
02022 template<class T>
02023 forceinline T*
02024 Space::alloc(long unsigned int n) {
02025 T* p = static_cast<T*>(ralloc(sizeof(T)*n));
02026 for (long unsigned int i=n; i--; )
02027 (void) new (p+i) T();
02028 return p;
02029 }
02030 template<class T>
02031 forceinline T*
02032 Space::alloc(long int n) {
02033 assert(n >= 0);
02034 return alloc<T>(static_cast<long unsigned int>(n));
02035 }
02036 template<class T>
02037 forceinline T*
02038 Space::alloc(unsigned int n) {
02039 return alloc<T>(static_cast<long unsigned int>(n));
02040 }
02041 template<class T>
02042 forceinline T*
02043 Space::alloc(int n) {
02044 assert(n >= 0);
02045 return alloc<T>(static_cast<long unsigned int>(n));
02046 }
02047
02048 template<class T>
02049 forceinline void
02050 Space::free(T* b, long unsigned int n) {
02051 for (long unsigned int i=n; i--; )
02052 b[i].~T();
02053 rfree(b,n*sizeof(T));
02054 }
02055 template<class T>
02056 forceinline void
02057 Space::free(T* b, long int n) {
02058 assert(n >= 0);
02059 free<T>(b,static_cast<long unsigned int>(n));
02060 }
02061 template<class T>
02062 forceinline void
02063 Space::free(T* b, unsigned int n) {
02064 free<T>(b,static_cast<long unsigned int>(n));
02065 }
02066 template<class T>
02067 forceinline void
02068 Space::free(T* b, int n) {
02069 assert(n >= 0);
02070 free<T>(b,static_cast<long unsigned int>(n));
02071 }
02072
02073 template<class T>
02074 forceinline T*
02075 Space::realloc(T* b, long unsigned int n, long unsigned int m) {
02076 if (n < m) {
02077 T* p = static_cast<T*>(ralloc(sizeof(T)*m));
02078 for (long unsigned int i=n; i--; )
02079 (void) new (p+i) T(b[i]);
02080 for (long unsigned int i=n; i<m; i++)
02081 (void) new (p+i) T();
02082 free<T>(b,n);
02083 return p;
02084 } else {
02085 free<T>(b+m,m-n);
02086 return b;
02087 }
02088 }
02089 template<class T>
02090 forceinline T*
02091 Space::realloc(T* b, long int n, long int m) {
02092 assert((n >= 0) && (m >= 0));
02093 return realloc<T>(b,static_cast<long unsigned int>(n),
02094 static_cast<long unsigned int>(m));
02095 }
02096 template<class T>
02097 forceinline T*
02098 Space::realloc(T* b, unsigned int n, unsigned int m) {
02099 return realloc<T>(b,static_cast<long unsigned int>(n),
02100 static_cast<long unsigned int>(m));
02101 }
02102 template<class T>
02103 forceinline T*
02104 Space::realloc(T* b, int n, int m) {
02105 assert((n >= 0) && (m >= 0));
02106 return realloc<T>(b,static_cast<long unsigned int>(n),
02107 static_cast<long unsigned int>(m));
02108 }
02109
02110 #define GECODE_KERNEL_REALLOC(T) \
02111 template<> \
02112 forceinline T* \
02113 Space::realloc<T>(T* b, long unsigned int n, long unsigned int m) { \
02114 return static_cast<T*>(rrealloc(b,n*sizeof(T),m*sizeof(T))); \
02115 } \
02116 template<> \
02117 forceinline T* \
02118 Space::realloc<T>(T* b, long int n, long int m) { \
02119 assert((n >= 0) && (m >= 0)); \
02120 return realloc<T>(b,static_cast<long unsigned int>(n), \
02121 static_cast<long unsigned int>(m)); \
02122 } \
02123 template<> \
02124 forceinline T* \
02125 Space::realloc<T>(T* b, unsigned int n, unsigned int m) { \
02126 return realloc<T>(b,static_cast<long unsigned int>(n), \
02127 static_cast<long unsigned int>(m)); \
02128 } \
02129 template<> \
02130 forceinline T* \
02131 Space::realloc<T>(T* b, int n, int m) { \
02132 assert((n >= 0) && (m >= 0)); \
02133 return realloc<T>(b,static_cast<long unsigned int>(n), \
02134 static_cast<long unsigned int>(m)); \
02135 }
02136
02137 GECODE_KERNEL_REALLOC(bool)
02138 GECODE_KERNEL_REALLOC(signed char)
02139 GECODE_KERNEL_REALLOC(unsigned char)
02140 GECODE_KERNEL_REALLOC(signed short int)
02141 GECODE_KERNEL_REALLOC(unsigned short int)
02142 GECODE_KERNEL_REALLOC(signed int)
02143 GECODE_KERNEL_REALLOC(unsigned int)
02144 GECODE_KERNEL_REALLOC(signed long int)
02145 GECODE_KERNEL_REALLOC(unsigned long int)
02146 GECODE_KERNEL_REALLOC(float)
02147 GECODE_KERNEL_REALLOC(double)
02148
02149 #undef GECODE_KERNEL_REALLOC
02150
02151 template<class T>
02152 forceinline T**
02153 Space::realloc(T** b, long unsigned int n, long unsigned int m) {
02154 return static_cast<T**>(rrealloc(b,n*sizeof(T),m*sizeof(T*)));
02155 }
02156 template<class T>
02157 forceinline T**
02158 Space::realloc(T** b, long int n, long int m) {
02159 assert((n >= 0) && (m >= 0));
02160 return realloc<T*>(b,static_cast<long unsigned int>(n),
02161 static_cast<long unsigned int>(m));
02162 }
02163 template<class T>
02164 forceinline T**
02165 Space::realloc(T** b, unsigned int n, unsigned int m) {
02166 return realloc<T*>(b,static_cast<long unsigned int>(n),
02167 static_cast<long unsigned int>(m));
02168 }
02169 template<class T>
02170 forceinline T**
02171 Space::realloc(T** b, int n, int m) {
02172 assert((n >= 0) && (m >= 0));
02173 return realloc<T*>(b,static_cast<long unsigned int>(n),
02174 static_cast<long unsigned int>(m));
02175 }
02176
02177
02178 #ifdef GECODE_HAS_VAR_DISPOSE
02179 template<class VIC>
02180 forceinline VarImpBase*
02181 Space::vars_d(void) const {
02182 return _vars_d[VIC::idx_d];
02183 }
02184 template<class VIC>
02185 forceinline void
02186 Space::vars_d(VarImpBase* x) {
02187 _vars_d[VIC::idx_d] = x;
02188 }
02189 #endif
02190
02191
02192 forceinline void
02193 Actor::operator delete(void*) {}
02194 forceinline void
02195 Actor::operator delete(void*, Space&) {}
02196 forceinline void*
02197 Actor::operator new(size_t s, Space& home) {
02198 return home.ralloc(s);
02199 }
02200
02201 template<class VIC>
02202 forceinline void
02203 VarImp<VIC>::operator delete(void*) {}
02204 template<class VIC>
02205 forceinline void
02206 VarImp<VIC>::operator delete(void*, Space&) {}
02207 template<class VIC>
02208 forceinline void*
02209 VarImp<VIC>::operator new(size_t s, Space& home) {
02210 return home.ralloc(s);
02211 }
02212
02213 #ifndef __GNUC__
02214 forceinline void
02215 Advisor::operator delete(void*) {}
02216 #endif
02217 forceinline void
02218 Advisor::operator delete(void*, Space&) {}
02219 forceinline void*
02220 Advisor::operator new(size_t s, Space& home) {
02221 return home.ralloc(s);
02222 }
02223
02224
02225
02226
02227
02228 forceinline
02229 SharedHandle::Object::Object(void)
02230 : next(NULL), fwd(NULL), use_cnt(0) {}
02231 forceinline
02232 SharedHandle::Object::~Object(void) {
02233 assert(use_cnt == 0);
02234 }
02235
02236 forceinline SharedHandle::Object*
02237 SharedHandle::object(void) const {
02238 return o;
02239 }
02240 forceinline void
02241 SharedHandle::subscribe(void) {
02242 if (o != NULL) o->use_cnt++;
02243 }
02244 forceinline void
02245 SharedHandle::cancel(void) {
02246 if ((o != NULL) && (--o->use_cnt == 0))
02247 delete o;
02248 o=NULL;
02249 }
02250 forceinline void
02251 SharedHandle::object(SharedHandle::Object* n) {
02252 if (n != o) {
02253 cancel(); o=n; subscribe();
02254 }
02255 }
02256 forceinline
02257 SharedHandle::SharedHandle(void) : o(NULL) {}
02258 forceinline
02259 SharedHandle::SharedHandle(SharedHandle::Object* so) : o(so) {
02260 subscribe();
02261 }
02262 forceinline
02263 SharedHandle::SharedHandle(const SharedHandle& sh) : o(sh.o) {
02264 subscribe();
02265 }
02266 forceinline SharedHandle&
02267 SharedHandle::operator =(const SharedHandle& sh) {
02268 if (&sh != this) {
02269 cancel(); o=sh.o; subscribe();
02270 }
02271 return *this;
02272 }
02273 forceinline void
02274 SharedHandle::update(Space& home, bool share, SharedHandle& sh) {
02275 if (sh.o == NULL) {
02276 o=NULL; return;
02277 } else if (share) {
02278 o=sh.o;
02279 } else if (sh.o->fwd != NULL) {
02280 o=sh.o->fwd;
02281 } else {
02282 o = sh.o->copy();
02283 sh.o->fwd = o;
02284 sh.o->next = home.pc.c.shared;
02285 home.pc.c.shared = sh.o;
02286 }
02287 subscribe();
02288 }
02289 forceinline
02290 SharedHandle::~SharedHandle(void) {
02291 cancel();
02292 }
02293
02294
02295
02296
02297
02298
02299
02300 forceinline ActorLink*
02301 ActorLink::prev(void) const {
02302 return _prev;
02303 }
02304
02305 forceinline ActorLink*
02306 ActorLink::next(void) const {
02307 return _next;
02308 }
02309
02310 forceinline ActorLink**
02311 ActorLink::next_ref(void) {
02312 return &_next;
02313 }
02314
02315 forceinline void
02316 ActorLink::prev(ActorLink* al) {
02317 _prev = al;
02318 }
02319
02320 forceinline void
02321 ActorLink::next(ActorLink* al) {
02322 _next = al;
02323 }
02324
02325 forceinline void
02326 ActorLink::unlink(void) {
02327 ActorLink* p = _prev; ActorLink* n = _next;
02328 p->_next = n; n->_prev = p;
02329 }
02330
02331 forceinline void
02332 ActorLink::init(void) {
02333 _next = this; _prev =this;
02334 }
02335
02336 forceinline void
02337 ActorLink::head(ActorLink* a) {
02338
02339 ActorLink* n = _next;
02340 this->_next = a; a->_prev = this;
02341 a->_next = n; n->_prev = a;
02342 }
02343
02344 forceinline void
02345 ActorLink::tail(ActorLink* a) {
02346
02347 ActorLink* p = _prev;
02348 a->_next = this; this->_prev = a;
02349 p->_next = a; a->_prev = p;
02350 }
02351
02352 forceinline bool
02353 ActorLink::empty(void) const {
02354 return _next == this;
02355 }
02356
02357 template<class T>
02358 forceinline ActorLink*
02359 ActorLink::cast(T* a) {
02360
02361 GECODE_NOT_NULL(a);
02362 ActorLink& t = *a;
02363 return static_cast<ActorLink*>(&t);
02364 }
02365
02366 template<class T>
02367 forceinline const ActorLink*
02368 ActorLink::cast(const T* a) {
02369
02370 GECODE_NOT_NULL(a);
02371 const ActorLink& t = *a;
02372 return static_cast<const ActorLink*>(&t);
02373 }
02374
02375
02376
02377
02378
02379
02380 forceinline Actor*
02381 Actor::cast(ActorLink* al) {
02382
02383 GECODE_NOT_NULL(al);
02384 ActorLink& t = *al;
02385 return static_cast<Actor*>(&t);
02386 }
02387
02388 forceinline const Actor*
02389 Actor::cast(const ActorLink* al) {
02390
02391 GECODE_NOT_NULL(al);
02392 const ActorLink& t = *al;
02393 return static_cast<const Actor*>(&t);
02394 }
02395
02396 forceinline void
02397 Space::notice(Actor& a, ActorProperty p) {
02398 if (p & AP_DISPOSE) {
02399 if (d_cur == d_lst)
02400 d_resize();
02401 *(d_cur++) = &a;
02402 }
02403 if (p & AP_WEAKLY) {
02404 if (n_wmp == 0)
02405 n_wmp = 2;
02406 else
02407 n_wmp++;
02408 }
02409 }
02410
02411 forceinline void
02412 Home::notice(Actor& a, ActorProperty p) {
02413 s.notice(a,p);
02414 }
02415
02416 forceinline void
02417 Space::ignore(Actor& a, ActorProperty p) {
02418 if (p & AP_DISPOSE) {
02419
02420
02421 Actor** f = d_fst;
02422 if (f != NULL) {
02423 while (&a != *f)
02424 f++;
02425 *f = *(--d_cur);
02426 }
02427 }
02428 if (p & AP_WEAKLY) {
02429 assert(n_wmp > 1);
02430 n_wmp--;
02431 }
02432 }
02433
02434 forceinline Space*
02435 Space::clone(bool share, CloneStatistics&) const {
02436
02437
02438
02439 return const_cast<Space*>(this)->_clone(share);
02440 }
02441
02442 forceinline void
02443 Space::commit(const Choice& c, unsigned int a, CommitStatistics&) {
02444 _commit(c,a);
02445 }
02446
02447 forceinline size_t
02448 Actor::dispose(Space&) {
02449 return sizeof(*this);
02450 }
02451
02452
02453
02454
02455
02456
02457 forceinline
02458 Home::Home(Space& s0, Propagator* p0) : s(s0), p(p0) {}
02459 forceinline
02460 Home::operator Space&(void) {
02461 return s;
02462 }
02463 forceinline Home
02464 Home::operator ()(Propagator& p) {
02465 return Home(s,&p);
02466 }
02467 forceinline Home
02468 Space::operator ()(Propagator& p) {
02469 return Home(*this,&p);
02470 }
02471 forceinline Propagator*
02472 Home::propagator(void) const {
02473 return p;
02474 }
02475
02476
02477
02478
02479
02480 forceinline Propagator*
02481 Propagator::cast(ActorLink* al) {
02482
02483 GECODE_NOT_NULL(al);
02484 ActorLink& t = *al;
02485 return static_cast<Propagator*>(&t);
02486 }
02487
02488 forceinline const Propagator*
02489 Propagator::cast(const ActorLink* al) {
02490
02491 GECODE_NOT_NULL(al);
02492 const ActorLink& t = *al;
02493 return static_cast<const Propagator*>(&t);
02494 }
02495
02496 forceinline
02497 Propagator::Propagator(Home home)
02498 : pi((home.propagator() != NULL) ?
02499
02500 home.propagator()->pi :
02501
02502 static_cast<Space&>(home).gpi.allocate()) {
02503 u.advisors = NULL;
02504 assert((u.med == 0) && (u.size == 0));
02505 static_cast<Space&>(home).pl.head(this);
02506 }
02507
02508 forceinline
02509 Propagator::Propagator(Space&, bool, Propagator& p)
02510 : pi(p.pi) {
02511 u.advisors = NULL;
02512 assert((u.med == 0) && (u.size == 0));
02513
02514 p.prev(this);
02515 }
02516
02517 forceinline double
02518 Propagator::afc(void) const {
02519 return pi.afc();
02520 }
02521
02522 forceinline ExecStatus
02523 Space::ES_SUBSUMED_DISPOSED(Propagator& p, size_t s) {
02524 p.u.size = s;
02525 return __ES_SUBSUMED;
02526 }
02527
02528 forceinline ExecStatus
02529 Space::ES_SUBSUMED(Propagator& p) {
02530 p.u.size = p.dispose(*this);
02531 return __ES_SUBSUMED;
02532 }
02533
02534 forceinline ExecStatus
02535 Space::ES_FIX_PARTIAL(Propagator& p, const ModEventDelta& med) {
02536 p.u.med = med;
02537 assert(p.u.med != 0);
02538 return __ES_PARTIAL;
02539 }
02540
02541 forceinline ExecStatus
02542 Space::ES_NOFIX_PARTIAL(Propagator& p, const ModEventDelta& med) {
02543 p.u.med = AllVarConf::med_combine(p.u.med,med);
02544 assert(p.u.med != 0);
02545 return __ES_PARTIAL;
02546 }
02547
02548
02549
02550
02551
02552
02553
02554 forceinline Brancher*
02555 Brancher::cast(ActorLink* al) {
02556
02557 GECODE_NOT_NULL(al);
02558 ActorLink& t = *al;
02559 return static_cast<Brancher*>(&t);
02560 }
02561
02562 forceinline const Brancher*
02563 Brancher::cast(const ActorLink* al) {
02564
02565 GECODE_NOT_NULL(al);
02566 const ActorLink& t = *al;
02567 return static_cast<const Brancher*>(&t);
02568 }
02569
02570 forceinline
02571 Brancher::Brancher(Home home) :
02572 _id(static_cast<Space&>(home).pc.p.branch_id++) {
02573 if (static_cast<Space&>(home).pc.p.branch_id == 0U)
02574 throw TooManyBranchers("Brancher::Brancher");
02575
02576 if (static_cast<Space&>(home).b_status == &static_cast<Space&>(home).bl) {
02577 static_cast<Space&>(home).b_status = this;
02578 if (static_cast<Space&>(home).b_commit == &static_cast<Space&>(home).bl)
02579 static_cast<Space&>(home).b_commit = this;
02580 }
02581 static_cast<Space&>(home).bl.tail(this);
02582 }
02583
02584 forceinline
02585 Brancher::Brancher(Space&, bool, Brancher& b)
02586 : _id(b._id) {
02587
02588 b.prev(this);
02589 }
02590
02591 forceinline unsigned int
02592 Brancher::id(void) const {
02593 return _id;
02594 }
02595
02596
02597
02598
02599
02600
02601 forceinline LocalObject*
02602 LocalObject::cast(ActorLink* al) {
02603
02604 GECODE_NOT_NULL(al);
02605 ActorLink& t = *al;
02606 return static_cast<LocalObject*>(&t);
02607 }
02608
02609 forceinline const LocalObject*
02610 LocalObject::cast(const ActorLink* al) {
02611
02612 GECODE_NOT_NULL(al);
02613 const ActorLink& t = *al;
02614 return static_cast<const LocalObject*>(&t);
02615 }
02616
02617 forceinline
02618 LocalObject::LocalObject(Home) {
02619 ActorLink::cast(this)->prev(NULL);
02620 }
02621
02622 forceinline
02623 LocalObject::LocalObject(Space&,bool,LocalObject&) {
02624 ActorLink::cast(this)->prev(NULL);
02625 }
02626
02627 forceinline LocalObject*
02628 LocalObject::fwd(Space& home, bool share) {
02629 if (prev() == NULL)
02630 fwdcopy(home,share);
02631 return LocalObject::cast(prev());
02632 }
02633
02634 forceinline
02635 LocalHandle::LocalHandle(void) : o(NULL) {}
02636 forceinline
02637 LocalHandle::LocalHandle(LocalObject* lo) : o(lo) {}
02638 forceinline
02639 LocalHandle::LocalHandle(const LocalHandle& lh) : o(lh.o) {}
02640 forceinline LocalHandle&
02641 LocalHandle::operator =(const LocalHandle& lh) {
02642 o = lh.o;
02643 return *this;
02644 }
02645 forceinline
02646 LocalHandle::~LocalHandle(void) {}
02647 forceinline LocalObject*
02648 LocalHandle::object(void) const { return o; }
02649 forceinline void
02650 LocalHandle::object(LocalObject* n) { o = n; }
02651 forceinline void
02652 LocalHandle::update(Space& home, bool share, LocalHandle& lh) {
02653 object(lh.object()->fwd(home,share));
02654 }
02655
02656
02657
02658
02659
02660
02661 forceinline
02662 Choice::Choice(const Brancher& b, const unsigned int a)
02663 : _id(b.id()), _alt(a) {}
02664
02665 forceinline unsigned int
02666 Choice::alternatives(void) const {
02667 return _alt;
02668 }
02669
02670 forceinline unsigned int
02671 Choice::id(void) const {
02672 return _id;
02673 }
02674
02675 forceinline
02676 Choice::~Choice(void) {}
02677
02678
02679
02680
02681
02682
02683
02684 template<class A>
02685 forceinline
02686 Advisor::Advisor(Space&, Propagator& p, Council<A>& c) {
02687
02688 ActorLink::prev(&p);
02689
02690 ActorLink::next(c.advisors); c.advisors = static_cast<A*>(this);
02691 }
02692
02693 forceinline
02694 Advisor::Advisor(Space&, bool, Advisor&) {}
02695
02696 forceinline bool
02697 Advisor::disposed(void) const {
02698 return prev() == NULL;
02699 }
02700
02701 forceinline Advisor*
02702 Advisor::cast(ActorLink* al) {
02703 return static_cast<Advisor*>(al);
02704 }
02705
02706 forceinline const Advisor*
02707 Advisor::cast(const ActorLink* al) {
02708 return static_cast<const Advisor*>(al);
02709 }
02710
02711 forceinline Propagator&
02712 Advisor::propagator(void) const {
02713 assert(!disposed());
02714 return *Propagator::cast(ActorLink::prev());
02715 }
02716
02717 template<class A>
02718 forceinline void
02719 Advisor::dispose(Space&,Council<A>&) {
02720 assert(!disposed());
02721 ActorLink::prev(NULL);
02722
02723 Advisor* n = Advisor::cast(next());
02724 if ((n != NULL) && n->disposed())
02725 next(n->next());
02726 }
02727
02728 template<class A>
02729 forceinline ExecStatus
02730 Space::ES_FIX_DISPOSE(Council<A>& c, A& a) {
02731 a.dispose(*this,c);
02732 return ES_FIX;
02733 }
02734
02735 template<class A>
02736 forceinline ExecStatus
02737 Space::ES_NOFIX_DISPOSE(Council<A>& c, A& a) {
02738 a.dispose(*this,c);
02739 return ES_NOFIX;
02740 }
02741
02742 template<class A>
02743 forceinline ExecStatus
02744 Space::ES_NOFIX_DISPOSE_FORCE(Council<A>& c, A& a) {
02745 a.dispose(*this,c);
02746 return ES_NOFIX_FORCE;
02747 }
02748
02749
02750
02751
02752
02753
02754
02755 template<class A>
02756 forceinline
02757 Council<A>::Council(void) {}
02758
02759 template<class A>
02760 forceinline
02761 Council<A>::Council(Space&)
02762 : advisors(NULL) {}
02763
02764 template<class A>
02765 forceinline bool
02766 Council<A>::empty(void) const {
02767 ActorLink* a = advisors;
02768 while ((a != NULL) && static_cast<A*>(a)->disposed())
02769 a = a->next();
02770 advisors = a;
02771 return a == NULL;
02772 }
02773
02774 template<class A>
02775 forceinline void
02776 Council<A>::update(Space& home, bool share, Council<A>& c) {
02777
02778 {
02779 ActorLink* a = c.advisors;
02780 while ((a != NULL) && static_cast<A*>(a)->disposed())
02781 a = a->next();
02782 c.advisors = a;
02783 }
02784
02785 if (c.advisors != NULL) {
02786
02787 Propagator* p_f = &static_cast<A*>(c.advisors)->propagator();
02788
02789 Propagator* p_t = Propagator::cast(p_f->prev());
02790
02791 ActorLink** a_f = &c.advisors;
02792
02793 A* a_t = NULL;
02794 while (*a_f != NULL) {
02795 if (static_cast<A*>(*a_f)->disposed()) {
02796 *a_f = (*a_f)->next();
02797 } else {
02798
02799 A* a = new (home) A(home,share,*static_cast<A*>(*a_f));
02800
02801 a->prev(p_t);
02802
02803 (*a_f)->prev(a);
02804
02805 a->next(a_t);
02806 a_t = a;
02807 a_f = (*a_f)->next_ref();
02808 }
02809 }
02810 advisors = a_t;
02811
02812 assert(p_f->u.advisors == NULL);
02813 p_f->u.advisors = c.advisors;
02814 } else {
02815 advisors = NULL;
02816 }
02817 }
02818
02819 template<class A>
02820 forceinline void
02821 Council<A>::dispose(Space& home) {
02822 ActorLink* a = advisors;
02823 while (a != NULL) {
02824 if (!static_cast<A*>(a)->disposed())
02825 static_cast<A*>(a)->dispose(home,*this);
02826 a = a->next();
02827 }
02828 }
02829
02830
02831
02832
02833
02834
02835
02836 template<class A>
02837 forceinline
02838 Advisors<A>::Advisors(const Council<A>& c)
02839 : a(c.advisors) {
02840 while ((a != NULL) && static_cast<A*>(a)->disposed())
02841 a = a->next();
02842 }
02843
02844 template<class A>
02845 forceinline bool
02846 Advisors<A>::operator ()(void) const {
02847 return a != NULL;
02848 }
02849
02850 template<class A>
02851 forceinline void
02852 Advisors<A>::operator ++(void) {
02853 do {
02854 a = a->next();
02855 } while ((a != NULL) && static_cast<A*>(a)->disposed());
02856 }
02857
02858 template<class A>
02859 forceinline A&
02860 Advisors<A>::advisor(void) const {
02861 return *static_cast<A*>(a);
02862 }
02863
02864
02865
02866
02867
02868
02869
02870 forceinline void
02871 Space::enqueue(Propagator* p) {
02872 ActorLink::cast(p)->unlink();
02873 ActorLink* c = &pc.p.queue[p->cost(*this,p->u.med).ac];
02874 c->tail(ActorLink::cast(p));
02875 if (c > pc.p.active)
02876 pc.p.active = c;
02877 }
02878
02879 forceinline void
02880 Space::fail(void) {
02881
02882
02883
02884
02885
02886 pc.p.active = &pc.p.queue[PropCost::AC_MAX+2];
02887 }
02888 forceinline void
02889 Home::fail(void) {
02890 s.fail();
02891 }
02892
02893 forceinline bool
02894 Space::failed(void) const {
02895 return pc.p.active > &pc.p.queue[PropCost::AC_MAX+1];
02896 }
02897 forceinline bool
02898 Home::failed(void) const {
02899 return s.failed();
02900 }
02901
02902 forceinline bool
02903 Space::stable(void) const {
02904 return ((pc.p.active < &pc.p.queue[0]) ||
02905 (pc.p.active > &pc.p.queue[PropCost::AC_MAX+1]));
02906 }
02907
02908
02909
02910
02911
02912
02913
02914 template<class VIC>
02915 forceinline ActorLink**
02916 VarImp<VIC>::actor(PropCond pc) {
02917 assert((pc >= 0) && (pc < pc_max+2));
02918 return (pc == 0) ? base : base+u.idx[pc-1];
02919 }
02920
02921 template<class VIC>
02922 forceinline ActorLink**
02923 VarImp<VIC>::actorNonZero(PropCond pc) {
02924 assert((pc > 0) && (pc < pc_max+2));
02925 return base+u.idx[pc-1];
02926 }
02927
02928 template<class VIC>
02929 forceinline unsigned int&
02930 VarImp<VIC>::idx(PropCond pc) {
02931 assert((pc > 0) && (pc < pc_max+2));
02932 return u.idx[pc-1];
02933 }
02934
02935 template<class VIC>
02936 forceinline unsigned int
02937 VarImp<VIC>::idx(PropCond pc) const {
02938 assert((pc > 0) && (pc < pc_max+2));
02939 return u.idx[pc-1];
02940 }
02941
02942 template<class VIC>
02943 forceinline
02944 VarImp<VIC>::VarImp(Space&) {
02945 base = NULL; entries = 0;
02946 for (PropCond pc=1; pc<pc_max+2; pc++)
02947 idx(pc) = 0;
02948 free_and_bits = 0;
02949 }
02950
02951 template<class VIC>
02952 forceinline
02953 VarImp<VIC>::VarImp(void) {
02954 base = NULL; entries = 0;
02955 for (PropCond pc=1; pc<pc_max+2; pc++)
02956 idx(pc) = 0;
02957 free_and_bits = 0;
02958 }
02959
02960 template<class VIC>
02961 forceinline unsigned int
02962 VarImp<VIC>::degree(void) const {
02963 assert(!copied());
02964 return entries;
02965 }
02966
02967 template<class VIC>
02968 forceinline double
02969 VarImp<VIC>::afc(void) const {
02970 if (degree() == 0)
02971 return 0.0;
02972 double d = degree();
02973
02974 {
02975 ActorLink** a = const_cast<VarImp<VIC>*>(this)->actor(0);
02976 ActorLink** e = const_cast<VarImp<VIC>*>(this)->actorNonZero(pc_max+1);
02977 while (a < e) {
02978 d += Propagator::cast(*a)->afc(); a++;
02979 }
02980 }
02981
02982 {
02983 ActorLink** a = const_cast<VarImp<VIC>*>(this)->actorNonZero(pc_max+1);
02984 ActorLink** e = const_cast<VarImp<VIC>*>(this)->base+entries;
02985 while (a < e) {
02986 d += Advisor::cast(*a)->propagator().afc(); a++;
02987 }
02988 }
02989 return d;
02990 }
02991
02992 template<class VIC>
02993 forceinline ModEvent
02994 VarImp<VIC>::modevent(const Delta& d) {
02995 return d.me;
02996 }
02997
02998 template<class VIC>
02999 forceinline unsigned int
03000 VarImp<VIC>::bits(void) const {
03001 return free_and_bits;
03002 }
03003
03004 template<class VIC>
03005 forceinline unsigned int&
03006 VarImp<VIC>::bits(void) {
03007 return free_and_bits;
03008 }
03009
03010 #ifdef GECODE_HAS_VAR_DISPOSE
03011 template<class VIC>
03012 forceinline VarImp<VIC>*
03013 VarImp<VIC>::vars_d(Space& home) {
03014 return static_cast<VarImp<VIC>*>(home.vars_d<VIC>());
03015 }
03016
03017 template<class VIC>
03018 forceinline void
03019 VarImp<VIC>::vars_d(Space& home, VarImp<VIC>* x) {
03020 home.vars_d<VIC>(x);
03021 }
03022 #endif
03023
03024 template<class VIC>
03025 forceinline bool
03026 VarImp<VIC>::copied(void) const {
03027 return Support::marked(base);
03028 }
03029
03030 template<class VIC>
03031 forceinline VarImp<VIC>*
03032 VarImp<VIC>::forward(void) const {
03033 assert(copied());
03034 return reinterpret_cast<VarImp<VIC>*>(Support::unmark(base));
03035 }
03036
03037 template<class VIC>
03038 forceinline VarImp<VIC>*
03039 VarImp<VIC>::next(void) const {
03040 assert(copied());
03041 return u.next;
03042 }
03043
03044 template<class VIC>
03045 forceinline
03046 VarImp<VIC>::VarImp(Space& home, bool, VarImp<VIC>& x) {
03047 VarImpBase** reg;
03048 free_and_bits = x.free_and_bits & ((1 << free_bits) - 1);
03049 if (x.base == NULL) {
03050
03051 reg = &home.pc.c.vars_noidx;
03052 assert(x.degree() == 0);
03053 } else {
03054 reg = &home.pc.c.vars_u[idx_c];
03055 }
03056
03057 base = x.base;
03058 entries = x.entries;
03059 for (PropCond pc=1; pc<pc_max+2; pc++)
03060 idx(pc) = x.idx(pc);
03061
03062
03063 x.base = reinterpret_cast<ActorLink**>(Support::mark(this));
03064
03065 x.u.next = static_cast<VarImp<VIC>*>(*reg); *reg = &x;
03066 }
03067
03068 template<class VIC>
03069 forceinline ModEvent
03070 VarImp<VIC>::me(const ModEventDelta& med) {
03071 return static_cast<ModEvent>((med & VIC::med_mask) >> VIC::med_fst);
03072 }
03073
03074 template<class VIC>
03075 forceinline ModEventDelta
03076 VarImp<VIC>::med(ModEvent me) {
03077 return static_cast<ModEventDelta>(me << VIC::med_fst);
03078 }
03079
03080 template<class VIC>
03081 forceinline ModEvent
03082 VarImp<VIC>::me_combine(ModEvent me1, ModEvent me2) {
03083 return VIC::me_combine(me1,me2);
03084 }
03085
03086 template<class VIC>
03087 forceinline void
03088 VarImp<VIC>::schedule(Space& home, Propagator& p, ModEvent me,
03089 bool force) {
03090 if (VIC::med_update(p.u.med,me) || force)
03091 home.enqueue(&p);
03092 }
03093
03094 template<class VIC>
03095 forceinline void
03096 VarImp<VIC>::schedule(Space& home, PropCond pc1, PropCond pc2, ModEvent me) {
03097 ActorLink** b = actor(pc1);
03098 ActorLink** p = actorNonZero(pc2+1);
03099 while (p-- > b)
03100 schedule(home,*Propagator::cast(*p),me);
03101 }
03102
03103 template<class VIC>
03104 forceinline void
03105 VarImp<VIC>::enter(Space& home, Propagator* p, PropCond pc) {
03106 assert(pc <= pc_max);
03107
03108 home.pc.p.n_sub += 1;
03109 if ((free_and_bits >> free_bits) == 0)
03110 resize(home);
03111 free_and_bits -= 1 << free_bits;
03112
03113
03114 base[entries] = *actorNonZero(pc_max+1);
03115 entries++;
03116 for (PropCond j = pc_max; j > pc; j--) {
03117 *actorNonZero(j+1) = *actorNonZero(j);
03118 idx(j+1)++;
03119 }
03120 *actorNonZero(pc+1) = *actor(pc);
03121 idx(pc+1)++;
03122 *actor(pc) = ActorLink::cast(p);
03123
03124 #ifdef GECODE_AUDIT
03125 ActorLink** f = actor(pc);
03126 while (f < (pc == pc_max+1 ? base+entries : actorNonZero(pc+1)))
03127 if (*f == p)
03128 goto found;
03129 else
03130 f++;
03131 GECODE_NEVER;
03132 found: ;
03133 #endif
03134 }
03135
03136 template<class VIC>
03137 forceinline void
03138 VarImp<VIC>::enter(Space& home, Advisor* a) {
03139
03140 home.pc.p.n_sub += 1;
03141 if ((free_and_bits >> free_bits) == 0)
03142 resize(home);
03143 free_and_bits -= 1 << free_bits;
03144
03145
03146 base[entries++] = *actorNonZero(pc_max+1);
03147 *actorNonZero(pc_max+1) = a;
03148 }
03149
03150 template<class VIC>
03151 void
03152 VarImp<VIC>::resize(Space& home) {
03153 if (base == NULL) {
03154 assert((free_and_bits >> free_bits) == 0);
03155
03156 free_and_bits += 4 << free_bits;
03157 base = home.alloc<ActorLink*>(4);
03158 for (int i=0; i<pc_max+1; i++)
03159 u.idx[i] = 0;
03160 } else {
03161
03162 unsigned int n = degree();
03163
03164
03165
03166 ActorLink** s = static_cast<ActorLink**>(home.mm.subscriptions());
03167 unsigned int m =
03168 ((s <= base) && (base < s+home.pc.p.n_sub)) ?
03169 (n+4) : ((n+1)*3>>1);
03170 ActorLink** prop = home.alloc<ActorLink*>(m);
03171 free_and_bits += (m-n) << free_bits;
03172
03173 Heap::copy<ActorLink*>(prop, base, n);
03174 home.free<ActorLink*>(base,n);
03175 base = prop;
03176 }
03177 }
03178
03179 template<class VIC>
03180 void
03181 VarImp<VIC>::subscribe(Space& home, Propagator& p, PropCond pc,
03182 bool assigned, ModEvent me, bool schedule) {
03183 if (assigned) {
03184
03185 if (schedule)
03186 VarImp<VIC>::schedule(home,p,ME_GEN_ASSIGNED);
03187 } else {
03188 enter(home,&p,pc);
03189
03190 if (schedule && (pc != PC_GEN_ASSIGNED))
03191 VarImp<VIC>::schedule(home,p,me);
03192 }
03193 }
03194
03195 template<class VIC>
03196 forceinline void
03197 VarImp<VIC>::subscribe(Space& home, Advisor& a, bool assigned) {
03198 if (!assigned)
03199 enter(home,&a);
03200 }
03201
03202 template<class VIC>
03203 forceinline void
03204 VarImp<VIC>::remove(Space& home, Propagator* p, PropCond pc) {
03205 assert(pc <= pc_max);
03206 ActorLink* a = ActorLink::cast(p);
03207
03208 ActorLink** f = actor(pc);
03209 #ifdef GECODE_AUDIT
03210 while (f < actorNonZero(pc+1))
03211 if (*f == a)
03212 goto found;
03213 else
03214 f++;
03215 GECODE_NEVER;
03216 found: ;
03217 #else
03218 while (*f != a) f++;
03219 #endif
03220
03221 *f = *(actorNonZero(pc+1)-1);
03222 for (PropCond j = pc+1; j< pc_max+1; j++) {
03223 *(actorNonZero(j)-1) = *(actorNonZero(j+1)-1);
03224 idx(j)--;
03225 }
03226 *(actorNonZero(pc_max+1)-1) = base[entries-1];
03227 idx(pc_max+1)--;
03228 entries--;
03229 free_and_bits += 1 << free_bits;
03230 home.pc.p.n_sub -= 1;
03231 }
03232
03233 template<class VIC>
03234 forceinline void
03235 VarImp<VIC>::remove(Space& home, Advisor* a) {
03236
03237 ActorLink** f = actorNonZero(pc_max+1);
03238 #ifdef GECODE_AUDIT
03239 while (f < base+entries)
03240 if (*f == a)
03241 goto found;
03242 else
03243 f++;
03244 GECODE_NEVER;
03245 found: ;
03246 #else
03247 while (*f != a) f++;
03248 #endif
03249
03250 *f = base[--entries];
03251 free_and_bits += 1 << free_bits;
03252 home.pc.p.n_sub -= 1;
03253 }
03254
03255 template<class VIC>
03256 forceinline void
03257 VarImp<VIC>::cancel(Space& home, Propagator& p, PropCond pc, bool assigned) {
03258 if (!assigned)
03259 remove(home,&p,pc);
03260 }
03261
03262 template<class VIC>
03263 forceinline void
03264 VarImp<VIC>::cancel(Space& home, Advisor& a, bool assigned) {
03265 if (!assigned)
03266 remove(home,&a);
03267 }
03268
03269 template<class VIC>
03270 forceinline void
03271 VarImp<VIC>::cancel(Space& home) {
03272 unsigned int n_sub = degree();
03273 home.pc.p.n_sub -= n_sub;
03274 unsigned int n = (free_and_bits >> VIC::free_bits) + n_sub;
03275 home.free<ActorLink*>(base,n);
03276
03277 base = NULL;
03278
03279 entries = 0;
03280 }
03281
03282 template<class VIC>
03283 forceinline bool
03284 VarImp<VIC>::advise(Space& home, ModEvent me, Delta& d) {
03285
03286
03287
03288
03289
03290 ActorLink** la = actorNonZero(pc_max+1);
03291 ActorLink** le = base+entries;
03292 if (la == le)
03293 return true;
03294 d.me = me;
03295
03296
03297
03298 do {
03299 Advisor* a = Advisor::cast(*la);
03300 assert(!a->disposed());
03301 Propagator& p = a->propagator();
03302 switch (p.advise(home,*a,d)) {
03303 case ES_FIX:
03304 break;
03305 case ES_FAILED:
03306 p.pi.fail(home.gpi);
03307 return false;
03308 case ES_NOFIX:
03309 schedule(home,p,me);
03310 break;
03311 case ES_NOFIX_FORCE:
03312 schedule(home,p,me,true);
03313 break;
03314 default:
03315 GECODE_NEVER;
03316 }
03317 } while (++la < le);
03318 return true;
03319 }
03320
03321 template<class VIC>
03322 forceinline void
03323 VarImp<VIC>::update(VarImp<VIC>* x, ActorLink**& sub) {
03324
03325
03326
03327 x->base = base;
03328 x->u.idx[0] = u.idx[0];
03329 if (pc_max > 0 && sizeof(ActorLink**) > sizeof(unsigned int))
03330 x->u.idx[1] = u.idx[1];
03331
03332 ActorLink** f = x->base;
03333 unsigned int n = x->degree();
03334 ActorLink** t = sub;
03335 sub += n;
03336 base = t;
03337
03338 while (n >= 4) {
03339 n -= 4;
03340 t[0]=f[0]->prev(); t[1]=f[1]->prev();
03341 t[2]=f[2]->prev(); t[3]=f[3]->prev();
03342 t += 4; f += 4;
03343 }
03344 if (n >= 2) {
03345 n -= 2;
03346 t[0]=f[0]->prev(); t[1]=f[1]->prev();
03347 t += 2; f += 2;
03348 }
03349 if (n > 0) {
03350 t[0]=f[0]->prev();
03351 }
03352 }
03353
03354 template<class VIC>
03355 forceinline void
03356 VarImp<VIC>::update(Space& home, ActorLink**& sub) {
03357 VarImp<VIC>* x = static_cast<VarImp<VIC>*>(home.pc.c.vars_u[idx_c]);
03358 while (x != NULL) {
03359 VarImp<VIC>* n = x->next(); x->forward()->update(x,sub); x = n;
03360 }
03361 }
03362
03363
03364
03365
03366
03367
03368
03369 template<class VarImp>
03370 VarImpDisposer<VarImp>::VarImpDisposer(void) {
03371 #ifdef GECODE_HAS_VAR_DISPOSE
03372 Space::vd[VarImp::idx_d] = this;
03373 #endif
03374 }
03375
03376 template<class VarImp>
03377 void
03378 VarImpDisposer<VarImp>::dispose(Space& home, VarImpBase* _x) {
03379 VarImp* x = static_cast<VarImp*>(_x);
03380 do {
03381 x->dispose(home); x = static_cast<VarImp*>(x->next_d());
03382 } while (x != NULL);
03383 }
03384
03385
03386
03387
03388
03389 forceinline void
03390 StatusStatistics::reset(void) {
03391 propagate = 0;
03392 wmp = false;
03393 }
03394 forceinline
03395 StatusStatistics::StatusStatistics(void) {
03396 reset();
03397 }
03398 forceinline StatusStatistics&
03399 StatusStatistics::operator +=(const StatusStatistics& s) {
03400 propagate += s.propagate;
03401 wmp |= s.wmp;
03402 return *this;
03403 }
03404 forceinline StatusStatistics
03405 StatusStatistics::operator +(const StatusStatistics& s) {
03406 StatusStatistics t(s);
03407 return t += *this;
03408 }
03409
03410 forceinline void
03411 CloneStatistics::reset(void) {}
03412
03413 forceinline
03414 CloneStatistics::CloneStatistics(void) {
03415 reset();
03416 }
03417 forceinline CloneStatistics
03418 CloneStatistics::operator +(const CloneStatistics&) {
03419 CloneStatistics s;
03420 return s;
03421 }
03422 forceinline CloneStatistics&
03423 CloneStatistics::operator +=(const CloneStatistics&) {
03424 return *this;
03425 }
03426
03427 forceinline void
03428 CommitStatistics::reset(void) {}
03429
03430 forceinline
03431 CommitStatistics::CommitStatistics(void) {
03432 reset();
03433 }
03434 forceinline CommitStatistics
03435 CommitStatistics::operator +(const CommitStatistics&) {
03436 CommitStatistics s;
03437 return s;
03438 }
03439 forceinline CommitStatistics&
03440 CommitStatistics::operator +=(const CommitStatistics&) {
03441 return *this;
03442 }
03443
03444
03445
03446
03447
03448
03449 forceinline
03450 PropCost::PropCost(PropCost::ActualCost ac0) : ac(ac0) {}
03451
03452 forceinline PropCost
03453 PropCost::cost(PropCost::Mod m,
03454 PropCost::ActualCost lo, PropCost::ActualCost hi,
03455 unsigned int n) {
03456 if (n < 2)
03457 return (m == LO) ? AC_UNARY_LO : AC_UNARY_HI;
03458 else if (n == 2)
03459 return (m == LO) ? AC_BINARY_LO : AC_BINARY_HI;
03460 else if (n == 3)
03461 return (m == LO) ? AC_TERNARY_LO : AC_TERNARY_HI;
03462 else
03463 return (m == LO) ? lo : hi;
03464 }
03465
03466 forceinline PropCost
03467 PropCost::crazy(PropCost::Mod m, unsigned int n) {
03468 return cost(m,AC_CRAZY_LO,AC_CRAZY_HI,n);
03469 }
03470 forceinline PropCost
03471 PropCost::crazy(PropCost::Mod m, int n) {
03472 assert(n >= 0);
03473 return crazy(m,static_cast<unsigned int>(n));
03474 }
03475 forceinline PropCost
03476 PropCost::cubic(PropCost::Mod m, unsigned int n) {
03477 return cost(m,AC_CUBIC_LO,AC_CUBIC_HI,n);
03478 }
03479 forceinline PropCost
03480 PropCost::cubic(PropCost::Mod m, int n) {
03481 assert(n >= 0);
03482 return cubic(m,static_cast<unsigned int>(n));
03483 }
03484 forceinline PropCost
03485 PropCost::quadratic(PropCost::Mod m, unsigned int n) {
03486 return cost(m,AC_QUADRATIC_LO,AC_QUADRATIC_HI,n);
03487 }
03488 forceinline PropCost
03489 PropCost::quadratic(PropCost::Mod m, int n) {
03490 assert(n >= 0);
03491 return quadratic(m,static_cast<unsigned int>(n));
03492 }
03493 forceinline PropCost
03494 PropCost::linear(PropCost::Mod m, unsigned int n) {
03495 return cost(m,AC_LINEAR_LO,AC_LINEAR_HI,n);
03496 }
03497 forceinline PropCost
03498 PropCost::linear(PropCost::Mod m, int n) {
03499 assert(n >= 0);
03500 return linear(m,static_cast<unsigned int>(n));
03501 }
03502 forceinline PropCost
03503 PropCost::ternary(PropCost::Mod m) {
03504 return (m == LO) ? AC_TERNARY_LO : AC_TERNARY_HI;
03505 }
03506 forceinline PropCost
03507 PropCost::binary(PropCost::Mod m) {
03508 return (m == LO) ? AC_BINARY_LO : AC_BINARY_HI;
03509 }
03510 forceinline PropCost
03511 PropCost::unary(PropCost::Mod m) {
03512 return (m == LO) ? AC_UNARY_LO : AC_UNARY_HI;
03513 }
03514
03515
03516
03517
03518
03519 forceinline
03520 Space::Propagators::Propagators(const Space& home0)
03521 : home(home0), q(home.pc.p.active) {
03522 while (q >= &home.pc.p.queue[0]) {
03523 if (q->next() != q) {
03524 c = q->next(); e = q; q--;
03525 return;
03526 }
03527 q--;
03528 }
03529 q = NULL;
03530 if (!home.pl.empty()) {
03531 c = Propagator::cast(home.pl.next());
03532 e = Propagator::cast(&home.pl);
03533 } else {
03534 c = e = NULL;
03535 }
03536 }
03537 forceinline bool
03538 Space::Propagators::operator ()(void) const {
03539 return c != NULL;
03540 }
03541 forceinline void
03542 Space::Propagators::operator ++(void) {
03543 c = c->next();
03544 if (c == e) {
03545 if (q == NULL) {
03546 c = NULL;
03547 } else {
03548 while (q >= &home.pc.p.queue[0]) {
03549 if (q->next() != q) {
03550 c = q->next(); e = q; q--;
03551 return;
03552 }
03553 q--;
03554 }
03555 q = NULL;
03556 if (!home.pl.empty()) {
03557 c = Propagator::cast(home.pl.next());
03558 e = Propagator::cast(&home.pl);
03559 } else {
03560 c = NULL;
03561 }
03562 }
03563 }
03564 }
03565 forceinline const Propagator&
03566 Space::Propagators::propagator(void) const {
03567 return *Propagator::cast(c);
03568 }
03569
03570 forceinline
03571 Space::Branchers::Branchers(const Space& home)
03572 : c(Brancher::cast(home.bl.next())), e(&home.bl) {}
03573 forceinline bool
03574 Space::Branchers::operator ()(void) const {
03575 return c != e;
03576 }
03577 forceinline void
03578 Space::Branchers::operator ++(void) {
03579 c = c->next();
03580 }
03581 forceinline const Brancher&
03582 Space::Branchers::brancher(void) const {
03583 return *Brancher::cast(c);
03584 }
03585
03586
03587
03588
03589
03590 template<class T>
03591 forceinline T&
03592 Space::construct(void) {
03593 return alloc<T>(1);
03594 }
03595 template<class T, typename A1>
03596 forceinline T&
03597 Space::construct(A1 const& a1) {
03598 T& t = *static_cast<T*>(ralloc(sizeof(T)));
03599 new (&t) T(a1);
03600 return t;
03601 }
03602 template<class T, typename A1, typename A2>
03603 forceinline T&
03604 Space::construct(A1 const& a1, A2 const& a2) {
03605 T& t = *static_cast<T*>(ralloc(sizeof(T)));
03606 new (&t) T(a1,a2);
03607 return t;
03608 }
03609 template<class T, typename A1, typename A2, typename A3>
03610 forceinline T&
03611 Space::construct(A1 const& a1, A2 const& a2, A3 const& a3) {
03612 T& t = *static_cast<T*>(ralloc(sizeof(T)));
03613 new (&t) T(a1,a2,a3);
03614 return t;
03615 }
03616 template<class T, typename A1, typename A2, typename A3, typename A4>
03617 forceinline T&
03618 Space::construct(A1 const& a1, A2 const& a2, A3 const& a3, A4 const& a4) {
03619 T& t = *static_cast<T*>(ralloc(sizeof(T)));
03620 new (&t) T(a1,a2,a3,a4);
03621 return t;
03622 }
03623 template<class T, typename A1, typename A2, typename A3, typename A4, typename A5>
03624 forceinline T&
03625 Space::construct(A1 const& a1, A2 const& a2, A3 const& a3, A4 const& a4, A5 const& a5) {
03626 T& t = *static_cast<T*>(ralloc(sizeof(T)));
03627 new (&t) T(a1,a2,a3,a4,a5);
03628 return t;
03629 }
03630
03631 }
03632
03633