Generated on Sat May 25 2013 18:00:36 for Gecode by doxygen 1.8.3.1
cumulative.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  * Guido Tack <tack@gecode.org>
6  *
7  * Copyright:
8  * Christian Schulte, 2009
9  * Guido Tack, 2010
10  *
11  * Last modified:
12  * $Date: 2013-03-11 06:26:07 +0100 (Mon, 11 Mar 2013) $ by $Author: tack $
13  * $Revision: 13487 $
14  *
15  * This file is part of Gecode, the generic constraint
16  * development environment:
17  * http://www.gecode.org
18  *
19  * Permission is hereby granted, free of charge, to any person obtaining
20  * a copy of this software and associated documentation files (the
21  * "Software"), to deal in the Software without restriction, including
22  * without limitation the rights to use, copy, modify, merge, publish,
23  * distribute, sublicense, and/or sell copies of the Software, and to
24  * permit persons to whom the Software is furnished to do so, subject to
25  * the following conditions:
26  *
27  * The above copyright notice and this permission notice shall be
28  * included in all copies or substantial portions of the Software.
29  *
30  * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,
31  * EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF
32  * MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND
33  * NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE
34  * LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION
35  * OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION
36  * WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
37  *
38  */
39 
40 #include <gecode/int/cumulative.hh>
41 
42 #include <algorithm>
43 
44 namespace Gecode {
45 
46  template<class Cap>
47  void
48  cumulative(Home home, Cap c, const TaskTypeArgs& t,
49  const IntVarArgs& s, const IntArgs& p, const IntArgs& u,
50  IntConLevel icl) {
51  using namespace Gecode::Int;
52  using namespace Gecode::Int::Cumulative;
53  if ((s.size() != p.size()) || (s.size() != u.size()) ||
54  (s.size() != t.size()))
55  throw Int::ArgumentSizeMismatch("Int::cumulative");
56  long long int w = 0;
57  for (int i=p.size(); i--; ) {
58  Limits::nonnegative(p[i],"Int::cumulative");
59  Limits::nonnegative(u[i],"Int::cumulative");
60  Limits::check(static_cast<long long int>(s[i].max()) + p[i],
61  "Int::cumulative");
62  mul_check(p[i],u[i]);
63  w += s[i].width();
64  }
65  mul_check(c.max(),w,s.size());
66  if (home.failed()) return;
67 
68  int minU = INT_MAX; int minU2 = INT_MAX; int maxU = INT_MIN;
69  for (int i=u.size(); i--;) {
70  if (u[i] < minU)
71  minU = u[i];
72  else if (u[i] < minU2)
73  minU2 = u[i];
74  if (u[i] > maxU)
75  maxU = u[i];
76  }
77  bool disjunctive =
78  (minU > c.max()/2) || (minU2 > c.max()/2 && minU+minU2>c.max());
79  if (disjunctive) {
80  GECODE_ME_FAIL(c.gq(home,maxU));
81  unary(home,t,s,p,icl);
82  } else {
83  bool fixp = true;
84  for (int i=t.size(); i--;)
85  if (t[i] != TT_FIXP) {
86  fixp = false; break;
87  }
88  if (fixp) {
89  TaskArray<ManFixPTask> tasks(home,s.size());
90  for (int i=0; i<s.size(); i++)
91  tasks[i].init(s[i],p[i],u[i]);
93  } else {
94  TaskArray<ManFixPSETask> tasks(home,s.size());
95  for (int i=s.size(); i--;)
96  tasks[i].init(t[i],s[i],p[i],u[i]);
98  }
99  }
100  }
101 
102  void
103  cumulative(Home home, int c, const TaskTypeArgs& t,
104  const IntVarArgs& s, const IntArgs& p, const IntArgs& u,
105  IntConLevel icl) {
106  Int::Limits::nonnegative(c,"Int::cumulative");
107  cumulative(home,Int::ConstIntView(c),t,s,p,u,icl);
108  }
109  void
111  const IntVarArgs& s, const IntArgs& p, const IntArgs& u,
112  IntConLevel icl) {
113  if (c.assigned())
114  cumulative(home,c.val(),t,s,p,u,icl);
115  else
116  cumulative(home,Int::IntView(c),t,s,p,u,icl);
117  }
118 
119  template<class Cap>
120  void
121  cumulative(Home home, Cap c, const TaskTypeArgs& t,
122  const IntVarArgs& s, const IntArgs& p, const IntArgs& u,
123  const BoolVarArgs& m, IntConLevel icl) {
124  using namespace Gecode::Int;
125  using namespace Gecode::Int::Cumulative;
126  if ((s.size() != p.size()) || (s.size() != u.size()) ||
127  (s.size() != t.size()) || (s.size() != m.size()))
128  throw Int::ArgumentSizeMismatch("Int::cumulative");
129  long long int w = 0;
130  for (int i=p.size(); i--; ) {
131  Limits::nonnegative(p[i],"Int::cumulative");
132  Limits::nonnegative(u[i],"Int::cumulative");
133  Limits::check(static_cast<long long int>(s[i].max()) + p[i],
134  "Int::cumulative");
135  mul_check(p[i],u[i]);
136  w += s[i].width();
137  }
138  mul_check(c.max(),w,s.size());
139  if (home.failed()) return;
140 
141  bool allMandatory = true;
142  for (int i=m.size(); i--;) {
143  if (!m[i].one()) {
144  allMandatory = false;
145  break;
146  }
147  }
148  if (allMandatory) {
149  cumulative(home,c,t,s,p,u,icl);
150  } else {
151  bool fixp = true;
152  for (int i=t.size(); i--;)
153  if (t[i] != TT_FIXP) {
154  fixp = false; break;
155  }
156  if (fixp) {
157  TaskArray<OptFixPTask> tasks(home,s.size());
158  for (int i=0; i<s.size(); i++)
159  tasks[i].init(s[i],p[i],u[i],m[i]);
161  } else {
162  TaskArray<OptFixPSETask> tasks(home,s.size());
163  for (int i=s.size(); i--;)
164  tasks[i].init(t[i],s[i],p[i],u[i],m[i]);
166  }
167  }
168  }
169 
170  void
171  cumulative(Home home, int c, const TaskTypeArgs& t,
172  const IntVarArgs& s, const IntArgs& p, const IntArgs& u,
173  const BoolVarArgs& m, IntConLevel icl) {
174  Int::Limits::nonnegative(c,"Int::cumulative");
175  cumulative(home,Int::ConstIntView(c),t,s,p,u,m,icl);
176  }
177  void
179  const IntVarArgs& s, const IntArgs& p, const IntArgs& u,
180  const BoolVarArgs& m, IntConLevel icl) {
181  if (c.assigned())
182  cumulative(home,c.val(),t,s,p,u,m,icl);
183  else
184  cumulative(home,Int::IntView(c),t,s,p,u,m,icl);
185  }
186 
187  template<class Cap>
188  void
189  cumulative(Home home, Cap c, const IntVarArgs& s,
190  const IntArgs& p, const IntArgs& u, IntConLevel icl) {
191  using namespace Gecode::Int;
192  using namespace Gecode::Int::Cumulative;
193  if ((s.size() != p.size()) || (s.size() != u.size()))
194  throw Int::ArgumentSizeMismatch("Int::cumulative");
195  long long int w = 0;
196  for (int i=p.size(); i--; ) {
197  Limits::nonnegative(p[i],"Int::cumulative");
198  Limits::nonnegative(u[i],"Int::cumulative");
199  Limits::check(static_cast<long long int>(s[i].max()) + p[i],
200  "Int::cumulative");
201  mul_check(p[i],u[i]);
202  w += s[i].width();
203  }
204  mul_check(c.max(),w,s.size());
205  if (home.failed()) return;
206 
207  int minU = INT_MAX; int minU2 = INT_MAX; int maxU = INT_MIN;
208  for (int i=u.size(); i--;) {
209  if (u[i] < minU)
210  minU = u[i];
211  else if (u[i] < minU2)
212  minU2 = u[i];
213  if (u[i] > maxU)
214  maxU = u[i];
215  }
216  bool disjunctive =
217  (minU > c.max()/2) || (minU2 > c.max()/2 && minU+minU2>c.max());
218  if (disjunctive) {
219  GECODE_ME_FAIL(c.gq(home,maxU));
220  unary(home,s,p,icl);
221  } else {
222  TaskArray<ManFixPTask> t(home,s.size());
223  for (int i=0; i<s.size(); i++) {
224  t[i].init(s[i],p[i],u[i]);
225  }
227  }
228  }
229 
230  void
231  cumulative(Home home, int c, const IntVarArgs& s,
232  const IntArgs& p, const IntArgs& u, IntConLevel icl) {
233  Int::Limits::nonnegative(c,"Int::cumulative");
234  cumulative(home,Int::ConstIntView(c),s,p,u,icl);
235  }
236  void
237  cumulative(Home home, IntVar c, const IntVarArgs& s,
238  const IntArgs& p, const IntArgs& u, IntConLevel icl) {
239  if (c.assigned())
240  cumulative(home,c.val(),s,p,u,icl);
241  else
242  cumulative(home,Int::IntView(c),s,p,u,icl);
243  }
244 
245  template<class Cap>
246  void
247  cumulative(Home home, Cap c, const IntVarArgs& s, const IntArgs& p,
248  const IntArgs& u, const BoolVarArgs& m, IntConLevel icl) {
249  using namespace Gecode::Int;
250  using namespace Gecode::Int::Cumulative;
251  if ((s.size() != p.size()) || (s.size() != u.size()) ||
252  (s.size() != m.size()))
253  throw Int::ArgumentSizeMismatch("Int::cumulative");
254  long long int w = 0;
255  for (int i=p.size(); i--; ) {
256  Limits::nonnegative(p[i],"Int::cumulative");
257  Limits::nonnegative(u[i],"Int::cumulative");
258  Limits::check(static_cast<long long int>(s[i].max()) + p[i],
259  "Int::cumulative");
260  mul_check(p[i],u[i]);
261  w += s[i].width();
262  }
263  mul_check(c.max(),w,s.size());
264  if (home.failed()) return;
265 
266  bool allMandatory = true;
267  for (int i=m.size(); i--;) {
268  if (!m[i].one()) {
269  allMandatory = false;
270  break;
271  }
272  }
273  if (allMandatory) {
274  cumulative(home,c,s,p,u,icl);
275  } else {
276  TaskArray<OptFixPTask> t(home,s.size());
277  for (int i=0; i<s.size(); i++) {
278  t[i].init(s[i],p[i],u[i],m[i]);
279  }
281  }
282  }
283 
284  void
285  cumulative(Home home, int c, const IntVarArgs& s, const IntArgs& p,
286  const IntArgs& u, const BoolVarArgs& m, IntConLevel icl) {
287  Int::Limits::nonnegative(c,"Int::cumulative");
288  cumulative(home,Int::ConstIntView(c),s,p,u,m,icl);
289  }
290  void
291  cumulative(Home home, IntVar c, const IntVarArgs& s, const IntArgs& p,
292  const IntArgs& u, const BoolVarArgs& m, IntConLevel icl) {
293  if (c.assigned())
294  cumulative(home,c.val(),s,p,u,m,icl);
295  else
296  cumulative(home,Int::IntView(c),s,p,u,m,icl);
297  }
298 
299  template<class Cap>
300  void
301  cumulative(Home home, Cap c, const IntVarArgs& s,
302  const IntVarArgs& p, const IntVarArgs& e,
303  const IntArgs& u, IntConLevel icl) {
304  using namespace Gecode::Int;
305  using namespace Gecode::Int::Cumulative;
306  if ((s.size() != p.size()) || (s.size() != e.size()) ||
307  (s.size() != u.size()))
308  throw Int::ArgumentSizeMismatch("Int::cumulative");
309  long long int w = 0;
310  for (int i=p.size(); i--; ) {
311  rel(home, p[i], IRT_GQ, 0);
312  }
313  for (int i=p.size(); i--; ) {
314  Limits::nonnegative(u[i],"Int::cumulative");
315  Limits::check(static_cast<long long int>(s[i].max()) + p[i].max(),
316  "Int::cumulative");
317  mul_check(p[i].max(),u[i]);
318  w += s[i].width();
319  }
320  mul_check(c.max(),w,s.size());
321  if (home.failed()) return;
322 
323  bool fixP = true;
324  for (int i=p.size(); i--;) {
325  if (!p[i].assigned()) {
326  fixP = false;
327  break;
328  }
329  }
330  if (fixP) {
331  IntArgs pp(p.size());
332  for (int i=p.size(); i--;)
333  pp[i] = p[i].val();
334  cumulative(home,c,s,pp,u,icl);
335  } else {
336  TaskArray<ManFlexTask> t(home,s.size());
337  for (int i=s.size(); i--; )
338  t[i].init(s[i],p[i],e[i],u[i]);
340  }
341  }
342 
343  void
344  cumulative(Home home, int c, const IntVarArgs& s,
345  const IntVarArgs& p, const IntVarArgs& e,
346  const IntArgs& u, IntConLevel icl) {
347  Int::Limits::nonnegative(c,"Int::cumulative");
348  cumulative(home,Int::ConstIntView(c),s,p,e,u,icl);
349  }
350  void
351  cumulative(Home home, IntVar c, const IntVarArgs& s,
352  const IntVarArgs& p, const IntVarArgs& e,
353  const IntArgs& u, IntConLevel icl) {
354  if (c.assigned())
355  cumulative(home,c.val(),s,p,e,u,icl);
356  else
357  cumulative(home,Int::IntView(c),s,p,e,u,icl);
358  }
359 
360  template<class Cap>
361  void
362  cumulative(Home home, Cap c, const IntVarArgs& s, const IntVarArgs& p,
363  const IntVarArgs& e, const IntArgs& u, const BoolVarArgs& m,
364  IntConLevel icl) {
365  using namespace Gecode::Int;
366  using namespace Gecode::Int::Cumulative;
367  if ((s.size() != p.size()) || (s.size() != u.size()) ||
368  (s.size() != e.size()) || (s.size() != m.size()))
369  throw Int::ArgumentSizeMismatch("Int::cumulative");
370  for (int i=p.size(); i--; ) {
371  rel(home, p[i], IRT_GQ, 0);
372  }
373  long long int w = 0;
374  for (int i=p.size(); i--; ) {
375  Limits::nonnegative(u[i],"Int::cumulative");
376  Limits::check(static_cast<long long int>(s[i].max()) + p[i].max(),
377  "Int::cumulative");
378  mul_check(p[i].max(),u[i]);
379  w += s[i].width();
380  }
381  mul_check(c.max(),w,s.size());
382  if (home.failed()) return;
383 
384  bool allMandatory = true;
385  for (int i=m.size(); i--;) {
386  if (!m[i].one()) {
387  allMandatory = false;
388  break;
389  }
390  }
391  if (allMandatory) {
392  cumulative(home,c,s,p,e,u,icl);
393  } else {
394  TaskArray<OptFlexTask> t(home,s.size());
395  for (int i=s.size(); i--; )
396  t[i].init(s[i],p[i],e[i],u[i],m[i]);
398  }
399  }
400 
401  void
402  cumulative(Home home, int c, const IntVarArgs& s, const IntVarArgs& p,
403  const IntVarArgs& e, const IntArgs& u, const BoolVarArgs& m,
404  IntConLevel icl) {
405  Int::Limits::nonnegative(c,"Int::cumulative");
406  cumulative(home,Int::ConstIntView(c),s,p,e,u,m,icl);
407  }
408  void
409  cumulative(Home home, IntVar c, const IntVarArgs& s, const IntVarArgs& p,
410  const IntVarArgs& e, const IntArgs& u, const BoolVarArgs& m,
411  IntConLevel icl) {
412  if (c.assigned())
413  cumulative(home,c.val(),s,p,e,u,m,icl);
414  else
415  cumulative(home,Int::IntView(c),s,p,e,u,m,icl);
416  }
417 
418 }
419 
420 // STATISTICS: int-post