Generated on Wed Jan 4 17:49:13 2006 for Gecode by doxygen 1.4.6

branching.icc

Go to the documentation of this file.
00001 /*
00002  *  Main authors:
00003  *     Christian Schulte <schulte@gecode.org>
00004  *     Guido Tack <tack@gecode.org>
00005  *
00006  *  Copyright:
00007  *     Christian Schulte, 2004
00008  *     Guido Tack, 2004
00009  *
00010  *  Last modified:
00011  *     $Date: 2005-08-09 17:26:38 +0200 (Tue, 09 Aug 2005) $ by $Author: schulte $
00012  *     $Revision: 2190 $
00013  *
00014  *  This file is part of Gecode, the generic constraint
00015  *  development environment:
00016  *     http://www.gecode.org
00017  *
00018  *  See the file "LICENSE" for information on usage and
00019  *  redistribution of this file, and for a
00020  *     DISCLAIMER OF ALL WARRANTIES.
00021  *
00022  */
00023 
00024 namespace Gecode {
00025 
00034 
00035   enum ViewSelStatus {
00036     VSS_NONE,   
00037     VSS_SELECT, 
00038     VSS_COMMIT  
00039   };
00040 
00067   template <class View, class Val, class ViewSel, class ValSel>
00068   class ViewValBranching : public Branching {
00069   protected:
00070     ViewArray<View> x; 
00071     int start;         
00072     int next;          
00073 
00074     ViewValBranching(Space* home, bool share, ViewValBranching& b);
00075   public:
00077     ViewValBranching(Space* home, ViewArray<View>& x);
00079     virtual unsigned int   branch(void);
00081     virtual BranchingDesc* description(void);
00083     virtual ExecStatus commit(Space* home, unsigned int a, BranchingDesc* d);
00085     virtual Actor* copy(Space* home, bool share);
00086   };
00087 
00092   template <class Val>
00093   class PosValDesc : public BranchingDesc {
00094   protected:
00095     const int _pos;
00096     const Val _val;
00097   public:
00099     PosValDesc(Branching*,int,Val);
00101     int pos(void) const;
00103     Val val(void) const;
00105     virtual size_t size(void) const;
00106   };
00107 
00109 
00110 
00111 
00112 
00113 
00114 
00115   /*
00116    * Branching descriptions with position and value
00117    *
00118    */
00119 
00120   template <class Val>
00121   forceinline
00122   PosValDesc<Val>::PosValDesc(Branching* b, int pos, Val val)
00123     : BranchingDesc(b), _pos(pos), _val(val) {}
00124 
00125   template <class Val>
00126   forceinline int
00127   PosValDesc<Val>::pos(void) const {
00128     return _pos;
00129   }
00130 
00131   template <class Val>
00132   forceinline Val
00133   PosValDesc<Val>::val(void) const {
00134     return _val;
00135   }
00136 
00137   template <class Val>
00138   size_t
00139   PosValDesc<Val>::size(void) const {
00140     return sizeof(PosValDesc<Val>);
00141   }
00142 
00143 
00144   /*
00145    * Generic branching based on variable/value selection
00146    *
00147    */
00148 
00149   template <class View, class Val, class ViewSel, class ValSel>
00150   forceinline
00151   ViewValBranching<View,Val,ViewSel,ValSel>::ViewValBranching
00152   (Space* home, ViewArray<View>& x0)
00153     : Branching(home), x(x0), start(0) {}
00154 
00155 
00156   template <class View, class Val, class ViewSel, class ValSel>
00157   forceinline
00158   ViewValBranching<View,Val,ViewSel,ValSel>::ViewValBranching
00159   (Space* home, bool share, ViewValBranching& b)
00160     : Branching(home,share,b), start(b.start), next(b.next) {
00161     x.update(home,share,b.x);
00162   }
00163 
00164   template <class View, class Val, class ViewSel, class ValSel>
00165   Actor*
00166   ViewValBranching<View,Val,ViewSel,ValSel>::copy(Space* home, bool share) {
00167     return new (home)
00168       ViewValBranching<View,Val,ViewSel,ValSel>(home,share,*this);
00169   }
00170 
00171   template <class View, class Val, class ViewSel, class ValSel>
00172   unsigned int
00173   ViewValBranching<View,Val,ViewSel,ValSel>::branch(void) {
00174     for (int i=start; i < x.size(); i++)
00175       if (!x[i].assigned()) {
00176         start = i;
00177         int b = i++;
00178         ViewSel vs;
00179         if (vs.init(x[b]) == VSS_COMMIT)
00180           goto commit;
00181         for (; i < x.size(); i++)
00182           if (!x[i].assigned()) {
00183             ViewSelStatus vss = vs.select(x[i]);
00184             if (vss != VSS_NONE) {
00185               b = i;
00186               if (vss == VSS_COMMIT)
00187                 goto commit;
00188             }
00189           }
00190       commit:
00191         next = b;
00192         return 2;
00193       }
00194     return 0;
00195   }
00196 
00197   template <class View, class Val, class ViewSel, class ValSel>
00198   BranchingDesc*
00199   ViewValBranching<View,Val,ViewSel,ValSel>::description(void) {
00200     ValSel vl;
00201     return new PosValDesc<Val>(this,next,vl.val(x[next]));
00202   }
00203 
00204   template <class View, class Val, class ViewSel, class ValSel>
00205   ExecStatus
00206   ViewValBranching<View,Val,ViewSel,ValSel>::commit
00207   (Space* home, unsigned int a, BranchingDesc* d) {
00208     PosValDesc<Val>* pvd = static_cast<PosValDesc<Val>*>(d);
00209     ValSel vs;
00210     int p;
00211     Val v;
00212     if (pvd == NULL) {
00213       p = next; v = vs.val(x[p]);
00214     } else {
00215       p = pvd->pos(); v = pvd->val();
00216     }
00217     return me_failed(vs.tell(home,a,x[p],v)) ? ES_FAILED : ES_OK;
00218   }
00219 
00220 }
00221 
00222 // STATISTICS: kernel-other