Generated on Mon Feb 8 2021 00:00:00 for Gecode by doxygen 1.8.20
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  * This file is part of Gecode, the generic constrain
16  * development environment:
17  * http://www.gecode.org
18  *
19  *
20  * Permission is hereby granted, free of charge, to any person obtaining
21  * a copy of this software and associated documentation files (the
22  * "Software"), to deal in the Software without restriction, including
23  * without limitation the rights to use, copy, modify, merge, publish,
24  * distribute, sublicense, and/or sell copies of the Software, and to
25  * permit persons to whom the Software is furnished to do so, subject to
26  * the following conditions:
27  *
28  * The above copyright notice and this permission notice shall be
29  * included in all copies or substantial portions of the Software.
30  *
31  * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,
32  * EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF
33  * MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND
34  * NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE
35  * LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION
36  * OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION
37  * WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
38  */
39 
40 namespace Gecode { namespace Int { namespace GCC {
41 
43  template<class T>
44  forceinline bool
45  lookupValue(T& a, int v, int& i) {
46  int l = 0;
47  int r = a.size() - 1;
48 
49  while (l <= r) {
50  int m = l + (r - l) / 2;
51  if (v == a[m].card()) {
52  i=m; return true;
53  } else if (l == r) {
54  return false;
55  } else if (v < a[m].card()) {
56  r=m-1;
57  } else {
58  l=m+1;
59  }
60  }
61  return false;
62  }
63 
65  class CardConst {
66  private:
68  int _min;
70  int _max;
72  int _card;
74  int _counter;
75  public:
77  static const bool propagate = false;
78 
80 
81  CardConst(void);
84  void init(Space& home, int min, int max, int c);
86 
88 
89  int min(void) const;
92  int max(void) const;
94  int card(void) const;
96  int counter(void) const;
98 
102  bool assigned(void) const;
104 
108  void counter(int n);
110  ModEvent inc(void);
112  ModEvent lq(Space& home, int n);
114  ModEvent gq(Space& home, int n);
116  ModEvent eq(Space& home, int n);
118 
122  void subscribe(Space& home, Propagator& p, PropCond pc, bool process=true);
124  void cancel(Space& home, Propagator& p, PropCond pc);
126  void reschedule(Space& home, Propagator& p, PropCond pc);
128 
132  void update(Space& home, CardConst& x);
134 
136  IntView base(void) const;
137  };
138 
140  class CardView : public DerivedView<IntView> {
141  protected:
144  int _card;
146  int _counter;
147  public:
149  static const bool propagate = true;
151 
152  CardView(void);
155  void init(const IntView& y, int c);
157  void init(Space& home, const IntSet& s, int c);
159 
161 
162  int min(void) const;
165  int max(void) const;
167  unsigned int size(void) const;
169  int counter(void) const;
171  int card(void) const;
173 
177  void counter(int n);
179  ModEvent inc(void);
181  ModEvent lq(Space& home, int n);
183  ModEvent gq(Space& home, int n);
185  ModEvent eq(Space& home, int n);
187 
189 
190  template<class I>
192  ModEvent narrow_v(Space& home, I& i, bool depends=true);
194  template<class I>
195  ModEvent inter_v(Space& home, I& i, bool depends=true);
197  template<class I>
198  ModEvent minus_v(Space& home, I& i, bool depends=true);
200 
204  void update(Space& home, CardView& x);
206  };
207 
208 
209 
210  /*
211  * Constant cardinality view
212  *
213  */
216  forceinline void
217  CardConst::init(Space&, int min, int max, int c) {
218  _min = min; _max=max; _card = c; _counter = 0;
219  }
220 
221  forceinline int
222  CardConst::min(void) const {
223  return _min;
224  }
225  forceinline int
226  CardConst::max(void) const {
227  return _max;
228  }
229  forceinline int
230  CardConst::card(void) const {
231  return _card;
232  }
233  forceinline int
234  CardConst::counter(void) const {
235  return _counter;
236  }
237  forceinline bool
238  CardConst::assigned(void) const {
239  return _min==_max;
240  }
241 
242 
243  forceinline void
245  _counter = n;
246  }
249  if (++_counter > _max)
250  return ME_INT_FAILED;
251  return ME_INT_NONE;
252  }
255  if (_min > n)
256  return ME_INT_FAILED;
257  return ME_INT_NONE;
258  }
261  if (_max < n)
262  return ME_INT_FAILED;
263  return ME_INT_NONE;
264  }
267  if ((_min > n) || (_max < n))
268  return ME_INT_FAILED;
269  return ME_INT_NONE;
270  }
271 
272  forceinline void
274  forceinline void
276  forceinline void
278 
279  forceinline void
281  _min=x._min; _max=x._max; _card=x._card; _counter=x._counter;
282  }
283 
285  CardConst::base(void) const {
286  GECODE_NEVER;
287  return IntView();
288  }
289 
290 
291 
292  /*
293  * Cardinality integer view
294  *
295  */
298  forceinline void
299  CardView::init(const IntView& y, int c) {
300  x = y; _card = c; _counter = 0;
301  }
302  forceinline void
303  CardView::init(Space& home, const IntSet& s, int c) {
304  x = IntVar(home,s); _card = c; _counter = 0;
305  }
306 
307  forceinline int
308  CardView::counter(void) const {
309  return _counter;
310  }
311  forceinline int
312  CardView::card(void) const {
313  return _card;
314  }
315  forceinline int
316  CardView::min(void) const {
317  return x.min();
318  }
319  forceinline int
320  CardView::max(void) const {
321  return x.max();
322  }
323  forceinline unsigned int
324  CardView::size(void) const {
325  return x.size();
326  }
327 
328  forceinline void
330  _counter = n;
331  }
334  if (++_counter > this->max())
335  return ME_INT_FAILED;
336  return ME_GEN_NONE;
337  }
339  CardView::lq(Space& home, int n) {
340  return x.lq(home,n);
341  }
343  CardView::gq(Space& home, int n) {
344  return x.gq(home,n);
345  }
347  CardView::eq(Space& home, int n) {
348  return x.eq(home,n);
349  }
350 
351  template<class I>
353  CardView::narrow_v(Space& home, I& i, bool depends) {
354  return x.narrow_v(home,i,depends);
355  }
356  template<class I>
358  CardView::inter_v(Space& home, I& i, bool depends) {
359  return x.inter_v(home,i,depends);
360  }
361  template<class I>
363  CardView::minus_v(Space& home, I& i, bool depends) {
364  return x.minus_v(home,i,depends);
365  }
366 
367  forceinline void
369  x.update(home,y.x);
370  _card = y._card; _counter = y._counter;
371  }
372 
373 }
374 
375 
379  template<>
380  class ViewRanges<GCC::CardView>
381  : public Gecode::Int::ViewRanges<IntView> {
382  public:
386  ViewRanges(void);
388  ViewRanges(const GCC::CardView& x);
390  void init(const GCC::CardView& x);
392  };
393 
396  Gecode::Int::ViewRanges<IntView>() {}
397 
400  : Gecode::Int::ViewRanges<IntView>(x.base()) {}
401 
402  forceinline void
405  }
406 
407 }}
408 
409 
410 
411 // STATISTICS: int-prop
Post propagator for SetVar x
Definition: set.hh:767
int card(void) const
Return cardinality.
Definition: view.hpp:312
Post propagator for SetVar SetOpType SetVar y
Definition: set.hh:767
void max(Home home, FloatVar x0, FloatVar x1, FloatVar x2)
Post propagator for .
Definition: arithmetic.cpp:49
Constant view containing lower and upper cardinality bounds.
Definition: view.hpp:65
void reschedule(Space &home, Propagator &p, PropCond pc)
Schedule propagator p.
Definition: view.hpp:277
const Gecode::ModEvent ME_INT_FAILED
Domain operation has resulted in failure.
Definition: var-type.hpp:52
void init(const View &x)
Initialize with ranges for view x.
ModEvent eq(Space &home, int n)
Restrict domain values to be equal to n.
Definition: view.hpp:266
int min(void) const
Return minimum of domain.
Definition: int.hpp:58
CardView(void)
Default constructor.
Definition: view.hpp:297
int card(void) const
Return cardinality.
Definition: view.hpp:230
void update(Space &home, CardConst &x)
Definition: view.hpp:280
void cancel(Space &home, Propagator &p, PropCond pc)
Cancel subscription of propagator p with propagation condition pc to view.
Definition: view.hpp:275
const Gecode::ModEvent ME_INT_NONE
Domain operation has not changed domain.
Definition: var-type.hpp:54
ModEvent minus_v(Space &home, I &i, bool depends=true)
Remove from domain the values described by i.
Definition: int.hpp:206
ModEvent gq(Space &home, int n)
Restrict domain values to be greater or equal than n.
Definition: view.hpp:260
Computation spaces.
Definition: core.hpp:1742
void update(Space &home, VarImpView< Var > &y)
Update this view to be a clone of view y.
Definition: view.hpp:567
ModEvent inter_v(Space &home, I &i, bool depends=true)
Intersect domain with values described by i.
Definition: view.hpp:358
bool lookupValue(T &a, int v, int &i)
Return index of v in array a.
Definition: view.hpp:45
ModEvent lq(Space &home, int n)
Restrict domain values to be less or equal than n.
Definition: view.hpp:254
ModEvent lq(Space &home, int n)
Restrict domain values to be less or equal than n.
Definition: view.hpp:339
static const bool propagate
This view does not require propagation.
Definition: view.hpp:77
Base-class for derived views.
Definition: view.hpp:230
int _card
Cardinality.
Definition: view.hpp:144
Gecode toplevel namespace
int max(void) const
Return maximum of domain.
Definition: int.hpp:62
Base-class for propagators.
Definition: core.hpp:1064
VarImp * x
Pointer to variable implementation.
Definition: var.hpp:50
bool assigned(void) const
Definition: view.hpp:238
Range iterator for integer views.
Definition: view.hpp:54
Integer sets.
Definition: int.hh:174
const unsigned int card
Maximum cardinality of an integer set.
Definition: set.hh:101
unsigned int size(void) const
Return size (cardinality) of domain.
Definition: int.hpp:81
IntView base(void) const
Return used IntView (cannot be used)
Definition: view.hpp:285
int _counter
Counter.
Definition: view.hpp:146
void init(Space &home, int min, int max, int c)
Initialize with min, max, and cardinality c.
Definition: view.hpp:217
ModEvent inter_v(Space &home, I &i, bool depends=true)
Intersect domain with values described by i.
Definition: int.hpp:201
unsigned int size(void) const
Return size (cardinality) of domain.
Definition: view.hpp:324
const ModEvent ME_GEN_NONE
Generic modification event: no modification.
Definition: core.hpp:67
ModEvent gq(Space &home, int n)
Restrict domain values to be greater or equal than n.
Definition: view.hpp:343
int max(void) const
Return maximum of domain.
Definition: view.hpp:226
Post propagator for SetVar SetOpType SetVar SetRelType r
Definition: set.hh:767
void init(const IntView &y, int c)
Initialize with integer view y and value c.
Definition: view.hpp:299
ViewRanges(void)
Default constructor.
int counter(void) const
Return the number of times the value occurs.
Definition: view.hpp:308
const double base
Base for geometric restart sequence.
Definition: search.hh:126
Integer variables.
Definition: int.hh:371
#define GECODE_NEVER
Assert that this command is never executed.
Definition: macros.hpp:56
ModEvent eq(Space &home, int n)
Restrict domain values to be equal to n.
Definition: view.hpp:347
struct Gecode::@602::NNF::@65::@67 a
For atomic nodes.
int ModEvent
Type for modification events.
Definition: core.hpp:62
int min(void) const
Return minimum of domain.
Definition: view.hpp:316
int PropCond
Type for propagation conditions.
Definition: core.hpp:72
IntView x
View from which this view is derived.
Definition: view.hpp:238
const int v[7]
Definition: distinct.cpp:259
NNF * l
Left subtree.
Definition: bool-expr.cpp:240
Integer view for integer variables.
Definition: view.hpp:129
ModEvent inc(void)
Increment counter.
Definition: view.hpp:333
Range iterator for integer variable views
Definition: int.hpp:246
int counter(void) const
Return the number of times the value occurs.
Definition: view.hpp:234
#define forceinline
Definition: config.hpp:192
int min(void) const
Return minimum of domain.
Definition: view.hpp:222
static const bool propagate
This view does require propagation.
Definition: view.hpp:149
void min(Home home, FloatVar x0, FloatVar x1, FloatVar x2)
Post propagator for .
Definition: arithmetic.cpp:67
ModEvent lq(Space &home, int n)
Restrict domain values to be less or equal than n.
Definition: int.hpp:121
ModEvent narrow_v(Space &home, I &i, bool depends=true)
Replace domain by values described by i.
Definition: view.hpp:353
Gecode::FloatVal c(-8, 8)
ModEvent narrow_v(Space &home, I &i, bool depends=true)
Replace domain by values described by i.
Definition: int.hpp:196
ModEvent gq(Space &home, int n)
Restrict domain values to be greater or equal than n.
Definition: int.hpp:139
CardConst(void)
Default constructor.
Definition: view.hpp:215
void update(Space &home, CardView &x)
Definition: view.hpp:368
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:273
int n
Number of negative literals for node type.
Definition: bool-expr.cpp:234
ModEvent minus_v(Space &home, I &i, bool depends=true)
Remove from domain the values described by i.
Definition: view.hpp:363
Cardinality integer view.
Definition: view.hpp:140
Gecode::IntArgs i({1, 2, 3, 4})
int p
Number of positive literals for node type.
Definition: bool-expr.cpp:232
ModEvent inc(void)
Increment counter.
Definition: view.hpp:248
ModEvent eq(Space &home, int n)
Restrict domain values to be equal to n.
Definition: int.hpp:166
int max(void) const
Return maximum of domain.
Definition: view.hpp:320