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