Generated on Thu Apr 11 13:59:15 2019 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  *     Samuel Gagnon <samuel.gagnon92@gmail.com>
00011  *
00012  *  Copyright:
00013  *     Christian Schulte, 2002
00014  *     Guido Tack, 2003
00015  *     Mikael Lagerkvist, 2006
00016  *     LOGIS, s.r.o., 2009
00017  *     Samuel Gagnon, 2018
00018  *
00019  *  Bugfixes provided by:
00020  *     Alexander Samoilov <alexander_samoilov@yahoo.com>
00021  *
00022  *  This file is part of Gecode, the generic constraint
00023  *  development environment:
00024  *     http://www.gecode.org
00025  *
00026  *  Permission is hereby granted, free of charge, to any person obtaining
00027  *  a copy of this software and associated documentation files (the
00028  *  "Software"), to deal in the Software without restriction, including
00029  *  without limitation the rights to use, copy, modify, merge, publish,
00030  *  distribute, sublicense, and/or sell copies of the Software, and to
00031  *  permit persons to whom the Software is furnished to do so, subject to
00032  *  the following conditions:
00033  *
00034  *  The above copyright notice and this permission notice shall be
00035  *  included in all copies or substantial portions of the Software.
00036  *
00037  *  THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,
00038  *  EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF
00039  *  MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND
00040  *  NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE
00041  *  LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION
00042  *  OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION
00043  *  WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
00044  *
00045  */
00046 
00047 #include <iostream>
00048 
00049 namespace Gecode {
00050 
00051   class Space;
00052 
00061 
00062   typedef int ModEvent;
00063 
00065   const ModEvent ME_GEN_FAILED   = -1;
00067   const ModEvent ME_GEN_NONE     =  0;
00069   const ModEvent ME_GEN_ASSIGNED =  1;
00070 
00072   typedef int PropCond;
00074   const PropCond PC_GEN_NONE     = -1;
00076   const PropCond PC_GEN_ASSIGNED = 0;
00078 
00089   typedef int ModEventDelta;
00090 
00091 }
00092 
00093 #include <gecode/kernel/var-type.hpp>
00094 
00095 namespace Gecode {
00096 
00098   class NoIdxVarImpConf {
00099   public:
00101     static const int idx_c = -1;
00103     static const int idx_d = -1;
00105     static const PropCond pc_max = PC_GEN_ASSIGNED;
00107     static const int free_bits = 0;
00109     static const int med_fst = 0;
00111     static const int med_lst = 0;
00113     static const int med_mask = 0;
00115     static Gecode::ModEvent me_combine(ModEvent me1, ModEvent me2);
00117     static bool med_update(ModEventDelta& med, ModEvent me);
00118   };
00119 
00120   forceinline ModEvent
00121   NoIdxVarImpConf::me_combine(ModEvent, ModEvent) {
00122     GECODE_NEVER; return 0;
00123   }
00124   forceinline bool
00125   NoIdxVarImpConf::med_update(ModEventDelta&, ModEvent) {
00126     GECODE_NEVER; return false;
00127   }
00128 
00129 
00130   /*
00131    * These are the classes of interest
00132    *
00133    */
00134   class ActorLink;
00135   class Actor;
00136   class Propagator;
00137   class SubscribedPropagators;
00138   class LocalObject;
00139   class Advisor;
00140   class AFC;
00141   class Choice;
00142   class Brancher;
00143   class Group;
00144   class PropagatorGroup;
00145   class BrancherGroup;
00146   class PostInfo;
00147   class ViewTraceInfo;
00148   class PropagateTraceInfo;
00149   class CommitTraceInfo;
00150   class PostTraceInfo;
00151   class TraceRecorder;
00152   class TraceFilter;
00153   class Tracer;
00154 
00155   template<class A> class Council;
00156   template<class A> class Advisors;
00157   template<class VIC> class VarImp;
00158 
00159 
00160   /*
00161    * Variable implementations
00162    *
00163    */
00164 
00172   class VarImpBase {};
00173 
00180   class GECODE_VTABLE_EXPORT VarImpDisposerBase {
00181   public:
00183     GECODE_KERNEL_EXPORT virtual void dispose(Space& home, VarImpBase* x);
00185     GECODE_KERNEL_EXPORT virtual ~VarImpDisposerBase(void);
00186   };
00187 
00194   template<class VarImp>
00195   class VarImpDisposer : public VarImpDisposerBase {
00196   public:
00198     VarImpDisposer(void);
00200     virtual void dispose(Space& home, VarImpBase* x);
00201   };
00202 
00204   class Delta {
00205     template<class VIC> friend class VarImp;
00206   private:
00208     ModEvent me;
00209   };
00210 
00218   template<class VIC>
00219   class VarImp : public VarImpBase {
00220     friend class Space;
00221     friend class Propagator;
00222     template<class VarImp> friend class VarImpDisposer;
00223     friend class SubscribedPropagators;
00224   private:
00225     union {
00233       ActorLink** base;
00242       VarImp<VIC>* fwd;
00243     } b;
00244 
00246     static const int idx_c = VIC::idx_c;
00248     static const int idx_d = VIC::idx_d;
00250     static const int free_bits = VIC::free_bits;
00252     unsigned int entries;
00254     unsigned int free_and_bits;
00256     static const Gecode::PropCond pc_max = VIC::pc_max;
00257 #ifdef GECODE_HAS_CBS
00258 
00259     const unsigned var_id;
00260 #endif
00261 
00262     union {
00273       unsigned int idx[pc_max+1];
00275       VarImp<VIC>* next;
00276     } u;
00277 
00279     ActorLink** actor(PropCond pc);
00281     ActorLink** actorNonZero(PropCond pc);
00283     unsigned int& idx(PropCond pc);
00285     unsigned int idx(PropCond pc) const;
00286 
00293     void update(VarImp* x, ActorLink**& sub);
00300     static void update(Space& home, ActorLink**& sub);
00301 
00303     void enter(Space& home, Propagator* p, PropCond pc);
00305     void enter(Space& home, Advisor* a);
00307     void resize(Space& home);
00309     void remove(Space& home, Propagator* p, PropCond pc);
00311     void remove(Space& home, Advisor* a);
00312 
00313 
00314   protected:
00316     void cancel(Space& home);
00322     bool advise(Space& home, ModEvent me, Delta& d);
00323   private:
00325     void _fail(Space& home);
00326   protected:
00328     ModEvent fail(Space& home);
00329 #ifdef GECODE_HAS_VAR_DISPOSE
00330 
00331     static VarImp<VIC>* vars_d(Space& home);
00333     static void vars_d(Space& home, VarImp<VIC>* x);
00334 #endif
00335 
00336   public:
00338     VarImp(Space& home);
00340     VarImp(void);
00341 
00342 #ifdef GECODE_HAS_CBS
00343 
00344     unsigned int id(void) const;
00345 #endif
00346 
00348 
00349 
00361     void subscribe(Space& home, Propagator& p, PropCond pc,
00362                    bool assigned, ModEvent me, bool schedule);
00364     void cancel(Space& home, Propagator& p, PropCond pc);
00373     void subscribe(Space& home, Advisor& a, bool assigned, bool fail);
00375     void cancel(Space& home, Advisor& a, bool fail);
00376 
00383     unsigned int degree(void) const;
00390     double afc(void) const;
00392 
00394 
00395 
00396     VarImp(Space& home, VarImp& x);
00398     bool copied(void) const;
00400     VarImp* forward(void) const;
00402     VarImp* next(void) const;
00404 
00406 
00407 
00414     static void schedule(Space& home, Propagator& p, ModEvent me,
00415                          bool force = false);
00423     static void reschedule(Space& home, Propagator& p, PropCond pc,
00424                            bool assigned, ModEvent me);
00426     static ModEvent me(const ModEventDelta& med);
00428     static ModEventDelta med(ModEvent me);
00430     static ModEvent me_combine(ModEvent me1, ModEvent me2);
00432 
00434 
00435 
00436     static ModEvent modevent(const Delta& d);
00438 
00440 
00441 
00442     unsigned int bits(void) const;
00444     unsigned int& bits(void);
00446 
00447   protected:
00449     void schedule(Space& home, PropCond pc1, PropCond pc2, ModEvent me);
00450 
00451   public:
00453 
00454 
00455     static void* operator new(size_t,Space&);
00457     static void  operator delete(void*,Space&);
00459     static void  operator delete(void*);
00461   };
00462 
00463 
00472   enum ExecStatus {
00473     __ES_SUBSUMED       = -2, 
00474     ES_FAILED           = -1, 
00475     ES_NOFIX            =  0, 
00476     ES_OK               =  0, 
00477     ES_FIX              =  1, 
00478     ES_NOFIX_FORCE      =  2, 
00479     __ES_PARTIAL        =  2  
00480   };
00481 
00486   class PropCost {
00487     friend class Space;
00488   public:
00490     enum ActualCost {
00491       AC_RECORD       = 0, 
00492       AC_CRAZY_LO     = 1, 
00493       AC_CRAZY_HI     = 1, 
00494       AC_CUBIC_LO     = 1, 
00495       AC_CUBIC_HI     = 1, 
00496       AC_QUADRATIC_LO = 2, 
00497       AC_QUADRATIC_HI = 2, 
00498       AC_LINEAR_HI    = 3, 
00499       AC_LINEAR_LO    = 4, 
00500       AC_TERNARY_HI   = 4, 
00501       AC_BINARY_HI    = 5, 
00502       AC_TERNARY_LO   = 5, 
00503       AC_BINARY_LO    = 6, 
00504       AC_UNARY_LO     = 6, 
00505       AC_UNARY_HI     = 6, 
00506       AC_MAX          = 6  
00507     };
00509     ActualCost ac;
00510   public:
00512     enum Mod {
00513       LO, 
00514       HI  
00515     };
00516   private:
00518     static PropCost cost(Mod m, ActualCost lo, ActualCost hi, unsigned int n);
00520     PropCost(ActualCost ac);
00521   public:
00523     static PropCost record(void);
00525     static PropCost crazy(PropCost::Mod m, unsigned int n);
00527     static PropCost crazy(PropCost::Mod m, int n);
00529     static PropCost cubic(PropCost::Mod m, unsigned int n);
00531     static PropCost cubic(PropCost::Mod m, int n);
00533     static PropCost quadratic(PropCost::Mod m, unsigned int n);
00535     static PropCost quadratic(PropCost::Mod m, int n);
00537     static PropCost linear(PropCost::Mod m, unsigned int n);
00539     static PropCost linear(PropCost::Mod m, int n);
00541     static PropCost ternary(PropCost::Mod m);
00543     static PropCost binary(PropCost::Mod m);
00545     static PropCost unary(PropCost::Mod m);
00546   };
00547 
00548 
00553   enum ActorProperty {
00562     AP_DISPOSE = (1 << 0),
00568     AP_WEAKLY = (1 << 1),
00573     AP_VIEW_TRACE = (1 << 2),
00578     AP_TRACE = (1 << 3)
00579   };
00580 
00581 
00589   class ActorLink {
00590     friend class Actor;
00591     friend class Propagator;
00592     friend class Advisor;
00593     friend class Brancher;
00594     friend class LocalObject;
00595     friend class Space;
00596     template<class VIC> friend class VarImp;
00597   private:
00598     ActorLink* _next; ActorLink* _prev;
00599   public:
00601 
00602     ActorLink* prev(void) const; void prev(ActorLink*);
00603     ActorLink* next(void) const; void next(ActorLink*);
00604     ActorLink** next_ref(void);
00606 
00608     void init(void);
00610     void unlink(void);
00612     void head(ActorLink* al);
00614     void tail(ActorLink* al);
00616     bool empty(void) const;
00618     template<class T> static ActorLink* cast(T* a);
00620     template<class T> static const ActorLink* cast(const T* a);
00621   };
00622 
00623 
00628   class GECODE_VTABLE_EXPORT Actor : private ActorLink {
00629     friend class ActorLink;
00630     friend class Space;
00631     friend class Propagator;
00632     friend class Advisor;
00633     friend class Brancher;
00634     friend class LocalObject;
00635     template<class VIC> friend class VarImp;
00636     template<class A> friend class Council;
00637   private:
00639     static Actor* cast(ActorLink* al);
00641     static const Actor* cast(const ActorLink* al);
00643     GECODE_KERNEL_EXPORT static Actor* sentinel;
00644   public:
00646     virtual Actor* copy(Space& home) = 0;
00647 
00649 
00650 
00651     GECODE_KERNEL_EXPORT
00652     virtual size_t dispose(Space& home);
00654     static void* operator new(size_t s, Space& home);
00656     static void  operator delete(void* p, Space& home);
00658   public:
00660     GECODE_KERNEL_EXPORT virtual ~Actor(void);
00662     static void* operator new(size_t s);
00664     static void  operator delete(void* p);
00665   };
00666 
00667   class Home;
00668 
00673   class Group {
00674     friend class Home;
00675     friend class Propagator;
00676     friend class Brancher;
00677     friend class ViewTraceInfo;
00678     friend class PropagateTraceInfo;
00679     friend class CommitTraceInfo;
00680     friend class PostTraceInfo;
00681   protected:
00683     static const unsigned int GROUPID_ALL = 0U;
00685     static const unsigned int GROUPID_DEF = 1U;
00687     static const unsigned int GROUPID_MAX = UINT_MAX >> 2;
00689     unsigned int gid;
00691     GECODE_KERNEL_EXPORT
00692     static unsigned int next;
00694     GECODE_KERNEL_EXPORT
00695     static Support::Mutex m;
00697     Group(unsigned int gid0);
00698   public:
00700 
00701 
00702     GECODE_KERNEL_EXPORT
00703     Group(void);
00705     Group(const Group& g);
00707     Group& operator =(const Group& g);
00709     unsigned int id(void) const;
00711     bool in(Group a) const;
00713     bool in(void) const;
00715 
00716     GECODE_KERNEL_EXPORT
00717     static Group all;
00719     GECODE_KERNEL_EXPORT
00720     static Group def;
00721   };
00722 
00727   class PropagatorGroup : public Group {
00728     friend class Propagator;
00729     friend class ViewTraceInfo;
00730     friend class PropagateTraceInfo;
00731     friend class PostTraceInfo;
00732   protected:
00734     PropagatorGroup(unsigned int gid);
00735   public:
00737 
00738 
00739     PropagatorGroup(void);
00741     PropagatorGroup(const PropagatorGroup& g);
00743     PropagatorGroup& operator =(const PropagatorGroup& g);
00745     Home operator ()(Space& home);
00747 
00748 
00749 
00750     GECODE_KERNEL_EXPORT
00751     PropagatorGroup& move(Space& home, PropagatorGroup g);
00753     PropagatorGroup& move(Space& home, Propagator& p);
00760     GECODE_KERNEL_EXPORT
00761     PropagatorGroup& move(Space& home, unsigned int id);
00763 
00764 
00765 
00766     bool operator ==(PropagatorGroup g) const;
00768     bool operator !=(PropagatorGroup g) const;
00770     GECODE_KERNEL_EXPORT
00771     unsigned int size(Space& home) const;
00773     GECODE_KERNEL_EXPORT
00774     void kill(Space& home);
00776     GECODE_KERNEL_EXPORT
00777     void disable(Space& home);
00784     GECODE_KERNEL_EXPORT
00785     void enable(Space& home, bool s=true);
00787 
00788     GECODE_KERNEL_EXPORT
00789     static PropagatorGroup all;
00791     GECODE_KERNEL_EXPORT
00792     static PropagatorGroup def;
00793   };
00794 
00799   class BrancherGroup : public Group {
00800     friend class Brancher;
00801   protected:
00803     BrancherGroup(unsigned int gid);
00804   public:
00806 
00807 
00808     BrancherGroup(void);
00810     BrancherGroup(const BrancherGroup& g);
00812     BrancherGroup& operator =(const BrancherGroup& g);
00814     Home operator ()(Space& home);
00816 
00817 
00818 
00819     GECODE_KERNEL_EXPORT
00820     BrancherGroup& move(Space& home, BrancherGroup g);
00822     BrancherGroup& move(Space& home, Brancher& b);
00829     GECODE_KERNEL_EXPORT
00830     BrancherGroup& move(Space& home, unsigned int id);
00832 
00833 
00834 
00835     bool operator ==(BrancherGroup g) const;
00837     bool operator !=(BrancherGroup g) const;
00839     GECODE_KERNEL_EXPORT
00840     unsigned int size(Space& home) const;
00842     GECODE_KERNEL_EXPORT
00843     void kill(Space& home);
00845 
00846     GECODE_KERNEL_EXPORT
00847     static BrancherGroup all;
00849     GECODE_KERNEL_EXPORT
00850     static BrancherGroup def;
00851   };
00852 
00856   class Home {
00857     friend class PostInfo;
00858   protected:
00860     Space& s;
00862     Propagator* p;
00864     PropagatorGroup pg;
00866     BrancherGroup bg;
00867   public:
00869 
00870 
00871     Home(Space& s, Propagator* p=NULL,
00872          PropagatorGroup pg=PropagatorGroup::def,
00873          BrancherGroup bg=BrancherGroup::def);
00875     Home& operator =(const Home& h);
00877     operator Space&(void);
00879 
00880 
00881 
00882     Home operator ()(Propagator& p);
00884     Home operator ()(PropagatorGroup pg);
00886     Home operator ()(BrancherGroup bg);
00888     Propagator* propagator(void) const;
00890     PropagatorGroup propagatorgroup(void) const;
00892     BrancherGroup branchergroup(void) const;
00894 
00895 
00896 
00897     bool failed(void) const;
00899     void fail(void);
00901     void notice(Actor& a, ActorProperty p, bool duplicate=false);
00903   };
00904 
00908   class ViewTraceInfo {
00909     friend class Space;
00910     friend class PostInfo;
00911   public:
00913     enum What {
00915       PROPAGATOR = 0,
00917       BRANCHER   = 1,
00919       POST       = 2,
00921       OTHER      = 3
00922     };
00923   protected:
00925     ptrdiff_t who;
00927     void propagator(Propagator& p);
00929     void brancher(Brancher& b);
00931     void post(PropagatorGroup g);
00933     void other(void);
00934   public:
00936     What what(void) const;
00938     const Propagator& propagator(void) const;
00940     const Brancher& brancher(void) const;
00942     PropagatorGroup post(void) const;
00943   };
00944 
00948   class PostInfo {
00949     friend class Space;
00950   protected:
00952     Space& h;
00954     PropagatorGroup pg;
00956     unsigned int pid;
00958     bool nested;
00959   public:
00961     PostInfo(Home home);
00963     ~PostInfo(void);
00964   };
00965 
00969   class PropagateTraceInfo {
00970     friend class Space;
00971   public:
00973     enum Status {
00974       FIX,     
00975       NOFIX,   
00976       FAILED,  
00977       SUBSUMED 
00978     };
00979   protected:
00981     unsigned int i;
00983     PropagatorGroup g;
00985     const Propagator* p;
00987     Status s;
00989     PropagateTraceInfo(unsigned int i, PropagatorGroup g,
00990                        const Propagator* p, Status s);
00991   public:
00993     unsigned int id(void) const;
00995     PropagatorGroup group(void) const;
00997     const Propagator* propagator(void) const;
00999     Status status(void) const;
01000   };
01001 
01005   class CommitTraceInfo {
01006     friend class Space;
01007   protected:
01009     const Brancher& b;
01011     const Choice& c;
01013     unsigned int a;
01015     CommitTraceInfo(const Brancher& b, const Choice& c, unsigned int a);
01016   public:
01018     unsigned int id(void) const;
01020     BrancherGroup group(void) const;
01022     const Brancher& brancher(void) const;
01024     const Choice& choice(void) const;
01026     unsigned int alternative(void) const;
01027   };
01028  
01032   class PostTraceInfo {
01033     friend class Space;
01034     friend class PostInfo;
01035   public:
01037     enum Status {
01038       POSTED,  
01039       FAILED,  
01040       SUBSUMED 
01041     };
01042   protected:
01044     PropagatorGroup g;
01046     Status s;
01048     unsigned int n;
01050     PostTraceInfo(PropagatorGroup g, Status s, unsigned int n);
01051   public:
01053     Status status(void) const;
01055     PropagatorGroup group(void) const;
01057     unsigned int propagators(void) const;
01058   };
01059 
01064   class GECODE_VTABLE_EXPORT Propagator : public Actor {
01065     friend class ActorLink;
01066     friend class Space;
01067     template<class VIC> friend class VarImp;
01068     friend class Advisor;
01069     template<class A> friend class Council;
01070     friend class SubscribedPropagators;
01071     friend class PropagatorGroup;
01072   private:
01073     union {
01075       ModEventDelta med;
01077       size_t size;
01079       Gecode::ActorLink* advisors;
01080     } u;
01082     void* gpi_disabled;
01084     static Propagator* cast(ActorLink* al);
01086     static const Propagator* cast(const ActorLink* al);
01088     void disable(Space& home);
01090     void enable(Space& home);
01091   protected:
01093     Propagator(Home home);
01095     Propagator(Space& home, Propagator& p);
01097     Propagator* fwd(void) const;
01099     Kernel::GPI::Info& gpi(void);
01100 
01101   public:
01103 
01104 
01112     virtual void reschedule(Space& home) = 0;
01136     virtual ExecStatus propagate(Space& home, const ModEventDelta& med) = 0;
01138     virtual PropCost cost(const Space& home, const ModEventDelta& med) const = 0;
01146     ModEventDelta modeventdelta(void) const;
01182     GECODE_KERNEL_EXPORT
01183     virtual ExecStatus advise(Space& home, Advisor& a, const Delta& d);
01185     GECODE_KERNEL_EXPORT
01186     virtual void advise(Space& home, Advisor& a);
01188 
01189 
01190 
01191     double afc(void) const;
01193 #ifdef GECODE_HAS_CBS
01194 
01195 
01196 
01202 
01203     typedef std::function<void(unsigned int prop_id, unsigned int var_id,
01204                                int val, double dens)> SendMarginal;
01205     virtual void solndistrib(Space& home, SendMarginal send) const;
01213 
01214     typedef std::function<bool(unsigned int var_id)> InDecision;
01215     virtual void domainsizesum(InDecision in, unsigned int& size,
01216                                unsigned int& size_b) const;
01218 #endif
01219 
01220 
01221 
01222     unsigned int id(void) const;
01224     PropagatorGroup group(void) const;
01226     void group(PropagatorGroup g);
01228     bool disabled(void) const;
01230   };
01231 
01232 
01240   template<class A>
01241   class Council {
01242     friend class Advisor;
01243     friend class Advisors<A>;
01244   private:
01246     mutable ActorLink* advisors;
01247   public:
01249     Council(void);
01251     Council(Space& home);
01253     bool empty(void) const;
01255     void update(Space& home, Council<A>& c);
01257     void dispose(Space& home);
01258   };
01259 
01260 
01265   template<class A>
01266   class Advisors {
01267   private:
01269     ActorLink* a;
01270   public:
01272     Advisors(const Council<A>& c);
01274     bool operator ()(void) const;
01276     void operator ++(void);
01278     A& advisor(void) const;
01279   };
01280 
01281 
01292   class Advisor : private ActorLink {
01293     template<class VIC> friend class VarImp;
01294     template<class A> friend class Council;
01295     template<class A> friend class Advisors;
01296     friend class SubscribedPropagators;
01297   private:
01299     bool disposed(void) const;
01301     static Advisor* cast(ActorLink* al);
01303     static const Advisor* cast(const ActorLink* al);
01304   protected:
01306     Propagator& propagator(void) const;
01307   public:
01309     template<class A>
01310     Advisor(Space& home, Propagator& p, Council<A>& c);
01312     Advisor(Space& home, Advisor& a);
01314     const ViewTraceInfo& operator ()(const Space& home) const;
01315 
01317 
01318 
01319     template<class A>
01320     void dispose(Space& home, Council<A>& c);
01322     static void* operator new(size_t s, Space& home);
01324     static void  operator delete(void* p, Space& home);
01326   private:
01327 #ifndef __GNUC__
01328 
01329     static void  operator delete(void* p);
01330 #endif
01331 
01332     static void* operator new(size_t s);
01333   };
01334 
01335 
01340   class GECODE_VTABLE_EXPORT NGL {
01341   private:
01343     void* nl;
01344   public:
01346     enum Status {
01347       FAILED,   
01348       SUBSUMED, 
01349       NONE      
01350     };
01352     NGL(void);
01354     NGL(Space& home);
01356     NGL(Space& home, NGL& ngl);
01358     virtual void subscribe(Space& home, Propagator& p) = 0;
01360     virtual void cancel(Space& home, Propagator& p) = 0;
01362     virtual void reschedule(Space& home, Propagator& p) = 0;
01364     virtual NGL::Status status(const Space& home) const = 0;
01366     virtual ExecStatus prune(Space& home) = 0;
01368     virtual NGL* copy(Space& home) = 0;
01370     GECODE_KERNEL_EXPORT
01371     virtual bool notice(void) const;
01373     virtual size_t dispose(Space& home);
01375 
01376 
01377     bool leaf(void) const;
01379     NGL* next(void) const;
01381     void leaf(bool l);
01383     void next(NGL* n);
01385     NGL* add(NGL* n, bool l);
01387 
01388 
01389 
01390     static void* operator new(size_t s, Space& home);
01392     static void  operator delete(void* s, Space& home);
01394     static void  operator delete(void* p);
01396   public:
01398     GECODE_KERNEL_EXPORT virtual ~NGL(void);
01400     static void* operator new(size_t s);
01401   };
01402 
01412   class GECODE_VTABLE_EXPORT Choice : public HeapAllocated {
01413     friend class Space;
01414   private:
01415     unsigned int bid; 
01416     unsigned int alt; 
01417 
01419     unsigned int id(void) const;
01420   protected:
01422     Choice(const Brancher& b, const unsigned int a);
01423   public:
01425     unsigned int alternatives(void) const;
01427     GECODE_KERNEL_EXPORT virtual ~Choice(void);
01429     GECODE_KERNEL_EXPORT
01430     virtual void archive(Archive& e) const;
01431   };
01432 
01442   class GECODE_VTABLE_EXPORT Brancher : public Actor {
01443     friend class ActorLink;
01444     friend class Space;
01445     friend class Choice;
01446   private:
01448     unsigned int bid;
01450     unsigned int gid;
01452     static Brancher* cast(ActorLink* al);
01454     static const Brancher* cast(const ActorLink* al);
01455   protected:
01457     Brancher(Home home);
01459     Brancher(Space& home, Brancher& b);
01460   public:
01462 
01463 
01471     virtual bool status(const Space& home) const = 0;
01479     virtual const Choice* choice(Space& home) = 0;
01481     virtual const Choice* choice(const Space& home, Archive& e) = 0;
01488     virtual ExecStatus commit(Space& home, const Choice& c,
01489                               unsigned int a) = 0;
01503     GECODE_KERNEL_EXPORT
01504     virtual NGL* ngl(Space& home, const Choice& c, unsigned int a) const;
01512     GECODE_KERNEL_EXPORT
01513     virtual void print(const Space& home, const Choice& c, unsigned int a,
01514                        std::ostream& o) const;
01516 
01517 
01518 
01519     unsigned int id(void) const;
01521     BrancherGroup group(void) const;
01523     void group(BrancherGroup g);
01525   };
01526 
01533   class LocalObject : public Actor {
01534     friend class ActorLink;
01535     friend class Space;
01536     friend class LocalHandle;
01537   protected:
01539     LocalObject(Home home);
01541     LocalObject(Space& home, LocalObject& l);
01543     static LocalObject* cast(ActorLink* al);
01545     static const LocalObject* cast(const ActorLink* al);
01546   private:
01548     GECODE_KERNEL_EXPORT void fwdcopy(Space& home);
01549   public:
01551     LocalObject* fwd(Space& home);
01552   };
01553 
01558   class LocalHandle {
01559   private:
01561     LocalObject* o;
01562   protected:
01564     LocalHandle(void);
01566     LocalHandle(LocalObject* lo);
01568     LocalHandle(const LocalHandle& lh);
01569   public:
01571     LocalHandle& operator =(const LocalHandle& lh);
01573     void update(Space& home, LocalHandle& lh);
01575     ~LocalHandle(void);
01576   protected:
01578     LocalObject* object(void) const;
01580     void object(LocalObject* n);
01581   };
01582 
01583 
01588   class GECODE_VTABLE_EXPORT NoGoods {
01589   protected:
01591     unsigned long int n;
01592   public:
01594     NoGoods(void);
01596     GECODE_KERNEL_EXPORT
01597     virtual void post(Space& home) const;
01599     unsigned long int ng(void) const;
01601     void ng(unsigned long int n);
01603     virtual ~NoGoods(void);
01605     GECODE_KERNEL_EXPORT
01606     static NoGoods eng;
01607   };
01608 
01613   class GECODE_VTABLE_EXPORT MetaInfo {
01614   public:
01616     enum Type {
01618       RESTART,
01620       PORTFOLIO
01621     };
01622   protected:
01624     const Type t;
01626 
01627 
01628     const unsigned long int r;
01630     const unsigned long int s;
01632     const unsigned long int f;
01634     const Space* l;
01636     const NoGoods& ng;
01638 
01639 
01640 
01641     const unsigned int a;
01643   public:
01645 
01646 
01647     MetaInfo(unsigned long int r,
01648              unsigned long int s,
01649              unsigned long int f,
01650              const Space* l,
01651              NoGoods& ng);
01653     MetaInfo(unsigned int a);
01655 
01656     Type type(void) const;
01658 
01659 
01660     unsigned long int restart(void) const;
01662     unsigned long int solution(void) const;
01664     unsigned long int fail(void) const;
01666     const Space* last(void) const;
01668     const NoGoods& nogoods(void) const;
01670 
01671 
01672 
01673     unsigned int asset(void) const;
01675   };
01676 
01681   enum SpaceStatus {
01682     SS_FAILED, 
01683     SS_SOLVED, 
01684     SS_BRANCH  
01685   };
01686 
01691   class StatusStatistics {
01692   public:
01694     unsigned long int propagate;
01696     StatusStatistics(void);
01698     void reset(void);
01700     StatusStatistics operator +(const StatusStatistics& s);
01702     StatusStatistics& operator +=(const StatusStatistics& s);
01703   };
01704 
01709   class CloneStatistics {
01710   public:
01712     CloneStatistics(void);
01714     void reset(void);
01716     CloneStatistics operator +(const CloneStatistics& s);
01718     CloneStatistics& operator +=(const CloneStatistics& s);
01719   };
01720 
01725   class CommitStatistics {
01726   public:
01728     CommitStatistics(void);
01730     void reset(void);
01732     CommitStatistics operator +(const CommitStatistics& s);
01734     CommitStatistics& operator +=(const CommitStatistics& s);
01735   };
01736 
01737 
01738 
01742   class GECODE_VTABLE_EXPORT Space : public HeapAllocated {
01743     friend class Actor;
01744     friend class Propagator;
01745     friend class PropagatorGroup;
01746     friend class Propagators;
01747     friend class Brancher;
01748     friend class BrancherGroup;
01749     friend class Branchers;
01750     friend class Advisor;
01751     template <class A> friend class Council;
01752     template<class VIC> friend class VarImp;
01753     template<class VarImp> friend class VarImpDisposer;
01754     friend class LocalObject;
01755     friend class Region;
01756     friend class AFC;
01757     friend class PostInfo;
01758     friend GECODE_KERNEL_EXPORT
01759     void trace(Home home, TraceFilter tf, int te, Tracer& t);
01760   private:
01762     Kernel::SharedSpaceData ssd;
01764     Kernel::MemoryManager mm;
01765 #ifdef GECODE_HAS_CBS
01766 
01767     unsigned int var_id_counter;
01768 #endif
01769 
01770     ActorLink pl;
01772     ActorLink bl;
01778     Brancher* b_status;
01790     Brancher* b_commit;
01792     Brancher* brancher(unsigned int id);
01793 
01795     void kill(Brancher& b);
01797     void kill(Propagator& p);
01798 
01800     GECODE_KERNEL_EXPORT
01801     void kill_brancher(unsigned int id);
01802 
01804     static const unsigned reserved_bid = 0U;
01805 
01807     static const unsigned int sc_bits = 2;
01809     static const unsigned int sc_fast = 0;
01811     static const unsigned int sc_disabled = 1;
01813     static const unsigned int sc_trace = 2;
01814 
01815     union {
01817       struct {
01830         ActorLink* active;
01832         ActorLink queue[PropCost::AC_MAX+1];
01839         unsigned int bid_sc;
01841         unsigned int n_sub;
01843         ViewTraceInfo vti;
01844       } p;
01846       struct {
01848         VarImpBase* vars_u[AllVarConf::idx_c];
01850         VarImpBase* vars_noidx;
01852         LocalObject* local;
01853       } c;
01854     } pc;
01856     void enqueue(Propagator* p);
01861 #ifdef GECODE_HAS_VAR_DISPOSE
01862 
01863     GECODE_KERNEL_EXPORT static VarImpDisposerBase* vd[AllVarConf::idx_d];
01865     VarImpBase* _vars_d[AllVarConf::idx_d];
01867     template<class VIC> VarImpBase* vars_d(void) const;
01869     template<class VIC> void vars_d(VarImpBase* x);
01870 #endif
01871 
01872     void update(ActorLink** sub);
01874 
01876     Actor** d_fst;
01878     Actor** d_cur;
01880     Actor** d_lst;
01881 
01883     GECODE_KERNEL_EXPORT static StatusStatistics unused_status;
01885     GECODE_KERNEL_EXPORT static CloneStatistics unused_clone;
01887     GECODE_KERNEL_EXPORT static CommitStatistics unused_commit;
01888 
01902     GECODE_KERNEL_EXPORT Space* _clone(void);
01903 
01936     GECODE_KERNEL_EXPORT
01937     void _commit(const Choice& c, unsigned int a);
01938 
01969     GECODE_KERNEL_EXPORT
01970     void _trycommit(const Choice& c, unsigned int a);
01971 
01973     GECODE_KERNEL_EXPORT
01974     TraceRecorder* findtracerecorder(void);
01976     GECODE_KERNEL_EXPORT
01977     void post(const PostInfo& pi);
01978 
01985     GECODE_KERNEL_EXPORT
01986     void ap_notice_dispose(Actor* a, bool d);
01993     GECODE_KERNEL_EXPORT
01994     void ap_ignore_dispose(Actor* a, bool d);
01995   public:
02000     GECODE_KERNEL_EXPORT
02001     Space(void);
02010     GECODE_KERNEL_EXPORT
02011     Space(Space& s);
02016     GECODE_KERNEL_EXPORT
02017     virtual ~Space(void);
02024     virtual Space* copy(void) = 0;
02035     GECODE_KERNEL_EXPORT virtual void constrain(const Space& best);
02059     GECODE_KERNEL_EXPORT
02060     virtual bool master(const MetaInfo& mi);
02086     GECODE_KERNEL_EXPORT
02087     virtual bool slave(const MetaInfo& mi);
02088 
02089     /*
02090      * Member functions for search engines
02091      *
02092      */
02093 
02105     GECODE_KERNEL_EXPORT
02106     SpaceStatus status(StatusStatistics& stat=unused_status);
02107 
02139     GECODE_KERNEL_EXPORT
02140     const Choice* choice(void);
02141 
02151     GECODE_KERNEL_EXPORT
02152     const Choice* choice(Archive& e) const;
02153 
02169     Space* clone(CloneStatistics& stat=unused_clone) const;
02170 
02205     void commit(const Choice& c, unsigned int a,
02206                 CommitStatistics& stat=unused_commit);
02239     void trycommit(const Choice& c, unsigned int a,
02240                    CommitStatistics& stat=unused_commit);
02259     GECODE_KERNEL_EXPORT
02260     NGL* ngl(const Choice& c, unsigned int a);
02261 
02276     GECODE_KERNEL_EXPORT
02277     void print(const Choice& c, unsigned int a, std::ostream& o) const;
02278 
02287     GECODE_KERNEL_EXPORT
02288     void notice(Actor& a, ActorProperty p, bool duplicate=false);
02296     GECODE_KERNEL_EXPORT
02297     void ignore(Actor& a, ActorProperty p, bool duplicate=false);
02298 
02299 
02310     ExecStatus ES_SUBSUMED(Propagator& p);
02325     ExecStatus ES_SUBSUMED_DISPOSED(Propagator& p, size_t s);
02336     ExecStatus ES_FIX_PARTIAL(Propagator& p, const ModEventDelta& med);
02347     ExecStatus ES_NOFIX_PARTIAL(Propagator& p, const ModEventDelta& med);
02348 
02359     template<class A>
02360     ExecStatus ES_FIX_DISPOSE(Council<A>& c, A& a);
02371     template<class A>
02372     ExecStatus ES_NOFIX_DISPOSE(Council<A>& c, A& a);
02384     template<class A>
02385     ExecStatus ES_NOFIX_DISPOSE_FORCE(Council<A>& c, A& a);
02386 
02394     void fail(void);
02403     bool failed(void) const;
02408     bool stable(void) const;
02409 
02411 
02412 
02413     Home operator ()(Propagator& p);
02415     Home operator ()(PropagatorGroup pg);
02417     Home operator ()(BrancherGroup bg);
02419 
02431     template<class T>
02432     T* alloc(long unsigned int n);
02439     template<class T>
02440     T* alloc(long int n);
02447     template<class T>
02448     T* alloc(unsigned int n);
02455     template<class T>
02456     T* alloc(int n);
02466     template<class T>
02467     void free(T* b, long unsigned int n);
02477     template<class T>
02478     void free(T* b, long int n);
02488     template<class T>
02489     void free(T* b, unsigned int n);
02499     template<class T>
02500     void free(T* b, int n);
02512     template<class T>
02513     T* realloc(T* b, long unsigned int n, long unsigned int m);
02525     template<class T>
02526     T* realloc(T* b, long int n, long int m);
02538     template<class T>
02539     T* realloc(T* b, unsigned int n, unsigned int m);
02551     template<class T>
02552     T* realloc(T* b, int n, int m);
02560     template<class T>
02561     T** realloc(T** b, long unsigned int n, long unsigned int m);
02569     template<class T>
02570     T** realloc(T** b, long int n, long int m);
02578     template<class T>
02579     T** realloc(T** b, unsigned int n, unsigned int m);
02587     template<class T>
02588     T** realloc(T** b, int n, int m);
02590     void* ralloc(size_t s);
02592     void rfree(void* p, size_t s);
02594     void* rrealloc(void* b, size_t n, size_t m);
02596     template<size_t> void* fl_alloc(void);
02602     template<size_t> void  fl_dispose(FreeList* f, FreeList* l);
02604 
02605 
02606 
02609     template<class T>
02610     T& construct(void);
02616     template<class T, typename A1>
02617     T& construct(A1 const& a1);
02623     template<class T, typename A1, typename A2>
02624     T& construct(A1 const& a1, A2 const& a2);
02630     template<class T, typename A1, typename A2, typename A3>
02631     T& construct(A1 const& a1, A2 const& a2, A3 const& a3);
02637     template<class T, typename A1, typename A2, typename A3, typename A4>
02638     T& construct(A1 const& a1, A2 const& a2, A3 const& a3, A4 const& a4);
02644     template<class T, typename A1, typename A2, typename A3, typename A4, typename A5>
02645     T& construct(A1 const& a1, A2 const& a2, A3 const& a3, A4 const& a4, A5 const& a5);
02647 
02649 
02650 
02651     void afc_decay(double d);
02653     double afc_decay(void) const;
02655     GECODE_KERNEL_EXPORT void afc_unshare(void);
02657 
02658   protected:
02664     class Propagators {
02665     private:
02667       Space& home;
02669       ActorLink* q;
02671       ActorLink* c;
02673       ActorLink* e;
02674     public:
02676       Propagators(Space& home);
02678       bool operator ()(void) const;
02680       void operator ++(void);
02682       Propagator& propagator(void) const;
02683     };
02689     class ScheduledPropagators {
02690     private:
02692       Space& home;
02694       ActorLink* q;
02696       ActorLink* c;
02698       ActorLink* e;
02699     public:
02701       ScheduledPropagators(Space& home);
02703       bool operator ()(void) const;
02705       void operator ++(void);
02707       Propagator& propagator(void) const;
02708     };
02714     class IdlePropagators {
02715     private:
02717       ActorLink* c;
02719       ActorLink* e;
02720     public:
02722       IdlePropagators(Space& home);
02724       bool operator ()(void) const;
02726       void operator ++(void);
02728       Propagator& propagator(void) const;
02729     };
02735     class Branchers {
02736     private:
02738       ActorLink* c;
02740       ActorLink* e;
02741     public:
02743       Branchers(Space& home);
02745       bool operator ()(void) const;
02747       void operator ++(void);
02749       Brancher& brancher(void) const;
02750     };
02751   };
02752 
02754   class Propagators {
02755   private:
02757     Space::Propagators ps;
02759     PropagatorGroup g;
02760   public:
02762     Propagators(const Space& home, PropagatorGroup g);
02764     bool operator ()(void) const;
02766     void operator ++(void);
02768     const Propagator& propagator(void) const;
02769   };
02770 
02772   class Branchers {
02773   private:
02775     Space::Branchers bs;
02777     BrancherGroup g;
02778   public:
02780     Branchers(const Space& home, BrancherGroup g);
02782     bool operator ()(void) const;
02784     void operator ++(void);
02786     const Brancher& brancher(void) const;
02787   };
02788 
02789 
02790 
02791 
02792   /*
02793    * Memory management
02794    *
02795    */
02796 
02797   // Space allocation: general space heaps and free lists
02798   forceinline void*
02799   Space::ralloc(size_t s) {
02800     return mm.alloc(ssd.data().sm,s);
02801   }
02802   forceinline void
02803   Space::rfree(void* p, size_t s) {
02804     return mm.reuse(p,s);
02805   }
02806   forceinline void*
02807   Space::rrealloc(void* _b, size_t n, size_t m) {
02808     char* b = static_cast<char*>(_b);
02809     if (n < m) {
02810       char* p = static_cast<char*>(ralloc(m));
02811       memcpy(p,b,n);
02812       rfree(b,n);
02813       return p;
02814     } else {
02815       rfree(b+m,m-n);
02816       return b;
02817     }
02818   }
02819 
02820   template<size_t s>
02821   forceinline void*
02822   Space::fl_alloc(void) {
02823     return mm.template fl_alloc<s>(ssd.data().sm);
02824   }
02825   template<size_t s>
02826   forceinline void
02827   Space::fl_dispose(FreeList* f, FreeList* l) {
02828     mm.template fl_dispose<s>(f,l);
02829   }
02830 
02831   /*
02832    * Typed allocation routines
02833    *
02834    */
02835   template<class T>
02836   forceinline T*
02837   Space::alloc(long unsigned int n) {
02838     T* p = static_cast<T*>(ralloc(sizeof(T)*n));
02839     for (long unsigned int i=0; i<n; i++)
02840       (void) new (p+i) T();
02841     return p;
02842   }
02843   template<class T>
02844   forceinline T*
02845   Space::alloc(long int n) {
02846     assert(n >= 0);
02847     return alloc<T>(static_cast<long unsigned int>(n));
02848   }
02849   template<class T>
02850   forceinline T*
02851   Space::alloc(unsigned int n) {
02852     return alloc<T>(static_cast<long unsigned int>(n));
02853   }
02854   template<class T>
02855   forceinline T*
02856   Space::alloc(int n) {
02857     assert(n >= 0);
02858     return alloc<T>(static_cast<long unsigned int>(n));
02859   }
02860 
02861   template<class T>
02862   forceinline void
02863   Space::free(T* b, long unsigned int n) {
02864     for (long unsigned int i=0; i<n; i++)
02865       b[i].~T();
02866     rfree(b,n*sizeof(T));
02867   }
02868   template<class T>
02869   forceinline void
02870   Space::free(T* b, long int n) {
02871     assert(n >= 0);
02872     free<T>(b,static_cast<long unsigned int>(n));
02873   }
02874   template<class T>
02875   forceinline void
02876   Space::free(T* b, unsigned int n) {
02877     free<T>(b,static_cast<long unsigned int>(n));
02878   }
02879   template<class T>
02880   forceinline void
02881   Space::free(T* b, int n) {
02882     assert(n >= 0);
02883     free<T>(b,static_cast<long unsigned int>(n));
02884   }
02885 
02886   template<class T>
02887   forceinline T*
02888   Space::realloc(T* b, long unsigned int n, long unsigned int m) {
02889     if (n < m) {
02890       T* p = static_cast<T*>(ralloc(sizeof(T)*m));
02891       for (long unsigned int i=0; i<n; i++)
02892         (void) new (p+i) T(b[i]);
02893       for (long unsigned int i=n; i<m; i++)
02894         (void) new (p+i) T();
02895       free<T>(b,n);
02896       return p;
02897     } else {
02898       free<T>(b+m,m-n);
02899       return b;
02900     }
02901   }
02902   template<class T>
02903   forceinline T*
02904   Space::realloc(T* b, long int n, long int m) {
02905     assert((n >= 0) && (m >= 0));
02906     return realloc<T>(b,static_cast<long unsigned int>(n),
02907                       static_cast<long unsigned int>(m));
02908   }
02909   template<class T>
02910   forceinline T*
02911   Space::realloc(T* b, unsigned int n, unsigned int m) {
02912     return realloc<T>(b,static_cast<long unsigned int>(n),
02913                       static_cast<long unsigned int>(m));
02914   }
02915   template<class T>
02916   forceinline T*
02917   Space::realloc(T* b, int n, int m) {
02918     assert((n >= 0) && (m >= 0));
02919     return realloc<T>(b,static_cast<long unsigned int>(n),
02920                       static_cast<long unsigned int>(m));
02921   }
02922 
02923 #define GECODE_KERNEL_REALLOC(T)                                        \
02924   template<>                                                            \
02925   forceinline T*                                                        \
02926   Space::realloc<T>(T* b, long unsigned int n, long unsigned int m) {   \
02927     return static_cast<T*>(rrealloc(b,n*sizeof(T),m*sizeof(T)));        \
02928   }                                                                     \
02929   template<>                                                            \
02930   forceinline T*                                                        \
02931   Space::realloc<T>(T* b, long int n, long int m) {                     \
02932     assert((n >= 0) && (m >= 0));                                       \
02933     return realloc<T>(b,static_cast<long unsigned int>(n),              \
02934                       static_cast<long unsigned int>(m));               \
02935   }                                                                     \
02936   template<>                                                            \
02937   forceinline T*                                                        \
02938   Space::realloc<T>(T* b, unsigned int n, unsigned int m) {             \
02939     return realloc<T>(b,static_cast<long unsigned int>(n),              \
02940                       static_cast<long unsigned int>(m));               \
02941   }                                                                     \
02942   template<>                                                            \
02943   forceinline T*                                                        \
02944   Space::realloc<T>(T* b, int n, int m) {                               \
02945     assert((n >= 0) && (m >= 0));                                       \
02946     return realloc<T>(b,static_cast<long unsigned int>(n),              \
02947                       static_cast<long unsigned int>(m));               \
02948   }
02949 
02950   GECODE_KERNEL_REALLOC(bool)
02951   GECODE_KERNEL_REALLOC(signed char)
02952   GECODE_KERNEL_REALLOC(unsigned char)
02953   GECODE_KERNEL_REALLOC(signed short int)
02954   GECODE_KERNEL_REALLOC(unsigned short int)
02955   GECODE_KERNEL_REALLOC(signed int)
02956   GECODE_KERNEL_REALLOC(unsigned int)
02957   GECODE_KERNEL_REALLOC(signed long int)
02958   GECODE_KERNEL_REALLOC(unsigned long int)
02959   GECODE_KERNEL_REALLOC(float)
02960   GECODE_KERNEL_REALLOC(double)
02961 
02962 #undef GECODE_KERNEL_REALLOC
02963 
02964   template<class T>
02965   forceinline T**
02966   Space::realloc(T** b, long unsigned int n, long unsigned int m) {
02967     return static_cast<T**>(rrealloc(b,n*sizeof(T),m*sizeof(T*)));
02968   }
02969   template<class T>
02970   forceinline T**
02971   Space::realloc(T** b, long int n, long int m) {
02972     assert((n >= 0) && (m >= 0));
02973     return realloc<T*>(b,static_cast<long unsigned int>(n),
02974                        static_cast<long unsigned int>(m));
02975   }
02976   template<class T>
02977   forceinline T**
02978   Space::realloc(T** b, unsigned int n, unsigned int m) {
02979     return realloc<T*>(b,static_cast<long unsigned int>(n),
02980                        static_cast<long unsigned int>(m));
02981   }
02982   template<class T>
02983   forceinline T**
02984   Space::realloc(T** b, int n, int m) {
02985     assert((n >= 0) && (m >= 0));
02986     return realloc<T*>(b,static_cast<long unsigned int>(n),
02987                        static_cast<long unsigned int>(m));
02988   }
02989 
02990 
02991 #ifdef GECODE_HAS_VAR_DISPOSE
02992   template<class VIC>
02993   forceinline VarImpBase*
02994   Space::vars_d(void) const {
02995     return _vars_d[VIC::idx_d];
02996   }
02997   template<class VIC>
02998   forceinline void
02999   Space::vars_d(VarImpBase* x) {
03000     _vars_d[VIC::idx_d] = x;
03001   }
03002 #endif
03003 
03004   // Space allocated entities: Actors, variable implementations, and advisors
03005   forceinline void
03006   Actor::operator delete(void*) {}
03007   forceinline void
03008   Actor::operator delete(void*, Space&) {}
03009   forceinline void*
03010   Actor::operator new(size_t s, Space& home) {
03011     return home.ralloc(s);
03012   }
03013 
03014   template<class VIC>
03015   forceinline void
03016   VarImp<VIC>::operator delete(void*) {}
03017   template<class VIC>
03018   forceinline void
03019   VarImp<VIC>::operator delete(void*, Space&) {}
03020   template<class VIC>
03021   forceinline void*
03022   VarImp<VIC>::operator new(size_t s, Space& home) {
03023     return home.ralloc(s);
03024   }
03025 
03026 #ifndef __GNUC__
03027   forceinline void
03028   Advisor::operator delete(void*) {}
03029 #endif
03030   forceinline void
03031   Advisor::operator delete(void*, Space&) {}
03032   forceinline void*
03033   Advisor::operator new(size_t s, Space& home) {
03034     return home.ralloc(s);
03035   }
03036 
03037   forceinline void
03038   NGL::operator delete(void*) {}
03039   forceinline void
03040   NGL::operator delete(void*, Space&) {}
03041   forceinline void*
03042   NGL::operator new(size_t s, Space& home) {
03043     return home.ralloc(s);
03044   }
03045 
03046 
03047   /*
03048    * No-goods
03049    *
03050    */
03051   forceinline
03052   NoGoods::NoGoods(void)
03053     : n(0) {}
03054   forceinline unsigned long int
03055   NoGoods::ng(void) const {
03056     return n;
03057   }
03058   forceinline void
03059   NoGoods::ng(unsigned long int n0) {
03060     n=n0;
03061   }
03062   forceinline
03063   NoGoods::~NoGoods(void) {}
03064 
03065 
03066   /*
03067    * Information from meta search engines
03068    */
03069   forceinline
03070   MetaInfo::MetaInfo(unsigned long int r0,
03071                      unsigned long int s0,
03072                      unsigned long int f0,
03073                      const Space* l0,
03074                      NoGoods& ng0)
03075     : t(RESTART), r(r0), s(s0), f(f0), l(l0), ng(ng0), a(0) {}
03076 
03077   forceinline
03078   MetaInfo::MetaInfo(unsigned int a0)
03079     : t(PORTFOLIO), r(0), s(0), f(0), l(NULL), ng(NoGoods::eng), a(a0) {}
03080 
03081   forceinline MetaInfo::Type
03082   MetaInfo::type(void) const {
03083     return t;
03084   }
03085   forceinline unsigned long int
03086   MetaInfo::restart(void) const {
03087     assert(type() == RESTART);
03088     return r;
03089   }
03090   forceinline unsigned long int
03091   MetaInfo::solution(void) const {
03092     assert(type() == RESTART);
03093     return s;
03094   }
03095   forceinline unsigned long int
03096   MetaInfo::fail(void) const {
03097     assert(type() == RESTART);
03098     return f;
03099   }
03100   forceinline const Space*
03101   MetaInfo::last(void) const {
03102     assert(type() == RESTART);
03103     return l;
03104   }
03105   forceinline const NoGoods&
03106   MetaInfo::nogoods(void) const {
03107     assert(type() == RESTART);
03108     return ng;
03109   }
03110   forceinline unsigned int
03111   MetaInfo::asset(void) const {
03112     assert(type() == PORTFOLIO);
03113     return a;
03114   }
03115 
03116 
03117 
03118   /*
03119    * ActorLink
03120    *
03121    */
03122   forceinline ActorLink*
03123   ActorLink::prev(void) const {
03124     return _prev;
03125   }
03126 
03127   forceinline ActorLink*
03128   ActorLink::next(void) const {
03129     return _next;
03130   }
03131 
03132   forceinline ActorLink**
03133   ActorLink::next_ref(void) {
03134     return &_next;
03135   }
03136 
03137   forceinline void
03138   ActorLink::prev(ActorLink* al) {
03139     _prev = al;
03140   }
03141 
03142   forceinline void
03143   ActorLink::next(ActorLink* al) {
03144     _next = al;
03145   }
03146 
03147   forceinline void
03148   ActorLink::unlink(void) {
03149     ActorLink* p = _prev; ActorLink* n = _next;
03150     p->_next = n; n->_prev = p;
03151   }
03152 
03153   forceinline void
03154   ActorLink::init(void) {
03155     _next = this; _prev =this;
03156   }
03157 
03158   forceinline void
03159   ActorLink::head(ActorLink* a) {
03160     // Inserts al at head of link-chain (that is, after this)
03161     ActorLink* n = _next;
03162     this->_next = a; a->_prev = this;
03163     a->_next = n; n->_prev = a;
03164   }
03165 
03166   forceinline void
03167   ActorLink::tail(ActorLink* a) {
03168     // Inserts al at tail of link-chain (that is, before this)
03169     ActorLink* p = _prev;
03170     a->_next = this; this->_prev = a;
03171     p->_next = a; a->_prev = p;
03172   }
03173 
03174   forceinline bool
03175   ActorLink::empty(void) const {
03176     return _next == this;
03177   }
03178 
03179   template<class T>
03180   forceinline ActorLink*
03181   ActorLink::cast(T* a) {
03182     // Turning al into a reference is for gcc, assume is for MSVC
03183     GECODE_NOT_NULL(a);
03184     ActorLink& t = *a;
03185     return static_cast<ActorLink*>(&t);
03186   }
03187 
03188   template<class T>
03189   forceinline const ActorLink*
03190   ActorLink::cast(const T* a) {
03191     // Turning al into a reference is for gcc, assume is for MSVC
03192     GECODE_NOT_NULL(a);
03193     const ActorLink& t = *a;
03194     return static_cast<const ActorLink*>(&t);
03195   }
03196 
03197 
03198   /*
03199    * Actor
03200    *
03201    */
03202   forceinline Actor*
03203   Actor::cast(ActorLink* al) {
03204     // Turning al into a reference is for gcc, assume is for MSVC
03205     GECODE_NOT_NULL(al);
03206     ActorLink& t = *al;
03207     return static_cast<Actor*>(&t);
03208   }
03209 
03210   forceinline const Actor*
03211   Actor::cast(const ActorLink* al) {
03212     // Turning al into a reference is for gcc, assume is for MSVC
03213     GECODE_NOT_NULL(al);
03214     const ActorLink& t = *al;
03215     return static_cast<const Actor*>(&t);
03216   }
03217 
03218   forceinline void
03219   Home::notice(Actor& a, ActorProperty p, bool duplicate) {
03220     s.notice(a,p,duplicate);
03221   }
03222 
03223   forceinline Space*
03224   Space::clone(CloneStatistics&) const {
03225     // Clone is only const for search engines. During cloning, several data
03226     // structures are updated (e.g. forwarding pointers), so we have to
03227     // cast away the constness.
03228     return const_cast<Space*>(this)->_clone();
03229   }
03230 
03231   forceinline void
03232   Space::commit(const Choice& c, unsigned int a, CommitStatistics&) {
03233     _commit(c,a);
03234   }
03235 
03236   forceinline void
03237   Space::trycommit(const Choice& c, unsigned int a, CommitStatistics&) {
03238     _trycommit(c,a);
03239   }
03240 
03241   forceinline double
03242   Space::afc_decay(void) const {
03243     return ssd.data().gpi.decay();
03244   }
03245 
03246   forceinline void
03247   Space::afc_decay(double d) {
03248     ssd.data().gpi.decay(d);
03249   }
03250 
03251   forceinline size_t
03252   Actor::dispose(Space&) {
03253     return sizeof(*this);
03254   }
03255 
03256 
03257   /*
03258    * Home for posting actors
03259    *
03260    */
03261   forceinline
03262   Home::Home(Space& s0, Propagator* p0,
03263              PropagatorGroup pg0, BrancherGroup bg0)
03264     : s(s0), p(p0), pg(pg0), bg(bg0) {}
03265   forceinline Home&
03266   Home::operator =(const Home& h) {
03267     s=h.s; p=h.p; pg=h.pg; bg=h.bg;
03268     return *this;
03269   }
03270   forceinline
03271   Home::operator Space&(void) {
03272     return s;
03273   }
03274   forceinline Home
03275   Home::operator ()(Propagator& p) {
03276     return Home(s,&p);
03277   }
03278   forceinline Home
03279   Home::operator ()(PropagatorGroup pg) {
03280     return Home(s,NULL,pg,BrancherGroup::def);
03281   }
03282   forceinline Home
03283   Home::operator ()(BrancherGroup bg) {
03284     return Home(s,NULL,PropagatorGroup::def,bg);
03285   }
03286   forceinline Home
03287   Space::operator ()(Propagator& p) {
03288     return Home(*this,&p);
03289   }
03290   forceinline Home
03291   Space::operator ()(PropagatorGroup pg) {
03292     return Home(*this,NULL,pg,BrancherGroup::def);
03293   }
03294   forceinline Home
03295   Space::operator ()(BrancherGroup bg) {
03296     return Home(*this,NULL,PropagatorGroup::def,bg);
03297   }
03298   forceinline Propagator*
03299   Home::propagator(void) const {
03300     return p;
03301   }
03302   forceinline PropagatorGroup
03303   Home::propagatorgroup(void) const {
03304     return pg;
03305   }
03306   forceinline BrancherGroup
03307   Home::branchergroup(void) const {
03308     return bg;
03309   }
03310 
03311   /*
03312    * View trace information
03313    *
03314    */
03315   forceinline void
03316   ViewTraceInfo::propagator(Propagator& p) {
03317     who = reinterpret_cast<ptrdiff_t>(&p) | PROPAGATOR;
03318   }
03319   forceinline void
03320   ViewTraceInfo::brancher(Brancher& b) {
03321     who = reinterpret_cast<ptrdiff_t>(&b) | BRANCHER;
03322   }
03323   forceinline void
03324   ViewTraceInfo::post(PropagatorGroup g) {
03325     who = (g.id() << 2) | POST;
03326   }
03327   forceinline void
03328   ViewTraceInfo::other(void) {
03329     who = OTHER;
03330   }
03331   forceinline ViewTraceInfo::What
03332   ViewTraceInfo::what(void) const {
03333     return static_cast<What>(who & 3);
03334   }
03335   forceinline const Propagator&
03336   ViewTraceInfo::propagator(void) const {
03337     assert(what() == PROPAGATOR);
03338     // Because PROPAGATOR == 0
03339     return *reinterpret_cast<Propagator*>(who);
03340   }
03341   forceinline const Brancher&
03342   ViewTraceInfo::brancher(void) const {
03343     assert(what() == BRANCHER);
03344     return *reinterpret_cast<Brancher*>(who & ~3);
03345   }
03346   forceinline PropagatorGroup
03347   ViewTraceInfo::post(void) const {
03348     assert(what() == POST);
03349     return PropagatorGroup(static_cast<unsigned int>(who >> 2));
03350   }
03351 
03352   /*
03353    * Post information
03354    */
03355   forceinline
03356   PostInfo::PostInfo(Home home)
03357     : h(home), pg(home.propagatorgroup()),
03358       pid(h.ssd.data().gpi.pid()),
03359       nested(h.pc.p.vti.what() != ViewTraceInfo::OTHER) {
03360     h.pc.p.vti.post(pg);
03361   }
03362 
03363   forceinline
03364   PostInfo::~PostInfo(void) {
03365     if (!nested) {
03366       if (h.pc.p.bid_sc & Space::sc_trace)
03367         h.post(*this);
03368       h.pc.p.vti.other();
03369     }
03370   }
03371 
03372 
03373   /*
03374    * Propagate trace information
03375    *
03376    */
03377   forceinline
03378   PropagateTraceInfo::PropagateTraceInfo(unsigned int i0, PropagatorGroup g0,
03379                                          const Propagator* p0, Status s0)
03380     : i(i0), g(g0), p(p0), s(s0) {}
03381   forceinline unsigned int
03382   PropagateTraceInfo::id(void) const {
03383     return i;
03384   }
03385   forceinline PropagatorGroup
03386   PropagateTraceInfo::group(void) const {
03387     return g;
03388   }
03389   forceinline const Propagator*
03390   PropagateTraceInfo::propagator(void) const {
03391     return p;
03392   }
03393   forceinline PropagateTraceInfo::Status
03394   PropagateTraceInfo::status(void) const {
03395     return s;
03396   }
03397 
03398 
03399   /*
03400    * Commit trace information
03401    *
03402    */
03403   forceinline
03404   CommitTraceInfo::CommitTraceInfo(const Brancher& b0, const Choice& c0,
03405                                    unsigned int a0)
03406     : b(b0), c(c0), a(a0) {}
03407   forceinline unsigned int
03408   CommitTraceInfo::id(void) const {
03409     return b.id();
03410   }
03411   forceinline BrancherGroup
03412   CommitTraceInfo::group(void) const {
03413     return b.group();
03414   }
03415   forceinline const Brancher&
03416   CommitTraceInfo::brancher(void) const {
03417     return b;
03418   }
03419   forceinline const Choice&
03420   CommitTraceInfo::choice(void) const {
03421     return c;
03422   }
03423   forceinline unsigned int
03424   CommitTraceInfo::alternative(void) const {
03425     return a;
03426   }
03427 
03428 
03429   /*
03430    * Post trace information
03431    *
03432    */
03433   forceinline
03434   PostTraceInfo::PostTraceInfo(PropagatorGroup g0, Status s0, unsigned int n0)
03435     : g(g0), s(s0), n(n0) {}
03436   forceinline PropagatorGroup
03437   PostTraceInfo::group(void) const {
03438     return g;
03439   }
03440   forceinline PostTraceInfo::Status
03441   PostTraceInfo::status(void) const {
03442     return s;
03443   }
03444   forceinline unsigned int
03445   PostTraceInfo::propagators(void) const {
03446     return n;
03447   }
03448 
03449 
03450   /*
03451    * Propagator
03452    *
03453    */
03454   forceinline Propagator*
03455   Propagator::cast(ActorLink* al) {
03456     // Turning al into a reference is for gcc, assume is for MSVC
03457     GECODE_NOT_NULL(al);
03458     ActorLink& t = *al;
03459     return static_cast<Propagator*>(&t);
03460   }
03461 
03462   forceinline const Propagator*
03463   Propagator::cast(const ActorLink* al) {
03464     // Turning al into a reference is for gcc, assume is for MSVC
03465     GECODE_NOT_NULL(al);
03466     const ActorLink& t = *al;
03467     return static_cast<const Propagator*>(&t);
03468   }
03469 
03470   forceinline Propagator*
03471   Propagator::fwd(void) const {
03472     return static_cast<Propagator*>(prev());
03473   }
03474 
03475   forceinline bool
03476   Propagator::disabled(void) const {
03477     return Support::marked(gpi_disabled);
03478   }
03479 
03480   forceinline void
03481   Propagator::disable(Space& home) {
03482     home.pc.p.bid_sc |= Space::sc_disabled;
03483     gpi_disabled = Support::fmark(gpi_disabled);
03484   }
03485 
03486   forceinline void
03487   Propagator::enable(Space& home) {
03488     (void) home;
03489     gpi_disabled = Support::funmark(gpi_disabled);
03490   }
03491 
03492   forceinline Kernel::GPI::Info&
03493   Propagator::gpi(void) {
03494     return *static_cast<Kernel::GPI::Info*>(Support::funmark(gpi_disabled));
03495   }
03496 
03497   forceinline
03498   Propagator::Propagator(Home home)
03499     : gpi_disabled((home.propagator() != NULL) ?
03500                    // Inherit propagator information
03501                    home.propagator()->gpi_disabled :
03502                    // New propagator information
03503                    static_cast<Space&>(home).ssd.data().gpi.allocate
03504                    (home.propagatorgroup().gid)) {
03505     u.advisors = NULL;
03506     assert((u.med == 0) && (u.size == 0));
03507     static_cast<Space&>(home).pl.head(this);
03508   }
03509 
03510   forceinline
03511   Propagator::Propagator(Space&, Propagator& p)
03512     : gpi_disabled(p.gpi_disabled) {
03513     u.advisors = NULL;
03514     assert((u.med == 0) && (u.size == 0));
03515     // Set forwarding pointer
03516     p.prev(this);
03517   }
03518 
03519   forceinline ModEventDelta
03520   Propagator::modeventdelta(void) const {
03521     return u.med;
03522   }
03523 
03524   forceinline double
03525   Propagator::afc(void) const {
03526     return const_cast<Propagator&>(*this).gpi().afc;
03527   }
03528 
03529 #ifdef GECODE_HAS_CBS
03530   forceinline void
03531   Propagator::solndistrib(Space&, SendMarginal) const {}
03532 
03533   forceinline void
03534   Propagator::domainsizesum(InDecision, unsigned int& size,
03535                                   unsigned int& size_b) const {
03536     size = 0;
03537     size_b = 0;
03538   }
03539 #endif
03540 
03541   forceinline unsigned int
03542   Propagator::id(void) const {
03543     return const_cast<Propagator&>(*this).gpi().pid;
03544   }
03545 
03546   forceinline PropagatorGroup
03547   Propagator::group(void) const {
03548     return PropagatorGroup(const_cast<Propagator&>(*this).gpi().gid);
03549   }
03550 
03551   forceinline void
03552   Propagator::group(PropagatorGroup g) {
03553     gpi().gid = g.id();
03554   }
03555 
03556   forceinline ExecStatus
03557   Space::ES_SUBSUMED_DISPOSED(Propagator& p, size_t s) {
03558     p.u.size = s;
03559     return __ES_SUBSUMED;
03560   }
03561 
03562   forceinline ExecStatus
03563   Space::ES_SUBSUMED(Propagator& p) {
03564     p.u.size = p.dispose(*this);
03565     return __ES_SUBSUMED;
03566   }
03567 
03568   forceinline ExecStatus
03569   Space::ES_FIX_PARTIAL(Propagator& p, const ModEventDelta& med) {
03570     p.u.med = med;
03571     assert(p.u.med != 0);
03572     return __ES_PARTIAL;
03573   }
03574 
03575   forceinline ExecStatus
03576   Space::ES_NOFIX_PARTIAL(Propagator& p, const ModEventDelta& med) {
03577     p.u.med = AllVarConf::med_combine(p.u.med,med);
03578     assert(p.u.med != 0);
03579     return __ES_PARTIAL;
03580   }
03581 
03582 
03583 
03584   /*
03585    * Brancher
03586    *
03587    */
03588   forceinline Brancher*
03589   Brancher::cast(ActorLink* al) {
03590     // Turning al into a reference is for gcc, assume is for MSVC
03591     GECODE_NOT_NULL(al);
03592     ActorLink& t = *al;
03593     return static_cast<Brancher*>(&t);
03594   }
03595 
03596   forceinline const Brancher*
03597   Brancher::cast(const ActorLink* al) {
03598     // Turning al into a reference is for gcc, assume is for MSVC
03599     GECODE_NOT_NULL(al);
03600     const ActorLink& t = *al;
03601     return static_cast<const Brancher*>(&t);
03602   }
03603 
03604   forceinline
03605   Brancher::Brancher(Home _home) :
03606     gid(_home.branchergroup().gid) {
03607     Space& home = static_cast<Space&>(_home);
03608     bid = home.pc.p.bid_sc >> Space::sc_bits;
03609     home.pc.p.bid_sc += (1 << Space::sc_bits);
03610     if ((home.pc.p.bid_sc >> Space::sc_bits) == 0U)
03611       throw TooManyBranchers("Brancher::Brancher");
03612     // If no brancher available, make it the first one
03613     if (home.b_status == &static_cast<Space&>(home).bl) {
03614       home.b_status = this;
03615       if (home.b_commit == &static_cast<Space&>(home).bl)
03616         home.b_commit = this;
03617     }
03618     home.bl.tail(this);
03619   }
03620 
03621   forceinline
03622   Brancher::Brancher(Space&, Brancher& b)
03623     : bid(b.bid), gid(b.gid) {
03624     // Set forwarding pointer
03625     b.prev(this);
03626   }
03627 
03628   forceinline unsigned int
03629   Brancher::id(void) const {
03630     return bid;
03631   }
03632 
03633   forceinline BrancherGroup
03634   Brancher::group(void) const {
03635     return BrancherGroup(gid);
03636   }
03637 
03638   forceinline void
03639   Brancher::group(BrancherGroup g) {
03640     gid = g.id();
03641   }
03642 
03643 
03644   forceinline void
03645   Space::kill(Brancher& b) {
03646     assert(!failed());
03647     // Make sure that neither b_status nor b_commit does not point to b!
03648     if (b_commit == &b)
03649       b_commit = Brancher::cast(b.next());
03650     if (b_status == &b)
03651       b_status = Brancher::cast(b.next());
03652     b.unlink();
03653     rfree(&b,b.dispose(*this));
03654   }
03655 
03656   forceinline void
03657   Space::kill(Propagator& p) {
03658     assert(!failed());
03659     p.unlink();
03660     rfree(&p,p.dispose(*this));
03661   }
03662 
03663   forceinline Brancher*
03664   Space::brancher(unsigned int id) {
03665     /*
03666      * Due to weakly monotonic propagators the following scenario might
03667      * occur: a brancher has been committed with all its available
03668      * choices. Then, propagation determines less information
03669      * than before and the brancher now will create new choices.
03670      * Later, during recomputation, all of these choices
03671      * can be used together, possibly interleaved with
03672      * choices for other branchers. That means all branchers
03673      * must be scanned to find the matching brancher for the choice.
03674      *
03675      * b_commit tries to optimize scanning as it is most likely that
03676      * recomputation does not generate new choices during recomputation
03677      * and hence b_commit is moved from newer to older branchers.
03678      */
03679     Brancher* b_old = b_commit;
03680     // Try whether we are lucky
03681     while (b_commit != Brancher::cast(&bl))
03682       if (id != b_commit->id())
03683         b_commit = Brancher::cast(b_commit->next());
03684       else
03685         return b_commit;
03686     if (b_commit == Brancher::cast(&bl)) {
03687       // We did not find the brancher, start at the beginning
03688       b_commit = Brancher::cast(bl.next());
03689       while (b_commit != b_old)
03690         if (id != b_commit->id())
03691           b_commit = Brancher::cast(b_commit->next());
03692         else
03693           return b_commit;
03694     }
03695     return NULL;
03696   }
03697 
03698 
03699   /*
03700    * Local objects
03701    *
03702    */
03703 
03704   forceinline LocalObject*
03705   LocalObject::cast(ActorLink* al) {
03706     // Turning al into a reference is for gcc, assume is for MSVC
03707     GECODE_NOT_NULL(al);
03708     ActorLink& t = *al;
03709     return static_cast<LocalObject*>(&t);
03710   }
03711 
03712   forceinline const LocalObject*
03713   LocalObject::cast(const ActorLink* al) {
03714     // Turning al into a reference is for gcc, assume is for MSVC
03715     GECODE_NOT_NULL(al);
03716     const ActorLink& t = *al;
03717     return static_cast<const LocalObject*>(&t);
03718   }
03719 
03720   forceinline
03721   LocalObject::LocalObject(Home home) {
03722     (void) home;
03723     ActorLink::cast(this)->prev(NULL);
03724   }
03725 
03726   forceinline
03727   LocalObject::LocalObject(Space&, LocalObject&) {
03728     ActorLink::cast(this)->prev(NULL);
03729   }
03730 
03731   forceinline LocalObject*
03732   LocalObject::fwd(Space& home) {
03733     if (prev() == NULL)
03734       fwdcopy(home);
03735     return LocalObject::cast(prev());
03736   }
03737 
03738   forceinline
03739   LocalHandle::LocalHandle(void) : o(NULL) {}
03740   forceinline
03741   LocalHandle::LocalHandle(LocalObject* lo) : o(lo) {}
03742   forceinline
03743   LocalHandle::LocalHandle(const LocalHandle& lh) : o(lh.o) {}
03744   forceinline LocalHandle&
03745   LocalHandle::operator =(const LocalHandle& lh) {
03746     o = lh.o;
03747     return *this;
03748   }
03749   forceinline
03750   LocalHandle::~LocalHandle(void) {}
03751   forceinline LocalObject*
03752   LocalHandle::object(void) const { return o; }
03753   forceinline void
03754   LocalHandle::object(LocalObject* n) { o = n; }
03755   forceinline void
03756   LocalHandle::update(Space& home, LocalHandle& lh) {
03757     object(lh.object()->fwd(home));
03758   }
03759 
03760 
03761   /*
03762    * Choices
03763    *
03764    */
03765   forceinline
03766   Choice::Choice(const Brancher& b, const unsigned int a)
03767     : bid(b.id()), alt(a) {}
03768 
03769   forceinline unsigned int
03770   Choice::alternatives(void) const {
03771     return alt;
03772   }
03773 
03774   forceinline unsigned int
03775   Choice::id(void) const {
03776     return bid;
03777   }
03778 
03779   forceinline
03780   Choice::~Choice(void) {}
03781 
03782 
03783 
03784   /*
03785    * No-good literal
03786    *
03787    */
03788   forceinline bool
03789   NGL::leaf(void) const {
03790     return Support::marked(nl);
03791   }
03792   forceinline NGL*
03793   NGL::next(void) const {
03794     return static_cast<NGL*>(Support::funmark(nl));
03795   }
03796   forceinline void
03797   NGL::leaf(bool l) {
03798     nl = l ? Support::fmark(nl) : Support::funmark(nl);
03799   }
03800   forceinline void
03801   NGL::next(NGL* n) {
03802     nl = Support::marked(nl) ? Support::mark(n) : n;
03803   }
03804   forceinline NGL*
03805   NGL::add(NGL* n, bool l) {
03806     nl = Support::marked(nl) ? Support::mark(n) : n;
03807     n->leaf(l);
03808     return n;
03809   }
03810 
03811   forceinline
03812   NGL::NGL(void)
03813     : nl(NULL) {}
03814   forceinline
03815   NGL::NGL(Space&)
03816     : nl(NULL) {}
03817   forceinline
03818   NGL::NGL(Space&, NGL&)
03819     : nl(NULL) {}
03820   forceinline size_t
03821   NGL::dispose(Space&) {
03822     return sizeof(*this);
03823   }
03824 
03825   /*
03826    * Advisor
03827    *
03828    */
03829   template<class A>
03830   forceinline
03831   Advisor::Advisor(Space&, Propagator& p, Council<A>& c) {
03832     // Store propagator and forwarding in prev()
03833     ActorLink::prev(&p);
03834     // Link to next advisor in next()
03835     ActorLink::next(c.advisors); c.advisors = static_cast<A*>(this);
03836   }
03837 
03838   forceinline
03839   Advisor::Advisor(Space&, Advisor&) {}
03840 
03841   forceinline bool
03842   Advisor::disposed(void) const {
03843     return prev() == NULL;
03844   }
03845 
03846   forceinline Advisor*
03847   Advisor::cast(ActorLink* al) {
03848     return static_cast<Advisor*>(al);
03849   }
03850 
03851   forceinline const Advisor*
03852   Advisor::cast(const ActorLink* al) {
03853     return static_cast<const Advisor*>(al);
03854   }
03855 
03856   forceinline Propagator&
03857   Advisor::propagator(void) const {
03858     assert(!disposed());
03859     return *Propagator::cast(ActorLink::prev());
03860   }
03861 
03862   template<class A>
03863   forceinline void
03864   Advisor::dispose(Space&,Council<A>&) {
03865     assert(!disposed());
03866     ActorLink::prev(NULL);
03867     // Shorten chains of disposed advisors by one, if possible
03868     Advisor* n = Advisor::cast(next());
03869     if ((n != NULL) && n->disposed())
03870       next(n->next());
03871   }
03872 
03873   forceinline const ViewTraceInfo&
03874   Advisor::operator ()(const Space& home) const {
03875     return home.pc.p.vti;
03876   }
03877 
03878   template<class A>
03879   forceinline ExecStatus
03880   Space::ES_FIX_DISPOSE(Council<A>& c, A& a) {
03881     a.dispose(*this,c);
03882     return ES_FIX;
03883   }
03884 
03885   template<class A>
03886   forceinline ExecStatus
03887   Space::ES_NOFIX_DISPOSE(Council<A>& c, A& a) {
03888     a.dispose(*this,c);
03889     return ES_NOFIX;
03890   }
03891 
03892   template<class A>
03893   forceinline ExecStatus
03894   Space::ES_NOFIX_DISPOSE_FORCE(Council<A>& c, A& a) {
03895     a.dispose(*this,c);
03896     return ES_NOFIX_FORCE;
03897   }
03898 
03899 
03900 
03901   /*
03902    * Advisor council
03903    *
03904    */
03905   template<class A>
03906   forceinline
03907   Council<A>::Council(void) {}
03908 
03909   template<class A>
03910   forceinline
03911   Council<A>::Council(Space&)
03912     : advisors(NULL) {}
03913 
03914   template<class A>
03915   forceinline bool
03916   Council<A>::empty(void) const {
03917     ActorLink* a = advisors;
03918     while ((a != NULL) && static_cast<A*>(a)->disposed())
03919       a = a->next();
03920     advisors = a;
03921     return a == NULL;
03922   }
03923 
03924   template<class A>
03925   forceinline void
03926   Council<A>::update(Space& home, Council<A>& c) {
03927     // Skip all disposed advisors
03928     {
03929       ActorLink* a = c.advisors;
03930       while ((a != NULL) && static_cast<A*>(a)->disposed())
03931         a = a->next();
03932       c.advisors = a;
03933     }
03934     // Are there any advisors to be cloned?
03935     if (c.advisors != NULL) {
03936       // The propagator in from-space
03937       Propagator* p_f = &static_cast<A*>(c.advisors)->propagator();
03938       // The propagator in to-space
03939       Propagator* p_t = Propagator::cast(p_f->prev());
03940       // Advisors in from-space
03941       ActorLink** a_f = &c.advisors;
03942       // Advisors in to-space
03943       A* a_t = NULL;
03944       while (*a_f != NULL) {
03945         if (static_cast<A*>(*a_f)->disposed()) {
03946           *a_f = (*a_f)->next();
03947         } else {
03948           // Run specific copying part
03949           A* a = new (home) A(home,*static_cast<A*>(*a_f));
03950           // Set propagator pointer
03951           a->prev(p_t);
03952           // Set forwarding pointer
03953           (*a_f)->prev(a);
03954           // Link
03955           a->next(a_t);
03956           a_t = a;
03957           a_f = (*a_f)->next_ref();
03958         }
03959       }
03960       advisors = a_t;
03961       // Enter advisor link for reset
03962       assert(p_f->u.advisors == NULL);
03963       p_f->u.advisors = c.advisors;
03964     } else {
03965       advisors = NULL;
03966     }
03967   }
03968 
03969   template<class A>
03970   forceinline void
03971   Council<A>::dispose(Space& home) {
03972     ActorLink* a = advisors;
03973     while (a != NULL) {
03974       if (!static_cast<A*>(a)->disposed())
03975         static_cast<A*>(a)->dispose(home,*this);
03976       a = a->next();
03977     }
03978   }
03979 
03980 
03981 
03982   /*
03983    * Advisor iterator
03984    *
03985    */
03986   template<class A>
03987   forceinline
03988   Advisors<A>::Advisors(const Council<A>& c)
03989     : a(c.advisors) {
03990     while ((a != NULL) && static_cast<A*>(a)->disposed())
03991       a = a->next();
03992   }
03993 
03994   template<class A>
03995   forceinline bool
03996   Advisors<A>::operator ()(void) const {
03997     return a != NULL;
03998   }
03999 
04000   template<class A>
04001   forceinline void
04002   Advisors<A>::operator ++(void) {
04003     do {
04004       a = a->next();
04005     } while ((a != NULL) && static_cast<A*>(a)->disposed());
04006   }
04007 
04008   template<class A>
04009   forceinline A&
04010   Advisors<A>::advisor(void) const {
04011     return *static_cast<A*>(a);
04012   }
04013 
04014 
04015 
04016   /*
04017    * Space
04018    *
04019    */
04020   forceinline void
04021   Space::enqueue(Propagator* p) {
04022     ActorLink::cast(p)->unlink();
04023     ActorLink* c = &pc.p.queue[p->cost(*this,p->u.med).ac];
04024     c->tail(ActorLink::cast(p));
04025     if (c > pc.p.active)
04026       pc.p.active = c;
04027   }
04028 
04029   forceinline void
04030   Space::fail(void) {
04031     pc.p.active = &pc.p.queue[PropCost::AC_MAX+1]+1;
04032     /*
04033      * Now active points beyond the last queue. This is essential as
04034      * enqueuing a propagator in a failed space keeps the space
04035      * failed.
04036      */
04037   }
04038   forceinline void
04039   Home::fail(void) {
04040     s.fail();
04041   }
04042 
04043   forceinline bool
04044   Space::failed(void) const {
04045     return pc.p.active > &pc.p.queue[PropCost::AC_MAX+1];
04046   }
04047   forceinline bool
04048   Home::failed(void) const {
04049     return s.failed();
04050   }
04051 
04052   forceinline bool
04053   Space::stable(void) const {
04054     return ((pc.p.active < &pc.p.queue[0]) ||
04055             (pc.p.active > &pc.p.queue[PropCost::AC_MAX+1]));
04056   }
04057 
04058   forceinline void
04059   Space::notice(Actor& a, ActorProperty p, bool d) {
04060     if (p & AP_DISPOSE) {
04061       ap_notice_dispose(&a,d);
04062     }
04063     if (p & AP_VIEW_TRACE) {
04064       pc.p.bid_sc |= sc_trace;
04065     }
04066     if (p & AP_TRACE) {
04067       pc.p.bid_sc |= sc_trace;
04068     }
04069     // Currently unused
04070     if (p & AP_WEAKLY) {}
04071   }
04072 
04073   forceinline void
04074   Space::ignore(Actor& a, ActorProperty p, bool d) {
04075     // Check wether array has already been discarded as space
04076     // deletion is already in progress
04077     if ((p & AP_DISPOSE) && (d_fst != NULL))
04078       ap_ignore_dispose(&a,d);
04079     if (p & AP_VIEW_TRACE) {}
04080     if (p & AP_TRACE) {}
04081     // Currently unused
04082     if (p & AP_WEAKLY) {}
04083   }
04084 
04085 
04086 
04087   /*
04088    * Variable implementation
04089    *
04090    */
04091   template<class VIC>
04092   forceinline ActorLink**
04093   VarImp<VIC>::actor(PropCond pc) {
04094     assert((pc >= 0)  && (pc < pc_max+2));
04095     return (pc == 0) ? b.base : b.base+u.idx[pc-1];
04096   }
04097 
04098   template<class VIC>
04099   forceinline ActorLink**
04100   VarImp<VIC>::actorNonZero(PropCond pc) {
04101     assert((pc > 0)  && (pc < pc_max+2));
04102     return b.base+u.idx[pc-1];
04103   }
04104 
04105   template<class VIC>
04106   forceinline unsigned int&
04107   VarImp<VIC>::idx(PropCond pc) {
04108     assert((pc > 0)  && (pc < pc_max+2));
04109     return u.idx[pc-1];
04110   }
04111 
04112   template<class VIC>
04113   forceinline unsigned int
04114   VarImp<VIC>::idx(PropCond pc) const {
04115     assert((pc > 0)  && (pc < pc_max+2));
04116     return u.idx[pc-1];
04117   }
04118 
04119   template<class VIC>
04120   forceinline
04121   VarImp<VIC>::VarImp(Space& home)
04122 #ifdef GECODE_HAS_CBS
04123   : var_id(++home.var_id_counter)
04124 #endif
04125   {
04126 #ifndef GECODE_HAS_CBS
04127     (void) home;
04128 #endif
04129     b.base = NULL; entries = 0;
04130     for (PropCond pc=1; pc<pc_max+2; pc++)
04131       idx(pc) = 0;
04132     free_and_bits = 0;
04133   }
04134 
04135   template<class VIC>
04136   forceinline
04137   VarImp<VIC>::VarImp(void)
04138 #ifdef GECODE_HAS_CBS
04139   : var_id(0)
04140 #endif
04141   {
04142     b.base = NULL; entries = 0;
04143     for (PropCond pc=1; pc<pc_max+2; pc++)
04144       idx(pc) = 0;
04145     free_and_bits = 0;
04146   }
04147 
04148 #ifdef GECODE_HAS_CBS
04149   template<class VIC>
04150   forceinline unsigned int
04151   VarImp<VIC>::id(void) const {
04152     return var_id;
04153   }
04154 #endif
04155 
04156   template<class VIC>
04157   forceinline unsigned int
04158   VarImp<VIC>::degree(void) const {
04159     assert(!copied());
04160     return entries;
04161   }
04162 
04163   template<class VIC>
04164   forceinline double
04165   VarImp<VIC>::afc(void) const {
04166     double d = 0.0;
04167     // Count the afc of each propagator
04168     {
04169       ActorLink** a = const_cast<VarImp<VIC>*>(this)->actor(0);
04170       ActorLink** e = const_cast<VarImp<VIC>*>(this)->actorNonZero(pc_max+1);
04171       while (a < e) {
04172         d += Propagator::cast(*a)->afc(); a++;
04173       }
04174     }
04175     // Count the afc of each advisor's propagator
04176     {
04177       ActorLink** a = const_cast<VarImp<VIC>*>(this)->actorNonZero(pc_max+1);
04178       ActorLink** e = const_cast<VarImp<VIC>*>(this)->b.base+entries;
04179       while (a < e) {
04180         d += Advisor::cast(static_cast<ActorLink*>(Support::funmark(*a)))
04181           ->propagator().afc();
04182         a++;
04183       }
04184     }
04185     return d;
04186   }
04187 
04188   template<class VIC>
04189   forceinline ModEvent
04190   VarImp<VIC>::modevent(const Delta& d) {
04191     return d.me;
04192   }
04193 
04194   template<class VIC>
04195   forceinline unsigned int
04196   VarImp<VIC>::bits(void) const {
04197     return free_and_bits;
04198   }
04199 
04200   template<class VIC>
04201   forceinline unsigned int&
04202   VarImp<VIC>::bits(void) {
04203     return free_and_bits;
04204   }
04205 
04206 #ifdef GECODE_HAS_VAR_DISPOSE
04207   template<class VIC>
04208   forceinline VarImp<VIC>*
04209   VarImp<VIC>::vars_d(Space& home) {
04210     return static_cast<VarImp<VIC>*>(home.vars_d<VIC>());
04211   }
04212 
04213   template<class VIC>
04214   forceinline void
04215   VarImp<VIC>::vars_d(Space& home, VarImp<VIC>* x) {
04216     home.vars_d<VIC>(x);
04217   }
04218 #endif
04219 
04220   template<class VIC>
04221   forceinline bool
04222   VarImp<VIC>::copied(void) const {
04223     return Support::marked(b.fwd);
04224   }
04225 
04226   template<class VIC>
04227   forceinline VarImp<VIC>*
04228   VarImp<VIC>::forward(void) const {
04229     assert(copied());
04230     return static_cast<VarImp<VIC>*>(Support::unmark(b.fwd));
04231   }
04232 
04233   template<class VIC>
04234   forceinline VarImp<VIC>*
04235   VarImp<VIC>::next(void) const {
04236     assert(copied());
04237     return u.next;
04238   }
04239 
04240   template<class VIC>
04241   forceinline
04242   VarImp<VIC>::VarImp(Space& home, VarImp<VIC>& x)
04243 #ifdef GECODE_HAS_CBS
04244   : var_id(x.var_id)
04245 #endif
04246   {
04247     VarImpBase** reg;
04248     free_and_bits = x.free_and_bits & ((1 << free_bits) - 1);
04249     if (x.b.base == NULL) {
04250       // Variable implementation needs no index structure
04251       reg = &home.pc.c.vars_noidx;
04252       assert(x.degree() == 0);
04253     } else {
04254       reg = &home.pc.c.vars_u[idx_c];
04255     }
04256     // Save subscriptions in copy
04257     b.base = x.b.base;
04258     entries = x.entries;
04259     for (PropCond pc=1; pc<pc_max+2; pc++)
04260       idx(pc) = x.idx(pc);
04261 
04262     // Set forwarding pointer
04263     x.b.fwd = static_cast<VarImp<VIC>*>(Support::mark(this));
04264     // Register original
04265     x.u.next = static_cast<VarImp<VIC>*>(*reg); *reg = &x;
04266   }
04267 
04268   template<class VIC>
04269   forceinline ModEvent
04270   VarImp<VIC>::me(const ModEventDelta& med) {
04271     return static_cast<ModEvent>((med & VIC::med_mask) >> VIC::med_fst);
04272   }
04273 
04274   template<class VIC>
04275   forceinline ModEventDelta
04276   VarImp<VIC>::med(ModEvent me) {
04277     return static_cast<ModEventDelta>(me << VIC::med_fst);
04278   }
04279 
04280   template<class VIC>
04281   forceinline ModEvent
04282   VarImp<VIC>::me_combine(ModEvent me1, ModEvent me2) {
04283     return VIC::me_combine(me1,me2);
04284   }
04285 
04286   template<class VIC>
04287   forceinline void
04288   VarImp<VIC>::schedule(Space& home, Propagator& p, ModEvent me,
04289                         bool force) {
04290     if (VIC::med_update(p.u.med,me) || force)
04291       home.enqueue(&p);
04292   }
04293 
04294   template<class VIC>
04295   forceinline void
04296   VarImp<VIC>::schedule(Space& home, PropCond pc1, PropCond pc2, ModEvent me) {
04297     ActorLink** b = actor(pc1);
04298     ActorLink** p = actorNonZero(pc2+1);
04299     while (p-- > b)
04300       schedule(home,*Propagator::cast(*p),me);
04301   }
04302 
04303   template<class VIC>
04304   forceinline void
04305   VarImp<VIC>::resize(Space& home) {
04306     if (b.base == NULL) {
04307       assert((free_and_bits >> free_bits) == 0);
04308       // Create fresh dependency array with four entries
04309       free_and_bits += 4 << free_bits;
04310       b.base = home.alloc<ActorLink*>(4);
04311       for (int i=0; i<pc_max+1; i++)
04312         u.idx[i] = 0;
04313     } else {
04314       // Resize dependency array
04315       unsigned int n = degree();
04316       // Find out whether the area is most likely in the special area
04317       // reserved for subscriptions. If yes, just resize mildly otherwise
04318       // more agressively
04319       ActorLink** s = static_cast<ActorLink**>(home.mm.subscriptions());
04320       unsigned int m =
04321         ((s <= b.base) && (b.base < s+home.pc.p.n_sub)) ?
04322         (n+4) : ((n+1)*3>>1);
04323       ActorLink** prop = home.alloc<ActorLink*>(m);
04324       free_and_bits += (m-n) << free_bits;
04325       // Copy entries
04326       Heap::copy<ActorLink*>(prop, b.base, n);
04327       home.free<ActorLink*>(b.base,n);
04328       b.base = prop;
04329     }
04330   }
04331 
04332   template<class VIC>
04333   forceinline void
04334   VarImp<VIC>::enter(Space& home, Propagator* p, PropCond pc) {
04335     assert(pc <= pc_max);
04336     // Count one new subscription
04337     home.pc.p.n_sub += 1;
04338     if ((free_and_bits >> free_bits) == 0)
04339       resize(home);
04340     free_and_bits -= 1 << free_bits;
04341 
04342     // Enter subscription
04343     b.base[entries] = *actorNonZero(pc_max+1);
04344     entries++;
04345     for (PropCond j = pc_max; j > pc; j--) {
04346       *actorNonZero(j+1) = *actorNonZero(j);
04347       idx(j+1)++;
04348     }
04349     *actorNonZero(pc+1) = *actor(pc);
04350     idx(pc+1)++;
04351     *actor(pc) = ActorLink::cast(p);
04352 
04353 #ifdef GECODE_AUDIT
04354     ActorLink** f = actor(pc);
04355     while (f < (pc == pc_max+1 ? b.base+entries : actorNonZero(pc+1)))
04356       if (*f == p)
04357         goto found;
04358       else
04359         f++;
04360     GECODE_NEVER;
04361     found: ;
04362 #endif
04363   }
04364 
04365   template<class VIC>
04366   forceinline void
04367   VarImp<VIC>::enter(Space& home, Advisor* a) {
04368     // Note that a might be a marked pointer
04369     // Count one new subscription
04370     home.pc.p.n_sub += 1;
04371     if ((free_and_bits >> free_bits) == 0)
04372       resize(home);
04373     free_and_bits -= 1 << free_bits;
04374 
04375     // Enter subscription
04376     b.base[entries++] = *actorNonZero(pc_max+1);
04377     *actorNonZero(pc_max+1) = a;
04378   }
04379 
04380   template<class VIC>
04381   forceinline void
04382   VarImp<VIC>::subscribe(Space& home, Propagator& p, PropCond pc,
04383                          bool assigned, ModEvent me, bool schedule) {
04384     if (assigned) {
04385       // Do not subscribe, just schedule the propagator
04386       if (schedule)
04387         VarImp<VIC>::schedule(home,p,ME_GEN_ASSIGNED);
04388     } else {
04389       enter(home,&p,pc);
04390       // Schedule propagator
04391       if (schedule && (pc != PC_GEN_ASSIGNED))
04392         VarImp<VIC>::schedule(home,p,me);
04393     }
04394   }
04395 
04396   template<class VIC>
04397   forceinline void
04398   VarImp<VIC>::subscribe(Space& home, Advisor& a, bool assigned, bool fail) {
04399     if (!assigned) {
04400       Advisor* ma = static_cast<Advisor*>(Support::ptrjoin(&a,fail ? 1 : 0));
04401       enter(home,ma);
04402     }
04403   }
04404 
04405   template<class VIC>
04406   forceinline void
04407   VarImp<VIC>::reschedule(Space& home, Propagator& p, PropCond pc,
04408                           bool assigned, ModEvent me) {
04409     if (assigned)
04410       VarImp<VIC>::schedule(home,p,ME_GEN_ASSIGNED);
04411     else if (pc != PC_GEN_ASSIGNED)
04412       VarImp<VIC>::schedule(home,p,me);
04413   }
04414 
04415   template<class VIC>
04416   void
04417   VarImp<VIC>::remove(Space& home, Propagator* p, PropCond pc) {
04418     assert(pc <= pc_max);
04419     ActorLink* a = ActorLink::cast(p);
04420     // Find actor in dependency array
04421     ActorLink** f = actor(pc);
04422 #ifdef GECODE_AUDIT
04423     while (f < actorNonZero(pc+1))
04424       if (*f == a)
04425         goto found;
04426       else
04427         f++;
04428     GECODE_NEVER;
04429   found: ;
04430 #else
04431     while (*f != a) f++;
04432 #endif
04433     // Remove actor
04434     *f = *(actorNonZero(pc+1)-1);
04435     for (PropCond j = pc+1; j< pc_max+1; j++) {
04436       *(actorNonZero(j)-1) = *(actorNonZero(j+1)-1);
04437       idx(j)--;
04438     }
04439     *(actorNonZero(pc_max+1)-1) = b.base[entries-1];
04440     idx(pc_max+1)--;
04441     entries--;
04442     free_and_bits += 1 << free_bits;
04443     home.pc.p.n_sub -= 1;
04444   }
04445 
04446   template<class VIC>
04447   forceinline void
04448   VarImp<VIC>::cancel(Space& home, Propagator& p, PropCond pc) {
04449     if (b.base != NULL)
04450       remove(home,&p,pc);
04451   }
04452 
04453   template<class VIC>
04454   void
04455   VarImp<VIC>::remove(Space& home, Advisor* a) {
04456     // Note that a might be a marked pointer
04457     // Find actor in dependency array
04458     ActorLink** f = actorNonZero(pc_max+1);
04459 #ifdef GECODE_AUDIT
04460     while (f < b.base+entries)
04461       if (*f == a)
04462         goto found;
04463       else
04464         f++;
04465     GECODE_NEVER;
04466   found: ;
04467 #else
04468     while (*f != a) f++;
04469 #endif
04470     // Remove actor
04471     *f = b.base[--entries];
04472     free_and_bits += 1 << free_bits;
04473     home.pc.p.n_sub -= 1;
04474   }
04475 
04476   template<class VIC>
04477   forceinline void
04478   VarImp<VIC>::cancel(Space& home, Advisor& a, bool fail) {
04479     if (b.base != NULL) {
04480       Advisor* ma = static_cast<Advisor*>(Support::ptrjoin(&a,fail ? 1 : 0));
04481       remove(home,ma);
04482     }
04483   }
04484 
04485   template<class VIC>
04486   forceinline void
04487   VarImp<VIC>::cancel(Space& home) {
04488     unsigned int n_sub = degree();
04489     home.pc.p.n_sub -= n_sub;
04490     unsigned int n = (free_and_bits >> free_bits) + n_sub;
04491     home.free<ActorLink*>(b.base,n);
04492     // Must be NULL such that cloning works
04493     b.base = NULL;
04494     // Must be 0 such that degree works
04495     entries = 0;
04496     // Must be NULL such that afc works
04497     for (PropCond pc=1; pc<pc_max+2; pc++)
04498       idx(pc) = 0;
04499     free_and_bits &= (1 << free_bits) - 1;
04500   }
04501 
04502   template<class VIC>
04503   forceinline bool
04504   VarImp<VIC>::advise(Space& home, ModEvent me, Delta& d) {
04505     /*
04506      * An advisor that is executed might remove itself due to subsumption.
04507      * As entries are removed from front to back, the advisors must
04508      * be iterated in forward direction.
04509      */
04510     ActorLink** la = actorNonZero(pc_max+1);
04511     ActorLink** le = b.base+entries;
04512     if (la == le)
04513       return true;
04514     d.me = me;
04515     // An advisor that is run, might be removed during execution.
04516     // As removal is done from the back the advisors have to be executed
04517     // in inverse order.
04518     do {
04519       Advisor* a = Advisor::cast
04520         (static_cast<ActorLink*>(Support::funmark(*la)));
04521       assert(!a->disposed());
04522       Propagator& p = a->propagator();
04523       switch (p.advise(home,*a,d)) {
04524       case ES_FIX:
04525         break;
04526       case ES_FAILED:
04527         return false;
04528       case ES_NOFIX:
04529         schedule(home,p,me);
04530         break;
04531       case ES_NOFIX_FORCE:
04532         schedule(home,p,me,true);
04533         break;
04534       case __ES_SUBSUMED:
04535       default:
04536         GECODE_NEVER;
04537       }
04538     } while (++la < le);
04539     return true;
04540   }
04541 
04542   template<class VIC>
04543   void
04544   VarImp<VIC>::_fail(Space& home) {
04545     /*
04546      * An advisor that is executed might remove itself due to subsumption.
04547      * As entries are removed from front to back, the advisors must
04548      * be iterated in forward direction.
04549      */
04550     ActorLink** la = actorNonZero(pc_max+1);
04551     ActorLink** le = b.base+entries;
04552     if (la == le)
04553       return;
04554     // An advisor that is run, might be removed during execution.
04555     // As removal is done from the back the advisors have to be executed
04556     // in inverse order.
04557     do {
04558       if (Support::marked(*la)) {
04559         Advisor* a = Advisor::cast(static_cast<ActorLink*>
04560                                    (Support::unmark(*la)));
04561         assert(!a->disposed());
04562         Propagator& p = a->propagator();
04563         p.advise(home,*a);
04564       }
04565     } while (++la < le);
04566   }
04567 
04568   template<class VIC>
04569   ModEvent
04570   VarImp<VIC>::fail(Space& home) {
04571     _fail(home); 
04572     return ME_GEN_FAILED;
04573   }
04574 
04575   template<class VIC>
04576   forceinline void
04577   VarImp<VIC>::update(VarImp<VIC>* x, ActorLink**& sub) {
04578     // this refers to the variable to be updated (clone)
04579     // x refers to the original
04580     // Recover from copy
04581     x->b.base = b.base;
04582     x->u.idx[0] = u.idx[0];
04583     if (pc_max > 0 && sizeof(ActorLink**) > sizeof(unsigned int))
04584       x->u.idx[1] = u.idx[1];
04585 
04586     unsigned int np =
04587       static_cast<unsigned int>(x->actorNonZero(pc_max+1) - x->actor(0));
04588     unsigned int na = 
04589       static_cast<unsigned int >(x->b.base + x->entries - 
04590                                  x->actorNonZero(pc_max+1));
04591     unsigned int n  = na + np;
04592     assert(n == x->degree());
04593 
04594     ActorLink** f = x->b.base;
04595     ActorLink** t = sub;
04596 
04597     sub += n;
04598     b.base = t;
04599     // Process propagator subscriptions
04600     while (np >= 4) {
04601       ActorLink* p3 = f[3]->prev();
04602       ActorLink* p0 = f[0]->prev();
04603       ActorLink* p1 = f[1]->prev();
04604       ActorLink* p2 = f[2]->prev(); 
04605       t[0] = p0; t[1] = p1; t[2] = p2; t[3] = p3;
04606       np -= 4; t += 4; f += 4;
04607     }
04608     if (np >= 2) {
04609       ActorLink* p0 = f[0]->prev();
04610       ActorLink* p1 = f[1]->prev();
04611       t[0] = p0; t[1] = p1;
04612       np -= 2; t += 2; f += 2;
04613     }
04614     if (np > 0) {
04615       ActorLink* p0 = f[0]->prev();
04616       t[0] = p0;
04617       t += 1; f += 1;
04618     }
04619     // Process advisor subscriptions
04620     while (na >= 4) {
04621       ptrdiff_t m0, m1, m2, m3;
04622       ActorLink* p3 =
04623         static_cast<ActorLink*>(Support::ptrsplit(f[3],m3))->prev();
04624       ActorLink* p0 = 
04625         static_cast<ActorLink*>(Support::ptrsplit(f[0],m0))->prev();
04626       ActorLink* p1 =
04627         static_cast<ActorLink*>(Support::ptrsplit(f[1],m1))->prev();
04628       ActorLink* p2 =
04629         static_cast<ActorLink*>(Support::ptrsplit(f[2],m2))->prev();
04630       t[0] = static_cast<ActorLink*>(Support::ptrjoin(p0,m0));
04631       t[1] = static_cast<ActorLink*>(Support::ptrjoin(p1,m1));
04632       t[2] = static_cast<ActorLink*>(Support::ptrjoin(p2,m2));
04633       t[3] = static_cast<ActorLink*>(Support::ptrjoin(p3,m3));
04634       na -= 4; t += 4; f += 4;
04635     }
04636     if (na >= 2) {
04637       ptrdiff_t m0, m1;
04638       ActorLink* p0 = 
04639         static_cast<ActorLink*>(Support::ptrsplit(f[0],m0))->prev();
04640       ActorLink* p1 =
04641         static_cast<ActorLink*>(Support::ptrsplit(f[1],m1))->prev();
04642       t[0] = static_cast<ActorLink*>(Support::ptrjoin(p0,m0));
04643       t[1] = static_cast<ActorLink*>(Support::ptrjoin(p1,m1));
04644       na -= 2; t += 2; f += 2;
04645     }
04646     if (na > 0) {
04647       ptrdiff_t m0;
04648       ActorLink* p0 = 
04649         static_cast<ActorLink*>(Support::ptrsplit(f[0],m0))->prev();
04650       t[0] = static_cast<ActorLink*>(Support::ptrjoin(p0,m0));
04651     }
04652   }
04653 
04654   template<class VIC>
04655   forceinline void
04656   VarImp<VIC>::update(Space& home, ActorLink**& sub) {
04657     VarImp<VIC>* x = static_cast<VarImp<VIC>*>(home.pc.c.vars_u[idx_c]);
04658     while (x != NULL) {
04659       VarImp<VIC>* n = x->next(); x->forward()->update(x,sub); x = n;
04660     }
04661   }
04662 
04663 
04664 
04665   /*
04666    * Variable disposer
04667    *
04668    */
04669   template<class VarImp>
04670   VarImpDisposer<VarImp>::VarImpDisposer(void) {
04671 #ifdef GECODE_HAS_VAR_DISPOSE
04672     Space::vd[VarImp::idx_d] = this;
04673 #endif
04674   }
04675 
04676   template<class VarImp>
04677   void
04678   VarImpDisposer<VarImp>::dispose(Space& home, VarImpBase* _x) {
04679     VarImp* x = static_cast<VarImp*>(_x);
04680     do {
04681       x->dispose(home); x = static_cast<VarImp*>(x->next_d());
04682     } while (x != NULL);
04683   }
04684 
04685   /*
04686    * Statistics
04687    */
04688 
04689   forceinline void
04690   StatusStatistics::reset(void) {
04691     propagate = 0;
04692   }
04693   forceinline
04694   StatusStatistics::StatusStatistics(void) {
04695     reset();
04696   }
04697   forceinline StatusStatistics&
04698   StatusStatistics::operator +=(const StatusStatistics& s) {
04699     propagate += s.propagate;
04700     return *this;
04701   }
04702   forceinline StatusStatistics
04703   StatusStatistics::operator +(const StatusStatistics& s) {
04704     StatusStatistics t(s);
04705     return t += *this;
04706   }
04707 
04708   forceinline void
04709   CloneStatistics::reset(void) {}
04710 
04711   forceinline
04712   CloneStatistics::CloneStatistics(void) {
04713     reset();
04714   }
04715   forceinline CloneStatistics
04716   CloneStatistics::operator +(const CloneStatistics&) {
04717     CloneStatistics s;
04718     return s;
04719   }
04720   forceinline CloneStatistics&
04721   CloneStatistics::operator +=(const CloneStatistics&) {
04722     return *this;
04723   }
04724 
04725   forceinline void
04726   CommitStatistics::reset(void) {}
04727 
04728   forceinline
04729   CommitStatistics::CommitStatistics(void) {
04730     reset();
04731   }
04732   forceinline CommitStatistics
04733   CommitStatistics::operator +(const CommitStatistics&) {
04734     CommitStatistics s;
04735     return s;
04736   }
04737   forceinline CommitStatistics&
04738   CommitStatistics::operator +=(const CommitStatistics&) {
04739     return *this;
04740   }
04741 
04742   /*
04743    * Cost computation
04744    *
04745    */
04746 
04747   forceinline
04748   PropCost::PropCost(PropCost::ActualCost ac0) : ac(ac0) {}
04749 
04750   forceinline PropCost
04751   PropCost::cost(PropCost::Mod m,
04752                  PropCost::ActualCost lo, PropCost::ActualCost hi,
04753                  unsigned int n) {
04754     if (n < 2)
04755       return (m == LO) ? AC_UNARY_LO : AC_UNARY_HI;
04756     else if (n == 2)
04757       return (m == LO) ? AC_BINARY_LO : AC_BINARY_HI;
04758     else if (n == 3)
04759       return (m == LO) ? AC_TERNARY_LO : AC_TERNARY_HI;
04760     else
04761       return (m == LO) ? lo : hi;
04762   }
04763 
04764   forceinline PropCost
04765   PropCost::record(void) {
04766     return AC_RECORD;
04767   }
04768   forceinline PropCost
04769   PropCost::crazy(PropCost::Mod m, unsigned int n) {
04770     return cost(m,AC_CRAZY_LO,AC_CRAZY_HI,n);
04771   }
04772   forceinline PropCost
04773   PropCost::crazy(PropCost::Mod m, int n) {
04774     assert(n >= 0);
04775     return crazy(m,static_cast<unsigned int>(n));
04776   }
04777   forceinline PropCost
04778   PropCost::cubic(PropCost::Mod m, unsigned int n) {
04779     return cost(m,AC_CUBIC_LO,AC_CUBIC_HI,n);
04780   }
04781   forceinline PropCost
04782   PropCost::cubic(PropCost::Mod m, int n) {
04783     assert(n >= 0);
04784     return cubic(m,static_cast<unsigned int>(n));
04785   }
04786   forceinline PropCost
04787   PropCost::quadratic(PropCost::Mod m, unsigned int n) {
04788     return cost(m,AC_QUADRATIC_LO,AC_QUADRATIC_HI,n);
04789   }
04790   forceinline PropCost
04791   PropCost::quadratic(PropCost::Mod m, int n) {
04792     assert(n >= 0);
04793     return quadratic(m,static_cast<unsigned int>(n));
04794   }
04795   forceinline PropCost
04796   PropCost::linear(PropCost::Mod m, unsigned int n) {
04797     return cost(m,AC_LINEAR_LO,AC_LINEAR_HI,n);
04798   }
04799   forceinline PropCost
04800   PropCost::linear(PropCost::Mod m, int n) {
04801     assert(n >= 0);
04802     return linear(m,static_cast<unsigned int>(n));
04803   }
04804   forceinline PropCost
04805   PropCost::ternary(PropCost::Mod m) {
04806     return (m == LO) ? AC_TERNARY_LO : AC_TERNARY_HI;
04807   }
04808   forceinline PropCost
04809   PropCost::binary(PropCost::Mod m) {
04810     return (m == LO) ? AC_BINARY_LO : AC_BINARY_HI;
04811   }
04812   forceinline PropCost
04813   PropCost::unary(PropCost::Mod m) {
04814     return (m == LO) ? AC_UNARY_LO : AC_UNARY_HI;
04815   }
04816 
04817   /*
04818    * Iterators for propagators and branchers of a space
04819    *
04820    */
04821   forceinline
04822   Space::Propagators::Propagators(Space& home0)
04823     : home(home0), q(home.pc.p.active) {
04824     while (q >= &home.pc.p.queue[0]) {
04825       if (q->next() != q) {
04826         c = q->next(); e = q; q--;
04827         return;
04828       }
04829       q--;
04830     }
04831     q = NULL;
04832     if (!home.pl.empty()) {
04833       c = Propagator::cast(home.pl.next());
04834       e = Propagator::cast(&home.pl);
04835     } else {
04836       c = e = NULL;
04837     }
04838   }
04839   forceinline bool
04840   Space::Propagators::operator ()(void) const {
04841     return c != NULL;
04842   }
04843   forceinline void
04844   Space::Propagators::operator ++(void) {
04845     c = c->next();
04846     if (c == e) {
04847       if (q == NULL) {
04848         c = NULL;
04849       } else {
04850         while (q >= &home.pc.p.queue[0]) {
04851           if (q->next() != q) {
04852             c = q->next(); e = q; q--;
04853             return;
04854           }
04855           q--;
04856         }
04857         q = NULL;
04858         if (!home.pl.empty()) {
04859           c = Propagator::cast(home.pl.next());
04860           e = Propagator::cast(&home.pl);
04861         } else {
04862           c = NULL;
04863         }
04864       }
04865     }
04866   }
04867   forceinline Propagator&
04868   Space::Propagators::propagator(void) const {
04869     return *Propagator::cast(c);
04870   }
04871 
04872 
04873   forceinline
04874   Space::ScheduledPropagators::ScheduledPropagators(Space& home0)
04875     : home(home0), q(home.pc.p.active) {
04876     while (q >= &home.pc.p.queue[0]) {
04877       if (q->next() != q) {
04878         c = q->next(); e = q; q--;
04879         return;
04880       }
04881       q--;
04882     }
04883     q = c = e = NULL;
04884   }
04885   forceinline bool
04886   Space::ScheduledPropagators::operator ()(void) const {
04887     return c != NULL;
04888   }
04889   forceinline void
04890   Space::ScheduledPropagators::operator ++(void) {
04891     c = c->next();
04892     if (c == e) {
04893       if (q == NULL) {
04894         c = NULL;
04895       } else {
04896         while (q >= &home.pc.p.queue[0]) {
04897           if (q->next() != q) {
04898             c = q->next(); e = q; q--;
04899             return;
04900           }
04901           q--;
04902         }
04903         q = c = e = NULL;
04904       }
04905     }
04906   }
04907   forceinline Propagator&
04908   Space::ScheduledPropagators::propagator(void) const {
04909     return *Propagator::cast(c);
04910   }
04911 
04912 
04913   forceinline
04914   Space::IdlePropagators::IdlePropagators(Space& home) {
04915     c = Propagator::cast(home.pl.next());
04916     e = Propagator::cast(&home.pl);
04917   }
04918   forceinline bool
04919   Space::IdlePropagators::operator ()(void) const {
04920     return c != e;
04921   }
04922   forceinline void
04923   Space::IdlePropagators::operator ++(void) {
04924     c = c->next();
04925   }
04926   forceinline Propagator&
04927   Space::IdlePropagators::propagator(void) const {
04928     return *Propagator::cast(c);
04929   }
04930 
04931 
04932   forceinline
04933   Space::Branchers::Branchers(Space& home)
04934     : c(Brancher::cast(home.bl.next())), e(&home.bl) {}
04935   forceinline bool
04936   Space::Branchers::operator ()(void) const {
04937     return c != e;
04938   }
04939   forceinline void
04940   Space::Branchers::operator ++(void) {
04941     c = c->next();
04942   }
04943   forceinline Brancher&
04944   Space::Branchers::brancher(void) const {
04945     return *Brancher::cast(c);
04946   }
04947 
04948 
04949   /*
04950    * Groups of actors
04951    */
04952   forceinline
04953   Group::Group(unsigned int gid0) : gid(gid0) {}
04954 
04955   forceinline bool
04956   Group::in(Group actor) const {
04957     return (gid == GROUPID_ALL) || (gid == actor.gid);
04958   }
04959 
04960   forceinline bool
04961   Group::in(void) const {
04962     return (gid != GROUPID_ALL) && (gid != GROUPID_DEF);
04963   }
04964 
04965   forceinline
04966   Group::Group(const Group& g) : gid(g.gid) {}
04967 
04968   forceinline Group&
04969   Group::operator =(const Group& g) {
04970     gid=g.gid; return *this;
04971   }
04972 
04973   forceinline unsigned int
04974   Group::id(void) const {
04975     return gid;
04976   }
04977 
04978 
04979   forceinline
04980   PropagatorGroup::PropagatorGroup(void) {}
04981 
04982   forceinline
04983   PropagatorGroup::PropagatorGroup(unsigned int gid)
04984     : Group(gid) {}
04985 
04986   forceinline
04987   PropagatorGroup::PropagatorGroup(const PropagatorGroup& g)
04988     : Group(g) {}
04989 
04990   forceinline PropagatorGroup&
04991   PropagatorGroup::operator =(const PropagatorGroup& g) {
04992     return static_cast<PropagatorGroup&>(Group::operator =(g));
04993   }
04994 
04995   forceinline Home
04996   PropagatorGroup::operator ()(Space& home) {
04997     return Home(home,NULL,*this,BrancherGroup::def);
04998   }
04999 
05000   forceinline bool
05001   PropagatorGroup::operator ==(PropagatorGroup g) const {
05002     return id() == g.id();
05003   }
05004   forceinline bool
05005   PropagatorGroup::operator !=(PropagatorGroup g) const {
05006     return id() != g.id();
05007   }
05008 
05009   forceinline PropagatorGroup&
05010   PropagatorGroup::move(Space& , Propagator& p) {
05011     if (id() != GROUPID_ALL)
05012       p.group(*this);
05013     return *this;
05014   }
05015 
05016 
05017   forceinline
05018   BrancherGroup::BrancherGroup(void) {}
05019 
05020   forceinline
05021   BrancherGroup::BrancherGroup(unsigned int gid)
05022     : Group(gid) {}
05023 
05024   forceinline
05025   BrancherGroup::BrancherGroup(const BrancherGroup& g)
05026     : Group(g) {}
05027 
05028   forceinline BrancherGroup&
05029   BrancherGroup::operator =(const BrancherGroup& g) {
05030     return static_cast<BrancherGroup&>(Group::operator =(g));
05031   }
05032 
05033   forceinline Home
05034   BrancherGroup::operator ()(Space& home) {
05035     return Home(home,NULL,PropagatorGroup::def,*this);
05036   }
05037 
05038   forceinline bool
05039   BrancherGroup::operator ==(BrancherGroup g) const {
05040     return id() == g.id();
05041   }
05042   forceinline bool
05043   BrancherGroup::operator !=(BrancherGroup g) const {
05044     return id() != g.id();
05045   }
05046 
05047   forceinline BrancherGroup&
05048   BrancherGroup::move(Space& , Brancher& p) {
05049     if (id() != GROUPID_ALL)
05050       p.group(*this);
05051     return *this;
05052   }
05053 
05054 
05055   /*
05056    * Iterators for propagators and branchers in a group
05057    *
05058    */
05059   forceinline
05060   Propagators::Propagators(const Space& home, PropagatorGroup g0)
05061     : ps(const_cast<Space&>(home)), g(g0) {
05062     while (ps() && !g.in(ps.propagator().group()))
05063       ++ps;
05064   }
05065   forceinline bool
05066   Propagators::operator ()(void) const {
05067     return ps();
05068   }
05069   forceinline void
05070   Propagators::operator ++(void) {
05071     do
05072       ++ps;
05073     while (ps() && !g.in(ps.propagator().group()));
05074   }
05075   forceinline const Propagator&
05076   Propagators::propagator(void) const {
05077     return ps.propagator();
05078   }
05079 
05080   forceinline
05081   Branchers::Branchers(const Space& home, BrancherGroup g0)
05082     : bs(const_cast<Space&>(home)), g(g0) {
05083     while (bs() && !g.in(bs.brancher().group()))
05084       ++bs;
05085   }
05086   forceinline bool
05087   Branchers::operator ()(void) const {
05088     return bs();
05089   }
05090   forceinline void
05091   Branchers::operator ++(void) {
05092     do
05093       ++bs;
05094     while (bs() && !g.in(bs.brancher().group()));
05095   }
05096   forceinline const Brancher&
05097   Branchers::brancher(void) const {
05098     return bs.brancher();
05099   }
05100 
05101 
05102   /*
05103    * Space construction support
05104    *
05105    */
05106   template<class T>
05107   forceinline T&
05108   Space::construct(void) {
05109     return alloc<T>(1);
05110   }
05111   template<class T, typename A1>
05112   forceinline T&
05113   Space::construct(A1 const& a1) {
05114     T& t = *static_cast<T*>(ralloc(sizeof(T)));
05115     new (&t) T(a1);
05116     return t;
05117   }
05118   template<class T, typename A1, typename A2>
05119   forceinline T&
05120   Space::construct(A1 const& a1, A2 const& a2) {
05121     T& t = *static_cast<T*>(ralloc(sizeof(T)));
05122     new (&t) T(a1,a2);
05123     return t;
05124   }
05125   template<class T, typename A1, typename A2, typename A3>
05126   forceinline T&
05127   Space::construct(A1 const& a1, A2 const& a2, A3 const& a3) {
05128     T& t = *static_cast<T*>(ralloc(sizeof(T)));
05129     new (&t) T(a1,a2,a3);
05130     return t;
05131   }
05132   template<class T, typename A1, typename A2, typename A3, typename A4>
05133   forceinline T&
05134   Space::construct(A1 const& a1, A2 const& a2, A3 const& a3, A4 const& a4) {
05135     T& t = *static_cast<T*>(ralloc(sizeof(T)));
05136     new (&t) T(a1,a2,a3,a4);
05137     return t;
05138   }
05139   template<class T, typename A1, typename A2, typename A3, typename A4, typename A5>
05140   forceinline T&
05141   Space::construct(A1 const& a1, A2 const& a2, A3 const& a3, A4 const& a4, A5 const& a5) {
05142     T& t = *static_cast<T*>(ralloc(sizeof(T)));
05143     new (&t) T(a1,a2,a3,a4,a5);
05144     return t;
05145   }
05146 
05147 }
05148 
05149 // STATISTICS: kernel-core