Generated on Mon Aug 27 2012 17:15:41 for Gecode by doxygen 1.8.1.2
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 18:39:13 +1000 (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 
85  CardConst(void);
87  void init(Space& home, int min, int max, int c);
89 
91 
92 
93  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 
154  CardView(void);
156  void init(const IntView& y, int c);
158  void init(Space& home, const IntSet& s, int c);
160 
162 
163 
164  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 
192  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  }
255  CardConst::lq(Space&, int n) {
256  if (_min > n)
257  return ME_INT_FAILED;
258  return ME_INT_NONE;
259  }
261  CardConst::gq(Space&, int n) {
262  if (_max < n)
263  return ME_INT_FAILED;
264  return ME_INT_NONE;
265  }
267  CardConst::eq(Space&, int n) {
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