brancher-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: 2011-05-11 12:44:17 +0200 (Wed, 11 May 2011) $ by $Author: tack $
00011  *     $Revision: 12001 $
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;
00071       void archive(Archive& e) const;
00072     };
00074     ViewSelTieBreakStatic(void);
00076     ViewSelTieBreakStatic(Space& home, A& a, B& b);
00078     ViewSelStatus init(Space& home, typename A::View x);
00080     ViewSelStatus select(Space& home, typename A::View x);
00082     Choice choice(Space& home);
00084     Choice choice(const Space& home, Archive& e);
00086     void commit(Space& home, const Choice& c, unsigned int a);
00088     void update(Space& home, bool share, ViewSelTieBreakStatic& vs);
00090     void dispose(Space& home);
00091   };
00092 
00096   class ChoiceVirtualBase {
00097   public:
00099     virtual ChoiceVirtualBase* copy(void) const = 0;
00101     virtual size_t size(void) const = 0;
00103     GECODE_KERNEL_EXPORT virtual ~ChoiceVirtualBase(void);
00105     virtual void archive(Archive& e) const = 0;
00107 
00108 
00109     static void* operator new(size_t s);
00111     static void  operator delete(void*);
00113   };
00114 
00118   template<class View>
00119   class ViewSelVirtualBase {
00120   public:
00122     virtual ViewSelStatus init(Space& home, View x) = 0;
00124     virtual ViewSelStatus select(Space& home, View x) = 0;
00126     virtual ChoiceVirtualBase* choice(Space& home) = 0;
00128     virtual ChoiceVirtualBase* choice(const Space& home, Archive& e) = 0;
00130     virtual void commit(Space& home, const ChoiceVirtualBase* c, 
00131                         unsigned int a) = 0;
00133     virtual ViewSelVirtualBase<View>* copy(Space& home, bool share) = 0;
00135     virtual size_t dispose(Space& home) = 0;
00137 
00138 
00139     static void* operator new(size_t s, Space& home);
00141     static void  operator delete(void* p, Space& home);
00143     static void  operator delete(void*);
00145   };
00146 
00150   template<class Choice>
00151   class ChoiceVirtual : public ChoiceVirtualBase {
00152   public:
00154     Choice choice;
00156     ChoiceVirtual(const Choice& c);
00158     virtual ChoiceVirtualBase* copy(void) const;
00160     virtual size_t size(void) const;
00162     virtual ~ChoiceVirtual(void);
00164     virtual void archive(Archive& e) const;
00165   };
00166 
00170   template<class ViewSel>
00171   class ViewSelVirtual : public ViewSelVirtualBase<typename ViewSel::View> {
00172   protected:
00174     ViewSel viewsel;
00175   public:
00177     ViewSelVirtual(Space& home, const VarBranchOptions& vbo);
00179     ViewSelVirtual(Space& home, bool share, ViewSelVirtual& vsv);
00181     virtual ViewSelStatus init(Space& home, typename ViewSel::View x);
00183     virtual ViewSelStatus select(Space& home, typename ViewSel::View x);
00185     virtual ChoiceVirtualBase* choice(Space& home);
00187     virtual ChoiceVirtualBase* choice(const Space& home, Archive& e);
00189     virtual void commit(Space& home, const ChoiceVirtualBase* d,
00190                         unsigned int a);
00192     virtual ViewSelVirtualBase<typename ViewSel::View>*
00193     copy(Space& home, bool share);
00195     virtual size_t dispose(Space& home);
00196   };
00197 
00201   template<class _View>
00202   class ViewSelTieBreakDynamic {
00203   protected:
00205     int n;
00207     ViewSelVirtualBase<_View>** tb;
00208   public:
00210     typedef _View View;
00212     class Choice {
00213     public:
00215       int n;
00217       ChoiceVirtualBase** c;
00219       Choice(Space& home, ViewSelVirtualBase<_View>** tb, int n0);
00221       Choice(const Space& home, Archive& e,
00222              ViewSelVirtualBase<_View>** tb, int n0);
00224       Choice(const Choice& ce);
00226       const Choice& operator =(const Choice& ce);
00228       void commit(Space& home, unsigned int a,
00229                   ViewSelVirtualBase<_View>** tb)  const;
00231       size_t size(void) const;
00233       ~Choice(void);
00235       void archive(Archive& e) const;
00236     };
00238     ViewSelTieBreakDynamic(void);
00240     ViewSelTieBreakDynamic(Space& home, ViewSelVirtualBase<_View>** vsv,
00241                            int n);
00243     ViewSelStatus init(Space& home, _View x);
00245     ViewSelStatus select(Space& home, _View x);
00247     Choice choice(Space& home);
00249     Choice choice(const Space& home, Archive& e);
00251     void commit(Space& home,
00252                 const typename ViewSelTieBreakDynamic<_View>::Choice& c,
00253                 unsigned int a);
00255     void update(Space& home, bool share, ViewSelTieBreakDynamic& vs);
00257     void dispose(Space& home);
00258   };
00260 
00261 
00262   // Select variable with static tie breaking
00263   template<class A, class B>
00264   forceinline
00265   ViewSelTieBreakStatic<A,B>::Choice::Choice(const typename A::Choice& a0,
00266                                              const typename B::Choice& b0)
00267     : a(a0), b(b0) {}
00268   template<class A, class B>
00269   forceinline size_t
00270   ViewSelTieBreakStatic<A,B>::Choice::size(void) const {
00271     return a.size() + b.size();
00272   }
00273   template<class A, class B>
00274   forceinline void
00275   ViewSelTieBreakStatic<A,B>::Choice::archive(Archive& e) const {
00276     a.archive(e);
00277     b.archive(e);
00278   }
00279 
00280   template<class A, class B>
00281   forceinline
00282   ViewSelTieBreakStatic<A,B>::ViewSelTieBreakStatic(void) {}
00283   template<class A, class B>
00284   forceinline
00285   ViewSelTieBreakStatic<A,B>::
00286   ViewSelTieBreakStatic(Space&, A& a0, B& b0)
00287     : a(a0), b(b0) {}
00288   template<class A, class B>
00289   forceinline ViewSelStatus
00290   ViewSelTieBreakStatic<A,B>::init(Space& home, typename A::View x) {
00291     ViewSelStatus s = a.init(home,x);
00292     return (b.init(home,x) != VSS_BEST) ? VSS_BETTER : s;
00293   }
00294   template<class A, class B>
00295   forceinline ViewSelStatus
00296   ViewSelTieBreakStatic<A,B>::select(Space& home, typename A::View x) {
00297     switch (a.select(home,x)) {
00298     case VSS_BEST:
00299       return (b.init(home,x) != VSS_BEST) ? VSS_BETTER : VSS_BEST;
00300     case VSS_BETTER:
00301       (void) b.init(home,x);
00302       return VSS_BETTER;
00303     case VSS_WORSE:
00304       return VSS_WORSE;
00305     case VSS_TIE:
00306       switch (b.select(home,x)) {
00307       case VSS_BEST:   return VSS_BETTER;
00308       case VSS_BETTER: return VSS_BETTER;
00309       case VSS_TIE:    return VSS_TIE;
00310       case VSS_WORSE:  return VSS_WORSE;
00311       default: GECODE_NEVER;
00312       }
00313     default: GECODE_NEVER;
00314       return VSS_WORSE;
00315     }
00316   }
00317   template<class A, class B>
00318   inline typename ViewSelTieBreakStatic<A,B>::Choice
00319   ViewSelTieBreakStatic<A,B>::choice(Space& home) {
00320     typename ViewSelTieBreakStatic<A,B>::Choice c(a.choice(home),
00321                                                   b.choice(home));
00322     return c;
00323   }
00324   template<class A, class B>
00325   inline typename ViewSelTieBreakStatic<A,B>::Choice
00326   ViewSelTieBreakStatic<A,B>::choice(const Space& home, Archive& e) {
00327     typename ViewSelTieBreakStatic<A,B>::Choice c(a.choice(home,e),
00328                                                   b.choice(home,e));
00329     return c;
00330   }
00331   template<class A, class B>
00332   forceinline void
00333   ViewSelTieBreakStatic<A,B>::commit(Space& home, const Choice& c,
00334                                      unsigned int al) {
00335     a.commit(home, c.a, al);
00336     b.commit(home, c.b, al);
00337   }
00338   template<class A, class B>
00339   forceinline void
00340   ViewSelTieBreakStatic<A,B>::update(Space& home, bool share,
00341                                      ViewSelTieBreakStatic<A,B>& vstb) {
00342     a.update(home,share,vstb.a);
00343     b.update(home,share,vstb.b);
00344   }
00345   template<class A, class B>
00346   forceinline void
00347   ViewSelTieBreakStatic<A,B>::dispose(Space& home) {
00348     a.dispose(home);
00349     b.dispose(home);
00350   }
00351 
00352 
00353   // Virtualized view selection
00354   template<class View>
00355   forceinline void
00356   ViewSelVirtualBase<View>::operator delete(void*) {}
00357   template<class View>
00358   forceinline void
00359   ViewSelVirtualBase<View>::operator delete(void*, Space&) {}
00360   template<class View>
00361   forceinline void*
00362   ViewSelVirtualBase<View>::operator new(size_t s, Space& home) {
00363     return home.ralloc(s);
00364   }
00365 
00366   // Virtualized choice
00367   forceinline void
00368   ChoiceVirtualBase::operator delete(void* p) {
00369     heap.rfree(p);
00370   }
00371   forceinline void*
00372   ChoiceVirtualBase::operator new(size_t s) {
00373     return heap.ralloc(s);
00374   }
00375   forceinline
00376   ChoiceVirtualBase::~ChoiceVirtualBase(void) {
00377   }
00378 
00379 
00380   template<class Choice>
00381   forceinline
00382   ChoiceVirtual<Choice>::ChoiceVirtual(const Choice& c)
00383     : choice(c) {}
00384   template<class Choice>
00385   forceinline ChoiceVirtualBase*
00386   ChoiceVirtual<Choice>::copy(void) const {
00387     return new ChoiceVirtual<Choice>(choice);
00388   }
00389   template<class Choice>
00390   forceinline size_t
00391   ChoiceVirtual<Choice>::size(void) const {
00392     return sizeof(ChoiceVirtual<Choice>);
00393   }
00394   template<class Choice>
00395   ChoiceVirtual<Choice>::~ChoiceVirtual(void) {}
00396   template<class Choice> void
00397   ChoiceVirtual<Choice>::archive(Archive& e) const {
00398     choice.archive(e);
00399   }
00400 
00401   template<class ViewSel>
00402   forceinline
00403   ViewSelVirtual<ViewSel>::ViewSelVirtual(Space& home,
00404                                           const VarBranchOptions& vbo)
00405     : viewsel(home,vbo) {}
00406   template<class ViewSel>
00407   forceinline
00408   ViewSelVirtual<ViewSel>::ViewSelVirtual(Space& home, bool share,
00409                                           ViewSelVirtual<ViewSel>& vsv) {
00410     viewsel.update(home,share,vsv.viewsel);
00411   }
00412   template<class ViewSel>
00413   ViewSelStatus
00414   ViewSelVirtual<ViewSel>::init(Space& home, typename ViewSel::View x) {
00415     return viewsel.init(home,x);
00416   }
00417   template<class ViewSel>
00418   ViewSelStatus
00419   ViewSelVirtual<ViewSel>::select(Space& home, typename ViewSel::View x) {
00420     return viewsel.select(home,x);
00421   }
00422   template<class ViewSel>
00423   ChoiceVirtualBase*
00424   ViewSelVirtual<ViewSel>::choice(Space& home) {
00425     return new ChoiceVirtual<typename ViewSel::Choice>(viewsel.choice(home));
00426   }
00427   template<class ViewSel>
00428   ChoiceVirtualBase*
00429   ViewSelVirtual<ViewSel>::choice(const Space& home, Archive& e) {
00430     return new ChoiceVirtual<typename ViewSel::Choice>(viewsel.choice(home,e));
00431   }
00432   template<class ViewSel>
00433   void
00434   ViewSelVirtual<ViewSel>::commit(Space& home, const ChoiceVirtualBase* _c,
00435                                   unsigned int a) {
00436     const ChoiceVirtual<typename ViewSel::Choice>* c =
00437       static_cast<const ChoiceVirtual<typename ViewSel::Choice>*>(_c);
00438     viewsel.commit(home, c->choice, a);
00439   }
00440   template<class ViewSel>
00441   ViewSelVirtualBase<typename ViewSel::View>*
00442   ViewSelVirtual<ViewSel>::copy(Space& home, bool share) {
00443     return new (home) ViewSelVirtual<ViewSel>(home,share,*this);
00444   }
00445   template<class ViewSel>
00446   size_t
00447   ViewSelVirtual<ViewSel>::dispose(Space& home) {
00448     viewsel.dispose(home);
00449     return sizeof(ViewSelVirtual<ViewSel>);
00450   }
00451 
00452 
00453   // Choice for dynamic tie breaking
00454   template<class View>
00455   forceinline
00456   ViewSelTieBreakDynamic<View>::Choice::Choice
00457   (Space& home, ViewSelVirtualBase<View>** tb, int n0)
00458     : n(n0), c(heap.alloc<ChoiceVirtualBase*>(n)) {
00459     for (int i=n; i--; )
00460       c[i] = tb[i]->choice(home);
00461   }
00462   template<class View>
00463   forceinline
00464   ViewSelTieBreakDynamic<View>::Choice::Choice
00465   (const Space& home, Archive& e, ViewSelVirtualBase<View>** tb,
00466    int n0)
00467     : n(n0), c(heap.alloc<ChoiceVirtualBase*>(n)) {
00468     for (int i=n; i--; )
00469       c[i] = tb[i]->choice(home,e);
00470   }
00471   template<class View>
00472   forceinline
00473   ViewSelTieBreakDynamic<View>::Choice::Choice(const Choice& ce)
00474     : n(ce.n), c(heap.alloc<ChoiceVirtualBase*>(n)) {
00475     for (int i=n; i--; )
00476       c[i] = ce.c[i]->copy();
00477   }
00478   template<class View>
00479   forceinline const typename ViewSelTieBreakDynamic<View>::Choice&
00480   ViewSelTieBreakDynamic<View>::Choice::operator =(const Choice& ce) {
00481     if (&ce != this) {
00482       assert(ce.n == n);
00483       for (int i=n; i--; ) {
00484         delete c[i]; c[i] = ce.c[i]->copy();
00485       }
00486     }
00487     return *this;
00488   }
00489   template<class View>
00490   forceinline void
00491   ViewSelTieBreakDynamic<View>::Choice::commit
00492   (Space& home, unsigned int a, ViewSelVirtualBase<View>** tb)  const {
00493     for (int i=n; i--; )
00494       tb[i]->commit(home, c[i], a);
00495   }
00496   template<class View>
00497   forceinline size_t
00498   ViewSelTieBreakDynamic<View>::Choice::size(void) const {
00499     size_t s = (sizeof(typename ViewSelTieBreakDynamic<View>::Choice) +
00500                 n * sizeof(ChoiceVirtualBase*));
00501     for (int i=n; i--; )
00502       s += c[i]->size();
00503     return s;
00504   }
00505   template<class View>
00506   forceinline
00507   ViewSelTieBreakDynamic<View>::Choice::~Choice(void) {
00508     for (int i=n; i--; )
00509       delete c[i];
00510     heap.free(c,n);
00511   }
00512   template<class View>
00513   forceinline void
00514   ViewSelTieBreakDynamic<View>::Choice::archive(Archive& e) const 
00515   {
00516     for (int i=0; i<n; i++)
00517       c[i]->archive(e);
00518   }
00519 
00520 
00521   // Select variable with dynamic tie breaking
00522   template<class View>
00523   forceinline
00524   ViewSelTieBreakDynamic<View>::ViewSelTieBreakDynamic(void) {}
00525   template<class View>
00526   forceinline
00527   ViewSelTieBreakDynamic<View>::
00528   ViewSelTieBreakDynamic(Space& home, ViewSelVirtualBase<View>** vsv, int n0)
00529     : n(n0), tb(home.alloc<ViewSelVirtualBase<View>*>(n)) {
00530     for (int i=0; i<n; i++)
00531       tb[i]=vsv[i];
00532     assert(n > 0);
00533   }
00534   template<class View>
00535   forceinline ViewSelStatus
00536   ViewSelTieBreakDynamic<View>::init(Space& home, View x) {
00537     ViewSelStatus s = VSS_BEST;
00538     for (int i=0; i<n; i++)
00539       if (tb[i]->init(home,x) != VSS_BEST)
00540         s = VSS_BETTER;
00541     return s;
00542   }
00543   template<class View>
00544   forceinline ViewSelStatus
00545   ViewSelTieBreakDynamic<View>::select(Space& home, View x) {
00546     switch (tb[0]->select(home,x)) {
00547     case VSS_BEST:
00548       {
00549         ViewSelStatus s = VSS_BEST;
00550         for (int i=1; i<n; i++)
00551           if (tb[i]->init(home,x) != VSS_BEST)
00552             s = VSS_BETTER;
00553         return s;
00554       }
00555     case VSS_BETTER:
00556       for (int i=1; i<n; i++)
00557         (void) tb[i]->init(home,x);
00558       return VSS_BETTER;
00559     case VSS_WORSE:
00560       return VSS_WORSE;
00561     case VSS_TIE:
00562       for (int i=1; i<n; i++)
00563         switch (tb[i]->select(home,x)) {
00564         case VSS_BEST: case VSS_BETTER:
00565           for (int j=i+1; j<n; j++)
00566             (void) tb[j]->init(home,x);
00567           return VSS_BETTER;
00568         case VSS_TIE:    break;
00569         case VSS_WORSE:  return VSS_WORSE;
00570         default: GECODE_NEVER;
00571         }
00572       return VSS_TIE;
00573     default: GECODE_NEVER;
00574       return VSS_WORSE;
00575     }
00576   }
00577   template<class _View>
00578   inline typename ViewSelTieBreakDynamic<_View>::Choice
00579   ViewSelTieBreakDynamic<_View>::choice(Space& home) {
00580     Choice c(home,tb,n);
00581     return c;
00582   }
00583   template<class _View>
00584   inline typename ViewSelTieBreakDynamic<_View>::Choice
00585   ViewSelTieBreakDynamic<_View>::choice(const Space& home, Archive& e) {
00586     Choice c(home,e,tb,n);
00587     return c;
00588   }
00589   template<class _View>
00590   forceinline void
00591   ViewSelTieBreakDynamic<_View>::commit
00592   (Space& home, const typename ViewSelTieBreakDynamic<_View>::Choice& c,
00593    unsigned int a) {
00594     c.commit(home,a,tb);
00595   }
00596   template<class _View>
00597   forceinline void
00598   ViewSelTieBreakDynamic<_View>::update(Space& home, bool share,
00599                                         ViewSelTieBreakDynamic<_View>& vstb) {
00600     n = vstb.n;
00601     tb = home.alloc<ViewSelVirtualBase<View>*>(n);
00602     for (int i=0; i<n; i++)
00603       tb[i] = vstb.tb[i]->copy(home,share);
00604   }
00605   template<class _View>
00606   forceinline void
00607   ViewSelTieBreakDynamic<_View>::dispose(Space& home) {
00608     for (int i=0; i<n; i++)
00609       home.rfree(tb[i],tb[i]->dispose(home));
00610     home.free<ViewSelVirtualBase<_View>*>(tb,n);
00611   }
00612 
00613 }
00614 
00615 // STATISTICS: kernel-branch