core.icc

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>
 *
 *  Copyright:
 *     Christian Schulte, 2002
 *     Guido Tack, 2003
 *     Mikael Lagerkvist, 2006
 *
 *  Bugfixes provided by:
 *     Alexander Samoilov <alexander_samoilov@yahoo.com>
 *
 *  Last modified:
 *     $Date: 2008-07-11 10:27:28 +0200 (Fri, 11 Jul 2008) $ by $Author: tack $
 *     $Revision: 7332 $
 *
 *  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.
 *
 */

namespace Gecode {

  class Space;

  class SharedHandle {
  public:
    class Object {
      friend class Space;
      friend class SharedHandle;
    private:
      unsigned int use_cnt;
      Object* next;
      Object* fwd;
    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(Object* so);
    SharedHandle(const SharedHandle& sh);
    SharedHandle& operator=(const SharedHandle& sh);
    void update(Space* home, bool share, SharedHandle& sh);
    ~SharedHandle(void);
  protected:
    Object* object(void) const;
    void object(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.icc"

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);
    static GECODE_KERNEL_EXPORT const Support::Symbol vti;
  };

  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 Advisor;
  template <class A> class Council;
  template <class A> class Advisors;
  template <class VIC> class VarImp;


  /*
   * Variable implementations
   *
   */

  class VarImpBase {};

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

  template <class VarType>
  class VarDisposer : public VarDisposerBase {
  public:
    VarDisposer(void);
    virtual void dispose(Space* home, VarImpBase* x);
  };

  class Delta {
    template <class VIC> friend class VarImp;
  private:
    ModEvent me; 
  public:
    ModEvent modevent(void) const;
  };

  template <class VIC>
  class VarImp : public VarImpBase {
    friend class Space;
    friend class Propagator;
    template <class VarType> friend class VarDisposer;
  private:
    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 free_and_bits;
    static const Gecode::PropCond pc_max = VIC::pc_max;
    ActorLink** idx[pc_max+3];

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

    void enter(Space* home, ActorLink* a, PropCond pc);
    void resize(Space* home);
    void remove(Space* home, ActorLink* a, PropCond pc);

  protected:
#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* p, bool assigned);
    void cancel(Space* home);
    unsigned int degree(void) const;
    bool advise(Space* home, ModEvent me, Delta* d);



    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);
    static ModEvent me(ModEventDelta med);
    static ModEventDelta med(ModEvent me);
    static ModEvent me_combine(ModEvent me1, ModEvent me2);

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


    static const Support::Symbol vti;
    
  };

  template <class VIC>
  const Support::Symbol
  VarImp<VIC>::vti = VIC::vti;


  namespace Reflection {
    class ActorSpecIter;
    class ActorSpec;
    class BranchingSpec;
    class VarMap;
  }

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

  enum PropCost {
    PC_CRAZY_LO     = 0, 
    PC_CRAZY_HI     = 0, 
    PC_CUBIC_LO     = 1, 
    PC_CUBIC_HI     = 1, 
    PC_QUADRATIC_LO = 2, 
    PC_QUADRATIC_HI = 2, 
    PC_LINEAR_HI    = 3, 
    PC_LINEAR_LO    = 4, 
    PC_TERNARY_HI   = 5, 
    PC_BINARY_HI    = 6, 
    PC_TERNARY_LO   = 6, 
    PC_BINARY_LO    = 7, 
    PC_UNARY_LO     = 7, 
    PC_UNARY_HI     = 7, 
    PC_MAX          = 7  
  };

  class ActorLink {
    friend class Actor;
    friend class Propagator;
    friend class Advisor;
    friend class Branching;
    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);
    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 Branching;
    friend class Reflection::ActorSpecIter;
    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*,bool) = 0;



    GECODE_KERNEL_EXPORT 
    virtual size_t allocated(void) const;
    GECODE_KERNEL_EXPORT
    virtual size_t dispose(Space* home);
    void force(Space* home);
    void unforce(Space* home);
    static void* operator new(size_t s, Space* home);
    static void  operator delete(void* p, Space* home);
    GECODE_KERNEL_EXPORT
    virtual Reflection::ActorSpec spec(const Space* home,
                                       Reflection::VarMap& m) const;
  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
  };


  ExecStatus ES_SUBSUMED(Propagator* p, size_t s);
  ExecStatus ES_SUBSUMED(Propagator* p, Space* home);
  ExecStatus ES_FIX_PARTIAL(Propagator* p, ModEventDelta med);
  ExecStatus ES_NOFIX_PARTIAL(Propagator* p, ModEventDelta med);

  class GECODE_VTABLE_EXPORT Propagator : public Actor {
    friend class ActorLink;
    friend class Space;
    template <class VIC> friend class VarImp;
    friend ExecStatus ES_SUBSUMED(Propagator*, size_t);
    friend ExecStatus ES_SUBSUMED(Propagator*, Space*);
    friend ExecStatus ES_FIX_PARTIAL(Propagator*, ModEventDelta);
    friend ExecStatus ES_NOFIX_PARTIAL(Propagator*, ModEventDelta);
    friend class Advisor;
    template <class A> friend class Council;
  private:
    union {
      ModEventDelta med;
      size_t size;
      Gecode::ActorLink* advisors;
    } u;
    static Propagator* cast(ActorLink* al);
    static const Propagator* cast(const ActorLink* al);
  protected:
    Propagator(Space* home);
    Propagator(Space* home, bool share, Propagator& p);

  public:


    virtual ExecStatus propagate(Space* home, ModEventDelta med) = 0;
    virtual PropCost cost(ModEventDelta med) const  = 0;
    GECODE_KERNEL_EXPORT
    virtual ExecStatus advise(Space* home, Advisor* a, const Delta* d);
  };


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


  template <class A>
  ExecStatus ES_SUBSUMED_FIX(A* a, Space* home, Council<A>& c);
  template <class A>
  ExecStatus ES_SUBSUMED_NOFIX(A* a, Space* home, Council<A>& c);

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

  class BranchingDesc {
    friend class Space;
    friend class Reflection::BranchingSpec;
  private:
    unsigned int _id;  
    unsigned int _alt; 

    unsigned int id(void) const;
  protected:
    BranchingDesc(const Branching* b, const unsigned int a);
  public:
    unsigned int alternatives(void) const;
    GECODE_KERNEL_EXPORT virtual ~BranchingDesc(void);
    virtual size_t size(void) const = 0;
    static void* operator new(size_t);
    static void  operator delete(void*);
  };

  class GECODE_VTABLE_EXPORT Branching : public Actor {
    friend class ActorLink;
    friend class Space;
    friend class BranchingDesc;
    friend class Reflection::ActorSpecIter;
  private:
    unsigned int id; 
    static Branching* cast(ActorLink* al);
    static const Branching* cast(const ActorLink* al);
  protected:
    Branching(Space* home);
    Branching(Space* home, bool share, Branching& b);

  public:


    virtual bool status(const Space* home) const = 0;
    virtual const BranchingDesc* description(const Space* home) const = 0;
    virtual ExecStatus commit(Space* home, const BranchingDesc* d,
                              unsigned int a) = 0;
    


    virtual GECODE_KERNEL_EXPORT Reflection::BranchingSpec
    branchingSpec(const Space* home,
                  Reflection::VarMap& m, const BranchingDesc* d) const;
  };



  enum SpaceStatus {
    SS_FAILED, 
    SS_SOLVED, 
    SS_BRANCH  
  };

  class GECODE_VTABLE_EXPORT Space {
    friend class Actor;
    friend class Propagator;
    friend class Branching;
    friend class Advisor;
    friend class Reflection::ActorSpecIter;
    template <class VIC> friend class VarImp;
    template <class VarType> friend class VarDisposer;
    friend class SharedHandle;
  private:
    MemoryManager mm; 
    ActorLink a_actors;
    Branching* b_status;
    Branching* b_commit;
    union {
      struct {
        ActorLink* active;
        ActorLink queue[PC_MAX+1];
        unsigned int branch_id;
        unsigned int n_sub;
      } p;
      struct {
        VarImpBase* vars_u[AllVarConf::idx_c];
        VarImpBase* vars_noidx;
        SharedHandle::Object* shared;
      } c;
    } pc;
    void enqueue(Propagator* p);
#ifdef GECODE_HAS_VAR_DISPOSE
    GECODE_KERNEL_EXPORT static VarDisposerBase* 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);

    GECODE_KERNEL_EXPORT static unsigned long int unused_uli;
  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;
    static void* operator new(size_t);
    static void  operator delete(void*);


    /*
     * Member functions for search engines
     *
     */

    GECODE_KERNEL_EXPORT SpaceStatus status(unsigned long int& pn=unused_uli);

    const BranchingDesc* description(void) const;

    GECODE_KERNEL_EXPORT Space* clone(bool share=true);

    GECODE_KERNEL_EXPORT void commit(const BranchingDesc* d, unsigned int 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 branchings(void) const;


    GECODE_KERNEL_EXPORT
    virtual void getVars(Reflection::VarMap& m, bool registerOnly);
    GECODE_KERNEL_EXPORT
    Reflection::BranchingSpec branchingSpec(Reflection::VarMap& m,
                                            const BranchingDesc* d) const;


    void* alloc(size_t);
    void  reuse(void*,size_t);
    template <size_t> void* fl_alloc(void);
    template <size_t> void  fl_dispose(FreeList* f, FreeList* l);
    GECODE_KERNEL_EXPORT 
    size_t allocated(void) const;
  };




  /*
   * Memory management
   *
   */

  // Heap allocated
  forceinline void* 
  SharedHandle::Object::operator new(size_t s) {
    return Memory::malloc(s);
  }
  forceinline void
  SharedHandle::Object::operator delete(void* p) {
    Memory::free(p);
  }

  forceinline void*
  Space::operator new(size_t s) {
    return Memory::malloc(s);
  }
  forceinline void
  Space::operator delete(void* p) {
    Memory::free(p);
  }

  forceinline void
  BranchingDesc::operator delete(void* p) {
    Memory::free(p);
  }
  forceinline void*
  BranchingDesc::operator new(size_t s) {
    return Memory::malloc(s);
  }

  // Space allocation: general space heaps and free lists
  forceinline void*
  Space::alloc(size_t s) {
    return mm.alloc(s);
  }
  forceinline void
  Space::reuse(void* p, size_t s) {
    return mm.reuse(p,s);
  }
  template <size_t s>
  forceinline void*
  Space::fl_alloc(void) {
    return mm.template fl_alloc<s>();
  }
  template <size_t s>
  forceinline void
  Space::fl_dispose(FreeList* f, FreeList* l) {
    mm.template fl_dispose<s>(f,l);
  }

#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->alloc(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->alloc(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->alloc(s);
  }


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

  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 
  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;
    } else if (share) {
      o = sh.o; subscribe();
    } else if (sh.o->fwd != NULL) {
      o = sh.o->fwd; subscribe();
    } 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();
  }
  forceinline SharedHandle::Object* 
  SharedHandle::object(void) const {
    return o;
  }
  forceinline void 
  SharedHandle::object(SharedHandle::Object* n) {
    if (n != o) {
      cancel(); o=n; subscribe();
    }
  }



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

  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
  Actor::force(Space* home) {
    if (home->d_cur == home->d_lst)
      home->d_resize();
    *(home->d_cur++) = this;
  }

  forceinline void
  Actor::unforce(Space* home) {
    // Check wether array has already been discarded as space
    // deletion is already in progress
    Actor** f = home->d_fst;
    if (f != NULL) {
      while (this != *f)
        f++;
      *f = *(--home->d_cur);
    }
  }

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


  /*
   * 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(Space* home) {
    u.advisors = NULL;
    assert(u.med == 0 && u.size == 0);
    home->a_actors.head(this);
  }

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

  forceinline ExecStatus
  ES_SUBSUMED(Propagator* p, size_t s) {
    p->u.size = s; 
    return __ES_SUBSUMED;
  }

  forceinline ExecStatus
  ES_SUBSUMED(Propagator* p, Space* home) {
    p->u.size = p->dispose(home); 
    return __ES_SUBSUMED;
  }

  forceinline ExecStatus
  ES_FIX_PARTIAL(Propagator* p, ModEventDelta med) {
    p->u.med = med; 
    assert(p->u.med != 0);
    return __ES_PARTIAL;
  }

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



  /*
   * Branching
   *
   */
  forceinline Branching* 
  Branching::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<Branching*>(&t);
  }

  forceinline const Branching* 
  Branching::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 Branching*>(&t);
  }

  forceinline
  Branching::Branching(Space* home) {
    // Propagators are put at the tail of the link of actors
    id = home->pc.p.branch_id++;
    // If no branching available, make it the first one
    if (home->b_status == &(home->a_actors)) {
      home->b_status = this;
      if (home->b_commit == &(home->a_actors))
        home->b_commit = this;
    }
    home->a_actors.tail(this);
  }

  forceinline
  Branching::Branching(Space*, bool, Branching& b)
    : id(b.id)  {
    // Set forwarding pointer
    b.prev(this);
  }



  /*
   * Branching description
   *
   */
  forceinline
  BranchingDesc::BranchingDesc(const Branching* b, const unsigned int a)
    : _id(b->id), _alt(a) {}

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

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

  forceinline
  BranchingDesc::~BranchingDesc(void) {}



  /*
   * Delta information for advisors
   *
   */
  forceinline ModEvent
  Delta::modevent(void) const {
    return me;
  }



  /*
   * Advisor
   *
   */
  template <class A>
  forceinline 
  Advisor::Advisor(Space*, Propagator* p, Council<A>& c) {
    assert(p != NULL);
    // 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
  ES_SUBSUMED_FIX(A* a, Space* home, Council<A>& c) {
    a->dispose(home,c);
    return ES_FIX;
  }

  template <class A>
  forceinline ExecStatus
  ES_SUBSUMED_NOFIX(A* a, Space* home, Council<A>& c) {
    a->dispose(home,c);
    return ES_NOFIX;
  }



  /*
   * 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;
    }
  }
  
  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(p->u.med)];
    c->tail(ActorLink::cast(p));
    if (c > pc.p.active)
      pc.p.active = c;
  }

  forceinline const BranchingDesc*
  Space::description(void) const {
    return b_status->description(this);
  }

  forceinline void
  Space::fail(void) {
    pc.p.active = NULL;
  }

  forceinline bool
  Space::failed(void) const {
    return pc.p.active == NULL;
  }

  forceinline bool
  Space::stable(void) const {
    return pc.p.active < &pc.p.queue[0];
  }



  /*
   * Variable implementation
   *
   */
  template <class VIC>
  forceinline
  VarImp<VIC>::VarImp(Space*) {
    for (PropCond i=0; i<pc_max+3; i++)
      idx[i] = NULL;
    free_and_bits = 0;
  }

  template <class VIC>
  forceinline
  VarImp<VIC>::VarImp(void) {
    for (PropCond i=0; i<pc_max+3; i++)
      idx[i] = NULL;
    free_and_bits = 0;
  }

  template <class VIC>
  forceinline unsigned int
  VarImp<VIC>::degree(void) const {
    assert(!copied());
    return static_cast<unsigned int>(idx[pc_max+2] - idx[0]);
  }

  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(idx[0]);
  }

  template <class VIC>
  forceinline VarImp<VIC>*
  VarImp<VIC>::forward(void) const {
    assert(copied());
    return reinterpret_cast<VarImp<VIC>*>(Support::unmark(idx[0]));
  }

  template <class VIC>
  forceinline VarImp<VIC>*
  VarImp<VIC>::next(void) const {
    assert(copied());
    return reinterpret_cast<VarImp<VIC>*>(idx[1]);
  }

  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.idx[0] == NULL) {
      // Variable implementation needs no index structure
      for (PropCond i=0; i<pc_max+3; i++)
        idx[i] = NULL;
      reg = &home->pc.c.vars_noidx;
    } else {
      // Save original values in copy
      idx[0] = x.idx[0];
      idx[1] = x.idx[1];
      reg = &home->pc.c.vars_u[idx_c];
    }
    // Set forwarding pointer
    x.idx[0] = reinterpret_cast<ActorLink**>(Support::mark(this));
    // Register original
    x.idx[1] = reinterpret_cast<ActorLink**>(*reg); *reg = &x;
  }

  template <class VIC>
  forceinline ModEvent
  VarImp<VIC>::me(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) {
    if (VIC::med_update(p->u.med,me))
      home->enqueue(p);
  }

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

  template <class VIC>
  forceinline void
  VarImp<VIC>::enter(Space* home, ActorLink* a, PropCond pc) {
    // 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
    --idx[0];
    for (PropCond i = 0; i < pc; i++)
      *(idx[i]) = *(--idx[i+1]);
    *idx[pc]=a;
  }

  template <class VIC>
  void
  VarImp<VIC>::resize(Space* home) {
    if (idx[0] == NULL) {
      assert((free_and_bits >> free_bits) == 0);
      // Create fresh dependency array with four entries
      free_and_bits += 4 << free_bits;
      ActorLink** prop = static_cast<ActorLink**>
        (home->alloc(4*sizeof(ActorLink*))) + 4;
      for (PropCond i=0; i<pc_max+3; i++)
        idx[i] = prop;
    } else {
      // Resize dependency array
      unsigned int n = static_cast<unsigned int>(idx[pc_max+2] - idx[0]);
      // 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 <= idx[0]) && (idx[0] < s+home->pc.p.n_sub)) ?
        (n+4) : ((n+1)*3>>1);
      ActorLink** prop = static_cast<ActorLink**>
        (home->alloc(m*sizeof(ActorLink*))) + m-n;
      free_and_bits += (m-n) << free_bits;
      // Copy entries
      memcpy(prop, idx[0], n*sizeof(ActorLink*));
      home->reuse(idx[0], n*sizeof(ActorLink*));
      // Update index pointers
      ptrdiff_t o = prop - idx[0];
      idx[0] = prop;
      for (PropCond i = pc_max+2; i > 0; i--)
        idx[i] += o;
    }
  }

  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,ActorLink::cast(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,pc_max+1);
  }

  template <class VIC>
  forceinline void
  VarImp<VIC>::remove(Space* home, ActorLink* a, PropCond pc) {
    /*
     * The entries are removed from front to back, so when iterating
     * over dependencies wile removing them it must be done in
     * forward direction.
     */
    ActorLink** f = idx[pc];
#ifdef GECODE_AUDIT
    while (f < idx[pc+1])
      if (*f == a)
        goto found;
      else
        f++;
    GECODE_NEVER;
  found: ;
#else
    while (*f != a) f++;
#endif
    *f=*idx[pc];
    for (PropCond i=pc; i>0; i--)
      *(idx[i]++)=*(idx[i-1]);
    idx[0]++;
    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,ActorLink::cast(p),pc);
  }

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

  template <class VIC>
  forceinline void
  VarImp<VIC>::cancel(Space* home) {
    // Entries in index structure are disabled. However they
    // must still work for cloning (idx[0]) and degree (idx[PC+2])
    ActorLink** b = idx[0]; idx[0] = NULL;
    ActorLink** p = idx[pc_max+2]; idx[pc_max+2] = NULL;
    home->pc.p.n_sub -= (p-b);
    unsigned int n = (free_and_bits >> VIC::free_bits) + (p-b);
    home->reuse(p-n,n*sizeof(ActorLink*));
  }

  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 = idx[pc_max+1];
    ActorLink** le = idx[pc_max+2];
    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);
      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;
      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->idx[0] = idx[0];
    ActorLink** f = x->idx[0];
    x->idx[1] = idx[1];
    int n = static_cast<int>(x->idx[pc_max+2] - f);
    ActorLink** t = sub;
    sub += n;
    idx[0] = t;
    ptrdiff_t o = t - f;
    for (PropCond i = 1; i<pc_max+3; i++)
      idx[i] = x->idx[i]+o;
    while ((n-4) >= 0) {
      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) >= 0) {
      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 VarType>
  VarDisposer<VarType>::VarDisposer(void) {
#ifdef GECODE_HAS_VAR_DISPOSE
    Space::vd[VarType::idx_d] = this;
#endif
  }

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

}

// STATISTICS: kernel-core