Generated on Thu Apr 5 2018 19:44:19 for Gecode by doxygen 1.8.13
view.hpp
Go to the documentation of this file.
1 /* -*- mode: C++; c-basic-offset: 2; indent-tabs-mode: nil -*- */
2 /*
3  * Main authors:
4  * Christian Schulte <schulte@gecode.org>
5  *
6  * Copyright:
7  * Christian Schulte, 2012
8  *
9  * Last modified:
10  * $Date$ by $Author$
11  * $Revision$
12  *
13  * This file is part of Gecode, the generic constraint
14  * development environment:
15  * http://www.gecode.org
16  *
17  * Permission is hereby granted, free of charge, to any person obtaining
18  * a copy of this software and associated documentation files (the
19  * "Software"), to deal in the Software without restriction, including
20  * without limitation the rights to use, copy, modify, merge, publish,
21  * distribute, sublicense, and/or sell copies of the Software, and to
22  * permit persons to whom the Software is furnished to do so, subject to
23  * the following conditions:
24  *
25  * The above copyright notice and this permission notice shall be
26  * included in all copies or substantial portions of the Software.
27  *
28  * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,
29  * EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF
30  * MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND
31  * NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE
32  * LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION
33  * OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION
34  * WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
35  *
36  */
37 
38 namespace Gecode {
39 
47  class Pos {
49  public:
51  const int pos;
53  Pos(int p);
55  Pos(const Pos& p);
56  };
57 
60  private:
62  const Pos _pos;
63  protected:
65  PosChoice(const PosChoice& c);
66  public:
68  PosChoice(const Brancher& b, unsigned int a, const Pos& p);
70  const Pos& pos(void) const;
72  virtual void archive(Archive& e) const;
73  };
74 
81  template<class View, class Filter, int n>
82  class ViewBrancher : public Brancher {
83  protected:
85  typedef typename View::VarType Var;
89  mutable int start;
93  Filter f;
95  Pos pos(Space& home);
97  View view(const Pos& p) const;
102  BranchFilter<Var> bf);
103  public:
105  virtual bool status(const Space& home) const;
107  virtual size_t dispose(Space& home);
108  };
109 
111 
112 
113  /*
114  * Position information
115  *
116  */
118  Pos::Pos(int p) : pos(p) {}
120  Pos::Pos(const Pos& p) : pos(p.pos) {}
121 
122  /*
123  * Choice with position
124  *
125  */
127  PosChoice::PosChoice(const Brancher& b, unsigned int a, const Pos& p)
128  : Choice(b,a), _pos(p) {}
129  forceinline const Pos&
130  PosChoice::pos(void) const {
131  return _pos;
132  }
133  forceinline void
135  Choice::archive(e);
136  e << _pos.pos;
137  }
138 
139  template<class View, class Filter, int n>
142  ViewSel<View>* vs0[n],
144  : Brancher(home), x(x0), start(0), f(bf) {
145  for (int i=0; i<n; i++)
146  vs[i] = vs0[i];
147  for (int i=0; i<n; i++)
148  if (f.notice() || vs[i]->notice()) {
149  home.notice(*this,AP_DISPOSE,true);
150  break;
151  }
152  }
153 
154  template<class View, class Filter, int n>
158  : Brancher(home,vb), start(vb.start), f(vb.f) {
159  x.update(home,vb.x);
160  for (int i=0; i<n; i++)
161  vs[i] = vb.vs[i]->copy(home);
162  }
163 
164  template<class View, class Filter, int n>
165  bool
167  for (int i=start; i < x.size(); i++)
168  if (!x[i].assigned() && f(home,x[i],i)) {
169  start = i;
170  return true;
171  }
172  return false;
173  }
174 
175  template<class View, class Filter, int n>
176  inline Pos
178  assert(!x[start].assigned());
179  int s;
180  if (f) {
181  if (n == 1) {
182  s = vs[0]->select(home,x,start,f);
183  } else {
184  Region r;
185  int* ties = r.alloc<int>(x.size()-start+1);
186  int n_ties;
187  vs[0]->ties(home,x,start,ties,n_ties,f);
188  for (int i=1; (i < n-1) && (n_ties > 1); i++)
189  vs[i]->brk(home,x,ties,n_ties);
190  if (n_ties > 1)
191  s = vs[n-1]->select(home,x,ties,n_ties);
192  else
193  s = ties[0];
194  }
195  } else {
196  if (n == 1) {
197  s = vs[0]->select(home,x,start);
198  } else {
199  Region r;
200  int* ties = r.alloc<int>(x.size()-start+1);
201  int n_ties;
202  vs[0]->ties(home,x,start,ties,n_ties);
203  for (int i=1; (i < n-1) && (n_ties > 1); i++)
204  vs[i]->brk(home,x,ties,n_ties);
205  if (n_ties > 1)
206  s = vs[n-1]->select(home,x,ties,n_ties);
207  else
208  s = ties[0];
209  }
210  }
211  Pos p(s);
212  return p;
213  }
214 
215  template<class View, class Filter, int n>
216  forceinline View
218  return x[p.pos];
219  }
220 
221  template<class View, class Filter, int n>
222  forceinline size_t
224  for (int i=0; i<n; i++)
225  if (f.notice() || vs[i]->notice()) {
226  home.ignore(*this,AP_DISPOSE,true);
227  break;
228  }
229  for (int i=0; i<n; i++)
230  vs[i]->dispose(home);
231  (void) Brancher::dispose(home);
232  return sizeof(ViewBrancher<View,Filter,n>);
233  }
234 
235 }
236 
237 // STATISTICS: kernel-branch
Actor must always be disposed.
Definition: core.hpp:554
T * alloc(long unsigned int n)
Allocate block of n objects of type T from region.
Definition: region.hpp:384
Generic brancher by view selection.
Definition: view.hpp:82
bool pos(const View &x)
Test whether x is postive.
Definition: mult.hpp:45
Handle to region.
Definition: region.hpp:57
ViewArray< View > x
Views to branch on.
Definition: view.hpp:87
#define forceinline
Definition: config.hpp:182
Computation spaces.
Definition: core.hpp:1668
const Pos & pos(void) const
Return position in array.
Definition: view.hpp:130
ViewSel< View > * vs[n]
View selection objects.
Definition: view.hpp:91
Gecode::FloatVal c(-8, 8)
int p
Number of positive literals for node type.
Definition: bool-expr.cpp:236
Gecode::IntArgs i(4, 1, 2, 3, 4)
Base-class for branchers.
Definition: core.hpp:1368
int n
Number of negative literals for node type.
Definition: bool-expr.cpp:238
NNF * r
Right subtree.
Definition: bool-expr.cpp:246
int start
Unassigned views start at x[start].
Definition: view.hpp:89
std::function< bool(const Space &home, Var x, int i)> BranchFilter
Function type for branch filter functions.
Definition: filter.hpp:45
Choices storing position
Definition: view.hpp:59
ViewBrancher(Space &home, ViewBrancher< View, Filter, n > &b)
Constructor for cloning b.
Definition: view.hpp:156
Position information.
Definition: view.hpp:48
View arrays.
Definition: array.hpp:228
void notice(Actor &a, ActorProperty p, bool duplicate=false)
Notice actor property.
Definition: core.hpp:3139
virtual ViewSel< View > * copy(Space &home)=0
Create copy during cloning.
Pos(int p)
Create position information.
Definition: view.hpp:118
struct Gecode::@585::NNF::@62::@63 b
For binary nodes (and, or, eqv)
Post propagator for f(x \diamond_{\mathit{op}} y) \sim_r z \f$ void rel(Home home
Node * x
Pointer to corresponding Boolean expression node.
Definition: bool-expr.cpp:253
void ignore(Actor &a, ActorProperty p, bool duplicate=false)
Ignore actor property.
Definition: core.hpp:3944
virtual void archive(Archive &e) const
Archive into e.
Definition: core.cpp:857
struct Gecode::@585::NNF::@62::@64 a
For atomic nodes.
Choice for performing commit
Definition: core.hpp:1338
Archive representation
Definition: archive.hpp:46
bool assigned(View x, int v)
Whether x is assigned to value v.
Definition: single.hpp:47
Filter f
Filter function.
Definition: view.hpp:93
View::VarType Var
The corresponding variable.
Definition: view.hpp:85
Post propagator for SetVar x
Definition: set.hh:769
virtual void archive(Archive &e) const
Archive into e.
Definition: view.hpp:134
Gecode toplevel namespace
#define GECODE_VTABLE_EXPORT
Definition: support.hh:76
const int pos
Position of view.
Definition: view.hpp:51
PosChoice(const PosChoice &c)
Initialize.
Home class for posting propagators
Definition: core.hpp:846