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