Generated on Sat Feb 7 2015 02:01:27 for Gecode by doxygen 1.8.9.1
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: 2013-05-22 16:48:57 +0200 (Wed, 22 May 2013) $ by $Author: schulte $
11  * $Revision: 13654 $
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, int n>
79  class ViewBrancher : public Brancher {
80  protected:
86  mutable int start;
90  BranchFilter bf;
92  Pos pos(Space& home);
94  View view(const Pos& p) const;
99  ViewSel<View>* vs[n], BranchFilter bf);
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, int n>
141  ViewSel<View>* vs0[n], BranchFilter bf0)
142  : Brancher(home), x(x0), start(0), bf(bf0) {
143  for (int i=0; i<n; i++)
144  vs[i] = vs0[i];
145  for (int i=0; i<n; i++)
146  if (vs[i]->notice()) {
147  home.notice(*this,AP_DISPOSE);
148  break;
149  }
150  }
151 
152  template<class View, int n>
156  : Brancher(home,shared,vb), start(vb.start), bf(vb.bf) {
157  x.update(home,shared,vb.x);
158  for (int i=0; i<n; i++)
159  vs[i] = vb.vs[i]->copy(home,shared);
160  }
161 
162  template<class View, int n>
163  bool
164  ViewBrancher<View,n>::status(const Space& home) const {
165  if (bf == NULL) {
166  for (int i=start; i < x.size(); i++)
167  if (!x[i].assigned()) {
168  start = i;
169  return true;
170  }
171  } else {
172  for (int i=start; i < x.size(); i++) {
173  typename View::VarType y(x[i].varimp());
174  if (!x[i].assigned() && bf(home,y,i)) {
175  start = i;
176  return true;
177  }
178  }
179  }
180  return false;
181  }
182 
183  template<class View, int n>
184  inline Pos
186  assert(!x[start].assigned());
187  int s;
188  if (bf == NULL) {
189  if (n == 1) {
190  s = vs[0]->select(home,x,start);
191  } else {
192  Region r(home);
193  int* ties = r.alloc<int>(x.size()-start+1);
194  int n_ties;
195  vs[0]->ties(home,x,start,ties,n_ties);
196  for (int i=1; (i < n-1) && (n_ties > 1); i++)
197  vs[i]->brk(home,x,ties,n_ties);
198  if (n_ties > 1)
199  s = vs[n-1]->select(home,x,ties,n_ties);
200  else
201  s = ties[0];
202  }
203  } else {
204  if (n == 1) {
205  s = vs[0]->select(home,x,start,bf);
206  } else {
207  Region r(home);
208  int* ties = r.alloc<int>(x.size()-start+1);
209  int n_ties;
210  vs[0]->ties(home,x,start,ties,n_ties,bf);
211  for (int i=1; (i < n-1) && (n_ties > 1); i++)
212  vs[i]->brk(home,x,ties,n_ties);
213  if (n_ties > 1)
214  s = vs[n-1]->select(home,x,ties,n_ties);
215  else
216  s = ties[0];
217  }
218  }
219  Pos p(s);
220  return p;
221  }
222 
223  template<class View, int n>
224  forceinline View
226  return x[p.pos];
227  }
228 
229  template<class View, int n>
230  forceinline size_t
232  for (int i=0; i<n; i++)
233  if (vs[i]->notice()) {
234  home.ignore(*this,AP_DISPOSE,true);
235  break;
236  }
237  for (int i=0; i<n; i++)
238  vs[i]->dispose(home);
239  (void) Brancher::dispose(home);
240  return sizeof(ViewBrancher<View,n>);
241  }
242 
243 }
244 
245 // STATISTICS: kernel-branch
const Pos & pos(void) const
Return position in array.
BranchFilter bf
Branch filter function.
Actor must always be disposed.
Definition: core.hpp:610
T * alloc(long unsigned int n)
Allocate block of n objects of type T from region.
Definition: region.hpp:326
BranchTraits< typename View::VarType >::Filter BranchFilter
The branch filter that corresponds to the var type.
Generic brancher by view selection.
bool pos(const View &x)
Test whether x is postive.
Definition: mult.hpp:45
Handle to region.
Definition: region.hpp:61
ViewBrancher(Space &home, bool shared, ViewBrancher< View, n > &b)
Constructor for cloning b.
Computation spaces.
Definition: core.hpp:1362
virtual size_t dispose(Space &home)
Delete brancher and return its size.
Pos pos(Space &home)
Return position information.
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:1071
int n
Number of negative literals for node type.
Definition: bool-expr.cpp:238
NNF * r
Right subtree.
Definition: bool-expr.cpp:246
ViewSel< View > * vs[n]
View selection objects.
View view(const Pos &p) const
Return view according to position information p.
virtual void archive(Archive &e) const
Archive into e.
Definition: core.cpp:670
unsigned int size(I &i)
Size of all ranges of range iterator i.
Choices storing position
PosChoice(const Brancher &b, unsigned int a, const Pos &p)
Initialize choice for brancher b, number of alternatives a, and position p.
virtual size_t size(void) const
Report size occupied.
Position information.
View arrays.
Definition: array.hpp:234
void notice(Actor &a, ActorProperty p, bool duplicate=false)
Notice actor property.
Definition: core.hpp:2849
virtual void archive(Archive &e) const
Archive into e.
Pos(int p)
Create position information.
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.cpp:169
Choice for performing commit
Definition: core.hpp:1036
virtual size_t dispose(Space &home)
Delete actor and return its size.
Definition: core.hpp:2877
Archive representation
Definition: archive.hpp:45
bool assigned(View x, int v)
Whether x is assigned to value v.
Definition: single.hpp:47
#define forceinline
Definition: config.hpp:132
int start
Unassigned views start at x[start].
virtual bool status(const Space &home) const
Check status of brancher, return true if alternatives left.
bool shared(const ConstView< ViewA > &, const ConstView< ViewB > &)
Test whether views share same variable.
Definition: view.hpp:662
struct Gecode::@518::NNF::@57::@58 b
For binary nodes (and, or, eqv)
Gecode toplevel namespace
#define GECODE_VTABLE_EXPORT
Definition: support.hh:76
const int pos
Position of view.
ViewArray< View > x
Views to branch on.
virtual ViewSel< View > * copy(Space &home, bool shared)=0
Create copy during cloning.
Home class for posting propagators
Definition: core.hpp:717
Traits for branching.
struct Gecode::@518::NNF::@57::@59 a
For atomic nodes.