this repo has no description
dekker.one
1/* -*- mode: C++; c-basic-offset: 2; indent-tabs-mode: nil -*- */
2/*
3 * Main authors:
4 * Guido Tack <tack@gecode.org>
5 * Christian Schulte <schulte@gecode.org>
6 *
7 * Contributing authors:
8 * Gabor Szokoli <szokoli@gecode.org>
9 *
10 * Copyright:
11 * Guido Tack, 2004
12 * Christian Schulte, 2004
13 * Gabor Szokoli, 2004
14 *
15 * This file is part of Gecode, the generic constraint
16 * development environment:
17 * http://www.gecode.org
18 *
19 * Permission is hereby granted, free of charge, to any person obtaining
20 * a copy of this software and associated documentation files (the
21 * "Software"), to deal in the Software without restriction, including
22 * without limitation the rights to use, copy, modify, merge, publish,
23 * distribute, sublicense, and/or sell copies of the Software, and to
24 * permit persons to whom the Software is furnished to do so, subject to
25 * the following conditions:
26 *
27 * The above copyright notice and this permission notice shall be
28 * included in all copies or substantial portions of the Software.
29 *
30 * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,
31 * EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF
32 * MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND
33 * NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE
34 * LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION
35 * OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION
36 * WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
37 *
38 */
39
40#ifndef GECODE_SET_REL_HH
41#define GECODE_SET_REL_HH
42
43#include <gecode/set.hh>
44
45namespace Gecode { namespace Set { namespace Rel {
46
47 /**
48 * \namespace Gecode::Set::Rel
49 * \brief Standard set relation propagators
50 */
51
52 /// Test whether two views are in fact the same
53 template<class VX, class VY>
54 bool same(VX c, VY y);
55
56 /**
57 * \brief %Propagator for the subset constraint
58 *
59 * Requires \code #include <gecode/set/rel.hh> \endcode
60 * \ingroup FuncSetProp
61 */
62
63 template<class View0, class View1>
64 class Subset :
65 public MixBinaryPropagator<View0,PC_SET_CGLB,View1,PC_SET_CLUB> {
66 protected:
67 using MixBinaryPropagator<View0,PC_SET_CGLB,View1,PC_SET_CLUB>::x0;
68 using MixBinaryPropagator<View0,PC_SET_CGLB,View1,PC_SET_CLUB>::x1;
69 /// Constructor for cloning \a p
70 Subset(Space& home, Subset& p);
71 /// Constructor for posting
72 Subset(Home home, View0 x0, View1 x1);
73 public:
74 /// Copy propagator during cloning
75 virtual Actor* copy(Space& home);
76 /// Perform propagation
77 virtual ExecStatus propagate(Space& home, const ModEventDelta& med);
78 /// Post propagator \f$ x\subseteq y\f$
79 static ExecStatus post(Home home, View0 x, View1 y);
80 };
81
82 /**
83 * \brief %Propagator for the negated subset constraint
84 *
85 * Requires \code #include <gecode/set/rel.hh> \endcode
86 * \ingroup FuncSetProp
87 */
88
89 template<class View0, class View1>
90 class NoSubset :
91 public MixBinaryPropagator<View0,PC_SET_CLUB,View1,PC_SET_CGLB> {
92 protected:
93 using MixBinaryPropagator<View0,PC_SET_CLUB,View1,PC_SET_CGLB>::x0;
94 using MixBinaryPropagator<View0,PC_SET_CLUB,View1,PC_SET_CGLB>::x1;
95 /// Constructor for cloning \a p
96 NoSubset(Space& home, NoSubset& p);
97 /// Constructor for posting
98 NoSubset(Home home, View0 x0, View1 x1);
99 public:
100 /// Copy propagator during cloning
101 virtual Actor* copy(Space& home);
102 /// Perform propagation
103 virtual ExecStatus propagate(Space& home, const ModEventDelta& med);
104 /// Post propagator \f$ x\subseteq y\f$
105 static ExecStatus post(Home home,View0 x,View1 y);
106 };
107
108 /**
109 * \brief %Reified subset propagator
110 *
111 * Requires \code #include <gecode/set/rel.hh> \endcode
112 * \ingroup FuncSetProp
113 */
114 template<class View0, class View1, class CtrlView, ReifyMode rm>
115 class ReSubset : public Propagator {
116 protected:
117 /// Variable view
118 View0 x0;
119 /// Variable view
120 View1 x1;
121 /// Boolean control view
122 CtrlView b;
123 /// Constructor for cloning \a p
124 ReSubset(Space& home, ReSubset& p);
125 /// Constructor for posting
126 ReSubset(Home home, View0 x0, View1 x1, CtrlView b);
127 public:
128 /// Copy propagator during cloning
129 virtual Actor* copy(Space& home);
130 /// Cost function (defined as ternary low)
131 virtual PropCost cost(const Space& home, const ModEventDelta& med) const;
132 /// Schedule function
133 virtual void reschedule(Space& home);
134 /// Delete propagator and return its size
135 virtual size_t dispose(Space& home);
136 /// Perform propagation
137 virtual ExecStatus propagate(Space& home, const ModEventDelta& med);
138 /// Post propagator for \f$ (x\subseteq y) \Leftrightarrow b \f$
139 static ExecStatus post(Home home, View0 x, View1 y,
140 CtrlView b);
141 };
142
143 /**
144 * \brief %Propagator for set equality
145 *
146 * Requires \code #include <gecode/set/rel.hh> \endcode
147 * \ingroup FuncSetProp
148 */
149 template<class View0, class View1>
150 class Eq : public MixBinaryPropagator<View0,PC_SET_ANY,View1,PC_SET_ANY> {
151 protected:
152 using MixBinaryPropagator<View0,PC_SET_ANY,View1,PC_SET_ANY>::x0;
153 using MixBinaryPropagator<View0,PC_SET_ANY,View1,PC_SET_ANY>::x1;
154 /// Constructor for cloning \a p
155 Eq(Space& home, Eq& p);
156 /// Constructor for posting
157 Eq(Home home, View0 x0, View1 x1);
158 public:
159 /// Copy propagator during cloning
160 virtual Actor* copy(Space& home);
161 /// Perform propagation
162 virtual ExecStatus propagate(Space& home, const ModEventDelta& med);
163 /// Post propagator \f$ x=y \f$
164 static ExecStatus post(Home home, View0 x, View1 y);
165 };
166
167 /**
168 * \brief %Reified equality propagator
169 *
170 * Requires \code #include <gecode/set/rel.hh> \endcode
171 * \ingroup FuncSetProp
172 */
173 template<class View0, class View1, class CtrlView, ReifyMode rm>
174 class ReEq : public Propagator {
175 protected:
176 View0 x0;
177 View1 x1;
178 CtrlView b;
179 /// Constructor for cloning \a p
180 ReEq(Space& home, ReEq&);
181 /// Constructor for posting
182 ReEq(Home home, View0 x0, View1 x1, CtrlView b);
183 public:
184 /// Copy propagator during cloning
185 virtual Actor* copy(Space& home);
186 /// Cost function (defined as PC_TERNARY_LO)
187 virtual PropCost cost(const Space& home, const ModEventDelta& med) const;
188 /// Schedule function
189 virtual void reschedule(Space& home);
190 /// Delete propagator and return its size
191 virtual size_t dispose(Space& home);
192 /// Perform propagation
193 virtual ExecStatus propagate(Space& home, const ModEventDelta& med);
194 /// Post propagator for \f$ (x=y) \Leftrightarrow b\f$
195 static ExecStatus post(Home home, View0 x, View1 y,
196 CtrlView b);
197 };
198
199 /**
200 * \brief %Propagator for set less than or equal
201 *
202 * Propagates strict inequality if \a strict is true.
203 *
204 * Requires \code #include <gecode/set/rel.hh> \endcode
205 * \ingroup FuncSetProp
206 */
207 template<class View0, class View1, bool strict=false>
208 class Lq : public MixBinaryPropagator<View0,PC_SET_ANY,View1,PC_SET_ANY> {
209 protected:
210 using MixBinaryPropagator<View0,PC_SET_ANY,View1,PC_SET_ANY>::x0;
211 using MixBinaryPropagator<View0,PC_SET_ANY,View1,PC_SET_ANY>::x1;
212 /// Constructor for cloning \a p
213 Lq(Space& home, Lq& p);
214 /// Constructor for posting
215 Lq(Home home, View0 x0, View1 x1);
216 public:
217 /// Copy propagator during cloning
218 virtual Actor* copy(Space& home);
219 /// Perform propagation
220 virtual ExecStatus propagate(Space& home, const ModEventDelta& med);
221 /// Post propagator \f$ x\leq y \f$
222 static ExecStatus post(Home home, View0 x, View1 y);
223 };
224
225 /**
226 * \brief %Reified propagator for set less than or equal
227 *
228 * Propagates strict inequality if \a strict is true.
229 *
230 * Requires \code #include <gecode/set/rel.hh> \endcode
231 * \ingroup FuncSetProp
232 */
233 template<class View0, class View1, ReifyMode rm, bool strict=false>
234 class ReLq : public Propagator {
235 protected:
236 View0 x0;
237 View1 x1;
238 Gecode::Int::BoolView b;
239 /// Constructor for cloning \a p
240 ReLq(Space& home, ReLq& p);
241 /// Constructor for posting
242 ReLq(Home home, View0 x0, View1 x1, Gecode::Int::BoolView b);
243 public:
244 /// Copy propagator during cloning
245 virtual Actor* copy(Space& home);
246 /// Cost function (defined as PC_TERNARY_LO)
247 virtual PropCost cost(const Space& home, const ModEventDelta& med) const;
248 /// Schedule function
249 virtual void reschedule(Space& home);
250 /// Delete propagator and return its size
251 virtual size_t dispose(Space& home);
252 /// Perform propagation
253 virtual ExecStatus propagate(Space& home, const ModEventDelta& med);
254 /// Post propagator for \f$ (x\leq y) \Leftrightarrow b\f$
255 static ExecStatus post(Home home, View0 x, View1 y,
256 Gecode::Int::BoolView b);
257 };
258
259 /**
260 * \brief %Propagator for negated equality
261 *
262 * Requires \code #include <gecode/set/rel.hh> \endcode
263 * \ingroup FuncSetProp
264 */
265
266 template<class View0, class View1>
267 class Distinct :
268 public MixBinaryPropagator<View0,PC_SET_VAL,View1,PC_SET_VAL> {
269 protected:
270 using MixBinaryPropagator<View0,PC_SET_VAL,View1,PC_SET_VAL>::x0;
271 using MixBinaryPropagator<View0,PC_SET_VAL,View1,PC_SET_VAL>::x1;
272 /// Constructor for cloning \a p
273 Distinct(Space& home, Distinct& p);
274 /// Constructor for posting
275 Distinct(Home home, View0 x0, View1 x1);
276 public:
277 /// Copy propagator during cloning
278 virtual Actor* copy(Space& home);
279 /// Perform propagation
280 virtual ExecStatus propagate(Space& home, const ModEventDelta& med);
281 /// Post propagator \f$ x\neq y \f$
282 static ExecStatus post(Home home, View0 x, View1 y);
283 };
284
285 /**
286 * \brief %Propagator for negated equality
287 *
288 * This propagator actually propagates the distinctness, after the
289 * Distinct propagator waited for one variable to become
290 * assigned.
291 *
292 * Requires \code #include <gecode/set/rel.hh> \endcode
293 * \ingroup FuncSetProp
294 */
295 template<class View0>
296 class DistinctDoit : public UnaryPropagator<View0,PC_SET_ANY> {
297 protected:
298 using UnaryPropagator<View0,PC_SET_ANY>::x0;
299 /// The view that is already assigned
300 ConstSetView y;
301 /// Constructor for cloning \a p
302 DistinctDoit(Space& home, DistinctDoit&);
303 /// Constructor for posting
304 DistinctDoit(Home home, View0 x0, ConstSetView y);
305 public:
306 /// Copy propagator during cloning
307 virtual Actor* copy(Space& home);
308 /// Perform propagation
309 virtual ExecStatus propagate(Space& home, const ModEventDelta& med);
310 /// Post propagator \f$ x\neq y \f$
311 static ExecStatus post(Home home, View0 x, ConstSetView y);
312 };
313
314}}}
315
316#include <gecode/set/rel/common.hpp>
317#include <gecode/set/rel/subset.hpp>
318#include <gecode/set/rel/nosubset.hpp>
319#include <gecode/set/rel/re-subset.hpp>
320#include <gecode/set/rel/eq.hpp>
321#include <gecode/set/rel/re-eq.hpp>
322#include <gecode/set/rel/nq.hpp>
323#include <gecode/set/rel/lq.hpp>
324#include <gecode/set/rel/re-lq.hpp>
325
326#endif
327
328// STATISTICS: set-prop