Generated on Sun Feb 17 15:24:11 2019 for Gecode by doxygen 1.6.3

view.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, 2012
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 {
00035 
00043 
00044   class Pos {
00045   public:
00047     const int pos;
00049     Pos(int p);
00051     Pos(const Pos& p);
00052   };
00053 
00055   class GECODE_VTABLE_EXPORT PosChoice : public Choice {
00056   private:
00058     const Pos _pos;
00059   protected:
00061     PosChoice(const PosChoice& c);
00062   public:
00064     PosChoice(const Brancher& b, unsigned int a, const Pos& p);
00066     const Pos& pos(void) const;
00068     virtual void archive(Archive& e) const;
00069   };
00070 
00077   template<class View, class Filter, int n>
00078   class ViewBrancher : public Brancher {
00079   protected:
00081     typedef typename View::VarType Var;
00083     ViewArray<View> x;
00085     mutable int start;
00087     ViewSel<View>* vs[n];
00089     Filter f;
00091     Pos pos(Space& home);
00093     View view(const Pos& p) const;
00095     ViewBrancher(Space& home, ViewBrancher<View,Filter,n>& b);
00097     ViewBrancher(Home home, ViewArray<View>& x, ViewSel<View>* vs[n],
00098                  BranchFilter<Var> bf);
00099   public:
00101     virtual bool status(const Space& home) const;
00103     virtual size_t dispose(Space& home);
00104   };
00105 
00107 
00108 
00109   /*
00110    * Position information
00111    *
00112    */
00113   forceinline
00114   Pos::Pos(int p) : pos(p) {}
00115   forceinline
00116   Pos::Pos(const Pos& p) : pos(p.pos) {}
00117 
00118   /*
00119    * Choice with position
00120    *
00121    */
00122   forceinline
00123   PosChoice::PosChoice(const Brancher& b, unsigned int a, const Pos& p)
00124     : Choice(b,a), _pos(p) {}
00125   forceinline const Pos&
00126   PosChoice::pos(void) const {
00127     return _pos;
00128   }
00129   forceinline void
00130   PosChoice::archive(Archive& e) const {
00131     Choice::archive(e);
00132     e << _pos.pos;
00133   }
00134 
00135   template<class View, class Filter, int n>
00136   forceinline
00137   ViewBrancher<View,Filter,n>::ViewBrancher(Home home, ViewArray<View>& x0,
00138                                             ViewSel<View>* vs0[n],
00139                                             BranchFilter<Var> bf)
00140     : Brancher(home), x(x0), start(0), f(bf) {
00141     for (int i=0; i<n; i++)
00142       vs[i] = vs0[i];
00143     for (int i=0; i<n; i++)
00144       if (f.notice() || vs[i]->notice()) {
00145         home.notice(*this,AP_DISPOSE,true);
00146         break;
00147       }
00148   }
00149 
00150   template<class View, class Filter, int n>
00151   forceinline
00152   ViewBrancher<View,Filter,n>::ViewBrancher(Space& home,
00153                                             ViewBrancher<View,Filter,n>& vb)
00154     : Brancher(home,vb), start(vb.start), f(vb.f) {
00155     x.update(home,vb.x);
00156     for (int i=0; i<n; i++)
00157       vs[i] = vb.vs[i]->copy(home);
00158   }
00159 
00160   template<class View, class Filter, int n>
00161   bool
00162   ViewBrancher<View,Filter,n>::status(const Space& home) const {
00163     for (int i=start; i < x.size(); i++)
00164       if (!x[i].assigned() && f(home,x[i],i)) {
00165         start = i;
00166         return true;
00167       }
00168     return false;
00169   }
00170 
00171   template<class View, class Filter, int n>
00172   inline Pos
00173   ViewBrancher<View,Filter,n>::pos(Space& home) {
00174     assert(!x[start].assigned());
00175     int s;
00176     if (f) {
00177       if (n == 1) {
00178         s = vs[0]->select(home,x,start,f);
00179       } else {
00180         Region r;
00181         int* ties = r.alloc<int>(x.size()-start+1);
00182         int n_ties;
00183         vs[0]->ties(home,x,start,ties,n_ties,f);
00184         for (int i=1; (i < n-1) && (n_ties > 1); i++)
00185           vs[i]->brk(home,x,ties,n_ties);
00186         if (n_ties > 1)
00187           s = vs[n-1]->select(home,x,ties,n_ties);
00188         else
00189           s = ties[0];
00190       }
00191     } else {
00192       if (n == 1) {
00193         s = vs[0]->select(home,x,start);
00194       } else {
00195         Region r;
00196         int* ties = r.alloc<int>(x.size()-start+1);
00197         int n_ties;
00198         vs[0]->ties(home,x,start,ties,n_ties);
00199         for (int i=1; (i < n-1) && (n_ties > 1); i++)
00200           vs[i]->brk(home,x,ties,n_ties);
00201         if (n_ties > 1)
00202           s = vs[n-1]->select(home,x,ties,n_ties);
00203         else
00204           s = ties[0];
00205       }
00206     }
00207     Pos p(s);
00208     return p;
00209   }
00210 
00211   template<class View, class Filter, int n>
00212   forceinline View
00213   ViewBrancher<View,Filter,n>::view(const Pos& p) const {
00214     return x[p.pos];
00215   }
00216 
00217   template<class View, class Filter, int n>
00218   forceinline size_t
00219   ViewBrancher<View,Filter,n>::dispose(Space& home) {
00220     for (int i=0; i<n; i++)
00221       if (f.notice() || vs[i]->notice()) {
00222         home.ignore(*this,AP_DISPOSE,true);
00223         break;
00224       }
00225     for (int i=0; i<n; i++)
00226       vs[i]->dispose(home);
00227     (void) Brancher::dispose(home);
00228     return sizeof(ViewBrancher<View,Filter,n>);
00229   }
00230 
00231 }
00232 
00233 // STATISTICS: kernel-branch