main page modules namespaces classes files
Gecode home

search for 

branching.icc

Go to the documentation of this file.

/*
 *  Main authors:
 *     Christian Schulte <schulte@gecode.org>
 *     Guido Tack <tack@gecode.org>
 *
 *  Copyright:
 *     Christian Schulte, 2004
 *     Guido Tack, 2004
 *
 *  Last modified:
 *     $Date: 2006-10-25 10:39:24 +0200 (Wed, 25 Oct 2006) $ by $Author: tack $
 *     $Revision: 3784 $
 *
 *  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 {


  enum ViewSelStatus {
    VSS_NONE,   
    VSS_SELECT, 
    VSS_COMMIT  
  };

  template <class View, class Val, class ViewSel, class ValSel>
  class ViewValBranching : public Branching {
  protected:
    ViewArray<View> x;  
    mutable int start;  

    ViewValBranching(Space* home, bool share, ViewValBranching& b);
  public:
    ViewValBranching(Space* home, ViewArray<View>& x);
    virtual bool status(const Space* home) const;
    virtual const BranchingDesc* description(const Space* home) const;
    virtual ExecStatus commit(Space* home, const BranchingDesc* d,
                              unsigned int a);
    virtual Actor* copy(Space* home, bool share);
  };

  template <class Val>
  class PosValDesc : public BranchingDesc {
  protected:
    const int _pos;
    const Val _val;
    const int _start;
  public:
    PosValDesc(const Branching* b, const int p, const Val& n, const int s=0);
    int pos(void) const;
    Val val(void) const;
    int start(void) const;
    virtual size_t size(void) const;
  };







  /*
   * Branching descriptions with position and value
   *
   */

  template <class Val>
  forceinline
  PosValDesc<Val>::PosValDesc(const Branching* b, const int p, const Val& n, 
                              const int s)
    : BranchingDesc(b,2), _pos(p), _val(n), _start(s) {}

  template <class Val>
  forceinline int
  PosValDesc<Val>::pos(void) const {
    return _pos;
  }

  template <class Val>
  forceinline Val
  PosValDesc<Val>::val(void) const {
    return _val;
  }

  template <class Val>
  forceinline int
  PosValDesc<Val>::start(void) const {
    return _start;
  }

  template <class Val>
  size_t
  PosValDesc<Val>::size(void) const {
    return sizeof(PosValDesc<Val>);
  }


  /*
   * Generic branching based on variable/value selection
   *
   */

  template <class View, class Val, class ViewSel, class ValSel>
  forceinline
  ViewValBranching<View,Val,ViewSel,ValSel>
  ::ViewValBranching(Space* home, ViewArray<View>& x0)
    : Branching(home), x(x0), start(0) {}


  template <class View, class Val, class ViewSel, class ValSel>
  forceinline
  ViewValBranching<View,Val,ViewSel,ValSel>
  ::ViewValBranching(Space* home, bool share, ViewValBranching& b)
    : Branching(home,share,b), start(b.start) {
    x.update(home,share,b.x);
  }

  template <class View, class Val, class ViewSel, class ValSel>
  Actor*
  ViewValBranching<View,Val,ViewSel,ValSel>::copy(Space* home, bool share) {
    return new (home)
      ViewValBranching<View,Val,ViewSel,ValSel>(home,share,*this);
  }

  template <class View, class Val, class ViewSel, class ValSel>
  bool
  ViewValBranching<View,Val,ViewSel,ValSel>
  ::status(const Space*) const {
    for (int i=start; i < x.size(); i++)
      if (!x[i].assigned()) {
        start = i;
        return true;
      }
    return false;
  }

  template <class View, class Val, class ViewSel, class ValSel>
  const BranchingDesc*
  ViewValBranching<View,Val,ViewSel,ValSel>
  ::description(const Space* home) const {
    assert(!x[start].assigned());
    ViewSel vs; // For view selection
    ValSel  vl; // For value selection
    int i = start;
    int b = i++;
    if (vs.init(home,x[b]) != VSS_COMMIT)
      for (; i < x.size(); i++)
        if (!x[i].assigned())
          switch (vs.select(home,x[i])) {
          case VSS_SELECT: b=i; break;
          case VSS_COMMIT: b=i; goto create;
          case VSS_NONE:   break;
          default:         GECODE_NEVER;
          }
  create:
    return new PosValDesc<Val>(this,b-start,vl.val(home,x[b]),start);
  }

  template <class View, class Val, class ViewSel, class ValSel>
  ExecStatus
  ViewValBranching<View,Val,ViewSel,ValSel>
  ::commit(Space* home, const BranchingDesc* d, unsigned int a) {
    const PosValDesc<Val>* pvd = static_cast<const PosValDesc<Val>*>(d);
    // Eliminate views from x[0] ... x[d->start()-1]
    x.drop_fst(pvd->start()); start = 0;
    ValSel vs;
    return me_failed(vs.tell(home,a,x[pvd->pos()],pvd->val()))
      ? ES_FAILED : ES_OK;
  }

}

// STATISTICS: kernel-other