Generated on Tue May 22 09:39:55 2018 for Gecode by doxygen 1.6.3

view-values.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  *
00006  *  Copyright:
00007  *     Christian Schulte, 2008
00008  *
00009  *  This file is part of Gecode, the generic constraint
00010  *  development environment:
00011  *     http://www.gecode.org
00012  *
00013  *  Permission is hereby granted, free of charge, to any person obtaining
00014  *  a copy of this software and associated documentation files (the
00015  *  "Software"), to deal in the Software without restriction, including
00016  *  without limitation the rights to use, copy, modify, merge, publish,
00017  *  distribute, sublicense, and/or sell copies of the Software, and to
00018  *  permit persons to whom the Software is furnished to do so, subject to
00019  *  the following conditions:
00020  *
00021  *  The above copyright notice and this permission notice shall be
00022  *  included in all copies or substantial portions of the Software.
00023  *
00024  *  THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,
00025  *  EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF
00026  *  MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND
00027  *  NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE
00028  *  LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION
00029  *  OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION
00030  *  WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
00031  *
00032  */
00033 
00034 namespace Gecode { namespace Int { namespace Branch {
00035 
00037   class GECODE_VTABLE_EXPORT PosValuesChoice : public PosChoice {
00038   private:
00040     class PosMin {
00041     public:
00043       unsigned int pos;
00045       int min;
00046     };
00048     unsigned int n;
00050     PosMin* pm;
00051   public:
00053     GECODE_INT_EXPORT
00054     PosValuesChoice(const Brancher& b, const Pos& p, IntView x);
00056     GECODE_INT_EXPORT
00057     PosValuesChoice(const Brancher& b, unsigned int alt, Pos p, Archive& e);
00059     int val(unsigned int a) const;
00061     GECODE_INT_EXPORT
00062     virtual ~PosValuesChoice(void);
00064     GECODE_INT_EXPORT
00065     virtual void archive(Archive& e) const;
00066   };
00067 
00068   forceinline int
00069   PosValuesChoice::val(unsigned int a) const {
00070     PosMin* l = &pm[0];
00071     PosMin* r = &pm[n-1];
00072     while (true) {
00073       PosMin* m = l + (r-l)/2;
00074       if (a < m->pos) {
00075         r=m-1;
00076       } else if (a >= (m+1)->pos) {
00077         l=m+1;
00078       } else {
00079         return m->min + static_cast<int>(a - m->pos);
00080       }
00081     }
00082     GECODE_NEVER;
00083     return 0;
00084   }
00085 
00086 
00087   template<int n, bool min, class Filter, class Print>
00088   forceinline
00089   ViewValuesBrancher<n,min,Filter,Print>::
00090   ViewValuesBrancher(Home home, ViewArray<IntView>& x,
00091                      ViewSel<IntView>* vs[n],
00092                      IntBranchFilter bf,
00093                      IntVarValPrint vvp)
00094     : ViewBrancher<IntView,Filter,n>(home,x,vs,bf), p(vvp) {
00095     if (p.notice())
00096       home.notice(*this,AP_DISPOSE,true);
00097   }
00098 
00099   template<int n, bool min, class Filter, class Print>
00100   forceinline void
00101   ViewValuesBrancher<n,min,Filter,Print>::post(Home home, 
00102                                                ViewArray<IntView>& x,
00103                                                ViewSel<IntView>* vs[n],
00104                                                IntBranchFilter bf,
00105                                                IntVarValPrint vvp) {
00106     (void) new (home) ViewValuesBrancher<n,min,Filter,Print>(home,x,vs,bf,vvp);
00107   }
00108 
00109   template<int n, bool min, class Filter, class Print>
00110   forceinline
00111   ViewValuesBrancher<n,min,Filter,Print>::
00112   ViewValuesBrancher(Space& home, ViewValuesBrancher& b)
00113     : ViewBrancher<IntView,Filter,n>(home,b), p(b.p) {}
00114 
00115   template<int n, bool min, class Filter, class Print>
00116   Actor*
00117   ViewValuesBrancher<n,min,Filter,Print>::copy(Space& home) {
00118     return new (home) ViewValuesBrancher<n,min,Filter,Print>
00119       (home,*this);
00120   }
00121 
00122   template<int n, bool min, class Filter, class Print>
00123   const Choice*
00124   ViewValuesBrancher<n,min,Filter,Print>::choice(Space& home) {
00125     Pos p = ViewBrancher<IntView,Filter,n>::pos(home);
00126     return new PosValuesChoice(*this,p,
00127                                ViewBrancher<IntView,Filter,n>::view(p));
00128   }
00129 
00130   template<int n, bool min, class Filter, class Print>
00131   const Choice*
00132   ViewValuesBrancher<n,min,Filter,Print>::choice
00133   (const Space& home, Archive& e) {
00134     (void) home;
00135     int p;
00136     unsigned int a;
00137     e >> p >> a;
00138     return new PosValuesChoice(*this,a,p,e);
00139   }
00140 
00141   template<int n, bool min, class Filter, class Print>
00142   ExecStatus
00143   ViewValuesBrancher<n,min,Filter,Print>::commit(Space& home, const Choice& c,
00144                                                  unsigned int a) {
00145     const PosValuesChoice& pvc
00146       = static_cast<const PosValuesChoice&>(c);
00147     IntView x(ViewBrancher<IntView,Filter,n>::view(pvc.pos()));
00148     unsigned int b = min ? a : (pvc.alternatives() - 1 - a);
00149     return me_failed(x.eq(home,pvc.val(b))) ? ES_FAILED : ES_OK;
00150   }
00151 
00152   template<int n, bool min, class Filter, class Print>
00153   NGL*
00154   ViewValuesBrancher<n,min,Filter,Print>::ngl(Space& home, const Choice& c,
00155                                               unsigned int a) const {
00156     const PosValuesChoice& pvc
00157       = static_cast<const PosValuesChoice&>(c);
00158     IntView x(ViewBrancher<IntView,Filter,n>::view(pvc.pos()));
00159     unsigned int b = min ? a : (pvc.alternatives() - 1 - a);
00160     return new (home) EqNGL<IntView>(home,x,pvc.val(b));
00161   }
00162 
00163   template<int n, bool min, class Filter, class Print>
00164   void
00165   ViewValuesBrancher<n,min,Filter,Print>::print(const Space& home,
00166                                                 const Choice& c,
00167                                                 unsigned int a, 
00168                                                 std::ostream& o) const {
00169     const PosValuesChoice& pvc
00170       = static_cast<const PosValuesChoice&>(c);
00171     IntView x(ViewBrancher<IntView,Filter,n>::view(pvc.pos()));
00172     unsigned int b = min ? a : (pvc.alternatives() - 1 - a);
00173     int nn = pvc.val(b);
00174     if (p)
00175       p(home,*this,a,x,pvc.pos().pos,nn,o);
00176     else
00177       o << "var[" << pvc.pos().pos << "] = " << nn;
00178   }
00179 
00180   template<int n, bool min, class Filter, class Print>
00181   forceinline size_t
00182   ViewValuesBrancher<n,min,Filter,Print>::dispose(Space& home) {
00183     if (p.notice())
00184       home.ignore(*this,AP_DISPOSE,true);
00185     (void) ViewBrancher<IntView,Filter,n>::dispose(home);
00186     return sizeof(ViewValuesBrancher<n,min,Filter,Print>);
00187   }
00188 
00189   template<int n, bool min>
00190   forceinline void
00191   postviewvaluesbrancher(Home home, ViewArray<IntView>& x,
00192                          ViewSel<IntView>* vs[n],
00193                          IntBranchFilter bf,
00194                          IntVarValPrint vvp) {
00195     if (bf) {
00196       if (vvp) {
00197         ViewValuesBrancher<n,min,BrancherFilter<IntView>,
00198           BrancherPrint<IntView,int> >
00199           ::post(home,x,vs,bf,vvp);
00200       } else {
00201         ViewValuesBrancher<n,min,BrancherFilter<IntView>,
00202           BrancherNoPrint<IntView,int> >
00203           ::post(home,x,vs,bf,vvp);
00204       }
00205     } else {
00206       if (vvp) {
00207         ViewValuesBrancher<n,min,BrancherNoFilter<IntView>,
00208           BrancherPrint<IntView,int> >
00209           ::post(home,x,vs,bf,vvp);
00210       } else {
00211         ViewValuesBrancher<n,min,BrancherNoFilter<IntView>,
00212           BrancherNoPrint<IntView,int> >
00213           ::post(home,x,vs,bf,vvp);
00214       }
00215     }
00216   }
00217 
00218 
00219 }}}
00220 
00221 // STATISTICS: int-branch