Generated on Mon May 10 06:46:42 2010 for Gecode by doxygen 1.6.3

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-04-08 12:35:31 +0200 (Thu, 08 Apr 2010) $ by $Author: schulte $
00022  *     $Revision: 10684 $
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 
00135 
00144 
00145   typedef int ModEvent;
00146 
00148   const ModEvent ME_GEN_FAILED   = -1;
00150   const ModEvent ME_GEN_NONE     =  0;
00152   const ModEvent ME_GEN_ASSIGNED =  1;
00153 
00155   typedef int PropCond;
00157   const PropCond PC_GEN_NONE     = -1;
00159   const PropCond PC_GEN_ASSIGNED = 0;
00161 
00172   typedef int ModEventDelta;
00173 
00174 }
00175 
00176 #include <gecode/kernel/var-type.hpp>
00177 
00178 namespace Gecode {
00179 
00181   class NoIdxVarImpConf {
00182   public:
00184     static const int idx_c = -1;
00186     static const int idx_d = -1;
00188     static const PropCond pc_max = PC_GEN_ASSIGNED;
00190     static const int free_bits = 0;
00192     static const int med_fst = 0;
00194     static const int med_lst = 0;
00196     static const int med_mask = 0;
00198     static Gecode::ModEvent me_combine(ModEvent me1, ModEvent me2);
00200     static bool med_update(ModEventDelta& med, ModEvent me);
00201   };
00202 
00203   forceinline ModEvent
00204   NoIdxVarImpConf::me_combine(ModEvent, ModEvent) {
00205     GECODE_NEVER; return 0;
00206   }
00207   forceinline bool
00208   NoIdxVarImpConf::med_update(ModEventDelta&, ModEvent) {
00209     GECODE_NEVER; return false;
00210   }
00211 
00212 
00213   /*
00214    * These are the classes of interest
00215    *
00216    */
00217   class ActorLink;
00218   class Actor;
00219   class Propagator;
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 VarDisposerBase {
00247   public:
00249     GECODE_KERNEL_EXPORT virtual void dispose(Space& home, VarImpBase* x);
00251     GECODE_KERNEL_EXPORT virtual ~VarDisposerBase(void);
00252   };
00253 
00260   template<class VarType>
00261   class VarDisposer : public VarDisposerBase {
00262   public:
00264     VarDisposer(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   public:
00277     ModEvent modevent(void) const;
00278   };
00279 
00287   template<class VIC>
00288   class VarImp : public VarImpBase {
00289     friend class Space;
00290     friend class Propagator;
00291     template<class VarType> friend class VarDisposer;
00292   private:
00304     ActorLink** base;
00305 
00307     static const int idx_c = VIC::idx_c;
00309     static const int idx_d = VIC::idx_d;
00311     static const int free_bits = VIC::free_bits;
00313     unsigned int entries;
00315     unsigned int free_and_bits;
00317     static const Gecode::PropCond pc_max = VIC::pc_max;
00318 
00319     union {
00330       unsigned int idx[pc_max+1];
00332       VarImp<VIC>* next;
00333     } u;
00334 
00336     ActorLink** actor(PropCond pc);
00338     ActorLink** actorNonZero(PropCond pc);
00340     unsigned int& idx(PropCond pc);
00342     unsigned int idx(PropCond pc) const;
00343 
00350     void update(VarImp* x, ActorLink**& sub);
00357     static void update(Space& home, ActorLink**& sub);
00358 
00360     void enter(Space& home, Propagator* p, PropCond pc);
00362     void enter(Space& home, Advisor* a);
00364     void resize(Space& home);
00366     void remove(Space& home, Propagator* p, PropCond pc);
00368     void remove(Space& home, Advisor* a);
00369 
00370   protected:
00371 #ifdef GECODE_HAS_VAR_DISPOSE
00372 
00373     static VarImp<VIC>* vars_d(Space& home);
00375     static void vars_d(Space& home, VarImp<VIC>* x);
00376 #endif
00377 
00378   public:
00380     VarImp(Space& home);
00382     VarImp(void);
00383 
00385 
00386 
00398     void subscribe(Space& home, Propagator& p, PropCond pc,
00399                    bool assigned, ModEvent me, bool schedule);
00405     void cancel(Space& home, Propagator& p, PropCond pc,
00406                 bool assigned);
00412     void subscribe(Space& home, Advisor& a, bool assigned);
00418     void cancel(Space& home, Advisor& a, bool assigned);
00420     void cancel(Space& home);
00427     unsigned int degree(void) const;
00434     double afc(void) const;
00440     bool advise(Space& home, ModEvent me, Delta& d);
00442 
00444 
00445 
00446     VarImp(Space& home, bool share, VarImp& x);
00448     bool copied(void) const;
00450     VarImp* forward(void) const;
00452     VarImp* next(void) const;
00454 
00456 
00457 
00464     static void schedule(Space& home, Propagator& p, ModEvent me,
00465                          bool force = false);
00467     static ModEvent me(const ModEventDelta& med);
00469     static ModEventDelta med(ModEvent me);
00471     static ModEvent me_combine(ModEvent me1, ModEvent me2);
00473 
00475     unsigned int bits(void) const;
00477     unsigned int& bits(void);
00478 
00479   protected:
00481     void schedule(Space& home, PropCond pc1, PropCond pc2, ModEvent me);
00482 
00483   public:
00485 
00486 
00487     static void* operator new(size_t,Space&);
00489     static void  operator delete(void*,Space&);
00491     static void  operator delete(void*);
00493   };
00494 
00503   enum ExecStatus {
00504     __ES_SUBSUMED       = -2, 
00505     ES_FAILED           = -1, 
00506     ES_NOFIX            =  0, 
00507     ES_OK               =  0, 
00508     ES_FIX              =  1, 
00509     ES_NOFIX_FORCE      =  2, 
00510     __ES_PARTIAL        =  2  
00511   };
00512 
00517   class PropCost {
00518     friend class Space;
00519   public:
00521     enum ActualCost {
00522       AC_CRAZY_LO     = 0, 
00523       AC_CRAZY_HI     = 0, 
00524       AC_CUBIC_LO     = 1, 
00525       AC_CUBIC_HI     = 1, 
00526       AC_QUADRATIC_LO = 2, 
00527       AC_QUADRATIC_HI = 2, 
00528       AC_LINEAR_HI    = 3, 
00529       AC_LINEAR_LO    = 4, 
00530       AC_TERNARY_HI   = 4, 
00531       AC_BINARY_HI    = 5, 
00532       AC_TERNARY_LO   = 5, 
00533       AC_BINARY_LO    = 6, 
00534       AC_UNARY_LO     = 6, 
00535       AC_UNARY_HI     = 6, 
00536       AC_MAX          = 6  
00537     };
00539     ActualCost ac;
00540   public:
00542     enum Mod {
00543       LO, 
00544       HI  
00545     };
00546   private:
00548     static PropCost cost(Mod m, ActualCost lo, ActualCost hi, unsigned int n);
00550     PropCost(ActualCost ac);
00551   public:
00553     static PropCost crazy(PropCost::Mod m, unsigned int n);
00555     static PropCost crazy(PropCost::Mod m, int n);
00557     static PropCost cubic(PropCost::Mod m, unsigned int n);
00559     static PropCost cubic(PropCost::Mod m, int n);
00561     static PropCost quadratic(PropCost::Mod m, unsigned int n);
00563     static PropCost quadratic(PropCost::Mod m, int n);
00565     static PropCost linear(PropCost::Mod m, unsigned int n);
00567     static PropCost linear(PropCost::Mod m, int n);
00569     static PropCost ternary(PropCost::Mod m);
00571     static PropCost binary(PropCost::Mod m);
00573     static PropCost unary(PropCost::Mod m);
00574   };
00575 
00576 
00581   enum ActorProperty {
00590     AP_DISPOSE = (1 << 0),
00596     AP_WEAKLY  = (1 << 1)
00597   };
00598 
00599 
00607   class ActorLink {
00608     friend class Actor;
00609     friend class Propagator;
00610     friend class Advisor;
00611     friend class Brancher;
00612     friend class Space;
00613     template<class VIC> friend class VarImp;
00614   private:
00615     ActorLink* _next; ActorLink* _prev;
00616   public:
00618 
00619     ActorLink* prev(void) const; void prev(ActorLink*);
00620     ActorLink* next(void) const; void next(ActorLink*);
00621     ActorLink** next_ref(void);
00623 
00625     void init(void);
00627     void unlink(void);
00629     void head(ActorLink* al);
00631     void tail(ActorLink* al);
00633     bool empty(void) const;
00635     template<class T> static ActorLink* cast(T* a);
00637     template<class T> static const ActorLink* cast(const T* a);
00638   };
00639 
00640 
00645   class GECODE_VTABLE_EXPORT Actor : private ActorLink {
00646     friend class ActorLink;
00647     friend class Space;
00648     friend class Propagator;
00649     friend class Advisor;
00650     friend class Brancher;
00651     template<class VIC> friend class VarImp;
00652     template<class A> friend class Council;
00653   private:
00655     static Actor* cast(ActorLink* al);
00657     static const Actor* cast(const ActorLink* al);
00658   public:
00660     virtual Actor* copy(Space& home, bool share) = 0;
00661 
00663 
00664 
00665     GECODE_KERNEL_EXPORT
00666     virtual size_t allocated(void) const;
00668     GECODE_KERNEL_EXPORT
00669     virtual size_t dispose(Space& home);
00671     static void* operator new(size_t s, Space& home);
00673     static void  operator delete(void* p, Space& home);
00674   private:
00675 #ifndef __GNUC__
00676 
00677     static void  operator delete(void* p);
00678 #endif
00679 
00680     static void* operator new(size_t s);
00682 #ifdef __GNUC__
00683   public:
00685     GECODE_KERNEL_EXPORT virtual ~Actor(void);
00687     static void  operator delete(void* p);
00688 #endif
00689   };
00690 
00691 
00692 
00696   class Home {
00697   protected:
00699     Space& s;
00701     Propagator* p;
00702   public:
00704 
00705 
00706     Home(Space& s, Propagator* p=NULL);
00708     operator Space&(void);
00710 
00711 
00712 
00713     Home operator ()(Propagator& p);
00715     Propagator* propagator(void) const;
00717 
00718 
00719 
00720     bool failed(void) const;
00722     void fail(void);
00724     void notice(Actor& a, ActorProperty p);
00726   };
00727 
00732   class GECODE_VTABLE_EXPORT Propagator : public Actor {
00733     friend class ActorLink;
00734     friend class Space;
00735     template<class VIC> friend class VarImp;
00736     friend class Advisor;
00737     template<class A> friend class Council;
00738   private:
00739     union {
00741       ModEventDelta med;
00743       size_t size;
00745       Gecode::ActorLink* advisors;
00746     } u;
00748     PropInfo& pi;
00750     static Propagator* cast(ActorLink* al);
00752     static const Propagator* cast(const ActorLink* al);
00753   protected:
00755     Propagator(Home home);
00757     Propagator(Space& home, bool share, Propagator& p);
00758 
00759   public:
00761 
00762 
00785     virtual ExecStatus propagate(Space& home, const ModEventDelta& med) = 0;
00787     virtual PropCost cost(const Space& home, const ModEventDelta& med) const = 0;
00823     GECODE_KERNEL_EXPORT
00824     virtual ExecStatus advise(Space& home, Advisor& a, const Delta& d);
00826 
00827 
00828 
00829     double afc(void) const;
00831   };
00832 
00833 
00841   template<class A>
00842   class Council {
00843     friend class Advisor;
00844     friend class Advisors<A>;
00845   private:
00847     mutable ActorLink* advisors;
00848   public:
00850     Council(void);
00852     Council(Space& home);
00854     bool empty(void) const;
00856     void update(Space& home, bool share, Council<A>& c);
00858     void dispose(Space& home);
00859   };
00860 
00861 
00866   template<class A>
00867   class Advisors {
00868   private:
00870     ActorLink* a;
00871   public:
00873     Advisors(const Council<A>& c);
00875     bool operator ()(void) const;
00877     void operator ++(void);
00879     A& advisor(void) const;
00880   };
00881 
00882 
00893   class Advisor : private ActorLink {
00894     template<class VIC> friend class VarImp;
00895     template<class A> friend class Council;
00896     template<class A> friend class Advisors;
00897   private:
00899     bool disposed(void) const;
00901     static Advisor* cast(ActorLink* al);
00903     static const Advisor* cast(const ActorLink* al);
00904   protected:
00906     Propagator& propagator(void) const;
00907   public:
00909     template<class A>
00910     Advisor(Space& home, Propagator& p, Council<A>& c);
00912     Advisor(Space& home, bool share, Advisor& a);
00913 
00915 
00916 
00917     template<class A>
00918     void dispose(Space& home, Council<A>& c);
00920     static void* operator new(size_t s, Space& home);
00922     static void  operator delete(void* p, Space& home);
00924   private:
00925 #ifndef __GNUC__
00926 
00927     static void  operator delete(void* p);
00928 #endif
00929 
00930     static void* operator new(size_t s);
00931   };
00932 
00933 
00934   class Brancher;
00935 
00945   class Choice {
00946     friend class Space;
00947   private:
00948     unsigned int _id;  
00949     unsigned int _alt; 
00950 
00952     unsigned int id(void) const;
00953   protected:
00955     Choice(const Brancher& b, const unsigned int a);
00956   public:
00958     unsigned int alternatives(void) const;
00960     GECODE_KERNEL_EXPORT virtual ~Choice(void);
00962     virtual size_t size(void) const = 0;
00964     static void* operator new(size_t);
00966     static void  operator delete(void*);
00967   };
00968 
00978   class GECODE_VTABLE_EXPORT Brancher : public Actor {
00979     friend class ActorLink;
00980     friend class Space;
00981     friend class Choice;
00982   private:
00984     unsigned int _id;
00986     static Brancher* cast(ActorLink* al);
00988     static const Brancher* cast(const ActorLink* al);
00989   protected:
00991     Brancher(Home home);
00993     Brancher(Space& home, bool share, Brancher& b);
00994   public:
00996 
00997 
01005     virtual bool status(const Space& home) const = 0;
01013     virtual const Choice* choice(Space& home) = 0;
01020     virtual ExecStatus commit(Space& home, const Choice& c, 
01021                               unsigned int a) = 0;
01023     unsigned int id(void) const;
01025   };
01026 
01027 
01028 
01033   enum SpaceStatus {
01034     SS_FAILED, 
01035     SS_SOLVED, 
01036     SS_BRANCH  
01037   };
01038 
01043   class StatusStatistics {
01044   public:
01046     unsigned long int propagate;
01048     bool wmp;
01050     StatusStatistics(void);
01052     void reset(void);
01054     StatusStatistics operator +(const StatusStatistics& s);
01056     StatusStatistics& operator +=(const StatusStatistics& s);
01057   };
01058 
01063   class CloneStatistics {
01064   public:
01066     CloneStatistics(void);
01068     void reset(void);
01070     CloneStatistics operator +(const CloneStatistics& s);
01072     CloneStatistics& operator +=(const CloneStatistics& s);
01073   };
01074 
01079   class CommitStatistics {
01080   public:
01082     CommitStatistics(void);
01084     void reset(void);
01086     CommitStatistics operator +(const CommitStatistics& s);
01088     CommitStatistics& operator +=(const CommitStatistics& s);
01089   };
01090 
01094   class GECODE_VTABLE_EXPORT Space {
01095     friend class Actor;
01096     friend class Propagator;
01097     friend class Brancher;
01098     friend class Advisor;
01099     template<class VIC> friend class VarImp;
01100     template<class VarType> friend class VarDisposer;
01101     friend class SharedHandle;
01102     friend class Region;
01103   private:
01105     SharedMemory* sm;
01107     MemoryManager mm;
01109     GlobalPropInfo gpi;
01111     ActorLink pl;
01113     ActorLink bl;
01119     Brancher* b_status;
01131     Brancher* b_commit;
01132     union {
01134       struct {
01147         ActorLink* active;
01149         ActorLink queue[PropCost::AC_MAX+1];
01151         unsigned int branch_id;
01153         unsigned int n_sub;
01154       } p;
01156       struct {
01158         VarImpBase* vars_u[AllVarConf::idx_c];
01160         VarImpBase* vars_noidx;
01162         SharedHandle::Object* shared;
01163       } c;
01164     } pc;
01166     void enqueue(Propagator* p);
01171 #ifdef GECODE_HAS_VAR_DISPOSE
01172 
01173     GECODE_KERNEL_EXPORT static VarDisposerBase* vd[AllVarConf::idx_d];
01175     VarImpBase* _vars_d[AllVarConf::idx_d];
01177     template<class VIC> VarImpBase* vars_d(void) const;
01179     template<class VIC> void vars_d(VarImpBase* x);
01180 #endif
01181 
01182     void update(ActorLink** sub);
01184 
01186     Actor** d_fst;
01188     Actor** d_cur;
01190     Actor** d_lst;
01192     GECODE_KERNEL_EXPORT void d_resize(void);
01193 
01201     unsigned int n_wmp;
01202 
01204     GECODE_KERNEL_EXPORT static StatusStatistics unused_status;
01206     GECODE_KERNEL_EXPORT static CloneStatistics unused_clone;
01208     GECODE_KERNEL_EXPORT static CommitStatistics unused_commit;
01210     GECODE_KERNEL_EXPORT static unsigned long int unused_uli;
01212     GECODE_KERNEL_EXPORT static bool unused_b;
01213 
01228     GECODE_KERNEL_EXPORT Space* _clone(bool share=true);
01229 
01262     GECODE_KERNEL_EXPORT
01263     void _commit(const Choice& c, unsigned int a);
01264 
01265   public:
01270     GECODE_KERNEL_EXPORT Space(void);
01275     GECODE_KERNEL_EXPORT virtual ~Space(void);
01286     GECODE_KERNEL_EXPORT Space(bool share, Space& s);
01293     virtual Space* copy(bool share) = 0;
01305     GECODE_KERNEL_EXPORT virtual void constrain(const Space& best);
01310     static void* operator new(size_t);
01315     static void  operator delete(void*);
01316 
01317 
01318     /*
01319      * Member functions for search engines
01320      *
01321      */
01322 
01334     GECODE_KERNEL_EXPORT
01335     SpaceStatus status(StatusStatistics& stat=unused_status);
01336 
01368     GECODE_KERNEL_EXPORT
01369     const Choice* choice(void);
01370 
01388     Space* clone(bool share=true, CloneStatistics& stat=unused_clone) const;
01389 
01424     void commit(const Choice& c, unsigned int a,
01425                 CommitStatistics& stat=unused_commit);
01426 
01434     void notice(Actor& a, ActorProperty p);
01442     void ignore(Actor& a, ActorProperty p);
01443 
01444 
01455     ExecStatus ES_SUBSUMED(Propagator& p);
01470     ExecStatus ES_SUBSUMED_DISPOSED(Propagator& p, size_t s);
01481     ExecStatus ES_FIX_PARTIAL(Propagator& p, const ModEventDelta& med);
01492     ExecStatus ES_NOFIX_PARTIAL(Propagator& p, const ModEventDelta& med);
01493     
01504     template<class A>
01505     ExecStatus ES_FIX_DISPOSE(Council<A>& c, A& a);
01516     template<class A>
01517     ExecStatus ES_NOFIX_DISPOSE(Council<A>& c, A& a);
01529     template<class A>
01530     ExecStatus ES_NOFIX_DISPOSE_FORCE(Council<A>& c, A& a);
01531     
01539     void fail(void);
01548     bool failed(void) const;
01553     bool stable(void) const;
01560     GECODE_KERNEL_EXPORT unsigned int propagators(void) const;
01567     GECODE_KERNEL_EXPORT unsigned int branchers(void) const;
01568 
01570 
01571 
01572     Home operator ()(Propagator& p);
01574 
01586     template<class T>
01587     T* alloc(long unsigned int n);
01594     template<class T>
01595     T* alloc(long int n);
01602     template<class T>
01603     T* alloc(unsigned int n);
01610     template<class T>
01611     T* alloc(int n);
01621     template<class T>
01622     void free(T* b, long unsigned int n);
01632     template<class T>
01633     void free(T* b, long int n);
01643     template<class T>
01644     void free(T* b, unsigned int n);
01654     template<class T>
01655     void free(T* b, int n);
01667     template<class T>
01668     T* realloc(T* b, long unsigned int n, long unsigned int m);
01680     template<class T>
01681     T* realloc(T* b, long int n, long int m);
01693     template<class T>
01694     T* realloc(T* b, unsigned int n, unsigned int m);
01706     template<class T>
01707     T* realloc(T* b, int n, int m);
01715     template<class T>
01716     T** realloc(T** b, long unsigned int n, long unsigned int m);
01724     template<class T>
01725     T** realloc(T** b, long int n, long int m);
01733     template<class T>
01734     T** realloc(T** b, unsigned int n, unsigned int m);
01742     template<class T>
01743     T** realloc(T** b, int n, int m);
01745     void* ralloc(size_t s);
01747     void rfree(void* p, size_t s);
01749     void* rrealloc(void* b, size_t n, size_t m);
01751     template<size_t> void* fl_alloc(void);
01757     template<size_t> void  fl_dispose(FreeList* f, FreeList* l);
01764     size_t allocated(void) const;
01774     GECODE_KERNEL_EXPORT void flush(void);
01776 
01777 
01778 
01781     template<class T> 
01782     T& construct(void);
01788     template<class T, typename A1> 
01789     T& construct(A1 const& a1);
01795     template<class T, typename A1, typename A2> 
01796     T& construct(A1 const& a1, A2 const& a2);
01802     template<class T, typename A1, typename A2, typename A3>
01803     T& construct(A1 const& a1, A2 const& a2, A3 const& a3);
01809     template<class T, typename A1, typename A2, typename A3, typename A4>
01810     T& construct(A1 const& a1, A2 const& a2, A3 const& a3, A4 const& a4);
01816     template<class T, typename A1, typename A2, typename A3, typename A4, typename A5>
01817     T& construct(A1 const& a1, A2 const& a2, A3 const& a3, A4 const& a4, A5 const& a5);
01819 
01825     class Propagators {
01826     private:
01828       const Space& home;
01830       const ActorLink* q;
01832       const ActorLink* c;
01834       const ActorLink* e;
01835     public:
01837       Propagators(const Space& home);
01839       bool operator ()(void) const;
01841       void operator ++(void);
01843       const Propagator& propagator(void) const;
01844     };
01845 
01851     class Branchers {
01852     private:
01854       const ActorLink* c;
01856       const ActorLink* e;
01857     public:
01859       Branchers(const Space& home);
01861       bool operator ()(void) const;
01863       void operator ++(void);
01865       const Brancher& brancher(void) const;
01866     };    
01867   };
01868 
01869 
01870 
01871 
01872   /*
01873    * Memory management
01874    *
01875    */
01876 
01877   // Heap allocated
01878   forceinline void*
01879   SharedHandle::Object::operator new(size_t s) {
01880     return heap.ralloc(s);
01881   }
01882   forceinline void
01883   SharedHandle::Object::operator delete(void* p) {
01884     heap.rfree(p);
01885   }
01886 
01887   forceinline void*
01888   Space::operator new(size_t s) {
01889     return heap.ralloc(s);
01890   }
01891   forceinline void
01892   Space::operator delete(void* p) {
01893     heap.rfree(p);
01894   }
01895 
01896   forceinline void
01897   Choice::operator delete(void* p) {
01898     heap.rfree(p);
01899   }
01900   forceinline void*
01901   Choice::operator new(size_t s) {
01902     return heap.ralloc(s);
01903   }
01904 
01905   // Space allocation: general space heaps and free lists
01906   forceinline void*
01907   Space::ralloc(size_t s) {
01908     return mm.alloc(sm,s);
01909   }
01910   forceinline void
01911   Space::rfree(void* p, size_t s) {
01912     return mm.reuse(p,s);
01913   }
01914   forceinline void*
01915   Space::rrealloc(void* _b, size_t n, size_t m) {
01916     char* b = static_cast<char*>(_b);
01917     if (n < m) {
01918       char* p = static_cast<char*>(ralloc(m));
01919       memcpy(p,b,n);
01920       rfree(b,n);
01921       return p;
01922     } else {
01923       rfree(b+m,m-n);
01924       return b;
01925     }
01926   }
01927 
01928   template<size_t s>
01929   forceinline void*
01930   Space::fl_alloc(void) {
01931     return mm.template fl_alloc<s>(sm);
01932   }
01933   template<size_t s>
01934   forceinline void
01935   Space::fl_dispose(FreeList* f, FreeList* l) {
01936     mm.template fl_dispose<s>(f,l);
01937   }
01938 
01939   forceinline size_t
01940   Space::allocated(void) const {
01941     size_t s = mm.allocated();
01942     for (Actor** a = d_fst; a < d_cur; a++)
01943       s += (*a)->allocated();
01944     return s;
01945   }
01946 
01947   /*
01948    * Typed allocation routines
01949    *
01950    */
01951   template<class T>
01952   forceinline T*
01953   Space::alloc(long unsigned int n) {
01954     T* p = static_cast<T*>(ralloc(sizeof(T)*n));
01955     for (long unsigned int i=n; i--; )
01956       (void) new (p+i) T();
01957     return p;
01958   }
01959   template<class T>
01960   forceinline T*
01961   Space::alloc(long int n) {
01962     assert(n >= 0);
01963     return alloc<T>(static_cast<long unsigned int>(n));
01964   }
01965   template<class T>
01966   forceinline T*
01967   Space::alloc(unsigned int n) {
01968     return alloc<T>(static_cast<long unsigned int>(n));
01969   }
01970   template<class T>
01971   forceinline T*
01972   Space::alloc(int n) {
01973     assert(n >= 0);
01974     return alloc<T>(static_cast<long unsigned int>(n));
01975   }
01976 
01977   template<class T>
01978   forceinline void
01979   Space::free(T* b, long unsigned int n) {
01980     for (long unsigned int i=n; i--; )
01981       b[i].~T();
01982     rfree(b,n*sizeof(T));
01983   }
01984   template<class T>
01985   forceinline void
01986   Space::free(T* b, long int n) {
01987     assert(n >= 0);
01988     free<T>(b,static_cast<long unsigned int>(n));
01989   }
01990   template<class T>
01991   forceinline void
01992   Space::free(T* b, unsigned int n) {
01993     free<T>(b,static_cast<long unsigned int>(n));
01994   }
01995   template<class T>
01996   forceinline void
01997   Space::free(T* b, int n) {
01998     assert(n >= 0);
01999     free<T>(b,static_cast<long unsigned int>(n));
02000   }
02001 
02002   template<class T>
02003   forceinline T*
02004   Space::realloc(T* b, long unsigned int n, long unsigned int m) {
02005     if (n < m) {
02006       T* p = static_cast<T*>(ralloc(sizeof(T)*m));
02007       for (long unsigned int i=n; i--; )
02008         (void) new (p+i) T(b[i]);
02009       for (long unsigned int i=n; i<m; i++)
02010         (void) new (p+i) T();
02011       free<T>(b,n);
02012       return p;
02013     } else {
02014       free<T>(b+m,m-n);
02015       return b;
02016     }
02017   }
02018   template<class T>
02019   forceinline T*
02020   Space::realloc(T* b, long int n, long int m) {
02021     assert((n >= 0) && (m >= 0));
02022     return realloc<T>(b,static_cast<long unsigned int>(n),
02023                       static_cast<long unsigned int>(m));
02024   }
02025   template<class T>
02026   forceinline T*
02027   Space::realloc(T* b, unsigned int n, unsigned int m) {
02028     return realloc<T>(b,static_cast<long unsigned int>(n),
02029                       static_cast<long unsigned int>(m));
02030   }
02031   template<class T>
02032   forceinline T*
02033   Space::realloc(T* b, int n, int m) {
02034     assert((n >= 0) && (m >= 0));
02035     return realloc<T>(b,static_cast<long unsigned int>(n),
02036                       static_cast<long unsigned int>(m));
02037   }
02038 
02039 #define GECODE_KERNEL_REALLOC(T)                                        \
02040   template<>                                                            \
02041   forceinline T*                                                        \
02042   Space::realloc<T>(T* b, long unsigned int n, long unsigned int m) {   \
02043     return static_cast<T*>(rrealloc(b,n*sizeof(T),m*sizeof(T)));        \
02044   }                                                                     \
02045   template<>                                                            \
02046   forceinline T*                                                        \
02047   Space::realloc<T>(T* b, long int n, long int m) {                     \
02048     assert((n >= 0) && (m >= 0));                                       \
02049     return realloc<T>(b,static_cast<long unsigned int>(n),              \
02050                       static_cast<long unsigned int>(m));               \
02051   }                                                                     \
02052   template<>                                                            \
02053   forceinline T*                                                        \
02054   Space::realloc<T>(T* b, unsigned int n, unsigned int m) {             \
02055     return realloc<T>(b,static_cast<long unsigned int>(n),              \
02056                       static_cast<long unsigned int>(m));               \
02057   }                                                                     \
02058   template<>                                                            \
02059   forceinline T*                                                        \
02060   Space::realloc<T>(T* b, int n, int m) {                               \
02061     assert((n >= 0) && (m >= 0));                                       \
02062     return realloc<T>(b,static_cast<long unsigned int>(n),              \
02063                       static_cast<long unsigned int>(m));               \
02064   }
02065 
02066   GECODE_KERNEL_REALLOC(bool)
02067   GECODE_KERNEL_REALLOC(signed char)
02068   GECODE_KERNEL_REALLOC(unsigned char)
02069   GECODE_KERNEL_REALLOC(signed short int)
02070   GECODE_KERNEL_REALLOC(unsigned short int)
02071   GECODE_KERNEL_REALLOC(signed int)
02072   GECODE_KERNEL_REALLOC(unsigned int)
02073   GECODE_KERNEL_REALLOC(signed long int)
02074   GECODE_KERNEL_REALLOC(unsigned long int)
02075   GECODE_KERNEL_REALLOC(float)
02076   GECODE_KERNEL_REALLOC(double)
02077 
02078 #undef GECODE_KERNEL_REALLOC
02079 
02080   template<class T>
02081   forceinline T**
02082   Space::realloc(T** b, long unsigned int n, long unsigned int m) {
02083     return static_cast<T**>(rrealloc(b,n*sizeof(T),m*sizeof(T*)));
02084   }
02085   template<class T>
02086   forceinline T**
02087   Space::realloc(T** b, long int n, long int m) {
02088     assert((n >= 0) && (m >= 0));
02089     return realloc<T*>(b,static_cast<long unsigned int>(n),
02090                        static_cast<long unsigned int>(m));
02091   }
02092   template<class T>
02093   forceinline T**
02094   Space::realloc(T** b, unsigned int n, unsigned int m) {
02095     return realloc<T*>(b,static_cast<long unsigned int>(n),
02096                        static_cast<long unsigned int>(m));
02097   }
02098   template<class T>
02099   forceinline T**
02100   Space::realloc(T** b, int n, int m) {
02101     assert((n >= 0) && (m >= 0));
02102     return realloc<T*>(b,static_cast<long unsigned int>(n),
02103                        static_cast<long unsigned int>(m));
02104   }
02105 
02106 
02107 #ifdef GECODE_HAS_VAR_DISPOSE
02108   template<class VIC>
02109   forceinline VarImpBase*
02110   Space::vars_d(void) const {
02111     return _vars_d[VIC::idx_d];
02112   }
02113   template<class VIC>
02114   forceinline void
02115   Space::vars_d(VarImpBase* x) {
02116     _vars_d[VIC::idx_d] = x;
02117   }
02118 #endif
02119 
02120   // Space allocated entities: Actors, variable implementations, and advisors
02121   forceinline void
02122   Actor::operator delete(void*) {}
02123   forceinline void
02124   Actor::operator delete(void*, Space&) {}
02125   forceinline void*
02126   Actor::operator new(size_t s, Space& home) {
02127     return home.ralloc(s);
02128   }
02129 
02130   template<class VIC>
02131   forceinline void
02132   VarImp<VIC>::operator delete(void*) {}
02133   template<class VIC>
02134   forceinline void
02135   VarImp<VIC>::operator delete(void*, Space&) {}
02136   template<class VIC>
02137   forceinline void*
02138   VarImp<VIC>::operator new(size_t s, Space& home) {
02139     return home.ralloc(s);
02140   }
02141 
02142 #ifndef __GNUC__
02143   forceinline void
02144   Advisor::operator delete(void*) {}
02145 #endif
02146   forceinline void
02147   Advisor::operator delete(void*, Space&) {}
02148   forceinline void*
02149   Advisor::operator new(size_t s, Space& home) {
02150     return home.ralloc(s);
02151   }
02152 
02153   /*
02154    * Shared objects and handles
02155    *
02156    */
02157   forceinline
02158   SharedHandle::Object::Object(void)
02159     : next(NULL), fwd(NULL), use_cnt(0) {}
02160   forceinline
02161   SharedHandle::Object::~Object(void) {
02162     assert(use_cnt == 0);
02163   }
02164 
02165   forceinline SharedHandle::Object*
02166   SharedHandle::object(void) const {
02167     return o;
02168   }
02169   forceinline void
02170   SharedHandle::subscribe(void) {
02171     if (o != NULL) o->use_cnt++;
02172   }
02173   forceinline void
02174   SharedHandle::cancel(void) {
02175     if ((o != NULL) && (--o->use_cnt == 0))
02176       delete o;
02177     o=NULL;
02178   }
02179   forceinline void
02180   SharedHandle::object(SharedHandle::Object* n) {
02181     if (n != o) {
02182       cancel(); o=n; subscribe();
02183     }
02184   }
02185   forceinline
02186   SharedHandle::SharedHandle(void) : o(NULL) {}
02187   forceinline
02188   SharedHandle::SharedHandle(SharedHandle::Object* so) : o(so) {
02189     subscribe();
02190   }
02191   forceinline
02192   SharedHandle::SharedHandle(const SharedHandle& sh) : o(sh.o) {
02193     subscribe();
02194   }
02195   forceinline SharedHandle&
02196   SharedHandle::operator =(const SharedHandle& sh) {
02197     if (&sh != this) {
02198       cancel(); o=sh.o; subscribe();
02199     }
02200     return *this;
02201   }
02202   forceinline void
02203   SharedHandle::update(Space& home, bool share, SharedHandle& sh) {
02204     if (sh.o == NULL) {
02205       o=NULL; return;
02206     } else if (share) {
02207       o=sh.o;
02208     } else if (sh.o->fwd != NULL) {
02209       o=sh.o->fwd;
02210     } else {
02211       o = sh.o->copy();
02212       sh.o->fwd = o;
02213       sh.o->next = home.pc.c.shared;
02214       home.pc.c.shared = sh.o;
02215     }
02216     subscribe();
02217   }
02218   forceinline
02219   SharedHandle::~SharedHandle(void) {
02220     cancel();
02221   }
02222 
02223 
02224 
02225   /*
02226    * ActorLink
02227    *
02228    */
02229   forceinline ActorLink*
02230   ActorLink::prev(void) const {
02231     return _prev;
02232   }
02233 
02234   forceinline ActorLink*
02235   ActorLink::next(void) const {
02236     return _next;
02237   }
02238 
02239   forceinline ActorLink**
02240   ActorLink::next_ref(void) {
02241     return &_next;
02242   }
02243 
02244   forceinline void
02245   ActorLink::prev(ActorLink* al) {
02246     _prev = al;
02247   }
02248 
02249   forceinline void
02250   ActorLink::next(ActorLink* al) {
02251     _next = al;
02252   }
02253 
02254   forceinline void
02255   ActorLink::unlink(void) {
02256     ActorLink* p = _prev; ActorLink* n = _next;
02257     p->_next = n; n->_prev = p;
02258   }
02259 
02260   forceinline void
02261   ActorLink::init(void) {
02262     _next = this; _prev =this;
02263   }
02264 
02265   forceinline void
02266   ActorLink::head(ActorLink* a) {
02267     // Inserts al at head of link-chain (that is, after this)
02268     ActorLink* n = _next;
02269     this->_next = a; a->_prev = this;
02270     a->_next = n; n->_prev = a;
02271   }
02272 
02273   forceinline void
02274   ActorLink::tail(ActorLink* a) {
02275     // Inserts al at tail of link-chain (that is, before this)
02276     ActorLink* p = _prev;
02277     a->_next = this; this->_prev = a;
02278     p->_next = a; a->_prev = p;
02279   }
02280 
02281   forceinline bool
02282   ActorLink::empty(void) const {
02283     return _next == this;
02284   }
02285 
02286   template<class T>
02287   forceinline ActorLink*
02288   ActorLink::cast(T* a) {
02289     // Turning al into a reference is for gcc, assume is for MSVC
02290     GECODE_NOT_NULL(a);
02291     ActorLink& t = *a;
02292     return static_cast<ActorLink*>(&t);
02293   }
02294 
02295   template<class T>
02296   forceinline const ActorLink*
02297   ActorLink::cast(const T* a) {
02298     // Turning al into a reference is for gcc, assume is for MSVC
02299     GECODE_NOT_NULL(a);
02300     const ActorLink& t = *a;
02301     return static_cast<const ActorLink*>(&t);
02302   }
02303 
02304 
02305   /*
02306    * Actor
02307    *
02308    */
02309   forceinline Actor*
02310   Actor::cast(ActorLink* al) {
02311     // Turning al into a reference is for gcc, assume is for MSVC
02312     GECODE_NOT_NULL(al);
02313     ActorLink& t = *al;
02314     return static_cast<Actor*>(&t);
02315   }
02316 
02317   forceinline const Actor*
02318   Actor::cast(const ActorLink* al) {
02319     // Turning al into a reference is for gcc, assume is for MSVC
02320     GECODE_NOT_NULL(al);
02321     const ActorLink& t = *al;
02322     return static_cast<const Actor*>(&t);
02323   }
02324 
02325   forceinline void
02326   Space::notice(Actor& a, ActorProperty p) {
02327     if (p & AP_DISPOSE) {
02328       if (d_cur == d_lst)
02329         d_resize();
02330       *(d_cur++) = &a;
02331     }
02332     if (p & AP_WEAKLY) {
02333       if (n_wmp == 0)
02334         n_wmp = 2;
02335       else
02336         n_wmp++;
02337     }
02338   }
02339 
02340   forceinline void
02341   Home::notice(Actor& a, ActorProperty p) {
02342     s.notice(a,p);
02343   }
02344 
02345   forceinline void
02346   Space::ignore(Actor& a, ActorProperty p) {
02347     if (p & AP_DISPOSE) {
02348       // Check wether array has already been discarded as space
02349       // deletion is already in progress
02350       Actor** f = d_fst;
02351       if (f != NULL) {
02352         while (&a != *f)
02353           f++;
02354         *f = *(--d_cur);
02355       }
02356     }
02357     if (p & AP_WEAKLY) {
02358       assert(n_wmp > 1);
02359       n_wmp--;
02360     }
02361   }
02362 
02363   forceinline Space*
02364   Space::clone(bool share, CloneStatistics&) const {
02365     // Clone is only const for search engines. During cloning, several data
02366     // structures are updated (e.g. forwarding pointers), so we have to
02367     // cast away the constness.
02368     return const_cast<Space*>(this)->_clone(share);
02369   }
02370 
02371   forceinline void
02372   Space::commit(const Choice& c, unsigned int a, CommitStatistics&) {
02373     _commit(c,a);
02374   }
02375 
02376   forceinline size_t
02377   Actor::dispose(Space&) {
02378     return sizeof(*this);
02379   }
02380 
02381 
02382   /*
02383    * Home for posting actors
02384    *
02385    */
02386   forceinline
02387   Home::Home(Space& s0, Propagator* p0) : s(s0), p(p0) {}
02388   forceinline
02389   Home::operator Space&(void) { 
02390     return s; 
02391   }
02392   forceinline Home
02393   Home::operator ()(Propagator& p) {
02394     return Home(s,&p);
02395   }
02396   forceinline Home
02397   Space::operator ()(Propagator& p) {
02398     return Home(*this,&p);
02399   }
02400   forceinline Propagator*
02401   Home::propagator(void) const {
02402     return p;
02403   }
02404 
02405   /*
02406    * Propagator
02407    *
02408    */
02409   forceinline Propagator*
02410   Propagator::cast(ActorLink* al) {
02411     // Turning al into a reference is for gcc, assume is for MSVC
02412     GECODE_NOT_NULL(al);
02413     ActorLink& t = *al;
02414     return static_cast<Propagator*>(&t);
02415   }
02416 
02417   forceinline const Propagator*
02418   Propagator::cast(const ActorLink* al) {
02419     // Turning al into a reference is for gcc, assume is for MSVC
02420     GECODE_NOT_NULL(al);
02421     const ActorLink& t = *al;
02422     return static_cast<const Propagator*>(&t);
02423   }
02424 
02425   forceinline
02426   Propagator::Propagator(Home home) 
02427     : pi((home.propagator() != NULL) ?
02428          // Inherit propagator information
02429          home.propagator()->pi :
02430          // New propagator information
02431          static_cast<Space&>(home).gpi.allocate()) {
02432     u.advisors = NULL;
02433     assert((u.med == 0) && (u.size == 0));
02434     static_cast<Space&>(home).pl.head(this);
02435   }
02436 
02437   forceinline
02438   Propagator::Propagator(Space&, bool, Propagator& p) 
02439     : pi(p.pi) {
02440     u.advisors = NULL;
02441     assert((u.med == 0) && (u.size == 0));
02442     // Set forwarding pointer
02443     p.prev(this);
02444   }
02445 
02446   forceinline double
02447   Propagator::afc(void) const {
02448     return pi.afc();
02449   }
02450 
02451   forceinline ExecStatus
02452   Space::ES_SUBSUMED_DISPOSED(Propagator& p, size_t s) {
02453     p.u.size = s;
02454     return __ES_SUBSUMED;
02455   }
02456 
02457   forceinline ExecStatus
02458   Space::ES_SUBSUMED(Propagator& p) {
02459     p.u.size = p.dispose(*this);
02460     return __ES_SUBSUMED;
02461   }
02462 
02463   forceinline ExecStatus
02464   Space::ES_FIX_PARTIAL(Propagator& p, const ModEventDelta& med) {
02465     p.u.med = med;
02466     assert(p.u.med != 0);
02467     return __ES_PARTIAL;
02468   }
02469 
02470   forceinline ExecStatus
02471   Space::ES_NOFIX_PARTIAL(Propagator& p, const ModEventDelta& med) {
02472     p.u.med = AllVarConf::med_combine(p.u.med,med);
02473     assert(p.u.med != 0);
02474     return __ES_PARTIAL;
02475   }
02476 
02477 
02478 
02479   /*
02480    * Brancher
02481    *
02482    */
02483   forceinline Brancher*
02484   Brancher::cast(ActorLink* al) {
02485     // Turning al into a reference is for gcc, assume is for MSVC
02486     GECODE_NOT_NULL(al);
02487     ActorLink& t = *al;
02488     return static_cast<Brancher*>(&t);
02489   }
02490 
02491   forceinline const Brancher*
02492   Brancher::cast(const ActorLink* al) {
02493     // Turning al into a reference is for gcc, assume is for MSVC
02494     GECODE_NOT_NULL(al);
02495     const ActorLink& t = *al;
02496     return static_cast<const Brancher*>(&t);
02497   }
02498 
02499   forceinline
02500   Brancher::Brancher(Home home) :
02501     _id(static_cast<Space&>(home).pc.p.branch_id++) {
02502     if (static_cast<Space&>(home).pc.p.branch_id == 0U)
02503       throw TooManyBranchers("Brancher::Brancher");
02504     // If no brancher available, make it the first one
02505     if (static_cast<Space&>(home).b_status == &static_cast<Space&>(home).bl) {
02506       static_cast<Space&>(home).b_status = this;
02507       if (static_cast<Space&>(home).b_commit == &static_cast<Space&>(home).bl)
02508         static_cast<Space&>(home).b_commit = this;
02509     }
02510     static_cast<Space&>(home).bl.tail(this);
02511   }
02512 
02513   forceinline
02514   Brancher::Brancher(Space&, bool, Brancher& b)
02515     : _id(b._id) {
02516     // Set forwarding pointer
02517     b.prev(this);
02518   }
02519 
02520   forceinline unsigned int
02521   Brancher::id(void) const {
02522     return _id;
02523   }
02524 
02525 
02526 
02527   /*
02528    * Choices
02529    *
02530    */
02531   forceinline
02532   Choice::Choice(const Brancher& b, const unsigned int a)
02533     : _id(b.id()), _alt(a) {}
02534 
02535   forceinline unsigned int
02536   Choice::alternatives(void) const {
02537     return _alt;
02538   }
02539 
02540   forceinline unsigned int
02541   Choice::id(void) const {
02542     return _id;
02543   }
02544 
02545   forceinline
02546   Choice::~Choice(void) {}
02547 
02548 
02549 
02550   /*
02551    * Delta information for advisors
02552    *
02553    */
02554   forceinline ModEvent
02555   Delta::modevent(void) const {
02556     return me;
02557   }
02558 
02559 
02560 
02561   /*
02562    * Advisor
02563    *
02564    */
02565   template<class A>
02566   forceinline
02567   Advisor::Advisor(Space&, Propagator& p, Council<A>& c) {
02568     // Store propagator and forwarding in prev()
02569     ActorLink::prev(&p);
02570     // Link to next advisor in next()
02571     ActorLink::next(c.advisors); c.advisors = static_cast<A*>(this);
02572   }
02573 
02574   forceinline
02575   Advisor::Advisor(Space&, bool, Advisor&) {}
02576 
02577   forceinline bool
02578   Advisor::disposed(void) const {
02579     return prev() == NULL;
02580   }
02581 
02582   forceinline Advisor*
02583   Advisor::cast(ActorLink* al) {
02584     return static_cast<Advisor*>(al);
02585   }
02586 
02587   forceinline const Advisor*
02588   Advisor::cast(const ActorLink* al) {
02589     return static_cast<const Advisor*>(al);
02590   }
02591 
02592   forceinline Propagator&
02593   Advisor::propagator(void) const {
02594     assert(!disposed());
02595     return *Propagator::cast(ActorLink::prev());
02596   }
02597 
02598   template<class A>
02599   forceinline void
02600   Advisor::dispose(Space&,Council<A>&) {
02601     assert(!disposed());
02602     ActorLink::prev(NULL);
02603     // Shorten chains of disposed advisors by one, if possible
02604     Advisor* n = Advisor::cast(next());
02605     if ((n != NULL) && n->disposed())
02606       next(n->next());
02607   }
02608 
02609   template<class A>
02610   forceinline ExecStatus
02611   Space::ES_FIX_DISPOSE(Council<A>& c, A& a) {
02612     a.dispose(*this,c);
02613     return ES_FIX;
02614   }
02615 
02616   template<class A>
02617   forceinline ExecStatus
02618   Space::ES_NOFIX_DISPOSE(Council<A>& c, A& a) {
02619     a.dispose(*this,c);
02620     return ES_NOFIX;
02621   }
02622 
02623   template<class A>
02624   forceinline ExecStatus
02625   Space::ES_NOFIX_DISPOSE_FORCE(Council<A>& c, A& a) {
02626     a.dispose(*this,c);
02627     return ES_NOFIX_FORCE;
02628   }
02629 
02630 
02631 
02632   /*
02633    * Advisor council
02634    *
02635    */
02636   template<class A>
02637   forceinline
02638   Council<A>::Council(void) {}
02639 
02640   template<class A>
02641   forceinline
02642   Council<A>::Council(Space&)
02643     : advisors(NULL) {}
02644 
02645   template<class A>
02646   forceinline bool
02647   Council<A>::empty(void) const {
02648     ActorLink* a = advisors;
02649     while ((a != NULL) && static_cast<A*>(a)->disposed())
02650       a = a->next();
02651     advisors = a;
02652     return a == NULL;
02653   }
02654 
02655   template<class A>
02656   forceinline void
02657   Council<A>::update(Space& home, bool share, Council<A>& c) {
02658     // Skip all disposed advisors
02659     {
02660       ActorLink* a = c.advisors;
02661       while ((a != NULL) && static_cast<A*>(a)->disposed())
02662         a = a->next();
02663       c.advisors = a;
02664     }
02665     // Are there any advisors to be cloned?
02666     if (c.advisors != NULL) {
02667       // The propagator in from-space
02668       Propagator* p_f = &static_cast<A*>(c.advisors)->propagator();
02669       // The propagator in to-space
02670       Propagator* p_t = Propagator::cast(p_f->prev());
02671       // Advisors in from-space
02672       ActorLink** a_f = &c.advisors;
02673       // Advisors in to-space
02674       A* a_t = NULL;
02675       while (*a_f != NULL) {
02676         if (static_cast<A*>(*a_f)->disposed()) {
02677           *a_f = (*a_f)->next();
02678         } else {
02679           // Run specific copying part
02680           A* a = new (home) A(home,share,*static_cast<A*>(*a_f));
02681           // Set propagator pointer
02682           a->prev(p_t);
02683           // Set forwarding pointer
02684           (*a_f)->prev(a);
02685           // Link
02686           a->next(a_t);
02687           a_t = a;
02688           a_f = (*a_f)->next_ref();
02689         }
02690       }
02691       advisors = a_t;
02692       // Enter advisor link for reset
02693       assert(p_f->u.advisors == NULL);
02694       p_f->u.advisors = c.advisors;
02695     } else {
02696       advisors = NULL;
02697     }
02698   }
02699 
02700   template<class A>
02701   forceinline void
02702   Council<A>::dispose(Space& home) {
02703     ActorLink* a = advisors;
02704     while (a != NULL) {
02705       if (!static_cast<A*>(a)->disposed())
02706         static_cast<A*>(a)->dispose(home,*this);
02707       a = a->next();
02708     }
02709   }
02710 
02711 
02712 
02713   /*
02714    * Advisor iterator
02715    *
02716    */
02717   template<class A>
02718   forceinline
02719   Advisors<A>::Advisors(const Council<A>& c)
02720     : a(c.advisors) {
02721     while ((a != NULL) && static_cast<A*>(a)->disposed())
02722       a = a->next();
02723   }
02724 
02725   template<class A>
02726   forceinline bool
02727   Advisors<A>::operator ()(void) const {
02728     return a != NULL;
02729   }
02730 
02731   template<class A>
02732   forceinline void
02733   Advisors<A>::operator ++(void) {
02734     do {
02735       a = a->next();
02736     } while ((a != NULL) && static_cast<A*>(a)->disposed());
02737   }
02738 
02739   template<class A>
02740   forceinline A&
02741   Advisors<A>::advisor(void) const {
02742     return *static_cast<A*>(a);
02743   }
02744 
02745 
02746 
02747   /*
02748    * Space
02749    *
02750    */
02751   forceinline void
02752   Space::enqueue(Propagator* p) {
02753     ActorLink::cast(p)->unlink();
02754     ActorLink* c = &pc.p.queue[p->cost(*this,p->u.med).ac];
02755     c->tail(ActorLink::cast(p));
02756     if (c > pc.p.active)
02757       pc.p.active = c;
02758   }
02759 
02760   forceinline void
02761   Space::fail(void) {
02762     pc.p.active = NULL;
02763   }
02764   forceinline void
02765   Home::fail(void) {
02766     s.fail();
02767   }
02768 
02769   forceinline bool
02770   Space::failed(void) const {
02771     return pc.p.active == NULL;
02772   }
02773   forceinline bool
02774   Home::failed(void) const {
02775     return s.failed();
02776   }
02777 
02778   forceinline bool
02779   Space::stable(void) const {
02780     return pc.p.active < &pc.p.queue[0];
02781   }
02782 
02783 
02784 
02785   /*
02786    * Variable implementation
02787    *
02788    */
02789   template<class VIC>
02790   forceinline ActorLink**
02791   VarImp<VIC>::actor(PropCond pc) {
02792     assert((pc >= 0)  && (pc < pc_max+2));
02793     return (pc == 0) ? base : base+u.idx[pc-1];
02794   }
02795 
02796   template<class VIC>
02797   forceinline ActorLink**
02798   VarImp<VIC>::actorNonZero(PropCond pc) {
02799     assert((pc > 0)  && (pc < pc_max+2));
02800     return base+u.idx[pc-1];
02801   }
02802 
02803   template<class VIC>
02804   forceinline unsigned int&
02805   VarImp<VIC>::idx(PropCond pc) {
02806     assert((pc > 0)  && (pc < pc_max+2));
02807     return u.idx[pc-1];
02808   }
02809 
02810   template<class VIC>
02811   forceinline unsigned int
02812   VarImp<VIC>::idx(PropCond pc) const {
02813     assert((pc > 0)  && (pc < pc_max+2));
02814     return u.idx[pc-1];
02815   }
02816 
02817   template<class VIC>
02818   forceinline
02819   VarImp<VIC>::VarImp(Space&) {
02820     base = NULL; entries = 0;
02821     for (PropCond pc=1; pc<pc_max+2; pc++)
02822       idx(pc) = 0;
02823     free_and_bits = 0;
02824   }
02825 
02826   template<class VIC>
02827   forceinline
02828   VarImp<VIC>::VarImp(void) {
02829     base = NULL; entries = 0;
02830     for (PropCond pc=1; pc<pc_max+2; pc++)
02831       idx(pc) = 0;
02832     free_and_bits = 0;
02833   }
02834 
02835   template<class VIC>
02836   forceinline unsigned int
02837   VarImp<VIC>::degree(void) const {
02838     assert(!copied());
02839     return entries;
02840   }
02841 
02842   template<class VIC>
02843   forceinline double
02844   VarImp<VIC>::afc(void) const {
02845     if (degree() == 0)
02846       return 0.0;
02847     double d = degree();
02848     // Count the afc of each propagator
02849     {
02850       ActorLink** a = const_cast<VarImp<VIC>*>(this)->actor(0);
02851       ActorLink** e = const_cast<VarImp<VIC>*>(this)->actorNonZero(pc_max+1);
02852       while (a < e) {
02853         d += Propagator::cast(*a)->afc(); a++;
02854       }
02855     }
02856     // Count the afc of each advisor's propagator
02857     {
02858       ActorLink** a = const_cast<VarImp<VIC>*>(this)->actorNonZero(pc_max+1);
02859       ActorLink** e = const_cast<VarImp<VIC>*>(this)->base+entries;
02860       while (a < e) {
02861         d += Advisor::cast(*a)->propagator().afc(); a++;
02862       }
02863     }
02864     return d;
02865   }
02866 
02867   template<class VIC>
02868   forceinline unsigned int
02869   VarImp<VIC>::bits(void) const {
02870     return free_and_bits;
02871   }
02872 
02873   template<class VIC>
02874   forceinline unsigned int&
02875   VarImp<VIC>::bits(void) {
02876     return free_and_bits;
02877   }
02878 
02879 #ifdef GECODE_HAS_VAR_DISPOSE
02880   template<class VIC>
02881   forceinline VarImp<VIC>*
02882   VarImp<VIC>::vars_d(Space& home) {
02883     return static_cast<VarImp<VIC>*>(home.vars_d<VIC>());
02884   }
02885 
02886   template<class VIC>
02887   forceinline void
02888   VarImp<VIC>::vars_d(Space& home, VarImp<VIC>* x) {
02889     home.vars_d<VIC>(x);
02890   }
02891 #endif
02892 
02893   template<class VIC>
02894   forceinline bool
02895   VarImp<VIC>::copied(void) const {
02896     return Support::marked(base);
02897   }
02898 
02899   template<class VIC>
02900   forceinline VarImp<VIC>*
02901   VarImp<VIC>::forward(void) const {
02902     assert(copied());
02903     return reinterpret_cast<VarImp<VIC>*>(Support::unmark(base));
02904   }
02905 
02906   template<class VIC>
02907   forceinline VarImp<VIC>*
02908   VarImp<VIC>::next(void) const {
02909     assert(copied());
02910     return u.next;
02911   }
02912 
02913   template<class VIC>
02914   forceinline
02915   VarImp<VIC>::VarImp(Space& home, bool, VarImp<VIC>& x) {
02916     VarImpBase** reg;
02917     free_and_bits = x.free_and_bits & ((1 << free_bits) - 1);
02918     if (x.base == NULL) {
02919       // Variable implementation needs no index structure
02920       reg = &home.pc.c.vars_noidx;
02921       assert(x.degree() == 0);
02922     } else {
02923       reg = &home.pc.c.vars_u[idx_c];
02924     }
02925     // Save subscriptions in copy
02926     base = x.base;
02927     entries = x.entries;
02928     for (PropCond pc=1; pc<pc_max+2; pc++)
02929       idx(pc) = x.idx(pc);
02930 
02931     // Set forwarding pointer
02932     x.base = reinterpret_cast<ActorLink**>(Support::mark(this));
02933     // Register original
02934     x.u.next = static_cast<VarImp<VIC>*>(*reg); *reg = &x;
02935   }
02936 
02937   template<class VIC>
02938   forceinline ModEvent
02939   VarImp<VIC>::me(const ModEventDelta& med) {
02940     return static_cast<ModEvent>((med & VIC::med_mask) >> VIC::med_fst);
02941   }
02942 
02943   template<class VIC>
02944   forceinline ModEventDelta
02945   VarImp<VIC>::med(ModEvent me) {
02946     return static_cast<ModEventDelta>(me << VIC::med_fst);
02947   }
02948 
02949   template<class VIC>
02950   forceinline ModEvent
02951   VarImp<VIC>::me_combine(ModEvent me1, ModEvent me2) {
02952     return VIC::me_combine(me1,me2);
02953   }
02954 
02955   template<class VIC>
02956   forceinline void
02957   VarImp<VIC>::schedule(Space& home, Propagator& p, ModEvent me,
02958                         bool force) {
02959     if (VIC::med_update(p.u.med,me) || force)
02960       home.enqueue(&p);
02961   }
02962 
02963   template<class VIC>
02964   forceinline void
02965   VarImp<VIC>::schedule(Space& home, PropCond pc1, PropCond pc2, ModEvent me) {
02966     ActorLink** b = actor(pc1);
02967     ActorLink** p = actorNonZero(pc2+1);
02968     while (p-- > b)
02969       schedule(home,*Propagator::cast(*p),me);
02970   }
02971 
02972   template<class VIC>
02973   forceinline void
02974   VarImp<VIC>::enter(Space& home, Propagator* p, PropCond pc) {
02975     assert(pc <= pc_max);
02976     // Count one new subscription
02977     home.pc.p.n_sub += 1;
02978     if ((free_and_bits >> free_bits) == 0)
02979       resize(home);
02980     free_and_bits -= 1 << free_bits;
02981 
02982     // Enter subscription
02983     base[entries] = *actorNonZero(pc_max+1);
02984     entries++;
02985     for (PropCond j = pc_max; j > pc; j--) {
02986       *actorNonZero(j+1) = *actorNonZero(j);
02987       idx(j+1)++;
02988     }
02989     *actorNonZero(pc+1) = *actor(pc);
02990     idx(pc+1)++;
02991     *actor(pc) = ActorLink::cast(p);
02992 
02993 #ifdef GECODE_AUDIT
02994     ActorLink** f = actor(pc);
02995     while (f < (pc == pc_max+1 ? base+entries : actorNonZero(pc+1)))
02996       if (*f == p)
02997         goto found;
02998       else
02999         f++;
03000     GECODE_NEVER;
03001     found: ;
03002 #endif
03003   }
03004 
03005   template<class VIC>
03006   forceinline void
03007   VarImp<VIC>::enter(Space& home, Advisor* a) {
03008     // Count one new subscription
03009     home.pc.p.n_sub += 1;
03010     if ((free_and_bits >> free_bits) == 0)
03011       resize(home);
03012     free_and_bits -= 1 << free_bits;
03013 
03014     // Enter subscription
03015     base[entries++] = *actorNonZero(pc_max+1);
03016     *actorNonZero(pc_max+1) = a;
03017   }
03018 
03019   template<class VIC>
03020   void
03021   VarImp<VIC>::resize(Space& home) {
03022     if (base == NULL) {
03023       assert((free_and_bits >> free_bits) == 0);
03024       // Create fresh dependency array with four entries
03025       free_and_bits += 4 << free_bits;
03026       base = home.alloc<ActorLink*>(4);
03027       for (int i=0; i<pc_max+1; i++)
03028         u.idx[i] = 0;
03029     } else {
03030       // Resize dependency array
03031       unsigned int n = degree();
03032       // Find out whether the area is most likely in the special area
03033       // reserved for subscriptions. If yes, just resize mildly otherwise
03034       // more agressively
03035       ActorLink** s = static_cast<ActorLink**>(home.mm.subscriptions());
03036       unsigned int m =
03037         ((s <= base) && (base < s+home.pc.p.n_sub)) ?
03038         (n+4) : ((n+1)*3>>1);
03039       ActorLink** prop = home.alloc<ActorLink*>(m);
03040       free_and_bits += (m-n) << free_bits;
03041       // Copy entries
03042       Heap::copy<ActorLink*>(prop, base, n);
03043       home.free<ActorLink*>(base,n);
03044       base = prop;
03045     }
03046   }
03047 
03048   template<class VIC>
03049   void
03050   VarImp<VIC>::subscribe(Space& home, Propagator& p, PropCond pc,
03051                          bool assigned, ModEvent me, bool schedule) {
03052     if (assigned) {
03053       // Do not subscribe, just schedule the propagator
03054       if (schedule)
03055         VarImp<VIC>::schedule(home,p,ME_GEN_ASSIGNED);
03056     } else {
03057       enter(home,&p,pc);
03058       // Schedule propagator
03059       if (schedule && (pc != PC_GEN_ASSIGNED))
03060         VarImp<VIC>::schedule(home,p,me);
03061     }
03062   }
03063 
03064   template<class VIC>
03065   forceinline void
03066   VarImp<VIC>::subscribe(Space& home, Advisor& a, bool assigned) {
03067     if (!assigned)
03068       enter(home,&a);
03069   }
03070 
03071   template<class VIC>
03072   forceinline void
03073   VarImp<VIC>::remove(Space& home, Propagator* p, PropCond pc) {
03074     assert(pc <= pc_max);
03075     ActorLink* a = ActorLink::cast(p);
03076     // Find actor in dependency array
03077     ActorLink** f = actor(pc);
03078 #ifdef GECODE_AUDIT
03079     while (f < actorNonZero(pc+1))
03080       if (*f == a)
03081         goto found;
03082       else
03083         f++;
03084     GECODE_NEVER;
03085   found: ;
03086 #else
03087     while (*f != a) f++;
03088 #endif
03089     // Remove actor
03090     *f = *(actorNonZero(pc+1)-1);
03091     for (PropCond j = pc+1; j< pc_max+1; j++) {
03092       *(actorNonZero(j)-1) = *(actorNonZero(j+1)-1);
03093       idx(j)--;
03094     }
03095     *(actorNonZero(pc_max+1)-1) = base[entries-1];
03096     idx(pc_max+1)--;
03097     entries--;
03098     free_and_bits += 1 << free_bits;
03099     home.pc.p.n_sub -= 1;
03100   }
03101 
03102   template<class VIC>
03103   forceinline void
03104   VarImp<VIC>::remove(Space& home, Advisor* a) {
03105     // Find actor in dependency array
03106     ActorLink** f = actorNonZero(pc_max+1);
03107 #ifdef GECODE_AUDIT
03108     while (f < base+entries)
03109       if (*f == a)
03110         goto found;
03111       else
03112         f++;
03113     GECODE_NEVER;
03114   found: ;
03115 #else
03116     while (*f != a) f++;
03117 #endif
03118     // Remove actor
03119     *f = base[--entries];
03120     free_and_bits += 1 << free_bits;
03121     home.pc.p.n_sub -= 1;
03122   }
03123 
03124   template<class VIC>
03125   forceinline void
03126   VarImp<VIC>::cancel(Space& home, Propagator& p, PropCond pc, bool assigned) {
03127     if (!assigned)
03128       remove(home,&p,pc);
03129   }
03130 
03131   template<class VIC>
03132   forceinline void
03133   VarImp<VIC>::cancel(Space& home, Advisor& a, bool assigned) {
03134     if (!assigned)
03135       remove(home,&a);
03136   }
03137 
03138   template<class VIC>
03139   forceinline void
03140   VarImp<VIC>::cancel(Space& home) {
03141     unsigned int n_sub = degree();
03142     home.pc.p.n_sub -= n_sub;
03143     unsigned int n = (free_and_bits >> VIC::free_bits) + n_sub;
03144     home.free<ActorLink*>(base,n);
03145     // Must be NULL such that cloning works
03146     base = NULL;
03147     // Must be 0 such that degree works
03148     entries = 0;
03149   }
03150 
03151   template<class VIC>
03152   forceinline bool
03153   VarImp<VIC>::advise(Space& home, ModEvent me, Delta& d) {
03154     /*
03155      * An advisor that is executed might remove itself due to subsumption.
03156      * As entries are removed from front to back, the advisors must
03157      * be iterated in forward direction.
03158      */
03159     ActorLink** la = actorNonZero(pc_max+1);
03160     ActorLink** le = base+entries;
03161     if (la == le)
03162       return true;
03163     d.me = me;
03164     // An advisor that is run, might be removed during execution.
03165     // As removal is done from the back the advisors have to be executed
03166     // in inverse order.
03167     do {
03168       Advisor* a = Advisor::cast(*la);
03169       assert(!a->disposed());
03170       Propagator& p = a->propagator();
03171       switch (p.advise(home,*a,d)) {
03172       case ES_FIX:
03173         break;
03174       case ES_FAILED:
03175         p.pi.fail(home.gpi);
03176         return false;
03177       case ES_NOFIX:
03178         schedule(home,p,me);
03179         break;
03180       case ES_NOFIX_FORCE:
03181         schedule(home,p,me,true);
03182         break;
03183       default:
03184         GECODE_NEVER;
03185       }
03186     } while (++la < le);
03187     return true;
03188   }
03189 
03190   template<class VIC>
03191   forceinline void
03192   VarImp<VIC>::update(VarImp<VIC>* x, ActorLink**& sub) {
03193     // this refers to the variable to be updated (clone)
03194     // x refers to the original
03195     // Recover from copy
03196     x->base = base;
03197     x->u.idx[0] = u.idx[0];
03198     if (pc_max > 0 && sizeof(ActorLink**) > sizeof(unsigned int))
03199       x->u.idx[1] = u.idx[1];
03200 
03201     ActorLink** f = x->base;
03202     unsigned int n = x->degree();
03203     ActorLink** t = sub;
03204     sub += n;
03205     base = t;
03206     // Set subscriptions using actor forwarding pointers
03207     while (n >= 4) {
03208       n -= 4;
03209       t[0]=f[0]->prev(); t[1]=f[1]->prev();
03210       t[2]=f[2]->prev(); t[3]=f[3]->prev();
03211       t += 4; f += 4;
03212     }
03213     if (n >= 2) {
03214       n -= 2;
03215       t[0]=f[0]->prev(); t[1]=f[1]->prev();
03216       t += 2; f += 2;
03217     }
03218     if (n > 0) {
03219       t[0]=f[0]->prev();
03220     }
03221   }
03222 
03223   template<class VIC>
03224   forceinline void
03225   VarImp<VIC>::update(Space& home, ActorLink**& sub) {
03226     VarImp<VIC>* x = static_cast<VarImp<VIC>*>(home.pc.c.vars_u[idx_c]);
03227     while (x != NULL) {
03228       VarImp<VIC>* n = x->next(); x->forward()->update(x,sub); x = n;
03229     }
03230   }
03231 
03232 
03233 
03234   /*
03235    * Variable disposer
03236    *
03237    */
03238   template<class VarType>
03239   VarDisposer<VarType>::VarDisposer(void) {
03240 #ifdef GECODE_HAS_VAR_DISPOSE
03241     Space::vd[VarType::idx_d] = this;
03242 #endif
03243   }
03244 
03245   template<class VarType>
03246   void
03247   VarDisposer<VarType>::dispose(Space& home, VarImpBase* _x) {
03248     VarType* x = static_cast<VarType*>(_x);
03249     do {
03250       x->dispose(home); x = static_cast<VarType*>(x->next_d());
03251     } while (x != NULL);
03252   }
03253 
03254   /*
03255    * Statistics
03256    */
03257 
03258   forceinline void
03259   StatusStatistics::reset(void) {
03260     propagate = 0;
03261     wmp = false;
03262   }
03263   forceinline
03264   StatusStatistics::StatusStatistics(void) {
03265     reset();
03266   }
03267   forceinline StatusStatistics&
03268   StatusStatistics::operator +=(const StatusStatistics& s) { 
03269     propagate += s.propagate;
03270     wmp |= s.wmp;
03271     return *this;
03272   }
03273   forceinline StatusStatistics
03274   StatusStatistics::operator +(const StatusStatistics& s) {
03275     StatusStatistics t(s);
03276     return t += *this;
03277   }
03278 
03279   forceinline void
03280   CloneStatistics::reset(void) {}
03281 
03282   forceinline
03283   CloneStatistics::CloneStatistics(void) {
03284     reset();
03285   }
03286   forceinline CloneStatistics
03287   CloneStatistics::operator +(const CloneStatistics&) {
03288     CloneStatistics s;
03289     return s;
03290   }
03291   forceinline CloneStatistics&
03292   CloneStatistics::operator +=(const CloneStatistics&) { 
03293     return *this;
03294   }
03295 
03296   forceinline void
03297   CommitStatistics::reset(void) {}
03298 
03299   forceinline
03300   CommitStatistics::CommitStatistics(void) {
03301     reset();
03302   }
03303   forceinline CommitStatistics
03304   CommitStatistics::operator +(const CommitStatistics&) {
03305     CommitStatistics s;
03306     return s;
03307   }
03308   forceinline CommitStatistics&
03309   CommitStatistics::operator +=(const CommitStatistics&) { 
03310     return *this;
03311   }
03312 
03313   /*
03314    * Cost computation
03315    *
03316    */
03317 
03318   forceinline
03319   PropCost::PropCost(PropCost::ActualCost ac0) : ac(ac0) {}
03320 
03321   forceinline PropCost
03322   PropCost::cost(PropCost::Mod m,
03323                  PropCost::ActualCost lo, PropCost::ActualCost hi,
03324                  unsigned int n) {
03325     if (n < 2)
03326       return (m == LO) ? AC_UNARY_LO : AC_UNARY_HI;
03327     else if (n == 2)
03328       return (m == LO) ? AC_BINARY_LO : AC_BINARY_HI;
03329     else if (n == 3)
03330       return (m == LO) ? AC_TERNARY_LO : AC_TERNARY_HI;
03331     else
03332       return (m == LO) ? lo : hi;
03333   }
03334 
03335   forceinline PropCost
03336   PropCost::crazy(PropCost::Mod m, unsigned int n) {
03337     return cost(m,AC_CRAZY_LO,AC_CRAZY_HI,n);
03338   }
03339   forceinline PropCost
03340   PropCost::crazy(PropCost::Mod m, int n) {
03341     assert(n >= 0);
03342     return crazy(m,static_cast<unsigned int>(n));
03343   }
03344   forceinline PropCost
03345   PropCost::cubic(PropCost::Mod m, unsigned int n) {
03346     return cost(m,AC_CUBIC_LO,AC_CUBIC_HI,n);
03347   }
03348   forceinline PropCost
03349   PropCost::cubic(PropCost::Mod m, int n) {
03350     assert(n >= 0);
03351     return cubic(m,static_cast<unsigned int>(n));
03352   }
03353   forceinline PropCost
03354   PropCost::quadratic(PropCost::Mod m, unsigned int n) {
03355     return cost(m,AC_QUADRATIC_LO,AC_QUADRATIC_HI,n);
03356   }
03357   forceinline PropCost
03358   PropCost::quadratic(PropCost::Mod m, int n) {
03359     assert(n >= 0);
03360     return quadratic(m,static_cast<unsigned int>(n));
03361   }
03362   forceinline PropCost
03363   PropCost::linear(PropCost::Mod m, unsigned int n) {
03364     return cost(m,AC_LINEAR_LO,AC_LINEAR_HI,n);
03365   }
03366   forceinline PropCost
03367   PropCost::linear(PropCost::Mod m, int n) {
03368     assert(n >= 0);
03369     return linear(m,static_cast<unsigned int>(n));
03370   }
03371   forceinline PropCost
03372   PropCost::ternary(PropCost::Mod m) {
03373     return (m == LO) ? AC_TERNARY_LO : AC_TERNARY_HI;
03374   }
03375   forceinline PropCost
03376   PropCost::binary(PropCost::Mod m) {
03377     return (m == LO) ? AC_BINARY_LO : AC_BINARY_HI;
03378   }
03379   forceinline PropCost
03380   PropCost::unary(PropCost::Mod m) {
03381     return (m == LO) ? AC_UNARY_LO : AC_UNARY_HI;
03382   }
03383 
03384   /*
03385    * Iterators for propagators and branchers of a space
03386    *
03387    */
03388   forceinline
03389   Space::Propagators::Propagators(const Space& home0) 
03390     : home(home0), q(home.pc.p.active) {
03391     while (q >= &home.pc.p.queue[0]) {
03392       if (q->next() != q) {
03393         c = q->next(); e = q; q--;
03394         return;
03395       }
03396       q--;
03397     }
03398     q = NULL;
03399     if (!home.pl.empty()) {
03400       c = Propagator::cast(home.pl.next());
03401       e = Propagator::cast(&home.pl);
03402     } else {
03403       c = e = NULL;
03404     }
03405   }
03406   forceinline bool 
03407   Space::Propagators::operator ()(void) const {
03408     return c != NULL;
03409   }
03410   forceinline void 
03411   Space::Propagators::operator ++(void) {
03412     c = c->next();
03413     if (c == e) {
03414       if (q == NULL) {
03415         c = NULL;
03416       } else {
03417         while (q >= &home.pc.p.queue[0]) {
03418           if (q->next() != q) {
03419             c = q->next(); e = q; q--;
03420             return;
03421           }
03422           q--;
03423         }
03424         q = NULL;
03425         if (!home.pl.empty()) {
03426           c = Propagator::cast(home.pl.next());
03427           e = Propagator::cast(&home.pl);
03428         } else {
03429           c = NULL;
03430         }
03431       }
03432     }
03433   }
03434   forceinline const Propagator& 
03435   Space::Propagators::propagator(void) const {
03436     return *Propagator::cast(c);
03437   }
03438 
03439   forceinline
03440   Space::Branchers::Branchers(const Space& home) 
03441     : c(Brancher::cast(home.bl.next())), e(&home.bl) {}
03442   forceinline bool 
03443   Space::Branchers::operator ()(void) const {
03444     return c != e;
03445   }
03446   forceinline void 
03447   Space::Branchers::operator ++(void) {
03448     c = c->next();
03449   }
03450   forceinline const Brancher& 
03451   Space::Branchers::brancher(void) const {
03452     return *Brancher::cast(c);
03453   }
03454 
03455   /*
03456    * Space construction support
03457    *
03458    */
03459   template<class T> 
03460   forceinline T& 
03461   Space::construct(void) {
03462     return alloc<T>(1);
03463   }
03464   template<class T, typename A1> 
03465   forceinline T& 
03466   Space::construct(A1 const& a1) {
03467     T& t = *static_cast<T*>(ralloc(sizeof(T)));
03468     new (&t) T(a1);
03469     return t;
03470   }
03471   template<class T, typename A1, typename A2> 
03472   forceinline T& 
03473   Space::construct(A1 const& a1, A2 const& a2) {
03474     T& t = *static_cast<T*>(ralloc(sizeof(T)));
03475     new (&t) T(a1,a2);
03476     return t;
03477   }
03478   template<class T, typename A1, typename A2, typename A3>
03479   forceinline T& 
03480   Space::construct(A1 const& a1, A2 const& a2, A3 const& a3) {
03481     T& t = *static_cast<T*>(ralloc(sizeof(T)));
03482     new (&t) T(a1,a2,a3);
03483     return t;
03484   }
03485   template<class T, typename A1, typename A2, typename A3, typename A4>
03486   forceinline T& 
03487   Space::construct(A1 const& a1, A2 const& a2, A3 const& a3, A4 const& a4) {
03488     T& t = *static_cast<T*>(ralloc(sizeof(T)));
03489     new (&t) T(a1,a2,a3,a4);
03490     return t;
03491   }
03492   template<class T, typename A1, typename A2, typename A3, typename A4, typename A5>
03493   forceinline T& 
03494   Space::construct(A1 const& a1, A2 const& a2, A3 const& a3, A4 const& a4, A5 const& a5) {
03495     T& t = *static_cast<T*>(ralloc(sizeof(T)));
03496     new (&t) T(a1,a2,a3,a4,a5);
03497     return t;
03498   }
03499 
03500 }
03501 
03502 // STATISTICS: kernel-core