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 *
6 * Copyright:
7 * Christian Schulte, 2011
8 *
9 * This file is part of Gecode, the generic constraint
10 * development environment:
11 * http://www.gecode.org
12 *
13 * Permission is hereby granted, free of charge, to any person obtaining
14 * a copy of this software and associated documentation files (the
15 * "Software"), to deal in the Software without restriction, including
16 * without limitation the rights to use, copy, modify, merge, publish,
17 * distribute, sublicense, and/or sell copies of the Software, and to
18 * permit persons to whom the Software is furnished to do so, subject to
19 * the following conditions:
20 *
21 * The above copyright notice and this permission notice shall be
22 * included in all copies or substantial portions of the Software.
23 *
24 * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,
25 * EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF
26 * MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND
27 * NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE
28 * LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION
29 * OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION
30 * WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
31 *
32 */
33
34#ifndef GECODE_INT_NO_OVERLAP_HH
35#define GECODE_INT_NO_OVERLAP_HH
36
37#include <gecode/int.hh>
38
39/**
40 * \namespace Gecode::Int::NoOverlap
41 * \brief %No-overlap propagators
42 */
43
44namespace Gecode { namespace Int { namespace NoOverlap {
45
46 /**
47 * \brief Dimension combining coordinate and integer size information
48 */
49 class FixDim {
50 protected:
51 /// Coordinate
52 IntView c;
53 /// Size
54 int s;
55 /// Modify smallest start coordinate
56 ExecStatus ssc(Space& home, int n);
57 /// Modify largest end coordinate
58 ExecStatus lec(Space& home, int n);
59 /// Dimension must not overlap with coordinates \a n to \a m
60 ExecStatus nooverlap(Space& home, int n, int m);
61 public:
62 /// Default constructor
63 FixDim(void);
64 /// Constructor
65 FixDim(IntView c, int s);
66
67 /// Return smallest start coordinate
68 int ssc(void) const;
69 /// Return largest start coordinate
70 int lsc(void) const;
71 /// Return smallest end coordinate
72 int sec(void) const;
73 /// Return largest end coordinate
74 int lec(void) const;
75
76 /// Dimension must not overlap with \a d
77 ExecStatus nooverlap(Space& home, FixDim& d);
78
79 /// Update dimension during cloning
80 void update(Space& home, FixDim& d);
81
82 /// Subscribe propagator \a p to dimension
83 void subscribe(Space& home, Propagator& p);
84 /// Cancel propagator \a p from dimension
85 void cancel(Space& home, Propagator& p);
86 /// Schedule propagator \a p
87 void reschedule(Space& home, Propagator& p);
88 };
89
90 /**
91 * \brief Dimension combining coordinate and integer view size information
92 */
93 class FlexDim {
94 protected:
95 /// Start coordinate
96 IntView c0;
97 /// Size
98 IntView s;
99 /// End coordinate
100 IntView c1;
101 /// Modify smallest start coordinate
102 ExecStatus ssc(Space& home, int n);
103 /// Modify largest end coordinate
104 ExecStatus lec(Space& home, int n);
105 /// Dimension must not overlap with coordinates \a n to \a m
106 ExecStatus nooverlap(Space& home, int n, int m);
107 public:
108 /// Default constructor
109 FlexDim(void);
110 /// Constructor
111 FlexDim(IntView c0, IntView s, IntView c1);
112
113 /// Return smallest start coordinate
114 int ssc(void) const;
115 /// Return largest start coordinate
116 int lsc(void) const;
117 /// Return smallest end coordinate
118 int sec(void) const;
119 /// Return largest end coordinate
120 int lec(void) const;
121
122 /// Dimension must not overlap with \a d
123 ExecStatus nooverlap(Space& home, FlexDim& d);
124
125 /// Update dimension during cloning
126 void update(Space& home, FlexDim& d);
127
128 /// Subscribe propagator \a p to dimension
129 void subscribe(Space& home, Propagator& p);
130 /// Cancel propagator \a p from dimension
131 void cancel(Space& home, Propagator& p);
132 /// Schedule propagator \a p
133 void reschedule(Space& home, Propagator& p);
134 };
135
136}}}
137
138#include <gecode/int/no-overlap/dim.hpp>
139
140namespace Gecode { namespace Int { namespace NoOverlap {
141
142 /**
143 * \brief Mandatory box class
144 */
145 template<class Dim, int n>
146 class ManBox {
147 protected:
148 /// Dimensions
149 Dim d[n];
150 public:
151 /// Access to dimension \a i
152 const Dim& operator [](int i) const;
153 /// Access to dimension \a i
154 Dim& operator [](int i);
155 /// Return number of dimensions
156 static int dim(void);
157
158 /// Whether box is mandatory
159 bool mandatory(void) const;
160 /// Whether box is optional
161 bool optional(void) const;
162 /// Whether box is excluded
163 bool excluded(void) const;
164
165 /// Exclude box
166 ExecStatus exclude(Space& home);
167
168 /// Check whether this box does not any longer overlap with \a b
169 bool nooverlap(const ManBox<Dim,n>& b) const;
170 /// Check whether this box overlaps with \a b
171 bool overlap(const ManBox<Dim,n>& b) const;
172
173 /// Propagate that this box does not overlap with \a b
174 ExecStatus nooverlap(Space& home, ManBox<Dim,n>& b);
175
176 /// Update box during cloning
177 void update(Space& home, ManBox<Dim,n>& r);
178
179 /// Subscribe propagator \a p to box
180 void subscribe(Space& home, Propagator& p);
181 /// Cancel propagator \a p from box
182 void cancel(Space& home, Propagator& p);
183 /// Schedule propagator \a p
184 void reschedule(Space& home, Propagator& p);
185 };
186
187 /**
188 * \brief Optional box class
189 */
190 template<class Dim, int n>
191 class OptBox : public ManBox<Dim,n> {
192 protected:
193 using ManBox<Dim,n>::d;
194 /// Whether box is optional or not
195 BoolView o;
196 public:
197 /// Set Boolean view to \a o
198 void optional(BoolView o);
199 /// Whether box is mandatory
200 bool mandatory(void) const;
201 /// Whether box is optional
202 bool optional(void) const;
203 /// Whether box is excluded
204 bool excluded(void) const;
205
206 /// Exclude box
207 ExecStatus exclude(Space& home);
208
209 /// Update box during cloning
210 void update(Space& home, OptBox<Dim,n>& r);
211
212 /// Subscribe propagator \a p to box
213 void subscribe(Space& home, Propagator& p);
214 /// Cancel propagator \a p from box
215 void cancel(Space& home, Propagator& p);
216 /// Schedule propagator \a p
217 void reschedule(Space& home, Propagator& p);
218 };
219
220}}}
221
222#include <gecode/int/no-overlap/box.hpp>
223
224namespace Gecode { namespace Int { namespace NoOverlap {
225
226 /**
227 * \brief Base class for no-overlap propagator
228 *
229 * Requires \code #include <gecode/int/no-overlap.hh> \endcode
230 *
231 * \ingroup FuncIntProp
232 */
233 template<class Box>
234 class Base : public Propagator {
235 protected:
236 /// Boxes
237 Box* b;
238 /// Number of mandatory boxes: b[0] ... b[n-1]
239 int n;
240 /// Constructor for posting with \a n mandatory boxes
241 Base(Home home, Box* b, int n);
242 /// Constructor for cloning \a p with \a m boxes
243 Base(Space& home, Base<Box>& p, int m);
244 /**
245 * \brief Partition \a n boxes \a b starting at position \a i
246 *
247 * Returns the number of mandatory boxes at the front of \a b.
248 */
249 static int partition(Box* b, int i, int n);
250 public:
251 /// Cost function
252 virtual PropCost cost(const Space& home, const ModEventDelta& med) const;
253 /// Schedule function
254 virtual void reschedule(Space& home);
255 /// Destructor
256 virtual size_t dispose(Space& home);
257 };
258
259 /**
260 * \brief No-overlap propagator for mandatory boxes
261 *
262 * Requires \code #include <gecode/int/no-overlap.hh> \endcode
263 *
264 * \ingroup FuncIntProp
265 */
266 template<class Box>
267 class ManProp : public Base<Box> {
268 protected:
269 using Base<Box>::b;
270 using Base<Box>::n;
271 /// Constructor for posting
272 ManProp(Home home, Box* b, int n);
273 /// Constructor for cloning \a p
274 ManProp(Space& home, ManProp<Box>& p);
275 public:
276 /// Post propagator for boxes \a b
277 static ExecStatus post(Home home, Box* b, int n);
278 /// Perform propagation
279 virtual ExecStatus propagate(Space& home, const ModEventDelta& med);
280 /// Copy propagator during cloning
281 virtual Actor* copy(Space& home);
282 /// Destructor
283 virtual size_t dispose(Space& home);
284 };
285
286 /**
287 * \brief No-overlap propagator for optional boxes
288 *
289 * Requires \code #include <gecode/int/no-overlap.hh> \endcode
290 *
291 * \ingroup FuncIntProp
292 */
293 template<class Box>
294 class OptProp : public Base<Box> {
295 protected:
296 using Base<Box>::b;
297 using Base<Box>::n;
298 /// Number of optional boxes: b[n] ... b[n+m-1]
299 int m;
300 /// Constructor for posting
301 OptProp(Home home, Box* b, int n, int m);
302 /// Constructor for cloning \a p
303 OptProp(Space& home, OptProp<Box>& p);
304 public:
305 /// Post propagator for boxes \a b
306 static ExecStatus post(Home home, Box* b, int n);
307 /// Perform propagation
308 virtual ExecStatus propagate(Space& home, const ModEventDelta& med);
309 /// Copy propagator during cloning
310 virtual Actor* copy(Space& home);
311 /// Destructor
312 virtual size_t dispose(Space& home);
313 };
314
315}}}
316
317#include <gecode/int/no-overlap/base.hpp>
318#include <gecode/int/no-overlap/man.hpp>
319#include <gecode/int/no-overlap/opt.hpp>
320
321#endif
322
323// STATISTICS: int-prop
324