Generated on Fri Jul 13 2018 06:08:28 for Gecode by doxygen 1.8.14
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  * Last modified:
10  * $Date: 2016-06-29 17:28:17 +0200 (Wed, 29 Jun 2016) $ by $Author: schulte $
11  * $Revision: 15137 $
12  *
13  * This file is part of Gecode, the generic constraint
14  * development environment:
15  * http://www.gecode.org
16  *
17  * Permission is hereby granted, free of charge, to any person obtaining
18  * a copy of this software and associated documentation files (the
19  * "Software"), to deal in the Software without restriction, including
20  * without limitation the rights to use, copy, modify, merge, publish,
21  * distribute, sublicense, and/or sell copies of the Software, and to
22  * permit persons to whom the Software is furnished to do so, subject to
23  * the following conditions:
24  *
25  * The above copyright notice and this permission notice shall be
26  * included in all copies or substantial portions of the Software.
27  *
28  * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,
29  * EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF
30  * MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND
31  * NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE
32  * LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION
33  * OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION
34  * WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
35  *
36  */
37 
38 #ifndef __GECODE_INT_NO_OVERLAP_HH__
39 #define __GECODE_INT_NO_OVERLAP_HH__
40 
41 #include <gecode/int.hh>
42 
48 namespace Gecode { namespace Int { namespace NoOverlap {
49 
53  class FixDim {
54  protected:
58  int s;
60  ExecStatus ssc(Space& home, int n);
62  ExecStatus lec(Space& home, int n);
64  ExecStatus nooverlap(Space& home, int n, int m);
65  public:
67  FixDim(void);
69  FixDim(IntView c, int s);
70 
72  int ssc(void) const;
74  int lsc(void) const;
76  int sec(void) const;
78  int lec(void) const;
79 
82 
84  void update(Space& home, bool share, FixDim& d);
85 
87  void subscribe(Space& home, Propagator& p);
89  void cancel(Space& home, Propagator& p);
91  void reschedule(Space& home, Propagator& p);
92  };
93 
97  class FlexDim {
98  protected:
106  ExecStatus ssc(Space& home, int n);
108  ExecStatus lec(Space& home, int n);
110  ExecStatus nooverlap(Space& home, int n, int m);
111  public:
113  FlexDim(void);
116 
118  int ssc(void) const;
120  int lsc(void) const;
122  int sec(void) const;
124  int lec(void) const;
125 
128 
130  void update(Space& home, bool share, FlexDim& d);
131 
133  void subscribe(Space& home, Propagator& p);
135  void cancel(Space& home, Propagator& p);
137  void reschedule(Space& home, Propagator& p);
138  };
139 
140 }}}
141 
143 
144 namespace Gecode { namespace Int { namespace NoOverlap {
145 
149  template<class Dim, int n>
150  class ManBox {
151  protected:
153  Dim d[n];
154  public:
156  const Dim& operator [](int i) const;
158  Dim& operator [](int i);
160  static int dim(void);
161 
163  bool mandatory(void) const;
165  bool optional(void) const;
167  bool excluded(void) const;
168 
170  ExecStatus exclude(Space& home);
171 
173  bool nooverlap(const ManBox<Dim,n>& b) const;
175  bool overlap(const ManBox<Dim,n>& b) const;
176 
179 
181  void update(Space& home, bool share, ManBox<Dim,n>& r);
182 
184  void subscribe(Space& home, Propagator& p);
186  void cancel(Space& home, Propagator& p);
188  void reschedule(Space& home, Propagator& p);
189  };
190 
194  template<class Dim, int n>
195  class OptBox : public ManBox<Dim,n> {
196  protected:
197  using ManBox<Dim,n>::d;
200  public:
202  void optional(BoolView o);
204  bool mandatory(void) const;
206  bool optional(void) const;
208  bool excluded(void) const;
209 
211  ExecStatus exclude(Space& home);
212 
214  void update(Space& home, bool share, OptBox<Dim,n>& r);
215 
217  void subscribe(Space& home, Propagator& p);
219  void cancel(Space& home, Propagator& p);
221  void reschedule(Space& home, Propagator& p);
222  };
223 
224 }}}
225 
227 
228 namespace Gecode { namespace Int { namespace NoOverlap {
229 
237  template<class Box>
238  class Base : public Propagator {
239  protected:
241  Box* b;
243  int n;
245  Base(Home home, Box* b, int n);
247  Base(Space& home, bool share, Base<Box>& p, int m);
253  static int partition(Box* b, int i, int n);
254  public:
256  virtual PropCost cost(const Space& home, const ModEventDelta& med) const;
258  virtual void reschedule(Space& home);
260  virtual size_t dispose(Space& home);
261  };
262 
270  template<class Box>
271  class ManProp : public Base<Box> {
272  protected:
273  using Base<Box>::b;
274  using Base<Box>::n;
276  ManProp(Home home, Box* b, int n);
278  ManProp(Space& home, bool share, ManProp<Box>& p);
279  public:
281  static ExecStatus post(Home home, Box* b, int n);
283  virtual ExecStatus propagate(Space& home, const ModEventDelta& med);
285  virtual Actor* copy(Space& home, bool share);
287  virtual size_t dispose(Space& home);
288  };
289 
297  template<class Box>
298  class OptProp : public Base<Box> {
299  protected:
300  using Base<Box>::b;
301  using Base<Box>::n;
303  int m;
305  OptProp(Home home, Box* b, int n, int m);
307  OptProp(Space& home, bool share, OptProp<Box>& p);
308  public:
310  static ExecStatus post(Home home, Box* b, int n);
312  virtual ExecStatus propagate(Space& home, const ModEventDelta& med);
314  virtual Actor* copy(Space& home, bool share);
316  virtual size_t dispose(Space& home);
317  };
318 
319 }}}
320 
324 
325 #endif
326 
327 // STATISTICS: int-prop
328 
bool excluded(void) const
Whether box is excluded.
Definition: box.hpp:69
void subscribe(Space &home, Propagator &p)
Subscribe propagator p to dimension.
Definition: dim.hpp:186
void subscribe(Space &home, Propagator &p)
Subscribe propagator p to dimension.
Definition: dim.hpp:105
IntView c
Coordinate.
Definition: no-overlap.hh:56
virtual Actor * copy(Space &home, bool share)
Copy propagator during cloning.
Definition: opt.hpp:76
void reschedule(Space &home, Propagator &p)
Schedule propagator p.
Definition: dim.hpp:198
int ssc(void) const
Return smallest start coordinate.
Definition: dim.hpp:52
virtual size_t dispose(Space &home)
Destructor.
Definition: opt.hpp:61
virtual size_t dispose(Space &home)
Destructor.
Definition: base.hpp:63
ExecStatus nooverlap(Space &home, int n, int m)
Dimension must not overlap with coordinates n to m.
Definition: dim.hpp:79
bool mandatory(void) const
Whether box is mandatory.
Definition: box.hpp:160
Base-class for propagators.
Definition: core.hpp:1092
virtual ExecStatus propagate(Space &home, const ModEventDelta &med)
Perform propagation.
Definition: opt.hpp:82
static ExecStatus post(Home home, Box *b, int n)
Post propagator for boxes b.
Definition: man.hpp:47
static int dim(void)
Return number of dimensions.
Definition: box.hpp:58
void cancel(Space &home, Propagator &p)
Cancel propagator p from box.
Definition: box.hpp:196
bool nooverlap(const ManBox< Dim, n > &b) const
Check whether this box does not any longer overlap with b.
Definition: box.hpp:86
Optional box class.
Definition: no-overlap.hh:195
No-overlap propagator for mandatory boxes.
Definition: no-overlap.hh:271
bool overlap(const ManBox< Dim, n > &b) const
Check whether this box overlaps with b.
Definition: box.hpp:95
Computation spaces.
Definition: core.hpp:1748
virtual void reschedule(Space &home)
Schedule function.
Definition: base.hpp:87
virtual ExecStatus propagate(Space &home, const ModEventDelta &med)
Perform propagation.
Definition: man.hpp:74
Base-class for both propagators and branchers.
Definition: core.hpp:696
int m
Number of optional boxes: b[n] ... b[n+m-1].
Definition: no-overlap.hh:303
Gecode::IntSet d(v, 7)
bool mandatory(void) const
Whether box is mandatory.
Definition: box.hpp:64
void reschedule(Space &home, Propagator &p)
Schedule propagator p.
Definition: box.hpp:143
void update(Space &home, bool share, ManBox< Dim, n > &r)
Update box during cloning.
Definition: box.hpp:124
int p
Number of positive literals for node type.
Definition: bool-expr.cpp:236
void subscribe(Space &home, Propagator &p)
Subscribe propagator p to box.
Definition: box.hpp:131
Gecode::IntArgs i(4, 1, 2, 3, 4)
int n
Number of negative literals for node type.
Definition: bool-expr.cpp:238
FlexDim(void)
Default constructor.
Definition: dim.hpp:123
bool excluded(void) const
Whether box is excluded.
Definition: box.hpp:165
FixDim(void)
Default constructor.
Definition: dim.hpp:45
ModEventDelta med
A set of modification events (used during propagation)
Definition: core.hpp:1103
ExecStatus nooverlap(Space &home, int n, int m)
Dimension must not overlap with coordinates n to m.
Definition: dim.hpp:156
int lec(void) const
Return largest end coordinate.
Definition: dim.hpp:64
virtual Actor * copy(Space &home, bool share)
Copy propagator during cloning.
Definition: man.hpp:68
struct Gecode::@579::NNF::@61::@62 b
For binary nodes (and, or, eqv)
IntView c0
Start coordinate.
Definition: no-overlap.hh:100
OptProp(Home home, Box *b, int n, int m)
Constructor for posting.
Definition: opt.hpp:42
int sec(void) const
Return smallest end coordinate.
Definition: dim.hpp:137
void subscribe(Space &home, Propagator &p)
Subscribe propagator p to box.
Definition: box.hpp:190
Dimension combining coordinate and integer view size information.
Definition: no-overlap.hh:97
void update(Space &home, bool share, FlexDim &d)
Update dimension during cloning.
Definition: dim.hpp:179
ExecStatus exclude(Space &home)
Exclude box.
Definition: box.hpp:176
IntView c1
End coordinate.
Definition: no-overlap.hh:104
No-overlap propagator for optional boxes.
Definition: no-overlap.hh:298
Dimension combining coordinate and integer size information.
Definition: no-overlap.hh:53
void reschedule(Space &home, Propagator &p)
Schedule propagator p.
Definition: box.hpp:202
Post propagator for SetVar SetOpType SetVar SetRelType r
Definition: set.hh:784
Base(Home home, Box *b, int n)
Constructor for posting with n mandatory boxes.
Definition: base.hpp:42
Integer view for integer variables.
Definition: view.hpp:129
void update(Space &home, bool share, FixDim &d)
Update dimension during cloning.
Definition: dim.hpp:99
static ExecStatus post(Home home, Box *b, int n)
Post propagator for boxes b.
Definition: opt.hpp:50
Propagation cost.
Definition: core.hpp:554
void reschedule(Space &home, Propagator &p)
Schedule propagator p.
Definition: dim.hpp:113
ExecStatus
Definition: core.hpp:540
bool optional(void) const
Whether box is optional.
Definition: box.hpp:74
virtual size_t dispose(Space &home)
Destructor.
Definition: man.hpp:55
Base class for no-overlap propagator.
Definition: no-overlap.hh:238
int lsc(void) const
Return largest start coordinate.
Definition: dim.hpp:56
void update(Space &home, bool share, OptBox< Dim, n > &r)
Update box during cloning.
Definition: box.hpp:183
int n
Number of mandatory boxes: b[0] ... b[n-1].
Definition: no-overlap.hh:243
const Dim & operator[](int i) const
Access to dimension i.
Definition: box.hpp:46
int sec(void) const
Return smallest end coordinate.
Definition: dim.hpp:60
BoolView o
Whether box is optional or not.
Definition: no-overlap.hh:199
static int partition(Box *b, int i, int n)
Partition n boxes b starting at position i.
Definition: base.hpp:50
virtual PropCost cost(const Space &home, const ModEventDelta &med) const
Cost function.
Definition: base.hpp:81
Gecode toplevel namespace
Mandatory box class.
Definition: no-overlap.hh:150
bool optional(void) const
Whether box is optional.
Definition: box.hpp:170
int lec(void) const
Return largest end coordinate.
Definition: dim.hpp:141
ExecStatus exclude(Space &home)
Exclude box.
Definition: box.hpp:80
int ModEventDelta
Modification event deltas.
Definition: core.hpp:169
void cancel(Space &home, Propagator &p)
Cancel propagator p from box.
Definition: box.hpp:137
Home class for posting propagators
Definition: core.hpp:922
ManProp(Home home, Box *b, int n)
Constructor for posting.
Definition: man.hpp:42
int lsc(void) const
Return largest start coordinate.
Definition: dim.hpp:133
int ssc(void) const
Return smallest start coordinate.
Definition: dim.hpp:129
void cancel(Space &home, Propagator &p)
Cancel propagator p from dimension.
Definition: dim.hpp:192
void cancel(Space &home, Propagator &p)
Cancel propagator p from dimension.
Definition: dim.hpp:109
Boolean view for Boolean variables.
Definition: view.hpp:1315