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 namespace Gecode {
00028
00037
00038 typedef int ModEvent;
00039
00041 const ModEvent ME_GEN_FAILED = -1;
00043 const ModEvent ME_GEN_NONE = 0;
00045 const ModEvent ME_GEN_ASSIGNED = 1;
00047 const ModEvent ME_GEN_MAX = 15;
00048
00050 typedef int PropCond;
00052 const PropCond PC_GEN_ASSIGNED = 0;
00054 const PropCond PC_GEN_MAX = 15;
00056
00057
00070 enum VarTypeId {
00071 #include "gecode/vti.icc"
00072 VTI_LAST
00073 };
00074
00075
00076
00077
00078
00079
00080 class Actor;
00081 class Propagator;
00082 class Space;
00083 template <VarTypeId VTI, PropCond PC> class Variable;
00084
00085
00086
00087
00088
00089
00090
00098 class VarBase {};
00099
00107 class VarTypeProcessorBase {
00108 public:
00110 virtual void process(Space* home, VarBase* x) = 0;
00112 virtual void update(Space* home, VarBase* x) = 0;
00114 GECODE_KERNEL_EXPORT virtual ~VarTypeProcessorBase(void);
00115 };
00116
00124 template <VarTypeId VTI, PropCond PC>
00125 class VarTypeProcessor : public VarTypeProcessorBase {
00126 private:
00128 ModEvent met[ME_GEN_MAX+1][ME_GEN_MAX+1];
00135 PropCond pcs[ME_GEN_MAX+1];
00136 public:
00138 VarTypeProcessor(void);
00149 void mec(ModEvent me1, ModEvent me2, ModEvent me3);
00155 void mepc(ModEvent me, PropCond pc);
00160 void enter(void);
00162 virtual void process(Space* home, VarBase* x);
00164 virtual void update(Space* home, VarBase* x);
00165 };
00166
00177 typedef int PropModEvent;
00178
00179
00187 template <VarTypeId VTI, PropCond PC>
00188 class Variable : public VarBase {
00189 friend class Space;
00190 friend class Propagator;
00191 friend class VarTypeProcessor<VTI,PC>;
00192 private:
00193 Variable* _next;
00194
00201 unsigned int free_me;
00202 Propagator** idx[PC+2];
00203
00205 unsigned int free(void) const;
00207 void free(unsigned int n);
00209 void free_inc(void);
00211 void free_dec(void);
00212
00214 void update(Space* home, Variable* x);
00215
00217
00218
00219 Variable* next(void);
00221 ModEvent modevent(void) const;
00223 void modevent(ModEvent me);
00225
00226 public:
00228 Variable(Space* home);
00229
00231
00232
00240 void subscribe(Space* home, Propagator* p, PropCond pc,
00241 bool assigned, ModEvent me);
00243 void cancel(Space* home, Propagator* p, PropCond pc);
00245 unsigned int degree(void) const;
00247 void notify(Space* home, ModEvent me);
00249 void notify_unmodified(Space* home, ModEvent me);
00251
00253
00254
00255 bool modified(void) const;
00257
00259
00260
00261 Variable(Space* home, bool share, Variable& x);
00263 bool copied(void) const;
00265 Variable* forward(void) const;
00267
00269
00270
00271 static ModEvent pme(const Propagator* p);
00273 static PropModEvent pme(ModEvent me);
00275 static ModEvent combine(ModEvent me1, ModEvent me2);
00277
00279
00280
00281 static void* operator new(size_t,Space*);
00283 static void operator delete(void*,Space*);
00285 static void operator delete(void*);
00287 };
00288
00289
00290
00291
00296 enum ExecStatus {
00297 ES_FAILED = -1,
00298 ES_NOFIX = 0,
00299 ES_OK = 0,
00300 ES_FIX = 1,
00301 ES_SUBSUMED = 2,
00302 __ES_FIX_PARTIAL = 3,
00303 __ES_NOFIX_PARTIAL = 4
00304 };
00305
00310 enum PropCost {
00311 PC_CRAZY_LO = 0,
00312 PC_CRAZY_HI = 0,
00313 PC_CUBIC_LO = 1,
00314 PC_CUBIC_HI = 1,
00315 PC_QUADRATIC_LO = 2,
00316 PC_QUADRATIC_HI = 2,
00317 PC_LINEAR_HI = 3,
00318 PC_LINEAR_LO = 4,
00319 PC_TERNARY_HI = 5,
00320 PC_BINARY_HI = 6,
00321 PC_TERNARY_LO = 6,
00322 PC_BINARY_LO = 7,
00323 PC_UNARY_LO = 7,
00324 PC_UNARY_HI = 7,
00325 PC_MAX = 7
00326 };
00327
00335 class ActorLink {
00336 friend class Actor;
00337 friend class Space;
00338 template <VarTypeId VTI, PropCond PC> friend class Variable;
00339 private:
00340 ActorLink* _next; ActorLink* _prev;
00341 public:
00343
00344 ActorLink* prev(void) const; void prev(ActorLink*);
00345 ActorLink* next(void) const; void next(ActorLink*);
00347
00348
00350 void init(void);
00352 void unlink(void);
00354 void head(ActorLink* al);
00356 void tail(ActorLink* al);
00357 };
00358
00359
00370 class ActorDeleteLink : public ActorLink {
00371 friend class Actor;
00372 friend class Space;
00373 template <VarTypeId VTI, PropCond PC> friend class Variable;
00374 private:
00375 ActorDeleteLink* _next_d; ActorDeleteLink* _prev_d;
00376 public:
00377 ActorDeleteLink* next_delete(void) const;
00378 void next_delete(ActorDeleteLink*);
00379 ActorDeleteLink* prev_delete(void) const;
00380 void prev_delete(ActorDeleteLink*);
00381
00383 void init_delete(void);
00384 void unlink_delete(void);
00385 void insert_delete(ActorDeleteLink*,bool);
00386 };
00387
00388
00389
00394 class Actor : private ActorDeleteLink {
00395 friend class Space;
00396 template <VarTypeId VTI, PropCond PC> friend class Variable;
00397 public:
00399 virtual Actor* copy(Space*,bool) = 0;
00401 GECODE_KERNEL_EXPORT
00402 virtual size_t dispose(Space* home);
00403
00405
00406
00407 GECODE_KERNEL_EXPORT virtual void flush(void);
00409 GECODE_KERNEL_EXPORT virtual size_t cached(void) const;
00411 static void* operator new(size_t s, Space* home);
00413 static void operator delete(void* p, Space* home);
00414 private:
00415 #ifndef __GNUC__
00417 static void operator delete(void* p, size_t s);
00418 #endif
00420 static void* operator new(size_t s);
00422 void destruct(Space* home);
00423
00424 #ifdef __GNUC__
00425 public:
00427 virtual ~Actor(void) {}
00429 static void operator delete(void* p, size_t s);
00430 #endif
00431 };
00432
00433
00434
00439 class Propagator : public Actor {
00440 friend class Space;
00441 template <VarTypeId VTI, PropCond PC> friend class Variable;
00442 private:
00443 PropModEvent pme;
00444 protected:
00450 Propagator(Space* home, bool fd=false);
00452 Propagator(Space* home, bool share, Propagator& p);
00453
00455
00456
00466 ExecStatus ES_FIX_PARTIAL(PropModEvent pme);
00477 ExecStatus ES_NOFIX_PARTIAL(PropModEvent pme);
00479 public:
00481
00482
00483 virtual ExecStatus propagate(Space*) = 0;
00485 virtual PropCost cost(void) const = 0;
00487 };
00488
00489
00490
00491
00492
00493
00494
00495
00496 class Branching;
00497
00506 class BranchingDesc {
00507 friend class Space;
00508 private:
00509 unsigned int id;
00510 protected:
00512 BranchingDesc(Branching* b);
00513 public:
00515 GECODE_KERNEL_EXPORT
00516 virtual ~BranchingDesc(void);
00517
00519 virtual size_t size(void) const = 0;
00521 static void* operator new(size_t);
00523 static void operator delete(void*);
00524 };
00525
00530 class Branching : public Actor {
00531 friend class Space;
00532 friend class BranchingDesc;
00533 private:
00534 unsigned int id;
00535 protected:
00537 Branching(Space* home, bool fd=false);
00539 Branching(Space* home, bool share, Branching& b);
00540
00541 public:
00543
00544
00545 virtual unsigned int branch(Space* home) = 0;
00553 virtual ExecStatus commit(Space* home, unsigned int a, BranchingDesc* d) = 0;
00555 virtual BranchingDesc* description(void) = 0;
00557 };
00558
00559
00564 enum SpaceStatus {
00565 SS_FAILED,
00566 SS_SOLVED,
00567 SS_BRANCH
00568 };
00569
00573 class Space {
00574 friend class Propagator;
00575 friend class Branching;
00576 template <VarTypeId VTI, PropCond PC> friend class Variable;
00577 template <VarTypeId VTI, PropCond PC> friend class VarTypeProcessor;
00578 private:
00579 MemoryManager mm;
00580
00585
00586 class VarTypeData {
00587 public:
00589 VarTypeProcessorBase* proc;
00591 ModEvent mec[ME_GEN_MAX+1][ME_GEN_MAX+1];
00593 PropCond pcr[ME_GEN_MAX+1][PC_GEN_MAX+3];
00594 };
00596 GECODE_KERNEL_EXPORT static VarTypeData vtd[VTI_LAST];
00598 VarBase* vars[VTI_LAST];
00600 void process(void);
00602
00607
00608 ActorLink pool[PC_MAX+1];
00610 int pool_next;
00612 void pool_put(Propagator* p);
00614 bool pool_get(Propagator*& p);
00616
00623 ActorDeleteLink a_actors;
00630 Branching* b_fst;
00632 unsigned int branch_id;
00633
00635 GECODE_KERNEL_EXPORT static unsigned long int unused_uli;
00637 GECODE_KERNEL_EXPORT static unsigned int unused_ui;
00638
00640 unsigned long int _propagate(void);
00642 unsigned int _branch(void);
00643
00645 void propagator(Propagator* p, bool fd);
00647 void propagator(Propagator*);
00649 void branching(Branching* b, bool fd);
00651 template <VarTypeId VTI, PropCond PC>
00652 void variable(Variable<VTI,PC>* x);
00653
00658
00659 void process(VarTypeId VTI, Propagator* p, const ModEvent* mec);
00661 void process(VarTypeId VTI, Propagator* p);
00663
00664
00665 public:
00670 GECODE_KERNEL_EXPORT Space(void);
00675 GECODE_KERNEL_EXPORT virtual ~Space(void);
00686 GECODE_KERNEL_EXPORT Space(bool share, Space& s);
00693 virtual Space* copy(bool share) = 0;
00698 static void* operator new(size_t);
00703 static void operator delete(void*);
00704
00705
00706
00707
00708
00709
00710
00711
00712
00725 GECODE_KERNEL_EXPORT
00726 SpaceStatus status(unsigned int& a=unused_ui,
00727 unsigned long int& pn=unused_uli);
00728
00744 GECODE_KERNEL_EXPORT
00745 Space* clone(bool share=true, unsigned long int& pn=unused_uli);
00746
00774 GECODE_KERNEL_EXPORT
00775 void commit(unsigned int a, BranchingDesc* d=NULL,
00776 unsigned long int& pn=unused_uli);
00784 BranchingDesc* description(void) const;
00794 GECODE_KERNEL_EXPORT
00795 void flush(void);
00796
00797
00798
00799
00800
00801
00802
00810 void fail(void);
00819 bool failed(void) const;
00826 bool actors(void) const;
00836 GECODE_KERNEL_EXPORT
00837 unsigned int propagators(void) const;
00845 GECODE_KERNEL_EXPORT
00846 unsigned int branchings(void) const;
00847
00848
00849
00855
00856 void* alloc(size_t);
00858 void reuse(void*,size_t);
00860 template <size_t> void* fl_alloc(void);
00866 template <size_t> void fl_dispose(FreeList* f, FreeList* l);
00872 size_t allocated(void) const;
00874 GECODE_KERNEL_EXPORT size_t cached(void) const;
00876 };
00877
00878
00879
00880
00881
00882
00883
00884
00885
00886
00887
00888
00889
00890
00891 forceinline void*
00892 Space::operator new(size_t s) {
00893 return Memory::malloc(s);
00894 }
00895 forceinline void
00896 Space::operator delete(void* p) {
00897 Memory::free(p);
00898 }
00899
00900 forceinline void
00901 BranchingDesc::operator delete(void* p) {
00902 Memory::free(p);
00903 }
00904 forceinline void*
00905 BranchingDesc::operator new(size_t s) {
00906 return Memory::malloc(s);
00907 }
00908
00909
00910
00911
00912
00913
00914 forceinline void*
00915 Space::alloc(size_t s) {
00916 return mm.alloc(s);
00917 }
00918 forceinline void
00919 Space::reuse(void* p, size_t s) {
00920 return mm.reuse(p,s);
00921 }
00922
00923 template <size_t s>
00924 forceinline void*
00925 Space::fl_alloc(void) {
00926 return mm.template fl_alloc<s>();
00927 }
00928 template <size_t s>
00929 forceinline void
00930 Space::fl_dispose(FreeList* f, FreeList* l) {
00931 mm.template fl_dispose<s>(f,l);
00932 }
00933
00934 forceinline size_t
00935 Space::allocated(void) const {
00936 return mm.allocated();
00937 }
00938
00939
00940
00941
00942
00943
00944
00945 forceinline void
00946 Actor::operator delete(void* p, size_t s) {}
00947 forceinline void
00948 Actor::operator delete(void*,Space*) {}
00949 forceinline void*
00950 Actor::operator new(size_t s, Space* home) {
00951 return home->alloc(s);
00952 }
00953
00954 template <VarTypeId VTI, PropCond PC>
00955 forceinline void
00956 Variable<VTI,PC>::operator delete(void*) {}
00957 template <VarTypeId VTI, PropCond PC>
00958 forceinline void
00959 Variable<VTI,PC>::operator delete(void*, Space*) {}
00960 template <VarTypeId VTI, PropCond PC>
00961 forceinline void*
00962 Variable<VTI,PC>::operator new(size_t s, Space* home) {
00963 return home->alloc(s);
00964 }
00965
00966
00967
00968
00969
00970
00971
00972
00973 forceinline ActorLink*
00974 ActorLink::prev(void) const { return _prev; }
00975 forceinline ActorLink*
00976 ActorLink::next(void) const { return _next; }
00977 forceinline void
00978 ActorLink::prev(ActorLink* al) { _prev = al; }
00979 forceinline void
00980 ActorLink::next(ActorLink* al) { _next = al; }
00981
00982 forceinline void
00983 ActorLink::unlink(void) {
00984 ActorLink* p = _prev; ActorLink* n = _next;
00985 p->_next = n; n->_prev = p;
00986 }
00987 forceinline void
00988 ActorLink::init(void) {
00989 _next = this; _prev =this;
00990 }
00991 forceinline void
00992 ActorLink::head(ActorLink* a) {
00993
00994 ActorLink* n = _next;
00995 this->_next = a; a->_prev = this;
00996 a->_next = n; n->_prev = a;
00997 }
00998 forceinline void
00999 ActorLink::tail(ActorLink* a) {
01000
01001 ActorLink* p = _prev;
01002 a->_next = this; this->_prev = a;
01003 p->_next = a; a->_prev = p;
01004 }
01005
01006
01007
01008 forceinline ActorDeleteLink*
01009 ActorDeleteLink::next_delete(void) const { return _next_d; }
01010 forceinline ActorDeleteLink*
01011 ActorDeleteLink::prev_delete(void) const { return _prev_d; }
01012 forceinline void
01013 ActorDeleteLink::next_delete(ActorDeleteLink* adl) { _next_d = adl; }
01014 forceinline void
01015 ActorDeleteLink::prev_delete(ActorDeleteLink* adl) { _prev_d = adl; }
01016
01017 forceinline void
01018 ActorDeleteLink::unlink_delete(void) {
01019 ActorDeleteLink* p = _prev_d;
01020 ActorDeleteLink* n = _next_d;
01021 p->_next_d = n; n->_prev_d = p;
01022 }
01023
01024 forceinline void
01025 ActorDeleteLink::insert_delete(ActorDeleteLink* a, bool fd) {
01026 if (fd) {
01027
01028 ActorDeleteLink* n = _next_d;
01029 this->_next_d = a; a->_prev_d = this;
01030 a->_next_d = n; n->_prev_d = a;
01031 } else {
01032
01033 a->_prev_d = a; a->_next_d = a;
01034 }
01035 }
01036
01037 forceinline void
01038 ActorDeleteLink::init_delete(void) {
01039 _next_d = this; _prev_d = this;
01040 }
01041
01042
01043
01044
01045 forceinline size_t
01046 Actor::dispose(Space*) {
01047 return sizeof(*this);
01048 }
01049
01050 forceinline void
01051 Actor::destruct(Space* home) {
01052 unlink_delete();
01053 size_t s = dispose(home);
01054 home->reuse(this,s);
01055 }
01056
01057
01058
01059
01060
01061
01062
01063
01064
01065 forceinline BranchingDesc*
01066 Space::description(void) const {
01067 return b_fst->description();
01068 }
01069
01070
01071
01072
01073
01074
01075
01076
01077 template <VarTypeId VTI, PropCond PC>
01078 forceinline
01079 Variable<VTI,PC>::Variable(Space*) :
01080 _next(reinterpret_cast<Variable<VTI,PC>*>(1)), free_me(0) {
01081 for (int i=PC+2; i--; )
01082 idx[i] = NULL;
01083 }
01084
01085
01086 template <VarTypeId VTI, PropCond PC>
01087 forceinline unsigned int
01088 Variable<VTI,PC>::degree(void) const {
01089 return static_cast<unsigned int>(idx[PC+1] - idx[0]);
01090 }
01091
01092
01093
01094 template <VarTypeId VTI, PropCond PC>
01095 forceinline ModEvent
01096 Variable<VTI,PC>::modevent(void) const {
01097 return free_me & 15;
01098 }
01099
01100 template <VarTypeId VTI, PropCond PC>
01101 forceinline void
01102 Variable<VTI,PC>::modevent(ModEvent me) {
01103 free_me = (free_me & ~15) | me;
01104 }
01105 template <VarTypeId VTI, PropCond PC>
01106 forceinline unsigned int
01107 Variable<VTI,PC>::free(void) const {
01108 return free_me >> 4;
01109 }
01110
01111 template <VarTypeId VTI, PropCond PC>
01112 forceinline void
01113 Variable<VTI,PC>::free(unsigned int n) {
01114 free_me = (free_me & 15) | (n << 4);
01115 }
01116
01117 template <VarTypeId VTI, PropCond PC>
01118 forceinline void
01119 Variable<VTI,PC>::free_inc(void) {
01120 free_me += (1 << 4);
01121 }
01122
01123 template <VarTypeId VTI, PropCond PC>
01124 forceinline void
01125 Variable<VTI,PC>::free_dec(void) {
01126 free_me -= (1 << 4);
01127 }
01128
01129 template <VarTypeId VTI, PropCond PC>
01130 forceinline bool
01131 Variable<VTI,PC>::modified(void) const {
01132 return _next != reinterpret_cast<Variable<VTI,PC>*>(1);
01133 }
01134
01135
01136
01137 template <VarTypeId VTI, PropCond PC>
01138 forceinline Variable<VTI,PC>*
01139 Variable<VTI,PC>::next(void) {
01140 Variable<VTI,PC>* n = _next;
01141 _next = reinterpret_cast<Variable<VTI,PC>*>(1);
01142 return n;
01143 }
01144
01145 template <VarTypeId VTI, PropCond PC>
01146 forceinline bool
01147 Variable<VTI,PC>::copied(void) const {
01148 return _next != reinterpret_cast<Variable<VTI,PC>*>(1);
01149 }
01150
01151 template <VarTypeId VTI, PropCond PC>
01152 forceinline void
01153 Space::variable(Variable<VTI,PC>* x) {
01154 x->_next = static_cast<Variable<VTI,PC>*>(vars[VTI]);
01155 vars[VTI] = x;
01156 }
01157
01158 template <VarTypeId VTI, PropCond PC>
01159 forceinline
01160 Variable<VTI,PC>::Variable(Space* home, bool, Variable<VTI,PC>& x)
01161 : _next(reinterpret_cast<Variable<VTI,PC>*>(1)) {
01162
01163 idx[0] = x.idx[0];
01164
01165 x.idx[0] = reinterpret_cast<Propagator**>(this);
01166
01167 home->variable(&x);
01168 }
01169
01170 template <VarTypeId VTI, PropCond PC>
01171 forceinline Variable<VTI,PC>*
01172 Variable<VTI,PC>::forward(void) const {
01173 return reinterpret_cast<Variable<VTI,PC>*>(idx[0]);
01174 }
01175
01176
01177
01178
01179
01180
01181 template <VarTypeId VTI, PropCond PC>
01182 forceinline ModEvent
01183 Variable<VTI,PC>::pme(const Propagator* p) {
01184 return static_cast<ModEvent>((p->pme >> (VTI << 2)) & 15);
01185 }
01186
01187 template <VarTypeId VTI, PropCond PC>
01188 forceinline PropModEvent
01189 Variable<VTI,PC>::pme(ModEvent me) {
01190 return static_cast<PropModEvent>(me << (VTI << 2));
01191 }
01192
01193 template <VarTypeId VTI, PropCond PC>
01194 forceinline ModEvent
01195 Variable<VTI,PC>::combine(ModEvent me1, ModEvent me2) {
01196 return me2^Space::vtd[VTI].mec[me1][me2];
01197 }
01198
01199
01200
01201
01202
01203
01204 forceinline void
01205 Space::propagator(Propagator* p, bool fd) {
01206
01207 a_actors.head(p);
01208 a_actors.insert_delete(p,fd);
01209 }
01210
01211 forceinline void
01212 Space::propagator(Propagator* p) {
01213 a_actors.head(p);
01214 }
01215
01216 forceinline void
01217 Space::branching(Branching* b, bool fd) {
01218
01219 b->id = branch_id++;
01220
01221 if (b_fst == &a_actors)
01222 b_fst = b;
01223 a_actors.tail(b);
01224 a_actors.insert_delete(b,fd);
01225 }
01226
01227
01228
01229
01230
01231 forceinline
01232 Propagator::Propagator(Space* home, bool fd)
01233 : pme(0) {
01234 home->propagator(this,fd);
01235 }
01236
01237 forceinline
01238 Propagator::Propagator(Space*, bool, Propagator&)
01239 : pme(0) {}
01240
01241
01242
01243
01244
01245
01246
01247 forceinline
01248 Branching::Branching(Space* home, bool fd) {
01249 home->branching(this,fd);
01250 }
01251
01252 forceinline
01253 Branching::Branching(Space*, bool, Branching& b)
01254 : id(b.id) {}
01255
01256
01257
01258
01259
01260
01261
01262
01263 forceinline
01264 BranchingDesc::BranchingDesc(Branching* b)
01265 : id(b->id) {}
01266
01267 forceinline
01268 BranchingDesc::~BranchingDesc(void) {}
01269
01270
01271
01272
01273
01274
01275
01276
01277
01278
01279 forceinline void
01280 Space::pool_put(Propagator* p) {
01281 int c = p->cost();
01282 pool[c].tail(p);
01283 if (c > pool_next)
01284 pool_next = c;
01285 }
01286
01287 forceinline void
01288 Space::fail(void) {
01289 b_fst = NULL;
01290 }
01291
01292 forceinline bool
01293 Space::failed(void) const {
01294 return b_fst == NULL;
01295 }
01296
01297 forceinline bool
01298 Space::actors(void) const {
01299 return &a_actors != a_actors.next();
01300 }
01301
01302 forceinline void
01303 Space::process(VarTypeId VTI, Propagator* p) {
01304
01305 PropModEvent old_pme = p->pme;
01306
01307 ModEvent old_me = old_pme & (ME_GEN_MAX << (VTI << 2));
01308
01309 if (old_me == (ME_GEN_ASSIGNED << (VTI << 2)))
01310 return;
01311
01312 p->pme ^= old_me ^ (ME_GEN_ASSIGNED << (VTI << 2));
01313
01314 p->unlink();
01315 pool_put(p);
01316 }
01317
01318 forceinline void
01319 Space::process(VarTypeId VTI, Propagator* p, const ModEvent* mec) {
01320 PropModEvent old_pme = p->pme;
01321
01322 ModEvent old_me = ((old_pme >> (VTI << 2)) & ME_GEN_MAX);
01323
01324 ModEvent com_me = mec[old_me];
01325
01326 if (com_me == 0)
01327 return;
01328
01329 p->pme ^= (com_me << (VTI << 2));
01330
01331 p->unlink();
01332 pool_put(p);
01333 }
01334
01335 forceinline ExecStatus
01336 Propagator::ES_FIX_PARTIAL(PropModEvent pme) {
01337 this->pme = pme; return __ES_FIX_PARTIAL;
01338 }
01339
01340 forceinline ExecStatus
01341 Propagator::ES_NOFIX_PARTIAL(PropModEvent pme) {
01342 this->pme = pme; return __ES_NOFIX_PARTIAL;
01343 }
01344
01345
01346
01347
01348
01349
01350
01351 template <VarTypeId VTI, PropCond PC>
01352 forceinline void
01353 Variable<VTI,PC>::subscribe(Space* home, Propagator* p, PropCond pc,
01354 bool assigned, ModEvent me) {
01355 if (assigned) {
01356
01357 home->process(VTI,p);
01358 } else {
01359 if (free() == 0) {
01360 if (idx[0] == NULL) {
01361
01362 free(3);
01363 Propagator** prop = reinterpret_cast<Propagator**>
01364 (home->alloc(4*sizeof(Propagator*))) + 4;
01365 for (PropCond i = PC+2; i--; )
01366 idx[i] = prop;
01367 } else {
01368
01369 int n = static_cast<int>(idx[PC+1] - idx[0]);
01370 Propagator** prop = reinterpret_cast<Propagator**>
01371 (home->alloc(2*n*sizeof(Propagator*))) + n;
01372 free(n-1);
01373
01374 memcpy(prop, idx[0], n*sizeof(Propagator*));
01375 home->reuse(idx[0], n*sizeof(Propagator*));
01376
01377 ptrdiff_t o = prop - idx[0];
01378 idx[0] = prop;
01379 for (PropCond i = PC+1; i > 0; i--)
01380 idx[i] += o;
01381 }
01382 } else {
01383 free_dec();
01384 }
01385
01386 --idx[0];
01387 for (PropCond i = 0; i < pc; i++)
01388 *(idx[i]) = *(--idx[i+1]);
01389 *idx[pc]=p;
01390
01391 if (pc != PC_GEN_ASSIGNED) {
01392 ModEvent* mec = &home->vtd[VTI].mec[me][0];
01393 home->process(VTI,p,mec);
01394 }
01395 }
01396 }
01397
01398
01399
01400
01401
01402
01403
01404 template <VarTypeId VTI, PropCond PC>
01405 forceinline void
01406 Variable<VTI,PC>::cancel(Space*, Propagator* p, PropCond pc) {
01407 if (idx[0] != NULL) {
01408 Propagator** f = idx[pc];
01409 while (*f != p) f++;
01410 *f=*idx[pc];
01411 for (PropCond i=pc; i>0; i--)
01412 *(idx[i]++)=*(idx[i-1]);
01413 idx[0]++;
01414 free_inc();
01415 }
01416 }
01417
01418 template <VarTypeId VTI, PropCond PC>
01419 forceinline void
01420 Variable<VTI,PC>::notify(Space* home, ModEvent new_me) {
01421 if (modified()) {
01422 free_me ^= home->vtd[VTI].mec[new_me][modevent()];
01423 } else {
01424 home->variable(this);
01425 modevent(new_me);
01426 }
01427 }
01428
01429 template <VarTypeId VTI, PropCond PC>
01430 forceinline void
01431 Variable<VTI,PC>::notify_unmodified(Space* home, ModEvent new_me) {
01432 assert(!modified());
01433 home->variable(this);
01434 modevent(new_me);
01435 }
01436
01437
01438
01439
01440
01441
01442
01443 template <VarTypeId VTI, PropCond PC>
01444 forceinline
01445 VarTypeProcessor<VTI,PC>::VarTypeProcessor(void) {
01446
01447 for (ModEvent i = ME_GEN_MAX+1; i--; )
01448 for (ModEvent j = ME_GEN_MAX+1; j--; )
01449 met[i][j] = ME_GEN_NONE;
01450 for (ModEvent i = ME_GEN_MAX+1; i--; ) {
01451
01452 met[i][ME_GEN_ASSIGNED] = ME_GEN_ASSIGNED;
01453 met[ME_GEN_ASSIGNED][i] = ME_GEN_ASSIGNED;
01454
01455 met[i][ME_GEN_NONE] = i;
01456 met[ME_GEN_NONE][i] = i;
01457
01458 met[i][i] = i;
01459
01460 pcs[i] = 0;
01461 }
01462 }
01463
01464 template <VarTypeId VTI, PropCond PC>
01465 forceinline void
01466 VarTypeProcessor<VTI,PC>::mec(ModEvent me1, ModEvent me2, ModEvent me3) {
01467 met[me1][me2] = met[me2][me1] = me3;
01468 }
01469
01470 template <VarTypeId VTI, PropCond PC>
01471 forceinline void
01472 VarTypeProcessor<VTI,PC>::mepc(ModEvent me, PropCond pc) {
01473 pcs[me] |= (1 << pc);
01474 }
01475
01476 template <VarTypeId VTI, PropCond PC>
01477 void
01478 VarTypeProcessor<VTI,PC>::enter(void) {
01479 Space::vtd[VTI].proc = this;
01480
01481 for (ModEvent i = ME_GEN_MAX+1; i--; )
01482 for (ModEvent j = ME_GEN_MAX+1; j--; )
01483
01484 Space::vtd[VTI].mec[i][j] = j^met[i][j];
01485
01486 for (ModEvent me = ME_GEN_MAX+1; me--; ) {
01487 int i = 0;
01488 for (PropCond pc=PC+1; pc--; )
01489 if (pcs[me] & (1 << pc)) {
01490
01491 Space::vtd[VTI].pcr[me][i+1] = pc+1;
01492
01493 while (pcs[me] & (1 << (pc-1)))
01494 pc--;
01495
01496 Space::vtd[VTI].pcr[me][i+0] = pc;
01497 i += 2;
01498 }
01499 Space::vtd[VTI].pcr[me][i+0] = -1;
01500 }
01501 }
01502
01503 template <VarTypeId VTI, PropCond PC>
01504 forceinline void
01505 Variable<VTI,PC>::update(Space* home, Variable<VTI,PC>* x) {
01506
01507
01508 Propagator** f = idx[0];
01509 x->idx[0] = f;
01510 if (f == NULL) {
01511 free_me = 0;
01512 for (int i=1; i<PC+2; i++)
01513 idx[i] = NULL;
01514 } else {
01515 free_me = 1 << 4;
01516 int n = static_cast<int>(x->idx[PC+1] - f);
01517 Propagator** t = reinterpret_cast<Propagator**>
01518 (home->alloc((n+1)*sizeof(Propagator*))) + 1;
01519 idx[0] = t;
01520 ptrdiff_t o = t - f;
01521 for (PropCond i = PC+1; i>0; i--)
01522 idx[i] = x->idx[i]+o;
01523 if (n & 1)
01524 t[0] = static_cast<Propagator*>(f[0]->prev());
01525 for (int i = n-1; i>0; i -= 2) {
01526 t[i-1] = static_cast<Propagator*>(f[i-1]->prev());;
01527 t[i-0] = static_cast<Propagator*>(f[i-0]->prev());;
01528 }
01529 }
01530 }
01531
01532 template <VarTypeId VTI, PropCond PC>
01533 void
01534 VarTypeProcessor<VTI,PC>::update(Space* home, VarBase* vb) {
01535 Variable<VTI,PC>* x = static_cast<Variable<VTI,PC>*>(vb);
01536 do {
01537 x->forward()->update(home,x);
01538 x = x->next();
01539 } while (x != NULL);
01540 }
01541
01542 template <VarTypeId VTI, PropCond PC>
01543 void
01544 VarTypeProcessor<VTI,PC>::process(Space* home, VarBase* vb) {
01545 Variable<VTI,PC>* x = static_cast<Variable<VTI,PC>*>(vb);
01546 do {
01547 ModEvent me = x->modevent();
01548 if (me != ME_GEN_ASSIGNED) {
01549 ModEvent* mec = &home->vtd[VTI].mec[me][0];
01550 PropCond* pcr = &home->vtd[VTI].pcr[me][0];
01551 do {
01552 Propagator** b = x->idx[*pcr]; pcr++;
01553 Propagator** p = x->idx[*pcr]; pcr++;
01554 while (p-- > b)
01555 home->process(VTI,*p,mec);
01556 } while (*pcr >= 0);
01557 } else {
01558
01559
01560 Propagator** b = x->idx[0]; x->idx[0] = NULL;
01561 Propagator** p = x->idx[PC+1]; x->idx[PC+1] = NULL;
01562
01563 unsigned int n = x->free() + (p-b);
01564 Propagator** s = p-n;
01565 while (p-- > b)
01566 home->process(VTI,*p);
01567 home->reuse(s,n*sizeof(Propagator*));
01568 }
01569 x = x->next();
01570 } while (x != NULL);
01571 }
01572
01573
01574 }
01575
01576