Generated on Thu Jan 16 2025 00:00:00 for Gecode by doxygen 1.14.0
no-overlap.hh
Go to the documentation of this file.
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
43
44namespace Gecode { namespace Int { namespace NoOverlap {
45
49 class FixDim {
50 protected:
54 int s;
56 ExecStatus ssc(Space& home, int n);
58 ExecStatus lec(Space& home, int n);
60 ExecStatus nooverlap(Space& home, int n, int m);
61 public:
63 FixDim(void);
65 FixDim(IntView c, int s);
66
68 int ssc(void) const;
70 int lsc(void) const;
72 int sec(void) const;
74 int lec(void) const;
75
78
80 void update(Space& home, FixDim& d);
81
83 void subscribe(Space& home, Propagator& p);
85 void cancel(Space& home, Propagator& p);
87 void reschedule(Space& home, Propagator& p);
88 };
89
93 class FlexDim {
94 protected:
102 ExecStatus ssc(Space& home, int n);
104 ExecStatus lec(Space& home, int n);
106 ExecStatus nooverlap(Space& home, int n, int m);
107 public:
109 FlexDim(void);
112
114 int ssc(void) const;
116 int lsc(void) const;
118 int sec(void) const;
120 int lec(void) const;
121
124
126 void update(Space& home, FlexDim& d);
127
129 void subscribe(Space& home, Propagator& p);
131 void cancel(Space& home, Propagator& p);
133 void reschedule(Space& home, Propagator& p);
134 };
135
136}}}
137
139
140namespace Gecode { namespace Int { namespace NoOverlap {
141
145 template<class Dim, int n>
146 class ManBox {
147 protected:
149 Dim d[n];
150 public:
152 const Dim& operator [](int i) const;
154 Dim& operator [](int i);
156 static int dim(void);
157
159 bool mandatory(void) const;
161 bool optional(void) const;
163 bool excluded(void) const;
164
166 ExecStatus exclude(Space& home);
167
169 bool nooverlap(const ManBox<Dim,n>& b) const;
171 bool overlap(const ManBox<Dim,n>& b) const;
172
175
177 void update(Space& home, ManBox<Dim,n>& r);
178
180 void subscribe(Space& home, Propagator& p);
182 void cancel(Space& home, Propagator& p);
184 void reschedule(Space& home, Propagator& p);
185 };
186
190 template<class Dim, int n>
191 class OptBox : public ManBox<Dim,n> {
192 protected:
193 using ManBox<Dim,n>::d;
196 public:
198 void optional(BoolView o);
200 bool mandatory(void) const;
202 bool optional(void) const;
204 bool excluded(void) const;
205
207 ExecStatus exclude(Space& home);
208
210 void update(Space& home, OptBox<Dim,n>& r);
211
213 void subscribe(Space& home, Propagator& p);
215 void cancel(Space& home, Propagator& p);
217 void reschedule(Space& home, Propagator& p);
218 };
219
220}}}
221
223
224namespace Gecode { namespace Int { namespace NoOverlap {
225
233 template<class Box>
234 class Base : public Propagator {
235 protected:
237 Box* b;
239 int n;
241 Base(Home home, Box* b, int n);
243 Base(Space& home, Base<Box>& p, int m);
249 static int partition(Box* b, int i, int n);
250 public:
252 virtual PropCost cost(const Space& home, const ModEventDelta& med) const;
254 virtual void reschedule(Space& home);
256 virtual size_t dispose(Space& home);
257 };
258
266 template<class Box>
267 class ManProp : public Base<Box> {
268 protected:
269 using Base<Box>::b;
270 using Base<Box>::n;
272 ManProp(Home home, Box* b, int n);
274 ManProp(Space& home, ManProp<Box>& p);
275 public:
277 static ExecStatus post(Home home, Box* b, int n);
279 virtual ExecStatus propagate(Space& home, const ModEventDelta& med);
281 virtual Actor* copy(Space& home);
283 virtual size_t dispose(Space& home);
284 };
285
293 template<class Box>
294 class OptProp : public Base<Box> {
295 protected:
296 using Base<Box>::b;
297 using Base<Box>::n;
299 int m;
301 OptProp(Home home, Box* b, int n, int m);
303 OptProp(Space& home, OptProp<Box>& p);
304 public:
306 static ExecStatus post(Home home, Box* b, int n);
308 virtual ExecStatus propagate(Space& home, const ModEventDelta& med);
310 virtual Actor* copy(Space& home);
312 virtual size_t dispose(Space& home);
313 };
314
315}}}
316
320
321#endif
322
323// STATISTICS: int-prop
324
Home class for posting propagators
Definition core.hpp:856
Boolean view for Boolean variables.
Definition view.hpp:1380
Integer view for integer variables.
Definition view.hpp:129
int n
Number of mandatory boxes: b[0] ... b[n-1].
Base(Home home, Box *b, int n)
Constructor for posting with n mandatory boxes.
Definition base.hpp:38
virtual PropCost cost(const Space &home, const ModEventDelta &med) const
Cost function.
Definition base.hpp:77
virtual size_t dispose(Space &home)
Destructor.
Definition base.hpp:59
static int partition(Box *b, int i, int n)
Partition n boxes b starting at position i.
Definition base.hpp:46
virtual void reschedule(Space &home)
Schedule function.
Definition base.hpp:83
void subscribe(Space &home, Propagator &p)
Subscribe propagator p to dimension.
Definition dim.hpp:101
void update(Space &home, FixDim &d)
Update dimension during cloning.
Definition dim.hpp:95
void reschedule(Space &home, Propagator &p)
Schedule propagator p.
Definition dim.hpp:109
int lsc(void) const
Return largest start coordinate.
Definition dim.hpp:52
FixDim(void)
Default constructor.
Definition dim.hpp:41
int ssc(void) const
Return smallest start coordinate.
Definition dim.hpp:48
int sec(void) const
Return smallest end coordinate.
Definition dim.hpp:56
ExecStatus nooverlap(Space &home, int n, int m)
Dimension must not overlap with coordinates n to m.
Definition dim.hpp:75
int lec(void) const
Return largest end coordinate.
Definition dim.hpp:60
void cancel(Space &home, Propagator &p)
Cancel propagator p from dimension.
Definition dim.hpp:105
int ssc(void) const
Return smallest start coordinate.
Definition dim.hpp:125
int lsc(void) const
Return largest start coordinate.
Definition dim.hpp:129
IntView c1
End coordinate.
void subscribe(Space &home, Propagator &p)
Subscribe propagator p to dimension.
Definition dim.hpp:182
int sec(void) const
Return smallest end coordinate.
Definition dim.hpp:133
FlexDim(void)
Default constructor.
Definition dim.hpp:119
ExecStatus nooverlap(Space &home, int n, int m)
Dimension must not overlap with coordinates n to m.
Definition dim.hpp:152
IntView c0
Start coordinate.
Definition no-overlap.hh:96
void reschedule(Space &home, Propagator &p)
Schedule propagator p.
Definition dim.hpp:194
void cancel(Space &home, Propagator &p)
Cancel propagator p from dimension.
Definition dim.hpp:188
void update(Space &home, FlexDim &d)
Update dimension during cloning.
Definition dim.hpp:175
int lec(void) const
Return largest end coordinate.
Definition dim.hpp:137
static int dim(void)
Return number of dimensions.
Definition box.hpp:54
bool nooverlap(const ManBox< Dim, n > &b) const
Check whether this box does not any longer overlap with b.
Definition box.hpp:82
const Dim & operator[](int i) const
Access to dimension i.
Definition box.hpp:42
void reschedule(Space &home, Propagator &p)
Schedule propagator p.
Definition box.hpp:139
void update(Space &home, ManBox< Dim, n > &r)
Update box during cloning.
Definition box.hpp:120
bool overlap(const ManBox< Dim, n > &b) const
Check whether this box overlaps with b.
Definition box.hpp:91
bool excluded(void) const
Whether box is excluded.
Definition box.hpp:65
bool mandatory(void) const
Whether box is mandatory.
Definition box.hpp:60
void subscribe(Space &home, Propagator &p)
Subscribe propagator p to box.
Definition box.hpp:127
bool optional(void) const
Whether box is optional.
Definition box.hpp:70
ExecStatus exclude(Space &home)
Exclude box.
Definition box.hpp:76
void cancel(Space &home, Propagator &p)
Cancel propagator p from box.
Definition box.hpp:133
ManProp(Home home, Box *b, int n)
Constructor for posting.
Definition man.hpp:38
virtual ExecStatus propagate(Space &home, const ModEventDelta &med)
Perform propagation.
Definition man.hpp:70
virtual size_t dispose(Space &home)
Destructor.
Definition man.hpp:51
static ExecStatus post(Home home, Box *b, int n)
Post propagator for boxes b.
Definition man.hpp:43
virtual Actor * copy(Space &home)
Copy propagator during cloning.
Definition man.hpp:64
void update(Space &home, OptBox< Dim, n > &r)
Update box during cloning.
Definition box.hpp:179
BoolView o
Whether box is optional or not.
bool optional(void) const
Whether box is optional.
Definition box.hpp:166
bool mandatory(void) const
Whether box is mandatory.
Definition box.hpp:156
ExecStatus exclude(Space &home)
Exclude box.
Definition box.hpp:172
void reschedule(Space &home, Propagator &p)
Schedule propagator p.
Definition box.hpp:198
void subscribe(Space &home, Propagator &p)
Subscribe propagator p to box.
Definition box.hpp:186
void cancel(Space &home, Propagator &p)
Cancel propagator p from box.
Definition box.hpp:192
bool excluded(void) const
Whether box is excluded.
Definition box.hpp:161
virtual size_t dispose(Space &home)
Destructor.
Definition opt.hpp:57
static ExecStatus post(Home home, Box *b, int n)
Post propagator for boxes b.
Definition opt.hpp:46
virtual ExecStatus propagate(Space &home, const ModEventDelta &med)
Perform propagation.
Definition opt.hpp:78
OptProp(Home home, Box *b, int n, int m)
Constructor for posting.
Definition opt.hpp:38
virtual Actor * copy(Space &home)
Copy propagator during cloning.
Definition opt.hpp:72
int m
Number of optional boxes: b[n] ... b[n+m-1].
Propagation cost.
Definition core.hpp:486
Base-class for propagators.
Definition core.hpp:1066
friend class Space
Definition core.hpp:1068
ModEventDelta med
A set of modification events (used during propagation)
Definition core.hpp:1077
Propagator(Home home)
Constructor for posting.
Definition core.hpp:3505
Computation spaces.
Definition core.hpp:1744
int ModEventDelta
Modification event deltas.
Definition core.hpp:89
No-overlap propagators
Finite domain integers.
Gecode toplevel namespace
Post propagator for SetVar SetOpType SetVar SetRelType r
Definition set.hh:773
ExecStatus
Definition core.hpp:472