40 #ifndef __GECODE_SET_RELOP_COMM_ICC__ 41 #define __GECODE_SET_RELOP_COMM_ICC__ 45 template<
class View0,
class View1>
53 viewarrayshared<Set::SingletonView,Set::SetView>
60 viewarrayshared<Set::ComplementView<Set::SingletonView>,
Set::SetView>
68 viewarrayshared<Set::ComplementView<Set::SingletonView>,
70 (
const ViewArray<Set::ComplementView<Set::SingletonView> >&,
76 namespace Set {
namespace RelOp {
82 template<
class View0,
class View1,
class View2>
88 template<
class View0,
class View1,
class View2>
90 bool& retmodified, View0& x0, View1& x1, View2& x2) {
91 bool modified =
false;
93 retmodified |= modified;
103 if (x0.cardMin() + x1.cardMin() > s1) {
105 x2.cardMin(home, x0.cardMin()+x1.cardMin()-s1));
124 x0.cardMax()+x1.cardMax()-s1));
127 if (x2.cardMax() < x1.cardMin())
132 if (x2.cardMax() < x0.cardMin())
138 x0.cardMin(home,x2.cardMin()));
140 x1.cardMin(home,x2.cardMin()));
144 template<
class View0,
class View1,
class View2>
146 bool& retmodified, View0& x0, View1& x1, View2& x2) {
147 bool modified =
false;
149 retmodified |= modified;
157 unsigned int res =
std::max(x0.cardMin()+
159 0 : x1.cardMin()-s1),
172 std::min(x0.cardMax()+x1.cardMax(),s1)));
175 if (x2.cardMin() > x1.cardMax())
177 x0.cardMin(home,x2.cardMin() - x1.cardMax()));
179 if (x2.cardMin() > x0.cardMax())
181 x1.cardMin(home,x2.cardMin() - x0.cardMax()));
184 x0.cardMax(home,x2.cardMax()));
186 x1.cardMax(home,x2.cardMax()));
191 template<
class View0,
class View1>
195 int xsize = x.
size();
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; }
217 unsigned int* rightSum = r.
alloc<
unsigned int>(xsize);
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]) {
224 for (
int j=
i; j>0;j--) {
232 unsigned int leftAcc=unionOfDets.
size();
234 for (
int i=0;
i<xsize;
i++) {
235 unsigned int jsum = leftAcc+rightSum[
i];
237 if (jsum >= leftAcc && jsum < y.cardMin()) {
240 leftAcc += x[
i].cardMax();
250 new (&rightUnion[xsize-1])
GLBndSet(home);
251 for (
int i=xsize-1;
i--;) {
262 leftAcc.
update(home,unionOfDets);
263 for (
int i=0;
i<xsize;
i++) {
267 BndSetRanges> iter(left, right);
269 if (y.cardMin() > unionSize) {
271 x[i].cardMin(home, y.cardMin() - unionSize) );
277 for (
int i=xsize;
i--;)
278 rightUnion[
i].dispose(home);
292 template<
class View0,
class View1>
297 int xsize = x.
size();
298 for (
int i=xsize;
i--; ) {
306 template<
class View0,
class View1>
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()) {
322 for (
int i=xsize;
i--; ) {
323 cardMaxSum+=x[
i].cardMax();
324 if (cardMaxSum < x[
i].cardMax()) {
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;
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]) {
349 for (
int j=
i; j>0;j--) {
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]) {
362 unsigned int leftMinAcc=unionOfDets.
size();
363 unsigned int leftMaxAcc=unionOfDets.
size();
365 for (
int i=0;
i<xsize;
i++) {
366 unsigned int maxSum = leftMaxAcc+rightMaxSum[
i];
367 unsigned int minSum = leftMinAcc+rightMinSum[
i];
369 if (maxSum >= leftMaxAcc && maxSum < y.cardMin()) {
374 if (minSum < leftMinAcc || y.cardMax() < minSum) {
381 leftMaxAcc += x[
i].cardMax();
382 if (leftMaxAcc < x[
i].cardMax())
384 leftMinAcc += x[
i].cardMin();
385 if (leftMinAcc < x[
i].cardMin())
395 template<
class View0,
class View1>
399 int xsize = x.
size();
409 for (
int i=xsize;
i--;) {
412 afterUB[
i].
update(home,sofarAfterUB);
413 afterLB[
i].
update(home,sofarAfterLB);
426 for (
int i=0;
i<xsize;
i++) {
431 BndSetRanges> xjlb(slb, afterlb);
434 BndSetRanges> > diff1(yub, xjlb);
438 BndSetRanges sub(sofarBeforeUB);
439 BndSetRanges afterub(afterUB[i]);
441 BndSetRanges> xjub(sub, afterub);
444 BndSetRanges> > diff2(ylb, xjub);
456 for (
int i=xsize;
i--;) {
465 template<
class View0,
class View1>
470 int xsize = x.
size();
477 for (
int i=xsize;
i--;) {
479 afterLB[
i].
update(home,sofarAfterLB);
488 sofarBeforeLB.
update(home,unionOfDets);
489 for (
int i=0;
i<xsize;
i++) {
494 BndSetRanges> xjlb(slb, afterlb);
497 BndSetRanges> > diff1(yub, xjlb);
505 for (
int i=xsize;
i--;)
506 afterLB[
i].dispose(home);
511 template<
class View0,
class View1>
516 int xsize = x.
size();
523 for (
int i=xsize;
i--;) {
525 afterUB[
i].
update(home,sofarAfterUB);
535 sofarBeforeUB.
update(home,unionOfDets);
536 for (
int i=0;
i<xsize;
i++) {
541 BndSetRanges> xjub(sub, afterub);
544 BndSetRanges> > diff2(ylb, xjub);
552 for (
int i=xsize;
i--;)
553 afterUB[
i].dispose(home);
558 template<
class View0,
class View1>
564 int xsize = x.
size();
567 int nonEmptyCounter=0;
568 for (
int i = xsize;
i--; ) {
571 xLBs[nonEmptyCounter] =
r;
575 if (nonEmptyCounter !=0) {
585 template<
class View0,
class View1>
590 int xsize = x.
size();
593 int nonEmptyCounter=0;
594 for (
int i = xsize;
i--; ) {
597 xUBs[nonEmptyCounter] =
r;
601 if (nonEmptyCounter != 0) {
ExecStatus partitionNXiUB(Space &home, bool &modified, ViewArray< View0 > &x, View1 &y, GLBndSet &unionOfDets)
ExecStatus partitionNYLB(Space &home, bool &modified, ViewArray< View0 > &x, View1 &y, GLBndSet &unionOfDets)
const Gecode::ModEvent ME_SET_FAILED
Domain operation has resulted in failure.
const FloatNum max
Largest allowed float value.
ExecStatus unionNXiUB(Space &home, bool &modified, ViewArray< View0 > &x, View1 &y, GLBndSet &)
T * alloc(long unsigned int n)
Allocate block of n objects of type T from region.
ExecStatus partitionNXiLB(Space &home, bool &modified, ViewArray< View0 > &x, View1 &y, GLBndSet &unionOfDets)
Range iterator for the greatest lower bound.
ExecStatus interCard(Space &home, bool &retmodified, View0 &x0, View1 &x1, View2 &x2)
ExecStatus unionNCard(Space &home, bool &modified, ViewArray< View0 > &x, View1 &y, GLBndSet &unionOfDets)
Propagation has computed fixpoint.
const unsigned int card
Maximum cardinality of an integer set.
#define GECODE_ME_CHECK_MODIFIED(modified, me)
Check whether me is failed or modified, and forward failure.
Range iterator for the least upper bound.
const FloatNum min
Smallest allowed float value.
unsigned int size(void) const
Return size.
bool overflow(Term *t, int n, FloatVal c)
Gecode::IntArgs i({1, 2, 3, 4})
Range iterator for computing intersection (binary)
Range iterator for union of iterators.
ExecStatus partitionNXi(Space &home, bool &modified, ViewArray< View0 > &x, View1 &y)
unsigned int size(I &i)
Size of all ranges of range iterator i.
Range iterator for integer sets.
bool viewarrayshared(const ViewArray< View0 > &va, const View1 &y)
bool isConsistent(void) const
Check whether internal invariants hold.
ExecStatus partitionNYUB(Space &home, bool &modified, ViewArray< View0 > &x, View1 &y, GLBndSet &unionOfDets)
void update(Space &home, BndSet &x)
Update this set to be a clone of set x.
#define GECODE_ME_CHECK(me)
Check whether modification event me is failed, and forward failure.
bool includeI(Space &home, I &i)
Include the set represented by i in this set.
void dispose(Space &home)
Free memory used by this set.
bool shared(View0 v0, View1 v1, View2 v2)
Range iterator for computing union (binary)
Post propagator for SetVar SetOpType SetVar SetRelType r
Set view for set variables
Post propagator for SetVar SetOpType SetVar y
Growing sets of integers.
ExecStatus partitionNCard(Space &home, bool &modified, ViewArray< View0 > &x, View1 &y, GLBndSet &unionOfDets)
Post propagator for SetVar x
Propagation has not computed fixpoint.
Gecode toplevel namespace
Gecode::IntArgs v1({Gecode::Int::Limits::min+4, 0, 1, Gecode::Int::Limits::max})
Range iterator for computing set difference.
bool shared(ViewArray< ViewX > x, ViewArray< ViewY > y)
Gecode::IntArgs v2({Gecode::Int::Limits::min, 0, 1, Gecode::Int::Limits::max-4})
int size(void) const
Return size of array (number of elements)
ExecStatus unionCard(Space &home, bool &retmodified, View0 &x0, View1 &x1, View2 &x2)
void * ralloc(size_t s)
Allocate memory from region.