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 * Copyright:
8 * Guido Tack, 2004
9 * Christian Schulte, 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_SET_INT_HH
37#define GECODE_SET_INT_HH
38
39#include <gecode/set.hh>
40
41namespace Gecode { namespace Set { namespace Int {
42
43 /**
44 * \namespace Gecode::Set::Int
45 * \brief Propagators connecting set and int variables
46 */
47
48 /**
49 * \brief %Propagator for minimum element
50 *
51 * Requires \code #include <gecode/set/int.hh> \endcode
52 * \ingroup FuncSetProp
53 */
54 template<class View>
55 class MinElement :
56 public MixBinaryPropagator<View,PC_SET_ANY,
57 Gecode::Int::IntView,Gecode::Int::PC_INT_BND> {
58 protected:
59 using MixBinaryPropagator<View,PC_SET_ANY,
60 Gecode::Int::IntView,Gecode::Int::PC_INT_BND>::x0;
61 using MixBinaryPropagator<View,PC_SET_ANY,
62 Gecode::Int::IntView,Gecode::Int::PC_INT_BND>::x1;
63 /// Constructor for cloning \a p
64 MinElement(Space& home, MinElement& p);
65 /// Constructor for posting
66 MinElement(Home home, View, Gecode::Int::IntView);
67 public:
68 /// Copy propagator during cloning
69 virtual Actor* copy(Space& home);
70 /// Perform propagation
71 virtual ExecStatus propagate(Space& home, const ModEventDelta& med);
72 /// Post propagator for \a x is the minimal element of \a s
73 static ExecStatus post(Home home, View s, Gecode::Int::IntView x);
74 };
75
76 /**
77 * \brief %Propagator for not minimum element
78 *
79 * Requires \code #include <gecode/set/int.hh> \endcode
80 * \ingroup FuncSetProp
81 */
82 template<class View>
83 class NotMinElement :
84 public MixBinaryPropagator<View,PC_SET_ANY,
85 Gecode::Int::IntView,Gecode::Int::PC_INT_DOM> {
86 protected:
87 using MixBinaryPropagator<View,PC_SET_ANY,
88 Gecode::Int::IntView,Gecode::Int::PC_INT_DOM>::x0;
89 using MixBinaryPropagator<View,PC_SET_ANY,
90 Gecode::Int::IntView,Gecode::Int::PC_INT_DOM>::x1;
91 /// Constructor for cloning \a p
92 NotMinElement(Space& home, NotMinElement& p);
93 /// Constructor for posting
94 NotMinElement(Home home, View, Gecode::Int::IntView);
95 public:
96 /// Copy propagator during cloning
97 virtual Actor* copy(Space& home);
98 /// Perform propagation
99 virtual ExecStatus propagate(Space& home, const ModEventDelta& med);
100 /// Post propagator for \a x is not the minimal element of \a s
101 static ExecStatus post(Home home, View s, Gecode::Int::IntView x);
102 };
103
104 /**
105 * \brief %Propagator for reified minimum element
106 *
107 * Requires \code #include <gecode/set/int.hh> \endcode
108 * \ingroup FuncSetProp
109 */
110 template<class View, ReifyMode rm>
111 class ReMinElement :
112 public Gecode::Int::ReMixBinaryPropagator<View,PC_SET_ANY,
113 Gecode::Int::IntView,Gecode::Int::PC_INT_DOM,Gecode::Int::BoolView> {
114 protected:
115 using Gecode::Int::ReMixBinaryPropagator<View,PC_SET_ANY,
116 Gecode::Int::IntView,Gecode::Int::PC_INT_DOM,Gecode::Int::BoolView>::x0;
117 using Gecode::Int::ReMixBinaryPropagator<View,PC_SET_ANY,
118 Gecode::Int::IntView,Gecode::Int::PC_INT_DOM,Gecode::Int::BoolView>::x1;
119 using Gecode::Int::ReMixBinaryPropagator<View,PC_SET_ANY,
120 Gecode::Int::IntView,Gecode::Int::PC_INT_DOM,Gecode::Int::BoolView>::b;
121 /// Constructor for cloning \a p
122 ReMinElement(Space& home, ReMinElement& p);
123 /// Constructor for posting
124 ReMinElement(Home home, View, Gecode::Int::IntView,
125 Gecode::Int::BoolView);
126 public:
127 /// Copy propagator during cloning
128 virtual Actor* copy(Space& home);
129 /// Perform propagation
130 virtual ExecStatus propagate(Space& home, const ModEventDelta& med);
131 /// Post reified propagator for \a b iff \a x is the minimal element of \a s
132 static ExecStatus post(Home home, View s, Gecode::Int::IntView x,
133 Gecode::Int::BoolView b);
134 };
135
136 /**
137 * \brief %Propagator for maximum element
138 *
139 * Requires \code #include <gecode/set/int.hh> \endcode
140 * \ingroup FuncSetProp
141 */
142 template<class View>
143 class MaxElement :
144 public MixBinaryPropagator<View,PC_SET_ANY,Gecode::Int::IntView,Gecode::Int::PC_INT_BND> {
145 protected:
146 using MixBinaryPropagator<View,PC_SET_ANY,
147 Gecode::Int::IntView,Gecode::Int::PC_INT_BND>::x0;
148 using MixBinaryPropagator<View,PC_SET_ANY,
149 Gecode::Int::IntView,Gecode::Int::PC_INT_BND>::x1;
150 /// Constructor for cloning \a p
151 MaxElement(Space& home, MaxElement& p);
152 /// Constructor for posting
153 MaxElement(Home home, View, Gecode::Int::IntView);
154 public:
155 /// Copy propagator during cloning
156 virtual Actor* copy(Space& home);
157 /// Perform propagation
158 virtual ExecStatus propagate(Space& home, const ModEventDelta& med);
159 /// Post propagator for \a x is the largest element of \a s
160 static ExecStatus post(Home home, View s, Gecode::Int::IntView x);
161 };
162
163 /**
164 * \brief %Propagator for not maximum element
165 *
166 * Requires \code #include <gecode/set/int.hh> \endcode
167 * \ingroup FuncSetProp
168 */
169 template<class View>
170 class NotMaxElement :
171 public MixBinaryPropagator<View,PC_SET_ANY,
172 Gecode::Int::IntView,Gecode::Int::PC_INT_DOM> {
173 protected:
174 using MixBinaryPropagator<View,PC_SET_ANY,
175 Gecode::Int::IntView,Gecode::Int::PC_INT_DOM>::x0;
176 using MixBinaryPropagator<View,PC_SET_ANY,
177 Gecode::Int::IntView,Gecode::Int::PC_INT_DOM>::x1;
178 /// Constructor for cloning \a p
179 NotMaxElement(Space& home, NotMaxElement& p);
180 /// Constructor for posting
181 NotMaxElement(Home home, View, Gecode::Int::IntView);
182 public:
183 /// Copy propagator during cloning
184 virtual Actor* copy(Space& home);
185 /// Perform propagation
186 virtual ExecStatus propagate(Space& home, const ModEventDelta& med);
187 /// Post propagator for \a x is not the largest element of \a s
188 static ExecStatus post(Home home, View s, Gecode::Int::IntView x);
189 };
190
191 /**
192 * \brief %Reified propagator for maximum element
193 *
194 * Requires \code #include <gecode/set/int.hh> \endcode
195 * \ingroup FuncSetProp
196 */
197 template<class View, ReifyMode rm>
198 class ReMaxElement :
199 public Gecode::Int::ReMixBinaryPropagator<View,PC_SET_ANY,
200 Gecode::Int::IntView,Gecode::Int::PC_INT_DOM,Gecode::Int::BoolView> {
201 protected:
202 using Gecode::Int::ReMixBinaryPropagator<View,PC_SET_ANY,
203 Gecode::Int::IntView,Gecode::Int::PC_INT_DOM,Gecode::Int::BoolView>::x0;
204 using Gecode::Int::ReMixBinaryPropagator<View,PC_SET_ANY,
205 Gecode::Int::IntView,Gecode::Int::PC_INT_DOM,Gecode::Int::BoolView>::x1;
206 using Gecode::Int::ReMixBinaryPropagator<View,PC_SET_ANY,
207 Gecode::Int::IntView,Gecode::Int::PC_INT_DOM,Gecode::Int::BoolView>::b;
208 /// Constructor for cloning \a p
209 ReMaxElement(Space& home, ReMaxElement& p);
210 /// Constructor for posting
211 ReMaxElement(Home home, View, Gecode::Int::IntView, Gecode::Int::BoolView);
212 public:
213 /// Copy propagator during cloning
214 virtual Actor* copy(Space& home);
215 /// Perform propagation
216 virtual ExecStatus propagate(Space& home, const ModEventDelta& med);
217 /// Post reified propagator for \a b iff \a x is the largest element of \a s
218 static ExecStatus post(Home home, View s, Gecode::Int::IntView x,
219 Gecode::Int::BoolView b);
220 };
221
222 /**
223 * \brief %Propagator for cardinality
224 *
225 * Requires \code #include <gecode/set/int.hh> \endcode
226 * \ingroup FuncSetProp
227 */
228 template<class View>
229 class Card :
230 public MixBinaryPropagator<View,PC_SET_CARD,
231 Gecode::Int::IntView,Gecode::Int::PC_INT_BND> {
232 protected:
233 using MixBinaryPropagator<View,PC_SET_CARD,
234 Gecode::Int::IntView,Gecode::Int::PC_INT_BND>::x0;
235 using MixBinaryPropagator<View,PC_SET_CARD,
236 Gecode::Int::IntView,Gecode::Int::PC_INT_BND>::x1;
237 /// Constructor for cloning \a p
238 Card(Space& home, Card& p);
239 /// Constructor for posting
240 Card(Home home, View, Gecode::Int::IntView);
241 public:
242 /// Copy propagator during cloning
243 virtual Actor* copy(Space& home);
244 /// Perform propagation
245 virtual ExecStatus propagate(Space& home, const ModEventDelta& med);
246 /// Post propagator for \f$ |s|=x \f$
247 static ExecStatus post(Home home, View s, Gecode::Int::IntView x);
248 };
249
250 /**
251 * \brief %Propagator for weight of a set
252 *
253 * Requires \code #include <gecode/set/int.hh> \endcode
254 * \ingroup FuncSetProp
255 */
256 template<class View>
257 class Weights : public Propagator {
258 protected:
259 /// List of elements in the upper bound
260 SharedArray<int> elements;
261 /// Weights for the elements in the upper bound
262 SharedArray<int> weights;
263
264 /// The set view
265 View x;
266 /// The integer view
267 Gecode::Int::IntView y;
268
269 /// Constructor for cloning \a p
270 Weights(Space& home, Weights& p);
271 /// Constructor for posting
272 Weights(Home home, const SharedArray<int>&, const SharedArray<int>&,
273 View, Gecode::Int::IntView);
274 public:
275 /// Copy propagator during cloning
276 virtual Actor* copy(Space& home);
277 /// Cost function (defined as PC_LINEAR_LO)
278 virtual PropCost cost(const Space& home, const ModEventDelta& med) const;
279 /// Schedule function
280 virtual void reschedule(Space& home);
281 /// Delete propagator and return its size
282 virtual size_t dispose(Space& home);
283 /// Perform propagation
284 virtual ExecStatus propagate(Space& home, const ModEventDelta& med);
285 /// Post propagator for \f$\sum_{i\in x} weights_i = y \f$
286 static ExecStatus post(Home home,
287 const SharedArray<int>& elements,
288 const SharedArray<int>& weights,
289 View x, Gecode::Int::IntView y);
290 };
291
292}}}
293
294#include <gecode/set/int/minmax.hpp>
295#include <gecode/set/int/card.hpp>
296#include <gecode/set/int/weights.hpp>
297
298#endif
299
300// STATISTICS: set-prop