branching-tiebreak.hpp

00001 /* -*- mode: C++; c-basic-offset: 2; indent-tabs-mode: nil -*- */
00002 /*
00003  *  Main author:
00004  *     Christian Schulte <schulte@gecode.org>
00005  *
00006  *  Copyright:
00007  *     Christian Schulte, 2008
00008  *
00009  *  Last modified:
00010  *     $Date: 2009-02-05 11:48:53 +0100 (Thu, 05 Feb 2009) $ by $Author: schulte $
00011  *     $Revision: 8155 $
00012  *
00013  *  This file is part of Gecode, the generic constraint
00014  *  development environment:
00015  *     http://www.gecode.org
00016  *
00017  *  Permission is hereby granted, free of charge, to any person obtaining
00018  *  a copy of this software and associated documentation files (the
00019  *  "Software"), to deal in the Software without restriction, including
00020  *  without limitation the rights to use, copy, modify, merge, publish,
00021  *  distribute, sublicense, and/or sell copies of the Software, and to
00022  *  permit persons to whom the Software is furnished to do so, subject to
00023  *  the following conditions:
00024  *
00025  *  The above copyright notice and this permission notice shall be
00026  *  included in all copies or substantial portions of the Software.
00027  *
00028  *  THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,
00029  *  EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF
00030  *  MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND
00031  *  NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE
00032  *  LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION
00033  *  OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION
00034  *  WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
00035  *
00036  */
00037 
00038 namespace Gecode {
00039 
00049   template<class A, class B>
00050   class ViewSelTieBreakStatic {
00051   protected:
00053     A a;
00055     B b;
00056   public:
00058     typedef typename A::View View;
00060     class Desc {
00061     public:
00063       typename A::Desc a;
00065       typename B::Desc b;
00067       Desc(const typename A::Desc& a, const typename B::Desc& b);
00069       size_t size(void) const;
00070     };
00072     ViewSelTieBreakStatic(void);
00074     ViewSelTieBreakStatic(Space& home, A& a, B& b);
00076     ViewSelStatus init(Space& home, typename A::View x);
00078     ViewSelStatus select(Space& home, typename A::View x);
00080     Desc description(Space& home);
00082     void commit(Space& home, const Desc& d, unsigned a);
00084     void update(Space& home, bool share, ViewSelTieBreakStatic& vs);
00086     void dispose(Space& home);
00087   };
00088 
00092   class DescVirtualBase {
00093   public:
00095     virtual DescVirtualBase* copy(void) const = 0;
00097     virtual size_t size(void) const = 0;
00099     GECODE_KERNEL_EXPORT virtual ~DescVirtualBase(void);
00101 
00102 
00103     static void* operator new(size_t s);
00105     static void  operator delete(void*);
00107   };
00108 
00112   template <class View>
00113   class ViewSelVirtualBase {
00114   public:
00116     virtual ViewSelStatus init(Space& home, View x) = 0;
00118     virtual ViewSelStatus select(Space& home, View x) = 0;
00120     virtual DescVirtualBase* description(Space& home) = 0;
00122     virtual void commit(Space& home, const DescVirtualBase* d, unsigned a) = 0;
00124     virtual ViewSelVirtualBase<View>* copy(Space& home, bool share) = 0;
00126     virtual size_t dispose(Space& home) = 0;
00128 
00129 
00130     static void* operator new(size_t s, Space& home);
00132     static void  operator delete(void* p, Space& home);
00134     static void  operator delete(void*);
00136   };
00137 
00141   template <class Desc>
00142   class DescVirtual : public DescVirtualBase {
00143   public:
00145     Desc desc;
00147     DescVirtual(const Desc& d);
00149     virtual DescVirtualBase* copy(void) const;
00151     virtual size_t size(void) const;
00153     virtual ~DescVirtual(void);
00154   };
00155 
00159   template <class ViewSel>
00160   class ViewSelVirtual : public ViewSelVirtualBase<typename ViewSel::View> {
00161   protected:
00163     ViewSel viewsel;
00164   public:
00166     ViewSelVirtual(Space& home, const VarBranchOptions& vbo);
00168     ViewSelVirtual(Space& home, bool share, ViewSelVirtual& vsv);
00170     virtual ViewSelStatus init(Space& home, typename ViewSel::View x);
00172     virtual ViewSelStatus select(Space& home, typename ViewSel::View x);
00174     virtual DescVirtualBase* description(Space& home);
00176     virtual void commit(Space& home, const DescVirtualBase* d, unsigned a);
00178     virtual ViewSelVirtualBase<typename ViewSel::View>*
00179     copy(Space& home, bool share);
00181     virtual size_t dispose(Space& home);
00182   };
00183 
00187   template<class _View>
00188   class ViewSelTieBreakDynamic {
00189   protected:
00191     int n;
00193     ViewSelVirtualBase<_View>** tb;
00194   public:
00196     typedef _View View;
00198     class Desc {
00199     public:
00201       int n;
00203       DescVirtualBase** d;
00205       Desc(Space& home, ViewSelVirtualBase<_View>** tb, int n0);
00207       Desc(const Desc& de);
00209       const Desc& operator =(const Desc& de);
00211       void commit(Space& home, unsigned int a,
00212                   ViewSelVirtualBase<_View>** tb)  const;
00214       size_t size(void) const;
00216       ~Desc(void);
00217     };
00219     ViewSelTieBreakDynamic(void);
00221     ViewSelTieBreakDynamic(Space& home, ViewSelVirtualBase<_View>** vsv,
00222                            int n);
00224     ViewSelStatus init(Space& home, _View x);
00226     ViewSelStatus select(Space& home, _View x);
00228     Desc description(Space& home);
00230     void commit(Space& home, const Desc& d, unsigned a);
00232     void update(Space& home, bool share, ViewSelTieBreakDynamic& vs);
00234     void dispose(Space& home);
00235   };
00237 
00238 
00239   // Select variable with static tie breaking
00240   template<class A, class B>
00241   forceinline
00242   ViewSelTieBreakStatic<A,B>::Desc::Desc(const typename A::Desc& a0,
00243                                          const typename B::Desc& b0)
00244     : a(a0), b(b0) {}
00245   template<class A, class B>
00246   forceinline size_t
00247   ViewSelTieBreakStatic<A,B>::Desc::size(void) const {
00248     return a.size() + b.size();
00249   }
00250 
00251   template<class A, class B>
00252   forceinline
00253   ViewSelTieBreakStatic<A,B>::ViewSelTieBreakStatic(void) {}
00254   template<class A, class B>
00255   forceinline
00256   ViewSelTieBreakStatic<A,B>::
00257   ViewSelTieBreakStatic(Space&, A& a0, B& b0)
00258     : a(a0), b(b0) {}
00259   template<class A, class B>
00260   forceinline ViewSelStatus
00261   ViewSelTieBreakStatic<A,B>::init(Space& home, typename A::View x) {
00262     ViewSelStatus s = a.init(home,x);
00263     return (b.init(home,x) != VSS_BEST) ? VSS_BETTER : s;
00264   }
00265   template<class A, class B>
00266   forceinline ViewSelStatus
00267   ViewSelTieBreakStatic<A,B>::select(Space& home, typename A::View x) {
00268     switch (a.select(home,x)) {
00269     case VSS_BEST:
00270       return (b.init(home,x) != VSS_BEST) ? VSS_BETTER : VSS_BEST;
00271     case VSS_BETTER:
00272       (void) b.init(home,x);
00273       return VSS_BETTER;
00274     case VSS_WORSE:
00275       return VSS_WORSE;
00276     case VSS_TIE:
00277       switch (b.select(home,x)) {
00278       case VSS_BEST:   return VSS_BETTER;
00279       case VSS_BETTER: return VSS_BETTER;
00280       case VSS_TIE:    return VSS_TIE;
00281       case VSS_WORSE:  return VSS_WORSE;
00282       default: GECODE_NEVER;
00283       }
00284     default: GECODE_NEVER;
00285       return VSS_WORSE;
00286     }
00287   }
00288   template<class A, class B>
00289   forceinline typename ViewSelTieBreakStatic<A,B>::Desc
00290   ViewSelTieBreakStatic<A,B>::description(Space& home) {
00291     typename ViewSelTieBreakStatic<A,B>::Desc d(a.description(home),
00292                                                 b.description(home));
00293     return d;
00294   }
00295   template<class A, class B>
00296   forceinline void
00297   ViewSelTieBreakStatic<A,B>::commit(Space& home, const Desc& d,
00298                                      unsigned int al) {
00299     a.commit(home, d.a, al);
00300     b.commit(home, d.b, al);
00301   }
00302   template<class A, class B>
00303   forceinline void
00304   ViewSelTieBreakStatic<A,B>::update(Space& home, bool share,
00305                                      ViewSelTieBreakStatic<A,B>& vstb) {
00306     a.update(home,share,vstb.a);
00307     b.update(home,share,vstb.b);
00308   }
00309   template<class A, class B>
00310   forceinline void
00311   ViewSelTieBreakStatic<A,B>::dispose(Space& home) {
00312     a.dispose(home);
00313     b.dispose(home);
00314   }
00315 
00316 
00317   // Virtualized view selection
00318   template <class View>
00319   forceinline void
00320   ViewSelVirtualBase<View>::operator delete(void*) {}
00321   template <class View>
00322   forceinline void
00323   ViewSelVirtualBase<View>::operator delete(void*, Space&) {}
00324   template <class View>
00325   forceinline void*
00326   ViewSelVirtualBase<View>::operator new(size_t s, Space& home) {
00327     return home.ralloc(s);
00328   }
00329 
00330   // Virtualized description
00331   forceinline void
00332   DescVirtualBase::operator delete(void* p) {
00333     heap.rfree(p);
00334   }
00335   forceinline void*
00336   DescVirtualBase::operator new(size_t s) {
00337     return heap.ralloc(s);
00338   }
00339   forceinline
00340   DescVirtualBase::~DescVirtualBase(void) {
00341   }
00342 
00343 
00344   template <class Desc>
00345   forceinline
00346   DescVirtual<Desc>::DescVirtual(const Desc& d)
00347     : desc(d) {}
00348   template <class Desc>
00349   forceinline DescVirtualBase*
00350   DescVirtual<Desc>::copy(void) const {
00351     return new DescVirtual<Desc>(desc);
00352   }
00353   template <class Desc>
00354   forceinline size_t
00355   DescVirtual<Desc>::size(void) const {
00356     return sizeof(DescVirtual<Desc>);
00357   }
00358   template <class Desc>
00359   DescVirtual<Desc>::~DescVirtual(void) {}
00360 
00361 
00362   template<class ViewSel>
00363   forceinline
00364   ViewSelVirtual<ViewSel>::ViewSelVirtual(Space& home,
00365                                           const VarBranchOptions& vbo)
00366     : viewsel(home,vbo) {}
00367   template <class ViewSel>
00368   forceinline
00369   ViewSelVirtual<ViewSel>::ViewSelVirtual(Space& home, bool share,
00370                                           ViewSelVirtual<ViewSel>& vsv) {
00371     viewsel.update(home,share,vsv.viewsel);
00372   }
00373   template <class ViewSel>
00374   ViewSelStatus
00375   ViewSelVirtual<ViewSel>::init(Space& home, typename ViewSel::View x) {
00376     return viewsel.init(home,x);
00377   }
00378   template <class ViewSel>
00379   ViewSelStatus
00380   ViewSelVirtual<ViewSel>::select(Space& home, typename ViewSel::View x) {
00381     return viewsel.select(home,x);
00382   }
00383   template <class ViewSel>
00384   DescVirtualBase*
00385   ViewSelVirtual<ViewSel>::description(Space& home) {
00386     return new DescVirtual<typename ViewSel::Desc>(viewsel.description(home));
00387   }
00388   template <class ViewSel>
00389   void
00390   ViewSelVirtual<ViewSel>::commit(Space& home, const DescVirtualBase* _d,
00391                                   unsigned int a) {
00392     const DescVirtual<typename ViewSel::Desc>* d =
00393       static_cast<const DescVirtual<typename ViewSel::Desc>*>(_d);
00394     viewsel.commit(home, d->desc, a);
00395   }
00396   template <class ViewSel>
00397   ViewSelVirtualBase<typename ViewSel::View>*
00398   ViewSelVirtual<ViewSel>::copy(Space& home, bool share) {
00399     return new (home) ViewSelVirtual<ViewSel>(home,share,*this);
00400   }
00401   template <class ViewSel>
00402   size_t
00403   ViewSelVirtual<ViewSel>::dispose(Space& home) {
00404     viewsel.dispose(home);
00405     return sizeof(ViewSelVirtual<ViewSel>);
00406   }
00407 
00408 
00409   // Description for dynamic tie breaking
00410   template<class View>
00411   forceinline
00412   ViewSelTieBreakDynamic<View>::Desc::Desc
00413   (Space& home, ViewSelVirtualBase<View>** tb, int n0)
00414     : n(n0), d(heap.alloc<DescVirtualBase*>(n)) {
00415     for (int i=n; i--; )
00416       d[i] = tb[i]->description(home);
00417   }
00418   template<class View>
00419   forceinline
00420   ViewSelTieBreakDynamic<View>::Desc::Desc(const Desc& de)
00421     : n(de.n), d(heap.alloc<DescVirtualBase*>(n)) {
00422     for (int i=n; i--; )
00423       d[i] = de.d[i]->copy();
00424   }
00425   template<class View>
00426   forceinline const typename ViewSelTieBreakDynamic<View>::Desc&
00427   ViewSelTieBreakDynamic<View>::Desc::operator =(const Desc& de) {
00428     if (&de != this) {
00429       assert(de.n == n);
00430       for (int i=n; i--; ) {
00431         delete d[i]; d[i] = de.d[i]->copy();
00432       }
00433     }
00434     return *this;
00435   }
00436   template<class View>
00437   forceinline void
00438   ViewSelTieBreakDynamic<View>::Desc::commit
00439   (Space& home, unsigned int a, ViewSelVirtualBase<View>** tb)  const {
00440     for (int i=n; i--; )
00441       tb[i]->commit(home, d[i], a);
00442   }
00443   template<class View>
00444   forceinline size_t
00445   ViewSelTieBreakDynamic<View>::Desc::size(void) const {
00446     size_t s = (sizeof(typename ViewSelTieBreakDynamic<View>::Desc) +
00447                 n * sizeof(DescVirtualBase*));
00448     for (int i=n; i--; )
00449       s += d[i]->size();
00450     return s;
00451   }
00452   template<class View>
00453   forceinline
00454   ViewSelTieBreakDynamic<View>::Desc::~Desc(void) {
00455     for (int i=n; i--; )
00456       delete d[i];
00457     heap.free(d,n);
00458   }
00459 
00460 
00461   // Select variable with dynamic tie breaking
00462   template<class View>
00463   forceinline
00464   ViewSelTieBreakDynamic<View>::ViewSelTieBreakDynamic(void) {}
00465   template<class View>
00466   forceinline
00467   ViewSelTieBreakDynamic<View>::
00468   ViewSelTieBreakDynamic(Space& home, ViewSelVirtualBase<View>** vsv, int n0)
00469     : n(n0), tb(home.alloc<ViewSelVirtualBase<View>*>(n)) {
00470     for (int i=0; i<n; i++)
00471       tb[i]=vsv[i];
00472     assert(n > 0);
00473   }
00474   template<class View>
00475   forceinline ViewSelStatus
00476   ViewSelTieBreakDynamic<View>::init(Space& home, View x) {
00477     ViewSelStatus s = VSS_BEST;
00478     for (int i=0; i<n; i++)
00479       if (tb[i]->init(home,x) != VSS_BEST)
00480         s = VSS_BETTER;
00481     return s;
00482   }
00483   template<class View>
00484   forceinline ViewSelStatus
00485   ViewSelTieBreakDynamic<View>::select(Space& home, View x) {
00486     switch (tb[0]->select(home,x)) {
00487     case VSS_BEST:
00488       {
00489         ViewSelStatus s = VSS_BEST;
00490         for (int i=1; i<n; i++)
00491           if (tb[i]->init(home,x) != VSS_BEST)
00492             s = VSS_BETTER;
00493         return s;
00494       }
00495     case VSS_BETTER:
00496       for (int i=1; i<n; i++)
00497         (void) tb[i]->init(home,x);
00498       return VSS_BETTER;
00499     case VSS_WORSE:
00500       return VSS_WORSE;
00501     case VSS_TIE:
00502       for (int i=1; i<n; i++)
00503         switch (tb[i]->select(home,x)) {
00504         case VSS_BEST: case VSS_BETTER:
00505           for (int j=i+1; j<n; j++)
00506             (void) tb[j]->init(home,x);
00507           return VSS_BETTER;
00508         case VSS_TIE:    break;
00509         case VSS_WORSE:  return VSS_WORSE;
00510         default: GECODE_NEVER;
00511         }
00512       return VSS_TIE;
00513     default: GECODE_NEVER;
00514       return VSS_WORSE;
00515     }
00516   }
00517   template<class View>
00518   forceinline typename ViewSelTieBreakDynamic<View>::Desc
00519   ViewSelTieBreakDynamic<View>::description(Space& home) {
00520     Desc d(home,tb,n);
00521     return d;
00522   }
00523   template<class View>
00524   forceinline void
00525   ViewSelTieBreakDynamic<View>::commit
00526   (Space& home, const typename ViewSelTieBreakDynamic<View>::Desc& d,
00527    unsigned int a) {
00528     d.commit(home,a,tb);
00529   }
00530   template<class View>
00531   forceinline void
00532   ViewSelTieBreakDynamic<View>::update(Space& home, bool share,
00533                                        ViewSelTieBreakDynamic<View>& vstb) {
00534     n = vstb.n;
00535     tb = home.alloc<ViewSelVirtualBase<View>*>(n);
00536     for (int i=0; i<n; i++)
00537       tb[i] = vstb.tb[i]->copy(home,share);
00538   }
00539   template<class View>
00540   forceinline void
00541   ViewSelTieBreakDynamic<View>::dispose(Space& home) {
00542     for (int i=0; i<n; i++)
00543       home.rfree(tb[i],tb[i]->dispose(home));
00544     home.free<ViewSelVirtualBase<View>*>(tb,n);
00545   }
00546 
00547 }
00548 
00549 // STATISTICS: kernel-branch