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 PostTraceInfo;
00151 class TraceRecorder;
00152 class TraceFilter;
00153 class Tracer;
00154
00155 template<class A> class Council;
00156 template<class A> class Advisors;
00157 template<class VIC> class VarImp;
00158
00159
00160
00161
00162
00163
00164
00172 class VarImpBase {};
00173
00180 class GECODE_VTABLE_EXPORT VarImpDisposerBase {
00181 public:
00183 GECODE_KERNEL_EXPORT virtual void dispose(Space& home, VarImpBase* x);
00185 GECODE_KERNEL_EXPORT virtual ~VarImpDisposerBase(void);
00186 };
00187
00194 template<class VarImp>
00195 class VarImpDisposer : public VarImpDisposerBase {
00196 public:
00198 VarImpDisposer(void);
00200 virtual void dispose(Space& home, VarImpBase* x);
00201 };
00202
00204 class Delta {
00205 template<class VIC> friend class VarImp;
00206 private:
00208 ModEvent me;
00209 };
00210
00218 template<class VIC>
00219 class VarImp : public VarImpBase {
00220 friend class Space;
00221 friend class Propagator;
00222 template<class VarImp> friend class VarImpDisposer;
00223 friend class SubscribedPropagators;
00224 private:
00225 union {
00233 ActorLink** base;
00242 VarImp<VIC>* fwd;
00243 } b;
00244
00246 static const int idx_c = VIC::idx_c;
00248 static const int idx_d = VIC::idx_d;
00250 static const int free_bits = VIC::free_bits;
00252 unsigned int entries;
00254 unsigned int free_and_bits;
00256 static const Gecode::PropCond pc_max = VIC::pc_max;
00257 #ifdef GECODE_HAS_CBS
00258
00259 const unsigned var_id;
00260 #endif
00261
00262 union {
00273 unsigned int idx[pc_max+1];
00275 VarImp<VIC>* next;
00276 } u;
00277
00279 ActorLink** actor(PropCond pc);
00281 ActorLink** actorNonZero(PropCond pc);
00283 unsigned int& idx(PropCond pc);
00285 unsigned int idx(PropCond pc) const;
00286
00293 void update(VarImp* x, ActorLink**& sub);
00300 static void update(Space& home, ActorLink**& sub);
00301
00303 void enter(Space& home, Propagator* p, PropCond pc);
00305 void enter(Space& home, Advisor* a);
00307 void resize(Space& home);
00309 void remove(Space& home, Propagator* p, PropCond pc);
00311 void remove(Space& home, Advisor* a);
00312
00313
00314 protected:
00316 void cancel(Space& home);
00322 bool advise(Space& home, ModEvent me, Delta& d);
00323 private:
00325 void _fail(Space& home);
00326 protected:
00328 ModEvent fail(Space& home);
00329 #ifdef GECODE_HAS_VAR_DISPOSE
00330
00331 static VarImp<VIC>* vars_d(Space& home);
00333 static void vars_d(Space& home, VarImp<VIC>* x);
00334 #endif
00335
00336 public:
00338 VarImp(Space& home);
00340 VarImp(void);
00341
00342 #ifdef GECODE_HAS_CBS
00343
00344 unsigned int id(void) const;
00345 #endif
00346
00348
00349
00361 void subscribe(Space& home, Propagator& p, PropCond pc,
00362 bool assigned, ModEvent me, bool schedule);
00364 void cancel(Space& home, Propagator& p, PropCond pc);
00373 void subscribe(Space& home, Advisor& a, bool assigned, bool fail);
00375 void cancel(Space& home, Advisor& a, bool fail);
00376
00383 unsigned int degree(void) const;
00390 double afc(void) const;
00392
00394
00395
00396 VarImp(Space& home, VarImp& x);
00398 bool copied(void) const;
00400 VarImp* forward(void) const;
00402 VarImp* next(void) const;
00404
00406
00407
00414 static void schedule(Space& home, Propagator& p, ModEvent me,
00415 bool force = false);
00423 static void reschedule(Space& home, Propagator& p, PropCond pc,
00424 bool assigned, ModEvent me);
00426 static ModEvent me(const ModEventDelta& med);
00428 static ModEventDelta med(ModEvent me);
00430 static ModEvent me_combine(ModEvent me1, ModEvent me2);
00432
00434
00435
00436 static ModEvent modevent(const Delta& d);
00438
00440
00441
00442 unsigned int bits(void) const;
00444 unsigned int& bits(void);
00446
00447 protected:
00449 void schedule(Space& home, PropCond pc1, PropCond pc2, ModEvent me);
00450
00451 public:
00453
00454
00455 static void* operator new(size_t,Space&);
00457 static void operator delete(void*,Space&);
00459 static void operator delete(void*);
00461 };
00462
00463
00472 enum ExecStatus {
00473 __ES_SUBSUMED = -2,
00474 ES_FAILED = -1,
00475 ES_NOFIX = 0,
00476 ES_OK = 0,
00477 ES_FIX = 1,
00478 ES_NOFIX_FORCE = 2,
00479 __ES_PARTIAL = 2
00480 };
00481
00486 class PropCost {
00487 friend class Space;
00488 public:
00490 enum ActualCost {
00491 AC_RECORD = 0,
00492 AC_CRAZY_LO = 1,
00493 AC_CRAZY_HI = 1,
00494 AC_CUBIC_LO = 1,
00495 AC_CUBIC_HI = 1,
00496 AC_QUADRATIC_LO = 2,
00497 AC_QUADRATIC_HI = 2,
00498 AC_LINEAR_HI = 3,
00499 AC_LINEAR_LO = 4,
00500 AC_TERNARY_HI = 4,
00501 AC_BINARY_HI = 5,
00502 AC_TERNARY_LO = 5,
00503 AC_BINARY_LO = 6,
00504 AC_UNARY_LO = 6,
00505 AC_UNARY_HI = 6,
00506 AC_MAX = 6
00507 };
00509 ActualCost ac;
00510 public:
00512 enum Mod {
00513 LO,
00514 HI
00515 };
00516 private:
00518 static PropCost cost(Mod m, ActualCost lo, ActualCost hi, unsigned int n);
00520 PropCost(ActualCost ac);
00521 public:
00523 static PropCost record(void);
00525 static PropCost crazy(PropCost::Mod m, unsigned int n);
00527 static PropCost crazy(PropCost::Mod m, int n);
00529 static PropCost cubic(PropCost::Mod m, unsigned int n);
00531 static PropCost cubic(PropCost::Mod m, int n);
00533 static PropCost quadratic(PropCost::Mod m, unsigned int n);
00535 static PropCost quadratic(PropCost::Mod m, int n);
00537 static PropCost linear(PropCost::Mod m, unsigned int n);
00539 static PropCost linear(PropCost::Mod m, int n);
00541 static PropCost ternary(PropCost::Mod m);
00543 static PropCost binary(PropCost::Mod m);
00545 static PropCost unary(PropCost::Mod m);
00546 };
00547
00548
00553 enum ActorProperty {
00562 AP_DISPOSE = (1 << 0),
00568 AP_WEAKLY = (1 << 1),
00573 AP_VIEW_TRACE = (1 << 2),
00578 AP_TRACE = (1 << 3)
00579 };
00580
00581
00589 class ActorLink {
00590 friend class Actor;
00591 friend class Propagator;
00592 friend class Advisor;
00593 friend class Brancher;
00594 friend class LocalObject;
00595 friend class Space;
00596 template<class VIC> friend class VarImp;
00597 private:
00598 ActorLink* _next; ActorLink* _prev;
00599 public:
00601
00602 ActorLink* prev(void) const; void prev(ActorLink*);
00603 ActorLink* next(void) const; void next(ActorLink*);
00604 ActorLink** next_ref(void);
00606
00608 void init(void);
00610 void unlink(void);
00612 void head(ActorLink* al);
00614 void tail(ActorLink* al);
00616 bool empty(void) const;
00618 template<class T> static ActorLink* cast(T* a);
00620 template<class T> static const ActorLink* cast(const T* a);
00621 };
00622
00623
00628 class GECODE_VTABLE_EXPORT Actor : private ActorLink {
00629 friend class ActorLink;
00630 friend class Space;
00631 friend class Propagator;
00632 friend class Advisor;
00633 friend class Brancher;
00634 friend class LocalObject;
00635 template<class VIC> friend class VarImp;
00636 template<class A> friend class Council;
00637 private:
00639 static Actor* cast(ActorLink* al);
00641 static const Actor* cast(const ActorLink* al);
00643 GECODE_KERNEL_EXPORT static Actor* sentinel;
00644 public:
00646 virtual Actor* copy(Space& home) = 0;
00647
00649
00650
00651 GECODE_KERNEL_EXPORT
00652 virtual size_t dispose(Space& home);
00654 static void* operator new(size_t s, Space& home);
00656 static void operator delete(void* p, Space& home);
00658 public:
00660 GECODE_KERNEL_EXPORT virtual ~Actor(void);
00662 static void* operator new(size_t s);
00664 static void operator delete(void* p);
00665 };
00666
00667 class Home;
00668
00673 class Group {
00674 friend class Home;
00675 friend class Propagator;
00676 friend class Brancher;
00677 friend class ViewTraceInfo;
00678 friend class PropagateTraceInfo;
00679 friend class CommitTraceInfo;
00680 friend class PostTraceInfo;
00681 protected:
00683 static const unsigned int GROUPID_ALL = 0U;
00685 static const unsigned int GROUPID_DEF = 1U;
00687 static const unsigned int GROUPID_MAX = UINT_MAX >> 2;
00689 unsigned int gid;
00691 GECODE_KERNEL_EXPORT
00692 static unsigned int next;
00694 GECODE_KERNEL_EXPORT
00695 static Support::Mutex m;
00697 Group(unsigned int gid0);
00698 public:
00700
00701
00702 GECODE_KERNEL_EXPORT
00703 Group(void);
00705 Group(const Group& g);
00707 Group& operator =(const Group& g);
00709 unsigned int id(void) const;
00711 bool in(Group a) const;
00713 bool in(void) const;
00715
00716 GECODE_KERNEL_EXPORT
00717 static Group all;
00719 GECODE_KERNEL_EXPORT
00720 static Group def;
00721 };
00722
00727 class PropagatorGroup : public Group {
00728 friend class Propagator;
00729 friend class ViewTraceInfo;
00730 friend class PropagateTraceInfo;
00731 friend class PostTraceInfo;
00732 protected:
00734 PropagatorGroup(unsigned int gid);
00735 public:
00737
00738
00739 PropagatorGroup(void);
00741 PropagatorGroup(const PropagatorGroup& g);
00743 PropagatorGroup& operator =(const PropagatorGroup& g);
00745 Home operator ()(Space& home);
00747
00748
00749
00750 GECODE_KERNEL_EXPORT
00751 PropagatorGroup& move(Space& home, PropagatorGroup g);
00753 PropagatorGroup& move(Space& home, Propagator& p);
00760 GECODE_KERNEL_EXPORT
00761 PropagatorGroup& move(Space& home, unsigned int id);
00763
00764
00765
00766 bool operator ==(PropagatorGroup g) const;
00768 bool operator !=(PropagatorGroup g) const;
00770 GECODE_KERNEL_EXPORT
00771 unsigned int size(Space& home) const;
00773 GECODE_KERNEL_EXPORT
00774 void kill(Space& home);
00776 GECODE_KERNEL_EXPORT
00777 void disable(Space& home);
00784 GECODE_KERNEL_EXPORT
00785 void enable(Space& home, bool s=true);
00787
00788 GECODE_KERNEL_EXPORT
00789 static PropagatorGroup all;
00791 GECODE_KERNEL_EXPORT
00792 static PropagatorGroup def;
00793 };
00794
00799 class BrancherGroup : public Group {
00800 friend class Brancher;
00801 protected:
00803 BrancherGroup(unsigned int gid);
00804 public:
00806
00807
00808 BrancherGroup(void);
00810 BrancherGroup(const BrancherGroup& g);
00812 BrancherGroup& operator =(const BrancherGroup& g);
00814 Home operator ()(Space& home);
00816
00817
00818
00819 GECODE_KERNEL_EXPORT
00820 BrancherGroup& move(Space& home, BrancherGroup g);
00822 BrancherGroup& move(Space& home, Brancher& b);
00829 GECODE_KERNEL_EXPORT
00830 BrancherGroup& move(Space& home, unsigned int id);
00832
00833
00834
00835 bool operator ==(BrancherGroup g) const;
00837 bool operator !=(BrancherGroup g) const;
00839 GECODE_KERNEL_EXPORT
00840 unsigned int size(Space& home) const;
00842 GECODE_KERNEL_EXPORT
00843 void kill(Space& home);
00845
00846 GECODE_KERNEL_EXPORT
00847 static BrancherGroup all;
00849 GECODE_KERNEL_EXPORT
00850 static BrancherGroup def;
00851 };
00852
00856 class Home {
00857 friend class PostInfo;
00858 protected:
00860 Space& s;
00862 Propagator* p;
00864 PropagatorGroup pg;
00866 BrancherGroup bg;
00867 public:
00869
00870
00871 Home(Space& s, Propagator* p=NULL,
00872 PropagatorGroup pg=PropagatorGroup::def,
00873 BrancherGroup bg=BrancherGroup::def);
00875 Home& operator =(const Home& h);
00877 operator Space&(void);
00879
00880
00881
00882 Home operator ()(Propagator& p);
00884 Home operator ()(PropagatorGroup pg);
00886 Home operator ()(BrancherGroup bg);
00888 Propagator* propagator(void) const;
00890 PropagatorGroup propagatorgroup(void) const;
00892 BrancherGroup branchergroup(void) const;
00894
00895
00896
00897 bool failed(void) const;
00899 void fail(void);
00901 void notice(Actor& a, ActorProperty p, bool duplicate=false);
00903 };
00904
00908 class ViewTraceInfo {
00909 friend class Space;
00910 friend class PostInfo;
00911 public:
00913 enum What {
00915 PROPAGATOR = 0,
00917 BRANCHER = 1,
00919 POST = 2,
00921 OTHER = 3
00922 };
00923 protected:
00925 ptrdiff_t who;
00927 void propagator(Propagator& p);
00929 void brancher(Brancher& b);
00931 void post(PropagatorGroup g);
00933 void other(void);
00934 public:
00936 What what(void) const;
00938 const Propagator& propagator(void) const;
00940 const Brancher& brancher(void) const;
00942 PropagatorGroup post(void) const;
00943 };
00944
00948 class PostInfo {
00949 friend class Space;
00950 protected:
00952 Space& h;
00954 PropagatorGroup pg;
00956 unsigned int pid;
00958 bool nested;
00959 public:
00961 PostInfo(Home home);
00963 ~PostInfo(void);
00964 };
00965
00969 class PropagateTraceInfo {
00970 friend class Space;
00971 public:
00973 enum Status {
00974 FIX,
00975 NOFIX,
00976 FAILED,
00977 SUBSUMED
00978 };
00979 protected:
00981 unsigned int i;
00983 PropagatorGroup g;
00985 const Propagator* p;
00987 Status s;
00989 PropagateTraceInfo(unsigned int i, PropagatorGroup g,
00990 const Propagator* p, Status s);
00991 public:
00993 unsigned int id(void) const;
00995 PropagatorGroup group(void) const;
00997 const Propagator* propagator(void) const;
00999 Status status(void) const;
01000 };
01001
01005 class CommitTraceInfo {
01006 friend class Space;
01007 protected:
01009 const Brancher& b;
01011 const Choice& c;
01013 unsigned int a;
01015 CommitTraceInfo(const Brancher& b, const Choice& c, unsigned int a);
01016 public:
01018 unsigned int id(void) const;
01020 BrancherGroup group(void) const;
01022 const Brancher& brancher(void) const;
01024 const Choice& choice(void) const;
01026 unsigned int alternative(void) const;
01027 };
01028
01032 class PostTraceInfo {
01033 friend class Space;
01034 friend class PostInfo;
01035 public:
01037 enum Status {
01038 POSTED,
01039 FAILED,
01040 SUBSUMED
01041 };
01042 protected:
01044 PropagatorGroup g;
01046 Status s;
01048 unsigned int n;
01050 PostTraceInfo(PropagatorGroup g, Status s, unsigned int n);
01051 public:
01053 Status status(void) const;
01055 PropagatorGroup group(void) const;
01057 unsigned int propagators(void) const;
01058 };
01059
01064 class GECODE_VTABLE_EXPORT Propagator : public Actor {
01065 friend class ActorLink;
01066 friend class Space;
01067 template<class VIC> friend class VarImp;
01068 friend class Advisor;
01069 template<class A> friend class Council;
01070 friend class SubscribedPropagators;
01071 friend class PropagatorGroup;
01072 private:
01073 union {
01075 ModEventDelta med;
01077 size_t size;
01079 Gecode::ActorLink* advisors;
01080 } u;
01082 void* gpi_disabled;
01084 static Propagator* cast(ActorLink* al);
01086 static const Propagator* cast(const ActorLink* al);
01088 void disable(Space& home);
01090 void enable(Space& home);
01091 protected:
01093 Propagator(Home home);
01095 Propagator(Space& home, Propagator& p);
01097 Propagator* fwd(void) const;
01099 Kernel::GPI::Info& gpi(void);
01100
01101 public:
01103
01104
01112 virtual void reschedule(Space& home) = 0;
01136 virtual ExecStatus propagate(Space& home, const ModEventDelta& med) = 0;
01138 virtual PropCost cost(const Space& home, const ModEventDelta& med) const = 0;
01146 ModEventDelta modeventdelta(void) const;
01182 GECODE_KERNEL_EXPORT
01183 virtual ExecStatus advise(Space& home, Advisor& a, const Delta& d);
01185 GECODE_KERNEL_EXPORT
01186 virtual void advise(Space& home, Advisor& a);
01188
01189
01190
01191 double afc(void) const;
01193 #ifdef GECODE_HAS_CBS
01194
01195
01196
01202
01203 typedef std::function<void(unsigned int prop_id, unsigned int var_id,
01204 int val, double dens)> SendMarginal;
01205 virtual void solndistrib(Space& home, SendMarginal send) const;
01213
01214 typedef std::function<bool(unsigned int var_id)> InDecision;
01215 virtual void domainsizesum(InDecision in, unsigned int& size,
01216 unsigned int& size_b) const;
01218 #endif
01219
01220
01221
01222 unsigned int id(void) const;
01224 PropagatorGroup group(void) const;
01226 void group(PropagatorGroup g);
01228 bool disabled(void) const;
01230 };
01231
01232
01240 template<class A>
01241 class Council {
01242 friend class Advisor;
01243 friend class Advisors<A>;
01244 private:
01246 mutable ActorLink* advisors;
01247 public:
01249 Council(void);
01251 Council(Space& home);
01253 bool empty(void) const;
01255 void update(Space& home, Council<A>& c);
01257 void dispose(Space& home);
01258 };
01259
01260
01265 template<class A>
01266 class Advisors {
01267 private:
01269 ActorLink* a;
01270 public:
01272 Advisors(const Council<A>& c);
01274 bool operator ()(void) const;
01276 void operator ++(void);
01278 A& advisor(void) const;
01279 };
01280
01281
01292 class Advisor : private ActorLink {
01293 template<class VIC> friend class VarImp;
01294 template<class A> friend class Council;
01295 template<class A> friend class Advisors;
01296 friend class SubscribedPropagators;
01297 private:
01299 bool disposed(void) const;
01301 static Advisor* cast(ActorLink* al);
01303 static const Advisor* cast(const ActorLink* al);
01304 protected:
01306 Propagator& propagator(void) const;
01307 public:
01309 template<class A>
01310 Advisor(Space& home, Propagator& p, Council<A>& c);
01312 Advisor(Space& home, Advisor& a);
01314 const ViewTraceInfo& operator ()(const Space& home) const;
01315
01317
01318
01319 template<class A>
01320 void dispose(Space& home, Council<A>& c);
01322 static void* operator new(size_t s, Space& home);
01324 static void operator delete(void* p, Space& home);
01326 private:
01327 #ifndef __GNUC__
01328
01329 static void operator delete(void* p);
01330 #endif
01331
01332 static void* operator new(size_t s);
01333 };
01334
01335
01340 class GECODE_VTABLE_EXPORT NGL {
01341 private:
01343 void* nl;
01344 public:
01346 enum Status {
01347 FAILED,
01348 SUBSUMED,
01349 NONE
01350 };
01352 NGL(void);
01354 NGL(Space& home);
01356 NGL(Space& home, NGL& ngl);
01358 virtual void subscribe(Space& home, Propagator& p) = 0;
01360 virtual void cancel(Space& home, Propagator& p) = 0;
01362 virtual void reschedule(Space& home, Propagator& p) = 0;
01364 virtual NGL::Status status(const Space& home) const = 0;
01366 virtual ExecStatus prune(Space& home) = 0;
01368 virtual NGL* copy(Space& home) = 0;
01370 GECODE_KERNEL_EXPORT
01371 virtual bool notice(void) const;
01373 virtual size_t dispose(Space& home);
01375
01376
01377 bool leaf(void) const;
01379 NGL* next(void) const;
01381 void leaf(bool l);
01383 void next(NGL* n);
01385 NGL* add(NGL* n, bool l);
01387
01388
01389
01390 static void* operator new(size_t s, Space& home);
01392 static void operator delete(void* s, Space& home);
01394 static void operator delete(void* p);
01396 public:
01398 GECODE_KERNEL_EXPORT virtual ~NGL(void);
01400 static void* operator new(size_t s);
01401 };
01402
01412 class GECODE_VTABLE_EXPORT Choice : public HeapAllocated {
01413 friend class Space;
01414 private:
01415 unsigned int bid;
01416 unsigned int alt;
01417
01419 unsigned int id(void) const;
01420 protected:
01422 Choice(const Brancher& b, const unsigned int a);
01423 public:
01425 unsigned int alternatives(void) const;
01427 GECODE_KERNEL_EXPORT virtual ~Choice(void);
01429 GECODE_KERNEL_EXPORT
01430 virtual void archive(Archive& e) const;
01431 };
01432
01442 class GECODE_VTABLE_EXPORT Brancher : public Actor {
01443 friend class ActorLink;
01444 friend class Space;
01445 friend class Choice;
01446 private:
01448 unsigned int bid;
01450 unsigned int gid;
01452 static Brancher* cast(ActorLink* al);
01454 static const Brancher* cast(const ActorLink* al);
01455 protected:
01457 Brancher(Home home);
01459 Brancher(Space& home, Brancher& b);
01460 public:
01462
01463
01471 virtual bool status(const Space& home) const = 0;
01479 virtual const Choice* choice(Space& home) = 0;
01481 virtual const Choice* choice(const Space& home, Archive& e) = 0;
01488 virtual ExecStatus commit(Space& home, const Choice& c,
01489 unsigned int a) = 0;
01503 GECODE_KERNEL_EXPORT
01504 virtual NGL* ngl(Space& home, const Choice& c, unsigned int a) const;
01512 GECODE_KERNEL_EXPORT
01513 virtual void print(const Space& home, const Choice& c, unsigned int a,
01514 std::ostream& o) const;
01516
01517
01518
01519 unsigned int id(void) const;
01521 BrancherGroup group(void) const;
01523 void group(BrancherGroup g);
01525 };
01526
01533 class LocalObject : public Actor {
01534 friend class ActorLink;
01535 friend class Space;
01536 friend class LocalHandle;
01537 protected:
01539 LocalObject(Home home);
01541 LocalObject(Space& home, LocalObject& l);
01543 static LocalObject* cast(ActorLink* al);
01545 static const LocalObject* cast(const ActorLink* al);
01546 private:
01548 GECODE_KERNEL_EXPORT void fwdcopy(Space& home);
01549 public:
01551 LocalObject* fwd(Space& home);
01552 };
01553
01558 class LocalHandle {
01559 private:
01561 LocalObject* o;
01562 protected:
01564 LocalHandle(void);
01566 LocalHandle(LocalObject* lo);
01568 LocalHandle(const LocalHandle& lh);
01569 public:
01571 LocalHandle& operator =(const LocalHandle& lh);
01573 void update(Space& home, LocalHandle& lh);
01575 ~LocalHandle(void);
01576 protected:
01578 LocalObject* object(void) const;
01580 void object(LocalObject* n);
01581 };
01582
01583
01588 class GECODE_VTABLE_EXPORT NoGoods {
01589 protected:
01591 unsigned long int n;
01592 public:
01594 NoGoods(void);
01596 GECODE_KERNEL_EXPORT
01597 virtual void post(Space& home) const;
01599 unsigned long int ng(void) const;
01601 void ng(unsigned long int n);
01603 virtual ~NoGoods(void);
01605 GECODE_KERNEL_EXPORT
01606 static NoGoods eng;
01607 };
01608
01613 class GECODE_VTABLE_EXPORT MetaInfo {
01614 public:
01616 enum Type {
01618 RESTART,
01620 PORTFOLIO
01621 };
01622 protected:
01624 const Type t;
01626
01627
01628 const unsigned long int r;
01630 const unsigned long int s;
01632 const unsigned long int f;
01634 const Space* l;
01636 const NoGoods& ng;
01638
01639
01640
01641 const unsigned int a;
01643 public:
01645
01646
01647 MetaInfo(unsigned long int r,
01648 unsigned long int s,
01649 unsigned long int f,
01650 const Space* l,
01651 NoGoods& ng);
01653 MetaInfo(unsigned int a);
01655
01656 Type type(void) const;
01658
01659
01660 unsigned long int restart(void) const;
01662 unsigned long int solution(void) const;
01664 unsigned long int fail(void) const;
01666 const Space* last(void) const;
01668 const NoGoods& nogoods(void) const;
01670
01671
01672
01673 unsigned int asset(void) const;
01675 };
01676
01681 enum SpaceStatus {
01682 SS_FAILED,
01683 SS_SOLVED,
01684 SS_BRANCH
01685 };
01686
01691 class StatusStatistics {
01692 public:
01694 unsigned long int propagate;
01696 StatusStatistics(void);
01698 void reset(void);
01700 StatusStatistics operator +(const StatusStatistics& s);
01702 StatusStatistics& operator +=(const StatusStatistics& s);
01703 };
01704
01709 class CloneStatistics {
01710 public:
01712 CloneStatistics(void);
01714 void reset(void);
01716 CloneStatistics operator +(const CloneStatistics& s);
01718 CloneStatistics& operator +=(const CloneStatistics& s);
01719 };
01720
01725 class CommitStatistics {
01726 public:
01728 CommitStatistics(void);
01730 void reset(void);
01732 CommitStatistics operator +(const CommitStatistics& s);
01734 CommitStatistics& operator +=(const CommitStatistics& s);
01735 };
01736
01737
01738
01742 class GECODE_VTABLE_EXPORT Space : public HeapAllocated {
01743 friend class Actor;
01744 friend class Propagator;
01745 friend class PropagatorGroup;
01746 friend class Propagators;
01747 friend class Brancher;
01748 friend class BrancherGroup;
01749 friend class Branchers;
01750 friend class Advisor;
01751 template <class A> friend class Council;
01752 template<class VIC> friend class VarImp;
01753 template<class VarImp> friend class VarImpDisposer;
01754 friend class LocalObject;
01755 friend class Region;
01756 friend class AFC;
01757 friend class PostInfo;
01758 friend GECODE_KERNEL_EXPORT
01759 void trace(Home home, TraceFilter tf, int te, Tracer& t);
01760 private:
01762 Kernel::SharedSpaceData ssd;
01764 Kernel::MemoryManager mm;
01765 #ifdef GECODE_HAS_CBS
01766
01767 unsigned int var_id_counter;
01768 #endif
01769
01770 ActorLink pl;
01772 ActorLink bl;
01778 Brancher* b_status;
01790 Brancher* b_commit;
01792 Brancher* brancher(unsigned int id);
01793
01795 void kill(Brancher& b);
01797 void kill(Propagator& p);
01798
01800 GECODE_KERNEL_EXPORT
01801 void kill_brancher(unsigned int id);
01802
01804 static const unsigned reserved_bid = 0U;
01805
01807 static const unsigned int sc_bits = 2;
01809 static const unsigned int sc_fast = 0;
01811 static const unsigned int sc_disabled = 1;
01813 static const unsigned int sc_trace = 2;
01814
01815 union {
01817 struct {
01830 ActorLink* active;
01832 ActorLink queue[PropCost::AC_MAX+1];
01839 unsigned int bid_sc;
01841 unsigned int n_sub;
01843 ViewTraceInfo vti;
01844 } p;
01846 struct {
01848 VarImpBase* vars_u[AllVarConf::idx_c];
01850 VarImpBase* vars_noidx;
01852 LocalObject* local;
01853 } c;
01854 } pc;
01856 void enqueue(Propagator* p);
01861 #ifdef GECODE_HAS_VAR_DISPOSE
01862
01863 GECODE_KERNEL_EXPORT static VarImpDisposerBase* vd[AllVarConf::idx_d];
01865 VarImpBase* _vars_d[AllVarConf::idx_d];
01867 template<class VIC> VarImpBase* vars_d(void) const;
01869 template<class VIC> void vars_d(VarImpBase* x);
01870 #endif
01871
01872 void update(ActorLink** sub);
01874
01876 Actor** d_fst;
01878 Actor** d_cur;
01880 Actor** d_lst;
01881
01883 GECODE_KERNEL_EXPORT static StatusStatistics unused_status;
01885 GECODE_KERNEL_EXPORT static CloneStatistics unused_clone;
01887 GECODE_KERNEL_EXPORT static CommitStatistics unused_commit;
01888
01902 GECODE_KERNEL_EXPORT Space* _clone(void);
01903
01936 GECODE_KERNEL_EXPORT
01937 void _commit(const Choice& c, unsigned int a);
01938
01969 GECODE_KERNEL_EXPORT
01970 void _trycommit(const Choice& c, unsigned int a);
01971
01973 GECODE_KERNEL_EXPORT
01974 TraceRecorder* findtracerecorder(void);
01976 GECODE_KERNEL_EXPORT
01977 void post(const PostInfo& pi);
01978
01985 GECODE_KERNEL_EXPORT
01986 void ap_notice_dispose(Actor* a, bool d);
01993 GECODE_KERNEL_EXPORT
01994 void ap_ignore_dispose(Actor* a, bool d);
01995 public:
02000 GECODE_KERNEL_EXPORT
02001 Space(void);
02010 GECODE_KERNEL_EXPORT
02011 Space(Space& s);
02016 GECODE_KERNEL_EXPORT
02017 virtual ~Space(void);
02024 virtual Space* copy(void) = 0;
02035 GECODE_KERNEL_EXPORT virtual void constrain(const Space& best);
02059 GECODE_KERNEL_EXPORT
02060 virtual bool master(const MetaInfo& mi);
02086 GECODE_KERNEL_EXPORT
02087 virtual bool slave(const MetaInfo& mi);
02088
02089
02090
02091
02092
02093
02105 GECODE_KERNEL_EXPORT
02106 SpaceStatus status(StatusStatistics& stat=unused_status);
02107
02139 GECODE_KERNEL_EXPORT
02140 const Choice* choice(void);
02141
02151 GECODE_KERNEL_EXPORT
02152 const Choice* choice(Archive& e) const;
02153
02169 Space* clone(CloneStatistics& stat=unused_clone) const;
02170
02205 void commit(const Choice& c, unsigned int a,
02206 CommitStatistics& stat=unused_commit);
02239 void trycommit(const Choice& c, unsigned int a,
02240 CommitStatistics& stat=unused_commit);
02259 GECODE_KERNEL_EXPORT
02260 NGL* ngl(const Choice& c, unsigned int a);
02261
02276 GECODE_KERNEL_EXPORT
02277 void print(const Choice& c, unsigned int a, std::ostream& o) const;
02278
02287 GECODE_KERNEL_EXPORT
02288 void notice(Actor& a, ActorProperty p, bool duplicate=false);
02296 GECODE_KERNEL_EXPORT
02297 void ignore(Actor& a, ActorProperty p, bool duplicate=false);
02298
02299
02310 ExecStatus ES_SUBSUMED(Propagator& p);
02325 ExecStatus ES_SUBSUMED_DISPOSED(Propagator& p, size_t s);
02336 ExecStatus ES_FIX_PARTIAL(Propagator& p, const ModEventDelta& med);
02347 ExecStatus ES_NOFIX_PARTIAL(Propagator& p, const ModEventDelta& med);
02348
02359 template<class A>
02360 ExecStatus ES_FIX_DISPOSE(Council<A>& c, A& a);
02371 template<class A>
02372 ExecStatus ES_NOFIX_DISPOSE(Council<A>& c, A& a);
02384 template<class A>
02385 ExecStatus ES_NOFIX_DISPOSE_FORCE(Council<A>& c, A& a);
02386
02394 void fail(void);
02403 bool failed(void) const;
02408 bool stable(void) const;
02409
02411
02412
02413 Home operator ()(Propagator& p);
02415 Home operator ()(PropagatorGroup pg);
02417 Home operator ()(BrancherGroup bg);
02419
02431 template<class T>
02432 T* alloc(long unsigned int n);
02439 template<class T>
02440 T* alloc(long int n);
02447 template<class T>
02448 T* alloc(unsigned int n);
02455 template<class T>
02456 T* alloc(int n);
02466 template<class T>
02467 void free(T* b, long unsigned int n);
02477 template<class T>
02478 void free(T* b, long int n);
02488 template<class T>
02489 void free(T* b, unsigned int n);
02499 template<class T>
02500 void free(T* b, int n);
02512 template<class T>
02513 T* realloc(T* b, long unsigned int n, long unsigned int m);
02525 template<class T>
02526 T* realloc(T* b, long int n, long int m);
02538 template<class T>
02539 T* realloc(T* b, unsigned int n, unsigned int m);
02551 template<class T>
02552 T* realloc(T* b, int n, int m);
02560 template<class T>
02561 T** realloc(T** b, long unsigned int n, long unsigned int m);
02569 template<class T>
02570 T** realloc(T** b, long int n, long int m);
02578 template<class T>
02579 T** realloc(T** b, unsigned int n, unsigned int m);
02587 template<class T>
02588 T** realloc(T** b, int n, int m);
02590 void* ralloc(size_t s);
02592 void rfree(void* p, size_t s);
02594 void* rrealloc(void* b, size_t n, size_t m);
02596 template<size_t> void* fl_alloc(void);
02602 template<size_t> void fl_dispose(FreeList* f, FreeList* l);
02604
02605
02606
02609 template<class T>
02610 T& construct(void);
02616 template<class T, typename A1>
02617 T& construct(A1 const& a1);
02623 template<class T, typename A1, typename A2>
02624 T& construct(A1 const& a1, A2 const& a2);
02630 template<class T, typename A1, typename A2, typename A3>
02631 T& construct(A1 const& a1, A2 const& a2, A3 const& a3);
02637 template<class T, typename A1, typename A2, typename A3, typename A4>
02638 T& construct(A1 const& a1, A2 const& a2, A3 const& a3, A4 const& a4);
02644 template<class T, typename A1, typename A2, typename A3, typename A4, typename A5>
02645 T& construct(A1 const& a1, A2 const& a2, A3 const& a3, A4 const& a4, A5 const& a5);
02647
02649
02650
02651 void afc_decay(double d);
02653 double afc_decay(void) const;
02655 GECODE_KERNEL_EXPORT void afc_unshare(void);
02657
02658 protected:
02664 class Propagators {
02665 private:
02667 Space& home;
02669 ActorLink* q;
02671 ActorLink* c;
02673 ActorLink* e;
02674 public:
02676 Propagators(Space& home);
02678 bool operator ()(void) const;
02680 void operator ++(void);
02682 Propagator& propagator(void) const;
02683 };
02689 class ScheduledPropagators {
02690 private:
02692 Space& home;
02694 ActorLink* q;
02696 ActorLink* c;
02698 ActorLink* e;
02699 public:
02701 ScheduledPropagators(Space& home);
02703 bool operator ()(void) const;
02705 void operator ++(void);
02707 Propagator& propagator(void) const;
02708 };
02714 class IdlePropagators {
02715 private:
02717 ActorLink* c;
02719 ActorLink* e;
02720 public:
02722 IdlePropagators(Space& home);
02724 bool operator ()(void) const;
02726 void operator ++(void);
02728 Propagator& propagator(void) const;
02729 };
02735 class Branchers {
02736 private:
02738 ActorLink* c;
02740 ActorLink* e;
02741 public:
02743 Branchers(Space& home);
02745 bool operator ()(void) const;
02747 void operator ++(void);
02749 Brancher& brancher(void) const;
02750 };
02751 };
02752
02754 class Propagators {
02755 private:
02757 Space::Propagators ps;
02759 PropagatorGroup g;
02760 public:
02762 Propagators(const Space& home, PropagatorGroup g);
02764 bool operator ()(void) const;
02766 void operator ++(void);
02768 const Propagator& propagator(void) const;
02769 };
02770
02772 class Branchers {
02773 private:
02775 Space::Branchers bs;
02777 BrancherGroup g;
02778 public:
02780 Branchers(const Space& home, BrancherGroup g);
02782 bool operator ()(void) const;
02784 void operator ++(void);
02786 const Brancher& brancher(void) const;
02787 };
02788
02789
02790
02791
02792
02793
02794
02795
02796
02797
02798 forceinline void*
02799 Space::ralloc(size_t s) {
02800 return mm.alloc(ssd.data().sm,s);
02801 }
02802 forceinline void
02803 Space::rfree(void* p, size_t s) {
02804 return mm.reuse(p,s);
02805 }
02806 forceinline void*
02807 Space::rrealloc(void* _b, size_t n, size_t m) {
02808 char* b = static_cast<char*>(_b);
02809 if (n < m) {
02810 char* p = static_cast<char*>(ralloc(m));
02811 memcpy(p,b,n);
02812 rfree(b,n);
02813 return p;
02814 } else {
02815 rfree(b+m,m-n);
02816 return b;
02817 }
02818 }
02819
02820 template<size_t s>
02821 forceinline void*
02822 Space::fl_alloc(void) {
02823 return mm.template fl_alloc<s>(ssd.data().sm);
02824 }
02825 template<size_t s>
02826 forceinline void
02827 Space::fl_dispose(FreeList* f, FreeList* l) {
02828 mm.template fl_dispose<s>(f,l);
02829 }
02830
02831
02832
02833
02834
02835 template<class T>
02836 forceinline T*
02837 Space::alloc(long unsigned int n) {
02838 T* p = static_cast<T*>(ralloc(sizeof(T)*n));
02839 for (long unsigned int i=0; i<n; i++)
02840 (void) new (p+i) T();
02841 return p;
02842 }
02843 template<class T>
02844 forceinline T*
02845 Space::alloc(long int n) {
02846 assert(n >= 0);
02847 return alloc<T>(static_cast<long unsigned int>(n));
02848 }
02849 template<class T>
02850 forceinline T*
02851 Space::alloc(unsigned int n) {
02852 return alloc<T>(static_cast<long unsigned int>(n));
02853 }
02854 template<class T>
02855 forceinline T*
02856 Space::alloc(int n) {
02857 assert(n >= 0);
02858 return alloc<T>(static_cast<long unsigned int>(n));
02859 }
02860
02861 template<class T>
02862 forceinline void
02863 Space::free(T* b, long unsigned int n) {
02864 for (long unsigned int i=0; i<n; i++)
02865 b[i].~T();
02866 rfree(b,n*sizeof(T));
02867 }
02868 template<class T>
02869 forceinline void
02870 Space::free(T* b, long int n) {
02871 assert(n >= 0);
02872 free<T>(b,static_cast<long unsigned int>(n));
02873 }
02874 template<class T>
02875 forceinline void
02876 Space::free(T* b, unsigned int n) {
02877 free<T>(b,static_cast<long unsigned int>(n));
02878 }
02879 template<class T>
02880 forceinline void
02881 Space::free(T* b, int n) {
02882 assert(n >= 0);
02883 free<T>(b,static_cast<long unsigned int>(n));
02884 }
02885
02886 template<class T>
02887 forceinline T*
02888 Space::realloc(T* b, long unsigned int n, long unsigned int m) {
02889 if (n < m) {
02890 T* p = static_cast<T*>(ralloc(sizeof(T)*m));
02891 for (long unsigned int i=0; i<n; i++)
02892 (void) new (p+i) T(b[i]);
02893 for (long unsigned int i=n; i<m; i++)
02894 (void) new (p+i) T();
02895 free<T>(b,n);
02896 return p;
02897 } else {
02898 free<T>(b+m,m-n);
02899 return b;
02900 }
02901 }
02902 template<class T>
02903 forceinline T*
02904 Space::realloc(T* b, long int n, long int m) {
02905 assert((n >= 0) && (m >= 0));
02906 return realloc<T>(b,static_cast<long unsigned int>(n),
02907 static_cast<long unsigned int>(m));
02908 }
02909 template<class T>
02910 forceinline T*
02911 Space::realloc(T* b, unsigned int n, unsigned int m) {
02912 return realloc<T>(b,static_cast<long unsigned int>(n),
02913 static_cast<long unsigned int>(m));
02914 }
02915 template<class T>
02916 forceinline T*
02917 Space::realloc(T* b, int n, int m) {
02918 assert((n >= 0) && (m >= 0));
02919 return realloc<T>(b,static_cast<long unsigned int>(n),
02920 static_cast<long unsigned int>(m));
02921 }
02922
02923 #define GECODE_KERNEL_REALLOC(T) \
02924 template<> \
02925 forceinline T* \
02926 Space::realloc<T>(T* b, long unsigned int n, long unsigned int m) { \
02927 return static_cast<T*>(rrealloc(b,n*sizeof(T),m*sizeof(T))); \
02928 } \
02929 template<> \
02930 forceinline T* \
02931 Space::realloc<T>(T* b, long int n, long int m) { \
02932 assert((n >= 0) && (m >= 0)); \
02933 return realloc<T>(b,static_cast<long unsigned int>(n), \
02934 static_cast<long unsigned int>(m)); \
02935 } \
02936 template<> \
02937 forceinline T* \
02938 Space::realloc<T>(T* b, unsigned int n, unsigned int m) { \
02939 return realloc<T>(b,static_cast<long unsigned int>(n), \
02940 static_cast<long unsigned int>(m)); \
02941 } \
02942 template<> \
02943 forceinline T* \
02944 Space::realloc<T>(T* b, int n, int m) { \
02945 assert((n >= 0) && (m >= 0)); \
02946 return realloc<T>(b,static_cast<long unsigned int>(n), \
02947 static_cast<long unsigned int>(m)); \
02948 }
02949
02950 GECODE_KERNEL_REALLOC(bool)
02951 GECODE_KERNEL_REALLOC(signed char)
02952 GECODE_KERNEL_REALLOC(unsigned char)
02953 GECODE_KERNEL_REALLOC(signed short int)
02954 GECODE_KERNEL_REALLOC(unsigned short int)
02955 GECODE_KERNEL_REALLOC(signed int)
02956 GECODE_KERNEL_REALLOC(unsigned int)
02957 GECODE_KERNEL_REALLOC(signed long int)
02958 GECODE_KERNEL_REALLOC(unsigned long int)
02959 GECODE_KERNEL_REALLOC(float)
02960 GECODE_KERNEL_REALLOC(double)
02961
02962 #undef GECODE_KERNEL_REALLOC
02963
02964 template<class T>
02965 forceinline T**
02966 Space::realloc(T** b, long unsigned int n, long unsigned int m) {
02967 return static_cast<T**>(rrealloc(b,n*sizeof(T),m*sizeof(T*)));
02968 }
02969 template<class T>
02970 forceinline T**
02971 Space::realloc(T** b, long int n, long int m) {
02972 assert((n >= 0) && (m >= 0));
02973 return realloc<T*>(b,static_cast<long unsigned int>(n),
02974 static_cast<long unsigned int>(m));
02975 }
02976 template<class T>
02977 forceinline T**
02978 Space::realloc(T** b, unsigned int n, unsigned int m) {
02979 return realloc<T*>(b,static_cast<long unsigned int>(n),
02980 static_cast<long unsigned int>(m));
02981 }
02982 template<class T>
02983 forceinline T**
02984 Space::realloc(T** b, int n, int m) {
02985 assert((n >= 0) && (m >= 0));
02986 return realloc<T*>(b,static_cast<long unsigned int>(n),
02987 static_cast<long unsigned int>(m));
02988 }
02989
02990
02991 #ifdef GECODE_HAS_VAR_DISPOSE
02992 template<class VIC>
02993 forceinline VarImpBase*
02994 Space::vars_d(void) const {
02995 return _vars_d[VIC::idx_d];
02996 }
02997 template<class VIC>
02998 forceinline void
02999 Space::vars_d(VarImpBase* x) {
03000 _vars_d[VIC::idx_d] = x;
03001 }
03002 #endif
03003
03004
03005 forceinline void
03006 Actor::operator delete(void*) {}
03007 forceinline void
03008 Actor::operator delete(void*, Space&) {}
03009 forceinline void*
03010 Actor::operator new(size_t s, Space& home) {
03011 return home.ralloc(s);
03012 }
03013
03014 template<class VIC>
03015 forceinline void
03016 VarImp<VIC>::operator delete(void*) {}
03017 template<class VIC>
03018 forceinline void
03019 VarImp<VIC>::operator delete(void*, Space&) {}
03020 template<class VIC>
03021 forceinline void*
03022 VarImp<VIC>::operator new(size_t s, Space& home) {
03023 return home.ralloc(s);
03024 }
03025
03026 #ifndef __GNUC__
03027 forceinline void
03028 Advisor::operator delete(void*) {}
03029 #endif
03030 forceinline void
03031 Advisor::operator delete(void*, Space&) {}
03032 forceinline void*
03033 Advisor::operator new(size_t s, Space& home) {
03034 return home.ralloc(s);
03035 }
03036
03037 forceinline void
03038 NGL::operator delete(void*) {}
03039 forceinline void
03040 NGL::operator delete(void*, Space&) {}
03041 forceinline void*
03042 NGL::operator new(size_t s, Space& home) {
03043 return home.ralloc(s);
03044 }
03045
03046
03047
03048
03049
03050
03051 forceinline
03052 NoGoods::NoGoods(void)
03053 : n(0) {}
03054 forceinline unsigned long int
03055 NoGoods::ng(void) const {
03056 return n;
03057 }
03058 forceinline void
03059 NoGoods::ng(unsigned long int n0) {
03060 n=n0;
03061 }
03062 forceinline
03063 NoGoods::~NoGoods(void) {}
03064
03065
03066
03067
03068
03069 forceinline
03070 MetaInfo::MetaInfo(unsigned long int r0,
03071 unsigned long int s0,
03072 unsigned long int f0,
03073 const Space* l0,
03074 NoGoods& ng0)
03075 : t(RESTART), r(r0), s(s0), f(f0), l(l0), ng(ng0), a(0) {}
03076
03077 forceinline
03078 MetaInfo::MetaInfo(unsigned int a0)
03079 : t(PORTFOLIO), r(0), s(0), f(0), l(NULL), ng(NoGoods::eng), a(a0) {}
03080
03081 forceinline MetaInfo::Type
03082 MetaInfo::type(void) const {
03083 return t;
03084 }
03085 forceinline unsigned long int
03086 MetaInfo::restart(void) const {
03087 assert(type() == RESTART);
03088 return r;
03089 }
03090 forceinline unsigned long int
03091 MetaInfo::solution(void) const {
03092 assert(type() == RESTART);
03093 return s;
03094 }
03095 forceinline unsigned long int
03096 MetaInfo::fail(void) const {
03097 assert(type() == RESTART);
03098 return f;
03099 }
03100 forceinline const Space*
03101 MetaInfo::last(void) const {
03102 assert(type() == RESTART);
03103 return l;
03104 }
03105 forceinline const NoGoods&
03106 MetaInfo::nogoods(void) const {
03107 assert(type() == RESTART);
03108 return ng;
03109 }
03110 forceinline unsigned int
03111 MetaInfo::asset(void) const {
03112 assert(type() == PORTFOLIO);
03113 return a;
03114 }
03115
03116
03117
03118
03119
03120
03121
03122 forceinline ActorLink*
03123 ActorLink::prev(void) const {
03124 return _prev;
03125 }
03126
03127 forceinline ActorLink*
03128 ActorLink::next(void) const {
03129 return _next;
03130 }
03131
03132 forceinline ActorLink**
03133 ActorLink::next_ref(void) {
03134 return &_next;
03135 }
03136
03137 forceinline void
03138 ActorLink::prev(ActorLink* al) {
03139 _prev = al;
03140 }
03141
03142 forceinline void
03143 ActorLink::next(ActorLink* al) {
03144 _next = al;
03145 }
03146
03147 forceinline void
03148 ActorLink::unlink(void) {
03149 ActorLink* p = _prev; ActorLink* n = _next;
03150 p->_next = n; n->_prev = p;
03151 }
03152
03153 forceinline void
03154 ActorLink::init(void) {
03155 _next = this; _prev =this;
03156 }
03157
03158 forceinline void
03159 ActorLink::head(ActorLink* a) {
03160
03161 ActorLink* n = _next;
03162 this->_next = a; a->_prev = this;
03163 a->_next = n; n->_prev = a;
03164 }
03165
03166 forceinline void
03167 ActorLink::tail(ActorLink* a) {
03168
03169 ActorLink* p = _prev;
03170 a->_next = this; this->_prev = a;
03171 p->_next = a; a->_prev = p;
03172 }
03173
03174 forceinline bool
03175 ActorLink::empty(void) const {
03176 return _next == this;
03177 }
03178
03179 template<class T>
03180 forceinline ActorLink*
03181 ActorLink::cast(T* a) {
03182
03183 GECODE_NOT_NULL(a);
03184 ActorLink& t = *a;
03185 return static_cast<ActorLink*>(&t);
03186 }
03187
03188 template<class T>
03189 forceinline const ActorLink*
03190 ActorLink::cast(const T* a) {
03191
03192 GECODE_NOT_NULL(a);
03193 const ActorLink& t = *a;
03194 return static_cast<const ActorLink*>(&t);
03195 }
03196
03197
03198
03199
03200
03201
03202 forceinline Actor*
03203 Actor::cast(ActorLink* al) {
03204
03205 GECODE_NOT_NULL(al);
03206 ActorLink& t = *al;
03207 return static_cast<Actor*>(&t);
03208 }
03209
03210 forceinline const Actor*
03211 Actor::cast(const ActorLink* al) {
03212
03213 GECODE_NOT_NULL(al);
03214 const ActorLink& t = *al;
03215 return static_cast<const Actor*>(&t);
03216 }
03217
03218 forceinline void
03219 Home::notice(Actor& a, ActorProperty p, bool duplicate) {
03220 s.notice(a,p,duplicate);
03221 }
03222
03223 forceinline Space*
03224 Space::clone(CloneStatistics&) const {
03225
03226
03227
03228 return const_cast<Space*>(this)->_clone();
03229 }
03230
03231 forceinline void
03232 Space::commit(const Choice& c, unsigned int a, CommitStatistics&) {
03233 _commit(c,a);
03234 }
03235
03236 forceinline void
03237 Space::trycommit(const Choice& c, unsigned int a, CommitStatistics&) {
03238 _trycommit(c,a);
03239 }
03240
03241 forceinline double
03242 Space::afc_decay(void) const {
03243 return ssd.data().gpi.decay();
03244 }
03245
03246 forceinline void
03247 Space::afc_decay(double d) {
03248 ssd.data().gpi.decay(d);
03249 }
03250
03251 forceinline size_t
03252 Actor::dispose(Space&) {
03253 return sizeof(*this);
03254 }
03255
03256
03257
03258
03259
03260
03261 forceinline
03262 Home::Home(Space& s0, Propagator* p0,
03263 PropagatorGroup pg0, BrancherGroup bg0)
03264 : s(s0), p(p0), pg(pg0), bg(bg0) {}
03265 forceinline Home&
03266 Home::operator =(const Home& h) {
03267 s=h.s; p=h.p; pg=h.pg; bg=h.bg;
03268 return *this;
03269 }
03270 forceinline
03271 Home::operator Space&(void) {
03272 return s;
03273 }
03274 forceinline Home
03275 Home::operator ()(Propagator& p) {
03276 return Home(s,&p);
03277 }
03278 forceinline Home
03279 Home::operator ()(PropagatorGroup pg) {
03280 return Home(s,NULL,pg,BrancherGroup::def);
03281 }
03282 forceinline Home
03283 Home::operator ()(BrancherGroup bg) {
03284 return Home(s,NULL,PropagatorGroup::def,bg);
03285 }
03286 forceinline Home
03287 Space::operator ()(Propagator& p) {
03288 return Home(*this,&p);
03289 }
03290 forceinline Home
03291 Space::operator ()(PropagatorGroup pg) {
03292 return Home(*this,NULL,pg,BrancherGroup::def);
03293 }
03294 forceinline Home
03295 Space::operator ()(BrancherGroup bg) {
03296 return Home(*this,NULL,PropagatorGroup::def,bg);
03297 }
03298 forceinline Propagator*
03299 Home::propagator(void) const {
03300 return p;
03301 }
03302 forceinline PropagatorGroup
03303 Home::propagatorgroup(void) const {
03304 return pg;
03305 }
03306 forceinline BrancherGroup
03307 Home::branchergroup(void) const {
03308 return bg;
03309 }
03310
03311
03312
03313
03314
03315 forceinline void
03316 ViewTraceInfo::propagator(Propagator& p) {
03317 who = reinterpret_cast<ptrdiff_t>(&p) | PROPAGATOR;
03318 }
03319 forceinline void
03320 ViewTraceInfo::brancher(Brancher& b) {
03321 who = reinterpret_cast<ptrdiff_t>(&b) | BRANCHER;
03322 }
03323 forceinline void
03324 ViewTraceInfo::post(PropagatorGroup g) {
03325 who = (g.id() << 2) | POST;
03326 }
03327 forceinline void
03328 ViewTraceInfo::other(void) {
03329 who = OTHER;
03330 }
03331 forceinline ViewTraceInfo::What
03332 ViewTraceInfo::what(void) const {
03333 return static_cast<What>(who & 3);
03334 }
03335 forceinline const Propagator&
03336 ViewTraceInfo::propagator(void) const {
03337 assert(what() == PROPAGATOR);
03338
03339 return *reinterpret_cast<Propagator*>(who);
03340 }
03341 forceinline const Brancher&
03342 ViewTraceInfo::brancher(void) const {
03343 assert(what() == BRANCHER);
03344 return *reinterpret_cast<Brancher*>(who & ~3);
03345 }
03346 forceinline PropagatorGroup
03347 ViewTraceInfo::post(void) const {
03348 assert(what() == POST);
03349 return PropagatorGroup(static_cast<unsigned int>(who >> 2));
03350 }
03351
03352
03353
03354
03355 forceinline
03356 PostInfo::PostInfo(Home home)
03357 : h(home), pg(home.propagatorgroup()),
03358 pid(h.ssd.data().gpi.pid()),
03359 nested(h.pc.p.vti.what() != ViewTraceInfo::OTHER) {
03360 h.pc.p.vti.post(pg);
03361 }
03362
03363 forceinline
03364 PostInfo::~PostInfo(void) {
03365 if (!nested) {
03366 if (h.pc.p.bid_sc & Space::sc_trace)
03367 h.post(*this);
03368 h.pc.p.vti.other();
03369 }
03370 }
03371
03372
03373
03374
03375
03376
03377 forceinline
03378 PropagateTraceInfo::PropagateTraceInfo(unsigned int i0, PropagatorGroup g0,
03379 const Propagator* p0, Status s0)
03380 : i(i0), g(g0), p(p0), s(s0) {}
03381 forceinline unsigned int
03382 PropagateTraceInfo::id(void) const {
03383 return i;
03384 }
03385 forceinline PropagatorGroup
03386 PropagateTraceInfo::group(void) const {
03387 return g;
03388 }
03389 forceinline const Propagator*
03390 PropagateTraceInfo::propagator(void) const {
03391 return p;
03392 }
03393 forceinline PropagateTraceInfo::Status
03394 PropagateTraceInfo::status(void) const {
03395 return s;
03396 }
03397
03398
03399
03400
03401
03402
03403 forceinline
03404 CommitTraceInfo::CommitTraceInfo(const Brancher& b0, const Choice& c0,
03405 unsigned int a0)
03406 : b(b0), c(c0), a(a0) {}
03407 forceinline unsigned int
03408 CommitTraceInfo::id(void) const {
03409 return b.id();
03410 }
03411 forceinline BrancherGroup
03412 CommitTraceInfo::group(void) const {
03413 return b.group();
03414 }
03415 forceinline const Brancher&
03416 CommitTraceInfo::brancher(void) const {
03417 return b;
03418 }
03419 forceinline const Choice&
03420 CommitTraceInfo::choice(void) const {
03421 return c;
03422 }
03423 forceinline unsigned int
03424 CommitTraceInfo::alternative(void) const {
03425 return a;
03426 }
03427
03428
03429
03430
03431
03432
03433 forceinline
03434 PostTraceInfo::PostTraceInfo(PropagatorGroup g0, Status s0, unsigned int n0)
03435 : g(g0), s(s0), n(n0) {}
03436 forceinline PropagatorGroup
03437 PostTraceInfo::group(void) const {
03438 return g;
03439 }
03440 forceinline PostTraceInfo::Status
03441 PostTraceInfo::status(void) const {
03442 return s;
03443 }
03444 forceinline unsigned int
03445 PostTraceInfo::propagators(void) const {
03446 return n;
03447 }
03448
03449
03450
03451
03452
03453
03454 forceinline Propagator*
03455 Propagator::cast(ActorLink* al) {
03456
03457 GECODE_NOT_NULL(al);
03458 ActorLink& t = *al;
03459 return static_cast<Propagator*>(&t);
03460 }
03461
03462 forceinline const Propagator*
03463 Propagator::cast(const ActorLink* al) {
03464
03465 GECODE_NOT_NULL(al);
03466 const ActorLink& t = *al;
03467 return static_cast<const Propagator*>(&t);
03468 }
03469
03470 forceinline Propagator*
03471 Propagator::fwd(void) const {
03472 return static_cast<Propagator*>(prev());
03473 }
03474
03475 forceinline bool
03476 Propagator::disabled(void) const {
03477 return Support::marked(gpi_disabled);
03478 }
03479
03480 forceinline void
03481 Propagator::disable(Space& home) {
03482 home.pc.p.bid_sc |= Space::sc_disabled;
03483 gpi_disabled = Support::fmark(gpi_disabled);
03484 }
03485
03486 forceinline void
03487 Propagator::enable(Space& home) {
03488 (void) home;
03489 gpi_disabled = Support::funmark(gpi_disabled);
03490 }
03491
03492 forceinline Kernel::GPI::Info&
03493 Propagator::gpi(void) {
03494 return *static_cast<Kernel::GPI::Info*>(Support::funmark(gpi_disabled));
03495 }
03496
03497 forceinline
03498 Propagator::Propagator(Home home)
03499 : gpi_disabled((home.propagator() != NULL) ?
03500
03501 home.propagator()->gpi_disabled :
03502
03503 static_cast<Space&>(home).ssd.data().gpi.allocate
03504 (home.propagatorgroup().gid)) {
03505 u.advisors = NULL;
03506 assert((u.med == 0) && (u.size == 0));
03507 static_cast<Space&>(home).pl.head(this);
03508 }
03509
03510 forceinline
03511 Propagator::Propagator(Space&, Propagator& p)
03512 : gpi_disabled(p.gpi_disabled) {
03513 u.advisors = NULL;
03514 assert((u.med == 0) && (u.size == 0));
03515
03516 p.prev(this);
03517 }
03518
03519 forceinline ModEventDelta
03520 Propagator::modeventdelta(void) const {
03521 return u.med;
03522 }
03523
03524 forceinline double
03525 Propagator::afc(void) const {
03526 return const_cast<Propagator&>(*this).gpi().afc;
03527 }
03528
03529 #ifdef GECODE_HAS_CBS
03530 forceinline void
03531 Propagator::solndistrib(Space&, SendMarginal) const {}
03532
03533 forceinline void
03534 Propagator::domainsizesum(InDecision, unsigned int& size,
03535 unsigned int& size_b) const {
03536 size = 0;
03537 size_b = 0;
03538 }
03539 #endif
03540
03541 forceinline unsigned int
03542 Propagator::id(void) const {
03543 return const_cast<Propagator&>(*this).gpi().pid;
03544 }
03545
03546 forceinline PropagatorGroup
03547 Propagator::group(void) const {
03548 return PropagatorGroup(const_cast<Propagator&>(*this).gpi().gid);
03549 }
03550
03551 forceinline void
03552 Propagator::group(PropagatorGroup g) {
03553 gpi().gid = g.id();
03554 }
03555
03556 forceinline ExecStatus
03557 Space::ES_SUBSUMED_DISPOSED(Propagator& p, size_t s) {
03558 p.u.size = s;
03559 return __ES_SUBSUMED;
03560 }
03561
03562 forceinline ExecStatus
03563 Space::ES_SUBSUMED(Propagator& p) {
03564 p.u.size = p.dispose(*this);
03565 return __ES_SUBSUMED;
03566 }
03567
03568 forceinline ExecStatus
03569 Space::ES_FIX_PARTIAL(Propagator& p, const ModEventDelta& med) {
03570 p.u.med = med;
03571 assert(p.u.med != 0);
03572 return __ES_PARTIAL;
03573 }
03574
03575 forceinline ExecStatus
03576 Space::ES_NOFIX_PARTIAL(Propagator& p, const ModEventDelta& med) {
03577 p.u.med = AllVarConf::med_combine(p.u.med,med);
03578 assert(p.u.med != 0);
03579 return __ES_PARTIAL;
03580 }
03581
03582
03583
03584
03585
03586
03587
03588 forceinline Brancher*
03589 Brancher::cast(ActorLink* al) {
03590
03591 GECODE_NOT_NULL(al);
03592 ActorLink& t = *al;
03593 return static_cast<Brancher*>(&t);
03594 }
03595
03596 forceinline const Brancher*
03597 Brancher::cast(const ActorLink* al) {
03598
03599 GECODE_NOT_NULL(al);
03600 const ActorLink& t = *al;
03601 return static_cast<const Brancher*>(&t);
03602 }
03603
03604 forceinline
03605 Brancher::Brancher(Home _home) :
03606 gid(_home.branchergroup().gid) {
03607 Space& home = static_cast<Space&>(_home);
03608 bid = home.pc.p.bid_sc >> Space::sc_bits;
03609 home.pc.p.bid_sc += (1 << Space::sc_bits);
03610 if ((home.pc.p.bid_sc >> Space::sc_bits) == 0U)
03611 throw TooManyBranchers("Brancher::Brancher");
03612
03613 if (home.b_status == &static_cast<Space&>(home).bl) {
03614 home.b_status = this;
03615 if (home.b_commit == &static_cast<Space&>(home).bl)
03616 home.b_commit = this;
03617 }
03618 home.bl.tail(this);
03619 }
03620
03621 forceinline
03622 Brancher::Brancher(Space&, Brancher& b)
03623 : bid(b.bid), gid(b.gid) {
03624
03625 b.prev(this);
03626 }
03627
03628 forceinline unsigned int
03629 Brancher::id(void) const {
03630 return bid;
03631 }
03632
03633 forceinline BrancherGroup
03634 Brancher::group(void) const {
03635 return BrancherGroup(gid);
03636 }
03637
03638 forceinline void
03639 Brancher::group(BrancherGroup g) {
03640 gid = g.id();
03641 }
03642
03643
03644 forceinline void
03645 Space::kill(Brancher& b) {
03646 assert(!failed());
03647
03648 if (b_commit == &b)
03649 b_commit = Brancher::cast(b.next());
03650 if (b_status == &b)
03651 b_status = Brancher::cast(b.next());
03652 b.unlink();
03653 rfree(&b,b.dispose(*this));
03654 }
03655
03656 forceinline void
03657 Space::kill(Propagator& p) {
03658 assert(!failed());
03659 p.unlink();
03660 rfree(&p,p.dispose(*this));
03661 }
03662
03663 forceinline Brancher*
03664 Space::brancher(unsigned int id) {
03665
03666
03667
03668
03669
03670
03671
03672
03673
03674
03675
03676
03677
03678
03679 Brancher* b_old = b_commit;
03680
03681 while (b_commit != Brancher::cast(&bl))
03682 if (id != b_commit->id())
03683 b_commit = Brancher::cast(b_commit->next());
03684 else
03685 return b_commit;
03686 if (b_commit == Brancher::cast(&bl)) {
03687
03688 b_commit = Brancher::cast(bl.next());
03689 while (b_commit != b_old)
03690 if (id != b_commit->id())
03691 b_commit = Brancher::cast(b_commit->next());
03692 else
03693 return b_commit;
03694 }
03695 return NULL;
03696 }
03697
03698
03699
03700
03701
03702
03703
03704 forceinline LocalObject*
03705 LocalObject::cast(ActorLink* al) {
03706
03707 GECODE_NOT_NULL(al);
03708 ActorLink& t = *al;
03709 return static_cast<LocalObject*>(&t);
03710 }
03711
03712 forceinline const LocalObject*
03713 LocalObject::cast(const ActorLink* al) {
03714
03715 GECODE_NOT_NULL(al);
03716 const ActorLink& t = *al;
03717 return static_cast<const LocalObject*>(&t);
03718 }
03719
03720 forceinline
03721 LocalObject::LocalObject(Home home) {
03722 (void) home;
03723 ActorLink::cast(this)->prev(NULL);
03724 }
03725
03726 forceinline
03727 LocalObject::LocalObject(Space&, LocalObject&) {
03728 ActorLink::cast(this)->prev(NULL);
03729 }
03730
03731 forceinline LocalObject*
03732 LocalObject::fwd(Space& home) {
03733 if (prev() == NULL)
03734 fwdcopy(home);
03735 return LocalObject::cast(prev());
03736 }
03737
03738 forceinline
03739 LocalHandle::LocalHandle(void) : o(NULL) {}
03740 forceinline
03741 LocalHandle::LocalHandle(LocalObject* lo) : o(lo) {}
03742 forceinline
03743 LocalHandle::LocalHandle(const LocalHandle& lh) : o(lh.o) {}
03744 forceinline LocalHandle&
03745 LocalHandle::operator =(const LocalHandle& lh) {
03746 o = lh.o;
03747 return *this;
03748 }
03749 forceinline
03750 LocalHandle::~LocalHandle(void) {}
03751 forceinline LocalObject*
03752 LocalHandle::object(void) const { return o; }
03753 forceinline void
03754 LocalHandle::object(LocalObject* n) { o = n; }
03755 forceinline void
03756 LocalHandle::update(Space& home, LocalHandle& lh) {
03757 object(lh.object()->fwd(home));
03758 }
03759
03760
03761
03762
03763
03764
03765 forceinline
03766 Choice::Choice(const Brancher& b, const unsigned int a)
03767 : bid(b.id()), alt(a) {}
03768
03769 forceinline unsigned int
03770 Choice::alternatives(void) const {
03771 return alt;
03772 }
03773
03774 forceinline unsigned int
03775 Choice::id(void) const {
03776 return bid;
03777 }
03778
03779 forceinline
03780 Choice::~Choice(void) {}
03781
03782
03783
03784
03785
03786
03787
03788 forceinline bool
03789 NGL::leaf(void) const {
03790 return Support::marked(nl);
03791 }
03792 forceinline NGL*
03793 NGL::next(void) const {
03794 return static_cast<NGL*>(Support::funmark(nl));
03795 }
03796 forceinline void
03797 NGL::leaf(bool l) {
03798 nl = l ? Support::fmark(nl) : Support::funmark(nl);
03799 }
03800 forceinline void
03801 NGL::next(NGL* n) {
03802 nl = Support::marked(nl) ? Support::mark(n) : n;
03803 }
03804 forceinline NGL*
03805 NGL::add(NGL* n, bool l) {
03806 nl = Support::marked(nl) ? Support::mark(n) : n;
03807 n->leaf(l);
03808 return n;
03809 }
03810
03811 forceinline
03812 NGL::NGL(void)
03813 : nl(NULL) {}
03814 forceinline
03815 NGL::NGL(Space&)
03816 : nl(NULL) {}
03817 forceinline
03818 NGL::NGL(Space&, NGL&)
03819 : nl(NULL) {}
03820 forceinline size_t
03821 NGL::dispose(Space&) {
03822 return sizeof(*this);
03823 }
03824
03825
03826
03827
03828
03829 template<class A>
03830 forceinline
03831 Advisor::Advisor(Space&, Propagator& p, Council<A>& c) {
03832
03833 ActorLink::prev(&p);
03834
03835 ActorLink::next(c.advisors); c.advisors = static_cast<A*>(this);
03836 }
03837
03838 forceinline
03839 Advisor::Advisor(Space&, Advisor&) {}
03840
03841 forceinline bool
03842 Advisor::disposed(void) const {
03843 return prev() == NULL;
03844 }
03845
03846 forceinline Advisor*
03847 Advisor::cast(ActorLink* al) {
03848 return static_cast<Advisor*>(al);
03849 }
03850
03851 forceinline const Advisor*
03852 Advisor::cast(const ActorLink* al) {
03853 return static_cast<const Advisor*>(al);
03854 }
03855
03856 forceinline Propagator&
03857 Advisor::propagator(void) const {
03858 assert(!disposed());
03859 return *Propagator::cast(ActorLink::prev());
03860 }
03861
03862 template<class A>
03863 forceinline void
03864 Advisor::dispose(Space&,Council<A>&) {
03865 assert(!disposed());
03866 ActorLink::prev(NULL);
03867
03868 Advisor* n = Advisor::cast(next());
03869 if ((n != NULL) && n->disposed())
03870 next(n->next());
03871 }
03872
03873 forceinline const ViewTraceInfo&
03874 Advisor::operator ()(const Space& home) const {
03875 return home.pc.p.vti;
03876 }
03877
03878 template<class A>
03879 forceinline ExecStatus
03880 Space::ES_FIX_DISPOSE(Council<A>& c, A& a) {
03881 a.dispose(*this,c);
03882 return ES_FIX;
03883 }
03884
03885 template<class A>
03886 forceinline ExecStatus
03887 Space::ES_NOFIX_DISPOSE(Council<A>& c, A& a) {
03888 a.dispose(*this,c);
03889 return ES_NOFIX;
03890 }
03891
03892 template<class A>
03893 forceinline ExecStatus
03894 Space::ES_NOFIX_DISPOSE_FORCE(Council<A>& c, A& a) {
03895 a.dispose(*this,c);
03896 return ES_NOFIX_FORCE;
03897 }
03898
03899
03900
03901
03902
03903
03904
03905 template<class A>
03906 forceinline
03907 Council<A>::Council(void) {}
03908
03909 template<class A>
03910 forceinline
03911 Council<A>::Council(Space&)
03912 : advisors(NULL) {}
03913
03914 template<class A>
03915 forceinline bool
03916 Council<A>::empty(void) const {
03917 ActorLink* a = advisors;
03918 while ((a != NULL) && static_cast<A*>(a)->disposed())
03919 a = a->next();
03920 advisors = a;
03921 return a == NULL;
03922 }
03923
03924 template<class A>
03925 forceinline void
03926 Council<A>::update(Space& home, Council<A>& c) {
03927
03928 {
03929 ActorLink* a = c.advisors;
03930 while ((a != NULL) && static_cast<A*>(a)->disposed())
03931 a = a->next();
03932 c.advisors = a;
03933 }
03934
03935 if (c.advisors != NULL) {
03936
03937 Propagator* p_f = &static_cast<A*>(c.advisors)->propagator();
03938
03939 Propagator* p_t = Propagator::cast(p_f->prev());
03940
03941 ActorLink** a_f = &c.advisors;
03942
03943 A* a_t = NULL;
03944 while (*a_f != NULL) {
03945 if (static_cast<A*>(*a_f)->disposed()) {
03946 *a_f = (*a_f)->next();
03947 } else {
03948
03949 A* a = new (home) A(home,*static_cast<A*>(*a_f));
03950
03951 a->prev(p_t);
03952
03953 (*a_f)->prev(a);
03954
03955 a->next(a_t);
03956 a_t = a;
03957 a_f = (*a_f)->next_ref();
03958 }
03959 }
03960 advisors = a_t;
03961
03962 assert(p_f->u.advisors == NULL);
03963 p_f->u.advisors = c.advisors;
03964 } else {
03965 advisors = NULL;
03966 }
03967 }
03968
03969 template<class A>
03970 forceinline void
03971 Council<A>::dispose(Space& home) {
03972 ActorLink* a = advisors;
03973 while (a != NULL) {
03974 if (!static_cast<A*>(a)->disposed())
03975 static_cast<A*>(a)->dispose(home,*this);
03976 a = a->next();
03977 }
03978 }
03979
03980
03981
03982
03983
03984
03985
03986 template<class A>
03987 forceinline
03988 Advisors<A>::Advisors(const Council<A>& c)
03989 : a(c.advisors) {
03990 while ((a != NULL) && static_cast<A*>(a)->disposed())
03991 a = a->next();
03992 }
03993
03994 template<class A>
03995 forceinline bool
03996 Advisors<A>::operator ()(void) const {
03997 return a != NULL;
03998 }
03999
04000 template<class A>
04001 forceinline void
04002 Advisors<A>::operator ++(void) {
04003 do {
04004 a = a->next();
04005 } while ((a != NULL) && static_cast<A*>(a)->disposed());
04006 }
04007
04008 template<class A>
04009 forceinline A&
04010 Advisors<A>::advisor(void) const {
04011 return *static_cast<A*>(a);
04012 }
04013
04014
04015
04016
04017
04018
04019
04020 forceinline void
04021 Space::enqueue(Propagator* p) {
04022 ActorLink::cast(p)->unlink();
04023 ActorLink* c = &pc.p.queue[p->cost(*this,p->u.med).ac];
04024 c->tail(ActorLink::cast(p));
04025 if (c > pc.p.active)
04026 pc.p.active = c;
04027 }
04028
04029 forceinline void
04030 Space::fail(void) {
04031 pc.p.active = &pc.p.queue[PropCost::AC_MAX+1]+1;
04032
04033
04034
04035
04036
04037 }
04038 forceinline void
04039 Home::fail(void) {
04040 s.fail();
04041 }
04042
04043 forceinline bool
04044 Space::failed(void) const {
04045 return pc.p.active > &pc.p.queue[PropCost::AC_MAX+1];
04046 }
04047 forceinline bool
04048 Home::failed(void) const {
04049 return s.failed();
04050 }
04051
04052 forceinline bool
04053 Space::stable(void) const {
04054 return ((pc.p.active < &pc.p.queue[0]) ||
04055 (pc.p.active > &pc.p.queue[PropCost::AC_MAX+1]));
04056 }
04057
04058 forceinline void
04059 Space::notice(Actor& a, ActorProperty p, bool d) {
04060 if (p & AP_DISPOSE) {
04061 ap_notice_dispose(&a,d);
04062 }
04063 if (p & AP_VIEW_TRACE) {
04064 pc.p.bid_sc |= sc_trace;
04065 }
04066 if (p & AP_TRACE) {
04067 pc.p.bid_sc |= sc_trace;
04068 }
04069
04070 if (p & AP_WEAKLY) {}
04071 }
04072
04073 forceinline void
04074 Space::ignore(Actor& a, ActorProperty p, bool d) {
04075
04076
04077 if ((p & AP_DISPOSE) && (d_fst != NULL))
04078 ap_ignore_dispose(&a,d);
04079 if (p & AP_VIEW_TRACE) {}
04080 if (p & AP_TRACE) {}
04081
04082 if (p & AP_WEAKLY) {}
04083 }
04084
04085
04086
04087
04088
04089
04090
04091 template<class VIC>
04092 forceinline ActorLink**
04093 VarImp<VIC>::actor(PropCond pc) {
04094 assert((pc >= 0) && (pc < pc_max+2));
04095 return (pc == 0) ? b.base : b.base+u.idx[pc-1];
04096 }
04097
04098 template<class VIC>
04099 forceinline ActorLink**
04100 VarImp<VIC>::actorNonZero(PropCond pc) {
04101 assert((pc > 0) && (pc < pc_max+2));
04102 return b.base+u.idx[pc-1];
04103 }
04104
04105 template<class VIC>
04106 forceinline unsigned int&
04107 VarImp<VIC>::idx(PropCond pc) {
04108 assert((pc > 0) && (pc < pc_max+2));
04109 return u.idx[pc-1];
04110 }
04111
04112 template<class VIC>
04113 forceinline unsigned int
04114 VarImp<VIC>::idx(PropCond pc) const {
04115 assert((pc > 0) && (pc < pc_max+2));
04116 return u.idx[pc-1];
04117 }
04118
04119 template<class VIC>
04120 forceinline
04121 VarImp<VIC>::VarImp(Space& home)
04122 #ifdef GECODE_HAS_CBS
04123 : var_id(++home.var_id_counter)
04124 #endif
04125 {
04126 #ifndef GECODE_HAS_CBS
04127 (void) home;
04128 #endif
04129 b.base = NULL; entries = 0;
04130 for (PropCond pc=1; pc<pc_max+2; pc++)
04131 idx(pc) = 0;
04132 free_and_bits = 0;
04133 }
04134
04135 template<class VIC>
04136 forceinline
04137 VarImp<VIC>::VarImp(void)
04138 #ifdef GECODE_HAS_CBS
04139 : var_id(0)
04140 #endif
04141 {
04142 b.base = NULL; entries = 0;
04143 for (PropCond pc=1; pc<pc_max+2; pc++)
04144 idx(pc) = 0;
04145 free_and_bits = 0;
04146 }
04147
04148 #ifdef GECODE_HAS_CBS
04149 template<class VIC>
04150 forceinline unsigned int
04151 VarImp<VIC>::id(void) const {
04152 return var_id;
04153 }
04154 #endif
04155
04156 template<class VIC>
04157 forceinline unsigned int
04158 VarImp<VIC>::degree(void) const {
04159 assert(!copied());
04160 return entries;
04161 }
04162
04163 template<class VIC>
04164 forceinline double
04165 VarImp<VIC>::afc(void) const {
04166 double d = 0.0;
04167
04168 {
04169 ActorLink** a = const_cast<VarImp<VIC>*>(this)->actor(0);
04170 ActorLink** e = const_cast<VarImp<VIC>*>(this)->actorNonZero(pc_max+1);
04171 while (a < e) {
04172 d += Propagator::cast(*a)->afc(); a++;
04173 }
04174 }
04175
04176 {
04177 ActorLink** a = const_cast<VarImp<VIC>*>(this)->actorNonZero(pc_max+1);
04178 ActorLink** e = const_cast<VarImp<VIC>*>(this)->b.base+entries;
04179 while (a < e) {
04180 d += Advisor::cast(static_cast<ActorLink*>(Support::funmark(*a)))
04181 ->propagator().afc();
04182 a++;
04183 }
04184 }
04185 return d;
04186 }
04187
04188 template<class VIC>
04189 forceinline ModEvent
04190 VarImp<VIC>::modevent(const Delta& d) {
04191 return d.me;
04192 }
04193
04194 template<class VIC>
04195 forceinline unsigned int
04196 VarImp<VIC>::bits(void) const {
04197 return free_and_bits;
04198 }
04199
04200 template<class VIC>
04201 forceinline unsigned int&
04202 VarImp<VIC>::bits(void) {
04203 return free_and_bits;
04204 }
04205
04206 #ifdef GECODE_HAS_VAR_DISPOSE
04207 template<class VIC>
04208 forceinline VarImp<VIC>*
04209 VarImp<VIC>::vars_d(Space& home) {
04210 return static_cast<VarImp<VIC>*>(home.vars_d<VIC>());
04211 }
04212
04213 template<class VIC>
04214 forceinline void
04215 VarImp<VIC>::vars_d(Space& home, VarImp<VIC>* x) {
04216 home.vars_d<VIC>(x);
04217 }
04218 #endif
04219
04220 template<class VIC>
04221 forceinline bool
04222 VarImp<VIC>::copied(void) const {
04223 return Support::marked(b.fwd);
04224 }
04225
04226 template<class VIC>
04227 forceinline VarImp<VIC>*
04228 VarImp<VIC>::forward(void) const {
04229 assert(copied());
04230 return static_cast<VarImp<VIC>*>(Support::unmark(b.fwd));
04231 }
04232
04233 template<class VIC>
04234 forceinline VarImp<VIC>*
04235 VarImp<VIC>::next(void) const {
04236 assert(copied());
04237 return u.next;
04238 }
04239
04240 template<class VIC>
04241 forceinline
04242 VarImp<VIC>::VarImp(Space& home, VarImp<VIC>& x)
04243 #ifdef GECODE_HAS_CBS
04244 : var_id(x.var_id)
04245 #endif
04246 {
04247 VarImpBase** reg;
04248 free_and_bits = x.free_and_bits & ((1 << free_bits) - 1);
04249 if (x.b.base == NULL) {
04250
04251 reg = &home.pc.c.vars_noidx;
04252 assert(x.degree() == 0);
04253 } else {
04254 reg = &home.pc.c.vars_u[idx_c];
04255 }
04256
04257 b.base = x.b.base;
04258 entries = x.entries;
04259 for (PropCond pc=1; pc<pc_max+2; pc++)
04260 idx(pc) = x.idx(pc);
04261
04262
04263 x.b.fwd = static_cast<VarImp<VIC>*>(Support::mark(this));
04264
04265 x.u.next = static_cast<VarImp<VIC>*>(*reg); *reg = &x;
04266 }
04267
04268 template<class VIC>
04269 forceinline ModEvent
04270 VarImp<VIC>::me(const ModEventDelta& med) {
04271 return static_cast<ModEvent>((med & VIC::med_mask) >> VIC::med_fst);
04272 }
04273
04274 template<class VIC>
04275 forceinline ModEventDelta
04276 VarImp<VIC>::med(ModEvent me) {
04277 return static_cast<ModEventDelta>(me << VIC::med_fst);
04278 }
04279
04280 template<class VIC>
04281 forceinline ModEvent
04282 VarImp<VIC>::me_combine(ModEvent me1, ModEvent me2) {
04283 return VIC::me_combine(me1,me2);
04284 }
04285
04286 template<class VIC>
04287 forceinline void
04288 VarImp<VIC>::schedule(Space& home, Propagator& p, ModEvent me,
04289 bool force) {
04290 if (VIC::med_update(p.u.med,me) || force)
04291 home.enqueue(&p);
04292 }
04293
04294 template<class VIC>
04295 forceinline void
04296 VarImp<VIC>::schedule(Space& home, PropCond pc1, PropCond pc2, ModEvent me) {
04297 ActorLink** b = actor(pc1);
04298 ActorLink** p = actorNonZero(pc2+1);
04299 while (p-- > b)
04300 schedule(home,*Propagator::cast(*p),me);
04301 }
04302
04303 template<class VIC>
04304 forceinline void
04305 VarImp<VIC>::resize(Space& home) {
04306 if (b.base == NULL) {
04307 assert((free_and_bits >> free_bits) == 0);
04308
04309 free_and_bits += 4 << free_bits;
04310 b.base = home.alloc<ActorLink*>(4);
04311 for (int i=0; i<pc_max+1; i++)
04312 u.idx[i] = 0;
04313 } else {
04314
04315 unsigned int n = degree();
04316
04317
04318
04319 ActorLink** s = static_cast<ActorLink**>(home.mm.subscriptions());
04320 unsigned int m =
04321 ((s <= b.base) && (b.base < s+home.pc.p.n_sub)) ?
04322 (n+4) : ((n+1)*3>>1);
04323 ActorLink** prop = home.alloc<ActorLink*>(m);
04324 free_and_bits += (m-n) << free_bits;
04325
04326 Heap::copy<ActorLink*>(prop, b.base, n);
04327 home.free<ActorLink*>(b.base,n);
04328 b.base = prop;
04329 }
04330 }
04331
04332 template<class VIC>
04333 forceinline void
04334 VarImp<VIC>::enter(Space& home, Propagator* p, PropCond pc) {
04335 assert(pc <= pc_max);
04336
04337 home.pc.p.n_sub += 1;
04338 if ((free_and_bits >> free_bits) == 0)
04339 resize(home);
04340 free_and_bits -= 1 << free_bits;
04341
04342
04343 b.base[entries] = *actorNonZero(pc_max+1);
04344 entries++;
04345 for (PropCond j = pc_max; j > pc; j--) {
04346 *actorNonZero(j+1) = *actorNonZero(j);
04347 idx(j+1)++;
04348 }
04349 *actorNonZero(pc+1) = *actor(pc);
04350 idx(pc+1)++;
04351 *actor(pc) = ActorLink::cast(p);
04352
04353 #ifdef GECODE_AUDIT
04354 ActorLink** f = actor(pc);
04355 while (f < (pc == pc_max+1 ? b.base+entries : actorNonZero(pc+1)))
04356 if (*f == p)
04357 goto found;
04358 else
04359 f++;
04360 GECODE_NEVER;
04361 found: ;
04362 #endif
04363 }
04364
04365 template<class VIC>
04366 forceinline void
04367 VarImp<VIC>::enter(Space& home, Advisor* a) {
04368
04369
04370 home.pc.p.n_sub += 1;
04371 if ((free_and_bits >> free_bits) == 0)
04372 resize(home);
04373 free_and_bits -= 1 << free_bits;
04374
04375
04376 b.base[entries++] = *actorNonZero(pc_max+1);
04377 *actorNonZero(pc_max+1) = a;
04378 }
04379
04380 template<class VIC>
04381 forceinline void
04382 VarImp<VIC>::subscribe(Space& home, Propagator& p, PropCond pc,
04383 bool assigned, ModEvent me, bool schedule) {
04384 if (assigned) {
04385
04386 if (schedule)
04387 VarImp<VIC>::schedule(home,p,ME_GEN_ASSIGNED);
04388 } else {
04389 enter(home,&p,pc);
04390
04391 if (schedule && (pc != PC_GEN_ASSIGNED))
04392 VarImp<VIC>::schedule(home,p,me);
04393 }
04394 }
04395
04396 template<class VIC>
04397 forceinline void
04398 VarImp<VIC>::subscribe(Space& home, Advisor& a, bool assigned, bool fail) {
04399 if (!assigned) {
04400 Advisor* ma = static_cast<Advisor*>(Support::ptrjoin(&a,fail ? 1 : 0));
04401 enter(home,ma);
04402 }
04403 }
04404
04405 template<class VIC>
04406 forceinline void
04407 VarImp<VIC>::reschedule(Space& home, Propagator& p, PropCond pc,
04408 bool assigned, ModEvent me) {
04409 if (assigned)
04410 VarImp<VIC>::schedule(home,p,ME_GEN_ASSIGNED);
04411 else if (pc != PC_GEN_ASSIGNED)
04412 VarImp<VIC>::schedule(home,p,me);
04413 }
04414
04415 template<class VIC>
04416 void
04417 VarImp<VIC>::remove(Space& home, Propagator* p, PropCond pc) {
04418 assert(pc <= pc_max);
04419 ActorLink* a = ActorLink::cast(p);
04420
04421 ActorLink** f = actor(pc);
04422 #ifdef GECODE_AUDIT
04423 while (f < actorNonZero(pc+1))
04424 if (*f == a)
04425 goto found;
04426 else
04427 f++;
04428 GECODE_NEVER;
04429 found: ;
04430 #else
04431 while (*f != a) f++;
04432 #endif
04433
04434 *f = *(actorNonZero(pc+1)-1);
04435 for (PropCond j = pc+1; j< pc_max+1; j++) {
04436 *(actorNonZero(j)-1) = *(actorNonZero(j+1)-1);
04437 idx(j)--;
04438 }
04439 *(actorNonZero(pc_max+1)-1) = b.base[entries-1];
04440 idx(pc_max+1)--;
04441 entries--;
04442 free_and_bits += 1 << free_bits;
04443 home.pc.p.n_sub -= 1;
04444 }
04445
04446 template<class VIC>
04447 forceinline void
04448 VarImp<VIC>::cancel(Space& home, Propagator& p, PropCond pc) {
04449 if (b.base != NULL)
04450 remove(home,&p,pc);
04451 }
04452
04453 template<class VIC>
04454 void
04455 VarImp<VIC>::remove(Space& home, Advisor* a) {
04456
04457
04458 ActorLink** f = actorNonZero(pc_max+1);
04459 #ifdef GECODE_AUDIT
04460 while (f < b.base+entries)
04461 if (*f == a)
04462 goto found;
04463 else
04464 f++;
04465 GECODE_NEVER;
04466 found: ;
04467 #else
04468 while (*f != a) f++;
04469 #endif
04470
04471 *f = b.base[--entries];
04472 free_and_bits += 1 << free_bits;
04473 home.pc.p.n_sub -= 1;
04474 }
04475
04476 template<class VIC>
04477 forceinline void
04478 VarImp<VIC>::cancel(Space& home, Advisor& a, bool fail) {
04479 if (b.base != NULL) {
04480 Advisor* ma = static_cast<Advisor*>(Support::ptrjoin(&a,fail ? 1 : 0));
04481 remove(home,ma);
04482 }
04483 }
04484
04485 template<class VIC>
04486 forceinline void
04487 VarImp<VIC>::cancel(Space& home) {
04488 unsigned int n_sub = degree();
04489 home.pc.p.n_sub -= n_sub;
04490 unsigned int n = (free_and_bits >> free_bits) + n_sub;
04491 home.free<ActorLink*>(b.base,n);
04492
04493 b.base = NULL;
04494
04495 entries = 0;
04496
04497 for (PropCond pc=1; pc<pc_max+2; pc++)
04498 idx(pc) = 0;
04499 free_and_bits &= (1 << free_bits) - 1;
04500 }
04501
04502 template<class VIC>
04503 forceinline bool
04504 VarImp<VIC>::advise(Space& home, ModEvent me, Delta& d) {
04505
04506
04507
04508
04509
04510 ActorLink** la = actorNonZero(pc_max+1);
04511 ActorLink** le = b.base+entries;
04512 if (la == le)
04513 return true;
04514 d.me = me;
04515
04516
04517
04518 do {
04519 Advisor* a = Advisor::cast
04520 (static_cast<ActorLink*>(Support::funmark(*la)));
04521 assert(!a->disposed());
04522 Propagator& p = a->propagator();
04523 switch (p.advise(home,*a,d)) {
04524 case ES_FIX:
04525 break;
04526 case ES_FAILED:
04527 return false;
04528 case ES_NOFIX:
04529 schedule(home,p,me);
04530 break;
04531 case ES_NOFIX_FORCE:
04532 schedule(home,p,me,true);
04533 break;
04534 case __ES_SUBSUMED:
04535 default:
04536 GECODE_NEVER;
04537 }
04538 } while (++la < le);
04539 return true;
04540 }
04541
04542 template<class VIC>
04543 void
04544 VarImp<VIC>::_fail(Space& home) {
04545
04546
04547
04548
04549
04550 ActorLink** la = actorNonZero(pc_max+1);
04551 ActorLink** le = b.base+entries;
04552 if (la == le)
04553 return;
04554
04555
04556
04557 do {
04558 if (Support::marked(*la)) {
04559 Advisor* a = Advisor::cast(static_cast<ActorLink*>
04560 (Support::unmark(*la)));
04561 assert(!a->disposed());
04562 Propagator& p = a->propagator();
04563 p.advise(home,*a);
04564 }
04565 } while (++la < le);
04566 }
04567
04568 template<class VIC>
04569 ModEvent
04570 VarImp<VIC>::fail(Space& home) {
04571 _fail(home);
04572 return ME_GEN_FAILED;
04573 }
04574
04575 template<class VIC>
04576 forceinline void
04577 VarImp<VIC>::update(VarImp<VIC>* x, ActorLink**& sub) {
04578
04579
04580
04581 x->b.base = b.base;
04582 x->u.idx[0] = u.idx[0];
04583 if (pc_max > 0 && sizeof(ActorLink**) > sizeof(unsigned int))
04584 x->u.idx[1] = u.idx[1];
04585
04586 unsigned int np =
04587 static_cast<unsigned int>(x->actorNonZero(pc_max+1) - x->actor(0));
04588 unsigned int na =
04589 static_cast<unsigned int >(x->b.base + x->entries -
04590 x->actorNonZero(pc_max+1));
04591 unsigned int n = na + np;
04592 assert(n == x->degree());
04593
04594 ActorLink** f = x->b.base;
04595 ActorLink** t = sub;
04596
04597 sub += n;
04598 b.base = t;
04599
04600 while (np >= 4) {
04601 ActorLink* p3 = f[3]->prev();
04602 ActorLink* p0 = f[0]->prev();
04603 ActorLink* p1 = f[1]->prev();
04604 ActorLink* p2 = f[2]->prev();
04605 t[0] = p0; t[1] = p1; t[2] = p2; t[3] = p3;
04606 np -= 4; t += 4; f += 4;
04607 }
04608 if (np >= 2) {
04609 ActorLink* p0 = f[0]->prev();
04610 ActorLink* p1 = f[1]->prev();
04611 t[0] = p0; t[1] = p1;
04612 np -= 2; t += 2; f += 2;
04613 }
04614 if (np > 0) {
04615 ActorLink* p0 = f[0]->prev();
04616 t[0] = p0;
04617 t += 1; f += 1;
04618 }
04619
04620 while (na >= 4) {
04621 ptrdiff_t m0, m1, m2, m3;
04622 ActorLink* p3 =
04623 static_cast<ActorLink*>(Support::ptrsplit(f[3],m3))->prev();
04624 ActorLink* p0 =
04625 static_cast<ActorLink*>(Support::ptrsplit(f[0],m0))->prev();
04626 ActorLink* p1 =
04627 static_cast<ActorLink*>(Support::ptrsplit(f[1],m1))->prev();
04628 ActorLink* p2 =
04629 static_cast<ActorLink*>(Support::ptrsplit(f[2],m2))->prev();
04630 t[0] = static_cast<ActorLink*>(Support::ptrjoin(p0,m0));
04631 t[1] = static_cast<ActorLink*>(Support::ptrjoin(p1,m1));
04632 t[2] = static_cast<ActorLink*>(Support::ptrjoin(p2,m2));
04633 t[3] = static_cast<ActorLink*>(Support::ptrjoin(p3,m3));
04634 na -= 4; t += 4; f += 4;
04635 }
04636 if (na >= 2) {
04637 ptrdiff_t m0, m1;
04638 ActorLink* p0 =
04639 static_cast<ActorLink*>(Support::ptrsplit(f[0],m0))->prev();
04640 ActorLink* p1 =
04641 static_cast<ActorLink*>(Support::ptrsplit(f[1],m1))->prev();
04642 t[0] = static_cast<ActorLink*>(Support::ptrjoin(p0,m0));
04643 t[1] = static_cast<ActorLink*>(Support::ptrjoin(p1,m1));
04644 na -= 2; t += 2; f += 2;
04645 }
04646 if (na > 0) {
04647 ptrdiff_t m0;
04648 ActorLink* p0 =
04649 static_cast<ActorLink*>(Support::ptrsplit(f[0],m0))->prev();
04650 t[0] = static_cast<ActorLink*>(Support::ptrjoin(p0,m0));
04651 }
04652 }
04653
04654 template<class VIC>
04655 forceinline void
04656 VarImp<VIC>::update(Space& home, ActorLink**& sub) {
04657 VarImp<VIC>* x = static_cast<VarImp<VIC>*>(home.pc.c.vars_u[idx_c]);
04658 while (x != NULL) {
04659 VarImp<VIC>* n = x->next(); x->forward()->update(x,sub); x = n;
04660 }
04661 }
04662
04663
04664
04665
04666
04667
04668
04669 template<class VarImp>
04670 VarImpDisposer<VarImp>::VarImpDisposer(void) {
04671 #ifdef GECODE_HAS_VAR_DISPOSE
04672 Space::vd[VarImp::idx_d] = this;
04673 #endif
04674 }
04675
04676 template<class VarImp>
04677 void
04678 VarImpDisposer<VarImp>::dispose(Space& home, VarImpBase* _x) {
04679 VarImp* x = static_cast<VarImp*>(_x);
04680 do {
04681 x->dispose(home); x = static_cast<VarImp*>(x->next_d());
04682 } while (x != NULL);
04683 }
04684
04685
04686
04687
04688
04689 forceinline void
04690 StatusStatistics::reset(void) {
04691 propagate = 0;
04692 }
04693 forceinline
04694 StatusStatistics::StatusStatistics(void) {
04695 reset();
04696 }
04697 forceinline StatusStatistics&
04698 StatusStatistics::operator +=(const StatusStatistics& s) {
04699 propagate += s.propagate;
04700 return *this;
04701 }
04702 forceinline StatusStatistics
04703 StatusStatistics::operator +(const StatusStatistics& s) {
04704 StatusStatistics t(s);
04705 return t += *this;
04706 }
04707
04708 forceinline void
04709 CloneStatistics::reset(void) {}
04710
04711 forceinline
04712 CloneStatistics::CloneStatistics(void) {
04713 reset();
04714 }
04715 forceinline CloneStatistics
04716 CloneStatistics::operator +(const CloneStatistics&) {
04717 CloneStatistics s;
04718 return s;
04719 }
04720 forceinline CloneStatistics&
04721 CloneStatistics::operator +=(const CloneStatistics&) {
04722 return *this;
04723 }
04724
04725 forceinline void
04726 CommitStatistics::reset(void) {}
04727
04728 forceinline
04729 CommitStatistics::CommitStatistics(void) {
04730 reset();
04731 }
04732 forceinline CommitStatistics
04733 CommitStatistics::operator +(const CommitStatistics&) {
04734 CommitStatistics s;
04735 return s;
04736 }
04737 forceinline CommitStatistics&
04738 CommitStatistics::operator +=(const CommitStatistics&) {
04739 return *this;
04740 }
04741
04742
04743
04744
04745
04746
04747 forceinline
04748 PropCost::PropCost(PropCost::ActualCost ac0) : ac(ac0) {}
04749
04750 forceinline PropCost
04751 PropCost::cost(PropCost::Mod m,
04752 PropCost::ActualCost lo, PropCost::ActualCost hi,
04753 unsigned int n) {
04754 if (n < 2)
04755 return (m == LO) ? AC_UNARY_LO : AC_UNARY_HI;
04756 else if (n == 2)
04757 return (m == LO) ? AC_BINARY_LO : AC_BINARY_HI;
04758 else if (n == 3)
04759 return (m == LO) ? AC_TERNARY_LO : AC_TERNARY_HI;
04760 else
04761 return (m == LO) ? lo : hi;
04762 }
04763
04764 forceinline PropCost
04765 PropCost::record(void) {
04766 return AC_RECORD;
04767 }
04768 forceinline PropCost
04769 PropCost::crazy(PropCost::Mod m, unsigned int n) {
04770 return cost(m,AC_CRAZY_LO,AC_CRAZY_HI,n);
04771 }
04772 forceinline PropCost
04773 PropCost::crazy(PropCost::Mod m, int n) {
04774 assert(n >= 0);
04775 return crazy(m,static_cast<unsigned int>(n));
04776 }
04777 forceinline PropCost
04778 PropCost::cubic(PropCost::Mod m, unsigned int n) {
04779 return cost(m,AC_CUBIC_LO,AC_CUBIC_HI,n);
04780 }
04781 forceinline PropCost
04782 PropCost::cubic(PropCost::Mod m, int n) {
04783 assert(n >= 0);
04784 return cubic(m,static_cast<unsigned int>(n));
04785 }
04786 forceinline PropCost
04787 PropCost::quadratic(PropCost::Mod m, unsigned int n) {
04788 return cost(m,AC_QUADRATIC_LO,AC_QUADRATIC_HI,n);
04789 }
04790 forceinline PropCost
04791 PropCost::quadratic(PropCost::Mod m, int n) {
04792 assert(n >= 0);
04793 return quadratic(m,static_cast<unsigned int>(n));
04794 }
04795 forceinline PropCost
04796 PropCost::linear(PropCost::Mod m, unsigned int n) {
04797 return cost(m,AC_LINEAR_LO,AC_LINEAR_HI,n);
04798 }
04799 forceinline PropCost
04800 PropCost::linear(PropCost::Mod m, int n) {
04801 assert(n >= 0);
04802 return linear(m,static_cast<unsigned int>(n));
04803 }
04804 forceinline PropCost
04805 PropCost::ternary(PropCost::Mod m) {
04806 return (m == LO) ? AC_TERNARY_LO : AC_TERNARY_HI;
04807 }
04808 forceinline PropCost
04809 PropCost::binary(PropCost::Mod m) {
04810 return (m == LO) ? AC_BINARY_LO : AC_BINARY_HI;
04811 }
04812 forceinline PropCost
04813 PropCost::unary(PropCost::Mod m) {
04814 return (m == LO) ? AC_UNARY_LO : AC_UNARY_HI;
04815 }
04816
04817
04818
04819
04820
04821 forceinline
04822 Space::Propagators::Propagators(Space& home0)
04823 : home(home0), q(home.pc.p.active) {
04824 while (q >= &home.pc.p.queue[0]) {
04825 if (q->next() != q) {
04826 c = q->next(); e = q; q--;
04827 return;
04828 }
04829 q--;
04830 }
04831 q = NULL;
04832 if (!home.pl.empty()) {
04833 c = Propagator::cast(home.pl.next());
04834 e = Propagator::cast(&home.pl);
04835 } else {
04836 c = e = NULL;
04837 }
04838 }
04839 forceinline bool
04840 Space::Propagators::operator ()(void) const {
04841 return c != NULL;
04842 }
04843 forceinline void
04844 Space::Propagators::operator ++(void) {
04845 c = c->next();
04846 if (c == e) {
04847 if (q == NULL) {
04848 c = NULL;
04849 } else {
04850 while (q >= &home.pc.p.queue[0]) {
04851 if (q->next() != q) {
04852 c = q->next(); e = q; q--;
04853 return;
04854 }
04855 q--;
04856 }
04857 q = NULL;
04858 if (!home.pl.empty()) {
04859 c = Propagator::cast(home.pl.next());
04860 e = Propagator::cast(&home.pl);
04861 } else {
04862 c = NULL;
04863 }
04864 }
04865 }
04866 }
04867 forceinline Propagator&
04868 Space::Propagators::propagator(void) const {
04869 return *Propagator::cast(c);
04870 }
04871
04872
04873 forceinline
04874 Space::ScheduledPropagators::ScheduledPropagators(Space& home0)
04875 : home(home0), q(home.pc.p.active) {
04876 while (q >= &home.pc.p.queue[0]) {
04877 if (q->next() != q) {
04878 c = q->next(); e = q; q--;
04879 return;
04880 }
04881 q--;
04882 }
04883 q = c = e = NULL;
04884 }
04885 forceinline bool
04886 Space::ScheduledPropagators::operator ()(void) const {
04887 return c != NULL;
04888 }
04889 forceinline void
04890 Space::ScheduledPropagators::operator ++(void) {
04891 c = c->next();
04892 if (c == e) {
04893 if (q == NULL) {
04894 c = NULL;
04895 } else {
04896 while (q >= &home.pc.p.queue[0]) {
04897 if (q->next() != q) {
04898 c = q->next(); e = q; q--;
04899 return;
04900 }
04901 q--;
04902 }
04903 q = c = e = NULL;
04904 }
04905 }
04906 }
04907 forceinline Propagator&
04908 Space::ScheduledPropagators::propagator(void) const {
04909 return *Propagator::cast(c);
04910 }
04911
04912
04913 forceinline
04914 Space::IdlePropagators::IdlePropagators(Space& home) {
04915 c = Propagator::cast(home.pl.next());
04916 e = Propagator::cast(&home.pl);
04917 }
04918 forceinline bool
04919 Space::IdlePropagators::operator ()(void) const {
04920 return c != e;
04921 }
04922 forceinline void
04923 Space::IdlePropagators::operator ++(void) {
04924 c = c->next();
04925 }
04926 forceinline Propagator&
04927 Space::IdlePropagators::propagator(void) const {
04928 return *Propagator::cast(c);
04929 }
04930
04931
04932 forceinline
04933 Space::Branchers::Branchers(Space& home)
04934 : c(Brancher::cast(home.bl.next())), e(&home.bl) {}
04935 forceinline bool
04936 Space::Branchers::operator ()(void) const {
04937 return c != e;
04938 }
04939 forceinline void
04940 Space::Branchers::operator ++(void) {
04941 c = c->next();
04942 }
04943 forceinline Brancher&
04944 Space::Branchers::brancher(void) const {
04945 return *Brancher::cast(c);
04946 }
04947
04948
04949
04950
04951
04952 forceinline
04953 Group::Group(unsigned int gid0) : gid(gid0) {}
04954
04955 forceinline bool
04956 Group::in(Group actor) const {
04957 return (gid == GROUPID_ALL) || (gid == actor.gid);
04958 }
04959
04960 forceinline bool
04961 Group::in(void) const {
04962 return (gid != GROUPID_ALL) && (gid != GROUPID_DEF);
04963 }
04964
04965 forceinline
04966 Group::Group(const Group& g) : gid(g.gid) {}
04967
04968 forceinline Group&
04969 Group::operator =(const Group& g) {
04970 gid=g.gid; return *this;
04971 }
04972
04973 forceinline unsigned int
04974 Group::id(void) const {
04975 return gid;
04976 }
04977
04978
04979 forceinline
04980 PropagatorGroup::PropagatorGroup(void) {}
04981
04982 forceinline
04983 PropagatorGroup::PropagatorGroup(unsigned int gid)
04984 : Group(gid) {}
04985
04986 forceinline
04987 PropagatorGroup::PropagatorGroup(const PropagatorGroup& g)
04988 : Group(g) {}
04989
04990 forceinline PropagatorGroup&
04991 PropagatorGroup::operator =(const PropagatorGroup& g) {
04992 return static_cast<PropagatorGroup&>(Group::operator =(g));
04993 }
04994
04995 forceinline Home
04996 PropagatorGroup::operator ()(Space& home) {
04997 return Home(home,NULL,*this,BrancherGroup::def);
04998 }
04999
05000 forceinline bool
05001 PropagatorGroup::operator ==(PropagatorGroup g) const {
05002 return id() == g.id();
05003 }
05004 forceinline bool
05005 PropagatorGroup::operator !=(PropagatorGroup g) const {
05006 return id() != g.id();
05007 }
05008
05009 forceinline PropagatorGroup&
05010 PropagatorGroup::move(Space& , Propagator& p) {
05011 if (id() != GROUPID_ALL)
05012 p.group(*this);
05013 return *this;
05014 }
05015
05016
05017 forceinline
05018 BrancherGroup::BrancherGroup(void) {}
05019
05020 forceinline
05021 BrancherGroup::BrancherGroup(unsigned int gid)
05022 : Group(gid) {}
05023
05024 forceinline
05025 BrancherGroup::BrancherGroup(const BrancherGroup& g)
05026 : Group(g) {}
05027
05028 forceinline BrancherGroup&
05029 BrancherGroup::operator =(const BrancherGroup& g) {
05030 return static_cast<BrancherGroup&>(Group::operator =(g));
05031 }
05032
05033 forceinline Home
05034 BrancherGroup::operator ()(Space& home) {
05035 return Home(home,NULL,PropagatorGroup::def,*this);
05036 }
05037
05038 forceinline bool
05039 BrancherGroup::operator ==(BrancherGroup g) const {
05040 return id() == g.id();
05041 }
05042 forceinline bool
05043 BrancherGroup::operator !=(BrancherGroup g) const {
05044 return id() != g.id();
05045 }
05046
05047 forceinline BrancherGroup&
05048 BrancherGroup::move(Space& , Brancher& p) {
05049 if (id() != GROUPID_ALL)
05050 p.group(*this);
05051 return *this;
05052 }
05053
05054
05055
05056
05057
05058
05059 forceinline
05060 Propagators::Propagators(const Space& home, PropagatorGroup g0)
05061 : ps(const_cast<Space&>(home)), g(g0) {
05062 while (ps() && !g.in(ps.propagator().group()))
05063 ++ps;
05064 }
05065 forceinline bool
05066 Propagators::operator ()(void) const {
05067 return ps();
05068 }
05069 forceinline void
05070 Propagators::operator ++(void) {
05071 do
05072 ++ps;
05073 while (ps() && !g.in(ps.propagator().group()));
05074 }
05075 forceinline const Propagator&
05076 Propagators::propagator(void) const {
05077 return ps.propagator();
05078 }
05079
05080 forceinline
05081 Branchers::Branchers(const Space& home, BrancherGroup g0)
05082 : bs(const_cast<Space&>(home)), g(g0) {
05083 while (bs() && !g.in(bs.brancher().group()))
05084 ++bs;
05085 }
05086 forceinline bool
05087 Branchers::operator ()(void) const {
05088 return bs();
05089 }
05090 forceinline void
05091 Branchers::operator ++(void) {
05092 do
05093 ++bs;
05094 while (bs() && !g.in(bs.brancher().group()));
05095 }
05096 forceinline const Brancher&
05097 Branchers::brancher(void) const {
05098 return bs.brancher();
05099 }
05100
05101
05102
05103
05104
05105
05106 template<class T>
05107 forceinline T&
05108 Space::construct(void) {
05109 return alloc<T>(1);
05110 }
05111 template<class T, typename A1>
05112 forceinline T&
05113 Space::construct(A1 const& a1) {
05114 T& t = *static_cast<T*>(ralloc(sizeof(T)));
05115 new (&t) T(a1);
05116 return t;
05117 }
05118 template<class T, typename A1, typename A2>
05119 forceinline T&
05120 Space::construct(A1 const& a1, A2 const& a2) {
05121 T& t = *static_cast<T*>(ralloc(sizeof(T)));
05122 new (&t) T(a1,a2);
05123 return t;
05124 }
05125 template<class T, typename A1, typename A2, typename A3>
05126 forceinline T&
05127 Space::construct(A1 const& a1, A2 const& a2, A3 const& a3) {
05128 T& t = *static_cast<T*>(ralloc(sizeof(T)));
05129 new (&t) T(a1,a2,a3);
05130 return t;
05131 }
05132 template<class T, typename A1, typename A2, typename A3, typename A4>
05133 forceinline T&
05134 Space::construct(A1 const& a1, A2 const& a2, A3 const& a3, A4 const& a4) {
05135 T& t = *static_cast<T*>(ralloc(sizeof(T)));
05136 new (&t) T(a1,a2,a3,a4);
05137 return t;
05138 }
05139 template<class T, typename A1, typename A2, typename A3, typename A4, typename A5>
05140 forceinline T&
05141 Space::construct(A1 const& a1, A2 const& a2, A3 const& a3, A4 const& a4, A5 const& a5) {
05142 T& t = *static_cast<T*>(ralloc(sizeof(T)));
05143 new (&t) T(a1,a2,a3,a4,a5);
05144 return t;
05145 }
05146
05147 }
05148
05149