Generated on Sat Apr 10 2021 00:00:00 for Gecode by doxygen 1.9.1
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  * This file is part of Gecode, the generic constraint
10  * development environment:
11  * http://www.gecode.org
12  *
13  * Permission is hereby granted, free of charge, to any person obtaining
14  * a copy of this software and associated documentation files (the
15  * "Software"), to deal in the Software without restriction, including
16  * without limitation the rights to use, copy, modify, merge, publish,
17  * distribute, sublicense, and/or sell copies of the Software, and to
18  * permit persons to whom the Software is furnished to do so, subject to
19  * the following conditions:
20  *
21  * The above copyright notice and this permission notice shall be
22  * included in all copies or substantial portions of the Software.
23  *
24  * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,
25  * EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF
26  * MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND
27  * NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE
28  * LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION
29  * OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION
30  * WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
31  *
32  */
33 
34 namespace Gecode {
35 
44  class Pos {
45  public:
47  const int pos;
49  Pos(int p);
51  Pos(const Pos& p);
52  };
53 
56  private:
58  const Pos _pos;
59  protected:
62  public:
64  PosChoice(const Brancher& b, unsigned int a, const Pos& p);
66  const Pos& pos(void) const;
68  virtual void archive(Archive& e) const;
69  };
70 
77  template<class View, class Filter, int n>
78  class ViewBrancher : public Brancher {
79  protected:
81  typedef typename View::VarType Var;
85  mutable int start;
89  Filter f;
91  Pos pos(Space& home);
93  View view(const Pos& p) const;
99  public:
101  virtual bool status(const Space& home) const;
103  virtual size_t dispose(Space& home);
104  };
105 
107 
108 
109  /*
110  * Position information
111  *
112  */
114  Pos::Pos(int p) : pos(p) {}
116  Pos::Pos(const Pos& p) : pos(p.pos) {}
117 
118  /*
119  * Choice with position
120  *
121  */
123  PosChoice::PosChoice(const Brancher& b, unsigned int a, const Pos& p)
124  : Choice(b,a), _pos(p) {}
125  forceinline const Pos&
126  PosChoice::pos(void) const {
127  return _pos;
128  }
129  forceinline void
131  Choice::archive(e);
132  e << _pos.pos;
133  }
134 
135  template<class View, class Filter, int n>
138  ViewSel<View>* vs0[n],
140  : Brancher(home), x(x0), start(0), f(bf) {
141  for (int i=0; i<n; i++)
142  vs[i] = vs0[i];
143  for (int i=0; i<n; i++)
144  if (f.notice() || vs[i]->notice()) {
145  home.notice(*this,AP_DISPOSE,true);
146  break;
147  }
148  }
149 
150  template<class View, class Filter, int n>
154  : Brancher(home,vb), start(vb.start), f(vb.f) {
155  x.update(home,vb.x);
156  for (int i=0; i<n; i++)
157  vs[i] = vb.vs[i]->copy(home);
158  }
159 
160  template<class View, class Filter, int n>
161  bool
163  for (int i=start; i < x.size(); i++)
164  if (!x[i].assigned() && f(home,x[i],i)) {
165  start = i;
166  return true;
167  }
168  return false;
169  }
170 
171  template<class View, class Filter, int n>
172  inline Pos
174  assert(!x[start].assigned());
175  int s;
176  if (f) {
177  if (n == 1) {
178  s = vs[0]->select(home,x,start,f);
179  } else {
180  Region r;
181  int* ties = r.alloc<int>(x.size()-start+1);
182  int n_ties;
183  vs[0]->ties(home,x,start,ties,n_ties,f);
184  for (int i=1; (i < n-1) && (n_ties > 1); i++)
185  vs[i]->brk(home,x,ties,n_ties);
186  if (n_ties > 1)
187  s = vs[n-1]->select(home,x,ties,n_ties);
188  else
189  s = ties[0];
190  }
191  } else {
192  if (n == 1) {
193  s = vs[0]->select(home,x,start);
194  } else {
195  Region r;
196  int* ties = r.alloc<int>(x.size()-start+1);
197  int n_ties;
198  vs[0]->ties(home,x,start,ties,n_ties);
199  for (int i=1; (i < n-1) && (n_ties > 1); i++)
200  vs[i]->brk(home,x,ties,n_ties);
201  if (n_ties > 1)
202  s = vs[n-1]->select(home,x,ties,n_ties);
203  else
204  s = ties[0];
205  }
206  }
207  Pos p(s);
208  return p;
209  }
210 
211  template<class View, class Filter, int n>
212  forceinline View
214  return x[p.pos];
215  }
216 
217  template<class View, class Filter, int n>
218  forceinline size_t
220  for (int i=0; i<n; i++)
221  if (f.notice() || vs[i]->notice()) {
222  home.ignore(*this,AP_DISPOSE,true);
223  break;
224  }
225  for (int i=0; i<n; i++)
226  vs[i]->dispose(home);
227  (void) Brancher::dispose(home);
228  return sizeof(ViewBrancher<View,Filter,n>);
229  }
230 
231 }
232 
233 // STATISTICS: kernel-branch
struct Gecode::@602::NNF::@65::@66 b
For binary nodes (and, or, eqv)
int p
Number of positive literals for node type.
Definition: bool-expr.cpp:232
int n
Number of negative literals for node type.
Definition: bool-expr.cpp:234
Node * x
Pointer to corresponding Boolean expression node.
Definition: bool-expr.cpp:249
struct Gecode::@602::NNF::@65::@67 a
For atomic nodes.
NNF * r
Right subtree.
Definition: bool-expr.cpp:242
std::function< bool(const Space &home, Var x, int i)> BranchFilter
Function type for branch filter functions.
Definition: filter.hpp:41
virtual size_t dispose(Space &home)
Delete actor and return its size.
Definition: core.hpp:3252
Archive representation
Definition: archive.hpp:42
Base-class for branchers.
Definition: core.hpp:1442
Choice for performing commit
Definition: core.hpp:1412
virtual void archive(Archive &e) const
Archive into e.
Definition: core.cpp:891
Home class for posting propagators
Definition: core.hpp:856
void notice(Actor &a, ActorProperty p, bool duplicate=false)
Notice actor property.
Definition: core.hpp:3219
Choices storing position
Definition: view.hpp:55
virtual void archive(Archive &e) const
Archive into e.
Definition: view.hpp:130
const Pos & pos(void) const
Return position in array.
Definition: view.hpp:126
PosChoice(const PosChoice &c)
Initialize.
Position information.
Definition: view.hpp:44
Pos(int p)
Create position information.
Definition: view.hpp:114
const int pos
Position of view.
Definition: view.hpp:47
Handle to region.
Definition: region.hpp:55
Computation spaces.
Definition: core.hpp:1742
View arrays.
Definition: array.hpp:253
Generic brancher by view selection.
Definition: view.hpp:78
Pos pos(Space &home)
Return position information.
Definition: view.hpp:173
Filter f
Filter function.
Definition: view.hpp:89
ViewBrancher(Home home, ViewArray< View > &x, ViewSel< View > *vs[n], BranchFilter< Var > bf)
Constructor for creation.
Definition: view.hpp:137
ViewArray< View > x
Views to branch on.
Definition: view.hpp:83
ViewBrancher(Space &home, ViewBrancher< View, Filter, n > &b)
Constructor for cloning b.
Definition: view.hpp:152
View view(const Pos &p) const
Return view according to position information p.
Definition: view.hpp:213
virtual size_t dispose(Space &home)
Delete brancher and return its size.
Definition: view.hpp:219
int start
Unassigned views start at x[start].
Definition: view.hpp:85
View::VarType Var
The corresponding variable.
Definition: view.hpp:81
ViewSel< View > * vs[n]
View selection objects.
Definition: view.hpp:87
virtual bool status(const Space &home) const
Check status of brancher, return true if alternatives left.
Definition: view.hpp:162
virtual ViewSel< View > * copy(Space &home)=0
Create copy during cloning.
virtual bool notice(void) const
Whether dispose must always be called (that is, notice is needed)
Definition: view-sel.hpp:397
void ignore(Actor &a, ActorProperty p, bool duplicate=false)
Ignore actor property.
Definition: core.hpp:4074
@ AP_DISPOSE
Actor must always be disposed.
Definition: core.hpp:562
bool pos(const View &x)
Test whether x is postive.
Definition: mult.hpp:41
bool assigned(View x, int v)
Whether x is assigned to value v.
Definition: single.hpp:43
Gecode::FloatVal c(-8, 8)
Gecode::IntArgs i({1, 2, 3, 4})
#define forceinline
Definition: config.hpp:192
#define GECODE_VTABLE_EXPORT
Definition: support.hh:72