Generated on Sat Feb 7 2015 02:01:24 for Gecode by doxygen 1.8.9.1
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  * Last modified:
10  * $Date: 2013-02-14 16:29:11 +0100 (Thu, 14 Feb 2013) $ by $Author: schulte $
11  * $Revision: 13292 $
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 #include <gecode/int/no-overlap.hh>
39 
40 namespace Gecode {
41 
42  namespace Int { namespace NoOverlap {
43 
44  bool
45  optional(const BoolVarArgs& m) {
46  for (int i=m.size(); i--; )
47  if (m[i].none())
48  return true;
49  return false;
50  }
51 
52  }}
53 
54  void
55  nooverlap(Home home,
56  const IntVarArgs& x, const IntArgs& w,
57  const IntVarArgs& y, const IntArgs& h,
58  IntConLevel) {
59  using namespace Int;
60  using namespace NoOverlap;
61  if ((x.size() != w.size()) || (x.size() != y.size()) ||
62  (x.size() != h.size()))
63  throw ArgumentSizeMismatch("Int::nooverlap");
64  for (int i=x.size(); i--; ) {
65  Limits::nonnegative(w[i],"Int::nooverlap");
66  Limits::nonnegative(h[i],"Int::nooverlap");
67  Limits::check(static_cast<long long int>(x[i].max()) + w[i],
68  "Int::nooverlap");
69  Limits::check(static_cast<long long int>(y[i].max()) + h[i],
70  "Int::nooverlap");
71  }
72  if (home.failed()) return;
73 
74  ManBox<FixDim,2>* b
75  = static_cast<Space&>(home).alloc<ManBox<FixDim,2> >(x.size());
76  for (int i=x.size(); i--; ) {
77  b[i][0] = FixDim(x[i],w[i]);
78  b[i][1] = FixDim(y[i],h[i]);
79  }
80 
82  NoOverlap::ManProp<ManBox<FixDim,2> >::post(home,b,x.size())));
83  }
84 
85  void
86  nooverlap(Home home,
87  const IntVarArgs& x, const IntArgs& w,
88  const IntVarArgs& y, const IntArgs& h,
89  const BoolVarArgs& m,
90  IntConLevel) {
91  using namespace Int;
92  using namespace NoOverlap;
93  if ((x.size() != w.size()) || (x.size() != y.size()) ||
94  (x.size() != h.size()) || (x.size() != m.size()))
95  throw ArgumentSizeMismatch("Int::nooverlap");
96  for (int i=x.size(); i--; ) {
97  Limits::nonnegative(w[i],"Int::nooverlap");
98  Limits::nonnegative(h[i],"Int::nooverlap");
99  Limits::check(static_cast<long long int>(x[i].max()) + w[i],
100  "Int::nooverlap");
101  Limits::check(static_cast<long long int>(y[i].max()) + h[i],
102  "Int::nooverlap");
103  }
104  if (home.failed()) return;
105 
106  if (optional(m)) {
107  OptBox<FixDim,2>* b
108  = static_cast<Space&>(home).alloc<OptBox<FixDim,2> >(x.size());
109  for (int i=x.size(); i--; ) {
110  b[i][0] = FixDim(x[i],w[i]);
111  b[i][1] = FixDim(y[i],h[i]);
112  b[i].optional(m[i]);
113  }
115  NoOverlap::OptProp<OptBox<FixDim,2> >::post(home,b,x.size())));
116  } else {
117  ManBox<FixDim,2>* b
118  = static_cast<Space&>(home).alloc<ManBox<FixDim,2> >(x.size());
119  int n = 0;
120  for (int i=0; i<x.size(); i++)
121  if (m[i].one()) {
122  b[n][0] = FixDim(x[i],w[i]);
123  b[n][1] = FixDim(y[i],h[i]);
124  n++;
125  }
126  GECODE_ES_FAIL((NoOverlap::ManProp<ManBox<FixDim,2> >::post(home,b,n)));
127  }
128  }
129 
130  void
132  const IntVarArgs& x0, const IntVarArgs& w, const IntVarArgs& x1,
133  const IntVarArgs& y0, const IntVarArgs& h, const IntVarArgs& y1,
134  IntConLevel) {
135  using namespace Int;
136  using namespace NoOverlap;
137  if ((x0.size() != w.size()) || (x0.size() != x1.size()) ||
138  (x0.size() != y0.size()) || (x0.size() != h.size()) ||
139  (x0.size() != y1.size()))
140  throw ArgumentSizeMismatch("Int::nooverlap");
141  if (home.failed()) return;
142 
143  for (int i=x0.size(); i--; ) {
144  GECODE_ME_FAIL(IntView(w[i]).gq(home,0));
145  GECODE_ME_FAIL(IntView(h[i]).gq(home,0));
146  }
147 
148  if (w.assigned() && h.assigned()) {
149  IntArgs wc(x0.size()), hc(x0.size());
150  for (int i=x0.size(); i--; ) {
151  wc[i] = w[i].val();
152  hc[i] = h[i].val();
153  }
154  nooverlap(home, x0, wc, y0, hc);
155  } else {
156  ManBox<FlexDim,2>* b
157  = static_cast<Space&>(home).alloc<ManBox<FlexDim,2> >(x0.size());
158  for (int i=x0.size(); i--; ) {
159  b[i][0] = FlexDim(x0[i],w[i],x1[i]);
160  b[i][1] = FlexDim(y0[i],h[i],y1[i]);
161  }
163  NoOverlap::ManProp<ManBox<FlexDim,2> >::post(home,b,x0.size())));
164  }
165  }
166 
167  void
169  const IntVarArgs& x0, const IntVarArgs& w, const IntVarArgs& x1,
170  const IntVarArgs& y0, const IntVarArgs& h, const IntVarArgs& y1,
171  const BoolVarArgs& m,
172  IntConLevel) {
173  using namespace Int;
174  using namespace NoOverlap;
175  if ((x0.size() != w.size()) || (x0.size() != x1.size()) ||
176  (x0.size() != y0.size()) || (x0.size() != h.size()) ||
177  (x0.size() != y1.size()) || (x0.size() != m.size()))
178  throw ArgumentSizeMismatch("Int::nooverlap");
179  if (home.failed()) return;
180 
181  for (int i=x0.size(); i--; ) {
182  GECODE_ME_FAIL(IntView(w[i]).gq(home,0));
183  GECODE_ME_FAIL(IntView(h[i]).gq(home,0));
184  }
185 
186  if (w.assigned() && h.assigned()) {
187  IntArgs wc(x0.size()), hc(x0.size());
188  for (int i=x0.size(); i--; ) {
189  wc[i] = w[i].val();
190  hc[i] = h[i].val();
191  }
192  nooverlap(home, x0, wc, y0, hc, m);
193  } else if (optional(m)) {
194  OptBox<FlexDim,2>* b
195  = static_cast<Space&>(home).alloc<OptBox<FlexDim,2> >(x0.size());
196  for (int i=x0.size(); i--; ) {
197  b[i][0] = FlexDim(x0[i],w[i],x1[i]);
198  b[i][1] = FlexDim(y0[i],h[i],y1[i]);
199  b[i].optional(m[i]);
200  }
202  NoOverlap::OptProp<OptBox<FlexDim,2> >::post(home,b,x0.size())));
203  } else {
204  ManBox<FlexDim,2>* b
205  = static_cast<Space&>(home).alloc<ManBox<FlexDim,2> >(x0.size());
206  int n = 0;
207  for (int i=0; i<x0.size(); i++)
208  if (m[i].one()) {
209  b[n][0] = FlexDim(x0[i],w[i],x1[i]);
210  b[n][1] = FlexDim(y0[i],h[i],y1[i]);
211  n++;
212  }
213  GECODE_ES_FAIL((NoOverlap::ManProp<ManBox<FlexDim,2> >::post(home,b,n)));
214  }
215  }
216 
217 }
218 
219 // STATISTICS: int-post
bool failed(void) const
Check whether corresponding space is failed.
Definition: core.hpp:3446
IntConLevel
Consistency levels for integer propagators.
Definition: int.hh:937
void post(Home home, Term *t, int n, FloatRelType frt, FloatVal c)
Post propagator for linear constraint over floats.
Definition: post.cpp:228
bool one(const Gecode::FloatValArgs &a)
Check whether has only one coefficients.
Definition: linear.cpp:50
int size(void) const
Return size of array (number of elements)
Definition: array.hpp:1662
void max(Home home, FloatVar x0, FloatVar x1, FloatVar x2)
Post propagator for .
Definition: arithmetic.cpp:57
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:72
No-overlap propagator for mandatory boxes.
Definition: no-overlap.hh:261
Computation spaces.
Definition: core.hpp:1362
Gecode::IntArgs i(4, 1, 2, 3, 4)
int n
Number of negative literals for node type.
Definition: bool-expr.cpp:238
Passing integer variables.
Definition: int.hh:636
Passing integer arguments.
Definition: int.hh:607
Passing Boolean variables.
Definition: int.hh:690
No-overlap propagator for optional boxes.
Definition: no-overlap.hh:288
Integer view for integer variables.
Definition: view.hpp:129
Node * x
Pointer to corresponding Boolean expression node.
Definition: bool-expr.cpp:253
#define GECODE_ME_FAIL(me)
Check whether modification event me is failed, and fail space home.
Definition: macros.hpp:70
void nooverlap(Home home, const IntVarArgs &x, const IntArgs &w, const IntVarArgs &y, const IntArgs &h, IntConLevel)
Post propagator for rectangle packing.
Definition: no-overlap.cpp:55
struct Gecode::@518::NNF::@57::@58 b
For binary nodes (and, or, eqv)
Gecode toplevel namespace
bool optional(const BoolVarArgs &m)
Definition: no-overlap.cpp:45
void check(int n, const char *l)
Check whether n is in range, otherwise throw out of limits with information l.
Definition: limits.hpp:50
Home class for posting propagators
Definition: core.hpp:717
Exception: Arguments are of different size
Definition: exception.hpp:77
#define GECODE_ES_FAIL(es)
Check whether execution status es is failed, and fail space home.
Definition: macros.hpp:96
bool assigned(void) const
Test if all variables are assigned.
Definition: array.hpp:2076