Generated on Mon Jul 27 2020 00:00:00 for Gecode by doxygen 1.8.18
no-overlap.cpp
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 #include <gecode/int/no-overlap.hh>
35 
36 namespace Gecode {
37 
38  namespace Int { namespace NoOverlap {
39 
40  bool
41  optional(const BoolVarArgs& m) {
42  for (int i=0; i<m.size(); i++)
43  if (m[i].none())
44  return true;
45  return false;
46  }
47 
48  }}
49 
50  void
52  const IntVarArgs& x, const IntArgs& w,
53  const IntVarArgs& y, const IntArgs& h,
54  IntPropLevel) {
55  using namespace Int;
56  using namespace NoOverlap;
57  if ((x.size() != w.size()) || (x.size() != y.size()) ||
58  (x.size() != h.size()))
59  throw ArgumentSizeMismatch("Int::nooverlap");
60  for (int i=0; i<x.size(); i++) {
61  Limits::nonnegative(w[i],"Int::nooverlap");
62  Limits::nonnegative(h[i],"Int::nooverlap");
63  Limits::check(static_cast<long long int>(x[i].max()) + w[i],
64  "Int::nooverlap");
65  Limits::check(static_cast<long long int>(y[i].max()) + h[i],
66  "Int::nooverlap");
67  }
69 
70  ManBox<FixDim,2>* b
71  = static_cast<Space&>(home).alloc<ManBox<FixDim,2> >(x.size());
72  for (int i=0; i<x.size(); i++) {
73  b[i][0] = FixDim(x[i],w[i]);
74  b[i][1] = FixDim(y[i],h[i]);
75  }
76 
78  NoOverlap::ManProp<ManBox<FixDim,2> >::post(home,b,x.size())));
79  }
80 
81  void
83  const IntVarArgs& x, const IntArgs& w,
84  const IntVarArgs& y, const IntArgs& h,
85  const BoolVarArgs& m,
86  IntPropLevel) {
87  using namespace Int;
88  using namespace NoOverlap;
89  if ((x.size() != w.size()) || (x.size() != y.size()) ||
90  (x.size() != h.size()) || (x.size() != m.size()))
91  throw ArgumentSizeMismatch("Int::nooverlap");
92  for (int i=0; i<x.size(); i++) {
93  Limits::nonnegative(w[i],"Int::nooverlap");
94  Limits::nonnegative(h[i],"Int::nooverlap");
95  Limits::check(static_cast<long long int>(x[i].max()) + w[i],
96  "Int::nooverlap");
97  Limits::check(static_cast<long long int>(y[i].max()) + h[i],
98  "Int::nooverlap");
99  }
100  GECODE_POST;
101 
102  if (optional(m)) {
103  OptBox<FixDim,2>* b
104  = static_cast<Space&>(home).alloc<OptBox<FixDim,2> >(x.size());
105  for (int i=0; i<x.size(); i++) {
106  b[i][0] = FixDim(x[i],w[i]);
107  b[i][1] = FixDim(y[i],h[i]);
108  b[i].optional(m[i]);
109  }
111  NoOverlap::OptProp<OptBox<FixDim,2> >::post(home,b,x.size())));
112  } else {
113  ManBox<FixDim,2>* b
114  = static_cast<Space&>(home).alloc<ManBox<FixDim,2> >(x.size());
115  int n = 0;
116  for (int i=0; i<x.size(); i++)
117  if (m[i].one()) {
118  b[n][0] = FixDim(x[i],w[i]);
119  b[n][1] = FixDim(y[i],h[i]);
120  n++;
121  }
122  GECODE_ES_FAIL((NoOverlap::ManProp<ManBox<FixDim,2> >::post(home,b,n)));
123  }
124  }
125 
126  void
128  const IntVarArgs& x0, const IntVarArgs& w, const IntVarArgs& x1,
129  const IntVarArgs& y0, const IntVarArgs& h, const IntVarArgs& y1,
130  IntPropLevel) {
131  using namespace Int;
132  using namespace NoOverlap;
133  if ((x0.size() != w.size()) || (x0.size() != x1.size()) ||
134  (x0.size() != y0.size()) || (x0.size() != h.size()) ||
135  (x0.size() != y1.size()))
136  throw ArgumentSizeMismatch("Int::nooverlap");
137  GECODE_POST;
138 
139  for (int i=0; i<x0.size(); i++) {
140  GECODE_ME_FAIL(IntView(w[i]).gq(home,0));
141  GECODE_ME_FAIL(IntView(h[i]).gq(home,0));
142  }
143 
144  if (w.assigned() && h.assigned()) {
145  IntArgs wc(x0.size()), hc(x0.size());
146  for (int i=0; i<x0.size(); i++) {
147  wc[i] = w[i].val();
148  hc[i] = h[i].val();
149  }
150  nooverlap(home, x0, wc, y0, hc);
151  } else {
152  ManBox<FlexDim,2>* b
153  = static_cast<Space&>(home).alloc<ManBox<FlexDim,2> >(x0.size());
154  for (int i=0; i<x0.size(); i++) {
155  b[i][0] = FlexDim(x0[i],w[i],x1[i]);
156  b[i][1] = FlexDim(y0[i],h[i],y1[i]);
157  }
159  NoOverlap::ManProp<ManBox<FlexDim,2> >::post(home,b,x0.size())));
160  }
161  }
162 
163  void
165  const IntVarArgs& x0, const IntVarArgs& w, const IntVarArgs& x1,
166  const IntVarArgs& y0, const IntVarArgs& h, const IntVarArgs& y1,
167  const BoolVarArgs& m,
168  IntPropLevel) {
169  using namespace Int;
170  using namespace NoOverlap;
171  if ((x0.size() != w.size()) || (x0.size() != x1.size()) ||
172  (x0.size() != y0.size()) || (x0.size() != h.size()) ||
173  (x0.size() != y1.size()) || (x0.size() != m.size()))
174  throw ArgumentSizeMismatch("Int::nooverlap");
175  GECODE_POST;
176 
177  for (int i=0; i<x0.size(); i++) {
178  GECODE_ME_FAIL(IntView(w[i]).gq(home,0));
179  GECODE_ME_FAIL(IntView(h[i]).gq(home,0));
180  }
181 
182  if (w.assigned() && h.assigned()) {
183  IntArgs wc(x0.size()), hc(x0.size());
184  for (int i=0; i<x0.size(); i++) {
185  wc[i] = w[i].val();
186  hc[i] = h[i].val();
187  }
188  nooverlap(home, x0, wc, y0, hc, m);
189  } else if (optional(m)) {
190  OptBox<FlexDim,2>* b
191  = static_cast<Space&>(home).alloc<OptBox<FlexDim,2> >(x0.size());
192  for (int i=0; i<x0.size(); i++) {
193  b[i][0] = FlexDim(x0[i],w[i],x1[i]);
194  b[i][1] = FlexDim(y0[i],h[i],y1[i]);
195  b[i].optional(m[i]);
196  }
198  NoOverlap::OptProp<OptBox<FlexDim,2> >::post(home,b,x0.size())));
199  } else {
200  ManBox<FlexDim,2>* b
201  = static_cast<Space&>(home).alloc<ManBox<FlexDim,2> >(x0.size());
202  int n = 0;
203  for (int i=0; i<x0.size(); i++)
204  if (m[i].one()) {
205  b[n][0] = FlexDim(x0[i],w[i],x1[i]);
206  b[n][1] = FlexDim(y0[i],h[i],y1[i]);
207  n++;
208  }
209  GECODE_ES_FAIL((NoOverlap::ManProp<ManBox<FlexDim,2> >::post(home,b,n)));
210  }
211  }
212 
213 }
214 
215 // STATISTICS: int-post
Post propagator for SetVar x
Definition: set.hh:767
Exception: Arguments are of different size
Definition: exception.hpp:73
Post propagator for SetVar SetOpType SetVar y
Definition: set.hh:767
#define GECODE_ES_FAIL(es)
Check whether execution status es is failed, and fail space home.
Definition: macros.hpp:103
bool optional(const BoolVarArgs &m)
Definition: no-overlap.cpp:41
void max(Home home, FloatVar x0, FloatVar x1, FloatVar x2)
Post propagator for .
Definition: arithmetic.cpp:49
Passing integer variables.
Definition: int.hh:656
bool assigned(void) const
Test if all variables are assigned.
Definition: array.hpp:1923
void check(int n, const char *l)
Check whether n is in range, otherwise throw out of limits with information l.
Definition: limits.hpp:46
IntPropLevel
Propagation levels for integer propagators.
Definition: int.hh:974
Computation spaces.
Definition: core.hpp:1742
Gecode toplevel namespace
Passing Boolean variables.
Definition: int.hh:712
Home class for posting propagators
Definition: core.hpp:856
TFE post(PropagatorGroup g)
Only post functions (but not propagators) from g are considered.
Definition: filter.cpp:138
void nonnegative(int n, const char *l)
Check whether n is in range and nonnegative, otherwise throw out of limits with information l.
Definition: limits.hpp:68
bool one(const Gecode::FloatValArgs &a)
Check whether has only one coefficients.
Definition: linear.cpp:46
struct Gecode::@602::NNF::@65::@66 b
For binary nodes (and, or, eqv)
No-overlap propagator for optional boxes.
Definition: no-overlap.hh:294
No-overlap propagator for mandatory boxes.
Definition: no-overlap.hh:267
#define GECODE_POST
Check for failure in a constraint post function.
Definition: macros.hpp:40
Integer view for integer variables.
Definition: view.hpp:129
#define GECODE_ME_FAIL(me)
Check whether modification event me is failed, and fail space home.
Definition: macros.hpp:77
void nooverlap(Home home, const IntVarArgs &x, const IntArgs &w, const IntVarArgs &y, const IntArgs &h, IntPropLevel)
Post propagator for rectangle packing.
Definition: no-overlap.cpp:51
int n
Number of negative literals for node type.
Definition: bool-expr.cpp:234
Passing integer arguments.
Definition: int.hh:628
Gecode::IntArgs i({1, 2, 3, 4})