this repo has no description
dekker.one
1/* -*- mode: C++; c-basic-offset: 2; indent-tabs-mode: nil -*- */
2/*
3 * Main authors:
4 * Guido Tack <tack@gecode.org>
5 * Christian Schulte <schulte@gecode.org>
6 *
7 * Contributing authors:
8 * Gabor Szokoli <szokoli@gecode.org>
9 *
10 * Copyright:
11 * Guido Tack, 2004
12 * Christian Schulte, 2004
13 * Gabor Szokoli, 2004
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#ifndef GECODE_SET_RELOP_COMM_ICC
41#define GECODE_SET_RELOP_COMM_ICC
42
43namespace Gecode {
44
45 template<class View0, class View1>
46 forceinline bool
47 viewarrayshared(const ViewArray<View0>& va, const View1& y) {
48 return shared(va,y);
49 }
50
51 template<>
52 forceinline bool
53 viewarrayshared<Set::SingletonView,Set::SetView>
54 (const ViewArray<Set::SingletonView>&, const Set::SetView&) {
55 return false;
56 }
57
58 template<>
59 forceinline bool
60 viewarrayshared<Set::ComplementView<Set::SingletonView>,Set::SetView>
61 (const ViewArray<Set::ComplementView<Set::SingletonView> >&,
62 const Set::SetView&) {
63 return false;
64 }
65
66 template<>
67 forceinline bool
68 viewarrayshared<Set::ComplementView<Set::SingletonView>,
69 Set::ComplementView<Set::SetView> >
70 (const ViewArray<Set::ComplementView<Set::SingletonView> >&,
71 const Set::ComplementView<Set::SetView>&) {
72 return false;
73 }
74
75
76namespace Set { namespace RelOp {
77
78 /*
79 * Detect sharing between 3 variables
80 *
81 */
82 template<class View0, class View1, class View2>
83 forceinline bool
84 shared(View0 v0, View1 v1, View2 v2) {
85 return shared(v0,v1) || shared(v0,v2) || shared(v1,v2);
86 }
87
88 template<class View0, class View1, class View2>
89 ExecStatus interCard(Space& home,
90 bool& retmodified, View0& x0, View1& x1, View2& x2) {
91 bool modified = false;
92 do {
93 retmodified |= modified;
94 modified = false;
95
96 {
97 LubRanges<View0> x0ub(x0);
98 LubRanges<View1> x1ub(x1);
99 Iter::Ranges::Union<LubRanges<View0>, LubRanges<View1> >
100 u1(x0ub,x1ub);
101 unsigned int s1 = Iter::Ranges::size(u1);
102
103 if (x0.cardMin() + x1.cardMin() > s1) {
104 GECODE_ME_CHECK_MODIFIED(modified,
105 x2.cardMin(home, x0.cardMin()+x1.cardMin()-s1));
106 }
107
108 // unsigned int res = std::max(x0.cardMin()+
109 // (x1.cardMin()<s1 ?
110 // 0 : x1.cardMin()-s1),
111 // std::max(x0.cardMin(),
112 // x1.cardMin()));
113 // GECODE_ME_CHECK_MODIFIED(modified, x2.cardMin(home,res));
114 }
115
116 {
117 GlbRanges<View0> x0lb(x0);
118 GlbRanges<View1> x1lb(x1);
119 Iter::Ranges::Union<GlbRanges<View0>, GlbRanges<View1> >
120 u1(x0lb,x1lb);
121 unsigned int s1 = Iter::Ranges::size(u1);
122 GECODE_ME_CHECK_MODIFIED(modified,
123 x2.cardMax(home,
124 x0.cardMax()+x1.cardMax()-s1));
125 }
126
127 if (x2.cardMax() < x1.cardMin())
128 GECODE_ME_CHECK_MODIFIED(modified,
129 x0.cardMax(home,
130 Set::Limits::card+x2.cardMax()-x1.cardMin()));
131
132 if (x2.cardMax() < x0.cardMin())
133 GECODE_ME_CHECK_MODIFIED(modified,
134 x1.cardMax(home,
135 Set::Limits::card+x2.cardMax()-x0.cardMin()));
136
137 GECODE_ME_CHECK_MODIFIED(modified,
138 x0.cardMin(home,x2.cardMin()));
139 GECODE_ME_CHECK_MODIFIED(modified,
140 x1.cardMin(home,x2.cardMin()));
141 } while(modified);
142 return ES_FIX;
143 }
144 template<class View0, class View1, class View2>
145 ExecStatus unionCard(Space& home,
146 bool& retmodified, View0& x0, View1& x1, View2& x2) {
147 bool modified = false;
148 do {
149 retmodified |= modified;
150 modified = false;
151
152 {
153 LubRanges<View0> x0ub(x0);
154 LubRanges<View1> x1ub(x1);
155 Iter::Ranges::Inter<LubRanges<View0>, LubRanges<View1> > i1(x0ub,x1ub);
156 unsigned int s1 = Iter::Ranges::size(i1);
157 unsigned int res = std::max(x0.cardMin()+
158 (x1.cardMin()<s1 ?
159 0 : x1.cardMin()-s1),
160 std::max(x0.cardMin(),
161 x1.cardMin()));
162 GECODE_ME_CHECK_MODIFIED(modified, x2.cardMin(home,res));
163 }
164
165 {
166 LubRanges<View0> x0ub(x0);
167 LubRanges<View1> x1ub(x1);
168 Iter::Ranges::Union<LubRanges<View0>, LubRanges<View1> > u1(x0ub,x1ub);
169 unsigned int s1 = Iter::Ranges::size(u1);
170 GECODE_ME_CHECK_MODIFIED(modified,
171 x2.cardMax(home,
172 std::min(x0.cardMax()+x1.cardMax(),s1)));
173 }
174
175 if (x2.cardMin() > x1.cardMax())
176 GECODE_ME_CHECK_MODIFIED(modified,
177 x0.cardMin(home,x2.cardMin() - x1.cardMax()));
178
179 if (x2.cardMin() > x0.cardMax())
180 GECODE_ME_CHECK_MODIFIED(modified,
181 x1.cardMin(home,x2.cardMin() - x0.cardMax()));
182
183 GECODE_ME_CHECK_MODIFIED(modified,
184 x0.cardMax(home,x2.cardMax()));
185 GECODE_ME_CHECK_MODIFIED(modified,
186 x1.cardMax(home,x2.cardMax()));
187 } while(modified);
188 return ES_FIX;
189 }
190
191 template<class View0, class View1>
192 ExecStatus
193 unionNCard(Space& home, bool& modified, ViewArray<View0>& x,
194 View1& y, GLBndSet& unionOfDets) {
195 int xsize = x.size();
196 // Max(Xi.cardMin) <= y.card <= Sum(Xi.cardMax)
197 // Xi.card <=y.cardMax
198 unsigned int cardMaxSum=unionOfDets.size();
199 bool maxValid = true;
200 for (int i=xsize; i--; ) {
201 cardMaxSum+=x[i].cardMax();
202 if (cardMaxSum < x[i].cardMax()) { maxValid = false; } //overflow
203 GECODE_ME_CHECK_MODIFIED(modified, y.cardMin(home,x[i].cardMin()) );
204 GECODE_ME_CHECK_MODIFIED(modified, x[i].cardMax(home,y.cardMax()) );
205 }
206 if (maxValid) {
207 GECODE_ME_CHECK_MODIFIED(modified, y.cardMax(home,cardMaxSum));
208 }
209 //y.cardMin - Sum(Xj.cardMax) <= Xi.card
210
211 if (x.size() == 0)
212 return ES_NOFIX;
213
214 Region r;
215 //TODO: overflow management is a waste now.
216 {
217 unsigned int* rightSum = r.alloc<unsigned int>(xsize);
218 rightSum[xsize-1]=0;
219
220 for (int i=x.size()-1;i--;) {
221 rightSum[i] = rightSum[i+1] + x[i+1].cardMax();
222 if (rightSum[i] < rightSum[i+1]) {
223 //overflow, fill the rest of the array.
224 for (int j=i; j>0;j--) {
225 rightSum[j]=Limits::card;
226 }
227 break;
228 }
229 }
230
231 //Size of union of determied vars missing from x sneaked in here:
232 unsigned int leftAcc=unionOfDets.size();
233
234 for (int i=0; i<xsize;i++) {
235 unsigned int jsum = leftAcc+rightSum[i];
236 //If jsum did not overflow and is less than y.cardMin:
237 if (jsum >= leftAcc && jsum < y.cardMin()) {
238 GECODE_ME_CHECK_MODIFIED(modified, x[i].cardMin(home,y.cardMin()-jsum));
239 }
240 leftAcc += x[i].cardMax();
241 if (leftAcc < x[i].cardMax()) {leftAcc = Limits::card;}
242 }
243 }
244
245 //y.cardMin - |U(Xj.ub)| <= Xi.card
246
247 {
248 GLBndSet* rightUnion =
249 static_cast<GLBndSet*>(r.ralloc(sizeof(GLBndSet)*xsize));
250 new (&rightUnion[xsize-1]) GLBndSet(home);
251 for (int i=xsize-1;i--;) {
252 BndSetRanges prev(rightUnion[i+1]);
253 LubRanges<View0> prevX(x[i+1]);
254 Iter::Ranges::Union< BndSetRanges,LubRanges<View0> >
255 iter(prev,prevX);
256 new (&rightUnion[i]) GLBndSet(home);
257 rightUnion[i].includeI(home, iter);
258 }
259
260 //union of determied vars missing from x sneaked in here:
261 GLBndSet leftAcc;
262 leftAcc.update(home,unionOfDets);
263 for (int i=0; i<xsize; i++) {
264 BndSetRanges left(leftAcc);
265 BndSetRanges right(rightUnion[i]);
266 Iter::Ranges::Union<BndSetRanges,
267 BndSetRanges> iter(left, right);
268 unsigned int unionSize = Iter::Ranges::size(iter);
269 if (y.cardMin() > unionSize) {
270 GECODE_ME_CHECK_MODIFIED(modified,
271 x[i].cardMin(home, y.cardMin() - unionSize) );
272 }
273 LubRanges<View0> xiub(x[i]);
274 leftAcc.includeI(home, xiub);
275 }
276
277 for (int i=xsize; i--;)
278 rightUnion[i].dispose(home);
279 leftAcc.dispose(home);
280 }
281
282 //no need for this: |y.lb - U(Xj.cardMax)| <= S.card
283
284 return ES_NOFIX;
285
286 }
287
288 /*
289 * Xi UB is subset of YUB
290 * Subscribes to Y UB
291 */
292 template<class View0, class View1>
293 ExecStatus
294 unionNXiUB(Space& home,
295 bool& modified, ViewArray<View0>& x, View1& y,
296 GLBndSet &) {
297 int xsize = x.size();
298 for (int i=xsize; i--; ) {
299 LubRanges<View1> yub(y);
300 GECODE_ME_CHECK_MODIFIED(modified, x[i].intersectI(home, yub));
301 }
302 return ES_FIX;
303 }
304
305 // cardinality rules for PartitionN constraint
306 template<class View0, class View1>
307 ExecStatus
308 partitionNCard(Space& home,
309 bool& modified, ViewArray<View0>& x, View1& y,
310 GLBndSet& unionOfDets) {
311 unsigned int cardMinSum=unionOfDets.size();
312 unsigned int cardMaxSum=unionOfDets.size();
313 int xsize = x.size();
314 for (int i=xsize; i--; ) {
315 cardMinSum+=x[i].cardMin();
316 if (cardMinSum < x[i].cardMin()) {
317 //sum of mins overflows: fail the space.
318 GECODE_ME_CHECK(ME_SET_FAILED);
319 }
320 }
321 GECODE_ME_CHECK_MODIFIED(modified, y.cardMin(home,cardMinSum));
322 for (int i=xsize; i--; ) {
323 cardMaxSum+=x[i].cardMax();
324 if (cardMaxSum < x[i].cardMax()) {
325 //sum of maxes overflows: no useful information to tell.
326 goto overflow;
327 }
328 }
329 GECODE_ME_CHECK_MODIFIED(modified, y.cardMax(home,cardMaxSum));
330
331 if (x.size() == 0)
332 return ES_NOFIX;
333
334 overflow:
335
336 //Cardinality of each x[i] limited by cardinality of y minus all x[j]s:
337
338 {
339 Region r;
340 unsigned int* rightMinSum = r.alloc<unsigned int>(xsize);
341 unsigned int* rightMaxSum = r.alloc<unsigned int>(xsize);
342 rightMinSum[xsize-1]=0;
343 rightMaxSum[xsize-1]=0;
344
345 for (int i=x.size()-1;i--;) {
346 rightMaxSum[i] = rightMaxSum[i+1] + x[i+1].cardMax();
347 if (rightMaxSum[i] < rightMaxSum[i+1]) {
348 //overflow, fill the rest of the array.
349 for (int j=i; j>0;j--) {
350 rightMaxSum[j]=Limits::card;
351 }
352 break;
353 }
354 }
355 for (int i=x.size()-1;i--;) {
356 rightMinSum[i] = rightMinSum[i+1] + x[i+1].cardMin();
357 if (rightMinSum[i] < rightMinSum[i+1]) {
358 //overflow, fail the space
359 GECODE_ME_CHECK(ME_SET_FAILED);
360 }
361 }
362 unsigned int leftMinAcc=unionOfDets.size();
363 unsigned int leftMaxAcc=unionOfDets.size();
364
365 for (int i=0; i<xsize;i++) {
366 unsigned int maxSum = leftMaxAcc+rightMaxSum[i];
367 unsigned int minSum = leftMinAcc+rightMinSum[i];
368 //If maxSum did not overflow and is less than y.cardMin:
369 if (maxSum >= leftMaxAcc && maxSum < y.cardMin()) {
370 GECODE_ME_CHECK_MODIFIED(modified, x[i].cardMin(home,y.cardMin()-maxSum));
371 }
372
373 //Overflow, fail.
374 if (minSum < leftMinAcc || y.cardMax() < minSum) {
375 GECODE_ME_CHECK(ME_SET_FAILED);
376 }
377 else {
378 GECODE_ME_CHECK_MODIFIED(modified, x[i].cardMax(home,y.cardMax()-minSum));
379 }
380
381 leftMaxAcc += x[i].cardMax();
382 if (leftMaxAcc < x[i].cardMax())
383 leftMaxAcc = Limits::card;
384 leftMinAcc += x[i].cardMin();
385 if (leftMinAcc < x[i].cardMin())
386 GECODE_ME_CHECK(ME_SET_FAILED);
387 }
388 }
389
390 return ES_NOFIX;
391 }
392
393 // Xi LB includes YLB minus union Xj UB
394 // Xi UB is subset of YUB minus union of Xj LBs
395 template<class View0, class View1>
396 ExecStatus
397 partitionNXi(Space& home,
398 bool& modified, ViewArray<View0>& x, View1& y) {
399 int xsize = x.size();
400 Region r;
401 GLBndSet* afterUB =
402 static_cast<GLBndSet*>(r.ralloc(sizeof(GLBndSet)*xsize));
403 GLBndSet* afterLB =
404 static_cast<GLBndSet*>(r.ralloc(sizeof(GLBndSet)*xsize));
405
406 {
407 GLBndSet sofarAfterUB;
408 GLBndSet sofarAfterLB;
409 for (int i=xsize; i--;) {
410 new (&afterUB[i]) GLBndSet(home);
411 new (&afterLB[i]) GLBndSet(home);
412 afterUB[i].update(home,sofarAfterUB);
413 afterLB[i].update(home,sofarAfterLB);
414 LubRanges<View0> xiub(x[i]);
415 GlbRanges<View0> xilb(x[i]);
416 sofarAfterUB.includeI(home,xiub);
417 sofarAfterLB.includeI(home,xilb);
418 }
419 sofarAfterUB.dispose(home);
420 sofarAfterLB.dispose(home);
421 }
422
423 {
424 GLBndSet sofarBeforeUB;
425 GLBndSet sofarBeforeLB;
426 for (int i=0; i<xsize; i++) {
427 LubRanges<View1> yub(y);
428 BndSetRanges slb(sofarBeforeLB);
429 BndSetRanges afterlb(afterLB[i]);
430 Iter::Ranges::Union<BndSetRanges,
431 BndSetRanges> xjlb(slb, afterlb);
432 Iter::Ranges::Diff<LubRanges<View1>,
433 Iter::Ranges::Union<BndSetRanges,
434 BndSetRanges> > diff1(yub, xjlb);
435 GECODE_ME_CHECK_MODIFIED(modified, x[i].intersectI(home,diff1));
436
437 GlbRanges<View1> ylb(y);
438 BndSetRanges sub(sofarBeforeUB);
439 BndSetRanges afterub(afterUB[i]);
440 Iter::Ranges::Union<BndSetRanges,
441 BndSetRanges> xjub(sub, afterub);
442 Iter::Ranges::Diff<GlbRanges<View1>,
443 Iter::Ranges::Union<BndSetRanges,
444 BndSetRanges> > diff2(ylb, xjub);
445 GECODE_ME_CHECK_MODIFIED(modified, x[i].includeI(home,diff2));
446
447 LubRanges<View0> xiub(x[i]);
448 GlbRanges<View0> xilb(x[i]);
449 sofarBeforeUB.includeI(home,xiub);
450 sofarBeforeLB.includeI(home,xilb);
451 }
452 sofarBeforeLB.dispose(home);
453 sofarBeforeUB.dispose(home);
454 }
455
456 for (int i=xsize;i--;) {
457 afterUB[i].dispose(home);
458 afterLB[i].dispose(home);
459 }
460
461 return ES_NOFIX;
462 }
463
464 // Xi UB is subset of YUB minus union of Xj LBs
465 template<class View0, class View1>
466 ExecStatus
467 partitionNXiUB(Space& home,
468 bool& modified, ViewArray<View0>& x, View1& y,
469 GLBndSet& unionOfDets) {
470 int xsize = x.size();
471 Region r;
472 GLBndSet* afterLB =
473 static_cast<GLBndSet*>(r.ralloc(sizeof(GLBndSet)*xsize));
474
475 {
476 GLBndSet sofarAfterLB;
477 for (int i=xsize; i--;) {
478 new (&afterLB[i]) GLBndSet(home);
479 afterLB[i].update(home,sofarAfterLB);
480 GlbRanges<View0> xilb(x[i]);
481 sofarAfterLB.includeI(home,xilb);
482 }
483 sofarAfterLB.dispose(home);
484 }
485
486 {
487 GLBndSet sofarBeforeLB;
488 sofarBeforeLB.update(home,unionOfDets);
489 for (int i=0; i<xsize; i++) {
490 LubRanges<View1> yub(y);
491 BndSetRanges slb(sofarBeforeLB);
492 BndSetRanges afterlb(afterLB[i]);
493 Iter::Ranges::Union<BndSetRanges,
494 BndSetRanges> xjlb(slb, afterlb);
495 Iter::Ranges::Diff<LubRanges<View1>,
496 Iter::Ranges::Union<BndSetRanges,
497 BndSetRanges> > diff1(yub, xjlb);
498 GECODE_ME_CHECK_MODIFIED(modified, x[i].intersectI(home,diff1));
499
500 GlbRanges<View0> xilb(x[i]);
501 sofarBeforeLB.includeI(home,xilb);
502 }
503 sofarBeforeLB.dispose(home);
504 }
505 for (int i=xsize; i--;)
506 afterLB[i].dispose(home);
507 return ES_NOFIX;
508 }
509
510 // Xi LB includes YLB minus union Xj UB
511 template<class View0, class View1>
512 ExecStatus
513 partitionNXiLB(Space& home,
514 bool& modified, ViewArray<View0>& x, View1& y,
515 GLBndSet& unionOfDets) {
516 int xsize = x.size();
517 Region r;
518 GLBndSet* afterUB =
519 static_cast<GLBndSet*>(r.ralloc(sizeof(GLBndSet)*xsize));
520
521 {
522 GLBndSet sofarAfterUB;
523 for (int i=xsize; i--;) {
524 new (&afterUB[i]) GLBndSet(home);
525 afterUB[i].update(home,sofarAfterUB);
526 LubRanges<View0> xiub(x[i]);
527 sofarAfterUB.includeI(home,xiub);
528 }
529 sofarAfterUB.dispose(home);
530 }
531
532 {
533 //The union of previously determined x[j]-s is added to the mix here:
534 GLBndSet sofarBeforeUB;
535 sofarBeforeUB.update(home,unionOfDets);
536 for (int i=0; i<xsize; i++) {
537 GlbRanges<View1> ylb(y);
538 BndSetRanges sub(sofarBeforeUB);
539 BndSetRanges afterub(afterUB[i]);
540 Iter::Ranges::Union<BndSetRanges,
541 BndSetRanges> xjub(sub, afterub);
542 Iter::Ranges::Diff<GlbRanges<View1>,
543 Iter::Ranges::Union<BndSetRanges,
544 BndSetRanges> > diff2(ylb, xjub);
545 GECODE_ME_CHECK_MODIFIED(modified, x[i].includeI(home,diff2));
546
547 LubRanges<View0> xiub(x[i]);
548 sofarBeforeUB.includeI(home,xiub);
549 }
550 sofarBeforeUB.dispose(home);
551 }
552 for (int i=xsize;i--;)
553 afterUB[i].dispose(home);
554 return ES_NOFIX;
555 }
556
557 // Y LB contains union of X LBs
558 template<class View0, class View1>
559 ExecStatus
560 partitionNYLB(Space& home,
561 bool& modified, ViewArray<View0>& x, View1& y,
562 GLBndSet& unionOfDets) {
563 assert(unionOfDets.isConsistent());
564 int xsize = x.size();
565 Region reg;
566 GlbRanges<View0>* xLBs = reg.alloc<GlbRanges<View0> >(xsize);
567 int nonEmptyCounter=0;
568 for (int i = xsize; i--; ) {
569 GlbRanges<View0> r(x[i]);
570 if (r()) {
571 xLBs[nonEmptyCounter] = r;
572 nonEmptyCounter++;
573 }
574 }
575 if (nonEmptyCounter !=0) {
576 Iter::Ranges::NaryUnion xLBUnion(reg,xLBs,nonEmptyCounter);
577 BndSetRanges dets(unionOfDets);
578 xLBUnion |= dets;
579 GECODE_ME_CHECK_MODIFIED(modified, y.includeI(home,xLBUnion));
580 }
581 return ES_FIX;
582 }
583
584 // Y UB is subset of union of X UBs
585 template<class View0, class View1>
586 ExecStatus
587 partitionNYUB(Space& home,
588 bool& modified, ViewArray<View0>& x, View1& y,
589 GLBndSet& unionOfDets) {
590 int xsize = x.size();
591 Region reg;
592 LubRanges<View0>* xUBs = reg.alloc<LubRanges<View0> >(xsize);
593 int nonEmptyCounter=0;
594 for (int i = xsize; i--; ) {
595 LubRanges<View0> r(x[i]);
596 if (r()) {
597 xUBs[nonEmptyCounter] = r;
598 nonEmptyCounter++;
599 }
600 }
601 if (nonEmptyCounter != 0) {
602 Iter::Ranges::NaryUnion xUBUnion(reg,xUBs,nonEmptyCounter);
603 BndSetRanges dets(unionOfDets);
604 xUBUnion |= dets;
605 GECODE_ME_CHECK_MODIFIED(modified, y.intersectI(home,xUBUnion));
606 }
607 return ES_FIX;
608 }
609
610}}}
611
612#endif
613
614// STATISTICS: set-prop