Generated on Sat Feb 7 2015 02:01:25 for Gecode by doxygen 1.8.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  * Last modified:
10  * $Date: 2012-09-10 19:36:08 +0200 (Mon, 10 Sep 2012) $ by $Author: schulte $
11  * $Revision: 13072 $
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);
90  };
91 
95  class FlexDim {
96  protected:
104  ExecStatus ssc(Space& home, int n);
106  ExecStatus lec(Space& home, int n);
108  ExecStatus nooverlap(Space& home, int n, int m);
109  public:
111  FlexDim(void);
113  FlexDim(IntView c0, IntView s, IntView c1);
114 
116  int ssc(void) const;
118  int lsc(void) const;
120  int sec(void) const;
122  int lec(void) const;
123 
126 
128  void update(Space& home, bool share, FlexDim& d);
129 
131  void subscribe(Space& home, Propagator& p);
133  void cancel(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, bool share, ManBox<Dim,n>& r);
178 
180  void subscribe(Space& home, Propagator& p);
182  void cancel(Space& home, Propagator& p);
183  };
184 
188  template<class Dim, int n>
189  class OptBox : public ManBox<Dim,n> {
190  protected:
191  using ManBox<Dim,n>::d;
194  public:
196  void optional(BoolView o);
198  bool mandatory(void) const;
200  bool optional(void) const;
202  bool excluded(void) const;
203 
205  ExecStatus exclude(Space& home);
206 
208  void update(Space& home, bool share, OptBox<Dim,n>& r);
209 
211  void subscribe(Space& home, Propagator& p);
213  void cancel(Space& home, Propagator& p);
214  };
215 
216 }}}
217 
219 
220 namespace Gecode { namespace Int { namespace NoOverlap {
221 
229  template<class Box>
230  class Base : public Propagator {
231  protected:
233  Box* b;
235  int n;
237  Base(Home home, Box* b, int n);
239  Base(Space& home, bool share, Base<Box>& p, int m);
245  static int partition(Box* b, int i, int n);
246  public:
248  virtual PropCost cost(const Space& home, const ModEventDelta& med) const;
250  virtual size_t dispose(Space& home);
251  };
252 
260  template<class Box>
261  class ManProp : public Base<Box> {
262  protected:
263  using Base<Box>::b;
264  using Base<Box>::n;
266  ManProp(Home home, Box* b, int n);
268  ManProp(Space& home, bool share, ManProp<Box>& p);
269  public:
271  static ExecStatus post(Home home, Box* b, int n);
273  virtual ExecStatus propagate(Space& home, const ModEventDelta& med);
275  virtual Actor* copy(Space& home, bool share);
277  virtual size_t dispose(Space& home);
278  };
279 
287  template<class Box>
288  class OptProp : public Base<Box> {
289  protected:
290  using Base<Box>::b;
291  using Base<Box>::n;
293  int m;
295  OptProp(Home home, Box* b, int n, int m);
297  OptProp(Space& home, bool share, OptProp<Box>& p);
298  public:
300  static ExecStatus post(Home home, Box* b, int n);
302  virtual ExecStatus propagate(Space& home, const ModEventDelta& med);
304  virtual Actor* copy(Space& home, bool share);
306  virtual size_t dispose(Space& home);
307  };
308 
309 }}}
310 
314 
315 #endif
316 
317 // STATISTICS: int-prop
318 
void subscribe(Space &home, Propagator &p)
Subscribe propagator p to dimension.
Definition: dim.hpp:182
bool mandatory(void) const
Whether box is mandatory.
Definition: box.hpp:64
void subscribe(Space &home, Propagator &p)
Subscribe propagator p to dimension.
Definition: dim.hpp:105
IntView c
Coordinate.
Definition: no-overlap.hh:56
const Dim & operator[](int i) const
Access to dimension i.
Definition: box.hpp:46
virtual Actor * copy(Space &home, bool share)
Copy propagator during cloning.
Definition: opt.hpp:76
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 overlap(const ManBox< Dim, n > &b) const
Check whether this box overlaps with b.
Definition: box.hpp:95
Base-class for propagators.
Definition: core.hpp:755
bool excluded(void) const
Whether box is excluded.
Definition: box.hpp:69
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:190
Optional box class.
Definition: no-overlap.hh:189
No-overlap propagator for mandatory boxes.
Definition: no-overlap.hh:261
int ssc(void) const
Return smallest start coordinate.
Definition: dim.hpp:125
Computation spaces.
Definition: core.hpp:1362
virtual ExecStatus propagate(Space &home, const ModEventDelta &med)
Perform propagation.
Definition: man.hpp:74
Base-class for both propagators and branchers.
Definition: core.hpp:666
int m
Number of optional boxes: b[n] ... b[n+m-1].
Definition: no-overlap.hh:293
Gecode::IntSet d(v, 7)
bool optional(void) const
Whether box is optional.
Definition: box.hpp:74
void update(Space &home, bool share, ManBox< Dim, n > &r)
Update box during cloning.
Definition: box.hpp:124
int lsc(void) const
Return largest start coordinate.
Definition: dim.hpp:56
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:119
FixDim(void)
Default constructor.
Definition: dim.hpp:45
NNF * r
Right subtree.
Definition: bool-expr.cpp:246
ModEventDelta med
A set of modification events (used during propagation)
Definition: core.hpp:764
ExecStatus nooverlap(Space &home, int n, int m)
Dimension must not overlap with coordinates n to m.
Definition: dim.hpp:152
virtual Actor * copy(Space &home, bool share)
Copy propagator during cloning.
Definition: man.hpp:68
IntView c0
Start coordinate.
Definition: no-overlap.hh:98
bool optional(void) const
Whether box is optional.
Definition: box.hpp:164
virtual PropCost cost(const Space &home, const ModEventDelta &med) const
Cost function.
Definition: base.hpp:81
OptProp(Home home, Box *b, int n, int m)
Constructor for posting.
Definition: opt.hpp:42
void subscribe(Space &home, Propagator &p)
Subscribe propagator p to box.
Definition: box.hpp:184
Dimension combining coordinate and integer view size information.
Definition: no-overlap.hh:95
void update(Space &home, bool share, FlexDim &d)
Update dimension during cloning.
Definition: dim.hpp:175
ExecStatus exclude(Space &home)
Exclude box.
Definition: box.hpp:170
IntView c1
End coordinate.
Definition: no-overlap.hh:102
No-overlap propagator for optional boxes.
Definition: no-overlap.hh:288
Dimension combining coordinate and integer size information.
Definition: no-overlap.hh:53
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:537
ExecStatus
Definition: core.hpp:523
virtual size_t dispose(Space &home)
Destructor.
Definition: man.hpp:55
int lsc(void) const
Return largest start coordinate.
Definition: dim.hpp:129
Base class for no-overlap propagator.
Definition: no-overlap.hh:230
int ssc(void) const
Return smallest start coordinate.
Definition: dim.hpp:52
void update(Space &home, bool share, OptBox< Dim, n > &r)
Update box during cloning.
Definition: box.hpp:177
int n
Number of mandatory boxes: b[0] ... b[n-1].
Definition: no-overlap.hh:235
bool nooverlap(const ManBox< Dim, n > &b) const
Check whether this box does not any longer overlap with b.
Definition: box.hpp:86
bool excluded(void) const
Whether box is excluded.
Definition: box.hpp:159
BoolView o
Whether box is optional or not.
Definition: no-overlap.hh:193
static int partition(Box *b, int i, int n)
Partition n boxes b starting at position i.
Definition: base.hpp:50
struct Gecode::@518::NNF::@57::@58 b
For binary nodes (and, or, eqv)
Gecode toplevel namespace
int sec(void) const
Return smallest end coordinate.
Definition: dim.hpp:60
int sec(void) const
Return smallest end coordinate.
Definition: dim.hpp:133
Mandatory box class.
Definition: no-overlap.hh:146
ExecStatus exclude(Space &home)
Exclude box.
Definition: box.hpp:80
int ModEventDelta
Modification event deltas.
Definition: core.hpp:173
void cancel(Space &home, Propagator &p)
Cancel propagator p from box.
Definition: box.hpp:137
Home class for posting propagators
Definition: core.hpp:717
ManProp(Home home, Box *b, int n)
Constructor for posting.
Definition: man.hpp:42
int lec(void) const
Return largest end coordinate.
Definition: dim.hpp:137
bool mandatory(void) const
Whether box is mandatory.
Definition: box.hpp:154
int lec(void) const
Return largest end coordinate.
Definition: dim.hpp:64
void cancel(Space &home, Propagator &p)
Cancel propagator p from dimension.
Definition: dim.hpp:188
void cancel(Space &home, Propagator &p)
Cancel propagator p from dimension.
Definition: dim.hpp:109
Boolean view for Boolean variables.
Definition: view.hpp:1315