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

brancher-tiebreak.hpp

Go to the documentation of this file.
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-09-30 12:12:35 +0200 (Wed, 30 Sep 2009) $ by $Author: tack $
00011  *     $Revision: 9779 $
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 Choice {
00061     public:
00063       typename A::Choice a;
00065       typename B::Choice b;
00067       Choice(const typename A::Choice& a, const typename B::Choice& 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     Choice choice(Space& home);
00082     void commit(Space& home, const Choice& c, unsigned int a);
00084     void update(Space& home, bool share, ViewSelTieBreakStatic& vs);
00086     void dispose(Space& home);
00087   };
00088 
00092   class ChoiceVirtualBase {
00093   public:
00095     virtual ChoiceVirtualBase* copy(void) const = 0;
00097     virtual size_t size(void) const = 0;
00099     GECODE_KERNEL_EXPORT virtual ~ChoiceVirtualBase(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 ChoiceVirtualBase* choice(Space& home) = 0;
00122     virtual void commit(Space& home, const ChoiceVirtualBase* c, 
00123                         unsigned int a) = 0;
00125     virtual ViewSelVirtualBase<View>* copy(Space& home, bool share) = 0;
00127     virtual size_t dispose(Space& home) = 0;
00129 
00130 
00131     static void* operator new(size_t s, Space& home);
00133     static void  operator delete(void* p, Space& home);
00135     static void  operator delete(void*);
00137   };
00138 
00142   template<class Choice>
00143   class ChoiceVirtual : public ChoiceVirtualBase {
00144   public:
00146     Choice choice;
00148     ChoiceVirtual(const Choice& c);
00150     virtual ChoiceVirtualBase* copy(void) const;
00152     virtual size_t size(void) const;
00154     virtual ~ChoiceVirtual(void);
00155   };
00156 
00160   template<class ViewSel>
00161   class ViewSelVirtual : public ViewSelVirtualBase<typename ViewSel::View> {
00162   protected:
00164     ViewSel viewsel;
00165   public:
00167     ViewSelVirtual(Space& home, const VarBranchOptions& vbo);
00169     ViewSelVirtual(Space& home, bool share, ViewSelVirtual& vsv);
00171     virtual ViewSelStatus init(Space& home, typename ViewSel::View x);
00173     virtual ViewSelStatus select(Space& home, typename ViewSel::View x);
00175     virtual ChoiceVirtualBase* choice(Space& home);
00177     virtual void commit(Space& home, const ChoiceVirtualBase* d,
00178                         unsigned int a);
00180     virtual ViewSelVirtualBase<typename ViewSel::View>*
00181     copy(Space& home, bool share);
00183     virtual size_t dispose(Space& home);
00184   };
00185 
00189   template<class _View>
00190   class ViewSelTieBreakDynamic {
00191   protected:
00193     int n;
00195     ViewSelVirtualBase<_View>** tb;
00196   public:
00198     typedef _View View;
00200     class Choice {
00201     public:
00203       int n;
00205       ChoiceVirtualBase** c;
00207       Choice(Space& home, ViewSelVirtualBase<_View>** tb, int n0);
00209       Choice(const Choice& ce);
00211       const Choice& operator =(const Choice& ce);
00213       void commit(Space& home, unsigned int a,
00214                   ViewSelVirtualBase<_View>** tb)  const;
00216       size_t size(void) const;
00218       ~Choice(void);
00219     };
00221     ViewSelTieBreakDynamic(void);
00223     ViewSelTieBreakDynamic(Space& home, ViewSelVirtualBase<_View>** vsv,
00224                            int n);
00226     ViewSelStatus init(Space& home, _View x);
00228     ViewSelStatus select(Space& home, _View x);
00230     Choice choice(Space& home);
00232     void commit(Space& home,
00233                 const typename ViewSelTieBreakDynamic<_View>::Choice& c,
00234                 unsigned int a);
00236     void update(Space& home, bool share, ViewSelTieBreakDynamic& vs);
00238     void dispose(Space& home);
00239   };
00241 
00242 
00243   // Select variable with static tie breaking
00244   template<class A, class B>
00245   forceinline
00246   ViewSelTieBreakStatic<A,B>::Choice::Choice(const typename A::Choice& a0,
00247                                              const typename B::Choice& b0)
00248     : a(a0), b(b0) {}
00249   template<class A, class B>
00250   forceinline size_t
00251   ViewSelTieBreakStatic<A,B>::Choice::size(void) const {
00252     return a.size() + b.size();
00253   }
00254 
00255   template<class A, class B>
00256   forceinline
00257   ViewSelTieBreakStatic<A,B>::ViewSelTieBreakStatic(void) {}
00258   template<class A, class B>
00259   forceinline
00260   ViewSelTieBreakStatic<A,B>::
00261   ViewSelTieBreakStatic(Space&, A& a0, B& b0)
00262     : a(a0), b(b0) {}
00263   template<class A, class B>
00264   forceinline ViewSelStatus
00265   ViewSelTieBreakStatic<A,B>::init(Space& home, typename A::View x) {
00266     ViewSelStatus s = a.init(home,x);
00267     return (b.init(home,x) != VSS_BEST) ? VSS_BETTER : s;
00268   }
00269   template<class A, class B>
00270   forceinline ViewSelStatus
00271   ViewSelTieBreakStatic<A,B>::select(Space& home, typename A::View x) {
00272     switch (a.select(home,x)) {
00273     case VSS_BEST:
00274       return (b.init(home,x) != VSS_BEST) ? VSS_BETTER : VSS_BEST;
00275     case VSS_BETTER:
00276       (void) b.init(home,x);
00277       return VSS_BETTER;
00278     case VSS_WORSE:
00279       return VSS_WORSE;
00280     case VSS_TIE:
00281       switch (b.select(home,x)) {
00282       case VSS_BEST:   return VSS_BETTER;
00283       case VSS_BETTER: return VSS_BETTER;
00284       case VSS_TIE:    return VSS_TIE;
00285       case VSS_WORSE:  return VSS_WORSE;
00286       default: GECODE_NEVER;
00287       }
00288     default: GECODE_NEVER;
00289       return VSS_WORSE;
00290     }
00291   }
00292   template<class A, class B>
00293   inline typename ViewSelTieBreakStatic<A,B>::Choice
00294   ViewSelTieBreakStatic<A,B>::choice(Space& home) {
00295     typename ViewSelTieBreakStatic<A,B>::Choice c(a.choice(home),
00296                                                   b.choice(home));
00297     return c;
00298   }
00299   template<class A, class B>
00300   forceinline void
00301   ViewSelTieBreakStatic<A,B>::commit(Space& home, const Choice& c,
00302                                      unsigned int al) {
00303     a.commit(home, c.a, al);
00304     b.commit(home, c.b, al);
00305   }
00306   template<class A, class B>
00307   forceinline void
00308   ViewSelTieBreakStatic<A,B>::update(Space& home, bool share,
00309                                      ViewSelTieBreakStatic<A,B>& vstb) {
00310     a.update(home,share,vstb.a);
00311     b.update(home,share,vstb.b);
00312   }
00313   template<class A, class B>
00314   forceinline void
00315   ViewSelTieBreakStatic<A,B>::dispose(Space& home) {
00316     a.dispose(home);
00317     b.dispose(home);
00318   }
00319 
00320 
00321   // Virtualized view selection
00322   template<class View>
00323   forceinline void
00324   ViewSelVirtualBase<View>::operator delete(void*) {}
00325   template<class View>
00326   forceinline void
00327   ViewSelVirtualBase<View>::operator delete(void*, Space&) {}
00328   template<class View>
00329   forceinline void*
00330   ViewSelVirtualBase<View>::operator new(size_t s, Space& home) {
00331     return home.ralloc(s);
00332   }
00333 
00334   // Virtualized choice
00335   forceinline void
00336   ChoiceVirtualBase::operator delete(void* p) {
00337     heap.rfree(p);
00338   }
00339   forceinline void*
00340   ChoiceVirtualBase::operator new(size_t s) {
00341     return heap.ralloc(s);
00342   }
00343   forceinline
00344   ChoiceVirtualBase::~ChoiceVirtualBase(void) {
00345   }
00346 
00347 
00348   template<class Choice>
00349   forceinline
00350   ChoiceVirtual<Choice>::ChoiceVirtual(const Choice& c)
00351     : choice(c) {}
00352   template<class Choice>
00353   forceinline ChoiceVirtualBase*
00354   ChoiceVirtual<Choice>::copy(void) const {
00355     return new ChoiceVirtual<Choice>(choice);
00356   }
00357   template<class Choice>
00358   forceinline size_t
00359   ChoiceVirtual<Choice>::size(void) const {
00360     return sizeof(ChoiceVirtual<Choice>);
00361   }
00362   template<class Choice>
00363   ChoiceVirtual<Choice>::~ChoiceVirtual(void) {}
00364 
00365 
00366   template<class ViewSel>
00367   forceinline
00368   ViewSelVirtual<ViewSel>::ViewSelVirtual(Space& home,
00369                                           const VarBranchOptions& vbo)
00370     : viewsel(home,vbo) {}
00371   template<class ViewSel>
00372   forceinline
00373   ViewSelVirtual<ViewSel>::ViewSelVirtual(Space& home, bool share,
00374                                           ViewSelVirtual<ViewSel>& vsv) {
00375     viewsel.update(home,share,vsv.viewsel);
00376   }
00377   template<class ViewSel>
00378   ViewSelStatus
00379   ViewSelVirtual<ViewSel>::init(Space& home, typename ViewSel::View x) {
00380     return viewsel.init(home,x);
00381   }
00382   template<class ViewSel>
00383   ViewSelStatus
00384   ViewSelVirtual<ViewSel>::select(Space& home, typename ViewSel::View x) {
00385     return viewsel.select(home,x);
00386   }
00387   template<class ViewSel>
00388   ChoiceVirtualBase*
00389   ViewSelVirtual<ViewSel>::choice(Space& home) {
00390     return new ChoiceVirtual<typename ViewSel::Choice>(viewsel.choice(home));
00391   }
00392   template<class ViewSel>
00393   void
00394   ViewSelVirtual<ViewSel>::commit(Space& home, const ChoiceVirtualBase* _c,
00395                                   unsigned int a) {
00396     const ChoiceVirtual<typename ViewSel::Choice>* c =
00397       static_cast<const ChoiceVirtual<typename ViewSel::Choice>*>(_c);
00398     viewsel.commit(home, c->choice, a);
00399   }
00400   template<class ViewSel>
00401   ViewSelVirtualBase<typename ViewSel::View>*
00402   ViewSelVirtual<ViewSel>::copy(Space& home, bool share) {
00403     return new (home) ViewSelVirtual<ViewSel>(home,share,*this);
00404   }
00405   template<class ViewSel>
00406   size_t
00407   ViewSelVirtual<ViewSel>::dispose(Space& home) {
00408     viewsel.dispose(home);
00409     return sizeof(ViewSelVirtual<ViewSel>);
00410   }
00411 
00412 
00413   // Choice for dynamic tie breaking
00414   template<class View>
00415   forceinline
00416   ViewSelTieBreakDynamic<View>::Choice::Choice
00417   (Space& home, ViewSelVirtualBase<View>** tb, int n0)
00418     : n(n0), c(heap.alloc<ChoiceVirtualBase*>(n)) {
00419     for (int i=n; i--; )
00420       c[i] = tb[i]->choice(home);
00421   }
00422   template<class View>
00423   forceinline
00424   ViewSelTieBreakDynamic<View>::Choice::Choice(const Choice& ce)
00425     : n(ce.n), c(heap.alloc<ChoiceVirtualBase*>(n)) {
00426     for (int i=n; i--; )
00427       c[i] = ce.c[i]->copy();
00428   }
00429   template<class View>
00430   forceinline const typename ViewSelTieBreakDynamic<View>::Choice&
00431   ViewSelTieBreakDynamic<View>::Choice::operator =(const Choice& ce) {
00432     if (&ce != this) {
00433       assert(ce.n == n);
00434       for (int i=n; i--; ) {
00435         delete c[i]; c[i] = ce.c[i]->copy();
00436       }
00437     }
00438     return *this;
00439   }
00440   template<class View>
00441   forceinline void
00442   ViewSelTieBreakDynamic<View>::Choice::commit
00443   (Space& home, unsigned int a, ViewSelVirtualBase<View>** tb)  const {
00444     for (int i=n; i--; )
00445       tb[i]->commit(home, c[i], a);
00446   }
00447   template<class View>
00448   forceinline size_t
00449   ViewSelTieBreakDynamic<View>::Choice::size(void) const {
00450     size_t s = (sizeof(typename ViewSelTieBreakDynamic<View>::Choice) +
00451                 n * sizeof(ChoiceVirtualBase*));
00452     for (int i=n; i--; )
00453       s += c[i]->size();
00454     return s;
00455   }
00456   template<class View>
00457   forceinline
00458   ViewSelTieBreakDynamic<View>::Choice::~Choice(void) {
00459     for (int i=n; i--; )
00460       delete c[i];
00461     heap.free(c,n);
00462   }
00463 
00464 
00465   // Select variable with dynamic tie breaking
00466   template<class View>
00467   forceinline
00468   ViewSelTieBreakDynamic<View>::ViewSelTieBreakDynamic(void) {}
00469   template<class View>
00470   forceinline
00471   ViewSelTieBreakDynamic<View>::
00472   ViewSelTieBreakDynamic(Space& home, ViewSelVirtualBase<View>** vsv, int n0)
00473     : n(n0), tb(home.alloc<ViewSelVirtualBase<View>*>(n)) {
00474     for (int i=0; i<n; i++)
00475       tb[i]=vsv[i];
00476     assert(n > 0);
00477   }
00478   template<class View>
00479   forceinline ViewSelStatus
00480   ViewSelTieBreakDynamic<View>::init(Space& home, View x) {
00481     ViewSelStatus s = VSS_BEST;
00482     for (int i=0; i<n; i++)
00483       if (tb[i]->init(home,x) != VSS_BEST)
00484         s = VSS_BETTER;
00485     return s;
00486   }
00487   template<class View>
00488   forceinline ViewSelStatus
00489   ViewSelTieBreakDynamic<View>::select(Space& home, View x) {
00490     switch (tb[0]->select(home,x)) {
00491     case VSS_BEST:
00492       {
00493         ViewSelStatus s = VSS_BEST;
00494         for (int i=1; i<n; i++)
00495           if (tb[i]->init(home,x) != VSS_BEST)
00496             s = VSS_BETTER;
00497         return s;
00498       }
00499     case VSS_BETTER:
00500       for (int i=1; i<n; i++)
00501         (void) tb[i]->init(home,x);
00502       return VSS_BETTER;
00503     case VSS_WORSE:
00504       return VSS_WORSE;
00505     case VSS_TIE:
00506       for (int i=1; i<n; i++)
00507         switch (tb[i]->select(home,x)) {
00508         case VSS_BEST: case VSS_BETTER:
00509           for (int j=i+1; j<n; j++)
00510             (void) tb[j]->init(home,x);
00511           return VSS_BETTER;
00512         case VSS_TIE:    break;
00513         case VSS_WORSE:  return VSS_WORSE;
00514         default: GECODE_NEVER;
00515         }
00516       return VSS_TIE;
00517     default: GECODE_NEVER;
00518       return VSS_WORSE;
00519     }
00520   }
00521   template<class _View>
00522   inline typename ViewSelTieBreakDynamic<_View>::Choice
00523   ViewSelTieBreakDynamic<_View>::choice(Space& home) {
00524     Choice c(home,tb,n);
00525     return c;
00526   }
00527   template<class _View>
00528   forceinline void
00529   ViewSelTieBreakDynamic<_View>::commit
00530   (Space& home, const typename ViewSelTieBreakDynamic<_View>::Choice& c,
00531    unsigned int a) {
00532     c.commit(home,a,tb);
00533   }
00534   template<class _View>
00535   forceinline void
00536   ViewSelTieBreakDynamic<_View>::update(Space& home, bool share,
00537                                         ViewSelTieBreakDynamic<_View>& vstb) {
00538     n = vstb.n;
00539     tb = home.alloc<ViewSelVirtualBase<View>*>(n);
00540     for (int i=0; i<n; i++)
00541       tb[i] = vstb.tb[i]->copy(home,share);
00542   }
00543   template<class _View>
00544   forceinline void
00545   ViewSelTieBreakDynamic<_View>::dispose(Space& home) {
00546     for (int i=0; i<n; i++)
00547       home.rfree(tb[i],tb[i]->dispose(home));
00548     home.free<ViewSelVirtualBase<_View>*>(tb,n);
00549   }
00550 
00551 }
00552 
00553 // STATISTICS: kernel-branch