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: 2012-02-22 06:18:28 +0100 (Wed, 22 Feb 2012) $ by $Author: tack $
 *     $Revision: 12538 $
 *
 *  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 {
      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);
      static void* operator new(size_t s);
      static void  operator delete(void* p);
    };
  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 LocalObject;
  class Advisor;
  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;
  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);
#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,
                bool assigned);
    void subscribe(Space& home, Advisor& a, bool assigned);
    void cancel(Space& home, Advisor& a, bool assigned);

    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 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_CRAZY_LO     = 0, 
      AC_CRAZY_HI     = 0, 
      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 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)
  };


  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);
  public:
    virtual Actor* copy(Space& home, bool share) = 0;



    GECODE_KERNEL_EXPORT
    virtual size_t allocated(void) const;
    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);
  private:
#ifndef __GNUC__

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

    static void* operator new(size_t s);
#ifdef __GNUC__
  public:
    GECODE_KERNEL_EXPORT virtual ~Actor(void);
    static void  operator delete(void* p);
#endif
  };



  class Home {
  protected:
    Space& s;
    Propagator* p;
  public:


    Home(Space& s, Propagator* p=NULL);
    operator Space&(void);



    Home operator ()(Propagator& p);
    Propagator* propagator(void) const;



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

  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;
  private:
    union {
      ModEventDelta med;
      size_t size;
      Gecode::ActorLink* advisors;
    } u;
    PropInfo& pi;
    static Propagator* cast(ActorLink* al);
    static const Propagator* cast(const ActorLink* al);
  protected:
    Propagator(Home home);
    Propagator(Space& home, bool share, Propagator& p);

  public:


    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);



    double afc(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;
  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);



    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 Brancher;
  class GECODE_VTABLE_EXPORT Choice {
    friend class Space;
  private:
    unsigned int _id;  
    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;
    static void* operator new(size_t);
    static void  operator delete(void*);
    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 _id;
    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;
    unsigned int id(void) const;
  };

  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);
  };


  enum SpaceStatus {
    SS_FAILED, 
    SS_SOLVED, 
    SS_BRANCH  
  };

  class StatusStatistics {
  public:
    unsigned long int propagate;
    bool wmp;
    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 {
    friend class Actor;
    friend class Propagator;
    friend class Brancher;
    friend class Advisor;
    template<class VIC> friend class VarImp;
    template<class VarImp> friend class VarImpDisposer;
    friend class SharedHandle;
    friend class LocalObject;
    friend class Region;
  private:
    SharedMemory* sm;
    MemoryManager mm;
    GlobalPropInfo gpi;
    ActorLink pl;
    ActorLink bl;
    Brancher* b_status;
    Brancher* b_commit;
    union {
      struct {
        ActorLink* active;
        ActorLink queue[PropCost::AC_MAX+1];
        unsigned int branch_id;
        unsigned int n_sub;
      } 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);

    Actor** d_fst;
    Actor** d_cur;
    Actor** d_lst;
    GECODE_KERNEL_EXPORT void d_resize(void);

    unsigned int n_wmp;

    GECODE_KERNEL_EXPORT static StatusStatistics unused_status;
    GECODE_KERNEL_EXPORT static CloneStatistics unused_clone;
    GECODE_KERNEL_EXPORT static CommitStatistics unused_commit;
    GECODE_KERNEL_EXPORT static unsigned long int unused_uli;
    GECODE_KERNEL_EXPORT static bool unused_b;

    GECODE_KERNEL_EXPORT Space* _clone(bool share=true);

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

  public:
    GECODE_KERNEL_EXPORT Space(void);
    GECODE_KERNEL_EXPORT virtual ~Space(void);
    GECODE_KERNEL_EXPORT Space(bool share, Space& s);
    virtual Space* copy(bool share) = 0;
    GECODE_KERNEL_EXPORT virtual void constrain(const Space& best);
    static void* operator new(size_t);
    static void  operator delete(void*);


    /*
     * 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=true, CloneStatistics& stat=unused_clone) const;

    void commit(const Choice& c, unsigned int a,
                CommitStatistics& stat=unused_commit);

    void notice(Actor& a, ActorProperty p);
    void ignore(Actor& a, ActorProperty p);


    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;
    GECODE_KERNEL_EXPORT unsigned int propagators(void) const;
    GECODE_KERNEL_EXPORT unsigned int branchers(void) const;



    Home operator ()(Propagator& p);

    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);
    size_t allocated(void) const;
    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);

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

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




  /*
   * Memory management
   *
   */

  // Heap allocated
  forceinline void*
  SharedHandle::Object::operator new(size_t s) {
    return heap.ralloc(s);
  }
  forceinline void
  SharedHandle::Object::operator delete(void* p) {
    heap.rfree(p);
  }

  forceinline void*
  Space::operator new(size_t s) {
    return heap.ralloc(s);
  }
  forceinline void
  Space::operator delete(void* p) {
    heap.rfree(p);
  }

  forceinline void
  Choice::operator delete(void* p) {
    heap.rfree(p);
  }
  forceinline void*
  Choice::operator new(size_t s) {
    return heap.ralloc(s);
  }

  // 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);
  }

  forceinline size_t
  Space::allocated(void) const {
    size_t s = mm.allocated();
    for (Actor** a = d_fst; a < d_cur; a++)
      s += (*a)->allocated();
    return s;
  }

  /*
   * 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);
  }

  /*
   * 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();
  }



  /*
   * 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
  Space::notice(Actor& a, ActorProperty p) {
    if (p & AP_DISPOSE) {
      if (d_cur == d_lst)
        d_resize();
      *(d_cur++) = &a;
    }
    if (p & AP_WEAKLY) {
      if (n_wmp == 0)
        n_wmp = 2;
      else
        n_wmp++;
    }
  }

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

  forceinline void
  Space::ignore(Actor& a, ActorProperty p) {
    if (p & AP_DISPOSE) {
      // Check wether array has already been discarded as space
      // deletion is already in progress
      Actor** f = d_fst;
      if (f != NULL) {
        while (&a != *f)
          f++;
        *f = *(--d_cur);
      }
    }
    if (p & AP_WEAKLY) {
      assert(n_wmp > 1);
      n_wmp--;
    }
  }

  forceinline Space*
  Space::clone(bool share, 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);
  }

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

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


  /*
   * Home for posting actors
   *
   */
  forceinline
  Home::Home(Space& s0, Propagator* p0) : s(s0), p(p0) {}
  forceinline
  Home::operator Space&(void) { 
    return s; 
  }
  forceinline Home
  Home::operator ()(Propagator& p) {
    return Home(s,&p);
  }
  forceinline Home
  Space::operator ()(Propagator& p) {
    return Home(*this,&p);
  }
  forceinline Propagator*
  Home::propagator(void) const {
    return p;
  }

  /*
   * 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(Home home) 
    : pi((home.propagator() != NULL) ?
         // Inherit propagator information
         home.propagator()->pi :
         // New propagator information
         static_cast<Space&>(home).gpi.allocate()) {
    u.advisors = NULL;
    assert((u.med == 0) && (u.size == 0));
    static_cast<Space&>(home).pl.head(this);
  }

  forceinline
  Propagator::Propagator(Space&, bool, Propagator& p) 
    : pi(p.pi) {
    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 pi.afc();
  }

  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) :
    _id(static_cast<Space&>(home).pc.p.branch_id++) {
    if (static_cast<Space&>(home).pc.p.branch_id == 0U)
      throw TooManyBranchers("Brancher::Brancher");
    // If no brancher available, make it the first one
    if (static_cast<Space&>(home).b_status == &static_cast<Space&>(home).bl) {
      static_cast<Space&>(home).b_status = this;
      if (static_cast<Space&>(home).b_commit == &static_cast<Space&>(home).bl)
        static_cast<Space&>(home).b_commit = this;
    }
    static_cast<Space&>(home).bl.tail(this);
  }

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

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

  /*
   * 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) {
    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)
    : _id(b.id()), _alt(a) {}

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

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

  forceinline
  Choice::~Choice(void) {}



  /*
   * 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());
  }

  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]));
  }



  /*
   * 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 {
    if (degree() == 0)
      return 0.0;
    double d = degree();
    // 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(*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>::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) {
    // 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>
  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>
  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) {
    if (!assigned)
      enter(home,&a);
  }

  template<class VIC>
  forceinline 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>::remove(Space& home, Advisor* a) {
    // 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, Propagator& p, PropCond pc, bool assigned) {
    if (!assigned)
      remove(home,&p,pc);
  }

  template<class VIC>
  forceinline void
  VarImp<VIC>::cancel(Space& home, Advisor& a, bool assigned) {
    if (!assigned)
      remove(home,&a);
  }

  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 >> VIC::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;
  }

  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(*la);
      assert(!a->disposed());
      Propagator& p = a->propagator();
      switch (p.advise(home,*a,d)) {
      case ES_FIX:
        break;
      case ES_FAILED:
        p.pi.fail(home.gpi);
        return false;
      case ES_NOFIX:
        schedule(home,p,me);
        break;
      case ES_NOFIX_FORCE:
        schedule(home,p,me,true);
        break;
      default:
        GECODE_NEVER;
      }
    } while (++la < le);
    return true;
  }

  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];

    ActorLink** f = x->b.base;
    unsigned int n = x->degree();
    ActorLink** t = sub;
    sub += n;
    b.base = t;
    // Set subscriptions using actor forwarding pointers
    while (n >= 4) {
      n -= 4;
      t[0]=f[0]->prev(); t[1]=f[1]->prev();
      t[2]=f[2]->prev(); t[3]=f[3]->prev();
      t += 4; f += 4;
    }
    if (n >= 2) {
      n -= 2;
      t[0]=f[0]->prev(); t[1]=f[1]->prev();
      t += 2; f += 2;
    }
    if (n > 0) {
      t[0]=f[0]->prev();
    }
  }

  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;
    wmp = false;
  }
  forceinline
  StatusStatistics::StatusStatistics(void) {
    reset();
  }
  forceinline StatusStatistics&
  StatusStatistics::operator +=(const StatusStatistics& s) { 
    propagate += s.propagate;
    wmp |= s.wmp;
    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::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(const 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 const Propagator& 
  Space::Propagators::propagator(void) const {
    return *Propagator::cast(c);
  }

  forceinline
  Space::Branchers::Branchers(const 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 const Brancher& 
  Space::Branchers::brancher(void) const {
    return *Brancher::cast(c);
  }

  /*
   * 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