core.hpp

Go to the documentation of this file.

/* -*- mode: C++; c-basic-offset: 2; indent-tabs-mode: nil -*- */
/*
 *  Main authors:
 *     Christian Schulte <schulte@gecode.org>
 *     Guido Tack <tack@gecode.org>
 *     Mikael Lagerkvist <lagerkvist@gecode.org>
 *
 *  Contributing authors:
 *     Filip Konvicka <filip.konvicka@logis.cz>
 *
 *  Copyright:
 *     Christian Schulte, 2002
 *     Guido Tack, 2003
 *     Mikael Lagerkvist, 2006
 *     LOGIS, s.r.o., 2009
 *
 *  Bugfixes provided by:
 *     Alexander Samoilov <alexander_samoilov@yahoo.com>
 *
 *  Last modified:
 *     $Date: 2017-03-17 23:04:57 +0100 (Fri, 17 Mar 2017) $ by $Author: schulte $
 *     $Revision: 15597 $
 *
 *  This file is part of Gecode, the generic constraint
 *  development environment:
 *     http://www.gecode.org
 *
 *  Permission is hereby granted, free of charge, to any person obtaining
 *  a copy of this software and associated documentation files (the
 *  "Software"), to deal in the Software without restriction, including
 *  without limitation the rights to use, copy, modify, merge, publish,
 *  distribute, sublicense, and/or sell copies of the Software, and to
 *  permit persons to whom the Software is furnished to do so, subject to
 *  the following conditions:
 *
 *  The above copyright notice and this permission notice shall be
 *  included in all copies or substantial portions of the Software.
 *
 *  THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,
 *  EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF
 *  MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND
 *  NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE
 *  LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION
 *  OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION
 *  WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
 *
 */

#include <iostream>

namespace Gecode {

  class Space;

  class SharedHandle {
  public:
    class Object : public HeapAllocated {
      friend class Space;
      friend class SharedHandle;
    private:
      Object* next;
      Object* fwd;
      unsigned int use_cnt;
    public:
      Object(void);
      virtual Object* copy(void) const = 0;
      virtual ~Object(void);
    };
  private:
    Object* o;
    void subscribe(void);
    void cancel(void);
  public:
    SharedHandle(void);
    SharedHandle(SharedHandle::Object* so);
    SharedHandle(const SharedHandle& sh);
    SharedHandle& operator =(const SharedHandle& sh);
    void update(Space& home, bool share, SharedHandle& sh);
    ~SharedHandle(void);
  protected:
    SharedHandle::Object* object(void) const;
    void object(SharedHandle::Object* n);
  };


  typedef int ModEvent;

  const ModEvent ME_GEN_FAILED   = -1;
  const ModEvent ME_GEN_NONE     =  0;
  const ModEvent ME_GEN_ASSIGNED =  1;

  typedef int PropCond;
  const PropCond PC_GEN_NONE     = -1;
  const PropCond PC_GEN_ASSIGNED = 0;

  typedef int ModEventDelta;

}

#include <gecode/kernel/var-type.hpp>

namespace Gecode {

  class NoIdxVarImpConf {
  public:
    static const int idx_c = -1;
    static const int idx_d = -1;
    static const PropCond pc_max = PC_GEN_ASSIGNED;
    static const int free_bits = 0;
    static const int med_fst = 0;
    static const int med_lst = 0;
    static const int med_mask = 0;
    static Gecode::ModEvent me_combine(ModEvent me1, ModEvent me2);
    static bool med_update(ModEventDelta& med, ModEvent me);
  };

  forceinline ModEvent
  NoIdxVarImpConf::me_combine(ModEvent, ModEvent) {
    GECODE_NEVER; return 0;
  }
  forceinline bool
  NoIdxVarImpConf::med_update(ModEventDelta&, ModEvent) {
    GECODE_NEVER; return false;
  }


  /*
   * These are the classes of interest
   *
   */
  class ActorLink;
  class Actor;
  class Propagator;
  class SubscribedPropagators;
  class LocalObject;
  class Advisor;
  class AFC;
  class Choice;
  class Brancher;
  class Group;
  class PropagatorGroup;
  class BrancherGroup;
  class PostInfo;
  class ViewTraceInfo;
  class PropagateTraceInfo;
  class CommitTraceInfo;
  class TraceRecorder;

  template<class A> class Council;
  template<class A> class Advisors;
  template<class VIC> class VarImp;


  /*
   * Variable implementations
   *
   */

  class VarImpBase {};

  class GECODE_VTABLE_EXPORT VarImpDisposerBase {
  public:
    GECODE_KERNEL_EXPORT virtual void dispose(Space& home, VarImpBase* x);
    GECODE_KERNEL_EXPORT virtual ~VarImpDisposerBase(void);
  };

  template<class VarImp>
  class VarImpDisposer : public VarImpDisposerBase {
  public:
    VarImpDisposer(void);
    virtual void dispose(Space& home, VarImpBase* x);
  };

  class Delta {
    template<class VIC> friend class VarImp;
  private:
    ModEvent me;
  };

  template<class VIC>
  class VarImp : public VarImpBase {
    friend class Space;
    friend class Propagator;
    template<class VarImp> friend class VarImpDisposer;
    friend class SubscribedPropagators;
  private:
    union {
      ActorLink** base;
      VarImp<VIC>* fwd;
    } b;

    static const int idx_c = VIC::idx_c;
    static const int idx_d = VIC::idx_d;
    static const int free_bits = VIC::free_bits;
    unsigned int entries;
    unsigned int free_and_bits;
    static const Gecode::PropCond pc_max = VIC::pc_max;

    union {
      unsigned int idx[pc_max+1];
      VarImp<VIC>* next;
    } u;

    ActorLink** actor(PropCond pc);
    ActorLink** actorNonZero(PropCond pc);
    unsigned int& idx(PropCond pc);
    unsigned int idx(PropCond pc) const;

    void update(VarImp* x, ActorLink**& sub);
    static void update(Space& home, ActorLink**& sub);

    void enter(Space& home, Propagator* p, PropCond pc);
    void enter(Space& home, Advisor* a);
    void resize(Space& home);
    void remove(Space& home, Propagator* p, PropCond pc);
    void remove(Space& home, Advisor* a);


  protected:
    void cancel(Space& home);
    bool advise(Space& home, ModEvent me, Delta& d);
  private:
    void _fail(Space& home);
  protected:
    ModEvent fail(Space& home);
#ifdef GECODE_HAS_VAR_DISPOSE

    static VarImp<VIC>* vars_d(Space& home);
    static void vars_d(Space& home, VarImp<VIC>* x);
#endif

  public:
    VarImp(Space& home);
    VarImp(void);



    void subscribe(Space& home, Propagator& p, PropCond pc,
                   bool assigned, ModEvent me, bool schedule);
    void cancel(Space& home, Propagator& p, PropCond pc);
    void subscribe(Space& home, Advisor& a, bool assigned, bool fail);
    void cancel(Space& home, Advisor& a, bool fail);

    unsigned int degree(void) const;
    double afc(void) const;



    VarImp(Space& home, bool share, VarImp& x);
    bool copied(void) const;
    VarImp* forward(void) const;
    VarImp* next(void) const;



    static void schedule(Space& home, Propagator& p, ModEvent me,
                         bool force = false);
    static void reschedule(Space& home, Propagator& p, PropCond pc,
                           bool assigned, ModEvent me);
    static ModEvent me(const ModEventDelta& med);
    static ModEventDelta med(ModEvent me);
    static ModEvent me_combine(ModEvent me1, ModEvent me2);



    static ModEvent modevent(const Delta& d);



    unsigned int bits(void) const;
    unsigned int& bits(void);

  protected:
    void schedule(Space& home, PropCond pc1, PropCond pc2, ModEvent me);

  public:


    static void* operator new(size_t,Space&);
    static void  operator delete(void*,Space&);
    static void  operator delete(void*);
  };


  enum ExecStatus {
    __ES_SUBSUMED       = -2, 
    ES_FAILED           = -1, 
    ES_NOFIX            =  0, 
    ES_OK               =  0, 
    ES_FIX              =  1, 
    ES_NOFIX_FORCE      =  2, 
    __ES_PARTIAL        =  2  
  };

  class PropCost {
    friend class Space;
  public:
    enum ActualCost {
      AC_RECORD       = 0, 
      AC_CRAZY_LO     = 1, 
      AC_CRAZY_HI     = 1, 
      AC_CUBIC_LO     = 1, 
      AC_CUBIC_HI     = 1, 
      AC_QUADRATIC_LO = 2, 
      AC_QUADRATIC_HI = 2, 
      AC_LINEAR_HI    = 3, 
      AC_LINEAR_LO    = 4, 
      AC_TERNARY_HI   = 4, 
      AC_BINARY_HI    = 5, 
      AC_TERNARY_LO   = 5, 
      AC_BINARY_LO    = 6, 
      AC_UNARY_LO     = 6, 
      AC_UNARY_HI     = 6, 
      AC_MAX          = 6  
    };
    ActualCost ac;
  public:
    enum Mod {
      LO, 
      HI  
    };
  private:
    static PropCost cost(Mod m, ActualCost lo, ActualCost hi, unsigned int n);
    PropCost(ActualCost ac);
  public:
    static PropCost record(void);
    static PropCost crazy(PropCost::Mod m, unsigned int n);
    static PropCost crazy(PropCost::Mod m, int n);
    static PropCost cubic(PropCost::Mod m, unsigned int n);
    static PropCost cubic(PropCost::Mod m, int n);
    static PropCost quadratic(PropCost::Mod m, unsigned int n);
    static PropCost quadratic(PropCost::Mod m, int n);
    static PropCost linear(PropCost::Mod m, unsigned int n);
    static PropCost linear(PropCost::Mod m, int n);
    static PropCost ternary(PropCost::Mod m);
    static PropCost binary(PropCost::Mod m);
    static PropCost unary(PropCost::Mod m);
  };


  enum ActorProperty {
    AP_DISPOSE = (1 << 0),
    AP_WEAKLY = (1 << 1),
    AP_VIEW_TRACE = (1 << 2),
    AP_TRACE = (1 << 3)
  };


  class ActorLink {
    friend class Actor;
    friend class Propagator;
    friend class Advisor;
    friend class Brancher;
    friend class LocalObject;
    friend class Space;
    template<class VIC> friend class VarImp;
  private:
    ActorLink* _next; ActorLink* _prev;
  public:

    ActorLink* prev(void) const; void prev(ActorLink*);
    ActorLink* next(void) const; void next(ActorLink*);
    ActorLink** next_ref(void);

    void init(void);
    void unlink(void);
    void head(ActorLink* al);
    void tail(ActorLink* al);
    bool empty(void) const;
    template<class T> static ActorLink* cast(T* a);
    template<class T> static const ActorLink* cast(const T* a);
  };


  class GECODE_VTABLE_EXPORT Actor : private ActorLink {
    friend class ActorLink;
    friend class Space;
    friend class Propagator;
    friend class Advisor;
    friend class Brancher;
    friend class LocalObject;
    template<class VIC> friend class VarImp;
    template<class A> friend class Council;
  private:
    static Actor* cast(ActorLink* al);
    static const Actor* cast(const ActorLink* al);
    GECODE_KERNEL_EXPORT static Actor* sentinel;
  public:
    virtual Actor* copy(Space& home, bool share) = 0;



    GECODE_KERNEL_EXPORT
    virtual size_t dispose(Space& home);
    static void* operator new(size_t s, Space& home);
    static void  operator delete(void* p, Space& home);
  public:
    GECODE_KERNEL_EXPORT virtual ~Actor(void);
    static void* operator new(size_t s);
    static void  operator delete(void* p);
  };

  class Home;

  class Group {
    friend class Home;
    friend class Propagator;
    friend class Brancher;
    friend class ViewTraceInfo;
    friend class PropagateTraceInfo;
    friend class CommitTraceInfo;
  protected:
    static const unsigned int GROUPID_ALL = 0U;
    static const unsigned int GROUPID_DEF = 1U;
    static const unsigned int GROUPID_MAX = UINT_MAX >> 2;
    unsigned int gid;
    GECODE_KERNEL_EXPORT
    static unsigned int next;
    GECODE_KERNEL_EXPORT
    static Support::Mutex m;
    Group(unsigned int gid0);
  public:


    GECODE_KERNEL_EXPORT
    Group(void);
    Group(const Group& g);
    Group& operator =(const Group& g);
    unsigned int id(void) const;
    bool in(Group a) const;
    bool in(void) const;

    GECODE_KERNEL_EXPORT
    static Group all;
    GECODE_KERNEL_EXPORT
    static Group def;
  };

  class PropagatorGroup : public Group {
    friend class Propagator;
    friend class ViewTraceInfo;
    friend class PropagateTraceInfo;
  protected:
    PropagatorGroup(unsigned int gid);
  public:


    PropagatorGroup(void);
    PropagatorGroup(const PropagatorGroup& g);
    PropagatorGroup& operator =(const PropagatorGroup& g);
    Home operator ()(Space& home);



    GECODE_KERNEL_EXPORT
    PropagatorGroup& move(Space& home, PropagatorGroup g);
    PropagatorGroup& move(Space& home, Propagator& p);
    GECODE_KERNEL_EXPORT
    PropagatorGroup& move(Space& home, unsigned int id);



    bool operator ==(PropagatorGroup g) const;
    bool operator !=(PropagatorGroup g) const;
    GECODE_KERNEL_EXPORT
    unsigned int size(Space& home) const;
    GECODE_KERNEL_EXPORT
    void kill(Space& home);
    GECODE_KERNEL_EXPORT
    void disable(Space& home);
    GECODE_KERNEL_EXPORT
    void enable(Space& home, bool s=true);

    GECODE_KERNEL_EXPORT
    static PropagatorGroup all;
    GECODE_KERNEL_EXPORT
    static PropagatorGroup def;
  };

  class BrancherGroup : public Group {
    friend class Brancher;
  protected:
    BrancherGroup(unsigned int gid);
  public:


    BrancherGroup(void);
    BrancherGroup(const BrancherGroup& g);
    BrancherGroup& operator =(const BrancherGroup& g);
    Home operator ()(Space& home);



    GECODE_KERNEL_EXPORT
    BrancherGroup& move(Space& home, BrancherGroup g);
    BrancherGroup& move(Space& home, Brancher& b);
    GECODE_KERNEL_EXPORT
    BrancherGroup& move(Space& home, unsigned int id);



    bool operator ==(BrancherGroup g) const;
    bool operator !=(BrancherGroup g) const;
    GECODE_KERNEL_EXPORT
    unsigned int size(Space& home) const;
    GECODE_KERNEL_EXPORT
    void kill(Space& home);

    GECODE_KERNEL_EXPORT
    static BrancherGroup all;
    GECODE_KERNEL_EXPORT
    static BrancherGroup def;
  };

  class Home {
    friend class PostInfo;
  protected:
    Space& s;
    Propagator* p;
    PropagatorGroup pg;
    BrancherGroup bg;
  public:


    Home(Space& s, Propagator* p=NULL,
         PropagatorGroup pg=PropagatorGroup::def,
         BrancherGroup bg=BrancherGroup::def);
    Home& operator =(const Home& h);
    operator Space&(void);



    Home operator ()(Propagator& p);
    Home operator ()(PropagatorGroup pg);
    Home operator ()(BrancherGroup bg);
    Propagator* propagator(void) const;
    PropagatorGroup propagatorgroup(void) const;
    BrancherGroup branchergroup(void) const;



    bool failed(void) const;
    void fail(void);
    void notice(Actor& a, ActorProperty p, bool duplicate=false);
  };

  class ViewTraceInfo {
    friend class Space;
    friend class PostInfo;
  public:
    enum What {
      PROPAGATOR = 0,
      BRANCHER   = 1,
      POST       = 2,
      OTHER      = 3
    };
  protected:
    ptrdiff_t who;
    void propagator(Propagator& p);
    void brancher(Brancher& b);
    void post(PropagatorGroup g);
    void other(void);
  public:
    What what(void) const;
    const Propagator& propagator(void) const;
    const Brancher& brancher(void) const;
    PropagatorGroup post(void) const;
  };

  class PostInfo {
  protected:
    Space& h;
  public:
    PostInfo(Home home);
    ~PostInfo(void);
  };

  class PropagateTraceInfo {
    friend class Space;
  public:
    enum Status {
      FIX,     
      NOFIX,   
      FAILED,  
      SUBSUMED 
    };
  protected:
    unsigned int i;
    PropagatorGroup g;
    const Propagator* p;
    Status s;
    PropagateTraceInfo(unsigned int i, PropagatorGroup g,
                       const Propagator* p, Status s);
  public:
    unsigned int id(void) const;
    PropagatorGroup group(void) const;
    const Propagator* propagator(void) const;
    Status status(void) const;
  };

  class CommitTraceInfo {
    friend class Space;
  protected:
    const Brancher& b;
    const Choice& c;
    unsigned int a;
    CommitTraceInfo(const Brancher& b, const Choice& c, unsigned int a);
  public:
    unsigned int id(void) const;
    BrancherGroup group(void) const;
    const Brancher& brancher(void) const;
    const Choice& choice(void) const;
    unsigned int alternative(void) const;
  };
 
  class GECODE_VTABLE_EXPORT Propagator : public Actor {
    friend class ActorLink;
    friend class Space;
    template<class VIC> friend class VarImp;
    friend class Advisor;
    template<class A> friend class Council;
    friend class SubscribedPropagators;
    friend class PropagatorGroup;
  private:
    union {
      ModEventDelta med;
      size_t size;
      Gecode::ActorLink* advisors;
    } u;
    void* gpi_disabled;
    static Propagator* cast(ActorLink* al);
    static const Propagator* cast(const ActorLink* al);
    void disable(Space& home);
    void enable(Space& home);
  protected:
    Propagator(Home home);
    Propagator(Space& home, bool share, Propagator& p);
    Propagator* fwd(void) const;
    GPI::Info& gpi(void);

  public:


    virtual void reschedule(Space& home) = 0;
    virtual ExecStatus propagate(Space& home, const ModEventDelta& med) = 0;
    virtual PropCost cost(const Space& home, const ModEventDelta& med) const = 0;
    ModEventDelta modeventdelta(void) const;
    GECODE_KERNEL_EXPORT
    virtual ExecStatus advise(Space& home, Advisor& a, const Delta& d);
    GECODE_KERNEL_EXPORT
    virtual void advise(Space& home, Advisor& a);



    double afc(void) const;



    unsigned int id(void) const;
    PropagatorGroup group(void) const;
    void group(PropagatorGroup g);
    bool disabled(void) const;
  };


  template<class A>
  class Council {
    friend class Advisor;
    friend class Advisors<A>;
  private:
    mutable ActorLink* advisors;
  public:
    Council(void);
    Council(Space& home);
    bool empty(void) const;
    void update(Space& home, bool share, Council<A>& c);
    void dispose(Space& home);
  };


  template<class A>
  class Advisors {
  private:
    ActorLink* a;
  public:
    Advisors(const Council<A>& c);
    bool operator ()(void) const;
    void operator ++(void);
    A& advisor(void) const;
  };


  class Advisor : private ActorLink {
    template<class VIC> friend class VarImp;
    template<class A> friend class Council;
    template<class A> friend class Advisors;
    friend class SubscribedPropagators;
  private:
    bool disposed(void) const;
    static Advisor* cast(ActorLink* al);
    static const Advisor* cast(const ActorLink* al);
  protected:
    Propagator& propagator(void) const;
  public:
    template<class A>
    Advisor(Space& home, Propagator& p, Council<A>& c);
    Advisor(Space& home, bool share, Advisor& a);
    const ViewTraceInfo& operator ()(const Space& home) const;



    template<class A>
    void dispose(Space& home, Council<A>& c);
    static void* operator new(size_t s, Space& home);
    static void  operator delete(void* p, Space& home);
  private:
#ifndef __GNUC__

    static void  operator delete(void* p);
#endif

    static void* operator new(size_t s);
  };


  class GECODE_VTABLE_EXPORT NGL {
  private:
    void* nl;
  public:
    enum Status {
      FAILED,   
      SUBSUMED, 
      NONE      
    };
    NGL(void);
    NGL(Space& home);
    NGL(Space& home, bool share, NGL& ngl);
    virtual void subscribe(Space& home, Propagator& p) = 0;
    virtual void cancel(Space& home, Propagator& p) = 0;
    virtual void reschedule(Space& home, Propagator& p) = 0;
    virtual NGL::Status status(const Space& home) const = 0;
    virtual ExecStatus prune(Space& home) = 0;
    virtual NGL* copy(Space& home, bool share) = 0;
    GECODE_KERNEL_EXPORT
    virtual bool notice(void) const;
    virtual size_t dispose(Space& home);


    bool leaf(void) const;
    NGL* next(void) const;
    void leaf(bool l);
    void next(NGL* n);
    NGL* add(NGL* n, bool l);



    static void* operator new(size_t s, Space& home);
    static void  operator delete(void* s, Space& home);
    static void  operator delete(void* p);
  public:
    GECODE_KERNEL_EXPORT virtual ~NGL(void);
    static void* operator new(size_t s);
  };

  class GECODE_VTABLE_EXPORT Choice : public HeapAllocated {
    friend class Space;
  private:
    unsigned int bid; 
    unsigned int alt; 

    unsigned int id(void) const;
  protected:
    Choice(const Brancher& b, const unsigned int a);
  public:
    unsigned int alternatives(void) const;
    GECODE_KERNEL_EXPORT virtual ~Choice(void);
    virtual size_t size(void) const = 0;
    GECODE_KERNEL_EXPORT
    virtual void archive(Archive& e) const;
  };

  class GECODE_VTABLE_EXPORT Brancher : public Actor {
    friend class ActorLink;
    friend class Space;
    friend class Choice;
  private:
    unsigned int bid;
    unsigned int gid;
    static Brancher* cast(ActorLink* al);
    static const Brancher* cast(const ActorLink* al);
  protected:
    Brancher(Home home);
    Brancher(Space& home, bool share, Brancher& b);
  public:


    virtual bool status(const Space& home) const = 0;
    virtual const Choice* choice(Space& home) = 0;
    virtual const Choice* choice(const Space& home, Archive& e) = 0;
    virtual ExecStatus commit(Space& home, const Choice& c,
                              unsigned int a) = 0;
    GECODE_KERNEL_EXPORT
    virtual NGL* ngl(Space& home, const Choice& c, unsigned int a) const;
    GECODE_KERNEL_EXPORT
    virtual void print(const Space& home, const Choice& c, unsigned int a,
                       std::ostream& o) const;



    unsigned int id(void) const;
    BrancherGroup group(void) const;
    void group(BrancherGroup g);
  };

  class LocalObject : public Actor {
    friend class ActorLink;
    friend class Space;
    friend class LocalHandle;
  protected:
    LocalObject(Home home);
    LocalObject(Space& home, bool share, LocalObject& l);
    static LocalObject* cast(ActorLink* al);
    static const LocalObject* cast(const ActorLink* al);
  private:
    GECODE_KERNEL_EXPORT void fwdcopy(Space& home, bool share);
  public:
    LocalObject* fwd(Space& home, bool share);
  };

  class LocalHandle {
  private:
    LocalObject* o;
  protected:
    LocalHandle(void);
    LocalHandle(LocalObject* lo);
    LocalHandle(const LocalHandle& lh);
  public:
    LocalHandle& operator =(const LocalHandle& lh);
    void update(Space& home, bool share, LocalHandle& lh);
    ~LocalHandle(void);
  protected:
    LocalObject* object(void) const;
    void object(LocalObject* n);
  };


  class GECODE_VTABLE_EXPORT NoGoods {
  protected:
    unsigned long int n;
  public:
    NoGoods(void);
    GECODE_KERNEL_EXPORT
    virtual void post(Space& home) const;
    unsigned long int ng(void) const;
    void ng(unsigned long int n);
    virtual ~NoGoods(void);
    GECODE_KERNEL_EXPORT
    static NoGoods eng;
  };

  class GECODE_VTABLE_EXPORT MetaInfo {
  public:
    enum Type {
      RESTART,
      PORTFOLIO
    };
  protected:
    const Type t;


    const unsigned long int r;
    const unsigned long int s;
    const unsigned long int f;
    const Space* l;
    const NoGoods& ng;



    const unsigned int a;
  public:


    MetaInfo(unsigned long int r,
             unsigned long int s,
             unsigned long int f,
             const Space* l,
             NoGoods& ng);
    MetaInfo(unsigned int a);

    Type type(void) const;


    unsigned long int restart(void) const;
    unsigned long int solution(void) const;
    unsigned long int fail(void) const;
    const Space* last(void) const;
    const NoGoods& nogoods(void) const;



    unsigned int asset(void) const;
  };

  enum SpaceStatus {
    SS_FAILED, 
    SS_SOLVED, 
    SS_BRANCH  
  };

  class StatusStatistics {
  public:
    unsigned long int propagate;
    StatusStatistics(void);
    void reset(void);
    StatusStatistics operator +(const StatusStatistics& s);
    StatusStatistics& operator +=(const StatusStatistics& s);
  };

  class CloneStatistics {
  public:
    CloneStatistics(void);
    void reset(void);
    CloneStatistics operator +(const CloneStatistics& s);
    CloneStatistics& operator +=(const CloneStatistics& s);
  };

  class CommitStatistics {
  public:
    CommitStatistics(void);
    void reset(void);
    CommitStatistics operator +(const CommitStatistics& s);
    CommitStatistics& operator +=(const CommitStatistics& s);
  };


  class GECODE_VTABLE_EXPORT Space : public HeapAllocated {
    friend class Actor;
    friend class Propagator;
    friend class PropagatorGroup;
    friend class Propagators;
    friend class Brancher;
    friend class BrancherGroup;
    friend class Branchers;
    friend class Advisor;
    template <class A> friend class Council;
    template<class VIC> friend class VarImp;
    template<class VarImp> friend class VarImpDisposer;
    friend class SharedHandle;
    friend class LocalObject;
    friend class Region;
    friend class AFC;
    friend class PostInfo;
  private:
    SharedMemory* sm;
    MemoryManager mm;
    GPI gpi;
    ActorLink pl;
    ActorLink bl;
    Brancher* b_status;
    Brancher* b_commit;
    Brancher* brancher(unsigned int id);

    void kill(Brancher& b);
    void kill(Propagator& p);

    GECODE_KERNEL_EXPORT
    void kill_brancher(unsigned int id);

    static const unsigned reserved_bid = 0U;

    static const unsigned int sc_bits = 2;
    static const unsigned int sc_fast = 0;
    static const unsigned int sc_disabled = 1;
    static const unsigned int sc_trace = 2;

    union {
      struct {
        ActorLink* active;
        ActorLink queue[PropCost::AC_MAX+1];
        unsigned int bid_sc;
        unsigned int n_sub;
        ViewTraceInfo vti;
      } p;
      struct {
        VarImpBase* vars_u[AllVarConf::idx_c];
        VarImpBase* vars_noidx;
        SharedHandle::Object* shared;
        LocalObject* local;
      } c;
    } pc;
    void enqueue(Propagator* p);
#ifdef GECODE_HAS_VAR_DISPOSE

    GECODE_KERNEL_EXPORT static VarImpDisposerBase* vd[AllVarConf::idx_d];
    VarImpBase* _vars_d[AllVarConf::idx_d];
    template<class VIC> VarImpBase* vars_d(void) const;
    template<class VIC> void vars_d(VarImpBase* x);
#endif

    void update(ActorLink** sub);

    TraceRecorder* findtr(void);

    Actor** d_fst;
    Actor** d_cur;
    Actor** d_lst;

    GECODE_KERNEL_EXPORT static StatusStatistics unused_status;
    GECODE_KERNEL_EXPORT static CloneStatistics unused_clone;
    GECODE_KERNEL_EXPORT static CommitStatistics unused_commit;

    GECODE_KERNEL_EXPORT Space* _clone(bool share_data=true,
                                       bool share_info=true);

    GECODE_KERNEL_EXPORT
    void _commit(const Choice& c, unsigned int a);

    GECODE_KERNEL_EXPORT
    void _trycommit(const Choice& c, unsigned int a);

    GECODE_KERNEL_EXPORT
    void ap_notice_dispose(Actor* a, bool d);
    GECODE_KERNEL_EXPORT
    void ap_ignore_dispose(Actor* a, bool d);

  public:
    GECODE_KERNEL_EXPORT
    Space(void);
    GECODE_KERNEL_EXPORT
    Space(bool share, Space& s);
    GECODE_KERNEL_EXPORT
    virtual ~Space(void);
    virtual Space* copy(bool share) = 0;
    GECODE_KERNEL_EXPORT virtual void constrain(const Space& best);
    GECODE_KERNEL_EXPORT
    virtual bool master(const MetaInfo& mi);
    GECODE_KERNEL_EXPORT
    virtual bool slave(const MetaInfo& mi);

    /*
     * Member functions for search engines
     *
     */

    GECODE_KERNEL_EXPORT
    SpaceStatus status(StatusStatistics& stat=unused_status);

    GECODE_KERNEL_EXPORT
    const Choice* choice(void);

    GECODE_KERNEL_EXPORT
    const Choice* choice(Archive& e) const;

    Space* clone(bool share_data=true,
                 bool share_info=true,
                 CloneStatistics& stat=unused_clone) const;

    void commit(const Choice& c, unsigned int a,
                CommitStatistics& stat=unused_commit);
    void trycommit(const Choice& c, unsigned int a,
                   CommitStatistics& stat=unused_commit);
    GECODE_KERNEL_EXPORT
    NGL* ngl(const Choice& c, unsigned int a);

    GECODE_KERNEL_EXPORT
    void print(const Choice& c, unsigned int a, std::ostream& o) const;

    GECODE_KERNEL_EXPORT
    void notice(Actor& a, ActorProperty p, bool duplicate=false);
    GECODE_KERNEL_EXPORT
    void ignore(Actor& a, ActorProperty p, bool duplicate=false);


    ExecStatus ES_SUBSUMED(Propagator& p);
    ExecStatus ES_SUBSUMED_DISPOSED(Propagator& p, size_t s);
    ExecStatus ES_FIX_PARTIAL(Propagator& p, const ModEventDelta& med);
    ExecStatus ES_NOFIX_PARTIAL(Propagator& p, const ModEventDelta& med);

    template<class A>
    ExecStatus ES_FIX_DISPOSE(Council<A>& c, A& a);
    template<class A>
    ExecStatus ES_NOFIX_DISPOSE(Council<A>& c, A& a);
    template<class A>
    ExecStatus ES_NOFIX_DISPOSE_FORCE(Council<A>& c, A& a);

    void fail(void);
    bool failed(void) const;
    bool stable(void) const;



    Home operator ()(Propagator& p);
    Home operator ()(PropagatorGroup pg);
    Home operator ()(BrancherGroup bg);

    template<class T>
    T* alloc(long unsigned int n);
    template<class T>
    T* alloc(long int n);
    template<class T>
    T* alloc(unsigned int n);
    template<class T>
    T* alloc(int n);
    template<class T>
    void free(T* b, long unsigned int n);
    template<class T>
    void free(T* b, long int n);
    template<class T>
    void free(T* b, unsigned int n);
    template<class T>
    void free(T* b, int n);
    template<class T>
    T* realloc(T* b, long unsigned int n, long unsigned int m);
    template<class T>
    T* realloc(T* b, long int n, long int m);
    template<class T>
    T* realloc(T* b, unsigned int n, unsigned int m);
    template<class T>
    T* realloc(T* b, int n, int m);
    template<class T>
    T** realloc(T** b, long unsigned int n, long unsigned int m);
    template<class T>
    T** realloc(T** b, long int n, long int m);
    template<class T>
    T** realloc(T** b, unsigned int n, unsigned int m);
    template<class T>
    T** realloc(T** b, int n, int m);
    void* ralloc(size_t s);
    void rfree(void* p, size_t s);
    void* rrealloc(void* b, size_t n, size_t m);
    template<size_t> void* fl_alloc(void);
    template<size_t> void  fl_dispose(FreeList* f, FreeList* l);
    GECODE_KERNEL_EXPORT void flush(void);



    template<class T>
    T& construct(void);
    template<class T, typename A1>
    T& construct(A1 const& a1);
    template<class T, typename A1, typename A2>
    T& construct(A1 const& a1, A2 const& a2);
    template<class T, typename A1, typename A2, typename A3>
    T& construct(A1 const& a1, A2 const& a2, A3 const& a3);
    template<class T, typename A1, typename A2, typename A3, typename A4>
    T& construct(A1 const& a1, A2 const& a2, A3 const& a3, A4 const& a4);
    template<class T, typename A1, typename A2, typename A3, typename A4, typename A5>
    T& construct(A1 const& a1, A2 const& a2, A3 const& a3, A4 const& a4, A5 const& a5);



    void afc_decay(double d);
    double afc_decay(void) const;

  private:
    class Propagators {
    private:
      Space& home;
      ActorLink* q;
      ActorLink* c;
      ActorLink* e;
    public:
      Propagators(Space& home);
      bool operator ()(void) const;
      void operator ++(void);
      Propagator& propagator(void) const;
    };
    class ScheduledPropagators {
    private:
      Space& home;
      ActorLink* q;
      ActorLink* c;
      ActorLink* e;
    public:
      ScheduledPropagators(Space& home);
      bool operator ()(void) const;
      void operator ++(void);
      Propagator& propagator(void) const;
    };
    class IdlePropagators {
    private:
      ActorLink* c;
      ActorLink* e;
    public:
      IdlePropagators(Space& home);
      bool operator ()(void) const;
      void operator ++(void);
      Propagator& propagator(void) const;
    };
    class Branchers {
    private:
      ActorLink* c;
      ActorLink* e;
    public:
      Branchers(Space& home);
      bool operator ()(void) const;
      void operator ++(void);
      Brancher& brancher(void) const;
    };
  };

  class Propagators {
  private:
    Space::Propagators ps;
    PropagatorGroup g;
  public:
    Propagators(Space& home, PropagatorGroup g);
    bool operator ()(void) const;
    void operator ++(void);
    const Propagator& propagator(void) const;
  };

  class Branchers {
  private:
    Space::Branchers bs;
    BrancherGroup g;
  public:
    Branchers(Space& home, BrancherGroup g);
    bool operator ()(void) const;
    void operator ++(void);
    const Brancher& brancher(void) const;
  };




  /*
   * Memory management
   *
   */

  // Space allocation: general space heaps and free lists
  forceinline void*
  Space::ralloc(size_t s) {
    return mm.alloc(sm,s);
  }
  forceinline void
  Space::rfree(void* p, size_t s) {
    return mm.reuse(p,s);
  }
  forceinline void*
  Space::rrealloc(void* _b, size_t n, size_t m) {
    char* b = static_cast<char*>(_b);
    if (n < m) {
      char* p = static_cast<char*>(ralloc(m));
      memcpy(p,b,n);
      rfree(b,n);
      return p;
    } else {
      rfree(b+m,m-n);
      return b;
    }
  }

  template<size_t s>
  forceinline void*
  Space::fl_alloc(void) {
    return mm.template fl_alloc<s>(sm);
  }
  template<size_t s>
  forceinline void
  Space::fl_dispose(FreeList* f, FreeList* l) {
    mm.template fl_dispose<s>(f,l);
  }

  /*
   * Typed allocation routines
   *
   */
  template<class T>
  forceinline T*
  Space::alloc(long unsigned int n) {
    T* p = static_cast<T*>(ralloc(sizeof(T)*n));
    for (long unsigned int i=n; i--; )
      (void) new (p+i) T();
    return p;
  }
  template<class T>
  forceinline T*
  Space::alloc(long int n) {
    assert(n >= 0);
    return alloc<T>(static_cast<long unsigned int>(n));
  }
  template<class T>
  forceinline T*
  Space::alloc(unsigned int n) {
    return alloc<T>(static_cast<long unsigned int>(n));
  }
  template<class T>
  forceinline T*
  Space::alloc(int n) {
    assert(n >= 0);
    return alloc<T>(static_cast<long unsigned int>(n));
  }

  template<class T>
  forceinline void
  Space::free(T* b, long unsigned int n) {
    for (long unsigned int i=n; i--; )
      b[i].~T();
    rfree(b,n*sizeof(T));
  }
  template<class T>
  forceinline void
  Space::free(T* b, long int n) {
    assert(n >= 0);
    free<T>(b,static_cast<long unsigned int>(n));
  }
  template<class T>
  forceinline void
  Space::free(T* b, unsigned int n) {
    free<T>(b,static_cast<long unsigned int>(n));
  }
  template<class T>
  forceinline void
  Space::free(T* b, int n) {
    assert(n >= 0);
    free<T>(b,static_cast<long unsigned int>(n));
  }

  template<class T>
  forceinline T*
  Space::realloc(T* b, long unsigned int n, long unsigned int m) {
    if (n < m) {
      T* p = static_cast<T*>(ralloc(sizeof(T)*m));
      for (long unsigned int i=n; i--; )
        (void) new (p+i) T(b[i]);
      for (long unsigned int i=n; i<m; i++)
        (void) new (p+i) T();
      free<T>(b,n);
      return p;
    } else {
      free<T>(b+m,m-n);
      return b;
    }
  }
  template<class T>
  forceinline T*
  Space::realloc(T* b, long int n, long int m) {
    assert((n >= 0) && (m >= 0));
    return realloc<T>(b,static_cast<long unsigned int>(n),
                      static_cast<long unsigned int>(m));
  }
  template<class T>
  forceinline T*
  Space::realloc(T* b, unsigned int n, unsigned int m) {
    return realloc<T>(b,static_cast<long unsigned int>(n),
                      static_cast<long unsigned int>(m));
  }
  template<class T>
  forceinline T*
  Space::realloc(T* b, int n, int m) {
    assert((n >= 0) && (m >= 0));
    return realloc<T>(b,static_cast<long unsigned int>(n),
                      static_cast<long unsigned int>(m));
  }

#define GECODE_KERNEL_REALLOC(T)                                        \
  template<>                                                            \
  forceinline T*                                                        \
  Space::realloc<T>(T* b, long unsigned int n, long unsigned int m) {   \
    return static_cast<T*>(rrealloc(b,n*sizeof(T),m*sizeof(T)));        \
  }                                                                     \
  template<>                                                            \
  forceinline T*                                                        \
  Space::realloc<T>(T* b, long int n, long int m) {                     \
    assert((n >= 0) && (m >= 0));                                       \
    return realloc<T>(b,static_cast<long unsigned int>(n),              \
                      static_cast<long unsigned int>(m));               \
  }                                                                     \
  template<>                                                            \
  forceinline T*                                                        \
  Space::realloc<T>(T* b, unsigned int n, unsigned int m) {             \
    return realloc<T>(b,static_cast<long unsigned int>(n),              \
                      static_cast<long unsigned int>(m));               \
  }                                                                     \
  template<>                                                            \
  forceinline T*                                                        \
  Space::realloc<T>(T* b, int n, int m) {                               \
    assert((n >= 0) && (m >= 0));                                       \
    return realloc<T>(b,static_cast<long unsigned int>(n),              \
                      static_cast<long unsigned int>(m));               \
  }

  GECODE_KERNEL_REALLOC(bool)
  GECODE_KERNEL_REALLOC(signed char)
  GECODE_KERNEL_REALLOC(unsigned char)
  GECODE_KERNEL_REALLOC(signed short int)
  GECODE_KERNEL_REALLOC(unsigned short int)
  GECODE_KERNEL_REALLOC(signed int)
  GECODE_KERNEL_REALLOC(unsigned int)
  GECODE_KERNEL_REALLOC(signed long int)
  GECODE_KERNEL_REALLOC(unsigned long int)
  GECODE_KERNEL_REALLOC(float)
  GECODE_KERNEL_REALLOC(double)

#undef GECODE_KERNEL_REALLOC

  template<class T>
  forceinline T**
  Space::realloc(T** b, long unsigned int n, long unsigned int m) {
    return static_cast<T**>(rrealloc(b,n*sizeof(T),m*sizeof(T*)));
  }
  template<class T>
  forceinline T**
  Space::realloc(T** b, long int n, long int m) {
    assert((n >= 0) && (m >= 0));
    return realloc<T*>(b,static_cast<long unsigned int>(n),
                       static_cast<long unsigned int>(m));
  }
  template<class T>
  forceinline T**
  Space::realloc(T** b, unsigned int n, unsigned int m) {
    return realloc<T*>(b,static_cast<long unsigned int>(n),
                       static_cast<long unsigned int>(m));
  }
  template<class T>
  forceinline T**
  Space::realloc(T** b, int n, int m) {
    assert((n >= 0) && (m >= 0));
    return realloc<T*>(b,static_cast<long unsigned int>(n),
                       static_cast<long unsigned int>(m));
  }


#ifdef GECODE_HAS_VAR_DISPOSE
  template<class VIC>
  forceinline VarImpBase*
  Space::vars_d(void) const {
    return _vars_d[VIC::idx_d];
  }
  template<class VIC>
  forceinline void
  Space::vars_d(VarImpBase* x) {
    _vars_d[VIC::idx_d] = x;
  }
#endif

  // Space allocated entities: Actors, variable implementations, and advisors
  forceinline void
  Actor::operator delete(void*) {}
  forceinline void
  Actor::operator delete(void*, Space&) {}
  forceinline void*
  Actor::operator new(size_t s, Space& home) {
    return home.ralloc(s);
  }

  template<class VIC>
  forceinline void
  VarImp<VIC>::operator delete(void*) {}
  template<class VIC>
  forceinline void
  VarImp<VIC>::operator delete(void*, Space&) {}
  template<class VIC>
  forceinline void*
  VarImp<VIC>::operator new(size_t s, Space& home) {
    return home.ralloc(s);
  }

#ifndef __GNUC__
  forceinline void
  Advisor::operator delete(void*) {}
#endif
  forceinline void
  Advisor::operator delete(void*, Space&) {}
  forceinline void*
  Advisor::operator new(size_t s, Space& home) {
    return home.ralloc(s);
  }

  forceinline void
  NGL::operator delete(void*) {}
  forceinline void
  NGL::operator delete(void*, Space&) {}
  forceinline void*
  NGL::operator new(size_t s, Space& home) {
    return home.ralloc(s);
  }

  /*
   * Shared objects and handles
   *
   */
  forceinline
  SharedHandle::Object::Object(void)
    : next(NULL), fwd(NULL), use_cnt(0) {}
  forceinline
  SharedHandle::Object::~Object(void) {
    assert(use_cnt == 0);
  }

  forceinline SharedHandle::Object*
  SharedHandle::object(void) const {
    return o;
  }
  forceinline void
  SharedHandle::subscribe(void) {
    if (o != NULL) o->use_cnt++;
  }
  forceinline void
  SharedHandle::cancel(void) {
    if ((o != NULL) && (--o->use_cnt == 0))
      delete o;
    o=NULL;
  }
  forceinline void
  SharedHandle::object(SharedHandle::Object* n) {
    if (n != o) {
      cancel(); o=n; subscribe();
    }
  }
  forceinline
  SharedHandle::SharedHandle(void) : o(NULL) {}
  forceinline
  SharedHandle::SharedHandle(SharedHandle::Object* so) : o(so) {
    subscribe();
  }
  forceinline
  SharedHandle::SharedHandle(const SharedHandle& sh) : o(sh.o) {
    subscribe();
  }
  forceinline SharedHandle&
  SharedHandle::operator =(const SharedHandle& sh) {
    if (&sh != this) {
      cancel(); o=sh.o; subscribe();
    }
    return *this;
  }
  forceinline void
  SharedHandle::update(Space& home, bool share, SharedHandle& sh) {
    if (sh.o == NULL) {
      o=NULL; return;
    } else if (share) {
      o=sh.o;
    } else if (sh.o->fwd != NULL) {
      o=sh.o->fwd;
    } else {
      o = sh.o->copy();
      sh.o->fwd = o;
      sh.o->next = home.pc.c.shared;
      home.pc.c.shared = sh.o;
    }
    subscribe();
  }
  forceinline
  SharedHandle::~SharedHandle(void) {
    cancel();
  }



  /*
   * No-goods
   *
   */
  forceinline
  NoGoods::NoGoods(void)
    : n(0) {}
  forceinline unsigned long int
  NoGoods::ng(void) const {
    return n;
  }
  forceinline void
  NoGoods::ng(unsigned long int n0) {
    n=n0;
  }
  forceinline
  NoGoods::~NoGoods(void) {}


  /*
   * Information from meta search engines
   */
  forceinline
  MetaInfo::MetaInfo(unsigned long int r0,
                     unsigned long int s0,
                     unsigned long int f0,
                     const Space* l0,
                     NoGoods& ng0)
    : t(RESTART), r(r0), s(s0), f(f0), l(l0), ng(ng0), a(0) {}

  forceinline
  MetaInfo::MetaInfo(unsigned int a0)
    : t(PORTFOLIO), r(0), s(0), f(0), l(NULL), ng(NoGoods::eng), a(a0) {}

  forceinline MetaInfo::Type
  MetaInfo::type(void) const {
    return t;
  }
  forceinline unsigned long int
  MetaInfo::restart(void) const {
    assert(type() == RESTART);
    return r;
  }
  forceinline unsigned long int
  MetaInfo::solution(void) const {
    assert(type() == RESTART);
    return s;
  }
  forceinline unsigned long int
  MetaInfo::fail(void) const {
    assert(type() == RESTART);
    return f;
  }
  forceinline const Space*
  MetaInfo::last(void) const {
    assert(type() == RESTART);
    return l;
  }
  forceinline const NoGoods&
  MetaInfo::nogoods(void) const {
    assert(type() == RESTART);
    return ng;
  }
  forceinline unsigned int
  MetaInfo::asset(void) const {
    assert(type() == PORTFOLIO);
    return a;
  }



  /*
   * ActorLink
   *
   */
  forceinline ActorLink*
  ActorLink::prev(void) const {
    return _prev;
  }

  forceinline ActorLink*
  ActorLink::next(void) const {
    return _next;
  }

  forceinline ActorLink**
  ActorLink::next_ref(void) {
    return &_next;
  }

  forceinline void
  ActorLink::prev(ActorLink* al) {
    _prev = al;
  }

  forceinline void
  ActorLink::next(ActorLink* al) {
    _next = al;
  }

  forceinline void
  ActorLink::unlink(void) {
    ActorLink* p = _prev; ActorLink* n = _next;
    p->_next = n; n->_prev = p;
  }

  forceinline void
  ActorLink::init(void) {
    _next = this; _prev =this;
  }

  forceinline void
  ActorLink::head(ActorLink* a) {
    // Inserts al at head of link-chain (that is, after this)
    ActorLink* n = _next;
    this->_next = a; a->_prev = this;
    a->_next = n; n->_prev = a;
  }

  forceinline void
  ActorLink::tail(ActorLink* a) {
    // Inserts al at tail of link-chain (that is, before this)
    ActorLink* p = _prev;
    a->_next = this; this->_prev = a;
    p->_next = a; a->_prev = p;
  }

  forceinline bool
  ActorLink::empty(void) const {
    return _next == this;
  }

  template<class T>
  forceinline ActorLink*
  ActorLink::cast(T* a) {
    // Turning al into a reference is for gcc, assume is for MSVC
    GECODE_NOT_NULL(a);
    ActorLink& t = *a;
    return static_cast<ActorLink*>(&t);
  }

  template<class T>
  forceinline const ActorLink*
  ActorLink::cast(const T* a) {
    // Turning al into a reference is for gcc, assume is for MSVC
    GECODE_NOT_NULL(a);
    const ActorLink& t = *a;
    return static_cast<const ActorLink*>(&t);
  }


  /*
   * Actor
   *
   */
  forceinline Actor*
  Actor::cast(ActorLink* al) {
    // Turning al into a reference is for gcc, assume is for MSVC
    GECODE_NOT_NULL(al);
    ActorLink& t = *al;
    return static_cast<Actor*>(&t);
  }

  forceinline const Actor*
  Actor::cast(const ActorLink* al) {
    // Turning al into a reference is for gcc, assume is for MSVC
    GECODE_NOT_NULL(al);
    const ActorLink& t = *al;
    return static_cast<const Actor*>(&t);
  }

  forceinline void
  Home::notice(Actor& a, ActorProperty p, bool duplicate) {
    s.notice(a,p,duplicate);
  }

  forceinline Space*
  Space::clone(bool share_data, bool share_info, CloneStatistics&) const {
    // Clone is only const for search engines. During cloning, several data
    // structures are updated (e.g. forwarding pointers), so we have to
    // cast away the constness.
    return const_cast<Space*>(this)->_clone(share_data,share_info);
  }

  forceinline void
  Space::commit(const Choice& c, unsigned int a, CommitStatistics&) {
    _commit(c,a);
  }

  forceinline void
  Space::trycommit(const Choice& c, unsigned int a, CommitStatistics&) {
    _trycommit(c,a);
  }

  forceinline double
  Space::afc_decay(void) const {
    return gpi.decay();
  }

  forceinline void
  Space::afc_decay(double d) {
    gpi.decay(d);
  }

  forceinline size_t
  Actor::dispose(Space&) {
    return sizeof(*this);
  }


  /*
   * Home for posting actors
   *
   */
  forceinline
  Home::Home(Space& s0, Propagator* p0,
             PropagatorGroup pg0, BrancherGroup bg0)
    : s(s0), p(p0), pg(pg0), bg(bg0) {}
  forceinline Home&
  Home::operator =(const Home& h) {
    s=h.s; p=h.p; pg=h.pg; bg=h.bg;
    return *this;
  }
  forceinline
  Home::operator Space&(void) {
    return s;
  }
  forceinline Home
  Home::operator ()(Propagator& p) {
    return Home(s,&p);
  }
  forceinline Home
  Home::operator ()(PropagatorGroup pg) {
    return Home(s,NULL,pg,BrancherGroup::def);
  }
  forceinline Home
  Home::operator ()(BrancherGroup bg) {
    return Home(s,NULL,PropagatorGroup::def,bg);
  }
  forceinline Home
  Space::operator ()(Propagator& p) {
    return Home(*this,&p);
  }
  forceinline Propagator*
  Home::propagator(void) const {
    return p;
  }
  forceinline PropagatorGroup
  Home::propagatorgroup(void) const {
    return pg;
  }
  forceinline BrancherGroup
  Home::branchergroup(void) const {
    return bg;
  }

  /*
   * View trace information
   *
   */
  forceinline void
  ViewTraceInfo::propagator(Propagator& p) {
    who = reinterpret_cast<ptrdiff_t>(&p) | PROPAGATOR;
  }
  forceinline void
  ViewTraceInfo::brancher(Brancher& b) {
    who = reinterpret_cast<ptrdiff_t>(&b) | BRANCHER;
  }
  forceinline void
  ViewTraceInfo::post(PropagatorGroup g) {
    who = (g.id() << 2) | POST;
  }
  forceinline void
  ViewTraceInfo::other(void) {
    who = OTHER;
  }
  forceinline ViewTraceInfo::What
  ViewTraceInfo::what(void) const {
    return static_cast<What>(who & 3);
  }
  forceinline const Propagator&
  ViewTraceInfo::propagator(void) const {
    assert(what() == PROPAGATOR);
    // Because PROPAGATOR == 0
    return *reinterpret_cast<Propagator*>(who);
  }
  forceinline const Brancher&
  ViewTraceInfo::brancher(void) const {
    assert(what() == BRANCHER);
    return *reinterpret_cast<Brancher*>(who & ~3);
  }
  forceinline PropagatorGroup
  ViewTraceInfo::post(void) const {
    assert(what() == POST);
    return PropagatorGroup(static_cast<unsigned int>(who >> 2));
  }

  /*
   * Post information
   */
  forceinline
  PostInfo::PostInfo(Home home) : h(home) {
    h.pc.p.vti.post(home.propagatorgroup());
  }
  forceinline
  PostInfo::~PostInfo(void) {
    h.pc.p.vti.other();
  }

  /*
   * Propagate trace information
   *
   */
  forceinline
  PropagateTraceInfo::PropagateTraceInfo(unsigned int i0, PropagatorGroup g0,
                                         const Propagator* p0, Status s0)
    : i(i0), g(g0), p(p0), s(s0) {}
  forceinline unsigned int
  PropagateTraceInfo::id(void) const {
    return i;
  }
  forceinline PropagatorGroup
  PropagateTraceInfo::group(void) const {
    return g;
  }
  forceinline const Propagator*
  PropagateTraceInfo::propagator(void) const {
    return p;
  }
  forceinline PropagateTraceInfo::Status
  PropagateTraceInfo::status(void) const {
    return s;
  }


  /*
   * Commit trace information
   *
   */
  forceinline
  CommitTraceInfo::CommitTraceInfo(const Brancher& b0, const Choice& c0,
                                   unsigned int a0)
    : b(b0), c(c0), a(a0) {}
  forceinline unsigned int
  CommitTraceInfo::id(void) const {
    return b.id();
  }
  forceinline BrancherGroup
  CommitTraceInfo::group(void) const {
    return b.group();
  }
  forceinline const Brancher&
  CommitTraceInfo::brancher(void) const {
    return b;
  }
  forceinline const Choice&
  CommitTraceInfo::choice(void) const {
    return c;
  }
  forceinline unsigned int
  CommitTraceInfo::alternative(void) const {
    return a;
  }


  /*
   * Propagator
   *
   */
  forceinline Propagator*
  Propagator::cast(ActorLink* al) {
    // Turning al into a reference is for gcc, assume is for MSVC
    GECODE_NOT_NULL(al);
    ActorLink& t = *al;
    return static_cast<Propagator*>(&t);
  }

  forceinline const Propagator*
  Propagator::cast(const ActorLink* al) {
    // Turning al into a reference is for gcc, assume is for MSVC
    GECODE_NOT_NULL(al);
    const ActorLink& t = *al;
    return static_cast<const Propagator*>(&t);
  }

  forceinline Propagator*
  Propagator::fwd(void) const {
    return static_cast<Propagator*>(prev());
  }

  forceinline bool
  Propagator::disabled(void) const {
    return Support::marked(gpi_disabled);
  }

  forceinline void
  Propagator::disable(Space& home) {
    home.pc.p.bid_sc |= Space::sc_disabled;
    gpi_disabled = Support::fmark(gpi_disabled);
  }

  forceinline void
  Propagator::enable(Space& home) {
    (void) home;
    gpi_disabled = Support::funmark(gpi_disabled);
  }

  forceinline GPI::Info&
  Propagator::gpi(void) {
    return *static_cast<GPI::Info*>(Support::funmark(gpi_disabled));
  }

  forceinline
  Propagator::Propagator(Home home)
    : gpi_disabled((home.propagator() != NULL) ?
                   // Inherit propagator information
                   home.propagator()->gpi_disabled :
                   // New propagator information
                   static_cast<Space&>(home).gpi.allocate(home.propagatorgroup().gid)) {
    u.advisors = NULL;
    assert((u.med == 0) && (u.size == 0));
    static_cast<Space&>(home).pl.head(this);
  }

  forceinline
  Propagator::Propagator(Space&, bool, Propagator& p)
    : gpi_disabled(p.gpi_disabled) {
    u.advisors = NULL;
    assert((u.med == 0) && (u.size == 0));
    // Set forwarding pointer
    p.prev(this);
  }

  forceinline ModEventDelta
  Propagator::modeventdelta(void) const {
    return u.med;
  }

  forceinline double
  Propagator::afc(void) const {
    return const_cast<Propagator&>(*this).gpi().afc;
  }

  forceinline unsigned int
  Propagator::id(void) const {
    return const_cast<Propagator&>(*this).gpi().pid;
  }

  forceinline PropagatorGroup
  Propagator::group(void) const {
    return PropagatorGroup(const_cast<Propagator&>(*this).gpi().gid);
  }

  forceinline void
  Propagator::group(PropagatorGroup g) {
    gpi().gid = g.id();
  }

  forceinline ExecStatus
  Space::ES_SUBSUMED_DISPOSED(Propagator& p, size_t s) {
    p.u.size = s;
    return __ES_SUBSUMED;
  }

  forceinline ExecStatus
  Space::ES_SUBSUMED(Propagator& p) {
    p.u.size = p.dispose(*this);
    return __ES_SUBSUMED;
  }

  forceinline ExecStatus
  Space::ES_FIX_PARTIAL(Propagator& p, const ModEventDelta& med) {
    p.u.med = med;
    assert(p.u.med != 0);
    return __ES_PARTIAL;
  }

  forceinline ExecStatus
  Space::ES_NOFIX_PARTIAL(Propagator& p, const ModEventDelta& med) {
    p.u.med = AllVarConf::med_combine(p.u.med,med);
    assert(p.u.med != 0);
    return __ES_PARTIAL;
  }



  /*
   * Brancher
   *
   */
  forceinline Brancher*
  Brancher::cast(ActorLink* al) {
    // Turning al into a reference is for gcc, assume is for MSVC
    GECODE_NOT_NULL(al);
    ActorLink& t = *al;
    return static_cast<Brancher*>(&t);
  }

  forceinline const Brancher*
  Brancher::cast(const ActorLink* al) {
    // Turning al into a reference is for gcc, assume is for MSVC
    GECODE_NOT_NULL(al);
    const ActorLink& t = *al;
    return static_cast<const Brancher*>(&t);
  }

  forceinline
  Brancher::Brancher(Home _home) :
    gid(_home.branchergroup().gid) {
    Space& home = static_cast<Space&>(_home);
    bid = home.pc.p.bid_sc >> Space::sc_bits;
    home.pc.p.bid_sc += (1 << Space::sc_bits);
    if ((home.pc.p.bid_sc >> Space::sc_bits) == 0U)
      throw TooManyBranchers("Brancher::Brancher");
    // If no brancher available, make it the first one
    if (home.b_status == &static_cast<Space&>(home).bl) {
      home.b_status = this;
      if (home.b_commit == &static_cast<Space&>(home).bl)
        home.b_commit = this;
    }
    home.bl.tail(this);
  }

  forceinline
  Brancher::Brancher(Space&, bool, Brancher& b)
    : bid(b.bid), gid(b.gid) {
    // Set forwarding pointer
    b.prev(this);
  }

  forceinline unsigned int
  Brancher::id(void) const {
    return bid;
  }

  forceinline BrancherGroup
  Brancher::group(void) const {
    return BrancherGroup(gid);
  }

  forceinline void
  Brancher::group(BrancherGroup g) {
    gid = g.id();
  }


  forceinline void
  Space::kill(Brancher& b) {
    assert(!failed());
    // Make sure that neither b_status nor b_commit does not point to b!
    if (b_commit == &b)
      b_commit = Brancher::cast(b.next());
    if (b_status == &b)
      b_status = Brancher::cast(b.next());
    b.unlink();
    rfree(&b,b.dispose(*this));
  }

  forceinline void
  Space::kill(Propagator& p) {
    assert(!failed());
    p.unlink();
    rfree(&p,p.dispose(*this));
  }

  forceinline Brancher*
  Space::brancher(unsigned int id) {
    /*
     * Due to weakly monotonic propagators the following scenario might
     * occur: a brancher has been committed with all its available
     * choices. Then, propagation determines less information
     * than before and the brancher now will create new choices.
     * Later, during recomputation, all of these choices
     * can be used together, possibly interleaved with
     * choices for other branchers. That means all branchers
     * must be scanned to find the matching brancher for the choice.
     *
     * b_commit tries to optimize scanning as it is most likely that
     * recomputation does not generate new choices during recomputation
     * and hence b_commit is moved from newer to older branchers.
     */
    Brancher* b_old = b_commit;
    // Try whether we are lucky
    while (b_commit != Brancher::cast(&bl))
      if (id != b_commit->id())
        b_commit = Brancher::cast(b_commit->next());
      else
        return b_commit;
    if (b_commit == Brancher::cast(&bl)) {
      // We did not find the brancher, start at the beginning
      b_commit = Brancher::cast(bl.next());
      while (b_commit != b_old)
        if (id != b_commit->id())
          b_commit = Brancher::cast(b_commit->next());
        else
          return b_commit;
    }
    return NULL;
  }


  /*
   * Local objects
   *
   */

  forceinline LocalObject*
  LocalObject::cast(ActorLink* al) {
    // Turning al into a reference is for gcc, assume is for MSVC
    GECODE_NOT_NULL(al);
    ActorLink& t = *al;
    return static_cast<LocalObject*>(&t);
  }

  forceinline const LocalObject*
  LocalObject::cast(const ActorLink* al) {
    // Turning al into a reference is for gcc, assume is for MSVC
    GECODE_NOT_NULL(al);
    const ActorLink& t = *al;
    return static_cast<const LocalObject*>(&t);
  }

  forceinline
  LocalObject::LocalObject(Home home) {
    (void) home;
    ActorLink::cast(this)->prev(NULL);
  }

  forceinline
  LocalObject::LocalObject(Space&,bool,LocalObject&) {
    ActorLink::cast(this)->prev(NULL);
  }

  forceinline LocalObject*
  LocalObject::fwd(Space& home, bool share) {
    if (prev() == NULL)
      fwdcopy(home,share);
    return LocalObject::cast(prev());
  }

  forceinline
  LocalHandle::LocalHandle(void) : o(NULL) {}
  forceinline
  LocalHandle::LocalHandle(LocalObject* lo) : o(lo) {}
  forceinline
  LocalHandle::LocalHandle(const LocalHandle& lh) : o(lh.o) {}
  forceinline LocalHandle&
  LocalHandle::operator =(const LocalHandle& lh) {
    o = lh.o;
    return *this;
  }
  forceinline
  LocalHandle::~LocalHandle(void) {}
  forceinline LocalObject*
  LocalHandle::object(void) const { return o; }
  forceinline void
  LocalHandle::object(LocalObject* n) { o = n; }
  forceinline void
  LocalHandle::update(Space& home, bool share, LocalHandle& lh) {
    object(lh.object()->fwd(home,share));
  }


  /*
   * Choices
   *
   */
  forceinline
  Choice::Choice(const Brancher& b, const unsigned int a)
    : bid(b.id()), alt(a) {}

  forceinline unsigned int
  Choice::alternatives(void) const {
    return alt;
  }

  forceinline unsigned int
  Choice::id(void) const {
    return bid;
  }

  forceinline
  Choice::~Choice(void) {}



  /*
   * No-good literal
   *
   */
  forceinline bool
  NGL::leaf(void) const {
    return Support::marked(nl);
  }
  forceinline NGL*
  NGL::next(void) const {
    return static_cast<NGL*>(Support::funmark(nl));
  }
  forceinline void
  NGL::leaf(bool l) {
    nl = l ? Support::fmark(nl) : Support::funmark(nl);
  }
  forceinline void
  NGL::next(NGL* n) {
    nl = Support::marked(nl) ? Support::mark(n) : n;
  }
  forceinline NGL*
  NGL::add(NGL* n, bool l) {
    nl = Support::marked(nl) ? Support::mark(n) : n;
    n->leaf(l);
    return n;
  }

  forceinline
  NGL::NGL(void)
    : nl(NULL) {}
  forceinline
  NGL::NGL(Space&)
    : nl(NULL) {}
  forceinline
  NGL::NGL(Space&, bool, NGL&)
    : nl(NULL) {}
  forceinline size_t
  NGL::dispose(Space&) {
    return sizeof(*this);
  }

  /*
   * Advisor
   *
   */
  template<class A>
  forceinline
  Advisor::Advisor(Space&, Propagator& p, Council<A>& c) {
    // Store propagator and forwarding in prev()
    ActorLink::prev(&p);
    // Link to next advisor in next()
    ActorLink::next(c.advisors); c.advisors = static_cast<A*>(this);
  }

  forceinline
  Advisor::Advisor(Space&, bool, Advisor&) {}

  forceinline bool
  Advisor::disposed(void) const {
    return prev() == NULL;
  }

  forceinline Advisor*
  Advisor::cast(ActorLink* al) {
    return static_cast<Advisor*>(al);
  }

  forceinline const Advisor*
  Advisor::cast(const ActorLink* al) {
    return static_cast<const Advisor*>(al);
  }

  forceinline Propagator&
  Advisor::propagator(void) const {
    assert(!disposed());
    return *Propagator::cast(ActorLink::prev());
  }

  template<class A>
  forceinline void
  Advisor::dispose(Space&,Council<A>&) {
    assert(!disposed());
    ActorLink::prev(NULL);
    // Shorten chains of disposed advisors by one, if possible
    Advisor* n = Advisor::cast(next());
    if ((n != NULL) && n->disposed())
      next(n->next());
  }

  forceinline const ViewTraceInfo&
  Advisor::operator ()(const Space& home) const {
    return home.pc.p.vti;
  }

  template<class A>
  forceinline ExecStatus
  Space::ES_FIX_DISPOSE(Council<A>& c, A& a) {
    a.dispose(*this,c);
    return ES_FIX;
  }

  template<class A>
  forceinline ExecStatus
  Space::ES_NOFIX_DISPOSE(Council<A>& c, A& a) {
    a.dispose(*this,c);
    return ES_NOFIX;
  }

  template<class A>
  forceinline ExecStatus
  Space::ES_NOFIX_DISPOSE_FORCE(Council<A>& c, A& a) {
    a.dispose(*this,c);
    return ES_NOFIX_FORCE;
  }



  /*
   * Advisor council
   *
   */
  template<class A>
  forceinline
  Council<A>::Council(void) {}

  template<class A>
  forceinline
  Council<A>::Council(Space&)
    : advisors(NULL) {}

  template<class A>
  forceinline bool
  Council<A>::empty(void) const {
    ActorLink* a = advisors;
    while ((a != NULL) && static_cast<A*>(a)->disposed())
      a = a->next();
    advisors = a;
    return a == NULL;
  }

  template<class A>
  forceinline void
  Council<A>::update(Space& home, bool share, Council<A>& c) {
    // Skip all disposed advisors
    {
      ActorLink* a = c.advisors;
      while ((a != NULL) && static_cast<A*>(a)->disposed())
        a = a->next();
      c.advisors = a;
    }
    // Are there any advisors to be cloned?
    if (c.advisors != NULL) {
      // The propagator in from-space
      Propagator* p_f = &static_cast<A*>(c.advisors)->propagator();
      // The propagator in to-space
      Propagator* p_t = Propagator::cast(p_f->prev());
      // Advisors in from-space
      ActorLink** a_f = &c.advisors;
      // Advisors in to-space
      A* a_t = NULL;
      while (*a_f != NULL) {
        if (static_cast<A*>(*a_f)->disposed()) {
          *a_f = (*a_f)->next();
        } else {
          // Run specific copying part
          A* a = new (home) A(home,share,*static_cast<A*>(*a_f));
          // Set propagator pointer
          a->prev(p_t);
          // Set forwarding pointer
          (*a_f)->prev(a);
          // Link
          a->next(a_t);
          a_t = a;
          a_f = (*a_f)->next_ref();
        }
      }
      advisors = a_t;
      // Enter advisor link for reset
      assert(p_f->u.advisors == NULL);
      p_f->u.advisors = c.advisors;
    } else {
      advisors = NULL;
    }
  }

  template<class A>
  forceinline void
  Council<A>::dispose(Space& home) {
    ActorLink* a = advisors;
    while (a != NULL) {
      if (!static_cast<A*>(a)->disposed())
        static_cast<A*>(a)->dispose(home,*this);
      a = a->next();
    }
  }



  /*
   * Advisor iterator
   *
   */
  template<class A>
  forceinline
  Advisors<A>::Advisors(const Council<A>& c)
    : a(c.advisors) {
    while ((a != NULL) && static_cast<A*>(a)->disposed())
      a = a->next();
  }

  template<class A>
  forceinline bool
  Advisors<A>::operator ()(void) const {
    return a != NULL;
  }

  template<class A>
  forceinline void
  Advisors<A>::operator ++(void) {
    do {
      a = a->next();
    } while ((a != NULL) && static_cast<A*>(a)->disposed());
  }

  template<class A>
  forceinline A&
  Advisors<A>::advisor(void) const {
    return *static_cast<A*>(a);
  }



  /*
   * Space
   *
   */
  forceinline void
  Space::enqueue(Propagator* p) {
    ActorLink::cast(p)->unlink();
    ActorLink* c = &pc.p.queue[p->cost(*this,p->u.med).ac];
    c->tail(ActorLink::cast(p));
    if (c > pc.p.active)
      pc.p.active = c;
  }

  forceinline void
  Space::fail(void) {
    /*
     * Now active points beyond the last queue. This is essential as
     * enqueuing a propagator in a failed space keeps the space
     * failed.
     */
    pc.p.active = &pc.p.queue[PropCost::AC_MAX+1]+1;
  }
  forceinline void
  Home::fail(void) {
    s.fail();
  }

  forceinline bool
  Space::failed(void) const {
    return pc.p.active > &pc.p.queue[PropCost::AC_MAX+1];
  }
  forceinline bool
  Home::failed(void) const {
    return s.failed();
  }

  forceinline bool
  Space::stable(void) const {
    return ((pc.p.active < &pc.p.queue[0]) ||
            (pc.p.active > &pc.p.queue[PropCost::AC_MAX+1]));
  }

  forceinline TraceRecorder*
  Space::findtr(void) {
    TraceRecorder* tr = NULL;
    for (Actor** a=d_fst; a<d_cur; a++)
      if (Support::marked(*a) &&
          !static_cast<Propagator*>(Support::unmark(*a))->disabled()) {
        tr = static_cast<TraceRecorder*>(Support::unmark(*a));
        std::swap(*d_fst,*a);
        break;
      }
    return tr;
  }

  forceinline void
  Space::notice(Actor& a, ActorProperty p, bool d) {
    if (p & AP_DISPOSE) {
      ap_notice_dispose(&a,d);
    }
    if (p & AP_VIEW_TRACE) {
      pc.p.bid_sc |= sc_trace;
    }
    if (p & AP_TRACE) {
      pc.p.bid_sc |= sc_trace;
      if (findtr())
        throw MoreThanOneTracer("Space::notice");
      ap_notice_dispose(static_cast<Actor*>(Support::fmark(&a)),d);
    }
    // Currently unused
    if (p & AP_WEAKLY) {}
  }

  forceinline void
  Space::ignore(Actor& a, ActorProperty p, bool d) {
    // Check wether array has already been discarded as space
    // deletion is already in progress
    if ((p & AP_DISPOSE) && (d_fst != NULL))
      ap_ignore_dispose(&a,d);
    if (p & AP_VIEW_TRACE) {}
    if ((p & AP_TRACE) && (d_fst != NULL))
      ap_ignore_dispose(static_cast<Actor*>(Support::fmark(&a)),d);
    // Currently unused
    if (p & AP_WEAKLY) {}
  }



  /*
   * Variable implementation
   *
   */
  template<class VIC>
  forceinline ActorLink**
  VarImp<VIC>::actor(PropCond pc) {
    assert((pc >= 0)  && (pc < pc_max+2));
    return (pc == 0) ? b.base : b.base+u.idx[pc-1];
  }

  template<class VIC>
  forceinline ActorLink**
  VarImp<VIC>::actorNonZero(PropCond pc) {
    assert((pc > 0)  && (pc < pc_max+2));
    return b.base+u.idx[pc-1];
  }

  template<class VIC>
  forceinline unsigned int&
  VarImp<VIC>::idx(PropCond pc) {
    assert((pc > 0)  && (pc < pc_max+2));
    return u.idx[pc-1];
  }

  template<class VIC>
  forceinline unsigned int
  VarImp<VIC>::idx(PropCond pc) const {
    assert((pc > 0)  && (pc < pc_max+2));
    return u.idx[pc-1];
  }

  template<class VIC>
  forceinline
  VarImp<VIC>::VarImp(Space&) {
    b.base = NULL; entries = 0;
    for (PropCond pc=1; pc<pc_max+2; pc++)
      idx(pc) = 0;
    free_and_bits = 0;
  }

  template<class VIC>
  forceinline
  VarImp<VIC>::VarImp(void) {
    b.base = NULL; entries = 0;
    for (PropCond pc=1; pc<pc_max+2; pc++)
      idx(pc) = 0;
    free_and_bits = 0;
  }

  template<class VIC>
  forceinline unsigned int
  VarImp<VIC>::degree(void) const {
    assert(!copied());
    return entries;
  }

  template<class VIC>
  forceinline double
  VarImp<VIC>::afc(void) const {
    double d = 0.0;
    // Count the afc of each propagator
    {
      ActorLink** a = const_cast<VarImp<VIC>*>(this)->actor(0);
      ActorLink** e = const_cast<VarImp<VIC>*>(this)->actorNonZero(pc_max+1);
      while (a < e) {
        d += Propagator::cast(*a)->afc(); a++;
      }
    }
    // Count the afc of each advisor's propagator
    {
      ActorLink** a = const_cast<VarImp<VIC>*>(this)->actorNonZero(pc_max+1);
      ActorLink** e = const_cast<VarImp<VIC>*>(this)->b.base+entries;
      while (a < e) {
        d += Advisor::cast(static_cast<ActorLink*>(Support::funmark(*a)))
          ->propagator().afc();
        a++;
      }
    }
    return d;
  }

  template<class VIC>
  forceinline ModEvent
  VarImp<VIC>::modevent(const Delta& d) {
    return d.me;
  }

  template<class VIC>
  forceinline unsigned int
  VarImp<VIC>::bits(void) const {
    return free_and_bits;
  }

  template<class VIC>
  forceinline unsigned int&
  VarImp<VIC>::bits(void) {
    return free_and_bits;
  }

#ifdef GECODE_HAS_VAR_DISPOSE
  template<class VIC>
  forceinline VarImp<VIC>*
  VarImp<VIC>::vars_d(Space& home) {
    return static_cast<VarImp<VIC>*>(home.vars_d<VIC>());
  }

  template<class VIC>
  forceinline void
  VarImp<VIC>::vars_d(Space& home, VarImp<VIC>* x) {
    home.vars_d<VIC>(x);
  }
#endif

  template<class VIC>
  forceinline bool
  VarImp<VIC>::copied(void) const {
    return Support::marked(b.fwd);
  }

  template<class VIC>
  forceinline VarImp<VIC>*
  VarImp<VIC>::forward(void) const {
    assert(copied());
    return static_cast<VarImp<VIC>*>(Support::unmark(b.fwd));
  }

  template<class VIC>
  forceinline VarImp<VIC>*
  VarImp<VIC>::next(void) const {
    assert(copied());
    return u.next;
  }

  template<class VIC>
  forceinline
  VarImp<VIC>::VarImp(Space& home, bool, VarImp<VIC>& x) {
    VarImpBase** reg;
    free_and_bits = x.free_and_bits & ((1 << free_bits) - 1);
    if (x.b.base == NULL) {
      // Variable implementation needs no index structure
      reg = &home.pc.c.vars_noidx;
      assert(x.degree() == 0);
    } else {
      reg = &home.pc.c.vars_u[idx_c];
    }
    // Save subscriptions in copy
    b.base = x.b.base;
    entries = x.entries;
    for (PropCond pc=1; pc<pc_max+2; pc++)
      idx(pc) = x.idx(pc);

    // Set forwarding pointer
    x.b.fwd = static_cast<VarImp<VIC>*>(Support::mark(this));
    // Register original
    x.u.next = static_cast<VarImp<VIC>*>(*reg); *reg = &x;
  }

  template<class VIC>
  forceinline ModEvent
  VarImp<VIC>::me(const ModEventDelta& med) {
    return static_cast<ModEvent>((med & VIC::med_mask) >> VIC::med_fst);
  }

  template<class VIC>
  forceinline ModEventDelta
  VarImp<VIC>::med(ModEvent me) {
    return static_cast<ModEventDelta>(me << VIC::med_fst);
  }

  template<class VIC>
  forceinline ModEvent
  VarImp<VIC>::me_combine(ModEvent me1, ModEvent me2) {
    return VIC::me_combine(me1,me2);
  }

  template<class VIC>
  forceinline void
  VarImp<VIC>::schedule(Space& home, Propagator& p, ModEvent me,
                        bool force) {
    if (VIC::med_update(p.u.med,me) || force)
      home.enqueue(&p);
  }

  template<class VIC>
  forceinline void
  VarImp<VIC>::schedule(Space& home, PropCond pc1, PropCond pc2, ModEvent me) {
    ActorLink** b = actor(pc1);
    ActorLink** p = actorNonZero(pc2+1);
    while (p-- > b)
      schedule(home,*Propagator::cast(*p),me);
  }

  template<class VIC>
  forceinline void
  VarImp<VIC>::resize(Space& home) {
    if (b.base == NULL) {
      assert((free_and_bits >> free_bits) == 0);
      // Create fresh dependency array with four entries
      free_and_bits += 4 << free_bits;
      b.base = home.alloc<ActorLink*>(4);
      for (int i=0; i<pc_max+1; i++)
        u.idx[i] = 0;
    } else {
      // Resize dependency array
      unsigned int n = degree();
      // Find out whether the area is most likely in the special area
      // reserved for subscriptions. If yes, just resize mildly otherwise
      // more agressively
      ActorLink** s = static_cast<ActorLink**>(home.mm.subscriptions());
      unsigned int m =
        ((s <= b.base) && (b.base < s+home.pc.p.n_sub)) ?
        (n+4) : ((n+1)*3>>1);
      ActorLink** prop = home.alloc<ActorLink*>(m);
      free_and_bits += (m-n) << free_bits;
      // Copy entries
      Heap::copy<ActorLink*>(prop, b.base, n);
      home.free<ActorLink*>(b.base,n);
      b.base = prop;
    }
  }

  template<class VIC>
  forceinline void
  VarImp<VIC>::enter(Space& home, Propagator* p, PropCond pc) {
    assert(pc <= pc_max);
    // Count one new subscription
    home.pc.p.n_sub += 1;
    if ((free_and_bits >> free_bits) == 0)
      resize(home);
    free_and_bits -= 1 << free_bits;

    // Enter subscription
    b.base[entries] = *actorNonZero(pc_max+1);
    entries++;
    for (PropCond j = pc_max; j > pc; j--) {
      *actorNonZero(j+1) = *actorNonZero(j);
      idx(j+1)++;
    }
    *actorNonZero(pc+1) = *actor(pc);
    idx(pc+1)++;
    *actor(pc) = ActorLink::cast(p);

#ifdef GECODE_AUDIT
    ActorLink** f = actor(pc);
    while (f < (pc == pc_max+1 ? b.base+entries : actorNonZero(pc+1)))
      if (*f == p)
        goto found;
      else
        f++;
    GECODE_NEVER;
    found: ;
#endif
  }

  template<class VIC>
  forceinline void
  VarImp<VIC>::enter(Space& home, Advisor* a) {
    // Note that a might be a marked pointer
    // Count one new subscription
    home.pc.p.n_sub += 1;
    if ((free_and_bits >> free_bits) == 0)
      resize(home);
    free_and_bits -= 1 << free_bits;

    // Enter subscription
    b.base[entries++] = *actorNonZero(pc_max+1);
    *actorNonZero(pc_max+1) = a;
  }

  template<class VIC>
  forceinline void
  VarImp<VIC>::subscribe(Space& home, Propagator& p, PropCond pc,
                         bool assigned, ModEvent me, bool schedule) {
    if (assigned) {
      // Do not subscribe, just schedule the propagator
      if (schedule)
        VarImp<VIC>::schedule(home,p,ME_GEN_ASSIGNED);
    } else {
      enter(home,&p,pc);
      // Schedule propagator
      if (schedule && (pc != PC_GEN_ASSIGNED))
        VarImp<VIC>::schedule(home,p,me);
    }
  }

  template<class VIC>
  forceinline void
  VarImp<VIC>::subscribe(Space& home, Advisor& a, bool assigned, bool fail) {
    if (!assigned) {
      Advisor* ma = static_cast<Advisor*>(Support::ptrjoin(&a,fail ? 1 : 0));
      enter(home,ma);
    }
  }

  template<class VIC>
  forceinline void
  VarImp<VIC>::reschedule(Space& home, Propagator& p, PropCond pc,
                          bool assigned, ModEvent me) {
    if (assigned)
      VarImp<VIC>::schedule(home,p,ME_GEN_ASSIGNED);
    else if (pc != PC_GEN_ASSIGNED)
      VarImp<VIC>::schedule(home,p,me);
  }

  template<class VIC>
  void
  VarImp<VIC>::remove(Space& home, Propagator* p, PropCond pc) {
    assert(pc <= pc_max);
    ActorLink* a = ActorLink::cast(p);
    // Find actor in dependency array
    ActorLink** f = actor(pc);
#ifdef GECODE_AUDIT
    while (f < actorNonZero(pc+1))
      if (*f == a)
        goto found;
      else
        f++;
    GECODE_NEVER;
  found: ;
#else
    while (*f != a) f++;
#endif
    // Remove actor
    *f = *(actorNonZero(pc+1)-1);
    for (PropCond j = pc+1; j< pc_max+1; j++) {
      *(actorNonZero(j)-1) = *(actorNonZero(j+1)-1);
      idx(j)--;
    }
    *(actorNonZero(pc_max+1)-1) = b.base[entries-1];
    idx(pc_max+1)--;
    entries--;
    free_and_bits += 1 << free_bits;
    home.pc.p.n_sub -= 1;
  }

  template<class VIC>
  forceinline void
  VarImp<VIC>::cancel(Space& home, Propagator& p, PropCond pc) {
    if (b.base != NULL)
      remove(home,&p,pc);
  }

  template<class VIC>
  void
  VarImp<VIC>::remove(Space& home, Advisor* a) {
    // Note that a might be a marked pointer
    // Find actor in dependency array
    ActorLink** f = actorNonZero(pc_max+1);
#ifdef GECODE_AUDIT
    while (f < b.base+entries)
      if (*f == a)
        goto found;
      else
        f++;
    GECODE_NEVER;
  found: ;
#else
    while (*f != a) f++;
#endif
    // Remove actor
    *f = b.base[--entries];
    free_and_bits += 1 << free_bits;
    home.pc.p.n_sub -= 1;
  }

  template<class VIC>
  forceinline void
  VarImp<VIC>::cancel(Space& home, Advisor& a, bool fail) {
    if (b.base != NULL) {
      Advisor* ma = static_cast<Advisor*>(Support::ptrjoin(&a,fail ? 1 : 0));
      remove(home,ma);
    }
  }

  template<class VIC>
  forceinline void
  VarImp<VIC>::cancel(Space& home) {
    unsigned int n_sub = degree();
    home.pc.p.n_sub -= n_sub;
    unsigned int n = (free_and_bits >> free_bits) + n_sub;
    home.free<ActorLink*>(b.base,n);
    // Must be NULL such that cloning works
    b.base = NULL;
    // Must be 0 such that degree works
    entries = 0;
    // Must be NULL such that afc works
    for (PropCond pc=1; pc<pc_max+2; pc++)
      idx(pc) = 0;
    free_and_bits &= (1 << free_bits) - 1;
  }

  template<class VIC>
  forceinline bool
  VarImp<VIC>::advise(Space& home, ModEvent me, Delta& d) {
    /*
     * An advisor that is executed might remove itself due to subsumption.
     * As entries are removed from front to back, the advisors must
     * be iterated in forward direction.
     */
    ActorLink** la = actorNonZero(pc_max+1);
    ActorLink** le = b.base+entries;
    if (la == le)
      return true;
    d.me = me;
    // An advisor that is run, might be removed during execution.
    // As removal is done from the back the advisors have to be executed
    // in inverse order.
    do {
      Advisor* a = Advisor::cast
        (static_cast<ActorLink*>(Support::funmark(*la)));
      assert(!a->disposed());
      Propagator& p = a->propagator();
      switch (p.advise(home,*a,d)) {
      case ES_FIX:
        break;
      case ES_FAILED:
        return false;
      case ES_NOFIX:
        schedule(home,p,me);
        break;
      case ES_NOFIX_FORCE:
        schedule(home,p,me,true);
        break;
      case __ES_SUBSUMED:
      default:
        GECODE_NEVER;
      }
    } while (++la < le);
    return true;
  }

  template<class VIC>
  void
  VarImp<VIC>::_fail(Space& home) {
    /*
     * An advisor that is executed might remove itself due to subsumption.
     * As entries are removed from front to back, the advisors must
     * be iterated in forward direction.
     */
    ActorLink** la = actorNonZero(pc_max+1);
    ActorLink** le = b.base+entries;
    if (la == le)
      return;
    // An advisor that is run, might be removed during execution.
    // As removal is done from the back the advisors have to be executed
    // in inverse order.
    do {
      if (Support::marked(*la)) {
        Advisor* a = Advisor::cast(static_cast<ActorLink*>
                                   (Support::unmark(*la)));
        assert(!a->disposed());
        Propagator& p = a->propagator();
        p.advise(home,*a);
      }
    } while (++la < le);
  }

  template<class VIC>
  ModEvent
  VarImp<VIC>::fail(Space& home) {
    _fail(home); 
    return ME_GEN_FAILED;
  }

  template<class VIC>
  forceinline void
  VarImp<VIC>::update(VarImp<VIC>* x, ActorLink**& sub) {
    // this refers to the variable to be updated (clone)
    // x refers to the original
    // Recover from copy
    x->b.base = b.base;
    x->u.idx[0] = u.idx[0];
    if (pc_max > 0 && sizeof(ActorLink**) > sizeof(unsigned int))
      x->u.idx[1] = u.idx[1];

    unsigned int np =
      static_cast<unsigned int>(x->actorNonZero(pc_max+1) - x->actor(0));
    unsigned int na = 
      static_cast<unsigned int >(x->b.base + x->entries - 
                                 x->actorNonZero(pc_max+1));
    unsigned int n  = na + np;
    assert(n == x->degree());

    ActorLink** f = x->b.base;
    ActorLink** t = sub;

    sub += n;
    b.base = t;
    // Process propagator subscriptions
    while (np >= 4) {
      ActorLink* p3 = f[3]->prev();
      ActorLink* p0 = f[0]->prev();
      ActorLink* p1 = f[1]->prev();
      ActorLink* p2 = f[2]->prev(); 
      t[0] = p0; t[1] = p1; t[2] = p2; t[3] = p3;
      np -= 4; t += 4; f += 4;
    }
    if (np >= 2) {
      ActorLink* p0 = f[0]->prev();
      ActorLink* p1 = f[1]->prev();
      t[0] = p0; t[1] = p1;
      np -= 2; t += 2; f += 2;
    }
    if (np > 0) {
      ActorLink* p0 = f[0]->prev();
      t[0] = p0;
      t += 1; f += 1;
    }
    // Process advisor subscriptions
    while (na >= 4) {
      ptrdiff_t m0, m1, m2, m3;
      ActorLink* p3 =
        static_cast<ActorLink*>(Support::ptrsplit(f[3],m3))->prev();
      ActorLink* p0 = 
        static_cast<ActorLink*>(Support::ptrsplit(f[0],m0))->prev();
      ActorLink* p1 =
        static_cast<ActorLink*>(Support::ptrsplit(f[1],m1))->prev();
      ActorLink* p2 =
        static_cast<ActorLink*>(Support::ptrsplit(f[2],m2))->prev();
      t[0] = static_cast<ActorLink*>(Support::ptrjoin(p0,m0));
      t[1] = static_cast<ActorLink*>(Support::ptrjoin(p1,m1));
      t[2] = static_cast<ActorLink*>(Support::ptrjoin(p2,m2));
      t[3] = static_cast<ActorLink*>(Support::ptrjoin(p3,m3));
      na -= 4; t += 4; f += 4;
    }
    if (na >= 2) {
      ptrdiff_t m0, m1;
      ActorLink* p0 = 
        static_cast<ActorLink*>(Support::ptrsplit(f[0],m0))->prev();
      ActorLink* p1 =
        static_cast<ActorLink*>(Support::ptrsplit(f[1],m1))->prev();
      t[0] = static_cast<ActorLink*>(Support::ptrjoin(p0,m0));
      t[1] = static_cast<ActorLink*>(Support::ptrjoin(p1,m1));
      na -= 2; t += 2; f += 2;
    }
    if (na > 0) {
      ptrdiff_t m0;
      ActorLink* p0 = 
        static_cast<ActorLink*>(Support::ptrsplit(f[0],m0))->prev();
      t[0] = static_cast<ActorLink*>(Support::ptrjoin(p0,m0));
    }
  }

  template<class VIC>
  forceinline void
  VarImp<VIC>::update(Space& home, ActorLink**& sub) {
    VarImp<VIC>* x = static_cast<VarImp<VIC>*>(home.pc.c.vars_u[idx_c]);
    while (x != NULL) {
      VarImp<VIC>* n = x->next(); x->forward()->update(x,sub); x = n;
    }
  }



  /*
   * Variable disposer
   *
   */
  template<class VarImp>
  VarImpDisposer<VarImp>::VarImpDisposer(void) {
#ifdef GECODE_HAS_VAR_DISPOSE
    Space::vd[VarImp::idx_d] = this;
#endif
  }

  template<class VarImp>
  void
  VarImpDisposer<VarImp>::dispose(Space& home, VarImpBase* _x) {
    VarImp* x = static_cast<VarImp*>(_x);
    do {
      x->dispose(home); x = static_cast<VarImp*>(x->next_d());
    } while (x != NULL);
  }

  /*
   * Statistics
   */

  forceinline void
  StatusStatistics::reset(void) {
    propagate = 0;
  }
  forceinline
  StatusStatistics::StatusStatistics(void) {
    reset();
  }
  forceinline StatusStatistics&
  StatusStatistics::operator +=(const StatusStatistics& s) {
    propagate += s.propagate;
    return *this;
  }
  forceinline StatusStatistics
  StatusStatistics::operator +(const StatusStatistics& s) {
    StatusStatistics t(s);
    return t += *this;
  }

  forceinline void
  CloneStatistics::reset(void) {}

  forceinline
  CloneStatistics::CloneStatistics(void) {
    reset();
  }
  forceinline CloneStatistics
  CloneStatistics::operator +(const CloneStatistics&) {
    CloneStatistics s;
    return s;
  }
  forceinline CloneStatistics&
  CloneStatistics::operator +=(const CloneStatistics&) {
    return *this;
  }

  forceinline void
  CommitStatistics::reset(void) {}

  forceinline
  CommitStatistics::CommitStatistics(void) {
    reset();
  }
  forceinline CommitStatistics
  CommitStatistics::operator +(const CommitStatistics&) {
    CommitStatistics s;
    return s;
  }
  forceinline CommitStatistics&
  CommitStatistics::operator +=(const CommitStatistics&) {
    return *this;
  }

  /*
   * Cost computation
   *
   */

  forceinline
  PropCost::PropCost(PropCost::ActualCost ac0) : ac(ac0) {}

  forceinline PropCost
  PropCost::cost(PropCost::Mod m,
                 PropCost::ActualCost lo, PropCost::ActualCost hi,
                 unsigned int n) {
    if (n < 2)
      return (m == LO) ? AC_UNARY_LO : AC_UNARY_HI;
    else if (n == 2)
      return (m == LO) ? AC_BINARY_LO : AC_BINARY_HI;
    else if (n == 3)
      return (m == LO) ? AC_TERNARY_LO : AC_TERNARY_HI;
    else
      return (m == LO) ? lo : hi;
  }

  forceinline PropCost
  PropCost::record(void) {
    return AC_RECORD;
  }
  forceinline PropCost
  PropCost::crazy(PropCost::Mod m, unsigned int n) {
    return cost(m,AC_CRAZY_LO,AC_CRAZY_HI,n);
  }
  forceinline PropCost
  PropCost::crazy(PropCost::Mod m, int n) {
    assert(n >= 0);
    return crazy(m,static_cast<unsigned int>(n));
  }
  forceinline PropCost
  PropCost::cubic(PropCost::Mod m, unsigned int n) {
    return cost(m,AC_CUBIC_LO,AC_CUBIC_HI,n);
  }
  forceinline PropCost
  PropCost::cubic(PropCost::Mod m, int n) {
    assert(n >= 0);
    return cubic(m,static_cast<unsigned int>(n));
  }
  forceinline PropCost
  PropCost::quadratic(PropCost::Mod m, unsigned int n) {
    return cost(m,AC_QUADRATIC_LO,AC_QUADRATIC_HI,n);
  }
  forceinline PropCost
  PropCost::quadratic(PropCost::Mod m, int n) {
    assert(n >= 0);
    return quadratic(m,static_cast<unsigned int>(n));
  }
  forceinline PropCost
  PropCost::linear(PropCost::Mod m, unsigned int n) {
    return cost(m,AC_LINEAR_LO,AC_LINEAR_HI,n);
  }
  forceinline PropCost
  PropCost::linear(PropCost::Mod m, int n) {
    assert(n >= 0);
    return linear(m,static_cast<unsigned int>(n));
  }
  forceinline PropCost
  PropCost::ternary(PropCost::Mod m) {
    return (m == LO) ? AC_TERNARY_LO : AC_TERNARY_HI;
  }
  forceinline PropCost
  PropCost::binary(PropCost::Mod m) {
    return (m == LO) ? AC_BINARY_LO : AC_BINARY_HI;
  }
  forceinline PropCost
  PropCost::unary(PropCost::Mod m) {
    return (m == LO) ? AC_UNARY_LO : AC_UNARY_HI;
  }

  /*
   * Iterators for propagators and branchers of a space
   *
   */
  forceinline
  Space::Propagators::Propagators(Space& home0)
    : home(home0), q(home.pc.p.active) {
    while (q >= &home.pc.p.queue[0]) {
      if (q->next() != q) {
        c = q->next(); e = q; q--;
        return;
      }
      q--;
    }
    q = NULL;
    if (!home.pl.empty()) {
      c = Propagator::cast(home.pl.next());
      e = Propagator::cast(&home.pl);
    } else {
      c = e = NULL;
    }
  }
  forceinline bool
  Space::Propagators::operator ()(void) const {
    return c != NULL;
  }
  forceinline void
  Space::Propagators::operator ++(void) {
    c = c->next();
    if (c == e) {
      if (q == NULL) {
        c = NULL;
      } else {
        while (q >= &home.pc.p.queue[0]) {
          if (q->next() != q) {
            c = q->next(); e = q; q--;
            return;
          }
          q--;
        }
        q = NULL;
        if (!home.pl.empty()) {
          c = Propagator::cast(home.pl.next());
          e = Propagator::cast(&home.pl);
        } else {
          c = NULL;
        }
      }
    }
  }
  forceinline Propagator&
  Space::Propagators::propagator(void) const {
    return *Propagator::cast(c);
  }


  forceinline
  Space::ScheduledPropagators::ScheduledPropagators(Space& home0)
    : home(home0), q(home.pc.p.active) {
    while (q >= &home.pc.p.queue[0]) {
      if (q->next() != q) {
        c = q->next(); e = q; q--;
        return;
      }
      q--;
    }
    q = c = e = NULL;
  }
  forceinline bool
  Space::ScheduledPropagators::operator ()(void) const {
    return c != NULL;
  }
  forceinline void
  Space::ScheduledPropagators::operator ++(void) {
    c = c->next();
    if (c == e) {
      if (q == NULL) {
        c = NULL;
      } else {
        while (q >= &home.pc.p.queue[0]) {
          if (q->next() != q) {
            c = q->next(); e = q; q--;
            return;
          }
          q--;
        }
        q = c = e = NULL;
      }
    }
  }
  forceinline Propagator&
  Space::ScheduledPropagators::propagator(void) const {
    return *Propagator::cast(c);
  }


  forceinline
  Space::IdlePropagators::IdlePropagators(Space& home) {
    c = Propagator::cast(home.pl.next());
    e = Propagator::cast(&home.pl);
  }
  forceinline bool
  Space::IdlePropagators::operator ()(void) const {
    return c != e;
  }
  forceinline void
  Space::IdlePropagators::operator ++(void) {
    c = c->next();
  }
  forceinline Propagator&
  Space::IdlePropagators::propagator(void) const {
    return *Propagator::cast(c);
  }


  forceinline
  Space::Branchers::Branchers(Space& home)
    : c(Brancher::cast(home.bl.next())), e(&home.bl) {}
  forceinline bool
  Space::Branchers::operator ()(void) const {
    return c != e;
  }
  forceinline void
  Space::Branchers::operator ++(void) {
    c = c->next();
  }
  forceinline Brancher&
  Space::Branchers::brancher(void) const {
    return *Brancher::cast(c);
  }


  /*
   * Groups of actors
   */
  forceinline
  Group::Group(unsigned int gid0) : gid(gid0) {}

  forceinline bool
  Group::in(Group actor) const {
    return (gid == GROUPID_ALL) || (gid == actor.gid);
  }

  forceinline bool
  Group::in(void) const {
    return (gid != GROUPID_ALL) && (gid != GROUPID_DEF);
  }

  forceinline
  Group::Group(const Group& g) : gid(g.gid) {}

  forceinline Group&
  Group::operator =(const Group& g) {
    gid=g.gid; return *this;
  }

  forceinline unsigned int
  Group::id(void) const {
    return gid;
  }


  forceinline
  PropagatorGroup::PropagatorGroup(void) {}

  forceinline
  PropagatorGroup::PropagatorGroup(unsigned int gid)
    : Group(gid) {}

  forceinline
  PropagatorGroup::PropagatorGroup(const PropagatorGroup& g)
    : Group(g) {}

  forceinline PropagatorGroup&
  PropagatorGroup::operator =(const PropagatorGroup& g) {
    return static_cast<PropagatorGroup&>(Group::operator =(g));
  }

  forceinline Home
  PropagatorGroup::operator ()(Space& home) {
    return Home(home,NULL,*this,BrancherGroup::def);
  }

  forceinline bool
  PropagatorGroup::operator ==(PropagatorGroup g) const {
    return id() == g.id();
  }
  forceinline bool
  PropagatorGroup::operator !=(PropagatorGroup g) const {
    return id() != g.id();
  }

  forceinline PropagatorGroup&
  PropagatorGroup::move(Space& , Propagator& p) {
    if (id() != GROUPID_ALL)
      p.group(*this);
    return *this;
  }


  forceinline
  BrancherGroup::BrancherGroup(void) {}

  forceinline
  BrancherGroup::BrancherGroup(unsigned int gid)
    : Group(gid) {}

  forceinline
  BrancherGroup::BrancherGroup(const BrancherGroup& g)
    : Group(g) {}

  forceinline BrancherGroup&
  BrancherGroup::operator =(const BrancherGroup& g) {
    return static_cast<BrancherGroup&>(Group::operator =(g));
  }

  forceinline Home
  BrancherGroup::operator ()(Space& home) {
    return Home(home,NULL,PropagatorGroup::def,*this);
  }

  forceinline bool
  BrancherGroup::operator ==(BrancherGroup g) const {
    return id() == g.id();
  }
  forceinline bool
  BrancherGroup::operator !=(BrancherGroup g) const {
    return id() != g.id();
  }

  forceinline BrancherGroup&
  BrancherGroup::move(Space& , Brancher& p) {
    if (id() != GROUPID_ALL)
      p.group(*this);
    return *this;
  }


  /*
   * Iterators for propagators and branchers in a group
   *
   */
  forceinline
  Propagators::Propagators(Space& home, PropagatorGroup g0)
    : ps(home), g(g0) {
    while (ps() && !g.in(ps.propagator().group()))
      ++ps;
  }
  forceinline bool
  Propagators::operator ()(void) const {
    return ps();
  }
  forceinline void
  Propagators::operator ++(void) {
    do
      ++ps;
    while (ps() && !g.in(ps.propagator().group()));
  }
  forceinline const Propagator&
  Propagators::propagator(void) const {
    return ps.propagator();
  }

  forceinline
  Branchers::Branchers(Space& home, BrancherGroup g0)
    : bs(home), g(g0) {
    while (bs() && !g.in(bs.brancher().group()))
      ++bs;
  }
  forceinline bool
  Branchers::operator ()(void) const {
    return bs();
  }
  forceinline void
  Branchers::operator ++(void) {
    do
      ++bs;
    while (bs() && !g.in(bs.brancher().group()));
  }
  forceinline const Brancher&
  Branchers::brancher(void) const {
    return bs.brancher();
  }


  /*
   * Space construction support
   *
   */
  template<class T>
  forceinline T&
  Space::construct(void) {
    return alloc<T>(1);
  }
  template<class T, typename A1>
  forceinline T&
  Space::construct(A1 const& a1) {
    T& t = *static_cast<T*>(ralloc(sizeof(T)));
    new (&t) T(a1);
    return t;
  }
  template<class T, typename A1, typename A2>
  forceinline T&
  Space::construct(A1 const& a1, A2 const& a2) {
    T& t = *static_cast<T*>(ralloc(sizeof(T)));
    new (&t) T(a1,a2);
    return t;
  }
  template<class T, typename A1, typename A2, typename A3>
  forceinline T&
  Space::construct(A1 const& a1, A2 const& a2, A3 const& a3) {
    T& t = *static_cast<T*>(ralloc(sizeof(T)));
    new (&t) T(a1,a2,a3);
    return t;
  }
  template<class T, typename A1, typename A2, typename A3, typename A4>
  forceinline T&
  Space::construct(A1 const& a1, A2 const& a2, A3 const& a3, A4 const& a4) {
    T& t = *static_cast<T*>(ralloc(sizeof(T)));
    new (&t) T(a1,a2,a3,a4);
    return t;
  }
  template<class T, typename A1, typename A2, typename A3, typename A4, typename A5>
  forceinline T&
  Space::construct(A1 const& a1, A2 const& a2, A3 const& a3, A4 const& a4, A5 const& a5) {
    T& t = *static_cast<T*>(ralloc(sizeof(T)));
    new (&t) T(a1,a2,a3,a4,a5);
    return t;
  }

}

// STATISTICS: kernel-core