Generated on Sat Jan 20 2018 22:21:13 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  * Patrick Pekczynski <pekczynski@ps.uni-sb.de>
5  *
6  * Contributing authors:
7  * Christian Schulte <schulte@gecode.org>
8  * Guido Tack <tack@gecode.org>
9  *
10  * Copyright:
11  * Patrick Pekczynski, 2004
12  * Christian Schulte, 2009
13  * Guido Tack, 2009
14  *
15  * Last modified: $Date: 2016-06-29 17:28:17 +0200 (Wed, 29 Jun 2016) $ by $Author: schulte $
16  * $Revision: 15137 $
17  *
18  * This file is part of Gecode, the generic constrain
19  * development environment:
20  * http://www.gecode.org
21  *
22  *
23  * Permission is hereby granted, free of charge, to any person obtaining
24  * a copy of this software and associated documentation files (the
25  * "Software"), to deal in the Software without restriction, including
26  * without limitation the rights to use, copy, modify, merge, publish,
27  * distribute, sublicense, and/or sell copies of the Software, and to
28  * permit persons to whom the Software is furnished to do so, subject to
29  * the following conditions:
30  *
31  * The above copyright notice and this permission notice shall be
32  * included in all copies or substantial portions of the Software.
33  *
34  * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,
35  * EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF
36  * MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND
37  * NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE
38  * LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION
39  * OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION
40  * WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
41  */
42 
43 namespace Gecode { namespace Int { namespace GCC {
44 
46  template<class T>
47  forceinline bool
48  lookupValue(T& a, int v, int& i) {
49  int l = 0;
50  int r = a.size() - 1;
51 
52  while (l <= r) {
53  int m = l + (r - l) / 2;
54  if (v == a[m].card()) {
55  i=m; return true;
56  } else if (l == r) {
57  return false;
58  } else if (v < a[m].card()) {
59  r=m-1;
60  } else {
61  l=m+1;
62  }
63  }
64  return false;
65  }
66 
68  class CardConst {
69  private:
71  int _min;
73  int _max;
75  int _card;
77  int _counter;
78  public:
80  static const bool propagate = false;
81 
83 
84  CardConst(void);
87  void init(Space& home, int min, int max, int c);
89 
91 
92  int min(void) const;
95  int max(void) const;
97  int card(void) const;
99  int counter(void) const;
101 
105  bool assigned(void) const;
107 
111  void counter(int n);
113  ModEvent inc(void);
115  ModEvent lq(Space& home, int n);
117  ModEvent gq(Space& home, int n);
119  ModEvent eq(Space& home, int n);
121 
125  void subscribe(Space& home, Propagator& p, PropCond pc, bool process=true);
127  void cancel(Space& home, Propagator& p, PropCond pc);
129  void reschedule(Space& home, Propagator& p, PropCond pc);
131 
135  void update(Space& home, bool share, CardConst& x);
137 
139  IntView base(void) const;
140  };
141 
143  class CardView : public DerivedView<IntView> {
144  protected:
147  int _card;
149  int _counter;
150  public:
152  static const bool propagate = true;
154 
155  CardView(void);
158  void init(const IntView& y, int c);
160  void init(Space& home, const IntSet& s, int c);
162 
164 
165  int min(void) const;
168  int max(void) const;
170  unsigned int size(void) const;
172  int counter(void) const;
174  int card(void) const;
176 
180  void counter(int n);
182  ModEvent inc(void);
184  ModEvent lq(Space& home, int n);
186  ModEvent gq(Space& home, int n);
188  ModEvent eq(Space& home, int n);
190 
192 
193  template<class I>
195  ModEvent narrow_v(Space& home, I& i, bool depends=true);
197  template<class I>
198  ModEvent inter_v(Space& home, I& i, bool depends=true);
200  template<class I>
201  ModEvent minus_v(Space& home, I& i, bool depends=true);
203 
207  void update(Space& home, bool share, CardView& x);
209  };
210 
211 
212 
213  /*
214  * Constant cardinality view
215  *
216  */
219  forceinline void
220  CardConst::init(Space&, int min, int max, int c) {
221  _min = min; _max=max; _card = c; _counter = 0;
222  }
223 
224  forceinline int
225  CardConst::min(void) const {
226  return _min;
227  }
228  forceinline int
229  CardConst::max(void) const {
230  return _max;
231  }
232  forceinline int
233  CardConst::card(void) const {
234  return _card;
235  }
236  forceinline int
237  CardConst::counter(void) const {
238  return _counter;
239  }
240  forceinline bool
241  CardConst::assigned(void) const {
242  return _min==_max;
243  }
244 
245 
246  forceinline void
248  _counter = n;
249  }
252  if (++_counter > _max)
253  return ME_INT_FAILED;
254  return ME_INT_NONE;
255  }
258  if (_min > n)
259  return ME_INT_FAILED;
260  return ME_INT_NONE;
261  }
264  if (_max < n)
265  return ME_INT_FAILED;
266  return ME_INT_NONE;
267  }
270  if ((_min > n) || (_max < n))
271  return ME_INT_FAILED;
272  return ME_INT_NONE;
273  }
274 
275  forceinline void
277  forceinline void
279  forceinline void
281 
282  forceinline void
284  _min=x._min; _max=x._max; _card=x._card; _counter=x._counter;
285  }
286 
288  CardConst::base(void) const {
289  GECODE_NEVER;
290  return IntView();
291  }
292 
293 
294 
295  /*
296  * Cardinality integer view
297  *
298  */
301  forceinline void
302  CardView::init(const IntView& y, int c) {
303  x = y; _card = c; _counter = 0;
304  }
305  forceinline void
306  CardView::init(Space& home, const IntSet& s, int c) {
307  x = IntVar(home,s); _card = c; _counter = 0;
308  }
309 
310  forceinline int
311  CardView::counter(void) const {
312  return _counter;
313  }
314  forceinline int
315  CardView::card(void) const {
316  return _card;
317  }
318  forceinline int
319  CardView::min(void) const {
320  return x.min();
321  }
322  forceinline int
323  CardView::max(void) const {
324  return x.max();
325  }
326  forceinline unsigned int
327  CardView::size(void) const {
328  return x.size();
329  }
330 
331  forceinline void
333  _counter = n;
334  }
337  if (++_counter > this->max())
338  return ME_INT_FAILED;
339  return ME_GEN_NONE;
340  }
342  CardView::lq(Space& home, int n) {
343  return x.lq(home,n);
344  }
346  CardView::gq(Space& home, int n) {
347  return x.gq(home,n);
348  }
350  CardView::eq(Space& home, int n) {
351  return x.eq(home,n);
352  }
353 
354  template<class I>
356  CardView::narrow_v(Space& home, I& i, bool depends) {
357  return x.narrow_v(home,i,depends);
358  }
359  template<class I>
361  CardView::inter_v(Space& home, I& i, bool depends) {
362  return x.inter_v(home,i,depends);
363  }
364  template<class I>
366  CardView::minus_v(Space& home, I& i, bool depends) {
367  return x.minus_v(home,i,depends);
368  }
369 
370  forceinline void
371  CardView::update(Space& home, bool share, CardView& y) {
372  x.update(home,share,y.x);
373  _card = y._card; _counter = y._counter;
374  }
375 
376 }
377 
378 
382  template<>
383  class ViewRanges<GCC::CardView>
384  : public Gecode::Int::ViewRanges<IntView> {
385  public:
389  ViewRanges(void);
391  ViewRanges(const GCC::CardView& x);
393  void init(const GCC::CardView& x);
395  };
396 
399  Gecode::Int::ViewRanges<IntView>() {}
400 
403  : Gecode::Int::ViewRanges<IntView>(x.base()) {}
404 
405  forceinline void
408  }
409 
410 }}
411 
412 
413 
414 // STATISTICS: int-prop
int max(void) const
Return maximum of domain.
Definition: view.hpp:323
View base(void) const
Return view from which this view is derived.
Definition: view.hpp:561
CardView(void)
Default constructor.
Definition: view.hpp:300
NNF * l
Left subtree.
Definition: bool-expr.cpp:244
void update(Space &home, bool share, CardView &x)
Definition: view.hpp:371
void cancel(Space &home, Propagator &p, PropCond pc)
Cancel subscription of propagator p with propagation condition pc to view.
Definition: view.hpp:278
void update(Space &home, bool share, VarImpVar< VarImp > &y)
Update this variable to be a clone of variable y.
Definition: var.hpp:128
IntView base(void) const
Return used IntView (cannot be used)
Definition: view.hpp:288
Constant view containing lower and upper cardinality bounds.
Definition: view.hpp:68
bool lookupValue(T &a, int v, int &i)
Return index of v in array a.
Definition: view.hpp:48
ViewRanges(void)
Default constructor.
int card(void) const
Return cardinality.
Definition: view.hpp:315
int _card
Cardinality.
Definition: view.hpp:147
int ModEvent
Type for modification events.
Definition: core.hpp:142
void reschedule(Space &home, Propagator &p, PropCond pc)
Schedule propagator p.
Definition: view.hpp:280
Base-class for propagators.
Definition: core.hpp:1092
unsigned int size(void) const
Return size (cardinality) of domain.
Definition: view.hpp:327
Range iterator for integer variable views
Definition: int.hpp:236
const unsigned int card
Maximum cardinality of an integer set.
Definition: set.hh:105
ModEvent lq(Space &home, int n)
Restrict domain values to be less or equal than n.
Definition: view.hpp:342
Computation spaces.
Definition: core.hpp:1748
void init(const View &x)
Initialize with ranges for view x.
Base-class for derived views.
Definition: view.hpp:222
Range iterator for integer views.
Definition: view.hpp:54
const Gecode::ModEvent ME_INT_FAILED
Domain operation has resulted in failure.
Definition: var-type.hpp:52
struct Gecode::@579::NNF::@61::@63 a
For atomic nodes.
Gecode::FloatVal c(-8, 8)
CardConst(void)
Default constructor.
Definition: view.hpp:218
ModEvent lq(Space &home, int n)
Restrict domain values to be less or equal than n.
Definition: view.hpp:257
int p
Number of positive literals for node type.
Definition: bool-expr.cpp:236
Gecode::IntArgs i(4, 1, 2, 3, 4)
int n
Number of negative literals for node type.
Definition: bool-expr.cpp:238
ModEvent inter_v(Space &home, I &i, bool depends=true)
Intersect domain with values described by i.
Definition: view.hpp:361
static const bool propagate
This view does not require propagation.
Definition: view.hpp:80
int _counter
Counter.
Definition: view.hpp:149
ModEvent eq(Space &home, int n)
Restrict domain values to be equal to n.
Definition: view.hpp:269
int PropCond
Type for propagation conditions.
Definition: core.hpp:152
ModEvent eq(Space &home, int n)
Restrict domain values to be equal to n.
Definition: view.hpp:350
int card(void) const
Return cardinality.
Definition: view.hpp:233
ModEvent gq(Space &home, int n)
Restrict domain values to be greater or equal than n.
Definition: view.hpp:346
unsigned int size(I &i)
Size of all ranges of range iterator i.
int min(void) const
Return minimum of domain.
Definition: view.hpp:319
Integer sets.
Definition: int.hh:174
Cardinality integer view.
Definition: view.hpp:143
void init(Space &home, int min, int max, int c)
Initialize with min, max, and cardinality c.
Definition: view.hpp:220
void init(const IntView &y, int c)
Initialize with integer view y and value c.
Definition: view.hpp:302
Post propagator for SetVar SetOpType SetVar SetRelType r
Definition: set.hh:784
const int v[7]
Definition: distinct.cpp:263
Integer view for integer variables.
Definition: view.hpp:129
ModEvent inc(void)
Increment counter.
Definition: view.hpp:251
Post propagator for SetVar SetOpType SetVar y
Definition: set.hh:784
const double base
Base for geometric restart sequence.
Definition: search.hh:122
ModEvent narrow_v(Space &home, I &i, bool depends=true)
Replace domain by values described by i.
Definition: view.hpp:356
void update(Space &home, bool share, CardConst &x)
Definition: view.hpp:283
Integer variables.
Definition: int.hh:353
ModEvent gq(Space &home, int n)
Restrict domain values to be greater or equal than n.
Definition: view.hpp:263
#define forceinline
Definition: config.hpp:173
void subscribe(Space &home, Propagator &p, PropCond pc, bool process=true)
Cancel subscription of propagator p with propagation condition pc to view.
Definition: view.hpp:276
const ModEvent ME_GEN_NONE
Generic modification event: no modification.
Definition: core.hpp:147
Post propagator for SetVar x
Definition: set.hh:784
View x
View from which this view is derived.
Definition: view.hpp:230
int counter(void) const
Return the number of times the value occurs.
Definition: view.hpp:311
int max(void) const
Return maximum of domain.
Definition: view.hpp:229
Gecode toplevel namespace
bool assigned(void) const
Definition: view.hpp:241
int min(void) const
Return minimum of domain.
Definition: view.hpp:225
ModEvent inc(void)
Increment counter.
Definition: view.hpp:336
int counter(void) const
Return the number of times the value occurs.
Definition: view.hpp:237
ModEvent minus_v(Space &home, I &i, bool depends=true)
Remove from domain the values described by i.
Definition: view.hpp:366
#define GECODE_NEVER
Assert that this command is never executed.
Definition: macros.hpp:60
const Gecode::ModEvent ME_INT_NONE
Domain operation has not changed domain.
Definition: var-type.hpp:54