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
00135
00144
00145 typedef int ModEvent;
00146
00148 const ModEvent ME_GEN_FAILED = -1;
00150 const ModEvent ME_GEN_NONE = 0;
00152 const ModEvent ME_GEN_ASSIGNED = 1;
00153
00155 typedef int PropCond;
00157 const PropCond PC_GEN_NONE = -1;
00159 const PropCond PC_GEN_ASSIGNED = 0;
00161
00172 typedef int ModEventDelta;
00173
00174 }
00175
00176 #include <gecode/kernel/var-type.hpp>
00177
00178 namespace Gecode {
00179
00181 class NoIdxVarImpConf {
00182 public:
00184 static const int idx_c = -1;
00186 static const int idx_d = -1;
00188 static const PropCond pc_max = PC_GEN_ASSIGNED;
00190 static const int free_bits = 0;
00192 static const int med_fst = 0;
00194 static const int med_lst = 0;
00196 static const int med_mask = 0;
00198 static Gecode::ModEvent me_combine(ModEvent me1, ModEvent me2);
00200 static bool med_update(ModEventDelta& med, ModEvent me);
00201 };
00202
00203 forceinline ModEvent
00204 NoIdxVarImpConf::me_combine(ModEvent, ModEvent) {
00205 GECODE_NEVER; return 0;
00206 }
00207 forceinline bool
00208 NoIdxVarImpConf::med_update(ModEventDelta&, ModEvent) {
00209 GECODE_NEVER; return false;
00210 }
00211
00212
00213
00214
00215
00216
00217 class ActorLink;
00218 class Actor;
00219 class Propagator;
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 VarDisposerBase {
00247 public:
00249 GECODE_KERNEL_EXPORT virtual void dispose(Space& home, VarImpBase* x);
00251 GECODE_KERNEL_EXPORT virtual ~VarDisposerBase(void);
00252 };
00253
00260 template<class VarType>
00261 class VarDisposer : public VarDisposerBase {
00262 public:
00264 VarDisposer(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 public:
00277 ModEvent modevent(void) const;
00278 };
00279
00287 template<class VIC>
00288 class VarImp : public VarImpBase {
00289 friend class Space;
00290 friend class Propagator;
00291 template<class VarType> friend class VarDisposer;
00292 private:
00304 ActorLink** base;
00305
00307 static const int idx_c = VIC::idx_c;
00309 static const int idx_d = VIC::idx_d;
00311 static const int free_bits = VIC::free_bits;
00313 unsigned int entries;
00315 unsigned int free_and_bits;
00317 static const Gecode::PropCond pc_max = VIC::pc_max;
00318
00319 union {
00330 unsigned int idx[pc_max+1];
00332 VarImp<VIC>* next;
00333 } u;
00334
00336 ActorLink** actor(PropCond pc);
00338 ActorLink** actorNonZero(PropCond pc);
00340 unsigned int& idx(PropCond pc);
00342 unsigned int idx(PropCond pc) const;
00343
00350 void update(VarImp* x, ActorLink**& sub);
00357 static void update(Space& home, ActorLink**& sub);
00358
00360 void enter(Space& home, Propagator* p, PropCond pc);
00362 void enter(Space& home, Advisor* a);
00364 void resize(Space& home);
00366 void remove(Space& home, Propagator* p, PropCond pc);
00368 void remove(Space& home, Advisor* a);
00369
00370 protected:
00371 #ifdef GECODE_HAS_VAR_DISPOSE
00372
00373 static VarImp<VIC>* vars_d(Space& home);
00375 static void vars_d(Space& home, VarImp<VIC>* x);
00376 #endif
00377
00378 public:
00380 VarImp(Space& home);
00382 VarImp(void);
00383
00385
00386
00398 void subscribe(Space& home, Propagator& p, PropCond pc,
00399 bool assigned, ModEvent me, bool schedule);
00405 void cancel(Space& home, Propagator& p, PropCond pc,
00406 bool assigned);
00412 void subscribe(Space& home, Advisor& a, bool assigned);
00418 void cancel(Space& home, Advisor& a, bool assigned);
00420 void cancel(Space& home);
00427 unsigned int degree(void) const;
00434 double afc(void) const;
00440 bool advise(Space& home, ModEvent me, Delta& d);
00442
00444
00445
00446 VarImp(Space& home, bool share, VarImp& x);
00448 bool copied(void) const;
00450 VarImp* forward(void) const;
00452 VarImp* next(void) const;
00454
00456
00457
00464 static void schedule(Space& home, Propagator& p, ModEvent me,
00465 bool force = false);
00467 static ModEvent me(const ModEventDelta& med);
00469 static ModEventDelta med(ModEvent me);
00471 static ModEvent me_combine(ModEvent me1, ModEvent me2);
00473
00475 unsigned int bits(void) const;
00477 unsigned int& bits(void);
00478
00479 protected:
00481 void schedule(Space& home, PropCond pc1, PropCond pc2, ModEvent me);
00482
00483 public:
00485
00486
00487 static void* operator new(size_t,Space&);
00489 static void operator delete(void*,Space&);
00491 static void operator delete(void*);
00493 };
00494
00503 enum ExecStatus {
00504 __ES_SUBSUMED = -2,
00505 ES_FAILED = -1,
00506 ES_NOFIX = 0,
00507 ES_OK = 0,
00508 ES_FIX = 1,
00509 ES_NOFIX_FORCE = 2,
00510 __ES_PARTIAL = 2
00511 };
00512
00517 class PropCost {
00518 friend class Space;
00519 public:
00521 enum ActualCost {
00522 AC_CRAZY_LO = 0,
00523 AC_CRAZY_HI = 0,
00524 AC_CUBIC_LO = 1,
00525 AC_CUBIC_HI = 1,
00526 AC_QUADRATIC_LO = 2,
00527 AC_QUADRATIC_HI = 2,
00528 AC_LINEAR_HI = 3,
00529 AC_LINEAR_LO = 4,
00530 AC_TERNARY_HI = 4,
00531 AC_BINARY_HI = 5,
00532 AC_TERNARY_LO = 5,
00533 AC_BINARY_LO = 6,
00534 AC_UNARY_LO = 6,
00535 AC_UNARY_HI = 6,
00536 AC_MAX = 6
00537 };
00539 ActualCost ac;
00540 public:
00542 enum Mod {
00543 LO,
00544 HI
00545 };
00546 private:
00548 static PropCost cost(Mod m, ActualCost lo, ActualCost hi, unsigned int n);
00550 PropCost(ActualCost ac);
00551 public:
00553 static PropCost crazy(PropCost::Mod m, unsigned int n);
00555 static PropCost crazy(PropCost::Mod m, int n);
00557 static PropCost cubic(PropCost::Mod m, unsigned int n);
00559 static PropCost cubic(PropCost::Mod m, int n);
00561 static PropCost quadratic(PropCost::Mod m, unsigned int n);
00563 static PropCost quadratic(PropCost::Mod m, int n);
00565 static PropCost linear(PropCost::Mod m, unsigned int n);
00567 static PropCost linear(PropCost::Mod m, int n);
00569 static PropCost ternary(PropCost::Mod m);
00571 static PropCost binary(PropCost::Mod m);
00573 static PropCost unary(PropCost::Mod m);
00574 };
00575
00576
00581 enum ActorProperty {
00590 AP_DISPOSE = (1 << 0),
00596 AP_WEAKLY = (1 << 1)
00597 };
00598
00599
00607 class ActorLink {
00608 friend class Actor;
00609 friend class Propagator;
00610 friend class Advisor;
00611 friend class Brancher;
00612 friend class Space;
00613 template<class VIC> friend class VarImp;
00614 private:
00615 ActorLink* _next; ActorLink* _prev;
00616 public:
00618
00619 ActorLink* prev(void) const; void prev(ActorLink*);
00620 ActorLink* next(void) const; void next(ActorLink*);
00621 ActorLink** next_ref(void);
00623
00625 void init(void);
00627 void unlink(void);
00629 void head(ActorLink* al);
00631 void tail(ActorLink* al);
00633 bool empty(void) const;
00635 template<class T> static ActorLink* cast(T* a);
00637 template<class T> static const ActorLink* cast(const T* a);
00638 };
00639
00640
00645 class GECODE_VTABLE_EXPORT Actor : private ActorLink {
00646 friend class ActorLink;
00647 friend class Space;
00648 friend class Propagator;
00649 friend class Advisor;
00650 friend class Brancher;
00651 template<class VIC> friend class VarImp;
00652 template<class A> friend class Council;
00653 private:
00655 static Actor* cast(ActorLink* al);
00657 static const Actor* cast(const ActorLink* al);
00658 public:
00660 virtual Actor* copy(Space& home, bool share) = 0;
00661
00663
00664
00665 GECODE_KERNEL_EXPORT
00666 virtual size_t allocated(void) const;
00668 GECODE_KERNEL_EXPORT
00669 virtual size_t dispose(Space& home);
00671 static void* operator new(size_t s, Space& home);
00673 static void operator delete(void* p, Space& home);
00674 private:
00675 #ifndef __GNUC__
00676
00677 static void operator delete(void* p);
00678 #endif
00679
00680 static void* operator new(size_t s);
00682 #ifdef __GNUC__
00683 public:
00685 GECODE_KERNEL_EXPORT virtual ~Actor(void);
00687 static void operator delete(void* p);
00688 #endif
00689 };
00690
00691
00692
00696 class Home {
00697 protected:
00699 Space& s;
00701 Propagator* p;
00702 public:
00704
00705
00706 Home(Space& s, Propagator* p=NULL);
00708 operator Space&(void);
00710
00711
00712
00713 Home operator ()(Propagator& p);
00715 Propagator* propagator(void) const;
00717
00718
00719
00720 bool failed(void) const;
00722 void fail(void);
00724 void notice(Actor& a, ActorProperty p);
00726 };
00727
00732 class GECODE_VTABLE_EXPORT Propagator : public Actor {
00733 friend class ActorLink;
00734 friend class Space;
00735 template<class VIC> friend class VarImp;
00736 friend class Advisor;
00737 template<class A> friend class Council;
00738 private:
00739 union {
00741 ModEventDelta med;
00743 size_t size;
00745 Gecode::ActorLink* advisors;
00746 } u;
00748 PropInfo& pi;
00750 static Propagator* cast(ActorLink* al);
00752 static const Propagator* cast(const ActorLink* al);
00753 protected:
00755 Propagator(Home home);
00757 Propagator(Space& home, bool share, Propagator& p);
00758
00759 public:
00761
00762
00785 virtual ExecStatus propagate(Space& home, const ModEventDelta& med) = 0;
00787 virtual PropCost cost(const Space& home, const ModEventDelta& med) const = 0;
00823 GECODE_KERNEL_EXPORT
00824 virtual ExecStatus advise(Space& home, Advisor& a, const Delta& d);
00826
00827
00828
00829 double afc(void) const;
00831 };
00832
00833
00841 template<class A>
00842 class Council {
00843 friend class Advisor;
00844 friend class Advisors<A>;
00845 private:
00847 mutable ActorLink* advisors;
00848 public:
00850 Council(void);
00852 Council(Space& home);
00854 bool empty(void) const;
00856 void update(Space& home, bool share, Council<A>& c);
00858 void dispose(Space& home);
00859 };
00860
00861
00866 template<class A>
00867 class Advisors {
00868 private:
00870 ActorLink* a;
00871 public:
00873 Advisors(const Council<A>& c);
00875 bool operator ()(void) const;
00877 void operator ++(void);
00879 A& advisor(void) const;
00880 };
00881
00882
00893 class Advisor : private ActorLink {
00894 template<class VIC> friend class VarImp;
00895 template<class A> friend class Council;
00896 template<class A> friend class Advisors;
00897 private:
00899 bool disposed(void) const;
00901 static Advisor* cast(ActorLink* al);
00903 static const Advisor* cast(const ActorLink* al);
00904 protected:
00906 Propagator& propagator(void) const;
00907 public:
00909 template<class A>
00910 Advisor(Space& home, Propagator& p, Council<A>& c);
00912 Advisor(Space& home, bool share, Advisor& a);
00913
00915
00916
00917 template<class A>
00918 void dispose(Space& home, Council<A>& c);
00920 static void* operator new(size_t s, Space& home);
00922 static void operator delete(void* p, Space& home);
00924 private:
00925 #ifndef __GNUC__
00926
00927 static void operator delete(void* p);
00928 #endif
00929
00930 static void* operator new(size_t s);
00931 };
00932
00933
00934 class Brancher;
00935
00945 class Choice {
00946 friend class Space;
00947 private:
00948 unsigned int _id;
00949 unsigned int _alt;
00950
00952 unsigned int id(void) const;
00953 protected:
00955 Choice(const Brancher& b, const unsigned int a);
00956 public:
00958 unsigned int alternatives(void) const;
00960 GECODE_KERNEL_EXPORT virtual ~Choice(void);
00962 virtual size_t size(void) const = 0;
00964 static void* operator new(size_t);
00966 static void operator delete(void*);
00967 };
00968
00978 class GECODE_VTABLE_EXPORT Brancher : public Actor {
00979 friend class ActorLink;
00980 friend class Space;
00981 friend class Choice;
00982 private:
00984 unsigned int _id;
00986 static Brancher* cast(ActorLink* al);
00988 static const Brancher* cast(const ActorLink* al);
00989 protected:
00991 Brancher(Home home);
00993 Brancher(Space& home, bool share, Brancher& b);
00994 public:
00996
00997
01005 virtual bool status(const Space& home) const = 0;
01013 virtual const Choice* choice(Space& home) = 0;
01020 virtual ExecStatus commit(Space& home, const Choice& c,
01021 unsigned int a) = 0;
01023 unsigned int id(void) const;
01025 };
01026
01027
01028
01033 enum SpaceStatus {
01034 SS_FAILED,
01035 SS_SOLVED,
01036 SS_BRANCH
01037 };
01038
01043 class StatusStatistics {
01044 public:
01046 unsigned long int propagate;
01048 bool wmp;
01050 StatusStatistics(void);
01052 void reset(void);
01054 StatusStatistics operator +(const StatusStatistics& s);
01056 StatusStatistics& operator +=(const StatusStatistics& s);
01057 };
01058
01063 class CloneStatistics {
01064 public:
01066 CloneStatistics(void);
01068 void reset(void);
01070 CloneStatistics operator +(const CloneStatistics& s);
01072 CloneStatistics& operator +=(const CloneStatistics& s);
01073 };
01074
01079 class CommitStatistics {
01080 public:
01082 CommitStatistics(void);
01084 void reset(void);
01086 CommitStatistics operator +(const CommitStatistics& s);
01088 CommitStatistics& operator +=(const CommitStatistics& s);
01089 };
01090
01094 class GECODE_VTABLE_EXPORT Space {
01095 friend class Actor;
01096 friend class Propagator;
01097 friend class Brancher;
01098 friend class Advisor;
01099 template<class VIC> friend class VarImp;
01100 template<class VarType> friend class VarDisposer;
01101 friend class SharedHandle;
01102 friend class Region;
01103 private:
01105 SharedMemory* sm;
01107 MemoryManager mm;
01109 GlobalPropInfo gpi;
01111 ActorLink pl;
01113 ActorLink bl;
01119 Brancher* b_status;
01131 Brancher* b_commit;
01132 union {
01134 struct {
01147 ActorLink* active;
01149 ActorLink queue[PropCost::AC_MAX+1];
01151 unsigned int branch_id;
01153 unsigned int n_sub;
01154 } p;
01156 struct {
01158 VarImpBase* vars_u[AllVarConf::idx_c];
01160 VarImpBase* vars_noidx;
01162 SharedHandle::Object* shared;
01163 } c;
01164 } pc;
01166 void enqueue(Propagator* p);
01171 #ifdef GECODE_HAS_VAR_DISPOSE
01172
01173 GECODE_KERNEL_EXPORT static VarDisposerBase* vd[AllVarConf::idx_d];
01175 VarImpBase* _vars_d[AllVarConf::idx_d];
01177 template<class VIC> VarImpBase* vars_d(void) const;
01179 template<class VIC> void vars_d(VarImpBase* x);
01180 #endif
01181
01182 void update(ActorLink** sub);
01184
01186 Actor** d_fst;
01188 Actor** d_cur;
01190 Actor** d_lst;
01192 GECODE_KERNEL_EXPORT void d_resize(void);
01193
01201 unsigned int n_wmp;
01202
01204 GECODE_KERNEL_EXPORT static StatusStatistics unused_status;
01206 GECODE_KERNEL_EXPORT static CloneStatistics unused_clone;
01208 GECODE_KERNEL_EXPORT static CommitStatistics unused_commit;
01210 GECODE_KERNEL_EXPORT static unsigned long int unused_uli;
01212 GECODE_KERNEL_EXPORT static bool unused_b;
01213
01228 GECODE_KERNEL_EXPORT Space* _clone(bool share=true);
01229
01262 GECODE_KERNEL_EXPORT
01263 void _commit(const Choice& c, unsigned int a);
01264
01265 public:
01270 GECODE_KERNEL_EXPORT Space(void);
01275 GECODE_KERNEL_EXPORT virtual ~Space(void);
01286 GECODE_KERNEL_EXPORT Space(bool share, Space& s);
01293 virtual Space* copy(bool share) = 0;
01305 GECODE_KERNEL_EXPORT virtual void constrain(const Space& best);
01310 static void* operator new(size_t);
01315 static void operator delete(void*);
01316
01317
01318
01319
01320
01321
01322
01334 GECODE_KERNEL_EXPORT
01335 SpaceStatus status(StatusStatistics& stat=unused_status);
01336
01368 GECODE_KERNEL_EXPORT
01369 const Choice* choice(void);
01370
01388 Space* clone(bool share=true, CloneStatistics& stat=unused_clone) const;
01389
01424 void commit(const Choice& c, unsigned int a,
01425 CommitStatistics& stat=unused_commit);
01426
01434 void notice(Actor& a, ActorProperty p);
01442 void ignore(Actor& a, ActorProperty p);
01443
01444
01455 ExecStatus ES_SUBSUMED(Propagator& p);
01470 ExecStatus ES_SUBSUMED_DISPOSED(Propagator& p, size_t s);
01481 ExecStatus ES_FIX_PARTIAL(Propagator& p, const ModEventDelta& med);
01492 ExecStatus ES_NOFIX_PARTIAL(Propagator& p, const ModEventDelta& med);
01493
01504 template<class A>
01505 ExecStatus ES_FIX_DISPOSE(Council<A>& c, A& a);
01516 template<class A>
01517 ExecStatus ES_NOFIX_DISPOSE(Council<A>& c, A& a);
01529 template<class A>
01530 ExecStatus ES_NOFIX_DISPOSE_FORCE(Council<A>& c, A& a);
01531
01539 void fail(void);
01548 bool failed(void) const;
01553 bool stable(void) const;
01560 GECODE_KERNEL_EXPORT unsigned int propagators(void) const;
01567 GECODE_KERNEL_EXPORT unsigned int branchers(void) const;
01568
01570
01571
01572 Home operator ()(Propagator& p);
01574
01586 template<class T>
01587 T* alloc(long unsigned int n);
01594 template<class T>
01595 T* alloc(long int n);
01602 template<class T>
01603 T* alloc(unsigned int n);
01610 template<class T>
01611 T* alloc(int n);
01621 template<class T>
01622 void free(T* b, long unsigned int n);
01632 template<class T>
01633 void free(T* b, long int n);
01643 template<class T>
01644 void free(T* b, unsigned int n);
01654 template<class T>
01655 void free(T* b, int n);
01667 template<class T>
01668 T* realloc(T* b, long unsigned int n, long unsigned int m);
01680 template<class T>
01681 T* realloc(T* b, long int n, long int m);
01693 template<class T>
01694 T* realloc(T* b, unsigned int n, unsigned int m);
01706 template<class T>
01707 T* realloc(T* b, int n, int m);
01715 template<class T>
01716 T** realloc(T** b, long unsigned int n, long unsigned int m);
01724 template<class T>
01725 T** realloc(T** b, long int n, long int m);
01733 template<class T>
01734 T** realloc(T** b, unsigned int n, unsigned int m);
01742 template<class T>
01743 T** realloc(T** b, int n, int m);
01745 void* ralloc(size_t s);
01747 void rfree(void* p, size_t s);
01749 void* rrealloc(void* b, size_t n, size_t m);
01751 template<size_t> void* fl_alloc(void);
01757 template<size_t> void fl_dispose(FreeList* f, FreeList* l);
01764 size_t allocated(void) const;
01774 GECODE_KERNEL_EXPORT void flush(void);
01776
01777
01778
01781 template<class T>
01782 T& construct(void);
01788 template<class T, typename A1>
01789 T& construct(A1 const& a1);
01795 template<class T, typename A1, typename A2>
01796 T& construct(A1 const& a1, A2 const& a2);
01802 template<class T, typename A1, typename A2, typename A3>
01803 T& construct(A1 const& a1, A2 const& a2, A3 const& a3);
01809 template<class T, typename A1, typename A2, typename A3, typename A4>
01810 T& construct(A1 const& a1, A2 const& a2, A3 const& a3, A4 const& a4);
01816 template<class T, typename A1, typename A2, typename A3, typename A4, typename A5>
01817 T& construct(A1 const& a1, A2 const& a2, A3 const& a3, A4 const& a4, A5 const& a5);
01819
01825 class Propagators {
01826 private:
01828 const Space& home;
01830 const ActorLink* q;
01832 const ActorLink* c;
01834 const ActorLink* e;
01835 public:
01837 Propagators(const Space& home);
01839 bool operator ()(void) const;
01841 void operator ++(void);
01843 const Propagator& propagator(void) const;
01844 };
01845
01851 class Branchers {
01852 private:
01854 const ActorLink* c;
01856 const ActorLink* e;
01857 public:
01859 Branchers(const Space& home);
01861 bool operator ()(void) const;
01863 void operator ++(void);
01865 const Brancher& brancher(void) const;
01866 };
01867 };
01868
01869
01870
01871
01872
01873
01874
01875
01876
01877
01878 forceinline void*
01879 SharedHandle::Object::operator new(size_t s) {
01880 return heap.ralloc(s);
01881 }
01882 forceinline void
01883 SharedHandle::Object::operator delete(void* p) {
01884 heap.rfree(p);
01885 }
01886
01887 forceinline void*
01888 Space::operator new(size_t s) {
01889 return heap.ralloc(s);
01890 }
01891 forceinline void
01892 Space::operator delete(void* p) {
01893 heap.rfree(p);
01894 }
01895
01896 forceinline void
01897 Choice::operator delete(void* p) {
01898 heap.rfree(p);
01899 }
01900 forceinline void*
01901 Choice::operator new(size_t s) {
01902 return heap.ralloc(s);
01903 }
01904
01905
01906 forceinline void*
01907 Space::ralloc(size_t s) {
01908 return mm.alloc(sm,s);
01909 }
01910 forceinline void
01911 Space::rfree(void* p, size_t s) {
01912 return mm.reuse(p,s);
01913 }
01914 forceinline void*
01915 Space::rrealloc(void* _b, size_t n, size_t m) {
01916 char* b = static_cast<char*>(_b);
01917 if (n < m) {
01918 char* p = static_cast<char*>(ralloc(m));
01919 memcpy(p,b,n);
01920 rfree(b,n);
01921 return p;
01922 } else {
01923 rfree(b+m,m-n);
01924 return b;
01925 }
01926 }
01927
01928 template<size_t s>
01929 forceinline void*
01930 Space::fl_alloc(void) {
01931 return mm.template fl_alloc<s>(sm);
01932 }
01933 template<size_t s>
01934 forceinline void
01935 Space::fl_dispose(FreeList* f, FreeList* l) {
01936 mm.template fl_dispose<s>(f,l);
01937 }
01938
01939 forceinline size_t
01940 Space::allocated(void) const {
01941 size_t s = mm.allocated();
01942 for (Actor** a = d_fst; a < d_cur; a++)
01943 s += (*a)->allocated();
01944 return s;
01945 }
01946
01947
01948
01949
01950
01951 template<class T>
01952 forceinline T*
01953 Space::alloc(long unsigned int n) {
01954 T* p = static_cast<T*>(ralloc(sizeof(T)*n));
01955 for (long unsigned int i=n; i--; )
01956 (void) new (p+i) T();
01957 return p;
01958 }
01959 template<class T>
01960 forceinline T*
01961 Space::alloc(long int n) {
01962 assert(n >= 0);
01963 return alloc<T>(static_cast<long unsigned int>(n));
01964 }
01965 template<class T>
01966 forceinline T*
01967 Space::alloc(unsigned int n) {
01968 return alloc<T>(static_cast<long unsigned int>(n));
01969 }
01970 template<class T>
01971 forceinline T*
01972 Space::alloc(int n) {
01973 assert(n >= 0);
01974 return alloc<T>(static_cast<long unsigned int>(n));
01975 }
01976
01977 template<class T>
01978 forceinline void
01979 Space::free(T* b, long unsigned int n) {
01980 for (long unsigned int i=n; i--; )
01981 b[i].~T();
01982 rfree(b,n*sizeof(T));
01983 }
01984 template<class T>
01985 forceinline void
01986 Space::free(T* b, long int n) {
01987 assert(n >= 0);
01988 free<T>(b,static_cast<long unsigned int>(n));
01989 }
01990 template<class T>
01991 forceinline void
01992 Space::free(T* b, unsigned int n) {
01993 free<T>(b,static_cast<long unsigned int>(n));
01994 }
01995 template<class T>
01996 forceinline void
01997 Space::free(T* b, int n) {
01998 assert(n >= 0);
01999 free<T>(b,static_cast<long unsigned int>(n));
02000 }
02001
02002 template<class T>
02003 forceinline T*
02004 Space::realloc(T* b, long unsigned int n, long unsigned int m) {
02005 if (n < m) {
02006 T* p = static_cast<T*>(ralloc(sizeof(T)*m));
02007 for (long unsigned int i=n; i--; )
02008 (void) new (p+i) T(b[i]);
02009 for (long unsigned int i=n; i<m; i++)
02010 (void) new (p+i) T();
02011 free<T>(b,n);
02012 return p;
02013 } else {
02014 free<T>(b+m,m-n);
02015 return b;
02016 }
02017 }
02018 template<class T>
02019 forceinline T*
02020 Space::realloc(T* b, long int n, long int m) {
02021 assert((n >= 0) && (m >= 0));
02022 return realloc<T>(b,static_cast<long unsigned int>(n),
02023 static_cast<long unsigned int>(m));
02024 }
02025 template<class T>
02026 forceinline T*
02027 Space::realloc(T* b, unsigned int n, unsigned int m) {
02028 return realloc<T>(b,static_cast<long unsigned int>(n),
02029 static_cast<long unsigned int>(m));
02030 }
02031 template<class T>
02032 forceinline T*
02033 Space::realloc(T* b, int n, int m) {
02034 assert((n >= 0) && (m >= 0));
02035 return realloc<T>(b,static_cast<long unsigned int>(n),
02036 static_cast<long unsigned int>(m));
02037 }
02038
02039 #define GECODE_KERNEL_REALLOC(T) \
02040 template<> \
02041 forceinline T* \
02042 Space::realloc<T>(T* b, long unsigned int n, long unsigned int m) { \
02043 return static_cast<T*>(rrealloc(b,n*sizeof(T),m*sizeof(T))); \
02044 } \
02045 template<> \
02046 forceinline T* \
02047 Space::realloc<T>(T* b, long int n, long int m) { \
02048 assert((n >= 0) && (m >= 0)); \
02049 return realloc<T>(b,static_cast<long unsigned int>(n), \
02050 static_cast<long unsigned int>(m)); \
02051 } \
02052 template<> \
02053 forceinline T* \
02054 Space::realloc<T>(T* b, unsigned int n, unsigned int m) { \
02055 return realloc<T>(b,static_cast<long unsigned int>(n), \
02056 static_cast<long unsigned int>(m)); \
02057 } \
02058 template<> \
02059 forceinline T* \
02060 Space::realloc<T>(T* b, int n, int m) { \
02061 assert((n >= 0) && (m >= 0)); \
02062 return realloc<T>(b,static_cast<long unsigned int>(n), \
02063 static_cast<long unsigned int>(m)); \
02064 }
02065
02066 GECODE_KERNEL_REALLOC(bool)
02067 GECODE_KERNEL_REALLOC(signed char)
02068 GECODE_KERNEL_REALLOC(unsigned char)
02069 GECODE_KERNEL_REALLOC(signed short int)
02070 GECODE_KERNEL_REALLOC(unsigned short int)
02071 GECODE_KERNEL_REALLOC(signed int)
02072 GECODE_KERNEL_REALLOC(unsigned int)
02073 GECODE_KERNEL_REALLOC(signed long int)
02074 GECODE_KERNEL_REALLOC(unsigned long int)
02075 GECODE_KERNEL_REALLOC(float)
02076 GECODE_KERNEL_REALLOC(double)
02077
02078 #undef GECODE_KERNEL_REALLOC
02079
02080 template<class T>
02081 forceinline T**
02082 Space::realloc(T** b, long unsigned int n, long unsigned int m) {
02083 return static_cast<T**>(rrealloc(b,n*sizeof(T),m*sizeof(T*)));
02084 }
02085 template<class T>
02086 forceinline T**
02087 Space::realloc(T** b, long int n, long int m) {
02088 assert((n >= 0) && (m >= 0));
02089 return realloc<T*>(b,static_cast<long unsigned int>(n),
02090 static_cast<long unsigned int>(m));
02091 }
02092 template<class T>
02093 forceinline T**
02094 Space::realloc(T** b, unsigned int n, unsigned int m) {
02095 return realloc<T*>(b,static_cast<long unsigned int>(n),
02096 static_cast<long unsigned int>(m));
02097 }
02098 template<class T>
02099 forceinline T**
02100 Space::realloc(T** b, int n, int m) {
02101 assert((n >= 0) && (m >= 0));
02102 return realloc<T*>(b,static_cast<long unsigned int>(n),
02103 static_cast<long unsigned int>(m));
02104 }
02105
02106
02107 #ifdef GECODE_HAS_VAR_DISPOSE
02108 template<class VIC>
02109 forceinline VarImpBase*
02110 Space::vars_d(void) const {
02111 return _vars_d[VIC::idx_d];
02112 }
02113 template<class VIC>
02114 forceinline void
02115 Space::vars_d(VarImpBase* x) {
02116 _vars_d[VIC::idx_d] = x;
02117 }
02118 #endif
02119
02120
02121 forceinline void
02122 Actor::operator delete(void*) {}
02123 forceinline void
02124 Actor::operator delete(void*, Space&) {}
02125 forceinline void*
02126 Actor::operator new(size_t s, Space& home) {
02127 return home.ralloc(s);
02128 }
02129
02130 template<class VIC>
02131 forceinline void
02132 VarImp<VIC>::operator delete(void*) {}
02133 template<class VIC>
02134 forceinline void
02135 VarImp<VIC>::operator delete(void*, Space&) {}
02136 template<class VIC>
02137 forceinline void*
02138 VarImp<VIC>::operator new(size_t s, Space& home) {
02139 return home.ralloc(s);
02140 }
02141
02142 #ifndef __GNUC__
02143 forceinline void
02144 Advisor::operator delete(void*) {}
02145 #endif
02146 forceinline void
02147 Advisor::operator delete(void*, Space&) {}
02148 forceinline void*
02149 Advisor::operator new(size_t s, Space& home) {
02150 return home.ralloc(s);
02151 }
02152
02153
02154
02155
02156
02157 forceinline
02158 SharedHandle::Object::Object(void)
02159 : next(NULL), fwd(NULL), use_cnt(0) {}
02160 forceinline
02161 SharedHandle::Object::~Object(void) {
02162 assert(use_cnt == 0);
02163 }
02164
02165 forceinline SharedHandle::Object*
02166 SharedHandle::object(void) const {
02167 return o;
02168 }
02169 forceinline void
02170 SharedHandle::subscribe(void) {
02171 if (o != NULL) o->use_cnt++;
02172 }
02173 forceinline void
02174 SharedHandle::cancel(void) {
02175 if ((o != NULL) && (--o->use_cnt == 0))
02176 delete o;
02177 o=NULL;
02178 }
02179 forceinline void
02180 SharedHandle::object(SharedHandle::Object* n) {
02181 if (n != o) {
02182 cancel(); o=n; subscribe();
02183 }
02184 }
02185 forceinline
02186 SharedHandle::SharedHandle(void) : o(NULL) {}
02187 forceinline
02188 SharedHandle::SharedHandle(SharedHandle::Object* so) : o(so) {
02189 subscribe();
02190 }
02191 forceinline
02192 SharedHandle::SharedHandle(const SharedHandle& sh) : o(sh.o) {
02193 subscribe();
02194 }
02195 forceinline SharedHandle&
02196 SharedHandle::operator =(const SharedHandle& sh) {
02197 if (&sh != this) {
02198 cancel(); o=sh.o; subscribe();
02199 }
02200 return *this;
02201 }
02202 forceinline void
02203 SharedHandle::update(Space& home, bool share, SharedHandle& sh) {
02204 if (sh.o == NULL) {
02205 o=NULL; return;
02206 } else if (share) {
02207 o=sh.o;
02208 } else if (sh.o->fwd != NULL) {
02209 o=sh.o->fwd;
02210 } else {
02211 o = sh.o->copy();
02212 sh.o->fwd = o;
02213 sh.o->next = home.pc.c.shared;
02214 home.pc.c.shared = sh.o;
02215 }
02216 subscribe();
02217 }
02218 forceinline
02219 SharedHandle::~SharedHandle(void) {
02220 cancel();
02221 }
02222
02223
02224
02225
02226
02227
02228
02229 forceinline ActorLink*
02230 ActorLink::prev(void) const {
02231 return _prev;
02232 }
02233
02234 forceinline ActorLink*
02235 ActorLink::next(void) const {
02236 return _next;
02237 }
02238
02239 forceinline ActorLink**
02240 ActorLink::next_ref(void) {
02241 return &_next;
02242 }
02243
02244 forceinline void
02245 ActorLink::prev(ActorLink* al) {
02246 _prev = al;
02247 }
02248
02249 forceinline void
02250 ActorLink::next(ActorLink* al) {
02251 _next = al;
02252 }
02253
02254 forceinline void
02255 ActorLink::unlink(void) {
02256 ActorLink* p = _prev; ActorLink* n = _next;
02257 p->_next = n; n->_prev = p;
02258 }
02259
02260 forceinline void
02261 ActorLink::init(void) {
02262 _next = this; _prev =this;
02263 }
02264
02265 forceinline void
02266 ActorLink::head(ActorLink* a) {
02267
02268 ActorLink* n = _next;
02269 this->_next = a; a->_prev = this;
02270 a->_next = n; n->_prev = a;
02271 }
02272
02273 forceinline void
02274 ActorLink::tail(ActorLink* a) {
02275
02276 ActorLink* p = _prev;
02277 a->_next = this; this->_prev = a;
02278 p->_next = a; a->_prev = p;
02279 }
02280
02281 forceinline bool
02282 ActorLink::empty(void) const {
02283 return _next == this;
02284 }
02285
02286 template<class T>
02287 forceinline ActorLink*
02288 ActorLink::cast(T* a) {
02289
02290 GECODE_NOT_NULL(a);
02291 ActorLink& t = *a;
02292 return static_cast<ActorLink*>(&t);
02293 }
02294
02295 template<class T>
02296 forceinline const ActorLink*
02297 ActorLink::cast(const T* a) {
02298
02299 GECODE_NOT_NULL(a);
02300 const ActorLink& t = *a;
02301 return static_cast<const ActorLink*>(&t);
02302 }
02303
02304
02305
02306
02307
02308
02309 forceinline Actor*
02310 Actor::cast(ActorLink* al) {
02311
02312 GECODE_NOT_NULL(al);
02313 ActorLink& t = *al;
02314 return static_cast<Actor*>(&t);
02315 }
02316
02317 forceinline const Actor*
02318 Actor::cast(const ActorLink* al) {
02319
02320 GECODE_NOT_NULL(al);
02321 const ActorLink& t = *al;
02322 return static_cast<const Actor*>(&t);
02323 }
02324
02325 forceinline void
02326 Space::notice(Actor& a, ActorProperty p) {
02327 if (p & AP_DISPOSE) {
02328 if (d_cur == d_lst)
02329 d_resize();
02330 *(d_cur++) = &a;
02331 }
02332 if (p & AP_WEAKLY) {
02333 if (n_wmp == 0)
02334 n_wmp = 2;
02335 else
02336 n_wmp++;
02337 }
02338 }
02339
02340 forceinline void
02341 Home::notice(Actor& a, ActorProperty p) {
02342 s.notice(a,p);
02343 }
02344
02345 forceinline void
02346 Space::ignore(Actor& a, ActorProperty p) {
02347 if (p & AP_DISPOSE) {
02348
02349
02350 Actor** f = d_fst;
02351 if (f != NULL) {
02352 while (&a != *f)
02353 f++;
02354 *f = *(--d_cur);
02355 }
02356 }
02357 if (p & AP_WEAKLY) {
02358 assert(n_wmp > 1);
02359 n_wmp--;
02360 }
02361 }
02362
02363 forceinline Space*
02364 Space::clone(bool share, CloneStatistics&) const {
02365
02366
02367
02368 return const_cast<Space*>(this)->_clone(share);
02369 }
02370
02371 forceinline void
02372 Space::commit(const Choice& c, unsigned int a, CommitStatistics&) {
02373 _commit(c,a);
02374 }
02375
02376 forceinline size_t
02377 Actor::dispose(Space&) {
02378 return sizeof(*this);
02379 }
02380
02381
02382
02383
02384
02385
02386 forceinline
02387 Home::Home(Space& s0, Propagator* p0) : s(s0), p(p0) {}
02388 forceinline
02389 Home::operator Space&(void) {
02390 return s;
02391 }
02392 forceinline Home
02393 Home::operator ()(Propagator& p) {
02394 return Home(s,&p);
02395 }
02396 forceinline Home
02397 Space::operator ()(Propagator& p) {
02398 return Home(*this,&p);
02399 }
02400 forceinline Propagator*
02401 Home::propagator(void) const {
02402 return p;
02403 }
02404
02405
02406
02407
02408
02409 forceinline Propagator*
02410 Propagator::cast(ActorLink* al) {
02411
02412 GECODE_NOT_NULL(al);
02413 ActorLink& t = *al;
02414 return static_cast<Propagator*>(&t);
02415 }
02416
02417 forceinline const Propagator*
02418 Propagator::cast(const ActorLink* al) {
02419
02420 GECODE_NOT_NULL(al);
02421 const ActorLink& t = *al;
02422 return static_cast<const Propagator*>(&t);
02423 }
02424
02425 forceinline
02426 Propagator::Propagator(Home home)
02427 : pi((home.propagator() != NULL) ?
02428
02429 home.propagator()->pi :
02430
02431 static_cast<Space&>(home).gpi.allocate()) {
02432 u.advisors = NULL;
02433 assert((u.med == 0) && (u.size == 0));
02434 static_cast<Space&>(home).pl.head(this);
02435 }
02436
02437 forceinline
02438 Propagator::Propagator(Space&, bool, Propagator& p)
02439 : pi(p.pi) {
02440 u.advisors = NULL;
02441 assert((u.med == 0) && (u.size == 0));
02442
02443 p.prev(this);
02444 }
02445
02446 forceinline double
02447 Propagator::afc(void) const {
02448 return pi.afc();
02449 }
02450
02451 forceinline ExecStatus
02452 Space::ES_SUBSUMED_DISPOSED(Propagator& p, size_t s) {
02453 p.u.size = s;
02454 return __ES_SUBSUMED;
02455 }
02456
02457 forceinline ExecStatus
02458 Space::ES_SUBSUMED(Propagator& p) {
02459 p.u.size = p.dispose(*this);
02460 return __ES_SUBSUMED;
02461 }
02462
02463 forceinline ExecStatus
02464 Space::ES_FIX_PARTIAL(Propagator& p, const ModEventDelta& med) {
02465 p.u.med = med;
02466 assert(p.u.med != 0);
02467 return __ES_PARTIAL;
02468 }
02469
02470 forceinline ExecStatus
02471 Space::ES_NOFIX_PARTIAL(Propagator& p, const ModEventDelta& med) {
02472 p.u.med = AllVarConf::med_combine(p.u.med,med);
02473 assert(p.u.med != 0);
02474 return __ES_PARTIAL;
02475 }
02476
02477
02478
02479
02480
02481
02482
02483 forceinline Brancher*
02484 Brancher::cast(ActorLink* al) {
02485
02486 GECODE_NOT_NULL(al);
02487 ActorLink& t = *al;
02488 return static_cast<Brancher*>(&t);
02489 }
02490
02491 forceinline const Brancher*
02492 Brancher::cast(const ActorLink* al) {
02493
02494 GECODE_NOT_NULL(al);
02495 const ActorLink& t = *al;
02496 return static_cast<const Brancher*>(&t);
02497 }
02498
02499 forceinline
02500 Brancher::Brancher(Home home) :
02501 _id(static_cast<Space&>(home).pc.p.branch_id++) {
02502 if (static_cast<Space&>(home).pc.p.branch_id == 0U)
02503 throw TooManyBranchers("Brancher::Brancher");
02504
02505 if (static_cast<Space&>(home).b_status == &static_cast<Space&>(home).bl) {
02506 static_cast<Space&>(home).b_status = this;
02507 if (static_cast<Space&>(home).b_commit == &static_cast<Space&>(home).bl)
02508 static_cast<Space&>(home).b_commit = this;
02509 }
02510 static_cast<Space&>(home).bl.tail(this);
02511 }
02512
02513 forceinline
02514 Brancher::Brancher(Space&, bool, Brancher& b)
02515 : _id(b._id) {
02516
02517 b.prev(this);
02518 }
02519
02520 forceinline unsigned int
02521 Brancher::id(void) const {
02522 return _id;
02523 }
02524
02525
02526
02527
02528
02529
02530
02531 forceinline
02532 Choice::Choice(const Brancher& b, const unsigned int a)
02533 : _id(b.id()), _alt(a) {}
02534
02535 forceinline unsigned int
02536 Choice::alternatives(void) const {
02537 return _alt;
02538 }
02539
02540 forceinline unsigned int
02541 Choice::id(void) const {
02542 return _id;
02543 }
02544
02545 forceinline
02546 Choice::~Choice(void) {}
02547
02548
02549
02550
02551
02552
02553
02554 forceinline ModEvent
02555 Delta::modevent(void) const {
02556 return me;
02557 }
02558
02559
02560
02561
02562
02563
02564
02565 template<class A>
02566 forceinline
02567 Advisor::Advisor(Space&, Propagator& p, Council<A>& c) {
02568
02569 ActorLink::prev(&p);
02570
02571 ActorLink::next(c.advisors); c.advisors = static_cast<A*>(this);
02572 }
02573
02574 forceinline
02575 Advisor::Advisor(Space&, bool, Advisor&) {}
02576
02577 forceinline bool
02578 Advisor::disposed(void) const {
02579 return prev() == NULL;
02580 }
02581
02582 forceinline Advisor*
02583 Advisor::cast(ActorLink* al) {
02584 return static_cast<Advisor*>(al);
02585 }
02586
02587 forceinline const Advisor*
02588 Advisor::cast(const ActorLink* al) {
02589 return static_cast<const Advisor*>(al);
02590 }
02591
02592 forceinline Propagator&
02593 Advisor::propagator(void) const {
02594 assert(!disposed());
02595 return *Propagator::cast(ActorLink::prev());
02596 }
02597
02598 template<class A>
02599 forceinline void
02600 Advisor::dispose(Space&,Council<A>&) {
02601 assert(!disposed());
02602 ActorLink::prev(NULL);
02603
02604 Advisor* n = Advisor::cast(next());
02605 if ((n != NULL) && n->disposed())
02606 next(n->next());
02607 }
02608
02609 template<class A>
02610 forceinline ExecStatus
02611 Space::ES_FIX_DISPOSE(Council<A>& c, A& a) {
02612 a.dispose(*this,c);
02613 return ES_FIX;
02614 }
02615
02616 template<class A>
02617 forceinline ExecStatus
02618 Space::ES_NOFIX_DISPOSE(Council<A>& c, A& a) {
02619 a.dispose(*this,c);
02620 return ES_NOFIX;
02621 }
02622
02623 template<class A>
02624 forceinline ExecStatus
02625 Space::ES_NOFIX_DISPOSE_FORCE(Council<A>& c, A& a) {
02626 a.dispose(*this,c);
02627 return ES_NOFIX_FORCE;
02628 }
02629
02630
02631
02632
02633
02634
02635
02636 template<class A>
02637 forceinline
02638 Council<A>::Council(void) {}
02639
02640 template<class A>
02641 forceinline
02642 Council<A>::Council(Space&)
02643 : advisors(NULL) {}
02644
02645 template<class A>
02646 forceinline bool
02647 Council<A>::empty(void) const {
02648 ActorLink* a = advisors;
02649 while ((a != NULL) && static_cast<A*>(a)->disposed())
02650 a = a->next();
02651 advisors = a;
02652 return a == NULL;
02653 }
02654
02655 template<class A>
02656 forceinline void
02657 Council<A>::update(Space& home, bool share, Council<A>& c) {
02658
02659 {
02660 ActorLink* a = c.advisors;
02661 while ((a != NULL) && static_cast<A*>(a)->disposed())
02662 a = a->next();
02663 c.advisors = a;
02664 }
02665
02666 if (c.advisors != NULL) {
02667
02668 Propagator* p_f = &static_cast<A*>(c.advisors)->propagator();
02669
02670 Propagator* p_t = Propagator::cast(p_f->prev());
02671
02672 ActorLink** a_f = &c.advisors;
02673
02674 A* a_t = NULL;
02675 while (*a_f != NULL) {
02676 if (static_cast<A*>(*a_f)->disposed()) {
02677 *a_f = (*a_f)->next();
02678 } else {
02679
02680 A* a = new (home) A(home,share,*static_cast<A*>(*a_f));
02681
02682 a->prev(p_t);
02683
02684 (*a_f)->prev(a);
02685
02686 a->next(a_t);
02687 a_t = a;
02688 a_f = (*a_f)->next_ref();
02689 }
02690 }
02691 advisors = a_t;
02692
02693 assert(p_f->u.advisors == NULL);
02694 p_f->u.advisors = c.advisors;
02695 } else {
02696 advisors = NULL;
02697 }
02698 }
02699
02700 template<class A>
02701 forceinline void
02702 Council<A>::dispose(Space& home) {
02703 ActorLink* a = advisors;
02704 while (a != NULL) {
02705 if (!static_cast<A*>(a)->disposed())
02706 static_cast<A*>(a)->dispose(home,*this);
02707 a = a->next();
02708 }
02709 }
02710
02711
02712
02713
02714
02715
02716
02717 template<class A>
02718 forceinline
02719 Advisors<A>::Advisors(const Council<A>& c)
02720 : a(c.advisors) {
02721 while ((a != NULL) && static_cast<A*>(a)->disposed())
02722 a = a->next();
02723 }
02724
02725 template<class A>
02726 forceinline bool
02727 Advisors<A>::operator ()(void) const {
02728 return a != NULL;
02729 }
02730
02731 template<class A>
02732 forceinline void
02733 Advisors<A>::operator ++(void) {
02734 do {
02735 a = a->next();
02736 } while ((a != NULL) && static_cast<A*>(a)->disposed());
02737 }
02738
02739 template<class A>
02740 forceinline A&
02741 Advisors<A>::advisor(void) const {
02742 return *static_cast<A*>(a);
02743 }
02744
02745
02746
02747
02748
02749
02750
02751 forceinline void
02752 Space::enqueue(Propagator* p) {
02753 ActorLink::cast(p)->unlink();
02754 ActorLink* c = &pc.p.queue[p->cost(*this,p->u.med).ac];
02755 c->tail(ActorLink::cast(p));
02756 if (c > pc.p.active)
02757 pc.p.active = c;
02758 }
02759
02760 forceinline void
02761 Space::fail(void) {
02762 pc.p.active = NULL;
02763 }
02764 forceinline void
02765 Home::fail(void) {
02766 s.fail();
02767 }
02768
02769 forceinline bool
02770 Space::failed(void) const {
02771 return pc.p.active == NULL;
02772 }
02773 forceinline bool
02774 Home::failed(void) const {
02775 return s.failed();
02776 }
02777
02778 forceinline bool
02779 Space::stable(void) const {
02780 return pc.p.active < &pc.p.queue[0];
02781 }
02782
02783
02784
02785
02786
02787
02788
02789 template<class VIC>
02790 forceinline ActorLink**
02791 VarImp<VIC>::actor(PropCond pc) {
02792 assert((pc >= 0) && (pc < pc_max+2));
02793 return (pc == 0) ? base : base+u.idx[pc-1];
02794 }
02795
02796 template<class VIC>
02797 forceinline ActorLink**
02798 VarImp<VIC>::actorNonZero(PropCond pc) {
02799 assert((pc > 0) && (pc < pc_max+2));
02800 return base+u.idx[pc-1];
02801 }
02802
02803 template<class VIC>
02804 forceinline unsigned int&
02805 VarImp<VIC>::idx(PropCond pc) {
02806 assert((pc > 0) && (pc < pc_max+2));
02807 return u.idx[pc-1];
02808 }
02809
02810 template<class VIC>
02811 forceinline unsigned int
02812 VarImp<VIC>::idx(PropCond pc) const {
02813 assert((pc > 0) && (pc < pc_max+2));
02814 return u.idx[pc-1];
02815 }
02816
02817 template<class VIC>
02818 forceinline
02819 VarImp<VIC>::VarImp(Space&) {
02820 base = NULL; entries = 0;
02821 for (PropCond pc=1; pc<pc_max+2; pc++)
02822 idx(pc) = 0;
02823 free_and_bits = 0;
02824 }
02825
02826 template<class VIC>
02827 forceinline
02828 VarImp<VIC>::VarImp(void) {
02829 base = NULL; entries = 0;
02830 for (PropCond pc=1; pc<pc_max+2; pc++)
02831 idx(pc) = 0;
02832 free_and_bits = 0;
02833 }
02834
02835 template<class VIC>
02836 forceinline unsigned int
02837 VarImp<VIC>::degree(void) const {
02838 assert(!copied());
02839 return entries;
02840 }
02841
02842 template<class VIC>
02843 forceinline double
02844 VarImp<VIC>::afc(void) const {
02845 if (degree() == 0)
02846 return 0.0;
02847 double d = degree();
02848
02849 {
02850 ActorLink** a = const_cast<VarImp<VIC>*>(this)->actor(0);
02851 ActorLink** e = const_cast<VarImp<VIC>*>(this)->actorNonZero(pc_max+1);
02852 while (a < e) {
02853 d += Propagator::cast(*a)->afc(); a++;
02854 }
02855 }
02856
02857 {
02858 ActorLink** a = const_cast<VarImp<VIC>*>(this)->actorNonZero(pc_max+1);
02859 ActorLink** e = const_cast<VarImp<VIC>*>(this)->base+entries;
02860 while (a < e) {
02861 d += Advisor::cast(*a)->propagator().afc(); a++;
02862 }
02863 }
02864 return d;
02865 }
02866
02867 template<class VIC>
02868 forceinline unsigned int
02869 VarImp<VIC>::bits(void) const {
02870 return free_and_bits;
02871 }
02872
02873 template<class VIC>
02874 forceinline unsigned int&
02875 VarImp<VIC>::bits(void) {
02876 return free_and_bits;
02877 }
02878
02879 #ifdef GECODE_HAS_VAR_DISPOSE
02880 template<class VIC>
02881 forceinline VarImp<VIC>*
02882 VarImp<VIC>::vars_d(Space& home) {
02883 return static_cast<VarImp<VIC>*>(home.vars_d<VIC>());
02884 }
02885
02886 template<class VIC>
02887 forceinline void
02888 VarImp<VIC>::vars_d(Space& home, VarImp<VIC>* x) {
02889 home.vars_d<VIC>(x);
02890 }
02891 #endif
02892
02893 template<class VIC>
02894 forceinline bool
02895 VarImp<VIC>::copied(void) const {
02896 return Support::marked(base);
02897 }
02898
02899 template<class VIC>
02900 forceinline VarImp<VIC>*
02901 VarImp<VIC>::forward(void) const {
02902 assert(copied());
02903 return reinterpret_cast<VarImp<VIC>*>(Support::unmark(base));
02904 }
02905
02906 template<class VIC>
02907 forceinline VarImp<VIC>*
02908 VarImp<VIC>::next(void) const {
02909 assert(copied());
02910 return u.next;
02911 }
02912
02913 template<class VIC>
02914 forceinline
02915 VarImp<VIC>::VarImp(Space& home, bool, VarImp<VIC>& x) {
02916 VarImpBase** reg;
02917 free_and_bits = x.free_and_bits & ((1 << free_bits) - 1);
02918 if (x.base == NULL) {
02919
02920 reg = &home.pc.c.vars_noidx;
02921 assert(x.degree() == 0);
02922 } else {
02923 reg = &home.pc.c.vars_u[idx_c];
02924 }
02925
02926 base = x.base;
02927 entries = x.entries;
02928 for (PropCond pc=1; pc<pc_max+2; pc++)
02929 idx(pc) = x.idx(pc);
02930
02931
02932 x.base = reinterpret_cast<ActorLink**>(Support::mark(this));
02933
02934 x.u.next = static_cast<VarImp<VIC>*>(*reg); *reg = &x;
02935 }
02936
02937 template<class VIC>
02938 forceinline ModEvent
02939 VarImp<VIC>::me(const ModEventDelta& med) {
02940 return static_cast<ModEvent>((med & VIC::med_mask) >> VIC::med_fst);
02941 }
02942
02943 template<class VIC>
02944 forceinline ModEventDelta
02945 VarImp<VIC>::med(ModEvent me) {
02946 return static_cast<ModEventDelta>(me << VIC::med_fst);
02947 }
02948
02949 template<class VIC>
02950 forceinline ModEvent
02951 VarImp<VIC>::me_combine(ModEvent me1, ModEvent me2) {
02952 return VIC::me_combine(me1,me2);
02953 }
02954
02955 template<class VIC>
02956 forceinline void
02957 VarImp<VIC>::schedule(Space& home, Propagator& p, ModEvent me,
02958 bool force) {
02959 if (VIC::med_update(p.u.med,me) || force)
02960 home.enqueue(&p);
02961 }
02962
02963 template<class VIC>
02964 forceinline void
02965 VarImp<VIC>::schedule(Space& home, PropCond pc1, PropCond pc2, ModEvent me) {
02966 ActorLink** b = actor(pc1);
02967 ActorLink** p = actorNonZero(pc2+1);
02968 while (p-- > b)
02969 schedule(home,*Propagator::cast(*p),me);
02970 }
02971
02972 template<class VIC>
02973 forceinline void
02974 VarImp<VIC>::enter(Space& home, Propagator* p, PropCond pc) {
02975 assert(pc <= pc_max);
02976
02977 home.pc.p.n_sub += 1;
02978 if ((free_and_bits >> free_bits) == 0)
02979 resize(home);
02980 free_and_bits -= 1 << free_bits;
02981
02982
02983 base[entries] = *actorNonZero(pc_max+1);
02984 entries++;
02985 for (PropCond j = pc_max; j > pc; j--) {
02986 *actorNonZero(j+1) = *actorNonZero(j);
02987 idx(j+1)++;
02988 }
02989 *actorNonZero(pc+1) = *actor(pc);
02990 idx(pc+1)++;
02991 *actor(pc) = ActorLink::cast(p);
02992
02993 #ifdef GECODE_AUDIT
02994 ActorLink** f = actor(pc);
02995 while (f < (pc == pc_max+1 ? base+entries : actorNonZero(pc+1)))
02996 if (*f == p)
02997 goto found;
02998 else
02999 f++;
03000 GECODE_NEVER;
03001 found: ;
03002 #endif
03003 }
03004
03005 template<class VIC>
03006 forceinline void
03007 VarImp<VIC>::enter(Space& home, Advisor* a) {
03008
03009 home.pc.p.n_sub += 1;
03010 if ((free_and_bits >> free_bits) == 0)
03011 resize(home);
03012 free_and_bits -= 1 << free_bits;
03013
03014
03015 base[entries++] = *actorNonZero(pc_max+1);
03016 *actorNonZero(pc_max+1) = a;
03017 }
03018
03019 template<class VIC>
03020 void
03021 VarImp<VIC>::resize(Space& home) {
03022 if (base == NULL) {
03023 assert((free_and_bits >> free_bits) == 0);
03024
03025 free_and_bits += 4 << free_bits;
03026 base = home.alloc<ActorLink*>(4);
03027 for (int i=0; i<pc_max+1; i++)
03028 u.idx[i] = 0;
03029 } else {
03030
03031 unsigned int n = degree();
03032
03033
03034
03035 ActorLink** s = static_cast<ActorLink**>(home.mm.subscriptions());
03036 unsigned int m =
03037 ((s <= base) && (base < s+home.pc.p.n_sub)) ?
03038 (n+4) : ((n+1)*3>>1);
03039 ActorLink** prop = home.alloc<ActorLink*>(m);
03040 free_and_bits += (m-n) << free_bits;
03041
03042 Heap::copy<ActorLink*>(prop, base, n);
03043 home.free<ActorLink*>(base,n);
03044 base = prop;
03045 }
03046 }
03047
03048 template<class VIC>
03049 void
03050 VarImp<VIC>::subscribe(Space& home, Propagator& p, PropCond pc,
03051 bool assigned, ModEvent me, bool schedule) {
03052 if (assigned) {
03053
03054 if (schedule)
03055 VarImp<VIC>::schedule(home,p,ME_GEN_ASSIGNED);
03056 } else {
03057 enter(home,&p,pc);
03058
03059 if (schedule && (pc != PC_GEN_ASSIGNED))
03060 VarImp<VIC>::schedule(home,p,me);
03061 }
03062 }
03063
03064 template<class VIC>
03065 forceinline void
03066 VarImp<VIC>::subscribe(Space& home, Advisor& a, bool assigned) {
03067 if (!assigned)
03068 enter(home,&a);
03069 }
03070
03071 template<class VIC>
03072 forceinline void
03073 VarImp<VIC>::remove(Space& home, Propagator* p, PropCond pc) {
03074 assert(pc <= pc_max);
03075 ActorLink* a = ActorLink::cast(p);
03076
03077 ActorLink** f = actor(pc);
03078 #ifdef GECODE_AUDIT
03079 while (f < actorNonZero(pc+1))
03080 if (*f == a)
03081 goto found;
03082 else
03083 f++;
03084 GECODE_NEVER;
03085 found: ;
03086 #else
03087 while (*f != a) f++;
03088 #endif
03089
03090 *f = *(actorNonZero(pc+1)-1);
03091 for (PropCond j = pc+1; j< pc_max+1; j++) {
03092 *(actorNonZero(j)-1) = *(actorNonZero(j+1)-1);
03093 idx(j)--;
03094 }
03095 *(actorNonZero(pc_max+1)-1) = base[entries-1];
03096 idx(pc_max+1)--;
03097 entries--;
03098 free_and_bits += 1 << free_bits;
03099 home.pc.p.n_sub -= 1;
03100 }
03101
03102 template<class VIC>
03103 forceinline void
03104 VarImp<VIC>::remove(Space& home, Advisor* a) {
03105
03106 ActorLink** f = actorNonZero(pc_max+1);
03107 #ifdef GECODE_AUDIT
03108 while (f < base+entries)
03109 if (*f == a)
03110 goto found;
03111 else
03112 f++;
03113 GECODE_NEVER;
03114 found: ;
03115 #else
03116 while (*f != a) f++;
03117 #endif
03118
03119 *f = base[--entries];
03120 free_and_bits += 1 << free_bits;
03121 home.pc.p.n_sub -= 1;
03122 }
03123
03124 template<class VIC>
03125 forceinline void
03126 VarImp<VIC>::cancel(Space& home, Propagator& p, PropCond pc, bool assigned) {
03127 if (!assigned)
03128 remove(home,&p,pc);
03129 }
03130
03131 template<class VIC>
03132 forceinline void
03133 VarImp<VIC>::cancel(Space& home, Advisor& a, bool assigned) {
03134 if (!assigned)
03135 remove(home,&a);
03136 }
03137
03138 template<class VIC>
03139 forceinline void
03140 VarImp<VIC>::cancel(Space& home) {
03141 unsigned int n_sub = degree();
03142 home.pc.p.n_sub -= n_sub;
03143 unsigned int n = (free_and_bits >> VIC::free_bits) + n_sub;
03144 home.free<ActorLink*>(base,n);
03145
03146 base = NULL;
03147
03148 entries = 0;
03149 }
03150
03151 template<class VIC>
03152 forceinline bool
03153 VarImp<VIC>::advise(Space& home, ModEvent me, Delta& d) {
03154
03155
03156
03157
03158
03159 ActorLink** la = actorNonZero(pc_max+1);
03160 ActorLink** le = base+entries;
03161 if (la == le)
03162 return true;
03163 d.me = me;
03164
03165
03166
03167 do {
03168 Advisor* a = Advisor::cast(*la);
03169 assert(!a->disposed());
03170 Propagator& p = a->propagator();
03171 switch (p.advise(home,*a,d)) {
03172 case ES_FIX:
03173 break;
03174 case ES_FAILED:
03175 p.pi.fail(home.gpi);
03176 return false;
03177 case ES_NOFIX:
03178 schedule(home,p,me);
03179 break;
03180 case ES_NOFIX_FORCE:
03181 schedule(home,p,me,true);
03182 break;
03183 default:
03184 GECODE_NEVER;
03185 }
03186 } while (++la < le);
03187 return true;
03188 }
03189
03190 template<class VIC>
03191 forceinline void
03192 VarImp<VIC>::update(VarImp<VIC>* x, ActorLink**& sub) {
03193
03194
03195
03196 x->base = base;
03197 x->u.idx[0] = u.idx[0];
03198 if (pc_max > 0 && sizeof(ActorLink**) > sizeof(unsigned int))
03199 x->u.idx[1] = u.idx[1];
03200
03201 ActorLink** f = x->base;
03202 unsigned int n = x->degree();
03203 ActorLink** t = sub;
03204 sub += n;
03205 base = t;
03206
03207 while (n >= 4) {
03208 n -= 4;
03209 t[0]=f[0]->prev(); t[1]=f[1]->prev();
03210 t[2]=f[2]->prev(); t[3]=f[3]->prev();
03211 t += 4; f += 4;
03212 }
03213 if (n >= 2) {
03214 n -= 2;
03215 t[0]=f[0]->prev(); t[1]=f[1]->prev();
03216 t += 2; f += 2;
03217 }
03218 if (n > 0) {
03219 t[0]=f[0]->prev();
03220 }
03221 }
03222
03223 template<class VIC>
03224 forceinline void
03225 VarImp<VIC>::update(Space& home, ActorLink**& sub) {
03226 VarImp<VIC>* x = static_cast<VarImp<VIC>*>(home.pc.c.vars_u[idx_c]);
03227 while (x != NULL) {
03228 VarImp<VIC>* n = x->next(); x->forward()->update(x,sub); x = n;
03229 }
03230 }
03231
03232
03233
03234
03235
03236
03237
03238 template<class VarType>
03239 VarDisposer<VarType>::VarDisposer(void) {
03240 #ifdef GECODE_HAS_VAR_DISPOSE
03241 Space::vd[VarType::idx_d] = this;
03242 #endif
03243 }
03244
03245 template<class VarType>
03246 void
03247 VarDisposer<VarType>::dispose(Space& home, VarImpBase* _x) {
03248 VarType* x = static_cast<VarType*>(_x);
03249 do {
03250 x->dispose(home); x = static_cast<VarType*>(x->next_d());
03251 } while (x != NULL);
03252 }
03253
03254
03255
03256
03257
03258 forceinline void
03259 StatusStatistics::reset(void) {
03260 propagate = 0;
03261 wmp = false;
03262 }
03263 forceinline
03264 StatusStatistics::StatusStatistics(void) {
03265 reset();
03266 }
03267 forceinline StatusStatistics&
03268 StatusStatistics::operator +=(const StatusStatistics& s) {
03269 propagate += s.propagate;
03270 wmp |= s.wmp;
03271 return *this;
03272 }
03273 forceinline StatusStatistics
03274 StatusStatistics::operator +(const StatusStatistics& s) {
03275 StatusStatistics t(s);
03276 return t += *this;
03277 }
03278
03279 forceinline void
03280 CloneStatistics::reset(void) {}
03281
03282 forceinline
03283 CloneStatistics::CloneStatistics(void) {
03284 reset();
03285 }
03286 forceinline CloneStatistics
03287 CloneStatistics::operator +(const CloneStatistics&) {
03288 CloneStatistics s;
03289 return s;
03290 }
03291 forceinline CloneStatistics&
03292 CloneStatistics::operator +=(const CloneStatistics&) {
03293 return *this;
03294 }
03295
03296 forceinline void
03297 CommitStatistics::reset(void) {}
03298
03299 forceinline
03300 CommitStatistics::CommitStatistics(void) {
03301 reset();
03302 }
03303 forceinline CommitStatistics
03304 CommitStatistics::operator +(const CommitStatistics&) {
03305 CommitStatistics s;
03306 return s;
03307 }
03308 forceinline CommitStatistics&
03309 CommitStatistics::operator +=(const CommitStatistics&) {
03310 return *this;
03311 }
03312
03313
03314
03315
03316
03317
03318 forceinline
03319 PropCost::PropCost(PropCost::ActualCost ac0) : ac(ac0) {}
03320
03321 forceinline PropCost
03322 PropCost::cost(PropCost::Mod m,
03323 PropCost::ActualCost lo, PropCost::ActualCost hi,
03324 unsigned int n) {
03325 if (n < 2)
03326 return (m == LO) ? AC_UNARY_LO : AC_UNARY_HI;
03327 else if (n == 2)
03328 return (m == LO) ? AC_BINARY_LO : AC_BINARY_HI;
03329 else if (n == 3)
03330 return (m == LO) ? AC_TERNARY_LO : AC_TERNARY_HI;
03331 else
03332 return (m == LO) ? lo : hi;
03333 }
03334
03335 forceinline PropCost
03336 PropCost::crazy(PropCost::Mod m, unsigned int n) {
03337 return cost(m,AC_CRAZY_LO,AC_CRAZY_HI,n);
03338 }
03339 forceinline PropCost
03340 PropCost::crazy(PropCost::Mod m, int n) {
03341 assert(n >= 0);
03342 return crazy(m,static_cast<unsigned int>(n));
03343 }
03344 forceinline PropCost
03345 PropCost::cubic(PropCost::Mod m, unsigned int n) {
03346 return cost(m,AC_CUBIC_LO,AC_CUBIC_HI,n);
03347 }
03348 forceinline PropCost
03349 PropCost::cubic(PropCost::Mod m, int n) {
03350 assert(n >= 0);
03351 return cubic(m,static_cast<unsigned int>(n));
03352 }
03353 forceinline PropCost
03354 PropCost::quadratic(PropCost::Mod m, unsigned int n) {
03355 return cost(m,AC_QUADRATIC_LO,AC_QUADRATIC_HI,n);
03356 }
03357 forceinline PropCost
03358 PropCost::quadratic(PropCost::Mod m, int n) {
03359 assert(n >= 0);
03360 return quadratic(m,static_cast<unsigned int>(n));
03361 }
03362 forceinline PropCost
03363 PropCost::linear(PropCost::Mod m, unsigned int n) {
03364 return cost(m,AC_LINEAR_LO,AC_LINEAR_HI,n);
03365 }
03366 forceinline PropCost
03367 PropCost::linear(PropCost::Mod m, int n) {
03368 assert(n >= 0);
03369 return linear(m,static_cast<unsigned int>(n));
03370 }
03371 forceinline PropCost
03372 PropCost::ternary(PropCost::Mod m) {
03373 return (m == LO) ? AC_TERNARY_LO : AC_TERNARY_HI;
03374 }
03375 forceinline PropCost
03376 PropCost::binary(PropCost::Mod m) {
03377 return (m == LO) ? AC_BINARY_LO : AC_BINARY_HI;
03378 }
03379 forceinline PropCost
03380 PropCost::unary(PropCost::Mod m) {
03381 return (m == LO) ? AC_UNARY_LO : AC_UNARY_HI;
03382 }
03383
03384
03385
03386
03387
03388 forceinline
03389 Space::Propagators::Propagators(const Space& home0)
03390 : home(home0), q(home.pc.p.active) {
03391 while (q >= &home.pc.p.queue[0]) {
03392 if (q->next() != q) {
03393 c = q->next(); e = q; q--;
03394 return;
03395 }
03396 q--;
03397 }
03398 q = NULL;
03399 if (!home.pl.empty()) {
03400 c = Propagator::cast(home.pl.next());
03401 e = Propagator::cast(&home.pl);
03402 } else {
03403 c = e = NULL;
03404 }
03405 }
03406 forceinline bool
03407 Space::Propagators::operator ()(void) const {
03408 return c != NULL;
03409 }
03410 forceinline void
03411 Space::Propagators::operator ++(void) {
03412 c = c->next();
03413 if (c == e) {
03414 if (q == NULL) {
03415 c = NULL;
03416 } else {
03417 while (q >= &home.pc.p.queue[0]) {
03418 if (q->next() != q) {
03419 c = q->next(); e = q; q--;
03420 return;
03421 }
03422 q--;
03423 }
03424 q = NULL;
03425 if (!home.pl.empty()) {
03426 c = Propagator::cast(home.pl.next());
03427 e = Propagator::cast(&home.pl);
03428 } else {
03429 c = NULL;
03430 }
03431 }
03432 }
03433 }
03434 forceinline const Propagator&
03435 Space::Propagators::propagator(void) const {
03436 return *Propagator::cast(c);
03437 }
03438
03439 forceinline
03440 Space::Branchers::Branchers(const Space& home)
03441 : c(Brancher::cast(home.bl.next())), e(&home.bl) {}
03442 forceinline bool
03443 Space::Branchers::operator ()(void) const {
03444 return c != e;
03445 }
03446 forceinline void
03447 Space::Branchers::operator ++(void) {
03448 c = c->next();
03449 }
03450 forceinline const Brancher&
03451 Space::Branchers::brancher(void) const {
03452 return *Brancher::cast(c);
03453 }
03454
03455
03456
03457
03458
03459 template<class T>
03460 forceinline T&
03461 Space::construct(void) {
03462 return alloc<T>(1);
03463 }
03464 template<class T, typename A1>
03465 forceinline T&
03466 Space::construct(A1 const& a1) {
03467 T& t = *static_cast<T*>(ralloc(sizeof(T)));
03468 new (&t) T(a1);
03469 return t;
03470 }
03471 template<class T, typename A1, typename A2>
03472 forceinline T&
03473 Space::construct(A1 const& a1, A2 const& a2) {
03474 T& t = *static_cast<T*>(ralloc(sizeof(T)));
03475 new (&t) T(a1,a2);
03476 return t;
03477 }
03478 template<class T, typename A1, typename A2, typename A3>
03479 forceinline T&
03480 Space::construct(A1 const& a1, A2 const& a2, A3 const& a3) {
03481 T& t = *static_cast<T*>(ralloc(sizeof(T)));
03482 new (&t) T(a1,a2,a3);
03483 return t;
03484 }
03485 template<class T, typename A1, typename A2, typename A3, typename A4>
03486 forceinline T&
03487 Space::construct(A1 const& a1, A2 const& a2, A3 const& a3, A4 const& a4) {
03488 T& t = *static_cast<T*>(ralloc(sizeof(T)));
03489 new (&t) T(a1,a2,a3,a4);
03490 return t;
03491 }
03492 template<class T, typename A1, typename A2, typename A3, typename A4, typename A5>
03493 forceinline T&
03494 Space::construct(A1 const& a1, A2 const& a2, A3 const& a3, A4 const& a4, A5 const& a5) {
03495 T& t = *static_cast<T*>(ralloc(sizeof(T)));
03496 new (&t) T(a1,a2,a3,a4,a5);
03497 return t;
03498 }
03499
03500 }
03501
03502