Generated on Wed Mar 19 07:30:01 2008 for Gecode by doxygen 1.5.5

branching.icc

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: 2008-02-16 10:42:26 +0100 (Sat, 16 Feb 2008) $ by $Author: tack $
00013  *     $Revision: 6185 $
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_NONE,   
00053     VSS_SELECT, 
00054     VSS_COMMIT  
00055   };
00056 
00083   template <class View, class Val, class ViewSel, class ValSel>
00084   class ViewValBranching : public Branching {
00085   protected:
00086     ViewArray<View> x;  
00087     mutable int start;  
00088 
00089     ViewValBranching(Space* home, bool share, ViewValBranching& b);
00090   public:
00092     ViewValBranching(Space* home, ViewArray<View>& x);
00094     virtual bool status(const Space* home) const;
00096     virtual const BranchingDesc* description(const Space* home) const;
00098     virtual ExecStatus commit(Space* home, const BranchingDesc* d,
00099                               unsigned int a);
00101     virtual Reflection::ActorSpec spec(const Space* home,
00102                                        Reflection::VarMap& m) const;
00104     virtual Reflection::BranchingSpec
00105     branchingSpec(const Space* home, 
00106                   Reflection::VarMap& m,
00107                   const BranchingDesc* d) const;
00109     static Support::Symbol ati(void);
00111     static void post(Space* home, Reflection::VarMap& m,
00112                      const Reflection::ActorSpec& spec);
00114     virtual Actor* copy(Space* home, bool share);
00115   };
00116 
00134   template <class View, class Val, class ValSel>
00135   class ViewValAssignment : public Branching {
00136   protected:
00137     ViewArray<View> x;  
00138     mutable int start;  
00139 
00140     ViewValAssignment(Space* home, bool share, ViewValAssignment& b);
00141   public:
00143     ViewValAssignment(Space* home, ViewArray<View>& x);
00145     virtual bool status(const Space* home) const;
00147     virtual const BranchingDesc* description(const Space* home) const;
00149     virtual ExecStatus commit(Space* home, const BranchingDesc* d,
00150                               unsigned int a);
00152     virtual Reflection::ActorSpec spec(const Space* home,
00153                                         Reflection::VarMap& m) const;
00155     virtual Reflection::BranchingSpec
00156     branchingSpec(const Space* home, 
00157                   Reflection::VarMap& m,
00158                   const BranchingDesc* d) const;
00160     static Support::Symbol ati(void);
00162     static void post(Space* home, Reflection::VarMap& m,
00163                      const Reflection::ActorSpec& spec);
00165     virtual Actor* copy(Space* home, bool share);
00166   };
00167 
00173   template <class Val, unsigned int alt>
00174   class PosValDesc : public BranchingDesc {
00175   protected:
00177     const int _pos;
00179     const Val _val;
00181     const int _start;
00182   public:
00188     PosValDesc(const Branching* b, const int p, const Val& n, const int s=0);
00190     int pos(void) const;
00192     Val val(void) const;
00194     int start(void) const;
00196     virtual size_t size(void) const;
00197   };
00198 
00200 
00201 
00202 
00203 
00204 
00205 
00206   /*
00207    * Branching descriptions with position and value
00208    *
00209    */
00210 
00211   template <class Val, unsigned int alt>
00212   forceinline
00213   PosValDesc<Val,alt>::PosValDesc(const Branching* b, const int p,
00214                                   const Val& n, const int s)
00215     : BranchingDesc(b,alt), _pos(p), _val(n), _start(s) {}
00216 
00217   template <class Val, unsigned int alt>
00218   forceinline int
00219   PosValDesc<Val,alt>::pos(void) const {
00220     return _pos;
00221   }
00222 
00223   template <class Val, unsigned int alt>
00224   forceinline Val
00225   PosValDesc<Val,alt>::val(void) const {
00226     return _val;
00227   }
00228 
00229   template <class Val, unsigned int alt>
00230   forceinline int
00231   PosValDesc<Val,alt>::start(void) const {
00232     return _start;
00233   }
00234 
00235   template <class Val, unsigned int alt>
00236   size_t
00237   PosValDesc<Val,alt>::size(void) const {
00238     return sizeof(PosValDesc<Val,alt>);
00239   }
00240 
00241 
00242   /*
00243    * Generic branching based on variable/value selection
00244    *
00245    */
00246 
00247   template <class View, class Val, class ViewSel, class ValSel>
00248   forceinline
00249   ViewValBranching<View,Val,ViewSel,ValSel>
00250   ::ViewValBranching(Space* home, ViewArray<View>& x0)
00251     : Branching(home), x(x0), start(0) {}
00252 
00253 
00254   template <class View, class Val, class ViewSel, class ValSel>
00255   forceinline
00256   ViewValBranching<View,Val,ViewSel,ValSel>
00257   ::ViewValBranching(Space* home, bool share, ViewValBranching& b)
00258     : Branching(home,share,b), start(b.start) {
00259     x.update(home,share,b.x);
00260   }
00261 
00262   template <class View, class Val, class ViewSel, class ValSel>
00263   Actor*
00264   ViewValBranching<View,Val,ViewSel,ValSel>::copy(Space* home, bool share) {
00265     return new (home)
00266       ViewValBranching<View,Val,ViewSel,ValSel>(home,share,*this);
00267   }
00268 
00269   template <class View, class Val, class ViewSel, class ValSel>
00270   bool
00271   ViewValBranching<View,Val,ViewSel,ValSel>
00272   ::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 View, class Val, class ViewSel, class ValSel>
00282   const BranchingDesc*
00283   ViewValBranching<View,Val,ViewSel,ValSel>
00284   ::description(const Space* home) const {
00285     assert(!x[start].assigned());
00286     ViewSel vs; // For view selection
00287     ValSel  vl; // For value selection
00288     int i = start;
00289     int b = i++;
00290     if (vs.init(home,x[b]) != VSS_COMMIT)
00291       for (; i < x.size(); i++)
00292         if (!x[i].assigned())
00293           switch (vs.select(home,x[i])) {
00294           case VSS_SELECT: b=i; break;
00295           case VSS_COMMIT: b=i; goto create;
00296           case VSS_NONE:   break;
00297           default:         GECODE_NEVER;
00298           }
00299   create:
00300     return new PosValDesc<Val,2>(this,b-start,vl.val(home,x[b]),start);
00301   }
00302 
00303   template <class View, class Val, class ViewSel, class ValSel>
00304   ExecStatus
00305   ViewValBranching<View,Val,ViewSel,ValSel>
00306   ::commit(Space* home, const BranchingDesc* d, unsigned int a) {
00307     const PosValDesc<Val,2>* pvd = static_cast<const PosValDesc<Val,2>*>(d);
00308     // Eliminate views from x[0] ... x[d->start()-1]
00309     x.drop_fst(pvd->start()); start = 0;
00310     ValSel vs;
00311     return me_failed(vs.tell(home,a,x[pvd->pos()],pvd->val()))
00312       ? ES_FAILED : ES_OK;
00313   }
00314 
00315   template <class View, class Val, class ViewSel, class ValSel>
00316   Support::Symbol
00317   ViewValBranching<View,Val,ViewSel,ValSel>::ati(void) {
00318     return Reflection::mangle<View,Val,ViewSel,ValSel>("Gecode::ViewValBranching");
00319   }
00320 
00321   template <class View, class Val, class ViewSel, class ValSel>
00322   void
00323   ViewValBranching<View,Val,ViewSel,ValSel>
00324     ::post(Space* home, Reflection::VarMap& vars,
00325            const Reflection::ActorSpec& spec) {
00326     spec.checkArity(1);
00327     ViewArray<View> x(home, vars, spec[0]);
00328     (void) new (home) ViewValBranching<View,Val,ViewSel,ValSel>(home, x);
00329   }
00330 
00331   template <class View, class Val, class ViewSel, class ValSel>
00332   Reflection::ActorSpec
00333   ViewValBranching<View,Val,ViewSel,ValSel>::spec(const Space* home,
00334     Reflection::VarMap& m) const {
00335     Reflection::ActorSpec s(ati());
00336     return s << x.spec(home, m);
00337   }
00338 
00339   template <class View, class Val, class ViewSel, class ValSel>
00340   Reflection::BranchingSpec
00341   ViewValBranching<View,Val,ViewSel,ValSel>::branchingSpec(const Space* home, 
00342     Reflection::VarMap& m, const BranchingDesc* d) const {
00343     Reflection::BranchingSpec bs(d);
00344     const PosValDesc<Val,2>* pvd = static_cast<const PosValDesc<Val,2>*>(d);
00345     ValSel vs;
00346     vs.branchingSpec(home, m, bs, 2, x[pvd->start()+pvd->pos()], pvd->val());
00347     return bs;
00348   }
00349 
00350   /*
00351    * Generic assignment based on value selection
00352    *
00353    */
00354 
00355   template <class View, class Val, class ValSel>
00356   forceinline
00357   ViewValAssignment<View,Val,ValSel>
00358   ::ViewValAssignment(Space* home, ViewArray<View>& x0)
00359     : Branching(home), x(x0), start(0) {}
00360 
00361 
00362   template <class View, class Val, class ValSel>
00363   forceinline
00364   ViewValAssignment<View,Val,ValSel>
00365   ::ViewValAssignment(Space* home, bool share, ViewValAssignment& b)
00366     : Branching(home,share,b), start(b.start) {
00367     x.update(home,share,b.x);
00368   }
00369 
00370   template <class View, class Val, class ValSel>
00371   Actor*
00372   ViewValAssignment<View,Val,ValSel>::copy(Space* home, bool share) {
00373     return new (home)
00374       ViewValAssignment<View,Val,ValSel>(home,share,*this);
00375   }
00376 
00377   template <class View, class Val, class ValSel>
00378   bool
00379   ViewValAssignment<View,Val,ValSel>
00380   ::status(const Space*) const {
00381     for (int i=start; i < x.size(); i++)
00382       if (!x[i].assigned()) {
00383         start = i;
00384         return true;
00385       }
00386     return false;
00387   }
00388 
00389   template <class View, class Val, class ValSel>
00390   const BranchingDesc*
00391   ViewValAssignment<View,Val,ValSel>
00392   ::description(const Space* home) const {
00393     assert(!x[start].assigned());
00394     ValSel vl; // For value selection
00395     return new PosValDesc<Val,1>(this,0,vl.val(home,x[start]),start);
00396   }
00397 
00398   template <class View, class Val, class ValSel>
00399   ExecStatus
00400   ViewValAssignment<View,Val,ValSel>
00401   ::commit(Space* home, const BranchingDesc* d, unsigned int) {
00402     const PosValDesc<Val,1>* pvd = static_cast<const PosValDesc<Val,1>*>(d);
00403     // Eliminate views from x[0] ... x[d->start()-1]
00404     x.drop_fst(pvd->start()); start = 0;
00405     ValSel vs;
00406     return me_failed(vs.tell(home,0,x[pvd->pos()],pvd->val()))
00407       ? ES_FAILED : ES_OK;
00408   }
00409 
00410   template <class View, class Val, class ValSel>
00411   Support::Symbol
00412   ViewValAssignment<View,Val,ValSel>::ati(void) {
00413     return Reflection::mangle<View,Val,ValSel>("Gecode::ViewValAssignment");
00414   }
00415 
00416   template <class View, class Val, class ValSel>
00417   void
00418   ViewValAssignment<View,Val,ValSel>
00419     ::post(Space* home, Reflection::VarMap& vars,
00420            const Reflection::ActorSpec& spec) {
00421     spec.checkArity(1);
00422     ViewArray<View> x(home, vars, spec[0]);
00423     (void) new (home) ViewValAssignment<View,Val,ValSel>(home, x);
00424   }
00425 
00426   template <class View, class Val, class ValSel>
00427   Reflection::ActorSpec
00428   ViewValAssignment<View,Val,ValSel>::spec(const Space* home,
00429     Reflection::VarMap& m) const {
00430     Reflection::ActorSpec s(ati());
00431     return s << x.spec(home, m);
00432   }
00433 
00434   template <class View, class Val, class ValSel>
00435   Reflection::BranchingSpec
00436   ViewValAssignment<View,Val,ValSel>::branchingSpec(const Space* home, 
00437     Reflection::VarMap& m, const BranchingDesc* d) const {
00438     Reflection::BranchingSpec bs(d);
00439     const PosValDesc<Val,1>* pvd = static_cast<const PosValDesc<Val,1>*>(d);
00440     ValSel vs;
00441     vs.branchingSpec(home, m, bs, 1, x[pvd->start()+pvd->pos()], pvd->val());
00442     return bs;
00443   }
00444 
00445 }
00446 
00447 // STATISTICS: kernel-other