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, 2004
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_ELEMENT_HH
37#define GECODE_INT_ELEMENT_HH
38
39#include <gecode/int.hh>
40#include <gecode/int/rel.hh>
41#include <gecode/int/idx-view.hh>
42
43/**
44 * \namespace Gecode::Int::Element
45 * \brief %Element propagators
46 */
47
48namespace Gecode { namespace Int { namespace Element {
49
50 /**
51 * \brief %Element propagator for array of integers
52 *
53 * Requires \code #include <gecode/int/element.hh> \endcode
54 * \ingroup FuncIntProp
55 */
56 template<class V0, class V1, class Idx, class Val>
57 class Int : public Propagator {
58 protected:
59 /**
60 * \brief Linked index-value pairs
61 *
62 * Data structure linking pairs of index and value (index,value)
63 * where pairs are linked in order of both index and
64 * value (to allow for easy removal while keeping both index and
65 * value sorted).
66 */
67 class IdxVal {
68 public:
69 Idx idx_next; ///< The position of the next pair in index order
70 Idx val_next; ///< The position of the next pair in value order
71 Idx idx; ///< The index
72 Val val; ///< The value
73 /// Mark that this pair should be removed
74 void mark(void);
75 /// Return whether this pair is marked for removal
76 bool marked(void) const;
77 };
78 /**
79 * \brief Value iterator for indices in index-value map
80 *
81 * The iterator also removes marked index-value pairs.
82 *
83 */
84 class IterIdxUnmark {
85 private:
86 IdxVal* iv; ///< The index value data structure
87 Idx i; ///< Current index value pair
88 public:
89 /// Initialize with start
90 IterIdxUnmark(IdxVal* iv);
91 /// Test whether more pairs to be iterated
92 bool operator ()(void) const;
93 /// Move to next index value pair (next index)
94 void operator ++(void);
95 /// Return index of current index value pair
96 Idx val(void) const;
97 };
98 /**
99 * \brief Value iterator for values in index-value map
100 *
101 * Note that the iterated value sequence is not strictly
102 * increasing (might contain duplicates).
103 */
104 class IterVal {
105 private:
106 IdxVal* iv; ///< The index value data structure
107 Idx i; ///< Current index value pair
108 public:
109 /// Initialize with start
110 IterVal(IdxVal* iv);
111 /// Test whether more pairs to be iterated
112 bool operator ()(void) const;
113 /// Move to next index value pair (next value)
114 void operator ++(void);
115 /// Return value of current index value pair
116 Val val(void) const;
117 };
118 /**
119 * \brief Value iterator for values in index-value map
120 *
121 * Note that the iterated value sequence is not strictly
122 * increasing (might contain duplicates).
123 *
124 * The iterator also removes marked index-value pairs.
125 */
126 class IterValUnmark {
127 private:
128 IdxVal* iv; ///< The index value data structure
129 Idx i; ///< Current index value pair
130 public:
131 /// Initialize with start
132 IterValUnmark(IdxVal* iv);
133 /// Test whether more pairs to be iterated
134 bool operator ()(void) const;
135 /// Move to next index value pair (next value)
136 void operator ++(void);
137 /// Return value of current index value pair
138 Val val(void) const;
139 };
140 /// Sorting pointers to (index,value) pairs in value order
141 class ByVal {
142 protected:
143 const IdxVal* iv; ///< Index-value pairs
144 public:
145 /// Initialize with index value pairs
146 ByVal(const IdxVal* iv);
147 /// Compare pairs at positions \a i and \a j
148 bool operator ()(Idx& i, Idx& j);
149 };
150
151 /// View for index
152 V0 x0;
153 /// Type for index size
154 typedef typename Gecode::Support::IntTypeTraits<Idx>::utype IdxSize;
155 /// Size of \a x0 at last execution
156 IdxSize s0;
157 /// View for result
158 V1 x1;
159 /// Type for value size
160 typedef typename Gecode::Support::IntTypeTraits<Val>::utype ValSize;
161 /// Size of \a x1 at last execution
162 ValSize s1;
163 /// Shared array of integer values
164 IntSharedArray c;
165 /// The index-value data structure
166 IdxVal* iv;
167 /// Prune index according to \a x0
168 void prune_idx(void);
169 /// Prune values according to \a x1
170 void prune_val(void);
171 /// Prune when \a x1 is assigned
172 static ExecStatus assigned_val(Space& home, IntSharedArray& c,
173 V0 x0, V1 x1);
174 /// Constructor for cloning \a p
175 Int(Space& home, Int& p);
176 /// Constructor for creation
177 Int(Home home, IntSharedArray& i, V0 x0, V1 x1);
178 public:
179 /// Perform copying during cloning
180 virtual Actor* copy(Space& home);
181 /// Cost function (defined as high binary)
182 virtual PropCost cost(const Space& home, const ModEventDelta& med) const;
183 /// Schedule function
184 virtual void reschedule(Space& home);
185 /// Perform propagation
186 virtual ExecStatus propagate(Space& home, const ModEventDelta& med);
187 /// Post propagator for \f$i_{x_0}=x_1\f$
188 static ExecStatus post(Home home, IntSharedArray& i, V0 x0, V1 x1);
189 /// Delete propagator and return its size
190 virtual size_t dispose(Space& home);
191 };
192
193 /// Post propagator with apropriate index and value types
194 template<class V0, class V1>
195 ExecStatus post_int(Home home, IntSharedArray& c, V0 x0, V1 x1);
196
197
198 /**
199 * \brief Base-class for element propagator for array of views
200 *
201 */
202 template<class VA, class VB, class VC, PropCond pc_ac>
203 class View : public Propagator {
204 protected:
205 /// Current index-view map
206 IdxViewArray<VA> iv;
207 /// View for index
208 VB x0;
209 /// View for result
210 VC x1;
211 /// Constructor for cloning \a p
212 View(Space& home, View& p);
213 /// Constructor for creation
214 View(Home home, IdxViewArray<VA>& iv, VB x0, VC x1);
215 public:
216 // Cost function (defined as low linear)
217 virtual PropCost cost(const Space& home, const ModEventDelta& med) const;
218 /// Schedule function
219 virtual void reschedule(Space& home);
220 /// Delete propagator and return its size
221 virtual size_t dispose(Space& home);
222 };
223
224
225 /**
226 * \brief Bounds consistent element propagator for array of views
227 *
228 * Requires \code #include <gecode/int/element.hh> \endcode
229 * \ingroup FuncIntProp
230 */
231 template<class VA, class VB, class VC>
232 class ViewBnd : public View<VA,VB,VC,PC_INT_BND> {
233 protected:
234 using View<VA,VB,VC,PC_INT_BND>::iv;
235 using View<VA,VB,VC,PC_INT_BND>::x0;
236 using View<VA,VB,VC,PC_INT_BND>::x1;
237
238 /// Constructor for cloning \a p
239 ViewBnd(Space& home, ViewBnd& p);
240 /// Constructor for creation
241 ViewBnd(Home home, IdxViewArray<VA>& iv, VB x0, VC x1);
242 public:
243 /// Perform copying 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$iv_{x_0}=x_1\f$
248 static ExecStatus post(Home home, IdxViewArray<VA>& iv, VB x0, VC x1);
249 };
250
251 /**
252 * \brief Domain consistent element propagator for array of views
253 *
254 * The propagator uses staging: first it uses
255 * bounds-propagation on the array of views and the uses
256 * domain-propagation on the array of views.
257 *
258 * Requires \code #include <gecode/int/element.hh> \endcode
259 * \ingroup FuncIntProp
260 */
261 template<class VA, class VB, class VC>
262 class ViewDom : public View<VA,VB,VC,PC_INT_DOM> {
263 protected:
264 using View<VA,VB,VC,PC_INT_DOM>::iv;
265 using View<VA,VB,VC,PC_INT_DOM>::x0;
266 using View<VA,VB,VC,PC_INT_DOM>::x1;
267
268 /// Constructor for cloning \a p
269 ViewDom(Space& home, ViewDom& p);
270 /// Constructor for creation
271 ViewDom(Home home, IdxViewArray<VA>& iv, VB x0, VC x1);
272 public:
273 /// Perform copying during cloning
274 virtual Actor* copy(Space& home);
275 /**
276 * \brief Cost function
277 *
278 * If in stage for bounds-propagation defined as low linear,
279 * otherwise as high linear.
280 *
281 */
282 virtual PropCost cost(const Space& home, const ModEventDelta& med) const;
283 /// Perform propagation
284 virtual ExecStatus propagate(Space& home, const ModEventDelta& med);
285 /// Post propagator for \f$iv_{x_0}=x_1\f$
286 static ExecStatus post(Home home, IdxViewArray<VA>& iv,
287 VB x0, VC x1);
288 };
289
290 /**
291 * \brief Domain consistent pair propagator
292 *
293 * Requires \code #include <gecode/int/element.hh> \endcode
294 *
295 * \ingroup FuncIntProp
296 */
297 class GECODE_VTABLE_EXPORT Pair
298 : public TernaryPropagator<IntView,PC_INT_DOM> {
299 protected:
300 using TernaryPropagator<IntView,PC_INT_DOM>::x0;
301 using TernaryPropagator<IntView,PC_INT_DOM>::x1;
302 using TernaryPropagator<IntView,PC_INT_DOM>::x2;
303 /// Width
304 int w;
305 /// Constructor for cloning \a p
306 Pair(Space& home, Pair& p);
307 public:
308 /// Constructor for posting
309 Pair(Home home, IntView x0, IntView x1, IntView x2, int w);
310 /// Post propagator \f$x_0+x_1\cdot w=x_2\f$
311 static ExecStatus post(Home home, IntView x0, IntView x1, IntView x2,
312 int w, int h);
313 /// Copy propagator during cloning
314 GECODE_INT_EXPORT virtual Actor* copy(Space& home);
315 /// Perform propagation
316 GECODE_INT_EXPORT virtual ExecStatus propagate(Space& home, const ModEventDelta& med);
317 };
318
319 /**
320 * \brief Domain consistent pair-with-offsets propagator
321 *
322 * Requires \code #include <gecode/int/element.hh> \endcode
323 *
324 * \ingroup FuncIntProp
325 */
326 class GECODE_VTABLE_EXPORT PairWithOffsets
327 : public TernaryPropagator<OffsetView,PC_INT_DOM> {
328 protected:
329 using TernaryPropagator<OffsetView,PC_INT_DOM>::x0;
330 using TernaryPropagator<OffsetView,PC_INT_DOM>::x1;
331 using TernaryPropagator<OffsetView,PC_INT_DOM>::x2;
332 /// Width
333 int w;
334 /// Constructor for cloning \a p
335 PairWithOffsets(Space& home, PairWithOffsets& p);
336 public:
337 /// Constructor for posting
338 PairWithOffsets(Home home, OffsetView x0, OffsetView x1, IntView x2, int w);
339 /// Post propagator \f$x_0+x_1\cdot w=x_2\f$
340 static ExecStatus post(Home home, OffsetView x0, OffsetView x1, IntView x2,
341 int w, int h);
342 /// Copy propagator during cloning
343 GECODE_INT_EXPORT virtual Actor* copy(Space& home);
344 /// Perform propagation
345 GECODE_INT_EXPORT virtual ExecStatus propagate(Space& home, const ModEventDelta& med);
346 };
347
348}}}
349
350#include <gecode/int/element/int.hpp>
351#include <gecode/int/element/view.hpp>
352#include <gecode/int/element/pair.hpp>
353
354#endif
355
356
357// STATISTICS: int-prop
358