this repo has no description
dekker.one
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
40namespace Gecode { namespace Int { namespace GCC {
41
42 /// Return index of \a v in array \a a
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
64 /// Constant view containing lower and upper cardinality bounds
65 class CardConst {
66 private:
67 /// Lower bound
68 int _min;
69 /// Upper bound
70 int _max;
71 /// Cardinality information
72 int _card;
73 /// Counting information
74 int _counter;
75 public:
76 /// This view does not require propagation
77 static const bool propagate = false;
78
79 /// \name Initialization
80 //@{
81 /// Default constructor
82 CardConst(void);
83 /// Initialize with \a min, \a max, and cardinality \a c
84 void init(Space& home, int min, int max, int c);
85 //@}
86
87 /// \name Value access
88 //@{
89 /// Return minimum of domain
90 int min(void) const;
91 /// Return maximum of domain
92 int max(void) const;
93 /// Return cardinality
94 int card(void) const;
95 /// Return the number of times the value occurs
96 int counter(void) const;
97 //@}
98
99 /// \name Domain tests
100 ///@{
101 /// Test whether view is assigned
102 bool assigned(void) const;
103 ///@}
104
105 /// \name Domain update by value
106 ///@{
107 /// Set counter to \a n
108 void counter(int n);
109 /// Increment counter
110 ModEvent inc(void);
111 /// Restrict domain values to be less or equal than \a n
112 ModEvent lq(Space& home, int n);
113 /// Restrict domain values to be greater or equal than \a n
114 ModEvent gq(Space& home, int n);
115 /// Restrict domain values to be equal to \a n
116 ModEvent eq(Space& home, int n);
117 ///@}
118
119 /// \name Dependencies
120 ///@{
121 /// Subscribe propagator \a p with propagation condition \a pc to view
122 void subscribe(Space& home, Propagator& p, PropCond pc, bool process=true);
123 /// Cancel subscription of propagator \a p with propagation condition \a pc to view
124 void cancel(Space& home, Propagator& p, PropCond pc);
125 /// Schedule propagator \a p
126 void reschedule(Space& home, Propagator& p, PropCond pc);
127 ///@}
128
129 /// \name Cloning
130 ///@{
131 /// Update this view to be a clone of view \a x
132 void update(Space& home, CardConst& x);
133 ///@}
134
135 /// Return used IntView (cannot be used)
136 IntView base(void) const;
137 };
138
139 /// Cardinality integer view
140 class CardView : public DerivedView<IntView> {
141 protected:
142 using DerivedView<IntView>::x;
143 /// Cardinality
144 int _card;
145 /// Counter
146 int _counter;
147 public:
148 /// This view does require propagation
149 static const bool propagate = true;
150 /// \name Initialization
151 //@{
152 /// Default constructor
153 CardView(void);
154 /// Initialize with integer view \a y and value \a c
155 void init(const IntView& y, int c);
156 /// Initialize for set \a s and cardinality \a c
157 void init(Space& home, const IntSet& s, int c);
158 //@}
159
160 /// \name Value access
161 //@{
162 /// Return minimum of domain
163 int min(void) const;
164 /// Return maximum of domain
165 int max(void) const;
166 /// Return size (cardinality) of domain
167 unsigned int size(void) const;
168 /// Return the number of times the value occurs
169 int counter(void) const;
170 /// Return cardinality
171 int card(void) const;
172 ///@}
173
174 /// \name Domain update by value
175 ///@{
176 /// Set the counter to the number of times value \a n occurs
177 void counter(int n);
178 /// Increment counter
179 ModEvent inc(void);
180 /// Restrict domain values to be less or equal than \a n
181 ModEvent lq(Space& home, int n);
182 /// Restrict domain values to be greater or equal than \a n
183 ModEvent gq(Space& home, int n);
184 /// Restrict domain values to be equal to \a n
185 ModEvent eq(Space& home, int n);
186 ///@}
187
188 /// \name Domain update by iterator
189 //@{
190 /// Replace domain by values described by \a i
191 template<class I>
192 ModEvent narrow_v(Space& home, I& i, bool depends=true);
193 /// Intersect domain with values described by \a i
194 template<class I>
195 ModEvent inter_v(Space& home, I& i, bool depends=true);
196 /// Remove from domain the values described by \a i
197 template<class I>
198 ModEvent minus_v(Space& home, I& i, bool depends=true);
199 //@}
200
201 /// \name Cloning
202 ///@{
203 /// Update this view to be a clone of view \a x
204 void update(Space& home, CardView& x);
205 ///@}
206 };
207
208
209
210 /*
211 * Constant cardinality view
212 *
213 */
214 forceinline
215 CardConst::CardConst(void) {}
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
244 CardConst::counter(int n) {
245 _counter = n;
246 }
247 forceinline ModEvent
248 CardConst::inc(void) {
249 if (++_counter > _max)
250 return ME_INT_FAILED;
251 return ME_INT_NONE;
252 }
253 forceinline ModEvent
254 CardConst::lq(Space&, int n) {
255 if (_min > n)
256 return ME_INT_FAILED;
257 return ME_INT_NONE;
258 }
259 forceinline ModEvent
260 CardConst::gq(Space&, int n) {
261 if (_max < n)
262 return ME_INT_FAILED;
263 return ME_INT_NONE;
264 }
265 forceinline ModEvent
266 CardConst::eq(Space&, int n) {
267 if ((_min > n) || (_max < n))
268 return ME_INT_FAILED;
269 return ME_INT_NONE;
270 }
271
272 forceinline void
273 CardConst::subscribe(Space&, Propagator&, PropCond, bool) {}
274 forceinline void
275 CardConst::cancel(Space&, Propagator&, PropCond) {}
276 forceinline void
277 CardConst::reschedule(Space&, Propagator&, PropCond) {}
278
279 forceinline void
280 CardConst::update(Space&, CardConst& x) {
281 _min=x._min; _max=x._max; _card=x._card; _counter=x._counter;
282 }
283
284 forceinline IntView
285 CardConst::base(void) const {
286 GECODE_NEVER;
287 return IntView();
288 }
289
290
291
292 /*
293 * Cardinality integer view
294 *
295 */
296 forceinline
297 CardView::CardView(void) {}
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
329 CardView::counter(int n) {
330 _counter = n;
331 }
332 forceinline ModEvent
333 CardView::inc(void) {
334 if (++_counter > this->max())
335 return ME_INT_FAILED;
336 return ME_GEN_NONE;
337 }
338 forceinline ModEvent
339 CardView::lq(Space& home, int n) {
340 return x.lq(home,n);
341 }
342 forceinline ModEvent
343 CardView::gq(Space& home, int n) {
344 return x.gq(home,n);
345 }
346 forceinline ModEvent
347 CardView::eq(Space& home, int n) {
348 return x.eq(home,n);
349 }
350
351 template<class I>
352 forceinline ModEvent
353 CardView::narrow_v(Space& home, I& i, bool depends) {
354 return x.narrow_v(home,i,depends);
355 }
356 template<class I>
357 forceinline ModEvent
358 CardView::inter_v(Space& home, I& i, bool depends) {
359 return x.inter_v(home,i,depends);
360 }
361 template<class I>
362 forceinline ModEvent
363 CardView::minus_v(Space& home, I& i, bool depends) {
364 return x.minus_v(home,i,depends);
365 }
366
367 forceinline void
368 CardView::update(Space& home, CardView& y) {
369 x.update(home,y.x);
370 _card = y._card; _counter = y._counter;
371 }
372
373}
374
375
376 /**
377 * \brief %Range iterator for indexed problem variables
378 */
379 template<>
380 class ViewRanges<GCC::CardView>
381 : public Gecode::Int::ViewRanges<IntView> {
382 public:
383 /// \name Constructors and initialization
384 ///@{
385 /// Default constructor
386 ViewRanges(void);
387 /// Initialize with ranges for view \a x
388 ViewRanges(const GCC::CardView& x);
389 /// Initialize with ranges for view \a x
390 void init(const GCC::CardView& x);
391 ///@}
392 };
393
394 forceinline
395 ViewRanges<GCC::CardView>::ViewRanges(void) :
396 Gecode::Int::ViewRanges<IntView>() {}
397
398 forceinline
399 ViewRanges<GCC::CardView>::ViewRanges (const GCC::CardView& x)
400 : Gecode::Int::ViewRanges<IntView>(x.base()) {}
401
402 forceinline void
403 ViewRanges<GCC::CardView>::init(const GCC::CardView& x) {
404 Gecode::Int::ViewRanges<IntView> xi(x.base());
405 }
406
407}}
408
409
410
411// STATISTICS: int-prop