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