Generated on Wed Nov 5 2014 05:18:29 for Gecode by doxygen 1.7.6.1
core.hpp
Go to the documentation of this file.
00001 /* -*- mode: C++; c-basic-offset: 2; indent-tabs-mode: nil -*- */
00002 /*
00003  *  Main authors:
00004  *     Christian Schulte <schulte@gecode.org>
00005  *     Guido Tack <tack@gecode.org>
00006  *     Mikael Lagerkvist <lagerkvist@gecode.org>
00007  *
00008  *  Contributing authors:
00009  *     Filip Konvicka <filip.konvicka@logis.cz>
00010  *
00011  *  Copyright:
00012  *     Christian Schulte, 2002
00013  *     Guido Tack, 2003
00014  *     Mikael Lagerkvist, 2006
00015  *     LOGIS, s.r.o., 2009
00016  *
00017  *  Bugfixes provided by:
00018  *     Alexander Samoilov <alexander_samoilov@yahoo.com>
00019  *
00020  *  Last modified:
00021  *     $Date: 2013-10-30 16:01:30 +0100 (Wed, 30 Oct 2013) $ by $Author: schulte $
00022  *     $Revision: 14038 $
00023  *
00024  *  This file is part of Gecode, the generic constraint
00025  *  development environment:
00026  *     http://www.gecode.org
00027  *
00028  *  Permission is hereby granted, free of charge, to any person obtaining
00029  *  a copy of this software and associated documentation files (the
00030  *  "Software"), to deal in the Software without restriction, including
00031  *  without limitation the rights to use, copy, modify, merge, publish,
00032  *  distribute, sublicense, and/or sell copies of the Software, and to
00033  *  permit persons to whom the Software is furnished to do so, subject to
00034  *  the following conditions:
00035  *
00036  *  The above copyright notice and this permission notice shall be
00037  *  included in all copies or substantial portions of the Software.
00038  *
00039  *  THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,
00040  *  EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF
00041  *  MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND
00042  *  NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE
00043  *  LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION
00044  *  OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION
00045  *  WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
00046  *
00047  */
00048 
00049 #include <iostream>
00050 
00051 namespace Gecode {
00052 
00053   class Space;
00054 
00079   class SharedHandle {
00080   public:
00088     class Object {
00089       friend class Space;
00090       friend class SharedHandle;
00091     private:
00093       Object* next;
00095       Object* fwd;
00097       unsigned int use_cnt;
00098     public:
00100       Object(void);
00102       virtual Object* copy(void) const = 0;
00104       virtual ~Object(void);
00106       static void* operator new(size_t s);
00108       static void  operator delete(void* p);
00109     };
00110   private:
00112     Object* o;
00114     void subscribe(void);
00116     void cancel(void);
00117   public:
00119     SharedHandle(void);
00121     SharedHandle(SharedHandle::Object* so);
00123     SharedHandle(const SharedHandle& sh);
00125     SharedHandle& operator =(const SharedHandle& sh);
00127     void update(Space& home, bool share, SharedHandle& sh);
00129     ~SharedHandle(void);
00130   protected:
00132     SharedHandle::Object* object(void) const;
00134     void object(SharedHandle::Object* n);
00135   };
00136 
00145 
00146   typedef int ModEvent;
00147 
00149   const ModEvent ME_GEN_FAILED   = -1;
00151   const ModEvent ME_GEN_NONE     =  0;
00153   const ModEvent ME_GEN_ASSIGNED =  1;
00154 
00156   typedef int PropCond;
00158   const PropCond PC_GEN_NONE     = -1;
00160   const PropCond PC_GEN_ASSIGNED = 0;
00162 
00173   typedef int ModEventDelta;
00174 
00175 }
00176 
00177 #include <gecode/kernel/var-type.hpp>
00178 
00179 namespace Gecode {
00180 
00182   class NoIdxVarImpConf {
00183   public:
00185     static const int idx_c = -1;
00187     static const int idx_d = -1;
00189     static const PropCond pc_max = PC_GEN_ASSIGNED;
00191     static const int free_bits = 0;
00193     static const int med_fst = 0;
00195     static const int med_lst = 0;
00197     static const int med_mask = 0;
00199     static Gecode::ModEvent me_combine(ModEvent me1, ModEvent me2);
00201     static bool med_update(ModEventDelta& med, ModEvent me);
00202   };
00203 
00204   forceinline ModEvent
00205   NoIdxVarImpConf::me_combine(ModEvent, ModEvent) {
00206     GECODE_NEVER; return 0;
00207   }
00208   forceinline bool
00209   NoIdxVarImpConf::med_update(ModEventDelta&, ModEvent) {
00210     GECODE_NEVER; return false;
00211   }
00212 
00213 
00214   /*
00215    * These are the classes of interest
00216    *
00217    */
00218   class ActorLink;
00219   class Actor;
00220   class Propagator;
00221   class LocalObject;
00222   class Advisor;
00223   class AFC;
00224   class Brancher;
00225   class BrancherHandle;
00226   template<class A> class Council;
00227   template<class A> class Advisors;
00228   template<class VIC> class VarImp;
00229 
00230 
00231   /*
00232    * Variable implementations
00233    *
00234    */
00235 
00243   class VarImpBase {};
00244 
00251   class GECODE_VTABLE_EXPORT VarImpDisposerBase {
00252   public:
00254     GECODE_KERNEL_EXPORT virtual void dispose(Space& home, VarImpBase* x);
00256     GECODE_KERNEL_EXPORT virtual ~VarImpDisposerBase(void);
00257   };
00258 
00265   template<class VarImp>
00266   class VarImpDisposer : public VarImpDisposerBase {
00267   public:
00269     VarImpDisposer(void);
00271     virtual void dispose(Space& home, VarImpBase* x);
00272   };
00273 
00275   class Delta {
00276     template<class VIC> friend class VarImp;
00277   private:
00279     ModEvent me;
00280   };
00281 
00289   template<class VIC>
00290   class VarImp : public VarImpBase {
00291     friend class Space;
00292     friend class Propagator;
00293     template<class VarImp> friend class VarImpDisposer;
00294   private:
00295     union {
00303       ActorLink** base;
00312       VarImp<VIC>* fwd;
00313     } b;
00314 
00316     static const int idx_c = VIC::idx_c;
00318     static const int idx_d = VIC::idx_d;
00320     static const int free_bits = VIC::free_bits;
00322     unsigned int entries;
00324     unsigned int free_and_bits;
00326     static const Gecode::PropCond pc_max = VIC::pc_max;
00327 
00328     union {
00339       unsigned int idx[pc_max+1];
00341       VarImp<VIC>* next;
00342     } u;
00343 
00345     ActorLink** actor(PropCond pc);
00347     ActorLink** actorNonZero(PropCond pc);
00349     unsigned int& idx(PropCond pc);
00351     unsigned int idx(PropCond pc) const;
00352 
00359     void update(VarImp* x, ActorLink**& sub);
00366     static void update(Space& home, ActorLink**& sub);
00367 
00369     void enter(Space& home, Propagator* p, PropCond pc);
00371     void enter(Space& home, Advisor* a);
00373     void resize(Space& home);
00375     void remove(Space& home, Propagator* p, PropCond pc);
00377     void remove(Space& home, Advisor* a);
00378 
00379 
00380   protected:
00382     void cancel(Space& home);
00388     bool advise(Space& home, ModEvent me, Delta& d);
00389 #ifdef GECODE_HAS_VAR_DISPOSE
00390 
00391     static VarImp<VIC>* vars_d(Space& home);
00393     static void vars_d(Space& home, VarImp<VIC>* x);
00394 #endif
00395 
00396   public:
00398     VarImp(Space& home);
00400     VarImp(void);
00401 
00403 
00404 
00416     void subscribe(Space& home, Propagator& p, PropCond pc,
00417                    bool assigned, ModEvent me, bool schedule);
00423     void cancel(Space& home, Propagator& p, PropCond pc,
00424                 bool assigned);
00430     void subscribe(Space& home, Advisor& a, bool assigned);
00436     void cancel(Space& home, Advisor& a, bool assigned);
00437 
00444     unsigned int degree(void) const;
00451     double afc(const Space& home) const;
00453 
00455 
00456 
00457     VarImp(Space& home, bool share, VarImp& x);
00459     bool copied(void) const;
00461     VarImp* forward(void) const;
00463     VarImp* next(void) const;
00465 
00467 
00468 
00475     static void schedule(Space& home, Propagator& p, ModEvent me,
00476                          bool force = false);
00478     static ModEvent me(const ModEventDelta& med);
00480     static ModEventDelta med(ModEvent me);
00482     static ModEvent me_combine(ModEvent me1, ModEvent me2);
00484 
00486 
00487 
00488     static ModEvent modevent(const Delta& d);
00490 
00492 
00493 
00494     unsigned int bits(void) const;
00496     unsigned int& bits(void);
00498 
00499   protected:
00501     void schedule(Space& home, PropCond pc1, PropCond pc2, ModEvent me);
00502 
00503   public:
00505 
00506 
00507     static void* operator new(size_t,Space&);
00509     static void  operator delete(void*,Space&);
00511     static void  operator delete(void*);
00513   };
00514 
00523   enum ExecStatus {
00524     __ES_SUBSUMED       = -2, 
00525     ES_FAILED           = -1, 
00526     ES_NOFIX            =  0, 
00527     ES_OK               =  0, 
00528     ES_FIX              =  1, 
00529     ES_NOFIX_FORCE      =  2, 
00530     __ES_PARTIAL        =  2  
00531   };
00532 
00537   class PropCost {
00538     friend class Space;
00539   public:
00541     enum ActualCost {
00542       AC_CRAZY_LO     = 0, 
00543       AC_CRAZY_HI     = 0, 
00544       AC_CUBIC_LO     = 1, 
00545       AC_CUBIC_HI     = 1, 
00546       AC_QUADRATIC_LO = 2, 
00547       AC_QUADRATIC_HI = 2, 
00548       AC_LINEAR_HI    = 3, 
00549       AC_LINEAR_LO    = 4, 
00550       AC_TERNARY_HI   = 4, 
00551       AC_BINARY_HI    = 5, 
00552       AC_TERNARY_LO   = 5, 
00553       AC_BINARY_LO    = 6, 
00554       AC_UNARY_LO     = 6, 
00555       AC_UNARY_HI     = 6, 
00556       AC_MAX          = 6  
00557     };
00559     ActualCost ac;
00560   public:
00562     enum Mod {
00563       LO, 
00564       HI  
00565     };
00566   private:
00568     static PropCost cost(Mod m, ActualCost lo, ActualCost hi, unsigned int n);
00570     PropCost(ActualCost ac);
00571   public:
00573     static PropCost crazy(PropCost::Mod m, unsigned int n);
00575     static PropCost crazy(PropCost::Mod m, int n);
00577     static PropCost cubic(PropCost::Mod m, unsigned int n);
00579     static PropCost cubic(PropCost::Mod m, int n);
00581     static PropCost quadratic(PropCost::Mod m, unsigned int n);
00583     static PropCost quadratic(PropCost::Mod m, int n);
00585     static PropCost linear(PropCost::Mod m, unsigned int n);
00587     static PropCost linear(PropCost::Mod m, int n);
00589     static PropCost ternary(PropCost::Mod m);
00591     static PropCost binary(PropCost::Mod m);
00593     static PropCost unary(PropCost::Mod m);
00594   };
00595 
00596 
00601   enum ActorProperty {
00610     AP_DISPOSE = (1 << 0),
00616     AP_WEAKLY  = (1 << 1)
00617   };
00618 
00619 
00627   class ActorLink {
00628     friend class Actor;
00629     friend class Propagator;
00630     friend class Advisor;
00631     friend class Brancher;
00632     friend class LocalObject;
00633     friend class Space;
00634     template<class VIC> friend class VarImp;
00635   private:
00636     ActorLink* _next; ActorLink* _prev;
00637   public:
00639 
00640     ActorLink* prev(void) const; void prev(ActorLink*);
00641     ActorLink* next(void) const; void next(ActorLink*);
00642     ActorLink** next_ref(void);
00644 
00646     void init(void);
00648     void unlink(void);
00650     void head(ActorLink* al);
00652     void tail(ActorLink* al);
00654     bool empty(void) const;
00656     template<class T> static ActorLink* cast(T* a);
00658     template<class T> static const ActorLink* cast(const T* a);
00659   };
00660 
00661 
00666   class GECODE_VTABLE_EXPORT Actor : private ActorLink {
00667     friend class ActorLink;
00668     friend class Space;
00669     friend class Propagator;
00670     friend class Advisor;
00671     friend class Brancher;
00672     friend class LocalObject;
00673     template<class VIC> friend class VarImp;
00674     template<class A> friend class Council;
00675   private:
00677     static Actor* cast(ActorLink* al);
00679     static const Actor* cast(const ActorLink* al);
00681     GECODE_KERNEL_EXPORT static Actor* sentinel;
00682   public:
00684     virtual Actor* copy(Space& home, bool share) = 0;
00685 
00687 
00688 
00689     GECODE_KERNEL_EXPORT
00690     virtual size_t dispose(Space& home);
00692     static void* operator new(size_t s, Space& home);
00694     static void  operator delete(void* p, Space& home);
00695   private:
00696 #ifndef __GNUC__
00697 
00698     static void  operator delete(void* p);
00699 #endif
00700 
00701     static void* operator new(size_t s);
00703 #ifdef __GNUC__
00704   public:
00706     GECODE_KERNEL_EXPORT virtual ~Actor(void);
00708     static void  operator delete(void* p);
00709 #endif
00710   };
00711 
00712 
00713 
00717   class Home {
00718   protected:
00720     Space& s;
00722     Propagator* p;
00723   public:
00725 
00726 
00727     Home(Space& s, Propagator* p=NULL);
00729     Home& operator =(const Home& h);
00731     operator Space&(void);
00733 
00734 
00735 
00736     Home operator ()(Propagator& p);
00738     Propagator* propagator(void) const;
00740 
00741 
00742 
00743     bool failed(void) const;
00745     void fail(void);
00747     void notice(Actor& a, ActorProperty p, bool duplicate=false);
00749   };
00750 
00755   class GECODE_VTABLE_EXPORT Propagator : public Actor {
00756     friend class ActorLink;
00757     friend class Space;
00758     template<class VIC> friend class VarImp;
00759     friend class Advisor;
00760     template<class A> friend class Council;
00761   private:
00762     union {
00764       ModEventDelta med;
00766       size_t size;
00768       Gecode::ActorLink* advisors;
00769     } u;
00771     GlobalAFC::Counter& gafc;
00773     static Propagator* cast(ActorLink* al);
00775     static const Propagator* cast(const ActorLink* al);
00776   protected:
00778     Propagator(Home home);
00780     Propagator(Space& home, bool share, Propagator& p);
00782     Propagator* fwd(void) const;
00783 
00784   public:
00786 
00787 
00810     virtual ExecStatus propagate(Space& home, const ModEventDelta& med) = 0;
00812     virtual PropCost cost(const Space& home, const ModEventDelta& med) const = 0;
00820     ModEventDelta modeventdelta(void) const;
00856     GECODE_KERNEL_EXPORT
00857     virtual ExecStatus advise(Space& home, Advisor& a, const Delta& d);
00859 
00860 
00861 
00862     double afc(const Space& home) const;
00864   };
00865 
00866 
00874   template<class A>
00875   class Council {
00876     friend class Advisor;
00877     friend class Advisors<A>;
00878   private:
00880     mutable ActorLink* advisors;
00881   public:
00883     Council(void);
00885     Council(Space& home);
00887     bool empty(void) const;
00889     void update(Space& home, bool share, Council<A>& c);
00891     void dispose(Space& home);
00892   };
00893 
00894 
00899   template<class A>
00900   class Advisors {
00901   private:
00903     ActorLink* a;
00904   public:
00906     Advisors(const Council<A>& c);
00908     bool operator ()(void) const;
00910     void operator ++(void);
00912     A& advisor(void) const;
00913   };
00914 
00915 
00926   class Advisor : private ActorLink {
00927     template<class VIC> friend class VarImp;
00928     template<class A> friend class Council;
00929     template<class A> friend class Advisors;
00930   private:
00932     bool disposed(void) const;
00934     static Advisor* cast(ActorLink* al);
00936     static const Advisor* cast(const ActorLink* al);
00937   protected:
00939     Propagator& propagator(void) const;
00940   public:
00942     template<class A>
00943     Advisor(Space& home, Propagator& p, Council<A>& c);
00945     Advisor(Space& home, bool share, Advisor& a);
00946 
00948 
00949 
00950     template<class A>
00951     void dispose(Space& home, Council<A>& c);
00953     static void* operator new(size_t s, Space& home);
00955     static void  operator delete(void* p, Space& home);
00957   private:
00958 #ifndef __GNUC__
00959 
00960     static void  operator delete(void* p);
00961 #endif
00962 
00963     static void* operator new(size_t s);
00964   };
00965 
00966 
00971   class GECODE_VTABLE_EXPORT NGL {
00972   private:
00974     void* nl;
00975   public:
00977     enum Status {
00978       FAILED,   
00979       SUBSUMED, 
00980       NONE      
00981     };
00983     NGL(void);
00985     NGL(Space& home);
00987     NGL(Space& home, bool share, NGL& ngl);
00989     virtual void subscribe(Space& home, Propagator& p) = 0;
00991     virtual void cancel(Space& home, Propagator& p) = 0;
00993     virtual NGL::Status status(const Space& home) const = 0;
00995     virtual ExecStatus prune(Space& home) = 0;
00997     virtual NGL* copy(Space& home, bool share) = 0;
00999     GECODE_KERNEL_EXPORT
01000     virtual bool notice(void) const;
01002     virtual size_t dispose(Space& home);
01004 
01005 
01006     bool leaf(void) const;
01008     NGL* next(void) const;
01010     void leaf(bool l);
01012     void next(NGL* n);
01014     NGL* add(NGL* n, bool l);
01016 
01017 
01018 
01019     static void* operator new(size_t s, Space& home);
01021     static void  operator delete(void* s, Space& home);
01023     static void  operator delete(void* p);
01025   };
01026 
01036   class GECODE_VTABLE_EXPORT Choice {
01037     friend class Space;
01038   private:
01039     unsigned int _id;  
01040     unsigned int _alt; 
01041 
01043     unsigned int id(void) const;
01044   protected:
01046     Choice(const Brancher& b, const unsigned int a);
01047   public:
01049     unsigned int alternatives(void) const;
01051     GECODE_KERNEL_EXPORT virtual ~Choice(void);
01053     virtual size_t size(void) const = 0;
01055     static void* operator new(size_t);
01057     static void  operator delete(void*);
01059     GECODE_KERNEL_EXPORT virtual void archive(Archive& e) const;
01060   };
01061 
01071   class GECODE_VTABLE_EXPORT Brancher : public Actor {
01072     friend class ActorLink;
01073     friend class Space;
01074     friend class Choice;
01075   private:
01077     unsigned int _id;
01079     static Brancher* cast(ActorLink* al);
01081     static const Brancher* cast(const ActorLink* al);
01082   protected:
01084     Brancher(Home home);
01086     Brancher(Space& home, bool share, Brancher& b);
01087   public:
01089 
01090 
01091     unsigned int id(void) const;
01100     virtual bool status(const Space& home) const = 0;
01108     virtual const Choice* choice(Space& home) = 0;
01110     virtual const Choice* choice(const Space& home, Archive& e) = 0;
01117     virtual ExecStatus commit(Space& home, const Choice& c, 
01118                               unsigned int a) = 0;
01132     GECODE_KERNEL_EXPORT 
01133     virtual NGL* ngl(Space& home, const Choice& c, unsigned int a) const;
01143     GECODE_KERNEL_EXPORT 
01144     virtual void print(const Space& home, const Choice& c, unsigned int a,
01145                        std::ostream& o) const;
01147   };
01148 
01157   class BrancherHandle {
01158   private:
01160     unsigned int _id;
01161   public:
01163     BrancherHandle(void);
01165     BrancherHandle(const Brancher& b);
01167     void update(Space& home, bool share, BrancherHandle& bh);
01169     unsigned int id(void) const;
01171     bool operator ()(const Space& home) const;
01173     void kill(Space& home);
01174   };
01175 
01183   class LocalObject : public Actor {
01184     friend class ActorLink;
01185     friend class Space;
01186     friend class LocalHandle;
01187   protected:
01189     LocalObject(Home home);
01191     LocalObject(Space& home, bool share, LocalObject& l);
01193     static LocalObject* cast(ActorLink* al);
01195     static const LocalObject* cast(const ActorLink* al);
01196   private:
01198     GECODE_KERNEL_EXPORT void fwdcopy(Space& home, bool share);
01199   public:
01201     LocalObject* fwd(Space& home, bool share);
01202   };
01203 
01210   class LocalHandle {
01211   private:
01213     LocalObject* o;
01214   protected:
01216     LocalHandle(void);
01218     LocalHandle(LocalObject* lo);
01220     LocalHandle(const LocalHandle& lh);
01221   public:
01223     LocalHandle& operator =(const LocalHandle& lh);
01225     void update(Space& home, bool share, LocalHandle& lh);
01227     ~LocalHandle(void);
01228   protected:
01230     LocalObject* object(void) const;
01232     void object(LocalObject* n);
01233   };
01234 
01235 
01240   class GECODE_VTABLE_EXPORT NoGoods {
01241   protected:
01243     unsigned long int n;
01244   public:
01246     NoGoods(void);
01248     GECODE_KERNEL_EXPORT 
01249     virtual void post(Space& home);
01251     unsigned long int ng(void) const;
01253     void ng(unsigned long int n);
01255     virtual ~NoGoods(void);
01256   };
01257 
01258 
01263   enum SpaceStatus {
01264     SS_FAILED, 
01265     SS_SOLVED, 
01266     SS_BRANCH  
01267   };
01268 
01273   class StatusStatistics {
01274   public:
01276     unsigned long int propagate;
01278     bool wmp;
01280     StatusStatistics(void);
01282     void reset(void);
01284     StatusStatistics operator +(const StatusStatistics& s);
01286     StatusStatistics& operator +=(const StatusStatistics& s);
01287   };
01288 
01293   class CloneStatistics {
01294   public:
01296     CloneStatistics(void);
01298     void reset(void);
01300     CloneStatistics operator +(const CloneStatistics& s);
01302     CloneStatistics& operator +=(const CloneStatistics& s);
01303   };
01304 
01309   class CommitStatistics {
01310   public:
01312     CommitStatistics(void);
01314     void reset(void);
01316     CommitStatistics operator +(const CommitStatistics& s);
01318     CommitStatistics& operator +=(const CommitStatistics& s);
01319   };
01320 
01321 
01325   class GECODE_VTABLE_EXPORT Space {
01326     friend class Actor;
01327     friend class Propagator;
01328     friend class Brancher;
01329     friend class Advisor;
01330     template<class VIC> friend class VarImp;
01331     template<class VarImp> friend class VarImpDisposer;
01332     friend class SharedHandle;
01333     friend class LocalObject;
01334     friend class Region;
01335     friend class AFC;
01336     friend class BrancherHandle;
01337   private:
01339     SharedMemory* sm;
01341     MemoryManager mm;
01343     GlobalAFC gafc;
01345     ActorLink pl;
01347     ActorLink bl;
01353     Brancher* b_status;
01365     Brancher* b_commit;
01367     Brancher* brancher(unsigned int id);
01369     GECODE_KERNEL_EXPORT
01370     void kill_brancher(unsigned int id);
01372     static const unsigned reserved_branch_id = 0U;
01373     union {
01375       struct {
01388         ActorLink* active;
01390         ActorLink queue[PropCost::AC_MAX+1];
01392         unsigned int branch_id;
01394         unsigned int n_sub;
01395       } p;
01397       struct {
01399         VarImpBase* vars_u[AllVarConf::idx_c];
01401         VarImpBase* vars_noidx;
01403         SharedHandle::Object* shared;
01405         LocalObject* local;
01406       } c;
01407     } pc;
01409     void enqueue(Propagator* p);
01414 #ifdef GECODE_HAS_VAR_DISPOSE
01415 
01416     GECODE_KERNEL_EXPORT static VarImpDisposerBase* vd[AllVarConf::idx_d];
01418     VarImpBase* _vars_d[AllVarConf::idx_d];
01420     template<class VIC> VarImpBase* vars_d(void) const;
01422     template<class VIC> void vars_d(VarImpBase* x);
01423 #endif
01424 
01425     void update(ActorLink** sub);
01427 
01429     Actor** d_fst;
01431     Actor** d_cur;
01433     Actor** d_lst;
01434 
01446     unsigned int _wmp_afc;
01448     void afc_enable(void);
01450     bool afc_enabled(void) const;
01452     void wmp(unsigned int n);
01454     unsigned int wmp(void) const;
01455 
01457     GECODE_KERNEL_EXPORT static StatusStatistics unused_status;
01459     GECODE_KERNEL_EXPORT static CloneStatistics unused_clone;
01461     GECODE_KERNEL_EXPORT static CommitStatistics unused_commit;
01462 
01481     GECODE_KERNEL_EXPORT Space* _clone(bool share=true);
01482 
01515     GECODE_KERNEL_EXPORT
01516     void _commit(const Choice& c, unsigned int a);
01517 
01548     GECODE_KERNEL_EXPORT
01549     void _trycommit(const Choice& c, unsigned int a);
01550 
01551   public:
01556     GECODE_KERNEL_EXPORT Space(void);
01561     GECODE_KERNEL_EXPORT virtual ~Space(void);
01572     GECODE_KERNEL_EXPORT Space(bool share, Space& s);
01579     virtual Space* copy(bool share) = 0;
01590     GECODE_KERNEL_EXPORT virtual void constrain(const Space& best);
01604     GECODE_KERNEL_EXPORT 
01605     virtual void master(unsigned long int i, const Space* s,
01606                         NoGoods& ng);
01619     GECODE_KERNEL_EXPORT 
01620     virtual void slave(unsigned long int i, const Space* s);
01625     static void* operator new(size_t);
01630     static void  operator delete(void*);
01631 
01632 
01633     /*
01634      * Member functions for search engines
01635      *
01636      */
01637 
01649     GECODE_KERNEL_EXPORT
01650     SpaceStatus status(StatusStatistics& stat=unused_status);
01651 
01683     GECODE_KERNEL_EXPORT
01684     const Choice* choice(void);
01685 
01695     GECODE_KERNEL_EXPORT
01696     const Choice* choice(Archive& e) const;
01697   
01718     Space* clone(bool share=true, CloneStatistics& stat=unused_clone) const;
01719 
01754     void commit(const Choice& c, unsigned int a,
01755                 CommitStatistics& stat=unused_commit);
01788     void trycommit(const Choice& c, unsigned int a,
01789                    CommitStatistics& stat=unused_commit);
01808     GECODE_KERNEL_EXPORT
01809     NGL* ngl(const Choice& c, unsigned int a);
01810 
01825     GECODE_KERNEL_EXPORT
01826     void print(const Choice& c, unsigned int a, std::ostream& o) const;
01827 
01836     GECODE_KERNEL_EXPORT
01837     void notice(Actor& a, ActorProperty p, bool duplicate=false);
01845     GECODE_KERNEL_EXPORT
01846     void ignore(Actor& a, ActorProperty p, bool duplicate=false);
01847 
01848 
01859     ExecStatus ES_SUBSUMED(Propagator& p);
01874     ExecStatus ES_SUBSUMED_DISPOSED(Propagator& p, size_t s);
01885     ExecStatus ES_FIX_PARTIAL(Propagator& p, const ModEventDelta& med);
01896     ExecStatus ES_NOFIX_PARTIAL(Propagator& p, const ModEventDelta& med);
01897     
01908     template<class A>
01909     ExecStatus ES_FIX_DISPOSE(Council<A>& c, A& a);
01920     template<class A>
01921     ExecStatus ES_NOFIX_DISPOSE(Council<A>& c, A& a);
01933     template<class A>
01934     ExecStatus ES_NOFIX_DISPOSE_FORCE(Council<A>& c, A& a);
01935     
01943     void fail(void);
01952     bool failed(void) const;
01957     bool stable(void) const;
01964     GECODE_KERNEL_EXPORT unsigned int propagators(void) const;
01971     GECODE_KERNEL_EXPORT unsigned int branchers(void) const;
01972 
01974 
01975 
01976     Home operator ()(Propagator& p);
01978 
01990     template<class T>
01991     T* alloc(long unsigned int n);
01998     template<class T>
01999     T* alloc(long int n);
02006     template<class T>
02007     T* alloc(unsigned int n);
02014     template<class T>
02015     T* alloc(int n);
02025     template<class T>
02026     void free(T* b, long unsigned int n);
02036     template<class T>
02037     void free(T* b, long int n);
02047     template<class T>
02048     void free(T* b, unsigned int n);
02058     template<class T>
02059     void free(T* b, int n);
02071     template<class T>
02072     T* realloc(T* b, long unsigned int n, long unsigned int m);
02084     template<class T>
02085     T* realloc(T* b, long int n, long int m);
02097     template<class T>
02098     T* realloc(T* b, unsigned int n, unsigned int m);
02110     template<class T>
02111     T* realloc(T* b, int n, int m);
02119     template<class T>
02120     T** realloc(T** b, long unsigned int n, long unsigned int m);
02128     template<class T>
02129     T** realloc(T** b, long int n, long int m);
02137     template<class T>
02138     T** realloc(T** b, unsigned int n, unsigned int m);
02146     template<class T>
02147     T** realloc(T** b, int n, int m);
02149     void* ralloc(size_t s);
02151     void rfree(void* p, size_t s);
02153     void* rrealloc(void* b, size_t n, size_t m);
02155     template<size_t> void* fl_alloc(void);
02161     template<size_t> void  fl_dispose(FreeList* f, FreeList* l);
02170     GECODE_KERNEL_EXPORT void flush(void);
02172 
02173 
02174 
02177     template<class T> 
02178     T& construct(void);
02184     template<class T, typename A1> 
02185     T& construct(A1 const& a1);
02191     template<class T, typename A1, typename A2> 
02192     T& construct(A1 const& a1, A2 const& a2);
02198     template<class T, typename A1, typename A2, typename A3>
02199     T& construct(A1 const& a1, A2 const& a2, A3 const& a3);
02205     template<class T, typename A1, typename A2, typename A3, typename A4>
02206     T& construct(A1 const& a1, A2 const& a2, A3 const& a3, A4 const& a4);
02212     template<class T, typename A1, typename A2, typename A3, typename A4, typename A5>
02213     T& construct(A1 const& a1, A2 const& a2, A3 const& a3, A4 const& a4, A5 const& a5);
02215 
02221     class Propagators {
02222     private:
02224       const Space& home;
02226       const ActorLink* q;
02228       const ActorLink* c;
02230       const ActorLink* e;
02231     public:
02233       Propagators(const Space& home);
02235       bool operator ()(void) const;
02237       void operator ++(void);
02239       const Propagator& propagator(void) const;
02240     };
02241 
02247     class Branchers {
02248     private:
02250       const ActorLink* c;
02252       const ActorLink* e;
02253     public:
02255       Branchers(const Space& home);
02257       bool operator ()(void) const;
02259       void operator ++(void);
02261       const Brancher& brancher(void) const;
02262     };    
02263 
02265 
02266 
02267     GECODE_KERNEL_EXPORT
02268     void afc_decay(double d);
02270     double afc_decay(void) const;
02272     GECODE_KERNEL_EXPORT
02273     void afc_set(double a);
02275   };
02276 
02277 
02278 
02279 
02280   /*
02281    * Memory management
02282    *
02283    */
02284 
02285   // Heap allocated
02286   forceinline void*
02287   SharedHandle::Object::operator new(size_t s) {
02288     return heap.ralloc(s);
02289   }
02290   forceinline void
02291   SharedHandle::Object::operator delete(void* p) {
02292     heap.rfree(p);
02293   }
02294 
02295   forceinline void*
02296   Space::operator new(size_t s) {
02297     return heap.ralloc(s);
02298   }
02299   forceinline void
02300   Space::operator delete(void* p) {
02301     heap.rfree(p);
02302   }
02303 
02304   forceinline void
02305   Choice::operator delete(void* p) {
02306     heap.rfree(p);
02307   }
02308   forceinline void*
02309   Choice::operator new(size_t s) {
02310     return heap.ralloc(s);
02311   }
02312 
02313 
02314   // Space allocation: general space heaps and free lists
02315   forceinline void*
02316   Space::ralloc(size_t s) {
02317     return mm.alloc(sm,s);
02318   }
02319   forceinline void
02320   Space::rfree(void* p, size_t s) {
02321     return mm.reuse(p,s);
02322   }
02323   forceinline void*
02324   Space::rrealloc(void* _b, size_t n, size_t m) {
02325     char* b = static_cast<char*>(_b);
02326     if (n < m) {
02327       char* p = static_cast<char*>(ralloc(m));
02328       memcpy(p,b,n);
02329       rfree(b,n);
02330       return p;
02331     } else {
02332       rfree(b+m,m-n);
02333       return b;
02334     }
02335   }
02336 
02337   template<size_t s>
02338   forceinline void*
02339   Space::fl_alloc(void) {
02340     return mm.template fl_alloc<s>(sm);
02341   }
02342   template<size_t s>
02343   forceinline void
02344   Space::fl_dispose(FreeList* f, FreeList* l) {
02345     mm.template fl_dispose<s>(f,l);
02346   }
02347 
02348   /*
02349    * Typed allocation routines
02350    *
02351    */
02352   template<class T>
02353   forceinline T*
02354   Space::alloc(long unsigned int n) {
02355     T* p = static_cast<T*>(ralloc(sizeof(T)*n));
02356     for (long unsigned int i=n; i--; )
02357       (void) new (p+i) T();
02358     return p;
02359   }
02360   template<class T>
02361   forceinline T*
02362   Space::alloc(long int n) {
02363     assert(n >= 0);
02364     return alloc<T>(static_cast<long unsigned int>(n));
02365   }
02366   template<class T>
02367   forceinline T*
02368   Space::alloc(unsigned int n) {
02369     return alloc<T>(static_cast<long unsigned int>(n));
02370   }
02371   template<class T>
02372   forceinline T*
02373   Space::alloc(int n) {
02374     assert(n >= 0);
02375     return alloc<T>(static_cast<long unsigned int>(n));
02376   }
02377 
02378   template<class T>
02379   forceinline void
02380   Space::free(T* b, long unsigned int n) {
02381     for (long unsigned int i=n; i--; )
02382       b[i].~T();
02383     rfree(b,n*sizeof(T));
02384   }
02385   template<class T>
02386   forceinline void
02387   Space::free(T* b, long int n) {
02388     assert(n >= 0);
02389     free<T>(b,static_cast<long unsigned int>(n));
02390   }
02391   template<class T>
02392   forceinline void
02393   Space::free(T* b, unsigned int n) {
02394     free<T>(b,static_cast<long unsigned int>(n));
02395   }
02396   template<class T>
02397   forceinline void
02398   Space::free(T* b, int n) {
02399     assert(n >= 0);
02400     free<T>(b,static_cast<long unsigned int>(n));
02401   }
02402 
02403   template<class T>
02404   forceinline T*
02405   Space::realloc(T* b, long unsigned int n, long unsigned int m) {
02406     if (n < m) {
02407       T* p = static_cast<T*>(ralloc(sizeof(T)*m));
02408       for (long unsigned int i=n; i--; )
02409         (void) new (p+i) T(b[i]);
02410       for (long unsigned int i=n; i<m; i++)
02411         (void) new (p+i) T();
02412       free<T>(b,n);
02413       return p;
02414     } else {
02415       free<T>(b+m,m-n);
02416       return b;
02417     }
02418   }
02419   template<class T>
02420   forceinline T*
02421   Space::realloc(T* b, long int n, long int m) {
02422     assert((n >= 0) && (m >= 0));
02423     return realloc<T>(b,static_cast<long unsigned int>(n),
02424                       static_cast<long unsigned int>(m));
02425   }
02426   template<class T>
02427   forceinline T*
02428   Space::realloc(T* b, unsigned int n, unsigned int m) {
02429     return realloc<T>(b,static_cast<long unsigned int>(n),
02430                       static_cast<long unsigned int>(m));
02431   }
02432   template<class T>
02433   forceinline T*
02434   Space::realloc(T* b, int n, int m) {
02435     assert((n >= 0) && (m >= 0));
02436     return realloc<T>(b,static_cast<long unsigned int>(n),
02437                       static_cast<long unsigned int>(m));
02438   }
02439 
02440 #define GECODE_KERNEL_REALLOC(T)                                        \
02441   template<>                                                            \
02442   forceinline T*                                                        \
02443   Space::realloc<T>(T* b, long unsigned int n, long unsigned int m) {   \
02444     return static_cast<T*>(rrealloc(b,n*sizeof(T),m*sizeof(T)));        \
02445   }                                                                     \
02446   template<>                                                            \
02447   forceinline T*                                                        \
02448   Space::realloc<T>(T* b, long int n, long int m) {                     \
02449     assert((n >= 0) && (m >= 0));                                       \
02450     return realloc<T>(b,static_cast<long unsigned int>(n),              \
02451                       static_cast<long unsigned int>(m));               \
02452   }                                                                     \
02453   template<>                                                            \
02454   forceinline T*                                                        \
02455   Space::realloc<T>(T* b, unsigned int n, unsigned int m) {             \
02456     return realloc<T>(b,static_cast<long unsigned int>(n),              \
02457                       static_cast<long unsigned int>(m));               \
02458   }                                                                     \
02459   template<>                                                            \
02460   forceinline T*                                                        \
02461   Space::realloc<T>(T* b, int n, int m) {                               \
02462     assert((n >= 0) && (m >= 0));                                       \
02463     return realloc<T>(b,static_cast<long unsigned int>(n),              \
02464                       static_cast<long unsigned int>(m));               \
02465   }
02466 
02467   GECODE_KERNEL_REALLOC(bool)
02468   GECODE_KERNEL_REALLOC(signed char)
02469   GECODE_KERNEL_REALLOC(unsigned char)
02470   GECODE_KERNEL_REALLOC(signed short int)
02471   GECODE_KERNEL_REALLOC(unsigned short int)
02472   GECODE_KERNEL_REALLOC(signed int)
02473   GECODE_KERNEL_REALLOC(unsigned int)
02474   GECODE_KERNEL_REALLOC(signed long int)
02475   GECODE_KERNEL_REALLOC(unsigned long int)
02476   GECODE_KERNEL_REALLOC(float)
02477   GECODE_KERNEL_REALLOC(double)
02478 
02479 #undef GECODE_KERNEL_REALLOC
02480 
02481   template<class T>
02482   forceinline T**
02483   Space::realloc(T** b, long unsigned int n, long unsigned int m) {
02484     return static_cast<T**>(rrealloc(b,n*sizeof(T),m*sizeof(T*)));
02485   }
02486   template<class T>
02487   forceinline T**
02488   Space::realloc(T** b, long int n, long int m) {
02489     assert((n >= 0) && (m >= 0));
02490     return realloc<T*>(b,static_cast<long unsigned int>(n),
02491                        static_cast<long unsigned int>(m));
02492   }
02493   template<class T>
02494   forceinline T**
02495   Space::realloc(T** b, unsigned int n, unsigned int m) {
02496     return realloc<T*>(b,static_cast<long unsigned int>(n),
02497                        static_cast<long unsigned int>(m));
02498   }
02499   template<class T>
02500   forceinline T**
02501   Space::realloc(T** b, int n, int m) {
02502     assert((n >= 0) && (m >= 0));
02503     return realloc<T*>(b,static_cast<long unsigned int>(n),
02504                        static_cast<long unsigned int>(m));
02505   }
02506 
02507 
02508 #ifdef GECODE_HAS_VAR_DISPOSE
02509   template<class VIC>
02510   forceinline VarImpBase*
02511   Space::vars_d(void) const {
02512     return _vars_d[VIC::idx_d];
02513   }
02514   template<class VIC>
02515   forceinline void
02516   Space::vars_d(VarImpBase* x) {
02517     _vars_d[VIC::idx_d] = x;
02518   }
02519 #endif
02520 
02521   // Space allocated entities: Actors, variable implementations, and advisors
02522   forceinline void
02523   Actor::operator delete(void*) {}
02524   forceinline void
02525   Actor::operator delete(void*, Space&) {}
02526   forceinline void*
02527   Actor::operator new(size_t s, Space& home) {
02528     return home.ralloc(s);
02529   }
02530 
02531   template<class VIC>
02532   forceinline void
02533   VarImp<VIC>::operator delete(void*) {}
02534   template<class VIC>
02535   forceinline void
02536   VarImp<VIC>::operator delete(void*, Space&) {}
02537   template<class VIC>
02538   forceinline void*
02539   VarImp<VIC>::operator new(size_t s, Space& home) {
02540     return home.ralloc(s);
02541   }
02542 
02543 #ifndef __GNUC__
02544   forceinline void
02545   Advisor::operator delete(void*) {}
02546 #endif
02547   forceinline void
02548   Advisor::operator delete(void*, Space&) {}
02549   forceinline void*
02550   Advisor::operator new(size_t s, Space& home) {
02551     return home.ralloc(s);
02552   }
02553 
02554   forceinline void
02555   NGL::operator delete(void*) {}
02556   forceinline void
02557   NGL::operator delete(void*, Space&) {}
02558   forceinline void*
02559   NGL::operator new(size_t s, Space& home) {
02560     return home.ralloc(s);
02561   }
02562 
02563   /*
02564    * Shared objects and handles
02565    *
02566    */
02567   forceinline
02568   SharedHandle::Object::Object(void)
02569     : next(NULL), fwd(NULL), use_cnt(0) {}
02570   forceinline
02571   SharedHandle::Object::~Object(void) {
02572     assert(use_cnt == 0);
02573   }
02574 
02575   forceinline SharedHandle::Object*
02576   SharedHandle::object(void) const {
02577     return o;
02578   }
02579   forceinline void
02580   SharedHandle::subscribe(void) {
02581     if (o != NULL) o->use_cnt++;
02582   }
02583   forceinline void
02584   SharedHandle::cancel(void) {
02585     if ((o != NULL) && (--o->use_cnt == 0))
02586       delete o;
02587     o=NULL;
02588   }
02589   forceinline void
02590   SharedHandle::object(SharedHandle::Object* n) {
02591     if (n != o) {
02592       cancel(); o=n; subscribe();
02593     }
02594   }
02595   forceinline
02596   SharedHandle::SharedHandle(void) : o(NULL) {}
02597   forceinline
02598   SharedHandle::SharedHandle(SharedHandle::Object* so) : o(so) {
02599     subscribe();
02600   }
02601   forceinline
02602   SharedHandle::SharedHandle(const SharedHandle& sh) : o(sh.o) {
02603     subscribe();
02604   }
02605   forceinline SharedHandle&
02606   SharedHandle::operator =(const SharedHandle& sh) {
02607     if (&sh != this) {
02608       cancel(); o=sh.o; subscribe();
02609     }
02610     return *this;
02611   }
02612   forceinline void
02613   SharedHandle::update(Space& home, bool share, SharedHandle& sh) {
02614     if (sh.o == NULL) {
02615       o=NULL; return;
02616     } else if (share) {
02617       o=sh.o;
02618     } else if (sh.o->fwd != NULL) {
02619       o=sh.o->fwd;
02620     } else {
02621       o = sh.o->copy();
02622       sh.o->fwd = o;
02623       sh.o->next = home.pc.c.shared;
02624       home.pc.c.shared = sh.o;
02625     }
02626     subscribe();
02627   }
02628   forceinline
02629   SharedHandle::~SharedHandle(void) {
02630     cancel();
02631   }
02632 
02633 
02634 
02635   /*
02636    * No-goods
02637    *
02638    */
02639   forceinline
02640   NoGoods::NoGoods(void) 
02641     : n(0) {}
02642   forceinline unsigned long int
02643   NoGoods::ng(void) const {
02644     return n;
02645   }
02646   forceinline void
02647   NoGoods::ng(unsigned long int n0) {
02648     n=n0;
02649   }
02650   forceinline
02651   NoGoods::~NoGoods(void) {}
02652 
02653 
02654   /*
02655    * ActorLink
02656    *
02657    */
02658   forceinline ActorLink*
02659   ActorLink::prev(void) const {
02660     return _prev;
02661   }
02662 
02663   forceinline ActorLink*
02664   ActorLink::next(void) const {
02665     return _next;
02666   }
02667 
02668   forceinline ActorLink**
02669   ActorLink::next_ref(void) {
02670     return &_next;
02671   }
02672 
02673   forceinline void
02674   ActorLink::prev(ActorLink* al) {
02675     _prev = al;
02676   }
02677 
02678   forceinline void
02679   ActorLink::next(ActorLink* al) {
02680     _next = al;
02681   }
02682 
02683   forceinline void
02684   ActorLink::unlink(void) {
02685     ActorLink* p = _prev; ActorLink* n = _next;
02686     p->_next = n; n->_prev = p;
02687   }
02688 
02689   forceinline void
02690   ActorLink::init(void) {
02691     _next = this; _prev =this;
02692   }
02693 
02694   forceinline void
02695   ActorLink::head(ActorLink* a) {
02696     // Inserts al at head of link-chain (that is, after this)
02697     ActorLink* n = _next;
02698     this->_next = a; a->_prev = this;
02699     a->_next = n; n->_prev = a;
02700   }
02701 
02702   forceinline void
02703   ActorLink::tail(ActorLink* a) {
02704     // Inserts al at tail of link-chain (that is, before this)
02705     ActorLink* p = _prev;
02706     a->_next = this; this->_prev = a;
02707     p->_next = a; a->_prev = p;
02708   }
02709 
02710   forceinline bool
02711   ActorLink::empty(void) const {
02712     return _next == this;
02713   }
02714 
02715   template<class T>
02716   forceinline ActorLink*
02717   ActorLink::cast(T* a) {
02718     // Turning al into a reference is for gcc, assume is for MSVC
02719     GECODE_NOT_NULL(a);
02720     ActorLink& t = *a;
02721     return static_cast<ActorLink*>(&t);
02722   }
02723 
02724   template<class T>
02725   forceinline const ActorLink*
02726   ActorLink::cast(const T* a) {
02727     // Turning al into a reference is for gcc, assume is for MSVC
02728     GECODE_NOT_NULL(a);
02729     const ActorLink& t = *a;
02730     return static_cast<const ActorLink*>(&t);
02731   }
02732 
02733 
02734   /*
02735    * Actor
02736    *
02737    */
02738   forceinline Actor*
02739   Actor::cast(ActorLink* al) {
02740     // Turning al into a reference is for gcc, assume is for MSVC
02741     GECODE_NOT_NULL(al);
02742     ActorLink& t = *al;
02743     return static_cast<Actor*>(&t);
02744   }
02745 
02746   forceinline const Actor*
02747   Actor::cast(const ActorLink* al) {
02748     // Turning al into a reference is for gcc, assume is for MSVC
02749     GECODE_NOT_NULL(al);
02750     const ActorLink& t = *al;
02751     return static_cast<const Actor*>(&t);
02752   }
02753 
02754   forceinline void
02755   Space::afc_enable(void) {
02756     _wmp_afc |= 1U;
02757   }
02758   forceinline bool
02759   Space::afc_enabled(void) const {
02760     return (_wmp_afc & 1U) != 0U;
02761   }
02762   forceinline void
02763   Space::wmp(unsigned int n) {
02764     _wmp_afc = (_wmp_afc & 1U) | (n << 1);
02765   }
02766   forceinline unsigned int
02767   Space::wmp(void) const {
02768     return _wmp_afc >> 1U;
02769   }
02770 
02771   forceinline void
02772   Home::notice(Actor& a, ActorProperty p, bool duplicate) {
02773     s.notice(a,p,duplicate);
02774   }
02775 
02776   forceinline Space*
02777   Space::clone(bool share, CloneStatistics&) const {
02778     // Clone is only const for search engines. During cloning, several data
02779     // structures are updated (e.g. forwarding pointers), so we have to
02780     // cast away the constness.
02781     return const_cast<Space*>(this)->_clone(share);
02782   }
02783 
02784   forceinline void
02785   Space::commit(const Choice& c, unsigned int a, CommitStatistics&) {
02786     _commit(c,a);
02787   }
02788 
02789   forceinline void
02790   Space::trycommit(const Choice& c, unsigned int a, CommitStatistics&) {
02791     _trycommit(c,a);
02792   }
02793 
02794   forceinline double
02795   Space::afc_decay(void) const {
02796     return gafc.decay();
02797   }
02798 
02799   forceinline size_t
02800   Actor::dispose(Space&) {
02801     return sizeof(*this);
02802   }
02803 
02804 
02805   /*
02806    * Home for posting actors
02807    *
02808    */
02809   forceinline
02810   Home::Home(Space& s0, Propagator* p0) : s(s0), p(p0) {}
02811   forceinline Home&
02812   Home::operator =(const Home& h) {
02813     s=h.s; p=h.p;
02814     return *this;
02815   }
02816   forceinline
02817   Home::operator Space&(void) { 
02818     return s; 
02819   }
02820   forceinline Home
02821   Home::operator ()(Propagator& p) {
02822     return Home(s,&p);
02823   }
02824   forceinline Home
02825   Space::operator ()(Propagator& p) {
02826     return Home(*this,&p);
02827   }
02828   forceinline Propagator*
02829   Home::propagator(void) const {
02830     return p;
02831   }
02832 
02833   /*
02834    * Propagator
02835    *
02836    */
02837   forceinline Propagator*
02838   Propagator::cast(ActorLink* al) {
02839     // Turning al into a reference is for gcc, assume is for MSVC
02840     GECODE_NOT_NULL(al);
02841     ActorLink& t = *al;
02842     return static_cast<Propagator*>(&t);
02843   }
02844 
02845   forceinline const Propagator*
02846   Propagator::cast(const ActorLink* al) {
02847     // Turning al into a reference is for gcc, assume is for MSVC
02848     GECODE_NOT_NULL(al);
02849     const ActorLink& t = *al;
02850     return static_cast<const Propagator*>(&t);
02851   }
02852 
02853   forceinline Propagator*
02854   Propagator::fwd(void) const {
02855     return static_cast<Propagator*>(prev());
02856   }
02857 
02858   forceinline
02859   Propagator::Propagator(Home home) 
02860     : gafc((home.propagator() != NULL) ?
02861            // Inherit time counter information
02862            home.propagator()->gafc :
02863            // New propagator information
02864            static_cast<Space&>(home).gafc.allocate()) {
02865     u.advisors = NULL;
02866     assert((u.med == 0) && (u.size == 0));
02867     static_cast<Space&>(home).pl.head(this);
02868   }
02869 
02870   forceinline
02871   Propagator::Propagator(Space&, bool, Propagator& p) 
02872     : gafc(p.gafc) {
02873     u.advisors = NULL;
02874     assert((u.med == 0) && (u.size == 0));
02875     // Set forwarding pointer
02876     p.prev(this);
02877   }
02878 
02879   forceinline ModEventDelta
02880   Propagator::modeventdelta(void) const {
02881     return u.med;
02882   }
02883 
02884   forceinline double
02885   Propagator::afc(const Space& home) const {
02886     return const_cast<Space&>(home).gafc.afc(gafc);
02887   }
02888 
02889   forceinline ExecStatus
02890   Space::ES_SUBSUMED_DISPOSED(Propagator& p, size_t s) {
02891     p.u.size = s;
02892     return __ES_SUBSUMED;
02893   }
02894 
02895   forceinline ExecStatus
02896   Space::ES_SUBSUMED(Propagator& p) {
02897     p.u.size = p.dispose(*this);
02898     return __ES_SUBSUMED;
02899   }
02900 
02901   forceinline ExecStatus
02902   Space::ES_FIX_PARTIAL(Propagator& p, const ModEventDelta& med) {
02903     p.u.med = med;
02904     assert(p.u.med != 0);
02905     return __ES_PARTIAL;
02906   }
02907 
02908   forceinline ExecStatus
02909   Space::ES_NOFIX_PARTIAL(Propagator& p, const ModEventDelta& med) {
02910     p.u.med = AllVarConf::med_combine(p.u.med,med);
02911     assert(p.u.med != 0);
02912     return __ES_PARTIAL;
02913   }
02914 
02915 
02916 
02917   /*
02918    * Brancher
02919    *
02920    */
02921   forceinline Brancher*
02922   Brancher::cast(ActorLink* al) {
02923     // Turning al into a reference is for gcc, assume is for MSVC
02924     GECODE_NOT_NULL(al);
02925     ActorLink& t = *al;
02926     return static_cast<Brancher*>(&t);
02927   }
02928 
02929   forceinline const Brancher*
02930   Brancher::cast(const ActorLink* al) {
02931     // Turning al into a reference is for gcc, assume is for MSVC
02932     GECODE_NOT_NULL(al);
02933     const ActorLink& t = *al;
02934     return static_cast<const Brancher*>(&t);
02935   }
02936 
02937   forceinline
02938   Brancher::Brancher(Home home) :
02939     _id(static_cast<Space&>(home).pc.p.branch_id++) {
02940     if (static_cast<Space&>(home).pc.p.branch_id == 0U)
02941       throw TooManyBranchers("Brancher::Brancher");
02942     // If no brancher available, make it the first one
02943     if (static_cast<Space&>(home).b_status == &static_cast<Space&>(home).bl) {
02944       static_cast<Space&>(home).b_status = this;
02945       if (static_cast<Space&>(home).b_commit == &static_cast<Space&>(home).bl)
02946         static_cast<Space&>(home).b_commit = this;
02947     }
02948     static_cast<Space&>(home).bl.tail(this);
02949   }
02950 
02951   forceinline
02952   Brancher::Brancher(Space&, bool, Brancher& b)
02953     : _id(b._id) {
02954     // Set forwarding pointer
02955     b.prev(this);
02956   }
02957 
02958   forceinline unsigned int
02959   Brancher::id(void) const {
02960     return _id;
02961   }
02962 
02963   forceinline Brancher*
02964   Space::brancher(unsigned int id) {
02965     /*
02966      * Due to weakly monotonic propagators the following scenario might
02967      * occur: a brancher has been committed with all its available
02968      * choices. Then, propagation determines less information
02969      * than before and the brancher now will create new choices.
02970      * Later, during recomputation, all of these choices
02971      * can be used together, possibly interleaved with 
02972      * choices for other branchers. That means all branchers
02973      * must be scanned to find the matching brancher for the choice.
02974      *
02975      * b_commit tries to optimize scanning as it is most likely that
02976      * recomputation does not generate new choices during recomputation
02977      * and hence b_commit is moved from newer to older branchers.
02978      */
02979     Brancher* b_old = b_commit;
02980     // Try whether we are lucky
02981     while (b_commit != Brancher::cast(&bl))
02982       if (id != b_commit->id())
02983         b_commit = Brancher::cast(b_commit->next());
02984       else
02985         return b_commit;
02986     if (b_commit == Brancher::cast(&bl)) {
02987       // We did not find the brancher, start at the beginning
02988       b_commit = Brancher::cast(bl.next());
02989       while (b_commit != b_old)
02990         if (id != b_commit->id())
02991           b_commit = Brancher::cast(b_commit->next());
02992         else
02993           return b_commit;
02994     }
02995     return NULL;
02996   }
02997   
02998   /*
02999    * Brancher handle
03000    *
03001    */
03002   forceinline
03003   BrancherHandle::BrancherHandle(void)
03004     : _id(Space::reserved_branch_id) {}
03005   forceinline
03006   BrancherHandle::BrancherHandle(const Brancher& b)
03007     : _id(b.id()) {}
03008   forceinline void
03009   BrancherHandle::update(Space&, bool, BrancherHandle& bh) {
03010     _id = bh._id;
03011   }
03012   forceinline unsigned int
03013   BrancherHandle::id(void) const {
03014     return _id;
03015   }
03016   forceinline bool
03017   BrancherHandle::operator ()(const Space& home) const {
03018     return const_cast<Space&>(home).brancher(_id) != NULL;
03019   }
03020   forceinline void
03021   BrancherHandle::kill(Space& home) {
03022     home.kill_brancher(_id);
03023   }
03024 
03025   
03026   /*
03027    * Local objects
03028    *
03029    */
03030 
03031   forceinline LocalObject*
03032   LocalObject::cast(ActorLink* al) {
03033     // Turning al into a reference is for gcc, assume is for MSVC
03034     GECODE_NOT_NULL(al);
03035     ActorLink& t = *al;
03036     return static_cast<LocalObject*>(&t);
03037   }
03038 
03039   forceinline const LocalObject*
03040   LocalObject::cast(const ActorLink* al) {
03041     // Turning al into a reference is for gcc, assume is for MSVC
03042     GECODE_NOT_NULL(al);
03043     const ActorLink& t = *al;
03044     return static_cast<const LocalObject*>(&t);
03045   }
03046 
03047   forceinline
03048   LocalObject::LocalObject(Home) {
03049     ActorLink::cast(this)->prev(NULL);
03050   }
03051 
03052   forceinline
03053   LocalObject::LocalObject(Space&,bool,LocalObject&) {
03054     ActorLink::cast(this)->prev(NULL);
03055   }
03056 
03057   forceinline LocalObject*
03058   LocalObject::fwd(Space& home, bool share) {
03059     if (prev() == NULL)
03060       fwdcopy(home,share);
03061     return LocalObject::cast(prev());
03062   }
03063 
03064   forceinline
03065   LocalHandle::LocalHandle(void) : o(NULL) {}
03066   forceinline
03067   LocalHandle::LocalHandle(LocalObject* lo) : o(lo) {}
03068   forceinline
03069   LocalHandle::LocalHandle(const LocalHandle& lh) : o(lh.o) {}
03070   forceinline LocalHandle&
03071   LocalHandle::operator =(const LocalHandle& lh) {
03072     o = lh.o;
03073     return *this;
03074   }
03075   forceinline
03076   LocalHandle::~LocalHandle(void) {}
03077   forceinline LocalObject*
03078   LocalHandle::object(void) const { return o; }
03079   forceinline void
03080   LocalHandle::object(LocalObject* n) { o = n; }
03081   forceinline void
03082   LocalHandle::update(Space& home, bool share, LocalHandle& lh) {
03083     object(lh.object()->fwd(home,share));
03084   }
03085 
03086 
03087   /*
03088    * Choices
03089    *
03090    */
03091   forceinline
03092   Choice::Choice(const Brancher& b, const unsigned int a)
03093     : _id(b.id()), _alt(a) {}
03094 
03095   forceinline unsigned int
03096   Choice::alternatives(void) const {
03097     return _alt;
03098   }
03099 
03100   forceinline unsigned int
03101   Choice::id(void) const {
03102     return _id;
03103   }
03104 
03105   forceinline
03106   Choice::~Choice(void) {}
03107 
03108 
03109 
03110   /*
03111    * No-good literal
03112    *
03113    */
03114   forceinline bool
03115   NGL::leaf(void) const {
03116     return Support::marked(nl);
03117   }
03118   forceinline NGL*
03119   NGL::next(void) const {
03120     return static_cast<NGL*>(Support::funmark(nl));
03121   }
03122   forceinline void
03123   NGL::leaf(bool l) {
03124     nl = l ? Support::fmark(nl) : Support::funmark(nl);
03125   }
03126   forceinline void
03127   NGL::next(NGL* n) {
03128     nl = Support::marked(nl) ? Support::mark(n) : n;
03129   }
03130   forceinline NGL*
03131   NGL::add(NGL* n, bool l) {
03132     nl = Support::marked(nl) ? Support::mark(n) : n;
03133     n->leaf(l);
03134     return n;
03135   }
03136 
03137   forceinline
03138   NGL::NGL(void) 
03139     : nl(NULL) {}
03140   forceinline
03141   NGL::NGL(Space&) 
03142     : nl(NULL) {}
03143   forceinline
03144   NGL::NGL(Space&, bool, NGL&) 
03145     : nl(NULL) {}
03146   forceinline size_t
03147   NGL::dispose(Space&) {
03148     return sizeof(*this);
03149   }
03150 
03151   /*
03152    * Advisor
03153    *
03154    */
03155   template<class A>
03156   forceinline
03157   Advisor::Advisor(Space&, Propagator& p, Council<A>& c) {
03158     // Store propagator and forwarding in prev()
03159     ActorLink::prev(&p);
03160     // Link to next advisor in next()
03161     ActorLink::next(c.advisors); c.advisors = static_cast<A*>(this);
03162   }
03163 
03164   forceinline
03165   Advisor::Advisor(Space&, bool, Advisor&) {}
03166 
03167   forceinline bool
03168   Advisor::disposed(void) const {
03169     return prev() == NULL;
03170   }
03171 
03172   forceinline Advisor*
03173   Advisor::cast(ActorLink* al) {
03174     return static_cast<Advisor*>(al);
03175   }
03176 
03177   forceinline const Advisor*
03178   Advisor::cast(const ActorLink* al) {
03179     return static_cast<const Advisor*>(al);
03180   }
03181 
03182   forceinline Propagator&
03183   Advisor::propagator(void) const {
03184     assert(!disposed());
03185     return *Propagator::cast(ActorLink::prev());
03186   }
03187 
03188   template<class A>
03189   forceinline void
03190   Advisor::dispose(Space&,Council<A>&) {
03191     assert(!disposed());
03192     ActorLink::prev(NULL);
03193     // Shorten chains of disposed advisors by one, if possible
03194     Advisor* n = Advisor::cast(next());
03195     if ((n != NULL) && n->disposed())
03196       next(n->next());
03197   }
03198 
03199   template<class A>
03200   forceinline ExecStatus
03201   Space::ES_FIX_DISPOSE(Council<A>& c, A& a) {
03202     a.dispose(*this,c);
03203     return ES_FIX;
03204   }
03205 
03206   template<class A>
03207   forceinline ExecStatus
03208   Space::ES_NOFIX_DISPOSE(Council<A>& c, A& a) {
03209     a.dispose(*this,c);
03210     return ES_NOFIX;
03211   }
03212 
03213   template<class A>
03214   forceinline ExecStatus
03215   Space::ES_NOFIX_DISPOSE_FORCE(Council<A>& c, A& a) {
03216     a.dispose(*this,c);
03217     return ES_NOFIX_FORCE;
03218   }
03219 
03220 
03221 
03222   /*
03223    * Advisor council
03224    *
03225    */
03226   template<class A>
03227   forceinline
03228   Council<A>::Council(void) {}
03229 
03230   template<class A>
03231   forceinline
03232   Council<A>::Council(Space&)
03233     : advisors(NULL) {}
03234 
03235   template<class A>
03236   forceinline bool
03237   Council<A>::empty(void) const {
03238     ActorLink* a = advisors;
03239     while ((a != NULL) && static_cast<A*>(a)->disposed())
03240       a = a->next();
03241     advisors = a;
03242     return a == NULL;
03243   }
03244 
03245   template<class A>
03246   forceinline void
03247   Council<A>::update(Space& home, bool share, Council<A>& c) {
03248     // Skip all disposed advisors
03249     {
03250       ActorLink* a = c.advisors;
03251       while ((a != NULL) && static_cast<A*>(a)->disposed())
03252         a = a->next();
03253       c.advisors = a;
03254     }
03255     // Are there any advisors to be cloned?
03256     if (c.advisors != NULL) {
03257       // The propagator in from-space
03258       Propagator* p_f = &static_cast<A*>(c.advisors)->propagator();
03259       // The propagator in to-space
03260       Propagator* p_t = Propagator::cast(p_f->prev());
03261       // Advisors in from-space
03262       ActorLink** a_f = &c.advisors;
03263       // Advisors in to-space
03264       A* a_t = NULL;
03265       while (*a_f != NULL) {
03266         if (static_cast<A*>(*a_f)->disposed()) {
03267           *a_f = (*a_f)->next();
03268         } else {
03269           // Run specific copying part
03270           A* a = new (home) A(home,share,*static_cast<A*>(*a_f));
03271           // Set propagator pointer
03272           a->prev(p_t);
03273           // Set forwarding pointer
03274           (*a_f)->prev(a);
03275           // Link
03276           a->next(a_t);
03277           a_t = a;
03278           a_f = (*a_f)->next_ref();
03279         }
03280       }
03281       advisors = a_t;
03282       // Enter advisor link for reset
03283       assert(p_f->u.advisors == NULL);
03284       p_f->u.advisors = c.advisors;
03285     } else {
03286       advisors = NULL;
03287     }
03288   }
03289 
03290   template<class A>
03291   forceinline void
03292   Council<A>::dispose(Space& home) {
03293     ActorLink* a = advisors;
03294     while (a != NULL) {
03295       if (!static_cast<A*>(a)->disposed())
03296         static_cast<A*>(a)->dispose(home,*this);
03297       a = a->next();
03298     }
03299   }
03300 
03301 
03302 
03303   /*
03304    * Advisor iterator
03305    *
03306    */
03307   template<class A>
03308   forceinline
03309   Advisors<A>::Advisors(const Council<A>& c)
03310     : a(c.advisors) {
03311     while ((a != NULL) && static_cast<A*>(a)->disposed())
03312       a = a->next();
03313   }
03314 
03315   template<class A>
03316   forceinline bool
03317   Advisors<A>::operator ()(void) const {
03318     return a != NULL;
03319   }
03320 
03321   template<class A>
03322   forceinline void
03323   Advisors<A>::operator ++(void) {
03324     do {
03325       a = a->next();
03326     } while ((a != NULL) && static_cast<A*>(a)->disposed());
03327   }
03328 
03329   template<class A>
03330   forceinline A&
03331   Advisors<A>::advisor(void) const {
03332     return *static_cast<A*>(a);
03333   }
03334 
03335 
03336 
03337   /*
03338    * Space
03339    *
03340    */
03341   forceinline void
03342   Space::enqueue(Propagator* p) {
03343     ActorLink::cast(p)->unlink();
03344     ActorLink* c = &pc.p.queue[p->cost(*this,p->u.med).ac];
03345     c->tail(ActorLink::cast(p));
03346     if (c > pc.p.active)
03347       pc.p.active = c;
03348   }
03349 
03350   forceinline void
03351   Space::fail(void) {
03352     /*
03353      * Now active points beyond the last queue. This is essential as
03354      * enqueuing a propagator in a failed space keeps the space
03355      * failed.
03356      */
03357     pc.p.active = &pc.p.queue[PropCost::AC_MAX+1]+1;
03358   }
03359   forceinline void
03360   Home::fail(void) {
03361     s.fail();
03362   }
03363 
03364   forceinline bool
03365   Space::failed(void) const {
03366     return pc.p.active > &pc.p.queue[PropCost::AC_MAX+1];
03367   }
03368   forceinline bool
03369   Home::failed(void) const {
03370     return s.failed();
03371   }
03372 
03373   forceinline bool
03374   Space::stable(void) const {
03375     return ((pc.p.active < &pc.p.queue[0]) ||
03376             (pc.p.active > &pc.p.queue[PropCost::AC_MAX+1]));
03377   }
03378 
03379 
03380 
03381   /*
03382    * Variable implementation
03383    *
03384    */
03385   template<class VIC>
03386   forceinline ActorLink**
03387   VarImp<VIC>::actor(PropCond pc) {
03388     assert((pc >= 0)  && (pc < pc_max+2));
03389     return (pc == 0) ? b.base : b.base+u.idx[pc-1];
03390   }
03391 
03392   template<class VIC>
03393   forceinline ActorLink**
03394   VarImp<VIC>::actorNonZero(PropCond pc) {
03395     assert((pc > 0)  && (pc < pc_max+2));
03396     return b.base+u.idx[pc-1];
03397   }
03398 
03399   template<class VIC>
03400   forceinline unsigned int&
03401   VarImp<VIC>::idx(PropCond pc) {
03402     assert((pc > 0)  && (pc < pc_max+2));
03403     return u.idx[pc-1];
03404   }
03405 
03406   template<class VIC>
03407   forceinline unsigned int
03408   VarImp<VIC>::idx(PropCond pc) const {
03409     assert((pc > 0)  && (pc < pc_max+2));
03410     return u.idx[pc-1];
03411   }
03412 
03413   template<class VIC>
03414   forceinline
03415   VarImp<VIC>::VarImp(Space&) {
03416     b.base = NULL; entries = 0;
03417     for (PropCond pc=1; pc<pc_max+2; pc++)
03418       idx(pc) = 0;
03419     free_and_bits = 0;
03420   }
03421 
03422   template<class VIC>
03423   forceinline
03424   VarImp<VIC>::VarImp(void) {
03425     b.base = NULL; entries = 0;
03426     for (PropCond pc=1; pc<pc_max+2; pc++)
03427       idx(pc) = 0;
03428     free_and_bits = 0;
03429   }
03430 
03431   template<class VIC>
03432   forceinline unsigned int
03433   VarImp<VIC>::degree(void) const {
03434     assert(!copied());
03435     return entries;
03436   }
03437 
03438   template<class VIC>
03439   forceinline double
03440   VarImp<VIC>::afc(const Space& home) const {
03441     double d = 0.0;
03442     // Count the afc of each propagator
03443     {
03444       ActorLink** a = const_cast<VarImp<VIC>*>(this)->actor(0);
03445       ActorLink** e = const_cast<VarImp<VIC>*>(this)->actorNonZero(pc_max+1);
03446       while (a < e) {
03447         d += Propagator::cast(*a)->afc(home); a++;
03448       }
03449     }
03450     // Count the afc of each advisor's propagator
03451     {
03452       ActorLink** a = const_cast<VarImp<VIC>*>(this)->actorNonZero(pc_max+1);
03453       ActorLink** e = const_cast<VarImp<VIC>*>(this)->b.base+entries;
03454       while (a < e) {
03455         d += Advisor::cast(*a)->propagator().afc(home); a++;
03456       }
03457     }
03458     return d;
03459   }
03460 
03461   template<class VIC>
03462   forceinline ModEvent
03463   VarImp<VIC>::modevent(const Delta& d) {
03464     return d.me;
03465   }
03466 
03467   template<class VIC>
03468   forceinline unsigned int
03469   VarImp<VIC>::bits(void) const {
03470     return free_and_bits;
03471   }
03472 
03473   template<class VIC>
03474   forceinline unsigned int&
03475   VarImp<VIC>::bits(void) {
03476     return free_and_bits;
03477   }
03478 
03479 #ifdef GECODE_HAS_VAR_DISPOSE
03480   template<class VIC>
03481   forceinline VarImp<VIC>*
03482   VarImp<VIC>::vars_d(Space& home) {
03483     return static_cast<VarImp<VIC>*>(home.vars_d<VIC>());
03484   }
03485 
03486   template<class VIC>
03487   forceinline void
03488   VarImp<VIC>::vars_d(Space& home, VarImp<VIC>* x) {
03489     home.vars_d<VIC>(x);
03490   }
03491 #endif
03492 
03493   template<class VIC>
03494   forceinline bool
03495   VarImp<VIC>::copied(void) const {
03496     return Support::marked(b.fwd);
03497   }
03498 
03499   template<class VIC>
03500   forceinline VarImp<VIC>*
03501   VarImp<VIC>::forward(void) const {
03502     assert(copied());
03503     return static_cast<VarImp<VIC>*>(Support::unmark(b.fwd));
03504   }
03505 
03506   template<class VIC>
03507   forceinline VarImp<VIC>*
03508   VarImp<VIC>::next(void) const {
03509     assert(copied());
03510     return u.next;
03511   }
03512 
03513   template<class VIC>
03514   forceinline
03515   VarImp<VIC>::VarImp(Space& home, bool, VarImp<VIC>& x) {
03516     VarImpBase** reg;
03517     free_and_bits = x.free_and_bits & ((1 << free_bits) - 1);
03518     if (x.b.base == NULL) {
03519       // Variable implementation needs no index structure
03520       reg = &home.pc.c.vars_noidx;
03521       assert(x.degree() == 0);
03522     } else {
03523       reg = &home.pc.c.vars_u[idx_c];
03524     }
03525     // Save subscriptions in copy
03526     b.base = x.b.base;
03527     entries = x.entries;
03528     for (PropCond pc=1; pc<pc_max+2; pc++)
03529       idx(pc) = x.idx(pc);
03530 
03531     // Set forwarding pointer
03532     x.b.fwd = static_cast<VarImp<VIC>*>(Support::mark(this));
03533     // Register original
03534     x.u.next = static_cast<VarImp<VIC>*>(*reg); *reg = &x;
03535   }
03536 
03537   template<class VIC>
03538   forceinline ModEvent
03539   VarImp<VIC>::me(const ModEventDelta& med) {
03540     return static_cast<ModEvent>((med & VIC::med_mask) >> VIC::med_fst);
03541   }
03542 
03543   template<class VIC>
03544   forceinline ModEventDelta
03545   VarImp<VIC>::med(ModEvent me) {
03546     return static_cast<ModEventDelta>(me << VIC::med_fst);
03547   }
03548 
03549   template<class VIC>
03550   forceinline ModEvent
03551   VarImp<VIC>::me_combine(ModEvent me1, ModEvent me2) {
03552     return VIC::me_combine(me1,me2);
03553   }
03554 
03555   template<class VIC>
03556   forceinline void
03557   VarImp<VIC>::schedule(Space& home, Propagator& p, ModEvent me,
03558                         bool force) {
03559     if (VIC::med_update(p.u.med,me) || force)
03560       home.enqueue(&p);
03561   }
03562 
03563   template<class VIC>
03564   forceinline void
03565   VarImp<VIC>::schedule(Space& home, PropCond pc1, PropCond pc2, ModEvent me) {
03566     ActorLink** b = actor(pc1);
03567     ActorLink** p = actorNonZero(pc2+1);
03568     while (p-- > b)
03569       schedule(home,*Propagator::cast(*p),me);
03570   }
03571 
03572   template<class VIC>
03573   forceinline void
03574   VarImp<VIC>::enter(Space& home, Propagator* p, PropCond pc) {
03575     assert(pc <= pc_max);
03576     // Count one new subscription
03577     home.pc.p.n_sub += 1;
03578     if ((free_and_bits >> free_bits) == 0)
03579       resize(home);
03580     free_and_bits -= 1 << free_bits;
03581 
03582     // Enter subscription
03583     b.base[entries] = *actorNonZero(pc_max+1);
03584     entries++;
03585     for (PropCond j = pc_max; j > pc; j--) {
03586       *actorNonZero(j+1) = *actorNonZero(j);
03587       idx(j+1)++;
03588     }
03589     *actorNonZero(pc+1) = *actor(pc);
03590     idx(pc+1)++;
03591     *actor(pc) = ActorLink::cast(p);
03592 
03593 #ifdef GECODE_AUDIT
03594     ActorLink** f = actor(pc);
03595     while (f < (pc == pc_max+1 ? b.base+entries : actorNonZero(pc+1)))
03596       if (*f == p)
03597         goto found;
03598       else
03599         f++;
03600     GECODE_NEVER;
03601     found: ;
03602 #endif
03603   }
03604 
03605   template<class VIC>
03606   forceinline void
03607   VarImp<VIC>::enter(Space& home, Advisor* a) {
03608     // Count one new subscription
03609     home.pc.p.n_sub += 1;
03610     if ((free_and_bits >> free_bits) == 0)
03611       resize(home);
03612     free_and_bits -= 1 << free_bits;
03613 
03614     // Enter subscription
03615     b.base[entries++] = *actorNonZero(pc_max+1);
03616     *actorNonZero(pc_max+1) = a;
03617   }
03618 
03619   template<class VIC>
03620   void
03621   VarImp<VIC>::resize(Space& home) {
03622     if (b.base == NULL) {
03623       assert((free_and_bits >> free_bits) == 0);
03624       // Create fresh dependency array with four entries
03625       free_and_bits += 4 << free_bits;
03626       b.base = home.alloc<ActorLink*>(4);
03627       for (int i=0; i<pc_max+1; i++)
03628         u.idx[i] = 0;
03629     } else {
03630       // Resize dependency array
03631       unsigned int n = degree();
03632       // Find out whether the area is most likely in the special area
03633       // reserved for subscriptions. If yes, just resize mildly otherwise
03634       // more agressively
03635       ActorLink** s = static_cast<ActorLink**>(home.mm.subscriptions());
03636       unsigned int m =
03637         ((s <= b.base) && (b.base < s+home.pc.p.n_sub)) ?
03638         (n+4) : ((n+1)*3>>1);
03639       ActorLink** prop = home.alloc<ActorLink*>(m);
03640       free_and_bits += (m-n) << free_bits;
03641       // Copy entries
03642       Heap::copy<ActorLink*>(prop, b.base, n);
03643       home.free<ActorLink*>(b.base,n);
03644       b.base = prop;
03645     }
03646   }
03647 
03648   template<class VIC>
03649   void
03650   VarImp<VIC>::subscribe(Space& home, Propagator& p, PropCond pc,
03651                          bool assigned, ModEvent me, bool schedule) {
03652     if (assigned) {
03653       // Do not subscribe, just schedule the propagator
03654       if (schedule)
03655         VarImp<VIC>::schedule(home,p,ME_GEN_ASSIGNED);
03656     } else {
03657       enter(home,&p,pc);
03658       // Schedule propagator
03659       if (schedule && (pc != PC_GEN_ASSIGNED))
03660         VarImp<VIC>::schedule(home,p,me);
03661     }
03662   }
03663 
03664   template<class VIC>
03665   forceinline void
03666   VarImp<VIC>::subscribe(Space& home, Advisor& a, bool assigned) {
03667     if (!assigned)
03668       enter(home,&a);
03669   }
03670 
03671   template<class VIC>
03672   forceinline void
03673   VarImp<VIC>::remove(Space& home, Propagator* p, PropCond pc) {
03674     assert(pc <= pc_max);
03675     ActorLink* a = ActorLink::cast(p);
03676     // Find actor in dependency array
03677     ActorLink** f = actor(pc);
03678 #ifdef GECODE_AUDIT
03679     while (f < actorNonZero(pc+1))
03680       if (*f == a)
03681         goto found;
03682       else
03683         f++;
03684     GECODE_NEVER;
03685   found: ;
03686 #else
03687     while (*f != a) f++;
03688 #endif
03689     // Remove actor
03690     *f = *(actorNonZero(pc+1)-1);
03691     for (PropCond j = pc+1; j< pc_max+1; j++) {
03692       *(actorNonZero(j)-1) = *(actorNonZero(j+1)-1);
03693       idx(j)--;
03694     }
03695     *(actorNonZero(pc_max+1)-1) = b.base[entries-1];
03696     idx(pc_max+1)--;
03697     entries--;
03698     free_and_bits += 1 << free_bits;
03699     home.pc.p.n_sub -= 1;
03700   }
03701 
03702   template<class VIC>
03703   forceinline void
03704   VarImp<VIC>::remove(Space& home, Advisor* a) {
03705     // Find actor in dependency array
03706     ActorLink** f = actorNonZero(pc_max+1);
03707 #ifdef GECODE_AUDIT
03708     while (f < b.base+entries)
03709       if (*f == a)
03710         goto found;
03711       else
03712         f++;
03713     GECODE_NEVER;
03714   found: ;
03715 #else
03716     while (*f != a) f++;
03717 #endif
03718     // Remove actor
03719     *f = b.base[--entries];
03720     free_and_bits += 1 << free_bits;
03721     home.pc.p.n_sub -= 1;
03722   }
03723 
03724   template<class VIC>
03725   forceinline void
03726   VarImp<VIC>::cancel(Space& home, Propagator& p, PropCond pc, bool assigned) {
03727     if (!assigned)
03728       remove(home,&p,pc);
03729   }
03730 
03731   template<class VIC>
03732   forceinline void
03733   VarImp<VIC>::cancel(Space& home, Advisor& a, bool assigned) {
03734     if (!assigned)
03735       remove(home,&a);
03736   }
03737 
03738   template<class VIC>
03739   forceinline void
03740   VarImp<VIC>::cancel(Space& home) {
03741     unsigned int n_sub = degree();
03742     home.pc.p.n_sub -= n_sub;
03743     unsigned int n = (free_and_bits >> VIC::free_bits) + n_sub;
03744     home.free<ActorLink*>(b.base,n);
03745     // Must be NULL such that cloning works
03746     b.base = NULL;
03747     // Must be 0 such that degree works
03748     entries = 0;
03749   }
03750 
03751   template<class VIC>
03752   forceinline bool
03753   VarImp<VIC>::advise(Space& home, ModEvent me, Delta& d) {
03754     /*
03755      * An advisor that is executed might remove itself due to subsumption.
03756      * As entries are removed from front to back, the advisors must
03757      * be iterated in forward direction.
03758      */
03759     ActorLink** la = actorNonZero(pc_max+1);
03760     ActorLink** le = b.base+entries;
03761     if (la == le)
03762       return true;
03763     d.me = me;
03764     // An advisor that is run, might be removed during execution.
03765     // As removal is done from the back the advisors have to be executed
03766     // in inverse order.
03767     do {
03768       Advisor* a = Advisor::cast(*la);
03769       assert(!a->disposed());
03770       Propagator& p = a->propagator();
03771       switch (p.advise(home,*a,d)) {
03772       case ES_FIX:
03773         break;
03774       case ES_FAILED:
03775         if (home.afc_enabled())
03776           home.gafc.fail(p.gafc);
03777         return false;
03778       case ES_NOFIX:
03779         schedule(home,p,me);
03780         break;
03781       case ES_NOFIX_FORCE:
03782         schedule(home,p,me,true);
03783         break;
03784       default:
03785         GECODE_NEVER;
03786       }
03787     } while (++la < le);
03788     return true;
03789   }
03790 
03791   template<class VIC>
03792   forceinline void
03793   VarImp<VIC>::update(VarImp<VIC>* x, ActorLink**& sub) {
03794     // this refers to the variable to be updated (clone)
03795     // x refers to the original
03796     // Recover from copy
03797     x->b.base = b.base;
03798     x->u.idx[0] = u.idx[0];
03799     if (pc_max > 0 && sizeof(ActorLink**) > sizeof(unsigned int))
03800       x->u.idx[1] = u.idx[1];
03801 
03802     ActorLink** f = x->b.base;
03803     unsigned int n = x->degree();
03804     ActorLink** t = sub;
03805     sub += n;
03806     b.base = t;
03807     // Set subscriptions using actor forwarding pointers
03808     while (n >= 4) {
03809       n -= 4;
03810       t[0]=f[0]->prev(); t[1]=f[1]->prev();
03811       t[2]=f[2]->prev(); t[3]=f[3]->prev();
03812       t += 4; f += 4;
03813     }
03814     if (n >= 2) {
03815       n -= 2;
03816       t[0]=f[0]->prev(); t[1]=f[1]->prev();
03817       t += 2; f += 2;
03818     }
03819     if (n > 0) {
03820       t[0]=f[0]->prev();
03821     }
03822   }
03823 
03824   template<class VIC>
03825   forceinline void
03826   VarImp<VIC>::update(Space& home, ActorLink**& sub) {
03827     VarImp<VIC>* x = static_cast<VarImp<VIC>*>(home.pc.c.vars_u[idx_c]);
03828     while (x != NULL) {
03829       VarImp<VIC>* n = x->next(); x->forward()->update(x,sub); x = n;
03830     }
03831   }
03832 
03833 
03834 
03835   /*
03836    * Variable disposer
03837    *
03838    */
03839   template<class VarImp>
03840   VarImpDisposer<VarImp>::VarImpDisposer(void) {
03841 #ifdef GECODE_HAS_VAR_DISPOSE
03842     Space::vd[VarImp::idx_d] = this;
03843 #endif
03844   }
03845 
03846   template<class VarImp>
03847   void
03848   VarImpDisposer<VarImp>::dispose(Space& home, VarImpBase* _x) {
03849     VarImp* x = static_cast<VarImp*>(_x);
03850     do {
03851       x->dispose(home); x = static_cast<VarImp*>(x->next_d());
03852     } while (x != NULL);
03853   }
03854 
03855   /*
03856    * Statistics
03857    */
03858 
03859   forceinline void
03860   StatusStatistics::reset(void) {
03861     propagate = 0;
03862     wmp = false;
03863   }
03864   forceinline
03865   StatusStatistics::StatusStatistics(void) {
03866     reset();
03867   }
03868   forceinline StatusStatistics&
03869   StatusStatistics::operator +=(const StatusStatistics& s) { 
03870     propagate += s.propagate;
03871     wmp |= s.wmp;
03872     return *this;
03873   }
03874   forceinline StatusStatistics
03875   StatusStatistics::operator +(const StatusStatistics& s) {
03876     StatusStatistics t(s);
03877     return t += *this;
03878   }
03879 
03880   forceinline void
03881   CloneStatistics::reset(void) {}
03882 
03883   forceinline
03884   CloneStatistics::CloneStatistics(void) {
03885     reset();
03886   }
03887   forceinline CloneStatistics
03888   CloneStatistics::operator +(const CloneStatistics&) {
03889     CloneStatistics s;
03890     return s;
03891   }
03892   forceinline CloneStatistics&
03893   CloneStatistics::operator +=(const CloneStatistics&) { 
03894     return *this;
03895   }
03896 
03897   forceinline void
03898   CommitStatistics::reset(void) {}
03899 
03900   forceinline
03901   CommitStatistics::CommitStatistics(void) {
03902     reset();
03903   }
03904   forceinline CommitStatistics
03905   CommitStatistics::operator +(const CommitStatistics&) {
03906     CommitStatistics s;
03907     return s;
03908   }
03909   forceinline CommitStatistics&
03910   CommitStatistics::operator +=(const CommitStatistics&) { 
03911     return *this;
03912   }
03913 
03914   /*
03915    * Cost computation
03916    *
03917    */
03918 
03919   forceinline
03920   PropCost::PropCost(PropCost::ActualCost ac0) : ac(ac0) {}
03921 
03922   forceinline PropCost
03923   PropCost::cost(PropCost::Mod m,
03924                  PropCost::ActualCost lo, PropCost::ActualCost hi,
03925                  unsigned int n) {
03926     if (n < 2)
03927       return (m == LO) ? AC_UNARY_LO : AC_UNARY_HI;
03928     else if (n == 2)
03929       return (m == LO) ? AC_BINARY_LO : AC_BINARY_HI;
03930     else if (n == 3)
03931       return (m == LO) ? AC_TERNARY_LO : AC_TERNARY_HI;
03932     else
03933       return (m == LO) ? lo : hi;
03934   }
03935 
03936   forceinline PropCost
03937   PropCost::crazy(PropCost::Mod m, unsigned int n) {
03938     return cost(m,AC_CRAZY_LO,AC_CRAZY_HI,n);
03939   }
03940   forceinline PropCost
03941   PropCost::crazy(PropCost::Mod m, int n) {
03942     assert(n >= 0);
03943     return crazy(m,static_cast<unsigned int>(n));
03944   }
03945   forceinline PropCost
03946   PropCost::cubic(PropCost::Mod m, unsigned int n) {
03947     return cost(m,AC_CUBIC_LO,AC_CUBIC_HI,n);
03948   }
03949   forceinline PropCost
03950   PropCost::cubic(PropCost::Mod m, int n) {
03951     assert(n >= 0);
03952     return cubic(m,static_cast<unsigned int>(n));
03953   }
03954   forceinline PropCost
03955   PropCost::quadratic(PropCost::Mod m, unsigned int n) {
03956     return cost(m,AC_QUADRATIC_LO,AC_QUADRATIC_HI,n);
03957   }
03958   forceinline PropCost
03959   PropCost::quadratic(PropCost::Mod m, int n) {
03960     assert(n >= 0);
03961     return quadratic(m,static_cast<unsigned int>(n));
03962   }
03963   forceinline PropCost
03964   PropCost::linear(PropCost::Mod m, unsigned int n) {
03965     return cost(m,AC_LINEAR_LO,AC_LINEAR_HI,n);
03966   }
03967   forceinline PropCost
03968   PropCost::linear(PropCost::Mod m, int n) {
03969     assert(n >= 0);
03970     return linear(m,static_cast<unsigned int>(n));
03971   }
03972   forceinline PropCost
03973   PropCost::ternary(PropCost::Mod m) {
03974     return (m == LO) ? AC_TERNARY_LO : AC_TERNARY_HI;
03975   }
03976   forceinline PropCost
03977   PropCost::binary(PropCost::Mod m) {
03978     return (m == LO) ? AC_BINARY_LO : AC_BINARY_HI;
03979   }
03980   forceinline PropCost
03981   PropCost::unary(PropCost::Mod m) {
03982     return (m == LO) ? AC_UNARY_LO : AC_UNARY_HI;
03983   }
03984 
03985   /*
03986    * Iterators for propagators and branchers of a space
03987    *
03988    */
03989   forceinline
03990   Space::Propagators::Propagators(const Space& home0) 
03991     : home(home0), q(home.pc.p.active) {
03992     while (q >= &home.pc.p.queue[0]) {
03993       if (q->next() != q) {
03994         c = q->next(); e = q; q--;
03995         return;
03996       }
03997       q--;
03998     }
03999     q = NULL;
04000     if (!home.pl.empty()) {
04001       c = Propagator::cast(home.pl.next());
04002       e = Propagator::cast(&home.pl);
04003     } else {
04004       c = e = NULL;
04005     }
04006   }
04007   forceinline bool 
04008   Space::Propagators::operator ()(void) const {
04009     return c != NULL;
04010   }
04011   forceinline void 
04012   Space::Propagators::operator ++(void) {
04013     c = c->next();
04014     if (c == e) {
04015       if (q == NULL) {
04016         c = NULL;
04017       } else {
04018         while (q >= &home.pc.p.queue[0]) {
04019           if (q->next() != q) {
04020             c = q->next(); e = q; q--;
04021             return;
04022           }
04023           q--;
04024         }
04025         q = NULL;
04026         if (!home.pl.empty()) {
04027           c = Propagator::cast(home.pl.next());
04028           e = Propagator::cast(&home.pl);
04029         } else {
04030           c = NULL;
04031         }
04032       }
04033     }
04034   }
04035   forceinline const Propagator& 
04036   Space::Propagators::propagator(void) const {
04037     return *Propagator::cast(c);
04038   }
04039 
04040   forceinline
04041   Space::Branchers::Branchers(const Space& home) 
04042     : c(Brancher::cast(home.bl.next())), e(&home.bl) {}
04043   forceinline bool 
04044   Space::Branchers::operator ()(void) const {
04045     return c != e;
04046   }
04047   forceinline void 
04048   Space::Branchers::operator ++(void) {
04049     c = c->next();
04050   }
04051   forceinline const Brancher& 
04052   Space::Branchers::brancher(void) const {
04053     return *Brancher::cast(c);
04054   }
04055 
04056   /*
04057    * Space construction support
04058    *
04059    */
04060   template<class T> 
04061   forceinline T& 
04062   Space::construct(void) {
04063     return alloc<T>(1);
04064   }
04065   template<class T, typename A1> 
04066   forceinline T& 
04067   Space::construct(A1 const& a1) {
04068     T& t = *static_cast<T*>(ralloc(sizeof(T)));
04069     new (&t) T(a1);
04070     return t;
04071   }
04072   template<class T, typename A1, typename A2> 
04073   forceinline T& 
04074   Space::construct(A1 const& a1, A2 const& a2) {
04075     T& t = *static_cast<T*>(ralloc(sizeof(T)));
04076     new (&t) T(a1,a2);
04077     return t;
04078   }
04079   template<class T, typename A1, typename A2, typename A3>
04080   forceinline T& 
04081   Space::construct(A1 const& a1, A2 const& a2, A3 const& a3) {
04082     T& t = *static_cast<T*>(ralloc(sizeof(T)));
04083     new (&t) T(a1,a2,a3);
04084     return t;
04085   }
04086   template<class T, typename A1, typename A2, typename A3, typename A4>
04087   forceinline T& 
04088   Space::construct(A1 const& a1, A2 const& a2, A3 const& a3, A4 const& a4) {
04089     T& t = *static_cast<T*>(ralloc(sizeof(T)));
04090     new (&t) T(a1,a2,a3,a4);
04091     return t;
04092   }
04093   template<class T, typename A1, typename A2, typename A3, typename A4, typename A5>
04094   forceinline T& 
04095   Space::construct(A1 const& a1, A2 const& a2, A3 const& a3, A4 const& a4, A5 const& a5) {
04096     T& t = *static_cast<T*>(ralloc(sizeof(T)));
04097     new (&t) T(a1,a2,a3,a4,a5);
04098     return t;
04099   }
04100 
04101 }
04102 
04103 // STATISTICS: kernel-core