Generated on Tue Jan 28 2020 00:00:00 for Gecode by doxygen 1.8.17
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: 2016-10-24 01:28:34 +0200 (Mon, 24 Oct 2016) $ by $Author: tack $
11  * $Revision: 15224 $
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  FakeSpace* fs = new FakeSpace;
254  bool eq;
255  if (withConst) {
256  Region r(*fs);
257  Iter::Ranges::NaryUnion u(r, isrs, realN);
258  IntSetRanges isr(is);
260  Iter::Ranges::NaryUnion> uu(isr, u);
261  eq = Iter::Ranges::equal(uu, xnr);
262  } else {
263  Region r(*fs);
264  Iter::Ranges::NaryUnion u(r, isrs, realN);
265  eq = Iter::Ranges::equal(u, xnr);
266  }
267  delete [] isrs;
268  delete fs;
269  return eq;
270  }
271  case SOT_INTER:
272  {
273  if (withConst) {
274  FakeSpace* fs = new FakeSpace;
275  bool eq;
276  {
277  Region r(*fs);
278  Iter::Ranges::NaryInter u(r, isrs, realN);
279  IntSetRanges isr(is);
281  Iter::Ranges::NaryInter> uu(isr, u);
282  eq = (realN == 0 ? Iter::Ranges::equal(isr, xnr) :
283  Iter::Ranges::equal(uu, xnr));
284  delete [] isrs;
285  }
286  delete fs;
287  return eq;
288  } else {
289  if (realN == 0) {
290  bool ret =
292  delete [] isrs;
293  return ret;
294  } else {
295  FakeSpace* fs = new FakeSpace;
296  bool eq;
297  {
298  Region r(*fs);
299  Iter::Ranges::NaryInter u(r,isrs, realN);
300  eq = Iter::Ranges::equal(u, xnr);
301  }
302  delete [] isrs;
303  delete fs;
304  return eq;
305  }
306  }
307  }
308  default:
309  GECODE_NEVER;
310  }
311  GECODE_NEVER;
312  return false;
313  }
315  void post(Space& home, SetVarArray& x, IntVarArray&) {
316  int size = shared == 0 ? x.size()-1 : 3;
317  SetVarArgs xs(size);
318  SetVar xn;
319  switch (shared) {
320  case 0:
321  for (int i=x.size()-1; i--;)
322  xs[i]=x[i];
323  xn = x[x.size()-1];
324  break;
325  case 1:
326  xs[0] = x[0]; xs[1] = x[0]; xs[2] = x[1]; xn = x[2];
327  break;
328  case 2:
329  xs[0] = x[0]; xs[1] = x[1]; xs[2] = x[2]; xn = x[2];
330  break;
331  case 3:
332  xs[0] = x[0]; xs[1] = x[1]; xs[2] = x[0]; xn = x[0];
333  break;
334  default:
335  GECODE_NEVER;
336  break;
337  }
338  if (!withConst)
339  Gecode::rel(home, sot, xs, xn);
340  else
341  Gecode::rel(home, sot, xs, is, xn);
342  }
343  };
344 
346  class CreateN {
347  public:
349  CreateN(void) {
350  for (int wc=0; wc<=1; wc++) {
351  for (int i=0; i<=3; i++) {
352  (void) new RelN(Gecode::SOT_UNION, i, 0, wc);
353  (void) new RelN(Gecode::SOT_DUNION, i, 0, wc);
354  (void) new RelN(Gecode::SOT_INTER, i, 0, wc);
355 
356  if (i>0) {
357  (void) new RelN(Gecode::SOT_UNION, 0, i, wc);
358  (void) new RelN(Gecode::SOT_DUNION, 0, i, wc);
359  (void) new RelN(Gecode::SOT_INTER, 0, i, wc);
360  }
361  }
362  }
363  }
364  };
365 
367 
369  class RelIntN : public SetTest {
370  private:
371  Gecode::SetOpType sot;
372  int n;
373  bool withConst;
374  IntSet is;
375  public:
377  RelIntN(Gecode::SetOpType sot0, int n0, bool withConst0)
378  : SetTest("RelOp::IntN::"+str(sot0)+"::"+str(n0)+
379  "::C"+str(withConst0 ? 1 : 0),
380  1,ds_12,false,n0)
381  , sot(sot0), n(n0), withConst(withConst0)
382  , is(0,1) {
383  }
385  bool solution(const SetAssignment& x) const {
386  int* isrs = new int[n];
387  for (int i=0; i<n; i++)
388  isrs[i] = x.ints()[i];
389 
390  IntSet iss(isrs,n);
391  CountableSetRanges xnr(x.lub, x[0]);
392 
393  switch (sot) {
394  case SOT_DUNION:
395  {
396  IntSetRanges issr(iss);
397  unsigned int cardSum = Iter::Ranges::size(issr);
398  if (cardSum != static_cast<unsigned int>(n)) {
399  delete[] isrs;
400  return false;
401  }
402  if (withConst) {
403  IntSetRanges isr(is);
404  cardSum += Iter::Ranges::size(isr);
405  }
406  CountableSetRanges xnr2(x.lub, x[0]);
407  if (cardSum != Iter::Ranges::size(xnr2)) {
408  delete[] isrs;
409  return false;
410  }
411  }
412  // fall through to union case
413  case SOT_UNION:
414  {
415  if (withConst) {
416  IntSetRanges issr(iss);
417  IntSetRanges isr(is);
419  delete[] isrs;
420  return Iter::Ranges::equal(uu, xnr);
421  } else {
422  IntSetRanges issr(iss);
423  delete[] isrs;
424  return Iter::Ranges::equal(issr, xnr);
425  }
426  }
427  case SOT_INTER:
428  {
429  bool allEqual = true;
430  for (int i=1; i<n; i++) {
431  if (isrs[i] != isrs[0]) {
432  allEqual = false;
433  break;
434  }
435  }
436  if (withConst) {
437  if (allEqual) {
438  if (n == 0) {
439  IntSetRanges isr(is);
440  delete[] isrs;
441  return Iter::Ranges::equal(isr, xnr);
442  } else {
443  Iter::Ranges::Singleton s(isrs[0],isrs[0]);
444  IntSetRanges isr(is);
446  uu(isr, s);
447  delete[] isrs;
448  return Iter::Ranges::equal(uu, xnr);
449  }
450  } else {
451  delete[] isrs;
452  return Iter::Ranges::size(xnr) == 0;
453  }
454  } else {
455  if (allEqual) {
456  if (n == 0) {
457  delete[] isrs;
459  } else {
460  Iter::Ranges::Singleton s(isrs[0],isrs[0]);
461  delete[] isrs;
462  return Iter::Ranges::equal(s, xnr);
463  }
464  } else {
465  delete[] isrs;
466  return Iter::Ranges::size(xnr) == 0;
467  }
468  }
469  }
470  default:
471  GECODE_NEVER;
472  }
473  GECODE_NEVER;
474  return false;
475  }
477  void post(Space& home, SetVarArray& x, IntVarArray& y) {
478  if (!withConst)
479  Gecode::rel(home, sot, y, x[0]);
480  else
481  Gecode::rel(home, sot, y, is, x[0]);
482  }
483  };
484 
486  class CreateIntN {
487  public:
489  CreateIntN(void) {
490  for (int wc=0; wc<=1; wc++) {
491  for (int i=0; i<=3; i++) {
492  (void) new RelIntN(Gecode::SOT_UNION, i, wc);
493  (void) new RelIntN(Gecode::SOT_DUNION, i, wc);
494  (void) new RelIntN(Gecode::SOT_INTER, i, wc);
495  }
496  }
497  }
498  };
499 
501 
503 
504 }}}
505 
506 // STATISTICS: test-set
Post propagator for SetVar x
Definition: set.hh:784
Post propagator for SetVar SetOpType SetVar y
Definition: set.hh:784
Create c
Definition: rel-op.cpp:172
bool solution(const SetAssignment &x) const
Test whether x is solution
Definition: rel-op.cpp:385
unsigned int size(I &i)
Size of all ranges of range iterator i.
Help class to create and register tests.
Definition: rel-op.cpp:157
Gecode::IntArgs i(4, 1, 2, 3, 4)
Passing set variables.
Definition: set.hh:492
Test for ternary relation constraint
Definition: rel-op.cpp:57
Test for n-ary partition constraint
Definition: rel-op.cpp:175
void post(Space &home, SetVarArray &x, IntVarArray &y)
Post constraint on x.
Definition: rel-op.cpp:477
Computation spaces.
Definition: core.hpp:1748
SetOpType
Common operations for sets.
Definition: set.hh:662
@ SRT_SUB
Subset ( )
Definition: set.hh:648
bool subset(I &i, J &j)
Check whether range iterator i is subset of range iterator j.
Integer variable array.
Definition: int.hh:744
@ SRT_SUP
Superset ( )
Definition: set.hh:649
union Gecode::@579::NNF::@61 u
Union depending on nodetype t.
Range iterator for integer sets.
Definition: int.hh:274
RelN(Gecode::SetOpType sot0, int n0, int shared0, bool withConst0)
Create and register test.
Definition: rel-op.cpp:184
Generate all set assignments.
Definition: set.hh:158
@ SOT_INTER
Intersection
Definition: set.hh:665
@ SRT_DISJ
Disjoint ( )
Definition: set.hh:650
Gecode toplevel namespace
Integer sets.
Definition: int.hh:174
const unsigned int card
Maximum cardinality of an integer set.
Definition: set.hh:105
A complement iterator spezialized for the BndSet limits.
Definition: var-imp.hpp:296
@ SRT_EQ
Equality ( )
Definition: set.hh:646
struct Gecode::@579::NNF::@61::@63 a
For atomic nodes.
Create(void)
Perform creation and registration.
Definition: rel-op.cpp:160
struct Gecode::@579::NNF::@61::@62 b
For binary nodes (and, or, eqv)
Help class to create and register tests.
Definition: rel-op.cpp:486
Range iterator for computing intersection (binary)
@ SOT_UNION
Union.
Definition: set.hh:663
Post propagator for SetVar SetOpType SetVar SetRelType r
Definition: set.hh:784
Range iterator for computing set difference.
Definition: ranges-diff.hpp:47
Help class to create and register tests.
Definition: rel-op.cpp:346
CreateIntN(void)
Perform creation and registration.
Definition: rel-op.cpp:489
Set variables
Definition: set.hh:131
Base class for tests with set constraints
Definition: set.hh:289
bool equal(I &i, J &j)
Check whether range iterators i and j are equal.
Range iterator for union of iterators.
SetRelType
Common relation types for sets.
Definition: set.hh:645
CreateN cn
Definition: rel-op.cpp:366
Iterator for Boolean operation types.
Definition: set.hh:368
#define GECODE_NEVER
Assert that this command is never executed.
Definition: macros.hpp:60
@ SRT_NQ
Disequality ( )
Definition: set.hh:647
Iterator for set relation types.
Definition: set.hh:350
Range iterator for computing union (binary)
@ SRT_CMPL
Complement.
Definition: set.hh:651
@ SOT_DUNION
Disjoint union.
Definition: set.hh:664
Rel(Gecode::SetOpType sot0, Gecode::SetRelType srt0, int share0=0)
Create and register test.
Definition: rel-op.cpp:88
void rel(Home home, FloatVar x0, FloatRelType frt, FloatVal n)
Propagates .
Definition: rel.cpp:47
bool solution(const SetAssignment &x) const
Test whether x is solution
Definition: rel-op.cpp:192
Test for n-ary partition constraint
Definition: rel-op.cpp:369
bool shared(const IntSet &, VX)
Definition: view-base.hpp:122
void init(const Gecode::IntSet &d, int cur)
Initialize with set d0 and bit-pattern cur0.
Definition: set.hh:127
Test for Region memory area
Definition: region.cpp:46
bool solution(const SetAssignment &x) const
Test whether x is solution
Definition: rel-op.cpp:93
void post(Space &home, SetVarArray &x, IntVarArray &)
Post constraint on x.
Definition: rel-op.cpp:143
CreateIntN intcn
Definition: rel-op.cpp:500
General test support.
Definition: afc.cpp:43
Range iterator producing subsets of an IntSet.
Definition: set.hh:114
Range iterator for intersection of iterators.
void post(Space &home, SetVarArray &x, IntVarArray &)
Post constraint on x.
Definition: rel-op.cpp:315
CreateN(void)
Perform creation and registration.
Definition: rel-op.cpp:349
Range iterator for singleton range.
Fake space for creation of regions.
Definition: set.hh:58
Set variable array
Definition: set.hh:572
@ SOT_MINUS
Difference.
Definition: set.hh:666
int n
Number of negative literals for node type.
Definition: bool-expr.cpp:238
SetExpr inter(const SetVarArgs &x)
Intersection of set variables.
Definition: set-expr.cpp:699
RelIntN(Gecode::SetOpType sot0, int n0, bool withConst0)
Create and register test.
Definition: rel-op.cpp:377