main page modules namespaces classes files
Gecode home

search for 

core.icc

Go to the documentation of this file.

/*
 *  Main authors:
 *     Christian Schulte <schulte@gecode.org>
 *     Guido Tack <tack@gecode.org>
 *
 *  Copyright:
 *     Christian Schulte, 2002
 *     Guido Tack, 2003
 *
 *  Bugfixes provided by:
 *     Alexander Samoilov <alexander_samoilov@yahoo.com>
 *
 *  Last modified:
 *     $Date: 2006-10-25 13:51:24 +0200 (Wed, 25 Oct 2006) $ by $Author: schulte $
 *     $Revision: 3787 $
 *
 *  This file is part of Gecode, the generic constraint
 *  development environment:
 *     http://www.gecode.org
 *
 *  See the file "LICENSE" for information on usage and
 *  redistribution of this file, and for a
 *     DISCLAIMER OF ALL WARRANTIES.
 *
 */

namespace Gecode {


  typedef int ModEvent;

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

  typedef int PropCond;
  const PropCond PC_GEN_ASSIGNED = 0;
  const PropCond PC_GEN_MAX      = 15;


  enum VarTypeId {
#include "gecode/vti.icc"
    VTI_LAST,     
    VTI_NOIDX = 0 
  };


  /*
   * These are the classes of interest
   *
   */
  class Actor;
  class Propagator;
  class Space;
  template <VarTypeId VTI, PropCond PC, class MED> class Variable;


  /*
   * Variables
   *
   */

  class VarBase {};

  class VarTypeProcessorBase {
  public:
    virtual void process(Space* home, VarBase* x) = 0;
    virtual void update(VarBase* x, Propagator**& sub) = 0;
    virtual void dispose(Space* home, VarBase* x) = 0;
    GECODE_KERNEL_EXPORT virtual ~VarTypeProcessorBase(void);
  };

  template <VarTypeId VTI, PropCond PC, class MED>
  class VarTypeProcessor : public VarTypeProcessorBase {
  public:
    VarTypeProcessor(void);
    virtual void update(VarBase* x, Propagator**& sub);
    virtual void dispose(Space* home, VarBase* x);
  };

  typedef int PropModEvent;


  template <VarTypeId VTI, PropCond PC, class MED>
  class Variable : public VarBase {
    friend class Space;
    friend class Propagator;
    friend class VarTypeProcessor<VTI,PC,MED>;
  private:
    Variable* _next; 
    union {
      unsigned int free_me;
      Variable* fwd;
    } u;
    Propagator** idx[PC+2]; 

    unsigned int free(void) const;
    void free(unsigned int n);
    void free_inc(void);
    void free_dec(void);

    void update(Variable* x, Propagator**& sub);

    void resize(Space* home);

  public:
    Variable(Space* home);



    void subscribe(Space* home, Propagator* p, PropCond pc,
                   bool assigned, ModEvent me, bool process);
    void cancel(Space* home, Propagator* p, PropCond pc);
    unsigned int degree(void) const;
    void notify(Space* home, ModEvent me);
    void notify(Space* home);



    bool modified(void) const;



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



    static ModEvent     pme(const Propagator* p);
    static PropModEvent pme(ModEvent me);
    static ModEvent     combine(ModEvent me1, ModEvent me2);



    Variable* next(void);
    ModEvent modevent(void) const;
    void modevent(ModEvent me);
    void process(Space* home, PropCond pc1, PropCond pc2, ModEvent me);
    void process(Space* home);



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




  enum ExecStatus {
    ES_FAILED          = -1, 
    ES_NOFIX           =  0, 
    ES_OK              =  0, 
    ES_FIX             =  1, 
    ES_SUBSUMED        =  2, 
    __ES_FIX_PARTIAL   =  3, 
    __ES_NOFIX_PARTIAL =  4  
  };

  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 Space;
    template <VarTypeId VTI, PropCond PC, class MED> friend class Variable;
  private:
    ActorLink* _next; ActorLink* _prev;
  public:

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


    void init(void);
    void unlink(void);
    void head(ActorLink* al);
    void tail(ActorLink* al);
  };


  class ActorDeleteLink : public ActorLink {
    friend class Actor;
    friend class Space;
    template <VarTypeId VTI, PropCond PC, class MED> friend class Variable;
  private:
    ActorDeleteLink* _next_d; ActorDeleteLink* _prev_d;
  public:
    ActorDeleteLink* next_delete(void) const;
    void next_delete(ActorDeleteLink*);
    ActorDeleteLink* prev_delete(void) const;
    void prev_delete(ActorDeleteLink*);

    void init_delete(void);
    void unlink_delete(void);
    void insert_delete(ActorDeleteLink*,bool);
  };



  class Actor : private ActorDeleteLink {
    friend class Space;
    template <VarTypeId VTI, PropCond PC, class MED> friend class Variable;
  public:
    virtual Actor* copy(Space*,bool) = 0;
    GECODE_KERNEL_EXPORT
    virtual size_t dispose(Space* home);



    GECODE_KERNEL_EXPORT virtual void flush(void);
    GECODE_KERNEL_EXPORT virtual size_t cached(void) const;
    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, size_t s);
#endif

    static void* operator new(size_t s);
    void destruct(Space* home);
#ifdef __GNUC__
  public:
    virtual ~Actor(void) {}
    static void  operator delete(void* p, size_t s);
#endif
  };



  class Propagator : public Actor {
    friend class Space;
    template <VarTypeId VTI, PropCond PC, class MED> friend class Variable;
  private:
    PropModEvent pme;
  protected:
    Propagator(Space* home, bool fd=false);
    Propagator(Space* home, bool share, Propagator& p);



    ExecStatus ES_FIX_PARTIAL(PropModEvent pme);
    ExecStatus ES_NOFIX_PARTIAL(PropModEvent pme);
  public:


    virtual ExecStatus propagate(Space*) = 0;
    virtual PropCost cost(void) const  = 0;
  };



  /*
   * Branchings
   *
   */

  class Branching;

  class BranchingDesc {
    friend class Space;
  private:
    const unsigned int id;  
    const unsigned int alt; 
  protected:
    BranchingDesc(const Branching* b, const unsigned int a);
  public:
    GECODE_KERNEL_EXPORT virtual ~BranchingDesc(void);

    unsigned int alternatives(void) const;

    virtual size_t size(void) const = 0;
    static void* operator new(size_t);
    static void  operator delete(void*);
  };

  class Branching : public Actor {
    friend class Space;
    friend class BranchingDesc;
  private:
    unsigned int id; 
  protected:
    Branching(Space* home, bool fd=false);
    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;
  };



  enum SpaceStatus {
    SS_FAILED, 
    SS_SOLVED, 
    SS_BRANCH  
  };

  class Space {
    friend class Propagator;
    friend class Branching;
    template <VarTypeId VTI, PropCond PC, class MED> friend class Variable;
    template <VarTypeId VTI, PropCond PC, class MED> friend class VarTypeProcessor;
  private:
    MemoryManager   mm; 


    GECODE_KERNEL_EXPORT
    static VarTypeProcessorBase* vtp[VTI_LAST];
    VarBase* vars[VTI_LAST];
    VarBase* vars_dispose[VTI_LAST];
    VarBase* vars_noidx;
    void process(void);


    ActorLink pool[PC_MAX+1];
    int pool_next;
    void pool_put(Propagator* p);
    bool pool_get(Propagator*& p);

    ActorDeleteLink a_actors;
    Branching*      b_status;
    Branching*      b_commit;
    unsigned int    branch_id;

    unsigned int n_sub;
    Propagator** sub;
    GECODE_KERNEL_EXPORT static unsigned long int unused_uli;

    GECODE_KERNEL_EXPORT unsigned long int propagate(void);

    void propagator(Propagator* p, bool fd);
    void propagator(Propagator*);
    void branching(Branching* b, bool fd);


    template <VarTypeId VTI, class MED>
    void process(Propagator* p, ModEvent me);
    template <VarTypeId VTI, class MED>
    void process(Propagator* p);


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

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

    const BranchingDesc* description(void) const;

    GECODE_KERNEL_EXPORT
    Space* clone(bool share=true, unsigned long int& pn=unused_uli);

    GECODE_KERNEL_EXPORT
    void commit(const BranchingDesc* d, unsigned int a);

    GECODE_KERNEL_EXPORT
    void flush(void);


    /*
     * Status checking and failing outside actors
     *
     */

    void fail(void);
    bool failed(void) const;
    GECODE_KERNEL_EXPORT
    unsigned int propagators(void) const;
    GECODE_KERNEL_EXPORT
    unsigned int branchings(void) 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);
    size_t allocated(void) const;
    GECODE_KERNEL_EXPORT size_t cached(void) const;
    template <VarTypeId VTI> VarBase* varsDisposeList(void);
    template <VarTypeId VTI> void varsDisposeList(VarBase* v);
  };




  /***
   *** MEMORY MANAGEMENT
   ***
   ***/

  /*
   * Heap allocated: Space, BranchDesc
   *
   */

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

  forceinline size_t
  Space::allocated(void) const {
    return mm.allocated()+n_sub*sizeof(Propagator**);
  }

  template <VarTypeId VTI>
  forceinline VarBase*
  Space::varsDisposeList(void) {
    return vars_dispose[VTI];
  }

  template <VarTypeId VTI>
  forceinline void
  Space::varsDisposeList(VarBase* v) {
    vars_dispose[VTI]=v;
  }

  /*
   * Space allocated entities: Actors and Variables
   *
   */

  forceinline void
  Actor::operator delete(void*, size_t) {}
  forceinline void
  Actor::operator delete(void*,Space*) {}
  forceinline void*
  Actor::operator new(size_t s, Space* home) {
    return home->alloc(s);
  }

  template <VarTypeId VTI, PropCond PC, class MED>
  forceinline void
  Variable<VTI,PC,MED>::operator delete(void*) {}
  template <VarTypeId VTI, PropCond PC, class MED>
  forceinline void
  Variable<VTI,PC,MED>::operator delete(void*, Space*) {}
  template <VarTypeId VTI, PropCond PC, class MED>
  forceinline void*
  Variable<VTI,PC,MED>::operator new(size_t s, Space* home) {
    return home->alloc(s);
  }



  /*
   * ActorLinks as common subclass for propagators and branchings
   *
   */

  forceinline ActorLink*
  ActorLink::prev(void) const { return _prev; }
  forceinline ActorLink*
  ActorLink::next(void) const { 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 ActorDeleteLink*
  ActorDeleteLink::next_delete(void) const { return _next_d; }
  forceinline ActorDeleteLink*
  ActorDeleteLink::prev_delete(void) const { return _prev_d; }
  forceinline void
  ActorDeleteLink::next_delete(ActorDeleteLink* adl) { _next_d = adl; }
  forceinline void
  ActorDeleteLink::prev_delete(ActorDeleteLink* adl) { _prev_d = adl; }

  forceinline void
  ActorDeleteLink::unlink_delete(void) {
    ActorDeleteLink* p = _prev_d;
    ActorDeleteLink* n = _next_d;
    p->_next_d = n; n->_prev_d = p;
  }

  forceinline void
  ActorDeleteLink::insert_delete(ActorDeleteLink* a, bool fd) {
    if (fd) {
      // Link a after this
      ActorDeleteLink* n = _next_d;
      this->_next_d = a; a->_prev_d = this;
      a->_next_d = n; n->_prev_d = a;
    } else {
      // Just link to itself
      a->_prev_d = a; a->_next_d = a;
    }
  }

  forceinline void
  ActorDeleteLink::init_delete(void) {
    _next_d = this; _prev_d = this;
  }




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

  forceinline void
  Actor::destruct(Space* home) {
    unlink_delete();
    size_t s = dispose(home);
    home->reuse(this,s);
  }


  /*
   * Spaces
   *
   */

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

  forceinline bool
  Space::failed(void) const {
    return b_status == NULL;
  }

  /*
   * Main control for propagation and branching
   *  - a space only propagates and branches if requested by
   *    either a status, commit, or clone operation
   *  - for all of the operations the number of propagation
   *    steps performed is returned in the last (optional)
   *    reference argument
   *
   */
  forceinline SpaceStatus
  Space::status(unsigned long int& pn) {
    // Perform propagation and do not continue when failed
    pn += propagate();
    if (failed())
      return SS_FAILED;
    /*
     * Find the next branching that has still alternatives left
     *
     * It is important to note that branchings reporting to have no more
     * alternatives left can not be deleted. They can not be deleted
     * as there might be branching descriptions to be used in commit
     * that refer to one of these branchings.
     *
     * A branching reporting that no more alternatives exist will eventually
     * be deleted in commit. It will be deleted if the first branching
     * description is used in commit that does not refer to this branching.
     * As we insist that branching descriptions are used in order of
     * creation, all further branching descriptions cannot refer to this
     * branching.
     *
     */
    while (b_status != &a_actors) {
      if (b_status->status(this))
        return SS_BRANCH;
      b_status = static_cast<Branching*>(b_status->next());
    }
    // No branching with alternatives left, space is solved
    return SS_SOLVED;
  }


  /*
   * Variables
   *
   */

  template <VarTypeId VTI, PropCond PC, class MED>
  forceinline
  Variable<VTI,PC,MED>::Variable(Space*) :
    _next(reinterpret_cast<Variable<VTI,PC,MED>*>(1)) {
    u.free_me = 0;
    for (int i=PC+2; i--; )
      idx[i] = NULL;
  }


  template <VarTypeId VTI, PropCond PC, class MED>
  forceinline unsigned int
  Variable<VTI,PC,MED>::degree(void) const {
    return static_cast<unsigned int>(idx[PC+1] - idx[0]);
  }



  template <VarTypeId VTI, PropCond PC, class MED>
  forceinline ModEvent
  Variable<VTI,PC,MED>::modevent(void) const {
    return u.free_me & 15;
  }

  template <VarTypeId VTI, PropCond PC, class MED>
  forceinline void
  Variable<VTI,PC,MED>::modevent(ModEvent me) {
    u.free_me = (u.free_me & ~15) | me;
  }
  template <VarTypeId VTI, PropCond PC, class MED>
  forceinline unsigned int
  Variable<VTI,PC,MED>::free(void) const {
    return u.free_me >> 4;
  }

  template <VarTypeId VTI, PropCond PC, class MED>
  forceinline void
  Variable<VTI,PC,MED>::free(unsigned int n) {
    u.free_me = (u.free_me & 15) | (n << 4);
  }

  template <VarTypeId VTI, PropCond PC, class MED>
  forceinline void
  Variable<VTI,PC,MED>::free_inc(void) {
    u.free_me += (1 << 4);
  }

  template <VarTypeId VTI, PropCond PC, class MED>
  forceinline void
  Variable<VTI,PC,MED>::free_dec(void) {
    u.free_me -= (1 << 4);
  }

  template <VarTypeId VTI, PropCond PC, class MED>
  forceinline bool
  Variable<VTI,PC,MED>::modified(void) const {
    return _next != reinterpret_cast<Variable<VTI,PC,MED>*>(1);
  }



  template <VarTypeId VTI, PropCond PC, class MED>
  forceinline Variable<VTI,PC,MED>*
  Variable<VTI,PC,MED>::next(void) {
    Variable<VTI,PC,MED>* n = _next;
    _next = reinterpret_cast<Variable<VTI,PC,MED>*>(1);
    return n;
  }

  template <VarTypeId VTI, PropCond PC, class MED>
  forceinline bool
  Variable<VTI,PC,MED>::copied(void) const {
    return _next != reinterpret_cast<Variable<VTI,PC,MED>*>(1);
  }

  template <VarTypeId VTI, PropCond PC, class MED>
  forceinline
  Variable<VTI,PC,MED>::Variable(Space* home, bool, Variable<VTI,PC,MED>& x)
    : _next(reinterpret_cast<Variable<VTI,PC,MED>*>(1)) {
    VarBase** reg;
    if (x.idx[0] == NULL) {
      // Variable needs no index structure
      u.free_me = 0;
      for (int i=PC+2; i--; )
        idx[i] = NULL;
      reg = &home->vars_noidx;
    } else {
      // Recover original value in copy
      u.free_me = x.u.free_me;
      reg = &home->vars[VTI];
    }
    // Set forwarding pointer
    x.u.fwd = this;
    // Register original
    x._next = static_cast<Variable<VTI,PC,MED>*>(*reg); *reg = &x;
  }

  template <VarTypeId VTI, PropCond PC, class MED>
  forceinline Variable<VTI,PC,MED>*
  Variable<VTI,PC,MED>::forward(void) const {
    return u.fwd;
  }

  /*
   * Propagator modification events
   *
   */

  template <VarTypeId VTI, PropCond PC, class MED>
  forceinline ModEvent
  Variable<VTI,PC,MED>::pme(const Propagator* p) {
    return static_cast<ModEvent>((p->pme >> (VTI << 2)) & 15);
  }

  template <VarTypeId VTI, PropCond PC, class MED>
  forceinline PropModEvent
  Variable<VTI,PC,MED>::pme(ModEvent me) {
    return static_cast<PropModEvent>(me << (VTI << 2));
  }

  template <VarTypeId VTI, PropCond PC, class MED>
  forceinline ModEvent
  Variable<VTI,PC,MED>::combine(ModEvent me1, ModEvent me2) {
    MED med;
    return me2^med(me1,me2);
  }

  /*
   * Propagators
   *
   */

  forceinline void
  Space::propagator(Propagator* p, bool fd) {
    // Propagators are put at the front of the link of actors
    a_actors.head(p);
    a_actors.insert_delete(p,fd);
  }

  forceinline void
  Space::propagator(Propagator* p) {
    a_actors.head(p);
  }

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



  forceinline
  Propagator::Propagator(Space* home, bool fd)
    : pme(0) {
    home->propagator(this,fd);
  }

  forceinline
  Propagator::Propagator(Space*, bool, Propagator&)
    : pme(0) {}


  /*
   * Branchings
   *
   */

  forceinline
  Branching::Branching(Space* home, bool fd) {
    home->branching(this,fd);
  }

  forceinline
  Branching::Branching(Space*, bool, Branching& b)
    : id(b.id)  {}



  /*
   * Branching descriptions
   *
   */

  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
  BranchingDesc::~BranchingDesc(void) {}





  /*
   * Propagator pools
   *
   */

  forceinline void
  Space::pool_put(Propagator* p) {
    int c = p->cost();
    pool[c].tail(p);
    if (c > pool_next)
      pool_next = c;
  }

  forceinline void
  Space::fail(void) {
    b_status = NULL;
  }

  template <VarTypeId VTI, class MED>
  forceinline void
  Space::process(Propagator* p) {
    // The new event is ME_GEN_ASSIGNED
    PropModEvent old_pme = p->pme;
    // Compute old modification event
    ModEvent old_me = old_pme & (ME_GEN_MAX << (VTI << 2));
    // Check whether old event is already ME_GEN_ASSIGNED
    if (old_me == (ME_GEN_ASSIGNED << (VTI << 2)))
      return;
    // Update event
    p->pme ^= old_me ^ (ME_GEN_ASSIGNED << (VTI << 2));
    // Put propagator into right queue
    p->unlink();
    pool_put(p);
  }

  template <VarTypeId VTI, class MED>
  forceinline void
  Space::process(Propagator* p, ModEvent new_me) {
    MED med;
    PropModEvent old_pme = p->pme;
    // Compute the old modification event
    ModEvent old_me = ((old_pme >> (VTI << 2)) & ME_GEN_MAX);
    // Get the new modification event (xor-ed with the old one)
    ModEvent com_me = med(new_me,old_me);
    // Event has not changed, do not nothing
    if (com_me == 0)
      return;
    // Update modification event for propagator (use xor)
    p->pme ^= (com_me << (VTI << 2));
    // Put propagator into right queue
    p->unlink();
    pool_put(p);
  }

  forceinline ExecStatus
  Propagator::ES_FIX_PARTIAL(PropModEvent pme) {
    this->pme = pme; return __ES_FIX_PARTIAL;
  }

  forceinline ExecStatus
  Propagator::ES_NOFIX_PARTIAL(PropModEvent pme) {
    this->pme = pme; return __ES_NOFIX_PARTIAL;
  }


  /*
   * Subscribing to a variable
   *
   */

  template <VarTypeId VTI, PropCond PC, class MED>
  forceinline void
  Variable<VTI,PC,MED>::subscribe(Space* home, Propagator* p, PropCond pc,
                                  bool assigned, ModEvent me, bool process) {
    if (assigned) {
      // Do not subscribe, just process the propagator
      if (process)
        home->process<VTI,MED>(p);
    } else {
      // Count one new subscription
      home->n_sub += 1;
      if (free() == 0)
        resize(home);
      free_dec();
      // Enter propagator
      --idx[0];
      for (PropCond i = 0; i < pc; i++)
        *(idx[i]) = *(--idx[i+1]);
      *idx[pc]=p;
      // Process propagator
      if (process && (pc != PC_GEN_ASSIGNED))
        home->process<VTI,MED>(p,me);
    }
  }

  template <VarTypeId VTI, PropCond PC, class MED>
  void
  Variable<VTI,PC,MED>::resize(Space* home) {
    assert(free() == 0);
    if (idx[0] == NULL) {
      // Count the one new free entry
      home->n_sub += 1;
      // Create fresh dependency array
      free(4);
      Propagator** prop = reinterpret_cast<Propagator**>
        (home->alloc(4*sizeof(Propagator*))) + 4;
      for (PropCond i = PC+2; i--; )
        idx[i] = prop;
    } else {
      // Resize dependency array
      int n = static_cast<int>(idx[PC+1] - idx[0]);
      Propagator** prop = reinterpret_cast<Propagator**>
        (home->alloc(2*n*sizeof(Propagator*))) + n;
      free(n);
      // Copy entries
      memcpy(prop, idx[0], n*sizeof(Propagator*));
      home->reuse(idx[0], n*sizeof(Propagator*));
      // Update index pointers
      ptrdiff_t o = prop - idx[0];
      idx[0] = prop;
      for (PropCond i = PC+1; i > 0; i--)
        idx[i] += o;
    }
  }


  /*
   * Cancelling a subscription
   *
   */

  template <VarTypeId VTI, PropCond PC, class MED>
  forceinline void
  Variable<VTI,PC,MED>::cancel(Space* home, Propagator* p, PropCond pc) {
    if (idx[0] != NULL) {
      Propagator** f = idx[pc];
#ifdef GECODE_AUDIT
      while (f < idx[pc+1])
        if (*f == p)
          goto found;
        else
          f++;
      GECODE_NEVER;
    found: ;
#else
      while (*f != p) f++;
#endif
      *f=*idx[pc];
      for (PropCond i=pc; i>0; i--)
        *(idx[i]++)=*(idx[i-1]);
      idx[0]++;
      free_inc();
      home->n_sub -= 1;
    }
  }

  template <VarTypeId VTI, PropCond PC, class MED>
  forceinline void
  Variable<VTI,PC,MED>::notify(Space* home, ModEvent new_me) {
    if (modified()) {
      MED med;
      u.free_me ^= med(new_me,modevent());
    } else {
      _next = static_cast<Variable<VTI,PC,MED>*>(home->vars[VTI]);
      home->vars[VTI] = this;
      modevent(new_me);
    }
  }

  template <VarTypeId VTI, PropCond PC, class MED>
  forceinline void
  Variable<VTI,PC,MED>::notify(Space* home) {
    assert(!modified());
    _next = static_cast<Variable<VTI,PC,MED>*>(home->vars[VTI]);
    home->vars[VTI] = this;
    modevent(ME_GEN_ASSIGNED);
  }


  /*
   * PROCESSING
   *
   */

  template <VarTypeId VTI, PropCond PC, class MED>
  forceinline void
  Variable<VTI,PC,MED>::update(Variable<VTI,PC,MED>* x, Propagator**& sub) {
    // this refers to the variable to be updated (clone)
    // x refers to the original
    // Recover from copy (also overwrites forwarding pointer)
    x->u.free_me = u.free_me;
    Propagator** f = x->idx[0];
    int n = static_cast<int>(x->idx[PC+1] - f);
    u.free_me = 1 << 4;
    Propagator** t = sub + 1;
    sub += n+1;
    idx[0] = t;
    ptrdiff_t o = t - f;
    for (PropCond i = PC+1; i>0; i--)
      idx[i] = x->idx[i]+o;
    while ((n-4) >= 0) {
      n -= 4;
      t[0] = static_cast<Propagator*>(f[0]->prev());;
      t[1] = static_cast<Propagator*>(f[1]->prev());;
      t[2] = static_cast<Propagator*>(f[2]->prev());;
      t[3] = static_cast<Propagator*>(f[3]->prev());;
      t += 4; f += 4;
    }
    if ((n-2) >= 0) {
      n -= 2;
      t[0] = static_cast<Propagator*>(f[0]->prev());;
      t[1] = static_cast<Propagator*>(f[1]->prev());;
      t += 2; f += 2;
    }
    if (n > 0) {
      t[0] = static_cast<Propagator*>(f[0]->prev());;
    }
  }

  template <VarTypeId VTI, PropCond PC, class MED>
  VarTypeProcessor<VTI,PC,MED>::VarTypeProcessor(void) {
    Space::vtp[VTI] = this;
  }

  template <VarTypeId VTI, PropCond PC, class MED>
  void
  VarTypeProcessor<VTI,PC,MED>::update(VarBase* vb, Propagator**& sub) {
    Variable<VTI,PC,MED>* x = static_cast<Variable<VTI,PC,MED>*>(vb);
    do {
      x->forward()->update(x,sub); x = x->next();
    } while (x != NULL);
  }

  template <VarTypeId VTI, PropCond PC, class MED>
  void
  VarTypeProcessor<VTI,PC,MED>::dispose(Space* home, VarBase* x) {}

  /*
   * Processing a single modified variable
   *
   */
  template <VarTypeId VTI, PropCond PC, class MED>
  forceinline void
  Variable<VTI,PC,MED>::process(Space* home,
                                PropCond pc1, PropCond pc2, ModEvent me) {
    Propagator** b = idx[pc1];
    Propagator** p = idx[pc2+1];
    while (p-- > b)
      home->process<VTI,MED>(*p,me);
  }

  template <VarTypeId VTI, PropCond PC, class MED>
  forceinline void
  Variable<VTI,PC,MED>::process(Space* home) {
    // Entries in index structure are disabled. However they
    // must still work for cloning (idx[0]) and degree (idx[PC+1])
    Propagator** b = idx[0];    idx[0] = NULL;
    Propagator** p = idx[PC+1]; idx[PC+1] = NULL;
    /*
     * Decrement for p-b subscriptions
     *
     * Note that one would like to also decrement for the additional
     * single free slot that was counted initially. However, this
     * is not possible as there might be no free slot. So the number
     * of subscriptions is a conservative estimate and will be corrected
     * upon cloning.
     */
    home->n_sub -= p-b;
    // Information needed to release the dependency array
    unsigned int n = free() + (p-b);
    Propagator** s = p-n;
    while (p-- > b)
      home->process<VTI,MED>(*p);
    home->reuse(s,n*sizeof(Propagator*));
  }

}

// STATISTICS: kernel-core