Generated on Tue Jan 28 2020 00:00:00 for Gecode by doxygen 1.8.17
brancher-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: 2017-04-01 20:27:10 +0200 (Sat, 01 Apr 2017) $ by $Author: schulte $
11  * $Revision: 15623 $
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);
54  };
55 
58  private:
60  const Pos _pos;
61  public:
63  PosChoice(const Brancher& b, unsigned int a, const Pos& p);
65  const Pos& pos(void) const;
67  virtual size_t size(void) const;
69  virtual void archive(Archive& e) const;
70  };
71 
78  template<class View, class Filter, int n>
79  class ViewBrancher : public Brancher {
80  protected:
82  typedef typename View::VarType Var;
86  mutable int start;
90  Filter f;
92  Pos pos(Space& home);
94  View view(const Pos& p) const;
100  public:
102  virtual bool status(const Space& home) const;
104  virtual size_t dispose(Space& home);
105  };
106 
108 
109 
110  /*
111  * Position information
112  *
113  */
115  Pos::Pos(int p) : pos(p) {}
116 
117  /*
118  * Choice with position
119  *
120  */
122  PosChoice::PosChoice(const Brancher& b, unsigned int a, const Pos& p)
123  : Choice(b,a), _pos(p) {}
124  forceinline const Pos&
125  PosChoice::pos(void) const {
126  return _pos;
127  }
128  forceinline size_t
129  PosChoice::size(void) const {
130  return sizeof(PosChoice);
131  }
132  forceinline void
134  Choice::archive(e);
135  e << _pos.pos;
136  }
137 
138  template<class View, class Filter, int n>
141  ViewSel<View>* vs0[n],
143  : Brancher(home), x(x0), start(0), f(bf) {
144  for (int i=0; i<n; i++)
145  vs[i] = vs0[i];
146  for (int i=0; i<n; i++)
147  if (f.notice() || vs[i]->notice()) {
148  home.notice(*this,AP_DISPOSE,true);
149  break;
150  }
151  }
152 
153  template<class View, class Filter, int n>
157  : Brancher(home,shared,vb), start(vb.start),
158  f(home,shared,vb.f) {
159  x.update(home,shared,vb.x);
160  for (int i=0; i<n; i++)
161  vs[i] = vb.vs[i]->copy(home,shared);
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(home);
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(home);
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
void notice(Actor &a, ActorProperty p, bool duplicate=false)
Notice actor property.
Definition: core.hpp:3321
std::function< bool(const Space &home, Var x, int i)> BranchFilter
Function type for branch filter functions.
Post propagator for SetVar x
Definition: set.hh:784
#define forceinline
Definition: config.hpp:173
#define GECODE_VTABLE_EXPORT
Definition: support.hh:76
unsigned int size(I &i)
Size of all ranges of range iterator i.
virtual size_t size(void) const
Report size occupied.
bool assigned(View x, int v)
Whether x is assigned to value v.
Definition: single.hpp:47
Pos pos(Space &home)
Return position information.
Gecode::IntArgs i(4, 1, 2, 3, 4)
Archive representation
Definition: archive.hpp:45
Filter f
Filter function.
const int pos
Position of view.
int start
Unassigned views start at x[start].
ViewArray< View > x
Views to branch on.
Computation spaces.
Definition: core.hpp:1748
virtual void archive(Archive &e) const
Archive into e.
virtual size_t dispose(Space &home)
Delete brancher and return its size.
Gecode toplevel namespace
Generic brancher by view selection.
ViewSel< View > * vs[n]
View selection objects.
View::VarType Var
The corresponding variable.
Node * x
Pointer to corresponding Boolean expression node.
Definition: bool-expr.cpp:253
Choices storing position
Base-class for branchers.
Definition: core.hpp:1446
Home class for posting propagators
Definition: core.hpp:922
struct Gecode::@579::NNF::@61::@63 a
For atomic nodes.
struct Gecode::@579::NNF::@61::@62 b
For binary nodes (and, or, eqv)
Handle to region.
Definition: region.hpp:61
@ AP_DISPOSE
Actor must always be disposed.
Definition: core.hpp:630
View view(const Pos &p) const
Return view according to position information p.
ViewBrancher(Space &home, bool shared, ViewBrancher< View, Filter, n > &b)
Constructor for cloning b.
bool shared(const ConstView< ViewA > &, const ConstView< ViewB > &)
Test whether views share same variable.
PosChoice(const Brancher &b, unsigned int a, const Pos &p)
Initialize choice for brancher b, number of alternatives a, and position p.
bool shared(const IntSet &, VX)
Definition: view-base.hpp:122
Pos(int p)
Create position information.
NNF * r
Right subtree.
Definition: bool-expr.cpp:246
void ignore(Actor &a, ActorProperty p, bool duplicate=false)
Ignore actor property.
Definition: core.hpp:4141
Post propagator for f(x \diamond_{\mathit{op}} y) \sim_r z \f$ void rel(Home home
Position information.
View arrays.
Definition: array.hpp:234
virtual bool status(const Space &home) const
Check status of brancher, return true if alternatives left.
int n
Number of negative literals for node type.
Definition: bool-expr.cpp:238
Choice for performing commit
Definition: core.hpp:1414
bool pos(const View &x)
Test whether x is postive.
Definition: mult.hpp:45
int p
Number of positive literals for node type.
Definition: bool-expr.cpp:236
virtual void archive(Archive &e) const
Archive into e.
Definition: core.cpp:854
virtual ViewSel< View > * copy(Space &home, bool shared)=0
Create copy during cloning.
const Pos & pos(void) const
Return position in array.