Generated on Wed Jan 24 2018 21:22:26 for Gecode by doxygen 1.8.13
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);
115  FlexDim(IntView c0, IntView s, IntView c1);
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 
void subscribe(Space &home, Propagator &p)
Subscribe propagator p to dimension.
Definition: dim.hpp:105
IntView c
Coordinate.
Definition: no-overlap.hh:56
int ssc(void) const
Return smallest start coordinate.
Definition: dim.hpp:52
bool overlap(const FloatVal &x, const FloatVal &y)
Definition: val.hpp:502
ExecStatus nooverlap(Space &home, int n, int m)
Dimension must not overlap with coordinates n to m.
Definition: dim.hpp:79
Base-class for propagators.
Definition: core.hpp:1092
Type * partition(Type *l, Type *r, Less &less)
Standard partioning.
Definition: sort.hpp:117
Optional box class.
Definition: no-overlap.hh:195
No-overlap propagator for mandatory boxes.
Definition: no-overlap.hh:271
Computation spaces.
Definition: core.hpp:1748
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
ModEvent exclude(Space &home, View &x, int s)
Prune view x to exclude all values from s.
Definition: set-op.hpp:141
Gecode::IntSet d(v, 7)
int p
Number of positive literals for node type.
Definition: bool-expr.cpp:236
Gecode::IntArgs i(4, 1, 2, 3, 4)
int n
Number of negative literals for node type.
Definition: bool-expr.cpp:238
FixDim(void)
Default constructor.
Definition: dim.hpp:45
int lec(void) const
Return largest end coordinate.
Definition: dim.hpp:64
struct Gecode::@579::NNF::@61::@62 b
For binary nodes (and, or, eqv)
IntView c0
Start coordinate.
Definition: no-overlap.hh:100
Dimension combining coordinate and integer view size information.
Definition: no-overlap.hh:97
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
Post propagator for SetVar SetOpType SetVar SetRelType r
Definition: set.hh:784
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
Propagation cost.
Definition: core.hpp:554
void reschedule(Space &home, Propagator &p)
Schedule propagator p.
Definition: dim.hpp:113
ExecStatus
Definition: core.hpp:540
Base class for no-overlap propagator.
Definition: no-overlap.hh:238
int lsc(void) const
Return largest start coordinate.
Definition: dim.hpp:56
int n
Number of mandatory boxes: b[0] ... b[n-1].
Definition: no-overlap.hh:243
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
Gecode toplevel namespace
Mandatory box class.
Definition: no-overlap.hh:150
bool optional(const BoolVarArgs &m)
Definition: no-overlap.cpp:45
int ModEventDelta
Modification event deltas.
Definition: core.hpp:169
Home class for posting propagators
Definition: core.hpp:922
TFE post(PropagatorGroup g)
Only post functions (but not propagators) from g are considered.
void cancel(Space &home, Propagator &p)
Cancel propagator p from dimension.
Definition: dim.hpp:109
Boolean view for Boolean variables.
Definition: view.hpp:1315