Generated on Sat Jun 2 2018 07:17:44 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  }
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  }
135  GECODE_NEVER;
136  return false;
137  }
139  void post(Space& home, SetVarArray& x, IntVarArray&) {
140  SetVar a,b,c;
141  switch (share) {
142  case 0: a=x[0]; b=x[1]; c=x[2]; break;
143  case 1: a=x[0]; b=x[0]; c=x[0]; break;
144  case 2: a=x[0]; b=x[0]; c=x[1]; break;
145  case 3: a=x[0]; b=x[1]; c=x[0]; break;
146  case 4: a=x[0]; b=x[1]; c=x[1]; break;
147  }
148  Gecode::rel(home, a, sot, b, srt, c);
149  }
150  };
151 
153  class Create {
154  public:
156  Create(void) {
157  using namespace Gecode;
158  for (SetRelTypes srts; srts(); ++srts) {
159  for (SetOpTypes sots; sots(); ++sots) {
160  for (int i=0; i<=4; i++) {
161  (void) new Rel(sots.sot(),srts.srt(),i);
162  }
163  }
164  }
165  }
166  };
167 
169 
171  class RelN : public SetTest {
172  private:
173  Gecode::SetOpType sot;
174  int n;
175  int shared;
176  bool withConst;
177  IntSet is;
178  public:
180  RelN(Gecode::SetOpType sot0, int n0, int shared0, bool withConst0)
181  : SetTest("RelOp::N::"+str(sot0)+"::"+str(n0)+"::S"+str(shared0)+
182  "::C"+str(withConst0 ? 1 : 0),
183  shared0 == 0 ? n0+1 : (shared0 <= 2 ? 3 : 2),ds_12,false)
184  , sot(sot0), n(n0), shared(shared0), withConst(withConst0)
185  , is(0,1) {
186  }
188  bool solution(const SetAssignment& x) const {
189  int realN = shared == 0 ? n : 3;
190 
191  CountableSetRanges* isrs = new CountableSetRanges[realN];
192 
193  switch (shared) {
194  case 0:
195  for (int i=realN; i--; )
196  isrs[i].init(x.lub, x[i]);
197  break;
198  case 1:
199  isrs[0].init(x.lub, x[0]);
200  isrs[1].init(x.lub, x[0]);
201  isrs[2].init(x.lub, x[1]);
202  break;
203  case 2:
204  isrs[0].init(x.lub, x[0]);
205  isrs[1].init(x.lub, x[1]);
206  isrs[2].init(x.lub, x[2]);
207  break;
208  case 3:
209  isrs[0].init(x.lub, x[0]);
210  isrs[1].init(x.lub, x[1]);
211  isrs[2].init(x.lub, x[0]);
212  break;
213  default:
214  GECODE_NEVER;
215  }
216 
217  int result = shared == 0 ? x.size() - 1 : (shared <= 2 ? 2 : 0);
218  CountableSetRanges xnr(x.lub, x[result]);
219 
220  switch (sot) {
221  case SOT_DUNION:
222  {
223  if (shared == 1 && (isrs[0]() || isrs[1]())) {
224  delete[] isrs; return false;
225  }
226  if (shared == 3 && (isrs[0]() || isrs[2]())) {
227  delete[] isrs; return false;
228  }
229  unsigned int cardSum = 0;
230  if (shared == 1 || shared == 3) {
231  CountableSetRanges x1r(x.lub, x[1]);
232  cardSum = Iter::Ranges::size(x1r);
233  } else {
234  for (int i=0; i<realN; i++) {
235  CountableSetRanges xir(x.lub, x[i]);
236  cardSum += Iter::Ranges::size(xir);
237  }
238  }
239  if (withConst)
240  cardSum += 2;
241  CountableSetRanges xnr2(x.lub, x[result]);
242  if (cardSum != Iter::Ranges::size(xnr2)) {
243  delete[] isrs; return false;
244  }
245  }
246  // fall through to union case
247  case SOT_UNION:
248  {
249  bool eq;
250  if (withConst) {
251  Region r;
252  Iter::Ranges::NaryUnion u(r, isrs, realN);
253  IntSetRanges isr(is);
255  Iter::Ranges::NaryUnion> uu(isr, u);
256  eq = Iter::Ranges::equal(uu, xnr);
257  } else {
258  Region r;
259  Iter::Ranges::NaryUnion u(r, isrs, realN);
260  eq = Iter::Ranges::equal(u, xnr);
261  }
262  delete [] isrs;
263  return eq;
264  }
265  case SOT_INTER:
266  {
267  if (withConst) {
268  bool eq;
269  {
270  Region r;
271  Iter::Ranges::NaryInter u(r, isrs, realN);
272  IntSetRanges isr(is);
274  Iter::Ranges::NaryInter> uu(isr, u);
275  eq = (realN == 0 ? Iter::Ranges::equal(isr, xnr) :
276  Iter::Ranges::equal(uu, xnr));
277  delete [] isrs;
278  }
279  return eq;
280  } else {
281  if (realN == 0) {
282  bool ret =
284  delete [] isrs;
285  return ret;
286  } else {
287  bool eq;
288  {
289  Region r;
290  Iter::Ranges::NaryInter u(r,isrs, realN);
291  eq = Iter::Ranges::equal(u, xnr);
292  }
293  delete [] isrs;
294  return eq;
295  }
296  }
297  }
298  default:
299  GECODE_NEVER;
300  }
301  GECODE_NEVER;
302  return false;
303  }
305  void post(Space& home, SetVarArray& x, IntVarArray&) {
306  int size = shared == 0 ? x.size()-1 : 3;
307  SetVarArgs xs(size);
308  SetVar xn;
309  switch (shared) {
310  case 0:
311  for (int i=x.size()-1; i--;)
312  xs[i]=x[i];
313  xn = x[x.size()-1];
314  break;
315  case 1:
316  xs[0] = x[0]; xs[1] = x[0]; xs[2] = x[1]; xn = x[2];
317  break;
318  case 2:
319  xs[0] = x[0]; xs[1] = x[1]; xs[2] = x[2]; xn = x[2];
320  break;
321  case 3:
322  xs[0] = x[0]; xs[1] = x[1]; xs[2] = x[0]; xn = x[0];
323  break;
324  default:
325  GECODE_NEVER;
326  break;
327  }
328  if (!withConst)
329  Gecode::rel(home, sot, xs, xn);
330  else
331  Gecode::rel(home, sot, xs, is, xn);
332  }
333  };
334 
336  class CreateN {
337  public:
339  CreateN(void) {
340  for (int wc=0; wc<=1; wc++) {
341  for (int i=0; i<=3; i++) {
342  (void) new RelN(Gecode::SOT_UNION, i, 0, wc);
343  (void) new RelN(Gecode::SOT_DUNION, i, 0, wc);
344  (void) new RelN(Gecode::SOT_INTER, i, 0, wc);
345 
346  if (i>0) {
347  (void) new RelN(Gecode::SOT_UNION, 0, i, wc);
348  (void) new RelN(Gecode::SOT_DUNION, 0, i, wc);
349  (void) new RelN(Gecode::SOT_INTER, 0, i, wc);
350  }
351  }
352  }
353  }
354  };
355 
357 
359  class RelIntN : public SetTest {
360  private:
361  Gecode::SetOpType sot;
362  int n;
363  bool withConst;
364  IntSet is;
365  public:
367  RelIntN(Gecode::SetOpType sot0, int n0, bool withConst0)
368  : SetTest("RelOp::IntN::"+str(sot0)+"::"+str(n0)+
369  "::C"+str(withConst0 ? 1 : 0),
370  1,ds_12,false,n0)
371  , sot(sot0), n(n0), withConst(withConst0)
372  , is(0,1) {
373  }
375  bool solution(const SetAssignment& x) const {
376  int* isrs = new int[n];
377  for (int i=0; i<n; i++)
378  isrs[i] = x.ints()[i];
379 
380  IntSet iss(isrs,n);
381  CountableSetRanges xnr(x.lub, x[0]);
382 
383  switch (sot) {
384  case SOT_DUNION:
385  {
386  IntSetRanges issr(iss);
387  unsigned int cardSum = Iter::Ranges::size(issr);
388  if (cardSum != static_cast<unsigned int>(n)) {
389  delete[] isrs;
390  return false;
391  }
392  if (withConst) {
393  IntSetRanges isr(is);
394  cardSum += Iter::Ranges::size(isr);
395  }
396  CountableSetRanges xnr2(x.lub, x[0]);
397  if (cardSum != Iter::Ranges::size(xnr2)) {
398  delete[] isrs;
399  return false;
400  }
401  }
402  // fall through to union case
403  case SOT_UNION:
404  {
405  if (withConst) {
406  IntSetRanges issr(iss);
407  IntSetRanges isr(is);
409  delete[] isrs;
410  return Iter::Ranges::equal(uu, xnr);
411  } else {
412  IntSetRanges issr(iss);
413  delete[] isrs;
414  return Iter::Ranges::equal(issr, xnr);
415  }
416  }
417  case SOT_INTER:
418  {
419  bool allEqual = true;
420  for (int i=1; i<n; i++) {
421  if (isrs[i] != isrs[0]) {
422  allEqual = false;
423  break;
424  }
425  }
426  if (withConst) {
427  if (allEqual) {
428  if (n == 0) {
429  IntSetRanges isr(is);
430  delete[] isrs;
431  return Iter::Ranges::equal(isr, xnr);
432  } else {
433  Iter::Ranges::Singleton s(isrs[0],isrs[0]);
434  IntSetRanges isr(is);
436  uu(isr, s);
437  delete[] isrs;
438  return Iter::Ranges::equal(uu, xnr);
439  }
440  } else {
441  delete[] isrs;
442  return Iter::Ranges::size(xnr) == 0;
443  }
444  } else {
445  if (allEqual) {
446  if (n == 0) {
447  delete[] isrs;
449  } else {
450  Iter::Ranges::Singleton s(isrs[0],isrs[0]);
451  delete[] isrs;
452  return Iter::Ranges::equal(s, xnr);
453  }
454  } else {
455  delete[] isrs;
456  return Iter::Ranges::size(xnr) == 0;
457  }
458  }
459  }
460  default:
461  GECODE_NEVER;
462  }
463  GECODE_NEVER;
464  return false;
465  }
467  void post(Space& home, SetVarArray& x, IntVarArray& y) {
468  if (!withConst)
469  Gecode::rel(home, sot, y, x[0]);
470  else
471  Gecode::rel(home, sot, y, is, x[0]);
472  }
473  };
474 
476  class CreateIntN {
477  public:
479  CreateIntN(void) {
480  for (int wc=0; wc<=1; wc++) {
481  for (int i=0; i<=3; i++) {
482  (void) new RelIntN(Gecode::SOT_UNION, i, wc);
483  (void) new RelIntN(Gecode::SOT_DUNION, i, wc);
484  (void) new RelIntN(Gecode::SOT_INTER, i, wc);
485  }
486  }
487  }
488  };
489 
491 
493 
494 }}}
495 
496 // STATISTICS: test-set
Test for n-ary partition constraint
Definition: rel-op.cpp:171
Create(void)
Perform creation and registration.
Definition: rel-op.cpp:156
CreateIntN intcn
Definition: rel-op.cpp:490
Iterator for Boolean operation types.
Definition: set.hh:352
SetRelType
Common relation types for sets.
Definition: set.hh:641
Iterator for set relation types.
Definition: set.hh:334
void post(Space &home, SetVarArray &x, IntVarArray &)
Post constraint on x.
Definition: rel-op.cpp:139
Range iterator for singleton range.
Range iterator for integer sets.
Definition: int.hh:268
void post(Space &home, SetVarArray &x, IntVarArray &y)
Post constraint on x.
Definition: rel-op.cpp:467
int size(void) const
Return size of array (number of elements)
Definition: array.hpp:969
CreateIntN(void)
Perform creation and registration.
Definition: rel-op.cpp:479
bool solution(const SetAssignment &x) const
Test whether x is solution
Definition: rel-op.cpp:188
bool equal(I &i, J &j)
Check whether range iterators i and j are equal.
Integer variable array.
Definition: int.hh:738
Test for ternary relation constraint
Definition: rel-op.cpp:53
SetOpType
Common operations for sets.
Definition: set.hh:658
Superset ( )
Definition: set.hh:645
Complement.
Definition: set.hh:647
const unsigned int card
Maximum cardinality of an integer set.
Definition: set.hh:101
Test for n-ary partition constraint
Definition: rel-op.cpp:359
Computation spaces.
Definition: core.hpp:1701
Difference.
Definition: set.hh:662
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:339
void post(Space &home, SetVarArray &x, IntVarArray &)
Post constraint on x.
Definition: rel-op.cpp:305
Help class to create and register tests.
Definition: rel-op.cpp:336
Gecode::IntArgs i(4, 1, 2, 3, 4)
int n
Number of negative literals for node type.
Definition: bool-expr.cpp:234
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
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:644
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:367
Intersection
Definition: set.hh:661
union Gecode::@585::NNF::@62 u
Union depending on nodetype t.
Integer sets.
Definition: int.hh:170
const Test::Int::Assignment & ints(void) const
Return assignment for integer variables.
Definition: set.hh:171
Range iterator for computing union (binary)
Post propagator for SetVar SetOpType SetVar SetRelType r
Definition: set.hh:765
SetExpr inter(const SetVarArgs &x)
Intersection of set variables.
Definition: set-expr.cpp:695
General test support.
Definition: afc.cpp:39
Union.
Definition: set.hh:659
struct Gecode::@585::NNF::@62::@63 b
For binary nodes (and, or, eqv)
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:765
Set variables
Definition: set.hh:127
Help class to create and register tests.
Definition: rel-op.cpp:476
struct Gecode::@585::NNF::@62::@64 a
For atomic nodes.
Range iterator for intersection of iterators.
Disjoint union.
Definition: set.hh:660
bool solution(const SetAssignment &x) const
Test whether x is solution
Definition: rel-op.cpp:375
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:642
Disjoint ( )
Definition: set.hh:646
Post propagator for SetVar x
Definition: set.hh:765
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:735
Set variable array
Definition: set.hh:568
Disequality ( )
Definition: set.hh:643
RelN(Gecode::SetOpType sot0, int n0, int shared0, bool withConst0)
Create and register test.
Definition: rel-op.cpp:180
Gecode toplevel namespace
int size(void) const
Return arity.
Definition: set.hh:173
Range iterator for computing set difference.
Definition: ranges-diff.hpp:43
#define GECODE_NEVER
Assert that this command is never executed.
Definition: macros.hpp:56
Help class to create and register tests.
Definition: rel-op.cpp:153