Generated on Sat Feb 7 2015 02:01:17 for Gecode by doxygen 1.8.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  * 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: 2010-06-29 10:39:13 +0200 (Tue, 29 Jun 2010) $ by $Author: schulte $
16  * $Revision: 11118 $
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 
133  void update(Space& home, bool share, CardConst& x);
135 
137  IntView base(void) const;
138  };
139 
141  class CardView : public DerivedView<IntView> {
142  protected:
145  int _card;
147  int _counter;
148  public:
150  static const bool propagate = true;
152 
153  CardView(void);
156  void init(const IntView& y, int c);
158  void init(Space& home, const IntSet& s, int c);
160 
162 
163  int min(void) const;
166  int max(void) const;
168  unsigned int size(void) const;
170  int counter(void) const;
172  int card(void) const;
174 
178  void counter(int n);
180  ModEvent inc(void);
182  ModEvent lq(Space& home, int n);
184  ModEvent gq(Space& home, int n);
186  ModEvent eq(Space& home, int n);
188 
190 
191  template<class I>
193  ModEvent narrow_v(Space& home, I& i, bool depends=true);
195  template<class I>
196  ModEvent inter_v(Space& home, I& i, bool depends=true);
198  template<class I>
199  ModEvent minus_v(Space& home, I& i, bool depends=true);
201 
205  void update(Space& home, bool share, CardView& x);
207  };
208 
209 
210 
211  /*
212  * Constant cardinality view
213  *
214  */
217  forceinline void
218  CardConst::init(Space&, int min, int max, int c) {
219  _min = min; _max=max; _card = c; _counter = 0;
220  }
221 
222  forceinline int
223  CardConst::min(void) const {
224  return _min;
225  }
226  forceinline int
227  CardConst::max(void) const {
228  return _max;
229  }
230  forceinline int
231  CardConst::card(void) const {
232  return _card;
233  }
234  forceinline int
235  CardConst::counter(void) const {
236  return _counter;
237  }
238  forceinline bool
239  CardConst::assigned(void) const {
240  return _min==_max;
241  }
242 
243 
244  forceinline void
246  _counter = n;
247  }
250  if (++_counter > _max)
251  return ME_INT_FAILED;
252  return ME_INT_NONE;
253  }
256  if (_min > n)
257  return ME_INT_FAILED;
258  return ME_INT_NONE;
259  }
262  if (_max < n)
263  return ME_INT_FAILED;
264  return ME_INT_NONE;
265  }
268  if ((_min > n) || (_max < n))
269  return ME_INT_FAILED;
270  return ME_INT_NONE;
271  }
272 
273  forceinline void
275  forceinline void
277 
278  forceinline void
280  _min=x._min; _max=x._max; _card=x._card; _counter=x._counter;
281  }
282 
284  CardConst::base(void) const {
285  GECODE_NEVER;
286  return IntView();
287  }
288 
289 
290 
291  /*
292  * Cardinality integer view
293  *
294  */
297  forceinline void
298  CardView::init(const IntView& y, int c) {
299  x = y; _card = c; _counter = 0;
300  }
301  forceinline void
302  CardView::init(Space& home, const IntSet& s, int c) {
303  x = IntVar(home,s); _card = c; _counter = 0;
304  }
305 
306  forceinline int
307  CardView::counter(void) const {
308  return _counter;
309  }
310  forceinline int
311  CardView::card(void) const {
312  return _card;
313  }
314  forceinline int
315  CardView::min(void) const {
316  return x.min();
317  }
318  forceinline int
319  CardView::max(void) const {
320  return x.max();
321  }
322  forceinline unsigned int
323  CardView::size(void) const {
324  return x.size();
325  }
326 
327  forceinline void
329  _counter = n;
330  }
333  if (++_counter > this->max())
334  return ME_INT_FAILED;
335  return ME_GEN_NONE;
336  }
338  CardView::lq(Space& home, int n) {
339  return x.lq(home,n);
340  }
342  CardView::gq(Space& home, int n) {
343  return x.gq(home,n);
344  }
346  CardView::eq(Space& home, int n) {
347  return x.eq(home,n);
348  }
349 
350  template<class I>
352  CardView::narrow_v(Space& home, I& i, bool depends) {
353  return x.narrow_v(home,i,depends);
354  }
355  template<class I>
357  CardView::inter_v(Space& home, I& i, bool depends) {
358  return x.inter_v(home,i,depends);
359  }
360  template<class I>
362  CardView::minus_v(Space& home, I& i, bool depends) {
363  return x.minus_v(home,i,depends);
364  }
365 
366  forceinline void
367  CardView::update(Space& home, bool share, CardView& y) {
368  x.update(home,share,y.x);
369  _card = y._card; _counter = y._counter;
370  }
371 
372 }
373 
374 
378  template<>
379  class ViewRanges<GCC::CardView>
380  : public Gecode::Int::ViewRanges<IntView> {
381  public:
385  ViewRanges(void);
387  ViewRanges(const GCC::CardView& x);
389  void init(const GCC::CardView& x);
391  };
392 
395  Gecode::Int::ViewRanges<IntView>() {}
396 
399  : Gecode::Int::ViewRanges<IntView>(x.base()) {}
400 
401  forceinline void
404  }
405 
406 }}
407 
408 
409 
410 // STATISTICS: int-prop
CardView(void)
Default constructor.
Definition: view.hpp:296
bool assigned(void) const
Definition: view.hpp:239
NNF * l
Left subtree.
Definition: bool-expr.cpp:244
void update(Space &home, bool share, CardView &x)
Definition: view.hpp:367
int card(void) const
Return cardinality.
Definition: view.hpp:311
static const bool propagate
This view does require propagation.
Definition: view.hpp:150
void cancel(Space &home, Propagator &p, PropCond pc)
Cancel subscription of propagator p with propagation condition pc to view.
Definition: view.hpp:276
ModEvent eq(Space &home, int n)
Restrict domain values to be equal to n.
Definition: int.hpp:160
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
void max(Home home, FloatVar x0, FloatVar x1, FloatVar x2)
Post propagator for .
Definition: arithmetic.cpp:57
ViewRanges(void)
Default constructor.
int _card
Cardinality.
Definition: view.hpp:145
int ModEvent
Type for modification events.
Definition: core.hpp:146
Base-class for propagators.
Definition: core.hpp:755
Range iterator for integer variable views
Definition: int.hpp:236
unsigned int size(void) const
Return size (cardinality) of domain.
Definition: view.hpp:323
const unsigned int card
Maximum cardinality of an integer set.
Definition: set.hh:103
ModEvent lq(Space &home, int n)
Restrict domain values to be less or equal than n.
Definition: view.hpp:338
Computation spaces.
Definition: core.hpp:1362
void init(const View &x)
Initialize with ranges for view x.
Base-class for derived views.
Definition: view.hpp:208
ModEvent minus_v(Space &home, I &i, bool depends=true)
Remove from domain the values described by i.
Definition: int.hpp:200
Range iterator for integer views.
Definition: view.hpp:54
int max(void) const
Return maximum of domain.
Definition: int.hpp:62
const Gecode::ModEvent ME_INT_FAILED
Domain operation has resulted in failure.
Definition: var-type.hpp:52
Gecode::FloatVal c(-8, 8)
CardConst(void)
Default constructor.
Definition: view.hpp:216
ModEvent lq(Space &home, int n)
Restrict domain values to be less or equal than n.
Definition: view.hpp:255
int p
Number of positive literals for node type.
Definition: bool-expr.cpp:236
Gecode::IntArgs i(4, 1, 2, 3, 4)
int min(void) const
Return minimum of domain.
Definition: view.hpp:223
int n
Number of negative literals for node type.
Definition: bool-expr.cpp:238
ModEvent narrow_v(Space &home, I &i, bool depends=true)
Replace domain by values described by i.
Definition: int.hpp:190
ModEvent inter_v(Space &home, I &i, bool depends=true)
Intersect domain with values described by i.
Definition: view.hpp:357
ModEvent lq(Space &home, int n)
Restrict domain values to be less or equal than n.
Definition: int.hpp:115
static const bool propagate
This view does not require propagation.
Definition: view.hpp:80
NNF * r
Right subtree.
Definition: bool-expr.cpp:246
int _counter
Counter.
Definition: view.hpp:147
View base(void) const
Return view from which this view is derived.
Definition: view.hpp:526
ModEvent eq(Space &home, int n)
Restrict domain values to be equal to n.
Definition: view.hpp:267
unsigned int size(void) const
Return size (cardinality) of domain.
Definition: int.hpp:75
int PropCond
Type for propagation conditions.
Definition: core.hpp:156
ModEvent eq(Space &home, int n)
Restrict domain values to be equal to n.
Definition: view.hpp:346
ModEvent gq(Space &home, int n)
Restrict domain values to be greater or equal than n.
Definition: view.hpp:342
int min(void) const
Return minimum of domain.
Definition: int.hpp:58
Integer sets.
Definition: int.hh:171
Cardinality integer view.
Definition: view.hpp:141
IntView base(void) const
Return used IntView (cannot be used)
Definition: view.hpp:284
void update(Space &home, bool share, VarImpView< Var > &y)
Update this view to be a clone of view y.
Definition: view.hpp:494
void init(Space &home, int min, int max, int c)
Initialize with min, max, and cardinality c.
Definition: view.hpp:218
int max(void) const
Return maximum of domain.
Definition: view.hpp:227
int card(void) const
Return cardinality.
Definition: view.hpp:231
ModEvent inter_v(Space &home, I &i, bool depends=true)
Intersect domain with values described by i.
Definition: int.hpp:195
void init(const IntView &y, int c)
Initialize with integer view y and value c.
Definition: view.hpp:298
const int v[7]
Definition: distinct.cpp:207
void min(Home home, FloatVar x0, FloatVar x1, FloatVar x2)
Post propagator for .
Definition: arithmetic.cpp:75
Integer view for integer variables.
Definition: view.hpp:129
ModEvent inc(void)
Increment counter.
Definition: view.hpp:249
int max(void) const
Return maximum of domain.
Definition: view.hpp:319
Node * x
Pointer to corresponding Boolean expression node.
Definition: bool-expr.cpp:253
ModEvent narrow_v(Space &home, I &i, bool depends=true)
Replace domain by values described by i.
Definition: view.hpp:352
void update(Space &home, bool share, CardConst &x)
Definition: view.hpp:279
Integer variables.
Definition: int.hh:350
ModEvent gq(Space &home, int n)
Restrict domain values to be greater or equal than n.
Definition: view.hpp:261
#define forceinline
Definition: config.hpp:132
int counter(void) const
Return the number of times the value occurs.
Definition: view.hpp:235
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:274
ModEvent gq(Space &home, int n)
Restrict domain values to be greater or equal than n.
Definition: int.hpp:133
const ModEvent ME_GEN_NONE
Generic modification event: no modification.
Definition: core.hpp:151
IntView x
View from which this view is derived.
Definition: view.hpp:216
int min(void) const
Return minimum of domain.
Definition: view.hpp:315
int counter(void) const
Return the number of times the value occurs.
Definition: view.hpp:307
Gecode toplevel namespace
ModEvent inc(void)
Increment counter.
Definition: view.hpp:332
ModEvent minus_v(Space &home, I &i, bool depends=true)
Remove from domain the values described by i.
Definition: view.hpp:362
#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
struct Gecode::@518::NNF::@57::@59 a
For atomic nodes.