Generated on Mon May 10 06:46:42 2010 for Gecode by doxygen 1.6.3

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: 2010-03-11 22:16:29 +0100 (Thu, 11 Mar 2010) $ by $Author: schulte $
00013  *     $Revision: 10418 $
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);
00091     ViewBrancher(Home home, ViewArray<typename ViewSel::View>& x,
00092                  ViewSel& vi_s);
00093   public:
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);
00120     ViewValBrancher(Home home, ViewArray<typename ViewSel::View>& x,
00121                     ViewSel& vi_s, ValSel& va_s);
00122   public:
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);
00132     static void post(Home home, ViewArray<typename ViewSel::View>& x,
00133                      ViewSel& vi_s, ValSel& va_s);
00134 
00135   };
00136 
00137 
00139   template<class ViewSel>
00140   class GECODE_VTABLE_EXPORT PosChoice : public Choice {
00141   private:
00143     const Pos _pos;
00145     const typename ViewSel::Choice _viewchoice;
00146   public:
00148     PosChoice(const Brancher& b, unsigned int a, const Pos& p,
00149               const typename ViewSel::Choice& viewc);
00151     const Pos& pos(void) const;
00153     const typename ViewSel::Choice& viewchoice(void) const;
00155     virtual size_t size(void) const;
00156   };
00157 
00159   template<class ViewSel, class ValSel>
00160   class GECODE_VTABLE_EXPORT PosValChoice : public PosChoice<ViewSel> {
00161   private:
00163     const typename ValSel::Choice _valchoice;
00165     const typename ValSel::Val _val;
00166   public:
00168     PosValChoice(const Brancher& b, const Pos& p,
00169                  const typename ViewSel::Choice& viewc,
00170                  const typename ValSel::Choice& valc,
00171                  const typename ValSel::Val& n);
00173     const typename ValSel::Choice& valchoice(void) const;
00175     const typename ValSel::Val& val(void) const;
00177     virtual size_t size(void) const;
00178   };
00180 
00181 
00182 
00183 
00184   /*
00185    * Position information
00186    *
00187    */
00188   forceinline
00189   Pos::Pos(int p) : pos(p) {}
00190 
00191 
00192   /*
00193    * Choice with position
00194    *
00195    */
00196   template<class ViewSel>
00197   forceinline
00198   PosChoice<ViewSel>::PosChoice(const Brancher& b, unsigned int a, 
00199                                 const Pos& p,
00200                                 const typename ViewSel::Choice& viewc)
00201     : Choice(b,a), _pos(p), _viewchoice(viewc) {}
00202   template<class ViewSel>
00203   forceinline const Pos&
00204   PosChoice<ViewSel>::pos(void) const {
00205     return _pos;
00206   }
00207   template<class ViewSel>
00208   forceinline const typename ViewSel::Choice&
00209   PosChoice<ViewSel>::viewchoice(void) const {
00210     return _viewchoice;
00211   }
00212   template<class ViewSel>
00213   forceinline size_t
00214   PosChoice<ViewSel>::size(void) const {
00215     return sizeof(PosChoice<ViewSel>) + _viewchoice.size();
00216   }
00217 
00218 
00219   /*
00220    * %Choice with position and value
00221    *
00222    */
00223   template<class ViewSel, class ValSel>
00224   forceinline
00225   PosValChoice<ViewSel,ValSel>
00226   ::PosValChoice(const Brancher& b, const Pos& p,
00227                  const typename ViewSel::Choice& viewc,
00228                  const typename ValSel::Choice& valc,
00229                  const typename ValSel::Val& n)
00230     : PosChoice<ViewSel>(b,ValSel::alternatives,p,viewc),
00231       _valchoice(valc), _val(n) {}
00232 
00233   template<class ViewSel, class ValSel>
00234   forceinline const typename ValSel::Choice&
00235   PosValChoice<ViewSel,ValSel>::valchoice(void) const {
00236     return _valchoice;
00237   }
00238 
00239   template<class ViewSel, class ValSel>
00240   forceinline const typename ValSel::Val&
00241   PosValChoice<ViewSel,ValSel>::val(void) const {
00242     return _val;
00243   }
00244 
00245   template<class ViewSel, class ValSel>
00246   forceinline size_t
00247   PosValChoice<ViewSel, ValSel>::size(void) const {
00248     return sizeof(PosValChoice<ViewSel,ValSel>) + _valchoice.size();
00249   }
00250 
00251 
00252   /*
00253    * Generic brancher based on view selection
00254    *
00255    */
00256 
00257   template<class ViewSel>
00258   forceinline
00259   ViewBrancher<ViewSel>::ViewBrancher(Home home,
00260                                       ViewArray<typename ViewSel::View>& x0,
00261                                       ViewSel& vi_s)
00262     : Brancher(home), x(x0), start(0), viewsel(vi_s) {}
00263 
00264 
00265   template<class ViewSel>
00266   forceinline
00267   ViewBrancher<ViewSel>::ViewBrancher(Space& home, bool share,
00268                                       ViewBrancher& b)
00269     : Brancher(home,share,b), start(b.start) {
00270     x.update(home,share,b.x);
00271     viewsel.update(home,share,b.viewsel);
00272   }
00273 
00274   template<class ViewSel>
00275   bool
00276   ViewBrancher<ViewSel>::status(const Space&) const {
00277     for (int i=start; i < x.size(); i++)
00278       if (!x[i].assigned()) {
00279         start = i;
00280         return true;
00281       }
00282     return false;
00283   }
00284 
00285   template<class ViewSel>
00286   forceinline Pos
00287   ViewBrancher<ViewSel>::pos(Space& home) {
00288     assert(!x[start].assigned());
00289     int i = start;
00290     int b = i++;
00291     if (viewsel.init(home,x[b]) != VSS_BEST)
00292       for (; i < x.size(); i++)
00293         if (!x[i].assigned())
00294           switch (viewsel.select(home,x[i])) {
00295           case VSS_BETTER:              b=i; break;
00296           case VSS_BEST:                b=i; goto create;
00297           case VSS_TIE: case VSS_WORSE: break;
00298           default:                      GECODE_NEVER;
00299           }
00300   create:
00301     Pos p(b);
00302     return p;
00303   }
00304 
00305   template<class ViewSel>
00306   forceinline typename ViewSel::View
00307   ViewBrancher<ViewSel>::view(const Pos& p) const {
00308     return x[p.pos];
00309   }
00310 
00311   template<class ViewSel>
00312   forceinline size_t
00313   ViewBrancher<ViewSel>::dispose(Space& home) {
00314     viewsel.dispose(home);
00315     (void) Brancher::dispose(home);
00316     return sizeof(ViewBrancher<ViewSel>);
00317   }
00318 
00319 
00320 
00321   /*
00322    * Generic brancher based on variable/value selection
00323    *
00324    */
00325 
00326   template<class ViewSel, class ValSel>
00327   forceinline
00328   ViewValBrancher<ViewSel,ValSel>::
00329   ViewValBrancher(Home home, ViewArray<typename ViewSel::View>& x,
00330                   ViewSel& vi_s, ValSel& va_s)
00331     : ViewBrancher<ViewSel>(home,x,vi_s), valsel(va_s) {}
00332 
00333   template<class ViewSel, class ValSel>
00334   void
00335   ViewValBrancher<ViewSel,ValSel>::
00336   post(Home home, ViewArray<typename ViewSel::View>& x,
00337        ViewSel& vi_s, ValSel& va_s) {
00338     (void) new (home) ViewValBrancher<ViewSel,ValSel>(home,x,vi_s,va_s);
00339   }
00340 
00341   template<class ViewSel, class ValSel>
00342   forceinline
00343   ViewValBrancher<ViewSel,ValSel>::
00344   ViewValBrancher(Space& home, bool share, ViewValBrancher& b)
00345     : ViewBrancher<ViewSel>(home,share,b) {
00346     valsel.update(home,share,b.valsel);
00347   }
00348 
00349   template<class ViewSel, class ValSel>
00350   Actor*
00351   ViewValBrancher<ViewSel,ValSel>::copy(Space& home, bool share) {
00352     return new (home)
00353       ViewValBrancher<ViewSel,ValSel>(home,share,*this);
00354   }
00355 
00356   template<class ViewSel, class ValSel>
00357   const Choice*
00358   ViewValBrancher<ViewSel,ValSel>::choice(Space& home) {
00359     Pos p = ViewBrancher<ViewSel>::pos(home);
00360     typename ValSel::View v(ViewBrancher<ViewSel>::view(p).var());
00361     typename ValSel::Val val(valsel.val(home,v));
00362     return new PosValChoice<ViewSel,ValSel>
00363       (*this,p,
00364        viewsel.choice(home),valsel.choice(home),val);
00365   }
00366 
00367   template<class ViewSel, class ValSel>
00368   ExecStatus
00369   ViewValBrancher<ViewSel,ValSel>
00370   ::commit(Space& home, const Choice& c, unsigned int a) {
00371     const PosValChoice<ViewSel,ValSel>& pvc
00372       = static_cast<const PosValChoice<ViewSel,ValSel>&>(c);
00373     typename ValSel::View
00374       v(ViewBrancher<ViewSel>::view(pvc.pos()).var());
00375     viewsel.commit(home, pvc.viewchoice(), a);
00376     valsel.commit(home, pvc.valchoice(), a);
00377     return me_failed(valsel.tell(home,a,v,pvc.val())) ? ES_FAILED : ES_OK;
00378   }
00379 
00380   template<class ViewSel, class ValSel>
00381   forceinline size_t
00382   ViewValBrancher<ViewSel,ValSel>::dispose(Space& home) {
00383     valsel.dispose(home);
00384     (void) ViewBrancher<ViewSel>::dispose(home);
00385     return sizeof(ViewValBrancher<ViewSel,ValSel>);
00386   }
00387 
00388 }
00389 
00390 // STATISTICS: kernel-branch