Generated on Wed Jul 27 2011 15:08:49 for Gecode by doxygen 1.7.4
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: 2010-07-14 12:28:41 +0200 (Wed, 14 Jul 2010) $ by $Author: schulte $
00022  *     $Revision: 11184 $
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 
00077   class SharedHandle {
00078   public:
00086     class Object {
00087       friend class Space;
00088       friend class SharedHandle;
00089     private:
00091       Object* next;
00093       Object* fwd;
00095       unsigned int use_cnt;
00096     public:
00098       Object(void);
00100       virtual Object* copy(void) const = 0;
00102       virtual ~Object(void);
00104       static void* operator new(size_t s);
00106       static void  operator delete(void* p);
00107     };
00108   private:
00110     Object* o;
00112     void subscribe(void);
00114     void cancel(void);
00115   public:
00117     SharedHandle(void);
00119     SharedHandle(SharedHandle::Object* so);
00121     SharedHandle(const SharedHandle& sh);
00123     SharedHandle& operator =(const SharedHandle& sh);
00125     void update(Space& home, bool share, SharedHandle& sh);
00127     ~SharedHandle(void);
00128   protected:
00130     SharedHandle::Object* object(void) const;
00132     void object(SharedHandle::Object* n);
00133   };
00134 
00143 
00144   typedef int ModEvent;
00145 
00147   const ModEvent ME_GEN_FAILED   = -1;
00149   const ModEvent ME_GEN_NONE     =  0;
00151   const ModEvent ME_GEN_ASSIGNED =  1;
00152 
00154   typedef int PropCond;
00156   const PropCond PC_GEN_NONE     = -1;
00158   const PropCond PC_GEN_ASSIGNED = 0;
00160 
00171   typedef int ModEventDelta;
00172 
00173 }
00174 
00175 #include <gecode/kernel/var-type.hpp>
00176 
00177 namespace Gecode {
00178 
00180   class NoIdxVarImpConf {
00181   public:
00183     static const int idx_c = -1;
00185     static const int idx_d = -1;
00187     static const PropCond pc_max = PC_GEN_ASSIGNED;
00189     static const int free_bits = 0;
00191     static const int med_fst = 0;
00193     static const int med_lst = 0;
00195     static const int med_mask = 0;
00197     static Gecode::ModEvent me_combine(ModEvent me1, ModEvent me2);
00199     static bool med_update(ModEventDelta& med, ModEvent me);
00200   };
00201 
00202   forceinline ModEvent
00203   NoIdxVarImpConf::me_combine(ModEvent, ModEvent) {
00204     GECODE_NEVER; return 0;
00205   }
00206   forceinline bool
00207   NoIdxVarImpConf::med_update(ModEventDelta&, ModEvent) {
00208     GECODE_NEVER; return false;
00209   }
00210 
00211 
00212   /*
00213    * These are the classes of interest
00214    *
00215    */
00216   class ActorLink;
00217   class Actor;
00218   class Propagator;
00219   class LocalObject;
00220   class Advisor;
00221   template<class A> class Council;
00222   template<class A> class Advisors;
00223   template<class VIC> class VarImp;
00224 
00225 
00226   /*
00227    * Variable implementations
00228    *
00229    */
00230 
00238   class VarImpBase {};
00239 
00246   class GECODE_VTABLE_EXPORT VarImpDisposerBase {
00247   public:
00249     GECODE_KERNEL_EXPORT virtual void dispose(Space& home, VarImpBase* x);
00251     GECODE_KERNEL_EXPORT virtual ~VarImpDisposerBase(void);
00252   };
00253 
00260   template<class VarImp>
00261   class VarImpDisposer : public VarImpDisposerBase {
00262   public:
00264     VarImpDisposer(void);
00266     virtual void dispose(Space& home, VarImpBase* x);
00267   };
00268 
00270   class Delta {
00271     template<class VIC> friend class VarImp;
00272   private:
00274     ModEvent me;
00275   };
00276 
00284   template<class VIC>
00285   class VarImp : public VarImpBase {
00286     friend class Space;
00287     friend class Propagator;
00288     template<class VarImp> friend class VarImpDisposer;
00289   private:
00301     ActorLink** base;
00302 
00304     static const int idx_c = VIC::idx_c;
00306     static const int idx_d = VIC::idx_d;
00308     static const int free_bits = VIC::free_bits;
00310     unsigned int entries;
00312     unsigned int free_and_bits;
00314     static const Gecode::PropCond pc_max = VIC::pc_max;
00315 
00316     union {
00327       unsigned int idx[pc_max+1];
00329       VarImp<VIC>* next;
00330     } u;
00331 
00333     ActorLink** actor(PropCond pc);
00335     ActorLink** actorNonZero(PropCond pc);
00337     unsigned int& idx(PropCond pc);
00339     unsigned int idx(PropCond pc) const;
00340 
00347     void update(VarImp* x, ActorLink**& sub);
00354     static void update(Space& home, ActorLink**& sub);
00355 
00357     void enter(Space& home, Propagator* p, PropCond pc);
00359     void enter(Space& home, Advisor* a);
00361     void resize(Space& home);
00363     void remove(Space& home, Propagator* p, PropCond pc);
00365     void remove(Space& home, Advisor* a);
00366 
00367 
00368   protected:
00370     void cancel(Space& home);
00376     bool advise(Space& home, ModEvent me, Delta& d);
00377 #ifdef GECODE_HAS_VAR_DISPOSE
00378 
00379     static VarImp<VIC>* vars_d(Space& home);
00381     static void vars_d(Space& home, VarImp<VIC>* x);
00382 #endif
00383 
00384   public:
00386     VarImp(Space& home);
00388     VarImp(void);
00389 
00391 
00392 
00404     void subscribe(Space& home, Propagator& p, PropCond pc,
00405                    bool assigned, ModEvent me, bool schedule);
00411     void cancel(Space& home, Propagator& p, PropCond pc,
00412                 bool assigned);
00418     void subscribe(Space& home, Advisor& a, bool assigned);
00424     void cancel(Space& home, Advisor& a, bool assigned);
00425 
00432     unsigned int degree(void) const;
00439     double afc(void) const;
00441 
00443 
00444 
00445     VarImp(Space& home, bool share, VarImp& x);
00447     bool copied(void) const;
00449     VarImp* forward(void) const;
00451     VarImp* next(void) const;
00453 
00455 
00456 
00463     static void schedule(Space& home, Propagator& p, ModEvent me,
00464                          bool force = false);
00466     static ModEvent me(const ModEventDelta& med);
00468     static ModEventDelta med(ModEvent me);
00470     static ModEvent me_combine(ModEvent me1, ModEvent me2);
00472 
00474 
00475 
00476     static ModEvent modevent(const Delta& d);
00478 
00480 
00481 
00482     unsigned int bits(void) const;
00484     unsigned int& bits(void);
00486 
00487   protected:
00489     void schedule(Space& home, PropCond pc1, PropCond pc2, ModEvent me);
00490 
00491   public:
00493 
00494 
00495     static void* operator new(size_t,Space&);
00497     static void  operator delete(void*,Space&);
00499     static void  operator delete(void*);
00501   };
00502 
00511   enum ExecStatus {
00512     __ES_SUBSUMED       = -2, 
00513     ES_FAILED           = -1, 
00514     ES_NOFIX            =  0, 
00515     ES_OK               =  0, 
00516     ES_FIX              =  1, 
00517     ES_NOFIX_FORCE      =  2, 
00518     __ES_PARTIAL        =  2  
00519   };
00520 
00525   class PropCost {
00526     friend class Space;
00527   public:
00529     enum ActualCost {
00530       AC_CRAZY_LO     = 0, 
00531       AC_CRAZY_HI     = 0, 
00532       AC_CUBIC_LO     = 1, 
00533       AC_CUBIC_HI     = 1, 
00534       AC_QUADRATIC_LO = 2, 
00535       AC_QUADRATIC_HI = 2, 
00536       AC_LINEAR_HI    = 3, 
00537       AC_LINEAR_LO    = 4, 
00538       AC_TERNARY_HI   = 4, 
00539       AC_BINARY_HI    = 5, 
00540       AC_TERNARY_LO   = 5, 
00541       AC_BINARY_LO    = 6, 
00542       AC_UNARY_LO     = 6, 
00543       AC_UNARY_HI     = 6, 
00544       AC_MAX          = 6  
00545     };
00547     ActualCost ac;
00548   public:
00550     enum Mod {
00551       LO, 
00552       HI  
00553     };
00554   private:
00556     static PropCost cost(Mod m, ActualCost lo, ActualCost hi, unsigned int n);
00558     PropCost(ActualCost ac);
00559   public:
00561     static PropCost crazy(PropCost::Mod m, unsigned int n);
00563     static PropCost crazy(PropCost::Mod m, int n);
00565     static PropCost cubic(PropCost::Mod m, unsigned int n);
00567     static PropCost cubic(PropCost::Mod m, int n);
00569     static PropCost quadratic(PropCost::Mod m, unsigned int n);
00571     static PropCost quadratic(PropCost::Mod m, int n);
00573     static PropCost linear(PropCost::Mod m, unsigned int n);
00575     static PropCost linear(PropCost::Mod m, int n);
00577     static PropCost ternary(PropCost::Mod m);
00579     static PropCost binary(PropCost::Mod m);
00581     static PropCost unary(PropCost::Mod m);
00582   };
00583 
00584 
00589   enum ActorProperty {
00598     AP_DISPOSE = (1 << 0),
00604     AP_WEAKLY  = (1 << 1)
00605   };
00606 
00607 
00615   class ActorLink {
00616     friend class Actor;
00617     friend class Propagator;
00618     friend class Advisor;
00619     friend class Brancher;
00620     friend class LocalObject;
00621     friend class Space;
00622     template<class VIC> friend class VarImp;
00623   private:
00624     ActorLink* _next; ActorLink* _prev;
00625   public:
00627 
00628     ActorLink* prev(void) const; void prev(ActorLink*);
00629     ActorLink* next(void) const; void next(ActorLink*);
00630     ActorLink** next_ref(void);
00632 
00634     void init(void);
00636     void unlink(void);
00638     void head(ActorLink* al);
00640     void tail(ActorLink* al);
00642     bool empty(void) const;
00644     template<class T> static ActorLink* cast(T* a);
00646     template<class T> static const ActorLink* cast(const T* a);
00647   };
00648 
00649 
00654   class GECODE_VTABLE_EXPORT Actor : private ActorLink {
00655     friend class ActorLink;
00656     friend class Space;
00657     friend class Propagator;
00658     friend class Advisor;
00659     friend class Brancher;
00660     friend class LocalObject;
00661     template<class VIC> friend class VarImp;
00662     template<class A> friend class Council;
00663   private:
00665     static Actor* cast(ActorLink* al);
00667     static const Actor* cast(const ActorLink* al);
00668   public:
00670     virtual Actor* copy(Space& home, bool share) = 0;
00671 
00673 
00674 
00675     GECODE_KERNEL_EXPORT
00676     virtual size_t allocated(void) const;
00678     GECODE_KERNEL_EXPORT
00679     virtual size_t dispose(Space& home);
00681     static void* operator new(size_t s, Space& home);
00683     static void  operator delete(void* p, Space& home);
00684   private:
00685 #ifndef __GNUC__
00686 
00687     static void  operator delete(void* p);
00688 #endif
00689 
00690     static void* operator new(size_t s);
00692 #ifdef __GNUC__
00693   public:
00695     GECODE_KERNEL_EXPORT virtual ~Actor(void);
00697     static void  operator delete(void* p);
00698 #endif
00699   };
00700 
00701 
00702 
00706   class Home {
00707   protected:
00709     Space& s;
00711     Propagator* p;
00712   public:
00714 
00715 
00716     Home(Space& s, Propagator* p=NULL);
00718     operator Space&(void);
00720 
00721 
00722 
00723     Home operator ()(Propagator& p);
00725     Propagator* propagator(void) const;
00727 
00728 
00729 
00730     bool failed(void) const;
00732     void fail(void);
00734     void notice(Actor& a, ActorProperty p);
00736   };
00737 
00742   class GECODE_VTABLE_EXPORT Propagator : public Actor {
00743     friend class ActorLink;
00744     friend class Space;
00745     template<class VIC> friend class VarImp;
00746     friend class Advisor;
00747     template<class A> friend class Council;
00748   private:
00749     union {
00751       ModEventDelta med;
00753       size_t size;
00755       Gecode::ActorLink* advisors;
00756     } u;
00758     PropInfo& pi;
00760     static Propagator* cast(ActorLink* al);
00762     static const Propagator* cast(const ActorLink* al);
00763   protected:
00765     Propagator(Home home);
00767     Propagator(Space& home, bool share, Propagator& p);
00768 
00769   public:
00771 
00772 
00795     virtual ExecStatus propagate(Space& home, const ModEventDelta& med) = 0;
00797     virtual PropCost cost(const Space& home, const ModEventDelta& med) const = 0;
00833     GECODE_KERNEL_EXPORT
00834     virtual ExecStatus advise(Space& home, Advisor& a, const Delta& d);
00836 
00837 
00838 
00839     double afc(void) const;
00841   };
00842 
00843 
00851   template<class A>
00852   class Council {
00853     friend class Advisor;
00854     friend class Advisors<A>;
00855   private:
00857     mutable ActorLink* advisors;
00858   public:
00860     Council(void);
00862     Council(Space& home);
00864     bool empty(void) const;
00866     void update(Space& home, bool share, Council<A>& c);
00868     void dispose(Space& home);
00869   };
00870 
00871 
00876   template<class A>
00877   class Advisors {
00878   private:
00880     ActorLink* a;
00881   public:
00883     Advisors(const Council<A>& c);
00885     bool operator ()(void) const;
00887     void operator ++(void);
00889     A& advisor(void) const;
00890   };
00891 
00892 
00903   class Advisor : private ActorLink {
00904     template<class VIC> friend class VarImp;
00905     template<class A> friend class Council;
00906     template<class A> friend class Advisors;
00907   private:
00909     bool disposed(void) const;
00911     static Advisor* cast(ActorLink* al);
00913     static const Advisor* cast(const ActorLink* al);
00914   protected:
00916     Propagator& propagator(void) const;
00917   public:
00919     template<class A>
00920     Advisor(Space& home, Propagator& p, Council<A>& c);
00922     Advisor(Space& home, bool share, Advisor& a);
00923 
00925 
00926 
00927     template<class A>
00928     void dispose(Space& home, Council<A>& c);
00930     static void* operator new(size_t s, Space& home);
00932     static void  operator delete(void* p, Space& home);
00934   private:
00935 #ifndef __GNUC__
00936 
00937     static void  operator delete(void* p);
00938 #endif
00939 
00940     static void* operator new(size_t s);
00941   };
00942 
00943 
00944   class Brancher;
00945 
00955   class Choice {
00956     friend class Space;
00957   private:
00958     unsigned int _id;  
00959     unsigned int _alt; 
00960 
00962     unsigned int id(void) const;
00963   protected:
00965     Choice(const Brancher& b, const unsigned int a);
00966   public:
00968     unsigned int alternatives(void) const;
00970     GECODE_KERNEL_EXPORT virtual ~Choice(void);
00972     virtual size_t size(void) const = 0;
00974     static void* operator new(size_t);
00976     static void  operator delete(void*);
00977   };
00978 
00988   class GECODE_VTABLE_EXPORT Brancher : public Actor {
00989     friend class ActorLink;
00990     friend class Space;
00991     friend class Choice;
00992   private:
00994     unsigned int _id;
00996     static Brancher* cast(ActorLink* al);
00998     static const Brancher* cast(const ActorLink* al);
00999   protected:
01001     Brancher(Home home);
01003     Brancher(Space& home, bool share, Brancher& b);
01004   public:
01006 
01007 
01015     virtual bool status(const Space& home) const = 0;
01023     virtual const Choice* choice(Space& home) = 0;
01030     virtual ExecStatus commit(Space& home, const Choice& c, 
01031                               unsigned int a) = 0;
01033     unsigned int id(void) const;
01035   };
01036 
01044   class LocalObject : public Actor {
01045     friend class ActorLink;
01046     friend class Space;
01047     friend class LocalHandle;
01048   protected:
01050     LocalObject(Home home);
01052     LocalObject(Space& home, bool share, LocalObject& l);
01054     static LocalObject* cast(ActorLink* al);
01056     static const LocalObject* cast(const ActorLink* al);
01057   private:
01059     GECODE_KERNEL_EXPORT void fwdcopy(Space& home, bool share);
01060   public:
01062     LocalObject* fwd(Space& home, bool share);
01063   };
01064 
01071   class LocalHandle {
01072   private:
01074     LocalObject* o;
01075   protected:
01077     LocalHandle(void);
01079     LocalHandle(LocalObject* lo);
01081     LocalHandle(const LocalHandle& lh);
01082   public:
01084     LocalHandle& operator =(const LocalHandle& lh);
01086     void update(Space& home, bool share, LocalHandle& lh);
01088     ~LocalHandle(void);
01089   protected:
01091     LocalObject* object(void) const;
01093     void object(LocalObject* n);
01094   };
01095 
01096 
01101   enum SpaceStatus {
01102     SS_FAILED, 
01103     SS_SOLVED, 
01104     SS_BRANCH  
01105   };
01106 
01111   class StatusStatistics {
01112   public:
01114     unsigned long int propagate;
01116     bool wmp;
01118     StatusStatistics(void);
01120     void reset(void);
01122     StatusStatistics operator +(const StatusStatistics& s);
01124     StatusStatistics& operator +=(const StatusStatistics& s);
01125   };
01126 
01131   class CloneStatistics {
01132   public:
01134     CloneStatistics(void);
01136     void reset(void);
01138     CloneStatistics operator +(const CloneStatistics& s);
01140     CloneStatistics& operator +=(const CloneStatistics& s);
01141   };
01142 
01147   class CommitStatistics {
01148   public:
01150     CommitStatistics(void);
01152     void reset(void);
01154     CommitStatistics operator +(const CommitStatistics& s);
01156     CommitStatistics& operator +=(const CommitStatistics& s);
01157   };
01158 
01162   class GECODE_VTABLE_EXPORT Space {
01163     friend class Actor;
01164     friend class Propagator;
01165     friend class Brancher;
01166     friend class Advisor;
01167     template<class VIC> friend class VarImp;
01168     template<class VarImp> friend class VarImpDisposer;
01169     friend class SharedHandle;
01170     friend class LocalObject;
01171     friend class Region;
01172   private:
01174     SharedMemory* sm;
01176     MemoryManager mm;
01178     GlobalPropInfo gpi;
01180     ActorLink pl;
01182     ActorLink bl;
01188     Brancher* b_status;
01200     Brancher* b_commit;
01201     union {
01203       struct {
01216         ActorLink* active;
01218         ActorLink queue[PropCost::AC_MAX+1];
01220         unsigned int branch_id;
01222         unsigned int n_sub;
01223       } p;
01225       struct {
01227         VarImpBase* vars_u[AllVarConf::idx_c];
01229         VarImpBase* vars_noidx;
01231         SharedHandle::Object* shared;
01233         LocalObject* local;
01234       } c;
01235     } pc;
01237     void enqueue(Propagator* p);
01242 #ifdef GECODE_HAS_VAR_DISPOSE
01243 
01244     GECODE_KERNEL_EXPORT static VarImpDisposerBase* vd[AllVarConf::idx_d];
01246     VarImpBase* _vars_d[AllVarConf::idx_d];
01248     template<class VIC> VarImpBase* vars_d(void) const;
01250     template<class VIC> void vars_d(VarImpBase* x);
01251 #endif
01252 
01253     void update(ActorLink** sub);
01255 
01257     Actor** d_fst;
01259     Actor** d_cur;
01261     Actor** d_lst;
01263     GECODE_KERNEL_EXPORT void d_resize(void);
01264 
01272     unsigned int n_wmp;
01273 
01275     GECODE_KERNEL_EXPORT static StatusStatistics unused_status;
01277     GECODE_KERNEL_EXPORT static CloneStatistics unused_clone;
01279     GECODE_KERNEL_EXPORT static CommitStatistics unused_commit;
01281     GECODE_KERNEL_EXPORT static unsigned long int unused_uli;
01283     GECODE_KERNEL_EXPORT static bool unused_b;
01284 
01299     GECODE_KERNEL_EXPORT Space* _clone(bool share=true);
01300 
01333     GECODE_KERNEL_EXPORT
01334     void _commit(const Choice& c, unsigned int a);
01335 
01336   public:
01341     GECODE_KERNEL_EXPORT Space(void);
01346     GECODE_KERNEL_EXPORT virtual ~Space(void);
01357     GECODE_KERNEL_EXPORT Space(bool share, Space& s);
01364     virtual Space* copy(bool share) = 0;
01376     GECODE_KERNEL_EXPORT virtual void constrain(const Space& best);
01381     static void* operator new(size_t);
01386     static void  operator delete(void*);
01387 
01388 
01389     /*
01390      * Member functions for search engines
01391      *
01392      */
01393 
01405     GECODE_KERNEL_EXPORT
01406     SpaceStatus status(StatusStatistics& stat=unused_status);
01407 
01439     GECODE_KERNEL_EXPORT
01440     const Choice* choice(void);
01441 
01459     Space* clone(bool share=true, CloneStatistics& stat=unused_clone) const;
01460 
01495     void commit(const Choice& c, unsigned int a,
01496                 CommitStatistics& stat=unused_commit);
01497 
01505     void notice(Actor& a, ActorProperty p);
01513     void ignore(Actor& a, ActorProperty p);
01514 
01515 
01526     ExecStatus ES_SUBSUMED(Propagator& p);
01541     ExecStatus ES_SUBSUMED_DISPOSED(Propagator& p, size_t s);
01552     ExecStatus ES_FIX_PARTIAL(Propagator& p, const ModEventDelta& med);
01563     ExecStatus ES_NOFIX_PARTIAL(Propagator& p, const ModEventDelta& med);
01564     
01575     template<class A>
01576     ExecStatus ES_FIX_DISPOSE(Council<A>& c, A& a);
01587     template<class A>
01588     ExecStatus ES_NOFIX_DISPOSE(Council<A>& c, A& a);
01600     template<class A>
01601     ExecStatus ES_NOFIX_DISPOSE_FORCE(Council<A>& c, A& a);
01602     
01610     void fail(void);
01619     bool failed(void) const;
01624     bool stable(void) const;
01631     GECODE_KERNEL_EXPORT unsigned int propagators(void) const;
01638     GECODE_KERNEL_EXPORT unsigned int branchers(void) const;
01639 
01641 
01642 
01643     Home operator ()(Propagator& p);
01645 
01657     template<class T>
01658     T* alloc(long unsigned int n);
01665     template<class T>
01666     T* alloc(long int n);
01673     template<class T>
01674     T* alloc(unsigned int n);
01681     template<class T>
01682     T* alloc(int n);
01692     template<class T>
01693     void free(T* b, long unsigned int n);
01703     template<class T>
01704     void free(T* b, long int n);
01714     template<class T>
01715     void free(T* b, unsigned int n);
01725     template<class T>
01726     void free(T* b, int n);
01738     template<class T>
01739     T* realloc(T* b, long unsigned int n, long unsigned int m);
01751     template<class T>
01752     T* realloc(T* b, long int n, long int m);
01764     template<class T>
01765     T* realloc(T* b, unsigned int n, unsigned int m);
01777     template<class T>
01778     T* realloc(T* b, int n, int m);
01786     template<class T>
01787     T** realloc(T** b, long unsigned int n, long unsigned int m);
01795     template<class T>
01796     T** realloc(T** b, long int n, long int m);
01804     template<class T>
01805     T** realloc(T** b, unsigned int n, unsigned int m);
01813     template<class T>
01814     T** realloc(T** b, int n, int m);
01816     void* ralloc(size_t s);
01818     void rfree(void* p, size_t s);
01820     void* rrealloc(void* b, size_t n, size_t m);
01822     template<size_t> void* fl_alloc(void);
01828     template<size_t> void  fl_dispose(FreeList* f, FreeList* l);
01835     size_t allocated(void) const;
01845     GECODE_KERNEL_EXPORT void flush(void);
01847 
01848 
01849 
01852     template<class T> 
01853     T& construct(void);
01859     template<class T, typename A1> 
01860     T& construct(A1 const& a1);
01866     template<class T, typename A1, typename A2> 
01867     T& construct(A1 const& a1, A2 const& a2);
01873     template<class T, typename A1, typename A2, typename A3>
01874     T& construct(A1 const& a1, A2 const& a2, A3 const& a3);
01880     template<class T, typename A1, typename A2, typename A3, typename A4>
01881     T& construct(A1 const& a1, A2 const& a2, A3 const& a3, A4 const& a4);
01887     template<class T, typename A1, typename A2, typename A3, typename A4, typename A5>
01888     T& construct(A1 const& a1, A2 const& a2, A3 const& a3, A4 const& a4, A5 const& a5);
01890 
01896     class Propagators {
01897     private:
01899       const Space& home;
01901       const ActorLink* q;
01903       const ActorLink* c;
01905       const ActorLink* e;
01906     public:
01908       Propagators(const Space& home);
01910       bool operator ()(void) const;
01912       void operator ++(void);
01914       const Propagator& propagator(void) const;
01915     };
01916 
01922     class Branchers {
01923     private:
01925       const ActorLink* c;
01927       const ActorLink* e;
01928     public:
01930       Branchers(const Space& home);
01932       bool operator ()(void) const;
01934       void operator ++(void);
01936       const Brancher& brancher(void) const;
01937     };    
01938   };
01939 
01940 
01941 
01942 
01943   /*
01944    * Memory management
01945    *
01946    */
01947 
01948   // Heap allocated
01949   forceinline void*
01950   SharedHandle::Object::operator new(size_t s) {
01951     return heap.ralloc(s);
01952   }
01953   forceinline void
01954   SharedHandle::Object::operator delete(void* p) {
01955     heap.rfree(p);
01956   }
01957 
01958   forceinline void*
01959   Space::operator new(size_t s) {
01960     return heap.ralloc(s);
01961   }
01962   forceinline void
01963   Space::operator delete(void* p) {
01964     heap.rfree(p);
01965   }
01966 
01967   forceinline void
01968   Choice::operator delete(void* p) {
01969     heap.rfree(p);
01970   }
01971   forceinline void*
01972   Choice::operator new(size_t s) {
01973     return heap.ralloc(s);
01974   }
01975 
01976   // Space allocation: general space heaps and free lists
01977   forceinline void*
01978   Space::ralloc(size_t s) {
01979     return mm.alloc(sm,s);
01980   }
01981   forceinline void
01982   Space::rfree(void* p, size_t s) {
01983     return mm.reuse(p,s);
01984   }
01985   forceinline void*
01986   Space::rrealloc(void* _b, size_t n, size_t m) {
01987     char* b = static_cast<char*>(_b);
01988     if (n < m) {
01989       char* p = static_cast<char*>(ralloc(m));
01990       memcpy(p,b,n);
01991       rfree(b,n);
01992       return p;
01993     } else {
01994       rfree(b+m,m-n);
01995       return b;
01996     }
01997   }
01998 
01999   template<size_t s>
02000   forceinline void*
02001   Space::fl_alloc(void) {
02002     return mm.template fl_alloc<s>(sm);
02003   }
02004   template<size_t s>
02005   forceinline void
02006   Space::fl_dispose(FreeList* f, FreeList* l) {
02007     mm.template fl_dispose<s>(f,l);
02008   }
02009 
02010   forceinline size_t
02011   Space::allocated(void) const {
02012     size_t s = mm.allocated();
02013     for (Actor** a = d_fst; a < d_cur; a++)
02014       s += (*a)->allocated();
02015     return s;
02016   }
02017 
02018   /*
02019    * Typed allocation routines
02020    *
02021    */
02022   template<class T>
02023   forceinline T*
02024   Space::alloc(long unsigned int n) {
02025     T* p = static_cast<T*>(ralloc(sizeof(T)*n));
02026     for (long unsigned int i=n; i--; )
02027       (void) new (p+i) T();
02028     return p;
02029   }
02030   template<class T>
02031   forceinline T*
02032   Space::alloc(long int n) {
02033     assert(n >= 0);
02034     return alloc<T>(static_cast<long unsigned int>(n));
02035   }
02036   template<class T>
02037   forceinline T*
02038   Space::alloc(unsigned int n) {
02039     return alloc<T>(static_cast<long unsigned int>(n));
02040   }
02041   template<class T>
02042   forceinline T*
02043   Space::alloc(int n) {
02044     assert(n >= 0);
02045     return alloc<T>(static_cast<long unsigned int>(n));
02046   }
02047 
02048   template<class T>
02049   forceinline void
02050   Space::free(T* b, long unsigned int n) {
02051     for (long unsigned int i=n; i--; )
02052       b[i].~T();
02053     rfree(b,n*sizeof(T));
02054   }
02055   template<class T>
02056   forceinline void
02057   Space::free(T* b, long int n) {
02058     assert(n >= 0);
02059     free<T>(b,static_cast<long unsigned int>(n));
02060   }
02061   template<class T>
02062   forceinline void
02063   Space::free(T* b, unsigned int n) {
02064     free<T>(b,static_cast<long unsigned int>(n));
02065   }
02066   template<class T>
02067   forceinline void
02068   Space::free(T* b, int n) {
02069     assert(n >= 0);
02070     free<T>(b,static_cast<long unsigned int>(n));
02071   }
02072 
02073   template<class T>
02074   forceinline T*
02075   Space::realloc(T* b, long unsigned int n, long unsigned int m) {
02076     if (n < m) {
02077       T* p = static_cast<T*>(ralloc(sizeof(T)*m));
02078       for (long unsigned int i=n; i--; )
02079         (void) new (p+i) T(b[i]);
02080       for (long unsigned int i=n; i<m; i++)
02081         (void) new (p+i) T();
02082       free<T>(b,n);
02083       return p;
02084     } else {
02085       free<T>(b+m,m-n);
02086       return b;
02087     }
02088   }
02089   template<class T>
02090   forceinline T*
02091   Space::realloc(T* b, long int n, long int m) {
02092     assert((n >= 0) && (m >= 0));
02093     return realloc<T>(b,static_cast<long unsigned int>(n),
02094                       static_cast<long unsigned int>(m));
02095   }
02096   template<class T>
02097   forceinline T*
02098   Space::realloc(T* b, unsigned int n, unsigned int m) {
02099     return realloc<T>(b,static_cast<long unsigned int>(n),
02100                       static_cast<long unsigned int>(m));
02101   }
02102   template<class T>
02103   forceinline T*
02104   Space::realloc(T* b, int n, int m) {
02105     assert((n >= 0) && (m >= 0));
02106     return realloc<T>(b,static_cast<long unsigned int>(n),
02107                       static_cast<long unsigned int>(m));
02108   }
02109 
02110 #define GECODE_KERNEL_REALLOC(T)                                        \
02111   template<>                                                            \
02112   forceinline T*                                                        \
02113   Space::realloc<T>(T* b, long unsigned int n, long unsigned int m) {   \
02114     return static_cast<T*>(rrealloc(b,n*sizeof(T),m*sizeof(T)));        \
02115   }                                                                     \
02116   template<>                                                            \
02117   forceinline T*                                                        \
02118   Space::realloc<T>(T* b, long int n, long int m) {                     \
02119     assert((n >= 0) && (m >= 0));                                       \
02120     return realloc<T>(b,static_cast<long unsigned int>(n),              \
02121                       static_cast<long unsigned int>(m));               \
02122   }                                                                     \
02123   template<>                                                            \
02124   forceinline T*                                                        \
02125   Space::realloc<T>(T* b, unsigned int n, unsigned int m) {             \
02126     return realloc<T>(b,static_cast<long unsigned int>(n),              \
02127                       static_cast<long unsigned int>(m));               \
02128   }                                                                     \
02129   template<>                                                            \
02130   forceinline T*                                                        \
02131   Space::realloc<T>(T* b, int n, int m) {                               \
02132     assert((n >= 0) && (m >= 0));                                       \
02133     return realloc<T>(b,static_cast<long unsigned int>(n),              \
02134                       static_cast<long unsigned int>(m));               \
02135   }
02136 
02137   GECODE_KERNEL_REALLOC(bool)
02138   GECODE_KERNEL_REALLOC(signed char)
02139   GECODE_KERNEL_REALLOC(unsigned char)
02140   GECODE_KERNEL_REALLOC(signed short int)
02141   GECODE_KERNEL_REALLOC(unsigned short int)
02142   GECODE_KERNEL_REALLOC(signed int)
02143   GECODE_KERNEL_REALLOC(unsigned int)
02144   GECODE_KERNEL_REALLOC(signed long int)
02145   GECODE_KERNEL_REALLOC(unsigned long int)
02146   GECODE_KERNEL_REALLOC(float)
02147   GECODE_KERNEL_REALLOC(double)
02148 
02149 #undef GECODE_KERNEL_REALLOC
02150 
02151   template<class T>
02152   forceinline T**
02153   Space::realloc(T** b, long unsigned int n, long unsigned int m) {
02154     return static_cast<T**>(rrealloc(b,n*sizeof(T),m*sizeof(T*)));
02155   }
02156   template<class T>
02157   forceinline T**
02158   Space::realloc(T** b, long int n, long int m) {
02159     assert((n >= 0) && (m >= 0));
02160     return realloc<T*>(b,static_cast<long unsigned int>(n),
02161                        static_cast<long unsigned int>(m));
02162   }
02163   template<class T>
02164   forceinline T**
02165   Space::realloc(T** b, unsigned int n, unsigned int m) {
02166     return realloc<T*>(b,static_cast<long unsigned int>(n),
02167                        static_cast<long unsigned int>(m));
02168   }
02169   template<class T>
02170   forceinline T**
02171   Space::realloc(T** b, int n, int m) {
02172     assert((n >= 0) && (m >= 0));
02173     return realloc<T*>(b,static_cast<long unsigned int>(n),
02174                        static_cast<long unsigned int>(m));
02175   }
02176 
02177 
02178 #ifdef GECODE_HAS_VAR_DISPOSE
02179   template<class VIC>
02180   forceinline VarImpBase*
02181   Space::vars_d(void) const {
02182     return _vars_d[VIC::idx_d];
02183   }
02184   template<class VIC>
02185   forceinline void
02186   Space::vars_d(VarImpBase* x) {
02187     _vars_d[VIC::idx_d] = x;
02188   }
02189 #endif
02190 
02191   // Space allocated entities: Actors, variable implementations, and advisors
02192   forceinline void
02193   Actor::operator delete(void*) {}
02194   forceinline void
02195   Actor::operator delete(void*, Space&) {}
02196   forceinline void*
02197   Actor::operator new(size_t s, Space& home) {
02198     return home.ralloc(s);
02199   }
02200 
02201   template<class VIC>
02202   forceinline void
02203   VarImp<VIC>::operator delete(void*) {}
02204   template<class VIC>
02205   forceinline void
02206   VarImp<VIC>::operator delete(void*, Space&) {}
02207   template<class VIC>
02208   forceinline void*
02209   VarImp<VIC>::operator new(size_t s, Space& home) {
02210     return home.ralloc(s);
02211   }
02212 
02213 #ifndef __GNUC__
02214   forceinline void
02215   Advisor::operator delete(void*) {}
02216 #endif
02217   forceinline void
02218   Advisor::operator delete(void*, Space&) {}
02219   forceinline void*
02220   Advisor::operator new(size_t s, Space& home) {
02221     return home.ralloc(s);
02222   }
02223 
02224   /*
02225    * Shared objects and handles
02226    *
02227    */
02228   forceinline
02229   SharedHandle::Object::Object(void)
02230     : next(NULL), fwd(NULL), use_cnt(0) {}
02231   forceinline
02232   SharedHandle::Object::~Object(void) {
02233     assert(use_cnt == 0);
02234   }
02235 
02236   forceinline SharedHandle::Object*
02237   SharedHandle::object(void) const {
02238     return o;
02239   }
02240   forceinline void
02241   SharedHandle::subscribe(void) {
02242     if (o != NULL) o->use_cnt++;
02243   }
02244   forceinline void
02245   SharedHandle::cancel(void) {
02246     if ((o != NULL) && (--o->use_cnt == 0))
02247       delete o;
02248     o=NULL;
02249   }
02250   forceinline void
02251   SharedHandle::object(SharedHandle::Object* n) {
02252     if (n != o) {
02253       cancel(); o=n; subscribe();
02254     }
02255   }
02256   forceinline
02257   SharedHandle::SharedHandle(void) : o(NULL) {}
02258   forceinline
02259   SharedHandle::SharedHandle(SharedHandle::Object* so) : o(so) {
02260     subscribe();
02261   }
02262   forceinline
02263   SharedHandle::SharedHandle(const SharedHandle& sh) : o(sh.o) {
02264     subscribe();
02265   }
02266   forceinline SharedHandle&
02267   SharedHandle::operator =(const SharedHandle& sh) {
02268     if (&sh != this) {
02269       cancel(); o=sh.o; subscribe();
02270     }
02271     return *this;
02272   }
02273   forceinline void
02274   SharedHandle::update(Space& home, bool share, SharedHandle& sh) {
02275     if (sh.o == NULL) {
02276       o=NULL; return;
02277     } else if (share) {
02278       o=sh.o;
02279     } else if (sh.o->fwd != NULL) {
02280       o=sh.o->fwd;
02281     } else {
02282       o = sh.o->copy();
02283       sh.o->fwd = o;
02284       sh.o->next = home.pc.c.shared;
02285       home.pc.c.shared = sh.o;
02286     }
02287     subscribe();
02288   }
02289   forceinline
02290   SharedHandle::~SharedHandle(void) {
02291     cancel();
02292   }
02293 
02294 
02295 
02296   /*
02297    * ActorLink
02298    *
02299    */
02300   forceinline ActorLink*
02301   ActorLink::prev(void) const {
02302     return _prev;
02303   }
02304 
02305   forceinline ActorLink*
02306   ActorLink::next(void) const {
02307     return _next;
02308   }
02309 
02310   forceinline ActorLink**
02311   ActorLink::next_ref(void) {
02312     return &_next;
02313   }
02314 
02315   forceinline void
02316   ActorLink::prev(ActorLink* al) {
02317     _prev = al;
02318   }
02319 
02320   forceinline void
02321   ActorLink::next(ActorLink* al) {
02322     _next = al;
02323   }
02324 
02325   forceinline void
02326   ActorLink::unlink(void) {
02327     ActorLink* p = _prev; ActorLink* n = _next;
02328     p->_next = n; n->_prev = p;
02329   }
02330 
02331   forceinline void
02332   ActorLink::init(void) {
02333     _next = this; _prev =this;
02334   }
02335 
02336   forceinline void
02337   ActorLink::head(ActorLink* a) {
02338     // Inserts al at head of link-chain (that is, after this)
02339     ActorLink* n = _next;
02340     this->_next = a; a->_prev = this;
02341     a->_next = n; n->_prev = a;
02342   }
02343 
02344   forceinline void
02345   ActorLink::tail(ActorLink* a) {
02346     // Inserts al at tail of link-chain (that is, before this)
02347     ActorLink* p = _prev;
02348     a->_next = this; this->_prev = a;
02349     p->_next = a; a->_prev = p;
02350   }
02351 
02352   forceinline bool
02353   ActorLink::empty(void) const {
02354     return _next == this;
02355   }
02356 
02357   template<class T>
02358   forceinline ActorLink*
02359   ActorLink::cast(T* a) {
02360     // Turning al into a reference is for gcc, assume is for MSVC
02361     GECODE_NOT_NULL(a);
02362     ActorLink& t = *a;
02363     return static_cast<ActorLink*>(&t);
02364   }
02365 
02366   template<class T>
02367   forceinline const ActorLink*
02368   ActorLink::cast(const T* a) {
02369     // Turning al into a reference is for gcc, assume is for MSVC
02370     GECODE_NOT_NULL(a);
02371     const ActorLink& t = *a;
02372     return static_cast<const ActorLink*>(&t);
02373   }
02374 
02375 
02376   /*
02377    * Actor
02378    *
02379    */
02380   forceinline Actor*
02381   Actor::cast(ActorLink* al) {
02382     // Turning al into a reference is for gcc, assume is for MSVC
02383     GECODE_NOT_NULL(al);
02384     ActorLink& t = *al;
02385     return static_cast<Actor*>(&t);
02386   }
02387 
02388   forceinline const Actor*
02389   Actor::cast(const ActorLink* al) {
02390     // Turning al into a reference is for gcc, assume is for MSVC
02391     GECODE_NOT_NULL(al);
02392     const ActorLink& t = *al;
02393     return static_cast<const Actor*>(&t);
02394   }
02395 
02396   forceinline void
02397   Space::notice(Actor& a, ActorProperty p) {
02398     if (p & AP_DISPOSE) {
02399       if (d_cur == d_lst)
02400         d_resize();
02401       *(d_cur++) = &a;
02402     }
02403     if (p & AP_WEAKLY) {
02404       if (n_wmp == 0)
02405         n_wmp = 2;
02406       else
02407         n_wmp++;
02408     }
02409   }
02410 
02411   forceinline void
02412   Home::notice(Actor& a, ActorProperty p) {
02413     s.notice(a,p);
02414   }
02415 
02416   forceinline void
02417   Space::ignore(Actor& a, ActorProperty p) {
02418     if (p & AP_DISPOSE) {
02419       // Check wether array has already been discarded as space
02420       // deletion is already in progress
02421       Actor** f = d_fst;
02422       if (f != NULL) {
02423         while (&a != *f)
02424           f++;
02425         *f = *(--d_cur);
02426       }
02427     }
02428     if (p & AP_WEAKLY) {
02429       assert(n_wmp > 1);
02430       n_wmp--;
02431     }
02432   }
02433 
02434   forceinline Space*
02435   Space::clone(bool share, CloneStatistics&) const {
02436     // Clone is only const for search engines. During cloning, several data
02437     // structures are updated (e.g. forwarding pointers), so we have to
02438     // cast away the constness.
02439     return const_cast<Space*>(this)->_clone(share);
02440   }
02441 
02442   forceinline void
02443   Space::commit(const Choice& c, unsigned int a, CommitStatistics&) {
02444     _commit(c,a);
02445   }
02446 
02447   forceinline size_t
02448   Actor::dispose(Space&) {
02449     return sizeof(*this);
02450   }
02451 
02452 
02453   /*
02454    * Home for posting actors
02455    *
02456    */
02457   forceinline
02458   Home::Home(Space& s0, Propagator* p0) : s(s0), p(p0) {}
02459   forceinline
02460   Home::operator Space&(void) { 
02461     return s; 
02462   }
02463   forceinline Home
02464   Home::operator ()(Propagator& p) {
02465     return Home(s,&p);
02466   }
02467   forceinline Home
02468   Space::operator ()(Propagator& p) {
02469     return Home(*this,&p);
02470   }
02471   forceinline Propagator*
02472   Home::propagator(void) const {
02473     return p;
02474   }
02475 
02476   /*
02477    * Propagator
02478    *
02479    */
02480   forceinline Propagator*
02481   Propagator::cast(ActorLink* al) {
02482     // Turning al into a reference is for gcc, assume is for MSVC
02483     GECODE_NOT_NULL(al);
02484     ActorLink& t = *al;
02485     return static_cast<Propagator*>(&t);
02486   }
02487 
02488   forceinline const Propagator*
02489   Propagator::cast(const ActorLink* al) {
02490     // Turning al into a reference is for gcc, assume is for MSVC
02491     GECODE_NOT_NULL(al);
02492     const ActorLink& t = *al;
02493     return static_cast<const Propagator*>(&t);
02494   }
02495 
02496   forceinline
02497   Propagator::Propagator(Home home) 
02498     : pi((home.propagator() != NULL) ?
02499          // Inherit propagator information
02500          home.propagator()->pi :
02501          // New propagator information
02502          static_cast<Space&>(home).gpi.allocate()) {
02503     u.advisors = NULL;
02504     assert((u.med == 0) && (u.size == 0));
02505     static_cast<Space&>(home).pl.head(this);
02506   }
02507 
02508   forceinline
02509   Propagator::Propagator(Space&, bool, Propagator& p) 
02510     : pi(p.pi) {
02511     u.advisors = NULL;
02512     assert((u.med == 0) && (u.size == 0));
02513     // Set forwarding pointer
02514     p.prev(this);
02515   }
02516 
02517   forceinline double
02518   Propagator::afc(void) const {
02519     return pi.afc();
02520   }
02521 
02522   forceinline ExecStatus
02523   Space::ES_SUBSUMED_DISPOSED(Propagator& p, size_t s) {
02524     p.u.size = s;
02525     return __ES_SUBSUMED;
02526   }
02527 
02528   forceinline ExecStatus
02529   Space::ES_SUBSUMED(Propagator& p) {
02530     p.u.size = p.dispose(*this);
02531     return __ES_SUBSUMED;
02532   }
02533 
02534   forceinline ExecStatus
02535   Space::ES_FIX_PARTIAL(Propagator& p, const ModEventDelta& med) {
02536     p.u.med = med;
02537     assert(p.u.med != 0);
02538     return __ES_PARTIAL;
02539   }
02540 
02541   forceinline ExecStatus
02542   Space::ES_NOFIX_PARTIAL(Propagator& p, const ModEventDelta& med) {
02543     p.u.med = AllVarConf::med_combine(p.u.med,med);
02544     assert(p.u.med != 0);
02545     return __ES_PARTIAL;
02546   }
02547 
02548 
02549 
02550   /*
02551    * Brancher
02552    *
02553    */
02554   forceinline Brancher*
02555   Brancher::cast(ActorLink* al) {
02556     // Turning al into a reference is for gcc, assume is for MSVC
02557     GECODE_NOT_NULL(al);
02558     ActorLink& t = *al;
02559     return static_cast<Brancher*>(&t);
02560   }
02561 
02562   forceinline const Brancher*
02563   Brancher::cast(const ActorLink* al) {
02564     // Turning al into a reference is for gcc, assume is for MSVC
02565     GECODE_NOT_NULL(al);
02566     const ActorLink& t = *al;
02567     return static_cast<const Brancher*>(&t);
02568   }
02569 
02570   forceinline
02571   Brancher::Brancher(Home home) :
02572     _id(static_cast<Space&>(home).pc.p.branch_id++) {
02573     if (static_cast<Space&>(home).pc.p.branch_id == 0U)
02574       throw TooManyBranchers("Brancher::Brancher");
02575     // If no brancher available, make it the first one
02576     if (static_cast<Space&>(home).b_status == &static_cast<Space&>(home).bl) {
02577       static_cast<Space&>(home).b_status = this;
02578       if (static_cast<Space&>(home).b_commit == &static_cast<Space&>(home).bl)
02579         static_cast<Space&>(home).b_commit = this;
02580     }
02581     static_cast<Space&>(home).bl.tail(this);
02582   }
02583 
02584   forceinline
02585   Brancher::Brancher(Space&, bool, Brancher& b)
02586     : _id(b._id) {
02587     // Set forwarding pointer
02588     b.prev(this);
02589   }
02590 
02591   forceinline unsigned int
02592   Brancher::id(void) const {
02593     return _id;
02594   }
02595 
02596   /*
02597    * Local objects
02598    *
02599    */
02600 
02601   forceinline LocalObject*
02602   LocalObject::cast(ActorLink* al) {
02603     // Turning al into a reference is for gcc, assume is for MSVC
02604     GECODE_NOT_NULL(al);
02605     ActorLink& t = *al;
02606     return static_cast<LocalObject*>(&t);
02607   }
02608 
02609   forceinline const LocalObject*
02610   LocalObject::cast(const ActorLink* al) {
02611     // Turning al into a reference is for gcc, assume is for MSVC
02612     GECODE_NOT_NULL(al);
02613     const ActorLink& t = *al;
02614     return static_cast<const LocalObject*>(&t);
02615   }
02616 
02617   forceinline
02618   LocalObject::LocalObject(Home) {
02619     ActorLink::cast(this)->prev(NULL);
02620   }
02621 
02622   forceinline
02623   LocalObject::LocalObject(Space&,bool,LocalObject&) {
02624     ActorLink::cast(this)->prev(NULL);
02625   }
02626 
02627   forceinline LocalObject*
02628   LocalObject::fwd(Space& home, bool share) {
02629     if (prev() == NULL)
02630       fwdcopy(home,share);
02631     return LocalObject::cast(prev());
02632   }
02633 
02634   forceinline
02635   LocalHandle::LocalHandle(void) : o(NULL) {}
02636   forceinline
02637   LocalHandle::LocalHandle(LocalObject* lo) : o(lo) {}
02638   forceinline
02639   LocalHandle::LocalHandle(const LocalHandle& lh) : o(lh.o) {}
02640   forceinline LocalHandle&
02641   LocalHandle::operator =(const LocalHandle& lh) {
02642     o = lh.o;
02643     return *this;
02644   }
02645   forceinline
02646   LocalHandle::~LocalHandle(void) {}
02647   forceinline LocalObject*
02648   LocalHandle::object(void) const { return o; }
02649   forceinline void
02650   LocalHandle::object(LocalObject* n) { o = n; }
02651   forceinline void
02652   LocalHandle::update(Space& home, bool share, LocalHandle& lh) {
02653     object(lh.object()->fwd(home,share));
02654   }
02655 
02656 
02657   /*
02658    * Choices
02659    *
02660    */
02661   forceinline
02662   Choice::Choice(const Brancher& b, const unsigned int a)
02663     : _id(b.id()), _alt(a) {}
02664 
02665   forceinline unsigned int
02666   Choice::alternatives(void) const {
02667     return _alt;
02668   }
02669 
02670   forceinline unsigned int
02671   Choice::id(void) const {
02672     return _id;
02673   }
02674 
02675   forceinline
02676   Choice::~Choice(void) {}
02677 
02678 
02679 
02680   /*
02681    * Advisor
02682    *
02683    */
02684   template<class A>
02685   forceinline
02686   Advisor::Advisor(Space&, Propagator& p, Council<A>& c) {
02687     // Store propagator and forwarding in prev()
02688     ActorLink::prev(&p);
02689     // Link to next advisor in next()
02690     ActorLink::next(c.advisors); c.advisors = static_cast<A*>(this);
02691   }
02692 
02693   forceinline
02694   Advisor::Advisor(Space&, bool, Advisor&) {}
02695 
02696   forceinline bool
02697   Advisor::disposed(void) const {
02698     return prev() == NULL;
02699   }
02700 
02701   forceinline Advisor*
02702   Advisor::cast(ActorLink* al) {
02703     return static_cast<Advisor*>(al);
02704   }
02705 
02706   forceinline const Advisor*
02707   Advisor::cast(const ActorLink* al) {
02708     return static_cast<const Advisor*>(al);
02709   }
02710 
02711   forceinline Propagator&
02712   Advisor::propagator(void) const {
02713     assert(!disposed());
02714     return *Propagator::cast(ActorLink::prev());
02715   }
02716 
02717   template<class A>
02718   forceinline void
02719   Advisor::dispose(Space&,Council<A>&) {
02720     assert(!disposed());
02721     ActorLink::prev(NULL);
02722     // Shorten chains of disposed advisors by one, if possible
02723     Advisor* n = Advisor::cast(next());
02724     if ((n != NULL) && n->disposed())
02725       next(n->next());
02726   }
02727 
02728   template<class A>
02729   forceinline ExecStatus
02730   Space::ES_FIX_DISPOSE(Council<A>& c, A& a) {
02731     a.dispose(*this,c);
02732     return ES_FIX;
02733   }
02734 
02735   template<class A>
02736   forceinline ExecStatus
02737   Space::ES_NOFIX_DISPOSE(Council<A>& c, A& a) {
02738     a.dispose(*this,c);
02739     return ES_NOFIX;
02740   }
02741 
02742   template<class A>
02743   forceinline ExecStatus
02744   Space::ES_NOFIX_DISPOSE_FORCE(Council<A>& c, A& a) {
02745     a.dispose(*this,c);
02746     return ES_NOFIX_FORCE;
02747   }
02748 
02749 
02750 
02751   /*
02752    * Advisor council
02753    *
02754    */
02755   template<class A>
02756   forceinline
02757   Council<A>::Council(void) {}
02758 
02759   template<class A>
02760   forceinline
02761   Council<A>::Council(Space&)
02762     : advisors(NULL) {}
02763 
02764   template<class A>
02765   forceinline bool
02766   Council<A>::empty(void) const {
02767     ActorLink* a = advisors;
02768     while ((a != NULL) && static_cast<A*>(a)->disposed())
02769       a = a->next();
02770     advisors = a;
02771     return a == NULL;
02772   }
02773 
02774   template<class A>
02775   forceinline void
02776   Council<A>::update(Space& home, bool share, Council<A>& c) {
02777     // Skip all disposed advisors
02778     {
02779       ActorLink* a = c.advisors;
02780       while ((a != NULL) && static_cast<A*>(a)->disposed())
02781         a = a->next();
02782       c.advisors = a;
02783     }
02784     // Are there any advisors to be cloned?
02785     if (c.advisors != NULL) {
02786       // The propagator in from-space
02787       Propagator* p_f = &static_cast<A*>(c.advisors)->propagator();
02788       // The propagator in to-space
02789       Propagator* p_t = Propagator::cast(p_f->prev());
02790       // Advisors in from-space
02791       ActorLink** a_f = &c.advisors;
02792       // Advisors in to-space
02793       A* a_t = NULL;
02794       while (*a_f != NULL) {
02795         if (static_cast<A*>(*a_f)->disposed()) {
02796           *a_f = (*a_f)->next();
02797         } else {
02798           // Run specific copying part
02799           A* a = new (home) A(home,share,*static_cast<A*>(*a_f));
02800           // Set propagator pointer
02801           a->prev(p_t);
02802           // Set forwarding pointer
02803           (*a_f)->prev(a);
02804           // Link
02805           a->next(a_t);
02806           a_t = a;
02807           a_f = (*a_f)->next_ref();
02808         }
02809       }
02810       advisors = a_t;
02811       // Enter advisor link for reset
02812       assert(p_f->u.advisors == NULL);
02813       p_f->u.advisors = c.advisors;
02814     } else {
02815       advisors = NULL;
02816     }
02817   }
02818 
02819   template<class A>
02820   forceinline void
02821   Council<A>::dispose(Space& home) {
02822     ActorLink* a = advisors;
02823     while (a != NULL) {
02824       if (!static_cast<A*>(a)->disposed())
02825         static_cast<A*>(a)->dispose(home,*this);
02826       a = a->next();
02827     }
02828   }
02829 
02830 
02831 
02832   /*
02833    * Advisor iterator
02834    *
02835    */
02836   template<class A>
02837   forceinline
02838   Advisors<A>::Advisors(const Council<A>& c)
02839     : a(c.advisors) {
02840     while ((a != NULL) && static_cast<A*>(a)->disposed())
02841       a = a->next();
02842   }
02843 
02844   template<class A>
02845   forceinline bool
02846   Advisors<A>::operator ()(void) const {
02847     return a != NULL;
02848   }
02849 
02850   template<class A>
02851   forceinline void
02852   Advisors<A>::operator ++(void) {
02853     do {
02854       a = a->next();
02855     } while ((a != NULL) && static_cast<A*>(a)->disposed());
02856   }
02857 
02858   template<class A>
02859   forceinline A&
02860   Advisors<A>::advisor(void) const {
02861     return *static_cast<A*>(a);
02862   }
02863 
02864 
02865 
02866   /*
02867    * Space
02868    *
02869    */
02870   forceinline void
02871   Space::enqueue(Propagator* p) {
02872     ActorLink::cast(p)->unlink();
02873     ActorLink* c = &pc.p.queue[p->cost(*this,p->u.med).ac];
02874     c->tail(ActorLink::cast(p));
02875     if (c > pc.p.active)
02876       pc.p.active = c;
02877   }
02878 
02879   forceinline void
02880   Space::fail(void) {
02881     /*
02882      * Now active points beyond the last queue. This is essential as
02883      * enqueuing a propagator in a failed space keeps the space
02884      * failed.
02885      */
02886     pc.p.active = &pc.p.queue[PropCost::AC_MAX+2];
02887   }
02888   forceinline void
02889   Home::fail(void) {
02890     s.fail();
02891   }
02892 
02893   forceinline bool
02894   Space::failed(void) const {
02895     return pc.p.active > &pc.p.queue[PropCost::AC_MAX+1];
02896   }
02897   forceinline bool
02898   Home::failed(void) const {
02899     return s.failed();
02900   }
02901 
02902   forceinline bool
02903   Space::stable(void) const {
02904     return ((pc.p.active < &pc.p.queue[0]) ||
02905             (pc.p.active > &pc.p.queue[PropCost::AC_MAX+1]));
02906   }
02907 
02908 
02909 
02910   /*
02911    * Variable implementation
02912    *
02913    */
02914   template<class VIC>
02915   forceinline ActorLink**
02916   VarImp<VIC>::actor(PropCond pc) {
02917     assert((pc >= 0)  && (pc < pc_max+2));
02918     return (pc == 0) ? base : base+u.idx[pc-1];
02919   }
02920 
02921   template<class VIC>
02922   forceinline ActorLink**
02923   VarImp<VIC>::actorNonZero(PropCond pc) {
02924     assert((pc > 0)  && (pc < pc_max+2));
02925     return base+u.idx[pc-1];
02926   }
02927 
02928   template<class VIC>
02929   forceinline unsigned int&
02930   VarImp<VIC>::idx(PropCond pc) {
02931     assert((pc > 0)  && (pc < pc_max+2));
02932     return u.idx[pc-1];
02933   }
02934 
02935   template<class VIC>
02936   forceinline unsigned int
02937   VarImp<VIC>::idx(PropCond pc) const {
02938     assert((pc > 0)  && (pc < pc_max+2));
02939     return u.idx[pc-1];
02940   }
02941 
02942   template<class VIC>
02943   forceinline
02944   VarImp<VIC>::VarImp(Space&) {
02945     base = NULL; entries = 0;
02946     for (PropCond pc=1; pc<pc_max+2; pc++)
02947       idx(pc) = 0;
02948     free_and_bits = 0;
02949   }
02950 
02951   template<class VIC>
02952   forceinline
02953   VarImp<VIC>::VarImp(void) {
02954     base = NULL; entries = 0;
02955     for (PropCond pc=1; pc<pc_max+2; pc++)
02956       idx(pc) = 0;
02957     free_and_bits = 0;
02958   }
02959 
02960   template<class VIC>
02961   forceinline unsigned int
02962   VarImp<VIC>::degree(void) const {
02963     assert(!copied());
02964     return entries;
02965   }
02966 
02967   template<class VIC>
02968   forceinline double
02969   VarImp<VIC>::afc(void) const {
02970     if (degree() == 0)
02971       return 0.0;
02972     double d = degree();
02973     // Count the afc of each propagator
02974     {
02975       ActorLink** a = const_cast<VarImp<VIC>*>(this)->actor(0);
02976       ActorLink** e = const_cast<VarImp<VIC>*>(this)->actorNonZero(pc_max+1);
02977       while (a < e) {
02978         d += Propagator::cast(*a)->afc(); a++;
02979       }
02980     }
02981     // Count the afc of each advisor's propagator
02982     {
02983       ActorLink** a = const_cast<VarImp<VIC>*>(this)->actorNonZero(pc_max+1);
02984       ActorLink** e = const_cast<VarImp<VIC>*>(this)->base+entries;
02985       while (a < e) {
02986         d += Advisor::cast(*a)->propagator().afc(); a++;
02987       }
02988     }
02989     return d;
02990   }
02991 
02992   template<class VIC>
02993   forceinline ModEvent
02994   VarImp<VIC>::modevent(const Delta& d) {
02995     return d.me;
02996   }
02997 
02998   template<class VIC>
02999   forceinline unsigned int
03000   VarImp<VIC>::bits(void) const {
03001     return free_and_bits;
03002   }
03003 
03004   template<class VIC>
03005   forceinline unsigned int&
03006   VarImp<VIC>::bits(void) {
03007     return free_and_bits;
03008   }
03009 
03010 #ifdef GECODE_HAS_VAR_DISPOSE
03011   template<class VIC>
03012   forceinline VarImp<VIC>*
03013   VarImp<VIC>::vars_d(Space& home) {
03014     return static_cast<VarImp<VIC>*>(home.vars_d<VIC>());
03015   }
03016 
03017   template<class VIC>
03018   forceinline void
03019   VarImp<VIC>::vars_d(Space& home, VarImp<VIC>* x) {
03020     home.vars_d<VIC>(x);
03021   }
03022 #endif
03023 
03024   template<class VIC>
03025   forceinline bool
03026   VarImp<VIC>::copied(void) const {
03027     return Support::marked(base);
03028   }
03029 
03030   template<class VIC>
03031   forceinline VarImp<VIC>*
03032   VarImp<VIC>::forward(void) const {
03033     assert(copied());
03034     return reinterpret_cast<VarImp<VIC>*>(Support::unmark(base));
03035   }
03036 
03037   template<class VIC>
03038   forceinline VarImp<VIC>*
03039   VarImp<VIC>::next(void) const {
03040     assert(copied());
03041     return u.next;
03042   }
03043 
03044   template<class VIC>
03045   forceinline
03046   VarImp<VIC>::VarImp(Space& home, bool, VarImp<VIC>& x) {
03047     VarImpBase** reg;
03048     free_and_bits = x.free_and_bits & ((1 << free_bits) - 1);
03049     if (x.base == NULL) {
03050       // Variable implementation needs no index structure
03051       reg = &home.pc.c.vars_noidx;
03052       assert(x.degree() == 0);
03053     } else {
03054       reg = &home.pc.c.vars_u[idx_c];
03055     }
03056     // Save subscriptions in copy
03057     base = x.base;
03058     entries = x.entries;
03059     for (PropCond pc=1; pc<pc_max+2; pc++)
03060       idx(pc) = x.idx(pc);
03061 
03062     // Set forwarding pointer
03063     x.base = reinterpret_cast<ActorLink**>(Support::mark(this));
03064     // Register original
03065     x.u.next = static_cast<VarImp<VIC>*>(*reg); *reg = &x;
03066   }
03067 
03068   template<class VIC>
03069   forceinline ModEvent
03070   VarImp<VIC>::me(const ModEventDelta& med) {
03071     return static_cast<ModEvent>((med & VIC::med_mask) >> VIC::med_fst);
03072   }
03073 
03074   template<class VIC>
03075   forceinline ModEventDelta
03076   VarImp<VIC>::med(ModEvent me) {
03077     return static_cast<ModEventDelta>(me << VIC::med_fst);
03078   }
03079 
03080   template<class VIC>
03081   forceinline ModEvent
03082   VarImp<VIC>::me_combine(ModEvent me1, ModEvent me2) {
03083     return VIC::me_combine(me1,me2);
03084   }
03085 
03086   template<class VIC>
03087   forceinline void
03088   VarImp<VIC>::schedule(Space& home, Propagator& p, ModEvent me,
03089                         bool force) {
03090     if (VIC::med_update(p.u.med,me) || force)
03091       home.enqueue(&p);
03092   }
03093 
03094   template<class VIC>
03095   forceinline void
03096   VarImp<VIC>::schedule(Space& home, PropCond pc1, PropCond pc2, ModEvent me) {
03097     ActorLink** b = actor(pc1);
03098     ActorLink** p = actorNonZero(pc2+1);
03099     while (p-- > b)
03100       schedule(home,*Propagator::cast(*p),me);
03101   }
03102 
03103   template<class VIC>
03104   forceinline void
03105   VarImp<VIC>::enter(Space& home, Propagator* p, PropCond pc) {
03106     assert(pc <= pc_max);
03107     // Count one new subscription
03108     home.pc.p.n_sub += 1;
03109     if ((free_and_bits >> free_bits) == 0)
03110       resize(home);
03111     free_and_bits -= 1 << free_bits;
03112 
03113     // Enter subscription
03114     base[entries] = *actorNonZero(pc_max+1);
03115     entries++;
03116     for (PropCond j = pc_max; j > pc; j--) {
03117       *actorNonZero(j+1) = *actorNonZero(j);
03118       idx(j+1)++;
03119     }
03120     *actorNonZero(pc+1) = *actor(pc);
03121     idx(pc+1)++;
03122     *actor(pc) = ActorLink::cast(p);
03123 
03124 #ifdef GECODE_AUDIT
03125     ActorLink** f = actor(pc);
03126     while (f < (pc == pc_max+1 ? base+entries : actorNonZero(pc+1)))
03127       if (*f == p)
03128         goto found;
03129       else
03130         f++;
03131     GECODE_NEVER;
03132     found: ;
03133 #endif
03134   }
03135 
03136   template<class VIC>
03137   forceinline void
03138   VarImp<VIC>::enter(Space& home, Advisor* a) {
03139     // Count one new subscription
03140     home.pc.p.n_sub += 1;
03141     if ((free_and_bits >> free_bits) == 0)
03142       resize(home);
03143     free_and_bits -= 1 << free_bits;
03144 
03145     // Enter subscription
03146     base[entries++] = *actorNonZero(pc_max+1);
03147     *actorNonZero(pc_max+1) = a;
03148   }
03149 
03150   template<class VIC>
03151   void
03152   VarImp<VIC>::resize(Space& home) {
03153     if (base == NULL) {
03154       assert((free_and_bits >> free_bits) == 0);
03155       // Create fresh dependency array with four entries
03156       free_and_bits += 4 << free_bits;
03157       base = home.alloc<ActorLink*>(4);
03158       for (int i=0; i<pc_max+1; i++)
03159         u.idx[i] = 0;
03160     } else {
03161       // Resize dependency array
03162       unsigned int n = degree();
03163       // Find out whether the area is most likely in the special area
03164       // reserved for subscriptions. If yes, just resize mildly otherwise
03165       // more agressively
03166       ActorLink** s = static_cast<ActorLink**>(home.mm.subscriptions());
03167       unsigned int m =
03168         ((s <= base) && (base < s+home.pc.p.n_sub)) ?
03169         (n+4) : ((n+1)*3>>1);
03170       ActorLink** prop = home.alloc<ActorLink*>(m);
03171       free_and_bits += (m-n) << free_bits;
03172       // Copy entries
03173       Heap::copy<ActorLink*>(prop, base, n);
03174       home.free<ActorLink*>(base,n);
03175       base = prop;
03176     }
03177   }
03178 
03179   template<class VIC>
03180   void
03181   VarImp<VIC>::subscribe(Space& home, Propagator& p, PropCond pc,
03182                          bool assigned, ModEvent me, bool schedule) {
03183     if (assigned) {
03184       // Do not subscribe, just schedule the propagator
03185       if (schedule)
03186         VarImp<VIC>::schedule(home,p,ME_GEN_ASSIGNED);
03187     } else {
03188       enter(home,&p,pc);
03189       // Schedule propagator
03190       if (schedule && (pc != PC_GEN_ASSIGNED))
03191         VarImp<VIC>::schedule(home,p,me);
03192     }
03193   }
03194 
03195   template<class VIC>
03196   forceinline void
03197   VarImp<VIC>::subscribe(Space& home, Advisor& a, bool assigned) {
03198     if (!assigned)
03199       enter(home,&a);
03200   }
03201 
03202   template<class VIC>
03203   forceinline void
03204   VarImp<VIC>::remove(Space& home, Propagator* p, PropCond pc) {
03205     assert(pc <= pc_max);
03206     ActorLink* a = ActorLink::cast(p);
03207     // Find actor in dependency array
03208     ActorLink** f = actor(pc);
03209 #ifdef GECODE_AUDIT
03210     while (f < actorNonZero(pc+1))
03211       if (*f == a)
03212         goto found;
03213       else
03214         f++;
03215     GECODE_NEVER;
03216   found: ;
03217 #else
03218     while (*f != a) f++;
03219 #endif
03220     // Remove actor
03221     *f = *(actorNonZero(pc+1)-1);
03222     for (PropCond j = pc+1; j< pc_max+1; j++) {
03223       *(actorNonZero(j)-1) = *(actorNonZero(j+1)-1);
03224       idx(j)--;
03225     }
03226     *(actorNonZero(pc_max+1)-1) = base[entries-1];
03227     idx(pc_max+1)--;
03228     entries--;
03229     free_and_bits += 1 << free_bits;
03230     home.pc.p.n_sub -= 1;
03231   }
03232 
03233   template<class VIC>
03234   forceinline void
03235   VarImp<VIC>::remove(Space& home, Advisor* a) {
03236     // Find actor in dependency array
03237     ActorLink** f = actorNonZero(pc_max+1);
03238 #ifdef GECODE_AUDIT
03239     while (f < base+entries)
03240       if (*f == a)
03241         goto found;
03242       else
03243         f++;
03244     GECODE_NEVER;
03245   found: ;
03246 #else
03247     while (*f != a) f++;
03248 #endif
03249     // Remove actor
03250     *f = base[--entries];
03251     free_and_bits += 1 << free_bits;
03252     home.pc.p.n_sub -= 1;
03253   }
03254 
03255   template<class VIC>
03256   forceinline void
03257   VarImp<VIC>::cancel(Space& home, Propagator& p, PropCond pc, bool assigned) {
03258     if (!assigned)
03259       remove(home,&p,pc);
03260   }
03261 
03262   template<class VIC>
03263   forceinline void
03264   VarImp<VIC>::cancel(Space& home, Advisor& a, bool assigned) {
03265     if (!assigned)
03266       remove(home,&a);
03267   }
03268 
03269   template<class VIC>
03270   forceinline void
03271   VarImp<VIC>::cancel(Space& home) {
03272     unsigned int n_sub = degree();
03273     home.pc.p.n_sub -= n_sub;
03274     unsigned int n = (free_and_bits >> VIC::free_bits) + n_sub;
03275     home.free<ActorLink*>(base,n);
03276     // Must be NULL such that cloning works
03277     base = NULL;
03278     // Must be 0 such that degree works
03279     entries = 0;
03280   }
03281 
03282   template<class VIC>
03283   forceinline bool
03284   VarImp<VIC>::advise(Space& home, ModEvent me, Delta& d) {
03285     /*
03286      * An advisor that is executed might remove itself due to subsumption.
03287      * As entries are removed from front to back, the advisors must
03288      * be iterated in forward direction.
03289      */
03290     ActorLink** la = actorNonZero(pc_max+1);
03291     ActorLink** le = base+entries;
03292     if (la == le)
03293       return true;
03294     d.me = me;
03295     // An advisor that is run, might be removed during execution.
03296     // As removal is done from the back the advisors have to be executed
03297     // in inverse order.
03298     do {
03299       Advisor* a = Advisor::cast(*la);
03300       assert(!a->disposed());
03301       Propagator& p = a->propagator();
03302       switch (p.advise(home,*a,d)) {
03303       case ES_FIX:
03304         break;
03305       case ES_FAILED:
03306         p.pi.fail(home.gpi);
03307         return false;
03308       case ES_NOFIX:
03309         schedule(home,p,me);
03310         break;
03311       case ES_NOFIX_FORCE:
03312         schedule(home,p,me,true);
03313         break;
03314       default:
03315         GECODE_NEVER;
03316       }
03317     } while (++la < le);
03318     return true;
03319   }
03320 
03321   template<class VIC>
03322   forceinline void
03323   VarImp<VIC>::update(VarImp<VIC>* x, ActorLink**& sub) {
03324     // this refers to the variable to be updated (clone)
03325     // x refers to the original
03326     // Recover from copy
03327     x->base = base;
03328     x->u.idx[0] = u.idx[0];
03329     if (pc_max > 0 && sizeof(ActorLink**) > sizeof(unsigned int))
03330       x->u.idx[1] = u.idx[1];
03331 
03332     ActorLink** f = x->base;
03333     unsigned int n = x->degree();
03334     ActorLink** t = sub;
03335     sub += n;
03336     base = t;
03337     // Set subscriptions using actor forwarding pointers
03338     while (n >= 4) {
03339       n -= 4;
03340       t[0]=f[0]->prev(); t[1]=f[1]->prev();
03341       t[2]=f[2]->prev(); t[3]=f[3]->prev();
03342       t += 4; f += 4;
03343     }
03344     if (n >= 2) {
03345       n -= 2;
03346       t[0]=f[0]->prev(); t[1]=f[1]->prev();
03347       t += 2; f += 2;
03348     }
03349     if (n > 0) {
03350       t[0]=f[0]->prev();
03351     }
03352   }
03353 
03354   template<class VIC>
03355   forceinline void
03356   VarImp<VIC>::update(Space& home, ActorLink**& sub) {
03357     VarImp<VIC>* x = static_cast<VarImp<VIC>*>(home.pc.c.vars_u[idx_c]);
03358     while (x != NULL) {
03359       VarImp<VIC>* n = x->next(); x->forward()->update(x,sub); x = n;
03360     }
03361   }
03362 
03363 
03364 
03365   /*
03366    * Variable disposer
03367    *
03368    */
03369   template<class VarImp>
03370   VarImpDisposer<VarImp>::VarImpDisposer(void) {
03371 #ifdef GECODE_HAS_VAR_DISPOSE
03372     Space::vd[VarImp::idx_d] = this;
03373 #endif
03374   }
03375 
03376   template<class VarImp>
03377   void
03378   VarImpDisposer<VarImp>::dispose(Space& home, VarImpBase* _x) {
03379     VarImp* x = static_cast<VarImp*>(_x);
03380     do {
03381       x->dispose(home); x = static_cast<VarImp*>(x->next_d());
03382     } while (x != NULL);
03383   }
03384 
03385   /*
03386    * Statistics
03387    */
03388 
03389   forceinline void
03390   StatusStatistics::reset(void) {
03391     propagate = 0;
03392     wmp = false;
03393   }
03394   forceinline
03395   StatusStatistics::StatusStatistics(void) {
03396     reset();
03397   }
03398   forceinline StatusStatistics&
03399   StatusStatistics::operator +=(const StatusStatistics& s) { 
03400     propagate += s.propagate;
03401     wmp |= s.wmp;
03402     return *this;
03403   }
03404   forceinline StatusStatistics
03405   StatusStatistics::operator +(const StatusStatistics& s) {
03406     StatusStatistics t(s);
03407     return t += *this;
03408   }
03409 
03410   forceinline void
03411   CloneStatistics::reset(void) {}
03412 
03413   forceinline
03414   CloneStatistics::CloneStatistics(void) {
03415     reset();
03416   }
03417   forceinline CloneStatistics
03418   CloneStatistics::operator +(const CloneStatistics&) {
03419     CloneStatistics s;
03420     return s;
03421   }
03422   forceinline CloneStatistics&
03423   CloneStatistics::operator +=(const CloneStatistics&) { 
03424     return *this;
03425   }
03426 
03427   forceinline void
03428   CommitStatistics::reset(void) {}
03429 
03430   forceinline
03431   CommitStatistics::CommitStatistics(void) {
03432     reset();
03433   }
03434   forceinline CommitStatistics
03435   CommitStatistics::operator +(const CommitStatistics&) {
03436     CommitStatistics s;
03437     return s;
03438   }
03439   forceinline CommitStatistics&
03440   CommitStatistics::operator +=(const CommitStatistics&) { 
03441     return *this;
03442   }
03443 
03444   /*
03445    * Cost computation
03446    *
03447    */
03448 
03449   forceinline
03450   PropCost::PropCost(PropCost::ActualCost ac0) : ac(ac0) {}
03451 
03452   forceinline PropCost
03453   PropCost::cost(PropCost::Mod m,
03454                  PropCost::ActualCost lo, PropCost::ActualCost hi,
03455                  unsigned int n) {
03456     if (n < 2)
03457       return (m == LO) ? AC_UNARY_LO : AC_UNARY_HI;
03458     else if (n == 2)
03459       return (m == LO) ? AC_BINARY_LO : AC_BINARY_HI;
03460     else if (n == 3)
03461       return (m == LO) ? AC_TERNARY_LO : AC_TERNARY_HI;
03462     else
03463       return (m == LO) ? lo : hi;
03464   }
03465 
03466   forceinline PropCost
03467   PropCost::crazy(PropCost::Mod m, unsigned int n) {
03468     return cost(m,AC_CRAZY_LO,AC_CRAZY_HI,n);
03469   }
03470   forceinline PropCost
03471   PropCost::crazy(PropCost::Mod m, int n) {
03472     assert(n >= 0);
03473     return crazy(m,static_cast<unsigned int>(n));
03474   }
03475   forceinline PropCost
03476   PropCost::cubic(PropCost::Mod m, unsigned int n) {
03477     return cost(m,AC_CUBIC_LO,AC_CUBIC_HI,n);
03478   }
03479   forceinline PropCost
03480   PropCost::cubic(PropCost::Mod m, int n) {
03481     assert(n >= 0);
03482     return cubic(m,static_cast<unsigned int>(n));
03483   }
03484   forceinline PropCost
03485   PropCost::quadratic(PropCost::Mod m, unsigned int n) {
03486     return cost(m,AC_QUADRATIC_LO,AC_QUADRATIC_HI,n);
03487   }
03488   forceinline PropCost
03489   PropCost::quadratic(PropCost::Mod m, int n) {
03490     assert(n >= 0);
03491     return quadratic(m,static_cast<unsigned int>(n));
03492   }
03493   forceinline PropCost
03494   PropCost::linear(PropCost::Mod m, unsigned int n) {
03495     return cost(m,AC_LINEAR_LO,AC_LINEAR_HI,n);
03496   }
03497   forceinline PropCost
03498   PropCost::linear(PropCost::Mod m, int n) {
03499     assert(n >= 0);
03500     return linear(m,static_cast<unsigned int>(n));
03501   }
03502   forceinline PropCost
03503   PropCost::ternary(PropCost::Mod m) {
03504     return (m == LO) ? AC_TERNARY_LO : AC_TERNARY_HI;
03505   }
03506   forceinline PropCost
03507   PropCost::binary(PropCost::Mod m) {
03508     return (m == LO) ? AC_BINARY_LO : AC_BINARY_HI;
03509   }
03510   forceinline PropCost
03511   PropCost::unary(PropCost::Mod m) {
03512     return (m == LO) ? AC_UNARY_LO : AC_UNARY_HI;
03513   }
03514 
03515   /*
03516    * Iterators for propagators and branchers of a space
03517    *
03518    */
03519   forceinline
03520   Space::Propagators::Propagators(const Space& home0) 
03521     : home(home0), q(home.pc.p.active) {
03522     while (q >= &home.pc.p.queue[0]) {
03523       if (q->next() != q) {
03524         c = q->next(); e = q; q--;
03525         return;
03526       }
03527       q--;
03528     }
03529     q = NULL;
03530     if (!home.pl.empty()) {
03531       c = Propagator::cast(home.pl.next());
03532       e = Propagator::cast(&home.pl);
03533     } else {
03534       c = e = NULL;
03535     }
03536   }
03537   forceinline bool 
03538   Space::Propagators::operator ()(void) const {
03539     return c != NULL;
03540   }
03541   forceinline void 
03542   Space::Propagators::operator ++(void) {
03543     c = c->next();
03544     if (c == e) {
03545       if (q == NULL) {
03546         c = NULL;
03547       } else {
03548         while (q >= &home.pc.p.queue[0]) {
03549           if (q->next() != q) {
03550             c = q->next(); e = q; q--;
03551             return;
03552           }
03553           q--;
03554         }
03555         q = NULL;
03556         if (!home.pl.empty()) {
03557           c = Propagator::cast(home.pl.next());
03558           e = Propagator::cast(&home.pl);
03559         } else {
03560           c = NULL;
03561         }
03562       }
03563     }
03564   }
03565   forceinline const Propagator& 
03566   Space::Propagators::propagator(void) const {
03567     return *Propagator::cast(c);
03568   }
03569 
03570   forceinline
03571   Space::Branchers::Branchers(const Space& home) 
03572     : c(Brancher::cast(home.bl.next())), e(&home.bl) {}
03573   forceinline bool 
03574   Space::Branchers::operator ()(void) const {
03575     return c != e;
03576   }
03577   forceinline void 
03578   Space::Branchers::operator ++(void) {
03579     c = c->next();
03580   }
03581   forceinline const Brancher& 
03582   Space::Branchers::brancher(void) const {
03583     return *Brancher::cast(c);
03584   }
03585 
03586   /*
03587    * Space construction support
03588    *
03589    */
03590   template<class T> 
03591   forceinline T& 
03592   Space::construct(void) {
03593     return alloc<T>(1);
03594   }
03595   template<class T, typename A1> 
03596   forceinline T& 
03597   Space::construct(A1 const& a1) {
03598     T& t = *static_cast<T*>(ralloc(sizeof(T)));
03599     new (&t) T(a1);
03600     return t;
03601   }
03602   template<class T, typename A1, typename A2> 
03603   forceinline T& 
03604   Space::construct(A1 const& a1, A2 const& a2) {
03605     T& t = *static_cast<T*>(ralloc(sizeof(T)));
03606     new (&t) T(a1,a2);
03607     return t;
03608   }
03609   template<class T, typename A1, typename A2, typename A3>
03610   forceinline T& 
03611   Space::construct(A1 const& a1, A2 const& a2, A3 const& a3) {
03612     T& t = *static_cast<T*>(ralloc(sizeof(T)));
03613     new (&t) T(a1,a2,a3);
03614     return t;
03615   }
03616   template<class T, typename A1, typename A2, typename A3, typename A4>
03617   forceinline T& 
03618   Space::construct(A1 const& a1, A2 const& a2, A3 const& a3, A4 const& a4) {
03619     T& t = *static_cast<T*>(ralloc(sizeof(T)));
03620     new (&t) T(a1,a2,a3,a4);
03621     return t;
03622   }
03623   template<class T, typename A1, typename A2, typename A3, typename A4, typename A5>
03624   forceinline T& 
03625   Space::construct(A1 const& a1, A2 const& a2, A3 const& a3, A4 const& a4, A5 const& a5) {
03626     T& t = *static_cast<T*>(ralloc(sizeof(T)));
03627     new (&t) T(a1,a2,a3,a4,a5);
03628     return t;
03629   }
03630 
03631 }
03632 
03633 // STATISTICS: kernel-core