Generated on Mon Nov 30 23:53:32 2009 for Gecode by doxygen 1.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: 2009-11-03 17:47:56 +0100 (Tue, 03 Nov 2009) $ by $Author: schulte $
00022  *     $Revision: 10035 $
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 namespace Gecode {
00050 
00051   class Space;
00052 
00080   class CopiedHandle {
00081   public:
00089     class Object {
00090       friend class Space;
00091       friend class CopiedHandle;
00092     private:
00094       Object* next;
00096       Object* fwd;
00097     public:
00099       Object(void);
00101       virtual Object* copy(void) const = 0;
00103       virtual ~Object(void);
00105       static void* operator new(size_t, Space&);
00107       static void operator delete(void*, size_t);
00109       static void operator delete(void*, Space&);
00110     private:
00111       static void* operator new(size_t);
00112     };
00113   private:
00115     Object* o;
00116   public:
00118     CopiedHandle(void);
00120     CopiedHandle(Object* so);
00122     CopiedHandle(const CopiedHandle& sh);
00124     CopiedHandle& operator =(const CopiedHandle& sh);
00126     void update(Space& home, bool share, CopiedHandle& sh);
00128     void dispose(Space& home);
00129   protected:
00131     Object* object(void) const;
00133     void object(Object* n);
00134   };
00135 
00149   class SharedHandle : public CopiedHandle {
00150   public:
00158     class Object : public CopiedHandle::Object {
00159       friend class Space;
00160       friend class SharedHandle;
00161     private:
00163       unsigned int use_cnt;
00164     public:
00166       Object(void);
00168       virtual ~Object(void);
00170       static void* operator new(size_t s);
00172       static void  operator delete(void* p);
00173     };
00174   private:
00176     void subscribe(void);
00178     void cancel(void);
00179   public:
00181     SharedHandle(void);
00183     SharedHandle(SharedHandle::Object* so);
00185     SharedHandle(const SharedHandle& sh);
00187     SharedHandle& operator =(const SharedHandle& sh);
00189     void update(Space& home, bool share, SharedHandle& sh);
00191     ~SharedHandle(void);
00192   protected:
00194     Object* object(void) const;
00196     void object(SharedHandle::Object* n);
00197   };
00198 
00199 
00208 
00209   typedef int ModEvent;
00210 
00212   const ModEvent ME_GEN_FAILED   = -1;
00214   const ModEvent ME_GEN_NONE     =  0;
00216   const ModEvent ME_GEN_ASSIGNED =  1;
00217 
00219   typedef int PropCond;
00221   const PropCond PC_GEN_NONE     = -1;
00223   const PropCond PC_GEN_ASSIGNED = 0;
00225 
00236   typedef int ModEventDelta;
00237 
00238 }
00239 
00240 #include <gecode/kernel/var-type.hpp>
00241 
00242 namespace Gecode {
00243 
00245   class NoIdxVarImpConf {
00246   public:
00248     static const int idx_c = -1;
00250     static const int idx_d = -1;
00252     static const PropCond pc_max = PC_GEN_ASSIGNED;
00254     static const int free_bits = 0;
00256     static const int med_fst = 0;
00258     static const int med_lst = 0;
00260     static const int med_mask = 0;
00262     static Gecode::ModEvent me_combine(ModEvent me1, ModEvent me2);
00264     static bool med_update(ModEventDelta& med, ModEvent me);
00265   };
00266 
00267   forceinline ModEvent
00268   NoIdxVarImpConf::me_combine(ModEvent, ModEvent) {
00269     GECODE_NEVER; return 0;
00270   }
00271   forceinline bool
00272   NoIdxVarImpConf::med_update(ModEventDelta&, ModEvent) {
00273     GECODE_NEVER; return false;
00274   }
00275 
00276 
00277   /*
00278    * These are the classes of interest
00279    *
00280    */
00281   class ActorLink;
00282   class Actor;
00283   class Propagator;
00284   class Advisor;
00285   template<class A> class Council;
00286   template<class A> class Advisors;
00287   template<class VIC> class VarImp;
00288 
00289 
00290   /*
00291    * Variable implementations
00292    *
00293    */
00294 
00302   class VarImpBase {};
00303 
00310   class GECODE_VTABLE_EXPORT VarDisposerBase {
00311   public:
00313     GECODE_KERNEL_EXPORT virtual void dispose(Space& home, VarImpBase* x);
00315     GECODE_KERNEL_EXPORT virtual ~VarDisposerBase(void);
00316   };
00317 
00324   template<class VarType>
00325   class VarDisposer : public VarDisposerBase {
00326   public:
00328     VarDisposer(void);
00330     virtual void dispose(Space& home, VarImpBase* x);
00331   };
00332 
00334   class Delta {
00335     template<class VIC> friend class VarImp;
00336   private:
00338     ModEvent me;
00339   public:
00341     ModEvent modevent(void) const;
00342   };
00343 
00351   template<class VIC>
00352   class VarImp : public VarImpBase {
00353     friend class Space;
00354     friend class Propagator;
00355     template<class VarType> friend class VarDisposer;
00356   private:
00368     ActorLink** base;
00369 
00371     static const int idx_c = VIC::idx_c;
00373     static const int idx_d = VIC::idx_d;
00375     static const int free_bits = VIC::free_bits;
00377     unsigned int entries;
00379     unsigned int free_and_bits;
00381     static const Gecode::PropCond pc_max = VIC::pc_max;
00382 
00383     union {
00394       unsigned int idx[pc_max+1];
00396       VarImp<VIC>* next;
00397     } u;
00398 
00400     ActorLink** actor(PropCond pc);
00402     ActorLink** actorNonZero(PropCond pc);
00404     unsigned int& idx(PropCond pc);
00406     unsigned int idx(PropCond pc) const;
00407 
00414     void update(VarImp* x, ActorLink**& sub);
00421     static void update(Space& home, ActorLink**& sub);
00422 
00424     void enter(Space& home, Propagator* p, PropCond pc);
00426     void enter(Space& home, Advisor* a);
00428     void resize(Space& home);
00430     void remove(Space& home, Propagator* p, PropCond pc);
00432     void remove(Space& home, Advisor* a);
00433 
00434   protected:
00435 #ifdef GECODE_HAS_VAR_DISPOSE
00437     static VarImp<VIC>* vars_d(Space& home);
00439     static void vars_d(Space& home, VarImp<VIC>* x);
00440 #endif
00441 
00442   public:
00444     VarImp(Space& home);
00446     VarImp(void);
00447 
00449 
00450 
00462     void subscribe(Space& home, Propagator& p, PropCond pc,
00463                    bool assigned, ModEvent me, bool schedule);
00469     void cancel(Space& home, Propagator& p, PropCond pc,
00470                 bool assigned);
00476     void subscribe(Space& home, Advisor& a, bool assigned);
00482     void cancel(Space& home, Advisor& a, bool assigned);
00484     void cancel(Space& home);
00491     unsigned int degree(void) const;
00498     double afc(void) const;
00504     bool advise(Space& home, ModEvent me, Delta& d);
00506 
00508 
00509 
00510     VarImp(Space& home, bool share, VarImp& x);
00512     bool copied(void) const;
00514     VarImp* forward(void) const;
00516     VarImp* next(void) const;
00518 
00520 
00521 
00522     static void schedule(Space& home, Propagator& p, ModEvent me);
00524     static ModEvent me(const ModEventDelta& med);
00526     static ModEventDelta med(ModEvent me);
00528     static ModEvent me_combine(ModEvent me1, ModEvent me2);
00530 
00532     unsigned int bits(void) const;
00534     unsigned int& bits(void);
00535 
00536   protected:
00538     void schedule(Space& home, PropCond pc1, PropCond pc2, ModEvent me);
00539 
00540   public:
00542 
00543 
00544     static void* operator new(size_t,Space&);
00546     static void  operator delete(void*,Space&);
00548     static void  operator delete(void*);
00550   };
00551 
00560   enum ExecStatus {
00561     __ES_SUBSUMED       = -2, 
00562     ES_FAILED           = -1, 
00563     ES_NOFIX            =  0, 
00564     ES_OK               =  0, 
00565     ES_FIX              =  1, 
00566     __ES_PARTIAL        =  2  
00567   };
00568 
00573   class PropCost {
00574     friend class Space;
00575   public:
00577     enum ActualCost {
00578       AC_CRAZY_LO     = 0, 
00579       AC_CRAZY_HI     = 0, 
00580       AC_CUBIC_LO     = 1, 
00581       AC_CUBIC_HI     = 1, 
00582       AC_QUADRATIC_LO = 2, 
00583       AC_QUADRATIC_HI = 2, 
00584       AC_LINEAR_HI    = 3, 
00585       AC_LINEAR_LO    = 4, 
00586       AC_TERNARY_HI   = 4, 
00587       AC_BINARY_HI    = 5, 
00588       AC_TERNARY_LO   = 5, 
00589       AC_BINARY_LO    = 6, 
00590       AC_UNARY_LO     = 6, 
00591       AC_UNARY_HI     = 6, 
00592       AC_MAX          = 6  
00593     };
00595     ActualCost ac;
00596   public:
00598     enum Mod {
00599       LO, 
00600       HI  
00601     };
00602   private:
00604     static PropCost cost(Mod m, ActualCost lo, ActualCost hi, unsigned int n);
00606     PropCost(ActualCost ac);
00607   public:
00609     static PropCost crazy(PropCost::Mod m, unsigned int n);
00611     static PropCost crazy(PropCost::Mod m, int n);
00613     static PropCost cubic(PropCost::Mod m, unsigned int n);
00615     static PropCost cubic(PropCost::Mod m, int n);
00617     static PropCost quadratic(PropCost::Mod m, unsigned int n);
00619     static PropCost quadratic(PropCost::Mod m, int n);
00621     static PropCost linear(PropCost::Mod m, unsigned int n);
00623     static PropCost linear(PropCost::Mod m, int n);
00625     static PropCost ternary(PropCost::Mod m);
00627     static PropCost binary(PropCost::Mod m);
00629     static PropCost unary(PropCost::Mod m);
00630   };
00631 
00632 
00637   enum ActorProperty {
00646     AP_DISPOSE = (1 << 0),
00652     AP_WEAKLY  = (1 << 1)
00653   };
00654 
00655 
00663   class ActorLink {
00664     friend class Actor;
00665     friend class Propagator;
00666     friend class Advisor;
00667     friend class Brancher;
00668     friend class Space;
00669     template<class VIC> friend class VarImp;
00670   private:
00671     ActorLink* _next; ActorLink* _prev;
00672   public:
00674 
00675     ActorLink* prev(void) const; void prev(ActorLink*);
00676     ActorLink* next(void) const; void next(ActorLink*);
00677     ActorLink** next_ref(void);
00679 
00681     void init(void);
00683     void unlink(void);
00685     void head(ActorLink* al);
00687     void tail(ActorLink* al);
00689     bool empty(void) const;
00691     template<class T> static ActorLink* cast(T* a);
00693     template<class T> static const ActorLink* cast(const T* a);
00694   };
00695 
00696 
00701   class GECODE_VTABLE_EXPORT Actor : private ActorLink {
00702     friend class ActorLink;
00703     friend class Space;
00704     friend class Propagator;
00705     friend class Advisor;
00706     friend class Brancher;
00707     template<class VIC> friend class VarImp;
00708     template<class A> friend class Council;
00709   private:
00711     static Actor* cast(ActorLink* al);
00713     static const Actor* cast(const ActorLink* al);
00714   public:
00716     virtual Actor* copy(Space& home, bool share) = 0;
00717 
00719 
00720 
00721     GECODE_KERNEL_EXPORT
00722     virtual size_t allocated(void) const;
00724     GECODE_KERNEL_EXPORT
00725     virtual size_t dispose(Space& home);
00727     static void* operator new(size_t s, Space& home);
00729     static void  operator delete(void* p, Space& home);
00730   private:
00731 #ifndef __GNUC__
00733     static void  operator delete(void* p);
00734 #endif
00736     static void* operator new(size_t s);
00737 
00738 #ifdef __GNUC__
00739   public:
00741     GECODE_KERNEL_EXPORT virtual ~Actor(void);
00743     static void  operator delete(void* p);
00744 #endif
00745   };
00746 
00747 
00767   ExecStatus ES_SUBSUMED(Propagator& p, size_t s);
00778   ExecStatus ES_SUBSUMED(Propagator& p, Space& home);
00789   ExecStatus ES_FIX_PARTIAL(Propagator& p, const ModEventDelta& med);
00800   ExecStatus ES_NOFIX_PARTIAL(Propagator& p, const ModEventDelta& med);
00801 
00805   class Home {
00806   protected:
00808     Space& s;
00810     Propagator* p;
00811   public:
00813 
00814 
00815     Home(Space& s, Propagator* p=NULL);
00817     operator Space&(void);
00819 
00820 
00821 
00822     Home operator ()(Propagator& p);
00824     Propagator* propagator(void) const;
00826 
00827 
00828 
00829     bool failed(void) const;
00831     void fail(void);
00833     void notice(Actor& a, ActorProperty p);
00835   };
00836 
00841   class GECODE_VTABLE_EXPORT Propagator : public Actor {
00842     friend class ActorLink;
00843     friend class Space;
00844     template<class VIC> friend class VarImp;
00845     friend ExecStatus ES_SUBSUMED(Propagator&, size_t);
00846     friend ExecStatus ES_SUBSUMED(Propagator&, Space&);
00847     friend ExecStatus ES_FIX_PARTIAL(Propagator&, const ModEventDelta&);
00848     friend ExecStatus ES_NOFIX_PARTIAL(Propagator&, const ModEventDelta&);
00849     friend class Advisor;
00850     template<class A> friend class Council;
00851   private:
00852     union {
00854       ModEventDelta med;
00856       size_t size;
00858       Gecode::ActorLink* advisors;
00859     } u;
00861     PropInfo& pi;
00863     static Propagator* cast(ActorLink* al);
00865     static const Propagator* cast(const ActorLink* al);
00866   protected:
00868     Propagator(Home home);
00870     Propagator(Space& home, bool share, Propagator& p);
00871 
00872   public:
00874 
00875 
00898     virtual ExecStatus propagate(Space& home, const ModEventDelta& med) = 0;
00900     virtual PropCost cost(const Space& home, const ModEventDelta& med) const = 0;
00930     GECODE_KERNEL_EXPORT
00931     virtual ExecStatus advise(Space& home, Advisor& a, const Delta& d);
00933 
00934 
00935 
00936     double afc(void) const;
00938   };
00939 
00940 
00948   template<class A>
00949   class Council {
00950     friend class Advisor;
00951     friend class Advisors<A>;
00952   private:
00954     mutable ActorLink* advisors;
00955   public:
00957     Council(void);
00959     Council(Space& home);
00961     bool empty(void) const;
00963     void update(Space& home, bool share, Council<A>& c);
00965     void dispose(Space& home);
00966   };
00967 
00968 
00973   template<class A>
00974   class Advisors {
00975   private:
00977     ActorLink* a;
00978   public:
00980     Advisors(const Council<A>& c);
00982     bool operator ()(void) const;
00984     void operator ++(void);
00986     A& advisor(void) const;
00987   };
00988 
00989 
01001   template<class A>
01002   ExecStatus ES_SUBSUMED_FIX(A& a, Space& home, Council<A>& c);
01014   template<class A>
01015   ExecStatus ES_SUBSUMED_NOFIX(A& a, Space& home, Council<A>& c);
01016 
01027   class Advisor : private ActorLink {
01028     template<class VIC> friend class VarImp;
01029     template<class A> friend class Council;
01030     template<class A> friend class Advisors;
01031   private:
01033     bool disposed(void) const;
01035     static Advisor* cast(ActorLink* al);
01037     static const Advisor* cast(const ActorLink* al);
01038   protected:
01040     Propagator& propagator(void) const;
01041   public:
01043     template<class A>
01044     Advisor(Space& home, Propagator& p, Council<A>& c);
01046     Advisor(Space& home, bool share, Advisor& a);
01047 
01049 
01050 
01051     template<class A>
01052     void dispose(Space& home, Council<A>& c);
01054     static void* operator new(size_t s, Space& home);
01056     static void  operator delete(void* p, Space& home);
01058   private:
01059 #ifndef __GNUC__
01061     static void  operator delete(void* p);
01062 #endif
01064     static void* operator new(size_t s);
01065   };
01066 
01067 
01068   class Brancher;
01069 
01079   class Choice {
01080     friend class Space;
01081   private:
01082     unsigned int _id;  
01083     unsigned int _alt; 
01084 
01086     unsigned int id(void) const;
01087   protected:
01089     Choice(const Brancher& b, const unsigned int a);
01090   public:
01092     unsigned int alternatives(void) const;
01094     GECODE_KERNEL_EXPORT virtual ~Choice(void);
01096     virtual size_t size(void) const = 0;
01098     static void* operator new(size_t);
01100     static void  operator delete(void*);
01101   };
01102 
01112   class GECODE_VTABLE_EXPORT Brancher : public Actor {
01113     friend class ActorLink;
01114     friend class Space;
01115     friend class Choice;
01116   private:
01118     unsigned int _id;
01120     static Brancher* cast(ActorLink* al);
01122     static const Brancher* cast(const ActorLink* al);
01123   protected:
01125     Brancher(Home home);
01127     Brancher(Space& home, bool share, Brancher& b);
01128   public:
01130 
01131 
01139     virtual bool status(const Space& home) const = 0;
01147     virtual const Choice* choice(Space& home) = 0;
01154     virtual ExecStatus commit(Space& home, const Choice& c, 
01155                               unsigned int a) = 0;
01157     unsigned int id(void) const;
01159   };
01160 
01161 
01162 
01167   enum SpaceStatus {
01168     SS_FAILED, 
01169     SS_SOLVED, 
01170     SS_BRANCH  
01171   };
01172 
01177   class StatusStatistics {
01178   public:
01180     unsigned long int propagate;
01182     bool wmp;
01184     StatusStatistics(void);
01186     void reset(void);
01188     StatusStatistics operator +(const StatusStatistics& s);
01190     StatusStatistics& operator +=(const StatusStatistics& s);
01191   };
01192 
01197   class CloneStatistics {
01198   public:
01200     CloneStatistics(void);
01202     void reset(void);
01204     CloneStatistics operator +(const CloneStatistics& s);
01206     CloneStatistics& operator +=(const CloneStatistics& s);
01207   };
01208 
01213   class CommitStatistics {
01214   public:
01216     CommitStatistics(void);
01218     void reset(void);
01220     CommitStatistics operator +(const CommitStatistics& s);
01222     CommitStatistics& operator +=(const CommitStatistics& s);
01223   };
01224 
01228   class GECODE_VTABLE_EXPORT Space {
01229     friend class Actor;
01230     friend class Propagator;
01231     friend class Brancher;
01232     friend class Advisor;
01233     template<class VIC> friend class VarImp;
01234     template<class VarType> friend class VarDisposer;
01235     friend class CopiedHandle;
01236     friend class Region;
01237   private:
01239     SharedMemory* sm;
01241     MemoryManager mm;
01243     GlobalPropInfo gpi;
01245     ActorLink pl;
01247     ActorLink bl;
01253     Brancher* b_status;
01265     Brancher* b_commit;
01266     union {
01268       struct {
01281         ActorLink* active;
01283         ActorLink queue[PropCost::AC_MAX+1];
01285         unsigned int branch_id;
01287         unsigned int n_sub;
01288       } p;
01290       struct {
01292         VarImpBase* vars_u[AllVarConf::idx_c];
01294         VarImpBase* vars_noidx;
01296         CopiedHandle::Object* copied;
01297       } c;
01298     } pc;
01300     void enqueue(Propagator* p);
01305 #ifdef GECODE_HAS_VAR_DISPOSE
01307     GECODE_KERNEL_EXPORT static VarDisposerBase* vd[AllVarConf::idx_d];
01309     VarImpBase* _vars_d[AllVarConf::idx_d];
01311     template<class VIC> VarImpBase* vars_d(void) const;
01313     template<class VIC> void vars_d(VarImpBase* x);
01314 #endif
01316     void update(ActorLink** sub);
01317 
01318 
01320     Actor** d_fst;
01322     Actor** d_cur;
01324     Actor** d_lst;
01326     GECODE_KERNEL_EXPORT void d_resize(void);
01327 
01335     unsigned int n_wmp;
01336 
01338     GECODE_KERNEL_EXPORT static StatusStatistics unused_status;
01340     GECODE_KERNEL_EXPORT static CloneStatistics unused_clone;
01342     GECODE_KERNEL_EXPORT static CommitStatistics unused_commit;
01344     GECODE_KERNEL_EXPORT static unsigned long int unused_uli;
01346     GECODE_KERNEL_EXPORT static bool unused_b;
01347 
01362     GECODE_KERNEL_EXPORT Space* _clone(bool share=true);
01363 
01396     GECODE_KERNEL_EXPORT
01397     void _commit(const Choice& c, unsigned int a);
01398 
01399   public:
01404     GECODE_KERNEL_EXPORT Space(void);
01409     GECODE_KERNEL_EXPORT virtual ~Space(void);
01420     GECODE_KERNEL_EXPORT Space(bool share, Space& s);
01427     virtual Space* copy(bool share) = 0;
01439     GECODE_KERNEL_EXPORT virtual void constrain(const Space& best);
01444     static void* operator new(size_t);
01449     static void  operator delete(void*);
01450 
01451 
01452     /*
01453      * Member functions for search engines
01454      *
01455      */
01456 
01468     GECODE_KERNEL_EXPORT
01469     SpaceStatus status(StatusStatistics& stat=unused_status);
01470 
01502     GECODE_KERNEL_EXPORT
01503     const Choice* choice(void);
01504 
01522     Space* clone(bool share=true, CloneStatistics& stat=unused_clone) const;
01523 
01558     void commit(const Choice& c, unsigned int a,
01559                 CommitStatistics& stat=unused_commit);
01560 
01568     void notice(Actor& a, ActorProperty p);
01576     void ignore(Actor& a, ActorProperty p);
01577 
01585     void fail(void);
01594     bool failed(void) const;
01599     bool stable(void) const;
01606     GECODE_KERNEL_EXPORT unsigned int propagators(void) const;
01613     GECODE_KERNEL_EXPORT unsigned int branchers(void) const;
01614 
01616 
01617 
01618     Home operator ()(Propagator& p);
01620 
01632     template<class T>
01633     T* alloc(long unsigned int n);
01640     template<class T>
01641     T* alloc(long int n);
01648     template<class T>
01649     T* alloc(unsigned int n);
01656     template<class T>
01657     T* alloc(int n);
01667     template<class T>
01668     void free(T* b, long unsigned int n);
01678     template<class T>
01679     void free(T* b, long int n);
01689     template<class T>
01690     void free(T* b, unsigned int n);
01700     template<class T>
01701     void free(T* b, int n);
01713     template<class T>
01714     T* realloc(T* b, long unsigned int n, long unsigned int m);
01726     template<class T>
01727     T* realloc(T* b, long int n, long int m);
01739     template<class T>
01740     T* realloc(T* b, unsigned int n, unsigned int m);
01752     template<class T>
01753     T* realloc(T* b, int n, int m);
01761     template<class T>
01762     T** realloc(T** b, long unsigned int n, long unsigned int m);
01770     template<class T>
01771     T** realloc(T** b, long int n, long int m);
01779     template<class T>
01780     T** realloc(T** b, unsigned int n, unsigned int m);
01788     template<class T>
01789     T** realloc(T** b, int n, int m);
01791     void* ralloc(size_t s);
01793     void rfree(void* p, size_t s);
01795     void* rrealloc(void* b, size_t n, size_t m);
01797     template<size_t> void* fl_alloc(void);
01803     template<size_t> void  fl_dispose(FreeList* f, FreeList* l);
01810     size_t allocated(void) const;
01820     GECODE_KERNEL_EXPORT void flush(void);
01822 
01823 
01824 
01827     template<class T> 
01828     T& construct(void);
01834     template<class T, typename A1> 
01835     T& construct(A1 const& a1);
01841     template<class T, typename A1, typename A2> 
01842     T& construct(A1 const& a1, A2 const& a2);
01848     template<class T, typename A1, typename A2, typename A3>
01849     T& construct(A1 const& a1, A2 const& a2, A3 const& a3);
01855     template<class T, typename A1, typename A2, typename A3, typename A4>
01856     T& construct(A1 const& a1, A2 const& a2, A3 const& a3, A4 const& a4);
01862     template<class T, typename A1, typename A2, typename A3, typename A4, typename A5>
01863     T& construct(A1 const& a1, A2 const& a2, A3 const& a3, A4 const& a4, A5 const& a5);
01865 
01871     class Propagators {
01872     private:
01874       const Space& home;
01876       const ActorLink* q;
01878       const ActorLink* c;
01880       const ActorLink* e;
01881     public:
01883       Propagators(const Space& home);
01885       bool operator ()(void) const;
01887       void operator ++(void);
01889       const Propagator& propagator(void) const;
01890     };
01891 
01897     class Branchers {
01898     private:
01900       const ActorLink* c;
01902       const ActorLink* e;
01903     public:
01905       Branchers(const Space& home);
01907       bool operator ()(void) const;
01909       void operator ++(void);
01911       const Brancher& brancher(void) const;
01912     };    
01913   };
01914 
01915 
01916 
01917 
01918   /*
01919    * Memory management
01920    *
01921    */
01922 
01923   // Heap allocated
01924   forceinline void*
01925   SharedHandle::Object::operator new(size_t s) {
01926     return heap.ralloc(s);
01927   }
01928   forceinline void
01929   SharedHandle::Object::operator delete(void* p) {
01930     heap.rfree(p);
01931   }
01932 
01933   forceinline void*
01934   Space::operator new(size_t s) {
01935     return heap.ralloc(s);
01936   }
01937   forceinline void
01938   Space::operator delete(void* p) {
01939     heap.rfree(p);
01940   }
01941 
01942   forceinline void
01943   Choice::operator delete(void* p) {
01944     heap.rfree(p);
01945   }
01946   forceinline void*
01947   Choice::operator new(size_t s) {
01948     return heap.ralloc(s);
01949   }
01950 
01951   // Space allocation: general space heaps and free lists
01952   forceinline void*
01953   Space::ralloc(size_t s) {
01954     return mm.alloc(sm,s);
01955   }
01956   forceinline void
01957   Space::rfree(void* p, size_t s) {
01958     return mm.reuse(p,s);
01959   }
01960   forceinline void*
01961   Space::rrealloc(void* _b, size_t n, size_t m) {
01962     char* b = static_cast<char*>(_b);
01963     if (n < m) {
01964       char* p = static_cast<char*>(ralloc(m));
01965       memcpy(p,b,n);
01966       rfree(b,n);
01967       return p;
01968     } else {
01969       rfree(b+m,m-n);
01970       return b;
01971     }
01972   }
01973 
01974   template<size_t s>
01975   forceinline void*
01976   Space::fl_alloc(void) {
01977     return mm.template fl_alloc<s>(sm);
01978   }
01979   template<size_t s>
01980   forceinline void
01981   Space::fl_dispose(FreeList* f, FreeList* l) {
01982     mm.template fl_dispose<s>(f,l);
01983   }
01984 
01985   forceinline size_t
01986   Space::allocated(void) const {
01987     size_t s = mm.allocated();
01988     for (Actor** a = d_fst; a < d_cur; a++)
01989       s += (*a)->allocated();
01990     return s;
01991   }
01992 
01993   /*
01994    * Typed allocation routines
01995    *
01996    */
01997   template<class T>
01998   forceinline T*
01999   Space::alloc(long unsigned int n) {
02000     T* p = static_cast<T*>(ralloc(sizeof(T)*n));
02001     for (long unsigned int i=n; i--; )
02002       (void) new (p+i) T();
02003     return p;
02004   }
02005   template<class T>
02006   forceinline T*
02007   Space::alloc(long int n) {
02008     assert(n >= 0);
02009     return alloc<T>(static_cast<long unsigned int>(n));
02010   }
02011   template<class T>
02012   forceinline T*
02013   Space::alloc(unsigned int n) {
02014     return alloc<T>(static_cast<long unsigned int>(n));
02015   }
02016   template<class T>
02017   forceinline T*
02018   Space::alloc(int n) {
02019     assert(n >= 0);
02020     return alloc<T>(static_cast<long unsigned int>(n));
02021   }
02022 
02023   template<class T>
02024   forceinline void
02025   Space::free(T* b, long unsigned int n) {
02026     for (long unsigned int i=n; i--; )
02027       b[i].~T();
02028     rfree(b,n*sizeof(T));
02029   }
02030   template<class T>
02031   forceinline void
02032   Space::free(T* b, long int n) {
02033     assert(n >= 0);
02034     free<T>(b,static_cast<long unsigned int>(n));
02035   }
02036   template<class T>
02037   forceinline void
02038   Space::free(T* b, unsigned int n) {
02039     free<T>(b,static_cast<long unsigned int>(n));
02040   }
02041   template<class T>
02042   forceinline void
02043   Space::free(T* b, int n) {
02044     assert(n >= 0);
02045     free<T>(b,static_cast<long unsigned int>(n));
02046   }
02047 
02048   template<class T>
02049   forceinline T*
02050   Space::realloc(T* b, long unsigned int n, long unsigned int m) {
02051     if (n < m) {
02052       T* p = static_cast<T*>(ralloc(sizeof(T)*m));
02053       for (long unsigned int i=n; i--; )
02054         (void) new (p+i) T(b[i]);
02055       for (long unsigned int i=n; i<m; i++)
02056         (void) new (p+i) T();
02057       free<T>(b,n);
02058       return p;
02059     } else {
02060       free<T>(b+m,m-n);
02061       return b;
02062     }
02063   }
02064   template<class T>
02065   forceinline T*
02066   Space::realloc(T* b, long int n, long int m) {
02067     assert((n >= 0) && (m >= 0));
02068     return realloc<T>(b,static_cast<long unsigned int>(n),
02069                       static_cast<long unsigned int>(m));
02070   }
02071   template<class T>
02072   forceinline T*
02073   Space::realloc(T* b, unsigned int n, unsigned int m) {
02074     return realloc<T>(b,static_cast<long unsigned int>(n),
02075                       static_cast<long unsigned int>(m));
02076   }
02077   template<class T>
02078   forceinline T*
02079   Space::realloc(T* b, int n, int m) {
02080     assert((n >= 0) && (m >= 0));
02081     return realloc<T>(b,static_cast<long unsigned int>(n),
02082                       static_cast<long unsigned int>(m));
02083   }
02084 
02085 #define GECODE_KERNEL_REALLOC(T)                                        \
02086   template<>                                                            \
02087   forceinline T*                                                        \
02088   Space::realloc<T>(T* b, long unsigned int n, long unsigned int m) {   \
02089     return static_cast<T*>(rrealloc(b,n*sizeof(T),m*sizeof(T)));        \
02090   }                                                                     \
02091   template<>                                                            \
02092   forceinline T*                                                        \
02093   Space::realloc<T>(T* b, long int n, long int m) {                     \
02094     assert((n >= 0) && (m >= 0));                                       \
02095     return realloc<T>(b,static_cast<long unsigned int>(n),              \
02096                       static_cast<long unsigned int>(m));               \
02097   }                                                                     \
02098   template<>                                                            \
02099   forceinline T*                                                        \
02100   Space::realloc<T>(T* b, unsigned int n, unsigned int m) {             \
02101     return realloc<T>(b,static_cast<long unsigned int>(n),              \
02102                       static_cast<long unsigned int>(m));               \
02103   }                                                                     \
02104   template<>                                                            \
02105   forceinline T*                                                        \
02106   Space::realloc<T>(T* b, int n, int m) {                               \
02107     assert((n >= 0) && (m >= 0));                                       \
02108     return realloc<T>(b,static_cast<long unsigned int>(n),              \
02109                       static_cast<long unsigned int>(m));               \
02110   }
02111 
02112   GECODE_KERNEL_REALLOC(bool)
02113   GECODE_KERNEL_REALLOC(signed char)
02114   GECODE_KERNEL_REALLOC(unsigned char)
02115   GECODE_KERNEL_REALLOC(signed short int)
02116   GECODE_KERNEL_REALLOC(unsigned short int)
02117   GECODE_KERNEL_REALLOC(signed int)
02118   GECODE_KERNEL_REALLOC(unsigned int)
02119   GECODE_KERNEL_REALLOC(signed long int)
02120   GECODE_KERNEL_REALLOC(unsigned long int)
02121   GECODE_KERNEL_REALLOC(float)
02122   GECODE_KERNEL_REALLOC(double)
02123 
02124 #undef GECODE_KERNEL_REALLOC
02125 
02126   template<class T>
02127   forceinline T**
02128   Space::realloc(T** b, long unsigned int n, long unsigned int m) {
02129     return static_cast<T**>(rrealloc(b,n*sizeof(T),m*sizeof(T*)));
02130   }
02131   template<class T>
02132   forceinline T**
02133   Space::realloc(T** b, long int n, long int m) {
02134     assert((n >= 0) && (m >= 0));
02135     return realloc<T*>(b,static_cast<long unsigned int>(n),
02136                        static_cast<long unsigned int>(m));
02137   }
02138   template<class T>
02139   forceinline T**
02140   Space::realloc(T** b, unsigned int n, unsigned int m) {
02141     return realloc<T*>(b,static_cast<long unsigned int>(n),
02142                        static_cast<long unsigned int>(m));
02143   }
02144   template<class T>
02145   forceinline T**
02146   Space::realloc(T** b, int n, int m) {
02147     assert((n >= 0) && (m >= 0));
02148     return realloc<T*>(b,static_cast<long unsigned int>(n),
02149                        static_cast<long unsigned int>(m));
02150   }
02151 
02152 
02153 #ifdef GECODE_HAS_VAR_DISPOSE
02154   template<class VIC>
02155   forceinline VarImpBase*
02156   Space::vars_d(void) const {
02157     return _vars_d[VIC::idx_d];
02158   }
02159   template<class VIC>
02160   forceinline void
02161   Space::vars_d(VarImpBase* x) {
02162     _vars_d[VIC::idx_d] = x;
02163   }
02164 #endif
02165 
02166   // Space allocated entities: Actors, variable implementations, and advisors
02167   forceinline void
02168   Actor::operator delete(void*) {}
02169   forceinline void
02170   Actor::operator delete(void*, Space&) {}
02171   forceinline void*
02172   Actor::operator new(size_t s, Space& home) {
02173     return home.ralloc(s);
02174   }
02175 
02176   template<class VIC>
02177   forceinline void
02178   VarImp<VIC>::operator delete(void*) {}
02179   template<class VIC>
02180   forceinline void
02181   VarImp<VIC>::operator delete(void*, Space&) {}
02182   template<class VIC>
02183   forceinline void*
02184   VarImp<VIC>::operator new(size_t s, Space& home) {
02185     return home.ralloc(s);
02186   }
02187 
02188 #ifndef __GNUC__
02189   forceinline void
02190   Advisor::operator delete(void*) {}
02191 #endif
02192   forceinline void
02193   Advisor::operator delete(void*, Space&) {}
02194   forceinline void*
02195   Advisor::operator new(size_t s, Space& home) {
02196     return home.ralloc(s);
02197   }
02198 
02199   forceinline void
02200   CopiedHandle::Object::operator delete(void*, size_t) {}
02201   forceinline void
02202   CopiedHandle::Object::operator delete(void*, Space&) {}
02203   forceinline void*
02204   CopiedHandle::Object::operator new(size_t s, Space& home) {
02205     return home.ralloc(s);
02206   }
02207 
02208   /*
02209    * Copied objects and handles
02210    *
02211    */
02212   forceinline
02213   CopiedHandle::Object::Object(void)
02214     : fwd(NULL) {}
02215   forceinline
02216   CopiedHandle::Object::~Object(void) {}
02217 
02218   forceinline
02219   CopiedHandle::CopiedHandle(void) : o(NULL) {}
02220   forceinline
02221   CopiedHandle::CopiedHandle(CopiedHandle::Object* so) : o(so) {}
02222   forceinline
02223   CopiedHandle::CopiedHandle(const CopiedHandle& sh) : o(sh.o) {}
02224   forceinline CopiedHandle&
02225   CopiedHandle::operator =(const CopiedHandle& sh) {
02226     o = sh.o;
02227     return *this;
02228   }
02229   forceinline void
02230   CopiedHandle::update(Space& home, bool, CopiedHandle& sh) {
02231     if (sh.o == NULL) {
02232       o = NULL;
02233     } else if (sh.o->fwd != NULL) {
02234       o = sh.o->fwd;
02235     } else {
02236       o = sh.o->copy();
02237       sh.o->fwd = o;
02238       sh.o->next = home.pc.c.copied;
02239       home.pc.c.copied = sh.o;
02240     }
02241   }
02242   forceinline void
02243   CopiedHandle::dispose(Space&) {
02244     (*o).~Object();
02245   }
02246   forceinline CopiedHandle::Object*
02247   CopiedHandle::object(void) const {
02248     return o;
02249   }
02250   forceinline void
02251   CopiedHandle::object(CopiedHandle::Object* n) {
02252     o=n;
02253   }
02254 
02255   /*
02256    * Shared objects and handles
02257    *
02258    */
02259   forceinline
02260   SharedHandle::Object::Object(void)
02261     : use_cnt(0) {}
02262   forceinline
02263   SharedHandle::Object::~Object(void) {
02264     assert(use_cnt == 0);
02265   }
02266 
02267   forceinline SharedHandle::Object*
02268   SharedHandle::object(void) const {
02269     return static_cast<SharedHandle::Object*>(CopiedHandle::object());
02270   }
02271   forceinline void
02272   SharedHandle::subscribe(void) {
02273     if (object() != NULL) object()->use_cnt++;
02274   }
02275   forceinline void
02276   SharedHandle::cancel(void) {
02277     if ((object() != NULL) && (--object()->use_cnt == 0))
02278       delete object();
02279     CopiedHandle::object(NULL);
02280   }
02281   forceinline void
02282   SharedHandle::object(SharedHandle::Object* n) {
02283     if (n != object()) {
02284       cancel(); CopiedHandle::object(n); subscribe();
02285     }
02286   }
02287   forceinline
02288   SharedHandle::SharedHandle(void) {}
02289   forceinline
02290   SharedHandle::SharedHandle(SharedHandle::Object* so) : CopiedHandle(so) {
02291     subscribe();
02292   }
02293   forceinline
02294   SharedHandle::SharedHandle(const SharedHandle& sh) : CopiedHandle(sh) {
02295     subscribe();
02296   }
02297   forceinline SharedHandle&
02298   SharedHandle::operator =(const SharedHandle& sh) {
02299     if (&sh != this) {
02300       cancel(); CopiedHandle::object(sh.object()); subscribe();
02301     }
02302     return *this;
02303   }
02304   forceinline void
02305   SharedHandle::update(Space& home, bool share, SharedHandle& sh) {
02306     if (sh.object() == NULL) {
02307       CopiedHandle::object(NULL);
02308     } else if (share) {
02309       CopiedHandle::object(sh.object()); subscribe();
02310     } else {
02311       CopiedHandle::update(home, share, sh);
02312       subscribe();
02313     }
02314   }
02315   forceinline
02316   SharedHandle::~SharedHandle(void) {
02317     cancel();
02318   }
02319 
02320 
02321 
02322   /*
02323    * ActorLink
02324    *
02325    */
02326   forceinline ActorLink*
02327   ActorLink::prev(void) const {
02328     return _prev;
02329   }
02330 
02331   forceinline ActorLink*
02332   ActorLink::next(void) const {
02333     return _next;
02334   }
02335 
02336   forceinline ActorLink**
02337   ActorLink::next_ref(void) {
02338     return &_next;
02339   }
02340 
02341   forceinline void
02342   ActorLink::prev(ActorLink* al) {
02343     _prev = al;
02344   }
02345 
02346   forceinline void
02347   ActorLink::next(ActorLink* al) {
02348     _next = al;
02349   }
02350 
02351   forceinline void
02352   ActorLink::unlink(void) {
02353     ActorLink* p = _prev; ActorLink* n = _next;
02354     p->_next = n; n->_prev = p;
02355   }
02356 
02357   forceinline void
02358   ActorLink::init(void) {
02359     _next = this; _prev =this;
02360   }
02361 
02362   forceinline void
02363   ActorLink::head(ActorLink* a) {
02364     // Inserts al at head of link-chain (that is, after this)
02365     ActorLink* n = _next;
02366     this->_next = a; a->_prev = this;
02367     a->_next = n; n->_prev = a;
02368   }
02369 
02370   forceinline void
02371   ActorLink::tail(ActorLink* a) {
02372     // Inserts al at tail of link-chain (that is, before this)
02373     ActorLink* p = _prev;
02374     a->_next = this; this->_prev = a;
02375     p->_next = a; a->_prev = p;
02376   }
02377 
02378   forceinline bool
02379   ActorLink::empty(void) const {
02380     return _next == this;
02381   }
02382 
02383   template<class T>
02384   forceinline ActorLink*
02385   ActorLink::cast(T* a) {
02386     // Turning al into a reference is for gcc, assume is for MSVC
02387     GECODE_NOT_NULL(a);
02388     ActorLink& t = *a;
02389     return static_cast<ActorLink*>(&t);
02390   }
02391 
02392   template<class T>
02393   forceinline const ActorLink*
02394   ActorLink::cast(const T* a) {
02395     // Turning al into a reference is for gcc, assume is for MSVC
02396     GECODE_NOT_NULL(a);
02397     const ActorLink& t = *a;
02398     return static_cast<const ActorLink*>(&t);
02399   }
02400 
02401 
02402   /*
02403    * Actor
02404    *
02405    */
02406   forceinline Actor*
02407   Actor::cast(ActorLink* al) {
02408     // Turning al into a reference is for gcc, assume is for MSVC
02409     GECODE_NOT_NULL(al);
02410     ActorLink& t = *al;
02411     return static_cast<Actor*>(&t);
02412   }
02413 
02414   forceinline const Actor*
02415   Actor::cast(const ActorLink* al) {
02416     // Turning al into a reference is for gcc, assume is for MSVC
02417     GECODE_NOT_NULL(al);
02418     const ActorLink& t = *al;
02419     return static_cast<const Actor*>(&t);
02420   }
02421 
02422   forceinline void
02423   Space::notice(Actor& a, ActorProperty p) {
02424     if (p & AP_DISPOSE) {
02425       if (d_cur == d_lst)
02426         d_resize();
02427       *(d_cur++) = &a;
02428     }
02429     if (p & AP_WEAKLY) {
02430       if (n_wmp == 0)
02431         n_wmp = 2;
02432       else
02433         n_wmp++;
02434     }
02435   }
02436 
02437   forceinline void
02438   Home::notice(Actor& a, ActorProperty p) {
02439     s.notice(a,p);
02440   }
02441 
02442   forceinline void
02443   Space::ignore(Actor& a, ActorProperty p) {
02444     if (p & AP_DISPOSE) {
02445       // Check wether array has already been discarded as space
02446       // deletion is already in progress
02447       Actor** f = d_fst;
02448       if (f != NULL) {
02449         while (&a != *f)
02450           f++;
02451         *f = *(--d_cur);
02452       }
02453     }
02454     if (p & AP_WEAKLY) {
02455       assert(n_wmp > 1);
02456       n_wmp--;
02457     }
02458   }
02459 
02460   forceinline Space*
02461   Space::clone(bool share, CloneStatistics&) const {
02462     // Clone is only const for search engines. During cloning, several data
02463     // structures are updated (e.g. forwarding pointers), so we have to
02464     // cast away the constness.
02465     return const_cast<Space*>(this)->_clone(share);
02466   }
02467 
02468   forceinline void
02469   Space::commit(const Choice& c, unsigned int a, CommitStatistics&) {
02470     _commit(c,a);
02471   }
02472 
02473   forceinline size_t
02474   Actor::dispose(Space&) {
02475     return sizeof(*this);
02476   }
02477 
02478 
02479   /*
02480    * Home for posting actors
02481    *
02482    */
02483   forceinline
02484   Home::Home(Space& s0, Propagator* p0) : s(s0), p(p0) {}
02485   forceinline
02486   Home::operator Space&(void) { 
02487     return s; 
02488   }
02489   forceinline Home
02490   Home::operator ()(Propagator& p) {
02491     return Home(s,&p);
02492   }
02493   forceinline Home
02494   Space::operator ()(Propagator& p) {
02495     return Home(*this,&p);
02496   }
02497   forceinline Propagator*
02498   Home::propagator(void) const {
02499     return p;
02500   }
02501 
02502   /*
02503    * Propagator
02504    *
02505    */
02506   forceinline Propagator*
02507   Propagator::cast(ActorLink* al) {
02508     // Turning al into a reference is for gcc, assume is for MSVC
02509     GECODE_NOT_NULL(al);
02510     ActorLink& t = *al;
02511     return static_cast<Propagator*>(&t);
02512   }
02513 
02514   forceinline const Propagator*
02515   Propagator::cast(const ActorLink* al) {
02516     // Turning al into a reference is for gcc, assume is for MSVC
02517     GECODE_NOT_NULL(al);
02518     const ActorLink& t = *al;
02519     return static_cast<const Propagator*>(&t);
02520   }
02521 
02522   forceinline
02523   Propagator::Propagator(Home home) 
02524     : pi((home.propagator() != NULL) ?
02525          // Inherit propagator information
02526          home.propagator()->pi :
02527          // New propagator information
02528          static_cast<Space&>(home).gpi.allocate()) {
02529     u.advisors = NULL;
02530     assert((u.med == 0) && (u.size == 0));
02531     static_cast<Space&>(home).pl.head(this);
02532   }
02533 
02534   forceinline
02535   Propagator::Propagator(Space&, bool, Propagator& p) 
02536     : pi(p.pi) {
02537     u.advisors = NULL;
02538     assert((u.med == 0) && (u.size == 0));
02539     // Set forwarding pointer
02540     p.prev(this);
02541   }
02542 
02543   forceinline double
02544   Propagator::afc(void) const {
02545     return pi.afc();
02546   }
02547 
02548   forceinline ExecStatus
02549   ES_SUBSUMED(Propagator& p, size_t s) {
02550     p.u.size = s;
02551     return __ES_SUBSUMED;
02552   }
02553 
02554   forceinline ExecStatus
02555   ES_SUBSUMED(Propagator& p, Space& home) {
02556     p.u.size = p.dispose(home);
02557     return __ES_SUBSUMED;
02558   }
02559 
02560   forceinline ExecStatus
02561   ES_FIX_PARTIAL(Propagator& p, const ModEventDelta& med) {
02562     p.u.med = med;
02563     assert(p.u.med != 0);
02564     return __ES_PARTIAL;
02565   }
02566 
02567   forceinline ExecStatus
02568   ES_NOFIX_PARTIAL(Propagator& p, const ModEventDelta& med) {
02569     p.u.med = AllVarConf::med_combine(p.u.med,med);
02570     assert(p.u.med != 0);
02571     return __ES_PARTIAL;
02572   }
02573 
02574 
02575 
02576   /*
02577    * Brancher
02578    *
02579    */
02580   forceinline Brancher*
02581   Brancher::cast(ActorLink* al) {
02582     // Turning al into a reference is for gcc, assume is for MSVC
02583     GECODE_NOT_NULL(al);
02584     ActorLink& t = *al;
02585     return static_cast<Brancher*>(&t);
02586   }
02587 
02588   forceinline const Brancher*
02589   Brancher::cast(const ActorLink* al) {
02590     // Turning al into a reference is for gcc, assume is for MSVC
02591     GECODE_NOT_NULL(al);
02592     const ActorLink& t = *al;
02593     return static_cast<const Brancher*>(&t);
02594   }
02595 
02596   forceinline
02597   Brancher::Brancher(Home home) :
02598     _id(static_cast<Space&>(home).pc.p.branch_id++) {
02599     if (static_cast<Space&>(home).pc.p.branch_id == 0U)
02600       throw TooManyBranchers("Brancher::Brancher");
02601     // If no brancher available, make it the first one
02602     if (static_cast<Space&>(home).b_status == &static_cast<Space&>(home).bl) {
02603       static_cast<Space&>(home).b_status = this;
02604       if (static_cast<Space&>(home).b_commit == &static_cast<Space&>(home).bl)
02605         static_cast<Space&>(home).b_commit = this;
02606     }
02607     static_cast<Space&>(home).bl.tail(this);
02608   }
02609 
02610   forceinline
02611   Brancher::Brancher(Space&, bool, Brancher& b)
02612     : _id(b._id) {
02613     // Set forwarding pointer
02614     b.prev(this);
02615   }
02616 
02617   forceinline unsigned int
02618   Brancher::id(void) const {
02619     return _id;
02620   }
02621 
02622 
02623 
02624   /*
02625    * Choices
02626    *
02627    */
02628   forceinline
02629   Choice::Choice(const Brancher& b, const unsigned int a)
02630     : _id(b.id()), _alt(a) {}
02631 
02632   forceinline unsigned int
02633   Choice::alternatives(void) const {
02634     return _alt;
02635   }
02636 
02637   forceinline unsigned int
02638   Choice::id(void) const {
02639     return _id;
02640   }
02641 
02642   forceinline
02643   Choice::~Choice(void) {}
02644 
02645 
02646 
02647   /*
02648    * Delta information for advisors
02649    *
02650    */
02651   forceinline ModEvent
02652   Delta::modevent(void) const {
02653     return me;
02654   }
02655 
02656 
02657 
02658   /*
02659    * Advisor
02660    *
02661    */
02662   template<class A>
02663   forceinline
02664   Advisor::Advisor(Space&, Propagator& p, Council<A>& c) {
02665     // Store propagator and forwarding in prev()
02666     ActorLink::prev(&p);
02667     // Link to next advisor in next()
02668     ActorLink::next(c.advisors); c.advisors = static_cast<A*>(this);
02669   }
02670 
02671   forceinline
02672   Advisor::Advisor(Space&, bool, Advisor&) {}
02673 
02674   forceinline bool
02675   Advisor::disposed(void) const {
02676     return prev() == NULL;
02677   }
02678 
02679   forceinline Advisor*
02680   Advisor::cast(ActorLink* al) {
02681     return static_cast<Advisor*>(al);
02682   }
02683 
02684   forceinline const Advisor*
02685   Advisor::cast(const ActorLink* al) {
02686     return static_cast<const Advisor*>(al);
02687   }
02688 
02689   forceinline Propagator&
02690   Advisor::propagator(void) const {
02691     assert(!disposed());
02692     return *Propagator::cast(ActorLink::prev());
02693   }
02694 
02695   template<class A>
02696   forceinline void
02697   Advisor::dispose(Space&,Council<A>&) {
02698     assert(!disposed());
02699     ActorLink::prev(NULL);
02700     // Shorten chains of disposed advisors by one, if possible
02701     Advisor* n = Advisor::cast(next());
02702     if ((n != NULL) && n->disposed())
02703       next(n->next());
02704   }
02705 
02706   template<class A>
02707   forceinline ExecStatus
02708   ES_SUBSUMED_FIX(A& a, Space& home, Council<A>& c) {
02709     a.dispose(home,c);
02710     return ES_FIX;
02711   }
02712 
02713   template<class A>
02714   forceinline ExecStatus
02715   ES_SUBSUMED_NOFIX(A& a, Space& home, Council<A>& c) {
02716     a.dispose(home,c);
02717     return ES_NOFIX;
02718   }
02719 
02720 
02721 
02722   /*
02723    * Advisor council
02724    *
02725    */
02726   template<class A>
02727   forceinline
02728   Council<A>::Council(void) {}
02729 
02730   template<class A>
02731   forceinline
02732   Council<A>::Council(Space&)
02733     : advisors(NULL) {}
02734 
02735   template<class A>
02736   forceinline bool
02737   Council<A>::empty(void) const {
02738     ActorLink* a = advisors;
02739     while ((a != NULL) && static_cast<A*>(a)->disposed())
02740       a = a->next();
02741     advisors = a;
02742     return a == NULL;
02743   }
02744 
02745   template<class A>
02746   forceinline void
02747   Council<A>::update(Space& home, bool share, Council<A>& c) {
02748     // Skip all disposed advisors
02749     {
02750       ActorLink* a = c.advisors;
02751       while ((a != NULL) && static_cast<A*>(a)->disposed())
02752         a = a->next();
02753       c.advisors = a;
02754     }
02755     // Are there any advisors to be cloned?
02756     if (c.advisors != NULL) {
02757       // The propagator in from-space
02758       Propagator* p_f = &static_cast<A*>(c.advisors)->propagator();
02759       // The propagator in to-space
02760       Propagator* p_t = Propagator::cast(p_f->prev());
02761       // Advisors in from-space
02762       ActorLink** a_f = &c.advisors;
02763       // Advisors in to-space
02764       A* a_t = NULL;
02765       while (*a_f != NULL) {
02766         if (static_cast<A*>(*a_f)->disposed()) {
02767           *a_f = (*a_f)->next();
02768         } else {
02769           // Run specific copying part
02770           A* a = new (home) A(home,share,*static_cast<A*>(*a_f));
02771           // Set propagator pointer
02772           a->prev(p_t);
02773           // Set forwarding pointer
02774           (*a_f)->prev(a);
02775           // Link
02776           a->next(a_t);
02777           a_t = a;
02778           a_f = (*a_f)->next_ref();
02779         }
02780       }
02781       advisors = a_t;
02782       // Enter advisor link for reset
02783       assert(p_f->u.advisors == NULL);
02784       p_f->u.advisors = c.advisors;
02785     } else {
02786       advisors = NULL;
02787     }
02788   }
02789 
02790   template<class A>
02791   forceinline void
02792   Council<A>::dispose(Space& home) {
02793     ActorLink* a = advisors;
02794     while (a != NULL) {
02795       if (!static_cast<A*>(a)->disposed())
02796         static_cast<A*>(a)->dispose(home,*this);
02797       a = a->next();
02798     }
02799   }
02800 
02801 
02802 
02803   /*
02804    * Advisor iterator
02805    *
02806    */
02807   template<class A>
02808   forceinline
02809   Advisors<A>::Advisors(const Council<A>& c)
02810     : a(c.advisors) {
02811     while ((a != NULL) && static_cast<A*>(a)->disposed())
02812       a = a->next();
02813   }
02814 
02815   template<class A>
02816   forceinline bool
02817   Advisors<A>::operator ()(void) const {
02818     return a != NULL;
02819   }
02820 
02821   template<class A>
02822   forceinline void
02823   Advisors<A>::operator ++(void) {
02824     do {
02825       a = a->next();
02826     } while ((a != NULL) && static_cast<A*>(a)->disposed());
02827   }
02828 
02829   template<class A>
02830   forceinline A&
02831   Advisors<A>::advisor(void) const {
02832     return *static_cast<A*>(a);
02833   }
02834 
02835 
02836 
02837   /*
02838    * Space
02839    *
02840    */
02841   forceinline void
02842   Space::enqueue(Propagator* p) {
02843     ActorLink::cast(p)->unlink();
02844     ActorLink* c = &pc.p.queue[p->cost(*this,p->u.med).ac];
02845     c->tail(ActorLink::cast(p));
02846     if (c > pc.p.active)
02847       pc.p.active = c;
02848   }
02849 
02850   forceinline void
02851   Space::fail(void) {
02852     pc.p.active = NULL;
02853   }
02854   forceinline void
02855   Home::fail(void) {
02856     s.fail();
02857   }
02858 
02859   forceinline bool
02860   Space::failed(void) const {
02861     return pc.p.active == NULL;
02862   }
02863   forceinline bool
02864   Home::failed(void) const {
02865     return s.failed();
02866   }
02867 
02868   forceinline bool
02869   Space::stable(void) const {
02870     return pc.p.active < &pc.p.queue[0];
02871   }
02872 
02873 
02874 
02875   /*
02876    * Variable implementation
02877    *
02878    */
02879   template<class VIC>
02880   forceinline ActorLink**
02881   VarImp<VIC>::actor(PropCond pc) {
02882     assert((pc >= 0)  && (pc < pc_max+2));
02883     return (pc == 0) ? base : base+u.idx[pc-1];
02884   }
02885 
02886   template<class VIC>
02887   forceinline ActorLink**
02888   VarImp<VIC>::actorNonZero(PropCond pc) {
02889     assert((pc > 0)  && (pc < pc_max+2));
02890     return base+u.idx[pc-1];
02891   }
02892 
02893   template<class VIC>
02894   forceinline unsigned int&
02895   VarImp<VIC>::idx(PropCond pc) {
02896     assert((pc > 0)  && (pc < pc_max+2));
02897     return u.idx[pc-1];
02898   }
02899 
02900   template<class VIC>
02901   forceinline unsigned int
02902   VarImp<VIC>::idx(PropCond pc) const {
02903     assert((pc > 0)  && (pc < pc_max+2));
02904     return u.idx[pc-1];
02905   }
02906 
02907   template<class VIC>
02908   forceinline
02909   VarImp<VIC>::VarImp(Space&) {
02910     base = NULL; entries = 0;
02911     for (PropCond pc=1; pc<pc_max+2; pc++)
02912       idx(pc) = 0;
02913     free_and_bits = 0;
02914   }
02915 
02916   template<class VIC>
02917   forceinline
02918   VarImp<VIC>::VarImp(void) {
02919     base = NULL; entries = 0;
02920     for (PropCond pc=1; pc<pc_max+2; pc++)
02921       idx(pc) = 0;
02922     free_and_bits = 0;
02923   }
02924 
02925   template<class VIC>
02926   forceinline unsigned int
02927   VarImp<VIC>::degree(void) const {
02928     assert(!copied());
02929     return entries;
02930   }
02931 
02932   template<class VIC>
02933   forceinline double
02934   VarImp<VIC>::afc(void) const {
02935     if (degree() == 0)
02936       return 0.0;
02937     double d = degree();
02938     // Count the afc of each propagator
02939     {
02940       ActorLink** a = const_cast<VarImp<VIC>*>(this)->actor(0);
02941       ActorLink** e = const_cast<VarImp<VIC>*>(this)->actorNonZero(pc_max+1);
02942       while (a < e) {
02943         d += Propagator::cast(*a)->afc(); a++;
02944       }
02945     }
02946     // Count the afc of each advisor's propagator
02947     {
02948       ActorLink** a = const_cast<VarImp<VIC>*>(this)->actorNonZero(pc_max+1);
02949       ActorLink** e = const_cast<VarImp<VIC>*>(this)->base+entries;
02950       while (a < e) {
02951         d += Advisor::cast(*a)->propagator().afc(); a++;
02952       }
02953     }
02954     return d;
02955   }
02956 
02957   template<class VIC>
02958   forceinline unsigned int
02959   VarImp<VIC>::bits(void) const {
02960     return free_and_bits;
02961   }
02962 
02963   template<class VIC>
02964   forceinline unsigned int&
02965   VarImp<VIC>::bits(void) {
02966     return free_and_bits;
02967   }
02968 
02969 #ifdef GECODE_HAS_VAR_DISPOSE
02970   template<class VIC>
02971   forceinline VarImp<VIC>*
02972   VarImp<VIC>::vars_d(Space& home) {
02973     return static_cast<VarImp<VIC>*>(home.vars_d<VIC>());
02974   }
02975 
02976   template<class VIC>
02977   forceinline void
02978   VarImp<VIC>::vars_d(Space& home, VarImp<VIC>* x) {
02979     home.vars_d<VIC>(x);
02980   }
02981 #endif
02982 
02983   template<class VIC>
02984   forceinline bool
02985   VarImp<VIC>::copied(void) const {
02986     return Support::marked(base);
02987   }
02988 
02989   template<class VIC>
02990   forceinline VarImp<VIC>*
02991   VarImp<VIC>::forward(void) const {
02992     assert(copied());
02993     return reinterpret_cast<VarImp<VIC>*>(Support::unmark(base));
02994   }
02995 
02996   template<class VIC>
02997   forceinline VarImp<VIC>*
02998   VarImp<VIC>::next(void) const {
02999     assert(copied());
03000     return u.next;
03001   }
03002 
03003   template<class VIC>
03004   forceinline
03005   VarImp<VIC>::VarImp(Space& home, bool, VarImp<VIC>& x) {
03006     VarImpBase** reg;
03007     free_and_bits = x.free_and_bits & ((1 << free_bits) - 1);
03008     if (x.base == NULL) {
03009       // Variable implementation needs no index structure
03010       reg = &home.pc.c.vars_noidx;
03011       assert(x.degree() == 0);
03012     } else {
03013       reg = &home.pc.c.vars_u[idx_c];
03014     }
03015     // Save subscriptions in copy
03016     base = x.base;
03017     entries = x.entries;
03018     for (PropCond pc=1; pc<pc_max+2; pc++)
03019       idx(pc) = x.idx(pc);
03020 
03021     // Set forwarding pointer
03022     x.base = reinterpret_cast<ActorLink**>(Support::mark(this));
03023     // Register original
03024     x.u.next = static_cast<VarImp<VIC>*>(*reg); *reg = &x;
03025   }
03026 
03027   template<class VIC>
03028   forceinline ModEvent
03029   VarImp<VIC>::me(const ModEventDelta& med) {
03030     return static_cast<ModEvent>((med & VIC::med_mask) >> VIC::med_fst);
03031   }
03032 
03033   template<class VIC>
03034   forceinline ModEventDelta
03035   VarImp<VIC>::med(ModEvent me) {
03036     return static_cast<ModEventDelta>(me << VIC::med_fst);
03037   }
03038 
03039   template<class VIC>
03040   forceinline ModEvent
03041   VarImp<VIC>::me_combine(ModEvent me1, ModEvent me2) {
03042     return VIC::me_combine(me1,me2);
03043   }
03044 
03045   template<class VIC>
03046   forceinline void
03047   VarImp<VIC>::schedule(Space& home, Propagator& p, ModEvent me) {
03048     if (VIC::med_update(p.u.med,me))
03049       home.enqueue(&p);
03050   }
03051 
03052   template<class VIC>
03053   forceinline void
03054   VarImp<VIC>::schedule(Space& home, PropCond pc1, PropCond pc2, ModEvent me) {
03055     ActorLink** b = actor(pc1);
03056     ActorLink** p = actorNonZero(pc2+1);
03057     while (p-- > b)
03058       schedule(home,*Propagator::cast(*p),me);
03059   }
03060 
03061   template<class VIC>
03062   forceinline void
03063   VarImp<VIC>::enter(Space& home, Propagator* p, PropCond pc) {
03064     assert(pc <= pc_max);
03065     // Count one new subscription
03066     home.pc.p.n_sub += 1;
03067     if ((free_and_bits >> free_bits) == 0)
03068       resize(home);
03069     free_and_bits -= 1 << free_bits;
03070 
03071     // Enter subscription
03072     base[entries] = *actorNonZero(pc_max+1);
03073     entries++;
03074     for (PropCond j = pc_max; j > pc; j--) {
03075       *actorNonZero(j+1) = *actorNonZero(j);
03076       idx(j+1)++;
03077     }
03078     *actorNonZero(pc+1) = *actor(pc);
03079     idx(pc+1)++;
03080     *actor(pc) = ActorLink::cast(p);
03081 
03082 #ifdef GECODE_AUDIT
03083     ActorLink** f = actor(pc);
03084     while (f < (pc == pc_max+1 ? base+entries : actorNonZero(pc+1)))
03085       if (*f == p)
03086         goto found;
03087       else
03088         f++;
03089     GECODE_NEVER;
03090     found: ;
03091 #endif
03092   }
03093 
03094   template<class VIC>
03095   forceinline void
03096   VarImp<VIC>::enter(Space& home, Advisor* a) {
03097     // Count one new subscription
03098     home.pc.p.n_sub += 1;
03099     if ((free_and_bits >> free_bits) == 0)
03100       resize(home);
03101     free_and_bits -= 1 << free_bits;
03102 
03103     // Enter subscription
03104     base[entries++] = *actorNonZero(pc_max+1);
03105     *actorNonZero(pc_max+1) = a;
03106   }
03107 
03108   template<class VIC>
03109   void
03110   VarImp<VIC>::resize(Space& home) {
03111     if (base == NULL) {
03112       assert((free_and_bits >> free_bits) == 0);
03113       // Create fresh dependency array with four entries
03114       free_and_bits += 4 << free_bits;
03115       base = home.alloc<ActorLink*>(4);
03116       for (int i=0; i<pc_max+1; i++)
03117         u.idx[i] = 0;
03118     } else {
03119       // Resize dependency array
03120       unsigned int n = degree();
03121       // Find out whether the area is most likely in the special area
03122       // reserved for subscriptions. If yes, just resize mildly otherwise
03123       // more agressively
03124       ActorLink** s = static_cast<ActorLink**>(home.mm.subscriptions());
03125       unsigned int m =
03126         ((s <= base) && (base < s+home.pc.p.n_sub)) ?
03127         (n+4) : ((n+1)*3>>1);
03128       ActorLink** prop = home.alloc<ActorLink*>(m);
03129       free_and_bits += (m-n) << free_bits;
03130       // Copy entries
03131       Heap::copy<ActorLink*>(prop, base, n);
03132       home.free<ActorLink*>(base,n);
03133       base = prop;
03134     }
03135   }
03136 
03137   template<class VIC>
03138   void
03139   VarImp<VIC>::subscribe(Space& home, Propagator& p, PropCond pc,
03140                          bool assigned, ModEvent me, bool schedule) {
03141     if (assigned) {
03142       // Do not subscribe, just schedule the propagator
03143       if (schedule)
03144         VarImp<VIC>::schedule(home,p,ME_GEN_ASSIGNED);
03145     } else {
03146       enter(home,&p,pc);
03147       // Schedule propagator
03148       if (schedule && (pc != PC_GEN_ASSIGNED))
03149         VarImp<VIC>::schedule(home,p,me);
03150     }
03151   }
03152 
03153   template<class VIC>
03154   forceinline void
03155   VarImp<VIC>::subscribe(Space& home, Advisor& a, bool assigned) {
03156     if (!assigned)
03157       enter(home,&a);
03158   }
03159 
03160   template<class VIC>
03161   forceinline void
03162   VarImp<VIC>::remove(Space& home, Propagator* p, PropCond pc) {
03163     assert(pc <= pc_max);
03164     ActorLink* a = ActorLink::cast(p);
03165     // Find actor in dependency array
03166     ActorLink** f = actor(pc);
03167 #ifdef GECODE_AUDIT
03168     while (f < actorNonZero(pc+1))
03169       if (*f == a)
03170         goto found;
03171       else
03172         f++;
03173     GECODE_NEVER;
03174   found: ;
03175 #else
03176     while (*f != a) f++;
03177 #endif
03178     // Remove actor
03179     *f = *(actorNonZero(pc+1)-1);
03180     for (PropCond j = pc+1; j< pc_max+1; j++) {
03181       *(actorNonZero(j)-1) = *(actorNonZero(j+1)-1);
03182       idx(j)--;
03183     }
03184     *(actorNonZero(pc_max+1)-1) = base[entries-1];
03185     idx(pc_max+1)--;
03186     entries--;
03187     free_and_bits += 1 << free_bits;
03188     home.pc.p.n_sub -= 1;
03189   }
03190 
03191   template<class VIC>
03192   forceinline void
03193   VarImp<VIC>::remove(Space& home, Advisor* a) {
03194     // Find actor in dependency array
03195     ActorLink** f = actorNonZero(pc_max+1);
03196 #ifdef GECODE_AUDIT
03197     while (f < base+entries)
03198       if (*f == a)
03199         goto found;
03200       else
03201         f++;
03202     GECODE_NEVER;
03203   found: ;
03204 #else
03205     while (*f != a) f++;
03206 #endif
03207     // Remove actor
03208     *f = base[--entries];
03209     free_and_bits += 1 << free_bits;
03210     home.pc.p.n_sub -= 1;
03211   }
03212 
03213   template<class VIC>
03214   forceinline void
03215   VarImp<VIC>::cancel(Space& home, Propagator& p, PropCond pc, bool assigned) {
03216     if (!assigned)
03217       remove(home,&p,pc);
03218   }
03219 
03220   template<class VIC>
03221   forceinline void
03222   VarImp<VIC>::cancel(Space& home, Advisor& a, bool assigned) {
03223     if (!assigned)
03224       remove(home,&a);
03225   }
03226 
03227   template<class VIC>
03228   forceinline void
03229   VarImp<VIC>::cancel(Space& home) {
03230     unsigned int n_sub = degree();
03231     home.pc.p.n_sub -= n_sub;
03232     unsigned int n = (free_and_bits >> VIC::free_bits) + n_sub;
03233     home.free<ActorLink*>(base,n);
03234     // Must be NULL such that cloning works
03235     base = NULL;
03236     // Must be 0 such that degree works
03237     entries = 0;
03238   }
03239 
03240   template<class VIC>
03241   forceinline bool
03242   VarImp<VIC>::advise(Space& home, ModEvent me, Delta& d) {
03243     /*
03244      * An advisor that is executed might remove itself due to subsumption.
03245      * As entries are removed from front to back, the advisors must
03246      * be iterated in forward direction.
03247      */
03248     ActorLink** la = actorNonZero(pc_max+1);
03249     ActorLink** le = base+entries;
03250     if (la == le)
03251       return true;
03252     d.me = me;
03253     // An advisor that is run, might be removed during execution.
03254     // As removal is done from the back the advisors have to be executed
03255     // in inverse order.
03256     do {
03257       Advisor* a = Advisor::cast(*la);
03258       assert(!a->disposed());
03259       Propagator& p = a->propagator();
03260       switch (p.advise(home,*a,d)) {
03261       case ES_FIX:
03262         break;
03263       case ES_FAILED:
03264         p.pi.fail(home.gpi);
03265         return false;
03266       case ES_NOFIX:
03267         schedule(home,p,me);
03268         break;
03269       default:
03270         GECODE_NEVER;
03271       }
03272     } while (++la < le);
03273     return true;
03274   }
03275 
03276   template<class VIC>
03277   forceinline void
03278   VarImp<VIC>::update(VarImp<VIC>* x, ActorLink**& sub) {
03279     // this refers to the variable to be updated (clone)
03280     // x refers to the original
03281     // Recover from copy
03282     x->base = base;
03283     x->u.idx[0] = u.idx[0];
03284     if (pc_max > 0 && sizeof(ActorLink**) > sizeof(unsigned int))
03285       x->u.idx[1] = u.idx[1];
03286 
03287     ActorLink** f = x->base;
03288     unsigned int n = x->degree();
03289     ActorLink** t = sub;
03290     sub += n;
03291     base = t;
03292     // Set subscriptions using actor forwarding pointers
03293     while (n >= 4) {
03294       n -= 4;
03295       t[0]=f[0]->prev(); t[1]=f[1]->prev();
03296       t[2]=f[2]->prev(); t[3]=f[3]->prev();
03297       t += 4; f += 4;
03298     }
03299     if (n >= 2) {
03300       n -= 2;
03301       t[0]=f[0]->prev(); t[1]=f[1]->prev();
03302       t += 2; f += 2;
03303     }
03304     if (n > 0) {
03305       t[0]=f[0]->prev();
03306     }
03307   }
03308 
03309   template<class VIC>
03310   forceinline void
03311   VarImp<VIC>::update(Space& home, ActorLink**& sub) {
03312     VarImp<VIC>* x = static_cast<VarImp<VIC>*>(home.pc.c.vars_u[idx_c]);
03313     while (x != NULL) {
03314       VarImp<VIC>* n = x->next(); x->forward()->update(x,sub); x = n;
03315     }
03316   }
03317 
03318 
03319 
03320   /*
03321    * Variable disposer
03322    *
03323    */
03324   template<class VarType>
03325   VarDisposer<VarType>::VarDisposer(void) {
03326 #ifdef GECODE_HAS_VAR_DISPOSE
03327     Space::vd[VarType::idx_d] = this;
03328 #endif
03329   }
03330 
03331   template<class VarType>
03332   void
03333   VarDisposer<VarType>::dispose(Space& home, VarImpBase* _x) {
03334     VarType* x = static_cast<VarType*>(_x);
03335     do {
03336       x->dispose(home); x = static_cast<VarType*>(x->next_d());
03337     } while (x != NULL);
03338   }
03339 
03340   /*
03341    * Statistics
03342    */
03343 
03344   forceinline void
03345   StatusStatistics::reset(void) {
03346     propagate = 0;
03347     wmp = false;
03348   }
03349   forceinline
03350   StatusStatistics::StatusStatistics(void) {
03351     reset();
03352   }
03353   forceinline StatusStatistics&
03354   StatusStatistics::operator +=(const StatusStatistics& s) { 
03355     propagate += s.propagate;
03356     wmp |= s.wmp;
03357     return *this;
03358   }
03359   forceinline StatusStatistics
03360   StatusStatistics::operator +(const StatusStatistics& s) {
03361     StatusStatistics t(s);
03362     return t += *this;
03363   }
03364 
03365   forceinline void
03366   CloneStatistics::reset(void) {}
03367 
03368   forceinline
03369   CloneStatistics::CloneStatistics(void) {
03370     reset();
03371   }
03372   forceinline CloneStatistics
03373   CloneStatistics::operator +(const CloneStatistics&) {
03374     CloneStatistics s;
03375     return s;
03376   }
03377   forceinline CloneStatistics&
03378   CloneStatistics::operator +=(const CloneStatistics&) { 
03379     return *this;
03380   }
03381 
03382   forceinline void
03383   CommitStatistics::reset(void) {}
03384 
03385   forceinline
03386   CommitStatistics::CommitStatistics(void) {
03387     reset();
03388   }
03389   forceinline CommitStatistics
03390   CommitStatistics::operator +(const CommitStatistics&) {
03391     CommitStatistics s;
03392     return s;
03393   }
03394   forceinline CommitStatistics&
03395   CommitStatistics::operator +=(const CommitStatistics&) { 
03396     return *this;
03397   }
03398 
03399   /*
03400    * Cost computation
03401    *
03402    */
03403 
03404   forceinline
03405   PropCost::PropCost(PropCost::ActualCost ac0) : ac(ac0) {}
03406 
03407   forceinline PropCost
03408   PropCost::cost(PropCost::Mod m,
03409                  PropCost::ActualCost lo, PropCost::ActualCost hi,
03410                  unsigned int n) {
03411     if (n < 2)
03412       return (m == LO) ? AC_UNARY_LO : AC_UNARY_HI;
03413     else if (n == 2)
03414       return (m == LO) ? AC_BINARY_LO : AC_BINARY_HI;
03415     else if (n == 3)
03416       return (m == LO) ? AC_TERNARY_LO : AC_TERNARY_HI;
03417     else
03418       return (m == LO) ? lo : hi;
03419   }
03420 
03421   forceinline PropCost
03422   PropCost::crazy(PropCost::Mod m, unsigned int n) {
03423     return cost(m,AC_CRAZY_LO,AC_CRAZY_HI,n);
03424   }
03425   forceinline PropCost
03426   PropCost::crazy(PropCost::Mod m, int n) {
03427     assert(n >= 0);
03428     return crazy(m,static_cast<unsigned int>(n));
03429   }
03430   forceinline PropCost
03431   PropCost::cubic(PropCost::Mod m, unsigned int n) {
03432     return cost(m,AC_CUBIC_LO,AC_CUBIC_HI,n);
03433   }
03434   forceinline PropCost
03435   PropCost::cubic(PropCost::Mod m, int n) {
03436     assert(n >= 0);
03437     return cubic(m,static_cast<unsigned int>(n));
03438   }
03439   forceinline PropCost
03440   PropCost::quadratic(PropCost::Mod m, unsigned int n) {
03441     return cost(m,AC_QUADRATIC_LO,AC_QUADRATIC_HI,n);
03442   }
03443   forceinline PropCost
03444   PropCost::quadratic(PropCost::Mod m, int n) {
03445     assert(n >= 0);
03446     return quadratic(m,static_cast<unsigned int>(n));
03447   }
03448   forceinline PropCost
03449   PropCost::linear(PropCost::Mod m, unsigned int n) {
03450     return cost(m,AC_LINEAR_LO,AC_LINEAR_HI,n);
03451   }
03452   forceinline PropCost
03453   PropCost::linear(PropCost::Mod m, int n) {
03454     assert(n >= 0);
03455     return linear(m,static_cast<unsigned int>(n));
03456   }
03457   forceinline PropCost
03458   PropCost::ternary(PropCost::Mod m) {
03459     return (m == LO) ? AC_TERNARY_LO : AC_TERNARY_HI;
03460   }
03461   forceinline PropCost
03462   PropCost::binary(PropCost::Mod m) {
03463     return (m == LO) ? AC_BINARY_LO : AC_BINARY_HI;
03464   }
03465   forceinline PropCost
03466   PropCost::unary(PropCost::Mod m) {
03467     return (m == LO) ? AC_UNARY_LO : AC_UNARY_HI;
03468   }
03469 
03470   /*
03471    * Iterators for propagators and branchers of a space
03472    *
03473    */
03474   forceinline
03475   Space::Propagators::Propagators(const Space& home0) 
03476     : home(home0), q(home.pc.p.active) {
03477     while (q >= &home.pc.p.queue[0]) {
03478       if (q->next() != q) {
03479         c = q->next(); e = q; q--;
03480         return;
03481       }
03482       q--;
03483     }
03484     q = NULL;
03485     if (!home.pl.empty()) {
03486       c = Propagator::cast(home.pl.next());
03487       e = Propagator::cast(&home.pl);
03488     } else {
03489       c = e = NULL;
03490     }
03491   }
03492   forceinline bool 
03493   Space::Propagators::operator ()(void) const {
03494     return c != NULL;
03495   }
03496   forceinline void 
03497   Space::Propagators::operator ++(void) {
03498     c = c->next();
03499     if (c == e) {
03500       if (q == NULL) {
03501         c = NULL;
03502       } else {
03503         while (q >= &home.pc.p.queue[0]) {
03504           if (q->next() != q) {
03505             c = q->next(); e = q; q--;
03506             return;
03507           }
03508           q--;
03509         }
03510         q = NULL;
03511         if (!home.pl.empty()) {
03512           c = Propagator::cast(home.pl.next());
03513           e = Propagator::cast(&home.pl);
03514         } else {
03515           c = NULL;
03516         }
03517       }
03518     }
03519   }
03520   forceinline const Propagator& 
03521   Space::Propagators::propagator(void) const {
03522     return *Propagator::cast(c);
03523   }
03524 
03525   forceinline
03526   Space::Branchers::Branchers(const Space& home) 
03527     : c(Brancher::cast(home.bl.next())), e(&home.bl) {}
03528   forceinline bool 
03529   Space::Branchers::operator ()(void) const {
03530     return c != e;
03531   }
03532   forceinline void 
03533   Space::Branchers::operator ++(void) {
03534     c = c->next();
03535   }
03536   forceinline const Brancher& 
03537   Space::Branchers::brancher(void) const {
03538     return *Brancher::cast(c);
03539   }
03540 
03541   /*
03542    * Space construction support
03543    *
03544    */
03545   template<class T> 
03546   forceinline T& 
03547   Space::construct(void) {
03548     return alloc<T>(1);
03549   }
03550   template<class T, typename A1> 
03551   forceinline T& 
03552   Space::construct(A1 const& a1) {
03553     T& t = *static_cast<T*>(ralloc(sizeof(T)));
03554     new (&t) T(a1);
03555     return t;
03556   }
03557   template<class T, typename A1, typename A2> 
03558   forceinline T& 
03559   Space::construct(A1 const& a1, A2 const& a2) {
03560     T& t = *static_cast<T*>(ralloc(sizeof(T)));
03561     new (&t) T(a1,a2);
03562     return t;
03563   }
03564   template<class T, typename A1, typename A2, typename A3>
03565   forceinline T& 
03566   Space::construct(A1 const& a1, A2 const& a2, A3 const& a3) {
03567     T& t = *static_cast<T*>(ralloc(sizeof(T)));
03568     new (&t) T(a1,a2,a3);
03569     return t;
03570   }
03571   template<class T, typename A1, typename A2, typename A3, typename A4>
03572   forceinline T& 
03573   Space::construct(A1 const& a1, A2 const& a2, A3 const& a3, A4 const& a4) {
03574     T& t = *static_cast<T*>(ralloc(sizeof(T)));
03575     new (&t) T(a1,a2,a3,a4);
03576     return t;
03577   }
03578   template<class T, typename A1, typename A2, typename A3, typename A4, typename A5>
03579   forceinline T& 
03580   Space::construct(A1 const& a1, A2 const& a2, A3 const& a3, A4 const& a4, A5 const& a5) {
03581     T& t = *static_cast<T*>(ralloc(sizeof(T)));
03582     new (&t) T(a1,a2,a3,a4,a5);
03583     return t;
03584   }
03585 
03586 }
03587 
03588 // STATISTICS: kernel-core