Generated on Tue Jan 19 2021 06:15:49 for Gecode by doxygen 1.8.13
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
Test for n-ary partition constraint
Definition: rel-op.cpp:172
Create(void)
Perform creation and registration.
Definition: rel-op.cpp:157
CreateIntN intcn
Definition: rel-op.cpp:491
Iterator for Boolean operation types.
Definition: set.hh:352
SetRelType
Common relation types for sets.
Definition: set.hh:643
Iterator for set relation types.
Definition: set.hh:334
void post(Space &home, SetVarArray &x, IntVarArray &)
Post constraint on x.
Definition: rel-op.cpp:140
Range iterator for singleton range.
Range iterator for integer sets.
Definition: int.hh:292
void post(Space &home, SetVarArray &x, IntVarArray &y)
Post constraint on x.
Definition: rel-op.cpp:468
int size(void) const
Return size of array (number of elements)
Definition: array.hpp:908
CreateIntN(void)
Perform creation and registration.
Definition: rel-op.cpp:480
bool solution(const SetAssignment &x) const
Test whether x is solution
Definition: rel-op.cpp:189
bool equal(I &i, J &j)
Check whether range iterators i and j are equal.
Integer variable array.
Definition: int.hh:763
Test for ternary relation constraint
Definition: rel-op.cpp:53
SetOpType
Common operations for sets.
Definition: set.hh:660
Superset ( )
Definition: set.hh:647
Complement.
Definition: set.hh:649
const unsigned int card
Maximum cardinality of an integer set.
Definition: set.hh:101
Test for n-ary partition constraint
Definition: rel-op.cpp:360
Computation spaces.
Definition: core.hpp:1701
Difference.
Definition: set.hh:664
void init(const Gecode::IntSet &d, int cur)
Initialize with set d0 and bit-pattern cur0.
Definition: set.hh:111
Test for Region memory area
Definition: region.cpp:42
CreateN(void)
Perform creation and registration.
Definition: rel-op.cpp:340
void post(Space &home, SetVarArray &x, IntVarArray &)
Post constraint on x.
Definition: rel-op.cpp:306
Help class to create and register tests.
Definition: rel-op.cpp:337
int n
Number of negative literals for node type.
Definition: bool-expr.cpp:234
Gecode::IntArgs i({1, 2, 3, 4})
Range iterator for computing intersection (binary)
Range iterator for union of iterators.
A complement iterator spezialized for the BndSet limits.
Definition: var-imp.hpp:292
struct Gecode::@593::NNF::@62::@63 b
For binary nodes (and, or, eqv)
unsigned int size(I &i)
Size of all ranges of range iterator i.
bool solution(const SetAssignment &x) const
Test whether x is solution
Definition: rel-op.cpp:89
Subset ( )
Definition: set.hh:646
Gecode::IntSet lub
The common superset for all domains.
Definition: set.hh:154
RelIntN(Gecode::SetOpType sot0, int n0, bool withConst0)
Create and register test.
Definition: rel-op.cpp:368
Intersection
Definition: set.hh:663
Integer sets.
Definition: int.hh:174
const Test::Int::Assignment & ints(void) const
Return assignment for integer variables.
Definition: set.hh:171
Range iterator for computing union (binary)
union Gecode::@593::NNF::@62 u
Union depending on nodetype t.
Post propagator for SetVar SetOpType SetVar SetRelType r
Definition: set.hh:767
SetExpr inter(const SetVarArgs &x)
Intersection of set variables.
Definition: set-expr.cpp:696
General test support.
Definition: afc.cpp:39
Union.
Definition: set.hh:661
Passing set variables.
Definition: set.hh:488
Rel(Gecode::SetOpType sot0, Gecode::SetRelType srt0, int share0=0)
Create and register test.
Definition: rel-op.cpp:84
Post propagator for SetVar SetOpType SetVar y
Definition: set.hh:767
Set variables
Definition: set.hh:127
Help class to create and register tests.
Definition: rel-op.cpp:477
Range iterator for intersection of iterators.
Disjoint union.
Definition: set.hh:662
bool solution(const SetAssignment &x) const
Test whether x is solution
Definition: rel-op.cpp:376
Base class for tests with set constraints
Definition: set.hh:273
Generate all set assignments.
Definition: set.hh:142
void rel(Home home, FloatVar x0, FloatRelType frt, FloatVal n)
Propagates .
Definition: rel.cpp:43
Range iterator producing subsets of an IntSet.
Definition: set.hh:98
Equality ( )
Definition: set.hh:644
Disjoint ( )
Definition: set.hh:648
Post propagator for SetVar x
Definition: set.hh:767
bool subset(I &i, J &j)
Check whether range iterator i is subset of range iterator j.
Set variable array
Definition: set.hh:570
Disequality ( )
Definition: set.hh:645
RelN(Gecode::SetOpType sot0, int n0, int shared0, bool withConst0)
Create and register test.
Definition: rel-op.cpp:181
Gecode toplevel namespace
int size(void) const
Return arity.
Definition: set.hh:173
Range iterator for computing set difference.
Definition: ranges-diff.hpp:43
bool shared(ViewArray< ViewX > x, ViewArray< ViewY > y)
Definition: array.hpp:1428
#define GECODE_NEVER
Assert that this command is never executed.
Definition: macros.hpp:56
struct Gecode::@593::NNF::@62::@64 a
For atomic nodes.
Help class to create and register tests.
Definition: rel-op.cpp:154