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 #include <iostream>
00048
00049 namespace Gecode {
00050
00051 class Space;
00052
00061
00062 typedef int ModEvent;
00063
00065 const ModEvent ME_GEN_FAILED = -1;
00067 const ModEvent ME_GEN_NONE = 0;
00069 const ModEvent ME_GEN_ASSIGNED = 1;
00070
00072 typedef int PropCond;
00074 const PropCond PC_GEN_NONE = -1;
00076 const PropCond PC_GEN_ASSIGNED = 0;
00078
00089 typedef int ModEventDelta;
00090
00091 }
00092
00093 #include <gecode/kernel/var-type.hpp>
00094
00095 namespace Gecode {
00096
00098 class NoIdxVarImpConf {
00099 public:
00101 static const int idx_c = -1;
00103 static const int idx_d = -1;
00105 static const PropCond pc_max = PC_GEN_ASSIGNED;
00107 static const int free_bits = 0;
00109 static const int med_fst = 0;
00111 static const int med_lst = 0;
00113 static const int med_mask = 0;
00115 static Gecode::ModEvent me_combine(ModEvent me1, ModEvent me2);
00117 static bool med_update(ModEventDelta& med, ModEvent me);
00118 };
00119
00120 forceinline ModEvent
00121 NoIdxVarImpConf::me_combine(ModEvent, ModEvent) {
00122 GECODE_NEVER; return 0;
00123 }
00124 forceinline bool
00125 NoIdxVarImpConf::med_update(ModEventDelta&, ModEvent) {
00126 GECODE_NEVER; return false;
00127 }
00128
00129
00130
00131
00132
00133
00134 class ActorLink;
00135 class Actor;
00136 class Propagator;
00137 class SubscribedPropagators;
00138 class LocalObject;
00139 class Advisor;
00140 class AFC;
00141 class Choice;
00142 class Brancher;
00143 class Group;
00144 class PropagatorGroup;
00145 class BrancherGroup;
00146 class PostInfo;
00147 class ViewTraceInfo;
00148 class PropagateTraceInfo;
00149 class CommitTraceInfo;
00150 class TraceRecorder;
00151 class TraceFilter;
00152 class Tracer;
00153
00154 template<class A> class Council;
00155 template<class A> class Advisors;
00156 template<class VIC> class VarImp;
00157
00158
00159
00160
00161
00162
00163
00171 class VarImpBase {};
00172
00179 class GECODE_VTABLE_EXPORT VarImpDisposerBase {
00180 public:
00182 GECODE_KERNEL_EXPORT virtual void dispose(Space& home, VarImpBase* x);
00184 GECODE_KERNEL_EXPORT virtual ~VarImpDisposerBase(void);
00185 };
00186
00193 template<class VarImp>
00194 class VarImpDisposer : public VarImpDisposerBase {
00195 public:
00197 VarImpDisposer(void);
00199 virtual void dispose(Space& home, VarImpBase* x);
00200 };
00201
00203 class Delta {
00204 template<class VIC> friend class VarImp;
00205 private:
00207 ModEvent me;
00208 };
00209
00217 template<class VIC>
00218 class VarImp : public VarImpBase {
00219 friend class Space;
00220 friend class Propagator;
00221 template<class VarImp> friend class VarImpDisposer;
00222 friend class SubscribedPropagators;
00223 private:
00224 union {
00232 ActorLink** base;
00241 VarImp<VIC>* fwd;
00242 } b;
00243
00245 static const int idx_c = VIC::idx_c;
00247 static const int idx_d = VIC::idx_d;
00249 static const int free_bits = VIC::free_bits;
00251 unsigned int entries;
00253 unsigned int free_and_bits;
00255 static const Gecode::PropCond pc_max = VIC::pc_max;
00256 #ifdef GECODE_HAS_CBS
00257
00258 const unsigned var_id;
00259 #endif
00260
00261 union {
00272 unsigned int idx[pc_max+1];
00274 VarImp<VIC>* next;
00275 } u;
00276
00278 ActorLink** actor(PropCond pc);
00280 ActorLink** actorNonZero(PropCond pc);
00282 unsigned int& idx(PropCond pc);
00284 unsigned int idx(PropCond pc) const;
00285
00292 void update(VarImp* x, ActorLink**& sub);
00299 static void update(Space& home, ActorLink**& sub);
00300
00302 void enter(Space& home, Propagator* p, PropCond pc);
00304 void enter(Space& home, Advisor* a);
00306 void resize(Space& home);
00308 void remove(Space& home, Propagator* p, PropCond pc);
00310 void remove(Space& home, Advisor* a);
00311
00312
00313 protected:
00315 void cancel(Space& home);
00321 bool advise(Space& home, ModEvent me, Delta& d);
00322 private:
00324 void _fail(Space& home);
00325 protected:
00327 ModEvent fail(Space& home);
00328 #ifdef GECODE_HAS_VAR_DISPOSE
00329
00330 static VarImp<VIC>* vars_d(Space& home);
00332 static void vars_d(Space& home, VarImp<VIC>* x);
00333 #endif
00334
00335 public:
00337 VarImp(Space& home);
00339 VarImp(void);
00340
00341 #ifdef GECODE_HAS_CBS
00342
00343 unsigned int id(void) const;
00344 #endif
00345
00347
00348
00360 void subscribe(Space& home, Propagator& p, PropCond pc,
00361 bool assigned, ModEvent me, bool schedule);
00363 void cancel(Space& home, Propagator& p, PropCond pc);
00372 void subscribe(Space& home, Advisor& a, bool assigned, bool fail);
00374 void cancel(Space& home, Advisor& a, bool fail);
00375
00382 unsigned int degree(void) const;
00389 double afc(void) const;
00391
00393
00394
00395 VarImp(Space& home, VarImp& x);
00397 bool copied(void) const;
00399 VarImp* forward(void) const;
00401 VarImp* next(void) const;
00403
00405
00406
00413 static void schedule(Space& home, Propagator& p, ModEvent me,
00414 bool force = false);
00422 static void reschedule(Space& home, Propagator& p, PropCond pc,
00423 bool assigned, ModEvent me);
00425 static ModEvent me(const ModEventDelta& med);
00427 static ModEventDelta med(ModEvent me);
00429 static ModEvent me_combine(ModEvent me1, ModEvent me2);
00431
00433
00434
00435 static ModEvent modevent(const Delta& d);
00437
00439
00440
00441 unsigned int bits(void) const;
00443 unsigned int& bits(void);
00445
00446 protected:
00448 void schedule(Space& home, PropCond pc1, PropCond pc2, ModEvent me);
00449
00450 public:
00452
00453
00454 static void* operator new(size_t,Space&);
00456 static void operator delete(void*,Space&);
00458 static void operator delete(void*);
00460 };
00461
00462
00471 enum ExecStatus {
00472 __ES_SUBSUMED = -2,
00473 ES_FAILED = -1,
00474 ES_NOFIX = 0,
00475 ES_OK = 0,
00476 ES_FIX = 1,
00477 ES_NOFIX_FORCE = 2,
00478 __ES_PARTIAL = 2
00479 };
00480
00485 class PropCost {
00486 friend class Space;
00487 public:
00489 enum ActualCost {
00490 AC_RECORD = 0,
00491 AC_CRAZY_LO = 1,
00492 AC_CRAZY_HI = 1,
00493 AC_CUBIC_LO = 1,
00494 AC_CUBIC_HI = 1,
00495 AC_QUADRATIC_LO = 2,
00496 AC_QUADRATIC_HI = 2,
00497 AC_LINEAR_HI = 3,
00498 AC_LINEAR_LO = 4,
00499 AC_TERNARY_HI = 4,
00500 AC_BINARY_HI = 5,
00501 AC_TERNARY_LO = 5,
00502 AC_BINARY_LO = 6,
00503 AC_UNARY_LO = 6,
00504 AC_UNARY_HI = 6,
00505 AC_MAX = 6
00506 };
00508 ActualCost ac;
00509 public:
00511 enum Mod {
00512 LO,
00513 HI
00514 };
00515 private:
00517 static PropCost cost(Mod m, ActualCost lo, ActualCost hi, unsigned int n);
00519 PropCost(ActualCost ac);
00520 public:
00522 static PropCost record(void);
00524 static PropCost crazy(PropCost::Mod m, unsigned int n);
00526 static PropCost crazy(PropCost::Mod m, int n);
00528 static PropCost cubic(PropCost::Mod m, unsigned int n);
00530 static PropCost cubic(PropCost::Mod m, int n);
00532 static PropCost quadratic(PropCost::Mod m, unsigned int n);
00534 static PropCost quadratic(PropCost::Mod m, int n);
00536 static PropCost linear(PropCost::Mod m, unsigned int n);
00538 static PropCost linear(PropCost::Mod m, int n);
00540 static PropCost ternary(PropCost::Mod m);
00542 static PropCost binary(PropCost::Mod m);
00544 static PropCost unary(PropCost::Mod m);
00545 };
00546
00547
00552 enum ActorProperty {
00561 AP_DISPOSE = (1 << 0),
00567 AP_WEAKLY = (1 << 1),
00572 AP_VIEW_TRACE = (1 << 2),
00577 AP_TRACE = (1 << 3)
00578 };
00579
00580
00588 class ActorLink {
00589 friend class Actor;
00590 friend class Propagator;
00591 friend class Advisor;
00592 friend class Brancher;
00593 friend class LocalObject;
00594 friend class Space;
00595 template<class VIC> friend class VarImp;
00596 private:
00597 ActorLink* _next; ActorLink* _prev;
00598 public:
00600
00601 ActorLink* prev(void) const; void prev(ActorLink*);
00602 ActorLink* next(void) const; void next(ActorLink*);
00603 ActorLink** next_ref(void);
00605
00607 void init(void);
00609 void unlink(void);
00611 void head(ActorLink* al);
00613 void tail(ActorLink* al);
00615 bool empty(void) const;
00617 template<class T> static ActorLink* cast(T* a);
00619 template<class T> static const ActorLink* cast(const T* a);
00620 };
00621
00622
00627 class GECODE_VTABLE_EXPORT Actor : private ActorLink {
00628 friend class ActorLink;
00629 friend class Space;
00630 friend class Propagator;
00631 friend class Advisor;
00632 friend class Brancher;
00633 friend class LocalObject;
00634 template<class VIC> friend class VarImp;
00635 template<class A> friend class Council;
00636 private:
00638 static Actor* cast(ActorLink* al);
00640 static const Actor* cast(const ActorLink* al);
00642 GECODE_KERNEL_EXPORT static Actor* sentinel;
00643 public:
00645 virtual Actor* copy(Space& home) = 0;
00646
00648
00649
00650 GECODE_KERNEL_EXPORT
00651 virtual size_t dispose(Space& home);
00653 static void* operator new(size_t s, Space& home);
00655 static void operator delete(void* p, Space& home);
00657 public:
00659 GECODE_KERNEL_EXPORT virtual ~Actor(void);
00661 static void* operator new(size_t s);
00663 static void operator delete(void* p);
00664 };
00665
00666 class Home;
00667
00672 class Group {
00673 friend class Home;
00674 friend class Propagator;
00675 friend class Brancher;
00676 friend class ViewTraceInfo;
00677 friend class PropagateTraceInfo;
00678 friend class CommitTraceInfo;
00679 protected:
00681 static const unsigned int GROUPID_ALL = 0U;
00683 static const unsigned int GROUPID_DEF = 1U;
00685 static const unsigned int GROUPID_MAX = UINT_MAX >> 2;
00687 unsigned int gid;
00689 GECODE_KERNEL_EXPORT
00690 static unsigned int next;
00692 GECODE_KERNEL_EXPORT
00693 static Support::Mutex m;
00695 Group(unsigned int gid0);
00696 public:
00698
00699
00700 GECODE_KERNEL_EXPORT
00701 Group(void);
00703 Group(const Group& g);
00705 Group& operator =(const Group& g);
00707 unsigned int id(void) const;
00709 bool in(Group a) const;
00711 bool in(void) const;
00713
00714 GECODE_KERNEL_EXPORT
00715 static Group all;
00717 GECODE_KERNEL_EXPORT
00718 static Group def;
00719 };
00720
00725 class PropagatorGroup : public Group {
00726 friend class Propagator;
00727 friend class ViewTraceInfo;
00728 friend class PropagateTraceInfo;
00729 protected:
00731 PropagatorGroup(unsigned int gid);
00732 public:
00734
00735
00736 PropagatorGroup(void);
00738 PropagatorGroup(const PropagatorGroup& g);
00740 PropagatorGroup& operator =(const PropagatorGroup& g);
00742 Home operator ()(Space& home);
00744
00745
00746
00747 GECODE_KERNEL_EXPORT
00748 PropagatorGroup& move(Space& home, PropagatorGroup g);
00750 PropagatorGroup& move(Space& home, Propagator& p);
00757 GECODE_KERNEL_EXPORT
00758 PropagatorGroup& move(Space& home, unsigned int id);
00760
00761
00762
00763 bool operator ==(PropagatorGroup g) const;
00765 bool operator !=(PropagatorGroup g) const;
00767 GECODE_KERNEL_EXPORT
00768 unsigned int size(Space& home) const;
00770 GECODE_KERNEL_EXPORT
00771 void kill(Space& home);
00773 GECODE_KERNEL_EXPORT
00774 void disable(Space& home);
00781 GECODE_KERNEL_EXPORT
00782 void enable(Space& home, bool s=true);
00784
00785 GECODE_KERNEL_EXPORT
00786 static PropagatorGroup all;
00788 GECODE_KERNEL_EXPORT
00789 static PropagatorGroup def;
00790 };
00791
00796 class BrancherGroup : public Group {
00797 friend class Brancher;
00798 protected:
00800 BrancherGroup(unsigned int gid);
00801 public:
00803
00804
00805 BrancherGroup(void);
00807 BrancherGroup(const BrancherGroup& g);
00809 BrancherGroup& operator =(const BrancherGroup& g);
00811 Home operator ()(Space& home);
00813
00814
00815
00816 GECODE_KERNEL_EXPORT
00817 BrancherGroup& move(Space& home, BrancherGroup g);
00819 BrancherGroup& move(Space& home, Brancher& b);
00826 GECODE_KERNEL_EXPORT
00827 BrancherGroup& move(Space& home, unsigned int id);
00829
00830
00831
00832 bool operator ==(BrancherGroup g) const;
00834 bool operator !=(BrancherGroup g) const;
00836 GECODE_KERNEL_EXPORT
00837 unsigned int size(Space& home) const;
00839 GECODE_KERNEL_EXPORT
00840 void kill(Space& home);
00842
00843 GECODE_KERNEL_EXPORT
00844 static BrancherGroup all;
00846 GECODE_KERNEL_EXPORT
00847 static BrancherGroup def;
00848 };
00849
00853 class Home {
00854 friend class PostInfo;
00855 protected:
00857 Space& s;
00859 Propagator* p;
00861 PropagatorGroup pg;
00863 BrancherGroup bg;
00864 public:
00866
00867
00868 Home(Space& s, Propagator* p=NULL,
00869 PropagatorGroup pg=PropagatorGroup::def,
00870 BrancherGroup bg=BrancherGroup::def);
00872 Home& operator =(const Home& h);
00874 operator Space&(void);
00876
00877
00878
00879 Home operator ()(Propagator& p);
00881 Home operator ()(PropagatorGroup pg);
00883 Home operator ()(BrancherGroup bg);
00885 Propagator* propagator(void) const;
00887 PropagatorGroup propagatorgroup(void) const;
00889 BrancherGroup branchergroup(void) const;
00891
00892
00893
00894 bool failed(void) const;
00896 void fail(void);
00898 void notice(Actor& a, ActorProperty p, bool duplicate=false);
00900 };
00901
00905 class ViewTraceInfo {
00906 friend class Space;
00907 friend class PostInfo;
00908 public:
00910 enum What {
00912 PROPAGATOR = 0,
00914 BRANCHER = 1,
00916 POST = 2,
00918 OTHER = 3
00919 };
00920 protected:
00922 ptrdiff_t who;
00924 void propagator(Propagator& p);
00926 void brancher(Brancher& b);
00928 void post(PropagatorGroup g);
00930 void other(void);
00931 public:
00933 What what(void) const;
00935 const Propagator& propagator(void) const;
00937 const Brancher& brancher(void) const;
00939 PropagatorGroup post(void) const;
00940 };
00941
00945 class PostInfo {
00946 protected:
00948 Space& h;
00949 public:
00951 PostInfo(Home home);
00953 ~PostInfo(void);
00954 };
00955
00959 class PropagateTraceInfo {
00960 friend class Space;
00961 public:
00963 enum Status {
00964 FIX,
00965 NOFIX,
00966 FAILED,
00967 SUBSUMED
00968 };
00969 protected:
00971 unsigned int i;
00973 PropagatorGroup g;
00975 const Propagator* p;
00977 Status s;
00979 PropagateTraceInfo(unsigned int i, PropagatorGroup g,
00980 const Propagator* p, Status s);
00981 public:
00983 unsigned int id(void) const;
00985 PropagatorGroup group(void) const;
00987 const Propagator* propagator(void) const;
00989 Status status(void) const;
00990 };
00991
00995 class CommitTraceInfo {
00996 friend class Space;
00997 protected:
00999 const Brancher& b;
01001 const Choice& c;
01003 unsigned int a;
01005 CommitTraceInfo(const Brancher& b, const Choice& c, unsigned int a);
01006 public:
01008 unsigned int id(void) const;
01010 BrancherGroup group(void) const;
01012 const Brancher& brancher(void) const;
01014 const Choice& choice(void) const;
01016 unsigned int alternative(void) const;
01017 };
01018
01023 class GECODE_VTABLE_EXPORT Propagator : public Actor {
01024 friend class ActorLink;
01025 friend class Space;
01026 template<class VIC> friend class VarImp;
01027 friend class Advisor;
01028 template<class A> friend class Council;
01029 friend class SubscribedPropagators;
01030 friend class PropagatorGroup;
01031 private:
01032 union {
01034 ModEventDelta med;
01036 size_t size;
01038 Gecode::ActorLink* advisors;
01039 } u;
01041 void* gpi_disabled;
01043 static Propagator* cast(ActorLink* al);
01045 static const Propagator* cast(const ActorLink* al);
01047 void disable(Space& home);
01049 void enable(Space& home);
01050 protected:
01052 Propagator(Home home);
01054 Propagator(Space& home, Propagator& p);
01056 Propagator* fwd(void) const;
01058 Kernel::GPI::Info& gpi(void);
01059
01060 public:
01062
01063
01071 virtual void reschedule(Space& home) = 0;
01095 virtual ExecStatus propagate(Space& home, const ModEventDelta& med) = 0;
01097 virtual PropCost cost(const Space& home, const ModEventDelta& med) const = 0;
01105 ModEventDelta modeventdelta(void) const;
01141 GECODE_KERNEL_EXPORT
01142 virtual ExecStatus advise(Space& home, Advisor& a, const Delta& d);
01144 GECODE_KERNEL_EXPORT
01145 virtual void advise(Space& home, Advisor& a);
01147
01148
01149
01150 double afc(void) const;
01152 #ifdef GECODE_HAS_CBS
01153
01154
01155
01161
01162 typedef std::function<void(unsigned int prop_id, unsigned int var_id,
01163 int val, double dens)> SendMarginal;
01164 virtual void solndistrib(Space& home, SendMarginal send) const;
01172
01173 typedef std::function<bool(unsigned int var_id)> InDecision;
01174 virtual void domainsizesum(InDecision in, unsigned int& size,
01175 unsigned int& size_b) const;
01177 #endif
01178
01179
01180
01181 unsigned int id(void) const;
01183 PropagatorGroup group(void) const;
01185 void group(PropagatorGroup g);
01187 bool disabled(void) const;
01189 };
01190
01191
01199 template<class A>
01200 class Council {
01201 friend class Advisor;
01202 friend class Advisors<A>;
01203 private:
01205 mutable ActorLink* advisors;
01206 public:
01208 Council(void);
01210 Council(Space& home);
01212 bool empty(void) const;
01214 void update(Space& home, Council<A>& c);
01216 void dispose(Space& home);
01217 };
01218
01219
01224 template<class A>
01225 class Advisors {
01226 private:
01228 ActorLink* a;
01229 public:
01231 Advisors(const Council<A>& c);
01233 bool operator ()(void) const;
01235 void operator ++(void);
01237 A& advisor(void) const;
01238 };
01239
01240
01251 class Advisor : private ActorLink {
01252 template<class VIC> friend class VarImp;
01253 template<class A> friend class Council;
01254 template<class A> friend class Advisors;
01255 friend class SubscribedPropagators;
01256 private:
01258 bool disposed(void) const;
01260 static Advisor* cast(ActorLink* al);
01262 static const Advisor* cast(const ActorLink* al);
01263 protected:
01265 Propagator& propagator(void) const;
01266 public:
01268 template<class A>
01269 Advisor(Space& home, Propagator& p, Council<A>& c);
01271 Advisor(Space& home, Advisor& a);
01273 const ViewTraceInfo& operator ()(const Space& home) const;
01274
01276
01277
01278 template<class A>
01279 void dispose(Space& home, Council<A>& c);
01281 static void* operator new(size_t s, Space& home);
01283 static void operator delete(void* p, Space& home);
01285 private:
01286 #ifndef __GNUC__
01287
01288 static void operator delete(void* p);
01289 #endif
01290
01291 static void* operator new(size_t s);
01292 };
01293
01294
01299 class GECODE_VTABLE_EXPORT NGL {
01300 private:
01302 void* nl;
01303 public:
01305 enum Status {
01306 FAILED,
01307 SUBSUMED,
01308 NONE
01309 };
01311 NGL(void);
01313 NGL(Space& home);
01315 NGL(Space& home, NGL& ngl);
01317 virtual void subscribe(Space& home, Propagator& p) = 0;
01319 virtual void cancel(Space& home, Propagator& p) = 0;
01321 virtual void reschedule(Space& home, Propagator& p) = 0;
01323 virtual NGL::Status status(const Space& home) const = 0;
01325 virtual ExecStatus prune(Space& home) = 0;
01327 virtual NGL* copy(Space& home) = 0;
01329 GECODE_KERNEL_EXPORT
01330 virtual bool notice(void) const;
01332 virtual size_t dispose(Space& home);
01334
01335
01336 bool leaf(void) const;
01338 NGL* next(void) const;
01340 void leaf(bool l);
01342 void next(NGL* n);
01344 NGL* add(NGL* n, bool l);
01346
01347
01348
01349 static void* operator new(size_t s, Space& home);
01351 static void operator delete(void* s, Space& home);
01353 static void operator delete(void* p);
01355 public:
01357 GECODE_KERNEL_EXPORT virtual ~NGL(void);
01359 static void* operator new(size_t s);
01360 };
01361
01371 class GECODE_VTABLE_EXPORT Choice : public HeapAllocated {
01372 friend class Space;
01373 private:
01374 unsigned int bid;
01375 unsigned int alt;
01376
01378 unsigned int id(void) const;
01379 protected:
01381 Choice(const Brancher& b, const unsigned int a);
01382 public:
01384 unsigned int alternatives(void) const;
01386 GECODE_KERNEL_EXPORT virtual ~Choice(void);
01388 GECODE_KERNEL_EXPORT
01389 virtual void archive(Archive& e) const;
01390 };
01391
01401 class GECODE_VTABLE_EXPORT Brancher : public Actor {
01402 friend class ActorLink;
01403 friend class Space;
01404 friend class Choice;
01405 private:
01407 unsigned int bid;
01409 unsigned int gid;
01411 static Brancher* cast(ActorLink* al);
01413 static const Brancher* cast(const ActorLink* al);
01414 protected:
01416 Brancher(Home home);
01418 Brancher(Space& home, Brancher& b);
01419 public:
01421
01422
01430 virtual bool status(const Space& home) const = 0;
01438 virtual const Choice* choice(Space& home) = 0;
01440 virtual const Choice* choice(const Space& home, Archive& e) = 0;
01447 virtual ExecStatus commit(Space& home, const Choice& c,
01448 unsigned int a) = 0;
01462 GECODE_KERNEL_EXPORT
01463 virtual NGL* ngl(Space& home, const Choice& c, unsigned int a) const;
01471 GECODE_KERNEL_EXPORT
01472 virtual void print(const Space& home, const Choice& c, unsigned int a,
01473 std::ostream& o) const;
01475
01476
01477
01478 unsigned int id(void) const;
01480 BrancherGroup group(void) const;
01482 void group(BrancherGroup g);
01484 };
01485
01492 class LocalObject : public Actor {
01493 friend class ActorLink;
01494 friend class Space;
01495 friend class LocalHandle;
01496 protected:
01498 LocalObject(Home home);
01500 LocalObject(Space& home, LocalObject& l);
01502 static LocalObject* cast(ActorLink* al);
01504 static const LocalObject* cast(const ActorLink* al);
01505 private:
01507 GECODE_KERNEL_EXPORT void fwdcopy(Space& home);
01508 public:
01510 LocalObject* fwd(Space& home);
01511 };
01512
01517 class LocalHandle {
01518 private:
01520 LocalObject* o;
01521 protected:
01523 LocalHandle(void);
01525 LocalHandle(LocalObject* lo);
01527 LocalHandle(const LocalHandle& lh);
01528 public:
01530 LocalHandle& operator =(const LocalHandle& lh);
01532 void update(Space& home, LocalHandle& lh);
01534 ~LocalHandle(void);
01535 protected:
01537 LocalObject* object(void) const;
01539 void object(LocalObject* n);
01540 };
01541
01542
01547 class GECODE_VTABLE_EXPORT NoGoods {
01548 protected:
01550 unsigned long int n;
01551 public:
01553 NoGoods(void);
01555 GECODE_KERNEL_EXPORT
01556 virtual void post(Space& home) const;
01558 unsigned long int ng(void) const;
01560 void ng(unsigned long int n);
01562 virtual ~NoGoods(void);
01564 GECODE_KERNEL_EXPORT
01565 static NoGoods eng;
01566 };
01567
01572 class GECODE_VTABLE_EXPORT MetaInfo {
01573 public:
01575 enum Type {
01577 RESTART,
01579 PORTFOLIO
01580 };
01581 protected:
01583 const Type t;
01585
01586
01587 const unsigned long int r;
01589 const unsigned long int s;
01591 const unsigned long int f;
01593 const Space* l;
01595 const NoGoods& ng;
01597
01598
01599
01600 const unsigned int a;
01602 public:
01604
01605
01606 MetaInfo(unsigned long int r,
01607 unsigned long int s,
01608 unsigned long int f,
01609 const Space* l,
01610 NoGoods& ng);
01612 MetaInfo(unsigned int a);
01614
01615 Type type(void) const;
01617
01618
01619 unsigned long int restart(void) const;
01621 unsigned long int solution(void) const;
01623 unsigned long int fail(void) const;
01625 const Space* last(void) const;
01627 const NoGoods& nogoods(void) const;
01629
01630
01631
01632 unsigned int asset(void) const;
01634 };
01635
01640 enum SpaceStatus {
01641 SS_FAILED,
01642 SS_SOLVED,
01643 SS_BRANCH
01644 };
01645
01650 class StatusStatistics {
01651 public:
01653 unsigned long int propagate;
01655 StatusStatistics(void);
01657 void reset(void);
01659 StatusStatistics operator +(const StatusStatistics& s);
01661 StatusStatistics& operator +=(const StatusStatistics& s);
01662 };
01663
01668 class CloneStatistics {
01669 public:
01671 CloneStatistics(void);
01673 void reset(void);
01675 CloneStatistics operator +(const CloneStatistics& s);
01677 CloneStatistics& operator +=(const CloneStatistics& s);
01678 };
01679
01684 class CommitStatistics {
01685 public:
01687 CommitStatistics(void);
01689 void reset(void);
01691 CommitStatistics operator +(const CommitStatistics& s);
01693 CommitStatistics& operator +=(const CommitStatistics& s);
01694 };
01695
01696
01697
01701 class GECODE_VTABLE_EXPORT Space : public HeapAllocated {
01702 friend class Actor;
01703 friend class Propagator;
01704 friend class PropagatorGroup;
01705 friend class Propagators;
01706 friend class Brancher;
01707 friend class BrancherGroup;
01708 friend class Branchers;
01709 friend class Advisor;
01710 template <class A> friend class Council;
01711 template<class VIC> friend class VarImp;
01712 template<class VarImp> friend class VarImpDisposer;
01713 friend class LocalObject;
01714 friend class Region;
01715 friend class AFC;
01716 friend class PostInfo;
01717 friend GECODE_KERNEL_EXPORT
01718 void trace(Home home, TraceFilter tf, int te, Tracer& t);
01719 private:
01721 Kernel::SharedSpaceData ssd;
01723 Kernel::MemoryManager mm;
01724 #ifdef GECODE_HAS_CBS
01725
01726 unsigned int var_id_counter;
01727 #endif
01728
01729 ActorLink pl;
01731 ActorLink bl;
01737 Brancher* b_status;
01749 Brancher* b_commit;
01751 Brancher* brancher(unsigned int id);
01752
01754 void kill(Brancher& b);
01756 void kill(Propagator& p);
01757
01759 GECODE_KERNEL_EXPORT
01760 void kill_brancher(unsigned int id);
01761
01763 static const unsigned reserved_bid = 0U;
01764
01766 static const unsigned int sc_bits = 2;
01768 static const unsigned int sc_fast = 0;
01770 static const unsigned int sc_disabled = 1;
01772 static const unsigned int sc_trace = 2;
01773
01774 union {
01776 struct {
01789 ActorLink* active;
01791 ActorLink queue[PropCost::AC_MAX+1];
01798 unsigned int bid_sc;
01800 unsigned int n_sub;
01802 ViewTraceInfo vti;
01803 } p;
01805 struct {
01807 VarImpBase* vars_u[AllVarConf::idx_c];
01809 VarImpBase* vars_noidx;
01811 LocalObject* local;
01812 } c;
01813 } pc;
01815 void enqueue(Propagator* p);
01820 #ifdef GECODE_HAS_VAR_DISPOSE
01821
01822 GECODE_KERNEL_EXPORT static VarImpDisposerBase* vd[AllVarConf::idx_d];
01824 VarImpBase* _vars_d[AllVarConf::idx_d];
01826 template<class VIC> VarImpBase* vars_d(void) const;
01828 template<class VIC> void vars_d(VarImpBase* x);
01829 #endif
01830
01831 void update(ActorLink** sub);
01833
01835 Actor** d_fst;
01837 Actor** d_cur;
01839 Actor** d_lst;
01840
01842 GECODE_KERNEL_EXPORT static StatusStatistics unused_status;
01844 GECODE_KERNEL_EXPORT static CloneStatistics unused_clone;
01846 GECODE_KERNEL_EXPORT static CommitStatistics unused_commit;
01847
01861 GECODE_KERNEL_EXPORT Space* _clone(void);
01862
01895 GECODE_KERNEL_EXPORT
01896 void _commit(const Choice& c, unsigned int a);
01897
01928 GECODE_KERNEL_EXPORT
01929 void _trycommit(const Choice& c, unsigned int a);
01930
01932 GECODE_KERNEL_EXPORT
01933 TraceRecorder* findtracerecorder(void);
01934
01941 GECODE_KERNEL_EXPORT
01942 void ap_notice_dispose(Actor* a, bool d);
01949 GECODE_KERNEL_EXPORT
01950 void ap_ignore_dispose(Actor* a, bool d);
01951
01952 public:
01957 GECODE_KERNEL_EXPORT
01958 Space(void);
01967 GECODE_KERNEL_EXPORT
01968 Space(Space& s);
01973 GECODE_KERNEL_EXPORT
01974 virtual ~Space(void);
01981 virtual Space* copy(void) = 0;
01992 GECODE_KERNEL_EXPORT virtual void constrain(const Space& best);
02016 GECODE_KERNEL_EXPORT
02017 virtual bool master(const MetaInfo& mi);
02043 GECODE_KERNEL_EXPORT
02044 virtual bool slave(const MetaInfo& mi);
02045
02046
02047
02048
02049
02050
02062 GECODE_KERNEL_EXPORT
02063 SpaceStatus status(StatusStatistics& stat=unused_status);
02064
02096 GECODE_KERNEL_EXPORT
02097 const Choice* choice(void);
02098
02108 GECODE_KERNEL_EXPORT
02109 const Choice* choice(Archive& e) const;
02110
02126 Space* clone(CloneStatistics& stat=unused_clone) const;
02127
02162 void commit(const Choice& c, unsigned int a,
02163 CommitStatistics& stat=unused_commit);
02196 void trycommit(const Choice& c, unsigned int a,
02197 CommitStatistics& stat=unused_commit);
02216 GECODE_KERNEL_EXPORT
02217 NGL* ngl(const Choice& c, unsigned int a);
02218
02233 GECODE_KERNEL_EXPORT
02234 void print(const Choice& c, unsigned int a, std::ostream& o) const;
02235
02244 GECODE_KERNEL_EXPORT
02245 void notice(Actor& a, ActorProperty p, bool duplicate=false);
02253 GECODE_KERNEL_EXPORT
02254 void ignore(Actor& a, ActorProperty p, bool duplicate=false);
02255
02256
02267 ExecStatus ES_SUBSUMED(Propagator& p);
02282 ExecStatus ES_SUBSUMED_DISPOSED(Propagator& p, size_t s);
02293 ExecStatus ES_FIX_PARTIAL(Propagator& p, const ModEventDelta& med);
02304 ExecStatus ES_NOFIX_PARTIAL(Propagator& p, const ModEventDelta& med);
02305
02316 template<class A>
02317 ExecStatus ES_FIX_DISPOSE(Council<A>& c, A& a);
02328 template<class A>
02329 ExecStatus ES_NOFIX_DISPOSE(Council<A>& c, A& a);
02341 template<class A>
02342 ExecStatus ES_NOFIX_DISPOSE_FORCE(Council<A>& c, A& a);
02343
02351 void fail(void);
02360 bool failed(void) const;
02365 bool stable(void) const;
02366
02368
02369
02370 Home operator ()(Propagator& p);
02372 Home operator ()(PropagatorGroup pg);
02374 Home operator ()(BrancherGroup bg);
02376
02388 template<class T>
02389 T* alloc(long unsigned int n);
02396 template<class T>
02397 T* alloc(long int n);
02404 template<class T>
02405 T* alloc(unsigned int n);
02412 template<class T>
02413 T* alloc(int n);
02423 template<class T>
02424 void free(T* b, long unsigned int n);
02434 template<class T>
02435 void free(T* b, long int n);
02445 template<class T>
02446 void free(T* b, unsigned int n);
02456 template<class T>
02457 void free(T* b, int n);
02469 template<class T>
02470 T* realloc(T* b, long unsigned int n, long unsigned int m);
02482 template<class T>
02483 T* realloc(T* b, long int n, long int m);
02495 template<class T>
02496 T* realloc(T* b, unsigned int n, unsigned int m);
02508 template<class T>
02509 T* realloc(T* b, int n, int m);
02517 template<class T>
02518 T** realloc(T** b, long unsigned int n, long unsigned int m);
02526 template<class T>
02527 T** realloc(T** b, long int n, long int m);
02535 template<class T>
02536 T** realloc(T** b, unsigned int n, unsigned int m);
02544 template<class T>
02545 T** realloc(T** b, int n, int m);
02547 void* ralloc(size_t s);
02549 void rfree(void* p, size_t s);
02551 void* rrealloc(void* b, size_t n, size_t m);
02553 template<size_t> void* fl_alloc(void);
02559 template<size_t> void fl_dispose(FreeList* f, FreeList* l);
02561
02562
02563
02566 template<class T>
02567 T& construct(void);
02573 template<class T, typename A1>
02574 T& construct(A1 const& a1);
02580 template<class T, typename A1, typename A2>
02581 T& construct(A1 const& a1, A2 const& a2);
02587 template<class T, typename A1, typename A2, typename A3>
02588 T& construct(A1 const& a1, A2 const& a2, A3 const& a3);
02594 template<class T, typename A1, typename A2, typename A3, typename A4>
02595 T& construct(A1 const& a1, A2 const& a2, A3 const& a3, A4 const& a4);
02601 template<class T, typename A1, typename A2, typename A3, typename A4, typename A5>
02602 T& construct(A1 const& a1, A2 const& a2, A3 const& a3, A4 const& a4, A5 const& a5);
02604
02606
02607
02608 void afc_decay(double d);
02610 double afc_decay(void) const;
02612 GECODE_KERNEL_EXPORT void afc_unshare(void);
02614
02615 protected:
02621 class Propagators {
02622 private:
02624 Space& home;
02626 ActorLink* q;
02628 ActorLink* c;
02630 ActorLink* e;
02631 public:
02633 Propagators(Space& home);
02635 bool operator ()(void) const;
02637 void operator ++(void);
02639 Propagator& propagator(void) const;
02640 };
02646 class ScheduledPropagators {
02647 private:
02649 Space& home;
02651 ActorLink* q;
02653 ActorLink* c;
02655 ActorLink* e;
02656 public:
02658 ScheduledPropagators(Space& home);
02660 bool operator ()(void) const;
02662 void operator ++(void);
02664 Propagator& propagator(void) const;
02665 };
02671 class IdlePropagators {
02672 private:
02674 ActorLink* c;
02676 ActorLink* e;
02677 public:
02679 IdlePropagators(Space& home);
02681 bool operator ()(void) const;
02683 void operator ++(void);
02685 Propagator& propagator(void) const;
02686 };
02692 class Branchers {
02693 private:
02695 ActorLink* c;
02697 ActorLink* e;
02698 public:
02700 Branchers(Space& home);
02702 bool operator ()(void) const;
02704 void operator ++(void);
02706 Brancher& brancher(void) const;
02707 };
02708 };
02709
02711 class Propagators {
02712 private:
02714 Space::Propagators ps;
02716 PropagatorGroup g;
02717 public:
02719 Propagators(Space& home, PropagatorGroup g);
02721 bool operator ()(void) const;
02723 void operator ++(void);
02725 const Propagator& propagator(void) const;
02726 };
02727
02729 class Branchers {
02730 private:
02732 Space::Branchers bs;
02734 BrancherGroup g;
02735 public:
02737 Branchers(Space& home, BrancherGroup g);
02739 bool operator ()(void) const;
02741 void operator ++(void);
02743 const Brancher& brancher(void) const;
02744 };
02745
02746
02747
02748
02749
02750
02751
02752
02753
02754
02755 forceinline void*
02756 Space::ralloc(size_t s) {
02757 return mm.alloc(ssd.data().sm,s);
02758 }
02759 forceinline void
02760 Space::rfree(void* p, size_t s) {
02761 return mm.reuse(p,s);
02762 }
02763 forceinline void*
02764 Space::rrealloc(void* _b, size_t n, size_t m) {
02765 char* b = static_cast<char*>(_b);
02766 if (n < m) {
02767 char* p = static_cast<char*>(ralloc(m));
02768 memcpy(p,b,n);
02769 rfree(b,n);
02770 return p;
02771 } else {
02772 rfree(b+m,m-n);
02773 return b;
02774 }
02775 }
02776
02777 template<size_t s>
02778 forceinline void*
02779 Space::fl_alloc(void) {
02780 return mm.template fl_alloc<s>(ssd.data().sm);
02781 }
02782 template<size_t s>
02783 forceinline void
02784 Space::fl_dispose(FreeList* f, FreeList* l) {
02785 mm.template fl_dispose<s>(f,l);
02786 }
02787
02788
02789
02790
02791
02792 template<class T>
02793 forceinline T*
02794 Space::alloc(long unsigned int n) {
02795 T* p = static_cast<T*>(ralloc(sizeof(T)*n));
02796 for (long unsigned int i=n; i--; )
02797 (void) new (p+i) T();
02798 return p;
02799 }
02800 template<class T>
02801 forceinline T*
02802 Space::alloc(long int n) {
02803 assert(n >= 0);
02804 return alloc<T>(static_cast<long unsigned int>(n));
02805 }
02806 template<class T>
02807 forceinline T*
02808 Space::alloc(unsigned int n) {
02809 return alloc<T>(static_cast<long unsigned int>(n));
02810 }
02811 template<class T>
02812 forceinline T*
02813 Space::alloc(int n) {
02814 assert(n >= 0);
02815 return alloc<T>(static_cast<long unsigned int>(n));
02816 }
02817
02818 template<class T>
02819 forceinline void
02820 Space::free(T* b, long unsigned int n) {
02821 for (long unsigned int i=n; i--; )
02822 b[i].~T();
02823 rfree(b,n*sizeof(T));
02824 }
02825 template<class T>
02826 forceinline void
02827 Space::free(T* b, long int n) {
02828 assert(n >= 0);
02829 free<T>(b,static_cast<long unsigned int>(n));
02830 }
02831 template<class T>
02832 forceinline void
02833 Space::free(T* b, unsigned int n) {
02834 free<T>(b,static_cast<long unsigned int>(n));
02835 }
02836 template<class T>
02837 forceinline void
02838 Space::free(T* b, int n) {
02839 assert(n >= 0);
02840 free<T>(b,static_cast<long unsigned int>(n));
02841 }
02842
02843 template<class T>
02844 forceinline T*
02845 Space::realloc(T* b, long unsigned int n, long unsigned int m) {
02846 if (n < m) {
02847 T* p = static_cast<T*>(ralloc(sizeof(T)*m));
02848 for (long unsigned int i=n; i--; )
02849 (void) new (p+i) T(b[i]);
02850 for (long unsigned int i=n; i<m; i++)
02851 (void) new (p+i) T();
02852 free<T>(b,n);
02853 return p;
02854 } else {
02855 free<T>(b+m,m-n);
02856 return b;
02857 }
02858 }
02859 template<class T>
02860 forceinline T*
02861 Space::realloc(T* b, long int n, long int m) {
02862 assert((n >= 0) && (m >= 0));
02863 return realloc<T>(b,static_cast<long unsigned int>(n),
02864 static_cast<long unsigned int>(m));
02865 }
02866 template<class T>
02867 forceinline T*
02868 Space::realloc(T* b, unsigned int n, unsigned int m) {
02869 return realloc<T>(b,static_cast<long unsigned int>(n),
02870 static_cast<long unsigned int>(m));
02871 }
02872 template<class T>
02873 forceinline T*
02874 Space::realloc(T* b, int n, int m) {
02875 assert((n >= 0) && (m >= 0));
02876 return realloc<T>(b,static_cast<long unsigned int>(n),
02877 static_cast<long unsigned int>(m));
02878 }
02879
02880 #define GECODE_KERNEL_REALLOC(T) \
02881 template<> \
02882 forceinline T* \
02883 Space::realloc<T>(T* b, long unsigned int n, long unsigned int m) { \
02884 return static_cast<T*>(rrealloc(b,n*sizeof(T),m*sizeof(T))); \
02885 } \
02886 template<> \
02887 forceinline T* \
02888 Space::realloc<T>(T* b, long int n, long int m) { \
02889 assert((n >= 0) && (m >= 0)); \
02890 return realloc<T>(b,static_cast<long unsigned int>(n), \
02891 static_cast<long unsigned int>(m)); \
02892 } \
02893 template<> \
02894 forceinline T* \
02895 Space::realloc<T>(T* b, unsigned int n, unsigned int m) { \
02896 return realloc<T>(b,static_cast<long unsigned int>(n), \
02897 static_cast<long unsigned int>(m)); \
02898 } \
02899 template<> \
02900 forceinline T* \
02901 Space::realloc<T>(T* b, int n, int m) { \
02902 assert((n >= 0) && (m >= 0)); \
02903 return realloc<T>(b,static_cast<long unsigned int>(n), \
02904 static_cast<long unsigned int>(m)); \
02905 }
02906
02907 GECODE_KERNEL_REALLOC(bool)
02908 GECODE_KERNEL_REALLOC(signed char)
02909 GECODE_KERNEL_REALLOC(unsigned char)
02910 GECODE_KERNEL_REALLOC(signed short int)
02911 GECODE_KERNEL_REALLOC(unsigned short int)
02912 GECODE_KERNEL_REALLOC(signed int)
02913 GECODE_KERNEL_REALLOC(unsigned int)
02914 GECODE_KERNEL_REALLOC(signed long int)
02915 GECODE_KERNEL_REALLOC(unsigned long int)
02916 GECODE_KERNEL_REALLOC(float)
02917 GECODE_KERNEL_REALLOC(double)
02918
02919 #undef GECODE_KERNEL_REALLOC
02920
02921 template<class T>
02922 forceinline T**
02923 Space::realloc(T** b, long unsigned int n, long unsigned int m) {
02924 return static_cast<T**>(rrealloc(b,n*sizeof(T),m*sizeof(T*)));
02925 }
02926 template<class T>
02927 forceinline T**
02928 Space::realloc(T** b, long int n, long int m) {
02929 assert((n >= 0) && (m >= 0));
02930 return realloc<T*>(b,static_cast<long unsigned int>(n),
02931 static_cast<long unsigned int>(m));
02932 }
02933 template<class T>
02934 forceinline T**
02935 Space::realloc(T** b, unsigned int n, unsigned int m) {
02936 return realloc<T*>(b,static_cast<long unsigned int>(n),
02937 static_cast<long unsigned int>(m));
02938 }
02939 template<class T>
02940 forceinline T**
02941 Space::realloc(T** b, int n, int m) {
02942 assert((n >= 0) && (m >= 0));
02943 return realloc<T*>(b,static_cast<long unsigned int>(n),
02944 static_cast<long unsigned int>(m));
02945 }
02946
02947
02948 #ifdef GECODE_HAS_VAR_DISPOSE
02949 template<class VIC>
02950 forceinline VarImpBase*
02951 Space::vars_d(void) const {
02952 return _vars_d[VIC::idx_d];
02953 }
02954 template<class VIC>
02955 forceinline void
02956 Space::vars_d(VarImpBase* x) {
02957 _vars_d[VIC::idx_d] = x;
02958 }
02959 #endif
02960
02961
02962 forceinline void
02963 Actor::operator delete(void*) {}
02964 forceinline void
02965 Actor::operator delete(void*, Space&) {}
02966 forceinline void*
02967 Actor::operator new(size_t s, Space& home) {
02968 return home.ralloc(s);
02969 }
02970
02971 template<class VIC>
02972 forceinline void
02973 VarImp<VIC>::operator delete(void*) {}
02974 template<class VIC>
02975 forceinline void
02976 VarImp<VIC>::operator delete(void*, Space&) {}
02977 template<class VIC>
02978 forceinline void*
02979 VarImp<VIC>::operator new(size_t s, Space& home) {
02980 return home.ralloc(s);
02981 }
02982
02983 #ifndef __GNUC__
02984 forceinline void
02985 Advisor::operator delete(void*) {}
02986 #endif
02987 forceinline void
02988 Advisor::operator delete(void*, Space&) {}
02989 forceinline void*
02990 Advisor::operator new(size_t s, Space& home) {
02991 return home.ralloc(s);
02992 }
02993
02994 forceinline void
02995 NGL::operator delete(void*) {}
02996 forceinline void
02997 NGL::operator delete(void*, Space&) {}
02998 forceinline void*
02999 NGL::operator new(size_t s, Space& home) {
03000 return home.ralloc(s);
03001 }
03002
03003
03004
03005
03006
03007
03008 forceinline
03009 NoGoods::NoGoods(void)
03010 : n(0) {}
03011 forceinline unsigned long int
03012 NoGoods::ng(void) const {
03013 return n;
03014 }
03015 forceinline void
03016 NoGoods::ng(unsigned long int n0) {
03017 n=n0;
03018 }
03019 forceinline
03020 NoGoods::~NoGoods(void) {}
03021
03022
03023
03024
03025
03026 forceinline
03027 MetaInfo::MetaInfo(unsigned long int r0,
03028 unsigned long int s0,
03029 unsigned long int f0,
03030 const Space* l0,
03031 NoGoods& ng0)
03032 : t(RESTART), r(r0), s(s0), f(f0), l(l0), ng(ng0), a(0) {}
03033
03034 forceinline
03035 MetaInfo::MetaInfo(unsigned int a0)
03036 : t(PORTFOLIO), r(0), s(0), f(0), l(NULL), ng(NoGoods::eng), a(a0) {}
03037
03038 forceinline MetaInfo::Type
03039 MetaInfo::type(void) const {
03040 return t;
03041 }
03042 forceinline unsigned long int
03043 MetaInfo::restart(void) const {
03044 assert(type() == RESTART);
03045 return r;
03046 }
03047 forceinline unsigned long int
03048 MetaInfo::solution(void) const {
03049 assert(type() == RESTART);
03050 return s;
03051 }
03052 forceinline unsigned long int
03053 MetaInfo::fail(void) const {
03054 assert(type() == RESTART);
03055 return f;
03056 }
03057 forceinline const Space*
03058 MetaInfo::last(void) const {
03059 assert(type() == RESTART);
03060 return l;
03061 }
03062 forceinline const NoGoods&
03063 MetaInfo::nogoods(void) const {
03064 assert(type() == RESTART);
03065 return ng;
03066 }
03067 forceinline unsigned int
03068 MetaInfo::asset(void) const {
03069 assert(type() == PORTFOLIO);
03070 return a;
03071 }
03072
03073
03074
03075
03076
03077
03078
03079 forceinline ActorLink*
03080 ActorLink::prev(void) const {
03081 return _prev;
03082 }
03083
03084 forceinline ActorLink*
03085 ActorLink::next(void) const {
03086 return _next;
03087 }
03088
03089 forceinline ActorLink**
03090 ActorLink::next_ref(void) {
03091 return &_next;
03092 }
03093
03094 forceinline void
03095 ActorLink::prev(ActorLink* al) {
03096 _prev = al;
03097 }
03098
03099 forceinline void
03100 ActorLink::next(ActorLink* al) {
03101 _next = al;
03102 }
03103
03104 forceinline void
03105 ActorLink::unlink(void) {
03106 ActorLink* p = _prev; ActorLink* n = _next;
03107 p->_next = n; n->_prev = p;
03108 }
03109
03110 forceinline void
03111 ActorLink::init(void) {
03112 _next = this; _prev =this;
03113 }
03114
03115 forceinline void
03116 ActorLink::head(ActorLink* a) {
03117
03118 ActorLink* n = _next;
03119 this->_next = a; a->_prev = this;
03120 a->_next = n; n->_prev = a;
03121 }
03122
03123 forceinline void
03124 ActorLink::tail(ActorLink* a) {
03125
03126 ActorLink* p = _prev;
03127 a->_next = this; this->_prev = a;
03128 p->_next = a; a->_prev = p;
03129 }
03130
03131 forceinline bool
03132 ActorLink::empty(void) const {
03133 return _next == this;
03134 }
03135
03136 template<class T>
03137 forceinline ActorLink*
03138 ActorLink::cast(T* a) {
03139
03140 GECODE_NOT_NULL(a);
03141 ActorLink& t = *a;
03142 return static_cast<ActorLink*>(&t);
03143 }
03144
03145 template<class T>
03146 forceinline const ActorLink*
03147 ActorLink::cast(const T* a) {
03148
03149 GECODE_NOT_NULL(a);
03150 const ActorLink& t = *a;
03151 return static_cast<const ActorLink*>(&t);
03152 }
03153
03154
03155
03156
03157
03158
03159 forceinline Actor*
03160 Actor::cast(ActorLink* al) {
03161
03162 GECODE_NOT_NULL(al);
03163 ActorLink& t = *al;
03164 return static_cast<Actor*>(&t);
03165 }
03166
03167 forceinline const Actor*
03168 Actor::cast(const ActorLink* al) {
03169
03170 GECODE_NOT_NULL(al);
03171 const ActorLink& t = *al;
03172 return static_cast<const Actor*>(&t);
03173 }
03174
03175 forceinline void
03176 Home::notice(Actor& a, ActorProperty p, bool duplicate) {
03177 s.notice(a,p,duplicate);
03178 }
03179
03180 forceinline Space*
03181 Space::clone(CloneStatistics&) const {
03182
03183
03184
03185 return const_cast<Space*>(this)->_clone();
03186 }
03187
03188 forceinline void
03189 Space::commit(const Choice& c, unsigned int a, CommitStatistics&) {
03190 _commit(c,a);
03191 }
03192
03193 forceinline void
03194 Space::trycommit(const Choice& c, unsigned int a, CommitStatistics&) {
03195 _trycommit(c,a);
03196 }
03197
03198 forceinline double
03199 Space::afc_decay(void) const {
03200 return ssd.data().gpi.decay();
03201 }
03202
03203 forceinline void
03204 Space::afc_decay(double d) {
03205 ssd.data().gpi.decay(d);
03206 }
03207
03208 forceinline size_t
03209 Actor::dispose(Space&) {
03210 return sizeof(*this);
03211 }
03212
03213
03214
03215
03216
03217
03218 forceinline
03219 Home::Home(Space& s0, Propagator* p0,
03220 PropagatorGroup pg0, BrancherGroup bg0)
03221 : s(s0), p(p0), pg(pg0), bg(bg0) {}
03222 forceinline Home&
03223 Home::operator =(const Home& h) {
03224 s=h.s; p=h.p; pg=h.pg; bg=h.bg;
03225 return *this;
03226 }
03227 forceinline
03228 Home::operator Space&(void) {
03229 return s;
03230 }
03231 forceinline Home
03232 Home::operator ()(Propagator& p) {
03233 return Home(s,&p);
03234 }
03235 forceinline Home
03236 Home::operator ()(PropagatorGroup pg) {
03237 return Home(s,NULL,pg,BrancherGroup::def);
03238 }
03239 forceinline Home
03240 Home::operator ()(BrancherGroup bg) {
03241 return Home(s,NULL,PropagatorGroup::def,bg);
03242 }
03243 forceinline Home
03244 Space::operator ()(Propagator& p) {
03245 return Home(*this,&p);
03246 }
03247 forceinline Propagator*
03248 Home::propagator(void) const {
03249 return p;
03250 }
03251 forceinline PropagatorGroup
03252 Home::propagatorgroup(void) const {
03253 return pg;
03254 }
03255 forceinline BrancherGroup
03256 Home::branchergroup(void) const {
03257 return bg;
03258 }
03259
03260
03261
03262
03263
03264 forceinline void
03265 ViewTraceInfo::propagator(Propagator& p) {
03266 who = reinterpret_cast<ptrdiff_t>(&p) | PROPAGATOR;
03267 }
03268 forceinline void
03269 ViewTraceInfo::brancher(Brancher& b) {
03270 who = reinterpret_cast<ptrdiff_t>(&b) | BRANCHER;
03271 }
03272 forceinline void
03273 ViewTraceInfo::post(PropagatorGroup g) {
03274 who = (g.id() << 2) | POST;
03275 }
03276 forceinline void
03277 ViewTraceInfo::other(void) {
03278 who = OTHER;
03279 }
03280 forceinline ViewTraceInfo::What
03281 ViewTraceInfo::what(void) const {
03282 return static_cast<What>(who & 3);
03283 }
03284 forceinline const Propagator&
03285 ViewTraceInfo::propagator(void) const {
03286 assert(what() == PROPAGATOR);
03287
03288 return *reinterpret_cast<Propagator*>(who);
03289 }
03290 forceinline const Brancher&
03291 ViewTraceInfo::brancher(void) const {
03292 assert(what() == BRANCHER);
03293 return *reinterpret_cast<Brancher*>(who & ~3);
03294 }
03295 forceinline PropagatorGroup
03296 ViewTraceInfo::post(void) const {
03297 assert(what() == POST);
03298 return PropagatorGroup(static_cast<unsigned int>(who >> 2));
03299 }
03300
03301
03302
03303
03304 forceinline
03305 PostInfo::PostInfo(Home home) : h(home) {
03306 h.pc.p.vti.post(home.propagatorgroup());
03307 }
03308 forceinline
03309 PostInfo::~PostInfo(void) {
03310 h.pc.p.vti.other();
03311 }
03312
03313
03314
03315
03316
03317 forceinline
03318 PropagateTraceInfo::PropagateTraceInfo(unsigned int i0, PropagatorGroup g0,
03319 const Propagator* p0, Status s0)
03320 : i(i0), g(g0), p(p0), s(s0) {}
03321 forceinline unsigned int
03322 PropagateTraceInfo::id(void) const {
03323 return i;
03324 }
03325 forceinline PropagatorGroup
03326 PropagateTraceInfo::group(void) const {
03327 return g;
03328 }
03329 forceinline const Propagator*
03330 PropagateTraceInfo::propagator(void) const {
03331 return p;
03332 }
03333 forceinline PropagateTraceInfo::Status
03334 PropagateTraceInfo::status(void) const {
03335 return s;
03336 }
03337
03338
03339
03340
03341
03342
03343 forceinline
03344 CommitTraceInfo::CommitTraceInfo(const Brancher& b0, const Choice& c0,
03345 unsigned int a0)
03346 : b(b0), c(c0), a(a0) {}
03347 forceinline unsigned int
03348 CommitTraceInfo::id(void) const {
03349 return b.id();
03350 }
03351 forceinline BrancherGroup
03352 CommitTraceInfo::group(void) const {
03353 return b.group();
03354 }
03355 forceinline const Brancher&
03356 CommitTraceInfo::brancher(void) const {
03357 return b;
03358 }
03359 forceinline const Choice&
03360 CommitTraceInfo::choice(void) const {
03361 return c;
03362 }
03363 forceinline unsigned int
03364 CommitTraceInfo::alternative(void) const {
03365 return a;
03366 }
03367
03368
03369
03370
03371
03372
03373 forceinline Propagator*
03374 Propagator::cast(ActorLink* al) {
03375
03376 GECODE_NOT_NULL(al);
03377 ActorLink& t = *al;
03378 return static_cast<Propagator*>(&t);
03379 }
03380
03381 forceinline const Propagator*
03382 Propagator::cast(const ActorLink* al) {
03383
03384 GECODE_NOT_NULL(al);
03385 const ActorLink& t = *al;
03386 return static_cast<const Propagator*>(&t);
03387 }
03388
03389 forceinline Propagator*
03390 Propagator::fwd(void) const {
03391 return static_cast<Propagator*>(prev());
03392 }
03393
03394 forceinline bool
03395 Propagator::disabled(void) const {
03396 return Support::marked(gpi_disabled);
03397 }
03398
03399 forceinline void
03400 Propagator::disable(Space& home) {
03401 home.pc.p.bid_sc |= Space::sc_disabled;
03402 gpi_disabled = Support::fmark(gpi_disabled);
03403 }
03404
03405 forceinline void
03406 Propagator::enable(Space& home) {
03407 (void) home;
03408 gpi_disabled = Support::funmark(gpi_disabled);
03409 }
03410
03411 forceinline Kernel::GPI::Info&
03412 Propagator::gpi(void) {
03413 return *static_cast<Kernel::GPI::Info*>(Support::funmark(gpi_disabled));
03414 }
03415
03416 forceinline
03417 Propagator::Propagator(Home home)
03418 : gpi_disabled((home.propagator() != NULL) ?
03419
03420 home.propagator()->gpi_disabled :
03421
03422 static_cast<Space&>(home).ssd.data().gpi.allocate
03423 (home.propagatorgroup().gid)) {
03424 u.advisors = NULL;
03425 assert((u.med == 0) && (u.size == 0));
03426 static_cast<Space&>(home).pl.head(this);
03427 }
03428
03429 forceinline
03430 Propagator::Propagator(Space&, Propagator& p)
03431 : gpi_disabled(p.gpi_disabled) {
03432 u.advisors = NULL;
03433 assert((u.med == 0) && (u.size == 0));
03434
03435 p.prev(this);
03436 }
03437
03438 forceinline ModEventDelta
03439 Propagator::modeventdelta(void) const {
03440 return u.med;
03441 }
03442
03443 forceinline double
03444 Propagator::afc(void) const {
03445 return const_cast<Propagator&>(*this).gpi().afc;
03446 }
03447
03448 #ifdef GECODE_HAS_CBS
03449 forceinline void
03450 Propagator::solndistrib(Space&, SendMarginal) const {}
03451
03452 forceinline void
03453 Propagator::domainsizesum(InDecision, unsigned int& size,
03454 unsigned int& size_b) const {
03455 size = 0;
03456 size_b = 0;
03457 }
03458 #endif
03459
03460 forceinline unsigned int
03461 Propagator::id(void) const {
03462 return const_cast<Propagator&>(*this).gpi().pid;
03463 }
03464
03465 forceinline PropagatorGroup
03466 Propagator::group(void) const {
03467 return PropagatorGroup(const_cast<Propagator&>(*this).gpi().gid);
03468 }
03469
03470 forceinline void
03471 Propagator::group(PropagatorGroup g) {
03472 gpi().gid = g.id();
03473 }
03474
03475 forceinline ExecStatus
03476 Space::ES_SUBSUMED_DISPOSED(Propagator& p, size_t s) {
03477 p.u.size = s;
03478 return __ES_SUBSUMED;
03479 }
03480
03481 forceinline ExecStatus
03482 Space::ES_SUBSUMED(Propagator& p) {
03483 p.u.size = p.dispose(*this);
03484 return __ES_SUBSUMED;
03485 }
03486
03487 forceinline ExecStatus
03488 Space::ES_FIX_PARTIAL(Propagator& p, const ModEventDelta& med) {
03489 p.u.med = med;
03490 assert(p.u.med != 0);
03491 return __ES_PARTIAL;
03492 }
03493
03494 forceinline ExecStatus
03495 Space::ES_NOFIX_PARTIAL(Propagator& p, const ModEventDelta& med) {
03496 p.u.med = AllVarConf::med_combine(p.u.med,med);
03497 assert(p.u.med != 0);
03498 return __ES_PARTIAL;
03499 }
03500
03501
03502
03503
03504
03505
03506
03507 forceinline Brancher*
03508 Brancher::cast(ActorLink* al) {
03509
03510 GECODE_NOT_NULL(al);
03511 ActorLink& t = *al;
03512 return static_cast<Brancher*>(&t);
03513 }
03514
03515 forceinline const Brancher*
03516 Brancher::cast(const ActorLink* al) {
03517
03518 GECODE_NOT_NULL(al);
03519 const ActorLink& t = *al;
03520 return static_cast<const Brancher*>(&t);
03521 }
03522
03523 forceinline
03524 Brancher::Brancher(Home _home) :
03525 gid(_home.branchergroup().gid) {
03526 Space& home = static_cast<Space&>(_home);
03527 bid = home.pc.p.bid_sc >> Space::sc_bits;
03528 home.pc.p.bid_sc += (1 << Space::sc_bits);
03529 if ((home.pc.p.bid_sc >> Space::sc_bits) == 0U)
03530 throw TooManyBranchers("Brancher::Brancher");
03531
03532 if (home.b_status == &static_cast<Space&>(home).bl) {
03533 home.b_status = this;
03534 if (home.b_commit == &static_cast<Space&>(home).bl)
03535 home.b_commit = this;
03536 }
03537 home.bl.tail(this);
03538 }
03539
03540 forceinline
03541 Brancher::Brancher(Space&, Brancher& b)
03542 : bid(b.bid), gid(b.gid) {
03543
03544 b.prev(this);
03545 }
03546
03547 forceinline unsigned int
03548 Brancher::id(void) const {
03549 return bid;
03550 }
03551
03552 forceinline BrancherGroup
03553 Brancher::group(void) const {
03554 return BrancherGroup(gid);
03555 }
03556
03557 forceinline void
03558 Brancher::group(BrancherGroup g) {
03559 gid = g.id();
03560 }
03561
03562
03563 forceinline void
03564 Space::kill(Brancher& b) {
03565 assert(!failed());
03566
03567 if (b_commit == &b)
03568 b_commit = Brancher::cast(b.next());
03569 if (b_status == &b)
03570 b_status = Brancher::cast(b.next());
03571 b.unlink();
03572 rfree(&b,b.dispose(*this));
03573 }
03574
03575 forceinline void
03576 Space::kill(Propagator& p) {
03577 assert(!failed());
03578 p.unlink();
03579 rfree(&p,p.dispose(*this));
03580 }
03581
03582 forceinline Brancher*
03583 Space::brancher(unsigned int id) {
03584
03585
03586
03587
03588
03589
03590
03591
03592
03593
03594
03595
03596
03597
03598 Brancher* b_old = b_commit;
03599
03600 while (b_commit != Brancher::cast(&bl))
03601 if (id != b_commit->id())
03602 b_commit = Brancher::cast(b_commit->next());
03603 else
03604 return b_commit;
03605 if (b_commit == Brancher::cast(&bl)) {
03606
03607 b_commit = Brancher::cast(bl.next());
03608 while (b_commit != b_old)
03609 if (id != b_commit->id())
03610 b_commit = Brancher::cast(b_commit->next());
03611 else
03612 return b_commit;
03613 }
03614 return NULL;
03615 }
03616
03617
03618
03619
03620
03621
03622
03623 forceinline LocalObject*
03624 LocalObject::cast(ActorLink* al) {
03625
03626 GECODE_NOT_NULL(al);
03627 ActorLink& t = *al;
03628 return static_cast<LocalObject*>(&t);
03629 }
03630
03631 forceinline const LocalObject*
03632 LocalObject::cast(const ActorLink* al) {
03633
03634 GECODE_NOT_NULL(al);
03635 const ActorLink& t = *al;
03636 return static_cast<const LocalObject*>(&t);
03637 }
03638
03639 forceinline
03640 LocalObject::LocalObject(Home home) {
03641 (void) home;
03642 ActorLink::cast(this)->prev(NULL);
03643 }
03644
03645 forceinline
03646 LocalObject::LocalObject(Space&, LocalObject&) {
03647 ActorLink::cast(this)->prev(NULL);
03648 }
03649
03650 forceinline LocalObject*
03651 LocalObject::fwd(Space& home) {
03652 if (prev() == NULL)
03653 fwdcopy(home);
03654 return LocalObject::cast(prev());
03655 }
03656
03657 forceinline
03658 LocalHandle::LocalHandle(void) : o(NULL) {}
03659 forceinline
03660 LocalHandle::LocalHandle(LocalObject* lo) : o(lo) {}
03661 forceinline
03662 LocalHandle::LocalHandle(const LocalHandle& lh) : o(lh.o) {}
03663 forceinline LocalHandle&
03664 LocalHandle::operator =(const LocalHandle& lh) {
03665 o = lh.o;
03666 return *this;
03667 }
03668 forceinline
03669 LocalHandle::~LocalHandle(void) {}
03670 forceinline LocalObject*
03671 LocalHandle::object(void) const { return o; }
03672 forceinline void
03673 LocalHandle::object(LocalObject* n) { o = n; }
03674 forceinline void
03675 LocalHandle::update(Space& home, LocalHandle& lh) {
03676 object(lh.object()->fwd(home));
03677 }
03678
03679
03680
03681
03682
03683
03684 forceinline
03685 Choice::Choice(const Brancher& b, const unsigned int a)
03686 : bid(b.id()), alt(a) {}
03687
03688 forceinline unsigned int
03689 Choice::alternatives(void) const {
03690 return alt;
03691 }
03692
03693 forceinline unsigned int
03694 Choice::id(void) const {
03695 return bid;
03696 }
03697
03698 forceinline
03699 Choice::~Choice(void) {}
03700
03701
03702
03703
03704
03705
03706
03707 forceinline bool
03708 NGL::leaf(void) const {
03709 return Support::marked(nl);
03710 }
03711 forceinline NGL*
03712 NGL::next(void) const {
03713 return static_cast<NGL*>(Support::funmark(nl));
03714 }
03715 forceinline void
03716 NGL::leaf(bool l) {
03717 nl = l ? Support::fmark(nl) : Support::funmark(nl);
03718 }
03719 forceinline void
03720 NGL::next(NGL* n) {
03721 nl = Support::marked(nl) ? Support::mark(n) : n;
03722 }
03723 forceinline NGL*
03724 NGL::add(NGL* n, bool l) {
03725 nl = Support::marked(nl) ? Support::mark(n) : n;
03726 n->leaf(l);
03727 return n;
03728 }
03729
03730 forceinline
03731 NGL::NGL(void)
03732 : nl(NULL) {}
03733 forceinline
03734 NGL::NGL(Space&)
03735 : nl(NULL) {}
03736 forceinline
03737 NGL::NGL(Space&, NGL&)
03738 : nl(NULL) {}
03739 forceinline size_t
03740 NGL::dispose(Space&) {
03741 return sizeof(*this);
03742 }
03743
03744
03745
03746
03747
03748 template<class A>
03749 forceinline
03750 Advisor::Advisor(Space&, Propagator& p, Council<A>& c) {
03751
03752 ActorLink::prev(&p);
03753
03754 ActorLink::next(c.advisors); c.advisors = static_cast<A*>(this);
03755 }
03756
03757 forceinline
03758 Advisor::Advisor(Space&, Advisor&) {}
03759
03760 forceinline bool
03761 Advisor::disposed(void) const {
03762 return prev() == NULL;
03763 }
03764
03765 forceinline Advisor*
03766 Advisor::cast(ActorLink* al) {
03767 return static_cast<Advisor*>(al);
03768 }
03769
03770 forceinline const Advisor*
03771 Advisor::cast(const ActorLink* al) {
03772 return static_cast<const Advisor*>(al);
03773 }
03774
03775 forceinline Propagator&
03776 Advisor::propagator(void) const {
03777 assert(!disposed());
03778 return *Propagator::cast(ActorLink::prev());
03779 }
03780
03781 template<class A>
03782 forceinline void
03783 Advisor::dispose(Space&,Council<A>&) {
03784 assert(!disposed());
03785 ActorLink::prev(NULL);
03786
03787 Advisor* n = Advisor::cast(next());
03788 if ((n != NULL) && n->disposed())
03789 next(n->next());
03790 }
03791
03792 forceinline const ViewTraceInfo&
03793 Advisor::operator ()(const Space& home) const {
03794 return home.pc.p.vti;
03795 }
03796
03797 template<class A>
03798 forceinline ExecStatus
03799 Space::ES_FIX_DISPOSE(Council<A>& c, A& a) {
03800 a.dispose(*this,c);
03801 return ES_FIX;
03802 }
03803
03804 template<class A>
03805 forceinline ExecStatus
03806 Space::ES_NOFIX_DISPOSE(Council<A>& c, A& a) {
03807 a.dispose(*this,c);
03808 return ES_NOFIX;
03809 }
03810
03811 template<class A>
03812 forceinline ExecStatus
03813 Space::ES_NOFIX_DISPOSE_FORCE(Council<A>& c, A& a) {
03814 a.dispose(*this,c);
03815 return ES_NOFIX_FORCE;
03816 }
03817
03818
03819
03820
03821
03822
03823
03824 template<class A>
03825 forceinline
03826 Council<A>::Council(void) {}
03827
03828 template<class A>
03829 forceinline
03830 Council<A>::Council(Space&)
03831 : advisors(NULL) {}
03832
03833 template<class A>
03834 forceinline bool
03835 Council<A>::empty(void) const {
03836 ActorLink* a = advisors;
03837 while ((a != NULL) && static_cast<A*>(a)->disposed())
03838 a = a->next();
03839 advisors = a;
03840 return a == NULL;
03841 }
03842
03843 template<class A>
03844 forceinline void
03845 Council<A>::update(Space& home, Council<A>& c) {
03846
03847 {
03848 ActorLink* a = c.advisors;
03849 while ((a != NULL) && static_cast<A*>(a)->disposed())
03850 a = a->next();
03851 c.advisors = a;
03852 }
03853
03854 if (c.advisors != NULL) {
03855
03856 Propagator* p_f = &static_cast<A*>(c.advisors)->propagator();
03857
03858 Propagator* p_t = Propagator::cast(p_f->prev());
03859
03860 ActorLink** a_f = &c.advisors;
03861
03862 A* a_t = NULL;
03863 while (*a_f != NULL) {
03864 if (static_cast<A*>(*a_f)->disposed()) {
03865 *a_f = (*a_f)->next();
03866 } else {
03867
03868 A* a = new (home) A(home,*static_cast<A*>(*a_f));
03869
03870 a->prev(p_t);
03871
03872 (*a_f)->prev(a);
03873
03874 a->next(a_t);
03875 a_t = a;
03876 a_f = (*a_f)->next_ref();
03877 }
03878 }
03879 advisors = a_t;
03880
03881 assert(p_f->u.advisors == NULL);
03882 p_f->u.advisors = c.advisors;
03883 } else {
03884 advisors = NULL;
03885 }
03886 }
03887
03888 template<class A>
03889 forceinline void
03890 Council<A>::dispose(Space& home) {
03891 ActorLink* a = advisors;
03892 while (a != NULL) {
03893 if (!static_cast<A*>(a)->disposed())
03894 static_cast<A*>(a)->dispose(home,*this);
03895 a = a->next();
03896 }
03897 }
03898
03899
03900
03901
03902
03903
03904
03905 template<class A>
03906 forceinline
03907 Advisors<A>::Advisors(const Council<A>& c)
03908 : a(c.advisors) {
03909 while ((a != NULL) && static_cast<A*>(a)->disposed())
03910 a = a->next();
03911 }
03912
03913 template<class A>
03914 forceinline bool
03915 Advisors<A>::operator ()(void) const {
03916 return a != NULL;
03917 }
03918
03919 template<class A>
03920 forceinline void
03921 Advisors<A>::operator ++(void) {
03922 do {
03923 a = a->next();
03924 } while ((a != NULL) && static_cast<A*>(a)->disposed());
03925 }
03926
03927 template<class A>
03928 forceinline A&
03929 Advisors<A>::advisor(void) const {
03930 return *static_cast<A*>(a);
03931 }
03932
03933
03934
03935
03936
03937
03938
03939 forceinline void
03940 Space::enqueue(Propagator* p) {
03941 ActorLink::cast(p)->unlink();
03942 ActorLink* c = &pc.p.queue[p->cost(*this,p->u.med).ac];
03943 c->tail(ActorLink::cast(p));
03944 if (c > pc.p.active)
03945 pc.p.active = c;
03946 }
03947
03948 forceinline void
03949 Space::fail(void) {
03950
03951
03952
03953
03954
03955 pc.p.active = &pc.p.queue[PropCost::AC_MAX+1]+1;
03956 }
03957 forceinline void
03958 Home::fail(void) {
03959 s.fail();
03960 }
03961
03962 forceinline bool
03963 Space::failed(void) const {
03964 return pc.p.active > &pc.p.queue[PropCost::AC_MAX+1];
03965 }
03966 forceinline bool
03967 Home::failed(void) const {
03968 return s.failed();
03969 }
03970
03971 forceinline bool
03972 Space::stable(void) const {
03973 return ((pc.p.active < &pc.p.queue[0]) ||
03974 (pc.p.active > &pc.p.queue[PropCost::AC_MAX+1]));
03975 }
03976
03977 forceinline void
03978 Space::notice(Actor& a, ActorProperty p, bool d) {
03979 if (p & AP_DISPOSE) {
03980 ap_notice_dispose(&a,d);
03981 }
03982 if (p & AP_VIEW_TRACE) {
03983 pc.p.bid_sc |= sc_trace;
03984 }
03985 if (p & AP_TRACE) {
03986 pc.p.bid_sc |= sc_trace;
03987 }
03988
03989 if (p & AP_WEAKLY) {}
03990 }
03991
03992 forceinline void
03993 Space::ignore(Actor& a, ActorProperty p, bool d) {
03994
03995
03996 if ((p & AP_DISPOSE) && (d_fst != NULL))
03997 ap_ignore_dispose(&a,d);
03998 if (p & AP_VIEW_TRACE) {}
03999 if (p & AP_TRACE) {}
04000
04001 if (p & AP_WEAKLY) {}
04002 }
04003
04004
04005
04006
04007
04008
04009
04010 template<class VIC>
04011 forceinline ActorLink**
04012 VarImp<VIC>::actor(PropCond pc) {
04013 assert((pc >= 0) && (pc < pc_max+2));
04014 return (pc == 0) ? b.base : b.base+u.idx[pc-1];
04015 }
04016
04017 template<class VIC>
04018 forceinline ActorLink**
04019 VarImp<VIC>::actorNonZero(PropCond pc) {
04020 assert((pc > 0) && (pc < pc_max+2));
04021 return b.base+u.idx[pc-1];
04022 }
04023
04024 template<class VIC>
04025 forceinline unsigned int&
04026 VarImp<VIC>::idx(PropCond pc) {
04027 assert((pc > 0) && (pc < pc_max+2));
04028 return u.idx[pc-1];
04029 }
04030
04031 template<class VIC>
04032 forceinline unsigned int
04033 VarImp<VIC>::idx(PropCond pc) const {
04034 assert((pc > 0) && (pc < pc_max+2));
04035 return u.idx[pc-1];
04036 }
04037
04038 template<class VIC>
04039 forceinline
04040 VarImp<VIC>::VarImp(Space& home)
04041 #ifdef GECODE_HAS_CBS
04042 : var_id(++home.var_id_counter)
04043 #endif
04044 {
04045 #ifndef GECODE_HAS_CBS
04046 (void) home;
04047 #endif
04048 b.base = NULL; entries = 0;
04049 for (PropCond pc=1; pc<pc_max+2; pc++)
04050 idx(pc) = 0;
04051 free_and_bits = 0;
04052 }
04053
04054 template<class VIC>
04055 forceinline
04056 VarImp<VIC>::VarImp(void)
04057 #ifdef GECODE_HAS_CBS
04058 : var_id(0)
04059 #endif
04060 {
04061 b.base = NULL; entries = 0;
04062 for (PropCond pc=1; pc<pc_max+2; pc++)
04063 idx(pc) = 0;
04064 free_and_bits = 0;
04065 }
04066
04067 #ifdef GECODE_HAS_CBS
04068 template<class VIC>
04069 forceinline unsigned int
04070 VarImp<VIC>::id(void) const {
04071 return var_id;
04072 }
04073 #endif
04074
04075 template<class VIC>
04076 forceinline unsigned int
04077 VarImp<VIC>::degree(void) const {
04078 assert(!copied());
04079 return entries;
04080 }
04081
04082 template<class VIC>
04083 forceinline double
04084 VarImp<VIC>::afc(void) const {
04085 double d = 0.0;
04086
04087 {
04088 ActorLink** a = const_cast<VarImp<VIC>*>(this)->actor(0);
04089 ActorLink** e = const_cast<VarImp<VIC>*>(this)->actorNonZero(pc_max+1);
04090 while (a < e) {
04091 d += Propagator::cast(*a)->afc(); a++;
04092 }
04093 }
04094
04095 {
04096 ActorLink** a = const_cast<VarImp<VIC>*>(this)->actorNonZero(pc_max+1);
04097 ActorLink** e = const_cast<VarImp<VIC>*>(this)->b.base+entries;
04098 while (a < e) {
04099 d += Advisor::cast(static_cast<ActorLink*>(Support::funmark(*a)))
04100 ->propagator().afc();
04101 a++;
04102 }
04103 }
04104 return d;
04105 }
04106
04107 template<class VIC>
04108 forceinline ModEvent
04109 VarImp<VIC>::modevent(const Delta& d) {
04110 return d.me;
04111 }
04112
04113 template<class VIC>
04114 forceinline unsigned int
04115 VarImp<VIC>::bits(void) const {
04116 return free_and_bits;
04117 }
04118
04119 template<class VIC>
04120 forceinline unsigned int&
04121 VarImp<VIC>::bits(void) {
04122 return free_and_bits;
04123 }
04124
04125 #ifdef GECODE_HAS_VAR_DISPOSE
04126 template<class VIC>
04127 forceinline VarImp<VIC>*
04128 VarImp<VIC>::vars_d(Space& home) {
04129 return static_cast<VarImp<VIC>*>(home.vars_d<VIC>());
04130 }
04131
04132 template<class VIC>
04133 forceinline void
04134 VarImp<VIC>::vars_d(Space& home, VarImp<VIC>* x) {
04135 home.vars_d<VIC>(x);
04136 }
04137 #endif
04138
04139 template<class VIC>
04140 forceinline bool
04141 VarImp<VIC>::copied(void) const {
04142 return Support::marked(b.fwd);
04143 }
04144
04145 template<class VIC>
04146 forceinline VarImp<VIC>*
04147 VarImp<VIC>::forward(void) const {
04148 assert(copied());
04149 return static_cast<VarImp<VIC>*>(Support::unmark(b.fwd));
04150 }
04151
04152 template<class VIC>
04153 forceinline VarImp<VIC>*
04154 VarImp<VIC>::next(void) const {
04155 assert(copied());
04156 return u.next;
04157 }
04158
04159 template<class VIC>
04160 forceinline
04161 VarImp<VIC>::VarImp(Space& home, VarImp<VIC>& x)
04162 #ifdef GECODE_HAS_CBS
04163 : var_id(x.var_id)
04164 #endif
04165 {
04166 VarImpBase** reg;
04167 free_and_bits = x.free_and_bits & ((1 << free_bits) - 1);
04168 if (x.b.base == NULL) {
04169
04170 reg = &home.pc.c.vars_noidx;
04171 assert(x.degree() == 0);
04172 } else {
04173 reg = &home.pc.c.vars_u[idx_c];
04174 }
04175
04176 b.base = x.b.base;
04177 entries = x.entries;
04178 for (PropCond pc=1; pc<pc_max+2; pc++)
04179 idx(pc) = x.idx(pc);
04180
04181
04182 x.b.fwd = static_cast<VarImp<VIC>*>(Support::mark(this));
04183
04184 x.u.next = static_cast<VarImp<VIC>*>(*reg); *reg = &x;
04185 }
04186
04187 template<class VIC>
04188 forceinline ModEvent
04189 VarImp<VIC>::me(const ModEventDelta& med) {
04190 return static_cast<ModEvent>((med & VIC::med_mask) >> VIC::med_fst);
04191 }
04192
04193 template<class VIC>
04194 forceinline ModEventDelta
04195 VarImp<VIC>::med(ModEvent me) {
04196 return static_cast<ModEventDelta>(me << VIC::med_fst);
04197 }
04198
04199 template<class VIC>
04200 forceinline ModEvent
04201 VarImp<VIC>::me_combine(ModEvent me1, ModEvent me2) {
04202 return VIC::me_combine(me1,me2);
04203 }
04204
04205 template<class VIC>
04206 forceinline void
04207 VarImp<VIC>::schedule(Space& home, Propagator& p, ModEvent me,
04208 bool force) {
04209 if (VIC::med_update(p.u.med,me) || force)
04210 home.enqueue(&p);
04211 }
04212
04213 template<class VIC>
04214 forceinline void
04215 VarImp<VIC>::schedule(Space& home, PropCond pc1, PropCond pc2, ModEvent me) {
04216 ActorLink** b = actor(pc1);
04217 ActorLink** p = actorNonZero(pc2+1);
04218 while (p-- > b)
04219 schedule(home,*Propagator::cast(*p),me);
04220 }
04221
04222 template<class VIC>
04223 forceinline void
04224 VarImp<VIC>::resize(Space& home) {
04225 if (b.base == NULL) {
04226 assert((free_and_bits >> free_bits) == 0);
04227
04228 free_and_bits += 4 << free_bits;
04229 b.base = home.alloc<ActorLink*>(4);
04230 for (int i=0; i<pc_max+1; i++)
04231 u.idx[i] = 0;
04232 } else {
04233
04234 unsigned int n = degree();
04235
04236
04237
04238 ActorLink** s = static_cast<ActorLink**>(home.mm.subscriptions());
04239 unsigned int m =
04240 ((s <= b.base) && (b.base < s+home.pc.p.n_sub)) ?
04241 (n+4) : ((n+1)*3>>1);
04242 ActorLink** prop = home.alloc<ActorLink*>(m);
04243 free_and_bits += (m-n) << free_bits;
04244
04245 Heap::copy<ActorLink*>(prop, b.base, n);
04246 home.free<ActorLink*>(b.base,n);
04247 b.base = prop;
04248 }
04249 }
04250
04251 template<class VIC>
04252 forceinline void
04253 VarImp<VIC>::enter(Space& home, Propagator* p, PropCond pc) {
04254 assert(pc <= pc_max);
04255
04256 home.pc.p.n_sub += 1;
04257 if ((free_and_bits >> free_bits) == 0)
04258 resize(home);
04259 free_and_bits -= 1 << free_bits;
04260
04261
04262 b.base[entries] = *actorNonZero(pc_max+1);
04263 entries++;
04264 for (PropCond j = pc_max; j > pc; j--) {
04265 *actorNonZero(j+1) = *actorNonZero(j);
04266 idx(j+1)++;
04267 }
04268 *actorNonZero(pc+1) = *actor(pc);
04269 idx(pc+1)++;
04270 *actor(pc) = ActorLink::cast(p);
04271
04272 #ifdef GECODE_AUDIT
04273 ActorLink** f = actor(pc);
04274 while (f < (pc == pc_max+1 ? b.base+entries : actorNonZero(pc+1)))
04275 if (*f == p)
04276 goto found;
04277 else
04278 f++;
04279 GECODE_NEVER;
04280 found: ;
04281 #endif
04282 }
04283
04284 template<class VIC>
04285 forceinline void
04286 VarImp<VIC>::enter(Space& home, Advisor* a) {
04287
04288
04289 home.pc.p.n_sub += 1;
04290 if ((free_and_bits >> free_bits) == 0)
04291 resize(home);
04292 free_and_bits -= 1 << free_bits;
04293
04294
04295 b.base[entries++] = *actorNonZero(pc_max+1);
04296 *actorNonZero(pc_max+1) = a;
04297 }
04298
04299 template<class VIC>
04300 forceinline void
04301 VarImp<VIC>::subscribe(Space& home, Propagator& p, PropCond pc,
04302 bool assigned, ModEvent me, bool schedule) {
04303 if (assigned) {
04304
04305 if (schedule)
04306 VarImp<VIC>::schedule(home,p,ME_GEN_ASSIGNED);
04307 } else {
04308 enter(home,&p,pc);
04309
04310 if (schedule && (pc != PC_GEN_ASSIGNED))
04311 VarImp<VIC>::schedule(home,p,me);
04312 }
04313 }
04314
04315 template<class VIC>
04316 forceinline void
04317 VarImp<VIC>::subscribe(Space& home, Advisor& a, bool assigned, bool fail) {
04318 if (!assigned) {
04319 Advisor* ma = static_cast<Advisor*>(Support::ptrjoin(&a,fail ? 1 : 0));
04320 enter(home,ma);
04321 }
04322 }
04323
04324 template<class VIC>
04325 forceinline void
04326 VarImp<VIC>::reschedule(Space& home, Propagator& p, PropCond pc,
04327 bool assigned, ModEvent me) {
04328 if (assigned)
04329 VarImp<VIC>::schedule(home,p,ME_GEN_ASSIGNED);
04330 else if (pc != PC_GEN_ASSIGNED)
04331 VarImp<VIC>::schedule(home,p,me);
04332 }
04333
04334 template<class VIC>
04335 void
04336 VarImp<VIC>::remove(Space& home, Propagator* p, PropCond pc) {
04337 assert(pc <= pc_max);
04338 ActorLink* a = ActorLink::cast(p);
04339
04340 ActorLink** f = actor(pc);
04341 #ifdef GECODE_AUDIT
04342 while (f < actorNonZero(pc+1))
04343 if (*f == a)
04344 goto found;
04345 else
04346 f++;
04347 GECODE_NEVER;
04348 found: ;
04349 #else
04350 while (*f != a) f++;
04351 #endif
04352
04353 *f = *(actorNonZero(pc+1)-1);
04354 for (PropCond j = pc+1; j< pc_max+1; j++) {
04355 *(actorNonZero(j)-1) = *(actorNonZero(j+1)-1);
04356 idx(j)--;
04357 }
04358 *(actorNonZero(pc_max+1)-1) = b.base[entries-1];
04359 idx(pc_max+1)--;
04360 entries--;
04361 free_and_bits += 1 << free_bits;
04362 home.pc.p.n_sub -= 1;
04363 }
04364
04365 template<class VIC>
04366 forceinline void
04367 VarImp<VIC>::cancel(Space& home, Propagator& p, PropCond pc) {
04368 if (b.base != NULL)
04369 remove(home,&p,pc);
04370 }
04371
04372 template<class VIC>
04373 void
04374 VarImp<VIC>::remove(Space& home, Advisor* a) {
04375
04376
04377 ActorLink** f = actorNonZero(pc_max+1);
04378 #ifdef GECODE_AUDIT
04379 while (f < b.base+entries)
04380 if (*f == a)
04381 goto found;
04382 else
04383 f++;
04384 GECODE_NEVER;
04385 found: ;
04386 #else
04387 while (*f != a) f++;
04388 #endif
04389
04390 *f = b.base[--entries];
04391 free_and_bits += 1 << free_bits;
04392 home.pc.p.n_sub -= 1;
04393 }
04394
04395 template<class VIC>
04396 forceinline void
04397 VarImp<VIC>::cancel(Space& home, Advisor& a, bool fail) {
04398 if (b.base != NULL) {
04399 Advisor* ma = static_cast<Advisor*>(Support::ptrjoin(&a,fail ? 1 : 0));
04400 remove(home,ma);
04401 }
04402 }
04403
04404 template<class VIC>
04405 forceinline void
04406 VarImp<VIC>::cancel(Space& home) {
04407 unsigned int n_sub = degree();
04408 home.pc.p.n_sub -= n_sub;
04409 unsigned int n = (free_and_bits >> free_bits) + n_sub;
04410 home.free<ActorLink*>(b.base,n);
04411
04412 b.base = NULL;
04413
04414 entries = 0;
04415
04416 for (PropCond pc=1; pc<pc_max+2; pc++)
04417 idx(pc) = 0;
04418 free_and_bits &= (1 << free_bits) - 1;
04419 }
04420
04421 template<class VIC>
04422 forceinline bool
04423 VarImp<VIC>::advise(Space& home, ModEvent me, Delta& d) {
04424
04425
04426
04427
04428
04429 ActorLink** la = actorNonZero(pc_max+1);
04430 ActorLink** le = b.base+entries;
04431 if (la == le)
04432 return true;
04433 d.me = me;
04434
04435
04436
04437 do {
04438 Advisor* a = Advisor::cast
04439 (static_cast<ActorLink*>(Support::funmark(*la)));
04440 assert(!a->disposed());
04441 Propagator& p = a->propagator();
04442 switch (p.advise(home,*a,d)) {
04443 case ES_FIX:
04444 break;
04445 case ES_FAILED:
04446 return false;
04447 case ES_NOFIX:
04448 schedule(home,p,me);
04449 break;
04450 case ES_NOFIX_FORCE:
04451 schedule(home,p,me,true);
04452 break;
04453 case __ES_SUBSUMED:
04454 default:
04455 GECODE_NEVER;
04456 }
04457 } while (++la < le);
04458 return true;
04459 }
04460
04461 template<class VIC>
04462 void
04463 VarImp<VIC>::_fail(Space& home) {
04464
04465
04466
04467
04468
04469 ActorLink** la = actorNonZero(pc_max+1);
04470 ActorLink** le = b.base+entries;
04471 if (la == le)
04472 return;
04473
04474
04475
04476 do {
04477 if (Support::marked(*la)) {
04478 Advisor* a = Advisor::cast(static_cast<ActorLink*>
04479 (Support::unmark(*la)));
04480 assert(!a->disposed());
04481 Propagator& p = a->propagator();
04482 p.advise(home,*a);
04483 }
04484 } while (++la < le);
04485 }
04486
04487 template<class VIC>
04488 ModEvent
04489 VarImp<VIC>::fail(Space& home) {
04490 _fail(home);
04491 return ME_GEN_FAILED;
04492 }
04493
04494 template<class VIC>
04495 forceinline void
04496 VarImp<VIC>::update(VarImp<VIC>* x, ActorLink**& sub) {
04497
04498
04499
04500 x->b.base = b.base;
04501 x->u.idx[0] = u.idx[0];
04502 if (pc_max > 0 && sizeof(ActorLink**) > sizeof(unsigned int))
04503 x->u.idx[1] = u.idx[1];
04504
04505 unsigned int np =
04506 static_cast<unsigned int>(x->actorNonZero(pc_max+1) - x->actor(0));
04507 unsigned int na =
04508 static_cast<unsigned int >(x->b.base + x->entries -
04509 x->actorNonZero(pc_max+1));
04510 unsigned int n = na + np;
04511 assert(n == x->degree());
04512
04513 ActorLink** f = x->b.base;
04514 ActorLink** t = sub;
04515
04516 sub += n;
04517 b.base = t;
04518
04519 while (np >= 4) {
04520 ActorLink* p3 = f[3]->prev();
04521 ActorLink* p0 = f[0]->prev();
04522 ActorLink* p1 = f[1]->prev();
04523 ActorLink* p2 = f[2]->prev();
04524 t[0] = p0; t[1] = p1; t[2] = p2; t[3] = p3;
04525 np -= 4; t += 4; f += 4;
04526 }
04527 if (np >= 2) {
04528 ActorLink* p0 = f[0]->prev();
04529 ActorLink* p1 = f[1]->prev();
04530 t[0] = p0; t[1] = p1;
04531 np -= 2; t += 2; f += 2;
04532 }
04533 if (np > 0) {
04534 ActorLink* p0 = f[0]->prev();
04535 t[0] = p0;
04536 t += 1; f += 1;
04537 }
04538
04539 while (na >= 4) {
04540 ptrdiff_t m0, m1, m2, m3;
04541 ActorLink* p3 =
04542 static_cast<ActorLink*>(Support::ptrsplit(f[3],m3))->prev();
04543 ActorLink* p0 =
04544 static_cast<ActorLink*>(Support::ptrsplit(f[0],m0))->prev();
04545 ActorLink* p1 =
04546 static_cast<ActorLink*>(Support::ptrsplit(f[1],m1))->prev();
04547 ActorLink* p2 =
04548 static_cast<ActorLink*>(Support::ptrsplit(f[2],m2))->prev();
04549 t[0] = static_cast<ActorLink*>(Support::ptrjoin(p0,m0));
04550 t[1] = static_cast<ActorLink*>(Support::ptrjoin(p1,m1));
04551 t[2] = static_cast<ActorLink*>(Support::ptrjoin(p2,m2));
04552 t[3] = static_cast<ActorLink*>(Support::ptrjoin(p3,m3));
04553 na -= 4; t += 4; f += 4;
04554 }
04555 if (na >= 2) {
04556 ptrdiff_t m0, m1;
04557 ActorLink* p0 =
04558 static_cast<ActorLink*>(Support::ptrsplit(f[0],m0))->prev();
04559 ActorLink* p1 =
04560 static_cast<ActorLink*>(Support::ptrsplit(f[1],m1))->prev();
04561 t[0] = static_cast<ActorLink*>(Support::ptrjoin(p0,m0));
04562 t[1] = static_cast<ActorLink*>(Support::ptrjoin(p1,m1));
04563 na -= 2; t += 2; f += 2;
04564 }
04565 if (na > 0) {
04566 ptrdiff_t m0;
04567 ActorLink* p0 =
04568 static_cast<ActorLink*>(Support::ptrsplit(f[0],m0))->prev();
04569 t[0] = static_cast<ActorLink*>(Support::ptrjoin(p0,m0));
04570 }
04571 }
04572
04573 template<class VIC>
04574 forceinline void
04575 VarImp<VIC>::update(Space& home, ActorLink**& sub) {
04576 VarImp<VIC>* x = static_cast<VarImp<VIC>*>(home.pc.c.vars_u[idx_c]);
04577 while (x != NULL) {
04578 VarImp<VIC>* n = x->next(); x->forward()->update(x,sub); x = n;
04579 }
04580 }
04581
04582
04583
04584
04585
04586
04587
04588 template<class VarImp>
04589 VarImpDisposer<VarImp>::VarImpDisposer(void) {
04590 #ifdef GECODE_HAS_VAR_DISPOSE
04591 Space::vd[VarImp::idx_d] = this;
04592 #endif
04593 }
04594
04595 template<class VarImp>
04596 void
04597 VarImpDisposer<VarImp>::dispose(Space& home, VarImpBase* _x) {
04598 VarImp* x = static_cast<VarImp*>(_x);
04599 do {
04600 x->dispose(home); x = static_cast<VarImp*>(x->next_d());
04601 } while (x != NULL);
04602 }
04603
04604
04605
04606
04607
04608 forceinline void
04609 StatusStatistics::reset(void) {
04610 propagate = 0;
04611 }
04612 forceinline
04613 StatusStatistics::StatusStatistics(void) {
04614 reset();
04615 }
04616 forceinline StatusStatistics&
04617 StatusStatistics::operator +=(const StatusStatistics& s) {
04618 propagate += s.propagate;
04619 return *this;
04620 }
04621 forceinline StatusStatistics
04622 StatusStatistics::operator +(const StatusStatistics& s) {
04623 StatusStatistics t(s);
04624 return t += *this;
04625 }
04626
04627 forceinline void
04628 CloneStatistics::reset(void) {}
04629
04630 forceinline
04631 CloneStatistics::CloneStatistics(void) {
04632 reset();
04633 }
04634 forceinline CloneStatistics
04635 CloneStatistics::operator +(const CloneStatistics&) {
04636 CloneStatistics s;
04637 return s;
04638 }
04639 forceinline CloneStatistics&
04640 CloneStatistics::operator +=(const CloneStatistics&) {
04641 return *this;
04642 }
04643
04644 forceinline void
04645 CommitStatistics::reset(void) {}
04646
04647 forceinline
04648 CommitStatistics::CommitStatistics(void) {
04649 reset();
04650 }
04651 forceinline CommitStatistics
04652 CommitStatistics::operator +(const CommitStatistics&) {
04653 CommitStatistics s;
04654 return s;
04655 }
04656 forceinline CommitStatistics&
04657 CommitStatistics::operator +=(const CommitStatistics&) {
04658 return *this;
04659 }
04660
04661
04662
04663
04664
04665
04666 forceinline
04667 PropCost::PropCost(PropCost::ActualCost ac0) : ac(ac0) {}
04668
04669 forceinline PropCost
04670 PropCost::cost(PropCost::Mod m,
04671 PropCost::ActualCost lo, PropCost::ActualCost hi,
04672 unsigned int n) {
04673 if (n < 2)
04674 return (m == LO) ? AC_UNARY_LO : AC_UNARY_HI;
04675 else if (n == 2)
04676 return (m == LO) ? AC_BINARY_LO : AC_BINARY_HI;
04677 else if (n == 3)
04678 return (m == LO) ? AC_TERNARY_LO : AC_TERNARY_HI;
04679 else
04680 return (m == LO) ? lo : hi;
04681 }
04682
04683 forceinline PropCost
04684 PropCost::record(void) {
04685 return AC_RECORD;
04686 }
04687 forceinline PropCost
04688 PropCost::crazy(PropCost::Mod m, unsigned int n) {
04689 return cost(m,AC_CRAZY_LO,AC_CRAZY_HI,n);
04690 }
04691 forceinline PropCost
04692 PropCost::crazy(PropCost::Mod m, int n) {
04693 assert(n >= 0);
04694 return crazy(m,static_cast<unsigned int>(n));
04695 }
04696 forceinline PropCost
04697 PropCost::cubic(PropCost::Mod m, unsigned int n) {
04698 return cost(m,AC_CUBIC_LO,AC_CUBIC_HI,n);
04699 }
04700 forceinline PropCost
04701 PropCost::cubic(PropCost::Mod m, int n) {
04702 assert(n >= 0);
04703 return cubic(m,static_cast<unsigned int>(n));
04704 }
04705 forceinline PropCost
04706 PropCost::quadratic(PropCost::Mod m, unsigned int n) {
04707 return cost(m,AC_QUADRATIC_LO,AC_QUADRATIC_HI,n);
04708 }
04709 forceinline PropCost
04710 PropCost::quadratic(PropCost::Mod m, int n) {
04711 assert(n >= 0);
04712 return quadratic(m,static_cast<unsigned int>(n));
04713 }
04714 forceinline PropCost
04715 PropCost::linear(PropCost::Mod m, unsigned int n) {
04716 return cost(m,AC_LINEAR_LO,AC_LINEAR_HI,n);
04717 }
04718 forceinline PropCost
04719 PropCost::linear(PropCost::Mod m, int n) {
04720 assert(n >= 0);
04721 return linear(m,static_cast<unsigned int>(n));
04722 }
04723 forceinline PropCost
04724 PropCost::ternary(PropCost::Mod m) {
04725 return (m == LO) ? AC_TERNARY_LO : AC_TERNARY_HI;
04726 }
04727 forceinline PropCost
04728 PropCost::binary(PropCost::Mod m) {
04729 return (m == LO) ? AC_BINARY_LO : AC_BINARY_HI;
04730 }
04731 forceinline PropCost
04732 PropCost::unary(PropCost::Mod m) {
04733 return (m == LO) ? AC_UNARY_LO : AC_UNARY_HI;
04734 }
04735
04736
04737
04738
04739
04740 forceinline
04741 Space::Propagators::Propagators(Space& home0)
04742 : home(home0), q(home.pc.p.active) {
04743 while (q >= &home.pc.p.queue[0]) {
04744 if (q->next() != q) {
04745 c = q->next(); e = q; q--;
04746 return;
04747 }
04748 q--;
04749 }
04750 q = NULL;
04751 if (!home.pl.empty()) {
04752 c = Propagator::cast(home.pl.next());
04753 e = Propagator::cast(&home.pl);
04754 } else {
04755 c = e = NULL;
04756 }
04757 }
04758 forceinline bool
04759 Space::Propagators::operator ()(void) const {
04760 return c != NULL;
04761 }
04762 forceinline void
04763 Space::Propagators::operator ++(void) {
04764 c = c->next();
04765 if (c == e) {
04766 if (q == NULL) {
04767 c = NULL;
04768 } else {
04769 while (q >= &home.pc.p.queue[0]) {
04770 if (q->next() != q) {
04771 c = q->next(); e = q; q--;
04772 return;
04773 }
04774 q--;
04775 }
04776 q = NULL;
04777 if (!home.pl.empty()) {
04778 c = Propagator::cast(home.pl.next());
04779 e = Propagator::cast(&home.pl);
04780 } else {
04781 c = NULL;
04782 }
04783 }
04784 }
04785 }
04786 forceinline Propagator&
04787 Space::Propagators::propagator(void) const {
04788 return *Propagator::cast(c);
04789 }
04790
04791
04792 forceinline
04793 Space::ScheduledPropagators::ScheduledPropagators(Space& home0)
04794 : home(home0), q(home.pc.p.active) {
04795 while (q >= &home.pc.p.queue[0]) {
04796 if (q->next() != q) {
04797 c = q->next(); e = q; q--;
04798 return;
04799 }
04800 q--;
04801 }
04802 q = c = e = NULL;
04803 }
04804 forceinline bool
04805 Space::ScheduledPropagators::operator ()(void) const {
04806 return c != NULL;
04807 }
04808 forceinline void
04809 Space::ScheduledPropagators::operator ++(void) {
04810 c = c->next();
04811 if (c == e) {
04812 if (q == NULL) {
04813 c = NULL;
04814 } else {
04815 while (q >= &home.pc.p.queue[0]) {
04816 if (q->next() != q) {
04817 c = q->next(); e = q; q--;
04818 return;
04819 }
04820 q--;
04821 }
04822 q = c = e = NULL;
04823 }
04824 }
04825 }
04826 forceinline Propagator&
04827 Space::ScheduledPropagators::propagator(void) const {
04828 return *Propagator::cast(c);
04829 }
04830
04831
04832 forceinline
04833 Space::IdlePropagators::IdlePropagators(Space& home) {
04834 c = Propagator::cast(home.pl.next());
04835 e = Propagator::cast(&home.pl);
04836 }
04837 forceinline bool
04838 Space::IdlePropagators::operator ()(void) const {
04839 return c != e;
04840 }
04841 forceinline void
04842 Space::IdlePropagators::operator ++(void) {
04843 c = c->next();
04844 }
04845 forceinline Propagator&
04846 Space::IdlePropagators::propagator(void) const {
04847 return *Propagator::cast(c);
04848 }
04849
04850
04851 forceinline
04852 Space::Branchers::Branchers(Space& home)
04853 : c(Brancher::cast(home.bl.next())), e(&home.bl) {}
04854 forceinline bool
04855 Space::Branchers::operator ()(void) const {
04856 return c != e;
04857 }
04858 forceinline void
04859 Space::Branchers::operator ++(void) {
04860 c = c->next();
04861 }
04862 forceinline Brancher&
04863 Space::Branchers::brancher(void) const {
04864 return *Brancher::cast(c);
04865 }
04866
04867
04868
04869
04870
04871 forceinline
04872 Group::Group(unsigned int gid0) : gid(gid0) {}
04873
04874 forceinline bool
04875 Group::in(Group actor) const {
04876 return (gid == GROUPID_ALL) || (gid == actor.gid);
04877 }
04878
04879 forceinline bool
04880 Group::in(void) const {
04881 return (gid != GROUPID_ALL) && (gid != GROUPID_DEF);
04882 }
04883
04884 forceinline
04885 Group::Group(const Group& g) : gid(g.gid) {}
04886
04887 forceinline Group&
04888 Group::operator =(const Group& g) {
04889 gid=g.gid; return *this;
04890 }
04891
04892 forceinline unsigned int
04893 Group::id(void) const {
04894 return gid;
04895 }
04896
04897
04898 forceinline
04899 PropagatorGroup::PropagatorGroup(void) {}
04900
04901 forceinline
04902 PropagatorGroup::PropagatorGroup(unsigned int gid)
04903 : Group(gid) {}
04904
04905 forceinline
04906 PropagatorGroup::PropagatorGroup(const PropagatorGroup& g)
04907 : Group(g) {}
04908
04909 forceinline PropagatorGroup&
04910 PropagatorGroup::operator =(const PropagatorGroup& g) {
04911 return static_cast<PropagatorGroup&>(Group::operator =(g));
04912 }
04913
04914 forceinline Home
04915 PropagatorGroup::operator ()(Space& home) {
04916 return Home(home,NULL,*this,BrancherGroup::def);
04917 }
04918
04919 forceinline bool
04920 PropagatorGroup::operator ==(PropagatorGroup g) const {
04921 return id() == g.id();
04922 }
04923 forceinline bool
04924 PropagatorGroup::operator !=(PropagatorGroup g) const {
04925 return id() != g.id();
04926 }
04927
04928 forceinline PropagatorGroup&
04929 PropagatorGroup::move(Space& , Propagator& p) {
04930 if (id() != GROUPID_ALL)
04931 p.group(*this);
04932 return *this;
04933 }
04934
04935
04936 forceinline
04937 BrancherGroup::BrancherGroup(void) {}
04938
04939 forceinline
04940 BrancherGroup::BrancherGroup(unsigned int gid)
04941 : Group(gid) {}
04942
04943 forceinline
04944 BrancherGroup::BrancherGroup(const BrancherGroup& g)
04945 : Group(g) {}
04946
04947 forceinline BrancherGroup&
04948 BrancherGroup::operator =(const BrancherGroup& g) {
04949 return static_cast<BrancherGroup&>(Group::operator =(g));
04950 }
04951
04952 forceinline Home
04953 BrancherGroup::operator ()(Space& home) {
04954 return Home(home,NULL,PropagatorGroup::def,*this);
04955 }
04956
04957 forceinline bool
04958 BrancherGroup::operator ==(BrancherGroup g) const {
04959 return id() == g.id();
04960 }
04961 forceinline bool
04962 BrancherGroup::operator !=(BrancherGroup g) const {
04963 return id() != g.id();
04964 }
04965
04966 forceinline BrancherGroup&
04967 BrancherGroup::move(Space& , Brancher& p) {
04968 if (id() != GROUPID_ALL)
04969 p.group(*this);
04970 return *this;
04971 }
04972
04973
04974
04975
04976
04977
04978 forceinline
04979 Propagators::Propagators(Space& home, PropagatorGroup g0)
04980 : ps(home), g(g0) {
04981 while (ps() && !g.in(ps.propagator().group()))
04982 ++ps;
04983 }
04984 forceinline bool
04985 Propagators::operator ()(void) const {
04986 return ps();
04987 }
04988 forceinline void
04989 Propagators::operator ++(void) {
04990 do
04991 ++ps;
04992 while (ps() && !g.in(ps.propagator().group()));
04993 }
04994 forceinline const Propagator&
04995 Propagators::propagator(void) const {
04996 return ps.propagator();
04997 }
04998
04999 forceinline
05000 Branchers::Branchers(Space& home, BrancherGroup g0)
05001 : bs(home), g(g0) {
05002 while (bs() && !g.in(bs.brancher().group()))
05003 ++bs;
05004 }
05005 forceinline bool
05006 Branchers::operator ()(void) const {
05007 return bs();
05008 }
05009 forceinline void
05010 Branchers::operator ++(void) {
05011 do
05012 ++bs;
05013 while (bs() && !g.in(bs.brancher().group()));
05014 }
05015 forceinline const Brancher&
05016 Branchers::brancher(void) const {
05017 return bs.brancher();
05018 }
05019
05020
05021
05022
05023
05024
05025 template<class T>
05026 forceinline T&
05027 Space::construct(void) {
05028 return alloc<T>(1);
05029 }
05030 template<class T, typename A1>
05031 forceinline T&
05032 Space::construct(A1 const& a1) {
05033 T& t = *static_cast<T*>(ralloc(sizeof(T)));
05034 new (&t) T(a1);
05035 return t;
05036 }
05037 template<class T, typename A1, typename A2>
05038 forceinline T&
05039 Space::construct(A1 const& a1, A2 const& a2) {
05040 T& t = *static_cast<T*>(ralloc(sizeof(T)));
05041 new (&t) T(a1,a2);
05042 return t;
05043 }
05044 template<class T, typename A1, typename A2, typename A3>
05045 forceinline T&
05046 Space::construct(A1 const& a1, A2 const& a2, A3 const& a3) {
05047 T& t = *static_cast<T*>(ralloc(sizeof(T)));
05048 new (&t) T(a1,a2,a3);
05049 return t;
05050 }
05051 template<class T, typename A1, typename A2, typename A3, typename A4>
05052 forceinline T&
05053 Space::construct(A1 const& a1, A2 const& a2, A3 const& a3, A4 const& a4) {
05054 T& t = *static_cast<T*>(ralloc(sizeof(T)));
05055 new (&t) T(a1,a2,a3,a4);
05056 return t;
05057 }
05058 template<class T, typename A1, typename A2, typename A3, typename A4, typename A5>
05059 forceinline T&
05060 Space::construct(A1 const& a1, A2 const& a2, A3 const& a3, A4 const& a4, A5 const& a5) {
05061 T& t = *static_cast<T*>(ralloc(sizeof(T)));
05062 new (&t) T(a1,a2,a3,a4,a5);
05063 return t;
05064 }
05065
05066 }
05067
05068