Generated on Sat Feb 7 2015 02:01:30 for Gecode by doxygen 1.8.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  * Last modified:
10  * $Date: 2012-09-07 17:31:22 +0200 (Fri, 07 Sep 2012) $ by $Author: schulte $
11  * $Revision: 13068 $
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) {}
191  bool solution(const SetAssignment& x) const {
192  int realN = shared == 0 ? n : 3;
193 
194  CountableSetRanges* isrs = new CountableSetRanges[realN];
195 
196  switch (shared) {
197  case 0:
198  for (int i=realN; i--; )
199  isrs[i].init(x.lub, x[i]);
200  break;
201  case 1:
202  isrs[0].init(x.lub, x[0]);
203  isrs[1].init(x.lub, x[0]);
204  isrs[2].init(x.lub, x[1]);
205  break;
206  case 2:
207  isrs[0].init(x.lub, x[0]);
208  isrs[1].init(x.lub, x[1]);
209  isrs[2].init(x.lub, x[2]);
210  break;
211  case 3:
212  isrs[0].init(x.lub, x[0]);
213  isrs[1].init(x.lub, x[1]);
214  isrs[2].init(x.lub, x[0]);
215  break;
216  default:
217  GECODE_NEVER;
218  }
219 
220  int result = shared == 0 ? x.size() - 1 : (shared <= 2 ? 2 : 0);
221  CountableSetRanges xnr(x.lub, x[result]);
222 
223  switch (sot) {
224  case SOT_DUNION:
225  {
226  if (shared == 1 && (isrs[0]() || isrs[1]())) {
227  delete[] isrs; return false;
228  }
229  if (shared == 3 && (isrs[0]() || isrs[2]())) {
230  delete[] isrs; return false;
231  }
232  unsigned int cardSum = 0;
233  if (shared == 1 || shared == 3) {
234  CountableSetRanges x1r(x.lub, x[1]);
235  cardSum = Iter::Ranges::size(x1r);
236  } else {
237  for (int i=0; i<realN; i++) {
238  CountableSetRanges xir(x.lub, x[i]);
239  cardSum += Iter::Ranges::size(xir);
240  }
241  }
242  if (withConst)
243  cardSum += 2;
244  CountableSetRanges xnr2(x.lub, x[result]);
245  if (cardSum != Iter::Ranges::size(xnr2)) {
246  delete[] isrs; return false;
247  }
248  }
249  // fall through to union case
250  case SOT_UNION:
251  {
252  FakeSpace* fs = new FakeSpace;
253  bool eq;
254  if (withConst) {
255  Region r(*fs);
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(*fs);
263  Iter::Ranges::NaryUnion u(r, isrs, realN);
264  eq = Iter::Ranges::equal(u, xnr);
265  }
266  delete [] isrs;
267  delete fs;
268  return eq;
269  }
270  case SOT_INTER:
271  {
272  if (withConst) {
273  FakeSpace* fs = new FakeSpace;
274  bool eq;
275  {
276  Region r(*fs);
277  Iter::Ranges::NaryInter u(r, isrs, realN);
278  IntSetRanges isr(is);
280  Iter::Ranges::NaryInter> uu(isr, u);
281  eq = (realN == 0 ? Iter::Ranges::equal(isr, xnr) :
282  Iter::Ranges::equal(uu, xnr));
283  delete [] isrs;
284  }
285  delete fs;
286  return eq;
287  } else {
288  if (realN == 0) {
289  bool ret =
291  delete [] isrs;
292  return ret;
293  } else {
294  FakeSpace* fs = new FakeSpace;
295  bool eq;
296  {
297  Region r(*fs);
298  Iter::Ranges::NaryInter u(r,isrs, realN);
299  eq = Iter::Ranges::equal(u, xnr);
300  }
301  delete [] isrs;
302  delete fs;
303  return eq;
304  }
305  }
306  }
307  default:
308  GECODE_NEVER;
309  }
310  GECODE_NEVER;
311  return false;
312  }
314  void post(Space& home, SetVarArray& x, IntVarArray&) {
315  int size = shared == 0 ? x.size()-1 : 3;
316  SetVarArgs xs(size);
317  SetVar xn;
318  switch (shared) {
319  case 0:
320  for (int i=x.size()-1; i--;)
321  xs[i]=x[i];
322  xn = x[x.size()-1];
323  break;
324  case 1:
325  xs[0] = x[0]; xs[1] = x[0]; xs[2] = x[1]; xn = x[2];
326  break;
327  case 2:
328  xs[0] = x[0]; xs[1] = x[1]; xs[2] = x[2]; xn = x[2];
329  break;
330  case 3:
331  xs[0] = x[0]; xs[1] = x[1]; xs[2] = x[0]; xn = x[0];
332  break;
333  default:
334  GECODE_NEVER;
335  break;
336  }
337  if (!withConst)
338  Gecode::rel(home, sot, xs, xn);
339  else
340  Gecode::rel(home, sot, xs, is, xn);
341  }
342  };
343 
345  class CreateN {
346  public:
348  CreateN(void) {
349  for (int wc=0; wc<=1; wc++) {
350  for (int i=0; i<=3; i++) {
351  (void) new RelN(Gecode::SOT_UNION, i, 0, wc);
352  (void) new RelN(Gecode::SOT_DUNION, i, 0, wc);
353  (void) new RelN(Gecode::SOT_INTER, i, 0, wc);
354 
355  if (i>0) {
356  (void) new RelN(Gecode::SOT_UNION, 0, i, wc);
357  (void) new RelN(Gecode::SOT_DUNION, 0, i, wc);
358  (void) new RelN(Gecode::SOT_INTER, 0, i, wc);
359  }
360  }
361  }
362  }
363  };
364 
366 
368  class RelIntN : public SetTest {
369  private:
370  Gecode::SetOpType sot;
371  int n;
372  bool withConst;
373  IntSet is;
374  public:
376  RelIntN(Gecode::SetOpType sot0, int n0, bool withConst0)
377  : SetTest("RelOp::IntN::"+str(sot0)+"::"+str(n0)+
378  "::C"+str(withConst0 ? 1 : 0),
379  1,ds_12,false,n0)
380  , sot(sot0), n(n0), withConst(withConst0)
381  , is(0,1) {}
383  bool solution(const SetAssignment& x) const {
384  int* isrs = new int[n];
385  for (int i=0; i<n; i++)
386  isrs[i] = x.ints()[i];
387 
388  IntSet iss(isrs,n);
389  CountableSetRanges xnr(x.lub, x[0]);
390 
391  switch (sot) {
392  case SOT_DUNION:
393  {
394  IntSetRanges issr(iss);
395  unsigned int cardSum = Iter::Ranges::size(issr);
396  if (cardSum != static_cast<unsigned int>(n)) {
397  delete[] isrs;
398  return false;
399  }
400  if (withConst) {
401  IntSetRanges isr(is);
402  cardSum += Iter::Ranges::size(isr);
403  }
404  CountableSetRanges xnr2(x.lub, x[0]);
405  if (cardSum != Iter::Ranges::size(xnr2)) {
406  delete[] isrs;
407  return false;
408  }
409  }
410  // fall through to union case
411  case SOT_UNION:
412  {
413  if (withConst) {
414  IntSetRanges issr(iss);
415  IntSetRanges isr(is);
417  delete[] isrs;
418  return Iter::Ranges::equal(uu, xnr);
419  } else {
420  IntSetRanges issr(iss);
421  delete[] isrs;
422  return Iter::Ranges::equal(issr, xnr);
423  }
424  }
425  case SOT_INTER:
426  {
427  bool allEqual = true;
428  for (int i=1; i<n; i++) {
429  if (isrs[i] != isrs[0]) {
430  allEqual = false;
431  break;
432  }
433  }
434  if (withConst) {
435  if (allEqual) {
436  if (n == 0) {
437  IntSetRanges isr(is);
438  delete[] isrs;
439  return Iter::Ranges::equal(isr, xnr);
440  } else {
441  Iter::Ranges::Singleton s(isrs[0],isrs[0]);
442  IntSetRanges isr(is);
444  uu(isr, s);
445  delete[] isrs;
446  return Iter::Ranges::equal(uu, xnr);
447  }
448  } else {
449  delete[] isrs;
450  return Iter::Ranges::size(xnr) == 0;
451  }
452  } else {
453  if (allEqual) {
454  if (n == 0) {
455  delete[] isrs;
457  } else {
458  Iter::Ranges::Singleton s(isrs[0],isrs[0]);
459  delete[] isrs;
460  return Iter::Ranges::equal(s, xnr);
461  }
462  } else {
463  delete[] isrs;
464  return Iter::Ranges::size(xnr) == 0;
465  }
466  }
467  }
468  default:
469  GECODE_NEVER;
470  }
471  GECODE_NEVER;
472  return false;
473  }
475  void post(Space& home, SetVarArray& x, IntVarArray& y) {
476  if (!withConst)
477  Gecode::rel(home, sot, y, x[0]);
478  else
479  Gecode::rel(home, sot, y, is, x[0]);
480  }
481  };
482 
484  class CreateIntN {
485  public:
487  CreateIntN(void) {
488  for (int wc=0; wc<=1; wc++) {
489  for (int i=0; i<=3; i++) {
490  (void) new RelIntN(Gecode::SOT_UNION, i, wc);
491  (void) new RelIntN(Gecode::SOT_DUNION, i, wc);
492  (void) new RelIntN(Gecode::SOT_INTER, i, wc);
493  }
494  }
495  }
496  };
497 
499 
501 
502 }}}
503 
504 // 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:498
Iterator for Boolean operation types.
Definition: set.hh:343
SetRelType
Common relation types for sets.
Definition: set.hh:644
int size(void) const
Return arity.
Definition: set.hh:189
Iterator for set relation types.
Definition: set.hh:325
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:271
void post(Space &home, SetVarArray &x, IntVarArray &y)
Post constraint on x.
Definition: rel-op.cpp:475
Fake space for creation of regions.
Definition: set.hh:58
CreateIntN(void)
Perform creation and registration.
Definition: rel-op.cpp:487
bool equal(I &i, J &j)
Check whether range iterators i and j are equal.
Integer variable array.
Definition: int.hh:741
Test for ternary relation constraint
Definition: rel-op.cpp:57
Handle to region.
Definition: region.hpp:61
SetOpType
Common operations for sets.
Definition: set.hh:661
Superset ( )
Definition: set.hh:648
Complement.
Definition: set.hh:650
const unsigned int card
Maximum cardinality of an integer set.
Definition: set.hh:103
Test for n-ary partition constraint
Definition: rel-op.cpp:368
Computation spaces.
Definition: core.hpp:1362
Difference.
Definition: set.hh:665
bool solution(const SetAssignment &x) const
Test whether x is solution
Definition: rel-op.cpp:191
void init(const Gecode::IntSet &d, int cur)
Initialize with set d0 and bit-pattern cur0.
Definition: set.hh:127
CreateN(void)
Perform creation and registration.
Definition: rel-op.cpp:348
void post(Space &home, SetVarArray &x, IntVarArray &)
Post constraint on x.
Definition: rel-op.cpp:314
Help class to create and register tests.
Definition: rel-op.cpp:345
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)
NNF * r
Right subtree.
Definition: bool-expr.cpp:246
const Test::Int::Assignment & ints(void) const
Return assignment for integer variables.
Definition: set.hh:187
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.
Subset ( )
Definition: set.hh:647
Gecode::IntSet lub
The common superset for all domains.
Definition: set.hh:170
RelIntN(Gecode::SetOpType sot0, int n0, bool withConst0)
Create and register test.
Definition: rel-op.cpp:376
Intersection
Definition: set.hh:664
Integer sets.
Definition: int.hh:171
Range iterator for computing union (binary)
SetExpr inter(const SetVarArgs &x)
Intersection of set variables.
Definition: set-expr.cpp:696
union Gecode::@518::NNF::@57 u
Union depending on nodetype t.
General test support.
Definition: afc.cpp:43
Union.
Definition: set.hh:662
Passing set variables.
Definition: set.hh:490
Rel(Gecode::SetOpType sot0, Gecode::SetRelType srt0, int share0=0)
Create and register test.
Definition: rel-op.cpp:88
Node * x
Pointer to corresponding Boolean expression node.
Definition: bool-expr.cpp:253
Set variables
Definition: set.hh:129
Help class to create and register tests.
Definition: rel-op.cpp:484
Range iterator for intersection of iterators.
Disjoint union.
Definition: set.hh:663
Base class for tests with set constraints
Definition: set.hh:271
Generate all set assignments.
Definition: set.hh:158
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:114
Equality ( )
Definition: set.hh:645
Disjoint ( )
Definition: set.hh:649
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:662
Set variable array
Definition: set.hh:571
Disequality ( )
Definition: set.hh:646
RelN(Gecode::SetOpType sot0, int n0, int shared0, bool withConst0)
Create and register test.
Definition: rel-op.cpp:184
struct Gecode::@518::NNF::@57::@58 b
For binary nodes (and, or, eqv)
bool solution(const SetAssignment &x) const
Test whether x is solution
Definition: rel-op.cpp:383
Gecode toplevel namespace
Range iterator for computing set difference.
Definition: ranges-diff.hpp:47
int size(void) const
Return size of array (number of elements)
Definition: array.hpp:985
#define GECODE_NEVER
Assert that this command is never executed.
Definition: macros.hpp:60
bool solution(const SetAssignment &x) const
Test whether x is solution
Definition: rel-op.cpp:93
struct Gecode::@518::NNF::@57::@59 a
For atomic nodes.
Help class to create and register tests.
Definition: rel-op.cpp:157