Generated on Wed Jul 21 2021 00:00:00 for Gecode by doxygen 1.9.1
rel-op.cpp
Go to the documentation of this file.
1 /* -*- mode: C++; c-basic-offset: 2; indent-tabs-mode: nil -*- */
2 /*
3  * Main authors:
4  * Guido Tack <tack@gecode.org>
5  *
6  * Copyright:
7  * Guido Tack, 2005
8  *
9  * This file is part of Gecode, the generic constraint
10  * development environment:
11  * http://www.gecode.org
12  *
13  * Permission is hereby granted, free of charge, to any person obtaining
14  * a copy of this software and associated documentation files (the
15  * "Software"), to deal in the Software without restriction, including
16  * without limitation the rights to use, copy, modify, merge, publish,
17  * distribute, sublicense, and/or sell copies of the Software, and to
18  * permit persons to whom the Software is furnished to do so, subject to
19  * the following conditions:
20  *
21  * The above copyright notice and this permission notice shall be
22  * included in all copies or substantial portions of the Software.
23  *
24  * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,
25  * EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF
26  * MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND
27  * NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE
28  * LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION
29  * OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION
30  * WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
31  *
32  */
33 
34 #include "test/set.hh"
35 
36 using namespace Gecode;
37 
38 namespace Test { namespace Set {
39 
41  namespace RelOp {
42 
48 
49  static IntSet ds_22(-2,2);
50  static IntSet ds_12(-1,2);
51 
53  class Rel : public SetTest {
54  private:
57  int share;
58 
59  template<class I, class J>
60  bool
61  sol(I& i, J& j) const {
62  switch (srt) {
63  case SRT_EQ: return Iter::Ranges::equal(i,j);
64  case SRT_NQ: return !Iter::Ranges::equal(i,j);
65  case SRT_SUB: return Iter::Ranges::subset(i,j);
66  case SRT_SUP: return Iter::Ranges::subset(j,i);
67  case SRT_DISJ:
68  {
70  return !inter();
71  }
72  case SRT_CMPL:
73  {
75  return Iter::Ranges::equal(i,jc);
76  }
77  default: GECODE_NEVER;
78  }
79  return false;
80  }
81 
82  public:
84  Rel(Gecode::SetOpType sot0, Gecode::SetRelType srt0, int share0=0)
85  : SetTest("RelOp::"+str(sot0)+"::"+str(srt0)+"::S"+str(share0),
86  share0 == 0 ? 3 : 2,ds_22,false)
87  , sot(sot0), srt(srt0), share(share0) {}
89  bool solution(const SetAssignment& x) const {
90  int a=0, b=0, c=0;
91  switch (share) {
92  case 0: a=x[0]; b=x[1]; c=x[2]; break;
93  case 1: a=x[0]; b=x[0]; c=x[0]; break;
94  case 2: a=x[0]; b=x[0]; c=x[1]; break;
95  case 3: a=x[0]; b=x[1]; c=x[0]; break;
96  case 4: a=x[0]; b=x[1]; c=x[1]; break;
97  }
98  CountableSetRanges xr0(x.lub, a);
99  CountableSetRanges xr1(x.lub, b);
100  CountableSetRanges xr2(x.lub, c);
101  switch (sot) {
102  case SOT_UNION:
103  {
105  u(xr0,xr1);
106  return sol(u,xr2);
107  }
108  break;
109  case SOT_DUNION:
110  {
112  inter(xr0,xr1);
113  if (inter())
114  return false;
116  u(xr0,xr1);
117  return sol(u,xr2);
118  }
119  break;
120  case SOT_INTER:
121  {
123  u(xr0,xr1);
124  return sol(u,xr2);
125  }
126  break;
127  case SOT_MINUS:
128  {
130  u(xr0,xr1);
131  return sol(u,xr2);
132  }
133  break;
134  default: GECODE_NEVER;
135  }
136  GECODE_NEVER;
137  return false;
138  }
140  void post(Space& home, SetVarArray& x, IntVarArray&) {
141  SetVar a,b,c;
142  switch (share) {
143  case 0: a=x[0]; b=x[1]; c=x[2]; break;
144  case 1: a=x[0]; b=x[0]; c=x[0]; break;
145  case 2: a=x[0]; b=x[0]; c=x[1]; break;
146  case 3: a=x[0]; b=x[1]; c=x[0]; break;
147  case 4: a=x[0]; b=x[1]; c=x[1]; break;
148  }
149  Gecode::rel(home, a, sot, b, srt, c);
150  }
151  };
152 
154  class Create {
155  public:
157  Create(void) {
158  using namespace Gecode;
159  for (SetRelTypes srts; srts(); ++srts) {
160  for (SetOpTypes sots; sots(); ++sots) {
161  for (int i=0; i<=4; i++) {
162  (void) new Rel(sots.sot(),srts.srt(),i);
163  }
164  }
165  }
166  }
167  };
168 
170 
172  class RelN : public SetTest {
173  private:
174  Gecode::SetOpType sot;
175  int n;
176  int shared;
177  bool withConst;
178  IntSet is;
179  public:
181  RelN(Gecode::SetOpType sot0, int n0, int shared0, bool withConst0)
182  : SetTest("RelOp::N::"+str(sot0)+"::"+str(n0)+"::S"+str(shared0)+
183  "::C"+str(withConst0 ? 1 : 0),
184  shared0 == 0 ? n0+1 : (shared0 <= 2 ? 3 : 2),ds_12,false)
185  , sot(sot0), n(n0), shared(shared0), withConst(withConst0)
186  , is(0,1) {
187  }
189  bool solution(const SetAssignment& x) const {
190  int realN = shared == 0 ? n : 3;
191 
192  CountableSetRanges* isrs = new CountableSetRanges[realN];
193 
194  switch (shared) {
195  case 0:
196  for (int i=realN; i--; )
197  isrs[i].init(x.lub, x[i]);
198  break;
199  case 1:
200  isrs[0].init(x.lub, x[0]);
201  isrs[1].init(x.lub, x[0]);
202  isrs[2].init(x.lub, x[1]);
203  break;
204  case 2:
205  isrs[0].init(x.lub, x[0]);
206  isrs[1].init(x.lub, x[1]);
207  isrs[2].init(x.lub, x[2]);
208  break;
209  case 3:
210  isrs[0].init(x.lub, x[0]);
211  isrs[1].init(x.lub, x[1]);
212  isrs[2].init(x.lub, x[0]);
213  break;
214  default:
215  GECODE_NEVER;
216  }
217 
218  int result = shared == 0 ? x.size() - 1 : (shared <= 2 ? 2 : 0);
219  CountableSetRanges xnr(x.lub, x[result]);
220 
221  switch (sot) {
222  case SOT_DUNION:
223  {
224  if (shared == 1 && (isrs[0]() || isrs[1]())) {
225  delete[] isrs; return false;
226  }
227  if (shared == 3 && (isrs[0]() || isrs[2]())) {
228  delete[] isrs; return false;
229  }
230  unsigned int cardSum = 0;
231  if (shared == 1 || shared == 3) {
232  CountableSetRanges x1r(x.lub, x[1]);
233  cardSum = Iter::Ranges::size(x1r);
234  } else {
235  for (int i=0; i<realN; i++) {
236  CountableSetRanges xir(x.lub, x[i]);
237  cardSum += Iter::Ranges::size(xir);
238  }
239  }
240  if (withConst)
241  cardSum += 2;
242  CountableSetRanges xnr2(x.lub, x[result]);
243  if (cardSum != Iter::Ranges::size(xnr2)) {
244  delete[] isrs; return false;
245  }
246  }
247  // fall through to union case
248  case SOT_UNION:
249  {
250  bool eq;
251  if (withConst) {
252  Region r;
253  Iter::Ranges::NaryUnion u(r, isrs, realN);
254  IntSetRanges isr(is);
256  Iter::Ranges::NaryUnion> uu(isr, u);
257  eq = Iter::Ranges::equal(uu, xnr);
258  } else {
259  Region r;
260  Iter::Ranges::NaryUnion u(r, isrs, realN);
261  eq = Iter::Ranges::equal(u, xnr);
262  }
263  delete [] isrs;
264  return eq;
265  }
266  case SOT_INTER:
267  {
268  if (withConst) {
269  bool eq;
270  {
271  Region r;
272  Iter::Ranges::NaryInter u(r, isrs, realN);
273  IntSetRanges isr(is);
275  Iter::Ranges::NaryInter> uu(isr, u);
276  eq = (realN == 0 ? Iter::Ranges::equal(isr, xnr) :
277  Iter::Ranges::equal(uu, xnr));
278  delete [] isrs;
279  }
280  return eq;
281  } else {
282  if (realN == 0) {
283  bool ret =
285  delete [] isrs;
286  return ret;
287  } else {
288  bool eq;
289  {
290  Region r;
291  Iter::Ranges::NaryInter u(r,isrs, realN);
292  eq = Iter::Ranges::equal(u, xnr);
293  }
294  delete [] isrs;
295  return eq;
296  }
297  }
298  }
299  default:
300  GECODE_NEVER;
301  }
302  GECODE_NEVER;
303  return false;
304  }
306  void post(Space& home, SetVarArray& x, IntVarArray&) {
307  int size = shared == 0 ? x.size()-1 : 3;
308  SetVarArgs xs(size);
309  SetVar xn;
310  switch (shared) {
311  case 0:
312  for (int i=x.size()-1; i--;)
313  xs[i]=x[i];
314  xn = x[x.size()-1];
315  break;
316  case 1:
317  xs[0] = x[0]; xs[1] = x[0]; xs[2] = x[1]; xn = x[2];
318  break;
319  case 2:
320  xs[0] = x[0]; xs[1] = x[1]; xs[2] = x[2]; xn = x[2];
321  break;
322  case 3:
323  xs[0] = x[0]; xs[1] = x[1]; xs[2] = x[0]; xn = x[0];
324  break;
325  default:
326  GECODE_NEVER;
327  break;
328  }
329  if (!withConst)
330  Gecode::rel(home, sot, xs, xn);
331  else
332  Gecode::rel(home, sot, xs, is, xn);
333  }
334  };
335 
337  class CreateN {
338  public:
340  CreateN(void) {
341  for (int wc=0; wc<=1; wc++) {
342  for (int i=0; i<=3; i++) {
343  (void) new RelN(Gecode::SOT_UNION, i, 0, wc);
344  (void) new RelN(Gecode::SOT_DUNION, i, 0, wc);
345  (void) new RelN(Gecode::SOT_INTER, i, 0, wc);
346 
347  if (i>0) {
348  (void) new RelN(Gecode::SOT_UNION, 0, i, wc);
349  (void) new RelN(Gecode::SOT_DUNION, 0, i, wc);
350  (void) new RelN(Gecode::SOT_INTER, 0, i, wc);
351  }
352  }
353  }
354  }
355  };
356 
358 
360  class RelIntN : public SetTest {
361  private:
362  Gecode::SetOpType sot;
363  int n;
364  bool withConst;
365  IntSet is;
366  public:
368  RelIntN(Gecode::SetOpType sot0, int n0, bool withConst0)
369  : SetTest("RelOp::IntN::"+str(sot0)+"::"+str(n0)+
370  "::C"+str(withConst0 ? 1 : 0),
371  1,ds_12,false,n0)
372  , sot(sot0), n(n0), withConst(withConst0)
373  , is(0,1) {
374  }
376  bool solution(const SetAssignment& x) const {
377  int* isrs = new int[n];
378  for (int i=0; i<n; i++)
379  isrs[i] = x.ints()[i];
380 
381  IntSet iss(isrs,n);
382  CountableSetRanges xnr(x.lub, x[0]);
383 
384  switch (sot) {
385  case SOT_DUNION:
386  {
387  IntSetRanges issr(iss);
388  unsigned int cardSum = Iter::Ranges::size(issr);
389  if (cardSum != static_cast<unsigned int>(n)) {
390  delete[] isrs;
391  return false;
392  }
393  if (withConst) {
394  IntSetRanges isr(is);
395  cardSum += Iter::Ranges::size(isr);
396  }
397  CountableSetRanges xnr2(x.lub, x[0]);
398  if (cardSum != Iter::Ranges::size(xnr2)) {
399  delete[] isrs;
400  return false;
401  }
402  }
403  // fall through to union case
404  case SOT_UNION:
405  {
406  if (withConst) {
407  IntSetRanges issr(iss);
408  IntSetRanges isr(is);
410  delete[] isrs;
411  return Iter::Ranges::equal(uu, xnr);
412  } else {
413  IntSetRanges issr(iss);
414  delete[] isrs;
415  return Iter::Ranges::equal(issr, xnr);
416  }
417  }
418  case SOT_INTER:
419  {
420  bool allEqual = true;
421  for (int i=1; i<n; i++) {
422  if (isrs[i] != isrs[0]) {
423  allEqual = false;
424  break;
425  }
426  }
427  if (withConst) {
428  if (allEqual) {
429  if (n == 0) {
430  IntSetRanges isr(is);
431  delete[] isrs;
432  return Iter::Ranges::equal(isr, xnr);
433  } else {
434  Iter::Ranges::Singleton s(isrs[0],isrs[0]);
435  IntSetRanges isr(is);
437  uu(isr, s);
438  delete[] isrs;
439  return Iter::Ranges::equal(uu, xnr);
440  }
441  } else {
442  delete[] isrs;
443  return Iter::Ranges::size(xnr) == 0;
444  }
445  } else {
446  if (allEqual) {
447  if (n == 0) {
448  delete[] isrs;
450  } else {
451  Iter::Ranges::Singleton s(isrs[0],isrs[0]);
452  delete[] isrs;
453  return Iter::Ranges::equal(s, xnr);
454  }
455  } else {
456  delete[] isrs;
457  return Iter::Ranges::size(xnr) == 0;
458  }
459  }
460  }
461  default:
462  GECODE_NEVER;
463  }
464  GECODE_NEVER;
465  return false;
466  }
468  void post(Space& home, SetVarArray& x, IntVarArray& y) {
469  if (!withConst)
470  Gecode::rel(home, sot, y, x[0]);
471  else
472  Gecode::rel(home, sot, y, is, x[0]);
473  }
474  };
475 
477  class CreateIntN {
478  public:
480  CreateIntN(void) {
481  for (int wc=0; wc<=1; wc++) {
482  for (int i=0; i<=3; i++) {
483  (void) new RelIntN(Gecode::SOT_UNION, i, wc);
484  (void) new RelIntN(Gecode::SOT_DUNION, i, wc);
485  (void) new RelIntN(Gecode::SOT_INTER, i, wc);
486  }
487  }
488  }
489  };
490 
492 
494 
495 }}}
496 
497 // STATISTICS: test-set
struct Gecode::@602::NNF::@65::@66 b
For binary nodes (and, or, eqv)
union Gecode::@602::NNF::@65 u
Union depending on nodetype t.
int n
Number of negative literals for node type.
Definition: bool-expr.cpp:234
Node * x
Pointer to corresponding Boolean expression node.
Definition: bool-expr.cpp:249
struct Gecode::@602::NNF::@65::@67 a
For atomic nodes.
NNF * r
Right subtree.
Definition: bool-expr.cpp:242
Range iterator for integer sets.
Definition: int.hh:292
Integer sets.
Definition: int.hh:174
Integer variable array.
Definition: int.hh:763
Range iterator for computing set difference.
Definition: ranges-diff.hpp:43
Range iterator for computing intersection (binary)
Range iterator for intersection of iterators.
Range iterator for union of iterators.
Range iterator for singleton range.
Range iterator for computing union (binary)
Passing set variables.
Definition: set.hh:488
Set variable array
Definition: set.hh:570
Set variables
Definition: set.hh:127
A complement iterator spezialized for the BndSet limits.
Definition: var-imp.hpp:293
Computation spaces.
Definition: core.hpp:1742
Test for Region memory area
Definition: region.cpp:42
Range iterator producing subsets of an IntSet.
Definition: set.hh:99
void init(const Gecode::IntSet &d, int cur)
Initialize with set d0 and bit-pattern cur0.
Definition: set.hh:111
Help class to create and register tests.
Definition: rel-op.cpp:477
CreateIntN(void)
Perform creation and registration.
Definition: rel-op.cpp:480
Help class to create and register tests.
Definition: rel-op.cpp:337
CreateN(void)
Perform creation and registration.
Definition: rel-op.cpp:340
Help class to create and register tests.
Definition: rel-op.cpp:154
Create(void)
Perform creation and registration.
Definition: rel-op.cpp:157
Test for n-ary partition constraint
Definition: rel-op.cpp:360
bool solution(const SetAssignment &x) const
Test whether x is solution
Definition: rel-op.cpp:376
RelIntN(Gecode::SetOpType sot0, int n0, bool withConst0)
Create and register test.
Definition: rel-op.cpp:368
void post(Space &home, SetVarArray &x, IntVarArray &y)
Post constraint on x.
Definition: rel-op.cpp:468
Test for n-ary partition constraint
Definition: rel-op.cpp:172
void post(Space &home, SetVarArray &x, IntVarArray &)
Post constraint on x.
Definition: rel-op.cpp:306
bool solution(const SetAssignment &x) const
Test whether x is solution
Definition: rel-op.cpp:189
RelN(Gecode::SetOpType sot0, int n0, int shared0, bool withConst0)
Create and register test.
Definition: rel-op.cpp:181
Test for ternary relation constraint
Definition: rel-op.cpp:53
bool solution(const SetAssignment &x) const
Test whether x is solution
Definition: rel-op.cpp:89
Rel(Gecode::SetOpType sot0, Gecode::SetRelType srt0, int share0=0)
Create and register test.
Definition: rel-op.cpp:84
void post(Space &home, SetVarArray &x, IntVarArray &)
Post constraint on x.
Definition: rel-op.cpp:140
Generate all set assignments.
Definition: set.hh:142
Iterator for Boolean operation types.
Definition: set.hh:352
Iterator for set relation types.
Definition: set.hh:334
Base class for tests with set constraints
Definition: set.hh:273
Post propagator for SetVar SetOpType SetVar y
Definition: set.hh:767
void rel(Home home, FloatVar x0, FloatRelType frt, FloatVal n)
Propagates .
Definition: rel.cpp:43
SetOpType
Common operations for sets.
Definition: set.hh:660
SetRelType
Common relation types for sets.
Definition: set.hh:643
@ SOT_MINUS
Difference.
Definition: set.hh:664
@ SOT_DUNION
Disjoint union.
Definition: set.hh:662
@ SOT_UNION
Union.
Definition: set.hh:661
@ SOT_INTER
Intersection
Definition: set.hh:663
@ SRT_CMPL
Complement.
Definition: set.hh:649
@ SRT_NQ
Disequality ( )
Definition: set.hh:645
@ SRT_EQ
Equality ( )
Definition: set.hh:644
@ SRT_SUP
Superset ( )
Definition: set.hh:647
@ SRT_DISJ
Disjoint ( )
Definition: set.hh:648
@ SRT_SUB
Subset ( )
Definition: set.hh:646
bool shared(const IntSet &, VX)
Definition: view-base.hpp:118
bool subset(I &i, J &j)
Check whether range iterator i is subset of range iterator j.
unsigned int size(I &i)
Size of all ranges of range iterator i.
bool equal(I &i, J &j)
Check whether range iterators i and j are equal.
const unsigned int card
Maximum cardinality of an integer set.
Definition: set.hh:101
Gecode::IntArgs i({1, 2, 3, 4})
CreateIntN intcn
Definition: rel-op.cpp:491
General test support.
Definition: afc.cpp:39
SetExpr inter(const SetVarArgs &x)
Intersection of set variables.
Definition: set-expr.cpp:696
#define GECODE_NEVER
Assert that this command is never executed.
Definition: macros.hpp:56