Generated on Mon Nov 30 23:53:32 2009 for Gecode by doxygen 1.6.1

brancher.hpp

Go to the documentation of this file.
00001 /* -*- mode: C++; c-basic-offset: 2; indent-tabs-mode: nil -*- */
00002 /*
00003  *  Main authors:
00004  *     Christian Schulte <schulte@gecode.org>
00005  *     Guido Tack <tack@gecode.org>
00006  *
00007  *  Copyright:
00008  *     Christian Schulte, 2004
00009  *     Guido Tack, 2004
00010  *
00011  *  Last modified:
00012  *     $Date: 2009-10-12 17:36:53 +0200 (Mon, 12 Oct 2009) $ by $Author: schulte $
00013  *     $Revision: 9878 $
00014  *
00015  *  This file is part of Gecode, the generic constraint
00016  *  development environment:
00017  *     http://www.gecode.org
00018  *
00019  *  Permission is hereby granted, free of charge, to any person obtaining
00020  *  a copy of this software and associated documentation files (the
00021  *  "Software"), to deal in the Software without restriction, including
00022  *  without limitation the rights to use, copy, modify, merge, publish,
00023  *  distribute, sublicense, and/or sell copies of the Software, and to
00024  *  permit persons to whom the Software is furnished to do so, subject to
00025  *  the following conditions:
00026  *
00027  *  The above copyright notice and this permission notice shall be
00028  *  included in all copies or substantial portions of the Software.
00029  *
00030  *  THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,
00031  *  EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF
00032  *  MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND
00033  *  NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE
00034  *  LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION
00035  *  OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION
00036  *  WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
00037  *
00038  */
00039 
00040 namespace Gecode {
00041 
00050 
00051   enum ViewSelStatus {
00052     VSS_BEST,   
00053     VSS_BETTER, 
00054     VSS_TIE,    
00055     VSS_WORSE   
00056   };
00057 
00059   class Pos {
00060   public:
00062     const int pos;
00064     Pos(int p);
00065   };
00066 
00075   template<class ViewSel>
00076   class ViewBrancher : public Brancher {
00077   protected:
00079     ViewArray<typename ViewSel::View> x;
00081     mutable int start;
00083     ViewSel viewsel;
00085     Pos pos(Space& home);
00087     typename ViewSel::View view(const Pos& p) const;
00089     ViewBrancher(Space& home, bool share, ViewBrancher& b);
00090   public:
00092     ViewBrancher(Home home, ViewArray<typename ViewSel::View>& x,
00093                  ViewSel& vi_s);
00095     virtual bool status(const Space& home) const;
00097     virtual size_t dispose(Space& home);
00098   };
00099 
00100 
00110   template<class ViewSel, class ValSel>
00111   class ViewValBrancher : public ViewBrancher<ViewSel> {
00112   protected:
00113     using ViewBrancher<ViewSel>::viewsel;
00114     using ViewBrancher<ViewSel>::x;
00116     ValSel valsel;
00118     ViewValBrancher(Space& home, bool share, ViewValBrancher& b);
00119   public:
00121     ViewValBrancher(Home home, ViewArray<typename ViewSel::View>& x,
00122                     ViewSel& vi_s, ValSel& va_s);
00124     virtual const Choice* choice(Space& home);
00126     virtual ExecStatus commit(Space& home, const Choice& c, unsigned int a);
00128     virtual Actor* copy(Space& home, bool share);
00130     virtual size_t dispose(Space& home);
00131   };
00132 
00133 
00135   template<class ViewSel>
00136   class GECODE_VTABLE_EXPORT PosChoice : public Choice {
00137   private:
00139     const Pos _pos;
00141     const typename ViewSel::Choice _viewchoice;
00142   public:
00144     PosChoice(const Brancher& b, unsigned int a, const Pos& p,
00145               const typename ViewSel::Choice& viewc);
00147     const Pos& pos(void) const;
00149     const typename ViewSel::Choice& viewchoice(void) const;
00151     virtual size_t size(void) const;
00152   };
00153 
00155   template<class ViewSel, class ValSel>
00156   class GECODE_VTABLE_EXPORT PosValChoice : public PosChoice<ViewSel> {
00157   private:
00159     const typename ValSel::Choice _valchoice;
00161     const typename ValSel::Val _val;
00162   public:
00164     PosValChoice(const Brancher& b, const Pos& p,
00165                  const typename ViewSel::Choice& viewc,
00166                  const typename ValSel::Choice& valc,
00167                  const typename ValSel::Val& n);
00169     const typename ValSel::Choice& valchoice(void) const;
00171     const typename ValSel::Val& val(void) const;
00173     virtual size_t size(void) const;
00174   };
00176 
00177 
00178 
00179 
00180   /*
00181    * Position information
00182    *
00183    */
00184   forceinline
00185   Pos::Pos(int p) : pos(p) {}
00186 
00187 
00188   /*
00189    * Choice with position
00190    *
00191    */
00192   template<class ViewSel>
00193   forceinline
00194   PosChoice<ViewSel>::PosChoice(const Brancher& b, unsigned int a, 
00195                                 const Pos& p,
00196                                 const typename ViewSel::Choice& viewc)
00197     : Choice(b,a), _pos(p), _viewchoice(viewc) {}
00198   template<class ViewSel>
00199   forceinline const Pos&
00200   PosChoice<ViewSel>::pos(void) const {
00201     return _pos;
00202   }
00203   template<class ViewSel>
00204   forceinline const typename ViewSel::Choice&
00205   PosChoice<ViewSel>::viewchoice(void) const {
00206     return _viewchoice;
00207   }
00208   template<class ViewSel>
00209   forceinline size_t
00210   PosChoice<ViewSel>::size(void) const {
00211     return sizeof(PosChoice<ViewSel>) + _viewchoice.size();
00212   }
00213 
00214 
00215   /*
00216    * %Choice with position and value
00217    *
00218    */
00219   template<class ViewSel, class ValSel>
00220   forceinline
00221   PosValChoice<ViewSel,ValSel>
00222   ::PosValChoice(const Brancher& b, const Pos& p,
00223                  const typename ViewSel::Choice& viewc,
00224                  const typename ValSel::Choice& valc,
00225                  const typename ValSel::Val& n)
00226     : PosChoice<ViewSel>(b,ValSel::alternatives,p,viewc),
00227       _valchoice(valc), _val(n) {}
00228 
00229   template<class ViewSel, class ValSel>
00230   forceinline const typename ValSel::Choice&
00231   PosValChoice<ViewSel,ValSel>::valchoice(void) const {
00232     return _valchoice;
00233   }
00234 
00235   template<class ViewSel, class ValSel>
00236   forceinline const typename ValSel::Val&
00237   PosValChoice<ViewSel,ValSel>::val(void) const {
00238     return _val;
00239   }
00240 
00241   template<class ViewSel, class ValSel>
00242   forceinline size_t
00243   PosValChoice<ViewSel, ValSel>::size(void) const {
00244     return sizeof(PosValChoice<ViewSel,ValSel>) + _valchoice.size();
00245   }
00246 
00247 
00248   /*
00249    * Generic brancher based on view selection
00250    *
00251    */
00252 
00253   template<class ViewSel>
00254   forceinline
00255   ViewBrancher<ViewSel>::ViewBrancher(Home home,
00256                                       ViewArray<typename ViewSel::View>& x0,
00257                                       ViewSel& vi_s)
00258     : Brancher(home), x(x0), start(0), viewsel(vi_s) {}
00259 
00260 
00261   template<class ViewSel>
00262   forceinline
00263   ViewBrancher<ViewSel>::ViewBrancher(Space& home, bool share,
00264                                       ViewBrancher& b)
00265     : Brancher(home,share,b), start(b.start) {
00266     x.update(home,share,b.x);
00267     viewsel.update(home,share,b.viewsel);
00268   }
00269 
00270   template<class ViewSel>
00271   bool
00272   ViewBrancher<ViewSel>::status(const Space&) const {
00273     for (int i=start; i < x.size(); i++)
00274       if (!x[i].assigned()) {
00275         start = i;
00276         return true;
00277       }
00278     return false;
00279   }
00280 
00281   template<class ViewSel>
00282   forceinline Pos
00283   ViewBrancher<ViewSel>::pos(Space& home) {
00284     assert(!x[start].assigned());
00285     int i = start;
00286     int b = i++;
00287     if (viewsel.init(home,x[b]) != VSS_BEST)
00288       for (; i < x.size(); i++)
00289         if (!x[i].assigned())
00290           switch (viewsel.select(home,x[i])) {
00291           case VSS_BETTER:              b=i; break;
00292           case VSS_BEST:                b=i; goto create;
00293           case VSS_TIE: case VSS_WORSE: break;
00294           default:                      GECODE_NEVER;
00295           }
00296   create:
00297     Pos p(b);
00298     return p;
00299   }
00300 
00301   template<class ViewSel>
00302   forceinline typename ViewSel::View
00303   ViewBrancher<ViewSel>::view(const Pos& p) const {
00304     return x[p.pos];
00305   }
00306 
00307   template<class ViewSel>
00308   forceinline size_t
00309   ViewBrancher<ViewSel>::dispose(Space& home) {
00310     viewsel.dispose(home);
00311     (void) Brancher::dispose(home);
00312     return sizeof(ViewBrancher<ViewSel>);
00313   }
00314 
00315 
00316 
00317   /*
00318    * Generic brancher based on variable/value selection
00319    *
00320    */
00321 
00322   template<class ViewSel, class ValSel>
00323   forceinline
00324   ViewValBrancher<ViewSel,ValSel>::
00325   ViewValBrancher(Home home, ViewArray<typename ViewSel::View>& x,
00326                   ViewSel& vi_s, ValSel& va_s)
00327     : ViewBrancher<ViewSel>(home,x,vi_s), valsel(va_s) {}
00328 
00329   template<class ViewSel, class ValSel>
00330   forceinline
00331   ViewValBrancher<ViewSel,ValSel>::
00332   ViewValBrancher(Space& home, bool share, ViewValBrancher& b)
00333     : ViewBrancher<ViewSel>(home,share,b) {
00334     valsel.update(home,share,b.valsel);
00335   }
00336 
00337   template<class ViewSel, class ValSel>
00338   Actor*
00339   ViewValBrancher<ViewSel,ValSel>::copy(Space& home, bool share) {
00340     return new (home)
00341       ViewValBrancher<ViewSel,ValSel>(home,share,*this);
00342   }
00343 
00344   template<class ViewSel, class ValSel>
00345   const Choice*
00346   ViewValBrancher<ViewSel,ValSel>::choice(Space& home) {
00347     Pos p = ViewBrancher<ViewSel>::pos(home);
00348     typename ValSel::View v(ViewBrancher<ViewSel>::view(p).var());
00349     return new PosValChoice<ViewSel,ValSel>
00350       (*this,p,
00351        viewsel.choice(home),
00352        valsel.choice(home),valsel.val(home,v));
00353   }
00354 
00355   template<class ViewSel, class ValSel>
00356   ExecStatus
00357   ViewValBrancher<ViewSel,ValSel>
00358   ::commit(Space& home, const Choice& c, unsigned int a) {
00359     const PosValChoice<ViewSel,ValSel>& pvc
00360       = static_cast<const PosValChoice<ViewSel,ValSel>&>(c);
00361     typename ValSel::View
00362       v(ViewBrancher<ViewSel>::view(pvc.pos()).var());
00363     viewsel.commit(home, pvc.viewchoice(), a);
00364     valsel.commit(home, pvc.valchoice(), a);
00365     return me_failed(valsel.tell(home,a,v,pvc.val())) ? ES_FAILED : ES_OK;
00366   }
00367 
00368   template<class ViewSel, class ValSel>
00369   forceinline size_t
00370   ViewValBrancher<ViewSel,ValSel>::dispose(Space& home) {
00371     valsel.dispose(home);
00372     (void) ViewBrancher<ViewSel>::dispose(home);
00373     return sizeof(ViewValBrancher<ViewSel,ValSel>);
00374   }
00375 
00376 }
00377 
00378 // STATISTICS: kernel-branch