this repo has no description
dekker.one
1/* -*- mode: C++; c-basic-offset: 2; indent-tabs-mode: nil -*- */
2/*
3 * Main authors:
4 * Christian Schulte <schulte@gecode.org>
5 * Guido Tack <tack@gecode.org>
6 *
7 * Copyright:
8 * Christian Schulte, 2002
9 * Guido Tack, 2004
10 *
11 * This file is part of Gecode, the generic constraint
12 * development environment:
13 * http://www.gecode.org
14 *
15 * Permission is hereby granted, free of charge, to any person obtaining
16 * a copy of this software and associated documentation files (the
17 * "Software"), to deal in the Software without restriction, including
18 * without limitation the rights to use, copy, modify, merge, publish,
19 * distribute, sublicense, and/or sell copies of the Software, and to
20 * permit persons to whom the Software is furnished to do so, subject to
21 * the following conditions:
22 *
23 * The above copyright notice and this permission notice shall be
24 * included in all copies or substantial portions of the Software.
25 *
26 * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,
27 * EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF
28 * MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND
29 * NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE
30 * LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION
31 * OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION
32 * WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
33 *
34 */
35
36#ifndef GECODE_INT_COUNT_HH
37#define GECODE_INT_COUNT_HH
38
39#include <gecode/int.hh>
40
41/**
42 * \namespace Gecode::Int::Count
43 * \brief Counting propagators
44 */
45
46namespace Gecode { namespace Int { namespace Count {
47
48 /**
49 * Relations for domain consistent counting
50 *
51 */
52 //@{
53 /// Return whether \a y is an integer set
54 template<class VY>
55 bool isintset(VY y);
56 /// Return whether \a y is a value
57 template<class VY>
58 bool isval(VY y);
59
60 /// Subscribe propagator \a p to view \a y
61 template<class VY>
62 void subscribe(Space& home, Propagator& p, VY y);
63 /// Cancel propagator \a p for view \a y
64 template<class VY>
65 void cancel(Space& home, Propagator& p, VY y);
66 /// Schedule propagator \a p for view \a y
67 template<class VY>
68 void reschedule(Space& home, Propagator& p, VY y);
69 /// Update view \a y from \a py
70 template<class VY>
71 void update(VY& y, Space& home, bool shared, VY py);
72
73 /// Test whether \a x and \a y are equal
74 template<class VX>
75 RelTest holds(VX x, VX y);
76 /// Test whether \a x and \a y are equal
77 template<class VX>
78 RelTest holds(VX x, ConstIntView y);
79 /// Test whether \a x and \a y are equal
80 template<class VX>
81 RelTest holds(VX x, ZeroIntView y);
82 /// Test whether \a x and \a y are equal
83 template<class VX>
84 RelTest holds(VX x, const IntSet& y);
85
86 /// Post that all views in \a x are equal to \a y
87 template<class VX>
88 ExecStatus post_true(Home home, ViewArray<VX>& x, VX y);
89 /// Post that all views in \a x are equal to \a y
90 template<class VX>
91 ExecStatus post_true(Home home, ViewArray<VX>& x, ConstIntView y);
92 /// Post that all views in \a x are equal to \a y
93 template<class VX>
94 ExecStatus post_true(Home home, ViewArray<VX>& x, ZeroIntView y);
95 /// Post that all views in \a x are equal to \a y
96 template<class VX>
97 ExecStatus post_true(Home home, ViewArray<VX>& x, const IntSet& y);
98
99 /// Post that all views in \a x are not equal to \a y
100 template<class VX>
101 ExecStatus post_false(Home home, ViewArray<VX>& x, VX y);
102 /// Post that all views in \a x are not equal to \a y
103 template<class VX>
104 ExecStatus post_false(Home home, ViewArray<VX>& x, ConstIntView y);
105 /// Post that all views in \a x are not equal to \a y
106 template<class VX>
107 ExecStatus post_false(Home home, ViewArray<VX>& x, ZeroIntView y);
108 /// Post that all views in \a x are not equal to \a y
109 template<class VX>
110 ExecStatus post_false(Home home, ViewArray<VX>& x, const IntSet& y);
111
112 /// Prune that \a y is the union of \a x
113 template<class VX>
114 ExecStatus prune(Home home, ViewArray<VX>& x, VX y);
115 /// Prune that \a y is the union of \a x
116 template<class VX>
117 ExecStatus prune(Home home, ViewArray<VX>& x, ConstIntView y);
118 /// Prune that \a y is the union of \a x
119 template<class VX>
120 ExecStatus prune(Home home, ViewArray<VX>& x, ZeroIntView y);
121 /// Prune that \a y is the union of \a x
122 template<class VX>
123 ExecStatus prune(Home home, ViewArray<VX>& x, const IntSet& y);
124 //@}
125
126}}}
127
128#include <gecode/int/count/rel.hpp>
129
130
131namespace Gecode { namespace Int { namespace Count {
132
133 /**
134 * \brief Baseclass for count propagators (integer)
135 *
136 */
137 template<class VX, class VY>
138 class IntBase : public Propagator {
139 protected:
140 /// Views still to count
141 ViewArray<VX> x;
142 /// Views from x[0] ... x[n_s-1] have subscriptions
143 int n_s;
144 /// View to compare to
145 VY y;
146 /// Number of views which are equal and have been eliminated
147 int c;
148 /// Constructor for cloning \a p
149 IntBase(Space& home, IntBase& p);
150 /// Constructor for creation
151 IntBase(Home home, ViewArray<VX>& x, int n_s, VY y, int c);
152 public:
153 /// Cost function (defined as low linear)
154 virtual PropCost cost(const Space& home, const ModEventDelta& med) const;
155 /// Schedule function
156 virtual void reschedule(Space& home);
157 /// Delete propagator and return its size
158 virtual size_t dispose(Space& home);
159 };
160
161 /**
162 * \brief %Propagator for counting views (equal integer to number of equal views)
163 *
164 * Not all combinations of views are possible. The types \a VX
165 * and \a VY must be either equal, or \a VY must be ConstIntView,
166 * ZeroIntView, or IntSet.
167 *
168 * Requires \code #include <gecode/int/count.hh> \endcode
169 * \ingroup FuncIntProp
170 */
171 template<class VX, class VY>
172 class EqInt : public IntBase<VX,VY> {
173 protected:
174 using IntBase<VX,VY>::x;
175 using IntBase<VX,VY>::n_s;
176 using IntBase<VX,VY>::y;
177 using IntBase<VX,VY>::c;
178 /// Constructor for cloning \a p
179 EqInt(Space& home, EqInt& p);
180 /// Constructor for creation
181 EqInt(Home home, ViewArray<VX>& x, int n_s, VY y, int c);
182 public:
183 /// Create copy during cloning
184 virtual Actor* copy(Space& home);
185 /// Perform propagation
186 virtual ExecStatus propagate(Space& home, const ModEventDelta& med);
187 /// Post propagator for \f$\#\{i\in\{0,\ldots,|x|-1\}\;|\;x_i=y\}=c\f$
188 static ExecStatus post(Home home, ViewArray<VX>& x, VY y, int c);
189 };
190
191 /**
192 * \brief %Propagator for counting views (greater or equal integer to number of equal views)
193 *
194 * Not all combinations of views are possible. The types \a VX
195 * and \a VY must be either equal, or \a VY must be ConstIntView,
196 * ZeroIntView, or IntSet.
197 *
198 * Requires \code #include <gecode/int/count.hh> \endcode
199 * \ingroup FuncIntProp
200 */
201 template<class VX, class VY>
202 class GqInt : public IntBase<VX,VY> {
203 protected:
204 using IntBase<VX,VY>::x;
205 using IntBase<VX,VY>::n_s;
206 using IntBase<VX,VY>::y;
207 using IntBase<VX,VY>::c;
208 /// Constructor for cloning \a p
209 GqInt(Space& home, GqInt& p);
210 /// Constructor for creation
211 GqInt(Home home, ViewArray<VX>& x, int n_s, VY y, int c);
212 public:
213 /// Create copy during cloning
214 virtual Actor* copy(Space& home);
215 /// Perform propagation
216 virtual ExecStatus propagate(Space& home, const ModEventDelta& med);
217 /// Post propagator for \f$\#\{i\in\{0,\ldots,|x|-1\}\;|\;x_i=y\}\geq c\f$
218 static ExecStatus post(Home home, ViewArray<VX>& x, VY y, int c);
219 };
220
221 /**
222 * \brief %Propagator for counting views (less or equal integer to number of equal views)
223 *
224 * Not all combinations of views are possible. The types \a VX
225 * and \a VY must be either equal, or \a VY must be ConstIntView,
226 * ZeroIntView, or IntSet.
227 *
228 * Requires \code #include <gecode/int/count.hh> \endcode
229 * \ingroup FuncIntProp
230 */
231 template<class VX, class VY>
232 class LqInt : public IntBase<VX,VY> {
233 protected:
234 using IntBase<VX,VY>::x;
235 using IntBase<VX,VY>::n_s;
236 using IntBase<VX,VY>::y;
237 using IntBase<VX,VY>::c;
238 /// Constructor for cloning \a p
239 LqInt(Space& home, LqInt& p);
240 /// Constructor for creation
241 LqInt(Home home, ViewArray<VX>& x, int n_s, VY y, int c);
242 public:
243 /// Create copy during cloning
244 virtual Actor* copy(Space& home);
245 /// Perform propagation
246 virtual ExecStatus propagate(Space& home, const ModEventDelta& med);
247 /// Post propagator for \f$\#\{i\in\{0,\ldots,|x|-1\}\;|\;x_i=y\}\leq c\f$
248 static ExecStatus post(Home home, ViewArray<VX>& x, VY y, int c);
249 };
250
251}}}
252
253#include <gecode/int/count/int-base.hpp>
254#include <gecode/int/count/int-eq.hpp>
255#include <gecode/int/count/int-gq.hpp>
256#include <gecode/int/count/int-lq.hpp>
257
258
259namespace Gecode { namespace Int { namespace Count {
260
261 /**
262 * \brief Base-class for count propagators (view)
263 *
264 */
265 template<class VX, class VY, class VZ>
266 class ViewBase : public Propagator {
267 protected:
268 /// Views still to count
269 ViewArray<VX> x;
270 /// View to compare to
271 VY y;
272 /// View which yields result of counting
273 VZ z;
274 /// Number of views which are equal and have been eliminated
275 int c;
276 /// Constructor for cloning \a p
277 ViewBase(Space& home, ViewBase& p);
278 /// Constructor for creation
279 ViewBase(Home home, ViewArray<VX>& x, VY y, VZ z, int c);
280 public:
281 /// Delete propagator and return its size
282 virtual size_t dispose(Space& home);
283 /// Cost function (defined as low linear)
284 virtual PropCost cost(const Space& home, const ModEventDelta& med) const;
285 /// Schedule function
286 virtual void reschedule(Space& home);
287 protected:
288 /// Count how many views are equal now
289 void count(Space& home);
290 /// How many views are at least equal
291 int atleast(void) const;
292 /// How many views are at most equal
293 int atmost(void) const;
294 /// Test whether there is sharing of \a z with \a x or \a y
295 static bool sharing(const ViewArray<VX>& x, const VY& y, const VZ& z);
296 };
297
298 /**
299 * \brief %Propagator for counting views (equal to number of equal views)
300 *
301 * Not all combinations of views are possible. The types \a VX
302 * and \a VY must be either equal, or \a VY must be ConstIntView,
303 * ZeroIntView, or IntSet.
304 *
305 * Requires \code #include <gecode/int/count.hh> \endcode
306 * \ingroup FuncIntProp
307 */
308 template<class VX, class VY, class VZ, bool shr, bool dom>
309 class EqView : public ViewBase<VX,VY,VZ> {
310 protected:
311 using ViewBase<VX,VY,VZ>::x;
312 using ViewBase<VX,VY,VZ>::z;
313 using ViewBase<VX,VY,VZ>::c;
314 using ViewBase<VX,VY,VZ>::y;
315 using ViewBase<VX,VY,VZ>::count;
316 using ViewBase<VX,VY,VZ>::atleast;
317 using ViewBase<VX,VY,VZ>::atmost;
318 using ViewBase<VX,VY,VZ>::sharing;
319
320 /// Constructor for cloning \a p
321 EqView(Space& home, EqView& p);
322 public:
323 /// Constructor for creation
324 EqView(Home home, ViewArray<VX>& x, VY y, VZ z, int c);
325 /// Create copy during cloning
326 virtual Actor* copy(Space& home);
327 /// Perform propagation
328 virtual ExecStatus propagate(Space& home, const ModEventDelta& med);
329 /// Post propagator for \f$\#\{i\in\{0,\ldots,|x|-1\}\;|\;x_i=y\}=z+c\f$
330 static ExecStatus post(Home home, ViewArray<VX>& x, VY y, VZ z, int c);
331 };
332
333 /**
334 * \brief %Propagator for counting views (less or equal to number of equal views)
335 *
336 * Not all combinations of views are possible. The types \a VX
337 * and \a VY must be either equal, or \a VY must be ConstIntView,
338 * ZeroIntView, or IntSet.
339 *
340 * Requires \code #include <gecode/int/count.hh> \endcode
341 * \ingroup FuncIntProp
342 */
343 template<class VX, class VY, class VZ, bool shr>
344 class LqView : public ViewBase<VX,VY,VZ> {
345 protected:
346 using ViewBase<VX,VY,VZ>::x;
347 using ViewBase<VX,VY,VZ>::z;
348 using ViewBase<VX,VY,VZ>::c;
349 using ViewBase<VX,VY,VZ>::y;
350 using ViewBase<VX,VY,VZ>::count;
351 using ViewBase<VX,VY,VZ>::atleast;
352 using ViewBase<VX,VY,VZ>::atmost;
353 using ViewBase<VX,VY,VZ>::sharing;
354
355 /// Constructor for cloning \a p
356 LqView(Space& home, LqView& p);
357 public:
358 /// Constructor for creation
359 LqView(Home home, ViewArray<VX>& x, VY y, VZ z, int c);
360 /// Create copy during cloning
361 virtual Actor* copy(Space& home);
362 /// Perform propagation
363 virtual ExecStatus propagate(Space& home, const ModEventDelta& med);
364 /// Post propagator for \f$\#\{i\in\{0,\ldots,|x|-1\}\;|\;x_i=y\}\leq z+c\f$
365 static ExecStatus post(Home home, ViewArray<VX>& x, VY y, VZ z, int c);
366 };
367
368 /**
369 * \brief %Propagator for counting views (greater or equal to number of equal views)
370 *
371 * Not all combinations of views are possible. The types \a VX
372 * and \a VY must be either equal, or \a VY must be ConstIntView,
373 * ZeroIntView, or IntSet.
374 *
375 * Requires \code #include <gecode/int/count.hh> \endcode
376 * \ingroup FuncIntProp
377 */
378 template<class VX, class VY, class VZ, bool shr, bool dom>
379 class GqView : public ViewBase<VX,VY,VZ> {
380 protected:
381 using ViewBase<VX,VY,VZ>::x;
382 using ViewBase<VX,VY,VZ>::z;
383 using ViewBase<VX,VY,VZ>::c;
384 using ViewBase<VX,VY,VZ>::y;
385 using ViewBase<VX,VY,VZ>::count;
386 using ViewBase<VX,VY,VZ>::atleast;
387 using ViewBase<VX,VY,VZ>::atmost;
388 using ViewBase<VX,VY,VZ>::sharing;
389
390 /// Constructor for cloning \a p
391 GqView(Space& home, GqView& p);
392 public:
393 /// Constructor for creation
394 GqView(Home home, ViewArray<VX>& x, VY y, VZ z, int c);
395 /// Create copy during cloning
396 virtual Actor* copy(Space& home);
397 /// Perform propagation
398 virtual ExecStatus propagate(Space& home, const ModEventDelta& med);
399 /// Post propagator for \f$\#\{i\in\{0,\ldots,|x|-1\}\;|\;x_i=y\}\geq z+c\f$
400 static ExecStatus post(Home home, ViewArray<VX>& x, VY y, VZ z, int c);
401 };
402
403}}}
404
405#include <gecode/int/count/view-base.hpp>
406#include <gecode/int/count/view-eq.hpp>
407#include <gecode/int/count/view-gq.hpp>
408#include <gecode/int/count/view-lq.hpp>
409
410#endif
411
412// STATISTICS: int-prop
413