Generated on Wed Jul 21 2021 00:00:00 for Gecode by doxygen 1.9.1
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 
44 namespace 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 
140 namespace 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 
224 namespace 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 
struct Gecode::@602::NNF::@65::@66 b
For binary nodes (and, or, eqv)
int p
Number of positive literals for node type.
Definition: bool-expr.cpp:232
int n
Number of negative literals for node type.
Definition: bool-expr.cpp:234
NNF * r
Right subtree.
Definition: bool-expr.cpp:242
Base-class for both propagators and branchers.
Definition: core.hpp:628
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
Base class for no-overlap propagator.
Definition: no-overlap.hh:234
int n
Number of mandatory boxes: b[0] ... b[n-1].
Definition: no-overlap.hh:239
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
Dimension combining coordinate and integer size information.
Definition: no-overlap.hh:49
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
Dimension combining coordinate and integer view size information.
Definition: no-overlap.hh:93
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.
Definition: no-overlap.hh:100
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
Mandatory box class.
Definition: no-overlap.hh:146
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
No-overlap propagator for mandatory boxes.
Definition: no-overlap.hh:267
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.
Definition: no-overlap.hh:195
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
No-overlap propagator for optional boxes.
Definition: no-overlap.hh:294
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].
Definition: no-overlap.hh:299
Propagation cost.
Definition: core.hpp:486
Base-class for propagators.
Definition: core.hpp:1064
ModEventDelta med
A set of modification events (used during propagation)
Definition: core.hpp:1075
Computation spaces.
Definition: core.hpp:1742
ExecStatus
Definition: core.hpp:472
int ModEventDelta
Modification event deltas.
Definition: core.hpp:89
Gecode::IntArgs i({1, 2, 3, 4})
Gecode::IntSet d(v, 7)